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