src/vdu.h

   1 #ifndef __VDU_H
   2 #define __VDU_H
   3
   4 typedef ino64_t KEY;
   5 typedef KEY *PKEY;
   6 typedef struct stat64 VAL;
   7 typedef VAL *PVAL;
   8
   9 static inline
  10 unsigned int
  11 HASH(PKEY key){
  12     return (int) *key;
  13 }
  14
  15 static inline
  16 unsigned int // boolean
  17 EQUAL(PKEY key1, PKEY key2){
  18     return *key1 == *key2;
  19 }
  20
  21 #ifndef MIN
  22 #define MIN(x,y) (((x)<(y))?(x):(y))
  23 #endif // MIN
  24
  25 #ifndef MAX
  26 #define MAX(x,y) (((x)>(y))?(x):(y))
  27 #endif // MAX
  28
  29
  30 ////////////////////////////////////////////////////////////////////////////
  31 ////////////////////////////////////////////////////////////////////////////
  32 // hash table support for efficient lookup of duplicate inodes */
  33 ////////////////////////////////////////////////////////////////////////////
  34 ////////////////////////////////////////////////////////////////////////////
  35
  36 #define Multiplier  (0x9e3779b9)
  37 #define MaxLogBuckets  (((sizeof (unsigned long))*8) - 2)
  38 #define MaxBuckets     (1<<MaxLogBuckets)
  39 #define MinLogBuckets  (4)
  40 #define MinBuckets     (1<<MinLogBuckets)
  41
  42 // Thresholds for rehashing the table: *)
  43 // to avoid crazy oscillations, we must have MaxDensity > 2*MinDensity; *)
  44 // to avoid excessive probes, we must try to keep MaxDensity low. *)
  45 // Divide by 100 before using
  46 #define MaxDensity 75 /* max numEntries/NUMBER(buckets) */
  47 #define MinDensity 20 /* min numEntries/NUMBER(buckets) */
  48 #define IdealDensity 50
  49 #define BITSIZE(x) (sizeof(x)*8)
  50
  51 #define NEW(type,num) ((type*)malloc(sizeof(type)*num))
  52 #define DISPOSE(ptr) (free((void*)ptr))
  53
  54 ////////////////////////////////////////////////////////////////////////////
  55 ////////////////////////////////////////////////////////////////////////////
  56 // Generic Hash Entry Type
  57 ////////////////////////////////////////////////////////////////////////////
  58 ////////////////////////////////////////////////////////////////////////////
  59
  60 typedef struct VoidList {
  61   struct VoidList *tail;
  62 } VoidList, *PVoidList;
  63
  64 typedef struct HashTable {
  65   PVoidList *buckets;
  66   unsigned int numBuckets;    // number of buckets
  67   unsigned int minLogBuckets; // minimum value for Log_2(initial size)
  68   unsigned int logBuckets;    // CEILING(Log2(NUMBER(buckets^)))
  69   unsigned int maxEntries;    // maximum number of entries
  70   unsigned int minEntries;    // minimum number of entries
  71   unsigned int numEntries;    // current num of entries in table
  72   PVoidList cache;            // cache of removed elements
  73   int cacheSize;              // current size of the cache
  74   int maxCacheSize;           // maximum size, -1 means unbounded, 0 no cache
  75 } HashTable, *PHashTable;
  76
  77 ////////////////////////////////////////////////////////////////////////////
  78 ////////////////////////////////////////////////////////////////////////////
  79 // Hash Prototypes
  80 ////////////////////////////////////////////////////////////////////////////
  81 ////////////////////////////////////////////////////////////////////////////
  82
  83 PHashTable
  84 Init(PHashTable tbl, unsigned int n, int maxCacheSize);
  85
  86 void
  87 Dispose(PHashTable tbl);
  88
  89 unsigned int
  90 Log_2(unsigned int x);
  91
  92 void
  93 NewBuckets(PHashTable tbl, unsigned int logBuckets);
  94
  95 //
  96 // Generic Hash Table support
  97 //
  98
  99 PHashTable
 100 Init(PHashTable tbl, unsigned int n, int maxCacheSize){
 101   int idealBuckets;
 102   int minBuckets;
 103
 104   idealBuckets = MIN(((n*100)/IdealDensity),MaxBuckets);
 105   minBuckets = MAX(MinBuckets, idealBuckets);
 106   tbl->minLogBuckets = Log_2(minBuckets);
 107
 108   NewBuckets(tbl, tbl->minLogBuckets);
 109   tbl->numEntries = 0;
 110   tbl->maxCacheSize = maxCacheSize;
 111   tbl->cacheSize = 0;
 112   tbl->cache = 0;
 113   return tbl;
 114 } // Init()
 115
 116
 117 //
 118 // Internal procedures
 119 //
 120
 121 unsigned int
 122 Log_2(unsigned int x){
 123   // return CEILING(LOG_2(x))
 124   unsigned int log = 0;
 125   unsigned int n= 1;
 126
 127   assert(x != 0);
 128   while ((log < MaxLogBuckets) && (x > n)){
 129     log++;
 130     n += n;
 131   }
 132   return log;
 133 } // Log_2()
 134
 135 void
 136 NewBuckets(PHashTable tbl, unsigned int logBuckets){
 137   // Allocate "2^logBuckets" buckets.
 138   unsigned int numBuckets = 1 << logBuckets;
 139   PVoidList *b;
 140   unsigned int i;
 141
 142   tbl->buckets = NEW(PVoidList, numBuckets);
 143   tbl->numBuckets = numBuckets;
 144   b = tbl->buckets;
 145
 146   for (i=0; i<tbl->numBuckets; i++){
 147     b[i] = NULL;
 148   }
 149   tbl->logBuckets = logBuckets;
 150   tbl->maxEntries = MaxDensity * numBuckets / 100;
 151   tbl->minEntries = MinDensity * numBuckets / 100;
 152 } // NewBuckets()
 153
 154 #ifndef NULL
 155 #define NULL (void*)0
 156 #endif // !NULL
 157
 158 #ifndef TRUE
 159 #define TRUE 1
 160 #endif // !TRUE
 161
 162 #ifndef FALSE
 163 #define FALSE 0
 164 #endif // !FALSE
 165
 166 ////////////////////////////////////////////////////////////////////////////
 167 ////////////////////////////////////////////////////////////////////////////
 168 // Type specific hash entry
 169 ////////////////////////////////////////////////////////////////////////////
 170 ////////////////////////////////////////////////////////////////////////////
 171 typedef struct EntryList {
 172   struct EntryList *tail;
 173   KEY key;
 174   VAL val;
 175 }EntryList, *PEntryList;
 176
 177 ////////////////////////////////////////////////////////////////////////////
 178 ////////////////////////////////////////////////////////////////////////////
 179 // Type specific Hash implementation functions
 180 ////////////////////////////////////////////////////////////////////////////
 181 ////////////////////////////////////////////////////////////////////////////
 182
 183 static
 184 void
 185 Rehash(PHashTable tbl, unsigned int logBuckets) {
 186   // Reallocate "2^logBuckets" buckets, and rehash the entries into
 187   // the new table.
 188
 189   PVoidList *oldBucketPointer;
 190   PEntryList *ob, obi;
 191   PEntryList *nb, *nbh;
 192   PEntryList that, tail;
 193   unsigned int index;
 194   unsigned int i;
 195   unsigned int oldNumBuckets;
 196
 197   return;
 198   assert(logBuckets <= MaxLogBuckets);
 199   assert(logBuckets >= tbl->minLogBuckets);
 200   oldBucketPointer = tbl->buckets;
 201   ob = (PEntryList*)tbl->buckets;
 202   oldNumBuckets = tbl->numBuckets;
 203
 204   NewBuckets(tbl, logBuckets);
 205   nb = (PEntryList*)tbl->buckets;
 206
 207   for(i=0;i<oldNumBuckets;i++){
 208     obi = ob[i];
 209     that = obi;
 210     while (that != NULL) {
 211       index = (HASH(&(that->key))*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
 212       nbh = &(nb[index]);
 213       tail = that->tail;
 214       that->tail = *nbh;
 215       *nbh = that;
 216       that = tail;
 217     }
 218   }
 219   DISPOSE (oldBucketPointer);
 220 }
 221
 222 static inline
 223 unsigned int // boolean
 224 Get(PHashTable tbl, PKEY key, PVAL *val){
 225   PEntryList that;
 226   unsigned int index;
 227
 228   index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
 229   that = (PEntryList)tbl->buckets[index];
 230   while ((that != NULL) && !EQUAL(key,&(that->key))) {
 231     that = that->tail;
 232   }
 233   if (that != NULL){
 234     *val = &that->val;
 235     return TRUE;
 236   }
 237   else {
 238     return FALSE;
 239   }
 240 } // Get()
 241
 242 static inline
 243 unsigned int // boolean
 244 Put(PHashTable tbl, PKEY key, PVAL *val){
 245   PEntryList that;
 246   PEntryList *first;
 247   unsigned int index;
 248   unsigned int res;
 249
 250   index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
 251   first = (PEntryList*)&(tbl->buckets[index]);
 252   that = *first;
 253   while ((that != NULL) && !EQUAL(key, &(that->key))){
 254     that = that->tail;
 255   }
 256
 257   // found an entry in the hash table given above key
 258   if (that != NULL){
 259     res = TRUE;
 260   }
 261   else {
 262     // check if we can reuse something from the cache
 263     if (tbl->cache != NULL) {
 264           that = (PEntryList)tbl->cache;
 265           tbl->cache = (PVoidList)tbl->cache->tail;
 266           that->key = *key;
 267           that->tail = *first;
 268           *first = that;
 269     }
 270     else {
 271           that = NEW(EntryList,1);
 272           that->key = *key;
 273           that->tail = *first;
 274           *first = that;
 275     }
 276     that->val = **val;
 277
 278     tbl->numEntries++;
 279     if ((tbl->logBuckets < MaxLogBuckets)
 280         && (tbl->numEntries > tbl->maxEntries)){
 281       Rehash(tbl, tbl->logBuckets + 1); // too crowded
 282     }
 283     res = FALSE;
 284   }
 285   *val = &that->val;
 286   return res;
 287
 288 } // Put()
 289
 290 static inline
 291 int
 292 Delete(PHashTable tbl,PKEY key){
 293   PEntryList that, prev;
 294   PEntryList *first;
 295   unsigned int index;
 296
 297   index = (HASH(key)*Multiplier)>>(BITSIZE(unsigned long)-tbl->logBuckets);
 298   first = (PEntryList*)&(tbl->buckets[index]);
 299   that = *first;
 300   prev = NULL;
 301
 302   while ((that != NULL) && !EQUAL(key, &(that->key))){
 303     prev = that;
 304     that = that->tail;
 305   }
 306   if (that != NULL) {
 307     if (prev == NULL) {
 308       *first = that->tail;
 309     }
 310     else {
 311       prev->tail = that->tail;
 312     }
 313     if ((tbl->maxCacheSize == -1)||(tbl->cacheSize < tbl->maxCacheSize)) {
 314       that->tail = (PEntryList)tbl->cache;
 315       tbl->cache = (PVoidList)that;
 316       tbl->cacheSize++;
 317     }
 318     else {
 319       DISPOSE (that);
 320     }
 321     tbl->numEntries--;
 322     if (tbl->maxCacheSize == 0) {
 323       if ((tbl->logBuckets > tbl->minLogBuckets)
 324           && (tbl->numEntries < tbl->minEntries)) {
 325         Rehash(tbl, tbl->logBuckets - 1); // too sparse
 326       }
 327     }
 328     return TRUE;
 329   }
 330   else {
 331     return FALSE;
 332   }
 333 } // Delete()
 334
 335 typedef void (*callback)(PKEY key, PVAL val);
 336
 337 void
 338 Iterate(PHashTable tbl, callback fn)
 339 {
 340   PVoidList that;
 341   unsigned int i;
 342
 343   for(i=0;i<tbl->numBuckets;i++) {
 344     that = tbl->buckets[i];
 345     while ( that != (PVoidList)0 ) {
 346       PEntryList entry = (PEntryList)that;
 347       fn(&entry->key,&entry->val);
 348       that = that->tail;
 349     }
 350   }
 351 }
 352
 353 void
 354 Dispose(PHashTable tbl)
 355 {
 356   PVoidList that, next;
 357   unsigned int i;
 358
 359   for(i=0;i<tbl->numBuckets;i++) {
 360     that = tbl->buckets[i];
 361     while( that != NULL) {
 362         next = that->tail;
 363         DISPOSE (that);
 364         tbl->numEntries--;
 365         that = next;
 366     }
 367   }
 368   DISPOSE(tbl->buckets);
 369   assert(tbl->numEntries = 0);
 370 } // Dispose;
 371
 372
 373
 374 #endif // __VDU_H