libcitadel/lib/hash.c

   1 // Copyright (c) 1987-2022 by the citadel.org team
   2 //
   3 // Hashlist is a simple implementation of key value pairs. It doesn't implement collision handling.
   4 // the hashing algorithm is pluggeable on creation.
   5 // items are added with a function pointer to a destructor; that way complex structures can be added.
   6 // if no pointer is given, simply free is used. Use reference_free_handler if you don't want us to free your memory.
   7 //
   8 // This program is open source software.  Use, duplication, or disclosure
   9 // is subject to the terms of the GNU General Public License, version 3.
  10
  11 #include <stdint.h>
  12 #include <stdlib.h>
  13 #include <string.h>
  14 #include <limits.h>
  15 #include <stdio.h>
  16 #include "libcitadel.h"
  17 #include "lookup3.h"
  18
  19 typedef struct Payload Payload;
  20
  21
  22 /*
  23  * Hash Payload storage Structure; filled in linear.
  24  */
  25 struct Payload {
  26         void *Data; /**< the Data belonging to this storage */
  27         DeleteHashDataFunc Destructor; /**< if we want to destroy Data, do it with this function. */
  28 };
  29
  30
  31 /*
  32  * Hash key element; sorted by key
  33  */
  34 struct HashKey {
  35         long Key;         /**< Numeric Hashkey comperator for hash sorting */
  36         long Position;    /**< Pointer to a Payload struct in the Payload Aray */
  37         char *HashKey;    /**< the Plaintext Hashkey */
  38         long HKLen;       /**< length of the Plaintext Hashkey */
  39         Payload *PL;      /**< pointer to our payload for sorting */
  40 };
  41
  42 /*
  43  * Hash structure; holds arrays of Hashkey and Payload.
  44  */
  45 struct HashList {
  46         Payload **Members;     /**< Our Payload members. This fills up linear */
  47         HashKey **LookupTable; /**< Hash Lookup table. Elements point to members, and are sorted by their hashvalue */
  48         char **MyKeys;         /**< this keeps the members for a call of GetHashKeys */
  49         HashFunc Algorithm;    /**< should we use an alternating algorithm to calc the hash values? */
  50         long nMembersUsed;     /**< how many pointers inside of the array are used? */
  51         long nLookupTableItems; /**< how many items of the lookup table are used? */
  52         long MemberSize;       /**< how big is Members and LookupTable? */
  53         long tainted;          /**< if 0, we're hashed, else s.b. else sorted us in his own way. */
  54         long uniq;             /**< are the keys going to be uniq? */
  55 };
  56
  57 /*
  58  * Anonymous Hash Iterator Object. used for traversing the whole array from outside
  59  */
  60 struct HashPos {
  61         long Position;        /**< Position inside of the hash */
  62         int StepWidth;        /**< small? big? forward? backward? */
  63 };
  64
  65
  66 /*
  67  * Iterate over the hash and call PrintEntry.
  68  * Hash your Hashlist structure
  69  * Trans is called so you could for example print 'A:' if the next entries are like that.
  70  *        Must be aware to receive NULL in both pointers.
  71  * PrintEntry print entry one by one
  72  * returns the number of items printed
  73  */
  74 int PrintHash(HashList *Hash, TransitionFunc Trans, PrintHashDataFunc PrintEntry) {
  75         int i;
  76         void *Previous;
  77         void *Next;
  78         const char* KeyStr;
  79
  80         if (Hash == NULL)
  81                 return 0;
  82
  83         for (i=0; i < Hash->nLookupTableItems; i++) {
  84                 if (i==0) {
  85                         Previous = NULL;
  86                 }
  87                 else {
  88                         if (Hash->LookupTable[i - 1] == NULL)
  89                                 Previous = NULL;
  90                         else
  91                                 Previous = Hash->Members[Hash->LookupTable[i-1]->Position]->Data;
  92                 }
  93                 if (Hash->LookupTable[i] == NULL) {
  94                         KeyStr = "";
  95                         Next = NULL;
  96                 }
  97                 else {
  98                         Next = Hash->Members[Hash->LookupTable[i]->Position]->Data;
  99                         KeyStr = Hash->LookupTable[i]->HashKey;
 100                 }
 101
 102                 Trans(Previous, Next, i % 2);
 103                 PrintEntry(KeyStr, Next, i % 2);
 104         }
 105         return i;
 106 }
 107
 108 const char *dbg_PrintStrBufPayload(const char *Key, void *Item, int Odd) {
 109         return ChrPtr((StrBuf*)Item);
 110 }
 111
 112 /*
 113  * verify the contents of a hash list; here for debugging purposes.
 114  * Hash your Hashlist structure
 115  * First Functionpointer to allow you to print your payload
 116  * Second Functionpointer to allow you to print your payload
 117  * returns 0
 118  */
 119 int dbg_PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second) {
 120 #ifdef DEBUG
 121         const char *foo;
 122         const char *bar;
 123         const char *bla = "";
 124         long key;
 125 #endif
 126         long i;
 127
 128         if (Hash == NULL)
 129                 return 0;
 130
 131         if (Hash->MyKeys != NULL)
 132                 free (Hash->MyKeys);
 133
 134         Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
 135 #ifdef DEBUG
 136         printf("----------------------------------\n");
 137 #endif
 138         for (i=0; i < Hash->nLookupTableItems; i++) {
 139
 140                 if (Hash->LookupTable[i] == NULL)
 141                 {
 142 #ifdef DEBUG
 143                         foo = "";
 144                         bar = "";
 145                         key = 0;
 146 #endif
 147                 }
 148                 else
 149                 {
 150 #ifdef DEBUG
 151                         key = Hash->LookupTable[i]->Key;
 152                         foo = Hash->LookupTable[i]->HashKey;
 153 #endif
 154                         if (First != NULL)
 155 #ifdef DEBUG
 156                                 bar =
 157 #endif
 158                                         First(Hash->Members[Hash->LookupTable[i]->Position]->Data);
 159 #ifdef DEBUG
 160                         else
 161                                 bar = "";
 162 #endif
 163
 164                         if (Second != NULL)
 165 #ifdef DEBUG
 166                                 bla =
 167 #endif
 168                                         Second(Hash->Members[Hash->LookupTable[i]->Position]->Data);
 169 #ifdef DEBUG
 170
 171                         else
 172                                 bla = "";
 173 #endif
 174
 175                 }
 176 #ifdef DEBUG
 177                 if ((Hash->Algorithm == lFlathash) || (Hash->Algorithm == Flathash)) {
 178                         printf (" ---- Hashkey[%ld][%ld]: %ld '%s' Value: '%s' ; %s\n", i, key, *(long*) foo, foo, bar, bla);
 179                 }
 180                 else {
 181                         printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' ; %s\n", i, key, foo, bar, bla);
 182                 }
 183 #endif
 184         }
 185 #ifdef DEBUG
 186         printf("----------------------------------\n");
 187 #endif
 188         return 0;
 189 }
 190
 191
 192 int TestValidateHash(HashList *TestHash) {
 193         long i;
 194
 195         if (TestHash->nMembersUsed != TestHash->nLookupTableItems)
 196                 return 1;
 197
 198         if (TestHash->nMembersUsed > TestHash->MemberSize)
 199                 return 2;
 200
 201         for (i=0; i < TestHash->nMembersUsed; i++) {
 202
 203                 if (TestHash->LookupTable[i]->Position > TestHash->nMembersUsed)
 204                         return 3;
 205
 206                 if (TestHash->Members[TestHash->LookupTable[i]->Position] == NULL)
 207                         return 4;
 208                 if (TestHash->Members[TestHash->LookupTable[i]->Position]->Data == NULL)
 209                         return 5;
 210         }
 211         return 0;
 212 }
 213
 214 /*
 215  * instanciate a new hashlist
 216  * returns the newly allocated list.
 217  */
 218 HashList *NewHash(int Uniq, HashFunc F) {
 219         HashList *NewList;
 220         NewList = malloc (sizeof(HashList));
 221         if (NewList == NULL)
 222                 return NULL;
 223         memset(NewList, 0, sizeof(HashList));
 224
 225         NewList->Members = malloc(sizeof(Payload*) * 100);
 226         if (NewList->Members == NULL) {
 227                 free(NewList);
 228                 return NULL;
 229         }
 230         memset(NewList->Members, 0, sizeof(Payload*) * 100);
 231
 232         NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
 233         if (NewList->LookupTable == NULL) {
 234                 free(NewList->Members);
 235                 free(NewList);
 236                 return NULL;
 237         }
 238         memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
 239
 240         NewList->MemberSize = 100;
 241         NewList->tainted = 0;
 242         NewList->uniq = Uniq;
 243         NewList->Algorithm = F;
 244
 245         return NewList;
 246 }
 247
 248 int GetCount(HashList *Hash) {
 249         if(Hash==NULL) return 0;
 250         return Hash->nLookupTableItems;
 251 }
 252
 253
 254 /*
 255  * private destructor for one hash element.
 256  * Crashing? go one frame up and do 'print *FreeMe->LookupTable[i]'
 257  * Data an element to free using the user provided destructor, or just plain free
 258  */
 259 static void DeleteHashPayload (Payload *Data) {
 260         /** do we have a destructor for our payload? */
 261         if (Data->Destructor)
 262                 Data->Destructor(Data->Data);
 263         else
 264                 free(Data->Data);
 265 }
 266
 267 /*
 268  * Destructor for nested hashes
 269  */
 270 void HDeleteHash(void *vHash) {
 271         HashList *FreeMe = (HashList*)vHash;
 272         DeleteHash(&FreeMe);
 273 }
 274
 275 /*
 276  * flush the members of a hashlist
 277  * Crashing? do 'print *FreeMe->LookupTable[i]'
 278  * Hash Hash to destroy. Is NULL'ed so you are shure its done.
 279  */
 280 void DeleteHashContent(HashList **Hash) {
 281         int i;
 282         HashList *FreeMe;
 283
 284         FreeMe = *Hash;
 285         if (FreeMe == NULL)
 286                 return;
 287         /* even if there are sparse members already deleted... */
 288         for (i=0; i < FreeMe->nMembersUsed; i++) {
 289                 /** get rid of our payload */
 290                 if (FreeMe->Members[i] != NULL) {
 291                         DeleteHashPayload(FreeMe->Members[i]);
 292                         free(FreeMe->Members[i]);
 293                 }
 294                 /** delete our hashing data */
 295                 if (FreeMe->LookupTable[i] != NULL) {
 296                         free(FreeMe->LookupTable[i]->HashKey);
 297                         free(FreeMe->LookupTable[i]);
 298                 }
 299         }
 300         FreeMe->nMembersUsed = 0;
 301         FreeMe->tainted = 0;
 302         FreeMe->nLookupTableItems = 0;
 303         memset(FreeMe->Members, 0, sizeof(Payload*) * FreeMe->MemberSize);
 304         memset(FreeMe->LookupTable, 0, sizeof(HashKey*) * FreeMe->MemberSize);
 305
 306         // free the array of our keys
 307         if (FreeMe->MyKeys != NULL)
 308                 free(FreeMe->MyKeys);
 309 }
 310
 311
 312 /*
 313  * destroy a hashlist and all of its members
 314  * Crashing? do 'print *FreeMe->LookupTable[i]'
 315  * Hash Hash to destroy. Is NULL'ed so you are shure its done.
 316  */
 317 void DeleteHash(HashList **Hash) {
 318         HashList *FreeMe;
 319
 320         FreeMe = *Hash;
 321         if (FreeMe == NULL)
 322                 return;
 323         DeleteHashContent(Hash);
 324         /** now, free our arrays... */
 325         free(FreeMe->LookupTable);
 326         free(FreeMe->Members);
 327
 328         /** buye bye cruel world. */
 329         free (FreeMe);
 330         *Hash = NULL;
 331 }
 332
 333
 334 /*
 335  * Private function to increase the hash size.
 336  * Hash the Hasharray to increase
 337  */
 338 static int IncreaseHashSize(HashList *Hash) {
 339         /* Ok, Our space is used up. Double the available space. */
 340         Payload **NewPayloadArea;
 341         HashKey **NewTable;
 342
 343         if (Hash == NULL)
 344                 return 0;
 345
 346         /** If we grew to much, this might be the place to rehash and shrink again.
 347         if ((Hash->NMembersUsed > Hash->nLookupTableItems) &&
 348             ((Hash->NMembersUsed - Hash->nLookupTableItems) >
 349              (Hash->nLookupTableItems / 10)))
 350         {
 351
 352
 353         }
 354         */
 355
 356         NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
 357         if (NewPayloadArea == NULL)
 358                 return 0;
 359         NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
 360         if (NewTable == NULL) {
 361                 free(NewPayloadArea);
 362                 return 0;
 363         }
 364
 365         /** double our payload area */
 366         memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
 367         memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
 368         free(Hash->Members);
 369         Hash->Members = NewPayloadArea;
 370
 371         /** double our hashtable area */
 372         memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
 373         memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
 374         free(Hash->LookupTable);
 375         Hash->LookupTable = NewTable;
 376
 377         Hash->MemberSize *= 2;
 378         return 1;
 379 }
 380
 381
 382 /*
 383  * private function to add a new item to / replace an existing in -  the hashlist
 384  * if the hash list is full, its re-alloced with double size.
 385  * Hash our hashlist to manipulate
 386  * HashPos where should we insert / replace?
 387  * HashKeyStr the Hash-String
 388  * HKLen length of HashKeyStr
 389  * Data your Payload to add
 390  * Destructor Functionpointer to free Data. if NULL, default free() is used.
 391  */
 392 static int InsertHashItem(HashList *Hash,
 393                           long HashPos,
 394                           long HashBinKey,
 395                           const char *HashKeyStr,
 396                           long HKLen,
 397                           void *Data,
 398                           DeleteHashDataFunc Destructor)
 399 {
 400         Payload *NewPayloadItem;
 401         HashKey *NewHashKey;
 402         char *HashKeyOrgVal;
 403
 404         if (Hash == NULL)
 405                 return 0;
 406
 407         if ((Hash->nMembersUsed >= Hash->MemberSize) &&
 408             (!IncreaseHashSize (Hash)))
 409             return 0;
 410
 411         NewPayloadItem = (Payload*) malloc (sizeof(Payload));
 412         if (NewPayloadItem == NULL)
 413                 return 0;
 414         NewHashKey = (HashKey*) malloc (sizeof(HashKey));
 415         if (NewHashKey == NULL) {
 416                 free(NewPayloadItem);
 417                 return 0;
 418         }
 419         HashKeyOrgVal = (char *) malloc (HKLen + 1);
 420         if (HashKeyOrgVal == NULL) {
 421                 free(NewHashKey);
 422                 free(NewPayloadItem);
 423                 return 0;
 424         }
 425
 426
 427         /** Arrange the payload */
 428         NewPayloadItem->Data = Data;
 429         NewPayloadItem->Destructor = Destructor;
 430         /** Arrange the hashkey */
 431         NewHashKey->HKLen = HKLen;
 432         NewHashKey->HashKey = HashKeyOrgVal;
 433         memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
 434         NewHashKey->Key = HashBinKey;
 435         NewHashKey->PL = NewPayloadItem;
 436         /** our payload is queued at the end... */
 437         NewHashKey->Position = Hash->nMembersUsed;
 438         /** but if we should be sorted into a specific place... */
 439         if ((Hash->nLookupTableItems != 0) &&
 440             (HashPos != Hash->nLookupTableItems) ) {
 441                 long ItemsAfter;
 442
 443                 ItemsAfter = Hash->nLookupTableItems - HashPos;
 444                 /** make space were we can fill us in */
 445                 if (ItemsAfter > 0) {
 446                         memmove(&Hash->LookupTable[HashPos + 1], &Hash->LookupTable[HashPos], ItemsAfter * sizeof(HashKey*));
 447                 }
 448         }
 449
 450         Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
 451         Hash->LookupTable[HashPos] = NewHashKey;
 452         Hash->nMembersUsed++;
 453         Hash->nLookupTableItems++;
 454         return 1;
 455 }
 456
 457 /*
 458  * if the user has tainted the hash, but wants to insert / search items by their key
 459  *  we need to search linear through the array. You have been warned that this will take more time!
 460  * Hash Our Hash to manipulate
 461  * HashBinKey the Hash-Number to lookup.
 462  * returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
 463  */
 464 static long FindInTaintedHash(HashList *Hash, long HashBinKey) {
 465         long SearchPos;
 466
 467         if (Hash == NULL)
 468                 return 0;
 469
 470         for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
 471                 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
 472                         return SearchPos;
 473                 }
 474         }
 475         return SearchPos;
 476 }
 477
 478 /*
 479  * Private function to lookup the Item / the closest position to put it in
 480  * Hash Our Hash to manipulate
 481  * HashBinKey the Hash-Number to lookup.
 482  * returns the position (most closely) matching HashBinKey (-> Caller needs to compare! )
 483  */
 484 static long FindInHash(HashList *Hash, long HashBinKey) {
 485         long SearchPos;
 486         long StepWidth;
 487
 488         if (Hash == NULL)
 489                 return 0;
 490
 491         if (Hash->tainted)
 492                 return FindInTaintedHash(Hash, HashBinKey);
 493
 494         SearchPos = Hash->nLookupTableItems / 2;
 495         StepWidth = SearchPos / 2;
 496         while ((SearchPos > 0) && (SearchPos < Hash->nLookupTableItems)) {
 497                 /** Did we find it? */
 498                 if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
 499                         return SearchPos;
 500                 }
 501                 /** are we Aproximating in big steps? */
 502                 if (StepWidth > 1){
 503                         if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
 504                                 SearchPos -= StepWidth;
 505                         else
 506                                 SearchPos += StepWidth;
 507                         StepWidth /= 2;
 508                 }
 509                 else { /** We are right next to our target, within 4 positions */
 510                         if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
 511                                 if ((SearchPos > 0) && (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
 512                                         return SearchPos;
 513                                 SearchPos --;
 514                         }
 515                         else {
 516                                 if ((SearchPos + 1 < Hash->nLookupTableItems) && (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey)) {
 517                                         return SearchPos;
 518                                 }
 519                                 SearchPos ++;
 520                         }
 521                         StepWidth--;
 522                 }
 523         }
 524         return SearchPos;
 525 }
 526
 527
 528 /*
 529  * another hashing algorithm; treat it as just a pointer to int.
 530  * str Our pointer to the int value
 531  * len the length of the data pointed to; needs to be sizeof int, else we won't use it!
 532  * returns the calculated hash value
 533  */
 534 long Flathash(const char *str, long len) {
 535         if (len != sizeof (int)) {
 536 #ifdef DEBUG
 537                 int *crash = NULL;
 538                 *crash = 1;
 539 #endif
 540                 return 0;
 541         }
 542         else return *(int*)str;
 543 }
 544
 545 /*
 546  * another hashing algorithm; treat it as just a pointer to long.
 547  * str Our pointer to the long value
 548  * len the length of the data pointed to; needs to be sizeof long, else we won't use it!
 549  * returns the calculated hash value
 550  */
 551 long lFlathash(const char *str, long len) {
 552         if (len != sizeof (long)) {
 553 #ifdef DEBUG
 554                 int *crash = NULL;
 555                 *crash = 1;
 556 #endif
 557                 return 0;
 558         }
 559         else return *(long*)str;
 560 }
 561
 562 /*
 563  * another hashing algorithm; accepts exactly 4 characters, convert it to a hash key.
 564  * str Our pointer to the long value
 565  * len the length of the data pointed to; needs to be sizeof long, else we won't use it!
 566  * returns the calculated hash value
 567  */
 568 long FourHash(const char *key, long length) {
 569         int i;
 570         int ret = 0;
 571         const unsigned char *ptr = (const unsigned char*)key;
 572
 573         for (i = 0; i < 4; i++, ptr ++)
 574                 ret = (ret << 8) |
 575                         ( ((*ptr >= 'a') &&
 576                            (*ptr <= 'z'))?
 577                           *ptr - 'a' + 'A':
 578                           *ptr);
 579
 580         return ret;
 581 }
 582
 583 /*
 584  * private abstract wrapper around the hashing algorithm
 585  * HKey the hash string
 586  * HKLen length of HKey
 587  * returns the calculated hash value
 588  */
 589 inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen) {
 590         if (Hash == NULL)
 591                 return 0;
 592
 593         if (Hash->Algorithm == NULL)
 594                 return hashlittle(HKey, HKLen, 9283457);
 595         else
 596                 return Hash->Algorithm(HKey, HKLen);
 597 }
 598
 599
 600 /*
 601  * Add a new / Replace an existing item in the Hash
 602  * Hash the list to manipulate
 603  * HKey the hash-string to store Data under
 604  * HKLen Length of HKey
 605  * Data the payload you want to associate with HKey
 606  * DeleteIt if not free() should be used to delete Data set to NULL, else DeleteIt is used.
 607  */
 608 void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt) {
 609         long HashBinKey;
 610         long HashAt;
 611
 612         if (Hash == NULL)
 613                 return;
 614
 615         /** first, find out were we could fit in... */
 616         HashBinKey = CalcHashKey(Hash, HKey, HKLen);
 617         HashAt = FindInHash(Hash, HashBinKey);
 618
 619         if ((HashAt >= Hash->MemberSize) &&
 620             (!IncreaseHashSize (Hash)))
 621                 return;
 622
 623         /** oh, we're brand new... */
 624         if (Hash->LookupTable[HashAt] == NULL) {
 625                 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
 626         }/** Insert Before? */
 627         else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
 628                 InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
 629         }/** Insert After? */
 630         else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
 631                 InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
 632         }
 633         else { /** Ok, we have a colision. replace it. */
 634                 if (Hash->uniq) {
 635                         long PayloadPos;
 636
 637                         PayloadPos = Hash->LookupTable[HashAt]->Position;
 638                         DeleteHashPayload(Hash->Members[PayloadPos]);
 639                         Hash->Members[PayloadPos]->Data = Data;
 640                         Hash->Members[PayloadPos]->Destructor = DeleteIt;
 641                 }
 642                 else {
 643                         InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
 644                 }
 645         }
 646 }
 647
 648 /*
 649  * Lookup the Data associated with HKey
 650  * Hash the Hashlist to search in
 651  * HKey the hashkey to look up
 652  * HKLen length of HKey
 653  * Data returns the Data associated with HKey
 654  * returns 0 if not found, 1 if.
 655  */
 656 int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data) {
 657         long HashBinKey;
 658         long HashAt;
 659
 660         if (Hash == NULL)
 661                 return 0;
 662
 663         if (HKLen <= 0) {
 664                 *Data = NULL;
 665                 return  0;
 666         }
 667         /** first, find out were we could be... */
 668         HashBinKey = CalcHashKey(Hash, HKey, HKLen);
 669         HashAt = FindInHash(Hash, HashBinKey);
 670         if ((HashAt < 0) || /**< Not found at the lower edge? */
 671             (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
 672             (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
 673                 *Data = NULL;
 674                 return 0;
 675         }
 676         else { /** GOTCHA! */
 677                 long MemberPosition;
 678
 679                 MemberPosition = Hash->LookupTable[HashAt]->Position;
 680                 *Data = Hash->Members[MemberPosition]->Data;
 681                 return 1;
 682         }
 683 }
 684
 685 /* TODO? */
 686 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload) {
 687         return 0;
 688 }
 689
 690 /*
 691  * get the Keys present in this hash, similar to array_keys() in PHP
 692  *  Attention: List remains to Hash! don't modify or free it!
 693  * Hash Your Hashlist to extract the keys from
 694  * List returns the list of hashkeys stored in Hash
 695  */
 696 int GetHashKeys(HashList *Hash, char ***List) {
 697         long i;
 698
 699         *List = NULL;
 700         if (Hash == NULL)
 701                 return 0;
 702         if (Hash->MyKeys != NULL)
 703                 free (Hash->MyKeys);
 704
 705         Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
 706         if (Hash->MyKeys == NULL)
 707                 return 0;
 708
 709         for (i=0; i < Hash->nLookupTableItems; i++)
 710         {
 711                 Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
 712         }
 713         *List = (char**)Hash->MyKeys;
 714         return Hash->nLookupTableItems;
 715 }
 716
 717 /*
 718  * creates a hash-linear iterator object
 719  * Hash the list we reference
 720  * StepWidth in which step width should we iterate?
 721  *  If negative, the last position matching the
 722  *  step-raster is provided.
 723  * returns the hash iterator
 724  */
 725 HashPos *GetNewHashPos(const HashList *Hash, int StepWidth) {
 726         HashPos *Ret;
 727
 728         Ret = (HashPos*)malloc(sizeof(HashPos));
 729         if (Ret == NULL)
 730                 return NULL;
 731
 732         if (StepWidth != 0)
 733                 Ret->StepWidth = StepWidth;
 734         else
 735                 Ret->StepWidth = 1;
 736         if (Ret->StepWidth <  0) {
 737                 Ret->Position = Hash->nLookupTableItems - 1;
 738         }
 739         else {
 740                 Ret->Position = 0;
 741         }
 742         return Ret;
 743 }
 744
 745 /*
 746  * resets a hash-linear iterator object
 747  * Hash the list we reference
 748  * StepWidth in which step width should we iterate?
 749  * it the iterator object to manipulate
 750  *  If negative, the last position matching the
 751  *  step-raster is provided.
 752  * returns the hash iterator
 753  */
 754 void RewindHashPos(const HashList *Hash, HashPos *it, int StepWidth) {
 755         if (StepWidth != 0)
 756                 it->StepWidth = StepWidth;
 757         else
 758                 it->StepWidth = 1;
 759         if (it->StepWidth <  0) {
 760                 it->Position = Hash->nLookupTableItems - 1;
 761         }
 762         else {
 763                 it->Position = 0;
 764         }
 765 }
 766
 767 /*
 768  * Set iterator object to point to key. If not found, don't change iterator
 769  * Hash the list we reference
 770  * HKey key to search for
 771  * HKLen length of key
 772  * At HashPos to update
 773  * returns 0 if not found
 774  */
 775 int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At) {
 776         long HashBinKey;
 777         long HashAt;
 778
 779         if (Hash == NULL)
 780                 return 0;
 781
 782         if (HKLen <= 0) {
 783                 return  0;
 784         }
 785         /** first, find out were we could be... */
 786         HashBinKey = CalcHashKey(Hash, HKey, HKLen);
 787         HashAt = FindInHash(Hash, HashBinKey);
 788         if ((HashAt < 0) || /**< Not found at the lower edge? */
 789             (HashAt >= Hash->nLookupTableItems) || /**< Not found at the upper edge? */
 790             (Hash->LookupTable[HashAt]->Key != HashBinKey)) { /**< somewhere inbetween but no match? */
 791                 return 0;
 792         }
 793         /** GOTCHA! */
 794         At->Position = HashAt;
 795         return 1;
 796 }
 797
 798 /*
 799  * Delete from the Hash the entry at Position
 800  * Hash the list we reference
 801  * At the position within the Hash
 802  * returns 0 if not found
 803  */
 804 int DeleteEntryFromHash(HashList *Hash, HashPos *At) {
 805         Payload *FreeMe;
 806         if (Hash == NULL)
 807                 return 0;
 808
 809         /* if lockable, lock here */
 810         if ((Hash == NULL) ||
 811             (At->Position >= Hash->nLookupTableItems) ||
 812             (At->Position < 0) ||
 813             (At->Position > Hash->nLookupTableItems))
 814         {
 815                 /* unlock... */
 816                 return 0;
 817         }
 818
 819         FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
 820         Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;
 821
 822
 823         /** delete our hashing data */
 824         if (Hash->LookupTable[At->Position] != NULL) {
 825                 free(Hash->LookupTable[At->Position]->HashKey);
 826                 free(Hash->LookupTable[At->Position]);
 827                 if (At->Position < Hash->nLookupTableItems) {
 828                         memmove(&Hash->LookupTable[At->Position],
 829                                 &Hash->LookupTable[At->Position + 1],
 830                                 (Hash->nLookupTableItems - At->Position - 1) *
 831                                 sizeof(HashKey*));
 832
 833                         Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
 834                 }
 835                 else
 836                         Hash->LookupTable[At->Position] = NULL;
 837                 Hash->nLookupTableItems--;
 838         }
 839         /* unlock... */
 840
 841
 842         /** get rid of our payload */
 843         if (FreeMe != NULL) {
 844                 DeleteHashPayload(FreeMe);
 845                 free(FreeMe);
 846         }
 847         return 1;
 848 }
 849
 850 /*
 851  * retrieve the counter from the itteratoor
 852  * Hash which
 853  * At the Iterator to analyze
 854  * returns the n'th hashposition we point at
 855  */
 856 int GetHashPosCounter(HashList *Hash, HashPos *At) {
 857         if ((Hash == NULL) ||
 858             (At->Position >= Hash->nLookupTableItems) ||
 859             (At->Position < 0) ||
 860             (At->Position > Hash->nLookupTableItems))
 861                 return 0;
 862         return At->Position;
 863 }
 864
 865 /*
 866  * frees a linear hash iterator
 867  */
 868 void DeleteHashPos(HashPos **DelMe) {
 869         if (*DelMe != NULL) {
 870                 free(*DelMe);
 871                 *DelMe = NULL;
 872         }
 873 }
 874
 875
 876 /*
 877  * Get the data located where HashPos Iterator points at, and Move HashPos one forward
 878  * Hash your Hashlist to follow
 879  * At the position to retrieve the Item from and move forward afterwards
 880  * HKLen returns Length of Hashkey Returned
 881  * HashKey returns the Hashkey corrosponding to HashPos
 882  * Data returns the Data found at HashPos
 883  * returns whether the item was found or not.
 884  */
 885 int GetNextHashPos(const HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data) {
 886         long PayloadPos;
 887
 888         if ((Hash == NULL) ||
 889             (At->Position >= Hash->nLookupTableItems) ||
 890             (At->Position < 0) ||
 891             (At->Position > Hash->nLookupTableItems))
 892                 return 0;
 893         *HKLen = Hash->LookupTable[At->Position]->HKLen;
 894         *HashKey = Hash->LookupTable[At->Position]->HashKey;
 895         PayloadPos = Hash->LookupTable[At->Position]->Position;
 896         *Data = Hash->Members[PayloadPos]->Data;
 897
 898         /* Position is NULL-Based, while Stepwidth is not... */
 899         if ((At->Position % abs(At->StepWidth)) == 0)
 900                 At->Position += At->StepWidth;
 901         else
 902                 At->Position += ((At->Position) % abs(At->StepWidth)) *
 903                         (At->StepWidth / abs(At->StepWidth));
 904         return 1;
 905 }
 906
 907 /*
 908  * Get the data located where HashPos Iterator points at
 909  * Hash your Hashlist to follow
 910  * At the position retrieve the data from
 911  * HKLen returns Length of Hashkey Returned
 912  * HashKey returns the Hashkey corrosponding to HashPos
 913  * Data returns the Data found at HashPos
 914  * returns whether the item was found or not.
 915  */
 916 int GetHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data) {
 917         long PayloadPos;
 918
 919         if ((Hash == NULL) ||
 920             (At->Position >= Hash->nLookupTableItems) ||
 921             (At->Position < 0) ||
 922             (At->Position > Hash->nLookupTableItems))
 923                 return 0;
 924         *HKLen = Hash->LookupTable[At->Position]->HKLen;
 925         *HashKey = Hash->LookupTable[At->Position]->HashKey;
 926         PayloadPos = Hash->LookupTable[At->Position]->Position;
 927         *Data = Hash->Members[PayloadPos]->Data;
 928
 929         return 1;
 930 }
 931
 932 /*
 933  * Move HashPos one forward
 934  * Hash your Hashlist to follow
 935  * At the position to move forward
 936  * returns whether there is a next item or not.
 937  */
 938 int NextHashPos(HashList *Hash, HashPos *At) {
 939         if ((Hash == NULL) ||
 940             (At->Position >= Hash->nLookupTableItems) ||
 941             (At->Position < 0) ||
 942             (At->Position > Hash->nLookupTableItems))
 943                 return 0;
 944
 945         /* Position is NULL-Based, while Stepwidth is not... */
 946         if ((At->Position % abs(At->StepWidth)) == 0)
 947                 At->Position += At->StepWidth;
 948         else
 949                 At->Position += ((At->Position) % abs(At->StepWidth)) *
 950                         (At->StepWidth / abs(At->StepWidth));
 951         return !((At->Position >= Hash->nLookupTableItems) ||
 952                  (At->Position < 0) ||
 953                  (At->Position > Hash->nLookupTableItems));
 954 }
 955
 956 /*
 957  * Get the data located where At points to
 958  * note: you should prefer iterator operations instead of using me.
 959  * Hash your Hashlist peek from
 960  * At get the item in the position At.
 961  * HKLen returns Length of Hashkey Returned
 962  * HashKey returns the Hashkey corrosponding to HashPos
 963  * Data returns the Data found at HashPos
 964  * returns whether the item was found or not.
 965  */
 966 int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data) {
 967         long PayloadPos;
 968
 969         if ((Hash == NULL) ||
 970             (At < 0) ||
 971             (At >= Hash->nLookupTableItems))
 972                 return 0;
 973         *HKLen = Hash->LookupTable[At]->HKLen;
 974         *HashKey = Hash->LookupTable[At]->HashKey;
 975         PayloadPos = Hash->LookupTable[At]->Position;
 976         *Data = Hash->Members[PayloadPos]->Data;
 977         return 1;
 978 }
 979
 980 /*
 981  * Get the data located where At points to
 982  * note: you should prefer iterator operations instead of using me.
 983  * Hash your Hashlist peek from
 984  * HKLen returns Length of Hashkey Returned
 985  * HashKey returns the Hashkey corrosponding to HashPos
 986  * Data returns the Data found at HashPos
 987  * returns whether the item was found or not.
 988  */
 989 /*
 990 long GetHashIDAt(HashList *Hash,long At)
 991 {
 992         if ((Hash == NULL) ||
 993             (At < 0) ||
 994             (At > Hash->nLookupTableItems))
 995                 return 0;
 996
 997         return Hash->LookupTable[At]->Key;
 998 }
 999 */
