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