libcitadel/lib/hash.c

   1 #include <stdint.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 //dbg
   5 #include <stdio.h>
   6 #include "libcitadel.h"
   7 #include "lookup3.h"
   8
   9 typedef struct Payload Payload;
  10
  11 struct Payload {
  12         void *Data;
  13         DeleteHashDataFunc Destructor;
  14 };
  15
  16 struct HashKey {
  17         long Key;
  18         long Position;
  19         char *HashKey;
  20         long HKLen;
  21 };
  22
  23 struct HashList {
  24         Payload **Members;
  25         HashKey **LookupTable;
  26         char **MyKeys;
  27         long nMembersUsed;
  28         long MemberSize;
  29 };
  30
  31 struct HashPos {
  32         long Position;
  33 };
  34
  35 int PrintHash(HashList *Hash)
  36 {
  37         char *foo;
  38         char *bar;
  39         long key;
  40         long i;
  41         if (Hash->MyKeys != NULL)
  42                 free (Hash->MyKeys);
  43
  44         Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nMembersUsed);
  45         printf("----------------------------------\n");
  46         for (i=0; i < Hash->nMembersUsed; i++) {
  47
  48                 if (Hash->LookupTable[i] == NULL)
  49                 {
  50                         foo = "";
  51                         bar = "";
  52                         key = 0;
  53                 }
  54                 else
  55                 {
  56                         key = Hash->LookupTable[i]->Key;
  57                         foo = Hash->LookupTable[i]->HashKey;
  58                         bar = (char*) Hash->Members[Hash->LookupTable[i]->Position]->Data;
  59                 }
  60                 printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' \n", i, key, foo, bar);
  61         }
  62         printf("----------------------------------\n");
  63         return 0;
  64 }
  65
  66
  67
  68 HashList *NewHash(void)
  69 {
  70         HashList *NewList;
  71         NewList = malloc (sizeof(HashList));
  72         memset(NewList, 0, sizeof(HashList));
  73
  74         NewList->Members = malloc(sizeof(Payload*) * 100);
  75         memset(NewList->Members, 0, sizeof(Payload*) * 100);
  76
  77         NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
  78         memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
  79
  80         NewList->MemberSize = 100;
  81
  82         return NewList;
  83 }
  84
  85
  86 static void DeleteHashPayload (Payload *Data)
  87 {
  88         if (Data->Destructor)
  89                 Data->Destructor(Data->Data);
  90         else
  91                 free(Data->Data);
  92 }
  93 void DeleteHash(HashList **Hash)
  94 {
  95         int i;
  96         HashList *FreeMe;
  97
  98         FreeMe = *Hash;
  99         if (FreeMe == NULL)
 100                 return;
 101         for (i=0; i < FreeMe->nMembersUsed; i++)
 102         {
 103                 if (FreeMe->Members[i] != NULL)
 104                 {
 105                         DeleteHashPayload(FreeMe->Members[i]);
 106                         free(FreeMe->Members[i]);
 107                 }
 108                 if (FreeMe->LookupTable[i] != NULL)
 109                 {
 110                         free(FreeMe->LookupTable[i]->HashKey);
 111                         free(FreeMe->LookupTable[i]);
 112                 }
 113         }
 114
 115         free(FreeMe->LookupTable);
 116         free(FreeMe->Members);
 117         if (FreeMe->MyKeys != NULL)
 118                 free(FreeMe->MyKeys);
 119
 120         free (FreeMe);
 121         *Hash = NULL;
 122 }
 123
 124 static void InsertHashItem(HashList *Hash,
 125                            long HashPos,
 126                            long HashBinKey,
 127                            char *HashKeyStr,
 128                            long HKLen,
 129                            void *Data,
 130                            DeleteHashDataFunc Destructor)
 131 {
 132         Payload *NewPayloadItem;
 133         HashKey *NewHashKey;
 134
 135         if (Hash->nMembersUsed >= Hash->MemberSize)
 136         {
 137                 /* Ok, Our space is used up. Double the available space. */
 138                 Payload **NewPayloadArea;
 139                 HashKey **NewTable;
 140
 141                 NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
 142                 memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
 143                 memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
 144
 145                 NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
 146                 memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
 147                 memcpy(NewTable, &Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
 148
 149                 Hash->MemberSize *= 2;
 150         }
 151
 152         NewPayloadItem = (Payload*) malloc (sizeof(Payload));
 153         NewPayloadItem->Data = Data;
 154         NewPayloadItem->Destructor = Destructor;
 155
 156         NewHashKey = (HashKey*) malloc (sizeof(HashKey));
 157         NewHashKey->HashKey = (char *) malloc (HKLen + 1);
 158         NewHashKey->HKLen = HKLen;
 159         memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
 160         NewHashKey->Key = HashBinKey;
 161         NewHashKey->Position = Hash->nMembersUsed;
 162
 163         if ((Hash->nMembersUsed != 0) &&
 164             (HashPos != Hash->nMembersUsed) ) {
 165                 long InsertAt;
 166                 long ItemsAfter;
 167
 168                 ItemsAfter = Hash->nMembersUsed - HashPos;
 169                 InsertAt = HashPos;
 170
 171                 if (ItemsAfter > 0)
 172                 {
 173                         memmove(&Hash->LookupTable[InsertAt + 1],
 174                                 &Hash->LookupTable[InsertAt],
 175                                 ItemsAfter * sizeof(HashKey*));
 176                 }
 177         }
 178
 179         Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
 180         Hash->LookupTable[HashPos] = NewHashKey;
 181         Hash->nMembersUsed++;
 182 }
 183
 184 static long FindInHash(HashList *Hash, long HashBinKey)
 185 {
 186         long SearchPos;
 187         long StepWidth;
 188
 189         SearchPos = Hash->nMembersUsed / 2;
 190         StepWidth = SearchPos / 2;
 191         while ((SearchPos > 0) &&
 192                (SearchPos < Hash->nMembersUsed))
 193         {
 194                 /** Did we find it? */
 195                 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
 196                         return SearchPos;
 197                 }
 198                 /** are we Aproximating in big steps? */
 199                 if (StepWidth > 1){
 200                         if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
 201                                 SearchPos -= StepWidth;
 202                         else
 203                                 SearchPos += StepWidth;
 204                         StepWidth /= 2;
 205                 }
 206                 else { /** We are right next to our target, within 4 positions */
 207                         if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
 208                                 if ((SearchPos > 0) &&
 209                                     (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
 210                                         return SearchPos;
 211                                 SearchPos --;
 212                         }
 213                         else {
 214                                 if ((SearchPos + 1 < Hash->nMembersUsed) &&
 215                                     (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
 216                                         return SearchPos;
 217                                 SearchPos ++;
 218                         }
 219                         StepWidth--;
 220                 }
 221         }
 222         return SearchPos;
 223 }
 224
 225
 226
 227 inline static long CalcHashKey (char *HKey, long HKLen)
 228 {
 229         return hashlittle(HKey, HKLen, 9283457);
 230 }
 231
 232
 233 void Put(HashList *Hash, char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
 234 {
 235         long HashBinKey;
 236         long HashAt;
 237
 238
 239         HashBinKey = CalcHashKey(HKey, HKLen);
 240         HashAt = FindInHash(Hash, HashBinKey);
 241
 242         if (Hash->LookupTable[HashAt] == NULL){
 243                 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
 244         }
 245         else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
 246                 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
 247         }
 248         else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
 249                 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
 250         }
 251         else { /* Ok, we have a colision. replace it. */
 252                 long PayloadPos;
 253
 254                 PayloadPos = Hash->LookupTable[HashAt]->Position;
 255                 DeleteHashPayload(Hash->Members[PayloadPos]);
 256                 Hash->Members[PayloadPos]->Data = Data;
 257                 Hash->Members[PayloadPos]->Destructor = DeleteIt;
 258         }
 259 }
 260
 261 int GetHash(HashList *Hash, char *HKey, long HKLen, void **Data)
 262 {
 263         long HashBinKey;
 264         long HashAt;
 265
 266         HashBinKey = CalcHashKey(HKey, HKLen);
 267         HashAt = FindInHash(Hash, HashBinKey);
 268         if ((HashAt < 0) || (HashAt >= Hash->nMembersUsed)) {
 269                 *Data = NULL;
 270                 return 0;
 271         }
 272         else {
 273                 long MemberPosition;
 274
 275                 MemberPosition = Hash->LookupTable[HashAt]->Position;
 276                 *Data = Hash->Members[MemberPosition]->Data;
 277                 return 1;
 278         }
 279 }
 280
 281 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
 282 {
 283         return 0;
 284 }
 285
 286 int GetHashKeys(HashList *Hash, const char ***List)
 287 {
 288         long i;
 289         if (Hash->MyKeys != NULL)
 290                 free (Hash->MyKeys);
 291
 292         Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nMembersUsed);
 293         for (i=0; i < Hash->nMembersUsed; i++) {
 294
 295                 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
 296         }
 297         *List = Hash->MyKeys;
 298         return Hash->nMembersUsed;
 299 }
 300
 301 HashPos *GetNewHashPos(void)
 302 {
 303         HashPos *Ret;
 304
 305         Ret = (HashPos*)malloc(sizeof(HashPos));
 306         Ret->Position = 0;
 307         return Ret;
 308 }
 309
 310 void DeleteHashPos(HashPos **DelMe)
 311 {
 312         free(*DelMe);
 313         *DelMe = NULL;
 314 }
 315
 316 int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, char **HashKey, void **Data)
 317 {
 318         long PayloadPos;
 319
 320         if (Hash->nMembersUsed <= At->Position)
 321                 return 0;
 322         *HKLen = Hash->LookupTable[At->Position]->HKLen;
 323         *HashKey = Hash->LookupTable[At->Position]->HashKey;
 324         PayloadPos = Hash->LookupTable[At->Position]->Position;
 325         *Data = Hash->Members[PayloadPos]->Data;
 326         At->Position++;
 327         return 1;
 328 }