libs/basekit/source/PHash_inline.h

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