1 /********************************************************************************
2 * *
3 * D i c t i o n a r y C l a s s *
4 * *
5 *********************************************************************************
6 * Copyright (C) 1998,2006 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 4937 2019-03-10 19:59:30Z arthurcnorman $ *
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
hash(const FXchar * str)65 FXint FXDict::hash(const FXchar* str){
66 const FXuchar *s=(const FXuchar*)str;
67 FXint h=0;
68 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 FXint i;
83 FXMALLOC(&dict,FXDictEntry,DEF_HASH_SIZE);
84 for(i=0; i<DEF_HASH_SIZE; i++){
85 dict[i].key=NULL;
86 dict[i].data=NULL;
87 dict[i].hash=-1;
88 dict[i].mark=false;
89 }
90 total=DEF_HASH_SIZE;
91 number=0;
92 }
93
94
95 // Copy constructor
FXDict(const FXDict & orig)96 FXDict::FXDict(const FXDict& orig):FXObject(orig){
97 FXint i;
98 FXMALLOC(&dict,FXDictEntry,orig.total);
99 for(i=0; i<orig.total; i++){
100 if(0<=orig.dict[i].hash){
101 dict[i].key=strdup(orig.dict[i].key);
102 dict[i].data=orig.dict[i].data;
103 dict[i].hash=orig.dict[i].hash;
104 dict[i].mark=orig.dict[i].mark;
105 continue;
106 }
107 dict[i].key=NULL;
108 dict[i].data=NULL;
109 dict[i].hash=-1;
110 dict[i].mark=false;
111 }
112 total=orig.total;
113 number=orig.number;
114 }
115
116
117 // Assignment operator
operator =(const FXDict & orig)118 FXDict& FXDict::operator=(const FXDict& orig){
119 FXint i;
120 if(&orig!=this){
121 clear();
122 FXRESIZE(&dict,FXDictEntry,orig.total);
123 for(i=0; i<orig.total; i++){
124 if(0<=orig.dict[i].hash){
125 dict[i].key=strdup(orig.dict[i].key);
126 dict[i].data=orig.dict[i].data;
127 dict[i].hash=orig.dict[i].hash;
128 dict[i].mark=orig.dict[i].mark;
129 continue;
130 }
131 dict[i].key=NULL;
132 dict[i].data=NULL;
133 dict[i].hash=-1;
134 dict[i].mark=false;
135 }
136 total=orig.total;
137 number=orig.number;
138 }
139 return *this;
140 }
141
142
143 // Defaul implementation
createData(const void * ptr)144 void *FXDict::createData(const void* ptr){ return (void*)ptr; }
145
146
147 // Defaul implementation
deleteData(void *)148 void FXDict::deleteData(void*){ }
149
150
151 // Resize table
size(FXint m)152 void FXDict::size(FXint m){
153 FXint i,n,p,x,h;
154 FXDictEntry *k;
155 FXASSERT(number<=total);
156 if(m<DEF_HASH_SIZE) m=DEF_HASH_SIZE;
157 n=total;
158 while((n>>2)>m) n>>=1; // Shrink until n/4 <= m
159 while((n>>1)<m) n<<=1; // Grow until m <= n/2
160 FXASSERT(m<=(n>>1));
161 FXASSERT(DEF_HASH_SIZE<=n);
162 if(n!=total){
163 FXTRACE((200,"FXDict::size: %p: resizing from %d to %d\n",this,total,n));
164 FXASSERT(m<=n);
165 FXCALLOC(&k,FXDictEntry,n);
166 for(i=0; i<n; i++) k[i].hash=-1;
167 for(i=0; i<total; i++){
168 h=dict[i].hash;
169 if(0<=h){
170 p=HASH1(h,n);
171 FXASSERT(0<=p && p<n);
172 x=HASH2(h,n);
173 FXASSERT(1<=x && x<n);
174 while(k[p].hash!=-1) p=(p+x)%n;
175 FXASSERT(k[p].hash<0);
176 k[p]=dict[i];
177 }
178 }
179 FXFREE(&dict);
180 dict=k;
181 total=n;
182 }
183 }
184
185
186 // Insert a new entry, leave it alone if already existing
insert(const FXchar * ky,const void * pdata,bool mrk)187 void* FXDict::insert(const FXchar* ky,const void* pdata,bool mrk){
188 FXint p,i,x,h,n;
189 void *ptr;
190 if(!ky){ fxerror("FXDict::insert: NULL key argument.\n"); }
191 FXASSERT(number<total);
192 h=hash(ky);
193 FXASSERT(0<=h);
194 p=HASH1(h,total);
195 FXASSERT(0<=p && p<total);
196 x=HASH2(h,total);
197 FXASSERT(1<=x && x<total);
198 i=-1;
199 n=total;
200 while(n && dict[p].hash!=-1){
201 if((i==-1)&&(dict[p].hash==-2)) i=p;
202 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
203 return dict[p].data;
204 }
205 p=(p+x)%total;
206 n--;
207 }
208 if(i==-1) i=p;
209 FXTRACE((200,"FXDict::insert: %p: inserting: \"%s\"\n",this,ky));
210 FXASSERT(0<=i && i<total);
211 FXASSERT(dict[i].hash<0);
212 ptr=createData(pdata);
213 dict[i].hash=h;
214 dict[i].mark=mrk;
215 dict[i].key=strdup(ky);
216 dict[i].data=ptr;
217 number++;
218 if((100*number)>=(MAX_LOAD*total)) size(number);
219 FXASSERT(number<total);
220 return ptr;
221 }
222
223
224 // Add or replace entry
replace(const FXchar * ky,const void * pdata,bool mrk)225 void* FXDict::replace(const FXchar* ky,const void* pdata,bool mrk){
226 FXint p,i,x,h,n;
227 void *ptr;
228 if(!ky){ fxerror("FXDict::replace: NULL key argument.\n"); }
229 FXASSERT(number<total);
230 h=hash(ky);
231 FXASSERT(0<=h);
232 p=HASH1(h,total);
233 FXASSERT(0<=p && p<total);
234 x=HASH2(h,total);
235 FXASSERT(1<=x && x<total);
236 i=-1;
237 n=total;
238 while(n && dict[p].hash!=-1){
239 if((i==-1)&&(dict[p].hash==-2)) i=p;
240 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
241 if(dict[p].mark<=mrk){
242 FXTRACE((200,"FXDict::replace: %p: replacing: \"%s\"\n",this,ky));
243 deleteData(dict[p].data);
244 dict[p].mark=mrk;
245 dict[p].data=createData(pdata);
246 }
247 return dict[p].data;
248 }
249 p=(p+x)%total;
250 n--;
251 }
252 if(i==-1) i=p;
253 FXTRACE((200,"FXDict::replace: %p: inserting: \"%s\"\n",this,ky));
254 FXASSERT(0<=i && i<total);
255 FXASSERT(dict[i].hash<0);
256 ptr=createData(pdata);
257 dict[i].hash=h;
258 dict[i].mark=mrk;
259 dict[i].key=strdup(ky);
260 dict[i].data=ptr;
261 number++;
262 if((100*number)>=(MAX_LOAD*total)) size(number);
263 FXASSERT(number<total);
264 return ptr;
265 }
266
267
268 // Remove entry
remove(const FXchar * ky)269 void* FXDict::remove(const FXchar* ky){
270 FXint p,x,h,n;
271 if(!ky){ fxerror("FXDict::remove: NULL key argument.\n"); }
272 if(0<number){
273 h=hash(ky);
274 FXASSERT(0<=h);
275 p=HASH1(h,total);
276 FXASSERT(0<=p && p<total);
277 x=HASH2(h,total);
278 FXASSERT(1<=x && x<total);
279 FXASSERT(number<total);
280 n=total;
281 while(n && dict[p].hash!=-1){
282 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
283 FXTRACE((120,"FXDict::remove: %p removing: \"%s\"\n",this,ky));
284 dict[p].hash=-2;
285 dict[p].mark=false;
286 free(dict[p].key);
287 deleteData(dict[p].data);
288 dict[p].key=NULL;
289 dict[p].data=NULL;
290 number--;
291 if((100*number)<=(MIN_LOAD*total)) size(number);
292 FXASSERT(number<total);
293 return NULL;
294 }
295 p=(p+x)%total;
296 n--;
297 }
298 }
299 return NULL;
300 }
301
302
303 // Find entry
find(const FXchar * ky) const304 void* FXDict::find(const FXchar* ky) const {
305 FXint p,x,h,n;
306 if(!ky){ fxerror("FXDict::find: NULL key argument.\n"); }
307 if(0<number){
308 h=hash(ky);
309 FXASSERT(0<=h);
310 p=HASH1(h,total);
311 FXASSERT(0<=p && p<total);
312 x=HASH2(h,total);
313 FXASSERT(1<=x && x<total);
314 FXASSERT(number<total);
315 n=total;
316 while(n && dict[p].hash!=-1){
317 if(dict[p].hash==h && strcmp(dict[p].key,ky)==0){
318 return dict[p].data;
319 }
320 p=(p+x)%total;
321 n--;
322 }
323 }
324 return NULL;
325 }
326
327
328 // Get first non-empty entry
first() const329 FXint FXDict::first() const {
330 FXint pos=0;
331 while(pos<total){ if(0<=dict[pos].hash) break; pos++; }
332 FXASSERT(total<=pos || 0<=dict[pos].hash);
333 return pos;
334 }
335
336
337 // Get last non-empty entry
last() const338 FXint FXDict::last() const {
339 FXint pos=total-1;
340 while(0<=pos){ if(0<=dict[pos].hash) break; pos--; }
341 FXASSERT(pos<0 || 0<=dict[pos].hash);
342 return pos;
343 }
344
345
346 // Find next entry
next(FXint pos) const347 FXint FXDict::next(FXint pos) const {
348 FXASSERT(0<=pos && pos<total);
349 while(++pos <= total-1){ if(0<=dict[pos].hash) break; }
350 FXASSERT(total<=pos || 0<=dict[pos].hash);
351 return pos;
352 }
353
354
355 // Find previous entry
prev(FXint pos) const356 FXint FXDict::prev(FXint pos) const {
357 FXASSERT(0<=pos && pos<total);
358 while(--pos >= 0){ if(0<=dict[pos].hash) break; }
359 FXASSERT(pos<0 || 0<=dict[pos].hash);
360 return pos;
361 }
362
363
364 // Remove all
clear()365 void FXDict::clear(){
366 FXint i;
367 for(i=0; i<total; i++){
368 if(dict[i].hash>=0){
369 dict[i].hash=-1;
370 free(dict[i].key);
371 deleteData(dict[i].data);
372 }
373 }
374 number=0;
375 }
376
377
378 // Destroy table
~FXDict()379 FXDict::~FXDict(){
380 clear();
381 FXFREE(&dict);
382 dict=(FXDictEntry*)-1L;
383 }
384
385 }
386
387