From: Wilfried Göesgens Date: Sun, 2 Mar 2008 14:17:43 +0000 (+0000) Subject: * documented hashlist X-Git-Tag: v7.86~2449 X-Git-Url: https://code.citadel.org/?p=citadel.git;a=commitdiff_plain;h=276a9944e0503d0fb901b95bc660da83250fa1e7 * documented hashlist * the user may now sort the array in his prefered way. (this will mark the array tainted, and increase search times) * several sort funcions: * sort by the Hash-String * sort by the Hashkey (untaints the array) * sort by a user definable Comparator Function --- diff --git a/libcitadel/debian/changelog b/libcitadel/debian/changelog index 4c7317943..8bf8c3c05 100644 --- a/libcitadel/debian/changelog +++ b/libcitadel/debian/changelog @@ -1,3 +1,9 @@ +libcitadel (1.07-8) stable; urgency=high + + * new upstream version + + -- Wilfried Goesgens Sat, 23 Feb 2008 0:00:00 +0001 + libcitadel (1.06-7) stable; urgency=high * mime to icon guessing diff --git a/libcitadel/debian/files b/libcitadel/debian/files index 86dbb72dd..6b5384a91 100644 --- a/libcitadel/debian/files +++ b/libcitadel/debian/files @@ -1,3 +1,3 @@ -libcitadel1_1.06-7_i386.deb libs optional -libcitadel1-dbg_1.06-7_i386.deb libdevel optional -libcitadel-dev_1.06-7_i386.deb libdevel optional +libcitadel1_1.07-8_i386.deb libs optional +libcitadel1-dbg_1.07-8_i386.deb libdevel optional +libcitadel-dev_1.07-8_i386.deb libdevel optional diff --git a/libcitadel/lib/hash.c b/libcitadel/lib/hash.c index a3e33f1a2..50c3e8d7a 100644 --- a/libcitadel/lib/hash.c +++ b/libcitadel/lib/hash.c @@ -9,29 +9,50 @@ typedef struct Payload Payload; struct Payload { - void *Data; - DeleteHashDataFunc Destructor; + /** + * \brief Hash Payload storage Structure; filled in linear. + */ + void *Data; /**< the Data belonging to this storage */ + DeleteHashDataFunc Destructor; /**< if we want to destroy Data, do it with this function. */ }; struct HashKey { - long Key; - long Position; - char *HashKey; - long HKLen; + /** + * \brief Hash key element; sorted by Keye + */ + long Key; /**< Numeric Hashkey comperator for hash sorting */ + long Position; /**< Pointer to a Payload struct in the Payload Aray */ + char *HashKey; /**< the Plaintext Hashkey */ + long HKLen; /**< length of the Plaintext Hashkey */ + Payload *PL; /**< pointer to our payload for sorting */ }; struct HashList { - Payload **Members; - HashKey **LookupTable; - char **MyKeys; - long nMembersUsed; - long MemberSize; + /** + * \brief Hash structure; holds arrays of Hashkey and Payload. + */ + Payload **Members; /**< Our Payload members. This fills up linear */ + HashKey **LookupTable; /**< Hash Lookup table. Elements point to members, and are sorted by their hashvalue */ + char **MyKeys; /**< this keeps the members for a call of GetHashKeys */ + long nMembersUsed; /**< how many pointers inside of the array are used? */ + long MemberSize; /**< how big is Members and LookupTable? */ + long tainted; /**< if 0, we're hashed, else s.b. else sorted us in his own way. */ }; struct HashPos { + /** + * \brief Anonymous Hash Iterator Object. used for traversing the whole array from outside + */ long Position; }; -#define DEBUG + +/** + * \brief verify the contents of a hash list; here for debugging purposes. + * \param Hash your Hashlist structure + * \param First Functionpointer to allow you to print your payload + * \param Second Functionpointer to allow you to print your payload + * \returns 0 + */ int PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second) { const char *foo; @@ -74,7 +95,10 @@ int PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second) } - +/** + * \brief instanciate a new hashlist + * \returns the newly allocated list. + */ HashList *NewHash(void) { HashList *NewList; @@ -88,18 +112,28 @@ HashList *NewHash(void) memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100); NewList->MemberSize = 100; + NewList->tainted = 0; return NewList; } - +/** + * \brief private destructor for one hash element. + * \param Data an element to free using the user provided destructor, or just plain free + */ static void DeleteHashPayload (Payload *Data) { + /** do we have a destructor for our payload? */ if (Data->Destructor) Data->Destructor(Data->Data); else free(Data->Data); } + +/** + * \brief destroy a hashlist and all of its members + * \param Hash Hash to destroy. Is NULL'ed so you are shure its done. + */ void DeleteHash(HashList **Hash) { int i; @@ -110,27 +144,41 @@ void DeleteHash(HashList **Hash) return; for (i=0; i < FreeMe->nMembersUsed; i++) { + /** get rid of our payload */ if (FreeMe->Members[i] != NULL) { DeleteHashPayload(FreeMe->Members[i]); free(FreeMe->Members[i]); } + /** delete our hashing data */ if (FreeMe->LookupTable[i] != NULL) { free(FreeMe->LookupTable[i]->HashKey); free(FreeMe->LookupTable[i]); } } - + /** now, free our arrays... */ free(FreeMe->LookupTable); free(FreeMe->Members); + /** did s.b. want an array of our keys? free them. */ if (FreeMe->MyKeys != NULL) free(FreeMe->MyKeys); - + /** buye bye cruel world. */ free (FreeMe); *Hash = NULL; } + +/** + * \brief private function to add a new item to / replace an existing in - the hashlist + * if the hash list is full, its re-alloced with double size. + * \parame Hash our hashlist to manipulate + * \param HashPos where should we insert / replace? + * \param HashKeyStr the Hash-String + * \param HKLen length of HashKeyStr + * \param Data your Payload to add + * \param Destructor Functionpointer to free Data. if NULL, default free() is used. + */ static void InsertHashItem(HashList *Hash, long HashPos, long HashBinKey, @@ -148,12 +196,14 @@ static void InsertHashItem(HashList *Hash, Payload **NewPayloadArea; HashKey **NewTable; + /** double our payload area */ NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2); memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize); memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize); free(Hash->Members); Hash->Members = NewPayloadArea; + /** double our hashtable area */ NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2); memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize); memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize); @@ -162,18 +212,20 @@ static void InsertHashItem(HashList *Hash, Hash->MemberSize *= 2; } - + /** Arrange the payload */ NewPayloadItem = (Payload*) malloc (sizeof(Payload)); NewPayloadItem->Data = Data; NewPayloadItem->Destructor = Destructor; - + /** Arrange the hashkey */ NewHashKey = (HashKey*) malloc (sizeof(HashKey)); NewHashKey->HashKey = (char *) malloc (HKLen + 1); NewHashKey->HKLen = HKLen; memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1); NewHashKey->Key = HashBinKey; + NewHashKey->PL = NewPayloadItem; + /** our payload is queued at the end... */ NewHashKey->Position = Hash->nMembersUsed; - + /** but if we should be sorted into a specific place... */ if ((Hash->nMembersUsed != 0) && (HashPos != Hash->nMembersUsed) ) { long InsertAt; @@ -181,7 +233,7 @@ static void InsertHashItem(HashList *Hash, ItemsAfter = Hash->nMembersUsed - HashPos; InsertAt = HashPos; - + /** make space were we can fill us in */ if (ItemsAfter > 0) { memmove(&Hash->LookupTable[InsertAt + 1], @@ -189,17 +241,45 @@ static void InsertHashItem(HashList *Hash, ItemsAfter * sizeof(HashKey*)); } } - + Hash->Members[Hash->nMembersUsed] = NewPayloadItem; Hash->LookupTable[HashPos] = NewHashKey; Hash->nMembersUsed++; } +/** + * \brief if the user has tainted the hash, but wants to insert / search items by their key + * we need to search linear through the array. You have been warned that this will take more time! + * \param Hash Our Hash to manipulate + * \param HashBinKey the Hash-Number to lookup. + * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! ) + */ +static long FindInTaintedHash(HashList *Hash, long HashBinKey) +{ + long SearchPos; + + for (SearchPos = 0; SearchPos < Hash->nMembersUsed; SearchPos ++) { + if (Hash->LookupTable[SearchPos]->Key == HashBinKey){ + return SearchPos; + } + } + return SearchPos; +} + +/** + * \brief Private function to lookup the Item / the closest position to put it in + * \param Hash Our Hash to manipulate + * \param HashBinKey the Hash-Number to lookup. + * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! ) + */ static long FindInHash(HashList *Hash, long HashBinKey) { long SearchPos; long StepWidth; + if (Hash->tainted) + return FindInTaintedHash(Hash, HashBinKey); + SearchPos = Hash->nMembersUsed / 2; StepWidth = SearchPos / 2; while ((SearchPos > 0) && @@ -236,33 +316,46 @@ static long FindInHash(HashList *Hash, long HashBinKey) return SearchPos; } - - +/** + * \brief private abstract wrapper around the hashing algorithm + * \param HKey the hash string + * \param HKLen length of HKey + * \returns the calculated hash value + */ inline static long CalcHashKey (char *HKey, long HKLen) { return hashlittle(HKey, HKLen, 9283457); } +/** + * \brief Add a new / Replace an existing item in the Hash + * \param HashList the list to manipulate + * \param HKey the hash-string to store Data under + * \param HKeyLen Length of HKey + * \param Data the payload you want to associate with HKey + * \param DeleteIt if not free() should be used to delete Data set to NULL, else DeleteIt is used. + */ void Put(HashList *Hash, char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt) { long HashBinKey; long HashAt; - + /** first, find out were we could fit in... */ HashBinKey = CalcHashKey(HKey, HKLen); HashAt = FindInHash(Hash, HashBinKey); + /** oh, we're brand new... */ if (Hash->LookupTable[HashAt] == NULL){ InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt); - } + }/** Insert After? */ else if (Hash->LookupTable[HashAt]->Key > HashBinKey) { InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt); - } + }/** Insert before? */ else if (Hash->LookupTable[HashAt]->Key < HashBinKey) { InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt); } - else { /* Ok, we have a colision. replace it. */ + else { /** Ok, we have a colision. replace it. */ long PayloadPos; PayloadPos = Hash->LookupTable[HashAt]->Position; @@ -272,20 +365,29 @@ void Put(HashList *Hash, char *HKey, long HKLen, void *Data, DeleteHashDataFunc } } +/** + * \brief Lookup the Data associated with HKey + * \param Hash the Hashlist to search in + * \param HKey the hashkey to look up + * \param HKLen length of HKey + * \param Data returns the Data associated with HKey + * \returns 0 if not found, 1 if. + */ int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data) { long HashBinKey; long HashAt; + /** first, find out were we could be... */ HashBinKey = CalcHashKey((char*)HKey, HKLen); HashAt = FindInHash(Hash, HashBinKey); - if ((HashAt < 0) || - (HashAt >= Hash->nMembersUsed) || - (Hash->LookupTable[HashAt]->Key != HashBinKey)) { + if ((HashAt < 0) || /**< Not found at the lower edge? */ + (HashAt >= Hash->nMembersUsed) || /**< Not found at the upper edge? */ + (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */ *Data = NULL; return 0; } - else { + else { /** GOTCHA! */ long MemberPosition; MemberPosition = Hash->LookupTable[HashAt]->Position; @@ -294,11 +396,18 @@ int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data) } } +/* TODO? */ int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload) { return 0; } +/** + * \brief get the Keys present in this hash, simila to array_keys() in PHP + * Attention: List remains to Hash! don't modify or free it! + * \param Hash Your Hashlist to extract the keys from + * \param List returns the list of hashkeys stored in Hash + */ int GetHashKeys(HashList *Hash, char ***List) { long i; @@ -314,6 +423,10 @@ int GetHashKeys(HashList *Hash, char ***List) return Hash->nMembersUsed; } +/** + * \brief creates a hash-linear iterator object + * \returns the hash iterator + */ HashPos *GetNewHashPos(void) { HashPos *Ret; @@ -323,12 +436,24 @@ HashPos *GetNewHashPos(void) return Ret; } +/** + * \brief frees a linear hash iterator + */ void DeleteHashPos(HashPos **DelMe) { free(*DelMe); *DelMe = NULL; } + +/** + * \brief Get the data located where HashPos Iterator points at, and Move HashPos one forward + * \param Hash your Hashlist to follow + * \param HKLen returns Length of Hashkey Returned + * \param HashKey returns the Hashkey corrosponding to HashPos + * \param Data returns the Data found at HashPos + * \returns whether the item was found or not. + */ int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, char **HashKey, void **Data) { long PayloadPos; @@ -342,3 +467,99 @@ int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, char **HashKey, voi At->Position++; return 1; } + +/** + * \brief sorting function for sorting the Hash alphabeticaly by their strings + * \param Key1 first item + * \param Key2 second item + */ +static int SortByKeys(const void *Key1, const void* Key2) +{ + HashKey *HKey1, *HKey2; + HKey1 = *(HashKey**) Key1; + HKey2 = *(HashKey**) Key2; + + return strcasecmp(HKey1->HashKey, HKey2->HashKey); +} + +/** + * \brief sorting function to regain hash-sequence and revert tainted status + * \param Key1 first item + * \param Key2 second item + */ +static int SortByHashKeys(const void *Key1, const void* Key2) +{ + HashKey *HKey1, *HKey2; + HKey1 = *(HashKey**) Key1; + HKey2 = *(HashKey**) Key2; + + return HKey1->Key > HKey2->Key; +} + + +/** + * \brief sort the hash alphabeticaly by their keys. + * Caution: This taints the hashlist, so accessing it later + * will be significantly slower! You can un-taint it by SortByHashKeyStr + * \param Hash the list to sort + */ +void SortByHashKey(HashList *Hash) +{ + if (Hash->nMembersUsed < 2) + return; + qsort(Hash->LookupTable, Hash->nMembersUsed, sizeof(HashKey*), SortByKeys); + Hash->tainted = 1; +} + +/** + * \brief sort the hash by their keys (so it regains untainted state). + * this will result in the sequence the hashing allgorithm produces it by default. + * \param Hash the list to sort + */ +void SortByHashKeyStr(HashList *Hash) +{ + Hash->tainted = 0; + if (Hash->nMembersUsed < 2) + return; + qsort(Hash->LookupTable, Hash->nMembersUsed, sizeof(HashKey*), SortByHashKeys); +} + + +/** + * \brief gives user sort routines access to the hash payload + * \param Searchentry to retrieve Data to + * \returns Data belonging to HashVoid + */ +const void *GetSearchPayload(const void *HashVoid) +{ + return (*(HashKey**)HashVoid)->PL->Data; +} + +/** + * \brief sort the hash by your sort function. see the following sample. + * this will result in the sequence the hashing allgorithm produces it by default. + * \param Hash the list to sort + * \param SortBy Sortfunction; see below how to implement this + */ +void SortByPayload(HashList *Hash, CompareFunc SortBy) +{ + if (Hash->nMembersUsed < 2) + return; + qsort(Hash->LookupTable, Hash->nMembersUsed, sizeof(HashKey*), SortBy); + Hash->tainted = 1; +} + + + + +/** + * given you've put char * into your hash as a payload, a sort function might + * look like this: + * int SortByChar(const void* First, const void* Second) + * { + * char *a, *b; + * a = (char*) GetSearchPayload(First); + * b = (char*) GetSearchPayload(Second); + * return strcmp (a, b); + * } + */ diff --git a/libcitadel/lib/libcitadel.h b/libcitadel/lib/libcitadel.h index 83f69be4c..3a9bbbd67 100644 --- a/libcitadel/lib/libcitadel.h +++ b/libcitadel/lib/libcitadel.h @@ -10,7 +10,7 @@ */ #include #include -#define LIBCITADEL_VERSION_NUMBER 107 +#define LIBCITADEL_VERSION_NUMBER 108 /* * Here's a bunch of stupid magic to make the MIME parser portable. @@ -263,6 +263,7 @@ typedef struct HashPos HashPos; typedef void (*DeleteHashDataFunc)(void * Data); typedef const char *(*PrintHashContent)(void * Data); +typedef int (*CompareFunc)(const void* Item1, const void*Item2); HashList *NewHash(void); @@ -283,3 +284,10 @@ HashPos *GetNewHashPos(void); void DeleteHashPos(HashPos **DelMe); int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, char **HashKey, void **Data); + +void SortByHashKey(HashList *Hash); +void SortByHashKeyStr(HashList *Hash); + +const void *GetSearchPayload(const void *HashVoid); +void SortByPayload(HashList *Hash, CompareFunc SortBy); +