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