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