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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 31 - (show annotations) (download)
Tue Sep 7 03:24:11 2010 UTC (10 years, 2 months ago) by william
File size: 23438 byte(s)
committing r3113 initial commit again...
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/hash.cpp
3 // Purpose: wxHashTable implementation
4 // Author: Julian Smart
5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
6 // Created: 01/02/97
7 // RCS-ID: $Id: hash.cpp 49529 2007-10-30 00:32:18Z 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 #ifndef WX_PRECOMP
28 #include "wx/list.h"
29 #include "wx/hash.h"
30 #endif
31
32 #if wxUSE_OLD_HASH_TABLE
33
34 #include <string.h>
35 #include <stdarg.h>
36
37 // ----------------------------------------------------------------------------
38 // wxWin macros
39 // ----------------------------------------------------------------------------
40
41 IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
42
43 // ============================================================================
44 // implementation
45 // ============================================================================
46
47 // ----------------------------------------------------------------------------
48 // wxHashTablleBase for working with "void *" data
49 // ----------------------------------------------------------------------------
50
51 wxHashTableBase::wxHashTableBase()
52 {
53 m_deleteContents = false;
54 m_hashTable = (wxListBase **)NULL;
55 m_hashSize = 0;
56 m_count = 0;
57 m_keyType = wxKEY_NONE;
58 }
59
60 void wxHashTableBase::Create(wxKeyType keyType, size_t size)
61 {
62 Destroy();
63
64 m_hashSize = size;
65 m_keyType = keyType;
66 m_hashTable = new wxListBase *[size];
67 for ( size_t n = 0; n < m_hashSize; n++ )
68 {
69 m_hashTable[n] = (wxListBase *) NULL;
70 }
71 }
72
73 void wxHashTableBase::Destroy()
74 {
75 if ( m_hashTable )
76 {
77 for ( size_t n = 0; n < m_hashSize; n++ )
78 {
79 delete m_hashTable[n];
80 }
81
82 delete [] m_hashTable;
83
84 m_hashTable = (wxListBase **)NULL;
85
86 m_count = 0;
87 }
88 }
89
90 void wxHashTableBase::DeleteContents(bool flag)
91 {
92 m_deleteContents = flag;
93 for ( size_t n = 0; n < m_hashSize; n++ )
94 {
95 if ( m_hashTable[n] )
96 {
97 m_hashTable[n]->DeleteContents(flag);
98 }
99 }
100 }
101
102 wxNodeBase *wxHashTableBase::GetNode(long key, long value) const
103 {
104 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
105
106 wxNodeBase *node;
107 if ( m_hashTable[slot] )
108 {
109 node = m_hashTable[slot]->Find(wxListKey(value));
110 }
111 else
112 {
113 node = (wxNodeBase *)NULL;
114 }
115
116 return node;
117 }
118
119 #if WXWIN_COMPATIBILITY_2_4
120
121 // ----------------------------------------------------------------------------
122 // wxHashTableLong
123 // ----------------------------------------------------------------------------
124
125 wxHashTableLong::~wxHashTableLong()
126 {
127 Destroy();
128 }
129
130 void wxHashTableLong::Init(size_t size)
131 {
132 m_hashSize = size;
133 m_values = new wxArrayLong *[size];
134 m_keys = new wxArrayLong *[size];
135
136 for ( size_t n = 0; n < m_hashSize; n++ )
137 {
138 m_values[n] =
139 m_keys[n] = (wxArrayLong *)NULL;
140 }
141
142 m_count = 0;
143 }
144
145 void wxHashTableLong::Create(size_t size)
146 {
147 Init(size);
148 }
149
150 void wxHashTableLong::Destroy()
151 {
152 for ( size_t n = 0; n < m_hashSize; n++ )
153 {
154 delete m_values[n];
155 delete m_keys[n];
156 }
157
158 delete [] m_values;
159 delete [] m_keys;
160 m_hashSize = 0;
161 m_count = 0;
162 }
163
164 void wxHashTableLong::Put(long key, long value)
165 {
166 wxCHECK_RET( m_hashSize, _T("must call Create() first") );
167
168 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
169
170 if ( !m_keys[slot] )
171 {
172 m_keys[slot] = new wxArrayLong;
173 m_values[slot] = new wxArrayLong;
174 }
175
176 m_keys[slot]->Add(key);
177 m_values[slot]->Add(value);
178
179 m_count++;
180 }
181
182 long wxHashTableLong::Get(long key) const
183 {
184 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
185
186 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
187
188 wxArrayLong *keys = m_keys[slot];
189 if ( keys )
190 {
191 size_t count = keys->GetCount();
192 for ( size_t n = 0; n < count; n++ )
193 {
194 if ( keys->Item(n) == key )
195 {
196 return m_values[slot]->Item(n);
197 }
198 }
199 }
200
201 return wxNOT_FOUND;
202 }
203
204 long wxHashTableLong::Delete(long key)
205 {
206 wxCHECK_MSG( m_hashSize, wxNOT_FOUND, _T("must call Create() first") );
207
208 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
209
210 wxArrayLong *keys = m_keys[slot];
211 if ( keys )
212 {
213 size_t count = keys->GetCount();
214 for ( size_t n = 0; n < count; n++ )
215 {
216 if ( keys->Item(n) == key )
217 {
218 long val = m_values[slot]->Item(n);
219
220 keys->RemoveAt(n);
221 m_values[slot]->RemoveAt(n);
222
223 m_count--;
224
225 return val;
226 }
227 }
228 }
229
230 return wxNOT_FOUND;
231 }
232
233 // ----------------------------------------------------------------------------
234 // wxStringHashTable: more efficient than storing strings in a list
235 // ----------------------------------------------------------------------------
236
237 wxStringHashTable::wxStringHashTable(size_t sizeTable)
238 {
239 m_keys = new wxArrayLong *[sizeTable];
240 m_values = new wxArrayString *[sizeTable];
241
242 m_hashSize = sizeTable;
243 for ( size_t n = 0; n < m_hashSize; n++ )
244 {
245 m_values[n] = (wxArrayString *)NULL;
246 m_keys[n] = (wxArrayLong *)NULL;
247 }
248 }
249
250 wxStringHashTable::~wxStringHashTable()
251 {
252 Destroy();
253 }
254
255 void wxStringHashTable::Destroy()
256 {
257 for ( size_t n = 0; n < m_hashSize; n++ )
258 {
259 delete m_values[n];
260 delete m_keys[n];
261 }
262
263 delete [] m_values;
264 delete [] m_keys;
265 m_hashSize = 0;
266 }
267
268 void wxStringHashTable::Put(long key, const wxString& value)
269 {
270 wxCHECK_RET( m_hashSize, _T("must call Create() first") );
271
272 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
273
274 if ( !m_keys[slot] )
275 {
276 m_keys[slot] = new wxArrayLong;
277 m_values[slot] = new wxArrayString;
278 }
279
280 m_keys[slot]->Add(key);
281 m_values[slot]->Add(value);
282 }
283
284 wxString wxStringHashTable::Get(long key, bool *wasFound) const
285 {
286 wxCHECK_MSG( m_hashSize, wxEmptyString, _T("must call Create() first") );
287
288 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
289
290 wxArrayLong *keys = m_keys[slot];
291 if ( keys )
292 {
293 size_t count = keys->GetCount();
294 for ( size_t n = 0; n < count; n++ )
295 {
296 if ( keys->Item(n) == key )
297 {
298 if ( wasFound )
299 *wasFound = true;
300
301 return m_values[slot]->Item(n);
302 }
303 }
304 }
305
306 if ( wasFound )
307 *wasFound = false;
308
309 return wxEmptyString;
310 }
311
312 bool wxStringHashTable::Delete(long key) const
313 {
314 wxCHECK_MSG( m_hashSize, false, _T("must call Create() first") );
315
316 size_t slot = (size_t)abs((int)(key % (long)m_hashSize));
317
318 wxArrayLong *keys = m_keys[slot];
319 if ( keys )
320 {
321 size_t count = keys->GetCount();
322 for ( size_t n = 0; n < count; n++ )
323 {
324 if ( keys->Item(n) == key )
325 {
326 keys->RemoveAt(n);
327 m_values[slot]->RemoveAt(n);
328 return true;
329 }
330 }
331 }
332
333 return false;
334 }
335
336 #endif // WXWIN_COMPATIBILITY_2_4
337
338 // ----------------------------------------------------------------------------
339 // old not type safe wxHashTable
340 // ----------------------------------------------------------------------------
341
342 wxHashTable::wxHashTable (int the_key_type, int size)
343 {
344 n = 0;
345 hash_table = (wxList**) NULL;
346 Create(the_key_type, size);
347 m_count = 0;
348 m_deleteContents = false;
349 /*
350 n = size;
351 current_position = -1;
352 current_node = (wxNode *) NULL;
353
354 key_type = the_key_type;
355 hash_table = new wxList *[size];
356 int i;
357 for (i = 0; i < size; i++)
358 hash_table[i] = (wxList *) NULL;
359 */
360 }
361
362 wxHashTable::~wxHashTable ()
363 {
364 Destroy();
365 }
366
367 void wxHashTable::Destroy()
368 {
369 if (!hash_table) return;
370 int i;
371 for (i = 0; i < n; i++)
372 if (hash_table[i])
373 delete hash_table[i];
374 delete[] hash_table;
375 hash_table = NULL;
376 }
377
378 bool wxHashTable::Create(int the_key_type, int size)
379 {
380 Destroy();
381
382 n = size;
383 current_position = -1;
384 current_node = (wxNode *) NULL;
385
386 key_type = the_key_type;
387 hash_table = new wxList *[size];
388 int i;
389 for (i = 0; i < size; i++)
390 hash_table[i] = (wxList *) NULL;
391 return true;
392 }
393
394
395 void wxHashTable::DoCopy(const wxHashTable& table)
396 {
397 n = table.n;
398 m_count = table.m_count;
399 current_position = table.current_position;
400 current_node = NULL; // doesn't matter - Next() will reconstruct it
401 key_type = table.key_type;
402
403 hash_table = new wxList *[n];
404 for (int i = 0; i < n; i++) {
405 if (table.hash_table[i] == NULL)
406 hash_table[i] = NULL;
407 else {
408 hash_table[i] = new wxList(key_type);
409 *hash_table[i] = *(table.hash_table[i]);
410 }
411 }
412 }
413
414 void wxHashTable::Put (long key, long value, wxObject * object)
415 {
416 // Should NEVER be
417 long k = (long) key;
418
419 int position = (int) (k % n);
420 if (position < 0) position = -position;
421
422 if (!hash_table[position])
423 {
424 hash_table[position] = new wxList (wxKEY_INTEGER);
425 if (m_deleteContents) hash_table[position]->DeleteContents(true);
426 }
427
428 hash_table[position]->Append (value, object);
429 m_count++;
430 }
431
432 void wxHashTable::Put (long key, const wxChar *value, wxObject * object)
433 {
434 // Should NEVER be
435 long k = (long) key;
436
437 int position = (int) (k % n);
438 if (position < 0) position = -position;
439
440 if (!hash_table[position])
441 {
442 hash_table[position] = new wxList (wxKEY_STRING);
443 if (m_deleteContents) hash_table[position]->DeleteContents(true);
444 }
445
446 hash_table[position]->Append (value, object);
447 m_count++;
448 }
449
450 void wxHashTable::Put (long key, wxObject * object)
451 {
452 // Should NEVER be
453 long k = (long) key;
454
455 int position = (int) (k % n);
456 if (position < 0) position = -position;
457
458 if (!hash_table[position])
459 {
460 hash_table[position] = new wxList (wxKEY_INTEGER);
461 if (m_deleteContents) hash_table[position]->DeleteContents(true);
462 }
463
464 hash_table[position]->Append (k, object);
465 m_count++;
466 }
467
468 void wxHashTable::Put (const wxChar *key, wxObject * object)
469 {
470 int position = (int) (MakeKey (key) % n);
471 if (position < 0) position = -position;
472
473 if (!hash_table[position])
474 {
475 hash_table[position] = new wxList (wxKEY_STRING);
476 if (m_deleteContents) hash_table[position]->DeleteContents(true);
477 }
478
479 hash_table[position]->Append (key, object);
480 m_count++;
481 }
482
483 wxObject *wxHashTable::Get (long key, long value) const
484 {
485 // Should NEVER be
486 long k = (long) key;
487
488 int position = (int) (k % n);
489 if (position < 0) position = -position;
490
491 if (!hash_table[position])
492 return (wxObject *) NULL;
493 else
494 {
495 wxNode *node = hash_table[position]->Find (value);
496 if (node)
497 return node->GetData ();
498 else
499 return (wxObject *) NULL;
500 }
501 }
502
503 wxObject *wxHashTable::Get (long key, const wxChar *value) const
504 {
505 // Should NEVER be
506 long k = (long) key;
507
508 int position = (int) (k % n);
509 if (position < 0) position = -position;
510
511 if (!hash_table[position])
512 return (wxObject *) NULL;
513 else
514 {
515 wxNode *node = hash_table[position]->Find (value);
516 if (node)
517 return node->GetData ();
518 else
519 return (wxObject *) NULL;
520 }
521 }
522
523 wxObject *wxHashTable::Get (long key) const
524 {
525 // Should NEVER be
526 long k = (long) key;
527
528 int position = (int) (k % n);
529 if (position < 0) position = -position;
530
531 if (!hash_table[position])
532 return (wxObject *) NULL;
533 else
534 {
535 wxNode *node = hash_table[position]->Find (k);
536 return node ? node->GetData () : (wxObject*)NULL;
537 }
538 }
539
540 wxObject *wxHashTable::Get (const wxChar *key) const
541 {
542 int position = (int) (MakeKey (key) % n);
543 if (position < 0) position = -position;
544
545 if (!hash_table[position])
546 return (wxObject *) NULL;
547 else
548 {
549 wxNode *node = hash_table[position]->Find (key);
550 return node ? node->GetData () : (wxObject*)NULL;
551 }
552 }
553
554 wxObject *wxHashTable::Delete (long key)
555 {
556 // Should NEVER be
557 long k = (long) key;
558
559 int position = (int) (k % n);
560 if (position < 0) position = -position;
561
562 if (!hash_table[position])
563 return (wxObject *) NULL;
564 else
565 {
566 wxNode *node = hash_table[position]->Find (k);
567 if (node)
568 {
569 wxObject *data = node->GetData ();
570 delete node;
571 m_count--;
572 return data;
573 }
574 else
575 return (wxObject *) NULL;
576 }
577 }
578
579 wxObject *wxHashTable::Delete (const wxChar *key)
580 {
581 int position = (int) (MakeKey (key) % n);
582 if (position < 0) position = -position;
583
584 if (!hash_table[position])
585 return (wxObject *) NULL;
586 else
587 {
588 wxNode *node = hash_table[position]->Find (key);
589 if (node)
590 {
591 wxObject *data = node->GetData ();
592 delete node;
593 m_count--;
594 return data;
595 }
596 else
597 return (wxObject *) NULL;
598 }
599 }
600
601 wxObject *wxHashTable::Delete (long key, int value)
602 {
603 // Should NEVER be
604 long k = (long) key;
605
606 int position = (int) (k % n);
607 if (position < 0) position = -position;
608
609 if (!hash_table[position])
610 return (wxObject *) NULL;
611 else
612 {
613 wxNode *node = hash_table[position]->Find (value);
614 if (node)
615 {
616 wxObject *data = node->GetData ();
617 delete node;
618 m_count--;
619 return data;
620 }
621 else
622 return (wxObject *) NULL;
623 }
624 }
625
626 wxObject *wxHashTable::Delete (long key, const wxChar *value)
627 {
628 int position = (int) (key % n);
629 if (position < 0) position = -position;
630
631 if (!hash_table[position])
632 return (wxObject *) NULL;
633 else
634 {
635 wxNode *node = hash_table[position]->Find (value);
636 if (node)
637 {
638 wxObject *data = node->GetData ();
639 delete node;
640 m_count--;
641 return data;
642 }
643 else
644 return (wxObject *) NULL;
645 }
646 }
647
648 long wxHashTable::MakeKey (const wxChar *string) const
649 {
650 long int_key = 0;
651
652 while (*string)
653 int_key += (wxUChar) *string++;
654
655 return int_key;
656 }
657
658 void wxHashTable::BeginFind ()
659 {
660 current_position = -1;
661 current_node = (wxNode *) NULL;
662 }
663
664 wxHashTable::Node* wxHashTable::Next ()
665 {
666 wxNode *found = (wxNode *) NULL;
667 bool end = false;
668 while (!end && !found)
669 {
670 if (!current_node)
671 {
672 current_position++;
673 if (current_position >= n)
674 {
675 current_position = -1;
676 current_node = (wxNode *) NULL;
677 end = true;
678 }
679 else
680 {
681 if (hash_table[current_position])
682 {
683 current_node = hash_table[current_position]->GetFirst ();
684 found = current_node;
685 }
686 }
687 }
688 else
689 {
690 current_node = current_node->GetNext ();
691 found = current_node;
692 }
693 }
694 return found;
695 }
696
697 void wxHashTable::DeleteContents (bool flag)
698 {
699 int i;
700 m_deleteContents = flag;
701 for (i = 0; i < n; i++)
702 {
703 if (hash_table[i])
704 hash_table[i]->DeleteContents (flag);
705 }
706 }
707
708 void wxHashTable::Clear ()
709 {
710 int i;
711 if (hash_table)
712 {
713 for (i = 0; i < n; i++)
714 {
715 if (hash_table[i])
716 hash_table[i]->Clear ();
717 }
718 }
719 m_count = 0;
720 }
721
722 #else // if !wxUSE_OLD_HASH_TABLE
723
724 wxHashTableBase_Node::wxHashTableBase_Node( long key, void* value,
725 wxHashTableBase* table )
726 : m_value( value ), m_hashPtr( table )
727 {
728 m_key.integer = key;
729 }
730
731 wxHashTableBase_Node::wxHashTableBase_Node( const wxChar* key, void* value,
732 wxHashTableBase* table )
733 : m_value( value ), m_hashPtr( table )
734 {
735 m_key.string = wxStrcpy( new wxChar[wxStrlen( key ) + 1], key );
736 }
737
738 wxHashTableBase_Node::~wxHashTableBase_Node()
739 {
740 if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
741 }
742
743 //
744
745 wxHashTableBase::wxHashTableBase()
746 : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
747 m_deleteContents( false )
748 {
749 }
750
751 void wxHashTableBase::Create( wxKeyType keyType, size_t size )
752 {
753 m_keyType = keyType;
754 m_size = size;
755 m_table = new wxHashTableBase_Node*[ m_size ];
756
757 for( size_t i = 0; i < m_size; ++i )
758 m_table[i] = NULL;
759 }
760
761 void wxHashTableBase::Clear()
762 {
763 for( size_t i = 0; i < m_size; ++i )
764 {
765 Node* end = m_table[i];
766
767 if( end == NULL )
768 continue;
769
770 Node *curr, *next = end->GetNext();
771
772 do
773 {
774 curr = next;
775 next = curr->GetNext();
776
777 DoDestroyNode( curr );
778
779 delete curr;
780 }
781 while( curr != end );
782
783 m_table[i] = NULL;
784 }
785
786 m_count = 0;
787 }
788
789 void wxHashTableBase::DoRemoveNode( wxHashTableBase_Node* node )
790 {
791 size_t bucket = ( m_keyType == wxKEY_INTEGER ?
792 node->m_key.integer :
793 MakeKey( node->m_key.string ) ) % m_size;
794
795 if( node->GetNext() == node )
796 {
797 // single-node chain (common case)
798 m_table[bucket] = NULL;
799 }
800 else
801 {
802 Node *start = m_table[bucket], *curr;
803 Node* prev = start;
804
805 for( curr = prev->GetNext(); curr != node;
806 prev = curr, curr = curr->GetNext() ) ;
807
808 DoUnlinkNode( bucket, node, prev );
809 }
810
811 DoDestroyNode( node );
812 }
813
814 void wxHashTableBase::DoDestroyNode( wxHashTableBase_Node* node )
815 {
816 // if it is called from DoRemoveNode, node has already been
817 // removed, from other places it does not matter
818 node->m_hashPtr = NULL;
819
820 if( m_keyType == wxKEY_STRING )
821 delete[] node->m_key.string;
822 if( m_deleteContents )
823 DoDeleteContents( node );
824 }
825
826 void wxHashTableBase::Destroy()
827 {
828 Clear();
829
830 delete[] m_table;
831
832 m_table = NULL;
833 m_size = 0;
834 }
835
836 void wxHashTableBase::DoInsertNode( size_t bucket, wxHashTableBase_Node* node )
837 {
838 if( m_table[bucket] == NULL )
839 {
840 m_table[bucket] = node->m_next = node;
841 }
842 else
843 {
844 Node *prev = m_table[bucket];
845 Node *next = prev->m_next;
846
847 prev->m_next = node;
848 node->m_next = next;
849 m_table[bucket] = node;
850 }
851
852 ++m_count;
853 }
854
855 void wxHashTableBase::DoPut( long key, long hash, void* data )
856 {
857 wxASSERT( m_keyType == wxKEY_INTEGER );
858
859 size_t bucket = size_t(hash) % m_size;
860 Node* node = new wxHashTableBase_Node( key, data, this );
861
862 DoInsertNode( bucket, node );
863 }
864
865 void wxHashTableBase::DoPut( const wxChar* key, long hash, void* data )
866 {
867 wxASSERT( m_keyType == wxKEY_STRING );
868
869 size_t bucket = size_t(hash) % m_size;
870 Node* node = new wxHashTableBase_Node( key, data, this );
871
872 DoInsertNode( bucket, node );
873 }
874
875 void* wxHashTableBase::DoGet( long key, long hash ) const
876 {
877 wxASSERT( m_keyType == wxKEY_INTEGER );
878
879 size_t bucket = size_t(hash) % m_size;
880
881 if( m_table[bucket] == NULL )
882 return NULL;
883
884 Node *first = m_table[bucket]->GetNext(),
885 *curr = first;
886
887 do
888 {
889 if( curr->m_key.integer == key )
890 return curr->m_value;
891
892 curr = curr->GetNext();
893 }
894 while( curr != first );
895
896 return NULL;
897 }
898
899 void* wxHashTableBase::DoGet( const wxChar* key, long hash ) const
900 {
901 wxASSERT( m_keyType == wxKEY_STRING );
902
903 size_t bucket = size_t(hash) % m_size;
904
905 if( m_table[bucket] == NULL )
906 return NULL;
907
908 Node *first = m_table[bucket]->GetNext(),
909 *curr = first;
910
911 do
912 {
913 if( wxStrcmp( curr->m_key.string, key ) == 0 )
914 return curr->m_value;
915
916 curr = curr->GetNext();
917 }
918 while( curr != first );
919
920 return NULL;
921 }
922
923 void wxHashTableBase::DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node,
924 wxHashTableBase_Node* prev )
925 {
926 if( node == m_table[bucket] )
927 m_table[bucket] = prev;
928
929 if( prev == node && prev == node->GetNext() )
930 m_table[bucket] = NULL;
931 else
932 prev->m_next = node->m_next;
933
934 DoDestroyNode( node );
935 --m_count;
936 }
937
938 void* wxHashTableBase::DoDelete( long key, long hash )
939 {
940 wxASSERT( m_keyType == wxKEY_INTEGER );
941
942 size_t bucket = size_t(hash) % m_size;
943
944 if( m_table[bucket] == NULL )
945 return NULL;
946
947 Node *first = m_table[bucket]->GetNext(),
948 *curr = first,
949 *prev = m_table[bucket];
950
951 do
952 {
953 if( curr->m_key.integer == key )
954 {
955 void* retval = curr->m_value;
956 curr->m_value = NULL;
957
958 DoUnlinkNode( bucket, curr, prev );
959 delete curr;
960
961 return retval;
962 }
963
964 prev = curr;
965 curr = curr->GetNext();
966 }
967 while( curr != first );
968
969 return NULL;
970 }
971
972 void* wxHashTableBase::DoDelete( const wxChar* key, long hash )
973 {
974 wxASSERT( m_keyType == wxKEY_STRING );
975
976 size_t bucket = size_t(hash) % m_size;
977
978 if( m_table[bucket] == NULL )
979 return NULL;
980
981 Node *first = m_table[bucket]->GetNext(),
982 *curr = first,
983 *prev = m_table[bucket];
984
985 do
986 {
987 if( wxStrcmp( curr->m_key.string, key ) == 0 )
988 {
989 void* retval = curr->m_value;
990 curr->m_value = NULL;
991
992 DoUnlinkNode( bucket, curr, prev );
993 delete curr;
994
995 return retval;
996 }
997
998 prev = curr;
999 curr = curr->GetNext();
1000 }
1001 while( curr != first );
1002
1003 return NULL;
1004 }
1005
1006 long wxHashTableBase::MakeKey( const wxChar *str )
1007 {
1008 long int_key = 0;
1009
1010 while( *str )
1011 int_key += (wxUChar)*str++;
1012
1013 return int_key;
1014 }
1015
1016 // ----------------------------------------------------------------------------
1017 // wxHashTable
1018 // ----------------------------------------------------------------------------
1019
1020 wxHashTable::wxHashTable( const wxHashTable& table )
1021 : wxHashTableBase()
1022 {
1023 DoCopy( table );
1024 }
1025
1026 const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
1027 {
1028 Destroy();
1029 DoCopy( table );
1030
1031 return *this;
1032 }
1033
1034 void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
1035 {
1036 Create( m_keyType, m_size );
1037
1038 wxFAIL;
1039 }
1040
1041 void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
1042 {
1043 delete ((wxHashTable_Node*)node)->GetData();
1044 }
1045
1046 void wxHashTable::GetNextNode( size_t bucketStart )
1047 {
1048 for( size_t i = bucketStart; i < m_size; ++i )
1049 {
1050 if( m_table[i] != NULL )
1051 {
1052 m_curr = ((Node*)m_table[i])->GetNext();
1053 m_currBucket = i;
1054 return;
1055 }
1056 }
1057
1058 m_curr = NULL;
1059 m_currBucket = 0;
1060 }
1061
1062 wxHashTable::Node* wxHashTable::Next()
1063 {
1064 if( m_curr == NULL )
1065 GetNextNode( 0 );
1066 else
1067 {
1068 m_curr = m_curr->GetNext();
1069
1070 if( m_curr == ( (Node*)m_table[m_currBucket] )->GetNext() )
1071 GetNextNode( m_currBucket + 1 );
1072 }
1073
1074 return m_curr;
1075 }
1076
1077 #endif // !wxUSE_OLD_HASH_TABLE

  ViewVC Help
Powered by ViewVC 1.1.22