libs/basekit/source/SHash.c

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docCopyright("Marc Fauconneau", 2007)
   4 docLicense("BSD revised")
   5 */
   6
   7 #define SHASH_C
   8 #include "SHash.h"
   9 #undef SHASH_C
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <stdio.h>
  13
  14 void SHash_print(SHash* self)
  15 {
  16         printf("self->log2tableSize = %d\n", self->log2tableSize);
  17     printf("self->tableSize = %d\n", self->tableSize);
  18     printf("self->numKeys = %d\n", self->numKeys);
  19
  20     printf("self->mask = %d\n", self->mask);
  21     printf("self->balance = %d\n", self->balance);
  22     printf("self->maxLoops = %d\n", SHash_maxLoops(self));
  23     printf("self->maxKeys = %d\n", SHash_maxKeys(self));
  24
  25         printf("self->nullRecord.key = %d\n", self->nullRecord.key);
  26         printf("self->nullRecord.value = %d\n", self->nullRecord.value);
  27
  28         printf("\nmemory usage : %d bytes\n", SHash_memorySize(self));
  29         printf("\ndensity : %f \n", (self->numKeys*sizeof(SHashRecord))/(double)SHash_memorySize(self));
  30
  31         {
  32                 unsigned int i,j;
  33                 int count[2] = {0,0};
  34
  35                 for (j = 0; j < 2; j ++)
  36                 {
  37                         for (i = 0; i < self->tableSize; i ++)
  38                         {
  39                                 SHashRecord *record = SHASH_RECORDS_AT_(self, j, i);
  40                                 if (NULL == record->key)
  41                                 {
  42                                         if (NULL == record->value)
  43                                                 printf("_");
  44                                         else
  45                                                 printf("!");
  46                                 }
  47                                 else
  48                                 {
  49                                         printf("x");
  50                                         count[j]++;
  51                                 }
  52                         }
  53                         printf("\n");
  54                 }
  55                 printf("balance : %d / %d [%1.3f]\n", count[0], count[1], (count[0]-count[1])/(double)(count[0]+count[1]) );
  56         }
  57 }
  58
  59 void SHash_tableInit_(SHash* self, int log2tableSize)
  60 {
  61         if (log2tableSize > 20)
  62                 printf("ouuups");
  63         self->log2tableSize = log2tableSize;
  64         self->tableSize = 1<<self->log2tableSize;
  65         self->records = (SHashRecord *)io_calloc(1, sizeof(SHashRecord) * self->tableSize * 2);
  66         self->mask = self->tableSize-1;
  67 }
  68
  69 SHash *SHash_new(void)
  70 {
  71         SHash *self = (SHash *)io_calloc(1, sizeof(SHash));
  72         self->numKeys = 0;
  73         SHash_tableInit_(self, 1);
  74         //printf("ok");
  75         return self;
  76 }
  77
  78 SHash *SHash_clone(SHash *self)
  79 {
  80         SHash *child = SHash_new();
  81         SHash_copy_(child, self);
  82         return child;
  83 }
  84
  85 void SHash_free(SHash *self)
  86 {
  87         io_free(self->records);
  88         io_free(self);
  89 }
  90
  91 size_t SHash_memorySize(SHash *self)
  92 {
  93         return sizeof(SHash) + (self->tableSize * 2 * sizeof(SHashRecord));
  94 }
  95
  96 void SHash_compact(SHash *self)
  97 {
  98         printf("need to implement SHash_compact\n");
  99 }
 100
 101 void SHash_copy_(SHash *self, SHash *other)
 102 {
 103         SHashRecord *records = self->records;
 104         memcpy(self, other, sizeof(SHash));
 105         self->records = (SHashRecord *)io_realloc(records, sizeof(SHashRecord) * self->tableSize * 2);
 106         memcpy(self->records, other->records, sizeof(SHashRecord) * self->tableSize * 2);
 107 }
 108
 109 /*      this is where our cuckoo acts :
 110         it kicks records out of nests until it finds an empty nest or gets tired
 111         returns the empty nest if found, or NULL if it is too tired
 112 */
 113 SHashRecord *SHash_cuckoo_(SHash *self, SHashRecord* thisRecord)
 114 {
 115         unsigned int hash;
 116         SHashRecord* record;
 117         record = SHash_recordAt_(self, thisRecord->key);
 118
 119         if (record != &self->nullRecord && NULL == record->key)
 120                 return record;
 121         else
 122         {
 123                 if (SHash_keysAreEqual_(self, thisRecord->key, record->key))
 124                 {
 125                         return record;
 126                 }
 127                 else
 128                 {
 129                         int i;
 130                         // to balance load
 131                         if (self->balance)
 132                         {
 133                                 self->balance = 0;
 134
 135                                 hash = SHash_hash_more(self, SHash_hash(self, thisRecord->key));
 136                                 record = SHASH_RECORDS_AT_HASH_(self, 1, hash);
 137                                 if (NULL == record->key)
 138                                         return record;
 139                                 else
 140                                         SHashRecord_swap(record, thisRecord);
 141
 142                                 if (SHash_keysAreEqual_(self, thisRecord->key, record->key))
 143                                         return record;
 144                         }
 145                         self->balance = 1;
 146
 147                         for (i = 0; i < SHash_maxLoops(self); i++)
 148                         {
 149                                 hash = SHash_hash(self, thisRecord->key);
 150                                 record = SHASH_RECORDS_AT_HASH_(self, 0, hash);
 151                                 if (NULL == record->key)
 152                                         return record;
 153                                 else
 154                                         SHashRecord_swap(record, thisRecord);
 155
 156                                 if (SHash_keysAreEqual_(self, thisRecord->key, record->key))
 157                                         return record;
 158
 159                                 hash = SHash_hash_more(self, SHash_hash(self, thisRecord->key));
 160                                 record = SHASH_RECORDS_AT_HASH_(self, 1, hash);
 161                                 if (NULL == record->key)
 162                                         return record;
 163                                 else
 164                                         SHashRecord_swap(record, thisRecord);
 165
 166                                 if (SHash_keysAreEqual_(self, thisRecord->key, record->key))
 167                                         return record;
 168                         }
 169
 170                         // the cuckoo is tired ^^
 171                         return NULL;
 172                 }
 173         }
 174
 175         return NULL;
 176 }
 177
 178 void SHash_grow(SHash *self)
 179 {
 180         unsigned int oldTableSize = self->tableSize;
 181         SHashRecord* oldRecords = self->records;
 182
 183         self->records = NULL;
 184         while (self->records == NULL)
 185         {
 186                 unsigned int i;
 187
 188                 SHash_tableInit_(self, self->log2tableSize + 1);
 189
 190                 // enumerate old records
 191
 192                 i = 0;
 193                 while (i < oldTableSize*2)
 194                 {
 195                         SHashRecord thisRecord = oldRecords[i];
 196                         i++;
 197
 198                         if (thisRecord.key)
 199                         {
 200                                 SHashRecord *record = SHash_cuckoo_(self, &thisRecord);
 201                                 if (!record) // collision
 202                                 {
 203                                         io_free(self->records);
 204                                         self->records = NULL;
 205                                         break; // grow & rehash
 206                                 }
 207                                 *record = thisRecord;
 208                         }
 209                 }
 210         }
 211         io_free(oldRecords);
 212 }
 213
 214 void SHash_growWithRecord(SHash *self, SHashRecord* thisRecord)
 215 {
 216         // put the value anywhere, SHash_grow will rehash
 217         unsigned int i,j;
 218
 219         for (j = 0; j < 2; j ++)
 220         for (i = 0; i < self->tableSize; i ++)
 221         {
 222                 SHashRecord *record = SHASH_RECORDS_AT_(self, j, i);
 223
 224                 if (record != &self->nullRecord && NULL == record->key)
 225                 {
 226                         *record = *thisRecord;
 227                         self->numKeys ++;
 228                         SHash_grow(self);
 229                         return;
 230                 }
 231         }
 232
 233         // we can never be there
 234         return;
 235 }
 236
 237 void SHash_removeValue_(SHash *self, void *value)
 238 {
 239         SHashRecord *record;
 240         int index = 0;
 241
 242         while (index < self->tableSize*2)
 243         {
 244                 record = self->records + index;
 245                 index ++;
 246
 247                 if (record->key && record->value == value)
 248                 {
 249                         self->numKeys --;
 250                         memset(record, 0, sizeof(SHashRecord));
 251                         return;
 252                 }
 253         }
 254 }
 255
 256 void *SHash_firstKeyForValue_(SHash *self, void *v)
 257 {
 258         unsigned int i,j;
 259
 260         for (j = 0; j < 2; j ++)
 261         for (i = 0; i < self->tableSize; i ++)
 262         {
 263                 SHashRecord *record = SHASH_RECORDS_AT_(self, j, i);
 264
 265                 if (record->key && record->value == v)
 266                         return record->key;
 267         }
 268         return NULL;
 269 }
 270
 271