1 // Copyright (c) 1987-2022 by the citadel.org team
3 // Hashlist is a simple implementation of key value pairs. It doesn't implement collision handling.
4 // the hashing algorithm is pluggeable on creation.
5 // items are added with a function pointer to a destructor; that way complex structures can be added.
6 // if no pointer is given, simply free is used. Use reference_free_handler if you don't want us to free your memory.
8 // This program is open source software. Use, duplication, or disclosure
9 // is subject to the terms of the GNU General Public License, version 3.
16 #include "libcitadel.h"
19 typedef struct Payload Payload;
23 * Hash Payload storage Structure; filled in linear.
26 void *Data; /**< the Data belonging to this storage */
27 DeleteHashDataFunc Destructor; /**< if we want to destroy Data, do it with this function. */
32 * Hash key element; sorted by key
35 long Key; /**< Numeric Hashkey comperator for hash sorting */
36 long Position; /**< Pointer to a Payload struct in the Payload Aray */
37 char *HashKey; /**< the Plaintext Hashkey */
38 long HKLen; /**< length of the Plaintext Hashkey */
39 Payload *PL; /**< pointer to our payload for sorting */
43 * Hash structure; holds arrays of Hashkey and Payload.
46 Payload **Members; /**< Our Payload members. This fills up linear */
47 HashKey **LookupTable; /**< Hash Lookup table. Elements point to members, and are sorted by their hashvalue */
48 char **MyKeys; /**< this keeps the members for a call of GetHashKeys */
49 HashFunc Algorithm; /**< should we use an alternating algorithm to calc the hash values? */
50 long nMembersUsed; /**< how many pointers inside of the array are used? */
51 long nLookupTableItems; /**< how many items of the lookup table are used? */
52 long MemberSize; /**< how big is Members and LookupTable? */
53 long tainted; /**< if 0, we're hashed, else s.b. else sorted us in his own way. */
54 long uniq; /**< are the keys going to be uniq? */
58 * Anonymous Hash Iterator Object. used for traversing the whole array from outside
61 long Position; /**< Position inside of the hash */
62 int StepWidth; /**< small? big? forward? backward? */
67 * Iterate over the hash and call PrintEntry.
68 * Hash your Hashlist structure
69 * Trans is called so you could for example print 'A:' if the next entries are like that.
70 * Must be aware to receive NULL in both pointers.
71 * PrintEntry print entry one by one
72 * returns the number of items printed
74 int PrintHash(HashList *Hash, TransitionFunc Trans, PrintHashDataFunc PrintEntry) {
83 for (i=0; i < Hash->nLookupTableItems; i++) {
88 if (Hash->LookupTable[i - 1] == NULL)
91 Previous = Hash->Members[Hash->LookupTable[i-1]->Position]->Data;
93 if (Hash->LookupTable[i] == NULL) {
98 Next = Hash->Members[Hash->LookupTable[i]->Position]->Data;
99 KeyStr = Hash->LookupTable[i]->HashKey;
102 Trans(Previous, Next, i % 2);
103 PrintEntry(KeyStr, Next, i % 2);
108 const char *dbg_PrintStrBufPayload(const char *Key, void *Item, int Odd) {
109 return ChrPtr((StrBuf*)Item);
113 * verify the contents of a hash list; here for debugging purposes.
114 * Hash your Hashlist structure
115 * First Functionpointer to allow you to print your payload
116 * Second Functionpointer to allow you to print your payload
119 int dbg_PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second) {
123 const char *bla = "";
131 if (Hash->MyKeys != NULL)
134 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
136 printf("----------------------------------\n");
138 for (i=0; i < Hash->nLookupTableItems; i++) {
140 if (Hash->LookupTable[i] == NULL)
151 key = Hash->LookupTable[i]->Key;
152 foo = Hash->LookupTable[i]->HashKey;
158 First(Hash->Members[Hash->LookupTable[i]->Position]->Data);
168 Second(Hash->Members[Hash->LookupTable[i]->Position]->Data);
177 if ((Hash->Algorithm == lFlathash) || (Hash->Algorithm == Flathash)) {
178 printf (" ---- Hashkey[%ld][%ld]: %ld '%s' Value: '%s' ; %s\n", i, key, *(long*) foo, foo, bar, bla);
181 printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' ; %s\n", i, key, foo, bar, bla);
186 printf("----------------------------------\n");
192 int TestValidateHash(HashList *TestHash) {
195 if (TestHash->nMembersUsed != TestHash->nLookupTableItems)
198 if (TestHash->nMembersUsed > TestHash->MemberSize)
201 for (i=0; i < TestHash->nMembersUsed; i++) {
203 if (TestHash->LookupTable[i]->Position > TestHash->nMembersUsed)
206 if (TestHash->Members[TestHash->LookupTable[i]->Position] == NULL)
208 if (TestHash->Members[TestHash->LookupTable[i]->Position]->Data == NULL)
215 * instanciate a new hashlist
216 * returns the newly allocated list.
218 HashList *NewHash(int Uniq, HashFunc F) {
220 NewList = malloc (sizeof(HashList));
223 memset(NewList, 0, sizeof(HashList));
225 NewList->Members = malloc(sizeof(Payload*) * 100);
226 if (NewList->Members == NULL) {
230 memset(NewList->Members, 0, sizeof(Payload*) * 100);
232 NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
233 if (NewList->LookupTable == NULL) {
234 free(NewList->Members);
238 memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
240 NewList->MemberSize = 100;
241 NewList->tainted = 0;
242 NewList->uniq = Uniq;
243 NewList->Algorithm = F;
248 int GetCount(HashList *Hash) {
249 if(Hash==NULL) return 0;
250 return Hash->nLookupTableItems;
255 * private destructor for one hash element.
256 * Crashing? go one frame up and do 'print *FreeMe->LookupTable[i]'
257 * Data an element to free using the user provided destructor, or just plain free
259 static void DeleteHashPayload (Payload *Data) {
260 /** do we have a destructor for our payload? */
261 if (Data->Destructor)
262 Data->Destructor(Data->Data);
268 * Destructor for nested hashes
270 void HDeleteHash(void *vHash) {
271 HashList *FreeMe = (HashList*)vHash;
276 * flush the members of a hashlist
277 * Crashing? do 'print *FreeMe->LookupTable[i]'
278 * Hash Hash to destroy. Is NULL'ed so you are shure its done.
280 void DeleteHashContent(HashList **Hash) {
287 /* even if there are sparse members already deleted... */
288 for (i=0; i < FreeMe->nMembersUsed; i++) {
289 /** get rid of our payload */
290 if (FreeMe->Members[i] != NULL) {
291 DeleteHashPayload(FreeMe->Members[i]);
292 free(FreeMe->Members[i]);
294 /** delete our hashing data */
295 if (FreeMe->LookupTable[i] != NULL) {
296 free(FreeMe->LookupTable[i]->HashKey);
297 free(FreeMe->LookupTable[i]);
300 FreeMe->nMembersUsed = 0;
302 FreeMe->nLookupTableItems = 0;
303 memset(FreeMe->Members, 0, sizeof(Payload*) * FreeMe->MemberSize);
304 memset(FreeMe->LookupTable, 0, sizeof(HashKey*) * FreeMe->MemberSize);
306 // free the array of our keys
307 if (FreeMe->MyKeys != NULL)
308 free(FreeMe->MyKeys);
313 * destroy a hashlist and all of its members
314 * Crashing? do 'print *FreeMe->LookupTable[i]'
315 * Hash Hash to destroy. Is NULL'ed so you are shure its done.
317 void DeleteHash(HashList **Hash) {
323 DeleteHashContent(Hash);
324 /** now, free our arrays... */
325 free(FreeMe->LookupTable);
326 free(FreeMe->Members);
328 /** buye bye cruel world. */
335 * Private function to increase the hash size.
336 * Hash the Hasharray to increase
338 static int IncreaseHashSize(HashList *Hash) {
339 /* Ok, Our space is used up. Double the available space. */
340 Payload **NewPayloadArea;
346 /** If we grew to much, this might be the place to rehash and shrink again.
347 if ((Hash->NMembersUsed > Hash->nLookupTableItems) &&
348 ((Hash->NMembersUsed - Hash->nLookupTableItems) >
349 (Hash->nLookupTableItems / 10)))
356 NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
357 if (NewPayloadArea == NULL)
359 NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
360 if (NewTable == NULL) {
361 free(NewPayloadArea);
365 /** double our payload area */
366 memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
367 memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
369 Hash->Members = NewPayloadArea;
371 /** double our hashtable area */
372 memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
373 memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
374 free(Hash->LookupTable);
375 Hash->LookupTable = NewTable;
377 Hash->MemberSize *= 2;
383 * private function to add a new item to / replace an existing in - the hashlist
384 * if the hash list is full, its re-alloced with double size.
385 * Hash our hashlist to manipulate
386 * HashPos where should we insert / replace?
387 * HashKeyStr the Hash-String
388 * HKLen length of HashKeyStr
389 * Data your Payload to add
390 * Destructor Functionpointer to free Data. if NULL, default free() is used.
392 static int InsertHashItem(HashList *Hash,
395 const char *HashKeyStr,
398 DeleteHashDataFunc Destructor)
400 Payload *NewPayloadItem;
407 if ((Hash->nMembersUsed >= Hash->MemberSize) &&
408 (!IncreaseHashSize (Hash)))
411 NewPayloadItem = (Payload*) malloc (sizeof(Payload));
412 if (NewPayloadItem == NULL)
414 NewHashKey = (HashKey*) malloc (sizeof(HashKey));
415 if (NewHashKey == NULL) {
416 free(NewPayloadItem);
419 HashKeyOrgVal = (char *) malloc (HKLen + 1);
420 if (HashKeyOrgVal == NULL) {
422 free(NewPayloadItem);
427 /** Arrange the payload */
428 NewPayloadItem->Data = Data;
429 NewPayloadItem->Destructor = Destructor;
430 /** Arrange the hashkey */
431 NewHashKey->HKLen = HKLen;
432 NewHashKey->HashKey = HashKeyOrgVal;
433 memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
434 NewHashKey->Key = HashBinKey;
435 NewHashKey->PL = NewPayloadItem;
436 /** our payload is queued at the end... */
437 NewHashKey->Position = Hash->nMembersUsed;
438 /** but if we should be sorted into a specific place... */
439 if ((Hash->nLookupTableItems != 0) &&
440 (HashPos != Hash->nLookupTableItems) ) {
443 ItemsAfter = Hash->nLookupTableItems - HashPos;
444 /** make space were we can fill us in */
445 if (ItemsAfter > 0) {
446 memmove(&Hash->LookupTable[HashPos + 1], &Hash->LookupTable[HashPos], ItemsAfter * sizeof(HashKey*));
450 Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
451 Hash->LookupTable[HashPos] = NewHashKey;
452 Hash->nMembersUsed++;
453 Hash->nLookupTableItems++;
458 * if the user has tainted the hash, but wants to insert / search items by their key
459 * we need to search linear through the array. You have been warned that this will take more time!
460 * Hash Our Hash to manipulate
461 * HashBinKey the Hash-Number to lookup.
462 * returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
464 static long FindInTaintedHash(HashList *Hash, long HashBinKey) {
470 for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
471 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
479 * Private function to lookup the Item / the closest position to put it in
480 * Hash Our Hash to manipulate
481 * HashBinKey the Hash-Number to lookup.
482 * returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
484 static long FindInHash(HashList *Hash, long HashBinKey) {
492 return FindInTaintedHash(Hash, HashBinKey);
494 SearchPos = Hash->nLookupTableItems / 2;
495 StepWidth = SearchPos / 2;
496 while ((SearchPos > 0) && (SearchPos < Hash->nLookupTableItems)) {
497 /** Did we find it? */
498 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
501 /** are we Aproximating in big steps? */
503 if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
504 SearchPos -= StepWidth;
506 SearchPos += StepWidth;
509 else { /** We are right next to our target, within 4 positions */
510 if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
511 if ((SearchPos > 0) && (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
516 if ((SearchPos + 1 < Hash->nLookupTableItems) && (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey)) {
529 * another hashing algorithm; treat it as just a pointer to int.
530 * str Our pointer to the int value
531 * len the length of the data pointed to; needs to be sizeof int, else we won't use it!
532 * returns the calculated hash value
534 long Flathash(const char *str, long len) {
535 if (len != sizeof (int)) {
542 else return *(int*)str;
546 * another hashing algorithm; treat it as just a pointer to long.
547 * str Our pointer to the long value
548 * len the length of the data pointed to; needs to be sizeof long, else we won't use it!
549 * returns the calculated hash value
551 long lFlathash(const char *str, long len) {
552 if (len != sizeof (long)) {
559 else return *(long*)str;
563 * another hashing algorithm; accepts exactly 4 characters, convert it to a hash key.
564 * str Our pointer to the long value
565 * len the length of the data pointed to; needs to be sizeof long, else we won't use it!
566 * returns the calculated hash value
568 long FourHash(const char *key, long length) {
571 const unsigned char *ptr = (const unsigned char*)key;
573 for (i = 0; i < 4; i++, ptr ++)
584 * private abstract wrapper around the hashing algorithm
585 * HKey the hash string
586 * HKLen length of HKey
587 * returns the calculated hash value
589 inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen) {
593 if (Hash->Algorithm == NULL)
594 return hashlittle(HKey, HKLen, 9283457);
596 return Hash->Algorithm(HKey, HKLen);
601 * Add a new / Replace an existing item in the Hash
602 * Hash the list to manipulate
603 * HKey the hash-string to store Data under
604 * HKLen Length of HKey
605 * Data the payload you want to associate with HKey
606 * DeleteIt if not free() should be used to delete Data set to NULL, else DeleteIt is used.
608 void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt) {
615 /** first, find out were we could fit in... */
616 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
617 HashAt = FindInHash(Hash, HashBinKey);
619 if ((HashAt >= Hash->MemberSize) &&
620 (!IncreaseHashSize (Hash)))
623 /** oh, we're brand new... */
624 if (Hash->LookupTable[HashAt] == NULL) {
625 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
626 }/** Insert Before? */
627 else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
628 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
629 }/** Insert After? */
630 else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
631 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
633 else { /** Ok, we have a colision. replace it. */
637 PayloadPos = Hash->LookupTable[HashAt]->Position;
638 DeleteHashPayload(Hash->Members[PayloadPos]);
639 Hash->Members[PayloadPos]->Data = Data;
640 Hash->Members[PayloadPos]->Destructor = DeleteIt;
643 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
649 * Lookup the Data associated with HKey
650 * Hash the Hashlist to search in
651 * HKey the hashkey to look up
652 * HKLen length of HKey
653 * Data returns the Data associated with HKey
654 * returns 0 if not found, 1 if.
656 int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data) {
667 /** first, find out were we could be... */
668 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
669 HashAt = FindInHash(Hash, HashBinKey);
670 if ((HashAt < 0) || /**< Not found at the lower edge? */
671 (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
672 (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
676 else { /** GOTCHA! */
679 MemberPosition = Hash->LookupTable[HashAt]->Position;
680 *Data = Hash->Members[MemberPosition]->Data;
686 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload) {
691 * get the Keys present in this hash, similar to array_keys() in PHP
692 * Attention: List remains to Hash! don't modify or free it!
693 * Hash Your Hashlist to extract the keys from
694 * List returns the list of hashkeys stored in Hash
696 int GetHashKeys(HashList *Hash, char ***List) {
702 if (Hash->MyKeys != NULL)
705 Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
706 if (Hash->MyKeys == NULL)
709 for (i=0; i < Hash->nLookupTableItems; i++)
711 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
713 *List = (char**)Hash->MyKeys;
714 return Hash->nLookupTableItems;
718 * creates a hash-linear iterator object
719 * Hash the list we reference
720 * StepWidth in which step width should we iterate?
721 * If negative, the last position matching the
722 * step-raster is provided.
723 * returns the hash iterator
725 HashPos *GetNewHashPos(const HashList *Hash, int StepWidth) {
728 Ret = (HashPos*)malloc(sizeof(HashPos));
733 Ret->StepWidth = StepWidth;
736 if (Ret->StepWidth < 0) {
737 Ret->Position = Hash->nLookupTableItems - 1;
746 * resets a hash-linear iterator object
747 * Hash the list we reference
748 * StepWidth in which step width should we iterate?
749 * it the iterator object to manipulate
750 * If negative, the last position matching the
751 * step-raster is provided.
752 * returns the hash iterator
754 void RewindHashPos(const HashList *Hash, HashPos *it, int StepWidth) {
756 it->StepWidth = StepWidth;
759 if (it->StepWidth < 0) {
760 it->Position = Hash->nLookupTableItems - 1;
768 * Set iterator object to point to key. If not found, don't change iterator
769 * Hash the list we reference
770 * HKey key to search for
771 * HKLen length of key
772 * At HashPos to update
773 * returns 0 if not found
775 int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At) {
785 /** first, find out were we could be... */
786 HashBinKey = CalcHashKey(Hash, HKey, HKLen);
787 HashAt = FindInHash(Hash, HashBinKey);
788 if ((HashAt < 0) || /**< Not found at the lower edge? */
789 (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
790 (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
794 At->Position = HashAt;
799 * Delete from the Hash the entry at Position
800 * Hash the list we reference
801 * At the position within the Hash
802 * returns 0 if not found
804 int DeleteEntryFromHash(HashList *Hash, HashPos *At) {
809 /* if lockable, lock here */
810 if ((Hash == NULL) ||
811 (At->Position >= Hash->nLookupTableItems) ||
812 (At->Position < 0) ||
813 (At->Position > Hash->nLookupTableItems))
819 FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
820 Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;
823 /** delete our hashing data */
824 if (Hash->LookupTable[At->Position] != NULL) {
825 free(Hash->LookupTable[At->Position]->HashKey);
826 free(Hash->LookupTable[At->Position]);
827 if (At->Position < Hash->nLookupTableItems) {
828 memmove(&Hash->LookupTable[At->Position],
829 &Hash->LookupTable[At->Position + 1],
830 (Hash->nLookupTableItems - At->Position - 1) *
833 Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
836 Hash->LookupTable[At->Position] = NULL;
837 Hash->nLookupTableItems--;
842 /** get rid of our payload */
843 if (FreeMe != NULL) {
844 DeleteHashPayload(FreeMe);
851 * retrieve the counter from the itteratoor
853 * At the Iterator to analyze
854 * returns the n'th hashposition we point at
856 int GetHashPosCounter(HashList *Hash, HashPos *At) {
857 if ((Hash == NULL) ||
858 (At->Position >= Hash->nLookupTableItems) ||
859 (At->Position < 0) ||
860 (At->Position > Hash->nLookupTableItems))
866 * frees a linear hash iterator
868 void DeleteHashPos(HashPos **DelMe) {
869 if (*DelMe != NULL) {
877 * Get the data located where HashPos Iterator points at, and Move HashPos one forward
878 * Hash your Hashlist to follow
879 * At the position to retrieve the Item from and move forward afterwards
880 * HKLen returns Length of Hashkey Returned
881 * HashKey returns the Hashkey corrosponding to HashPos
882 * Data returns the Data found at HashPos
883 * returns whether the item was found or not.
885 int GetNextHashPos(const HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data) {
888 if ((Hash == NULL) ||
889 (At->Position >= Hash->nLookupTableItems) ||
890 (At->Position < 0) ||
891 (At->Position > Hash->nLookupTableItems))
893 *HKLen = Hash->LookupTable[At->Position]->HKLen;
894 *HashKey = Hash->LookupTable[At->Position]->HashKey;
895 PayloadPos = Hash->LookupTable[At->Position]->Position;
896 *Data = Hash->Members[PayloadPos]->Data;
898 /* Position is NULL-Based, while Stepwidth is not... */
899 if ((At->Position % abs(At->StepWidth)) == 0)
900 At->Position += At->StepWidth;
902 At->Position += ((At->Position) % abs(At->StepWidth)) *
903 (At->StepWidth / abs(At->StepWidth));
908 * Get the data located where HashPos Iterator points at
909 * Hash your Hashlist to follow
910 * At the position retrieve the data from
911 * HKLen returns Length of Hashkey Returned
912 * HashKey returns the Hashkey corrosponding to HashPos
913 * Data returns the Data found at HashPos
914 * returns whether the item was found or not.
916 int GetHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data) {
919 if ((Hash == NULL) ||
920 (At->Position >= Hash->nLookupTableItems) ||
921 (At->Position < 0) ||
922 (At->Position > Hash->nLookupTableItems))
924 *HKLen = Hash->LookupTable[At->Position]->HKLen;
925 *HashKey = Hash->LookupTable[At->Position]->HashKey;
926 PayloadPos = Hash->LookupTable[At->Position]->Position;
927 *Data = Hash->Members[PayloadPos]->Data;
933 * Move HashPos one forward
934 * Hash your Hashlist to follow
935 * At the position to move forward
936 * returns whether there is a next item or not.
938 int NextHashPos(HashList *Hash, HashPos *At) {
939 if ((Hash == NULL) ||
940 (At->Position >= Hash->nLookupTableItems) ||
941 (At->Position < 0) ||
942 (At->Position > Hash->nLookupTableItems))
945 /* Position is NULL-Based, while Stepwidth is not... */
946 if ((At->Position % abs(At->StepWidth)) == 0)
947 At->Position += At->StepWidth;
949 At->Position += ((At->Position) % abs(At->StepWidth)) *
950 (At->StepWidth / abs(At->StepWidth));
951 return !((At->Position >= Hash->nLookupTableItems) ||
952 (At->Position < 0) ||
953 (At->Position > Hash->nLookupTableItems));
957 * Get the data located where At points to
958 * note: you should prefer iterator operations instead of using me.
959 * Hash your Hashlist peek from
960 * At get the item in the position At.
961 * HKLen returns Length of Hashkey Returned
962 * HashKey returns the Hashkey corrosponding to HashPos
963 * Data returns the Data found at HashPos
964 * returns whether the item was found or not.
966 int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data) {
969 if ((Hash == NULL) ||
971 (At >= Hash->nLookupTableItems))
973 *HKLen = Hash->LookupTable[At]->HKLen;
974 *HashKey = Hash->LookupTable[At]->HashKey;
975 PayloadPos = Hash->LookupTable[At]->Position;
976 *Data = Hash->Members[PayloadPos]->Data;
981 * Get the data located where At points to
982 * note: you should prefer iterator operations instead of using me.
983 * Hash your Hashlist peek from
984 * HKLen returns Length of Hashkey Returned
985 * HashKey returns the Hashkey corrosponding to HashPos
986 * Data returns the Data found at HashPos
987 * returns whether the item was found or not.
990 long GetHashIDAt(HashList *Hash,long At)
992 if ((Hash == NULL) ||
994 (At > Hash->nLookupTableItems))
997 return Hash->LookupTable[At]->Key;
1003 * sorting function for sorting the Hash alphabeticaly by their strings
1007 static int SortByKeys(const void *Key1, const void* Key2) {
1008 HashKey *HKey1, *HKey2;
1009 HKey1 = *(HashKey**) Key1;
1010 HKey2 = *(HashKey**) Key2;
1012 return strcasecmp(HKey1->HashKey, HKey2->HashKey);
1016 * sorting function for sorting the Hash alphabeticaly reverse by their strings
1020 static int SortByKeysRev(const void *Key1, const void* Key2) {
1021 HashKey *HKey1, *HKey2;
1022 HKey1 = *(HashKey**) Key1;
1023 HKey2 = *(HashKey**) Key2;
1025 return strcasecmp(HKey2->HashKey, HKey1->HashKey);
1029 * sorting function to regain hash-sequence and revert tainted status
1033 static int SortByHashKeys(const void *Key1, const void* Key2) {
1034 HashKey *HKey1, *HKey2;
1035 HKey1 = *(HashKey**) Key1;
1036 HKey2 = *(HashKey**) Key2;
1038 return HKey1->Key > HKey2->Key;
1043 * sort the hash alphabeticaly by their keys.
1044 * Caution: This taints the hashlist, so accessing it later
1045 * will be significantly slower! You can un-taint it by SortByHashKeyStr
1046 * Hash the list to sort
1047 * Order 0/1 Forward/Backward
1049 void SortByHashKey(HashList *Hash, int Order) {
1050 if (Hash->nLookupTableItems < 2)
1052 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*),
1053 (Order)?SortByKeys:SortByKeysRev);
1058 * sort the hash by their keys (so it regains untainted state).
1059 * this will result in the sequence the hashing allgorithm produces it by default.
1060 * Hash the list to sort
1062 void SortByHashKeyStr(HashList *Hash) {
1064 if (Hash->nLookupTableItems < 2)
1066 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortByHashKeys);
1071 * gives user sort routines access to the hash payload
1072 * HashVoid to retrieve Data to
1073 * returns Data belonging to HashVoid
1075 const void *GetSearchPayload(const void *HashVoid) {
1076 return (*(HashKey**)HashVoid)->PL->Data;
1080 * sort the hash by your sort function. see the following sample.
1081 * this will result in the sequence the hashing allgorithm produces it by default.
1082 * Hash the list to sort
1083 * SortBy Sortfunction; see below how to implement this
1085 void SortByPayload(HashList *Hash, CompareFunc SortBy) {
1086 if (Hash->nLookupTableItems < 2) {
1089 qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortBy);
1097 * given you've put char * into your hash as a payload, a sort function might
1099 * int SortByChar(const void* First, const void* Second)
1102 * a = (char*) GetSearchPayload(First);
1103 * b = (char*) GetSearchPayload(Second);
1104 * return strcmp (a, b);
1110 * Generic function to free a reference.
1111 * since a reference actualy isn't needed to be freed, do nothing.
1113 void reference_free_handler(void *ptr) {
1119 * This exposes the hashlittle() function to consumers.
1121 int HashLittle(const void *key, size_t length) {
1122 return (int)hashlittle(key, length, 1);
1127 * parses an MSet string into a list for later use
1128 * MSetList List to be read from MSetStr
1129 * MSetStr String containing the list
1131 int ParseMSet(MSet **MSetList, StrBuf *MSetStr) {
1132 const char *POS = NULL, *SetPOS = NULL;
1135 long StartSet, EndSet;
1139 if ((MSetStr == NULL) || (StrLength(MSetStr) == 0))
1142 OneSet = NewStrBufPlain(NULL, StrLength(MSetStr));
1146 ThisMSet = NewHash(0, lFlathash);
1147 if (ThisMSet == NULL) {
1148 FreeStrBuf(&OneSet);
1152 *MSetList = (MSet*) ThisMSet;
1154 /* an MSet is a coma separated value list. */
1155 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1159 /* One set may consist of two Numbers: Start + optional End */
1160 StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1161 EndSet = 0; /* no range is our default. */
1162 /* do we have an end (aka range?) */
1163 if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL)) {
1164 if (*(SetPOS) == '*')
1165 EndSet = LONG_MAX; /* ranges with '*' go until infinity */
1167 /* in other cases, get the EndPoint */
1168 EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1171 pEndSet = (long*) malloc (sizeof(long));
1172 if (pEndSet == NULL) {
1173 FreeStrBuf(&OneSet);
1174 DeleteHash(&ThisMSet);
1179 Put(ThisMSet, LKEY(StartSet), pEndSet, NULL);
1180 /* if we don't have another, we're done. */
1181 if (POS == StrBufNOTNULL)
1183 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1185 FreeStrBuf(&OneSet);
1191 * checks whether a message is inside a mset
1192 * MSetList List to search for MsgNo
1193 * MsgNo number to search in mset
1195 int IsInMSetList(MSet *MSetList, long MsgNo) {
1196 /* basicaly we are a ... */
1197 long MemberPosition;
1198 HashList *Hash = (HashList*) MSetList;
1205 if (Hash->MemberSize == 0)
1207 /** first, find out were we could fit in... */
1208 HashAt = FindInHash(Hash, MsgNo);
1210 /* we're below the first entry, so not found. */
1213 /* upper edge? move to last item */
1214 if (HashAt >= Hash->nMembersUsed)
1215 HashAt = Hash->nMembersUsed - 1;
1216 /* Match? then we got it. */
1217 else if (Hash->LookupTable[HashAt]->Key == MsgNo)
1219 /* One above possible range start? we need to move to the lower one. */
1220 else if ((HashAt > 0) &&
1221 (Hash->LookupTable[HashAt]->Key > MsgNo))
1224 /* Fetch the actual data */
1225 StartAt = Hash->LookupTable[HashAt]->Key;
1226 MemberPosition = Hash->LookupTable[HashAt]->Position;
1227 EndAt = *(long*) Hash->Members[MemberPosition]->Data;
1228 if ((MsgNo >= StartAt) && (EndAt == LONG_MAX))
1233 /* inside of range? */
1234 if ((StartAt <= MsgNo) && (EndAt >= MsgNo))
1241 * frees a mset [redirects to @ref DeleteHash
1242 * FreeMe to be free'd
1244 void DeleteMSet(MSet **FreeMe) {
1245 DeleteHash((HashList**) FreeMe);