ViewVC Help
View File | Revision Log | Show Annotations | View Changeset | Root Listing
root/gclib/gclib/GHash.hh
Revision: 2
Committed: Mon Mar 22 22:03:27 2010 UTC (9 years, 7 months ago) by gpertea
File size: 16896 byte(s)
Log Message:
added my gclib source files

Line File contents
1 /********************************************************************************
2 * Hash table class template (char* based) *
3 *********************************************************************************/
4
5 #ifndef GHash_HH
6 #define GHash_HH
7 #include "GBase.h"
8 /**
9 * This class maintains a fast-access hash table of entities
10 * indexed by a character string.
11 * It is typically used to map strings to pointers; however, overloading
12 * the createData() and deleteData() members allows any type of data to
13 * be indexed by strings.
14 */
15 typedef struct {
16 char* key; // Key string
17 bool keyalloc; //shared key flag (to not free the key chars)
18 int hash; // Hash value of key
19 pointer data; // Data
20 bool mark; // Entry is marked
21 } GHashEntry;
22
23 template <class OBJ> class GHash {
24 protected:
25 GHashEntry* hash; // Hash
26 int fCapacity; // table size
27 int fCount; // number of valid entries
28 int fCurrentEntry;
29 char* lastkeyptr; //pointer to last key string added
30 //---------- Raw data retrieval (including empty entries
31 // Return key at position pos.
32 const char* Key(uint pos) const { return hash[pos].key; }
33 // return data OBJ* at given position
34 OBJ* Data(uint pos) const { return (OBJ*) hash[pos].data; }
35 // Return mark flag of entry at position pos.
36 bool Mark(uint pos) const { return hash[pos].mark; }
37 // Return position of first filled slot, or >= fCapacity
38 int First() const;
39 // Return position of last filled slot or -1
40 int Last() const;
41 // Return position of next filled slot in hash table
42 // or a value greater than or equal to fCapacity if no filled
43 // slot was found
44 int Next(int pos) const;
45 //Return position of previous filled slot in hash table
46 //or a -1 if no filled slot was found
47 int Prev(int pos) const;
48
49 private:
50 GHash(const GHash&);
51 GHash &operator=(const GHash&);
52 GFreeProc* fFreeProc; //procedure to free item data
53 protected:
54 public:
55 static void DefaultFreeProc(pointer item) {
56 delete (OBJ*)item;
57 item=NULL;
58 }
59 public:
60 GHash(GFreeProc* freeProc); // constructs of an empty hash
61 GHash(bool doFree=true); // constructs of an empty hash (free the item objects)
62 void setFreeItem(GFreeProc *freeProc) { fFreeProc=freeProc; }
63 void setFreeItem(bool doFree) { fFreeProc=(doFree)? &DefaultFreeProc : NULL; }
64 int Capacity() const { return fCapacity; } // table's size, including the empty slots.
65 void Resize(int m); // Resize the table to the given size.
66 int Count() const { return fCount; }// the total number of entries in the table.
67 // Insert a new entry into the table given key and mark.
68 // If there is already an entry with that key, leave it unchanged,
69 const OBJ* Add(const char* ky, const OBJ* ptr=NULL, bool mrk=false);
70 //same as Add, but the key pointer is stored directly, no string duplicate
71 //is made (shared-key-Add)
72 const OBJ* shkAdd(const char* ky, const OBJ* ptr, bool mrk=false);
73
74 // Replace data at key, if the entry's mark is less than
75 // or equal to the given mark. If there was no existing entry,
76 // a new entry is inserted with the given mark.
77 OBJ* Replace(const char* ky, const OBJ* ptr, bool mrk=false);
78 // Remove a given key and its data
79 OBJ* Remove(const char* ky);
80 // Find data OBJ* given key.
81 OBJ* Find(const char* ky, char** keyptr=NULL);
82 bool hasKey(const char* ky);
83 char* getLastKey() { return lastkeyptr; }
84 OBJ* operator[](const char* ky) { return Find(ky); }
85 void startIterate(); //iterator-like initialization
86 char* NextKey(); //returns next valid key in the table (NULL if no more)
87 OBJ* NextData(); //returns next valid hash[].data
88 OBJ* NextData(char*& nextkey); //returns next valid hash[].data
89 //or NULL if no more
90 //nextkey is SET to the corresponding key
91 GHashEntry* NextEntry(); //returns a pointer to a GHashEntry
92
93 /// Clear all entries
94 void Clear();
95
96 /// Destructor
97 virtual ~GHash();
98 };
99 //
100 //======================== method definitions ========================
101 //
102 /*
103 Notes:
104 - The hash algorithm should yield a fCount in the range [0...GHash::EMPTY)
105 GHash::EMPTY and GHash::UNUSED are needed for flag purposes.
106 - Since the algorithm doubles the table size when exceeding MAX_LOAD,
107 it would be prudent to keep MIN_LOAD less than 1/2 MAX_LOAD;
108 otherwise, the algorithm might hip-hop between halving and doubling,
109 which would be quite expensive!!
110 - Not many people seem to know that hash tables don't have to be prime
111 numbers; in fact, a table size of 2**n and odd probe distance are very
112 easy to arrange, and this works just as well!
113 - We store the hash key, so that 99.999% of the time we can compare hash numbers;
114 only when hash numbers match do we need to compare keys.
115 Thus, with a good hash function, the fCount of calls to strcmp() should be
116 roughly the same as the fCount of successful lookups.
117 - The hash table should NEVER get full, or stuff will loop forever!!
118 */
119
120 // Initial table size (MUST be power of 2)
121 #define DEF_HASH_SIZE 32
122 // Maximum hash table load factor (%)
123 #define MAX_LOAD 80
124 // Minimum hash table load factor (%)
125 #define MIN_LOAD 10
126 // Probe Position [0..n-1]
127 #define HASH1(x,n) (((unsigned int)(x)*13)%(n))
128 // Probe Distance [1..n-1]
129 #define HASH2(x,n) (1|(((unsigned int)(x)*17)%((n)-1)))
130
131 #define FREEDATA (fFreeProc!=NULL)
132
133 /*******************************************************************************/
134 // Construct empty hash
135 template <class OBJ> GHash<OBJ>::GHash(GFreeProc* freeProc) {
136 GMALLOC(hash, sizeof(GHashEntry)*DEF_HASH_SIZE);
137 fFreeProc=freeProc;
138 for (uint i=0; i<DEF_HASH_SIZE; i++)
139 hash[i].hash=-1; //this will be an indicator for 'empty' entries
140 fCapacity=DEF_HASH_SIZE;
141 fCount=0;
142 }
143
144 template <class OBJ> GHash<OBJ>::GHash(bool doFree) {
145 GMALLOC(hash, sizeof(GHashEntry)*DEF_HASH_SIZE);
146 fFreeProc = (doFree)?&DefaultFreeProc : NULL;
147 for (uint i=0; i<DEF_HASH_SIZE; i++)
148 hash[i].hash=-1; //this will be an indicator for 'empty' entries
149 fCapacity=DEF_HASH_SIZE;
150 fCount=0;
151 }
152
153
154 // Resize table
155 template <class OBJ> void GHash<OBJ>::Resize(int m){
156 register int i,n,p,x,h;
157 GHashEntry *k;
158 GASSERT(fCount<=fCapacity);
159 if(m<DEF_HASH_SIZE) m=DEF_HASH_SIZE;
160 n=fCapacity;
161 while((n>>2)>m) n>>=1; // Shrink until n/4 <= m
162 while((n>>1)<m) n<<=1; // Grow until m <= n/2
163 GASSERT(m<=(n>>1));
164 GASSERT(DEF_HASH_SIZE<=n);
165 if(n!=fCapacity){
166 GASSERT(m<=n);
167 GMALLOC(k, sizeof(GHashEntry)*n);
168 for(i=0; i<n; i++) k[i].hash=-1;
169 for(i=0; i<fCapacity; i++){
170 h=hash[i].hash;
171 if(0<=h){
172 p=HASH1(h,n);
173 GASSERT(0<=p && p<n);
174 x=HASH2(h,n);
175 GASSERT(1<=x && x<n);
176 while(k[p].hash!=-1) p=(p+x)%n;
177 GASSERT(k[p].hash<0);
178 k[p]=hash[i];
179 }
180 }
181 GFREE(hash);
182 hash=k;
183 fCapacity=n;
184 }
185 }
186
187 // add a new entry, leave it alone if already existing
188 template <class OBJ> const OBJ* GHash<OBJ>::Add(const char* ky,
189 const OBJ* pdata,bool mrk){
190 register int p,i,x,h,n;
191 if(!ky) GError("GHash::insert: NULL key argument.\n");
192 GASSERT(fCount<fCapacity);
193 h=strhash(ky);
194 GASSERT(0<=h);
195 p=HASH1(h,fCapacity);
196 GASSERT(0<=p && p<fCapacity);
197 x=HASH2(h,fCapacity);
198 GASSERT(1<=x && x<fCapacity);
199 i=-1;
200 n=fCapacity;
201 while(n && hash[p].hash!=-1){
202 if ((i==-1)&&(hash[p].hash==-2)) i=p;
203 if (hash[p].hash==h && strcmp(hash[p].key,ky)==0) {
204 //replace hash data for this key!
205 lastkeyptr=hash[p].key;
206 hash[p].data = (void*) pdata;
207 return (OBJ*)hash[p].data;
208 }
209 p=(p+x)%fCapacity;
210 n--;
211 }
212 if(i==-1) i=p;
213 GTRACE(("GHash::insert: key=\"%s\"\n",ky));
214 //GMessage("GHash::insert: key=\"%s\"\n",ky);
215 GASSERT(0<=i && i<fCapacity);
216 GASSERT(hash[i].hash<0);
217 hash[i].hash=h;
218 hash[i].mark=mrk;
219 hash[i].key=Gstrdup(ky);
220 hash[i].keyalloc=true;
221 lastkeyptr=hash[i].key;
222 hash[i].data= (void*) pdata;
223 fCount++;
224 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
225 GASSERT(fCount<fCapacity);
226 return pdata;
227 }
228
229 template <class OBJ> const OBJ* GHash<OBJ>::shkAdd(const char* ky,
230 const OBJ* pdata,bool mrk){
231 register int p,i,x,h,n;
232 if(!ky) GError("GHash::insert: NULL key argument.\n");
233 GASSERT(fCount<fCapacity);
234 h=strhash(ky);
235 GASSERT(0<=h);
236 p=HASH1(h,fCapacity);
237 GASSERT(0<=p && p<fCapacity);
238 x=HASH2(h,fCapacity);
239 GASSERT(1<=x && x<fCapacity);
240 i=-1;
241 n=fCapacity;
242 while(n && hash[p].hash!=-1){
243 if((i==-1)&&(hash[p].hash==-2)) i=p;
244 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
245 //replace hash data for this key!
246 lastkeyptr=hash[p].key;
247 hash[p].data = (void*) pdata;
248 return (OBJ*)hash[p].data;
249 }
250 p=(p+x)%fCapacity;
251 n--;
252 }
253 if(i==-1) i=p;
254 GTRACE(("GHash::insert: key=\"%s\"\n",ky));
255 //GMessage("GHash::insert: key=\"%s\"\n",ky);
256 GASSERT(0<=i && i<fCapacity);
257 GASSERT(hash[i].hash<0);
258 hash[i].hash=h;
259 hash[i].mark=mrk;
260 hash[i].key=(char *)ky;
261 lastkeyptr=hash[i].key;
262 hash[i].keyalloc=false;
263 hash[i].data= (void*) pdata;
264 fCount++;
265 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
266 GASSERT(fCount<fCapacity);
267 return pdata;
268 }
269
270
271 // Add or replace entry
272 template <class OBJ> OBJ* GHash<OBJ>::Replace(const char* ky,const OBJ* pdata, bool mrk){
273 register int p,i,x,h,n;
274 if(!ky){ GError("GHash::replace: NULL key argument.\n"); }
275 GASSERT(fCount<fCapacity);
276 h=strhash(ky);
277 GASSERT(0<=h);
278 p=HASH1(h,fCapacity);
279 GASSERT(0<=p && p<fCapacity);
280 x=HASH2(h,fCapacity);
281 GASSERT(1<=x && x<fCapacity);
282 i=-1;
283 n=fCapacity;
284 while(n && hash[p].hash!=-1){
285 if((i==-1)&&(hash[p].hash==-2)) i=p;
286 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
287 if(hash[p].mark<=mrk){
288 GTRACE(("GHash::replace: %08x: replacing: \"%s\"\n",this,ky));
289 if (FREEDATA) (*fFreeProc)(hash[p].data);
290 hash[p].mark=mrk;
291 hash[p].data=pdata;
292 }
293 return hash[p].data;
294 }
295 p=(p+x)%fCapacity;
296 n--;
297 }
298 if(i==-1) i=p;
299 GTRACE(("GHash::replace: %08x: inserting: \"%s\"\n",this,ky));
300 GASSERT(0<=i && i<fCapacity);
301 GASSERT(hash[i].hash<0);
302 hash[i].hash=h;
303 hash[i].mark=mrk;
304 hash[i].key=Gstrdup(ky);
305 hash[i].data=pdata;
306 fCount++;
307 if((100*fCount)>=(MAX_LOAD*fCapacity)) Resize(fCount);
308 GASSERT(fCount<fCapacity);
309 return pdata;
310 }
311
312
313 // Remove entry
314 template <class OBJ> OBJ* GHash<OBJ>::Remove(const char* ky){
315 register int p,x,h,n;
316 if(!ky){ GError("GHash::remove: NULL key argument.\n"); }
317 if(0<fCount){
318 h=strhash(ky);
319 GASSERT(0<=h);
320 p=HASH1(h,fCapacity);
321 GASSERT(0<=p && p<fCapacity);
322 x=HASH2(h,fCapacity);
323 GASSERT(1<=x && x<fCapacity);
324 GASSERT(fCount<fCapacity);
325 n=fCapacity;
326 while(n && hash[p].hash!=-1){
327 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
328 GTRACE(("GHash::remove: %08x removing: \"%s\"\n",this,ky));
329 hash[p].hash=-2;
330 hash[p].mark=false;
331 if (hash[p].keyalloc) GFREE((hash[p].key));
332 if (FREEDATA) (*fFreeProc)(hash[p].data);
333 hash[p].key=NULL;
334 hash[p].data=NULL;
335 fCount--;
336 if((100*fCount)<=(MIN_LOAD*fCapacity)) Resize(fCount);
337 GASSERT(fCount<fCapacity);
338 return NULL;
339 }
340 p=(p+x)%fCapacity;
341 n--;
342 }
343 }
344 return NULL;
345 }
346
347
348 // Find entry
349 template <class OBJ> bool GHash<OBJ>::hasKey(const char* ky) {
350 register int p,x,h,n;
351 if(!ky){ GError("GHash::find: NULL key argument.\n"); }
352 if(0<fCount){
353 h=strhash(ky);
354 GASSERT(0<=h);
355 p=HASH1(h,fCapacity);
356 GASSERT(0<=p && p<fCapacity);
357 x=HASH2(h,fCapacity);
358 GASSERT(1<=x && x<fCapacity);
359 GASSERT(fCount<fCapacity);
360 n=fCapacity;
361 while(n && hash[p].hash!=-1){
362 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
363 return true;
364 }
365 p=(p+x)%fCapacity;
366 n--;
367 }
368 }
369 return false;
370 }
371
372 template <class OBJ> OBJ* GHash<OBJ>::Find(const char* ky, char** keyptr){
373 register int p,x,h,n;
374 if(!ky){ GError("GHash::find: NULL key argument.\n"); }
375 if(0<fCount){
376 h=strhash(ky);
377 GASSERT(0<=h);
378 p=HASH1(h,fCapacity);
379 GASSERT(0<=p && p<fCapacity);
380 x=HASH2(h,fCapacity);
381 GASSERT(1<=x && x<fCapacity);
382 GASSERT(fCount<fCapacity);
383 n=fCapacity;
384 while(n && hash[p].hash!=-1){
385 if(hash[p].hash==h && strcmp(hash[p].key,ky)==0){
386 if (keyptr!=NULL) *keyptr = hash[p].key;
387 return (OBJ*)hash[p].data;
388 }
389 p=(p+x)%fCapacity;
390 n--;
391 }
392 }
393 return NULL;
394 }
395
396
397 template <class OBJ> void GHash<OBJ>::startIterate() {// initialize a key iterator; call
398 fCurrentEntry=0;
399 }
400
401 template <class OBJ> char* GHash<OBJ>::NextKey() {
402 register int pos=fCurrentEntry;
403 while (pos<fCapacity && hash[pos].hash<0) pos++;
404 if (pos==fCapacity) {
405 fCurrentEntry=fCapacity;
406 return NULL;
407 }
408 else {
409 fCurrentEntry=pos+1;
410 return hash[pos].key;
411 }
412 }
413
414 template <class OBJ> OBJ* GHash<OBJ>::NextData() {
415 register int pos=fCurrentEntry;
416 while (pos<fCapacity && hash[pos].hash<0) pos++;
417 if (pos==fCapacity) {
418 fCurrentEntry=fCapacity;
419 return NULL;
420 }
421 else {
422 fCurrentEntry=pos+1;
423 return (OBJ*)hash[pos].data;
424 }
425
426 }
427
428 template <class OBJ> OBJ* GHash<OBJ>::NextData(char* &nextkey) {
429 register int pos=fCurrentEntry;
430 while (pos<fCapacity && hash[pos].hash<0) pos++;
431 if (pos==fCapacity) {
432 fCurrentEntry=fCapacity;
433 nextkey=NULL;
434 return NULL;
435 }
436 else {
437 fCurrentEntry=pos+1;
438 nextkey=hash[pos].key;
439 return (OBJ*)hash[pos].data;
440 }
441
442 }
443
444 template <class OBJ> GHashEntry* GHash<OBJ>::NextEntry() {
445 register int pos=fCurrentEntry;
446 while (pos<fCapacity && hash[pos].hash<0) pos++;
447 if (pos==fCapacity) {
448 fCurrentEntry=fCapacity;
449 return NULL;
450 }
451 else {
452 fCurrentEntry=pos+1;
453 return &hash[pos];
454 }
455 }
456
457
458 // Get first non-empty entry
459 template <class OBJ> int GHash<OBJ>::First() const {
460 register int pos=0;
461 while(pos<fCapacity){ if(0<=hash[pos].hash) break; pos++; }
462 GASSERT(fCapacity<=pos || 0<=hash[pos].hash);
463 return pos;
464 }
465
466 // Get last non-empty entry
467 template <class OBJ> int GHash<OBJ>::Last() const {
468 register int pos=fCapacity-1;
469 while(0<=pos){ if(0<=hash[pos].hash) break; pos--; }
470 GASSERT(pos<0 || 0<=hash[pos].hash);
471 return pos;
472 }
473
474
475 // Find next valid entry
476 template <class OBJ> int GHash<OBJ>::Next(int pos) const {
477 GASSERT(0<=pos && pos<fCapacity);
478 while(++pos <= fCapacity-1){ if(0<=hash[pos].hash) break; }
479 GASSERT(fCapacity<=pos || 0<=hash[pos].hash);
480 return pos;
481 }
482
483
484 // Find previous valid entry
485 template <class OBJ> int GHash<OBJ>::Prev(int pos) const {
486 GASSERT(0<=pos && pos<fCapacity);
487 while(--pos >= 0){ if(0<=hash[pos].hash) break; }
488 GASSERT(pos<0 || 0<=hash[pos].hash);
489 return pos;
490 }
491
492
493 // Remove all
494 template <class OBJ> void GHash<OBJ>::Clear(){
495 register int i;
496 for(i=0; i<fCapacity; i++){
497 if(hash[i].hash>=0){
498 if (hash[i].keyalloc) GFREE((hash[i].key));
499 if (FREEDATA)
500 (*fFreeProc)(hash[i].data);
501 }
502 }
503 GFREE(hash);
504 GMALLOC(hash, sizeof(GHashEntry)*DEF_HASH_SIZE);
505 //reinitialize it
506 for (i=0; i<DEF_HASH_SIZE; i++)
507 hash[i].hash=-1; //this will be an indicator for 'empty' entries
508 fCapacity=DEF_HASH_SIZE;
509 fCount=0;
510 }
511
512
513 // Save data
514 /*
515 void GHash::Save(Stream& store) const {
516 Object::save(store);
517 store << fCapacity;
518 store << fCount;
519 for(int i=0; i<fCapacity; i++){
520 store << hash[i].hash;
521 if(hash[i].hash>=0){
522 uint len=strlen(hash[i].key);
523 store << len;
524 store << hash[i].mark;
525 store.save(hash[i].key,len);
526 }
527 }
528 }
529
530
531 // Load data
532 void GHash::Load(Stream& store){
533 Object::load(store);
534 store >> fCapacity;
535 store >> fCount;
536 for(int i=0; i<fCapacity; i++){
537 store >> hash[i].hash;
538 if(hash[i].hash>=0){
539 uint len;
540 store >> len;
541 store >> hash[i].mark;
542 GMALLOC(hash[i].key,len+1);
543 store.load(hash[i].key,len);
544 hash[i].key[len]='\0';
545 }
546 }
547 }
548 */
549
550 // Destroy table
551 template <class OBJ> GHash<OBJ>::~GHash(){
552 register int i;
553 for(i=0; i<fCapacity; i++){
554 if(hash[i].hash>=0){
555 if (hash[i].keyalloc) GFREE((hash[i].key));
556 if (FREEDATA) (*fFreeProc)(hash[i].data);
557 }
558 }
559 GFREE(hash);
560 }
561
562 #endif