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