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