1000
1001
1002 /*
1003  * sorting function for sorting the Hash alphabeticaly by their strings
1004  * Key1 first item
1005  * Key2 second item
1006  */
1007 static int SortByKeys(const void *Key1, const void* Key2) {
1008         HashKey *HKey1, *HKey2;
1009         HKey1 = *(HashKey**) Key1;
1010         HKey2 = *(HashKey**) Key2;
1011
1012         return strcasecmp(HKey1->HashKey, HKey2->HashKey);
1013 }
1014
1015 /*
1016  * sorting function for sorting the Hash alphabeticaly reverse by their strings
1017  * Key1 first item
1018  * Key2 second item
1019  */
1020 static int SortByKeysRev(const void *Key1, const void* Key2) {
1021         HashKey *HKey1, *HKey2;
1022         HKey1 = *(HashKey**) Key1;
1023         HKey2 = *(HashKey**) Key2;
1024
1025         return strcasecmp(HKey2->HashKey, HKey1->HashKey);
1026 }
1027
1028 /*
1029  * sorting function to regain hash-sequence and revert tainted status
1030  * Key1 first item
1031  * Key2 second item
1032  */
1033 static int SortByHashKeys(const void *Key1, const void* Key2) {
1034         HashKey *HKey1, *HKey2;
1035         HKey1 = *(HashKey**) Key1;
1036         HKey2 = *(HashKey**) Key2;
1037
1038         return HKey1->Key > HKey2->Key;
1039 }
1040
1041
1042 /*
1043  * sort the hash alphabeticaly by their keys.
1044  * Caution: This taints the hashlist, so accessing it later
1045  * will be significantly slower! You can un-taint it by SortByHashKeyStr
1046  * Hash the list to sort
1047  * Order 0/1 Forward/Backward
1048  */
1049 void SortByHashKey(HashList *Hash, int Order) {
1050         if (Hash->nLookupTableItems < 2)
1051                 return;
1052         qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*),
1053               (Order)?SortByKeys:SortByKeysRev);
1054         Hash->tainted = 1;
1055 }
1056
1057 /*
1058  * sort the hash by their keys (so it regains untainted state).
1059  * this will result in the sequence the hashing allgorithm produces it by default.
1060  * Hash the list to sort
1061  */
1062 void SortByHashKeyStr(HashList *Hash) {
1063         Hash->tainted = 0;
1064         if (Hash->nLookupTableItems < 2)
1065                 return;
1066         qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortByHashKeys);
1067 }
1068
1069
1070 /*
1071  * gives user sort routines access to the hash payload
1072  * HashVoid to retrieve Data to
1073  * returns Data belonging to HashVoid
1074  */
1075 const void *GetSearchPayload(const void *HashVoid) {
1076         return (*(HashKey**)HashVoid)->PL->Data;
1077 }
1078
1079 /*
1080  * sort the hash by your sort function. see the following sample.
1081  * this will result in the sequence the hashing allgorithm produces it by default.
1082  * Hash the list to sort
1083  * SortBy Sortfunction; see below how to implement this
1084  */
1085 void SortByPayload(HashList *Hash, CompareFunc SortBy) {
1086         if (Hash->nLookupTableItems < 2) {
1087                 return;
1088         }
1089         qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortBy);
1090         Hash->tainted = 1;
1091 }
1092
1093
1094
1095
1096 /*
1097  * given you've put char * into your hash as a payload, a sort function might
1098  * look like this:
1099  * int SortByChar(const void* First, const void* Second)
1100  * {
1101  *      char *a, *b;
1102  *      a = (char*) GetSearchPayload(First);
1103  *      b = (char*) GetSearchPayload(Second);
1104  *      return strcmp (a, b);
1105  * }
1106  */
1107
1108
1109 /*
1110  * Generic function to free a reference.
1111  * since a reference actualy isn't needed to be freed, do nothing.
1112  */
1113 void reference_free_handler(void *ptr) {
1114         return;
1115 }
1116
1117
1118 /*
1119  * This exposes the hashlittle() function to consumers.
1120  */
1121 int HashLittle(const void *key, size_t length) {
1122         return (int)hashlittle(key, length, 1);
1123 }
1124
1125
1126 /*
1127  * parses an MSet string into a list for later use
1128  * MSetList List to be read from MSetStr
1129  * MSetStr String containing the list
1130  */
1131 int ParseMSet(MSet **MSetList, StrBuf *MSetStr) {
1132         const char *POS = NULL, *SetPOS = NULL;
1133         StrBuf *OneSet;
1134         HashList *ThisMSet;
1135         long StartSet, EndSet;
1136         long *pEndSet;
1137
1138         *MSetList = NULL;
1139         if ((MSetStr == NULL) || (StrLength(MSetStr) == 0))
1140             return 0;
1141
1142         OneSet = NewStrBufPlain(NULL, StrLength(MSetStr));
1143         if (OneSet == NULL)
1144                 return 0;
1145
1146         ThisMSet = NewHash(0, lFlathash);
1147         if (ThisMSet == NULL) {
1148                 FreeStrBuf(&OneSet);
1149                 return 0;
1150         }
1151
1152         *MSetList = (MSet*) ThisMSet;
1153
1154         /* an MSet is a coma separated value list. */
1155         StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1156         do {
1157                 SetPOS = NULL;
1158
1159                 /* One set may consist of two Numbers: Start + optional End */
1160                 StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1161                 EndSet = 0; /* no range is our default. */
1162                 /* do we have an end (aka range?) */
1163                 if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL)) {
1164                         if (*(SetPOS) == '*')
1165                                 EndSet = LONG_MAX; /* ranges with '*' go until infinity */
1166                         else
1167                                 /* in other cases, get the EndPoint */
1168                                 EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
1169                 }
1170
1171                 pEndSet = (long*) malloc (sizeof(long));
1172                 if (pEndSet == NULL) {
1173                         FreeStrBuf(&OneSet);
1174                         DeleteHash(&ThisMSet);
1175                         return 0;
1176                 }
1177                 *pEndSet = EndSet;
1178
1179                 Put(ThisMSet, LKEY(StartSet), pEndSet, NULL);
1180                 /* if we don't have another, we're done. */
1181                 if (POS == StrBufNOTNULL)
1182                         break;
1183                 StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
1184         } while (1);
1185         FreeStrBuf(&OneSet);
1186
1187         return 1;
1188 }
1189
1190 /*
1191  * checks whether a message is inside a mset
1192  * MSetList List to search for MsgNo
1193  * MsgNo number to search in mset
1194  */
1195 int IsInMSetList(MSet *MSetList, long MsgNo) {
1196         /* basicaly we are a ... */
1197         long MemberPosition;
1198         HashList *Hash = (HashList*) MSetList;
1199         long HashAt;
1200         long EndAt;
1201         long StartAt;
1202
1203         if (Hash == NULL)
1204                 return 0;
1205         if (Hash->MemberSize == 0)
1206                 return 0;
1207         /** first, find out were we could fit in... */
1208         HashAt = FindInHash(Hash, MsgNo);
1209
1210         /* we're below the first entry, so not found. */
1211         if (HashAt < 0)
1212                 return 0;
1213         /* upper edge? move to last item */
1214         if (HashAt >= Hash->nMembersUsed)
1215                 HashAt = Hash->nMembersUsed - 1;
1216         /* Match? then we got it. */
1217         else if (Hash->LookupTable[HashAt]->Key == MsgNo)
1218                 return 1;
1219         /* One above possible range start? we need to move to the lower one. */
1220         else if ((HashAt > 0) &&
1221                  (Hash->LookupTable[HashAt]->Key > MsgNo))
1222                 HashAt -=1;
1223
1224         /* Fetch the actual data */
1225         StartAt = Hash->LookupTable[HashAt]->Key;
1226         MemberPosition = Hash->LookupTable[HashAt]->Position;
1227         EndAt = *(long*) Hash->Members[MemberPosition]->Data;
1228         if ((MsgNo >= StartAt) && (EndAt == LONG_MAX))
1229                 return 1;
1230         /* no range? */
1231         if (EndAt == 0)
1232                 return 0;
1233         /* inside of range? */
1234         if ((StartAt <= MsgNo) && (EndAt >= MsgNo))
1235                 return 1;
1236         return 0;
1237 }
1238
1239
1240 /*
1241  * frees a mset [redirects to @ref DeleteHash
1242  * FreeMe to be free'd
1243  */
1244 void DeleteMSet(MSet **FreeMe) {
1245         DeleteHash((HashList**) FreeMe);
1246 }