/[pcsx2_0.9.7]/trunk/3rdparty/wxWidgets/src/common/list.cpp
ViewVC logotype

Contents of /trunk/3rdparty/wxWidgets/src/common/list.cpp

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Tue Sep 7 03:24:11 2010 UTC (10 years, 3 months ago) by william
File size: 18959 byte(s)
committing r3113 initial commit again...
1 ////////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/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: list.cpp 43048 2006-11-04 18:14:50Z VZ $
8 // Copyright: (c) Julian Smart
9 // Licence: wxWindows licence
10 ////////////////////////////////////////////////////////////////////////////////
11
12 // =============================================================================
13 // declarations
14 // =============================================================================
15
16 // -----------------------------------------------------------------------------
17 // headers
18 // -----------------------------------------------------------------------------
19
20 // For compilers that support precompilation, includes "wx.h".
21 #include "wx/wxprec.h"
22
23 #ifdef __BORLANDC__
24 #pragma hdrstop
25 #endif
26
27 #include <stdarg.h>
28 #include <stdlib.h>
29 #include <string.h>
30
31 #ifndef WX_PRECOMP
32 #include "wx/list.h"
33 #endif
34
35 #if !wxUSE_STL
36
37 // =============================================================================
38 // implementation
39 // =============================================================================
40
41 // -----------------------------------------------------------------------------
42 // wxListKey
43 // -----------------------------------------------------------------------------
44 wxListKey wxDefaultListKey;
45
46 bool wxListKey::operator==(wxListKeyValue value) const
47 {
48 switch ( m_keyType )
49 {
50 default:
51 wxFAIL_MSG(wxT("bad key type."));
52 // let compiler optimize the line above away in release build
53 // by not putting return here...
54
55 case wxKEY_STRING:
56 return wxStrcmp(m_key.string, value.string) == 0;
57
58 case wxKEY_INTEGER:
59 return m_key.integer == value.integer;
60 }
61 }
62
63 // -----------------------------------------------------------------------------
64 // wxNodeBase
65 // -----------------------------------------------------------------------------
66
67 wxNodeBase::wxNodeBase(wxListBase *list,
68 wxNodeBase *previous, wxNodeBase *next,
69 void *data, const wxListKey& key)
70 {
71 m_list = list;
72 m_data = data;
73 m_previous = previous;
74 m_next = next;
75
76 switch ( key.GetKeyType() )
77 {
78 case wxKEY_NONE:
79 break;
80
81 case wxKEY_INTEGER:
82 m_key.integer = key.GetNumber();
83 break;
84
85 case wxKEY_STRING:
86 // to be free()d later
87 m_key.string = wxStrdup(key.GetString());
88 break;
89
90 default:
91 wxFAIL_MSG(wxT("invalid key type"));
92 }
93
94 if ( previous )
95 previous->m_next = this;
96
97 if ( next )
98 next->m_previous = this;
99 }
100
101 wxNodeBase::~wxNodeBase()
102 {
103 // handle the case when we're being deleted from the list by the user (i.e.
104 // not by the list itself from DeleteNode) - we must do it for
105 // compatibility with old code
106 if ( m_list != NULL )
107 {
108 if ( m_list->m_keyType == wxKEY_STRING )
109 {
110 free(m_key.string);
111 }
112
113 m_list->DetachNode(this);
114 }
115 }
116
117 int wxNodeBase::IndexOf() const
118 {
119 wxCHECK_MSG( m_list, wxNOT_FOUND, wxT("node doesn't belong to a list in IndexOf"));
120
121 // It would be more efficient to implement IndexOf() completely inside
122 // wxListBase (only traverse the list once), but this is probably a more
123 // reusable way of doing it. Can always be optimized at a later date (since
124 // IndexOf() resides in wxListBase as well) if efficiency is a problem.
125 int i;
126 wxNodeBase *prev = m_previous;
127
128 for( i = 0; prev; i++ )
129 {
130 prev = prev->m_previous;
131 }
132
133 return i;
134 }
135
136 // -----------------------------------------------------------------------------
137 // wxListBase
138 // -----------------------------------------------------------------------------
139
140 void wxListBase::Init(wxKeyType keyType)
141 {
142 m_nodeFirst =
143 m_nodeLast = (wxNodeBase *) NULL;
144 m_count = 0;
145 m_destroy = false;
146 m_keyType = keyType;
147 }
148
149 wxListBase::wxListBase(size_t count, void *elements[])
150 {
151 Init();
152
153 for ( size_t n = 0; n < count; n++ )
154 {
155 Append(elements[n]);
156 }
157 }
158
159 void wxListBase::DoCopy(const wxListBase& list)
160 {
161 wxASSERT_MSG( !list.m_destroy,
162 wxT("copying list which owns it's elements is a bad idea") );
163
164 m_destroy = list.m_destroy;
165 m_keyType = list.m_keyType;
166 m_nodeFirst =
167 m_nodeLast = (wxNodeBase *) NULL;
168
169 switch (m_keyType)
170 {
171 case wxKEY_INTEGER:
172 {
173 long key;
174 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
175 {
176 key = node->GetKeyInteger();
177 Append(key, node->GetData());
178 }
179 break;
180 }
181
182 case wxKEY_STRING:
183 {
184 const wxChar *key;
185 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
186 {
187 key = node->GetKeyString();
188 Append(key, node->GetData());
189 }
190 break;
191 }
192
193 default:
194 {
195 for ( wxNodeBase *node = list.GetFirst(); node; node = node->GetNext() )
196 {
197 Append(node->GetData());
198 }
199 break;
200 }
201 }
202
203 wxASSERT_MSG( m_count == list.m_count, _T("logic error in wxList::DoCopy") );
204 }
205
206 wxListBase::~wxListBase()
207 {
208 wxNodeBase *each = m_nodeFirst;
209 while ( each != NULL )
210 {
211 wxNodeBase *next = each->GetNext();
212 DoDeleteNode(each);
213 each = next;
214 }
215 }
216
217 wxNodeBase *wxListBase::AppendCommon(wxNodeBase *node)
218 {
219 if ( !m_nodeFirst )
220 {
221 m_nodeFirst = node;
222 m_nodeLast = m_nodeFirst;
223 }
224 else
225 {
226 m_nodeLast->m_next = node;
227 m_nodeLast = node;
228 }
229
230 m_count++;
231
232 return node;
233 }
234
235 wxNodeBase *wxListBase::Append(void *object)
236 {
237 // all objects in a keyed list should have a key
238 wxCHECK_MSG( m_keyType == wxKEY_NONE, (wxNodeBase *)NULL,
239 wxT("need a key for the object to append") );
240
241 // we use wxDefaultListKey even though it is the default parameter value
242 // because gcc under Mac OS X seems to miscompile this call otherwise
243 wxNodeBase *node = CreateNode(m_nodeLast, (wxNodeBase *)NULL, object,
244 wxDefaultListKey);
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 // wxDefaultListKey: see comment in Append() above
295 wxNodeBase *node = CreateNode(prev, next, object, wxDefaultListKey);
296 if ( !m_nodeFirst )
297 {
298 m_nodeLast = node;
299 }
300
301 if ( prev == NULL )
302 {
303 m_nodeFirst = node;
304 }
305
306 m_count++;
307
308 return node;
309 }
310
311 wxNodeBase *wxListBase::Item(size_t n) const
312 {
313 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
314 {
315 if ( n-- == 0 )
316 {
317 return current;
318 }
319 }
320
321 wxFAIL_MSG( wxT("invalid index in wxListBase::Item") );
322
323 return (wxNodeBase *)NULL;
324 }
325
326 wxNodeBase *wxListBase::Find(const wxListKey& key) const
327 {
328 wxASSERT_MSG( m_keyType == key.GetKeyType(),
329 wxT("this list is not keyed on the type of this key") );
330
331 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
332 {
333 if ( key == current->m_key )
334 {
335 return current;
336 }
337 }
338
339 // not found
340 return (wxNodeBase *)NULL;
341 }
342
343 wxNodeBase *wxListBase::Find(const void *object) const
344 {
345 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
346 {
347 if ( current->GetData() == object )
348 return current;
349 }
350
351 // not found
352 return (wxNodeBase *)NULL;
353 }
354
355 int wxListBase::IndexOf(void *object) const
356 {
357 wxNodeBase *node = Find( object );
358
359 return node ? node->IndexOf() : wxNOT_FOUND;
360 }
361
362 void wxListBase::DoDeleteNode(wxNodeBase *node)
363 {
364 // free node's data
365 if ( m_keyType == wxKEY_STRING )
366 {
367 free(node->m_key.string);
368 }
369
370 if ( m_destroy )
371 {
372 node->DeleteData();
373 }
374
375 // so that the node knows that it's being deleted by the list
376 node->m_list = NULL;
377 delete node;
378 }
379
380 wxNodeBase *wxListBase::DetachNode(wxNodeBase *node)
381 {
382 wxCHECK_MSG( node, NULL, wxT("detaching NULL wxNodeBase") );
383 wxCHECK_MSG( node->m_list == this, NULL,
384 wxT("detaching node which is not from this list") );
385
386 // update the list
387 wxNodeBase **prevNext = node->GetPrevious() ? &node->GetPrevious()->m_next
388 : &m_nodeFirst;
389 wxNodeBase **nextPrev = node->GetNext() ? &node->GetNext()->m_previous
390 : &m_nodeLast;
391
392 *prevNext = node->GetNext();
393 *nextPrev = node->GetPrevious();
394
395 m_count--;
396
397 // mark the node as not belonging to this list any more
398 node->m_list = NULL;
399
400 return node;
401 }
402
403 bool wxListBase::DeleteNode(wxNodeBase *node)
404 {
405 if ( !DetachNode(node) )
406 return false;
407
408 DoDeleteNode(node);
409
410 return true;
411 }
412
413 bool wxListBase::DeleteObject(void *object)
414 {
415 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
416 {
417 if ( current->GetData() == object )
418 {
419 DeleteNode(current);
420 return true;
421 }
422 }
423
424 // not found
425 return false;
426 }
427
428 void wxListBase::Clear()
429 {
430 wxNodeBase *current = m_nodeFirst;
431 while ( current )
432 {
433 wxNodeBase *next = current->GetNext();
434 DoDeleteNode(current);
435 current = next;
436 }
437
438 m_nodeFirst =
439 m_nodeLast = (wxNodeBase *)NULL;
440
441 m_count = 0;
442 }
443
444 void wxListBase::ForEach(wxListIterateFunction F)
445 {
446 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
447 {
448 (*F)(current->GetData());
449 }
450 }
451
452 void *wxListBase::FirstThat(wxListIterateFunction F)
453 {
454 for ( wxNodeBase *current = GetFirst(); current; current = current->GetNext() )
455 {
456 if ( (*F)(current->GetData()) )
457 return current->GetData();
458 }
459
460 return (wxNodeBase *)NULL;
461 }
462
463 void *wxListBase::LastThat(wxListIterateFunction F)
464 {
465 for ( wxNodeBase *current = GetLast(); current; current = current->GetPrevious() )
466 {
467 if ( (*F)(current->GetData()) )
468 return current->GetData();
469 }
470
471 return (wxNodeBase *)NULL;
472 }
473
474 // (stefan.hammes@urz.uni-heidelberg.de)
475 //
476 // function for sorting lists. the concept is borrowed from 'qsort'.
477 // by giving a sort function, arbitrary lists can be sorted.
478 // method:
479 // - put wxObject pointers into an array
480 // - sort the array with qsort
481 // - put back the sorted wxObject pointers into the list
482 //
483 // CAVE: the sort function receives pointers to wxObject pointers (wxObject **),
484 // so dereference right!
485 // EXAMPLE:
486 // int listcompare(const void *arg1, const void *arg2)
487 // {
488 // return(compare(**(wxString **)arg1,
489 // **(wxString **)arg2));
490 // }
491 //
492 // void main()
493 // {
494 // wxListBase list;
495 //
496 // list.Append(new wxString("DEF"));
497 // list.Append(new wxString("GHI"));
498 // list.Append(new wxString("ABC"));
499 // list.Sort(listcompare);
500 // }
501
502 void wxListBase::Sort(const wxSortCompareFunction compfunc)
503 {
504 // allocate an array for the wxObject pointers of the list
505 const size_t num = GetCount();
506 void **objArray = new void *[num];
507 void **objPtr = objArray;
508
509 // go through the list and put the pointers into the array
510 wxNodeBase *node;
511 for ( node = GetFirst(); node; node = node->GetNext() )
512 {
513 *objPtr++ = node->GetData();
514 }
515
516 // sort the array
517 qsort((void *)objArray,num,sizeof(wxObject *),
518 #ifdef __WXWINCE__
519 (int (__cdecl *)(const void *,const void *))
520 #endif
521 compfunc);
522
523 // put the sorted pointers back into the list
524 objPtr = objArray;
525 for ( node = GetFirst(); node; node = node->GetNext() )
526 {
527 node->SetData(*objPtr++);
528 }
529
530 // free the array
531 delete[] objArray;
532 }
533
534 void wxListBase::Reverse()
535 {
536 wxNodeBase* node = m_nodeFirst;
537 wxNodeBase* tmp;
538
539 while (node)
540 {
541 // swap prev and next pointers
542 tmp = node->m_next;
543 node->m_next = node->m_previous;
544 node->m_previous = tmp;
545
546 // this is the node that was next before swapping
547 node = tmp;
548 }
549
550 // swap first and last node
551 tmp = m_nodeFirst; m_nodeFirst = m_nodeLast; m_nodeLast = tmp;
552 }
553
554 void wxListBase::DeleteNodes(wxNodeBase* first, wxNodeBase* last)
555 {
556 wxNodeBase* node = first;
557
558 while (node != last)
559 {
560 wxNodeBase* next = node->GetNext();
561 DeleteNode(node);
562 node = next;
563 }
564 }
565
566 // ============================================================================
567 // compatibility section from now on
568 // ============================================================================
569
570 #ifdef wxLIST_COMPATIBILITY
571
572 // -----------------------------------------------------------------------------
573 // wxList (a.k.a. wxObjectList)
574 // -----------------------------------------------------------------------------
575
576 IMPLEMENT_DYNAMIC_CLASS(wxList, wxObject)
577
578 wxList::wxList( int key_type )
579 : wxObjectList( (wxKeyType)key_type )
580 {
581 }
582
583 void wxObjectListNode::DeleteData()
584 {
585 delete (wxObject *)GetData();
586 }
587
588 // ----------------------------------------------------------------------------
589 // wxStringList
590 // ----------------------------------------------------------------------------
591
592 static inline wxChar* MYcopystring(const wxChar* s)
593 {
594 wxChar* copy = new wxChar[wxStrlen(s) + 1];
595 return wxStrcpy(copy, s);
596 }
597
598 IMPLEMENT_DYNAMIC_CLASS(wxStringList, wxObject)
599
600 // instead of WX_DEFINE_LIST(wxStringListBase) we define this function
601 // ourselves
602 void wxStringListNode::DeleteData()
603 {
604 delete [] (char *)GetData();
605 }
606
607 bool wxStringList::Delete(const wxChar *s)
608 {
609 wxStringListNode *current;
610
611 for ( current = GetFirst(); current; current = current->GetNext() )
612 {
613 if ( wxStrcmp(current->GetData(), s) == 0 )
614 {
615 DeleteNode(current);
616 return true;
617 }
618 }
619
620 // not found
621 return false;
622 }
623
624 void wxStringList::DoCopy(const wxStringList& other)
625 {
626 wxASSERT( GetCount() == 0 ); // this list must be empty before copying!
627
628 size_t count = other.GetCount();
629 for ( size_t n = 0; n < count; n++ )
630 {
631 Add(other.Item(n)->GetData());
632 }
633 }
634
635 wxStringList::wxStringList()
636 {
637 DeleteContents(true);
638 }
639
640 // Variable argument list, terminated by a zero
641 // Makes new storage for the strings
642 wxStringList::wxStringList (const wxChar *first, ...)
643 {
644 DeleteContents(true);
645 if ( !first )
646 return;
647
648 va_list ap;
649 va_start(ap, first);
650
651 const wxChar *s = first;
652 for (;;)
653 {
654 Add(s);
655
656 // icc gives this warning in its own va_arg() macro, argh
657 #ifdef __INTELC__
658 #pragma warning(push)
659 #pragma warning(disable: 1684)
660 #endif
661
662 s = va_arg(ap, const wxChar *);
663
664 #ifdef __INTELC__
665 #pragma warning(pop)
666 #endif
667
668 if ( !s )
669 break;
670 }
671
672 va_end(ap);
673 }
674
675 // Only makes new strings if arg is true
676 wxChar **wxStringList::ListToArray(bool new_copies) const
677 {
678 wxChar **string_array = new wxChar *[GetCount()];
679 wxStringListNode *node = GetFirst();
680 for (size_t i = 0; i < GetCount(); i++)
681 {
682 wxChar *s = node->GetData();
683 if ( new_copies )
684 string_array[i] = MYcopystring(s);
685 else
686 string_array[i] = s;
687 node = node->GetNext();
688 }
689
690 return string_array;
691 }
692
693 // Checks whether s is a member of the list
694 bool wxStringList::Member(const wxChar *s) const
695 {
696 for ( wxStringListNode *node = GetFirst(); node; node = node->GetNext() )
697 {
698 const wxChar *s1 = node->GetData();
699 if (s == s1 || wxStrcmp (s, s1) == 0)
700 return true;
701 }
702
703 return false;
704 }
705
706 #ifdef __WXWINCE__
707 extern "C" int __cdecl
708 #else
709 extern "C" int LINKAGEMODE
710 #endif
711
712 wx_comparestrings(const void *arg1, const void *arg2)
713 {
714 wxChar **s1 = (wxChar **) arg1;
715 wxChar **s2 = (wxChar **) arg2;
716
717 return wxStrcmp (*s1, *s2);
718 }
719
720 // Sort a list of strings - deallocates old nodes, allocates new
721 void wxStringList::Sort()
722 {
723 size_t N = GetCount();
724 wxChar **array = new wxChar *[N];
725 wxStringListNode *node;
726
727 size_t i = 0;
728 for ( node = GetFirst(); node; node = node->GetNext() )
729 {
730 array[i++] = node->GetData();
731 }
732
733 qsort (array, N, sizeof (wxChar *), wx_comparestrings);
734
735 i = 0;
736 for ( node = GetFirst(); node; node = node->GetNext() )
737 node->SetData( array[i++] );
738
739 delete [] array;
740 }
741
742 wxNode *wxStringList::Add(const wxChar *s)
743 {
744 return (wxNode *)(wxStringListBase::Node *)
745 wxStringListBase::Append(MYcopystring(s));
746 }
747
748 wxNode *wxStringList::Prepend(const wxChar *s)
749 {
750 return (wxNode *)(wxStringListBase::Node *)
751 wxStringListBase::Insert(MYcopystring(s));
752 }
753
754 #endif // wxLIST_COMPATIBILITY
755
756 #else // wxUSE_STL = 1
757
758 #include "wx/listimpl.cpp"
759 WX_DEFINE_LIST(wxObjectList)
760
761 // with wxUSE_STL wxStringList contains wxString objects, not pointers
762 void _WX_LIST_HELPER_wxStringListBase::DeleteFunction( wxString WXUNUSED(X) )
763 {
764 }
765
766 wxStringListBase::BaseListType wxStringListBase::EmptyList;
767
768 #endif // !wxUSE_STL

  ViewVC Help
Powered by ViewVC 1.1.22