libs/basekit/source/PHash_inline.h

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docCopyright("Marc Fauconneau", 2007)
   4 docLicense("BSD revised")
   5 docDescription("""
   6         PHash - 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 PHASH_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 PHASH_RECORDS_AT_(self, tableIndex, index) (self->records + self->tableSize*tableIndex + index)
  22 #define PHASH_RECORDS_AT_HASH_(self, tableIndex, hash) \
  23 (self->records + self->tableSize*tableIndex + (hash & self->mask))
  24
  25 IOINLINE unsigned int PHash_count(PHash *self)
  26 {
  27         return self->numKeys;
  28 }
  29
  30 IOINLINE void PHashRecord_swap(PHashRecord* r1, PHashRecord* r2)
  31 {
  32         PHashRecord t = *r1;
  33         *r1 = *r2;
  34         *r2 = t;
  35 }
  36
  37 #define PHashKey_value(k) k
  38
  39 /*
  40 IOINLINE void *PHashKey_value(void *key)
  41 {
  42         return key;
  43 }
  44 */
  45
  46 IOINLINE unsigned int PHashKey_isEqual_(void *key1, void *key2)
  47 {
  48 //      return key2 && (PHashKey_value(key1) == PHashKey_value(key2));
  49         return key1 == key2;
  50 }
  51
  52 // simple hash functions, should be enough for pointers
  53 IOINLINE unsigned int PHash_hash(PHash *self, void *key)
  54 {
  55         intptr_t k = (intptr_t)PHashKey_value(key);
  56         return k^(k>>4);
  57 }
  58
  59 IOINLINE unsigned int PHash_hash_more(PHash *self, unsigned int hash)
  60 {
  61         return hash ^ (hash >> self->log2tableSize);
  62 }
  63
  64 // -----------------------------------
  65
  66 IOINLINE void PHash_clean(PHash *self)
  67 {
  68         memset(self->records, 0, sizeof(PHashRecord) * self->tableSize * 2);
  69         self->numKeys = 0;
  70 }
  71
  72 IOINLINE PHashRecord *PHash_recordAt_(PHash *self, void *key)
  73 {
  74         unsigned int hash;
  75         PHashRecord *record;
  76
  77         hash = PHash_hash(self, key);
  78         record = PHASH_RECORDS_AT_HASH_(self, 0, hash);
  79
  80         // we try the second location
  81         hash = PHash_hash_more(self, hash);
  82         record = (key == record->key) ? record : PHASH_RECORDS_AT_HASH_(self, 1, hash);
  83
  84         return (key == record->key) ? record : &self->nullRecord;
  85 }
  86
  87 IOINLINE void *PHash_at_(PHash *self, void *key)
  88 {
  89         return PHash_recordAt_(self, key)->value;
  90 }
  91
  92 IOINLINE unsigned char PHash_at_update_(PHash *self, void *key, void *value)
  93 {
  94         PHashRecord *record = PHash_recordAt_(self, key);
  95
  96         if (record->key)
  97         {
  98                 // already a matching key, replace it
  99                 if (PHashKey_isEqual_(key, record->key))
 100                 {
 101                         if (record->value == value)
 102                         {
 103                                 return 0; // return 0 if no change
 104                         }
 105
 106                         record->value = value;
 107                         return 1;
 108                 }
 109         }
 110
 111         return 0;
 112 }
 113
 114 IOINLINE void PHash_at_put_(PHash *self, void *key, void *value)
 115 {
 116         PHashRecord thisRecord;
 117         PHashRecord *record;
 118
 119         record = PHash_recordAt_(self, key);
 120
 121         // already a matching key, replace it
 122         if (record != &self->nullRecord && PHashKey_isEqual_(key, record->key))
 123         {
 124                 record->value = value;
 125                 return;
 126         }
 127
 128         thisRecord.key = key;
 129         thisRecord.value = value;
 130
 131         record = PHash_cuckoo_(self, &thisRecord);
 132
 133         if (!record) // collision
 134         {
 135                 PHash_growWithRecord(self, &thisRecord);
 136         }
 137         else
 138         {
 139                 *record = thisRecord;
 140                 self->numKeys ++;
 141                 if (self->numKeys > PHash_maxKeys(self))
 142                         PHash_grow(self);
 143         }
 144 }
 145
 146 IOINLINE void PHash_removeKey_(PHash *self, void *key)
 147 {
 148         PHashRecord *record = PHash_recordAt_(self, key);
 149         void *rkey = record->key;
 150
 151         if (rkey && PHashKey_value(rkey) == PHashKey_value(key))
 152         {
 153                 self->numKeys --;
 154                 memset(record, 0, sizeof(PHashRecord));
 155         }
 156 }
 157
 158 // --- enumeration --------------------------------------------------
 159
 160 #define PHASH_FOREACH(self, pkey, pvalue, code) \
 161 {\
 162         PHash *_self = (self);\
 163         unsigned int _i, _j, _size = _self->tableSize;\
 164         void * pkey;\
 165         void * pvalue;\
 166         \
 167         for (_j = 0; _j < 2; _j ++)\
 168         for (_i = 0; _i < _size; _i ++)\
 169         {\
 170                 PHashRecord *_record = PHASH_RECORDS_AT_(_self, _j, _i);\
 171                 if (_record->key)\
 172                 {\
 173                         pkey = _record->key;\
 174                         pvalue = _record->value;\
 175                         code;\
 176                 }\
 177         }\
 178 }
 179
 180 /*
 181 typedef BASEKIT_API void (PHashDoCallback)(void *);
 182
 183 IOINLINE void PHash_do_(PHash *self, PHashDoCallback *callback)
 184 { PHASH_FOREACH(self, k, v, (*callback)(v)); }
 185
 186 IOINLINE void *PHash_detect_(PHash *self, PHashDetectCallback *callback)
 187 { PHASH_FOREACH(self, k, v, if ((*callback)(v)) return k; ); return NULL; }
 188
 189 IOINLINE void PHash_doOnKeys_(PHash *self, PHashDoCallback *callback)
 190 { PHASH_FOREACH(self, k, v, (*callback)(k)); }
 191
 192 IOINLINE void PHash_doOnKeyAndValue_(PHash *self, PHashDoCallback *callback)
 193 { PHASH_FOREACH(self, k, v, (*callback)(k); (*callback)(v);); }
 194 */
 195
 196 #undef IO_IN_C_FILE
 197 #endif