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