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