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
41IMPLEMENT_DYNAMIC_CLASS(wxHashTable, wxObject)
42
43// ============================================================================
44// implementation
45// ============================================================================
46
47// ----------------------------------------------------------------------------
48// wxHashTablleBase for working with "void *" data
49// ----------------------------------------------------------------------------
50
51wxHashTableBase::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
60void 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
73void 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
90void 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
102wxNodeBase *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
125wxHashTableLong::~wxHashTableLong()
126{
127    Destroy();
128}
129
130void 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
145void wxHashTableLong::Create(size_t size)
146{
147    Init(size);
148}
149
150void 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
164void 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
182long 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
204long 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
237wxStringHashTable::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
250wxStringHashTable::~wxStringHashTable()
251{
252    Destroy();
253}
254
255void 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
268void 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
284wxString 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
312bool 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
342wxHashTable::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
362wxHashTable::~wxHashTable ()
363{
364  Destroy();
365}
366
367void 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
378bool 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
395void 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
414void 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
432void 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
450void 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
468void 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
483wxObject *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
503wxObject *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
523wxObject *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
540wxObject *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
554wxObject *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
579wxObject *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
601wxObject *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
626wxObject *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
648long 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
658void wxHashTable::BeginFind ()
659{
660  current_position = -1;
661  current_node = (wxNode *) NULL;
662}
663
664wxHashTable::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
697void 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
708void 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
724wxHashTableBase_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
731wxHashTableBase_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
738wxHashTableBase_Node::~wxHashTableBase_Node()
739{
740    if( m_hashPtr ) m_hashPtr->DoRemoveNode( this );
741}
742
743//
744
745wxHashTableBase::wxHashTableBase()
746    : m_size( 0 ), m_count( 0 ), m_table( NULL ), m_keyType( wxKEY_NONE ),
747      m_deleteContents( false )
748{
749}
750
751void 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
761void 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
789void 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
814void 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
826void wxHashTableBase::Destroy()
827{
828    Clear();
829
830    delete[] m_table;
831
832    m_table = NULL;
833    m_size = 0;
834}
835
836void 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
855void 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
865void 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
875void* 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
899void* 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
923void 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
938void* 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
972void* 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
1006long 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
1020wxHashTable::wxHashTable( const wxHashTable& table )
1021           : wxHashTableBase()
1022{
1023    DoCopy( table );
1024}
1025
1026const wxHashTable& wxHashTable::operator=( const wxHashTable& table )
1027{
1028    Destroy();
1029    DoCopy( table );
1030
1031    return *this;
1032}
1033
1034void wxHashTable::DoCopy( const wxHashTable& WXUNUSED(table) )
1035{
1036    Create( m_keyType, m_size );
1037
1038    wxFAIL;
1039}
1040
1041void wxHashTable::DoDeleteContents( wxHashTableBase_Node* node )
1042{
1043    delete ((wxHashTable_Node*)node)->GetData();
1044}
1045
1046void 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
1062wxHashTable::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
1078