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