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     // FIXME-UTF8: have only wxString forms here
 273     void Put(const wxString& value, wxObject *object)
 274         { DoPut( value, MakeKey( value ), object ); }
 275     void Put(long lhash, const wxChar *value, wxObject *object)
 276         { DoPut( value, lhash, object ); }
 277
 278     // key and value are the same
 279     wxObject *Get(long value) const
 280         { return (wxObject*)DoGet( value, value ); }
 281     wxObject *Get(long lhash, long value) const
 282         { return (wxObject*)DoGet( value, lhash ); }
 283     wxObject *Get(const wxChar *value) const
 284         { return (wxObject*)DoGet( value, MakeKey( value ) ); }
 285     // FIXME-UTF8: have only wxString forms here
 286     wxObject *Get(const wxString& value) const
 287         { return (wxObject*)DoGet( value, MakeKey( value ) ); }
 288     wxObject *Get(long lhash, const wxChar *value) const
 289         { return (wxObject*)DoGet( value, lhash ); }
 290
 291     // Deletes entry and returns data if found
 292     wxObject *Delete(long key)
 293         { return (wxObject*)DoDelete( key, key ); }
 294     wxObject *Delete(long lhash, long key)
 295         { return (wxObject*)DoDelete( key, lhash ); }
 296     wxObject *Delete(const wxChar *key)
 297         { return (wxObject*)DoDelete( key, MakeKey( key ) ); }
 298     // FIXME-UTF8: have only wxString forms here
 299     wxObject *Delete(const wxString& key)
 300         { return (wxObject*)DoDelete( key, MakeKey( key ) ); }
 301     wxObject *Delete(long lhash, const wxChar *key)
 302         { return (wxObject*)DoDelete( key, lhash ); }
 303
 304     // Construct your own integer key from a string, e.g. in case
 305     // you need to combine it with something
 306     long MakeKey(const wxChar *string) const
 307         { return wxHashTableBase::MakeKey(string); }
 308
 309     // Way of iterating through whole hash table (e.g. to delete everything)
 310     // Not necessary, of course, if you're only storing pointers to
 311     // objects maintained separately
 312     void BeginFind() { m_curr = NULL; m_currBucket = 0; }
 313     Node* Next();
 314
 315     void Clear() { wxHashTableBase::Clear(); }
 316
 317     size_t GetCount() const { return wxHashTableBase::GetCount(); }
 318 protected:
 319     // copy helper
 320     void DoCopy( const wxHashTable& copy );
 321
 322     // searches the next node starting from bucket bucketStart and sets
 323     // m_curr to it and m_currBucket to its bucket
 324     void GetNextNode( size_t bucketStart );
 325 private:
 326     virtual void DoDeleteContents( wxHashTableBase_Node* node );
 327
 328     // current node
 329     Node* m_curr;
 330
 331     // bucket the current node belongs to
 332     size_t m_currBucket;
 333 };
 334
 335 #else // if wxUSE_OLD_HASH_TABLE
 336
 337 class WXDLLIMPEXP_BASE wxHashTable : public wxObject
 338 {
 339 public:
 340     typedef wxNode Node;
 341     typedef wxNode* compatibility_iterator;
 342
 343     int n;
 344     int current_position;
 345     wxNode *current_node;
 346
 347     unsigned int key_type;
 348     wxList **hash_table;
 349
 350     wxHashTable(int the_key_type = wxKEY_INTEGER,
 351                 int size = wxHASH_SIZE_DEFAULT);
 352     virtual ~wxHashTable();
 353
 354     // copy ctor and assignment operator
 355     wxHashTable(const wxHashTable& table) : wxObject()
 356         { DoCopy(table); }
 357     wxHashTable& operator=(const wxHashTable& table)
 358         { Clear(); DoCopy(table); return *this; }
 359
 360     void DoCopy(const wxHashTable& table);
 361
 362     void Destroy();
 363
 364     bool Create(int the_key_type = wxKEY_INTEGER,
 365                 int size = wxHASH_SIZE_DEFAULT);
 366
 367     // Note that there are 2 forms of Put, Get.
 368     // With a key and a value, the *value* will be checked
 369     // when a collision is detected. Otherwise, if there are
 370     // 2 items with a different value but the same key,
 371     // we'll retrieve the WRONG ONE. So where possible,
 372     // supply the required value along with the key.
 373     // In fact, the value-only versions make a key, and still store
 374     // the value. The use of an explicit key might be required
 375     // e.g. when combining several values into one key.
 376     // When doing that, it's highly likely we'll get a collision,
 377     // e.g. 1 + 2 = 3, 2 + 1 = 3.
 378
 379     // key and value are NOT necessarily the same
 380     void Put(long key, long value, wxObject *object);
 381     void Put(long key, const wxChar *value, wxObject *object);
 382
 383     // key and value are the same
 384     void Put(long value, wxObject *object);
 385     void Put(const wxChar *value, wxObject *object);
 386
 387     // key and value not the same
 388     wxObject *Get(long key, long value) const;
 389     wxObject *Get(long key, const wxChar *value) const;
 390
 391     // key and value are the same
 392     wxObject *Get(long value) const;
 393     wxObject *Get(const wxChar *value) const;
 394
 395     // Deletes entry and returns data if found
 396     wxObject *Delete(long key);
 397     wxObject *Delete(const wxChar *key);
 398
 399     wxObject *Delete(long key, int value);
 400     wxObject *Delete(long key, const wxChar *value);
 401
 402     // Construct your own integer key from a string, e.g. in case
 403     // you need to combine it with something
 404     long MakeKey(const wxChar *string) const;
 405
 406     // Way of iterating through whole hash table (e.g. to delete everything)
 407     // Not necessary, of course, if you're only storing pointers to
 408     // objects maintained separately
 409
 410     void BeginFind();
 411     Node* Next();
 412
 413     void DeleteContents(bool flag);
 414     void Clear();
 415
 416     // Returns number of nodes
 417     size_t GetCount() const { return m_count; }
 418
 419 private:
 420     size_t m_count;             // number of elements in the hashtable
 421     bool m_deleteContents;
 422
 423     DECLARE_DYNAMIC_CLASS(wxHashTable)
 424 };
 425
 426 #endif // wxUSE_OLD_HASH_TABLE
 427
 428 #if !wxUSE_OLD_HASH_TABLE
 429
 430 // defines a new type safe hash table which stores the elements of type eltype
 431 // in lists of class listclass
 432 #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp)                  \
 433     classexp hashclass : public wxHashTableBase                               \
 434     {                                                                         \
 435     public:                                                                   \
 436         hashclass(wxKeyType keyType = wxKEY_INTEGER,                          \
 437                   size_t size = wxHASH_SIZE_DEFAULT)                          \
 438             : wxHashTableBase() { Create(keyType, size); }                    \
 439                                                                               \
 440         virtual ~hashclass() { Destroy(); }                                   \
 441                                                                               \
 442         void Put(long key, eltype *data) { DoPut(key, key, (void*)data); }    \
 443         void Put(long lhash, long key, eltype *data)                          \
 444             { DoPut(key, lhash, (void*)data); }                               \
 445         eltype *Get(long key) const { return (eltype*)DoGet(key, key); }      \
 446         eltype *Get(long lhash, long key) const                               \
 447             { return (eltype*)DoGet(key, lhash); }                            \
 448         eltype *Delete(long key) { return (eltype*)DoDelete(key, key); }      \
 449         eltype *Delete(long lhash, long key)                                  \
 450             { return (eltype*)DoDelete(key, lhash); }                         \
 451     private:                                                                  \
 452         virtual void DoDeleteContents( wxHashTableBase_Node* node )           \
 453             { delete (eltype*)node->GetData(); }                              \
 454                                                                               \
 455         DECLARE_NO_COPY_CLASS(hashclass)                                      \
 456     }
 457
 458 #else // if wxUSE_OLD_HASH_TABLE
 459
 460 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp)               \
 461     classexp hashclass : public wxHashTableBase                                \
 462     {                                                                          \
 463     public:                                                                    \
 464         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
 465                   size_t size = wxHASH_SIZE_DEFAULT)                           \
 466             { Create(keyType, size); }                                         \
 467                                                                                \
 468         virtual ~hashclass() { Destroy(); }                                            \
 469                                                                                \
 470         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
 471         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
 472                                                                                \
 473         eltype *Get(long key, long value) const                                \
 474         {                                                                      \
 475             wxNodeBase *node = GetNode(key, value);                            \
 476             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
 477         }                                                                      \
 478         eltype *Get(long key) const { return Get(key, key); }                  \
 479                                                                                \
 480         eltype *Delete(long key, long value)                                   \
 481         {                                                                      \
 482             eltype *data;                                                      \
 483                                                                                \
 484             wxNodeBase *node = GetNode(key, value);                            \
 485             if ( node )                                                        \
 486             {                                                                  \
 487                 data = ((listclass::Node *)node)->GetData();                   \
 488                                                                                \
 489                 delete node;                                                   \
 490                 m_count--;                                                     \
 491             }                                                                  \
 492             else                                                               \
 493             {                                                                  \
 494                 data = (eltype *)0;                                            \
 495             }                                                                  \
 496                                                                                \
 497             return data;                                                       \
 498         }                                                                      \
 499         eltype *Delete(long key) { return Delete(key, key); }                  \
 500                                                                                \
 501     protected:                                                                 \
 502         void DoPut(long key, long value, eltype *data)                         \
 503         {                                                                      \
 504             size_t slot = (size_t)abs((int)(key % (long)m_hashSize));          \
 505                                                                                \
 506             if ( !m_hashTable[slot] )                                          \
 507             {                                                                  \
 508                 m_hashTable[slot] = new listclass(m_keyType);                  \
 509                 if ( m_deleteContents )                                        \
 510                     m_hashTable[slot]->DeleteContents(true);                   \
 511             }                                                                  \
 512                                                                                \
 513             ((listclass *)m_hashTable[slot])->Append(value, data);             \
 514             m_count++;                                                         \
 515         }                                                                      \
 516                                                                                \
 517         DECLARE_NO_COPY_CLASS(hashclass)                                       \
 518     }
 519
 520 #endif // wxUSE_OLD_HASH_TABLE
 521
 522 // this macro is to be used in the user code
 523 #define WX_DECLARE_HASH(el, list, hash) \
 524     _WX_DECLARE_HASH(el, list, hash, class)
 525
 526 // and this one does exactly the same thing but should be used inside the
 527 // library
 528 #define WX_DECLARE_EXPORTED_HASH(el, list, hash)  \
 529     _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
 530
 531 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo)  \
 532     _WX_DECLARE_HASH(el, list, hash, class usergoo)
 533
 534 // delete all hash elements
 535 //
 536 // NB: the class declaration of the hash elements must be visible from the
 537 //     place where you use this macro, otherwise the proper destructor may not
 538 //     be called (a decent compiler should give a warning about it, but don't
 539 //     count on it)!
 540 #define WX_CLEAR_HASH_TABLE(hash)                                            \
 541     {                                                                        \
 542         (hash).BeginFind();                                                  \
 543         wxHashTable::compatibility_iterator it = (hash).Next();              \
 544         while( it )                                                          \
 545         {                                                                    \
 546             delete it->GetData();                                            \
 547             it = (hash).Next();                                              \
 548         }                                                                    \
 549         (hash).Clear();                                                      \
 550     }
 551
 552 #endif
 553     // _WX_HASH_H__