7 #include "libcitadel.h"
10 typedef struct Payload Payload;
13 * @brief Hash Payload storage Structure; filled in linear.
16 void *Data; /**< the Data belonging to this storage */
17 DeleteHashDataFunc Destructor; /**< if we want to destroy Data, do it with this function. */
22 * @brief Hash key element; sorted by key
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 */
33 * @brief Hash structure; holds arrays of Hashkey and Payload.
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? */
48 * @brief Anonymous Hash Iterator Object. used for traversing the whole array from outside
51 long Position; /**< Position inside of the hash */
52 int StepWidth; /**< small? big? forward? backward? */
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
64 int PrintHash(HashList *Hash, TransitionFunc Trans, PrintHashDataFunc PrintEntry)
74 for (i=0; i < Hash->nLookupTableItems; i++) {
79 if (Hash->LookupTable[i - 1] == NULL)
82 Previous = Hash->Members[Hash->LookupTable[i-1]->Position]->Data;
84 if (Hash->LookupTable[i] == NULL) {
89 Next = Hash->Members[Hash->LookupTable[i]->Position]->Data;
90 KeyStr = Hash->LookupTable[i]->HashKey;
93 Trans(Previous, Next, i % 2);
94 PrintEntry(KeyStr, Next, i % 2);
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
107 int dbg_PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second)
111 const char *bla = "";
118 if (Hash->MyKeys != NULL)
121 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
123 printf("----------------------------------\n");
125 for (i=0; i < Hash->nLookupTableItems; i++) {
127 if (Hash->LookupTable[i] == NULL)
135 key = Hash->LookupTable[i]->Key;
136 foo = Hash->LookupTable[i]->HashKey;
138 bar = First(Hash->Members[Hash->LookupTable[i]->Position]->Data);
142 bla = Second(Hash->Members[Hash->LookupTable[i]->Position]->Data);
147 printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' ; %s\n", i, key, foo, bar, bla);
151 printf("----------------------------------\n");
158 * @brief instanciate a new hashlist
159 * \returns the newly allocated list.
161 HashList *NewHash(int Uniq, HashFunc F)
164 NewList = malloc (sizeof(HashList));
165 memset(NewList, 0, sizeof(HashList));
167 NewList->Members = malloc(sizeof(Payload*) * 100);
168 memset(NewList->Members, 0, sizeof(Payload*) * 100);
170 NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
171 memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
173 NewList->MemberSize = 100;
174 NewList->tainted = 0;
175 NewList->uniq = Uniq;
176 NewList->Algorithm = F;
181 int GetCount(HashList *Hash)
183 if(Hash==NULL) return 0;
184 return Hash->nLookupTableItems;
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
193 static void DeleteHashPayload (Payload *Data)
195 /** do we have a destructor for our payload? */
196 if (Data->Destructor)
197 Data->Destructor(Data->Data);
203 * @brief Destructor for nested hashes
205 void HDeleteHash(void *vHash)
207 HashList *FreeMe = (HashList*)vHash;
212 * @brief flush the members of a hashlist
213 * Crashing? do 'print *FreeMe->LookupTable[i]'
214 * @param Hash Hash to destroy. Is NULL'ed so you are shure its done.
216 void DeleteHashContent(HashList **Hash)
224 /* even if there are sparse members already deleted... */
225 for (i=0; i < FreeMe->nMembersUsed; i++)
227 /** get rid of our payload */
228 if (FreeMe->Members[i] != NULL)
230 DeleteHashPayload(FreeMe->Members[i]);
231 free(FreeMe->Members[i]);
233 /** delete our hashing data */
234 if (FreeMe->LookupTable[i] != NULL)
236 free(FreeMe->LookupTable[i]->HashKey);
237 free(FreeMe->LookupTable[i]);
240 FreeMe->nMembersUsed = 0;
242 FreeMe->nLookupTableItems = 0;
243 memset(FreeMe->Members, 0, sizeof(Payload*) * FreeMe->MemberSize);
244 memset(FreeMe->LookupTable, 0, sizeof(HashKey*) * FreeMe->MemberSize);
246 /** did s.b. want an array of our keys? free them. */
247 if (FreeMe->MyKeys != NULL)
248 free(FreeMe->MyKeys);
252 * @brief destroy a hashlist and all of its members
253 * Crashing? do 'print *FreeMe->LookupTable[i]'
254 * @param Hash Hash to destroy. Is NULL'ed so you are shure its done.
256 void DeleteHash(HashList **Hash)
263 DeleteHashContent(Hash);
264 /** now, free our arrays... */
265 free(FreeMe->LookupTable);
266 free(FreeMe->Members);
268 /** buye bye cruel world. */
274 * @brief Private function to increase the hash size.
275 * @param Hash the Hasharray to increase
277 static void IncreaseHashSize(HashList *Hash)
279 /* Ok, Our space is used up. Double the available space. */
280 Payload **NewPayloadArea;
286 /** If we grew to much, this might be the place to rehash and shrink again.
287 if ((Hash->NMembersUsed > Hash->nLookupTableItems) &&
288 ((Hash->NMembersUsed - Hash->nLookupTableItems) >
289 (Hash->nLookupTableItems / 10)))
296 /** double our payload area */
297 NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
298 memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
299 memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
301 Hash->Members = NewPayloadArea;
303 /** double our hashtable area */
304 NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
305 memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
306 memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
307 free(Hash->LookupTable);
308 Hash->LookupTable = NewTable;
310 Hash->MemberSize *= 2;
315 * @brief private function to add a new item to / replace an existing in - the hashlist
316 * if the hash list is full, its re-alloced with double size.
317 * \parame Hash our hashlist to manipulate
318 * @param HashPos where should we insert / replace?
319 * @param HashKeyStr the Hash-String
320 * @param HKLen length of HashKeyStr
321 * @param Data your Payload to add
322 * @param Destructor Functionpointer to free Data. if NULL, default free() is used.
324 static void InsertHashItem(HashList *Hash,
327 const char *HashKeyStr,
330 DeleteHashDataFunc Destructor)
332 Payload *NewPayloadItem;
338 if (Hash->nMembersUsed >= Hash->MemberSize)
339 IncreaseHashSize (Hash);
341 /** Arrange the payload */
342 NewPayloadItem = (Payload*) malloc (sizeof(Payload));
343 NewPayloadItem->Data = Data;
344 NewPayloadItem->Destructor = Destructor;
345 /** Arrange the hashkey */
346 NewHashKey = (HashKey*) malloc (sizeof(HashKey));
347 NewHashKey->HashKey = (char *) malloc (HKLen + 1);
348 NewHashKey->HKLen = HKLen;
349 memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
350 NewHashKey->Key = HashBinKey;
351 NewHashKey->PL = NewPayloadItem;
352 /** our payload is queued at the end... */
353 NewHashKey->Position = Hash->nMembersUsed;
354 /** but if we should be sorted into a specific place... */
355 if ((Hash->nLookupTableItems != 0) &&
356 (HashPos != Hash->nLookupTableItems) ) {
359 ItemsAfter = Hash->nLookupTableItems - HashPos;
360 /** make space were we can fill us in */
363 memmove(&Hash->LookupTable[HashPos + 1],
364 &Hash->LookupTable[HashPos],
365 ItemsAfter * sizeof(HashKey*));
369 Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
370 Hash->LookupTable[HashPos] = NewHashKey;
371 Hash->nMembersUsed++;
372 Hash->nLookupTableItems++;
376 * @brief if the user has tainted the hash, but wants to insert / search items by their key
377 * we need to search linear through the array. You have been warned that this will take more time!
378 * @param Hash Our Hash to manipulate
379 * @param HashBinKey the Hash-Number to lookup.
380 * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
382 static long FindInTaintedHash(HashList *Hash, long HashBinKey)
389 for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
390 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
398 * @brief Private function to lookup the Item / the closest position to put it in
399 * @param Hash Our Hash to manipulate
400 * @param HashBinKey the Hash-Number to lookup.
401 * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
403 static long FindInHash(HashList *Hash, long HashBinKey)
412 return FindInTaintedHash(Hash, HashBinKey);
414 SearchPos = Hash->nLookupTableItems / 2;
415 StepWidth = SearchPos / 2;
416 while ((SearchPos > 0) &&
417 (SearchPos < Hash->nLookupTableItems))
419 /** Did we find it? */
420 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
423 /** are we Aproximating in big steps? */
425 if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
426 SearchPos -= StepWidth;
428 SearchPos += StepWidth;
431 else { /** We are right next to our target, within 4 positions */
432 if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
433 if ((SearchPos > 0) &&
434 (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
439 if ((SearchPos + 1 < Hash->nLookupTableItems) &&
440 (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
452 * @brief another hashing algorithm; treat it as just a pointer to int.
453 * @param str Our pointer to the int value
454 * @param len the length of the data pointed to; needs to be sizeof int, else we won't use it!
455 * \returns the calculated hash value
457 long Flathash(const char *str, long len)
459 if (len != sizeof (int))
461 else return *(int*)str;
465 * @brief another hashing algorithm; treat it as just a pointer to long.
466 * @param str Our pointer to the long value
467 * @param len the length of the data pointed to; needs to be sizeof long, else we won't use it!
468 * \returns the calculated hash value
470 long lFlathash(const char *str, long len)
472 if (len != sizeof (long))
474 else return *(long*)str;
478 * @brief private abstract wrapper around the hashing algorithm
479 * @param HKey the hash string
480 * @param HKLen length of HKey
481 * \returns the calculated hash value
483 inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
488 if (Hash->Algorithm == NULL)
489 return hashlittle(HKey, HKLen, 9283457);
491 return Hash->Algorithm(HKey, HKLen);
496 * @brief Add a new / Replace an existing item in the Hash
497 * @param HashList the list to manipulate
498 * @param HKey the hash-string to store Data under
499 * @param HKeyLen Length of HKey
500 * @param Data the payload you want to associate with HKey
501 * @param DeleteIt if not free() should be used to delete Data set to NULL, else DeleteIt is used.
503 void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
511 /** first, find out were we could fit in... */
512 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
513 HashAt = FindInHash(Hash, HashBinKey);
515 if (HashAt >= Hash->MemberSize)
516 IncreaseHashSize (Hash);
518 /** oh, we're brand new... */
519 if (Hash->LookupTable[HashAt] == NULL) {
520 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
521 }/** Insert After? */
522 else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
523 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
524 }/** Insert before? */
525 else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
526 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
528 else { /** Ok, we have a colision. replace it. */
532 PayloadPos = Hash->LookupTable[HashAt]->Position;
533 DeleteHashPayload(Hash->Members[PayloadPos]);
534 Hash->Members[PayloadPos]->Data = Data;
535 Hash->Members[PayloadPos]->Destructor = DeleteIt;
538 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
544 * @brief Lookup the Data associated with HKey
545 * @param Hash the Hashlist to search in
546 * @param HKey the hashkey to look up
547 * @param HKLen length of HKey
548 * @param Data returns the Data associated with HKey
549 * \returns 0 if not found, 1 if.
551 int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data)
563 /** first, find out were we could be... */
564 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
565 HashAt = FindInHash(Hash, HashBinKey);
566 if ((HashAt < 0) || /**< Not found at the lower edge? */
567 (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
568 (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
572 else { /** GOTCHA! */
575 MemberPosition = Hash->LookupTable[HashAt]->Position;
576 *Data = Hash->Members[MemberPosition]->Data;
582 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
588 * @brief get the Keys present in this hash, simila to array_keys() in PHP
589 * Attention: List remains to Hash! don't modify or free it!
590 * @param Hash Your Hashlist to extract the keys from
591 * @param List returns the list of hashkeys stored in Hash
593 int GetHashKeys(HashList *Hash, char ***List)
598 if (Hash->MyKeys != NULL)
601 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
602 for (i=0; i < Hash->nLookupTableItems; i++) {
604 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
606 *List = (char**)Hash->MyKeys;
607 return Hash->nLookupTableItems;
611 * @brief creates a hash-linear iterator object
612 * @param Hash the list we reference
613 * @param in which step width should we iterate?
614 * If negative, the last position matching the
615 * step-raster is provided.
616 * \returns the hash iterator
618 HashPos *GetNewHashPos(HashList *Hash, int StepWidth)
622 Ret = (HashPos*)malloc(sizeof(HashPos));
624 Ret->StepWidth = StepWidth;
627 if (Ret->StepWidth < 0) {
628 Ret->Position = Hash->nLookupTableItems - 1;
637 * @brief Set iterator object to point to key. If not found, don't change iterator
638 * @param Hash the list we reference
639 * @param HKey key to search for
640 * @param HKLen length of key
641 * @param At HashPos to update
642 * \returns 0 if not found
644 int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At)
655 /** first, find out were we could be... */
656 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
657 HashAt = FindInHash(Hash, HashBinKey);
658 if ((HashAt < 0) || /**< Not found at the lower edge? */
659 (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
660 (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
664 At->Position = Hash->LookupTable[HashAt]->Position;
669 * @brief Delete from the Hash the entry at Position
670 * @param Hash the list we reference
671 * @param At the position within the Hash
672 * \returns 0 if not found
674 int DeleteEntryFromHash(HashList *Hash, HashPos *At)
680 /* if lockable, lock here */
681 if ((Hash == NULL) ||
682 (At->Position >= Hash->nLookupTableItems) ||
683 (At->Position < 0) ||
684 (At->Position > Hash->nLookupTableItems))
690 FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
691 Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;
694 /** delete our hashing data */
695 if (Hash->LookupTable[At->Position] != NULL)
697 free(Hash->LookupTable[At->Position]->HashKey);
698 free(Hash->LookupTable[At->Position]);
699 if (At->Position < Hash->nLookupTableItems)
701 memmove(&Hash->LookupTable[At->Position],
702 &Hash->LookupTable[At->Position + 1],
703 (Hash->nLookupTableItems - At->Position - 1) *
706 Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
709 Hash->LookupTable[At->Position] = NULL;
710 Hash->nLookupTableItems--;
715 /** get rid of our payload */
718 DeleteHashPayload(FreeMe);
725 * @brief retrieve the counter from the itteratoor
726 * @param the Iterator to analyze
727 * \returns the n'th hashposition we point at
729 int GetHashPosCounter(HashList *Hash, HashPos *At)
731 if ((Hash == NULL) ||
732 (At->Position >= Hash->nLookupTableItems) ||
733 (At->Position < 0) ||
734 (At->Position > Hash->nLookupTableItems))
740 * @brief frees a linear hash iterator
742 void DeleteHashPos(HashPos **DelMe)
753 * @brief Get the data located where HashPos Iterator points at, and Move HashPos one forward
754 * @param Hash your Hashlist to follow
755 * @param At the position to retrieve the Item from and move forward afterwards
756 * @param HKLen returns Length of Hashkey Returned
757 * @param HashKey returns the Hashkey corrosponding to HashPos
758 * @param Data returns the Data found at HashPos
759 * \returns whether the item was found or not.
761 int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
765 if ((Hash == NULL) ||
766 (At->Position >= Hash->nLookupTableItems) ||
767 (At->Position < 0) ||
768 (At->Position > Hash->nLookupTableItems))
770 *HKLen = Hash->LookupTable[At->Position]->HKLen;
771 *HashKey = Hash->LookupTable[At->Position]->HashKey;
772 PayloadPos = Hash->LookupTable[At->Position]->Position;
773 *Data = Hash->Members[PayloadPos]->Data;
775 /* Position is NULL-Based, while Stepwidth is not... */
776 if ((At->Position % abs(At->StepWidth)) == 0)
777 At->Position += At->StepWidth;
779 At->Position += ((At->Position) % abs(At->StepWidth)) *
780 (At->StepWidth / abs(At->StepWidth));
785 * @brief Get the data located where HashPos Iterator points at
786 * @param Hash your Hashlist to follow
787 * @param At the position retrieve the data from
788 * @param HKLen returns Length of Hashkey Returned
789 * @param HashKey returns the Hashkey corrosponding to HashPos
790 * @param Data returns the Data found at HashPos
791 * \returns whether the item was found or not.
793 int GetHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
797 if ((Hash == NULL) ||
798 (At->Position >= Hash->nLookupTableItems) ||
799 (At->Position < 0) ||
800 (At->Position > Hash->nLookupTableItems))
802 *HKLen = Hash->LookupTable[At->Position]->HKLen;
803 *HashKey = Hash->LookupTable[At->Position]->HashKey;
804 PayloadPos = Hash->LookupTable[At->Position]->Position;
805 *Data = Hash->Members[PayloadPos]->Data;
811 * @brief Move HashPos one forward
812 * @param Hash your Hashlist to follow
813 * @param At the position to move forward
814 * \returns whether there is a next item or not.
816 int NextHashPos(HashList *Hash, HashPos *At)
818 if ((Hash == NULL) ||
819 (At->Position >= Hash->nLookupTableItems) ||
820 (At->Position < 0) ||
821 (At->Position > Hash->nLookupTableItems))
824 /* Position is NULL-Based, while Stepwidth is not... */
825 if ((At->Position % abs(At->StepWidth)) == 0)
826 At->Position += At->StepWidth;
828 At->Position += ((At->Position) % abs(At->StepWidth)) *
829 (At->StepWidth / abs(At->StepWidth));
830 return !((At->Position >= Hash->nLookupTableItems) ||
831 (At->Position < 0) ||
832 (At->Position > Hash->nLookupTableItems));
836 * @brief Get the data located where At points to
837 * note: you should prefer iterator operations instead of using me.
838 * @param Hash your Hashlist peek from
839 * @param HKLen returns Length of Hashkey Returned
840 * @param HashKey returns the Hashkey corrosponding to HashPos
841 * @param Data returns the Data found at HashPos
842 * \returns whether the item was found or not.
844 int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data)
848 if ((Hash == NULL) ||
850 (At >= Hash->nLookupTableItems))
852 *HKLen = Hash->LookupTable[At]->HKLen;
853 *HashKey = Hash->LookupTable[At]->HashKey;
854 PayloadPos = Hash->LookupTable[At]->Position;
855 *Data = Hash->Members[PayloadPos]->Data;
860 * @brief Get the data located where At points to
861 * note: you should prefer iterator operations instead of using me.
862 * @param Hash your Hashlist peek from
863 * @param HKLen returns Length of Hashkey Returned
864 * @param HashKey returns the Hashkey corrosponding to HashPos
865 * @param Data returns the Data found at HashPos
866 * \returns whether the item was found or not.
869 long GetHashIDAt(HashList *Hash,long At)
871 if ((Hash == NULL) ||
873 (At > Hash->nLookupTableItems))
876 return Hash->LookupTable[At]->Key;
882 * @brief sorting function for sorting the Hash alphabeticaly by their strings
883 * @param Key1 first item
884 * @param Key2 second item
886 static int SortByKeys(const void *Key1, const void* Key2)
888 HashKey *HKey1, *HKey2;
889 HKey1 = *(HashKey**) Key1;
890 HKey2 = *(HashKey**) Key2;
892 return strcasecmp(HKey1->HashKey, HKey2->HashKey);
896 * @brief sorting function for sorting the Hash alphabeticaly reverse by their strings
897 * @param Key1 first item
898 * @param Key2 second item
900 static int SortByKeysRev(const void *Key1, const void* Key2)
902 HashKey *HKey1, *HKey2;
903 HKey1 = *(HashKey**) Key1;
904 HKey2 = *(HashKey**) Key2;
906 return strcasecmp(HKey2->HashKey, HKey1->HashKey);
910 * @brief sorting function to regain hash-sequence and revert tainted status
911 * @param Key1 first item
912 * @param Key2 second item
914 static int SortByHashKeys(const void *Key1, const void* Key2)
916 HashKey *HKey1, *HKey2;
917 HKey1 = *(HashKey**) Key1;
918 HKey2 = *(HashKey**) Key2;
920 return HKey1->Key > HKey2->Key;
925 * @brief sort the hash alphabeticaly by their keys.
926 * Caution: This taints the hashlist, so accessing it later
927 * will be significantly slower! You can un-taint it by SortByHashKeyStr
928 * @param Hash the list to sort
929 * @param Order 0/1 Forward/Backward
931 void SortByHashKey(HashList *Hash, int Order)
933 if (Hash->nLookupTableItems < 2)
935 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*),
936 (Order)?SortByKeys:SortByKeysRev);
941 * @brief sort the hash by their keys (so it regains untainted state).
942 * this will result in the sequence the hashing allgorithm produces it by default.
943 * @param Hash the list to sort
945 void SortByHashKeyStr(HashList *Hash)
948 if (Hash->nLookupTableItems < 2)
950 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortByHashKeys);
955 * @brief gives user sort routines access to the hash payload
956 * @param Searchentry to retrieve Data to
957 * \returns Data belonging to HashVoid
959 const void *GetSearchPayload(const void *HashVoid)
961 return (*(HashKey**)HashVoid)->PL->Data;
965 * @brief sort the hash by your sort function. see the following sample.
966 * this will result in the sequence the hashing allgorithm produces it by default.
967 * @param Hash the list to sort
968 * @param SortBy Sortfunction; see below how to implement this
970 void SortByPayload(HashList *Hash, CompareFunc SortBy)
972 if (Hash->nLookupTableItems < 2)
974 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortBy);
982 * given you've put char * into your hash as a payload, a sort function might
984 * int SortByChar(const void* First, const void* Second)
987 * a = (char*) GetSearchPayload(First);
988 * b = (char*) GetSearchPayload(Second);
989 * return strcmp (a, b);
995 * Generic function to free a reference.
996 * since a reference actualy isn't needed to be freed, do nothing.
998 void reference_free_handler(void *ptr)
1005 * This exposes the hashlittle() function to consumers.
1007 int HashLittle(const void *key, size_t length) {
1008 return (int)hashlittle(key, length, 1);
1013 * \brief parses an MSet string into a list for later use
1014 * \param MSetList List to be read from MSetStr
1015 * \param MSetStr String containing the list
1017 int ParseMSet(MSet **MSetList, StrBuf *MSetStr)
1019 const char *POS = NULL, *SetPOS = NULL;
1022 long StartSet, EndSet;
1026 if ((MSetStr == NULL) || (StrLength(MSetStr) == 0))
1029 OneSet = NewStrBufPlain(NULL, StrLength(MSetStr));
1031 ThisMSet = NewHash(0, lFlathash);
1033 *MSetList = (MSet*) ThisMSet;
1035 /* an MSet is a coma separated value list. */
1036 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1040 /* One set may consist of two Numbers: Start + optional End */
1041 StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1042 EndSet = 0; /* no range is our default. */
1043 /* do we have an end (aka range?) */
1044 if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL))
1046 if (*(SetPOS) == '*')
1047 EndSet = LONG_MAX; /* ranges with '*' go until infinity */
1049 /* in other cases, get the EndPoint */
1050 EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1053 pEndSet = (long*) malloc (sizeof(long));
1056 Put(ThisMSet, LKEY(StartSet), pEndSet, NULL);
1057 /* if we don't have another, we're done. */
1058 if (POS == StrBufNOTNULL)
1060 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1062 FreeStrBuf(&OneSet);
1068 * \brief checks whether a message is inside a mset
1069 * \param MSetList List to search for MsgNo
1070 * \param MsgNo number to search in mset
1072 int IsInMSetList(MSet *MSetList, long MsgNo)
1074 /* basicaly we are a ... */
1075 long MemberPosition;
1076 HashList *Hash = (HashList*) MSetList;
1083 if (Hash->MemberSize == 0)
1085 /** first, find out were we could fit in... */
1086 HashAt = FindInHash(Hash, MsgNo);
1088 /* we're below the first entry, so not found. */
1091 /* upper edge? move to last item */
1092 if (HashAt >= Hash->nMembersUsed)
1093 HashAt = Hash->nMembersUsed - 1;
1094 /* Match? then we got it. */
1095 else if (Hash->LookupTable[HashAt]->Key == MsgNo)
1097 /* One above possible range start? we need to move to the lower one. */
1098 else if ((HashAt > 0) &&
1099 (Hash->LookupTable[HashAt]->Key > MsgNo))
1102 /* Fetch the actual data */
1103 StartAt = Hash->LookupTable[HashAt]->Key;
1104 MemberPosition = Hash->LookupTable[HashAt]->Position;
1105 EndAt = *(long*) Hash->Members[MemberPosition]->Data;
1106 if ((MsgNo >= StartAt) && (EndAt == LONG_MAX))
1111 /* inside of range? */
1112 if ((StartAt <= MsgNo) && (EndAt >= MsgNo))
1119 * \brief frees a mset [redirects to @ref DeleteHash
1120 * \param FreeMe to be free'd
1122 void DeleteMSet(MSet **FreeMe)
1124 DeleteHash((HashList**) FreeMe);