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