]> git.saurik.com Git - wxWidgets.git/blob - include/wx/hash.h
Added simplistic makefile/project files for wxWinCE.
[wxWidgets.git] / 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 #if defined(__GNUG__) && !defined(__APPLE__)
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)
83 { Init(size); }
84 virtual ~wxHashTableLong();
85
86 void Create(size_t size = wxHASH_SIZE_DEFAULT);
87 void Destroy();
88
89 size_t GetSize() const { return m_hashSize; }
90 size_t GetCount() const { return m_count; }
91
92 void Put(long key, long value);
93 long Get(long key) const;
94 long Delete(long key);
95
96 protected:
97 void Init(size_t size);
98
99 private:
100 wxArrayLong **m_values,
101 **m_keys;
102
103 // the size of array above
104 size_t m_hashSize;
105
106 // the total number of elements in the hash
107 size_t m_count;
108
109 // not implemented yet
110 DECLARE_NO_COPY_CLASS(wxHashTableLong)
111 };
112
113 // ----------------------------------------------------------------------------
114 // wxStringHashTable: a hash table which indexes strings with longs
115 // ----------------------------------------------------------------------------
116
117 class WXDLLEXPORT wxStringHashTable : public wxObject
118 {
119 public:
120 wxStringHashTable(size_t sizeTable = wxHASH_SIZE_DEFAULT);
121 virtual ~wxStringHashTable();
122
123 // add a string associated with this key to the table
124 void Put(long key, const wxString& value);
125
126 // get the string from the key: if not found, an empty string is returned
127 // and the wasFound is set to FALSE if not NULL
128 wxString Get(long key, bool *wasFound = NULL) const;
129
130 // remove the item, returning TRUE if the item was found and deleted
131 bool Delete(long key) const;
132
133 // clean up
134 void Destroy();
135
136 private:
137 wxArrayLong **m_keys;
138 wxArrayString **m_values;
139
140 // the size of array above
141 size_t m_hashSize;
142
143 DECLARE_NO_COPY_CLASS(wxStringHashTable)
144 };
145
146 // ----------------------------------------------------------------------------
147 // for compatibility only
148 // ----------------------------------------------------------------------------
149
150 class WXDLLEXPORT wxHashTable : public wxObject
151 {
152 public:
153 int n;
154 int current_position;
155 wxNode *current_node;
156
157 unsigned int key_type;
158 wxList **hash_table;
159
160 wxHashTable(int the_key_type = wxKEY_INTEGER,
161 int size = wxHASH_SIZE_DEFAULT);
162 ~wxHashTable();
163
164 // copy ctor and assignment operator
165 wxHashTable(const wxHashTable& table) : wxObject()
166 { DoCopy(table); }
167 wxHashTable& operator=(const wxHashTable& table)
168 { Clear(); DoCopy(table); return *this; }
169
170 void DoCopy(const wxHashTable& table);
171
172 void Destroy();
173
174 bool Create(int the_key_type = wxKEY_INTEGER,
175 int size = wxHASH_SIZE_DEFAULT);
176
177 // Note that there are 2 forms of Put, Get.
178 // With a key and a value, the *value* will be checked
179 // when a collision is detected. Otherwise, if there are
180 // 2 items with a different value but the same key,
181 // we'll retrieve the WRONG ONE. So where possible,
182 // supply the required value along with the key.
183 // In fact, the value-only versions make a key, and still store
184 // the value. The use of an explicit key might be required
185 // e.g. when combining several values into one key.
186 // When doing that, it's highly likely we'll get a collision,
187 // e.g. 1 + 2 = 3, 2 + 1 = 3.
188
189 // key and value are NOT necessarily the same
190 void Put(long key, long value, wxObject *object);
191 void Put(long key, const wxChar *value, wxObject *object);
192
193 // key and value are the same
194 void Put(long value, wxObject *object);
195 void Put(const wxChar *value, wxObject *object);
196
197 // key and value not the same
198 wxObject *Get(long key, long value) const;
199 wxObject *Get(long key, const wxChar *value) const;
200
201 // key and value are the same
202 wxObject *Get(long value) const;
203 wxObject *Get(const wxChar *value) const;
204
205 // Deletes entry and returns data if found
206 wxObject *Delete(long key);
207 wxObject *Delete(const wxChar *key);
208
209 wxObject *Delete(long key, int value);
210 wxObject *Delete(long key, const wxChar *value);
211
212 // Construct your own integer key from a string, e.g. in case
213 // you need to combine it with something
214 long MakeKey(const wxChar *string) const;
215
216 // Way of iterating through whole hash table (e.g. to delete everything)
217 // Not necessary, of course, if you're only storing pointers to
218 // objects maintained separately
219
220 void BeginFind();
221 wxNode *Next();
222
223 void DeleteContents(bool flag);
224 void Clear();
225
226 // Returns number of nodes
227 size_t GetCount() const { return m_count; }
228
229 private:
230 size_t m_count; // number of elements in the hashtable
231 bool m_deleteContents;
232
233 DECLARE_DYNAMIC_CLASS(wxHashTable)
234 };
235
236 // defines a new type safe hash table which stores the elements of type eltype
237 // in lists of class listclass
238 #define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \
239 classexp hashclass : public wxHashTableBase \
240 { \
241 public: \
242 hashclass(wxKeyType keyType = wxKEY_INTEGER, \
243 size_t size = wxHASH_SIZE_DEFAULT) \
244 { Create(keyType, size); } \
245 \
246 ~hashclass() { Destroy(); } \
247 \
248 void Put(long key, long val, eltype *data) { DoPut(key, val, data); } \
249 void Put(long key, eltype *data) { DoPut(key, key, data); } \
250 \
251 eltype *Get(long key, long value) const \
252 { \
253 wxNodeBase *node = GetNode(key, value); \
254 return node ? ((listclass::Node *)node)->GetData() : (eltype *)0; \
255 } \
256 eltype *Get(long key) const { return Get(key, key); } \
257 \
258 eltype *Delete(long key, long value) \
259 { \
260 eltype *data; \
261 \
262 wxNodeBase *node = GetNode(key, value); \
263 if ( node ) \
264 { \
265 data = ((listclass::Node *)node)->GetData(); \
266 \
267 delete node; \
268 m_count--; \
269 } \
270 else \
271 { \
272 data = (eltype *)0; \
273 } \
274 \
275 return data; \
276 } \
277 eltype *Delete(long key) { return Delete(key, key); } \
278 \
279 protected: \
280 void DoPut(long key, long value, eltype *data) \
281 { \
282 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \
283 \
284 if ( !m_hashTable[slot] ) \
285 { \
286 m_hashTable[slot] = new listclass(m_keyType); \
287 if ( m_deleteContents ) \
288 m_hashTable[slot]->DeleteContents(TRUE); \
289 } \
290 \
291 ((listclass *)m_hashTable[slot])->Append(value, data); \
292 m_count++; \
293 } \
294 }
295
296 // this macro is to be used in the user code
297 #define WX_DECLARE_HASH(el, list, hash) \
298 _WX_DECLARE_HASH(el, list, hash, class)
299
300 // and this one does exactly the same thing but should be used inside the
301 // library
302 #define WX_DECLARE_EXPORTED_HASH(el, list, hash) \
303 _WX_DECLARE_HASH(el, list, hash, class WXDLLEXPORT)
304
305 #define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \
306 _WX_DECLARE_HASH(el, list, hash, class usergoo)
307
308 #endif
309 // _WX_HASH_H__