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 #if defined(SUN_CC) && defined(__XVIEW__)
  42     #undef va_start
  43     #undef va_end
  44     #undef va_arg
  45     #undef va_list
  46 #endif
  47
  48 // =============================================================================
  49 // implementation
  50 // =============================================================================
  51
  52 // -----------------------------------------------------------------------------
  53 // wxListKey
  54 // -----------------------------------------------------------------------------
  55
  56 bool wxListKey::operator==(wxListKeyValue value) const
  57 {
  58     switch ( m_keyType )
  59     {
  60         default:
  61             wxFAIL_MSG("bad key type.");
  62             // let compiler optimize the line above away in release build
  63             // by not putting return here...
  64
  65         case wxKEY_STRING:
  66             return strcmp(m_key.string, value.string) == 0;
  67
  68         case wxKEY_INTEGER:
  69             return m_key.integer == value.integer;
  70     }
  71 }
  72
  73 // -----------------------------------------------------------------------------
  74 // wxNodeBase
  75 // -----------------------------------------------------------------------------
  76
  77 wxNodeBase::wxNodeBase(wxListBase *list,
  78                        wxNodeBase *previous, wxNodeBase *next,
  79                        void *data, const wxListKey& key)
  80 {
  81     m_list = list;
  82     m_data = data;
  83     m_previous = previous;
  84     m_next = next;
  85
  86     switch ( key.GetKeyType() )
  87     {
  88         case wxKEY_NONE:
  89             break;
  90
  91         case wxKEY_INTEGER:
  92             m_key.integer = key.GetNumber();
  93             break;
  94
  95         case wxKEY_STRING:
  96             // to be free()d later
  97             m_key.string = strdup(key.GetString());
  98             break;
  99
 100         default:
 101             wxFAIL_MSG("invalid key type");
 102     }
 103
 104     if ( previous )
 105         previous->m_next = this;
 106
 107     if ( next )
 108         next->m_previous = this;
 109 }
 110
 111 wxNodeBase::~wxNodeBase()
 112 {
 113     // handle the case when we're being deleted from the list by the user (i.e.
 114     // not by the list itself from DeleteNode) - we must do it for
 115     // compatibility with old code
 116     if ( m_list != NULL )
 117     {
 118         m_list->DetachNode(this);
 119     }
 120 }
 121
 122 int wxNodeBase::IndexOf() const
 123 {
 124     wxCHECK_MSG( m_list, NOT_FOUND, "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 = wxKEY_NONE)
 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                   "copying list which owns it's elements is a bad idea" );
 168
 169     m_count = list.m_count;
 170     m_destroy = list.m_destroy;
 171     m_keyType = list.m_keyType;
 172     m_nodeFirst =
 173     m_nodeLast = (wxNodeBase *) NULL;
 174
 175     for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
 176     {
 177         Append(node);
 178     }
 179 }
 180
 181 wxListBase::~wxListBase()
 182 {
 183   wxNodeBase *each = m_nodeFirst;
 184   while ( each != NULL )
 185   {
 186       wxNodeBase *next = each->GetNext();
 187       DoDeleteNode(each);
 188       each = next;
 189   }
 190 }
 191
 192 wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node)
 193 {
 194     if ( !m_nodeFirst )
 195     {
 196         m_nodeFirst = node;
 197         m_nodeLast = m_nodeFirst;
 198     }
 199     else
 200     {
 201         m_nodeLast->m_next = node;
 202         m_nodeLast = node;
 203     }
 204
 205     m_count++;
 206
 207     return node;
 208 }
 209
 210 wxNodeBase *wxListBase::Append(void *object)
 211 {
 212     // all objects in a keyed list should have a key
 213     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 214                  "need a key for the object to append" );
 215
 216     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object);
 217
 218     return AppendCommon(node);
 219 }
 220
 221 wxNodeBase *wxListBase::Append(long key, void *object)
 222 {
 223     wxCHECK_MSG( (m_keyType == wxKEY_INTEGER) ||
 224                  (m_keyType == wxKEY_NONE && m_count == 0),
 225                  (wxNodeBase *)NULL,
 226                  "can't append object with numeric key to this list" );
 227
 228     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 229     return AppendCommon(node);
 230 }
 231
 232 wxNodeBase *wxListBase::Append (const char *key, void *object)
 233 {
 234     wxCHECK_MSG( (m_keyType == wxKEY_STRING) ||
 235                  (m_keyType == wxKEY_NONE && m_count == 0),
 236                  (wxNodeBase *)NULL,
 237                  "can't append object with string key to this list" );
 238
 239     wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object, key);
 240     return AppendCommon(node);
 241 }
 242
 243 wxNodeBase *wxListBase::Insert(wxNodeBase *position, void *object)
 244 {
 245     // all objects in a keyed list should have a key
 246     wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
 247                  "need a key for the object to insert" );
 248
 249     wxCHECK_MSG( !position || position->m_list == this, (wxNodeBase *)NULL,
 250                  "can't insert before a node from another list" );
 251
 252     // previous and next node for the node being inserted
 253     wxNodeBase *prev, *next;
 254     if ( position )
 255     {
 256         prev = position->GetPrevious();
 257         next = position;
 258     }
 259     else
 260     {
 261         // inserting in the beginning of the list
 262         prev = (wxNodeBase *)NULL;
 263         next = m_nodeFirst;
 264     }
 265
 266     wxNodeBase *node = CreateNode(prev, next, object);
 267     if ( !m_nodeFirst )
 268     {
 269         m_nodeLast = node;
 270     }
 271
 272     if ( prev == NULL )
 273     {
 274         m_nodeFirst = node;
 275     }
 276
 277     m_count++;
 278
 279     return node;
 280 }
 281
 282 wxNodeBase *wxListBase::Item(size_t n) const
 283 {
 284     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 285     {
 286         if ( n-- == 0 )
 287         {
 288             return current;
 289         }
 290     }
 291
 292     wxFAIL_MSG( "invalid index in wxListBase::Item" );
 293
 294     return NULL;
 295 }
 296
 297 wxNodeBase *wxListBase::Find(const wxListKey& key) const
 298 {
 299     wxASSERT_MSG( m_keyType == key.GetKeyType(),
 300                   "this list is not keyed on the type of this key" );
 301
 302     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 303     {
 304         if ( key == current->m_key )
 305         {
 306             return current;
 307         }
 308     }
 309
 310     // not found
 311     return (wxNodeBase *)NULL;
 312 }
 313
 314 wxNodeBase *wxListBase::Find(void *object) const
 315 {
 316     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 317     {
 318         if ( current->GetData() == object )
 319             return current;
 320     }
 321
 322     // not found
 323     return (wxNodeBase *)NULL;
 324 }
 325
 326 int wxListBase::IndexOf(void *object) const
 327 {
 328     wxNodeBase *node = Find( object );
 329
 330     return node ? node->IndexOf() : NOT_FOUND;
 331 }
 332
 333 void wxListBase::DoDeleteNode(wxNodeBase *node)
 334 {
 335     // free node's data
 336     if ( m_keyType == wxKEY_STRING )
 337     {
 338         free(node->m_key.string);
 339     }
 340
 341     if ( m_destroy )
 342     {
 343         node->DeleteData();
 344     }
 345
 346     delete node;
 347 }
 348
 349 wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
 350 {
 351     wxCHECK_MSG( node, NULL, "detaching NULL wxNodeBase" );
 352     wxCHECK_MSG( node->m_list == this, NULL,
 353                  "detaching node which is not from this list" );
 354
 355     // update the list
 356     wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
 357                                                 : &m_nodeFirst;
 358     wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
 359                                             : &m_nodeLast;
 360
 361     *prevNext = node->GetNext();
 362     *nextPrev = node->GetPrevious();
 363
 364     m_count--;
 365
 366     // mark the node as not belonging to this list any more
 367     node->m_list = NULL;
 368
 369     return node;
 370 }
 371
 372 bool wxListBase::DeleteNode(wxNodeBase *node)
 373 {
 374     if ( !DetachNode(node) )
 375         return FALSE;
 376
 377     DoDeleteNode(node);
 378
 379     return TRUE;
 380 }
 381
 382 bool wxListBase::DeleteObject(void *object)
 383 {
 384     for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
 385     {
 386         if ( current->GetData() == object )
 387         {
 388             DeleteNode(current);
 389             return TRUE;
 390         }
 391     }
 392
 393     // not found
 394     return FALSE;
 395 }
 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 void wxStringList::DoCopy(const wxStringList& other)
 521 {
 522     wxASSERT( GetCount() == 0 );    // this list must be empty before copying!
 523
 524     size_t count = other.GetCount();
 525     for ( size_t n = 0; n < count; n++ )
 526     {
 527         Add(other.Item(n)->GetData());
 528     }
 529 }
 530
 531 // Variable argument list, terminated by a zero
 532 // Makes new storage for the strings
 533 wxStringList::wxStringList (const char *first, ...)
 534 {
 535   if ( !first )
 536     return;
 537
 538   va_list ap;
 539   va_start(ap, first);
 540
 541   const char *s = first;
 542   for (;;)
 543   {
 544       Add(s);
 545
 546       s = va_arg(ap, const char *);
 547       //    if (s == NULL)
 548 #ifdef __WXMSW__
 549       if ((int) s == 0)
 550 #else
 551       if ((long) s == 0)
 552 #endif
 553           break;
 554   }
 555
 556   va_end(ap);
 557 }
 558
 559 // Only makes new strings if arg is TRUE
 560 char **wxStringList::ListToArray(bool new_copies) const
 561 {
 562     char **string_array = new char *[GetCount()];
 563     wxStringListNode *node = GetFirst();
 564     for (size_t i = 0; i < GetCount(); i++)
 565     {
 566         char *s = node->GetData();
 567         if ( new_copies )
 568             string_array[i] = copystring(s);
 569         else
 570             string_array[i] = s;
 571         node = node->GetNext();
 572     }
 573
 574     return string_array;
 575 }
 576
 577 // Checks whether s is a member of the list
 578 bool wxStringList::Member(const char *s) const
 579 {
 580     for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
 581     {
 582         const char *s1 = node->GetData();
 583         if (s == s1 || strcmp (s, s1) == 0)
 584             return TRUE;
 585     }
 586
 587     return FALSE;
 588 }
 589
 590 static int
 591 wx_comparestrings(const void *arg1, const void *arg2)
 592 {
 593   char **s1 = (char **) arg1;
 594   char **s2 = (char **) arg2;
 595
 596   return strcmp (*s1, *s2);
 597 }
 598
 599 // Sort a list of strings - deallocates old nodes, allocates new
 600 void wxStringList::Sort()
 601 {
 602     size_t N = GetCount();
 603     char **array = new char *[N];
 604
 605     size_t i = 0;
 606     for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
 607     {
 608         array[i++] = node->GetData();
 609     }
 610
 611     qsort (array, N, sizeof (char *), wx_comparestrings);
 612     Clear();
 613
 614     for (i = 0; i < N; i++)
 615         Append (array[i]);
 616
 617     delete[]array;
 618 }
 619