]>
Commit | Line | Data |
---|---|---|
0508ba2a | 1 | ///////////////////////////////////////////////////////////////////////////// |
a4f24526 | 2 | // Name: hashmap.h |
0508ba2a MB |
3 | // Purpose: wxHashMap class |
4 | // Author: Mattia Barbon | |
376e1129 | 5 | // Modified by: |
0508ba2a MB |
6 | // Created: 29/01/2002 |
7 | // RCS-ID: $Id$ | |
8 | // Copyright: (c) Mattia Barbon | |
9 | // Licence: wxWindows licence | |
10 | ///////////////////////////////////////////////////////////////////////////// | |
11 | ||
12 | #ifndef _WX_HASHMAP_H_ | |
13 | #define _WX_HASHMAP_H_ | |
14 | ||
af49c4b8 | 15 | #if defined(__GNUG__) && !defined(__APPLE__) |
0508ba2a MB |
16 | #pragma interface "hashmap.h" |
17 | #endif | |
18 | ||
a4f24526 | 19 | #include "wx/string.h" |
0508ba2a MB |
20 | |
21 | // private | |
ac6e54ee | 22 | struct WXDLLEXPORT _wxHashTable_NodeBase |
0508ba2a MB |
23 | { |
24 | _wxHashTable_NodeBase() : m_nxt(0) {} | |
25 | ||
26 | _wxHashTable_NodeBase* m_nxt; | |
27 | }; | |
28 | ||
29 | // private | |
ac6e54ee | 30 | class WXDLLEXPORT _wxHashTableBase2 |
0508ba2a MB |
31 | { |
32 | public: | |
33 | typedef void (*NodeDtor)(_wxHashTable_NodeBase*); | |
376e1129 | 34 | typedef unsigned long (*BucketFromNode)(_wxHashTableBase2*,_wxHashTable_NodeBase*); |
0508ba2a MB |
35 | typedef _wxHashTable_NodeBase* (*ProcessNode)(_wxHashTable_NodeBase*); |
36 | protected: | |
37 | static _wxHashTable_NodeBase* DummyProcessNode(_wxHashTable_NodeBase* node); | |
38 | static void DeleteNodes( size_t buckets, _wxHashTable_NodeBase** table, | |
39 | NodeDtor dtor ); | |
40 | static _wxHashTable_NodeBase* GetFirstNode( size_t buckets, | |
41 | _wxHashTable_NodeBase** table ) | |
42 | { | |
43 | for( size_t i = 0; i < buckets; ++i ) | |
44 | if( table[i] ) | |
45 | return table[i]; | |
46 | return 0; | |
47 | } | |
48 | ||
376e1129 | 49 | // as static const unsigned prime_count = 31 but works with all compilers |
0508ba2a | 50 | enum { prime_count = 31 }; |
376e1129 | 51 | static const unsigned long ms_primes[prime_count]; |
0508ba2a | 52 | |
376e1129 | 53 | // returns the first prime in ms_primes greater than n |
0508ba2a MB |
54 | static unsigned long GetNextPrime( unsigned long n ); |
55 | ||
376e1129 VZ |
56 | // returns the first prime in ms_primes smaller than n |
57 | // ( or ms_primes[0] if n is very small ) | |
0508ba2a MB |
58 | static unsigned long GetPreviousPrime( unsigned long n ); |
59 | ||
60 | static void CopyHashTable( _wxHashTable_NodeBase** srcTable, | |
61 | size_t srcBuckets, _wxHashTableBase2* dst, | |
62 | _wxHashTable_NodeBase** dstTable, | |
63 | BucketFromNode func, ProcessNode proc ); | |
64 | ||
2b5f62a0 | 65 | static void** AllocTable( size_t sz ) |
0508ba2a | 66 | { |
2b5f62a0 | 67 | return (void **)calloc(sz, sizeof(void*)); |
0508ba2a MB |
68 | } |
69 | }; | |
70 | ||
71 | #define _WX_DECLARE_HASHTABLE( VALUE_T, KEY_T, HASH_T, KEY_EX_T, KEY_EQ_T, CLASSNAME, CLASSEXP, SHOULD_GROW, SHOULD_SHRINK ) \ | |
376e1129 | 72 | CLASSEXP CLASSNAME : protected _wxHashTableBase2 \ |
0508ba2a MB |
73 | { \ |
74 | public: \ | |
75 | typedef KEY_T key_type; \ | |
76 | typedef VALUE_T value_type; \ | |
77 | typedef HASH_T hasher; \ | |
78 | typedef KEY_EQ_T key_equal; \ | |
79 | \ | |
80 | typedef size_t size_type; \ | |
81 | typedef ptrdiff_t difference_type; \ | |
82 | typedef value_type* pointer; \ | |
83 | typedef const value_type* const_pointer; \ | |
84 | typedef value_type& reference; \ | |
85 | typedef const value_type& const_reference; \ | |
86 | /* should these be protected? */ \ | |
87 | typedef const KEY_T const_key_type; \ | |
88 | typedef const VALUE_T const_mapped_type; \ | |
bc850f29 | 89 | public: \ |
0508ba2a MB |
90 | struct Node; \ |
91 | typedef KEY_EX_T key_extractor; \ | |
92 | typedef CLASSNAME Self; \ | |
bc850f29 | 93 | protected: \ |
0508ba2a MB |
94 | Node** m_table; \ |
95 | size_t m_tableBuckets; \ | |
96 | size_t m_items; \ | |
97 | hasher m_hasher; \ | |
98 | key_equal m_equals; \ | |
99 | key_extractor m_getKey; \ | |
bc850f29 | 100 | public: \ |
0508ba2a MB |
101 | struct Node:public _wxHashTable_NodeBase \ |
102 | { \ | |
103 | public: \ | |
104 | Node( const value_type& value ) \ | |
105 | : m_value( value ) {} \ | |
106 | Node* m_next() { return (Node*)this->m_nxt; } \ | |
107 | \ | |
108 | value_type m_value; \ | |
109 | }; \ | |
110 | \ | |
111 | struct Iterator; \ | |
607f710e | 112 | friend struct Iterator; \ |
bc850f29 | 113 | protected: \ |
0508ba2a MB |
114 | static void DeleteNode( _wxHashTable_NodeBase* node ) \ |
115 | { \ | |
116 | delete (Node*)node; \ | |
117 | } \ | |
bc850f29 | 118 | public: \ |
0508ba2a MB |
119 | /* */ \ |
120 | /* forward iterator */ \ | |
121 | /* */ \ | |
122 | struct Iterator \ | |
123 | { \ | |
124 | Node* m_node; \ | |
125 | Self* m_ht; \ | |
126 | \ | |
127 | Iterator() : m_node(0), m_ht(0) {} \ | |
128 | Iterator( Node* node, const Self* ht ) \ | |
129 | : m_node(node), m_ht((Self*)ht) {} \ | |
130 | bool operator ==( const Iterator& it ) const \ | |
131 | { return m_node == it.m_node; } \ | |
132 | bool operator !=( const Iterator& it ) const \ | |
133 | { return m_node != it.m_node; } \ | |
134 | protected: \ | |
135 | Node* GetNextNode() \ | |
136 | { \ | |
376e1129 | 137 | size_type bucket = GetBucketForNode(m_ht,m_node); \ |
0508ba2a MB |
138 | for( size_type i = bucket + 1; i < m_ht->m_tableBuckets; ++i ) \ |
139 | { \ | |
140 | if( m_ht->m_table[i] ) \ | |
141 | return m_ht->m_table[i]; \ | |
142 | } \ | |
143 | return 0; \ | |
144 | } \ | |
145 | \ | |
146 | void PlusPlus() \ | |
147 | { \ | |
148 | Node* next = m_node->m_next(); \ | |
376e1129 | 149 | m_node = next ? next : GetNextNode(); \ |
0508ba2a MB |
150 | } \ |
151 | }; \ | |
152 | \ | |
153 | public: \ | |
154 | struct iterator:public Iterator \ | |
155 | { \ | |
156 | iterator() : Iterator() {} \ | |
157 | iterator( Node* node, Self* ht ) : Iterator( node, ht ) {} \ | |
158 | iterator& operator++() { PlusPlus(); return *this; } \ | |
159 | iterator operator++(int) { iterator it=*this;PlusPlus();return it; } \ | |
160 | reference operator *() const { return m_node->m_value; } \ | |
161 | pointer operator ->() const { return &(m_node->m_value); } \ | |
162 | }; \ | |
163 | \ | |
164 | struct const_iterator:public Iterator \ | |
165 | { \ | |
166 | const_iterator() : Iterator() {} \ | |
167 | const_iterator( Node* node, const Self* ht ) \ | |
168 | : Iterator( node, (Self*)ht ) {} \ | |
169 | const_iterator& operator++() { PlusPlus();return *this; } \ | |
170 | const_iterator operator++(int) { const_iterator it=*this;PlusPlus();return it; } \ | |
171 | const_reference operator *() const { return m_node->m_value; } \ | |
172 | const_pointer operator ->() const { return &(m_node->m_value); } \ | |
173 | }; \ | |
174 | \ | |
2b5f62a0 | 175 | CLASSNAME( size_type sz = 10, const hasher& hfun = hasher(), \ |
0508ba2a MB |
176 | const key_equal& k_eq = key_equal(), \ |
177 | const key_extractor& k_ex = key_extractor() ) \ | |
2b5f62a0 | 178 | : m_tableBuckets( GetNextPrime( sz ) ), \ |
0508ba2a MB |
179 | m_items( 0 ), \ |
180 | m_hasher( hfun ), \ | |
181 | m_equals( k_eq ), \ | |
182 | m_getKey( k_ex ) \ | |
183 | { \ | |
184 | m_table = (Node**)AllocTable( m_tableBuckets ); \ | |
185 | } \ | |
186 | \ | |
187 | CLASSNAME( const Self& ht ) \ | |
188 | : m_table( 0 ), \ | |
189 | m_tableBuckets( 0 ), \ | |
190 | m_items( ht.m_items ), \ | |
191 | m_hasher( ht.m_hasher ), \ | |
192 | m_equals( ht.m_equals ), \ | |
193 | m_getKey( ht.m_getKey ) \ | |
194 | { \ | |
195 | HashCopy( ht ); \ | |
196 | } \ | |
197 | \ | |
198 | const Self& operator=( const Self& ht ) \ | |
199 | { \ | |
200 | clear(); \ | |
201 | m_hasher = ht.m_hasher; \ | |
202 | m_equals = ht.m_equals; \ | |
203 | m_getKey = ht.m_getKey; \ | |
204 | m_items = ht.m_items; \ | |
205 | HashCopy( ht ); \ | |
376e1129 | 206 | return *this; \ |
0508ba2a MB |
207 | } \ |
208 | \ | |
209 | ~CLASSNAME() \ | |
210 | { \ | |
211 | clear(); \ | |
212 | \ | |
376e1129 | 213 | free(m_table); \ |
0508ba2a MB |
214 | } \ |
215 | \ | |
216 | hasher hash_funct() { return m_hasher; } \ | |
217 | key_equal key_eq() { return m_equals; } \ | |
218 | \ | |
219 | /* removes all elements from the hash table, but does not */ \ | |
220 | /* shrink it ( perhaps it should ) */ \ | |
2b5f62a0 VZ |
221 | void clear() \ |
222 | { \ | |
223 | DeleteNodes( m_tableBuckets, (_wxHashTable_NodeBase**)m_table, \ | |
224 | DeleteNode ); \ | |
225 | m_items = 0; \ | |
226 | } \ | |
0508ba2a MB |
227 | \ |
228 | size_type size() const { return m_items; } \ | |
229 | size_type max_size() const { return size_type(-1); } \ | |
230 | bool empty() const { return size() == 0; } \ | |
231 | \ | |
232 | const_iterator end() const { return const_iterator( 0, this ); } \ | |
233 | iterator end() { return iterator( 0, this ); } \ | |
234 | const_iterator begin() const \ | |
235 | { return const_iterator( (Node*)GetFirstNode( m_tableBuckets, (_wxHashTable_NodeBase**)m_table ), this ); }; \ | |
236 | iterator begin() \ | |
237 | { return iterator( (Node*)GetFirstNode( m_tableBuckets, (_wxHashTable_NodeBase**)m_table ), this ); }; \ | |
238 | \ | |
239 | size_type erase( const const_key_type& key ) \ | |
240 | { \ | |
241 | Node** node = GetNodePtr( key ); \ | |
242 | \ | |
243 | if( !node ) \ | |
244 | return 0; \ | |
245 | \ | |
246 | --m_items; \ | |
247 | Node* temp = (*node)->m_next(); \ | |
248 | delete *node; \ | |
249 | (*node) = temp; \ | |
250 | if( SHOULD_SHRINK( m_tableBuckets, m_items ) ) \ | |
251 | ResizeTable( GetPreviousPrime( m_tableBuckets ) - 1 ); \ | |
252 | return 1; \ | |
253 | } \ | |
254 | \ | |
255 | protected: \ | |
256 | static size_type GetBucketForNode( Self* ht, Node* node ) \ | |
257 | { \ | |
258 | return ht->m_hasher( ht->m_getKey( node->m_value ) ) \ | |
259 | % ht->m_tableBuckets; \ | |
260 | } \ | |
261 | static Node* CopyNode( Node* node ) { return new Node( *node ); } \ | |
262 | \ | |
263 | Node* GetOrCreateNode( const value_type& value ) \ | |
264 | { \ | |
265 | const const_key_type& key = m_getKey( value ); \ | |
266 | size_t bucket = m_hasher( key ) % m_tableBuckets; \ | |
267 | Node* node = m_table[bucket]; \ | |
268 | \ | |
269 | while( node ) \ | |
270 | { \ | |
271 | if( m_equals( m_getKey( node->m_value ), key ) ) \ | |
272 | return node; \ | |
273 | node = node->m_next(); \ | |
274 | } \ | |
275 | \ | |
276 | node = new Node( value ); \ | |
277 | node->m_nxt = m_table[bucket]; \ | |
278 | m_table[bucket] = node; \ | |
279 | \ | |
280 | /* must be after the node is inserted */ \ | |
281 | ++m_items; \ | |
282 | if( SHOULD_GROW( m_tableBuckets, m_items ) ) \ | |
283 | ResizeTable( m_tableBuckets ); \ | |
284 | \ | |
285 | return node; \ | |
286 | } \ | |
287 | \ | |
288 | /* returns NULL if not found */ \ | |
289 | Node** GetNodePtr( const const_key_type& key ) const \ | |
290 | { \ | |
291 | unsigned long hash = m_hasher( key ); \ | |
292 | Node** node = &m_table[hash % m_tableBuckets]; \ | |
293 | \ | |
294 | while( *node ) \ | |
295 | { \ | |
296 | if( m_equals( m_getKey( (*node)->m_value ), key ) ) \ | |
297 | return node; \ | |
298 | node = (Node**)&(*node)->m_nxt; \ | |
299 | } \ | |
300 | \ | |
301 | return 0; \ | |
302 | } \ | |
303 | \ | |
304 | /* returns NULL if not found */ \ | |
305 | /* expressing it in terms of GetNodePtr is 5-8% slower :-( */ \ | |
306 | Node* GetNode( const const_key_type& key ) const \ | |
307 | { \ | |
308 | unsigned long hash = m_hasher( key ); \ | |
309 | Node* node = m_table[hash % m_tableBuckets]; \ | |
310 | \ | |
311 | while( node ) \ | |
312 | { \ | |
313 | if( m_equals( m_getKey( node->m_value ), key ) ) \ | |
314 | return node; \ | |
315 | node = node->m_next(); \ | |
316 | } \ | |
317 | \ | |
318 | return 0; \ | |
319 | } \ | |
320 | \ | |
321 | void ResizeTable( size_t newSize ) \ | |
322 | { \ | |
323 | newSize = GetNextPrime( newSize ); \ | |
324 | Node** srcTable = m_table; \ | |
325 | size_t srcBuckets = m_tableBuckets; \ | |
326 | m_table = (Node**)AllocTable( newSize ); \ | |
327 | m_tableBuckets = newSize; \ | |
328 | \ | |
329 | CopyHashTable( (_wxHashTable_NodeBase**)srcTable, srcBuckets, \ | |
330 | this, (_wxHashTable_NodeBase**)m_table, \ | |
331 | (BucketFromNode)&GetBucketForNode,\ | |
332 | (ProcessNode)&DummyProcessNode ); \ | |
376e1129 | 333 | free(srcTable); \ |
0508ba2a MB |
334 | } \ |
335 | \ | |
336 | /* this must be called _after_ m_table has been cleaned */ \ | |
337 | void HashCopy( const Self& ht ) \ | |
338 | { \ | |
339 | ResizeTable( ht.size() ); \ | |
340 | CopyHashTable( (_wxHashTable_NodeBase**)ht.m_table, ht.m_tableBuckets,\ | |
341 | (_wxHashTableBase2*)this, \ | |
342 | (_wxHashTable_NodeBase**)m_table, \ | |
343 | (BucketFromNode)&GetBucketForNode, \ | |
344 | (ProcessNode)&CopyNode ); \ | |
345 | } \ | |
346 | }; | |
347 | ||
376e1129 VZ |
348 | // defines an STL-like pair class CLASSNAME storing two fields: first of type |
349 | // KEY_T and second of type VALUE_T | |
0508ba2a MB |
350 | #define _WX_DECLARE_PAIR( KEY_T, VALUE_T, CLASSNAME, CLASSEXP ) \ |
351 | CLASSEXP CLASSNAME \ | |
352 | { \ | |
353 | public: \ | |
354 | typedef KEY_T t1; \ | |
355 | typedef VALUE_T t2; \ | |
356 | typedef const KEY_T const_t1; \ | |
357 | typedef const VALUE_T const_t2; \ | |
358 | \ | |
359 | CLASSNAME( const const_t1& f, const const_t2& s ):first(t1(f)),second(t2(s)) {} \ | |
360 | CLASSNAME( const const_t1& f ):first(t1(f)),second(t2()) {} \ | |
361 | \ | |
362 | t1 first; \ | |
363 | t2 second; \ | |
364 | }; | |
365 | ||
376e1129 VZ |
366 | // defines the class CLASSNAME returning the key part (of type KEY_T) from a |
367 | // pair of type PAIR_T | |
0508ba2a MB |
368 | #define _WX_DECLARE_HASH_MAP_KEY_EX( KEY_T, PAIR_T, CLASSNAME, CLASSEXP ) \ |
369 | CLASSEXP CLASSNAME \ | |
370 | { \ | |
95197553 MB |
371 | typedef KEY_T key_type; \ |
372 | typedef PAIR_T pair_type; \ | |
373 | typedef const key_type const_key_type; \ | |
374 | typedef const pair_type const_pair_type; \ | |
375 | typedef const_key_type& const_key_reference; \ | |
376 | typedef const_pair_type& const_pair_reference; \ | |
0508ba2a | 377 | public: \ |
376e1129 | 378 | CLASSNAME() { } \ |
95197553 | 379 | const_key_reference operator()( const_pair_reference pair ) const { return pair.first; }\ |
376e1129 VZ |
380 | \ |
381 | /* the dummy assignment operator is needed to suppress compiler */ \ | |
382 | /* warnings from hash table class' operator=(): gcc complains about */ \ | |
383 | /* "statement with no effect" without it */ \ | |
384 | CLASSNAME& operator=(const CLASSNAME&) { return *this; } \ | |
0508ba2a MB |
385 | }; |
386 | ||
387 | // grow/shrink predicates | |
388 | inline bool never_grow( size_t, size_t ) { return FALSE; } | |
389 | inline bool never_shrink( size_t, size_t ) { return FALSE; } | |
390 | inline bool grow_lf70( size_t buckets, size_t items ) | |
391 | { | |
392 | return float(items)/float(buckets) >= 0.85; | |
393 | } | |
394 | ||
376e1129 VZ |
395 | // ---------------------------------------------------------------------------- |
396 | // hashing and comparison functors | |
397 | // ---------------------------------------------------------------------------- | |
398 | ||
399 | // NB: implementation detail: all of these classes must have dummy assignment | |
400 | // operators to suppress warnings about "statement with no effect" from gcc | |
401 | // in the hash table class assignment operator (where they're assigned) | |
402 | ||
0508ba2a | 403 | // integer types |
ac6e54ee | 404 | class WXDLLEXPORT wxIntegerHash |
0508ba2a MB |
405 | { |
406 | public: | |
376e1129 | 407 | wxIntegerHash() { } |
0508ba2a MB |
408 | unsigned long operator()( long x ) const { return (unsigned long)x; } |
409 | unsigned long operator()( unsigned long x ) const { return x; } | |
410 | unsigned long operator()( int x ) const { return (unsigned long)x; } | |
411 | unsigned long operator()( unsigned int x ) const { return x; } | |
376e1129 VZ |
412 | unsigned long operator()( short x ) const { return (unsigned long)x; } |
413 | unsigned long operator()( unsigned short x ) const { return x; } | |
414 | ||
415 | wxIntegerHash& operator=(const wxIntegerHash&) { return *this; } | |
0508ba2a MB |
416 | }; |
417 | ||
ac6e54ee | 418 | class WXDLLEXPORT wxIntegerEqual |
0508ba2a MB |
419 | { |
420 | public: | |
376e1129 | 421 | wxIntegerEqual() { } |
0508ba2a | 422 | bool operator()( long a, long b ) const { return a == b; } |
376e1129 | 423 | bool operator()( unsigned long a, unsigned long b ) const { return a == b; } |
0508ba2a | 424 | bool operator()( int a, int b ) const { return a == b; } |
376e1129 VZ |
425 | bool operator()( unsigned int a, unsigned int b ) const { return a == b; } |
426 | bool operator()( short a, short b ) const { return a == b; } | |
427 | bool operator()( unsigned short a, unsigned short b ) const { return a == b; } | |
428 | ||
429 | wxIntegerEqual& operator=(const wxIntegerEqual&) { return *this; } | |
0508ba2a MB |
430 | }; |
431 | ||
432 | // pointers | |
ac6e54ee | 433 | class WXDLLEXPORT wxPointerHash |
0508ba2a MB |
434 | { |
435 | public: | |
376e1129 VZ |
436 | wxPointerHash() { } |
437 | ||
438 | // TODO: this might not work well on architectures with 64 bit pointers but | |
439 | // 32 bit longs, we should use % ULONG_MAX there | |
440 | unsigned long operator()( const void* k ) const { return (unsigned long)k; } | |
441 | ||
442 | wxPointerHash& operator=(const wxPointerHash&) { return *this; } | |
0508ba2a MB |
443 | }; |
444 | ||
ac6e54ee | 445 | class WXDLLEXPORT wxPointerEqual |
0508ba2a MB |
446 | { |
447 | public: | |
376e1129 VZ |
448 | wxPointerEqual() { } |
449 | bool operator()( const void* a, const void* b ) const { return a == b; } | |
450 | ||
451 | wxPointerEqual& operator=(const wxPointerEqual&) { return *this; } | |
0508ba2a MB |
452 | }; |
453 | ||
454 | // wxString, char*, wxChar* | |
ac6e54ee | 455 | class WXDLLEXPORT wxStringHash |
0508ba2a MB |
456 | { |
457 | public: | |
376e1129 | 458 | wxStringHash() {} |
0508ba2a MB |
459 | unsigned long operator()( const wxString& x ) const |
460 | { return wxCharStringHash( x.c_str() ); } | |
461 | unsigned long operator()( const wxChar* x ) const | |
462 | { return wxCharStringHash( x ); } | |
463 | static unsigned long wxCharStringHash( const wxChar* ); | |
464 | #if wxUSE_UNICODE | |
465 | unsigned long operator()( const char* x ) const | |
466 | { return charStringHash( x ); } | |
467 | static unsigned long charStringHash( const char* ); | |
376e1129 VZ |
468 | #endif // wxUSE_UNICODE |
469 | ||
470 | wxStringHash& operator=(const wxStringHash&) { return *this; } | |
0508ba2a MB |
471 | }; |
472 | ||
ac6e54ee | 473 | class WXDLLEXPORT wxStringEqual |
0508ba2a MB |
474 | { |
475 | public: | |
376e1129 | 476 | wxStringEqual() {} |
0508ba2a MB |
477 | bool operator()( const wxString& a, const wxString& b ) const |
478 | { return a == b; } | |
479 | bool operator()( const wxChar* a, const wxChar* b ) const | |
480 | { return wxStrcmp( a, b ) == 0; } | |
481 | #if wxUSE_UNICODE | |
482 | bool operator()( const char* a, const char* b ) const | |
483 | { return strcmp( a, b ) == 0; } | |
376e1129 VZ |
484 | #endif // wxUSE_UNICODE |
485 | ||
486 | wxStringEqual& operator=(const wxStringEqual&) { return *this; } | |
0508ba2a MB |
487 | }; |
488 | ||
489 | #define _WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME, CLASSEXP ) \ | |
490 | _WX_DECLARE_PAIR( KEY_T, VALUE_T, CLASSNAME##_wxImplementation_Pair, CLASSEXP ) \ | |
491 | _WX_DECLARE_HASH_MAP_KEY_EX( KEY_T, CLASSNAME##_wxImplementation_Pair, CLASSNAME##_wxImplementation_KeyEx, CLASSEXP ) \ | |
492 | _WX_DECLARE_HASHTABLE( CLASSNAME##_wxImplementation_Pair, KEY_T, HASH_T, CLASSNAME##_wxImplementation_KeyEx, KEY_EQ_T, CLASSNAME##_wxImplementation_HashTable, CLASSEXP, grow_lf70, never_shrink ) \ | |
493 | CLASSEXP CLASSNAME:public CLASSNAME##_wxImplementation_HashTable \ | |
494 | { \ | |
495 | public: \ | |
496 | typedef VALUE_T mapped_type; \ | |
497 | \ | |
498 | CLASSNAME( size_type hint = 100, hasher hf = hasher(), key_equal eq = key_equal() ) \ | |
499 | : CLASSNAME##_wxImplementation_HashTable( hint, hf, eq, CLASSNAME##_wxImplementation_KeyEx() ) {} \ | |
500 | \ | |
501 | mapped_type& operator[]( const const_key_type& key ) \ | |
502 | { \ | |
503 | return GetOrCreateNode( CLASSNAME##_wxImplementation_Pair( key ) )->m_value.second; \ | |
504 | } \ | |
505 | \ | |
506 | const_iterator find( const const_key_type& key ) const \ | |
507 | { \ | |
508 | return const_iterator( GetNode( key ), this ); \ | |
509 | } \ | |
510 | \ | |
511 | iterator find( const const_key_type& key ) \ | |
512 | { \ | |
513 | return iterator( GetNode( key ), this ); \ | |
514 | } \ | |
515 | \ | |
516 | void insert( const value_type& v ) { (*this)[v.first] = v.second; } \ | |
517 | \ | |
518 | size_type erase( const key_type& k ) \ | |
519 | { return CLASSNAME##_wxImplementation_HashTable::erase( k ); } \ | |
520 | void erase( const iterator& it ) { erase( it->first ); } \ | |
521 | void erase( const const_iterator& it ) { erase( it->first ); } \ | |
522 | \ | |
523 | /* count() == 0 | 1 */ \ | |
524 | size_type count( const const_key_type& key ) \ | |
525 | { return GetNode( key ) ? 1 : 0; } \ | |
d86939c4 | 526 | } |
0508ba2a MB |
527 | |
528 | // these macros are to be used in the user code | |
529 | #define WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME) \ | |
530 | _WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME, class ) | |
531 | ||
532 | #define WX_DECLARE_STRING_HASH_MAP( VALUE_T, CLASSNAME ) \ | |
533 | _WX_DECLARE_HASH_MAP( wxString, VALUE_T, wxStringHash, wxStringEqual, \ | |
d86939c4 | 534 | CLASSNAME, class ) |
0508ba2a MB |
535 | |
536 | #define WX_DECLARE_VOIDPTR_HASH_MAP( VALUE_T, CLASSNAME ) \ | |
537 | _WX_DECLARE_HASH_MAP( void*, VALUE_T, wxPointerHash, wxPointerEqual, \ | |
d86939c4 | 538 | CLASSNAME, class ) |
0508ba2a MB |
539 | |
540 | // and these do exactly the same thing but should be used inside the | |
541 | // library | |
542 | #define WX_DECLARE_EXPORTED_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME) \ | |
543 | _WX_DECLARE_HASH_MAP( KEY_T, VALUE_T, HASH_T, KEY_EQ_T, CLASSNAME, class WXDLLEXPORT ) | |
544 | ||
545 | #define WX_DECLARE_EXPORTED_STRING_HASH_MAP( VALUE_T, CLASSNAME ) \ | |
546 | _WX_DECLARE_HASH_MAP( wxString, VALUE_T, wxStringHash, wxStringEqual, \ | |
d86939c4 | 547 | CLASSNAME, class WXDLLEXPORT ) |
0508ba2a MB |
548 | |
549 | #define WX_DECLARE_EXPORTED_VOIDPTR_HASH_MAP( VALUE_T, CLASSNAME ) \ | |
550 | _WX_DECLARE_HASH_MAP( void*, VALUE_T, wxPointerHash, wxPointerEqual, \ | |
d86939c4 | 551 | CLASSNAME, class WXDLLEXPORT ) |
0508ba2a | 552 | |
376e1129 | 553 | #endif // _WX_HASHMAP_H_ |
0508ba2a | 554 |