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