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