libcitadel/lib/hash.c

   1 #include <stdint.h>
   2 #include <stdlib.h>
   3 #include <string.h>
   4 //dbg
   5 #include <stdio.h>
   6 #include "libcitadel.h"
   7 #include "lookup3.h"
   8
   9 typedef struct Payload Payload;
  10
  11 /**
  12  * @brief Hash Payload storage Structure; filled in linear.
  13  */
  14 struct Payload {
  15         void *Data; /**< the Data belonging to this storage */
  16         DeleteHashDataFunc Destructor; /**< if we want to destroy Data, do it with this function. */
  17 };
  18
  19
  20 /**
  21  * @brief Hash key element; sorted by key
  22  */
  23 struct HashKey {
  24         long Key;         /**< Numeric Hashkey comperator for hash sorting */
  25         long Position;    /**< Pointer to a Payload struct in the Payload Aray */
  26         char *HashKey;    /**< the Plaintext Hashkey */
  27         long HKLen;       /**< length of the Plaintext Hashkey */
  28         Payload *PL;      /**< pointer to our payload for sorting */
  29 };
  30
  31 /**
  32  * @brief Hash structure; holds arrays of Hashkey and Payload.
  33  */
  34 struct HashList {
  35         Payload **Members;     /**< Our Payload members. This fills up linear */
  36         HashKey **LookupTable; /**< Hash Lookup table. Elements point to members, and are sorted by their hashvalue */
  37         char **MyKeys;         /**< this keeps the members for a call of GetHashKeys */
  38         HashFunc Algorithm;    /**< should we use an alternating algorithm to calc the hash values? */
  39         long nMembersUsed;     /**< how many pointers inside of the array are used? */
  40         long nLookpTableItems; /**< how many items of the lookup table are used? */
  41         long MemberSize;       /**< how big is Members and LookupTable? */
  42         long tainted;          /**< if 0, we're hashed, else s.b. else sorted us in his own way. */
  43         long uniq;             /**< are the keys going to be uniq? */
  44 };
  45
  46 /**
  47  * @brief Anonymous Hash Iterator Object. used for traversing the whole array from outside
  48  */
  49 struct HashPos {
  50         long Position;        /**< Position inside of the hash */
  51         int StepWidth;        /**< small? big? forward? backward? */
  52 };
  53
  54
  55 /**
  56  * @brief Iterate over the hash and call PrintEntry.
  57  * @param Hash your Hashlist structure
  58  * @param Trans is called so you could for example print 'A:' if the next entries are like that.
  59  *        Must be aware to receive NULL in both pointers.
  60  * @param PrintEntry print entry one by one
  61  * \returns the number of items printed
  62  */
  63 int PrintHash(HashList *Hash, TransitionFunc Trans, PrintHashDataFunc PrintEntry)
  64 {
  65         int i;
  66         void *Previous;
  67         void *Next;
  68         const char* KeyStr;
  69
  70         if (Hash == NULL)
  71                 return 0;
  72
  73         for (i=0; i < Hash->nLookpTableItems; i++) {
  74                 if (i==0) {
  75                         Previous = NULL;
  76                 }
  77                 else {
  78                         if (Hash->LookupTable[i - 1] == NULL)
  79                                 Previous = NULL;
  80                         else
  81                                 Previous = Hash->Members[Hash->LookupTable[i-1]->Position]->Data;
  82                 }
  83                 if (Hash->LookupTable[i] == NULL) {
  84                         KeyStr = "";
  85                         Next = NULL;
  86                 }
  87                 else {
  88                         Next = Hash->Members[Hash->LookupTable[i]->Position]->Data;
  89                         KeyStr = Hash->LookupTable[i]->HashKey;
  90                 }
  91
  92                 Trans(Previous, Next, i % 2);
  93                 PrintEntry(KeyStr, Next, i % 2);
  94         }
  95         return i;
  96 }
  97
  98
  99 /**
 100  * @brief verify the contents of a hash list; here for debugging purposes.
 101  * @param Hash your Hashlist structure
 102  * @param First Functionpointer to allow you to print your payload
 103  * @param Second Functionpointer to allow you to print your payload
 104  * \returns 0
 105  */
 106 int dbg_PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second)
 107 {
 108         const char *foo;
 109         const char *bar;
 110         const char *bla = "";
 111         long key;
 112         long i;
 113
 114         if (Hash == NULL)
 115                 return 0;
 116
 117         if (Hash->MyKeys != NULL)
 118                 free (Hash->MyKeys);
 119
 120         Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookpTableItems);
 121 #ifdef DEBUG
 122         printf("----------------------------------\n");
 123 #endif
 124         for (i=0; i < Hash->nLookpTableItems; i++) {
 125
 126                 if (Hash->LookupTable[i] == NULL)
 127                 {
 128                         foo = "";
 129                         bar = "";
 130                         key = 0;
 131                 }
 132                 else
 133                 {
 134                         key = Hash->LookupTable[i]->Key;
 135                         foo = Hash->LookupTable[i]->HashKey;
 136                         if (First != NULL)
 137                                 bar = First(Hash->Members[Hash->LookupTable[i]->Position]->Data);
 138                         else
 139                                 bar = "";
 140                         if (Second != NULL)
 141                                 bla = Second(Hash->Members[Hash->LookupTable[i]->Position]->Data);
 142                         else
 143                                 bla = "";
 144                 }
 145 #ifdef DEBUG
 146                 printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' ; %s\n", i, key, foo, bar, bla);
 147 #endif
 148         }
 149 #ifdef DEBUG
 150         printf("----------------------------------\n");
 151 #endif
 152         return 0;
 153 }
 154
 155
 156 /**
 157  * @brief instanciate a new hashlist
 158  * \returns the newly allocated list.
 159  */
 160 HashList *NewHash(int Uniq, HashFunc F)
 161 {
 162         HashList *NewList;
 163         NewList = malloc (sizeof(HashList));
 164         memset(NewList, 0, sizeof(HashList));
 165
 166         NewList->Members = malloc(sizeof(Payload*) * 100);
 167         memset(NewList->Members, 0, sizeof(Payload*) * 100);
 168
 169         NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
 170         memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
 171
 172         NewList->MemberSize = 100;
 173         NewList->tainted = 0;
 174         NewList->uniq = Uniq;
 175         NewList->Algorithm = F;
 176
 177         return NewList;
 178 }
 179
 180 int GetCount(HashList *Hash)
 181 {
 182         if(Hash==NULL) return 0;
 183         return Hash->nLookpTableItems;
 184 }
 185
 186
 187 /**
 188  * @brief private destructor for one hash element.
 189  * Crashing? go one frame up and do 'print *FreeMe->LookupTable[i]'
 190  * @param Data an element to free using the user provided destructor, or just plain free
 191  */
 192 static void DeleteHashPayload (Payload *Data)
 193 {
 194         /** do we have a destructor for our payload? */
 195         if (Data->Destructor)
 196                 Data->Destructor(Data->Data);
 197         else
 198                 free(Data->Data);
 199 }
 200
 201 /**
 202  * @brief Destructor for nested hashes
 203  */
 204 void HDeleteHash(void *vHash)
 205 {
 206         HashList *FreeMe = (HashList*)vHash;
 207         DeleteHash(&FreeMe);
 208 }
 209
 210 /**
 211  * @brief destroy a hashlist and all of its members
 212  * Crashing? do 'print *FreeMe->LookupTable[i]'
 213  * @param Hash Hash to destroy. Is NULL'ed so you are shure its done.
 214  */
 215 void DeleteHash(HashList **Hash)
 216 {
 217         int i;
 218         HashList *FreeMe;
 219
 220         FreeMe = *Hash;
 221         if (FreeMe == NULL)
 222                 return;
 223         /* even if there are sparse members already deleted... */
 224         for (i=0; i < FreeMe->nMembersUsed; i++)
 225         {
 226                 /** get rid of our payload */
 227                 if (FreeMe->Members[i] != NULL)
 228                 {
 229                         DeleteHashPayload(FreeMe->Members[i]);
 230                         free(FreeMe->Members[i]);
 231                 }
 232                 /** delete our hashing data */
 233                 if (FreeMe->LookupTable[i] != NULL)
 234                 {
 235                         free(FreeMe->LookupTable[i]->HashKey);
 236                         free(FreeMe->LookupTable[i]);
 237                 }
 238         }
 239         /** now, free our arrays... */
 240         free(FreeMe->LookupTable);
 241         free(FreeMe->Members);
 242         /** did s.b. want an array of our keys? free them. */
 243         if (FreeMe->MyKeys != NULL)
 244                 free(FreeMe->MyKeys);
 245         /** buye bye cruel world. */
 246         free (FreeMe);
 247         *Hash = NULL;
 248 }
 249
 250 /**
 251  * @brief Private function to increase the hash size.
 252  * @param Hash the Hasharray to increase
 253  */
 254 static void IncreaseHashSize(HashList *Hash)
 255 {
 256         /* Ok, Our space is used up. Double the available space. */
 257         Payload **NewPayloadArea;
 258         HashKey **NewTable;
 259
 260         if (Hash == NULL)
 261                 return ;
 262
 263         /** If we grew to much, this might be the place to rehash and shrink again.
 264         if ((Hash->NMembersUsed > Hash->nLookpTableItems) &&
 265             ((Hash->NMembersUsed - Hash->nLookpTableItems) >
 266              (Hash->nLookpTableItems / 10)))
 267         {
 268
 269
 270         }
 271         */
 272
 273         /** double our payload area */
 274         NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
 275         memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
 276         memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
 277         free(Hash->Members);
 278         Hash->Members = NewPayloadArea;
 279
 280         /** double our hashtable area */
 281         NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
 282         memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
 283         memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
 284         free(Hash->LookupTable);
 285         Hash->LookupTable = NewTable;
 286
 287         Hash->MemberSize *= 2;
 288 }
 289
 290
 291 /**
 292  * @brief private function to add a new item to / replace an existing in -  the hashlist
 293  * if the hash list is full, its re-alloced with double size.
 294  * \parame Hash our hashlist to manipulate
 295  * @param HashPos where should we insert / replace?
 296  * @param HashKeyStr the Hash-String
 297  * @param HKLen length of HashKeyStr
 298  * @param Data your Payload to add
 299  * @param Destructor Functionpointer to free Data. if NULL, default free() is used.
 300  */
 301 static void InsertHashItem(HashList *Hash,
 302                            long HashPos,
 303                            long HashBinKey,
 304                            const char *HashKeyStr,
 305                            long HKLen,
 306                            void *Data,
 307                            DeleteHashDataFunc Destructor)
 308 {
 309         Payload *NewPayloadItem;
 310         HashKey *NewHashKey;
 311
 312         if (Hash == NULL)
 313                 return;
 314
 315         if (Hash->nMembersUsed >= Hash->MemberSize)
 316                 IncreaseHashSize (Hash);
 317
 318         /** Arrange the payload */
 319         NewPayloadItem = (Payload*) malloc (sizeof(Payload));
 320         NewPayloadItem->Data = Data;
 321         NewPayloadItem->Destructor = Destructor;
 322         /** Arrange the hashkey */
 323         NewHashKey = (HashKey*) malloc (sizeof(HashKey));
 324         NewHashKey->HashKey = (char *) malloc (HKLen + 1);
 325         NewHashKey->HKLen = HKLen;
 326         memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
 327         NewHashKey->Key = HashBinKey;
 328         NewHashKey->PL = NewPayloadItem;
 329         /** our payload is queued at the end... */
 330         NewHashKey->Position = Hash->nMembersUsed;
 331         /** but if we should be sorted into a specific place... */
 332         if ((Hash->nLookpTableItems != 0) &&
 333             (HashPos != Hash->nLookpTableItems) ) {
 334                 long ItemsAfter;
 335
 336                 ItemsAfter = Hash->nLookpTableItems - HashPos;
 337                 /** make space were we can fill us in */
 338                 if (ItemsAfter > 0)
 339                 {
 340                         memmove(&Hash->LookupTable[HashPos + 1],
 341                                 &Hash->LookupTable[HashPos],
 342                                 ItemsAfter * sizeof(HashKey*));
 343                 }
 344         }
 345
 346         Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
 347         Hash->LookupTable[HashPos] = NewHashKey;
 348         Hash->nMembersUsed++;
 349         Hash->nLookpTableItems++;
 350 }
 351
 352 /**
 353  * @brief if the user has tainted the hash, but wants to insert / search items by their key
 354  *  we need to search linear through the array. You have been warned that this will take more time!
 355  * @param Hash Our Hash to manipulate
 356  * @param HashBinKey the Hash-Number to lookup.
 357  * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
 358  */
 359 static long FindInTaintedHash(HashList *Hash, long HashBinKey)
 360 {
 361         long SearchPos;
 362
 363         if (Hash == NULL)
 364                 return 0;
 365
 366         for (SearchPos = 0; SearchPos < Hash->nLookpTableItems; SearchPos ++) {
 367                 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
 368                         return SearchPos;
 369                 }
 370         }
 371         return SearchPos;
 372 }
 373
 374 /**
 375  * @brief Private function to lookup the Item / the closest position to put it in
 376  * @param Hash Our Hash to manipulate
 377  * @param HashBinKey the Hash-Number to lookup.
 378  * \returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
 379  */
 380 static long FindInHash(HashList *Hash, long HashBinKey)
 381 {
 382         long SearchPos;
 383         long StepWidth;
 384
 385         if (Hash == NULL)
 386                 return 0;
 387
 388         if (Hash->tainted)
 389                 return FindInTaintedHash(Hash, HashBinKey);
 390
 391         SearchPos = Hash->nLookpTableItems / 2;
 392         StepWidth = SearchPos / 2;
 393         while ((SearchPos > 0) &&
 394                (SearchPos < Hash->nLookpTableItems))
 395         {
 396                 /** Did we find it? */
 397                 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
 398                         return SearchPos;
 399                 }
 400                 /** are we Aproximating in big steps? */
 401                 if (StepWidth > 1){
 402                         if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
 403                                 SearchPos -= StepWidth;
 404                         else
 405                                 SearchPos += StepWidth;
 406                         StepWidth /= 2;
 407                 }
 408                 else { /** We are right next to our target, within 4 positions */
 409                         if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
 410                                 if ((SearchPos > 0) &&
 411                                     (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
 412                                         return SearchPos;
 413                                 SearchPos --;
 414                         }
 415                         else {
 416                                 if ((SearchPos + 1 < Hash->nLookpTableItems) &&
 417                                     (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
 418                                         return SearchPos;
 419                                 SearchPos ++;
 420                         }
 421                         StepWidth--;
 422                 }
 423         }
 424         return SearchPos;
 425 }
 426
 427
 428 /**
 429  * @brief another hashing algorithm; treat it as just a pointer to long.
 430  * @param str Our pointer to the long value
 431  * @param len the length of the data pointed to; needs to be sizeof int, else we won't use it!
 432  * \returns the calculated hash value
 433  */
 434 int Flathash(const char *str, long len)
 435 {
 436         if (len != sizeof (int))
 437                 return 0;
 438         else return *(int*)str;
 439 }
 440
 441 /**
 442  * @brief private abstract wrapper around the hashing algorithm
 443  * @param HKey the hash string
 444  * @param HKLen length of HKey
 445  * \returns the calculated hash value
 446  */
 447 inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
 448 {
 449         if (Hash == NULL)
 450                 return 0;
 451
 452         if (Hash->Algorithm == NULL)
 453                 return hashlittle(HKey, HKLen, 9283457);
 454         else
 455                 return Hash->Algorithm(HKey, HKLen);
 456 }
 457
 458
 459 /**
 460  * @brief Add a new / Replace an existing item in the Hash
 461  * @param HashList the list to manipulate
 462  * @param HKey the hash-string to store Data under
 463  * @param HKeyLen Length of HKey
 464  * @param Data the payload you want to associate with HKey
 465  * @param DeleteIt if not free() should be used to delete Data set to NULL, else DeleteIt is used.
 466  */
 467 void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
 468 {
 469         long HashBinKey;
 470         long HashAt;
 471
 472         if (Hash == NULL)
 473                 return;
 474
 475         /** first, find out were we could fit in... */
 476         HashBinKey = CalcHashKey(Hash, HKey, HKLen);
 477         HashAt = FindInHash(Hash, HashBinKey);
 478
 479         if (HashAt >= Hash->MemberSize)
 480                 IncreaseHashSize (Hash);
 481
 482         /** oh, we're brand new... */
 483         if (Hash->LookupTable[HashAt] == NULL) {
 484                 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
 485         }/** Insert After? */
 486         else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
 487                 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
 488         }/** Insert before? */
 489         else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
 490                 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
 491         }
 492         else { /** Ok, we have a colision. replace it. */
 493                 if (Hash->uniq) {
 494                         long PayloadPos;
 495
 496                         PayloadPos = Hash->LookupTable[HashAt]->Position;
 497                         DeleteHashPayload(Hash->Members[PayloadPos]);
 498                         Hash->Members[PayloadPos]->Data = Data;
 499                         Hash->Members[PayloadPos]->Destructor = DeleteIt;
 500                 }
 501                 else {
 502                         InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
 503                 }
 504         }
 505 }
 506
 507 /**
 508  * @brief Lookup the Data associated with HKey
 509  * @param Hash the Hashlist to search in
 510  * @param HKey the hashkey to look up
 511  * @param HKLen length of HKey
 512  * @param Data returns the Data associated with HKey
 513  * \returns 0 if not found, 1 if.
 514  */
 515 int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data)
 516 {
 517         long HashBinKey;
 518         long HashAt;
 519
 520         if (Hash == NULL)
 521                 return 0;
 522
 523         if (HKLen <= 0) {
 524                 *Data = NULL;
 525                 return  0;
 526         }
 527         /** first, find out were we could be... */
 528         HashBinKey = CalcHashKey(Hash, HKey, HKLen);
 529         HashAt = FindInHash(Hash, HashBinKey);
 530         if ((HashAt < 0) || /**< Not found at the lower edge? */
 531             (HashAt >= Hash->nLookpTableItems) || /**< Not found at the upper edge? */
 532             (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
 533                 *Data = NULL;
 534                 return 0;
 535         }
 536         else { /** GOTCHA! */
 537                 long MemberPosition;
 538
 539                 MemberPosition = Hash->LookupTable[HashAt]->Position;
 540                 *Data = Hash->Members[MemberPosition]->Data;
 541                 return 1;
 542         }
 543 }
 544
 545 /* TODO? */
 546 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
 547 {
 548         return 0;
 549 }
 550
 551 /**
 552  * @brief get the Keys present in this hash, simila to array_keys() in PHP
 553  *  Attention: List remains to Hash! don't modify or free it!
 554  * @param Hash Your Hashlist to extract the keys from
 555  * @param List returns the list of hashkeys stored in Hash
 556  */
 557 int GetHashKeys(HashList *Hash, char ***List)
 558 {
 559         long i;
 560         if (Hash == NULL)
 561                 return 0;
 562         if (Hash->MyKeys != NULL)
 563                 free (Hash->MyKeys);
 564
 565         Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookpTableItems);
 566         for (i=0; i < Hash->nLookpTableItems; i++) {
 567
 568                 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
 569         }
 570         *List = (char**)Hash->MyKeys;
 571         return Hash->nLookpTableItems;
 572 }
 573
 574 /**
 575  * @brief creates a hash-linear iterator object
 576  * @param Hash the list we reference
 577  * @param in which step width should we iterate?
 578  *  If negative, the last position matching the
 579  *  step-raster is provided.
 580  * \returns the hash iterator
 581  */
 582 HashPos *GetNewHashPos(HashList *Hash, int StepWidth)
 583 {
 584         HashPos *Ret;
 585
 586         Ret = (HashPos*)malloc(sizeof(HashPos));
 587         if (StepWidth != 0)
 588                 Ret->StepWidth = StepWidth;
 589         else
 590                 Ret->StepWidth = 1;
 591         if (Ret->StepWidth <  0) {
 592                 Ret->Position = Hash->nLookpTableItems - 1;
 593         }
 594         else {
 595                 Ret->Position = 0;
 596         }
 597         return Ret;
 598 }
 599
 600 /**
 601  * @brief Set iterator object to point to key. If not found, don't change iterator
 602  * @param Hash the list we reference
 603  * @param HKey key to search for
 604  * @param HKLen length of key
 605  * @param At HashPos to update
 606  * \returns 0 if not found
 607  */
 608 int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At)
 609 {
 610         long HashBinKey;
 611         long HashAt;
 612
 613         if (Hash == NULL)
 614                 return 0;
 615
 616         if (HKLen <= 0) {
 617                 return  0;
 618         }
 619         /** first, find out were we could be... */
 620         HashBinKey = CalcHashKey(Hash, HKey, HKLen);
 621         HashAt = FindInHash(Hash, HashBinKey);
 622         if ((HashAt < 0) || /**< Not found at the lower edge? */
 623             (HashAt >= Hash->nLookpTableItems) || /**< Not found at the upper edge? */
 624             (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
 625                 return 0;
 626         }
 627         /** GOTCHA! */
 628         At->Position = Hash->LookupTable[HashAt]->Position;
 629         return 1;
 630 }
 631
 632 /**
 633  * @brief Delete from the Hash the entry at Position
 634  * @param Hash the list we reference
 635  * @param At the position within the Hash
 636  * \returns 0 if not found
 637  */
 638 int DeleteEntryFromHash(HashList *Hash, HashPos *At)
 639 {
 640         Payload *FreeMe;
 641         if (Hash == NULL)
 642                 return 0;
 643
 644         /* if lockable, lock here */
 645         if ((Hash == NULL) ||
 646             (At->Position >= Hash->nLookpTableItems) ||
 647             (At->Position < 0) ||
 648             (At->Position > Hash->nLookpTableItems))
 649         {
 650                 /* unlock... */
 651                 return 0;
 652         }
 653
 654         FreeMe = Hash->Members[At->Position];
 655         Hash->Members[At->Position] = NULL;
 656
 657
 658         /** delete our hashing data */
 659         if (Hash->LookupTable[At->Position] != NULL)
 660         {
 661                 free(Hash->LookupTable[At->Position]->HashKey);
 662                 free(Hash->LookupTable[At->Position]);
 663                 if (At->Position < Hash->nLookpTableItems)
 664                 {
 665                         memmove(&Hash->LookupTable[At->Position],
 666                                 &Hash->LookupTable[At->Position + 1],
 667                                 (Hash->nLookpTableItems - At->Position - 1) *
 668                                 sizeof(HashKey*));
 669
 670                 }
 671                 else
 672                         Hash->LookupTable[At->Position] = NULL;
 673                 Hash->nLookpTableItems--;
 674         }
 675         /* unlock... */
 676
 677
 678         /** get rid of our payload */
 679         if (FreeMe != NULL)
 680         {
 681                 DeleteHashPayload(FreeMe);
 682                 free(FreeMe);
 683         }
 684         return 1;
 685 }
 686
 687 /**
 688  * @brief retrieve the counter from the itteratoor
 689  * @param the Iterator to analyze
 690  * \returns the n'th hashposition we point at
 691  */
 692 int GetHashPosCounter(HashList *Hash, HashPos *At)
 693 {
 694         if ((Hash == NULL) ||
 695             (At->Position >= Hash->nLookpTableItems) ||
 696             (At->Position < 0) ||
 697             (At->Position > Hash->nLookpTableItems))
 698                 return 0;
 699         return At->Position;
 700 }
 701
 702 /**
 703  * @brief frees a linear hash iterator
 704  */
 705 void DeleteHashPos(HashPos **DelMe)
 706 {
 707         if (*DelMe != NULL)
 708         {
 709                 free(*DelMe);
 710                 *DelMe = NULL;
 711         }
 712 }
 713
 714
 715 /**
 716  * @brief Get the data located where HashPos Iterator points at, and Move HashPos one forward
 717  * @param Hash your Hashlist to follow
 718  * @param HKLen returns Length of Hashkey Returned
 719  * @param HashKey returns the Hashkey corrosponding to HashPos
 720  * @param Data returns the Data found at HashPos
 721  * \returns whether the item was found or not.
 722  */
 723 int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
 724 {
 725         long PayloadPos;
 726
 727         if ((Hash == NULL) ||
 728             (At->Position >= Hash->nLookpTableItems) ||
 729             (At->Position < 0) ||
 730             (At->Position > Hash->nLookpTableItems))
 731                 return 0;
 732         *HKLen = Hash->LookupTable[At->Position]->HKLen;
 733         *HashKey = Hash->LookupTable[At->Position]->HashKey;
 734         PayloadPos = Hash->LookupTable[At->Position]->Position;
 735         *Data = Hash->Members[PayloadPos]->Data;
 736
 737         /* Position is NULL-Based, while Stepwidth is not... */
 738         if ((At->Position % abs(At->StepWidth)) == 0)
 739                 At->Position += At->StepWidth;
 740         else
 741                 At->Position += ((At->Position) % abs(At->StepWidth)) *
 742                         (At->StepWidth / abs(At->StepWidth));
 743         return 1;
 744 }
 745
 746 /**
 747  * @brief Get the data located where At points to
 748  * note: you should prefer iterator operations instead of using me.
 749  * @param Hash your Hashlist peek from
 750  * @param HKLen returns Length of Hashkey Returned
 751  * @param HashKey returns the Hashkey corrosponding to HashPos
 752  * @param Data returns the Data found at HashPos
 753  * \returns whether the item was found or not.
 754  */
 755 int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data)
 756 {
 757         long PayloadPos;
 758
 759         if ((Hash == NULL) ||
 760             (At < 0) ||
 761             (At > Hash->nLookpTableItems))
 762                 return 0;
 763         *HKLen = Hash->LookupTable[At]->HKLen;
 764         *HashKey = Hash->LookupTable[At]->HashKey;
 765         PayloadPos = Hash->LookupTable[At]->Position;
 766         *Data = Hash->Members[PayloadPos]->Data;
 767         return 1;
 768 }
 769
 770 /**
 771  * @brief Get the data located where At points to
 772  * note: you should prefer iterator operations instead of using me.
 773  * @param Hash your Hashlist peek from
 774  * @param HKLen returns Length of Hashkey Returned
 775  * @param HashKey returns the Hashkey corrosponding to HashPos
 776  * @param Data returns the Data found at HashPos
 777  * \returns whether the item was found or not.
 778  */
 779 /*
 780 long GetHashIDAt(HashList *Hash,long At)
 781 {
 782         if ((Hash == NULL) ||
 783             (At < 0) ||
 784             (At > Hash->nLookpTableItems))
 785                 return 0;
 786
 787         return Hash->LookupTable[At]->Key;
 788 }
 789 */
 790
 791
 792 /**
 793  * @brief sorting function for sorting the Hash alphabeticaly by their strings
 794  * @param Key1 first item
 795  * @param Key2 second item
 796  */
 797 static int SortByKeys(const void *Key1, const void* Key2)
 798 {
 799         HashKey *HKey1, *HKey2;
 800         HKey1 = *(HashKey**) Key1;
 801         HKey2 = *(HashKey**) Key2;
 802
 803         return strcasecmp(HKey1->HashKey, HKey2->HashKey);
 804 }
 805
 806 /**
 807  * @brief sorting function for sorting the Hash alphabeticaly reverse by their strings
 808  * @param Key1 first item
 809  * @param Key2 second item
 810  */
 811 static int SortByKeysRev(const void *Key1, const void* Key2)
 812 {
 813         HashKey *HKey1, *HKey2;
 814         HKey1 = *(HashKey**) Key1;
 815         HKey2 = *(HashKey**) Key2;
 816
 817         return strcasecmp(HKey2->HashKey, HKey1->HashKey);
 818 }
 819
 820 /**
 821  * @brief sorting function to regain hash-sequence and revert tainted status
 822  * @param Key1 first item
 823  * @param Key2 second item
 824  */
 825 static int SortByHashKeys(const void *Key1, const void* Key2)
 826 {
 827         HashKey *HKey1, *HKey2;
 828         HKey1 = *(HashKey**) Key1;
 829         HKey2 = *(HashKey**) Key2;
 830
 831         return HKey1->Key > HKey2->Key;
 832 }
 833
 834
 835 /**
 836  * @brief sort the hash alphabeticaly by their keys.
 837  * Caution: This taints the hashlist, so accessing it later
 838  * will be significantly slower! You can un-taint it by SortByHashKeyStr
 839  * @param Hash the list to sort
 840  * @param Order 0/1 Forward/Backward
 841  */
 842 void SortByHashKey(HashList *Hash, int Order)
 843 {
 844         if (Hash->nLookpTableItems < 2)
 845                 return;
 846         qsort(Hash->LookupTable, Hash->nLookpTableItems, sizeof(HashKey*),
 847               (Order)?SortByKeys:SortByKeysRev);
 848         Hash->tainted = 1;
 849 }
 850
 851 /**
 852  * @brief sort the hash by their keys (so it regains untainted state).
 853  * this will result in the sequence the hashing allgorithm produces it by default.
 854  * @param Hash the list to sort
 855  */
 856 void SortByHashKeyStr(HashList *Hash)
 857 {
 858         Hash->tainted = 0;
 859         if (Hash->nLookpTableItems < 2)
 860                 return;
 861         qsort(Hash->LookupTable, Hash->nLookpTableItems, sizeof(HashKey*), SortByHashKeys);
 862 }
 863
 864
 865 /**
 866  * @brief gives user sort routines access to the hash payload
 867  * @param Searchentry to retrieve Data to
 868  * \returns Data belonging to HashVoid
 869  */
 870 const void *GetSearchPayload(const void *HashVoid)
 871 {
 872         return (*(HashKey**)HashVoid)->PL->Data;
 873 }
 874
 875 /**
 876  * @brief sort the hash by your sort function. see the following sample.
 877  * this will result in the sequence the hashing allgorithm produces it by default.
 878  * @param Hash the list to sort
 879  * @param SortBy Sortfunction; see below how to implement this
 880  */
 881 void SortByPayload(HashList *Hash, CompareFunc SortBy)
 882 {
 883         if (Hash->nLookpTableItems < 2)
 884                 return;
 885         qsort(Hash->LookupTable, Hash->nLookpTableItems, sizeof(HashKey*), SortBy);
 886         Hash->tainted = 1;
 887 }
 888
 889
 890
 891
 892 /**
 893  * given you've put char * into your hash as a payload, a sort function might
 894  * look like this:
 895  * int SortByChar(const void* First, const void* Second)
 896  * {
 897  *      char *a, *b;
 898  *      a = (char*) GetSearchPayload(First);
 899  *      b = (char*) GetSearchPayload(Second);
 900  *      return strcmp (a, b);
 901  * }
 902  */
 903
 904
 905 /*
 906  * Generic function to free a pointer.  This can be used as a callback with the
 907  * hash table, even on systems where free() is defined as a macro or has had other
 908  * horrible things done to it.
 909  */
 910 void generic_free_handler(void *ptr) {
 911         free(ptr);
 912 }
 913
 914 /*
 915  * Generic function to free a reference.
 916  * since a reference actualy isn't needed to be freed, do nothing.
 917  */
 918 void reference_free_handler(void *ptr)
 919 {
 920         return;
 921 }
 922
 923
 924 /*
 925  * This exposes the hashlittle() function to consumers.
 926  */
 927 int HashLittle(const void *key, size_t length) {
 928         return (int)hashlittle(key, length, 1);
 929 }
 930