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