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