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