libs/basekit/source/SHash.c

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