| 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 | #include "wx/string.h" |
| 17 | |
| 18 | #if !wxUSE_STL |
| 19 | #include "wx/object.h" |
| 20 | #else |
| 21 | class WXDLLIMPEXP_FWD_BASE wxObject; |
| 22 | #endif |
| 23 | |
| 24 | // the default size of the hash |
| 25 | #define wxHASH_SIZE_DEFAULT (1000) |
| 26 | |
| 27 | /* |
| 28 | * A hash table is an array of user-definable size with lists |
| 29 | * of data items hanging off the array positions. Usually there'll |
| 30 | * be a hit, so no search is required; otherwise we'll have to run down |
| 31 | * the list to find the desired item. |
| 32 | */ |
| 33 | |
| 34 | union wxHashKeyValue |
| 35 | { |
| 36 | long integer; |
| 37 | wxString *string; |
| 38 | }; |
| 39 | |
| 40 | // for some compilers (AIX xlC), defining it as friend inside the class is not |
| 41 | // enough, so provide a real forward declaration |
| 42 | class WXDLLIMPEXP_FWD_BASE wxHashTableBase; |
| 43 | |
| 44 | class WXDLLIMPEXP_BASE wxHashTableBase_Node |
| 45 | { |
| 46 | friend class WXDLLIMPEXP_FWD_BASE wxHashTableBase; |
| 47 | typedef class WXDLLIMPEXP_FWD_BASE wxHashTableBase_Node _Node; |
| 48 | public: |
| 49 | wxHashTableBase_Node( long key, void* value, |
| 50 | wxHashTableBase* table ); |
| 51 | wxHashTableBase_Node( const wxString& key, void* value, |
| 52 | wxHashTableBase* table ); |
| 53 | ~wxHashTableBase_Node(); |
| 54 | |
| 55 | long GetKeyInteger() const { return m_key.integer; } |
| 56 | const wxString& GetKeyString() const { return *m_key.string; } |
| 57 | |
| 58 | void* GetData() const { return m_value; } |
| 59 | void SetData( void* data ) { m_value = data; } |
| 60 | |
| 61 | protected: |
| 62 | _Node* GetNext() const { return m_next; } |
| 63 | |
| 64 | protected: |
| 65 | // next node in the chain |
| 66 | wxHashTableBase_Node* m_next; |
| 67 | |
| 68 | // key |
| 69 | wxHashKeyValue m_key; |
| 70 | |
| 71 | // value |
| 72 | void* m_value; |
| 73 | |
| 74 | // pointer to the hash containing the node, used to remove the |
| 75 | // node from the hash when the user deletes the node iterating |
| 76 | // through it |
| 77 | // TODO: move it to wxHashTable_Node (only wxHashTable supports |
| 78 | // iteration) |
| 79 | wxHashTableBase* m_hashPtr; |
| 80 | }; |
| 81 | |
| 82 | class WXDLLIMPEXP_BASE wxHashTableBase |
| 83 | #if !wxUSE_STL |
| 84 | : public wxObject |
| 85 | #endif |
| 86 | { |
| 87 | friend class WXDLLIMPEXP_FWD_BASE wxHashTableBase_Node; |
| 88 | public: |
| 89 | typedef wxHashTableBase_Node Node; |
| 90 | |
| 91 | wxHashTableBase(); |
| 92 | virtual ~wxHashTableBase() { } |
| 93 | |
| 94 | void Create( wxKeyType keyType = wxKEY_INTEGER, |
| 95 | size_t size = wxHASH_SIZE_DEFAULT ); |
| 96 | void Clear(); |
| 97 | void Destroy(); |
| 98 | |
| 99 | size_t GetSize() const { return m_size; } |
| 100 | size_t GetCount() const { return m_count; } |
| 101 | |
| 102 | void DeleteContents( bool flag ) { m_deleteContents = flag; } |
| 103 | |
| 104 | static long MakeKey(const wxString& string); |
| 105 | |
| 106 | protected: |
| 107 | void DoPut( long key, long hash, void* data ); |
| 108 | void DoPut( const wxString& key, long hash, void* data ); |
| 109 | void* DoGet( long key, long hash ) const; |
| 110 | void* DoGet( const wxString& key, long hash ) const; |
| 111 | void* DoDelete( long key, long hash ); |
| 112 | void* DoDelete( const wxString& key, long hash ); |
| 113 | |
| 114 | private: |
| 115 | // Remove the node from the hash, *only called from |
| 116 | // ~wxHashTable*_Node destructor |
| 117 | void DoRemoveNode( wxHashTableBase_Node* node ); |
| 118 | |
| 119 | // destroys data contained in the node if appropriate: |
| 120 | // deletes the key if it is a string and destrys |
| 121 | // the value if m_deleteContents is true |
| 122 | void DoDestroyNode( wxHashTableBase_Node* node ); |
| 123 | |
| 124 | // inserts a node in the table (at the end of the chain) |
| 125 | void DoInsertNode( size_t bucket, wxHashTableBase_Node* node ); |
| 126 | |
| 127 | // removes a node from the table (fiven a pointer to the previous |
| 128 | // but does not delete it (only deletes its contents) |
| 129 | void DoUnlinkNode( size_t bucket, wxHashTableBase_Node* node, |
| 130 | wxHashTableBase_Node* prev ); |
| 131 | |
| 132 | // unconditionally deletes node value (invoking the |
| 133 | // correct destructor) |
| 134 | virtual void DoDeleteContents( wxHashTableBase_Node* node ) = 0; |
| 135 | |
| 136 | protected: |
| 137 | // number of buckets |
| 138 | size_t m_size; |
| 139 | |
| 140 | // number of nodes (key/value pairs) |
| 141 | size_t m_count; |
| 142 | |
| 143 | // table |
| 144 | Node** m_table; |
| 145 | |
| 146 | // key typ (INTEGER/STRING) |
| 147 | wxKeyType m_keyType; |
| 148 | |
| 149 | // delete contents when hash is cleared |
| 150 | bool m_deleteContents; |
| 151 | |
| 152 | private: |
| 153 | DECLARE_NO_COPY_CLASS(wxHashTableBase) |
| 154 | }; |
| 155 | |
| 156 | // ---------------------------------------------------------------------------- |
| 157 | // for compatibility only |
| 158 | // ---------------------------------------------------------------------------- |
| 159 | |
| 160 | class WXDLLIMPEXP_BASE wxHashTable_Node : public wxHashTableBase_Node |
| 161 | { |
| 162 | friend class WXDLLIMPEXP_FWD_BASE wxHashTable; |
| 163 | public: |
| 164 | wxHashTable_Node( long key, void* value, |
| 165 | wxHashTableBase* table ) |
| 166 | : wxHashTableBase_Node( key, value, table ) { } |
| 167 | wxHashTable_Node( const wxString& key, void* value, |
| 168 | wxHashTableBase* table ) |
| 169 | : wxHashTableBase_Node( key, value, table ) { } |
| 170 | |
| 171 | wxObject* GetData() const |
| 172 | { return (wxObject*)wxHashTableBase_Node::GetData(); } |
| 173 | void SetData( wxObject* data ) |
| 174 | { wxHashTableBase_Node::SetData( data ); } |
| 175 | |
| 176 | wxHashTable_Node* GetNext() const |
| 177 | { return (wxHashTable_Node*)wxHashTableBase_Node::GetNext(); } |
| 178 | }; |
| 179 | |
| 180 | // should inherit protectedly, but it is public for compatibility in |
| 181 | // order to publicly inherit from wxObject |
| 182 | class WXDLLIMPEXP_BASE wxHashTable : public wxHashTableBase |
| 183 | { |
| 184 | typedef wxHashTableBase hash; |
| 185 | public: |
| 186 | typedef wxHashTable_Node Node; |
| 187 | typedef wxHashTable_Node* compatibility_iterator; |
| 188 | public: |
| 189 | wxHashTable( wxKeyType keyType = wxKEY_INTEGER, |
| 190 | size_t size = wxHASH_SIZE_DEFAULT ) |
| 191 | : wxHashTableBase() { Create( keyType, size ); BeginFind(); } |
| 192 | wxHashTable( const wxHashTable& table ); |
| 193 | |
| 194 | virtual ~wxHashTable() { Destroy(); } |
| 195 | |
| 196 | const wxHashTable& operator=( const wxHashTable& ); |
| 197 | |
| 198 | // key and value are the same |
| 199 | void Put(long value, wxObject *object) |
| 200 | { DoPut( value, value, object ); } |
| 201 | void Put(long lhash, long value, wxObject *object) |
| 202 | { DoPut( value, lhash, object ); } |
| 203 | void Put(const wxString& value, wxObject *object) |
| 204 | { DoPut( value, MakeKey( value ), object ); } |
| 205 | void Put(long lhash, const wxString& value, wxObject *object) |
| 206 | { DoPut( value, lhash, object ); } |
| 207 | |
| 208 | // key and value are the same |
| 209 | wxObject *Get(long value) const |
| 210 | { return (wxObject*)DoGet( value, value ); } |
| 211 | wxObject *Get(long lhash, long value) const |
| 212 | { return (wxObject*)DoGet( value, lhash ); } |
| 213 | wxObject *Get(const wxString& value) const |
| 214 | { return (wxObject*)DoGet( value, MakeKey( value ) ); } |
| 215 | wxObject *Get(long lhash, const wxString& value) const |
| 216 | { return (wxObject*)DoGet( value, lhash ); } |
| 217 | |
| 218 | // Deletes entry and returns data if found |
| 219 | wxObject *Delete(long key) |
| 220 | { return (wxObject*)DoDelete( key, key ); } |
| 221 | wxObject *Delete(long lhash, long key) |
| 222 | { return (wxObject*)DoDelete( key, lhash ); } |
| 223 | wxObject *Delete(const wxString& key) |
| 224 | { return (wxObject*)DoDelete( key, MakeKey( key ) ); } |
| 225 | wxObject *Delete(long lhash, const wxString& key) |
| 226 | { return (wxObject*)DoDelete( key, lhash ); } |
| 227 | |
| 228 | // Way of iterating through whole hash table (e.g. to delete everything) |
| 229 | // Not necessary, of course, if you're only storing pointers to |
| 230 | // objects maintained separately |
| 231 | void BeginFind() { m_curr = NULL; m_currBucket = 0; } |
| 232 | Node* Next(); |
| 233 | |
| 234 | void Clear() { wxHashTableBase::Clear(); } |
| 235 | |
| 236 | size_t GetCount() const { return wxHashTableBase::GetCount(); } |
| 237 | protected: |
| 238 | // copy helper |
| 239 | void DoCopy( const wxHashTable& copy ); |
| 240 | |
| 241 | // searches the next node starting from bucket bucketStart and sets |
| 242 | // m_curr to it and m_currBucket to its bucket |
| 243 | void GetNextNode( size_t bucketStart ); |
| 244 | private: |
| 245 | virtual void DoDeleteContents( wxHashTableBase_Node* node ); |
| 246 | |
| 247 | // current node |
| 248 | Node* m_curr; |
| 249 | |
| 250 | // bucket the current node belongs to |
| 251 | size_t m_currBucket; |
| 252 | }; |
| 253 | |
| 254 | // defines a new type safe hash table which stores the elements of type eltype |
| 255 | // in lists of class listclass |
| 256 | #define _WX_DECLARE_HASH(eltype, dummy, hashclass, classexp) \ |
| 257 | classexp hashclass : public wxHashTableBase \ |
| 258 | { \ |
| 259 | public: \ |
| 260 | hashclass(wxKeyType keyType = wxKEY_INTEGER, \ |
| 261 | size_t size = wxHASH_SIZE_DEFAULT) \ |
| 262 | : wxHashTableBase() { Create(keyType, size); } \ |
| 263 | \ |
| 264 | virtual ~hashclass() { Destroy(); } \ |
| 265 | \ |
| 266 | void Put(long key, eltype *data) { DoPut(key, key, (void*)data); } \ |
| 267 | void Put(long lhash, long key, eltype *data) \ |
| 268 | { DoPut(key, lhash, (void*)data); } \ |
| 269 | eltype *Get(long key) const { return (eltype*)DoGet(key, key); } \ |
| 270 | eltype *Get(long lhash, long key) const \ |
| 271 | { return (eltype*)DoGet(key, lhash); } \ |
| 272 | eltype *Delete(long key) { return (eltype*)DoDelete(key, key); } \ |
| 273 | eltype *Delete(long lhash, long key) \ |
| 274 | { return (eltype*)DoDelete(key, lhash); } \ |
| 275 | private: \ |
| 276 | virtual void DoDeleteContents( wxHashTableBase_Node* node ) \ |
| 277 | { delete (eltype*)node->GetData(); } \ |
| 278 | \ |
| 279 | DECLARE_NO_COPY_CLASS(hashclass) \ |
| 280 | } |
| 281 | |
| 282 | |
| 283 | // this macro is to be used in the user code |
| 284 | #define WX_DECLARE_HASH(el, list, hash) \ |
| 285 | _WX_DECLARE_HASH(el, list, hash, class) |
| 286 | |
| 287 | // and this one does exactly the same thing but should be used inside the |
| 288 | // library |
| 289 | #define WX_DECLARE_EXPORTED_HASH(el, list, hash) \ |
| 290 | _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT) |
| 291 | |
| 292 | #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \ |
| 293 | _WX_DECLARE_HASH(el, list, hash, class usergoo) |
| 294 | |
| 295 | // delete all hash elements |
| 296 | // |
| 297 | // NB: the class declaration of the hash elements must be visible from the |
| 298 | // place where you use this macro, otherwise the proper destructor may not |
| 299 | // be called (a decent compiler should give a warning about it, but don't |
| 300 | // count on it)! |
| 301 | #define WX_CLEAR_HASH_TABLE(hash) \ |
| 302 | { \ |
| 303 | (hash).BeginFind(); \ |
| 304 | wxHashTable::compatibility_iterator it = (hash).Next(); \ |
| 305 | while( it ) \ |
| 306 | { \ |
| 307 | delete it->GetData(); \ |
| 308 | it = (hash).Next(); \ |
| 309 | } \ |
| 310 | (hash).Clear(); \ |
| 311 | } |
| 312 | |
| 313 | #endif // _WX_HASH_H__ |