]> git.saurik.com Git - wxWidgets.git/blame - src/common/list.cpp
* Fixed two memory leaks.
[wxWidgets.git] / src / common / list.cpp
CommitLineData
c801d85f
KB
1/////////////////////////////////////////////////////////////////////////////
2// Name: list.cpp
3// Purpose: wxList implementation
4// Author: Julian Smart
5// Modified by:
6// Created: 04/01/98
7// RCS-ID: $Id$
8// Copyright: (c) Julian Smart and Markus Holzem
9// Licence: wxWindows license
10/////////////////////////////////////////////////////////////////////////////
11
12#ifdef __GNUG__
13#pragma implementation "list.h"
14#endif
15
16// For compilers that support precompilation, includes "wx.h".
17#include "wx/wxprec.h"
18
19#ifdef __BORLANDC__
20#pragma hdrstop
21#endif
22
23#ifndef WX_PRECOMP
24#include "wx/defs.h"
25#include "wx/list.h"
26#include "wx/utils.h"
1a5a8367 27#include <wx/intl.h>
c801d85f
KB
28#endif
29
30// Sun CC compatibility (interference with xview/pkg.h, apparently...)
31#if defined(SUN_CC) && defined(__XVIEW__)
32#undef va_start
33#undef va_end
34#undef va_arg
35#undef va_list
36#endif
37
38#include <stdarg.h>
39#include <stdlib.h>
40#include <string.h>
41
42#if !USE_SHARED_LIBRARY
43IMPLEMENT_DYNAMIC_CLASS(wxNode, wxObject)
44IMPLEMENT_DYNAMIC_CLASS(wxList, wxObject)
45IMPLEMENT_DYNAMIC_CLASS(wxStringList, wxList)
46#endif
47
48wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one,
49 wxObject * object)
50{
51 data = object;
52 previous = last_one;
53 next = next_one;
54 list = the_list;
c67daf87 55 key.string = (char *) NULL;
c801d85f
KB
56
57 if (previous)
58 previous->next = this;
59
60 if (next)
61 next->previous = this;
62}
63
64// Keyed constructor
65wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one,
66 wxObject * object, long the_key)
67{
68 data = object;
69 previous = last_one;
70 next = next_one;
71 list = the_list;
72 key.integer = the_key;
73
74 if (previous)
75 previous->next = this;
76
77 if (next)
78 next->previous = this;
79}
80
81wxNode::wxNode (wxList * the_list, wxNode * last_one, wxNode * next_one,
82 wxObject * object, const char *the_key)
83{
84 data = object;
85 previous = last_one;
86 next = next_one;
87 list = the_list;
88 key.string = copystring (the_key);
89
90 if (previous)
91 previous->next = this;
92
93 if (next)
94 next->previous = this;
95}
96
97
98wxNode::~wxNode (void)
99{
100 if (list)
101 list->n--;
102
103 if (list && list->destroy_data)
104 delete data;
105
106 if (list && list->key_type == wxKEY_STRING && key.string)
107 delete[]key.string;
108
109 // Make next node point back to the previous node from here
110 if (next)
111 next->previous = previous;
112 else if (list)
113 // If there's a new end of list (deleting the last one)
114 // make sure the list knows about it.
115 list->last_node = previous;
116
117 // Make the previous node point to the next node from here
118 if (previous)
119 previous->next = next;
120
121 // Or if no previous node (start of list), make sure list points at
122 // the next node which becomes the first!.
123 else if (list)
124 list->first_node = next;
125}
126
127wxList::wxList (void)
128{
c67daf87
UR
129 first_node = (wxNode *) NULL;
130 last_node = (wxNode *) NULL;
c801d85f
KB
131 n = 0;
132 destroy_data = 0;
133 key_type = wxKEY_NONE;
134}
135
debe6624 136wxList::wxList (int N, wxObject * Objects[])
c801d85f 137{
c67daf87 138 wxNode *last = (wxNode *) NULL;
c801d85f
KB
139
140 int i;
141 for (i = 0; i < N; i++)
142 {
c67daf87 143 wxNode *next = new wxNode (this, last, (wxNode *) NULL, Objects[i]);
c801d85f
KB
144 last = next;
145 if (i == 0)
146 first_node = next;
147 }
148 last_node = last;
149 n = N;
150 key_type = wxKEY_NONE;
151}
152
153wxList::wxList (const unsigned int the_key_type)
154{
155 n = 0;
156 destroy_data = 0;
c67daf87
UR
157 first_node = (wxNode *) NULL;
158 last_node = (wxNode *) NULL;
c801d85f
KB
159 key_type = the_key_type;
160}
161
162// Variable argument list, terminated by a zero
163wxList::wxList (wxObject * first_one...)
164{
165// #ifndef __SGI__
166 va_list ap;
167
168 va_start (ap, first_one);
169
c67daf87 170 wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, first_one);
c801d85f
KB
171 first_node = last;
172 n = 1;
173
174 for (;;)
175 {
176 wxObject *object = va_arg (ap, wxObject *);
177// if (object == NULL) // Doesn't work in Windows -- segment is non-zero for NULL!
2049ba38 178#ifdef __WXMSW__
c801d85f
KB
179 if ((int) object == 0)
180#else
181 if ((long) object == 0)
182#endif
183 break;
184 else
185 {
c67daf87 186 wxNode *node = new wxNode (this, last, (wxNode *) NULL, object);
c801d85f
KB
187 last = node;
188 n++;
189 }
190 }
191 last_node = last;
192 va_end (ap);
193
194 destroy_data = 0;
195 key_type = wxKEY_NONE;
196/*
197#else
198 fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n");
199#endif
200*/
201}
202
203wxList::~wxList (void)
204{
205 wxNode *each = first_node;
206 while (each)
207 {
208 wxNode *next = each->Next ();
209 delete each;
210 each = next;
211 }
212}
213
c801d85f
KB
214wxNode *wxList::Append(wxObject *object)
215{
c67daf87 216 wxNode *node = new wxNode(this, last_node, (wxNode *) NULL, object);
c801d85f
KB
217 if (!first_node)
218 first_node = node;
219 last_node = node;
220 n ++;
221 return node;
222}
223
debe6624 224wxNode *wxList::Nth (int i) const
c801d85f
KB
225{
226 int j = 0;
227 for (wxNode * current = First (); current; current = current->Next ())
228 {
229 if (j++ == i)
230 return current;
231 }
c67daf87 232 return (wxNode *) NULL; // No such element
c801d85f
KB
233
234}
235
debe6624 236wxNode *wxList::Find (long key) const
c801d85f
KB
237{
238 wxNode *current = First();
239 while (current)
240 {
241 if (current->key.integer == key)
242 return current;
243 current = current->Next();
244 }
245
c67daf87 246 return (wxNode *) NULL; // Not found!
c801d85f
KB
247}
248
249wxNode *wxList::Find (const char *key) const
250{
251 wxNode *current = First();
252 while (current)
253 {
254 if (!current->key.string)
255 {
1a5a8367 256 wxFatalError (_("wxList: string key not present, probably did not Append correctly!"));
c801d85f
KB
257 break;
258 }
259 if (strcmp (current->key.string, key) == 0)
260 return current;
261 current = current->Next();
262 }
263
c67daf87 264 return (wxNode *) NULL; // Not found!
c801d85f
KB
265
266}
267
268wxNode *wxList::Member (wxObject * object) const
269{
270 for (wxNode * current = First (); current; current = current->Next ())
271 {
272 wxObject *each = current->Data ();
273 if (each == object)
274 return current;
275 }
c67daf87 276 return (wxNode *) NULL;
c801d85f
KB
277}
278
279bool wxList::DeleteNode (wxNode * node)
280{
281 if (node)
282 {
283 delete node;
284 return TRUE;
285 }
286 return FALSE;
287}
288
289bool wxList::DeleteObject (wxObject * object)
290{
291 // Search list for object
292 for (wxNode * current = first_node; current; current = current->Next ())
293 {
294 if (current->Data () == object)
295 {
296 delete current;
297 return TRUE;
298 }
299 }
300 return FALSE; // Did not find the object
301
302}
303
304
305// Insert new node at front of list
306wxNode *wxList::Insert (wxObject * object)
307{
c67daf87 308 wxNode *node = new wxNode (this, (wxNode *) NULL, First (), object);
c801d85f
KB
309 first_node = node;
310
311 if (!(node->Next ()))
312 last_node = node;
313
314 n++;
315 return node;
316}
317
318
319// Insert new node before given node.
320wxNode *wxList::Insert (wxNode * position, wxObject * object)
321{
c67daf87 322 wxNode *prev = (wxNode *) NULL;
c801d85f
KB
323 if (position)
324 prev = position->Previous ();
325
326 wxNode *node = new wxNode (this, prev, position, object);
327 if (!first_node)
328 {
329 first_node = node;
330 last_node = node;
331 }
332 if (!prev)
333 first_node = node;
334
335 n++;
336 return node;
337}
338
339// Keyed append
debe6624 340wxNode *wxList::Append (long key, wxObject * object)
c801d85f 341{
c67daf87 342 wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key);
c801d85f
KB
343 if (!first_node)
344 first_node = node;
345 last_node = node;
346 n++;
347 return node;
348}
349
350wxNode *wxList::Append (const char *key, wxObject * object)
351{
c67daf87 352 wxNode *node = new wxNode (this, last_node, (wxNode *) NULL, object, key);
c801d85f
KB
353 if (!first_node)
354 first_node = node;
355 last_node = node;
356 n++;
357 return node;
358}
359
360void wxList::Clear (void)
361{
362 wxNode *current = first_node;
363 while (current)
364 {
365 wxNode *next = current->Next ();
366 delete current;
367 current = next;
368 }
c67daf87
UR
369 first_node = (wxNode *) NULL;
370 last_node = (wxNode *) NULL;
c801d85f
KB
371 n = 0;
372}
373
374//Executes function F with all items present in the list
375void wxList::ForEach(wxListIterateFunction F)
376{
377 wxNode *each = first_node;
378 while (each)
379 { (*F)( each->Data ());
380 each = each->Next();
381 }
382}
383// Returns a pointer to the item which returns TRUE with function F
384// or NULL if no such item found
385wxObject *wxList::FirstThat(wxListIterateFunction F)
386{
387 wxNode *each = first_node;
388 while (each)
389 { if ((*F)( each->Data ())) return each->Data();
390 each = each->Next();
391 }
c67daf87 392 return (wxNode *) NULL;
c801d85f
KB
393}
394// Like FirstThat, but proceeds from the end backward
395wxObject *wxList::LastThat(wxListIterateFunction F)
396{
397 wxNode *each = last_node;
398 while (each)
399 { if ((*F)( each->Data ())) return each->Data();
400 each = each->Previous();
401 }
c67daf87 402 return (wxNode *) NULL;
c801d85f
KB
403}
404
405// (stefan.hammes@urz.uni-heidelberg.de)
406//
407// function for sorting lists. the concept is borrowed from 'qsort'.
408// by giving a sort function, arbitrary lists can be sorted.
409// method:
410// - put wxObject pointers into an array
411// - sort the array with qsort
412// - put back the sorted wxObject pointers into the list
413//
414// CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
415// so dereference right!
416// EXAMPLE:
417// int listcompare(const void *arg1, const void *arg2)
418// {
419// return(compare(**(wxString **)arg1,
420// **(wxString **)arg2));
421// }
422//
423// void main()
424// {
425// wxList list;
426//
427// list.Append(new wxString("DEF"));
428// list.Append(new wxString("GHI"));
429// list.Append(new wxString("ABC"));
430// list.Sort(listcompare);
431// }
432
433void wxList::Sort(const wxSortCompareFunction compfunc)
434{
435 // allocate an array for the wxObject pointers of the list
436 const size_t num = Number();
437 wxObject **objArray = new wxObject *[num];
438 wxObject **objPtr = objArray;
439
440 // go through the list and put the pointers into the array
441 wxNode *node = First();
442 while(node!=NULL){
443 *objPtr++ = node->Data();
444 node = node->Next();
445 }
446 // sort the array
447 qsort((void *)objArray,num,sizeof(wxObject *),compfunc);
448 // put the sorted pointers back into the list
449 objPtr = objArray;
450 node = First();
451 while(node!=NULL){
452 node->SetData(*objPtr++);
453 node = node->Next();
454 }
455 // free the array
456 delete[] objArray;
457}
458
459/*
460 * String list
461 *
462 */
463
464wxStringList::wxStringList (void):
465wxList ()
466{
467}
468
469// Variable argument list, terminated by a zero
470// Makes new storage for the strings
471wxStringList::wxStringList (const char *first...)
472{
473// #ifndef __SGI__
474 n = 0;
475 destroy_data = 0;
476 key_type = wxKEY_NONE;
c67daf87
UR
477 first_node = (wxNode *) NULL;
478 last_node = (wxNode *) NULL;
c801d85f
KB
479
480 if (!first)
481 return;
482
483 va_list ap;
484
485 va_start (ap, first);
486
c67daf87 487 wxNode *last = new wxNode (this, (wxNode *) NULL, (wxNode *) NULL, (wxObject *) copystring (first));
c801d85f
KB
488 first_node = last;
489 n = 1;
490
491 for (;;)
492 {
493 char *s = va_arg (ap, char *);
494// if (s == NULL)
2049ba38 495#ifdef __WXMSW__
c801d85f
KB
496 if ((int) s == 0)
497#else
498 if ((long) s == 0)
499#endif
500 break;
501 else
502 {
c67daf87 503 wxNode *node = new wxNode (this, last, (wxNode *) NULL, (wxObject *) copystring (s));
c801d85f
KB
504 last = node;
505 n++;
506 }
507 }
508 last_node = last;
509 va_end (ap);
510/*
511#else
512 fprintf (stderr, "Error: cannot use variable-argument functions on SGI!\n");
513#endif
514*/
515}
516
517wxStringList::~wxStringList (void)
518{
519 wxNode *each = first_node;
520 while (each)
521 {
522 char *s = (char *) each->Data ();
523 delete[]s;
524 wxNode *next = each->Next ();
525 delete each;
526 each = next;
527 }
528}
529
530wxNode *wxStringList::Add (const char *s)
531{
532 return Append ((wxObject *) (copystring (s)));
533}
534
535void wxStringList::Delete (const char *s)
536{
537 for (wxNode * node = First (); node; node = node->Next ())
538 {
539 char *string = (char *) node->Data ();
540 if (string == s || strcmp (string, s) == 0)
541 {
542 delete[]string;
543 delete node;
544 break; // Done!
545
546 }
547 } // for
548
549}
550
551// Only makes new strings if arg is TRUE
debe6624 552char **wxStringList::ListToArray (bool new_copies) const
c801d85f
KB
553{
554 char **string_array = new char *[Number ()];
555 wxNode *node = First ();
556 int i;
557 for (i = 0; i < n; i++)
558 {
559 char *s = (char *) node->Data ();
560 if (new_copies)
561 string_array[i] = copystring (s);
562 else
563 string_array[i] = s;
564 node = node->Next ();
565 }
566 return string_array;
567}
568
569static int
570wx_comparestrings (const void *arg1, const void *arg2)
571{
572 char **s1 = (char **) arg1;
573 char **s2 = (char **) arg2;
574
575 return strcmp (*s1, *s2);
576}
577
578// Sort a list of strings - deallocates old nodes, allocates new
579void wxStringList::Sort (void)
580{
581 size_t N = n;
582 char **array = new char *[N];
583
584 size_t i = 0;
585 for (wxNode * node = First (); node; node = node->Next ())
586 array[i++] = (char *) node->Data ();
587
588 qsort (array, N, sizeof (char *), wx_comparestrings);
589 Clear ();
590
591 for (i = 0; i < N; i++)
592 Append ((wxObject *) (array[i]));
593
594 delete[]array;
595}
596
597// Checks whether s is a member of the list
598bool wxStringList::Member (const char *s) const
599{
600 for (wxNode * node = First (); node; node = node->Next ())
601 {
602 const char *s1 = (const char *) node->Data ();
603 if (s == s1 || strcmp (s, s1) == 0)
604 return TRUE;
605 }
606 return FALSE;
607}