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 #ifdef __GNUG__
  20 #pragma implementation "list.h"
  21 #endif
  22
  23 // For compilers that support precompilation, includes "wx.h".
  24 #include "wx/wxprec.h"
  25
  26 #ifdef __BORLANDC__
  27     #pragma hdrstop
  28 #endif
  29
  30 #include <stdarg.h>
  31 #include <stdlib.h>
  32 #include <string.h>
  33
  34 #ifndef WX_PRECOMP
  35     #include "wx/defs.h"
  36     #include "wx/list.h"
  37     #include "wx/utils.h"   // for copystring() (beurk...)
  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("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 strcmp(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 = strdup(key.GetString());
  92             break;
  93
  94         default:
  95             wxFAIL_MSG("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, "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                   "copying list which owns it's elements is a bad idea" );
 167
 168     m_count = list.m_count;
 169     m_destroy = list.m_destroy;
 170     m_keyType = list.m_keyType;
 171     m_nodeFirst =
 172     m_nodeLast = (wxNodeBase *) NULL;
 173
 174     for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
 175     {
 176         Append(node);
 177     }
 178 }
 179
 180 wxListBase::~wxListBase()
 181 {
 182   wxNodeBase *each = m_nodeFirst;
 183   while ( each != NULL )
 184   {
 185       wxNodeBase *next = each->GetNext();
 186       DoDeleteNode(each);
 187       each = next;
 188   }
 189 }
 190
 191 wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node)
 192 {
 193     if ( !m_nodeFirst )
 194     {
 195         m_nodeFirst = node;
 196         m_nodeLast = m_nodeFirst;
 197     }
 198     else
 199     {
 200         m_nodeLast->m_next = node;
 201         m_nodeLast = node;
 202     }
 203
 204     m_count++;
 205
 206     return node;
 207 }
 208
 209 wxNodeBase *wxListBase::Append(void *object)
 210 {
 211     // all objects in a keyed list should have a key
 212     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 213                  "need a key for the object to append" );
 214
 215     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object);
 216
 217     return AppendCommon(node);
 218 }
 219
 220 wxNodeBase *wxListBase::Append(long key, void *object)
 221 {
 222     wxCHECK_MSG( (m_keyType == wxKEY_INTEGER) ||
 223                  (m_keyType == wxKEY_NONE && m_count == 0),
 224                  (wxNodeBase *)NULL,
 225                  "can't append object with numeric key to this list" );
 226
 227     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 228     return AppendCommon(node);
 229 }
 230
 231 wxNodeBase *wxListBase::Append (const char *key, void *object)
 232 {
 233     wxCHECK_MSG( (m_keyType == wxKEY_STRING) ||
 234                  (m_keyType == wxKEY_NONE && m_count == 0),
 235                  (wxNodeBase *)NULL,
 236                  "can't append object with string key to this list" );
 237
 238     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 239     return AppendCommon(node);
 240 }
 241
 242 wxNodeBase *wxListBase::Insert(wxNodeBase *position, void *object)
 243 {
 244     // all objects in a keyed list should have a key
 245     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 246                  "need a key for the object to insert" );
 247
 248     wxCHECK_MSG( !position || position->m_list == this, (wxNodeBase *)NULL,
 249                  "can't insert before a node from another list" );
 250
 251     // previous and next node for the node being inserted
 252     wxNodeBase *prev, *next;
 253     if ( position )
 254     {
 255         prev = position->GetPrevious();
 256         next = position;
 257     }
 258     else
 259     {
 260         // inserting in the beginning of the list
 261         prev = (wxNodeBase *)NULL;
 262         next = m_nodeFirst;
 263     }
 264
 265     wxNodeBase *node = CreateNode(prev, next, object);
 266     if ( !m_nodeFirst )
 267     {
 268         m_nodeLast = node;
 269     }
 270
 271     if ( prev == NULL )
 272     {
 273         m_nodeFirst = node;
 274     }
 275
 276     m_count++;
 277
 278     return node;
 279 }
 280
 281 wxNodeBase *wxListBase::Item(size_t n) const
 282 {
 283     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 284     {
 285         if ( n-- == 0 )
 286         {
 287             return current;
 288         }
 289     }
 290
 291     wxFAIL_MSG( "invalid index in wxListBase::Item" );
 292
 293     return (wxNodeBase *)NULL;
 294 }
 295
 296 wxNodeBase *wxListBase::Find(const wxListKey& key) const
 297 {
 298     wxASSERT_MSG( m_keyType == key.GetKeyType(),
 299                   "this list is not keyed on the type of this key" );
 300
 301     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 302     {
 303         if ( key == current->m_key )
 304         {
 305             return current;
 306         }
 307     }
 308
 309     // not found
 310     return (wxNodeBase *)NULL;
 311 }
 312
 313 wxNodeBase *wxListBase::Find(void *object) const
 314 {
 315     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 316     {
 317         if ( current->GetData() == object )
 318             return current;
 319     }
 320
 321     // not found
 322     return (wxNodeBase *)NULL;
 323 }
 324
 325 int wxListBase::IndexOf(void *object) const
 326 {
 327     wxNodeBase *node = Find( object );
 328
 329     return node ? node->IndexOf() : wxNOT_FOUND;
 330 }
 331
 332 void wxListBase::DoDeleteNode(wxNodeBase *node)
 333 {
 334     // free node's data
 335     if ( m_keyType == wxKEY_STRING )
 336     {
 337         free(node->m_key.string);
 338     }
 339
 340     if ( m_destroy )
 341     {
 342         node->DeleteData();
 343     }
 344
 345     // so that the node knows that it's being deleted by the list
 346     node->m_list = NULL;
 347     delete node;
 348 }
 349
 350 wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
 351 {
 352     wxCHECK_MSG( node, NULL, "detaching NULL wxNodeBase" );
 353     wxCHECK_MSG( node->m_list == this, NULL,
 354                  "detaching node which is not from this list" );
 355
 356     // update the list
 357     wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
 358                                                 : &m_nodeFirst;
 359     wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
 360                                             : &m_nodeLast;
 361
 362     *prevNext = node->GetNext();
 363     *nextPrev = node->GetPrevious();
 364
 365     m_count--;
 366
 367     // mark the node as not belonging to this list any more
 368     node->m_list = NULL;
 369
 370     return node;
 371 }
 372
 373 bool wxListBase::DeleteNode(wxNodeBase *node)
 374 {
 375     if ( !DetachNode(node) )
 376         return FALSE;
 377
 378     DoDeleteNode(node);
 379
 380     return TRUE;
 381 }
 382
 383 bool wxListBase::DeleteObject(void *object)
 384 {
 385     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 386     {
 387         if ( current->GetData() == object )
 388         {
 389             DeleteNode(current);
 390             return TRUE;
 391         }
 392     }
 393
 394     // not found
 395     return FALSE;
 396 }
 397
 398 void wxListBase::Clear()
 399 {
 400     wxNodeBase *current = m_nodeFirst;
 401     while ( current )
 402     {
 403         wxNodeBase *next = current->GetNext();
 404         DoDeleteNode(current);
 405         current = next;
 406     }
 407
 408     m_nodeFirst =
 409     m_nodeLast = (wxNodeBase *)NULL;
 410
 411     m_count = 0;
 412 }
 413
 414 void wxListBase::ForEach(wxListIterateFunction F)
 415 {
 416     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 417     {
 418         (*F)(current->GetData());
 419     }
 420 }
 421
 422 void *wxListBase::FirstThat(wxListIterateFunction F)
 423 {
 424     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 425     {
 426         if ( (*F)(current->GetData()) )
 427             return current->GetData();
 428     }
 429
 430     return (wxNodeBase *)NULL;
 431 }
 432
 433 void *wxListBase::LastThat(wxListIterateFunction F)
 434 {
 435     for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() )
 436     {
 437         if ( (*F)(current->GetData()) )
 438             return current->GetData();
 439     }
 440
 441     return (wxNodeBase *)NULL;
 442 }
 443
 444 // (stefan.hammes@urz.uni-heidelberg.de)
 445 //
 446 // function for sorting lists. the concept is borrowed from 'qsort'.
 447 // by giving a sort function, arbitrary lists can be sorted.
 448 // method:
 449 // - put wxObject pointers into an array
 450 // - sort the array with qsort
 451 // - put back the sorted wxObject pointers into the list
 452 //
 453 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
 454 //       so dereference right!
 455 // EXAMPLE:
 456 //   int listcompare(const void *arg1, const void *arg2)
 457 //   {
 458 //      return(compare(**(wxString **)arg1,
 459 //                     **(wxString **)arg2));
 460 //   }
 461 //
 462 //   void main()
 463 //   {
 464 //     wxListBase list;
 465 //
 466 //     list.Append(new wxString("DEF"));
 467 //     list.Append(new wxString("GHI"));
 468 //     list.Append(new wxString("ABC"));
 469 //     list.Sort(listcompare);
 470 //   }
 471
 472 void wxListBase::Sort(const wxSortCompareFunction compfunc)
 473 {
 474     // allocate an array for the wxObject pointers of the list
 475     const size_t num = GetCount();
 476     void **objArray = new void *[num];
 477     void **objPtr = objArray;
 478
 479     // go through the list and put the pointers into the array
 480     wxNodeBase *node;
 481     for ( node = GetFirst(); node; node = node->Next() )
 482     {
 483         *objPtr++ = node->Data();
 484     }
 485
 486     // sort the array
 487     qsort((void *)objArray,num,sizeof(wxObject *),compfunc);
 488
 489     // put the sorted pointers back into the list
 490     objPtr = objArray;
 491     for ( node = GetFirst(); node; node = node->Next() )
 492     {
 493         node->SetData(*objPtr++);
 494     }
 495
 496     // free the array
 497     delete[] objArray;
 498 }
 499
 500 // -----------------------------------------------------------------------------
 501 // wxList (a.k.a. wxObjectList)
 502 // -----------------------------------------------------------------------------
 503
 504 void wxObjectListNode::DeleteData()
 505 {
 506     delete (wxObject *)GetData();
 507 }
 508
 509 // -----------------------------------------------------------------------------
 510 // wxStringList
 511 // -----------------------------------------------------------------------------
 512
 513 // instead of WX_DEFINE_LIST(wxStringListBase) we define this function
 514 // ourselves
 515 void wxStringListNode::DeleteData()
 516 {
 517     delete [] (char *)GetData();
 518 }
 519
 520 bool wxStringList::Delete(const char *s)
 521 {
 522     wxStringListNode *current;
 523
 524     for ( current = GetFirst(); current; current = current->GetNext() )
 525     {
 526         if ( strcmp(current->GetData(), s) == 0 )
 527         {
 528             DeleteNode(current);
 529             return TRUE;
 530         }
 531     }
 532
 533     // not found
 534     return FALSE;
 535 }
 536
 537 void wxStringList::DoCopy(const wxStringList& other)
 538 {
 539     wxASSERT( GetCount() == 0 );    // this list must be empty before copying!
 540
 541     size_t count = other.GetCount();
 542     for ( size_t n = 0; n < count; n++ )
 543     {
 544         Add(other.Item(n)->GetData());
 545     }
 546 }
 547
 548 // Variable argument list, terminated by a zero
 549 // Makes new storage for the strings
 550 wxStringList::wxStringList (const char *first, ...)
 551 {
 552   if ( !first )
 553     return;
 554
 555   va_list ap;
 556   va_start(ap, first);
 557
 558   const char *s = first;
 559   for (;;)
 560   {
 561       Add(s);
 562
 563       s = va_arg(ap, const char *);
 564       //    if (s == NULL)
 565 #ifdef __WXMSW__
 566       if ((int) s == 0)
 567 #else
 568       if ((long) s == 0)
 569 #endif
 570           break;
 571   }
 572
 573   va_end(ap);
 574 }
 575
 576 // Only makes new strings if arg is TRUE
 577 char **wxStringList::ListToArray(bool new_copies) const
 578 {
 579     char **string_array = new char *[GetCount()];
 580     wxStringListNode *node = GetFirst();
 581     for (size_t i = 0; i < GetCount(); i++)
 582     {
 583         char *s = node->GetData();
 584         if ( new_copies )
 585             string_array[i] = copystring(s);
 586         else
 587             string_array[i] = s;
 588         node = node->GetNext();
 589     }
 590
 591     return string_array;
 592 }
 593
 594 // Checks whether s is a member of the list
 595 bool wxStringList::Member(const char *s) const
 596 {
 597     for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
 598     {
 599         const char *s1 = node->GetData();
 600         if (s == s1 || strcmp (s, s1) == 0)
 601             return TRUE;
 602     }
 603
 604     return FALSE;
 605 }
 606
 607 static int
 608 wx_comparestrings(const void *arg1, const void *arg2)
 609 {
 610   char **s1 = (char **) arg1;
 611   char **s2 = (char **) arg2;
 612
 613   return strcmp (*s1, *s2);
 614 }
 615
 616 // Sort a list of strings - deallocates old nodes, allocates new
 617 void wxStringList::Sort()
 618 {
 619     size_t N = GetCount();
 620     char **array = new char *[N];
 621     wxStringListNode *node;
 622
 623     size_t i = 0;
 624     for ( node = GetFirst(); node; node = node->GetNext() )
 625     {
 626         array[i++] = node->GetData();
 627     }
 628
 629     qsort (array, N, sizeof (char *), wx_comparestrings);
 630
 631     i = 0;
 632     for ( node = GetFirst(); node; node = node->GetNext() )
 633         node->SetData( array[i++] );
 634
 635     delete [] array;
 636 }
 637