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