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