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