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 #include "wx/defs.h"
  16
  17 #if !wxUSE_STL && WXWIN_COMPATIBILITY_2_4
  18     #define wxUSE_OLD_HASH_TABLE 1
  19 #else
  20     #define wxUSE_OLD_HASH_TABLE 0
  21 #endif
  22
  23 #if !wxUSE_STL
  24     #include "wx/object.h"
  25 #else
  26     class WXDLLIMPEXP_BASE wxObject;
  27 #endif
  28 #if wxUSE_OLD_HASH_TABLE
  29     #include "wx/list.h"
  30 #endif
  31 #if WXWIN_COMPATIBILITY_2_4
  32     #include "wx/dynarray.h"
  33 #endif
  34
  35 // the default size of the hash
  36 #define wxHASH_SIZE_DEFAULT     (1000)
  37
  38 /*
  39  * A hash table is an array of user-definable size with lists
  40  * of data items hanging off the array positions.  Usually there'll
  41  * be a hit, so no search is required; otherwise we'll have to run down
  42  * the list to find the desired item.
  43 */
  44
  45 // ----------------------------------------------------------------------------
  46 // this is the base class for object hashes: hash tables which contain
  47 // pointers to objects
  48 // ----------------------------------------------------------------------------
  49
  50 #if wxUSE_OLD_HASH_TABLE
  51
  52 class WXDLLIMPEXP_BASE wxHashTableBase : public wxObject
  53 {
  54 public:
  55     wxHashTableBase();
  56
  57     void Create(wxKeyType keyType = wxKEY_INTEGER,
  58                 size_t size = wxHASH_SIZE_DEFAULT);
  59     void Destroy();
  60
  61     size_t GetSize() const { return m_hashSize; }
  62     size_t GetCount() const { return m_count; }
  63
  64     void DeleteContents(bool flag);
  65
  66 protected:
  67     // find the node for (key, value)
  68     wxNodeBase *GetNode(long key, long value) const;
  69
  70     // the array of lists in which we store the values for given key hash
  71     wxListBase **m_hashTable;
  72
  73     // the size of m_lists array
  74     size_t m_hashSize;
  75
  76     // the type of indexing we use
  77     wxKeyType m_keyType;
  78
  79     // the total number of elements in the hash
  80     size_t m_count;
  81
  82     // should we delete our data?
  83     bool m_deleteContents;
  84
  85 private:
  86     // no copy ctor/assignment operator (yet)
  87     DECLARE_NO_COPY_CLASS(wxHashTableBase)
  88 };
  89
  90 #else // if !wxUSE_OLD_HASH_TABLE
  91
  92 #if !defined(wxENUM_KEY_TYPE_DEFINED)
  93 #define wxENUM_KEY_TYPE_DEFINED
  94
  95 enum wxKeyType
  96 {
  97     wxKEY_NONE,
  98     wxKEY_INTEGER,
  99     wxKEY_STRING
 100 };
 101
 102 #endif
 103
 104 union wxHashKeyValue
 105 {
 106     long integer;
 107     wxChar *string;
 108 };
 109
 110 // for some compilers (AIX xlC), defining it as friend inside the class is not
 111 // enough, so provide a real forward declaration
 112 class WXDLLIMPEXP_BASE wxHashTableBase;
 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     // key and value are the same
 352     void Put(long value, wxObject *object)
 353         { DoPut( value, value, object ); }
 354     void Put(long lhash, long value, wxObject *object)
 355         { DoPut( value, lhash, object ); }
 356     void Put(const wxChar *value, wxObject *object)
 357         { DoPut( value, MakeKey( value ), object ); }
 358     void Put(long lhash, const wxChar *value, wxObject *object)
 359         { DoPut( value, lhash, 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 lhash, long value) const
 365         { return (wxObject*)DoGet( value, lhash ); }
 366     wxObject *Get(const wxChar *value) const
 367         { return (wxObject*)DoGet( value, MakeKey( value ) ); }
 368     wxObject *Get(long lhash, const wxChar *value) const
 369         { return (wxObject*)DoGet( value, lhash ); }
 370
 371     // Deletes entry and returns data if found
 372     wxObject *Delete(long key)
 373         { return (wxObject*)DoDelete( key, key ); }
 374     wxObject *Delete(long lhash, long key)
 375         { return (wxObject*)DoDelete( key, lhash ); }
 376     wxObject *Delete(const wxChar *key)
 377         { return (wxObject*)DoDelete( key, MakeKey( key ) ); }
 378     wxObject *Delete(long lhash, const wxChar *key)
 379         { return (wxObject*)DoDelete( key, lhash ); }
 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     // copy helper
 397     void DoCopy( const wxHashTable& copy );
 398
 399     // searches the next node starting from bucket bucketStart and sets
 400     // m_curr to it and m_currBucket to its bucket
 401     void GetNextNode( size_t bucketStart );
 402 private:
 403     virtual void DoDeleteContents( wxHashTableBase_Node* node );
 404
 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     virtual ~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         virtual ~hashclass() { Destroy(); }                                   \
 518                                                                               \
 519         void Put(long key, eltype *data) { DoPut(key, key, (void*)data); }    \
 520         void Put(long lhash, long key, eltype *data)                          \
 521             { DoPut(key, lhash, (void*)data); }                               \
 522         eltype *Get(long key) const { return (eltype*)DoGet(key, key); }      \
 523         eltype *Get(long lhash, long key) const                               \
 524             { return (eltype*)DoGet(key, lhash); }                            \
 525         eltype *Delete(long key) { return (eltype*)DoDelete(key, key); }      \
 526         eltype *Delete(long lhash, long key)                                  \
 527             { return (eltype*)DoDelete(key, lhash); }                         \
 528     private:                                                                  \
 529         virtual void DoDeleteContents( wxHashTableBase_Node* node )           \
 530             { delete (eltype*)node->GetData(); }                              \
 531                                                                               \
 532         DECLARE_NO_COPY_CLASS(hashclass)                                      \
 533     }
 534
 535 #else // if wxUSE_OLD_HASH_TABLE
 536
 537 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp)               \
 538     classexp hashclass : public wxHashTableBase                                \
 539     {                                                                          \
 540     public:                                                                    \
 541         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
 542                   size_t size = wxHASH_SIZE_DEFAULT)                           \
 543             { Create(keyType, size); }                                         \
 544                                                                                \
 545         virtual ~hashclass() { Destroy(); }                                            \
 546                                                                                \
 547         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
 548         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
 549                                                                                \
 550         eltype *Get(long key, long value) const                                \
 551         {                                                                      \
 552             wxNodeBase *node = GetNode(key, value);                            \
 553             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
 554         }                                                                      \
 555         eltype *Get(long key) const { return Get(key, key); }                  \
 556                                                                                \
 557         eltype *Delete(long key, long value)                                   \
 558         {                                                                      \
 559             eltype *data;                                                      \
 560                                                                                \
 561             wxNodeBase *node = GetNode(key, value);                            \
 562             if ( node )                                                        \
 563             {                                                                  \
 564                 data = ((listclass::Node *)node)->GetData();                   \
 565                                                                                \
 566                 delete node;                                                   \
 567                 m_count--;                                                     \
 568             }                                                                  \
 569             else                                                               \
 570             {                                                                  \
 571                 data = (eltype *)0;                                            \
 572             }                                                                  \
 573                                                                                \
 574             return data;                                                       \
 575         }                                                                      \
 576         eltype *Delete(long key) { return Delete(key, key); }                  \
 577                                                                                \
 578     protected:                                                                 \
 579         void DoPut(long key, long value, eltype *data)                         \
 580         {                                                                      \
 581             size_t slot = (size_t)abs((int)(key % (long)m_hashSize));          \
 582                                                                                \
 583             if ( !m_hashTable[slot] )                                          \
 584             {                                                                  \
 585                 m_hashTable[slot] = new listclass(m_keyType);                  \
 586                 if ( m_deleteContents )                                        \
 587                     m_hashTable[slot]->DeleteContents(true);                   \
 588             }                                                                  \
 589                                                                                \
 590             ((listclass *)m_hashTable[slot])->Append(value, data);             \
 591             m_count++;                                                         \
 592         }                                                                      \
 593                                                                                \
 594         DECLARE_NO_COPY_CLASS(hashclass)                                       \
 595     }
 596
 597 #endif // wxUSE_OLD_HASH_TABLE
 598
 599 // this macro is to be used in the user code
 600 #define WX_DECLARE_HASH(el, list, hash) \
 601     _WX_DECLARE_HASH(el, list, hash, class)
 602
 603 // and this one does exactly the same thing but should be used inside the
 604 // library
 605 #define WX_DECLARE_EXPORTED_HASH(el, list, hash)  \
 606     _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
 607
 608 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo)  \
 609     _WX_DECLARE_HASH(el, list, hash, class usergoo)
 610
 611 // delete all hash elements
 612 //
 613 // NB: the class declaration of the hash elements must be visible from the
 614 //     place where you use this macro, otherwise the proper destructor may not
 615 //     be called (a decent compiler should give a warning about it, but don't
 616 //     count on it)!
 617 #define WX_CLEAR_HASH_TABLE(hash)                                            \
 618     {                                                                        \
 619         (hash).BeginFind();                                                  \
 620         wxHashTable::compatibility_iterator it = (hash).Next();              \
 621         while( it )                                                          \
 622         {                                                                    \
 623             delete it->GetData();                                            \
 624             it = (hash).Next();                                              \
 625         }                                                                    \
 626         (hash).Clear();                                                      \
 627     }
 628
 629 #endif
 630     // _WX_HASH_H__