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