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                               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         void SetData( wxObject* e )
 387         {
 388             citer* i = (citer*)this;
 389             i->m_iter->second = e;
 390         }
 391     private:
 392         dummy();
 393     };
 394 public:
 395     wxHashTable( wxKeyType keyType = wxKEY_INTEGER,
 396                  size_t size = wxHASH_SIZE_DEFAULT )
 397         : wxHashTableBase( keyType, size ) { }
 398
 399     void Destroy() { Clear(); }
 400
 401     // key and value are the same
 402     void Put(long value, wxObject *object) { DoPut( value, object ); }
 403     void Put(const wxChar *value, wxObject *object) { DoPut( value, object ); }
 404
 405     // key and value are the same
 406     wxObject *Get(long value) const { return (wxObject*)DoGet( value ); }
 407     wxObject *Get(const wxChar *value) const { return (wxObject*)DoGet( value ); }
 408
 409     // Deletes entry and returns data if found
 410     wxObject *Delete(long key) { return (wxObject*)DoGet( key ); }
 411     wxObject *Delete(const wxChar *key) { return (wxObject*)DoGet( key ); }
 412
 413 #if 0
 414     // Construct your own integer key from a string, e.g. in case
 415     // you need to combine it with something
 416     long MakeKey(const wxChar *string) const;
 417 #endif
 418     // Way of iterating through whole hash table (e.g. to delete everything)
 419     // Not necessary, of course, if you're only storing pointers to
 420     // objects maintained separately
 421     void BeginFind() { m_iter = citer( &this->m_map, this->m_map.begin() ); }
 422     compatibility_iterator Next()
 423     {
 424         compatibility_iterator it = m_iter;
 425         if( m_iter )
 426             m_iter = m_iter->GetNext();
 427         return it;
 428     }
 429
 430     void Clear() { wxHashTableBase::Clear(); }
 431
 432     size_t GetCount() const { return wxHashTableBase::GetCount(); }
 433 private:
 434     compatibility_iterator m_iter;
 435 };
 436
 437 #else // if !wxUSE_STL
 438
 439 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
 440 {
 441 public:
 442     int n;
 443     int current_position;
 444     wxNode *current_node;
 445
 446     unsigned int key_type;
 447     wxList **hash_table;
 448
 449     wxHashTable(int the_key_type = wxKEY_INTEGER,
 450                 int size = wxHASH_SIZE_DEFAULT);
 451     ~wxHashTable();
 452
 453     // copy ctor and assignment operator
 454     wxHashTable(const wxHashTable& table) : wxObject()
 455         { DoCopy(table); }
 456     wxHashTable& operator=(const wxHashTable& table)
 457         { Clear(); DoCopy(table); return *this; }
 458
 459     void DoCopy(const wxHashTable& table);
 460
 461     void Destroy();
 462
 463     bool Create(int the_key_type = wxKEY_INTEGER,
 464                 int size = wxHASH_SIZE_DEFAULT);
 465
 466     // Note that there are 2 forms of Put, Get.
 467     // With a key and a value, the *value* will be checked
 468     // when a collision is detected. Otherwise, if there are
 469     // 2 items with a different value but the same key,
 470     // we'll retrieve the WRONG ONE. So where possible,
 471     // supply the required value along with the key.
 472     // In fact, the value-only versions make a key, and still store
 473     // the value. The use of an explicit key might be required
 474     // e.g. when combining several values into one key.
 475     // When doing that, it's highly likely we'll get a collision,
 476     // e.g. 1 + 2 = 3, 2 + 1 = 3.
 477
 478     // key and value are NOT necessarily the same
 479     void Put(long key, long value, wxObject *object);
 480     void Put(long key, const wxChar *value, wxObject *object);
 481
 482     // key and value are the same
 483     void Put(long value, wxObject *object);
 484     void Put(const wxChar *value, wxObject *object);
 485
 486     // key and value not the same
 487     wxObject *Get(long key, long value) const;
 488     wxObject *Get(long key, const wxChar *value) const;
 489
 490     // key and value are the same
 491     wxObject *Get(long value) const;
 492     wxObject *Get(const wxChar *value) const;
 493
 494     // Deletes entry and returns data if found
 495     wxObject *Delete(long key);
 496     wxObject *Delete(const wxChar *key);
 497
 498     wxObject *Delete(long key, int value);
 499     wxObject *Delete(long key, const wxChar *value);
 500
 501     // Construct your own integer key from a string, e.g. in case
 502     // you need to combine it with something
 503     long MakeKey(const wxChar *string) const;
 504
 505     // Way of iterating through whole hash table (e.g. to delete everything)
 506     // Not necessary, of course, if you're only storing pointers to
 507     // objects maintained separately
 508
 509     void BeginFind();
 510     wxNode *Next();
 511
 512     void DeleteContents(bool flag);
 513     void Clear();
 514
 515     // Returns number of nodes
 516     size_t GetCount() const { return m_count; }
 517
 518     typedef wxNode* compatibility_iterator;
 519 private:
 520     size_t m_count;             // number of elements in the hashtable
 521     bool m_deleteContents;
 522
 523     DECLARE_DYNAMIC_CLASS(wxHashTable)
 524 };
 525
 526 #endif
 527
 528 #if wxUSE_STL
 529
 530 // defines a new type safe hash table which stores the elements of type eltype
 531 // in lists of class listclass
 532 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp)                  \
 533     classexp hashclass : public wxHashTableBase                               \
 534     {                                                                         \
 535     public:                                                                   \
 536         hashclass(wxKeyType keyType = wxKEY_INTEGER,                          \
 537                   size_t size = wxHASH_SIZE_DEFAULT)                          \
 538             : wxHashTableBase(keyType, size) { }                              \
 539                                                                               \
 540         ~hashclass() { Destroy(); }                                           \
 541                                                                               \
 542         void Destroy() { m_map.clear(); }                                     \
 543         void Put(long key, eltype *data) { DoPut(key, (void*)data); }         \
 544         eltype *Get(long key) const { return (eltype*)DoGet(key); }           \
 545         eltype *Delete(long key) { return (eltype*)DoDelete(key); }           \
 546     }
 547
 548 #else // if !wxUSE_STL
 549
 550 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp)               \
 551     classexp hashclass : public wxHashTableBase                                \
 552     {                                                                          \
 553     public:                                                                    \
 554         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
 555                   size_t size = wxHASH_SIZE_DEFAULT)                           \
 556             { Create(keyType, size); }                                         \
 557                                                                                \
 558         ~hashclass() { Destroy(); }                                            \
 559                                                                                \
 560         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
 561         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
 562                                                                                \
 563         eltype *Get(long key, long value) const                                \
 564         {                                                                      \
 565             wxNodeBase *node = GetNode(key, value);                            \
 566             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
 567         }                                                                      \
 568         eltype *Get(long key) const { return Get(key, key); }                  \
 569                                                                                \
 570         eltype *Delete(long key, long value)                                   \
 571         {                                                                      \
 572             eltype *data;                                                      \
 573                                                                                \
 574             wxNodeBase *node = GetNode(key, value);                            \
 575             if ( node )                                                        \
 576             {                                                                  \
 577                 data = ((listclass::Node *)node)->GetData();                   \
 578                                                                                \
 579                 delete node;                                                   \
 580                 m_count--;                                                     \
 581             }                                                                  \
 582             else                                                               \
 583             {                                                                  \
 584                 data = (eltype *)0;                                            \
 585             }                                                                  \
 586                                                                                \
 587             return data;                                                       \
 588         }                                                                      \
 589         eltype *Delete(long key) { return Delete(key, key); }                  \
 590                                                                                \
 591     protected:                                                                 \
 592         void DoPut(long key, long value, eltype *data)                         \
 593         {                                                                      \
 594             size_t slot = (size_t)abs((int)(key % (long)m_hashSize));          \
 595                                                                                \
 596             if ( !m_hashTable[slot] )                                          \
 597             {                                                                  \
 598                 m_hashTable[slot] = new listclass(m_keyType);                  \
 599                 if ( m_deleteContents )                                        \
 600                     m_hashTable[slot]->DeleteContents(TRUE);                   \
 601             }                                                                  \
 602                                                                                \
 603             ((listclass *)m_hashTable[slot])->Append(value, data);             \
 604             m_count++;                                                         \
 605         }                                                                      \
 606                                                                                \
 607         DECLARE_NO_COPY_CLASS(hashclass)                                       \
 608     }
 609
 610 #endif
 611
 612 // this macro is to be used in the user code
 613 #define WX_DECLARE_HASH(el, list, hash) \
 614     _WX_DECLARE_HASH(el, list, hash, class)
 615
 616 // and this one does exactly the same thing but should be used inside the
 617 // library
 618 #define WX_DECLARE_EXPORTED_HASH(el, list, hash)  \
 619     _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
 620
 621 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo)  \
 622     _WX_DECLARE_HASH(el, list, hash, class usergoo)
 623
 624 // delete all hash elements
 625 //
 626 // NB: the class declaration of the hash elements must be visible from the
 627 //     place where you use this macro, otherwise the proper destructor may not
 628 //     be called (a decent compiler should give a warning about it, but don't
 629 //     count on it)!
 630 #define WX_CLEAR_HASH_TABLE(hash)                                            \
 631     {                                                                        \
 632         (hash).BeginFind();                                                  \
 633         wxHashTable::compatibility_iterator it = (hash).Next();              \
 634         while( it )                                                          \
 635         {                                                                    \
 636             delete it->GetData();                                            \
 637             it = (hash).Next();                                              \
 638         }                                                                    \
 639         (hash).Clear();                                                      \
 640     }
 641
 642 #endif
 643     // _WX_HASH_H__