From c57c92d7b61a7db8da50a27e5bf1fa99ebd8ce14 Mon Sep 17 00:00:00 2001 From: =?utf8?q?Wilfried=20G=C3=B6esgens?= Date: Sat, 26 Apr 2008 09:00:15 +0000 Subject: [PATCH] * bugfix in the hash implementation; expanding the hash wasn't done properly * added possibility to have list with duplicate primary keys * added ability to specify custom "hashing" algorithm * bumped version number to 1.10 since the newhash function has a different signature now. --- libcitadel/configure.in | 2 +- libcitadel/lib/hash.c | 95 ++++++++++++++++++++++-------------- libcitadel/lib/libcitadel.h | 5 +- libcitadel/lib/mime_parser.c | 8 +-- 4 files changed, 68 insertions(+), 42 deletions(-) diff --git a/libcitadel/configure.in b/libcitadel/configure.in index db8b8f2d9..392d61805 100755 --- a/libcitadel/configure.in +++ b/libcitadel/configure.in @@ -5,7 +5,7 @@ dnl dnl Ensure that libcitadel is configured with autoconf 2.52 or newer AC_PREREQ(2.52) -AC_INIT(libcitadel, 1.09, https://uncensored.citadel.org) +AC_INIT(libcitadel, 1.10, https://uncensored.citadel.org) AC_CONFIG_SRCDIR(Makefile.in) AC_CONFIG_AUX_DIR(conftools) diff --git a/libcitadel/lib/hash.c b/libcitadel/lib/hash.c index 85c9cda95..330483840 100644 --- a/libcitadel/lib/hash.c +++ b/libcitadel/lib/hash.c @@ -34,9 +34,11 @@ struct HashList { 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 */ + HashFunc Algorithm; /**< should we use an alternating algorithm to calc the hash values? */ 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. */ + long uniq; /**< are the keys going to be uniq? */ }; struct HashPos { @@ -99,7 +101,7 @@ int PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second) * \brief instanciate a new hashlist * \returns the newly allocated list. */ -HashList *NewHash(void) +HashList *NewHash(int Uniq, HashFunc F) { HashList *NewList; NewList = malloc (sizeof(HashList)); @@ -113,6 +115,8 @@ HashList *NewHash(void) NewList->MemberSize = 100; NewList->tainted = 0; + NewList->uniq = Uniq; + NewList->Algorithm = F; return NewList; } @@ -168,6 +172,33 @@ void DeleteHash(HashList **Hash) *Hash = NULL; } +/** + * \brief Private function to increase the hash size. + * \param Hash the Hasharray to increase + */ +static void IncreaseHashSize(HashList *Hash) +{ + /* Ok, Our space is used up. Double the available space. */ + 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); + free(Hash->LookupTable); + Hash->LookupTable = NewTable; + + Hash->MemberSize *= 2; +} + /** * \brief private function to add a new item to / replace an existing in - the hashlist @@ -182,7 +213,7 @@ void DeleteHash(HashList **Hash) static void InsertHashItem(HashList *Hash, long HashPos, long HashBinKey, - char *HashKeyStr, + const char *HashKeyStr, long HKLen, void *Data, DeleteHashDataFunc Destructor) @@ -191,27 +222,8 @@ static void InsertHashItem(HashList *Hash, HashKey *NewHashKey; if (Hash->nMembersUsed >= Hash->MemberSize) - { - /* Ok, Our space is used up. Double the available space. */ - 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); - free(Hash->LookupTable); - Hash->LookupTable = NewTable; - - Hash->MemberSize *= 2; - } + IncreaseHashSize (Hash); + /** Arrange the payload */ NewPayloadItem = (Payload*) malloc (sizeof(Payload)); NewPayloadItem->Data = Data; @@ -322,9 +334,12 @@ static long FindInHash(HashList *Hash, long HashBinKey) * \param HKLen length of HKey * \returns the calculated hash value */ -inline static long CalcHashKey (char *HKey, long HKLen) +inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen) { - return hashlittle(HKey, HKLen, 9283457); + if (Hash->Algorithm == NULL) + return hashlittle(HKey, HKLen, 9283457); + else + return Hash->Algorithm(HKey, HKLen); } @@ -336,32 +351,40 @@ inline static long CalcHashKey (char *HKey, long HKLen) * \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) +void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt) { long HashBinKey; long HashAt; /** first, find out were we could fit in... */ - HashBinKey = CalcHashKey(HKey, HKLen); + HashBinKey = CalcHashKey(Hash, HKey, HKLen); HashAt = FindInHash(Hash, HashBinKey); + if (HashAt >= Hash->MemberSize) + IncreaseHashSize (Hash); + /** oh, we're brand new... */ - if (Hash->LookupTable[HashAt] == NULL){ + 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); + InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt); } else { /** Ok, we have a colision. replace it. */ - long PayloadPos; - - PayloadPos = Hash->LookupTable[HashAt]->Position; - DeleteHashPayload(Hash->Members[PayloadPos]); - Hash->Members[PayloadPos]->Data = Data; - Hash->Members[PayloadPos]->Destructor = DeleteIt; + if (Hash->uniq) { + long PayloadPos; + + PayloadPos = Hash->LookupTable[HashAt]->Position; + DeleteHashPayload(Hash->Members[PayloadPos]); + Hash->Members[PayloadPos]->Data = Data; + Hash->Members[PayloadPos]->Destructor = DeleteIt; + } + else { + InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt); + } } } @@ -383,7 +406,7 @@ int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data) return 0; } /** first, find out were we could be... */ - HashBinKey = CalcHashKey((char*)HKey, HKLen); + HashBinKey = CalcHashKey(Hash, HKey, HKLen); HashAt = FindInHash(Hash, HashBinKey); if ((HashAt < 0) || /**< Not found at the lower edge? */ (HashAt >= Hash->nMembersUsed) || /**< Not found at the upper edge? */ diff --git a/libcitadel/lib/libcitadel.h b/libcitadel/lib/libcitadel.h index a296b5550..b7af4f0e6 100644 --- a/libcitadel/lib/libcitadel.h +++ b/libcitadel/lib/libcitadel.h @@ -269,14 +269,15 @@ typedef struct HashPos HashPos; typedef void (*DeleteHashDataFunc)(void * Data); typedef const char *(*PrintHashContent)(void * Data); typedef int (*CompareFunc)(const void* Item1, const void*Item2); +typedef int (*HashFunc)(const char *Str, long Len); -HashList *NewHash(void); +HashList *NewHash(int Uniq, HashFunc F); void DeleteHash(HashList **Hash); int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data); -void Put(HashList *Hash, char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt); +void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt); int GetKey(HashList *Hash, char *HKey, long HKLen, void **Data); diff --git a/libcitadel/lib/mime_parser.c b/libcitadel/lib/mime_parser.c index 14f292a6d..b60b18beb 100644 --- a/libcitadel/lib/mime_parser.c +++ b/libcitadel/lib/mime_parser.c @@ -778,7 +778,7 @@ int LoadIconDir(const char *DirName) IconName *Icon; filedir = opendir (DirName); - IconHash = NewHash(); + IconHash = NewHash(1, NULL); if (filedir == NULL) { return 0; } @@ -842,19 +842,21 @@ int LoadIconDir(const char *DirName) const char *GetIconFilename(char *MimeType, size_t len) { + void *vIcon; IconName *Icon; if(IconHash == NULL) return NULL; - GetHash(IconHash, MimeType, len, (void**)&Icon); + GetHash(IconHash, MimeType, len, &vIcon), Icon = (IconName*) vIcon; /* didn't find the exact mimetype? try major only. */ if (Icon == NULL) { char * pMinor; pMinor = strchr(MimeType, '/'); if (pMinor != NULL) { *pMinor = '\0'; - GetHash(IconHash, MimeType, pMinor - MimeType, (void**)&Icon); + GetHash(IconHash, MimeType, pMinor - MimeType, &vIcon), + Icon = (IconName*) vIcon; } } if (Icon == NULL) { -- 2.30.2