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