Branch data Line data Source code
1 : : #include <stdint.h>
2 : : #include <stdlib.h>
3 : : #include <string.h>
4 : : #include <limits.h>
5 : : //dbg
6 : : #include <stdio.h>
7 : : #include "libcitadel.h"
8 : : #include "lookup3.h"
9 : :
10 : : typedef struct Payload Payload;
11 : :
12 : : /**
13 : : * @brief Hash Payload storage Structure; filled in linear.
14 : : */
15 : : struct Payload {
16 : : void *Data; /**< the Data belonging to this storage */
17 : : DeleteHashDataFunc Destructor; /**< if we want to destroy Data, do it with this function. */
18 : : };
19 : :
20 : :
21 : : /**
22 : : * @brief Hash key element; sorted by key
23 : : */
24 : : struct HashKey {
25 : : long Key; /**< Numeric Hashkey comperator for hash sorting */
26 : : long Position; /**< Pointer to a Payload struct in the Payload Aray */
27 : : char *HashKey; /**< the Plaintext Hashkey */
28 : : long HKLen; /**< length of the Plaintext Hashkey */
29 : : Payload *PL; /**< pointer to our payload for sorting */
30 : : };
31 : :
32 : : /**
33 : : * @brief Hash structure; holds arrays of Hashkey and Payload.
34 : : */
35 : : struct HashList {
36 : : Payload **Members; /**< Our Payload members. This fills up linear */
37 : : HashKey **LookupTable; /**< Hash Lookup table. Elements point to members, and are sorted by their hashvalue */
38 : : char **MyKeys; /**< this keeps the members for a call of GetHashKeys */
39 : : HashFunc Algorithm; /**< should we use an alternating algorithm to calc the hash values? */
40 : : long nMembersUsed; /**< how many pointers inside of the array are used? */
41 : : long nLookupTableItems; /**< how many items of the lookup table are used? */
42 : : long MemberSize; /**< how big is Members and LookupTable? */
43 : : long tainted; /**< if 0, we're hashed, else s.b. else sorted us in his own way. */
44 : : long uniq; /**< are the keys going to be uniq? */
45 : : };
46 : :
47 : : /**
48 : : * @brief Anonymous Hash Iterator Object. used for traversing the whole array from outside
49 : : */
50 : : struct HashPos {
51 : : long Position; /**< Position inside of the hash */
52 : : int StepWidth; /**< small? big? forward? backward? */
53 : : };
54 : :
55 : :
56 : : /**
57 : : * @brief Iterate over the hash and call PrintEntry.
58 : : * @param Hash your Hashlist structure
59 : : * @param Trans is called so you could for example print 'A:' if the next entries are like that.
60 : : * Must be aware to receive NULL in both pointers.
61 : : * @param PrintEntry print entry one by one
62 : : * \returns the number of items printed
63 : : */
64 : 0 : int PrintHash(HashList *Hash, TransitionFunc Trans, PrintHashDataFunc PrintEntry)
65 : : {
66 : : int i;
67 : : void *Previous;
68 : : void *Next;
69 : : const char* KeyStr;
70 : :
71 [ # # ]: 0 : if (Hash == NULL)
72 : 0 : return 0;
73 : :
74 [ # # ]: 0 : for (i=0; i < Hash->nLookupTableItems; i++) {
75 [ # # ]: 0 : if (i==0) {
76 : 0 : Previous = NULL;
77 : : }
78 : : else {
79 [ # # ]: 0 : if (Hash->LookupTable[i - 1] == NULL)
80 : 0 : Previous = NULL;
81 : : else
82 : 0 : Previous = Hash->Members[Hash->LookupTable[i-1]->Position]->Data;
83 : : }
84 [ # # ]: 0 : if (Hash->LookupTable[i] == NULL) {
85 : 0 : KeyStr = "";
86 : 0 : Next = NULL;
87 : : }
88 : : else {
89 : 0 : Next = Hash->Members[Hash->LookupTable[i]->Position]->Data;
90 : 0 : KeyStr = Hash->LookupTable[i]->HashKey;
91 : : }
92 : :
93 : 0 : Trans(Previous, Next, i % 2);
94 : 0 : PrintEntry(KeyStr, Next, i % 2);
95 : : }
96 : 0 : return i;
97 : : }
98 : :
99 : :
100 : : /**
101 : : * @brief verify the contents of a hash list; here for debugging purposes.
102 : : * @param Hash your Hashlist structure
103 : : * @param First Functionpointer to allow you to print your payload
104 : : * @param Second Functionpointer to allow you to print your payload
105 : : * \returns 0
106 : : */
107 : 0 : int dbg_PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second)
108 : : {
109 : : const char *foo;
110 : : const char *bar;
111 : 0 : const char *bla = "";
112 : : long key;
113 : : long i;
114 : :
115 [ # # ]: 0 : if (Hash == NULL)
116 : 0 : return 0;
117 : :
118 [ # # ]: 0 : if (Hash->MyKeys != NULL)
119 : 0 : free (Hash->MyKeys);
120 : :
121 : 0 : Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
122 : : #ifdef DEBUG
123 : 0 : printf("----------------------------------\n");
124 : : #endif
125 [ # # ]: 0 : for (i=0; i < Hash->nLookupTableItems; i++) {
126 : :
127 [ # # ]: 0 : if (Hash->LookupTable[i] == NULL)
128 : : {
129 : 0 : foo = "";
130 : 0 : bar = "";
131 : 0 : key = 0;
132 : : }
133 : : else
134 : : {
135 : 0 : key = Hash->LookupTable[i]->Key;
136 : 0 : foo = Hash->LookupTable[i]->HashKey;
137 [ # # ]: 0 : if (First != NULL)
138 : 0 : bar = First(Hash->Members[Hash->LookupTable[i]->Position]->Data);
139 : : else
140 : 0 : bar = "";
141 [ # # ]: 0 : if (Second != NULL)
142 : 0 : bla = Second(Hash->Members[Hash->LookupTable[i]->Position]->Data);
143 : : else
144 : 0 : bla = "";
145 : : }
146 : : #ifdef DEBUG
147 : 0 : printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' ; %s\n", i, key, foo, bar, bla);
148 : : #endif
149 : : }
150 : : #ifdef DEBUG
151 : 0 : printf("----------------------------------\n");
152 : : #endif
153 : 0 : return 0;
154 : : }
155 : :
156 : :
157 : : /**
158 : : * @brief instanciate a new hashlist
159 : : * \returns the newly allocated list.
160 : : */
161 : 107 : HashList *NewHash(int Uniq, HashFunc F)
162 : : {
163 : : HashList *NewList;
164 : 107 : NewList = malloc (sizeof(HashList));
165 : 107 : memset(NewList, 0, sizeof(HashList));
166 : :
167 : 107 : NewList->Members = malloc(sizeof(Payload*) * 100);
168 : 107 : memset(NewList->Members, 0, sizeof(Payload*) * 100);
169 : :
170 : 107 : NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
171 : 107 : memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
172 : :
173 : 107 : NewList->MemberSize = 100;
174 : 107 : NewList->tainted = 0;
175 : 107 : NewList->uniq = Uniq;
176 : 107 : NewList->Algorithm = F;
177 : :
178 : 107 : return NewList;
179 : : }
180 : :
181 : 43 : int GetCount(HashList *Hash)
182 : : {
183 [ - + ]: 43 : if(Hash==NULL) return 0;
184 : 43 : return Hash->nLookupTableItems;
185 : : }
186 : :
187 : :
188 : : /**
189 : : * @brief private destructor for one hash element.
190 : : * Crashing? go one frame up and do 'print *FreeMe->LookupTable[i]'
191 : : * @param Data an element to free using the user provided destructor, or just plain free
192 : : */
193 : 220 : static void DeleteHashPayload (Payload *Data)
194 : : {
195 : : /** do we have a destructor for our payload? */
196 [ + + ]: 220 : if (Data->Destructor)
197 : 190 : Data->Destructor(Data->Data);
198 : : else
199 : 30 : free(Data->Data);
200 : 220 : }
201 : :
202 : : /**
203 : : * @brief Destructor for nested hashes
204 : : */
205 : 0 : void HDeleteHash(void *vHash)
206 : : {
207 : 0 : HashList *FreeMe = (HashList*)vHash;
208 : 0 : DeleteHash(&FreeMe);
209 : 0 : }
210 : :
211 : : /**
212 : : * @brief destroy a hashlist and all of its members
213 : : * Crashing? do 'print *FreeMe->LookupTable[i]'
214 : : * @param Hash Hash to destroy. Is NULL'ed so you are shure its done.
215 : : */
216 : 235 : void DeleteHash(HashList **Hash)
217 : : {
218 : : int i;
219 : : HashList *FreeMe;
220 : :
221 : 235 : FreeMe = *Hash;
222 [ + + ]: 235 : if (FreeMe == NULL)
223 : 128 : return;
224 : : /* even if there are sparse members already deleted... */
225 [ + + ]: 327 : for (i=0; i < FreeMe->nMembersUsed; i++)
226 : : {
227 : : /** get rid of our payload */
228 [ + + ]: 220 : if (FreeMe->Members[i] != NULL)
229 : : {
230 : 218 : DeleteHashPayload(FreeMe->Members[i]);
231 : 218 : free(FreeMe->Members[i]);
232 : : }
233 : : /** delete our hashing data */
234 [ + + ]: 220 : if (FreeMe->LookupTable[i] != NULL)
235 : : {
236 : 218 : free(FreeMe->LookupTable[i]->HashKey);
237 : 218 : free(FreeMe->LookupTable[i]);
238 : : }
239 : : }
240 : : /** now, free our arrays... */
241 : 107 : free(FreeMe->LookupTable);
242 : 107 : free(FreeMe->Members);
243 : : /** did s.b. want an array of our keys? free them. */
244 [ - + ]: 107 : if (FreeMe->MyKeys != NULL)
245 : 0 : free(FreeMe->MyKeys);
246 : : /** buye bye cruel world. */
247 : 107 : free (FreeMe);
248 : 235 : *Hash = NULL;
249 : : }
250 : :
251 : : /**
252 : : * @brief Private function to increase the hash size.
253 : : * @param Hash the Hasharray to increase
254 : : */
255 : 0 : static void IncreaseHashSize(HashList *Hash)
256 : : {
257 : : /* Ok, Our space is used up. Double the available space. */
258 : : Payload **NewPayloadArea;
259 : : HashKey **NewTable;
260 : :
261 [ # # ]: 0 : if (Hash == NULL)
262 : 0 : return ;
263 : :
264 : : /** If we grew to much, this might be the place to rehash and shrink again.
265 : : if ((Hash->NMembersUsed > Hash->nLookupTableItems) &&
266 : : ((Hash->NMembersUsed - Hash->nLookupTableItems) >
267 : : (Hash->nLookupTableItems / 10)))
268 : : {
269 : :
270 : :
271 : : }
272 : : */
273 : :
274 : : /** double our payload area */
275 : 0 : NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
276 : 0 : memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
277 : 0 : memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
278 : 0 : free(Hash->Members);
279 : 0 : Hash->Members = NewPayloadArea;
280 : :
281 : : /** double our hashtable area */
282 : 0 : NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
283 : 0 : memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
284 : 0 : memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
285 : 0 : free(Hash->LookupTable);
286 : 0 : Hash->LookupTable = NewTable;
287 : :
288 : 0 : Hash->MemberSize *= 2;
289 : : }
290 : :
291 : :
292 : : /**
293 : : * @brief private function to add a new item to / replace an existing in - the hashlist
294 : : * if the hash list is full, its re-alloced with double size.
295 : : * \parame Hash our hashlist to manipulate
296 : : * @param HashPos where should we insert / replace?
297 : : * @param HashKeyStr the Hash-String
298 : : * @param HKLen length of HashKeyStr
299 : : * @param Data your Payload to add
300 : : * @param Destructor Functionpointer to free Data. if NULL, default free() is used.
301 : : */
302 : 220 : static void InsertHashItem(HashList *Hash,
303 : : long HashPos,
304 : : long HashBinKey,
305 : : const char *HashKeyStr,
306 : : long HKLen,
307 : : void *Data,
308 : : DeleteHashDataFunc Destructor)
309 : : {
310 : : Payload *NewPayloadItem;
311 : : HashKey *NewHashKey;
312 : :
313 [ - + ]: 220 : if (Hash == NULL)
314 : 0 : return;
315 : :
316 [ - + ]: 220 : if (Hash->nMembersUsed >= Hash->MemberSize)
317 : 0 : IncreaseHashSize (Hash);
318 : :
319 : : /** Arrange the payload */
320 : 220 : NewPayloadItem = (Payload*) malloc (sizeof(Payload));
321 : 220 : NewPayloadItem->Data = Data;
322 : 220 : NewPayloadItem->Destructor = Destructor;
323 : : /** Arrange the hashkey */
324 : 220 : NewHashKey = (HashKey*) malloc (sizeof(HashKey));
325 : 220 : NewHashKey->HashKey = (char *) malloc (HKLen + 1);
326 : 220 : NewHashKey->HKLen = HKLen;
327 : 220 : memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
328 : 220 : NewHashKey->Key = HashBinKey;
329 : 220 : NewHashKey->PL = NewPayloadItem;
330 : : /** our payload is queued at the end... */
331 : 220 : NewHashKey->Position = Hash->nMembersUsed;
332 : : /** but if we should be sorted into a specific place... */
333 [ + + ][ + + ]: 220 : if ((Hash->nLookupTableItems != 0) &&
334 : 155 : (HashPos != Hash->nLookupTableItems) ) {
335 : : long ItemsAfter;
336 : :
337 : 47 : ItemsAfter = Hash->nLookupTableItems - HashPos;
338 : : /** make space were we can fill us in */
339 [ + - ]: 47 : if (ItemsAfter > 0)
340 : : {
341 : 47 : memmove(&Hash->LookupTable[HashPos + 1],
342 : 47 : &Hash->LookupTable[HashPos],
343 : 47 : ItemsAfter * sizeof(HashKey*));
344 : : }
345 : : }
346 : :
347 : 220 : Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
348 : 220 : Hash->LookupTable[HashPos] = NewHashKey;
349 : 220 : Hash->nMembersUsed++;
350 : 220 : Hash->nLookupTableItems++;
351 : : }
352 : :
353 : : /**
354 : : * @brief if the user has tainted the hash, but wants to insert / search items by their key
355 : : * we need to search linear through the array. You have been warned that this will take more time!
356 : : * @param Hash Our Hash to manipulate
357 : : * @param HashBinKey the Hash-Number to lookup.
358 : : * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
359 : : */
360 : 0 : static long FindInTaintedHash(HashList *Hash, long HashBinKey)
361 : : {
362 : : long SearchPos;
363 : :
364 [ # # ]: 0 : if (Hash == NULL)
365 : 0 : return 0;
366 : :
367 [ # # ]: 0 : for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
368 [ # # ]: 0 : if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
369 : 0 : return SearchPos;
370 : : }
371 : : }
372 : 0 : return SearchPos;
373 : : }
374 : :
375 : : /**
376 : : * @brief Private function to lookup the Item / the closest position to put it in
377 : : * @param Hash Our Hash to manipulate
378 : : * @param HashBinKey the Hash-Number to lookup.
379 : : * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
380 : : */
381 : 302 : static long FindInHash(HashList *Hash, long HashBinKey)
382 : : {
383 : : long SearchPos;
384 : : long StepWidth;
385 : :
386 [ - + ]: 302 : if (Hash == NULL)
387 : 0 : return 0;
388 : :
389 [ - + ]: 302 : if (Hash->tainted)
390 : 0 : return FindInTaintedHash(Hash, HashBinKey);
391 : :
392 : 302 : SearchPos = Hash->nLookupTableItems / 2;
393 : 302 : StepWidth = SearchPos / 2;
394 [ + + ][ + + ]: 428 : while ((SearchPos > 0) &&
395 : 215 : (SearchPos < Hash->nLookupTableItems))
396 : : {
397 : : /** Did we find it? */
398 [ + + ]: 159 : if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
399 : 4 : return SearchPos;
400 : : }
401 : : /** are we Aproximating in big steps? */
402 [ + + ]: 155 : if (StepWidth > 1){
403 [ + + ]: 6 : if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
404 : 1 : SearchPos -= StepWidth;
405 : : else
406 : 5 : SearchPos += StepWidth;
407 : 6 : StepWidth /= 2;
408 : : }
409 : : else { /** We are right next to our target, within 4 positions */
410 [ + + ]: 149 : if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
411 [ + - ][ + + ]: 50 : if ((SearchPos > 0) &&
412 : 50 : (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
413 : 25 : return SearchPos;
414 : 25 : SearchPos --;
415 : : }
416 : : else {
417 [ + + ][ + + ]: 99 : if ((SearchPos + 1 < Hash->nLookupTableItems) &&
418 : 43 : (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
419 : 4 : return SearchPos;
420 : 95 : SearchPos ++;
421 : : }
422 : 120 : StepWidth--;
423 : : }
424 : : }
425 : 302 : return SearchPos;
426 : : }
427 : :
428 : :
429 : : /**
430 : : * @brief another hashing algorithm; treat it as just a pointer to int.
431 : : * @param str Our pointer to the int value
432 : : * @param len the length of the data pointed to; needs to be sizeof int, else we won't use it!
433 : : * \returns the calculated hash value
434 : : */
435 : 65 : long Flathash(const char *str, long len)
436 : : {
437 [ - + ]: 65 : if (len != sizeof (int))
438 : 0 : return 0;
439 : 65 : else return *(int*)str;
440 : : }
441 : :
442 : : /**
443 : : * @brief another hashing algorithm; treat it as just a pointer to long.
444 : : * @param str Our pointer to the long value
445 : : * @param len the length of the data pointed to; needs to be sizeof long, else we won't use it!
446 : : * \returns the calculated hash value
447 : : */
448 : 8 : long lFlathash(const char *str, long len)
449 : : {
450 [ - + ]: 8 : if (len != sizeof (long))
451 : 0 : return 0;
452 : 8 : else return *(long*)str;
453 : : }
454 : :
455 : : /**
456 : : * @brief private abstract wrapper around the hashing algorithm
457 : : * @param HKey the hash string
458 : : * @param HKLen length of HKey
459 : : * \returns the calculated hash value
460 : : */
461 : 270 : inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
462 : : {
463 [ - + ]: 270 : if (Hash == NULL)
464 : 0 : return 0;
465 : :
466 [ + + ]: 270 : if (Hash->Algorithm == NULL)
467 : 197 : return hashlittle(HKey, HKLen, 9283457);
468 : : else
469 : 270 : return Hash->Algorithm(HKey, HKLen);
470 : : }
471 : :
472 : :
473 : : /**
474 : : * @brief Add a new / Replace an existing item in the Hash
475 : : * @param HashList the list to manipulate
476 : : * @param HKey the hash-string to store Data under
477 : : * @param HKeyLen Length of HKey
478 : : * @param Data the payload you want to associate with HKey
479 : : * @param DeleteIt if not free() should be used to delete Data set to NULL, else DeleteIt is used.
480 : : */
481 : 220 : void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
482 : : {
483 : : long HashBinKey;
484 : : long HashAt;
485 : :
486 [ - + ]: 220 : if (Hash == NULL)
487 : 0 : return;
488 : :
489 : : /** first, find out were we could fit in... */
490 : 220 : HashBinKey = CalcHashKey(Hash, HKey, HKLen);
491 : 220 : HashAt = FindInHash(Hash, HashBinKey);
492 : :
493 [ - + ]: 220 : if (HashAt >= Hash->MemberSize)
494 : 0 : IncreaseHashSize (Hash);
495 : :
496 : : /** oh, we're brand new... */
497 [ + + ]: 220 : if (Hash->LookupTable[HashAt] == NULL) {
498 : 118 : InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
499 : : }/** Insert After? */
500 [ + + ]: 102 : else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
501 : 47 : InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
502 : : }/** Insert before? */
503 [ + - ]: 55 : else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
504 : 55 : InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
505 : : }
506 : : else { /** Ok, we have a colision. replace it. */
507 [ # # ]: 0 : if (Hash->uniq) {
508 : : long PayloadPos;
509 : :
510 : 0 : PayloadPos = Hash->LookupTable[HashAt]->Position;
511 : 0 : DeleteHashPayload(Hash->Members[PayloadPos]);
512 : 0 : Hash->Members[PayloadPos]->Data = Data;
513 : 0 : Hash->Members[PayloadPos]->Destructor = DeleteIt;
514 : : }
515 : : else {
516 : 220 : InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
517 : : }
518 : : }
519 : : }
520 : :
521 : : /**
522 : : * @brief Lookup the Data associated with HKey
523 : : * @param Hash the Hashlist to search in
524 : : * @param HKey the hashkey to look up
525 : : * @param HKLen length of HKey
526 : : * @param Data returns the Data associated with HKey
527 : : * \returns 0 if not found, 1 if.
528 : : */
529 : 50 : int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data)
530 : : {
531 : : long HashBinKey;
532 : : long HashAt;
533 : :
534 [ - + ]: 50 : if (Hash == NULL)
535 : 0 : return 0;
536 : :
537 [ - + ]: 50 : if (HKLen <= 0) {
538 : 0 : *Data = NULL;
539 : 0 : return 0;
540 : : }
541 : : /** first, find out were we could be... */
542 : 50 : HashBinKey = CalcHashKey(Hash, HKey, HKLen);
543 : 50 : HashAt = FindInHash(Hash, HashBinKey);
544 [ + - - + ]: 50 : if ((HashAt < 0) || /**< Not found at the lower edge? */
[ # # ]
545 : 50 : (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
546 : 0 : (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
547 : 50 : *Data = NULL;
548 : 50 : return 0;
549 : : }
550 : : else { /** GOTCHA! */
551 : : long MemberPosition;
552 : :
553 : 0 : MemberPosition = Hash->LookupTable[HashAt]->Position;
554 : 0 : *Data = Hash->Members[MemberPosition]->Data;
555 : 50 : return 1;
556 : : }
557 : : }
558 : :
559 : : /* TODO? */
560 : 0 : int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
561 : : {
562 : 0 : return 0;
563 : : }
564 : :
565 : : /**
566 : : * @brief get the Keys present in this hash, simila to array_keys() in PHP
567 : : * Attention: List remains to Hash! don't modify or free it!
568 : : * @param Hash Your Hashlist to extract the keys from
569 : : * @param List returns the list of hashkeys stored in Hash
570 : : */
571 : 0 : int GetHashKeys(HashList *Hash, char ***List)
572 : : {
573 : : long i;
574 [ # # ]: 0 : if (Hash == NULL)
575 : 0 : return 0;
576 [ # # ]: 0 : if (Hash->MyKeys != NULL)
577 : 0 : free (Hash->MyKeys);
578 : :
579 : 0 : Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
580 [ # # ]: 0 : for (i=0; i < Hash->nLookupTableItems; i++) {
581 : :
582 : 0 : Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
583 : : }
584 : 0 : *List = (char**)Hash->MyKeys;
585 : 0 : return Hash->nLookupTableItems;
586 : : }
587 : :
588 : : /**
589 : : * @brief creates a hash-linear iterator object
590 : : * @param Hash the list we reference
591 : : * @param in which step width should we iterate?
592 : : * If negative, the last position matching the
593 : : * step-raster is provided.
594 : : * \returns the hash iterator
595 : : */
596 : 112 : HashPos *GetNewHashPos(HashList *Hash, int StepWidth)
597 : : {
598 : : HashPos *Ret;
599 : :
600 : 112 : Ret = (HashPos*)malloc(sizeof(HashPos));
601 [ + + ]: 112 : if (StepWidth != 0)
602 : 30 : Ret->StepWidth = StepWidth;
603 : : else
604 : 82 : Ret->StepWidth = 1;
605 [ + + ]: 112 : if (Ret->StepWidth < 0) {
606 : 15 : Ret->Position = Hash->nLookupTableItems - 1;
607 : : }
608 : : else {
609 : 97 : Ret->Position = 0;
610 : : }
611 : 112 : return Ret;
612 : : }
613 : :
614 : : /**
615 : : * @brief Set iterator object to point to key. If not found, don't change iterator
616 : : * @param Hash the list we reference
617 : : * @param HKey key to search for
618 : : * @param HKLen length of key
619 : : * @param At HashPos to update
620 : : * \returns 0 if not found
621 : : */
622 : 0 : int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At)
623 : : {
624 : : long HashBinKey;
625 : : long HashAt;
626 : :
627 [ # # ]: 0 : if (Hash == NULL)
628 : 0 : return 0;
629 : :
630 [ # # ]: 0 : if (HKLen <= 0) {
631 : 0 : return 0;
632 : : }
633 : : /** first, find out were we could be... */
634 : 0 : HashBinKey = CalcHashKey(Hash, HKey, HKLen);
635 : 0 : HashAt = FindInHash(Hash, HashBinKey);
636 [ # # # # ]: 0 : if ((HashAt < 0) || /**< Not found at the lower edge? */
[ # # ]
637 : 0 : (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
638 : 0 : (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
639 : 0 : return 0;
640 : : }
641 : : /** GOTCHA! */
642 : 0 : At->Position = Hash->LookupTable[HashAt]->Position;
643 : 0 : return 1;
644 : : }
645 : :
646 : : /**
647 : : * @brief Delete from the Hash the entry at Position
648 : : * @param Hash the list we reference
649 : : * @param At the position within the Hash
650 : : * \returns 0 if not found
651 : : */
652 : 2 : int DeleteEntryFromHash(HashList *Hash, HashPos *At)
653 : : {
654 : : Payload *FreeMe;
655 [ - + ]: 2 : if (Hash == NULL)
656 : 0 : return 0;
657 : :
658 : : /* if lockable, lock here */
659 [ + - ][ + - ]: 2 : if ((Hash == NULL) ||
[ + - ][ - + ]
660 : 2 : (At->Position >= Hash->nLookupTableItems) ||
661 : 2 : (At->Position < 0) ||
662 : 2 : (At->Position > Hash->nLookupTableItems))
663 : : {
664 : : /* unlock... */
665 : 0 : return 0;
666 : : }
667 : :
668 : 2 : FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
669 : 2 : Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;
670 : :
671 : :
672 : : /** delete our hashing data */
673 [ + - ]: 2 : if (Hash->LookupTable[At->Position] != NULL)
674 : : {
675 : 2 : free(Hash->LookupTable[At->Position]->HashKey);
676 : 2 : free(Hash->LookupTable[At->Position]);
677 [ + - ]: 2 : if (At->Position < Hash->nLookupTableItems)
678 : : {
679 : 4 : memmove(&Hash->LookupTable[At->Position],
680 : 2 : &Hash->LookupTable[At->Position + 1],
681 : 2 : (Hash->nLookupTableItems - At->Position - 1) *
682 : : sizeof(HashKey*));
683 : :
684 : 2 : Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
685 : : }
686 : : else
687 : 0 : Hash->LookupTable[At->Position] = NULL;
688 : 2 : Hash->nLookupTableItems--;
689 : : }
690 : : /* unlock... */
691 : :
692 : :
693 : : /** get rid of our payload */
694 [ + - ]: 2 : if (FreeMe != NULL)
695 : : {
696 : 2 : DeleteHashPayload(FreeMe);
697 : 2 : free(FreeMe);
698 : : }
699 : 2 : return 1;
700 : : }
701 : :
702 : : /**
703 : : * @brief retrieve the counter from the itteratoor
704 : : * @param the Iterator to analyze
705 : : * \returns the n'th hashposition we point at
706 : : */
707 : 0 : int GetHashPosCounter(HashList *Hash, HashPos *At)
708 : : {
709 [ # # ][ # # ]: 0 : if ((Hash == NULL) ||
[ # # ][ # # ]
710 : 0 : (At->Position >= Hash->nLookupTableItems) ||
711 : 0 : (At->Position < 0) ||
712 : 0 : (At->Position > Hash->nLookupTableItems))
713 : 0 : return 0;
714 : 0 : return At->Position;
715 : : }
716 : :
717 : : /**
718 : : * @brief frees a linear hash iterator
719 : : */
720 : 110 : void DeleteHashPos(HashPos **DelMe)
721 : : {
722 [ + - ]: 110 : if (*DelMe != NULL)
723 : : {
724 : 110 : free(*DelMe);
725 : 110 : *DelMe = NULL;
726 : : }
727 : 110 : }
728 : :
729 : :
730 : : /**
731 : : * @brief Get the data located where HashPos Iterator points at, and Move HashPos one forward
732 : : * @param Hash your Hashlist to follow
733 : : * @param At the position to retrieve the Item from and move forward afterwards
734 : : * @param HKLen returns Length of Hashkey Returned
735 : : * @param HashKey returns the Hashkey corrosponding to HashPos
736 : : * @param Data returns the Data found at HashPos
737 : : * \returns whether the item was found or not.
738 : : */
739 : 495 : int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
740 : : {
741 : : long PayloadPos;
742 : :
743 [ + - ][ + + ]: 495 : if ((Hash == NULL) ||
[ + + ][ - + ]
744 : 495 : (At->Position >= Hash->nLookupTableItems) ||
745 : 400 : (At->Position < 0) ||
746 : 385 : (At->Position > Hash->nLookupTableItems))
747 : 110 : return 0;
748 : 385 : *HKLen = Hash->LookupTable[At->Position]->HKLen;
749 : 385 : *HashKey = Hash->LookupTable[At->Position]->HashKey;
750 : 385 : PayloadPos = Hash->LookupTable[At->Position]->Position;
751 : 385 : *Data = Hash->Members[PayloadPos]->Data;
752 : :
753 : : /* Position is NULL-Based, while Stepwidth is not... */
754 [ + + ]: 385 : if ((At->Position % abs(At->StepWidth)) == 0)
755 : 380 : At->Position += At->StepWidth;
756 : : else
757 : 5 : At->Position += ((At->Position) % abs(At->StepWidth)) *
758 : 10 : (At->StepWidth / abs(At->StepWidth));
759 : 495 : return 1;
760 : : }
761 : :
762 : : /**
763 : : * @brief Get the data located where HashPos Iterator points at
764 : : * @param Hash your Hashlist to follow
765 : : * @param At the position retrieve the data from
766 : : * @param HKLen returns Length of Hashkey Returned
767 : : * @param HashKey returns the Hashkey corrosponding to HashPos
768 : : * @param Data returns the Data found at HashPos
769 : : * \returns whether the item was found or not.
770 : : */
771 : 0 : int GetHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
772 : : {
773 : : long PayloadPos;
774 : :
775 [ # # ][ # # ]: 0 : if ((Hash == NULL) ||
[ # # ][ # # ]
776 : 0 : (At->Position >= Hash->nLookupTableItems) ||
777 : 0 : (At->Position < 0) ||
778 : 0 : (At->Position > Hash->nLookupTableItems))
779 : 0 : return 0;
780 : 0 : *HKLen = Hash->LookupTable[At->Position]->HKLen;
781 : 0 : *HashKey = Hash->LookupTable[At->Position]->HashKey;
782 : 0 : PayloadPos = Hash->LookupTable[At->Position]->Position;
783 : 0 : *Data = Hash->Members[PayloadPos]->Data;
784 : :
785 : 0 : return 1;
786 : : }
787 : :
788 : : /**
789 : : * @brief Move HashPos one forward
790 : : * @param Hash your Hashlist to follow
791 : : * @param At the position to move forward
792 : : * \returns whether there is a next item or not.
793 : : */
794 : 3 : int NextHashPos(HashList *Hash, HashPos *At)
795 : : {
796 [ + - ][ + - ]: 3 : if ((Hash == NULL) ||
[ + - ][ - + ]
797 : 3 : (At->Position >= Hash->nLookupTableItems) ||
798 : 3 : (At->Position < 0) ||
799 : 3 : (At->Position > Hash->nLookupTableItems))
800 : 0 : return 0;
801 : :
802 : : /* Position is NULL-Based, while Stepwidth is not... */
803 [ + - ]: 3 : if ((At->Position % abs(At->StepWidth)) == 0)
804 : 3 : At->Position += At->StepWidth;
805 : : else
806 : 0 : At->Position += ((At->Position) % abs(At->StepWidth)) *
807 : 0 : (At->StepWidth / abs(At->StepWidth));
808 [ + - ][ + - ]: 3 : return !((At->Position >= Hash->nLookupTableItems) ||
[ + - ]
809 : : (At->Position < 0) ||
810 : : (At->Position > Hash->nLookupTableItems));
811 : : }
812 : :
813 : : /**
814 : : * @brief Get the data located where At points to
815 : : * note: you should prefer iterator operations instead of using me.
816 : : * @param Hash your Hashlist peek from
817 : : * @param HKLen returns Length of Hashkey Returned
818 : : * @param HashKey returns the Hashkey corrosponding to HashPos
819 : : * @param Data returns the Data found at HashPos
820 : : * \returns whether the item was found or not.
821 : : */
822 : 0 : int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data)
823 : : {
824 : : long PayloadPos;
825 : :
826 [ # # ][ # # ]: 0 : if ((Hash == NULL) ||
[ # # ]
827 : : (At < 0) ||
828 : 0 : (At >= Hash->nLookupTableItems))
829 : 0 : return 0;
830 : 0 : *HKLen = Hash->LookupTable[At]->HKLen;
831 : 0 : *HashKey = Hash->LookupTable[At]->HashKey;
832 : 0 : PayloadPos = Hash->LookupTable[At]->Position;
833 : 0 : *Data = Hash->Members[PayloadPos]->Data;
834 : 0 : return 1;
835 : : }
836 : :
837 : : /**
838 : : * @brief Get the data located where At points to
839 : : * note: you should prefer iterator operations instead of using me.
840 : : * @param Hash your Hashlist peek from
841 : : * @param HKLen returns Length of Hashkey Returned
842 : : * @param HashKey returns the Hashkey corrosponding to HashPos
843 : : * @param Data returns the Data found at HashPos
844 : : * \returns whether the item was found or not.
845 : : */
846 : : /*
847 : : long GetHashIDAt(HashList *Hash,long At)
848 : : {
849 : : if ((Hash == NULL) ||
850 : : (At < 0) ||
851 : : (At > Hash->nLookupTableItems))
852 : : return 0;
853 : :
854 : : return Hash->LookupTable[At]->Key;
855 : : }
856 : : */
857 : :
858 : :
859 : : /**
860 : : * @brief sorting function for sorting the Hash alphabeticaly by their strings
861 : : * @param Key1 first item
862 : : * @param Key2 second item
863 : : */
864 : 0 : static int SortByKeys(const void *Key1, const void* Key2)
865 : : {
866 : : HashKey *HKey1, *HKey2;
867 : 0 : HKey1 = *(HashKey**) Key1;
868 : 0 : HKey2 = *(HashKey**) Key2;
869 : :
870 : 0 : return strcasecmp(HKey1->HashKey, HKey2->HashKey);
871 : : }
872 : :
873 : : /**
874 : : * @brief sorting function for sorting the Hash alphabeticaly reverse by their strings
875 : : * @param Key1 first item
876 : : * @param Key2 second item
877 : : */
878 : 0 : static int SortByKeysRev(const void *Key1, const void* Key2)
879 : : {
880 : : HashKey *HKey1, *HKey2;
881 : 0 : HKey1 = *(HashKey**) Key1;
882 : 0 : HKey2 = *(HashKey**) Key2;
883 : :
884 : 0 : return strcasecmp(HKey2->HashKey, HKey1->HashKey);
885 : : }
886 : :
887 : : /**
888 : : * @brief sorting function to regain hash-sequence and revert tainted status
889 : : * @param Key1 first item
890 : : * @param Key2 second item
891 : : */
892 : 0 : static int SortByHashKeys(const void *Key1, const void* Key2)
893 : : {
894 : : HashKey *HKey1, *HKey2;
895 : 0 : HKey1 = *(HashKey**) Key1;
896 : 0 : HKey2 = *(HashKey**) Key2;
897 : :
898 : 0 : return HKey1->Key > HKey2->Key;
899 : : }
900 : :
901 : :
902 : : /**
903 : : * @brief sort the hash alphabeticaly by their keys.
904 : : * Caution: This taints the hashlist, so accessing it later
905 : : * will be significantly slower! You can un-taint it by SortByHashKeyStr
906 : : * @param Hash the list to sort
907 : : * @param Order 0/1 Forward/Backward
908 : : */
909 : 0 : void SortByHashKey(HashList *Hash, int Order)
910 : : {
911 [ # # ]: 0 : if (Hash->nLookupTableItems < 2)
912 : 0 : return;
913 [ # # ]: 0 : qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*),
914 : : (Order)?SortByKeys:SortByKeysRev);
915 : 0 : Hash->tainted = 1;
916 : : }
917 : :
918 : : /**
919 : : * @brief sort the hash by their keys (so it regains untainted state).
920 : : * this will result in the sequence the hashing allgorithm produces it by default.
921 : : * @param Hash the list to sort
922 : : */
923 : 0 : void SortByHashKeyStr(HashList *Hash)
924 : : {
925 : 0 : Hash->tainted = 0;
926 [ # # ]: 0 : if (Hash->nLookupTableItems < 2)
927 : 0 : return;
928 : 0 : qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortByHashKeys);
929 : : }
930 : :
931 : :
932 : : /**
933 : : * @brief gives user sort routines access to the hash payload
934 : : * @param Searchentry to retrieve Data to
935 : : * \returns Data belonging to HashVoid
936 : : */
937 : 0 : const void *GetSearchPayload(const void *HashVoid)
938 : : {
939 : 0 : return (*(HashKey**)HashVoid)->PL->Data;
940 : : }
941 : :
942 : : /**
943 : : * @brief sort the hash by your sort function. see the following sample.
944 : : * this will result in the sequence the hashing allgorithm produces it by default.
945 : : * @param Hash the list to sort
946 : : * @param SortBy Sortfunction; see below how to implement this
947 : : */
948 : 0 : void SortByPayload(HashList *Hash, CompareFunc SortBy)
949 : : {
950 [ # # ]: 0 : if (Hash->nLookupTableItems < 2)
951 : 0 : return;
952 : 0 : qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortBy);
953 : 0 : Hash->tainted = 1;
954 : : }
955 : :
956 : :
957 : :
958 : :
959 : : /**
960 : : * given you've put char * into your hash as a payload, a sort function might
961 : : * look like this:
962 : : * int SortByChar(const void* First, const void* Second)
963 : : * {
964 : : * char *a, *b;
965 : : * a = (char*) GetSearchPayload(First);
966 : : * b = (char*) GetSearchPayload(Second);
967 : : * return strcmp (a, b);
968 : : * }
969 : : */
970 : :
971 : :
972 : : /*
973 : : * Generic function to free a reference.
974 : : * since a reference actualy isn't needed to be freed, do nothing.
975 : : */
976 : 0 : void reference_free_handler(void *ptr)
977 : : {
978 : : return;
979 : : }
980 : :
981 : :
982 : : /*
983 : : * This exposes the hashlittle() function to consumers.
984 : : */
985 : 0 : int HashLittle(const void *key, size_t length) {
986 : 0 : return (int)hashlittle(key, length, 1);
987 : : }
988 : :
989 : :
990 : : /**
991 : : * \brief parses an MSet string into a list for later use
992 : : * \param MSetList List to be read from MSetStr
993 : : * \param MSetStr String containing the list
994 : : */
995 : 4 : int ParseMSet(MSet **MSetList, StrBuf *MSetStr)
996 : : {
997 : 4 : const char *POS = NULL, *SetPOS = NULL;
998 : : StrBuf *OneSet;
999 : : HashList *ThisMSet;
1000 : : long StartSet, EndSet;
1001 : : long *pEndSet;
1002 : :
1003 : 4 : *MSetList = NULL;
1004 [ + - ][ - + ]: 4 : if ((MSetStr == NULL) || (StrLength(MSetStr) == 0))
1005 : 0 : return 0;
1006 : :
1007 : 4 : OneSet = NewStrBufPlain(NULL, StrLength(MSetStr));
1008 : :
1009 : 4 : ThisMSet = NewHash(0, lFlathash);
1010 : :
1011 : 4 : *MSetList = (MSet*) ThisMSet;
1012 : :
1013 : : /* an MSet is a coma separated value list. */
1014 : 4 : StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1015 : : do {
1016 : 8 : SetPOS = NULL;
1017 : :
1018 : : /* One set may consist of two Numbers: Start + optional End */
1019 : 8 : StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1020 : 8 : EndSet = 0; /* no range is our default. */
1021 : : /* do we have an end (aka range?) */
1022 [ + - + + ]: 8 : if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL))
1023 : : {
1024 [ + + ]: 3 : if (*(SetPOS) == '*')
1025 : 1 : EndSet = LONG_MAX; /* ranges with '*' go until infinity */
1026 : : else
1027 : : /* in other cases, get the EndPoint */
1028 : 2 : EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1029 : : }
1030 : :
1031 : 8 : pEndSet = (long*) malloc (sizeof(long));
1032 : 8 : *pEndSet = EndSet;
1033 : :
1034 : 8 : Put(ThisMSet, LKEY(StartSet), pEndSet, NULL);
1035 : : /* if we don't have another, we're done. */
1036 [ + + ]: 8 : if (POS == StrBufNOTNULL)
1037 : : break;
1038 : 4 : StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1039 : 8 : } while (1);
1040 : 4 : FreeStrBuf(&OneSet);
1041 : :
1042 : 4 : return 1;
1043 : : }
1044 : :
1045 : : /**
1046 : : * \brief checks whether a message is inside a mset
1047 : : * \param MSetList List to search for MsgNo
1048 : : * \param MsgNo number to search in mset
1049 : : */
1050 : 32 : int IsInMSetList(MSet *MSetList, long MsgNo)
1051 : : {
1052 : : /* basicaly we are a ... */
1053 : : long MemberPosition;
1054 : 32 : HashList *Hash = (HashList*) MSetList;
1055 : : long HashAt;
1056 : : long EndAt;
1057 : : long StartAt;
1058 : :
1059 [ - + ]: 32 : if (Hash == NULL)
1060 : 0 : return 0;
1061 [ - + ]: 32 : if (Hash->MemberSize == 0)
1062 : 0 : return 0;
1063 : : /** first, find out were we could fit in... */
1064 : 32 : HashAt = FindInHash(Hash, MsgNo);
1065 : :
1066 : : /* we're below the first entry, so not found. */
1067 [ - + ]: 32 : if (HashAt < 0)
1068 : 0 : return 0;
1069 : : /* upper edge? move to last item */
1070 [ + + ]: 32 : if (HashAt >= Hash->nMembersUsed)
1071 : 3 : HashAt = Hash->nMembersUsed - 1;
1072 : : /* Match? then we got it. */
1073 [ + + ]: 29 : else if (Hash->LookupTable[HashAt]->Key == MsgNo)
1074 : 8 : return 1;
1075 : : /* One above possible range start? we need to move to the lower one. */
1076 [ + + ][ + + ]: 21 : else if ((HashAt > 0) &&
1077 : 12 : (Hash->LookupTable[HashAt]->Key > MsgNo))
1078 : 8 : HashAt -=1;
1079 : :
1080 : : /* Fetch the actual data */
1081 : 24 : StartAt = Hash->LookupTable[HashAt]->Key;
1082 : 24 : MemberPosition = Hash->LookupTable[HashAt]->Position;
1083 : 24 : EndAt = *(long*) Hash->Members[MemberPosition]->Data;
1084 [ + + ][ + + ]: 24 : if ((MsgNo >= StartAt) && (EndAt == LONG_MAX))
1085 : 2 : return 1;
1086 : : /* no range? */
1087 [ + + ]: 22 : if (EndAt == 0)
1088 : 10 : return 0;
1089 : : /* inside of range? */
1090 [ + + ][ + + ]: 12 : if ((StartAt <= MsgNo) && (EndAt >= MsgNo))
1091 : 6 : return 1;
1092 : 32 : return 0;
1093 : : }
1094 : :
1095 : :
1096 : : /**
1097 : : * \brief frees a mset [redirects to @ref DeleteHash
1098 : : * \param FreeMe to be free'd
1099 : : */
1100 : 4 : void DeleteMSet(MSet **FreeMe)
1101 : : {
1102 : 4 : DeleteHash((HashList**) FreeMe);
1103 : 4 : }
|
