6 #include "libcitadel.h"
9 typedef struct Payload Payload;
13 DeleteHashDataFunc Destructor;
25 HashKey **LookupTable;
35 int PrintHash(HashList *Hash)
41 if (Hash->MyKeys != NULL)
44 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nMembersUsed);
46 printf("----------------------------------\n");
48 for (i=0; i < Hash->nMembersUsed; i++) {
50 if (Hash->LookupTable[i] == NULL)
58 key = Hash->LookupTable[i]->Key;
59 foo = Hash->LookupTable[i]->HashKey;
60 bar = (char*) Hash->Members[Hash->LookupTable[i]->Position]->Data;
63 printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' \n", i, key, foo, bar);
67 printf("----------------------------------\n");
74 HashList *NewHash(void)
77 NewList = malloc (sizeof(HashList));
78 memset(NewList, 0, sizeof(HashList));
80 NewList->Members = malloc(sizeof(Payload*) * 100);
81 memset(NewList->Members, 0, sizeof(Payload*) * 100);
83 NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
84 memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
86 NewList->MemberSize = 100;
92 static void DeleteHashPayload (Payload *Data)
95 Data->Destructor(Data->Data);
99 void DeleteHash(HashList **Hash)
107 for (i=0; i < FreeMe->nMembersUsed; i++)
109 if (FreeMe->Members[i] != NULL)
111 DeleteHashPayload(FreeMe->Members[i]);
112 free(FreeMe->Members[i]);
114 if (FreeMe->LookupTable[i] != NULL)
116 free(FreeMe->LookupTable[i]->HashKey);
117 free(FreeMe->LookupTable[i]);
121 free(FreeMe->LookupTable);
122 free(FreeMe->Members);
123 if (FreeMe->MyKeys != NULL)
124 free(FreeMe->MyKeys);
130 static void InsertHashItem(HashList *Hash,
136 DeleteHashDataFunc Destructor)
138 Payload *NewPayloadItem;
141 if (Hash->nMembersUsed >= Hash->MemberSize)
143 /* Ok, Our space is used up. Double the available space. */
144 Payload **NewPayloadArea;
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);
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);
155 Hash->MemberSize *= 2;
158 NewPayloadItem = (Payload*) malloc (sizeof(Payload));
159 NewPayloadItem->Data = Data;
160 NewPayloadItem->Destructor = Destructor;
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;
169 if ((Hash->nMembersUsed != 0) &&
170 (HashPos != Hash->nMembersUsed) ) {
174 ItemsAfter = Hash->nMembersUsed - HashPos;
179 memmove(&Hash->LookupTable[InsertAt + 1],
180 &Hash->LookupTable[InsertAt],
181 ItemsAfter * sizeof(HashKey*));
185 Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
186 Hash->LookupTable[HashPos] = NewHashKey;
187 Hash->nMembersUsed++;
190 static long FindInHash(HashList *Hash, long HashBinKey)
195 SearchPos = Hash->nMembersUsed / 2;
196 StepWidth = SearchPos / 2;
197 while ((SearchPos > 0) &&
198 (SearchPos < Hash->nMembersUsed))
200 /** Did we find it? */
201 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
204 /** are we Aproximating in big steps? */
206 if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
207 SearchPos -= StepWidth;
209 SearchPos += StepWidth;
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))
220 if ((SearchPos + 1 < Hash->nMembersUsed) &&
221 (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
233 inline static long CalcHashKey (char *HKey, long HKLen)
235 return hashlittle(HKey, HKLen, 9283457);
239 void Put(HashList *Hash, char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
245 HashBinKey = CalcHashKey(HKey, HKLen);
246 HashAt = FindInHash(Hash, HashBinKey);
248 if (Hash->LookupTable[HashAt] == NULL){
249 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
251 else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
252 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
254 else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
255 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
257 else { /* Ok, we have a colision. replace it. */
260 PayloadPos = Hash->LookupTable[HashAt]->Position;
261 DeleteHashPayload(Hash->Members[PayloadPos]);
262 Hash->Members[PayloadPos]->Data = Data;
263 Hash->Members[PayloadPos]->Destructor = DeleteIt;
267 int GetHash(HashList *Hash, char *HKey, long HKLen, void **Data)
272 HashBinKey = CalcHashKey(HKey, HKLen);
273 HashAt = FindInHash(Hash, HashBinKey);
274 if ((HashAt < 0) || (HashAt >= Hash->nMembersUsed)) {
281 MemberPosition = Hash->LookupTable[HashAt]->Position;
282 *Data = Hash->Members[MemberPosition]->Data;
287 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
292 int GetHashKeys(HashList *Hash, const char ***List)
295 if (Hash->MyKeys != NULL)
298 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nMembersUsed);
299 for (i=0; i < Hash->nMembersUsed; i++) {
301 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
303 *List = Hash->MyKeys;
304 return Hash->nMembersUsed;
307 HashPos *GetNewHashPos(void)
311 Ret = (HashPos*)malloc(sizeof(HashPos));
316 void DeleteHashPos(HashPos **DelMe)
322 int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, char **HashKey, void **Data)
326 if (Hash->nMembersUsed <= At->Position)
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;