A few bug fixes related to the mlogft machine.
[charm.git] / src / util / ckhashtable.h
1 /* Hash Table routines
2 Orion Sky Lawlor, olawlor@acm.org, 11/21/1999
3
4 This file defines the interface for the C++ Hashtable
5 class.  A Hashtable stores key/object pairs
6 so that an arbitrary key can be accessed in 
7 constant time.
8
9 This is a complicated non-chaining Hashtable implementation.
10 It dynamically rehashes when the table gets too full.  
11 Both the key and object are treated as arbitrary fixed-length 
12 runs of bytes.
13
14 Key hashing and comparison are handled by function pointers,
15 so the keys can be interpreted any way you like.  The default
16 (and C interface way) is to treat them as runs of plain bytes.
17 */
18
19 #ifdef __cplusplus
20 #include "pup.h"
21 extern "C" {
22 #endif
23 #ifndef __cplusplus
24 #include "pup_c.h"
25 #endif
26
27 #ifndef __OSL_HASH_TABLE_C
28 #define __OSL_HASH_TABLE_C
29
30 #include <stddef.h>
31
32 /*C Version of Hashtable header file: */
33 typedef void *CkHashtable_c;
34
35 /*Create hashtable with a single integer as the key*/
36 CkHashtable_c CkCreateHashtable_int(int objBytes,int initSize);
37 /*Create hashtable with a C string pointer as the key */
38 CkHashtable_c CkCreateHashtable_string(int objBytes,int initSize);
39 /*Create hashtable with a C pointer as the key */
40 CkHashtable_c CkCreateHashtable_pointer(int objBytes,int initSize);
41
42 void CkDeleteHashtable(CkHashtable_c h);
43
44 /*Return object storage for this (possibly new) key*/
45 void *CkHashtablePut(CkHashtable_c h,const void *atKey);
46
47 /*Return object storage for this (old) key-- */
48 /*  returns NULL if key not found.*/
49 void *CkHashtableGet(CkHashtable_c h,const void *fromKey);
50
51 /*Return the key associated with this object (previously returned with one of the above functions) */
52 void *CkHashtableKeyFromObject(CkHashtable_c h,const void *object);
53
54 /*Remove this key, rehashing as needed */
55 void CkHashtableRemove(CkHashtable_c h,const void *doomedKey);
56
57 /*Number of elements stored in the hashtable */
58 int CkHashtableSize(CkHashtable_c h);
59
60 /*C Version of Hashtable iterator */
61 typedef void *CkHashtableIterator_c;
62
63 /*Return the iterator for the given hashtable. It is reset to the beginning */
64 CkHashtableIterator_c CkHashtableGetIterator(CkHashtable_c h);
65
66 /* Return the next element in the hash table given the iterator (NULL if not found) */
67 void *CkHashtableIteratorNext(CkHashtableIterator_c it, void **retKey);
68
69 /* Seek the iterator into the hashtable by 'n' slot (*not* objects) */
70 void CkHashtableIteratorSeek(CkHashtableIterator_c it, int n);
71
72 /* Seek the iterator into the hashtable by 'n' slot (*not* objects) */
73 void CkHashtableIteratorSeekStart(CkHashtableIterator_c it);
74
75 #endif /*__OSL_HASH_TABLE_C*/
76 #ifdef __cplusplus
77 };
78
79 #ifndef __OSL_HASH_TABLE_CPP
80 #define __OSL_HASH_TABLE_CPP
81
82 #include <stdio.h>
83
84 //This data type is used to index into the hash table.
85 // For best results, all the bits of the hashCode should be
86 // meaningful (especially the high bits).
87 typedef unsigned int CkHashCode;
88
89 //A circular-left-shift, useful for creating hash codes.
90 inline CkHashCode circleShift(CkHashCode h,unsigned int by) 
91 {
92         const unsigned int intBits=8*sizeof(CkHashCode);
93         by%=intBits;
94         return (h<<by)|(h>>(intBits-by));
95 }
96
97 //Functions to map keys to hash codes.
98 typedef CkHashCode (*CkHashFunction)(const void *keyData,size_t keyLen);
99 CkHashCode CkHashFunction_default(const void *keyData,size_t keyLen);
100 CkHashCode CkHashFunction_string(const void *keyData,size_t keyLen);
101 inline CkHashCode CkHashFunction_int(const void *keyData,size_t /*len*/)
102         {return *(int *)keyData;}
103 inline CkHashCode CkHashFunction_pointer(const void *keyData,size_t /*len*/)
104         {if (sizeof(char*)==sizeof(int)) return *(int *)keyData;
105         else if (sizeof(char*)==2*sizeof(int)) return ((int*)keyData)[0] ^ ((int*)keyData)[1];
106         else *((char*)0) = 0;
107         return 0;
108         }
109
110 //Functions return 1 if two keys are equal; 0 otherwise
111 typedef int (*CkHashCompare)(const void *key1,const void *key2,size_t keyLen);
112 int CkHashCompare_default(const void *key1,const void *key2,size_t keyLen);
113 int CkHashCompare_string(const void *key1,const void *key2,size_t keyLen);
114 inline int CkHashCompare_int(const void *k1,const void *k2,size_t /*len*/)
115         {return *(int *)k1 == *(int *)k2;}
116 inline int CkHashCompare_pointer(const void *k1,const void *k2,size_t /*len*/)
117         {return *(char **)k1 == *(char **)k2;}
118
119 #ifdef _FAULT_MLOG_
120 extern int countHashRefs;
121 extern int countHashCollisions;
122 #endif
123
124 ///////////////////////// Hashtable //////////////////////
125
126 class CkHashtableIterator;
127
128 /**
129  Describes the in-memory layout of a hashtable entry.
130
131 Nobody should ever use this class directly; use CkHashtableT
132 or CkHashtableTslow instead.
133
134 "key" is a user-defined type, used as the unique object identifier.
135 The key is assumed to begin at the start of the entry.  
136 "empty" is a character, set to 1 if this entry in the table 
137 is unused, zero otherwise; the "empty" field must not overlap 
138 either of the other fields. "object" is the thing the table stores;
139 it is of a user-defined type and may overlap "key".
140
141      | key | empty | gap? | object | gap? |
142 ==   | <------- hashtable entry --------> |
143
144 */
145 class CkHashtableLayout {
146   int size; ///< Size of entire table entry, at least ks+os.
147   int ko,ks; ///< Key byte offset (always zero) and size
148   int po,ps; ///< "empty bit" offset and size (always 1)
149   int oo,os; ///< Object byte offset and size
150  public:
151   CkHashtableLayout(int keySize,int emptyOffset,
152                     int objectOffset,int objectSize,int entryLength):
153                 size(entryLength),
154                 ko(0), ks(keySize),
155                 po(emptyOffset), ps(1),
156                 oo(objectOffset), os(objectSize)
157   {}
158
159   inline int entrySize(void) const {return size;}
160   inline int keySize(void) const {return ks;}
161   inline int objectSize(void) const {return os;}
162
163 //Utility functions:
164   /// Given an entry pointer, return a pointer to the key
165   inline char *getKey(char *entry) const {return entry+ko;}
166   /// Given an entry pointer, return a pointer to the object
167   inline char *getObject(char *entry) const {return entry+oo;}
168   
169   /// Is this entry empty?
170   inline char isEmpty(char *entry) const {return *(entry+po);}
171   /// Mark this entry as empty
172   inline void empty(char *entry) const {*(entry+po)=1;}  
173   /// Mark this entry as full
174   inline void fill(char *entry) const {*(entry+po)=0;}
175
176   /// Move to the next entry
177   inline char *nextEntry(char *entry) const {return entry+size;}
178
179   /// Get entry pointer from key pointer
180   inline char *entryFromKey(char *key) const {return key-ko;}
181   
182   /// Get entry pointer from object pointer
183   inline char *entryFromObject(char *obj) const {return obj-oo;}
184 };
185
186 /**
187  A resize-on-demand extensible hashtable.  Users should probably
188 use CkHashtableT or CkHashtableTslow instead of calling this class
189 directly.
190 */
191 class CkHashtable {
192 private:
193         CkHashtable(const CkHashtable &); //Don't use these
194         void operator=(const CkHashtable &);
195 protected:
196         int len;//Vertical dimension of below array (best if prime)
197         CkHashtableLayout layout; //Byte-wise storage layout for an entry
198         char *table;//len hashtable entries
199         
200         int nObj;//Number of objects actually stored (0..len)
201         int resizeAt;//Resize when nObj>=resizeAt
202         CkHashFunction hash; //Function pointer to compute key hash
203         CkHashCompare compare; //Function pointer to compare keys
204         
205         float loadFactor;//Maximum fraction of table to fill 
206         // (0->always enlarge; 1->only when absolutely needed)
207         
208         //Increment i around the table
209         int inc(int &i) const {i++; if (i>=len) i=0; return i;}
210         
211         //Return the start of the i'th entry in the hash table
212         char *entry(int i) const {return (char *)(table+i*layout.entrySize());}
213
214         //Find the given key in the table.  If it's not there, return NULL
215         char *findKey(const void *key) const;
216         //Find a spot for the given key in the table.  If there's not room, return NULL
217         char *findEntry(const void *key) const;
218         
219         //Build a new empty table of the given size
220         void buildTable(int newLen);
221         //Set the table to the given size, re-hashing everything.
222         void rehash(int newLen);
223 public:
224         //Constructor-- create an empty hash table of the given size
225         CkHashtable(const CkHashtableLayout &layout_,
226                 int initLen=5,float NloadFactor=0.5,
227                 CkHashFunction hash=CkHashFunction_default,
228                 CkHashCompare compare=CkHashCompare_default);
229         //Destructor-- destroy table
230         ~CkHashtable();
231         
232         //Add the given object to this table under the given key
233         // Returns pointer to object storage.
234         // Table will be resized if needed.
235         void *put(const void *key);
236         
237         //Look up the given object in this table.  Return NULL if not found.
238         void *get(const void *key) const {
239                 char *ent=findKey(key);
240                 if (ent==NULL) return NULL;
241                 else return layout.getObject(ent);
242         }
243         
244         //Remove this object from the hashtable (re-hashing if needed)
245         void remove(const void *key);
246
247         //Remove all objects and keys
248         void empty(void);
249         
250         int numObjects(void) const { return nObj; } 
251         
252         //Return an iterator for the objects in this hash table
253         CkHashtableIterator *iterator(void);
254 };
255
256 //A HashtableIterator lets you easily list all the objects
257 // in a hash table (without knowing all the keys).
258 class CkHashtableIterator {
259 protected:
260         int len;
261         CkHashtableLayout layout; //Byte-wise storage layout for an entry
262         char *table;
263         int curNo;//Table index of current object (to be returned next)
264         //Return the start of the i'th entry in the hash table
265         char *entry(int i) const {return table+i*layout.entrySize();}
266 public:
267         CkHashtableIterator(char *table_,int len_,const CkHashtableLayout &lo)
268           :len(len_),layout(lo),table(table_),curNo(0)
269                 {}
270         CkHashtableIterator(const CkHashtableIterator &it);  //don't copy
271         void operator=(const CkHashtableIterator &it);      // don't copy
272         
273         //Seek to start of hash table
274         void seekStart(void);
275         
276         //Seek forward (or back) n hash slots (*not* n objects!)
277         void seek(int n);
278         
279         //Return 1 if next will be non-NULL
280         int hasNext(void);
281         //Return the next object, or NULL if none.
282         // The corresponding object key will be returned in retKey.
283         void *next(void **retKey=NULL);
284 };
285
286
287 /////////////////// Templated Hashtable /////////////////
288 /**
289 This class provides a thin typesafe layer over the (unsafe)
290 CkHashtable above.  Via the magic of function inlining, this
291 comes at zero time and space cost over the unsafe version.
292
293 The unsafe version exists to avoid the code bloat associated
294 with profligate use of templates; because the typeless layer
295 handles the difficult parts, this templated class is very cheap.
296 */
297 template <class KEY, class OBJ> 
298 class CkHashtableTslow:public CkHashtable {
299   //Return the layout for this hashtable:
300   static inline CkHashtableLayout getLayout(void) {
301     //This struct defines the in-memory layout that we will use.
302     //  By including it in a struct rather than figuring it out ourselves, 
303     //  we let the compiler figure out what the (bizarre) alignment requirements are.
304     struct entry_t {
305       KEY k;
306       char empty;
307       OBJ o;
308     };
309     // HACK: All I want is the offset from entry_t to empty and o;
310     //  but the compiler's "offsetof" keyword complains "non-POD type!".
311     entry_t *e=(entry_t *)0;
312     int emptyOffset=((char *)&e->empty)-(char *)e;
313     int oOffset=((char *)&e->o)-(char *)e;
314     return CkHashtableLayout(sizeof(KEY),emptyOffset,
315                              oOffset,sizeof(OBJ),sizeof(entry_t));
316   }
317 public:
318         //Constructor-- create an empty hash table of at least the given size
319         CkHashtableTslow(
320                 int initLen=5,float NloadFactor=0.5,
321                 CkHashFunction Nhash=CkHashFunction_default,
322                 CkHashCompare Ncompare=CkHashCompare_default)
323          :CkHashtable(getLayout(),initLen,NloadFactor,Nhash,Ncompare)
324          {}
325         
326         OBJ &put(const KEY &key) {
327                 void *obj = CkHashtable::put((const void *)&key);
328                 return *(OBJ *)obj;
329         }
330         OBJ get(const KEY &key) const {
331                 void *r=CkHashtable::get((const void *)&key);
332                 if (r==NULL) return OBJ(0);
333                 else return *(OBJ *)r;
334         }
335         //Use this version when you're sure the entry exists
336         OBJ &getRef(const KEY &key) {
337                 return *(OBJ *)CkHashtable::get((const void *)&key);
338         }
339         void remove(const KEY &key) {CkHashtable::remove((const void *)&key);}
340 };
341
342 //Declare the KEY.hash & KEY.compare functions inline for a 
343 // completely inlined (very fast) hashtable lookup.     
344 // You MUST be SURE the hash and compare functions return the same
345 //  values as the staticHash and staticCompare functions.
346 template <class KEY, class OBJ> 
347 class CkHashtableT:public CkHashtableTslow<KEY,OBJ> {
348 public:
349         //Constructor-- create an empty hash table of at least the given size
350         CkHashtableT(int initLen=5,float NloadFactor=0.5)
351           :CkHashtableTslow<KEY,OBJ>(initLen,NloadFactor,
352                                      KEY::staticHash,KEY::staticCompare)
353         {}
354         CkHashtableT(
355                 int initLen,float NloadFactor,
356                 CkHashFunction Nhash,CkHashCompare Ncompare)
357                 :CkHashtableTslow<KEY,OBJ>(initLen,NloadFactor,Nhash,Ncompare)
358          {}
359         
360         //Return the object, or "0" if it doesn't exist
361         OBJ get(const KEY &key) const {
362                 int i=key.hash()%this->len;
363                 while(1) {//Assumes key or empty slot will be found
364                         char *cur=this->entry(i);
365                         //An empty slot indicates the key is not here
366                         if (this->layout.isEmpty(cur)){ 
367                                 return OBJ(0);
368                         }
369                         //Is this the key?
370                         if (key.compare(*(KEY *)this->layout.getKey(cur)))
371                                 return *(OBJ *)this->layout.getObject(cur);
372                         this->inc(i);
373                 };
374         }
375
376 #ifdef _FAULT_MLOG_
377         OBJ *getPointer(const KEY &key) {
378         countHashRefs++;
379         int i=key.hash()%this->len;
380         while(1) {//Assumes key or empty slot will be found
381             char *cur=this->entry(i);
382                         //An empty slot indicates the key is not here
383             if (this->layout.isEmpty(cur)){
384                 return NULL;
385             }
386                         //Is this the key?
387             if (key.compare(*(KEY *)this->layout.getKey(cur)))
388                 return (OBJ *)this->layout.getObject(cur);
389             this->inc(i);
390             countHashCollisions++;
391         };
392         return NULL;
393     }
394 #endif
395
396         //Use this version when you're sure the entry exists--
397         // avoids the test for an empty entry
398         OBJ &getRef(const KEY &key) {
399                 int i=key.hash()%this->len;
400                 while(1) {//Assumes key or empty slot will be found
401                         char *cur=this->entry(i);
402                         //Is this the key?
403                         if (key.compare(*(KEY *)this->layout.getKey(cur)))
404                                 return *(OBJ *)this->layout.getObject(cur);
405                         this->inc(i);
406                 };
407         }
408         void pup(PUP::er &p){
409                 if(!p.isUnpacking()){
410                         /*packing phase: loop through the hashtable values*/
411                         CkHashtableIterator *it=CkHashtable::iterator();
412                         int hasNext=1;
413                         OBJ *o; KEY *k;
414                         while (NULL!=(o=(OBJ *)it->next((void **)&k))) {
415                                 p|hasNext;
416                                 p|*k;
417                                 p|*o;
418                         }
419                         hasNext=0; p|hasNext;
420                         delete it;
421                 }else{
422                 /*Unpacking phase: add each hashtable item*/
423                         int hasNext;
424                         p|hasNext;
425                         while (hasNext) {
426                                 OBJ o; KEY k;
427                                 p|k;
428                                 p|o;
429                                 put(k)=o;
430                                 p|hasNext;
431                         }
432                 }
433         }
434 };
435
436 /**
437 A useful adaptor class for using basic (memory only)
438   types like int, short, char, etc. as hashtable keys.
439
440 This class adds the hash, compare, staticHash, and staticCompare
441 routines needed to be a CkHashtableT KEY; you can thus use ints
442 as a fast key like this:
443         CkHashtableT<CkHashtableAdaptorT<int>, foo> bar;
444
445 */
446 template <class T> class CkHashtableAdaptorT {
447         T val;
448 public:
449         CkHashtableAdaptorT<T>(const T &v):val(v) {}
450         /**added to allow pup to do Key k while unPacking*/
451         CkHashtableAdaptorT<T>(){}
452         operator T & () {return val;}
453         operator const T & () const {return val;}
454         inline CkHashCode hash(void) const 
455                 {return (CkHashCode)val;}
456         static CkHashCode staticHash(const void *k,size_t) 
457                 {return ((CkHashtableAdaptorT<T> *)k)->hash();}
458         inline int compare(const CkHashtableAdaptorT<T> &t) const
459                 {return val==t.val;}
460         static int staticCompare(const void *a,const void *b,size_t) 
461         {
462                 return ((CkHashtableAdaptorT<T> *)a)->
463                      compare(*(CkHashtableAdaptorT<T> *)b);
464         }
465         void pup(PUP::er &p){
466                 p | val;
467         }
468 };
469
470 #endif /*__OSL_HASH_TABLE_C++*/
471
472 #endif /*C++*/