src/common/list.cpp

   1 ////////////////////////////////////////////////////////////////////////////////
   2 // Name:        src/common/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
   9 // Licence:     wxWindows licence
  10 ////////////////////////////////////////////////////////////////////////////////
  11
  12 // =============================================================================
  13 // declarations
  14 // =============================================================================
  15
  16 // -----------------------------------------------------------------------------
  17 // headers
  18 // -----------------------------------------------------------------------------
  19
  20 // For compilers that support precompilation, includes "wx.h".
  21 #include "wx/wxprec.h"
  22
  23 #ifdef __BORLANDC__
  24     #pragma hdrstop
  25 #endif
  26
  27 #include <stdarg.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #ifndef WX_PRECOMP
  32     #include "wx/list.h"
  33 #endif
  34
  35 #if !wxUSE_STL
  36
  37 // =============================================================================
  38 // implementation
  39 // =============================================================================
  40
  41 // -----------------------------------------------------------------------------
  42 // wxListKey
  43 // -----------------------------------------------------------------------------
  44 wxListKey wxDefaultListKey;
  45
  46 bool wxListKey::operator==(wxListKeyValue value) const
  47 {
  48     switch ( m_keyType )
  49     {
  50         default:
  51             wxFAIL_MSG(wxT("bad key type."));
  52             // let compiler optimize the line above away in release build
  53             // by not putting return here...
  54
  55         case wxKEY_STRING:
  56             return wxStrcmp(m_key.string, value.string) == 0;
  57
  58         case wxKEY_INTEGER:
  59             return m_key.integer == value.integer;
  60     }
  61 }
  62
  63 // -----------------------------------------------------------------------------
  64 // wxNodeBase
  65 // -----------------------------------------------------------------------------
  66
  67 wxNodeBase::wxNodeBase(wxListBase *list,
  68                        wxNodeBase *previous, wxNodeBase *next,
  69                        void *data, const wxListKey& key)
  70 {
  71     m_list = list;
  72     m_data = data;
  73     m_previous = previous;
  74     m_next = next;
  75
  76     switch ( key.GetKeyType() )
  77     {
  78         case wxKEY_NONE:
  79             break;
  80
  81         case wxKEY_INTEGER:
  82             m_key.integer = key.GetNumber();
  83             break;
  84
  85         case wxKEY_STRING:
  86             // to be free()d later
  87             m_key.string = wxStrdup(key.GetString());
  88             break;
  89
  90         default:
  91             wxFAIL_MSG(wxT("invalid key type"));
  92     }
  93
  94     if ( previous )
  95         previous->m_next = this;
  96
  97     if ( next )
  98         next->m_previous = this;
  99 }
 100
 101 wxNodeBase::~wxNodeBase()
 102 {
 103     // handle the case when we're being deleted from the list by the user (i.e.
 104     // not by the list itself from DeleteNode) - we must do it for
 105     // compatibility with old code
 106     if ( m_list != NULL )
 107     {
 108         if ( m_list->m_keyType == wxKEY_STRING )
 109         {
 110             free(m_key.string);
 111         }
 112
 113         m_list->DetachNode(this);
 114     }
 115 }
 116
 117 int wxNodeBase::IndexOf() const
 118 {
 119     wxCHECK_MSG( m_list, wxNOT_FOUND, wxT("node doesn't belong to a list in IndexOf"));
 120
 121     // It would be more efficient to implement IndexOf() completely inside
 122     // wxListBase (only traverse the list once), but this is probably a more
 123     // reusable way of doing it. Can always be optimized at a later date (since
 124     // IndexOf() resides in wxListBase as well) if efficiency is a problem.
 125     int i;
 126     wxNodeBase *prev = m_previous;
 127
 128     for( i = 0; prev; i++ )
 129     {
 130         prev = prev->m_previous;
 131     }
 132
 133     return i;
 134 }
 135
 136 // -----------------------------------------------------------------------------
 137 // wxListBase
 138 // -----------------------------------------------------------------------------
 139
 140 void wxListBase::Init(wxKeyType keyType)
 141 {
 142   m_nodeFirst =
 143   m_nodeLast = (wxNodeBase *) NULL;
 144   m_count = 0;
 145   m_destroy = false;
 146   m_keyType = keyType;
 147 }
 148
 149 wxListBase::wxListBase(size_t count, void *elements[])
 150 {
 151   Init();
 152
 153   for ( size_t n = 0; n < count; n++ )
 154   {
 155       Append(elements[n]);
 156   }
 157 }
 158
 159 void wxListBase::DoCopy(const wxListBase& list)
 160 {
 161     wxASSERT_MSG( !list.m_destroy,
 162                   wxT("copying list which owns it's elements is a bad idea") );
 163
 164     m_destroy = list.m_destroy;
 165     m_keyType = list.m_keyType;
 166     m_nodeFirst =
 167     m_nodeLast = (wxNodeBase *) NULL;
 168
 169     switch (m_keyType)
 170     {
 171         case wxKEY_INTEGER:
 172             {
 173                 long key;
 174                 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
 175                 {
 176                     key = node->GetKeyInteger();
 177                     Append(key, node->GetData());
 178                 }
 179                 break;
 180             }
 181
 182         case wxKEY_STRING:
 183             {
 184                 const wxChar *key;
 185                 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
 186                 {
 187                     key = node->GetKeyString();
 188                     Append(key, node->GetData());
 189                 }
 190                 break;
 191             }
 192
 193         default:
 194             {
 195                 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
 196                 {
 197                     Append(node->GetData());
 198                 }
 199                 break;
 200             }
 201     }
 202
 203     wxASSERT_MSG( m_count == list.m_count, _T("logic error in wxList::DoCopy") );
 204 }
 205
 206 wxListBase::~wxListBase()
 207 {
 208   wxNodeBase *each = m_nodeFirst;
 209   while ( each != NULL )
 210   {
 211       wxNodeBase *next = each->GetNext();
 212       DoDeleteNode(each);
 213       each = next;
 214   }
 215 }
 216
 217 wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node)
 218 {
 219     if ( !m_nodeFirst )
 220     {
 221         m_nodeFirst = node;
 222         m_nodeLast = m_nodeFirst;
 223     }
 224     else
 225     {
 226         m_nodeLast->m_next = node;
 227         m_nodeLast = node;
 228     }
 229
 230     m_count++;
 231
 232     return node;
 233 }
 234
 235 wxNodeBase *wxListBase::Append(void *object)
 236 {
 237     // all objects in a keyed list should have a key
 238     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 239                  wxT("need a key for the object to append") );
 240
 241     // we use wxDefaultListKey even though it is the default parameter value
 242     // because gcc under Mac OS X seems to miscompile this call otherwise
 243     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object,
 244                                   wxDefaultListKey);
 245
 246     return AppendCommon(node);
 247 }
 248
 249 wxNodeBase *wxListBase::Append(long key, void *object)
 250 {
 251     wxCHECK_MSG( (m_keyType == wxKEY_INTEGER) ||
 252                  (m_keyType == wxKEY_NONE && m_count == 0),
 253                  (wxNodeBase *)NULL,
 254                  wxT("can't append object with numeric key to this list") );
 255
 256     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 257     return AppendCommon(node);
 258 }
 259
 260 wxNodeBase *wxListBase::Append (const wxChar *key, void *object)
 261 {
 262     wxCHECK_MSG( (m_keyType == wxKEY_STRING) ||
 263                  (m_keyType == wxKEY_NONE && m_count == 0),
 264                  (wxNodeBase *)NULL,
 265                  wxT("can't append object with string key to this list") );
 266
 267     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 268     return AppendCommon(node);
 269 }
 270
 271 wxNodeBase *wxListBase::Insert(wxNodeBase *position, void *object)
 272 {
 273     // all objects in a keyed list should have a key
 274     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 275                  wxT("need a key for the object to insert") );
 276
 277     wxCHECK_MSG( !position || position->m_list == this, (wxNodeBase *)NULL,
 278                  wxT("can't insert before a node from another list") );
 279
 280     // previous and next node for the node being inserted
 281     wxNodeBase *prev, *next;
 282     if ( position )
 283     {
 284         prev = position->GetPrevious();
 285         next = position;
 286     }
 287     else
 288     {
 289         // inserting in the beginning of the list
 290         prev = (wxNodeBase *)NULL;
 291         next = m_nodeFirst;
 292     }
 293
 294     // wxDefaultListKey: see comment in Append() above
 295     wxNodeBase *node = CreateNode(prev, next, object, wxDefaultListKey);
 296     if ( !m_nodeFirst )
 297     {
 298         m_nodeLast = node;
 299     }
 300
 301     if ( prev == NULL )
 302     {
 303         m_nodeFirst = node;
 304     }
 305
 306     m_count++;
 307
 308     return node;
 309 }
 310
 311 wxNodeBase *wxListBase::Item(size_t n) const
 312 {
 313     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 314     {
 315         if ( n-- == 0 )
 316         {
 317             return current;
 318         }
 319     }
 320
 321     wxFAIL_MSG( wxT("invalid index in wxListBase::Item") );
 322
 323     return (wxNodeBase *)NULL;
 324 }
 325
 326 wxNodeBase *wxListBase::Find(const wxListKey& key) const
 327 {
 328     wxASSERT_MSG( m_keyType == key.GetKeyType(),
 329                   wxT("this list is not keyed on the type of this key") );
 330
 331     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 332     {
 333         if ( key == current->m_key )
 334         {
 335             return current;
 336         }
 337     }
 338
 339     // not found
 340     return (wxNodeBase *)NULL;
 341 }
 342
 343 wxNodeBase *wxListBase::Find(const void *object) const
 344 {
 345     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 346     {
 347         if ( current->GetData() == object )
 348             return current;
 349     }
 350
 351     // not found
 352     return (wxNodeBase *)NULL;
 353 }
 354
 355 int wxListBase::IndexOf(void *object) const
 356 {
 357     wxNodeBase *node = Find( object );
 358
 359     return node ? node->IndexOf() : wxNOT_FOUND;
 360 }
 361
 362 void wxListBase::DoDeleteNode(wxNodeBase *node)
 363 {
 364     // free node's data
 365     if ( m_keyType == wxKEY_STRING )
 366     {
 367         free(node->m_key.string);
 368     }
 369
 370     if ( m_destroy )
 371     {
 372         node->DeleteData();
 373     }
 374
 375     // so that the node knows that it's being deleted by the list
 376     node->m_list = NULL;
 377     delete node;
 378 }
 379
 380 wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
 381 {
 382     wxCHECK_MSG( node, NULL, wxT("detaching NULL wxNodeBase") );
 383     wxCHECK_MSG( node->m_list == this, NULL,
 384                  wxT("detaching node which is not from this list") );
 385
 386     // update the list
 387     wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
 388                                                 : &m_nodeFirst;
 389     wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
 390                                             : &m_nodeLast;
 391
 392     *prevNext = node->GetNext();
 393     *nextPrev = node->GetPrevious();
 394
 395     m_count--;
 396
 397     // mark the node as not belonging to this list any more
 398     node->m_list = NULL;
 399
 400     return node;
 401 }
 402
 403 bool wxListBase::DeleteNode(wxNodeBase *node)
 404 {
 405     if ( !DetachNode(node) )
 406         return false;
 407
 408     DoDeleteNode(node);
 409
 410     return true;
 411 }
 412
 413 bool wxListBase::DeleteObject(void *object)
 414 {
 415     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 416     {
 417         if ( current->GetData() == object )
 418         {
 419             DeleteNode(current);
 420             return true;
 421         }
 422     }
 423
 424     // not found
 425     return false;
 426 }
 427
 428 void wxListBase::Clear()
 429 {
 430     wxNodeBase *current = m_nodeFirst;
 431     while ( current )
 432     {
 433         wxNodeBase *next = current->GetNext();
 434         DoDeleteNode(current);
 435         current = next;
 436     }
 437
 438     m_nodeFirst =
 439     m_nodeLast = (wxNodeBase *)NULL;
 440
 441     m_count = 0;
 442 }
 443
 444 void wxListBase::ForEach(wxListIterateFunction F)
 445 {
 446     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 447     {
 448         (*F)(current->GetData());
 449     }
 450 }
 451
 452 void *wxListBase::FirstThat(wxListIterateFunction F)
 453 {
 454     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 455     {
 456         if ( (*F)(current->GetData()) )
 457             return current->GetData();
 458     }
 459
 460     return (wxNodeBase *)NULL;
 461 }
 462
 463 void *wxListBase::LastThat(wxListIterateFunction F)
 464 {
 465     for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() )
 466     {
 467         if ( (*F)(current->GetData()) )
 468             return current->GetData();
 469     }
 470
 471     return (wxNodeBase *)NULL;
 472 }
 473
 474 // (stefan.hammes@urz.uni-heidelberg.de)
 475 //
 476 // function for sorting lists. the concept is borrowed from 'qsort'.
 477 // by giving a sort function, arbitrary lists can be sorted.
 478 // method:
 479 // - put wxObject pointers into an array
 480 // - sort the array with qsort
 481 // - put back the sorted wxObject pointers into the list
 482 //
 483 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
 484 //       so dereference right!
 485 // EXAMPLE:
 486 //   int listcompare(const void *arg1, const void *arg2)
 487 //   {
 488 //      return(compare(**(wxString **)arg1,
 489 //                     **(wxString **)arg2));
 490 //   }
 491 //
 492 //   void main()
 493 //   {
 494 //     wxListBase list;
 495 //
 496 //     list.Append(new wxString("DEF"));
 497 //     list.Append(new wxString("GHI"));
 498 //     list.Append(new wxString("ABC"));
 499 //     list.Sort(listcompare);
 500 //   }
 501
 502 void wxListBase::Sort(const wxSortCompareFunction compfunc)
 503 {
 504     // allocate an array for the wxObject pointers of the list
 505     const size_t num = GetCount();
 506     void **objArray = new void *[num];
 507     void **objPtr = objArray;
 508
 509     // go through the list and put the pointers into the array
 510     wxNodeBase *node;
 511     for ( node = GetFirst(); node; node = node->GetNext() )
 512     {
 513         *objPtr++ = node->GetData();
 514     }
 515
 516     // sort the array
 517     qsort((void *)objArray,num,sizeof(wxObject *),
 518 #ifdef __WXWINCE__
 519         (int (__cdecl *)(const void *,const void *))
 520 #endif
 521         compfunc);
 522
 523     // put the sorted pointers back into the list
 524     objPtr = objArray;
 525     for ( node = GetFirst(); node; node = node->GetNext() )
 526     {
 527         node->SetData(*objPtr++);
 528     }
 529
 530     // free the array
 531     delete[] objArray;
 532 }
 533
 534 void wxListBase::Reverse()
 535 {
 536     wxNodeBase* node = m_nodeFirst;
 537     wxNodeBase* tmp;
 538
 539     while (node)
 540     {
 541         // swap prev and next pointers
 542         tmp = node->m_next;
 543         node->m_next = node->m_previous;
 544         node->m_previous = tmp;
 545
 546         // this is the node that was next before swapping
 547         node = tmp;
 548     }
 549
 550     // swap first and last node
 551     tmp = m_nodeFirst; m_nodeFirst = m_nodeLast; m_nodeLast = tmp;
 552 }
 553
 554 void wxListBase::DeleteNodes(wxNodeBase* first, wxNodeBase* last)
 555 {
 556     wxNodeBase* node = first;
 557
 558     while (node != last)
 559     {
 560         wxNodeBase* next = node->GetNext();
 561         DeleteNode(node);
 562         node = next;
 563     }
 564 }
 565
 566 // ============================================================================
 567 // compatibility section from now on
 568 // ============================================================================
 569
 570 #ifdef wxLIST_COMPATIBILITY
 571
 572 // -----------------------------------------------------------------------------
 573 // wxList (a.k.a. wxObjectList)
 574 // -----------------------------------------------------------------------------
 575
 576 IMPLEMENT_DYNAMIC_CLASS(wxList, wxObject)
 577
 578 wxList::wxList( int key_type )
 579     : wxObjectList( (wxKeyType)key_type )
 580 {
 581 }
 582
 583 void wxObjectListNode::DeleteData()
 584 {
 585     delete (wxObject *)GetData();
 586 }
 587
 588 // ----------------------------------------------------------------------------
 589 // wxStringList
 590 // ----------------------------------------------------------------------------
 591
 592 static inline wxChar* MYcopystring(const wxChar* s)
 593 {
 594     wxChar* copy = new wxChar[wxStrlen(s) + 1];
 595     return wxStrcpy(copy, s);
 596 }
 597
 598 IMPLEMENT_DYNAMIC_CLASS(wxStringList, wxObject)
 599
 600 // instead of WX_DEFINE_LIST(wxStringListBase) we define this function
 601 // ourselves
 602 void wxStringListNode::DeleteData()
 603 {
 604     delete [] (char *)GetData();
 605 }
 606
 607 bool wxStringList::Delete(const wxChar *s)
 608 {
 609     wxStringListNode *current;
 610
 611     for ( current = GetFirst(); current; current = current->GetNext() )
 612     {
 613         if ( wxStrcmp(current->GetData(), s) == 0 )
 614         {
 615             DeleteNode(current);
 616             return true;
 617         }
 618     }
 619
 620     // not found
 621     return false;
 622 }
 623
 624 void wxStringList::DoCopy(const wxStringList& other)
 625 {
 626     wxASSERT( GetCount() == 0 );    // this list must be empty before copying!
 627
 628     size_t count = other.GetCount();
 629     for ( size_t n = 0; n < count; n++ )
 630     {
 631         Add(other.Item(n)->GetData());
 632     }
 633 }
 634
 635 wxStringList::wxStringList()
 636 {
 637     DeleteContents(true);
 638 }
 639
 640 // Variable argument list, terminated by a zero
 641 // Makes new storage for the strings
 642 wxStringList::wxStringList (const wxChar *first, ...)
 643 {
 644   DeleteContents(true);
 645   if ( !first )
 646     return;
 647
 648   va_list ap;
 649   va_start(ap, first);
 650
 651   const wxChar *s = first;
 652   for (;;)
 653   {
 654       Add(s);
 655
 656       // icc gives this warning in its own va_arg() macro, argh
 657 #ifdef __INTELC__
 658     #pragma warning(push)
 659     #pragma warning(disable: 1684)
 660 #endif
 661
 662       s = va_arg(ap, const wxChar *);
 663
 664 #ifdef __INTELC__
 665     #pragma warning(pop)
 666 #endif
 667
 668       if ( !s )
 669           break;
 670   }
 671
 672   va_end(ap);
 673 }
 674
 675 // Only makes new strings if arg is true
 676 wxChar **wxStringList::ListToArray(bool new_copies) const
 677 {
 678     wxChar **string_array = new wxChar *[GetCount()];
 679     wxStringListNode *node = GetFirst();
 680     for (size_t i = 0; i < GetCount(); i++)
 681     {
 682         wxChar *s = node->GetData();
 683         if ( new_copies )
 684             string_array[i] = MYcopystring(s);
 685         else
 686             string_array[i] = s;
 687         node = node->GetNext();
 688     }
 689
 690     return string_array;
 691 }
 692
 693 // Checks whether s is a member of the list
 694 bool wxStringList::Member(const wxChar *s) const
 695 {
 696     for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
 697     {
 698         const wxChar *s1 = node->GetData();
 699         if (s == s1 || wxStrcmp (s, s1) == 0)
 700             return true;
 701     }
 702
 703     return false;
 704 }
 705
 706 #ifdef __WXWINCE__
 707 extern "C" int __cdecl
 708 #else
 709 extern "C" int LINKAGEMODE
 710 #endif
 711
 712 wx_comparestrings(const void *arg1, const void *arg2)
 713 {
 714   wxChar **s1 = (wxChar **) arg1;
 715   wxChar **s2 = (wxChar **) arg2;
 716
 717   return wxStrcmp (*s1, *s2);
 718 }
 719
 720 // Sort a list of strings - deallocates old nodes, allocates new
 721 void wxStringList::Sort()
 722 {
 723     size_t N = GetCount();
 724     wxChar **array = new wxChar *[N];
 725     wxStringListNode *node;
 726
 727     size_t i = 0;
 728     for ( node = GetFirst(); node; node = node->GetNext() )
 729     {
 730         array[i++] = node->GetData();
 731     }
 732
 733     qsort (array, N, sizeof (wxChar *), wx_comparestrings);
 734
 735     i = 0;
 736     for ( node = GetFirst(); node; node = node->GetNext() )
 737         node->SetData( array[i++] );
 738
 739     delete [] array;
 740 }
 741
 742 wxNode *wxStringList::Add(const wxChar *s)
 743 {
 744     return (wxNode *)(wxStringListBase::Node *)
 745             wxStringListBase::Append(MYcopystring(s));
 746 }
 747
 748 wxNode *wxStringList::Prepend(const wxChar *s)
 749 {
 750     return (wxNode *)(wxStringListBase::Node *)
 751             wxStringListBase::Insert(MYcopystring(s));
 752 }
 753
 754 #endif // wxLIST_COMPATIBILITY
 755
 756 #else // wxUSE_STL = 1
 757
 758     #include "wx/listimpl.cpp"
 759     WX_DEFINE_LIST(wxObjectList)
 760
 761 // with wxUSE_STL wxStringList contains wxString objects, not pointers
 762 void _WX_LIST_HELPER_wxStringListBase::DeleteFunction( wxString WXUNUSED(X) )
 763 {
 764 }
 765
 766 wxStringListBase::BaseListType wxStringListBase::EmptyList;
 767
 768 #endif // !wxUSE_STL