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 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.
216 void DeleteHash(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 /** now, free our arrays... */
241 free(FreeMe->LookupTable);
242 free(FreeMe->Members);
243 /** did s.b. want an array of our keys? free them. */
244 if (FreeMe->MyKeys != NULL)
245 free(FreeMe->MyKeys);
246 /** buye bye cruel world. */
252 * @brief Private function to increase the hash size.
253 * @param Hash the Hasharray to increase
255 static void IncreaseHashSize(HashList *Hash)
257 /* Ok, Our space is used up. Double the available space. */
258 Payload **NewPayloadArea;
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)))
274 /** double our payload area */
275 NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
276 memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
277 memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
279 Hash->Members = NewPayloadArea;
281 /** double our hashtable area */
282 NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
283 memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
284 memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
285 free(Hash->LookupTable);
286 Hash->LookupTable = NewTable;
288 Hash->MemberSize *= 2;
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.
302 static void InsertHashItem(HashList *Hash,
305 const char *HashKeyStr,
308 DeleteHashDataFunc Destructor)
310 Payload *NewPayloadItem;
316 if (Hash->nMembersUsed >= Hash->MemberSize)
317 IncreaseHashSize (Hash);
319 /** Arrange the payload */
320 NewPayloadItem = (Payload*) malloc (sizeof(Payload));
321 NewPayloadItem->Data = Data;
322 NewPayloadItem->Destructor = Destructor;
323 /** Arrange the hashkey */
324 NewHashKey = (HashKey*) malloc (sizeof(HashKey));
325 NewHashKey->HashKey = (char *) malloc (HKLen + 1);
326 NewHashKey->HKLen = HKLen;
327 memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
328 NewHashKey->Key = HashBinKey;
329 NewHashKey->PL = NewPayloadItem;
330 /** our payload is queued at the end... */
331 NewHashKey->Position = Hash->nMembersUsed;
332 /** but if we should be sorted into a specific place... */
333 if ((Hash->nLookupTableItems != 0) &&
334 (HashPos != Hash->nLookupTableItems) ) {
337 ItemsAfter = Hash->nLookupTableItems - HashPos;
338 /** make space were we can fill us in */
341 memmove(&Hash->LookupTable[HashPos + 1],
342 &Hash->LookupTable[HashPos],
343 ItemsAfter * sizeof(HashKey*));
347 Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
348 Hash->LookupTable[HashPos] = NewHashKey;
349 Hash->nMembersUsed++;
350 Hash->nLookupTableItems++;
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! )
360 static long FindInTaintedHash(HashList *Hash, long HashBinKey)
367 for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
368 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
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! )
381 static long FindInHash(HashList *Hash, long HashBinKey)
390 return FindInTaintedHash(Hash, HashBinKey);
392 SearchPos = Hash->nLookupTableItems / 2;
393 StepWidth = SearchPos / 2;
394 while ((SearchPos > 0) &&
395 (SearchPos < Hash->nLookupTableItems))
397 /** Did we find it? */
398 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
401 /** are we Aproximating in big steps? */
403 if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
404 SearchPos -= StepWidth;
406 SearchPos += StepWidth;
409 else { /** We are right next to our target, within 4 positions */
410 if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
411 if ((SearchPos > 0) &&
412 (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
417 if ((SearchPos + 1 < Hash->nLookupTableItems) &&
418 (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
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
435 long Flathash(const char *str, long len)
437 if (len != sizeof (int))
439 else return *(int*)str;
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
448 long lFlathash(const char *str, long len)
450 if (len != sizeof (long))
452 else return *(long*)str;
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
461 inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
466 if (Hash->Algorithm == NULL)
467 return hashlittle(HKey, HKLen, 9283457);
469 return Hash->Algorithm(HKey, HKLen);
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.
481 void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
489 /** first, find out were we could fit in... */
490 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
491 HashAt = FindInHash(Hash, HashBinKey);
493 if (HashAt >= Hash->MemberSize)
494 IncreaseHashSize (Hash);
496 /** oh, we're brand new... */
497 if (Hash->LookupTable[HashAt] == NULL) {
498 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
499 }/** Insert After? */
500 else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
501 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
502 }/** Insert before? */
503 else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
504 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
506 else { /** Ok, we have a colision. replace it. */
510 PayloadPos = Hash->LookupTable[HashAt]->Position;
511 DeleteHashPayload(Hash->Members[PayloadPos]);
512 Hash->Members[PayloadPos]->Data = Data;
513 Hash->Members[PayloadPos]->Destructor = DeleteIt;
516 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
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.
529 int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data)
541 /** first, find out were we could be... */
542 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
543 HashAt = FindInHash(Hash, HashBinKey);
544 if ((HashAt < 0) || /**< Not found at the lower edge? */
545 (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
546 (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
550 else { /** GOTCHA! */
553 MemberPosition = Hash->LookupTable[HashAt]->Position;
554 *Data = Hash->Members[MemberPosition]->Data;
560 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
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
571 int GetHashKeys(HashList *Hash, char ***List)
576 if (Hash->MyKeys != NULL)
579 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
580 for (i=0; i < Hash->nLookupTableItems; i++) {
582 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
584 *List = (char**)Hash->MyKeys;
585 return Hash->nLookupTableItems;
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
596 HashPos *GetNewHashPos(HashList *Hash, int StepWidth)
600 Ret = (HashPos*)malloc(sizeof(HashPos));
602 Ret->StepWidth = StepWidth;
605 if (Ret->StepWidth < 0) {
606 Ret->Position = Hash->nLookupTableItems - 1;
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
622 int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At)
633 /** first, find out were we could be... */
634 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
635 HashAt = FindInHash(Hash, HashBinKey);
636 if ((HashAt < 0) || /**< Not found at the lower edge? */
637 (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
638 (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
642 At->Position = Hash->LookupTable[HashAt]->Position;
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
652 int DeleteEntryFromHash(HashList *Hash, HashPos *At)
658 /* if lockable, lock here */
659 if ((Hash == NULL) ||
660 (At->Position >= Hash->nLookupTableItems) ||
661 (At->Position < 0) ||
662 (At->Position > Hash->nLookupTableItems))
668 FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
669 Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;
672 /** delete our hashing data */
673 if (Hash->LookupTable[At->Position] != NULL)
675 free(Hash->LookupTable[At->Position]->HashKey);
676 free(Hash->LookupTable[At->Position]);
677 if (At->Position < Hash->nLookupTableItems)
679 memmove(&Hash->LookupTable[At->Position],
680 &Hash->LookupTable[At->Position + 1],
681 (Hash->nLookupTableItems - At->Position - 1) *
684 Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
687 Hash->LookupTable[At->Position] = NULL;
688 Hash->nLookupTableItems--;
693 /** get rid of our payload */
696 DeleteHashPayload(FreeMe);
703 * @brief retrieve the counter from the itteratoor
704 * @param the Iterator to analyze
705 * \returns the n'th hashposition we point at
707 int GetHashPosCounter(HashList *Hash, HashPos *At)
709 if ((Hash == NULL) ||
710 (At->Position >= Hash->nLookupTableItems) ||
711 (At->Position < 0) ||
712 (At->Position > Hash->nLookupTableItems))
718 * @brief frees a linear hash iterator
720 void DeleteHashPos(HashPos **DelMe)
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.
739 int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
743 if ((Hash == NULL) ||
744 (At->Position >= Hash->nLookupTableItems) ||
745 (At->Position < 0) ||
746 (At->Position > Hash->nLookupTableItems))
748 *HKLen = Hash->LookupTable[At->Position]->HKLen;
749 *HashKey = Hash->LookupTable[At->Position]->HashKey;
750 PayloadPos = Hash->LookupTable[At->Position]->Position;
751 *Data = Hash->Members[PayloadPos]->Data;
753 /* Position is NULL-Based, while Stepwidth is not... */
754 if ((At->Position % abs(At->StepWidth)) == 0)
755 At->Position += At->StepWidth;
757 At->Position += ((At->Position) % abs(At->StepWidth)) *
758 (At->StepWidth / abs(At->StepWidth));
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.
771 int GetHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
775 if ((Hash == NULL) ||
776 (At->Position >= Hash->nLookupTableItems) ||
777 (At->Position < 0) ||
778 (At->Position > Hash->nLookupTableItems))
780 *HKLen = Hash->LookupTable[At->Position]->HKLen;
781 *HashKey = Hash->LookupTable[At->Position]->HashKey;
782 PayloadPos = Hash->LookupTable[At->Position]->Position;
783 *Data = Hash->Members[PayloadPos]->Data;
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.
794 int NextHashPos(HashList *Hash, HashPos *At)
796 if ((Hash == NULL) ||
797 (At->Position >= Hash->nLookupTableItems) ||
798 (At->Position < 0) ||
799 (At->Position > Hash->nLookupTableItems))
802 /* Position is NULL-Based, while Stepwidth is not... */
803 if ((At->Position % abs(At->StepWidth)) == 0)
804 At->Position += At->StepWidth;
806 At->Position += ((At->Position) % abs(At->StepWidth)) *
807 (At->StepWidth / abs(At->StepWidth));
808 return !((At->Position >= Hash->nLookupTableItems) ||
809 (At->Position < 0) ||
810 (At->Position > Hash->nLookupTableItems));
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.
822 int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data)
826 if ((Hash == NULL) ||
828 (At >= Hash->nLookupTableItems))
830 *HKLen = Hash->LookupTable[At]->HKLen;
831 *HashKey = Hash->LookupTable[At]->HashKey;
832 PayloadPos = Hash->LookupTable[At]->Position;
833 *Data = Hash->Members[PayloadPos]->Data;
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.
847 long GetHashIDAt(HashList *Hash,long At)
849 if ((Hash == NULL) ||
851 (At > Hash->nLookupTableItems))
854 return Hash->LookupTable[At]->Key;
860 * @brief sorting function for sorting the Hash alphabeticaly by their strings
861 * @param Key1 first item
862 * @param Key2 second item
864 static int SortByKeys(const void *Key1, const void* Key2)
866 HashKey *HKey1, *HKey2;
867 HKey1 = *(HashKey**) Key1;
868 HKey2 = *(HashKey**) Key2;
870 return strcasecmp(HKey1->HashKey, HKey2->HashKey);
874 * @brief sorting function for sorting the Hash alphabeticaly reverse by their strings
875 * @param Key1 first item
876 * @param Key2 second item
878 static int SortByKeysRev(const void *Key1, const void* Key2)
880 HashKey *HKey1, *HKey2;
881 HKey1 = *(HashKey**) Key1;
882 HKey2 = *(HashKey**) Key2;
884 return strcasecmp(HKey2->HashKey, HKey1->HashKey);
888 * @brief sorting function to regain hash-sequence and revert tainted status
889 * @param Key1 first item
890 * @param Key2 second item
892 static int SortByHashKeys(const void *Key1, const void* Key2)
894 HashKey *HKey1, *HKey2;
895 HKey1 = *(HashKey**) Key1;
896 HKey2 = *(HashKey**) Key2;
898 return HKey1->Key > HKey2->Key;
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
909 void SortByHashKey(HashList *Hash, int Order)
911 if (Hash->nLookupTableItems < 2)
913 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*),
914 (Order)?SortByKeys:SortByKeysRev);
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
923 void SortByHashKeyStr(HashList *Hash)
926 if (Hash->nLookupTableItems < 2)
928 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortByHashKeys);
933 * @brief gives user sort routines access to the hash payload
934 * @param Searchentry to retrieve Data to
935 * \returns Data belonging to HashVoid
937 const void *GetSearchPayload(const void *HashVoid)
939 return (*(HashKey**)HashVoid)->PL->Data;
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
948 void SortByPayload(HashList *Hash, CompareFunc SortBy)
950 if (Hash->nLookupTableItems < 2)
952 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortBy);
960 * given you've put char * into your hash as a payload, a sort function might
962 * int SortByChar(const void* First, const void* Second)
965 * a = (char*) GetSearchPayload(First);
966 * b = (char*) GetSearchPayload(Second);
967 * return strcmp (a, b);
973 * Generic function to free a reference.
974 * since a reference actualy isn't needed to be freed, do nothing.
976 void reference_free_handler(void *ptr)
983 * This exposes the hashlittle() function to consumers.
985 int HashLittle(const void *key, size_t length) {
986 return (int)hashlittle(key, length, 1);
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
995 int ParseMSet(MSet **MSetList, StrBuf *MSetStr)
997 const char *POS = NULL, *SetPOS = NULL;
1000 long StartSet, EndSet;
1004 if ((MSetStr == NULL) || (StrLength(MSetStr) == 0))
1007 OneSet = NewStrBufPlain(NULL, StrLength(MSetStr));
1009 ThisMSet = NewHash(0, lFlathash);
1011 *MSetList = (MSet*) ThisMSet;
1013 /* an MSet is a coma separated value list. */
1014 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1018 /* One set may consist of two Numbers: Start + optional End */
1019 StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1020 EndSet = 0; /* no range is our default. */
1021 /* do we have an end (aka range?) */
1022 if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL))
1024 if (*(SetPOS) == '*')
1025 EndSet = LONG_MAX; /* ranges with '*' go until infinity */
1027 /* in other cases, get the EndPoint */
1028 EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1031 pEndSet = (long*) malloc (sizeof(long));
1034 Put(ThisMSet, LKEY(StartSet), pEndSet, NULL);
1035 /* if we don't have another, we're done. */
1036 if (POS == StrBufNOTNULL)
1038 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1040 FreeStrBuf(&OneSet);
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
1050 int IsInMSetList(MSet *MSetList, long MsgNo)
1052 /* basicaly we are a ... */
1053 long MemberPosition;
1054 HashList *Hash = (HashList*) MSetList;
1061 if (Hash->MemberSize == 0)
1063 /** first, find out were we could fit in... */
1064 HashAt = FindInHash(Hash, MsgNo);
1066 /* we're below the first entry, so not found. */
1069 /* upper edge? move to last item */
1070 if (HashAt >= Hash->nMembersUsed)
1071 HashAt = Hash->nMembersUsed - 1;
1072 /* Match? then we got it. */
1073 else if (Hash->LookupTable[HashAt]->Key == MsgNo)
1075 /* One above possible range start? we need to move to the lower one. */
1076 else if ((HashAt > 0) &&
1077 (Hash->LookupTable[HashAt]->Key > MsgNo))
1080 /* Fetch the actual data */
1081 StartAt = Hash->LookupTable[HashAt]->Key;
1082 MemberPosition = Hash->LookupTable[HashAt]->Position;
1083 EndAt = *(long*) Hash->Members[MemberPosition]->Data;
1084 if ((MsgNo >= StartAt) && (EndAt == LONG_MAX))
1089 /* inside of range? */
1090 if ((StartAt <= MsgNo) && (EndAt >= MsgNo))
1097 * \brief frees a mset [redirects to @ref DeleteHash
1098 * \param FreeMe to be free'd
1100 void DeleteMSet(MSet **FreeMe)
1102 DeleteHash((HashList**) FreeMe);