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(NO_GCC_PRAGMA)
  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                               wxHashTableBaseBaseBase );
 144
 145 // hack: we should really have HASH_MULTI(MAP|SET), but this requires
 146 // less work
 147
 148 class WXDLLIMPEXP_BASE wxHashTableBaseBase : public wxHashTableBaseBaseBase
 149 {
 150 public:
 151     wxHashTableBaseBase(size_t size, const wxHashTableHash& hash,
 152                         const wxHashTableEqual& equal)
 153         : wxHashTableBaseBaseBase(size, hash, equal)
 154     { }
 155
 156     void multi_insert(const wxHashKeyValue& key, void* value)
 157     {
 158         CreateNodeLast(value_type(key, value));
 159     }
 160 };
 161
 162 class WXDLLIMPEXP_BASE wxHashTableBase
 163 {
 164 public:
 165     wxHashTableBase( wxKeyType keyType = wxKEY_INTEGER,
 166                      size_t size = wxHASH_SIZE_DEFAULT )
 167         : m_map( size, wxHashTableHash( keyType ),
 168                  wxHashTableEqual( keyType ) ),
 169           m_keyType( keyType ) { }
 170
 171     ~wxHashTableBase() { Clear(); }
 172
 173     size_t GetCount() const { return m_map.size(); }
 174
 175     void Clear()
 176     {
 177         if( m_keyType == wxKEY_STRING )
 178         {
 179             for( wxHashTableBaseBase::iterator it = m_map.begin(),
 180                                                en = m_map.end();
 181                  it != en; )
 182             {
 183                 wxChar* tmp = it->first.string;
 184                 ++it;
 185                 delete[] tmp; // used in operator++
 186             }
 187         }
 188         m_map.clear();
 189     }
 190 protected:
 191     void DoPut( long key, void* data )
 192     {
 193         wxASSERT( m_keyType == wxKEY_INTEGER );
 194
 195         wxHashKeyValue k; k.integer = key;
 196         m_map.multi_insert(k, data);
 197     }
 198
 199     void DoPut( const wxChar* key, void* data )
 200     {
 201         wxASSERT( m_keyType == wxKEY_STRING );
 202
 203         wxHashKeyValue k;
 204         k.string = wxStrcpy(new wxChar[wxStrlen(key) + 1], key);
 205         m_map.multi_insert(k, data);
 206     }
 207
 208     void* DoGet( long key ) const
 209     {
 210         wxASSERT( m_keyType == wxKEY_INTEGER );
 211
 212         wxHashKeyValue k; k.integer = key;
 213         wxHashTableBaseBase::const_iterator it = m_map.find( k );
 214
 215         return it != m_map.end() ? it->second : NULL;
 216     }
 217
 218     void* DoGet( const wxChar* key ) const
 219     {
 220         wxASSERT( m_keyType == wxKEY_STRING );
 221
 222         wxHashKeyValue k; k.string = (wxChar*)key;
 223         wxHashTableBaseBase::const_iterator it = m_map.find( k );
 224
 225         return it != m_map.end() ? it->second : NULL;
 226     }
 227
 228     void* DoDelete( long key )
 229     {
 230         wxASSERT( m_keyType == wxKEY_INTEGER );
 231
 232         wxHashKeyValue k; k.integer = key;
 233         wxHashTableBaseBase::iterator it = m_map.find( k );
 234
 235         if( it != m_map.end() )
 236         {
 237             void* data = it->second;
 238
 239             m_map.erase( it );
 240             return data;
 241         }
 242
 243         return NULL;
 244     }
 245
 246     void* DoDelete( const wxChar* key )
 247     {
 248         wxASSERT( m_keyType == wxKEY_STRING );
 249
 250         wxHashKeyValue k; k.string = (wxChar*)key;
 251         wxHashTableBaseBase::iterator it = m_map.find( k );
 252
 253         if( it != m_map.end() )
 254         {
 255             void* data = it->second;
 256             wxChar* k = it->first.string;
 257
 258             m_map.erase( it );
 259             delete[] k;
 260             return data;
 261         }
 262
 263         return NULL;
 264     }
 265
 266     wxHashTableBaseBase m_map;
 267     wxKeyType m_keyType;
 268 };
 269
 270 #endif // !wxUSE_STL
 271
 272 #if !wxUSE_STL
 273
 274 #if WXWIN_COMPATIBILITY_2_4
 275
 276 // ----------------------------------------------------------------------------
 277 // a hash table which stores longs
 278 // ----------------------------------------------------------------------------
 279
 280 class WXDLLIMPEXP_BASE wxHashTableLong : public wxObject
 281 {
 282 public:
 283     wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
 284         { Init(size); }
 285     virtual ~wxHashTableLong();
 286
 287     void Create(size_t size = wxHASH_SIZE_DEFAULT);
 288     void Destroy();
 289
 290     size_t GetSize() const { return m_hashSize; }
 291     size_t GetCount() const { return m_count; }
 292
 293     void Put(long key, long value);
 294     long Get(long key) const;
 295     long Delete(long key);
 296
 297 protected:
 298     void Init(size_t size);
 299
 300 private:
 301     wxArrayLong **m_values,
 302                 **m_keys;
 303
 304     // the size of array above
 305     size_t m_hashSize;
 306
 307     // the total number of elements in the hash
 308     size_t m_count;
 309
 310     // not implemented yet
 311     DECLARE_NO_COPY_CLASS(wxHashTableLong)
 312 };
 313
 314 // ----------------------------------------------------------------------------
 315 // wxStringHashTable: a hash table which indexes strings with longs
 316 // ----------------------------------------------------------------------------
 317
 318 class WXDLLIMPEXP_BASE wxStringHashTable : public wxObject
 319 {
 320 public:
 321     wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
 322     virtual ~wxStringHashTable();
 323
 324     // add a string associated with this key to the table
 325     void Put(long key, const wxString& value);
 326
 327     // get the string from the key: if not found, an empty string is returned
 328     // and the wasFound is set to FALSE if not NULL
 329     wxString Get(long key, bool *wasFound = NULL) const;
 330
 331     // remove the item, returning TRUE if the item was found and deleted
 332     bool Delete(long key) const;
 333
 334     // clean up
 335     void Destroy();
 336
 337 private:
 338     wxArrayLong **m_keys;
 339     wxArrayString **m_values;
 340
 341     // the size of array above
 342     size_t m_hashSize;
 343
 344     DECLARE_NO_COPY_CLASS(wxStringHashTable)
 345 };
 346
 347 #endif // WXWIN_COMPATIBILITY_2_4
 348
 349 #endif  // !wxUSE_STL
 350
 351 // ----------------------------------------------------------------------------
 352 // for compatibility only
 353 // ----------------------------------------------------------------------------
 354
 355 #if wxUSE_STL
 356
 357 class WXDLLIMPEXP_BASE wxHashTable : protected wxHashTableBase
 358 {
 359     typedef wxHashTableBaseBase hash;
 360 public:
 361     class dummy;
 362
 363     struct compatibility_iterator
 364     {
 365         hash::iterator m_iter;
 366         hash* m_hash;
 367
 368         operator bool() const { return m_iter != m_hash->end(); }
 369         bool operator !() const { return m_iter == m_hash->end(); }
 370         compatibility_iterator( hash* li, hash::iterator it )
 371             : m_iter( it ), m_hash( li ) {}
 372         compatibility_iterator() { }
 373
 374         dummy* operator->() { return (dummy*)this; }
 375     };
 376     typedef compatibility_iterator citer;
 377
 378     class dummy
 379     {
 380         typedef hash::iterator it;
 381         typedef compatibility_iterator citer;
 382     public:
 383         wxObject* GetData() const
 384         {
 385             citer* i = (citer*)this;
 386             return (wxObject*)i->m_iter->second;
 387         }
 388         citer GetNext() const
 389         {
 390             citer* i = (citer*)this;
 391             it lit = i->m_iter;
 392             return citer( i->m_hash, ++lit );
 393         }
 394         void SetData( wxObject* e )
 395         {
 396             citer* i = (citer*)this;
 397             i->m_iter->second = e;
 398         }
 399     private:
 400         dummy();
 401     };
 402 public:
 403     wxHashTable( wxKeyType keyType = wxKEY_INTEGER,
 404                  size_t size = wxHASH_SIZE_DEFAULT )
 405         : wxHashTableBase( keyType, size ) { }
 406
 407     void Destroy() { Clear(); }
 408
 409     // key and value are the same
 410     void Put(long value, wxObject *object) { DoPut( value, object ); }
 411     void Put(const wxChar *value, wxObject *object) { DoPut( value, object ); }
 412
 413     // key and value are the same
 414     wxObject *Get(long value) const { return (wxObject*)DoGet( value ); }
 415     wxObject *Get(const wxChar *value) const { return (wxObject*)DoGet( value ); }
 416
 417     // Deletes entry and returns data if found
 418     wxObject *Delete(long key) { return (wxObject*)DoDelete( key ); }
 419     wxObject *Delete(const wxChar *key) { return (wxObject*)DoDelete( key ); }
 420
 421 #if 0
 422     // Construct your own integer key from a string, e.g. in case
 423     // you need to combine it with something
 424     long MakeKey(const wxChar *string) const;
 425 #endif
 426     // Way of iterating through whole hash table (e.g. to delete everything)
 427     // Not necessary, of course, if you're only storing pointers to
 428     // objects maintained separately
 429     void BeginFind() { m_iter = citer( &this->m_map, this->m_map.begin() ); }
 430     compatibility_iterator Next()
 431     {
 432         compatibility_iterator it = m_iter;
 433         if( m_iter )
 434             m_iter = m_iter->GetNext();
 435         return it;
 436     }
 437
 438     void Clear() { wxHashTableBase::Clear(); }
 439
 440     size_t GetCount() const { return wxHashTableBase::GetCount(); }
 441 private:
 442     compatibility_iterator m_iter;
 443 };
 444
 445 #else // if !wxUSE_STL
 446
 447 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
 448 {
 449 public:
 450     int n;
 451     int current_position;
 452     wxNode *current_node;
 453
 454     unsigned int key_type;
 455     wxList **hash_table;
 456
 457     wxHashTable(int the_key_type = wxKEY_INTEGER,
 458                 int size = wxHASH_SIZE_DEFAULT);
 459     ~wxHashTable();
 460
 461     // copy ctor and assignment operator
 462     wxHashTable(const wxHashTable& table) : wxObject()
 463         { DoCopy(table); }
 464     wxHashTable& operator=(const wxHashTable& table)
 465         { Clear(); DoCopy(table); return *this; }
 466
 467     void DoCopy(const wxHashTable& table);
 468
 469     void Destroy();
 470
 471     bool Create(int the_key_type = wxKEY_INTEGER,
 472                 int size = wxHASH_SIZE_DEFAULT);
 473
 474     // Note that there are 2 forms of Put, Get.
 475     // With a key and a value, the *value* will be checked
 476     // when a collision is detected. Otherwise, if there are
 477     // 2 items with a different value but the same key,
 478     // we'll retrieve the WRONG ONE. So where possible,
 479     // supply the required value along with the key.
 480     // In fact, the value-only versions make a key, and still store
 481     // the value. The use of an explicit key might be required
 482     // e.g. when combining several values into one key.
 483     // When doing that, it's highly likely we'll get a collision,
 484     // e.g. 1 + 2 = 3, 2 + 1 = 3.
 485
 486     // key and value are NOT necessarily the same
 487     void Put(long key, long value, wxObject *object);
 488     void Put(long key, const wxChar *value, wxObject *object);
 489
 490     // key and value are the same
 491     void Put(long value, wxObject *object);
 492     void Put(const wxChar *value, wxObject *object);
 493
 494     // key and value not the same
 495     wxObject *Get(long key, long value) const;
 496     wxObject *Get(long key, const wxChar *value) const;
 497
 498     // key and value are the same
 499     wxObject *Get(long value) const;
 500     wxObject *Get(const wxChar *value) const;
 501
 502     // Deletes entry and returns data if found
 503     wxObject *Delete(long key);
 504     wxObject *Delete(const wxChar *key);
 505
 506     wxObject *Delete(long key, int value);
 507     wxObject *Delete(long key, const wxChar *value);
 508
 509     // Construct your own integer key from a string, e.g. in case
 510     // you need to combine it with something
 511     long MakeKey(const wxChar *string) const;
 512
 513     // Way of iterating through whole hash table (e.g. to delete everything)
 514     // Not necessary, of course, if you're only storing pointers to
 515     // objects maintained separately
 516
 517     void BeginFind();
 518     wxNode *Next();
 519
 520     void DeleteContents(bool flag);
 521     void Clear();
 522
 523     // Returns number of nodes
 524     size_t GetCount() const { return m_count; }
 525
 526     typedef wxNode* compatibility_iterator;
 527 private:
 528     size_t m_count;             // number of elements in the hashtable
 529     bool m_deleteContents;
 530
 531     DECLARE_DYNAMIC_CLASS(wxHashTable)
 532 };
 533
 534 #endif
 535
 536 #if wxUSE_STL
 537
 538 // defines a new type safe hash table which stores the elements of type eltype
 539 // in lists of class listclass
 540 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp)                  \
 541     classexp hashclass : public wxHashTableBase                               \
 542     {                                                                         \
 543     public:                                                                   \
 544         hashclass(wxKeyType keyType = wxKEY_INTEGER,                          \
 545                   size_t size = wxHASH_SIZE_DEFAULT)                          \
 546             : wxHashTableBase(keyType, size) { }                              \
 547                                                                               \
 548         ~hashclass() { Destroy(); }                                           \
 549                                                                               \
 550         void Destroy() { m_map.clear(); }                                     \
 551         void Put(long key, eltype *data) { DoPut(key, (void*)data); }         \
 552         eltype *Get(long key) const { return (eltype*)DoGet(key); }           \
 553         eltype *Delete(long key) { return (eltype*)DoDelete(key); }           \
 554     }
 555
 556 #else // if !wxUSE_STL
 557
 558 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp)               \
 559     classexp hashclass : public wxHashTableBase                                \
 560     {                                                                          \
 561     public:                                                                    \
 562         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
 563                   size_t size = wxHASH_SIZE_DEFAULT)                           \
 564             { Create(keyType, size); }                                         \
 565                                                                                \
 566         ~hashclass() { Destroy(); }                                            \
 567                                                                                \
 568         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
 569         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
 570                                                                                \
 571         eltype *Get(long key, long value) const                                \
 572         {                                                                      \
 573             wxNodeBase *node = GetNode(key, value);                            \
 574             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
 575         }                                                                      \
 576         eltype *Get(long key) const { return Get(key, key); }                  \
 577                                                                                \
 578         eltype *Delete(long key, long value)                                   \
 579         {                                                                      \
 580             eltype *data;                                                      \
 581                                                                                \
 582             wxNodeBase *node = GetNode(key, value);                            \
 583             if ( node )                                                        \
 584             {                                                                  \
 585                 data = ((listclass::Node *)node)->GetData();                   \
 586                                                                                \
 587                 delete node;                                                   \
 588                 m_count--;                                                     \
 589             }                                                                  \
 590             else                                                               \
 591             {                                                                  \
 592                 data = (eltype *)0;                                            \
 593             }                                                                  \
 594                                                                                \
 595             return data;                                                       \
 596         }                                                                      \
 597         eltype *Delete(long key) { return Delete(key, key); }                  \
 598                                                                                \
 599     protected:                                                                 \
 600         void DoPut(long key, long value, eltype *data)                         \
 601         {                                                                      \
 602             size_t slot = (size_t)abs((int)(key % (long)m_hashSize));          \
 603                                                                                \
 604             if ( !m_hashTable[slot] )                                          \
 605             {                                                                  \
 606                 m_hashTable[slot] = new listclass(m_keyType);                  \
 607                 if ( m_deleteContents )                                        \
 608                     m_hashTable[slot]->DeleteContents(TRUE);                   \
 609             }                                                                  \
 610                                                                                \
 611             ((listclass *)m_hashTable[slot])->Append(value, data);             \
 612             m_count++;                                                         \
 613         }                                                                      \
 614                                                                                \
 615         DECLARE_NO_COPY_CLASS(hashclass)                                       \
 616     }
 617
 618 #endif
 619
 620 // this macro is to be used in the user code
 621 #define WX_DECLARE_HASH(el, list, hash) \
 622     _WX_DECLARE_HASH(el, list, hash, class)
 623
 624 // and this one does exactly the same thing but should be used inside the
 625 // library
 626 #define WX_DECLARE_EXPORTED_HASH(el, list, hash)  \
 627     _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
 628
 629 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo)  \
 630     _WX_DECLARE_HASH(el, list, hash, class usergoo)
 631
 632 // delete all hash elements
 633 //
 634 // NB: the class declaration of the hash elements must be visible from the
 635 //     place where you use this macro, otherwise the proper destructor may not
 636 //     be called (a decent compiler should give a warning about it, but don't
 637 //     count on it)!
 638 #define WX_CLEAR_HASH_TABLE(hash)                                            \
 639     {                                                                        \
 640         (hash).BeginFind();                                                  \
 641         wxHashTable::compatibility_iterator it = (hash).Next();              \
 642         while( it )                                                          \
 643         {                                                                    \
 644             delete it->GetData();                                            \
 645             it = (hash).Next();                                              \
 646         }                                                                    \
 647         (hash).Clear();                                                      \
 648     }
 649
 650 #endif
 651     // _WX_HASH_H__