include/wx/hash.h

   1 /////////////////////////////////////////////////////////////////////////////
   2 // Name:        wx/hash.h
   3 // Purpose:     wxHashTable class
   4 // Author:      Julian Smart
   5 // Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
   6 // Created:     01/02/97
   7 // RCS-ID:      $Id$
   8 // Copyright:   (c)
   9 // Licence:     wxWindows licence
  10 /////////////////////////////////////////////////////////////////////////////
  11
  12 #ifndef _WX_HASH_H__
  13 #define _WX_HASH_H__
  14
  15 #if defined(__GNUG__) && !defined(__APPLE__)
  16 #pragma interface "hash.h"
  17 #endif
  18
  19 #include "wx/defs.h"
  20
  21 #if !wxUSE_STL
  22     #include "wx/list.h"
  23 #endif
  24 #if WXWIN_COMPATIBILITY_2_4
  25     #include "wx/dynarray.h"
  26 #endif
  27
  28 class WXDLLIMPEXP_BASE wxObject;
  29
  30 // the default size of the hash
  31 #define wxHASH_SIZE_DEFAULT     (1000)
  32
  33 /*
  34  * A hash table is an array of user-definable size with lists
  35  * of data items hanging off the array positions.  Usually there'll
  36  * be a hit, so no search is required; otherwise we'll have to run down
  37  * the list to find the desired item.
  38 */
  39
  40 // ----------------------------------------------------------------------------
  41 // this is the base class for object hashes: hash tables which contain
  42 // pointers to objects
  43 // ----------------------------------------------------------------------------
  44
  45 #if !wxUSE_STL
  46
  47 class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject
  48 {
  49 public:
  50     wxHashTableBase();
  51
  52     void Create(wxKeyType keyType = wxKEY_INTEGER,
  53                 size_t size = wxHASH_SIZE_DEFAULT);
  54     void Destroy();
  55
  56     size_t GetSize() const { return m_hashSize; }
  57     size_t GetCount() const { return m_count; }
  58
  59     void DeleteContents(bool flag);
  60
  61 protected:
  62     // find the node for (key, value)
  63     wxNodeBase *GetNode(long key, long value) const;
  64
  65     // the array of lists in which we store the values for given key hash
  66     wxListBase **m_hashTable;
  67
  68     // the size of m_lists array
  69     size_t m_hashSize;
  70
  71     // the type of indexing we use
  72     wxKeyType m_keyType;
  73
  74     // the total number of elements in the hash
  75     size_t m_count;
  76
  77     // should we delete our data?
  78     bool m_deleteContents;
  79
  80 private:
  81     // no copy ctor/assignment operator (yet)
  82     DECLARE_NO_COPY_CLASS(wxHashTableBase)
  83 };
  84
  85 #else
  86
  87 #include "wx/hashmap.h"
  88
  89 #if !defined(wxENUM_KEY_TYPE_DEFINED)
  90 #define wxENUM_KEY_TYPE_DEFINED
  91
  92 enum wxKeyType
  93 {
  94     wxKEY_NONE,
  95     wxKEY_INTEGER,
  96     wxKEY_STRING
  97 };
  98
  99 #endif
 100
 101 union wxHashKeyValue
 102 {
 103     long integer;
 104     wxChar *string;
 105 };
 106
 107 struct WXDLLIMPEXP_BASE wxHashTableHash
 108 {
 109     wxHashTableHash() { }
 110     wxHashTableHash( wxKeyType keyType ) : m_keyType( keyType ) { }
 111
 112     wxKeyType m_keyType;
 113
 114     unsigned long operator ()( const wxHashKeyValue& k ) const
 115     {
 116         if( m_keyType == wxKEY_STRING )
 117             return wxStringHash::wxCharStringHash( k.string );
 118         else
 119             return (unsigned long)k.integer;
 120     }
 121 };
 122
 123 struct WXDLLIMPEXP_BASE wxHashTableEqual
 124 {
 125     wxHashTableEqual() { }
 126     wxHashTableEqual( wxKeyType keyType ) : m_keyType( keyType ) { }
 127
 128     wxKeyType m_keyType;
 129
 130     bool operator ()( const wxHashKeyValue& k1, const wxHashKeyValue& k2 ) const
 131     {
 132         if( m_keyType == wxKEY_STRING )
 133             return wxStrcmp( k1.string, k2.string ) == 0;
 134         else
 135             return k1.integer == k2.integer;
 136     }
 137 };
 138
 139 WX_DECLARE_EXPORTED_HASH_MAP( wxHashKeyValue,
 140                               void*,
 141                               wxHashTableHash,
 142                               wxHashTableEqual,
 143                               wxHashTableBaseBase );
 144
 145 class WXDLLIMPEXP_BASE wxHashTableBase
 146 {
 147 public:
 148     wxHashTableBase( wxKeyType keyType = wxKEY_INTEGER,
 149                      size_t size = wxHASH_SIZE_DEFAULT )
 150         : m_map( size, wxHashTableHash( keyType ),
 151                  wxHashTableEqual( keyType ) ),
 152           m_keyType( keyType ) { }
 153
 154     ~wxHashTableBase() { Clear(); }
 155
 156     size_t GetCount() const { return m_map.size(); }
 157
 158     void Clear()
 159     {
 160         if( m_keyType == wxKEY_STRING )
 161         {
 162             for( wxHashTableBaseBase::iterator it = m_map.begin(),
 163                                                en = m_map.end();
 164                  it != en; )
 165             {
 166                 wxChar* tmp = it->first.string;
 167                 ++it;
 168                 delete[] tmp; // used in operator++
 169             }
 170         }
 171         m_map.clear();
 172     }
 173 protected:
 174     void DoPut( long key, void* data )
 175     {
 176         wxASSERT( m_keyType == wxKEY_INTEGER );
 177
 178         wxHashKeyValue k; k.integer = key;
 179         m_map[k] = data;
 180     }
 181
 182     void DoPut( const wxChar* key, void* data )
 183     {
 184         wxASSERT( m_keyType == wxKEY_STRING );
 185
 186         wxHashKeyValue k;
 187         k.string = (wxChar*)key;
 188         wxHashTableBaseBase::iterator it = m_map.find(k);
 189
 190         if( it == m_map.end() )
 191         {
 192             k.string = new wxChar[wxStrlen(key) + 1];
 193             wxStrcpy(k.string, key);
 194             m_map[k] = data;
 195         }
 196         else
 197             it->second = data;
 198     }
 199
 200     void* DoGet( long key ) const
 201     {
 202         wxASSERT( m_keyType == wxKEY_INTEGER );
 203
 204         wxHashKeyValue k; k.integer = key;
 205         wxHashTableBaseBase::const_iterator it = m_map.find( k );
 206
 207         return it != m_map.end() ? it->second : NULL;
 208     }
 209
 210     void* DoGet( const wxChar* key ) const
 211     {
 212         wxASSERT( m_keyType == wxKEY_STRING );
 213
 214         wxHashKeyValue k; k.string = (wxChar*)key;
 215         wxHashTableBaseBase::const_iterator it = m_map.find( k );
 216
 217         return it != m_map.end() ? it->second : NULL;
 218     }
 219
 220     void* DoDelete( long key )
 221     {
 222         wxASSERT( m_keyType == wxKEY_INTEGER );
 223
 224         wxHashKeyValue k; k.integer = key;
 225         wxHashTableBaseBase::iterator it = m_map.find( k );
 226
 227         if( it != m_map.end() )
 228         {
 229             void* data = it->second;
 230
 231             m_map.erase( it );
 232             return data;
 233         }
 234
 235         return NULL;
 236     }
 237
 238     void* DoDelete( const wxChar* key )
 239     {
 240         wxASSERT( m_keyType == wxKEY_STRING );
 241
 242         wxHashKeyValue k; k.string = (wxChar*)key;
 243         wxHashTableBaseBase::iterator it = m_map.find( k );
 244
 245         if( it != m_map.end() )
 246         {
 247             void* data = it->second;
 248             wxChar* k = it->first.string;
 249
 250             m_map.erase( it );
 251             delete[] k;
 252             return data;
 253         }
 254
 255         return NULL;
 256     }
 257
 258     wxHashTableBaseBase m_map;
 259     wxKeyType m_keyType;
 260 };
 261
 262 #endif // !wxUSE_STL
 263
 264 #if !wxUSE_STL
 265
 266 #if WXWIN_COMPATIBILITY_2_4
 267
 268 // ----------------------------------------------------------------------------
 269 // a hash table which stores longs
 270 // ----------------------------------------------------------------------------
 271
 272 class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject
 273 {
 274 public:
 275     wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
 276         { Init(size); }
 277     virtual ~wxHashTableLong();
 278
 279     void Create(size_t size = wxHASH_SIZE_DEFAULT);
 280     void Destroy();
 281
 282     size_t GetSize() const { return m_hashSize; }
 283     size_t GetCount() const { return m_count; }
 284
 285     void Put(long key, long value);
 286     long Get(long key) const;
 287     long Delete(long key);
 288
 289 protected:
 290     void Init(size_t size);
 291
 292 private:
 293     wxArrayLong **m_values,
 294                 **m_keys;
 295
 296     // the size of array above
 297     size_t m_hashSize;
 298
 299     // the total number of elements in the hash
 300     size_t m_count;
 301
 302     // not implemented yet
 303     DECLARE_NO_COPY_CLASS(wxHashTableLong)
 304 };
 305
 306 // ----------------------------------------------------------------------------
 307 // wxStringHashTable: a hash table which indexes strings with longs
 308 // ----------------------------------------------------------------------------
 309
 310 class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject
 311 {
 312 public:
 313     wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
 314     virtual ~wxStringHashTable();
 315
 316     // add a string associated with this key to the table
 317     void Put(long key, const wxString& value);
 318
 319     // get the string from the key: if not found, an empty string is returned
 320     // and the wasFound is set to FALSE if not NULL
 321     wxString Get(long key, bool *wasFound = NULL) const;
 322
 323     // remove the item, returning TRUE if the item was found and deleted
 324     bool Delete(long key) const;
 325
 326     // clean up
 327     void Destroy();
 328
 329 private:
 330     wxArrayLong **m_keys;
 331     wxArrayString **m_values;
 332
 333     // the size of array above
 334     size_t m_hashSize;
 335
 336     DECLARE_NO_COPY_CLASS(wxStringHashTable)
 337 };
 338
 339 #endif // WXWIN_COMPATIBILITY_2_4
 340
 341 #endif  // !wxUSE_STL
 342
 343 // ----------------------------------------------------------------------------
 344 // for compatibility only
 345 // ----------------------------------------------------------------------------
 346
 347 #if wxUSE_STL
 348
 349 class WXDLLIMPEXP_BASE wxHashTable : protected wxHashTableBase
 350 {
 351     typedef wxHashTableBaseBase hash;
 352 public:
 353     class dummy;
 354
 355     struct compatibility_iterator
 356     {
 357         hash::iterator m_iter;
 358         hash* m_hash;
 359
 360         operator bool() const { return m_iter != m_hash->end(); }
 361         bool operator !() const { return m_iter == m_hash->end(); }
 362         compatibility_iterator( hash* li, hash::iterator it )
 363             : m_iter( it ), m_hash( li ) {}
 364         compatibility_iterator() { }
 365
 366         dummy* operator->() { return (dummy*)this; }
 367     };
 368     typedef compatibility_iterator citer;
 369
 370     class dummy
 371     {
 372         typedef hash::iterator it;
 373         typedef compatibility_iterator citer;
 374     public:
 375         wxObject* GetData() const
 376         {
 377             citer* i = (citer*)this;
 378             return (wxObject*)i->m_iter->second;
 379         }
 380         citer GetNext() const
 381         {
 382             citer* i = (citer*)this;
 383             it lit = i->m_iter;
 384             return citer( i->m_hash, ++lit );
 385         }
 386         citer GetPrevious() const
 387         {
 388             citer* i = (citer*)this;
 389             it lit = i->m_iter;
 390             return citer( i->m_hash, ++lit );
 391         }
 392         void SetData( wxObject* e )
 393         {
 394             citer* i = (citer*)this;
 395             i->m_iter->second = e;
 396         }
 397     private:
 398         dummy();
 399     };
 400 public:
 401     wxHashTable( wxKeyType keyType = wxKEY_INTEGER,
 402                  size_t size = wxHASH_SIZE_DEFAULT )
 403         : wxHashTableBase( keyType, size ) { }
 404
 405     void Destroy() { Clear(); }
 406
 407     // key and value are the same
 408     void Put(long value, wxObject *object) { DoPut( value, object ); }
 409     void Put(const wxChar *value, wxObject *object) { DoPut( value, object ); }
 410
 411     // key and value are the same
 412     wxObject *Get(long value) const { return (wxObject*)DoGet( value ); }
 413     wxObject *Get(const wxChar *value) const { return (wxObject*)DoGet( value ); }
 414
 415     // Deletes entry and returns data if found
 416     wxObject *Delete(long key) { return (wxObject*)DoGet( key ); }
 417     wxObject *Delete(const wxChar *key) { return (wxObject*)DoGet( key ); }
 418
 419 #if 0
 420     // Construct your own integer key from a string, e.g. in case
 421     // you need to combine it with something
 422     long MakeKey(const wxChar *string) const;
 423 #endif
 424     // Way of iterating through whole hash table (e.g. to delete everything)
 425     // Not necessary, of course, if you're only storing pointers to
 426     // objects maintained separately
 427     void BeginFind() { m_iter = citer( &this->m_map, this->m_map.begin() ); }
 428     compatibility_iterator Next()
 429     {
 430         compatibility_iterator it = m_iter;
 431         if( m_iter )
 432             m_iter = m_iter->GetNext();
 433         return it;
 434     }
 435
 436     void Clear() { wxHashTableBase::Clear(); }
 437 private:
 438     compatibility_iterator m_iter;
 439 };
 440
 441 #else // if !wxUSE_STL
 442
 443 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
 444 {
 445 public:
 446     int n;
 447     int current_position;
 448     wxNode *current_node;
 449
 450     unsigned int key_type;
 451     wxList **hash_table;
 452
 453     wxHashTable(int the_key_type = wxKEY_INTEGER,
 454                 int size = wxHASH_SIZE_DEFAULT);
 455     ~wxHashTable();
 456
 457     // copy ctor and assignment operator
 458     wxHashTable(const wxHashTable& table) : wxObject()
 459         { DoCopy(table); }
 460     wxHashTable& operator=(const wxHashTable& table)
 461         { Clear(); DoCopy(table); return *this; }
 462
 463     void DoCopy(const wxHashTable& table);
 464
 465     void Destroy();
 466
 467     bool Create(int the_key_type = wxKEY_INTEGER,
 468                 int size = wxHASH_SIZE_DEFAULT);
 469
 470     // Note that there are 2 forms of Put, Get.
 471     // With a key and a value, the *value* will be checked
 472     // when a collision is detected. Otherwise, if there are
 473     // 2 items with a different value but the same key,
 474     // we'll retrieve the WRONG ONE. So where possible,
 475     // supply the required value along with the key.
 476     // In fact, the value-only versions make a key, and still store
 477     // the value. The use of an explicit key might be required
 478     // e.g. when combining several values into one key.
 479     // When doing that, it's highly likely we'll get a collision,
 480     // e.g. 1 + 2 = 3, 2 + 1 = 3.
 481
 482     // key and value are NOT necessarily the same
 483     void Put(long key, long value, wxObject *object);
 484     void Put(long key, const wxChar *value, wxObject *object);
 485
 486     // key and value are the same
 487     void Put(long value, wxObject *object);
 488     void Put(const wxChar *value, wxObject *object);
 489
 490     // key and value not the same
 491     wxObject *Get(long key, long value) const;
 492     wxObject *Get(long key, const wxChar *value) const;
 493
 494     // key and value are the same
 495     wxObject *Get(long value) const;
 496     wxObject *Get(const wxChar *value) const;
 497
 498     // Deletes entry and returns data if found
 499     wxObject *Delete(long key);
 500     wxObject *Delete(const wxChar *key);
 501
 502     wxObject *Delete(long key, int value);
 503     wxObject *Delete(long key, const wxChar *value);
 504
 505     // Construct your own integer key from a string, e.g. in case
 506     // you need to combine it with something
 507     long MakeKey(const wxChar *string) const;
 508
 509     // Way of iterating through whole hash table (e.g. to delete everything)
 510     // Not necessary, of course, if you're only storing pointers to
 511     // objects maintained separately
 512
 513     void BeginFind();
 514     wxNode *Next();
 515
 516     void DeleteContents(bool flag);
 517     void Clear();
 518
 519     // Returns number of nodes
 520     size_t GetCount() const { return m_count; }
 521
 522     typedef wxNode* compatibility_iterator;
 523 private:
 524     size_t m_count;             // number of elements in the hashtable
 525     bool m_deleteContents;
 526
 527     DECLARE_DYNAMIC_CLASS(wxHashTable)
 528 };
 529
 530 #endif
 531
 532 #if wxUSE_STL
 533
 534 // defines a new type safe hash table which stores the elements of type eltype
 535 // in lists of class listclass
 536 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp)                  \
 537     classexp hashclass : public wxHashTableBase                               \
 538     {                                                                         \
 539     public:                                                                   \
 540         hashclass(wxKeyType keyType = wxKEY_INTEGER,                          \
 541                   size_t size = wxHASH_SIZE_DEFAULT)                          \
 542             : wxHashTableBase(keyType, size) { }                              \
 543                                                                               \
 544         ~hashclass() { Destroy(); }                                           \
 545                                                                               \
 546         void Destroy() { m_map.clear(); }                                     \
 547         void Put(long key, eltype *data) { DoPut(key, (void*)data); }         \
 548         eltype *Get(long key) const { return (eltype*)DoGet(key); }           \
 549         eltype *Delete(long key) { return (eltype*)DoDelete(key); }           \
 550     }
 551
 552 #else // if !wxUSE_STL
 553
 554 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp)               \
 555     classexp hashclass : public wxHashTableBase                                \
 556     {                                                                          \
 557     public:                                                                    \
 558         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
 559                   size_t size = wxHASH_SIZE_DEFAULT)                           \
 560             { Create(keyType, size); }                                         \
 561                                                                                \
 562         ~hashclass() { Destroy(); }                                            \
 563                                                                                \
 564         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
 565         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
 566                                                                                \
 567         eltype *Get(long key, long value) const                                \
 568         {                                                                      \
 569             wxNodeBase *node = GetNode(key, value);                            \
 570             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
 571         }                                                                      \
 572         eltype *Get(long key) const { return Get(key, key); }                  \
 573                                                                                \
 574         eltype *Delete(long key, long value)                                   \
 575         {                                                                      \
 576             eltype *data;                                                      \
 577                                                                                \
 578             wxNodeBase *node = GetNode(key, value);                            \
 579             if ( node )                                                        \
 580             {                                                                  \
 581                 data = ((listclass::Node *)node)->GetData();                   \
 582                                                                                \
 583                 delete node;                                                   \
 584                 m_count--;                                                     \
 585             }                                                                  \
 586             else                                                               \
 587             {                                                                  \
 588                 data = (eltype *)0;                                            \
 589             }                                                                  \
 590                                                                                \
 591             return data;                                                       \
 592         }                                                                      \
 593         eltype *Delete(long key) { return Delete(key, key); }                  \
 594                                                                                \
 595     protected:                                                                 \
 596         void DoPut(long key, long value, eltype *data)                         \
 597         {                                                                      \
 598             size_t slot = (size_t)abs((int)(key % (long)m_hashSize));          \
 599                                                                                \
 600             if ( !m_hashTable[slot] )                                          \
 601             {                                                                  \
 602                 m_hashTable[slot] = new listclass(m_keyType);                  \
 603                 if ( m_deleteContents )                                        \
 604                     m_hashTable[slot]->DeleteContents(TRUE);                   \
 605             }                                                                  \
 606                                                                                \
 607             ((listclass *)m_hashTable[slot])->Append(value, data);             \
 608             m_count++;                                                         \
 609         }                                                                      \
 610                                                                                \
 611         DECLARE_NO_COPY_CLASS(hashclass)                                       \
 612     }
 613
 614 #endif
 615
 616 // this macro is to be used in the user code
 617 #define WX_DECLARE_HASH(el, list, hash) \
 618     _WX_DECLARE_HASH(el, list, hash, class)
 619
 620 // and this one does exactly the same thing but should be used inside the
 621 // library
 622 #define WX_DECLARE_EXPORTED_HASH(el, list, hash)  \
 623     _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
 624
 625 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo)  \
 626     _WX_DECLARE_HASH(el, list, hash, class usergoo)
 627
 628 // delete all hash elements
 629 //
 630 // NB: the class declaration of the hash elements must be visible from the
 631 //     place where you use this macro, otherwise the proper destructor may not
 632 //     be called (a decent compiler should give a warning about it, but don't
 633 //     count on it)!
 634 #define WX_CLEAR_HASH_TABLE(hash)                                            \
 635     {                                                                        \
 636         (hash).BeginFind();                                                  \
 637         wxHashTable::compatibility_iterator it = (hash).Next();              \
 638         while( it )                                                          \
 639         {                                                                    \
 640             delete it->GetData();                                            \
 641             it = (hash).Next();                                              \
 642         }                                                                    \
 643         (hash).Clear();                                                      \
 644     }
 645
 646 #endif
 647     // _WX_HASH_H__