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 #ifdef __GNUG__
  16 #pragma interface "hash.h"
  17 #endif
  18
  19 #include "wx/list.h"
  20 #include "wx/dynarray.h"
  21
  22 // the default size of the hash
  23 #define wxHASH_SIZE_DEFAULT     (1000)
  24
  25 /*
  26  * A hash table is an array of user-definable size with lists
  27  * of data items hanging off the array positions.  Usually there'll
  28  * be a hit, so no search is required; otherwise we'll have to run down
  29  * the list to find the desired item.
  30 */
  31
  32 // ----------------------------------------------------------------------------
  33 // this is the base class for object hashes: hash tables which contain
  34 // pointers to objects
  35 // ----------------------------------------------------------------------------
  36
  37 class WXDLLEXPORT wxHashTableBase : public wxObject
  38 {
  39 public:
  40     wxHashTableBase();
  41
  42     void Create(wxKeyType keyType = wxKEY_INTEGER,
  43                 size_t size = wxHASH_SIZE_DEFAULT);
  44     void Destroy();
  45
  46     size_t GetSize() const { return m_hashSize; }
  47     size_t GetCount() const { return m_count; }
  48
  49     void DeleteContents(bool flag);
  50
  51 protected:
  52     // find the node for (key, value)
  53     wxNodeBase *GetNode(long key, long value) const;
  54
  55     // the array of lists in which we store the values for given key hash
  56     wxListBase **m_hashTable;
  57
  58     // the size of m_lists array
  59     size_t m_hashSize;
  60
  61     // the type of indexing we use
  62     wxKeyType m_keyType;
  63
  64     // the total number of elements in the hash
  65     size_t m_count;
  66
  67     // should we delete our data?
  68     bool m_deleteContents;
  69
  70 private:
  71     // no copy ctor/assignment operator (yet)
  72     DECLARE_NO_COPY_CLASS(wxHashTableBase);
  73 };
  74
  75 // ----------------------------------------------------------------------------
  76 // a hash table which stores longs
  77 // ----------------------------------------------------------------------------
  78
  79 class WXDLLEXPORT wxHashTableLong : public wxObject
  80 {
  81 public:
  82     wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT) { Init(size); }
  83     virtual ~wxHashTableLong();
  84
  85     void Create(size_t size = wxHASH_SIZE_DEFAULT);
  86     void Destroy();
  87
  88     size_t GetSize() const { return m_hashSize; }
  89     size_t GetCount() const { return m_count; }
  90
  91     void Put(long key, long value);
  92     long Get(long key) const;
  93     long Delete(long key);
  94
  95 protected:
  96     void Init(size_t size);
  97
  98 private:
  99     wxArrayLong **m_values,
 100                 **m_keys;
 101
 102     // the size of array above
 103     size_t m_hashSize;
 104
 105     // the total number of elements in the hash
 106     size_t m_count;
 107
 108     // not implemented yet
 109     DECLARE_NO_COPY_CLASS(wxHashTableLong);
 110 };
 111
 112 // ----------------------------------------------------------------------------
 113 // for compatibility only
 114 // ----------------------------------------------------------------------------
 115
 116 class WXDLLEXPORT wxHashTable : public wxObject
 117 {
 118 public:
 119     int n;
 120     int current_position;
 121     wxNode *current_node;
 122
 123     unsigned int key_type;
 124     wxList **hash_table;
 125
 126     wxHashTable(int the_key_type = wxKEY_INTEGER,
 127                 int size = wxHASH_SIZE_DEFAULT);
 128     ~wxHashTable();
 129
 130     // copy ctor and assignment operator
 131     wxHashTable(const wxHashTable& table) { DoCopy(table); }
 132     wxHashTable& operator=(const wxHashTable& table)
 133         { Clear(); DoCopy(table); return *this; }
 134
 135     void DoCopy(const wxHashTable& table);
 136
 137     void Destroy();
 138
 139     bool Create(int the_key_type = wxKEY_INTEGER,
 140                 int size = wxHASH_SIZE_DEFAULT);
 141
 142     // Note that there are 2 forms of Put, Get.
 143     // With a key and a value, the *value* will be checked
 144     // when a collision is detected. Otherwise, if there are
 145     // 2 items with a different value but the same key,
 146     // we'll retrieve the WRONG ONE. So where possible,
 147     // supply the required value along with the key.
 148     // In fact, the value-only versions make a key, and still store
 149     // the value. The use of an explicit key might be required
 150     // e.g. when combining several values into one key.
 151     // When doing that, it's highly likely we'll get a collision,
 152     // e.g. 1 + 2 = 3, 2 + 1 = 3.
 153
 154     // key and value are NOT necessarily the same
 155     void Put(long key, long value, wxObject *object);
 156     void Put(long key, const wxChar *value, wxObject *object);
 157
 158     // key and value are the same
 159     void Put(long value, wxObject *object);
 160     void Put(const wxChar *value, wxObject *object);
 161
 162     // key and value not the same
 163     wxObject *Get(long key, long value) const;
 164     wxObject *Get(long key, const wxChar *value) const;
 165
 166     // key and value are the same
 167     wxObject *Get(long value) const;
 168     wxObject *Get(const wxChar *value) const;
 169
 170     // Deletes entry and returns data if found
 171     wxObject *Delete(long key);
 172     wxObject *Delete(const wxChar *key);
 173
 174     wxObject *Delete(long key, int value);
 175     wxObject *Delete(long key, const wxChar *value);
 176
 177     // Construct your own integer key from a string, e.g. in case
 178     // you need to combine it with something
 179     long MakeKey(const wxChar *string) const;
 180
 181     // Way of iterating through whole hash table (e.g. to delete everything)
 182     // Not necessary, of course, if you're only storing pointers to
 183     // objects maintained separately
 184
 185     void BeginFind();
 186     wxNode *Next();
 187
 188     void DeleteContents(bool flag);
 189     void Clear();
 190
 191     // Returns number of nodes
 192     size_t GetCount() const { return m_count; }
 193
 194 private:
 195     size_t m_count;             // number of elements in the hashtable
 196     bool m_deleteContents;
 197
 198     DECLARE_DYNAMIC_CLASS(wxHashTable)
 199 };
 200
 201 // defines a new type safe hash table which stores the elements of type eltype
 202 // in lists of class listclass
 203 #define WX_DECLARE_HASH(eltype, listclass, hashclass)                          \
 204     class WXDLLEXPORT hashclass : public wxHashTableBase                       \
 205     {                                                                          \
 206     public:                                                                    \
 207         hashclass(wxKeyType keyType = wxKEY_INTEGER,                           \
 208                   size_t size = wxHASH_SIZE_DEFAULT)                           \
 209             { Create(keyType, size); }                                         \
 210                                                                                \
 211         ~hashclass() { Destroy(); }                                            \
 212                                                                                \
 213         void Put(long key, long val, eltype *data) { DoPut(key, val, data); }  \
 214         void Put(long key, eltype *data) { DoPut(key, key, data); }            \
 215                                                                                \
 216         eltype *Get(long key, long value) const                                \
 217         {                                                                      \
 218             wxNodeBase *node = GetNode(key, value);                            \
 219             return node ? ((listclass::Node *)node)->GetData() : (eltype *)0;  \
 220         }                                                                      \
 221         eltype *Get(long key) const { return Get(key, key); }                  \
 222                                                                                \
 223         eltype *Delete(long key, long value)                                   \
 224         {                                                                      \
 225             eltype *data;                                                      \
 226                                                                                \
 227             wxNodeBase *node = GetNode(key, value);                            \
 228             if ( node )                                                        \
 229             {                                                                  \
 230                 data = ((listclass::Node *)node)->GetData();                   \
 231                                                                                \
 232                 delete node;                                                   \
 233                 m_count--;                                                     \
 234             }                                                                  \
 235             else                                                               \
 236             {                                                                  \
 237                 data = (eltype *)0;                                            \
 238             }                                                                  \
 239                                                                                \
 240             return data;                                                       \
 241         }                                                                      \
 242         eltype *Delete(long key) { return Delete(key, key); }                  \
 243                                                                                \
 244     protected:                                                                 \
 245         void DoPut(long key, long value, eltype *data)                         \
 246         {                                                                      \
 247             size_t slot = (size_t)abs(key % m_hashSize);                       \
 248                                                                                \
 249             if ( !m_hashTable[slot] )                                          \
 250             {                                                                  \
 251                 m_hashTable[slot] = new listclass(m_keyType);                  \
 252                 if ( m_deleteContents )                                        \
 253                     m_hashTable[slot]->DeleteContents(TRUE);                   \
 254             }                                                                  \
 255                                                                                \
 256             ((listclass *)m_hashTable[slot])->Append(value, data);             \
 257             m_count++;                                                         \
 258         }                                                                      \
 259     }
 260
 261 #endif
 262     // _WX_HASH_H__