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