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