* 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.

diff --git a/libcitadel/configure.in b/libcitadel/configure.in
index db8b8f2d9e59fe79db89e8ae7f4823ef61dfea61..392d61805daa6c81d5fb18f0032cd7b347a32019 100755 (executable)
--- 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 85c9cda95b0bebce676c9084ac0481aa7302fb99..33048384031b0276d674cfc9ad4bdd2720f8b219 100644 (file)
--- 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 a296b555017bb7a9d779b9ea7f5d52c784fb897e..b7af4f0e634cd948fa68037622abc4325429e6d0 100644 (file)
--- 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 14f292a6def95a637e5fe9275f2804e03a21f88a..b60b18beb63994b8d2722dc77550f789b76d5a1f 100644 (file)
--- 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) {