1 /********************************************************************************
2 * *
3 * D i c t i o n a r y C l a s s *
4 * *
5 *********************************************************************************
6 * Copyright (C) 1998,2005 by Jeroen van der Zijp. All Rights Reserved. *
7 *********************************************************************************
8 * This library is free software; you can redistribute it and/or *
9 * modify it under the terms of the GNU Lesser General Public *
10 * License as published by the Free Software Foundation; either *
11 * version 2.1 of the License, or (at your option) any later version. *
12 * *
13 * This library is distributed in the hope that it will be useful, *
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of *
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU *
16 * Lesser General Public License for more details. *
17 * *
18 * You should have received a copy of the GNU Lesser General Public *
19 * License along with this library; if not, write to the Free Software *
20 * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA. *
21 *********************************************************************************
22 * $Id: FXDict.cpp,v 1.28 2005/01/16 16:06:06 fox Exp $ *
23 ********************************************************************************/
24 #include "xincs.h"
25 #include "fxver.h"
26 #include "fxdefs.h"
27 #include "FXHash.h"
28 #include "FXStream.h"
29 #include "FXDict.h"
30
31
32 /*
33 Notes:
34 - The hash algorithm should yield a number in the range [0...FXDict::EMPTY)
35 We need FXDict::EMPTY and FXDict::UNUSED for flag purposes.
36 - Since the algorithm doubles the table size when exceeding MAX_LOAD,
37 it would be prudent to keep MIN_LOAD less than .5*MAX_LOAD;
38 otherwise, the algorithm might hip-hop between halving and doubling,
39 which would be quite expensive!!
40 - Not many people seem to know that hash tables don't have to be prime
41 numbers; in fact, a table size of 2**n and odd probe distance are very
42 easy to arrange, and this works just as well!
43 - We store the hash key, so that 99.999% of the time we can compare hash numbers;
44 only when hash numbers match do we need to compare keys.
45 Thus, with a good hash function, the number of calls to strcmp() should be
46 roughly the same as the number of successful lookups.
47 - The hash table should NEVER get full, or stuff will loop forever!!
48 */
49
50
51 #define DEF_HASH_SIZE 4 // Initial table size (MUST be power of 2)
52 #define MAX_LOAD 80 // Maximum hash table load factor (%)
53 #define MIN_LOAD 10 // Minimum hash table load factor (%)
54 #define HASH1(x,n) (((unsigned int)(x))%(n)) // Probe Position [0..n-1]
55 #define HASH2(x,n) (1|(((unsigned int)(x)*17)%((n)-1))) // Probe Distance [1..n-2]
56
57 using namespace FX;
58
59 /*******************************************************************************/
60
61 namespace FX {
62
63
64 // Hash function for string
strhash(const FXchar * str)65 static inline FXint strhash(const FXchar* str){
66 register const FXuchar *s=(const FXuchar*)str;
67 register FXint h=0;
68 register FXint c;
69 while((c=*s++)!='\0'){
70 h = ((h << 5) + h) ^ c;
71 }
72 return h&0x7fffffff;
73 }
74
75
76 // Object implementation
77 FXIMPLEMENT(FXDict,FXObject,NULL,0)
78
79
80 // Construct empty dictionary
FXDict()81 FXDict::FXDict(){
82 FXCALLOC(&dict,FXDictEntry,DEF_HASH_SIZE);
83 for(FXuint i=0; i<DEF_HASH_SIZE; i++) dict[i].hash=-1;
84 total=DEF_HASH_SIZE;
85 number=0;
86 }
87
88
89 // Defaul implementation
createData(const void * ptr)90 void *FXDict::createData(const void* ptr){ return (void*)ptr; }
91
92
93 // Defaul implementation
deleteData(void *)94 void FXDict::deleteData(void*){ }
95
96
97 // Resize table
size(FXint m)98 void FXDict::size(FXint m){
99 register FXint i,n,p,x,h;
100 FXDictEntry *k;
101 FXASSERT(number<=total);
102 if(m<DEF_HASH_SIZE) m=DEF_HASH_SIZE;
103 n=total;
104 while((n>>2)>m) n>>=1; // Shrink until n/4 <= m
105 while((n>>1)<m) n<<=1; // Grow until m <= n/2
106 FXASSERT(m<=(n>>1));
107 FXASSERT(DEF_HASH_SIZE<=n);
108 if(n!=total){
109 FXTRACE((200,"FXDict::size: %p: resizing from %d to %d\n",this,total,n));
110 FXASSERT(m<=n);
111 FXCALLOC(&k,FXDictEntry,n);
112 for(i=0; i<n; i++) k[i].hash=-1;
113 for(i=0; i<total; i++){
114 h=dict[i].hash;
115 if(0<=h){
116 p=HASH1(h,n);
117 FXASSERT(0<=p && p<n);
118 x=HASH2(h,n);
119 FXASSERT(1<=x && x<n);
120 while(k[p].hash!=-1) p=(p+x)%n;
121 FXASSERT(k[p].hash<0);
122 k[p]=dict[i];
123 }
124 }
125 FXFREE(&dict);
126 dict=k;
127 total=n;
128 }
129 }
130
131
132 // Insert a new entry, leave it alone if already existing
insert(const FXchar * ky,const void * pdata,FXbool mrk)133 void* FXDict::insert(const FXchar* ky,const void* pdata,FXbool mrk){
134 register FXint p,i,x,h,n;
135 register void *ptr;
136 if(!ky){ fxerror("FXDict::insert: NULL key argument.\n"); }
137 FXASSERT(number<total);
138 h=strhash(ky);
139 FXASSERT(0<=h);
140 p=HASH1(h,total);
141 FXASSERT(0<=p && p<total);
142 x=HASH2(h,total);
143 FXASSERT(1<=x && x<total);
144 i=-1;
145 n=total;
146 while(n && dict[p].hash!=-1){
147 if((i==-1)&&(dict[p].hash==-2)) i=p;
148 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
149 return dict[p].data;
150 }
151 p=(p+x)%total;
152 n--;
153 }
154 if(i==-1) i=p;
155 FXTRACE((200,"FXDict::insert: %p: inserting: \"%s\"\n",this,ky));
156 FXASSERT(0<=i && i<total);
157 FXASSERT(dict[i].hash<0);
158 ptr=createData(pdata);
159 dict[i].hash=h;
160 dict[i].mark=mrk;
161 dict[i].key=strdup(ky);
162 dict[i].data=ptr;
163 number++;
164 if((100*number)>=(MAX_LOAD*total)) size(number);
165 FXASSERT(number<total);
166 return ptr;
167 }
168
169
170 // Add or replace entry
replace(const FXchar * ky,const void * pdata,FXbool mrk)171 void* FXDict::replace(const FXchar* ky,const void* pdata,FXbool mrk){
172 register FXint p,i,x,h,n;
173 register void *ptr;
174 if(!ky){ fxerror("FXDict::replace: NULL key argument.\n"); }
175 FXASSERT(number<total);
176 h=strhash(ky);
177 FXASSERT(0<=h);
178 p=HASH1(h,total);
179 FXASSERT(0<=p && p<total);
180 x=HASH2(h,total);
181 FXASSERT(1<=x && x<total);
182 i=-1;
183 n=total;
184 while(n && dict[p].hash!=-1){
185 if((i==-1)&&(dict[p].hash==-2)) i=p;
186 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
187 if(dict[p].mark<=mrk){
188 FXTRACE((200,"FXDict::replace: %p: replacing: \"%s\"\n",this,ky));
189 deleteData(dict[p].data);
190 dict[p].mark=mrk;
191 dict[p].data=createData(pdata);
192 }
193 return dict[p].data;
194 }
195 p=(p+x)%total;
196 n--;
197 }
198 if(i==-1) i=p;
199 FXTRACE((200,"FXDict::replace: %p: inserting: \"%s\"\n",this,ky));
200 FXASSERT(0<=i && i<total);
201 FXASSERT(dict[i].hash<0);
202 ptr=createData(pdata);
203 dict[i].hash=h;
204 dict[i].mark=mrk;
205 dict[i].key=strdup(ky);
206 dict[i].data=ptr;
207 number++;
208 if((100*number)>=(MAX_LOAD*total)) size(number);
209 FXASSERT(number<total);
210 return ptr;
211 }
212
213
214 // Remove entry
remove(const FXchar * ky)215 void* FXDict::remove(const FXchar* ky){
216 register FXint p,x,h,n;
217 if(!ky){ fxerror("FXDict::remove: NULL key argument.\n"); }
218 if(0<number){
219 h=strhash(ky);
220 FXASSERT(0<=h);
221 p=HASH1(h,total);
222 FXASSERT(0<=p && p<total);
223 x=HASH2(h,total);
224 FXASSERT(1<=x && x<total);
225 FXASSERT(number<total);
226 n=total;
227 while(n && dict[p].hash!=-1){
228 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
229 FXTRACE((120,"FXDict::remove: %p removing: \"%s\"\n",this,ky));
230 dict[p].hash=-2;
231 dict[p].mark=FALSE;
232 free(dict[p].key);
233 deleteData(dict[p].data);
234 dict[p].key=NULL;
235 dict[p].data=NULL;
236 number--;
237 if((100*number)<=(MIN_LOAD*total)) size(number);
238 FXASSERT(number<total);
239 return NULL;
240 }
241 p=(p+x)%total;
242 n--;
243 }
244 }
245 return NULL;
246 }
247
248
249 // Find entry
find(const FXchar * ky) const250 void* FXDict::find(const FXchar* ky) const {
251 register FXint p,x,h,n;
252 if(!ky){ fxerror("FXDict::find: NULL key argument.\n"); }
253 if(0<number){
254 h=strhash(ky);
255 FXASSERT(0<=h);
256 p=HASH1(h,total);
257 FXASSERT(0<=p && p<total);
258 x=HASH2(h,total);
259 FXASSERT(1<=x && x<total);
260 FXASSERT(number<total);
261 n=total;
262 while(n && dict[p].hash!=-1){
263 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
264 return dict[p].data;
265 }
266 p=(p+x)%total;
267 n--;
268 }
269 }
270 return NULL;
271 }
272
273
274 // Get first non-empty entry
first() const275 FXint FXDict::first() const {
276 register FXint pos=0;
277 while(pos<total){ if(0<=dict[pos].hash) break; pos++; }
278 FXASSERT(total<=pos || 0<=dict[pos].hash);
279 return pos;
280 }
281
282
283 // Get last non-empty entry
last() const284 FXint FXDict::last() const {
285 register FXint pos=total-1;
286 while(0<=pos){ if(0<=dict[pos].hash) break; pos--; }
287 FXASSERT(pos<0 || 0<=dict[pos].hash);
288 return pos;
289 }
290
291
292 // Find next entry
next(FXint pos) const293 FXint FXDict::next(FXint pos) const {
294 FXASSERT(0<=pos && pos<total);
295 while(++pos <= total-1){ if(0<=dict[pos].hash) break; }
296 FXASSERT(total<=pos || 0<=dict[pos].hash);
297 return pos;
298 }
299
300
301 // Find previous entry
prev(FXint pos) const302 FXint FXDict::prev(FXint pos) const {
303 FXASSERT(0<=pos && pos<total);
304 while(--pos >= 0){ if(0<=dict[pos].hash) break; }
305 FXASSERT(pos<0 || 0<=dict[pos].hash);
306 return pos;
307 }
308
309
310 // Remove all
clear()311 void FXDict::clear(){
312 register FXint i;
313 for(i=0; i<total; i++){
314 if(dict[i].hash>=0){
315 dict[i].hash=-1;
316 free(dict[i].key);
317 deleteData(dict[i].data);
318 }
319 }
320 number=0;
321 }
322
323
324 // Destroy table
~FXDict()325 FXDict::~FXDict(){
326 clear();
327 FXFREE(&dict);
328 dict=(FXDictEntry*)-1L;
329 }
330
331 }
332
333