libs/basekit/source/SHash_inline.h

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docCopyright("Marc Fauconneau", 2007)
   4 docLicense("BSD revised")
   5 docDescription("""
   6         SHash - Cuckoo Hash
   7         keys and values are references (they are not copied or freed)
   8         key pointers are assumed unique
   9
  10 """)
  11 */
  12
  13 #ifdef SHASH_C
  14 #define IO_IN_C_FILE
  15 #endif
  16 #include "Common_inline.h"
  17 #ifdef IO_DECLARE_INLINES
  18
  19 #include <stdio.h>
  20
  21 #define SHASH_RECORDS_AT_(self, tableIndex, index) (self->records + self->tableSize*tableIndex + index)
  22 #define SHASH_RECORDS_AT_HASH_(self, tableIndex, hash) \
  23 (self->records + self->tableSize*tableIndex + (hash & self->mask))
  24
  25 IOINLINE unsigned int SHash_count(SHash *self)
  26 {
  27         return self->numKeys;
  28 }
  29
  30 IOINLINE void SHashRecord_swap(SHashRecord* r1, SHashRecord* r2)
  31 {
  32         SHashRecord t = *r1;
  33         *r1 = *r2;
  34         *r2 = t;
  35 }
  36
  37 IOINLINE unsigned int SHash_keysAreEqual_(SHash *self, void *key1, void *key2)
  38 {
  39         return key2 && self->keysEqual(key1, key2);
  40 }
  41
  42 // simple hash functions, should be enough for pointers
  43
  44 IOINLINE unsigned int SHash_hash(SHash *self, void *key)
  45 {
  46         intptr_t k = self->hashForKey(key);
  47         return k ^ (k >> 4);
  48 }
  49
  50 IOINLINE unsigned int SHash_hash_more(SHash *self, unsigned int hash)
  51 {
  52         return hash ^ (hash >> self->log2tableSize);
  53 }
  54
  55 // -----------------------------------
  56
  57 IOINLINE void SHash_clean(SHash *self)
  58 {
  59         memset(self->records, 0, sizeof(SHashRecord) * self->tableSize * 2);
  60         self->numKeys = 0;
  61 }
  62
  63 IOINLINE SHashRecord *SHash_recordAt_(SHash *self, void *key)
  64 {
  65         unsigned int hash;
  66         SHashRecord *record;
  67
  68         // try first location
  69
  70         hash = SHash_hash(self, key);
  71         record = SHASH_RECORDS_AT_HASH_(self, 0, hash);
  72         if (SHash_keysAreEqual_(self, key, record->key)) { return record; }
  73
  74         // try second location
  75
  76         hash = SHash_hash_more(self, hash);
  77         record = SHASH_RECORDS_AT_HASH_(self, 1, hash);
  78         if (SHash_keysAreEqual_(self, key, record->key)) { return record; }
  79
  80         return &self->nullRecord;
  81 }
  82
  83 IOINLINE void *SHash_at_(SHash *self, void *key)
  84 {
  85         return SHash_recordAt_(self, key)->value;
  86 }
  87
  88 IOINLINE int SHashKey_hasKey_(SHash *self, void *key)
  89 {
  90         return SHash_at_(self, key) != NULL;
  91 }
  92
  93 IOINLINE void SHash_at_put_(SHash *self, void *key, void *value)
  94 {
  95         SHashRecord thisRecord;
  96         SHashRecord *record;
  97
  98         record = SHash_recordAt_(self, key);
  99
 100         // already a matching key, replace it
 101         if (record != &self->nullRecord && SHash_keysAreEqual_(self, key, record->key))
 102         {
 103                 record->value = value;
 104                 return;
 105         }
 106
 107         thisRecord.key = key;
 108         thisRecord.value = value;
 109
 110         record = SHash_cuckoo_(self, &thisRecord);
 111
 112         if (!record) // collision
 113         {
 114                 SHash_growWithRecord(self, &thisRecord);
 115                 //printf("grow due to key collision: SHash_%p numKeys %i \ttableSize %i \tratio %f\n", (void *)self, self->numKeys, self->tableSize, (float) self->numKeys / (float) self->tableSize);
 116         }
 117         else
 118         {
 119                 *record = thisRecord;
 120                 self->numKeys ++;
 121                 if (self->numKeys > SHash_maxKeys(self))
 122                 {
 123                         SHash_grow(self);
 124                         //printf("grow due to full table: SHash_%p numKeys %i \ttableSize %i \tratio %f\n", (void *)self, self->numKeys, self->tableSize, (float) self->numKeys / (float) self->tableSize);
 125                 }
 126         }
 127
 128 }
 129
 130 IOINLINE void SHash_removeKey_(SHash *self, void *key)
 131 {
 132         SHashRecord *record = SHash_recordAt_(self, key);
 133         void *rkey = record->key;
 134
 135         if (rkey && SHash_keysAreEqual_(self, rkey, key))
 136         {
 137                 self->numKeys --;
 138                 memset(record, 0, sizeof(SHashRecord));
 139         }
 140 }
 141
 142 // --- enumeration --------------------------------------------------
 143
 144 #define SHASH_FOREACH(self, pkey, pvalue, code) \
 145 {\
 146         SHash *_self = (self);\
 147         unsigned int _i, _j, _size = _self->tableSize;\
 148         void * pkey;\
 149         void * pvalue;\
 150         \
 151         for (_j = 0; _j < 2; _j ++)\
 152         for (_i = 0; _i < _size; _i ++)\
 153         {\
 154                 SHashRecord *_record = SHASH_RECORDS_AT_(_self, _j, _i);\
 155                 if (_record->key)\
 156                 {\
 157                         pkey = _record->key;\
 158                         pvalue = _record->value;\
 159                         code;\
 160                 }\
 161         }\
 162 }
 163
 164 /*
 165  typedef BASEKIT_API void (SHashDoCallback)(void *);
 166 IOINLINE void SHash_do_(SHash *self, SHashDoCallback *callback)
 167 { SHASH_FOREACH(self, k, v, (*callback)(v)); }
 168
 169 IOINLINE void SHash_doOnKeys_(SHash *self, SHashDoCallback *callback)
 170 { SHASH_FOREACH(self, k, v, (*callback)(k)); }
 171
 172 IOINLINE void SHash_doOnKeyAndValue_(SHash *self, SHashDoCallback *callback)
 173 { SHASH_FOREACH(self, k, v, (*callback)(k); (*callback)(v);); }
 174 */
 175
 176 #undef IO_IN_C_FILE
 177 #endif