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