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