]> git.saurik.com Git - wxWidgets.git/blame - include/wx/hash.h
Added simplistic makefile/project files for wxWinCE.
[wxWidgets.git] / include / wx / hash.h
CommitLineData
c801d85f 1/////////////////////////////////////////////////////////////////////////////
bcaa23de 2// Name: wx/hash.h
c801d85f
KB
3// Purpose: wxHashTable class
4// Author: Julian Smart
bcaa23de 5// Modified by: VZ at 25.02.00: type safe hashes with WX_DECLARE_HASH()
c801d85f
KB
6// Created: 01/02/97
7// RCS-ID: $Id$
8// Copyright: (c)
bcaa23de 9// Licence: wxWindows licence
c801d85f
KB
10/////////////////////////////////////////////////////////////////////////////
11
bcaa23de
VZ
12#ifndef _WX_HASH_H__
13#define _WX_HASH_H__
c801d85f 14
af49c4b8 15#if defined(__GNUG__) && !defined(__APPLE__)
c801d85f
KB
16#pragma interface "hash.h"
17#endif
18
c801d85f 19#include "wx/list.h"
c2bb85e9 20#include "wx/dynarray.h"
c801d85f 21
bcaa23de
VZ
22// the default size of the hash
23#define wxHASH_SIZE_DEFAULT (1000)
24
c801d85f
KB
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
bcaa23de
VZ
32// ----------------------------------------------------------------------------
33// this is the base class for object hashes: hash tables which contain
34// pointers to objects
35// ----------------------------------------------------------------------------
36
37class WXDLLEXPORT wxHashTableBase : public wxObject
c801d85f 38{
bcaa23de
VZ
39public:
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
51protected:
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
70private:
71 // no copy ctor/assignment operator (yet)
1a0d517e 72 DECLARE_NO_COPY_CLASS(wxHashTableBase)
c801d85f
KB
73};
74
c2bb85e9
VZ
75// ----------------------------------------------------------------------------
76// a hash table which stores longs
77// ----------------------------------------------------------------------------
78
79class WXDLLEXPORT wxHashTableLong : public wxObject
80{
81public:
d84afea9
GD
82 wxHashTableLong(size_t size = wxHASH_SIZE_DEFAULT)
83 { Init(size); }
a95e38c0 84 virtual ~wxHashTableLong();
c2bb85e9
VZ
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
96protected:
97 void Init(size_t size);
98
99private:
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
1a0d517e 110 DECLARE_NO_COPY_CLASS(wxHashTableLong)
c2bb85e9
VZ
111};
112
bd83cb56
VZ
113// ----------------------------------------------------------------------------
114// wxStringHashTable: a hash table which indexes strings with longs
115// ----------------------------------------------------------------------------
116
117class WXDLLEXPORT wxStringHashTable : public wxObject
118{
119public:
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
53e112a0
JS
130 // remove the item, returning TRUE if the item was found and deleted
131 bool Delete(long key) const;
132
bd83cb56
VZ
133 // clean up
134 void Destroy();
135
136private:
137 wxArrayLong **m_keys;
138 wxArrayString **m_values;
139
140 // the size of array above
141 size_t m_hashSize;
142
1a0d517e 143 DECLARE_NO_COPY_CLASS(wxStringHashTable)
bd83cb56
VZ
144};
145
bcaa23de
VZ
146// ----------------------------------------------------------------------------
147// for compatibility only
148// ----------------------------------------------------------------------------
149
150class WXDLLEXPORT wxHashTable : public wxObject
151{
152public:
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
d84afea9
GD
165 wxHashTable(const wxHashTable& table) : wxObject()
166 { DoCopy(table); }
bcaa23de
VZ
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
229private:
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
f6bcfd97
BP
238#define _WX_DECLARE_HASH(eltype, listclass, hashclass, classexp) \
239 classexp hashclass : public wxHashTableBase \
bcaa23de
VZ
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 { \
6a5391af 282 size_t slot = (size_t)abs((int)(key % (long)m_hashSize)); \
bcaa23de
VZ
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
f6bcfd97
BP
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
0b9ab0bd
RL
305#define WX_DECLARE_USER_EXPORTED_HASH(el, list, hash, usergoo) \
306 _WX_DECLARE_HASH(el, list, hash, class usergoo)
307
c801d85f 308#endif
bcaa23de 309 // _WX_HASH_H__