1 /////////////////////////////////////////////////////////////////////////////
2 // Name: src/common/hashmap.cpp
3 // Purpose: wxHashMap implementation
4 // Author: Mattia Barbon
5 // Modified by:
6 // Created: 29/01/2002
7 // RCS-ID: $Id: hashmap.cpp 39802 2006-06-20 10:24:07Z ABX $
8 // Copyright: (c) Mattia Barbon
9 // Licence: wxWindows licence
10 /////////////////////////////////////////////////////////////////////////////
11
12 // For compilers that support precompilation, includes "wx.h".
13 #include "wx/wxprec.h"
14
15 #ifdef __BORLANDC__
16 #pragma hdrstop
17 #endif
18
19 #include "wx/hashmap.h"
20
21 /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */
22 /* from requirements by Colin Plumb. */
23 /* (http://burtleburtle.net/bob/hash/doobs.html) */
24 /* adapted from Perl sources ( hv.h ) */
wxCharStringHash(const wxChar * k)25 unsigned long wxStringHash::wxCharStringHash( const wxChar* k )
26 {
27 unsigned long hash = 0;
28
29 while( *k )
30 {
31 hash += *k++;
32 hash += (hash << 10);
33 hash ^= (hash >> 6);
34 }
35 hash += (hash << 3);
36 hash ^= (hash >> 11);
37
38 return hash + (hash << 15);
39 }
40
41 #if wxUSE_UNICODE
charStringHash(const char * k)42 unsigned long wxStringHash::charStringHash( const char* k )
43 {
44 unsigned long hash = 0;
45
46 while( *k )
47 {
48 hash += *k++;
49 hash += (hash << 10);
50 hash ^= (hash >> 6);
51 }
52 hash += (hash << 3);
53 hash ^= (hash >> 11);
54
55 return hash + (hash << 15);
56 }
57 #endif
58
59 #if !wxUSE_STL || !defined(HAVE_STL_HASH_MAP)
60
61 /* from SGI STL */
62 const unsigned long _wxHashTableBase2::ms_primes[prime_count] =
63 {
64 7ul, 13ul, 29ul,
65 53ul, 97ul, 193ul, 389ul, 769ul,
66 1543ul, 3079ul, 6151ul, 12289ul, 24593ul,
67 49157ul, 98317ul, 196613ul, 393241ul, 786433ul,
68 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul,
69 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul,
70 1610612741ul, 3221225473ul, 4294967291ul
71 };
72
GetNextPrime(unsigned long n)73 unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n )
74 {
75 const unsigned long* ptr = &ms_primes[0];
76 for( size_t i = 0; i < prime_count; ++i, ++ptr )
77 {
78 if( n < *ptr )
79 return *ptr;
80 }
81
82 /* someone might try to alloc a 2^32-element hash table */
83 wxFAIL_MSG( _T("hash table too big?") );
84
85 /* quiet warning */
86 return 0;
87 }
88
GetPreviousPrime(unsigned long n)89 unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n )
90 {
91 const unsigned long* ptr = &ms_primes[prime_count - 1];
92
93 for( size_t i = 0; i < prime_count; ++i, --ptr )
94 {
95 if( n > *ptr )
96 return *ptr;
97 }
98
99 /* quiet warning */
100 return 1;
101 }
102
DeleteNodes(size_t buckets,_wxHashTable_NodeBase ** table,NodeDtor dtor)103 void _wxHashTableBase2::DeleteNodes( size_t buckets,
104 _wxHashTable_NodeBase** table,
105 NodeDtor dtor )
106 {
107 size_t i;
108
109 for( i = 0; i < buckets; ++i )
110 {
111 _wxHashTable_NodeBase* node = table[i];
112 _wxHashTable_NodeBase* tmp;
113
114 while( node )
115 {
116 tmp = node->m_nxt;
117 dtor( node );
118 node = tmp;
119 }
120 }
121
122 memset( table, 0, buckets * sizeof(void*) );
123 }
124
CopyHashTable(_wxHashTable_NodeBase ** srcTable,size_t srcBuckets,_wxHashTableBase2 * dst,_wxHashTable_NodeBase ** dstTable,BucketFromNode func,ProcessNode proc)125 void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable,
126 size_t srcBuckets,
127 _wxHashTableBase2* dst,
128 _wxHashTable_NodeBase** dstTable,
129 BucketFromNode func, ProcessNode proc )
130 {
131 for( size_t i = 0; i < srcBuckets; ++i )
132 {
133 _wxHashTable_NodeBase* nextnode;
134
135 for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode )
136 {
137 size_t bucket = func( dst, node );
138
139 nextnode = node->m_nxt;
140 _wxHashTable_NodeBase* newnode = proc( node );
141 newnode->m_nxt = dstTable[bucket];
142 dstTable[bucket] = newnode;
143 }
144 }
145 }
146
DummyProcessNode(_wxHashTable_NodeBase * node)147 _wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node)
148 {
149 return node;
150 }
151
152 #endif // !wxUSE_STL || !defined(HAVE_STL_HASH_MAP)
153