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