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