src/common/list.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // Name:        list.cpp
   3 // Purpose:     wxList implementation
   4 // Author:      Julian Smart
   5 // Modified by: VZ at 16/11/98: WX_DECLARE_LIST() and typesafe lists added
   6 // Created:     04/01/98
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c) Julian Smart and Markus Holzem
   9 // Licence:     wxWindows license
  10 ////////////////////////////////////////////////////////////////////////////////
  11
  12 // =============================================================================
  13 // declarations
  14 // =============================================================================
  15
  16 // -----------------------------------------------------------------------------
  17 // headers
  18 // -----------------------------------------------------------------------------
  19 #ifdef __GNUG__
  20 #pragma implementation "list.h"
  21 #endif
  22
  23 // For compilers that support precompilation, includes "wx.h".
  24 #include "wx/wxprec.h"
  25
  26 #ifdef __BORLANDC__
  27     #pragma hdrstop
  28 #endif
  29
  30 #include <stdarg.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #ifndef WX_PRECOMP
  35     #include "wx/defs.h"
  36     #include "wx/list.h"
  37     #include "wx/utils.h"   // for copystring() (beurk...)
  38 #endif
  39
  40 // Sun CC compatibility (interference with xview/pkg.h, apparently...)
  41 // But XView is no longer supported.
  42 /*
  43 #if defined (SUN_CC) || defined(__SUNCC__) && defined(__XVIEW__)
  44     #undef va_start
  45     #undef va_end
  46     #undef va_arg
  47     #undef va_list
  48 #endif
  49 */
  50
  51 // =============================================================================
  52 // implementation
  53 // =============================================================================
  54
  55 // -----------------------------------------------------------------------------
  56 // wxListKey
  57 // -----------------------------------------------------------------------------
  58
  59 wxListKey wxDefaultListKey;
  60
  61 bool wxListKey::operator==(wxListKeyValue value) const
  62 {
  63     switch ( m_keyType )
  64     {
  65         default:
  66             wxFAIL_MSG("bad key type.");
  67             // let compiler optimize the line above away in release build
  68             // by not putting return here...
  69
  70         case wxKEY_STRING:
  71             return strcmp(m_key.string, value.string) == 0;
  72
  73         case wxKEY_INTEGER:
  74             return m_key.integer == value.integer;
  75     }
  76 }
  77
  78 // -----------------------------------------------------------------------------
  79 // wxNodeBase
  80 // -----------------------------------------------------------------------------
  81
  82 wxNodeBase::wxNodeBase(wxListBase *list,
  83                        wxNodeBase *previous, wxNodeBase *next,
  84                        void *data, const wxListKey& key)
  85 {
  86     m_list = list;
  87     m_data = data;
  88     m_previous = previous;
  89     m_next = next;
  90
  91     switch ( key.GetKeyType() )
  92     {
  93         case wxKEY_NONE:
  94             break;
  95
  96         case wxKEY_INTEGER:
  97             m_key.integer = key.GetNumber();
  98             break;
  99
 100         case wxKEY_STRING:
 101             // to be free()d later
 102             m_key.string = strdup(key.GetString());
 103             break;
 104
 105         default:
 106             wxFAIL_MSG("invalid key type");
 107     }
 108
 109     if ( previous )
 110         previous->m_next = this;
 111
 112     if ( next )
 113         next->m_previous = this;
 114 }
 115
 116 wxNodeBase::~wxNodeBase()
 117 {
 118     // handle the case when we're being deleted from the list by the user (i.e.
 119     // not by the list itself from DeleteNode) - we must do it for
 120     // compatibility with old code
 121     if ( m_list != NULL )
 122     {
 123         if ( m_list->m_keyType == wxKEY_STRING )
 124         {
 125             free(m_key.string);
 126         }
 127
 128         m_list->DetachNode(this);
 129     }
 130 }
 131
 132 int wxNodeBase::IndexOf() const
 133 {
 134     wxCHECK_MSG( m_list, NOT_FOUND, "node doesn't belong to a list in IndexOf");
 135
 136     // It would be more efficient to implement IndexOf() completely inside
 137     // wxListBase (only traverse the list once), but this is probably a more
 138     // reusable way of doing it. Can always be optimized at a later date (since
 139     // IndexOf() resides in wxListBase as well) if efficiency is a problem.
 140     int i;
 141     wxNodeBase *prev = m_previous;
 142
 143     for( i = 0; prev; i++ )
 144     {
 145         prev = prev->m_previous;
 146     }
 147
 148     return i;
 149 }
 150
 151 // -----------------------------------------------------------------------------
 152 // wxListBase
 153 // -----------------------------------------------------------------------------
 154
 155 void wxListBase::Init(wxKeyType keyType)
 156 {
 157   m_nodeFirst =
 158   m_nodeLast = (wxNodeBase *) NULL;
 159   m_count = 0;
 160   m_destroy = FALSE;
 161   m_keyType = keyType;
 162 }
 163
 164 wxListBase::wxListBase(size_t count, void *elements[])
 165 {
 166   Init();
 167
 168   for ( size_t n = 0; n < count; n++ )
 169   {
 170       Append(elements[n]);
 171   }
 172 }
 173
 174 void wxListBase::DoCopy(const wxListBase& list)
 175 {
 176     wxASSERT_MSG( !list.m_destroy,
 177                   "copying list which owns it's elements is a bad idea" );
 178
 179     m_count = list.m_count;
 180     m_destroy = list.m_destroy;
 181     m_keyType = list.m_keyType;
 182     m_nodeFirst =
 183     m_nodeLast = (wxNodeBase *) NULL;
 184
 185     for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
 186     {
 187         Append(node);
 188     }
 189 }
 190
 191 wxListBase::~wxListBase()
 192 {
 193   wxNodeBase *each = m_nodeFirst;
 194   while ( each != NULL )
 195   {
 196       wxNodeBase *next = each->GetNext();
 197       DoDeleteNode(each);
 198       each = next;
 199   }
 200 }
 201
 202 wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node)
 203 {
 204     if ( !m_nodeFirst )
 205     {
 206         m_nodeFirst = node;
 207         m_nodeLast = m_nodeFirst;
 208     }
 209     else
 210     {
 211         m_nodeLast->m_next = node;
 212         m_nodeLast = node;
 213     }
 214
 215     m_count++;
 216
 217     return node;
 218 }
 219
 220 wxNodeBase *wxListBase::Append(void *object)
 221 {
 222     // all objects in a keyed list should have a key
 223     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 224                  "need a key for the object to append" );
 225
 226     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object);
 227
 228     return AppendCommon(node);
 229 }
 230
 231 wxNodeBase *wxListBase::Append(long key, void *object)
 232 {
 233     wxCHECK_MSG( (m_keyType == wxKEY_INTEGER) ||
 234                  (m_keyType == wxKEY_NONE && m_count == 0),
 235                  (wxNodeBase *)NULL,
 236                  "can't append object with numeric key to this list" );
 237
 238     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 239     return AppendCommon(node);
 240 }
 241
 242 wxNodeBase *wxListBase::Append (const char *key, void *object)
 243 {
 244     wxCHECK_MSG( (m_keyType == wxKEY_STRING) ||
 245                  (m_keyType == wxKEY_NONE && m_count == 0),
 246                  (wxNodeBase *)NULL,
 247                  "can't append object with string key to this list" );
 248
 249     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 250     return AppendCommon(node);
 251 }
 252
 253 wxNodeBase *wxListBase::Insert(wxNodeBase *position, void *object)
 254 {
 255     // all objects in a keyed list should have a key
 256     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 257                  "need a key for the object to insert" );
 258
 259     wxCHECK_MSG( !position || position->m_list == this, (wxNodeBase *)NULL,
 260                  "can't insert before a node from another list" );
 261
 262     // previous and next node for the node being inserted
 263     wxNodeBase *prev, *next;
 264     if ( position )
 265     {
 266         prev = position->GetPrevious();
 267         next = position;
 268     }
 269     else
 270     {
 271         // inserting in the beginning of the list
 272         prev = (wxNodeBase *)NULL;
 273         next = m_nodeFirst;
 274     }
 275
 276     wxNodeBase *node = CreateNode(prev, next, object);
 277     if ( !m_nodeFirst )
 278     {
 279         m_nodeLast = node;
 280     }
 281
 282     if ( prev == NULL )
 283     {
 284         m_nodeFirst = node;
 285     }
 286
 287     m_count++;
 288
 289     return node;
 290 }
 291
 292 wxNodeBase *wxListBase::Item(size_t n) const
 293 {
 294     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 295     {
 296         if ( n-- == 0 )
 297         {
 298             return current;
 299         }
 300     }
 301
 302     wxFAIL_MSG( "invalid index in wxListBase::Item" );
 303
 304     return (wxNodeBase *)NULL;
 305 }
 306
 307 wxNodeBase *wxListBase::Find(const wxListKey& key) const
 308 {
 309     wxASSERT_MSG( m_keyType == key.GetKeyType(),
 310                   "this list is not keyed on the type of this key" );
 311
 312     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 313     {
 314         if ( key == current->m_key )
 315         {
 316             return current;
 317         }
 318     }
 319
 320     // not found
 321     return (wxNodeBase *)NULL;
 322 }
 323
 324 wxNodeBase *wxListBase::Find(void *object) const
 325 {
 326     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 327     {
 328         if ( current->GetData() == object )
 329             return current;
 330     }
 331
 332     // not found
 333     return (wxNodeBase *)NULL;
 334 }
 335
 336 int wxListBase::IndexOf(void *object) const
 337 {
 338     wxNodeBase *node = Find( object );
 339
 340     return node ? node->IndexOf() : NOT_FOUND;
 341 }
 342
 343 void wxListBase::DoDeleteNode(wxNodeBase *node)
 344 {
 345     // free node's data
 346     if ( m_keyType == wxKEY_STRING )
 347     {
 348         free(node->m_key.string);
 349     }
 350
 351     if ( m_destroy )
 352     {
 353         node->DeleteData();
 354     }
 355
 356     // so that the node knows that it's being deleted by the list
 357     node->m_list = NULL;
 358     delete node;
 359 }
 360
 361 wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
 362 {
 363     wxCHECK_MSG( node, NULL, "detaching NULL wxNodeBase" );
 364     wxCHECK_MSG( node->m_list == this, NULL,
 365                  "detaching node which is not from this list" );
 366
 367     // update the list
 368     wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
 369                                                 : &m_nodeFirst;
 370     wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
 371                                             : &m_nodeLast;
 372
 373     *prevNext = node->GetNext();
 374     *nextPrev = node->GetPrevious();
 375
 376     m_count--;
 377
 378     // mark the node as not belonging to this list any more
 379     node->m_list = NULL;
 380
 381     return node;
 382 }
 383
 384 bool wxListBase::DeleteNode(wxNodeBase *node)
 385 {
 386     if ( !DetachNode(node) )
 387         return FALSE;
 388
 389     DoDeleteNode(node);
 390
 391     return TRUE;
 392 }
 393
 394 bool wxListBase::DeleteObject(void *object)
 395 {
 396     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 397     {
 398         if ( current->GetData() == object )
 399         {
 400             DeleteNode(current);
 401             return TRUE;
 402         }
 403     }
 404
 405     // not found
 406     return FALSE;
 407 }
 408
 409 void wxListBase::Clear()
 410 {
 411     wxNodeBase *current = m_nodeFirst;
 412     while ( current )
 413     {
 414         wxNodeBase *next = current->GetNext();
 415         DoDeleteNode(current);
 416         current = next;
 417     }
 418
 419     m_nodeFirst =
 420     m_nodeLast = (wxNodeBase *)NULL;
 421
 422     m_count = 0;
 423 }
 424
 425 void wxListBase::ForEach(wxListIterateFunction F)
 426 {
 427     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 428     {
 429         (*F)(current->GetData());
 430     }
 431 }
 432
 433 void *wxListBase::FirstThat(wxListIterateFunction F)
 434 {
 435     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 436     {
 437         if ( (*F)(current->GetData()) )
 438             return current->GetData();
 439     }
 440
 441     return (wxNodeBase *)NULL;
 442 }
 443
 444 void *wxListBase::LastThat(wxListIterateFunction F)
 445 {
 446     for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() )
 447     {
 448         if ( (*F)(current->GetData()) )
 449             return current->GetData();
 450     }
 451
 452     return (wxNodeBase *)NULL;
 453 }
 454
 455 // (stefan.hammes@urz.uni-heidelberg.de)
 456 //
 457 // function for sorting lists. the concept is borrowed from 'qsort'.
 458 // by giving a sort function, arbitrary lists can be sorted.
 459 // method:
 460 // - put wxObject pointers into an array
 461 // - sort the array with qsort
 462 // - put back the sorted wxObject pointers into the list
 463 //
 464 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
 465 //       so dereference right!
 466 // EXAMPLE:
 467 //   int listcompare(const void *arg1, const void *arg2)
 468 //   {
 469 //      return(compare(**(wxString **)arg1,
 470 //                     **(wxString **)arg2));
 471 //   }
 472 //
 473 //   void main()
 474 //   {
 475 //     wxListBase list;
 476 //
 477 //     list.Append(new wxString("DEF"));
 478 //     list.Append(new wxString("GHI"));
 479 //     list.Append(new wxString("ABC"));
 480 //     list.Sort(listcompare);
 481 //   }
 482
 483 void wxListBase::Sort(const wxSortCompareFunction compfunc)
 484 {
 485     // allocate an array for the wxObject pointers of the list
 486     const size_t num = GetCount();
 487     void **objArray = new void *[num];
 488     void **objPtr = objArray;
 489
 490     // go through the list and put the pointers into the array
 491     wxNodeBase *node;
 492     for ( node = GetFirst(); node; node = node->Next() )
 493     {
 494         *objPtr++ = node->Data();
 495     }
 496
 497     // sort the array
 498     qsort((void *)objArray,num,sizeof(wxObject *),compfunc);
 499
 500     // put the sorted pointers back into the list
 501     objPtr = objArray;
 502     for ( node = GetFirst(); node; node = node->Next() )
 503     {
 504         node->SetData(*objPtr++);
 505     }
 506
 507     // free the array
 508     delete[] objArray;
 509 }
 510
 511 // -----------------------------------------------------------------------------
 512 // wxList (a.k.a. wxObjectList)
 513 // -----------------------------------------------------------------------------
 514
 515 void wxObjectListNode::DeleteData()
 516 {
 517     delete (wxObject *)GetData();
 518 }
 519
 520 // -----------------------------------------------------------------------------
 521 // wxStringList
 522 // -----------------------------------------------------------------------------
 523
 524 // instead of WX_DEFINE_LIST(wxStringListBase) we define this function
 525 // ourselves
 526 void wxStringListNode::DeleteData()
 527 {
 528     delete [] (char *)GetData();
 529 }
 530
 531 bool wxStringList::Delete(const char *s)
 532 {
 533     wxStringListNode *current;
 534
 535     for ( current = GetFirst(); current; current = current->GetNext() )
 536     {
 537         if ( strcmp(current->GetData(), s) == 0 )
 538         {
 539             DeleteNode(current);
 540             return TRUE;
 541         }
 542     }
 543
 544     // not found
 545     return FALSE;
 546 }
 547
 548 void wxStringList::DoCopy(const wxStringList& other)
 549 {
 550     wxASSERT( GetCount() == 0 );    // this list must be empty before copying!
 551
 552     size_t count = other.GetCount();
 553     for ( size_t n = 0; n < count; n++ )
 554     {
 555         Add(other.Item(n)->GetData());
 556     }
 557 }
 558
 559 // Variable argument list, terminated by a zero
 560 // Makes new storage for the strings
 561 wxStringList::wxStringList (const char *first, ...)
 562 {
 563   if ( !first )
 564     return;
 565
 566   va_list ap;
 567   va_start(ap, first);
 568
 569   const char *s = first;
 570   for (;;)
 571   {
 572       Add(s);
 573
 574       s = va_arg(ap, const char *);
 575       //    if (s == NULL)
 576 #ifdef __WXMSW__
 577       if ((int) s == 0)
 578 #else
 579       if ((long) s == 0)
 580 #endif
 581           break;
 582   }
 583
 584   va_end(ap);
 585 }
 586
 587 // Only makes new strings if arg is TRUE
 588 char **wxStringList::ListToArray(bool new_copies) const
 589 {
 590     char **string_array = new char *[GetCount()];
 591     wxStringListNode *node = GetFirst();
 592     for (size_t i = 0; i < GetCount(); i++)
 593     {
 594         char *s = node->GetData();
 595         if ( new_copies )
 596             string_array[i] = copystring(s);
 597         else
 598             string_array[i] = s;
 599         node = node->GetNext();
 600     }
 601
 602     return string_array;
 603 }
 604
 605 // Checks whether s is a member of the list
 606 bool wxStringList::Member(const char *s) const
 607 {
 608     for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
 609     {
 610         const char *s1 = node->GetData();
 611         if (s == s1 || strcmp (s, s1) == 0)
 612             return TRUE;
 613     }
 614
 615     return FALSE;
 616 }
 617
 618 static int
 619 wx_comparestrings(const void *arg1, const void *arg2)
 620 {
 621   char **s1 = (char **) arg1;
 622   char **s2 = (char **) arg2;
 623
 624   return strcmp (*s1, *s2);
 625 }
 626
 627 // Sort a list of strings - deallocates old nodes, allocates new
 628 void wxStringList::Sort()
 629 {
 630     size_t N = GetCount();
 631     char **array = new char *[N];
 632     wxStringListNode *node;
 633
 634     size_t i = 0;
 635     for ( node = GetFirst(); node; node = node->GetNext() )
 636     {
 637         array[i++] = node->GetData();
 638     }
 639
 640     qsort (array, N, sizeof (char *), wx_comparestrings);
 641
 642     i = 0;
 643     for ( node = GetFirst(); node; node = node->GetNext() )
 644         node->SetData( array[i++] );
 645
 646     delete [] array;
 647 }
 648