libs/basekit/source/PHash.c

   1 /*#io
   2 docCopyright("Steve Dekorte", 2002)
   3 docCopyright("Marc Fauconneau", 2007)
   4 docLicense("BSD revised")
   5 */
   6
   7 #define PHASH_C
   8 #include "PHash.h"
   9 #undef PHASH_C
  10 #include <stdlib.h>
  11 #include <string.h>
  12 #include <stdio.h>
  13
  14 void PHash_print(PHash* 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", PHash_maxLoops(self));
  23     printf("self->maxKeys = %d\n", PHash_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", PHash_memorySize(self));
  29         printf("\ndensity : %f \n", (self->numKeys*sizeof(PHashRecord))/(double)PHash_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                                 PHashRecord *record = PHASH_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 PHash_tableInit_(PHash* self, int log2tableSize)
  60 {
  61         if (log2tableSize > 20)
  62                 printf("ouuups");
  63         self->log2tableSize = log2tableSize;
  64         self->tableSize = 1<<self->log2tableSize;
  65         self->records = (PHashRecord *)io_calloc(1, sizeof(PHashRecord) * self->tableSize * 2);
  66         memset(self->records, 0x0, sizeof(PHashRecord) * self->tableSize * 2);
  67         self->mask = self->tableSize-1;
  68 }
  69
  70 PHash *PHash_new(void)
  71 {
  72         PHash *self = (PHash *)io_calloc(1, sizeof(PHash));
  73         memset(self, 0x0, sizeof(PHash));
  74         self->numKeys = 0;
  75         PHash_tableInit_(self, 1);
  76         //printf("ok");
  77         return self;
  78 }
  79
  80 PHash *PHash_clone(PHash *self)
  81 {
  82         PHash *child = PHash_new();
  83         PHash_copy_(child, self);
  84         return child;
  85 }
  86
  87 void PHash_free(PHash *self)
  88 {
  89         io_free(self->records);
  90         io_free(self);
  91 }
  92
  93 size_t PHash_memorySize(PHash *self)
  94 {
  95         return sizeof(PHash) + (self->tableSize * 2 * sizeof(PHashRecord));
  96 }
  97
  98 void PHash_compact(PHash *self)
  99 {
 100         printf("need to implement PHash_compact\n");
 101 }
 102
 103 void PHash_copy_(PHash *self, PHash *other)
 104 {
 105         PHashRecord *records = self->records;
 106         memcpy(self, other, sizeof(PHash));
 107         self->records = (PHashRecord *)io_realloc(records, sizeof(PHashRecord) * self->tableSize * 2);
 108         memcpy(self->records, other->records, sizeof(PHashRecord) * self->tableSize * 2);
 109 }
 110
 111 /*      this is where our cuckoo acts :
 112         it kicks records out of nests until it finds an empty nest or gets tired
 113         returns the empty nest if found, or NULL if it is too tired
 114 */
 115 PHashRecord *PHash_cuckoo_(PHash *self, PHashRecord* thisRecord)
 116 {
 117         unsigned int hash;
 118         PHashRecord* record;
 119         record = PHash_recordAt_(self, thisRecord->key);
 120
 121         if (record != &self->nullRecord && NULL == record->key)
 122                 return record;
 123         else
 124         {
 125                 if (PHashKey_isEqual_(thisRecord->key, record->key))
 126                 {
 127                         return record;
 128                 }
 129                 else
 130                 {
 131                         int i;
 132                         // to balance load
 133                         if (self->balance)
 134                         {
 135                                 self->balance = 0;
 136
 137                                 hash = PHash_hash_more(self, PHash_hash(self, thisRecord->key));
 138                                 record = PHASH_RECORDS_AT_HASH_(self, 1, hash);
 139                                 if (NULL == record->key)
 140                                         return record;
 141                                 else
 142                                         PHashRecord_swap(record, thisRecord);
 143
 144                                 if (PHashKey_isEqual_(thisRecord->key, record->key))
 145                                         return record;
 146                         }
 147                         self->balance = 1;
 148
 149                         for (i = 0; i < PHash_maxLoops(self); i++)
 150                         {
 151                                 hash = PHash_hash(self, thisRecord->key);
 152                                 record = PHASH_RECORDS_AT_HASH_(self, 0, hash);
 153                                 if (NULL == record->key)
 154                                         return record;
 155                                 else
 156                                         PHashRecord_swap(record, thisRecord);
 157
 158                                 if (PHashKey_isEqual_(thisRecord->key, record->key))
 159                                         return record;
 160
 161                                 hash = PHash_hash_more(self, PHash_hash(self, thisRecord->key));
 162                                 record = PHASH_RECORDS_AT_HASH_(self, 1, hash);
 163                                 if (NULL == record->key)
 164                                         return record;
 165                                 else
 166                                         PHashRecord_swap(record, thisRecord);
 167
 168                                 if (PHashKey_isEqual_(thisRecord->key, record->key))
 169                                         return record;
 170                         }
 171
 172                         // the cuckoo is tired ^^
 173                         return NULL;
 174                 }
 175         }
 176
 177         return NULL;
 178 }
 179
 180 void PHash_grow(PHash *self)
 181 {
 182         unsigned int oldTableSize = self->tableSize;
 183         PHashRecord* oldRecords = self->records;
 184
 185         self->records = NULL;
 186         while (self->records == NULL)
 187         {
 188                 unsigned int i;
 189
 190                 PHash_tableInit_(self, self->log2tableSize + 1);
 191
 192                 // enumerate old records
 193
 194                 i = 0;
 195                 while (i < oldTableSize*2)
 196                 {
 197                         PHashRecord thisRecord = oldRecords[i];
 198                         i++;
 199
 200                         if (thisRecord.key)
 201                         {
 202                                 PHashRecord *record = PHash_cuckoo_(self, &thisRecord);
 203                                 if (!record) // collision
 204                                 {
 205                                         io_free(self->records);
 206                                         self->records = NULL;
 207                                         break; // grow & rehash
 208                                 }
 209                                 *record = thisRecord;
 210                         }
 211                 }
 212         }
 213         io_free(oldRecords);
 214 }
 215
 216 void PHash_growWithRecord(PHash *self, PHashRecord* thisRecord)
 217 {
 218         // put the value anywhere, PHash_grow will rehash
 219         unsigned int i,j;
 220
 221         for (j = 0; j < 2; j ++)
 222         for (i = 0; i < self->tableSize; i ++)
 223         {
 224                 PHashRecord *record = PHASH_RECORDS_AT_(self, j, i);
 225
 226                 if (record != &self->nullRecord && NULL == record->key)
 227                 {
 228                         *record = *thisRecord;
 229                         self->numKeys ++;
 230                         PHash_grow(self);
 231                         return;
 232                 }
 233         }
 234
 235         // we can never be there
 236         return;
 237 }
 238
 239 void PHash_removeValue_(PHash *self, void *value)
 240 {
 241         PHashRecord *record;
 242         int index = 0;
 243
 244         while (index < self->tableSize*2)
 245         {
 246                 record = self->records + index;
 247                 index ++;
 248
 249                 if (record->key && record->value == value)
 250                 {
 251                         self->numKeys --;
 252                         memset(record, 0, sizeof(PHashRecord));
 253                         return;
 254                 }
 255         }
 256 }
 257
 258 void *PHash_firstKeyForValue_(PHash *self, void *v)
 259 {
 260         unsigned int i,j;
 261
 262         for (j = 0; j < 2; j ++)
 263         for (i = 0; i < self->tableSize; i ++)
 264         {
 265                 PHashRecord *record = PHASH_RECORDS_AT_(self, j, i);
 266
 267                 if (record->key && record->value == v)
 268                         return record->key;
 269         }
 270         return NULL;
 271 }
 272
 273