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