]>
Commit | Line | Data |
---|---|---|
1 | ///////////////////////////////////////////////////////////////////////////// | |
2 | // Name: hashmap.cpp | |
3 | // Purpose: wxHashMap implementation | |
4 | // Author: Mattia Barbon | |
5 | // Modified by: | |
6 | // Created: 29/01/2002 | |
7 | // RCS-ID: $Id$ | |
8 | // Copyright: (c) Mattia Barbon | |
9 | // Licence: wxWindows licence | |
10 | ///////////////////////////////////////////////////////////////////////////// | |
11 | ||
12 | #if defined(__GNUG__) && !defined(NO_GCC_PRAGMA) | |
13 | #pragma implementation "hashmap.h" | |
14 | #endif | |
15 | ||
16 | // For compilers that support precompilation, includes "wx.h". | |
17 | #include "wx/wxprec.h" | |
18 | ||
19 | #ifdef __BORLANDC__ | |
20 | #pragma hdrstop | |
21 | #endif | |
22 | ||
23 | #include "wx/hashmap.h" | |
24 | ||
25 | /* FYI: This is the "One-at-a-Time" algorithm by Bob Jenkins */ | |
26 | /* from requirements by Colin Plumb. */ | |
27 | /* (http://burtleburtle.net/bob/hash/doobs.html) */ | |
28 | /* adapted from Perl sources ( hv.h ) */ | |
29 | unsigned long wxStringHash::wxCharStringHash( const wxChar* k ) | |
30 | { | |
31 | unsigned long hash = 0; | |
32 | ||
33 | while( *k ) | |
34 | { | |
35 | hash += *k++; | |
36 | hash += (hash << 10); | |
37 | hash ^= (hash >> 6); | |
38 | } | |
39 | hash += (hash << 3); | |
40 | hash ^= (hash >> 11); | |
41 | ||
42 | return hash + (hash << 15); | |
43 | } | |
44 | ||
45 | #if wxUSE_UNICODE | |
46 | unsigned long wxStringHash::charStringHash( const char* k ) | |
47 | { | |
48 | unsigned long hash = 0; | |
49 | ||
50 | while( *k ) | |
51 | { | |
52 | hash += *k++; | |
53 | hash += (hash << 10); | |
54 | hash ^= (hash >> 6); | |
55 | } | |
56 | hash += (hash << 3); | |
57 | hash ^= (hash >> 11); | |
58 | ||
59 | return hash + (hash << 15); | |
60 | } | |
61 | #endif | |
62 | ||
63 | /* from SGI STL */ | |
64 | const unsigned long _wxHashTableBase2::ms_primes[prime_count] = | |
65 | { | |
66 | 7ul, 13ul, 29ul, | |
67 | 53ul, 97ul, 193ul, 389ul, 769ul, | |
68 | 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, | |
69 | 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, | |
70 | 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, | |
71 | 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, | |
72 | 1610612741ul, 3221225473ul, 4294967291ul | |
73 | }; | |
74 | ||
75 | unsigned long _wxHashTableBase2::GetNextPrime( unsigned long n ) | |
76 | { | |
77 | const unsigned long* ptr = &ms_primes[0]; | |
78 | for( size_t i = 0; i < prime_count; ++i, ++ptr ) | |
79 | { | |
80 | if( n < *ptr ) | |
81 | return *ptr; | |
82 | } | |
83 | ||
84 | /* someone might try to alloc a 2^32-element hash table */ | |
85 | wxFAIL_MSG( _T("hash table too big?") ); | |
86 | ||
87 | /* quiet warning */ | |
88 | return 0; | |
89 | } | |
90 | ||
91 | unsigned long _wxHashTableBase2::GetPreviousPrime( unsigned long n ) | |
92 | { | |
93 | const unsigned long* ptr = &ms_primes[prime_count - 1]; | |
94 | ||
95 | for( size_t i = 0; i < prime_count; ++i, --ptr ) | |
96 | { | |
97 | if( n > *ptr ) | |
98 | return *ptr; | |
99 | } | |
100 | ||
101 | /* quiet warning */ | |
102 | return 1; | |
103 | } | |
104 | ||
105 | void _wxHashTableBase2::DeleteNodes( size_t buckets, | |
106 | _wxHashTable_NodeBase** table, | |
107 | NodeDtor dtor ) | |
108 | { | |
109 | size_t i; | |
110 | ||
111 | for( i = 0; i < buckets; ++i ) | |
112 | { | |
113 | _wxHashTable_NodeBase* node = table[i]; | |
114 | _wxHashTable_NodeBase* tmp; | |
115 | ||
116 | while( node ) | |
117 | { | |
118 | tmp = node->m_nxt; | |
119 | dtor( node ); | |
120 | node = tmp; | |
121 | } | |
122 | } | |
123 | ||
124 | memset( table, 0, buckets * sizeof(void*) ); | |
125 | } | |
126 | ||
127 | void _wxHashTableBase2::CopyHashTable( _wxHashTable_NodeBase** srcTable, | |
128 | size_t srcBuckets, | |
129 | _wxHashTableBase2* dst, | |
130 | _wxHashTable_NodeBase** dstTable, | |
131 | size_t dstBuckets, | |
132 | BucketFromNode func, ProcessNode proc ) | |
133 | { | |
134 | // for compatibility with wxHashTable (to avoid reimplementig it | |
135 | // from scratch), we need to preserve the order of nodes in a | |
136 | // source bucket when copying the table, hence, to avoid | |
137 | // allocating an auxiliary table we use a circular list for each | |
138 | // bucket, and we keep the *tail* of each list in dstTable[i], to | |
139 | // be able to append nodes in O(1) time. Wen we're done copying, | |
140 | // we adjust dstTable[i] to point at the head of the list and we | |
141 | // break the circular list into a linear one. | |
142 | size_t i; | |
143 | ||
144 | for( i = 0; i < srcBuckets; ++i ) | |
145 | { | |
146 | _wxHashTable_NodeBase* nextnode; | |
147 | ||
148 | for( _wxHashTable_NodeBase* node = srcTable[i]; node; node = nextnode ) | |
149 | { | |
150 | size_t bucket = func( dst, node ); | |
151 | ||
152 | nextnode = node->m_nxt; | |
153 | _wxHashTable_NodeBase* newnode = proc( node ); | |
154 | if( dstTable[bucket] ) | |
155 | { | |
156 | newnode->m_nxt = dstTable[bucket]->m_nxt; // head of the list | |
157 | dstTable[bucket]->m_nxt = newnode; | |
158 | dstTable[bucket] = newnode; | |
159 | } | |
160 | else | |
161 | dstTable[bucket] = newnode->m_nxt = newnode; | |
162 | } | |
163 | } | |
164 | ||
165 | for( i = 0; i < dstBuckets; ++i ) | |
166 | { | |
167 | if( dstTable[i] ) | |
168 | { | |
169 | _wxHashTable_NodeBase* tmp = dstTable[i]; | |
170 | dstTable[i] = dstTable[i]->m_nxt; | |
171 | tmp->m_nxt = NULL; | |
172 | } | |
173 | } | |
174 | } | |
175 | ||
176 | _wxHashTable_NodeBase* _wxHashTableBase2::DummyProcessNode(_wxHashTable_NodeBase* node) | |
177 | { | |
178 | return node; | |
179 | } | |
180 |