+ /* Ok, Our space is used up. Double the available space. */
+ Payload **NewPayloadArea;
+ HashKey **NewTable;
+
+ if (Hash == NULL)
+ return 0;
+
+ /** If we grew to much, this might be the place to rehash and shrink again.
+ if ((Hash->NMembersUsed > Hash->nLookupTableItems) &&
+ ((Hash->NMembersUsed - Hash->nLookupTableItems) >
+ (Hash->nLookupTableItems / 10)))
+ {
+
+
+ }
+ */
+
+ NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
+ if (NewPayloadArea == NULL)
+ return 0;
+ NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
+ if (NewTable == NULL)
+ {
+ free(NewPayloadArea);
+ return 0;
+ }
+
+ /** double our payload area */
+ 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 */
+ 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;
+ return 1;
+}
+
+
+/**
+ * @ingroup HashListPrivate
+ * @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.
+ * @param 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 int InsertHashItem(HashList *Hash,
+ long HashPos,
+ long HashBinKey,
+ const char *HashKeyStr,
+ long HKLen,
+ void *Data,
+ DeleteHashDataFunc Destructor)
+{
+ Payload *NewPayloadItem;
+ HashKey *NewHashKey;
+ char *HashKeyOrgVal;
+
+ if (Hash == NULL)
+ return 0;
+
+ if ((Hash->nMembersUsed >= Hash->MemberSize) &&
+ (!IncreaseHashSize (Hash)))
+ return 0;
+
+ NewPayloadItem = (Payload*) malloc (sizeof(Payload));
+ if (NewPayloadItem == NULL)
+ return 0;
+ NewHashKey = (HashKey*) malloc (sizeof(HashKey));
+ if (NewHashKey == NULL)
+ {
+ free(NewPayloadItem);
+ return 0;
+ }
+ HashKeyOrgVal = (char *) malloc (HKLen + 1);
+ if (HashKeyOrgVal == NULL)
+ {
+ free(NewHashKey);
+ free(NewPayloadItem);
+ return 0;
+ }
+
+
+ /** Arrange the payload */
+ NewPayloadItem->Data = Data;
+ NewPayloadItem->Destructor = Destructor;
+ /** Arrange the hashkey */
+ NewHashKey->HKLen = HKLen;
+ NewHashKey->HashKey = HashKeyOrgVal;
+ 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->nLookupTableItems != 0) &&
+ (HashPos != Hash->nLookupTableItems) ) {
+ long ItemsAfter;
+
+ ItemsAfter = Hash->nLookupTableItems - HashPos;
+ /** make space were we can fill us in */
+ if (ItemsAfter > 0)
+ {
+ memmove(&Hash->LookupTable[HashPos + 1],
+ &Hash->LookupTable[HashPos],
+ ItemsAfter * sizeof(HashKey*));
+ }
+ }
+
+ Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
+ Hash->LookupTable[HashPos] = NewHashKey;
+ Hash->nMembersUsed++;
+ Hash->nLookupTableItems++;
+ return 1;
+}
+
+/**
+ * @ingroup HashListSort
+ * @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.
+ * @return the position (most closely) matching HashBinKey (-> Caller needs to compare! )
+ */
+static long FindInTaintedHash(HashList *Hash, long HashBinKey)
+{
+ long SearchPos;
+
+ if (Hash == NULL)
+ return 0;
+
+ for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
+ if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
+ return SearchPos;
+ }
+ }
+ return SearchPos;
+}
+
+/**
+ * @ingroup HashListPrivate
+ * @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.
+ * @return the position (most closely) matching HashBinKey (-> Caller needs to compare! )
+ */
+static long FindInHash(HashList *Hash, long HashBinKey)
+{
+ long SearchPos;
+ long StepWidth;
+
+ if (Hash == NULL)
+ return 0;
+
+ if (Hash->tainted)
+ return FindInTaintedHash(Hash, HashBinKey);
+
+ SearchPos = Hash->nLookupTableItems / 2;
+ StepWidth = SearchPos / 2;
+ while ((SearchPos > 0) &&
+ (SearchPos < Hash->nLookupTableItems))
+ {
+ /** Did we find it? */
+ if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
+ return SearchPos;
+ }
+ /** are we Aproximating in big steps? */
+ if (StepWidth > 1){
+ if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
+ SearchPos -= StepWidth;
+ else
+ SearchPos += StepWidth;
+ StepWidth /= 2;
+ }
+ else { /** We are right next to our target, within 4 positions */
+ if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
+ if ((SearchPos > 0) &&
+ (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
+ return SearchPos;
+ SearchPos --;
+ }
+ else {
+ if ((SearchPos + 1 < Hash->nLookupTableItems) &&
+ (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
+ return SearchPos;
+ SearchPos ++;
+ }
+ StepWidth--;
+ }
+ }
+ return SearchPos;
+}
+
+
+/**
+ * @ingroup HashListAlgorithm
+ * @brief another hashing algorithm; treat it as just a pointer to int.
+ * @param str Our pointer to the int value
+ * @param len the length of the data pointed to; needs to be sizeof int, else we won't use it!
+ * @return the calculated hash value
+ */
+long Flathash(const char *str, long len)
+{
+ if (len != sizeof (int))
+ return 0;
+ else return *(int*)str;
+}
+
+/**
+ * @ingroup HashListAlgorithm
+ * @brief another hashing algorithm; treat it as just a pointer to long.
+ * @param str Our pointer to the long value
+ * @param len the length of the data pointed to; needs to be sizeof long, else we won't use it!
+ * @return the calculated hash value
+ */
+long lFlathash(const char *str, long len)
+{
+ if (len != sizeof (long))
+ return 0;
+ else return *(long*)str;
+}
+
+/**
+ * @ingroup HashListPrivate
+ * @brief private abstract wrapper around the hashing algorithm
+ * @param HKey the hash string
+ * @param HKLen length of HKey
+ * @return the calculated hash value
+ */
+inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
+{
+ if (Hash == NULL)
+ return 0;
+
+ if (Hash->Algorithm == NULL)
+ return hashlittle(HKey, HKLen, 9283457);
+ else
+ return Hash->Algorithm(HKey, HKLen);
+}
+
+
+/**
+ * @ingroup HashListAccess
+ * @brief Add a new / Replace an existing item in the Hash
+ * @param Hash the list to manipulate
+ * @param HKey the hash-string to store Data under
+ * @param HKLen 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, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
+{
+ long HashBinKey;
+ long HashAt;
+
+ if (Hash == NULL)
+ return;
+
+ /** first, find out were we could fit in... */
+ HashBinKey = CalcHashKey(Hash, HKey, HKLen);
+ HashAt = FindInHash(Hash, HashBinKey);
+
+ if ((HashAt >= Hash->MemberSize) &&
+ (!IncreaseHashSize (Hash)))
+ return;
+
+ /** oh, we're brand new... */
+ if (Hash->LookupTable[HashAt] == NULL) {
+ InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
+ }/** Insert Before? */
+ else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
+ InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
+ }/** Insert After? */
+ else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
+ InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
+ }
+ else { /** Ok, we have a colision. replace it. */
+ 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);
+ }
+ }
+}
+
+/**
+ * @ingroup HashListAccess
+ * @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
+ * @return 0 if not found, 1 if.
+ */
+int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data)
+{
+ long HashBinKey;
+ long HashAt;
+
+ if (Hash == NULL)
+ return 0;
+
+ if (HKLen <= 0) {
+ *Data = NULL;
+ return 0;
+ }
+ /** first, find out were we could be... */
+ HashBinKey = CalcHashKey(Hash, HKey, HKLen);
+ HashAt = FindInHash(Hash, HashBinKey);
+ if ((HashAt < 0) || /**< Not found at the lower edge? */
+ (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
+ (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
+ *Data = NULL;
+ return 0;
+ }
+ else { /** GOTCHA! */
+ long MemberPosition;
+
+ MemberPosition = Hash->LookupTable[HashAt]->Position;
+ *Data = Hash->Members[MemberPosition]->Data;
+ return 1;
+ }