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