include/wx/hashmap.h

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