Back to index

libcitadel  8.12
hash.c
Go to the documentation of this file.
00001 /*
00002  * Copyright (c) 1987-2011 by the citadel.org team
00003  *
00004  * This program is open source software; you can redistribute it and/or modify
00005  * it under the terms of the GNU General Public License as published by
00006  * the Free Software Foundation; either version 3 of the License, or
00007  * (at your option) any later version.
00008  *
00009  * This program is distributed in the hope that it will be useful,
00010  * but WITHOUT ANY WARRANTY; without even the implied warranty of
00011  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
00012  * GNU General Public License for more details.
00013  *
00014  * You should have received a copy of the GNU General Public License
00015  * along with this program; if not, write to the Free Software
00016  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
00017  */
00018 
00019 #include <stdint.h>
00020 #include <stdlib.h>
00021 #include <string.h>
00022 #include <limits.h>
00023 //dbg
00024 #include <stdio.h>
00025 #include "libcitadel.h"
00026 #include "lookup3.h"
00027 
00028 typedef struct Payload Payload;
00029 
00077 struct Payload {
00078        void *Data; 
00079        DeleteHashDataFunc Destructor; 
00080 };
00081 
00082 
00087 struct HashKey {
00088        long Key;         
00089        long Position;    
00090        char *HashKey;    
00091        long HKLen;       
00092        Payload *PL;      
00093 };
00094 
00099 struct HashList {
00100        Payload **Members;     
00101        HashKey **LookupTable; 
00102        char **MyKeys;         
00103        HashFunc Algorithm;    
00104        long nMembersUsed;     
00105        long nLookupTableItems; 
00106        long MemberSize;       
00107        long tainted;          
00108        long uniq;             
00109 };
00110 
00115 struct HashPos {
00116        long Position;        
00117        int StepWidth;        
00118 };
00119 
00120 
00130 int PrintHash(HashList *Hash, TransitionFunc Trans, PrintHashDataFunc PrintEntry)
00131 {
00132        int i;
00133        void *Previous;
00134        void *Next;
00135        const char* KeyStr;
00136 
00137        if (Hash == NULL)
00138               return 0;
00139 
00140        for (i=0; i < Hash->nLookupTableItems; i++) {
00141               if (i==0) {
00142                      Previous = NULL;
00143               }
00144               else {
00145                      if (Hash->LookupTable[i - 1] == NULL)
00146                             Previous = NULL;
00147                      else
00148                             Previous = Hash->Members[Hash->LookupTable[i-1]->Position]->Data;
00149               }
00150               if (Hash->LookupTable[i] == NULL) {
00151                      KeyStr = "";
00152                      Next = NULL;
00153               }
00154               else {
00155                      Next = Hash->Members[Hash->LookupTable[i]->Position]->Data;
00156                      KeyStr = Hash->LookupTable[i]->HashKey;
00157               }
00158 
00159               Trans(Previous, Next, i % 2);
00160               PrintEntry(KeyStr, Next, i % 2);
00161        }
00162        return i;
00163 }
00164 
00165 
00174 int dbg_PrintHash(HashList *Hash, PrintHashContent First, PrintHashContent Second)
00175 {
00176 #ifdef DEBUG
00177        const char *foo;
00178        const char *bar;
00179        const char *bla = "";
00180        long key;
00181 #endif
00182        long i;
00183 
00184        if (Hash == NULL)
00185               return 0;
00186 
00187        if (Hash->MyKeys != NULL)
00188               free (Hash->MyKeys);
00189 
00190        Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
00191 #ifdef DEBUG
00192        printf("----------------------------------\n");
00193 #endif
00194        for (i=0; i < Hash->nLookupTableItems; i++) {
00195               
00196               if (Hash->LookupTable[i] == NULL)
00197               {
00198 #ifdef DEBUG
00199                      foo = "";
00200                      bar = "";
00201                      key = 0;
00202 #endif
00203               }
00204               else 
00205               {
00206 #ifdef DEBUG
00207                      key = Hash->LookupTable[i]->Key;
00208                      foo = Hash->LookupTable[i]->HashKey;
00209 #endif
00210                      if (First != NULL)
00211 #ifdef DEBUG
00212                             bar =
00213 #endif
00214                                    First(Hash->Members[Hash->LookupTable[i]->Position]->Data);
00215 #ifdef DEBUG
00216                      else 
00217                             bar = "";
00218 #endif
00219 
00220                      if (Second != NULL)
00221 #ifdef DEBUG
00222                             bla = 
00223 #endif 
00224                                    Second(Hash->Members[Hash->LookupTable[i]->Position]->Data);
00225 #ifdef DEBUG
00226 
00227                      else
00228                             bla = "";
00229 #endif
00230 
00231               }
00232 #ifdef DEBUG
00233               printf (" ---- Hashkey[%ld][%ld]: '%s' Value: '%s' ; %s\n", i, key, foo, bar, bla);
00234 #endif
00235        }
00236 #ifdef DEBUG
00237        printf("----------------------------------\n");
00238 #endif
00239        return 0;
00240 }
00241 
00242 
00243 int TestValidateHash(HashList *TestHash)
00244 {
00245        long i;
00246 
00247        if (TestHash->nMembersUsed != TestHash->nLookupTableItems)
00248               return 1;
00249 
00250        if (TestHash->nMembersUsed > TestHash->MemberSize)
00251               return 2;
00252 
00253        for (i=0; i < TestHash->nMembersUsed; i++)
00254        {
00255 
00256               if (TestHash->LookupTable[i]->Position > TestHash->nMembersUsed)
00257                      return 3;
00258               
00259               if (TestHash->Members[TestHash->LookupTable[i]->Position] == NULL)
00260                      return 4;
00261               if (TestHash->Members[TestHash->LookupTable[i]->Position]->Data == NULL)
00262                      return 5;
00263        }
00264        return 0;
00265 }
00266 
00272 HashList *NewHash(int Uniq, HashFunc F)
00273 {
00274        HashList *NewList;
00275        NewList = malloc (sizeof(HashList));
00276        memset(NewList, 0, sizeof(HashList));
00277 
00278        NewList->Members = malloc(sizeof(Payload*) * 100);
00279        memset(NewList->Members, 0, sizeof(Payload*) * 100);
00280 
00281        NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
00282        memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);
00283 
00284        NewList->MemberSize = 100;
00285        NewList->tainted = 0;
00286         NewList->uniq = Uniq;
00287        NewList->Algorithm = F;
00288 
00289        return NewList;
00290 }
00291 
00292 int GetCount(HashList *Hash)
00293 {
00294        if(Hash==NULL) return 0;
00295        return Hash->nLookupTableItems;
00296 }
00297 
00298 
00305 static void DeleteHashPayload (Payload *Data)
00306 {
00308        if (Data->Destructor)
00309               Data->Destructor(Data->Data);
00310        else
00311               free(Data->Data);
00312 }
00313 
00318 void HDeleteHash(void *vHash)
00319 {
00320        HashList *FreeMe = (HashList*)vHash;
00321        DeleteHash(&FreeMe);
00322 }
00323 
00330 void DeleteHashContent(HashList **Hash)
00331 {
00332        int i;
00333        HashList *FreeMe;
00334 
00335        FreeMe = *Hash;
00336        if (FreeMe == NULL)
00337               return;
00338        /* even if there are sparse members already deleted... */
00339        for (i=0; i < FreeMe->nMembersUsed; i++)
00340        {
00342               if (FreeMe->Members[i] != NULL)
00343               {
00344                      DeleteHashPayload(FreeMe->Members[i]);
00345                      free(FreeMe->Members[i]);
00346               }
00348               if (FreeMe->LookupTable[i] != NULL)
00349               {
00350                      free(FreeMe->LookupTable[i]->HashKey);
00351                      free(FreeMe->LookupTable[i]);
00352               }
00353        }
00354        FreeMe->nMembersUsed = 0;
00355        FreeMe->tainted = 0;
00356        FreeMe->nLookupTableItems = 0;
00357        memset(FreeMe->Members, 0, sizeof(Payload*) * FreeMe->MemberSize);
00358        memset(FreeMe->LookupTable, 0, sizeof(HashKey*) * FreeMe->MemberSize);
00359 
00361        if (FreeMe->MyKeys != NULL)
00362               free(FreeMe->MyKeys);
00363 }
00364 
00371 void DeleteHash(HashList **Hash)
00372 {
00373        HashList *FreeMe;
00374 
00375        FreeMe = *Hash;
00376        if (FreeMe == NULL)
00377               return;
00378        DeleteHashContent(Hash);
00380        free(FreeMe->LookupTable);
00381        free(FreeMe->Members);
00382 
00384        free (FreeMe);
00385        *Hash = NULL;
00386 }
00387 
00393 static void IncreaseHashSize(HashList *Hash)
00394 {
00395        /* Ok, Our space is used up. Double the available space. */
00396        Payload **NewPayloadArea;
00397        HashKey **NewTable;
00398        
00399        if (Hash == NULL)
00400               return ;
00401 
00413        NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
00414        memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
00415        memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
00416        free(Hash->Members);
00417        Hash->Members = NewPayloadArea;
00418        
00420        NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
00421        memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
00422        memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
00423        free(Hash->LookupTable);
00424        Hash->LookupTable = NewTable;
00425        
00426        Hash->MemberSize *= 2;
00427 }
00428 
00429 
00441 static void InsertHashItem(HashList *Hash, 
00442                         long HashPos, 
00443                         long HashBinKey, 
00444                         const char *HashKeyStr, 
00445                         long HKLen, 
00446                         void *Data,
00447                         DeleteHashDataFunc Destructor)
00448 {
00449        Payload *NewPayloadItem;
00450        HashKey *NewHashKey;
00451 
00452        if (Hash == NULL)
00453               return;
00454 
00455        if (Hash->nMembersUsed >= Hash->MemberSize)
00456               IncreaseHashSize (Hash);
00457 
00459        NewPayloadItem = (Payload*) malloc (sizeof(Payload));
00460        NewPayloadItem->Data = Data;
00461        NewPayloadItem->Destructor = Destructor;
00463        NewHashKey = (HashKey*) malloc (sizeof(HashKey));
00464        NewHashKey->HashKey = (char *) malloc (HKLen + 1);
00465        NewHashKey->HKLen = HKLen;
00466        memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
00467        NewHashKey->Key = HashBinKey;
00468        NewHashKey->PL = NewPayloadItem;
00470        NewHashKey->Position = Hash->nMembersUsed;
00472        if ((Hash->nLookupTableItems != 0) && 
00473            (HashPos != Hash->nLookupTableItems) ) {
00474               long ItemsAfter;
00475 
00476               ItemsAfter = Hash->nLookupTableItems - HashPos;
00478               if (ItemsAfter > 0)
00479               {
00480                      memmove(&Hash->LookupTable[HashPos + 1],
00481                             &Hash->LookupTable[HashPos],
00482                             ItemsAfter * sizeof(HashKey*));
00483               } 
00484        }
00485        
00486        Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
00487        Hash->LookupTable[HashPos] = NewHashKey;
00488        Hash->nMembersUsed++;
00489        Hash->nLookupTableItems++;
00490 }
00491 
00500 static long FindInTaintedHash(HashList *Hash, long HashBinKey)
00501 {
00502        long SearchPos;
00503 
00504        if (Hash == NULL)
00505               return 0;
00506 
00507        for (SearchPos = 0; SearchPos < Hash->nLookupTableItems; SearchPos ++) {
00508               if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
00509                      return SearchPos;
00510               }
00511        }
00512        return SearchPos;
00513 }
00514 
00522 static long FindInHash(HashList *Hash, long HashBinKey)
00523 {
00524        long SearchPos;
00525        long StepWidth;
00526 
00527        if (Hash == NULL)
00528               return 0;
00529 
00530        if (Hash->tainted)
00531               return FindInTaintedHash(Hash, HashBinKey);
00532 
00533        SearchPos = Hash->nLookupTableItems / 2;
00534        StepWidth = SearchPos / 2;
00535        while ((SearchPos > 0) && 
00536               (SearchPos < Hash->nLookupTableItems)) 
00537        {
00539               if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
00540                      return SearchPos;
00541               }
00543               if (StepWidth > 1){
00544                      if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
00545                             SearchPos -= StepWidth;
00546                      else
00547                             SearchPos += StepWidth;
00548                      StepWidth /= 2;                    
00549               }
00550               else { 
00551                      if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
00552                             if ((SearchPos > 0) && 
00553                                 (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
00554                                    return SearchPos;
00555                             SearchPos --;
00556                      }
00557                      else {
00558                             if ((SearchPos + 1 < Hash->nLookupTableItems) && 
00559                                 (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
00560                                    return SearchPos;
00561                             SearchPos ++;
00562                      }
00563                      StepWidth--;
00564               }
00565        }
00566        return SearchPos;
00567 }
00568 
00569 
00577 long Flathash(const char *str, long len)
00578 {
00579        if (len != sizeof (int))
00580               return 0;
00581        else return *(int*)str;
00582 }
00583 
00591 long lFlathash(const char *str, long len)
00592 {
00593        if (len != sizeof (long))
00594               return 0;
00595        else return *(long*)str;
00596 }
00597 
00605 inline static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
00606 {
00607        if (Hash == NULL)
00608               return 0;
00609 
00610        if (Hash->Algorithm == NULL)
00611               return hashlittle(HKey, HKLen, 9283457);
00612        else
00613               return Hash->Algorithm(HKey, HKLen);
00614 }
00615 
00616 
00626 void Put(HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
00627 {
00628        long HashBinKey;
00629        long HashAt;
00630 
00631        if (Hash == NULL)
00632               return;
00633 
00635        HashBinKey = CalcHashKey(Hash, HKey, HKLen);
00636        HashAt = FindInHash(Hash, HashBinKey);
00637 
00638        if (HashAt >= Hash->MemberSize)
00639               IncreaseHashSize (Hash);
00640 
00642        if (Hash->LookupTable[HashAt] == NULL) {
00643               InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
00644        }
00645        else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
00646               InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
00647        }
00648        else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
00649               InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
00650        }
00651        else { 
00652               if (Hash->uniq) {
00653                      long PayloadPos;
00654                      
00655                      PayloadPos = Hash->LookupTable[HashAt]->Position;
00656                      DeleteHashPayload(Hash->Members[PayloadPos]);
00657                      Hash->Members[PayloadPos]->Data = Data;
00658                      Hash->Members[PayloadPos]->Destructor = DeleteIt;
00659               }
00660               else {
00661                      InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
00662               }
00663        }
00664 }
00665 
00675 int GetHash(HashList *Hash, const char *HKey, long HKLen, void **Data)
00676 {
00677        long HashBinKey;
00678        long HashAt;
00679 
00680        if (Hash == NULL)
00681               return 0;
00682 
00683        if (HKLen <= 0) {
00684               *Data = NULL;
00685               return  0;
00686        }
00688        HashBinKey = CalcHashKey(Hash, HKey, HKLen);
00689        HashAt = FindInHash(Hash, HashBinKey);
00690        if ((HashAt < 0) || 
00691            (HashAt >= Hash->nLookupTableItems) || 
00692            (Hash->LookupTable[HashAt]->Key != HashBinKey)) { 
00693               *Data = NULL;
00694               return 0;
00695        }
00696        else { 
00697               long MemberPosition;
00698 
00699               MemberPosition = Hash->LookupTable[HashAt]->Position;
00700               *Data = Hash->Members[MemberPosition]->Data;
00701               return 1;
00702        }
00703 }
00704 
00705 /* TODO? */
00706 int GetKey(HashList *Hash, char *HKey, long HKLen, void **Payload)
00707 {
00708        return 0;
00709 }
00710 
00718 int GetHashKeys(HashList *Hash, char ***List)
00719 {
00720        long i;
00721        if (Hash == NULL)
00722               return 0;
00723        if (Hash->MyKeys != NULL)
00724               free (Hash->MyKeys);
00725 
00726        Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
00727        for (i=0; i < Hash->nLookupTableItems; i++) {
00728        
00729               Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
00730        }
00731        *List = (char**)Hash->MyKeys;
00732        return Hash->nLookupTableItems;
00733 }
00734 
00744 HashPos *GetNewHashPos(HashList *Hash, int StepWidth)
00745 {
00746        HashPos *Ret;
00747        
00748        Ret = (HashPos*)malloc(sizeof(HashPos));
00749        if (StepWidth != 0)
00750               Ret->StepWidth = StepWidth;
00751        else
00752               Ret->StepWidth = 1;
00753        if (Ret->StepWidth <  0) {
00754               Ret->Position = Hash->nLookupTableItems - 1;
00755        }
00756        else {
00757               Ret->Position = 0;
00758        }
00759        return Ret;
00760 }
00761 
00771 int GetHashPosFromKey(HashList *Hash, const char *HKey, long HKLen, HashPos *At)
00772 {
00773        long HashBinKey;
00774        long HashAt;
00775 
00776        if (Hash == NULL)
00777               return 0;
00778 
00779        if (HKLen <= 0) {
00780               return  0;
00781        }
00783        HashBinKey = CalcHashKey(Hash, HKey, HKLen);
00784        HashAt = FindInHash(Hash, HashBinKey);
00785        if ((HashAt < 0) || 
00786            (HashAt >= Hash->nLookupTableItems) || 
00787            (Hash->LookupTable[HashAt]->Key != HashBinKey)) { 
00788               return 0;
00789        }
00791        At->Position = HashAt;
00792        return 1;
00793 }
00794 
00802 int DeleteEntryFromHash(HashList *Hash, HashPos *At)
00803 {
00804        Payload *FreeMe;
00805        if (Hash == NULL)
00806               return 0;
00807 
00808        /* if lockable, lock here */
00809        if ((Hash == NULL) || 
00810            (At->Position >= Hash->nLookupTableItems) || 
00811            (At->Position < 0) ||
00812            (At->Position > Hash->nLookupTableItems))
00813        {
00814               /* unlock... */
00815               return 0;
00816        }
00817 
00818        FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
00819        Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;
00820 
00821 
00823        if (Hash->LookupTable[At->Position] != NULL)
00824        {
00825               free(Hash->LookupTable[At->Position]->HashKey);
00826               free(Hash->LookupTable[At->Position]);
00827               if (At->Position < Hash->nLookupTableItems)
00828               {
00829                      memmove(&Hash->LookupTable[At->Position],
00830                             &Hash->LookupTable[At->Position + 1],
00831                             (Hash->nLookupTableItems - At->Position - 1) * 
00832                             sizeof(HashKey*));
00833 
00834                      Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
00835               }
00836               else 
00837                      Hash->LookupTable[At->Position] = NULL;
00838               Hash->nLookupTableItems--;
00839        }
00840        /* unlock... */
00841 
00842 
00844        if (FreeMe != NULL)
00845        {
00846               DeleteHashPayload(FreeMe);
00847               free(FreeMe);
00848        }
00849        return 1;
00850 }
00851 
00859 int GetHashPosCounter(HashList *Hash, HashPos *At)
00860 {
00861        if ((Hash == NULL) || 
00862            (At->Position >= Hash->nLookupTableItems) || 
00863            (At->Position < 0) ||
00864            (At->Position > Hash->nLookupTableItems))
00865               return 0;
00866        return At->Position;
00867 }
00868 
00873 void DeleteHashPos(HashPos **DelMe)
00874 {
00875        if (*DelMe != NULL)
00876        {
00877               free(*DelMe);
00878               *DelMe = NULL;
00879        }
00880 }
00881 
00882 
00893 int GetNextHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
00894 {
00895        long PayloadPos;
00896 
00897        if ((Hash == NULL) || 
00898            (At->Position >= Hash->nLookupTableItems) || 
00899            (At->Position < 0) ||
00900            (At->Position > Hash->nLookupTableItems))
00901               return 0;
00902        *HKLen = Hash->LookupTable[At->Position]->HKLen;
00903        *HashKey = Hash->LookupTable[At->Position]->HashKey;
00904        PayloadPos = Hash->LookupTable[At->Position]->Position;
00905        *Data = Hash->Members[PayloadPos]->Data;
00906 
00907        /* Position is NULL-Based, while Stepwidth is not... */
00908        if ((At->Position % abs(At->StepWidth)) == 0)
00909               At->Position += At->StepWidth;
00910        else 
00911               At->Position += ((At->Position) % abs(At->StepWidth)) * 
00912                      (At->StepWidth / abs(At->StepWidth));
00913        return 1;
00914 }
00915 
00926 int GetHashPos(HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
00927 {
00928        long PayloadPos;
00929 
00930        if ((Hash == NULL) || 
00931            (At->Position >= Hash->nLookupTableItems) || 
00932            (At->Position < 0) ||
00933            (At->Position > Hash->nLookupTableItems))
00934               return 0;
00935        *HKLen = Hash->LookupTable[At->Position]->HKLen;
00936        *HashKey = Hash->LookupTable[At->Position]->HashKey;
00937        PayloadPos = Hash->LookupTable[At->Position]->Position;
00938        *Data = Hash->Members[PayloadPos]->Data;
00939 
00940        return 1;
00941 }
00942 
00950 int NextHashPos(HashList *Hash, HashPos *At)
00951 {
00952        if ((Hash == NULL) || 
00953            (At->Position >= Hash->nLookupTableItems) || 
00954            (At->Position < 0) ||
00955            (At->Position > Hash->nLookupTableItems))
00956               return 0;
00957 
00958        /* Position is NULL-Based, while Stepwidth is not... */
00959        if ((At->Position % abs(At->StepWidth)) == 0)
00960               At->Position += At->StepWidth;
00961        else 
00962               At->Position += ((At->Position) % abs(At->StepWidth)) * 
00963                      (At->StepWidth / abs(At->StepWidth));
00964        return !((At->Position >= Hash->nLookupTableItems) || 
00965                (At->Position < 0) ||
00966                (At->Position > Hash->nLookupTableItems));
00967 }
00968 
00980 int GetHashAt(HashList *Hash,long At, long *HKLen, const char **HashKey, void **Data)
00981 {
00982        long PayloadPos;
00983 
00984        if ((Hash == NULL) || 
00985            (At < 0) || 
00986            (At >= Hash->nLookupTableItems))
00987               return 0;
00988        *HKLen = Hash->LookupTable[At]->HKLen;
00989        *HashKey = Hash->LookupTable[At]->HashKey;
00990        PayloadPos = Hash->LookupTable[At]->Position;
00991        *Data = Hash->Members[PayloadPos]->Data;
00992        return 1;
00993 }
00994 
01005 /*
01006 long GetHashIDAt(HashList *Hash,long At)
01007 {
01008        if ((Hash == NULL) || 
01009            (At < 0) || 
01010            (At > Hash->nLookupTableItems))
01011               return 0;
01012 
01013        return Hash->LookupTable[At]->Key;
01014 }
01015 */
01016 
01017 
01024 static int SortByKeys(const void *Key1, const void* Key2)
01025 {
01026        HashKey *HKey1, *HKey2;
01027        HKey1 = *(HashKey**) Key1;
01028        HKey2 = *(HashKey**) Key2;
01029 
01030        return strcasecmp(HKey1->HashKey, HKey2->HashKey);
01031 }
01032 
01039 static int SortByKeysRev(const void *Key1, const void* Key2)
01040 {
01041        HashKey *HKey1, *HKey2;
01042        HKey1 = *(HashKey**) Key1;
01043        HKey2 = *(HashKey**) Key2;
01044 
01045        return strcasecmp(HKey2->HashKey, HKey1->HashKey);
01046 }
01047 
01054 static int SortByHashKeys(const void *Key1, const void* Key2)
01055 {
01056        HashKey *HKey1, *HKey2;
01057        HKey1 = *(HashKey**) Key1;
01058        HKey2 = *(HashKey**) Key2;
01059 
01060        return HKey1->Key > HKey2->Key;
01061 }
01062 
01063 
01072 void SortByHashKey(HashList *Hash, int Order)
01073 {
01074        if (Hash->nLookupTableItems < 2)
01075               return;
01076        qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), 
01077              (Order)?SortByKeys:SortByKeysRev);
01078        Hash->tainted = 1;
01079 }
01080 
01087 void SortByHashKeyStr(HashList *Hash)
01088 {
01089        Hash->tainted = 0;
01090        if (Hash->nLookupTableItems < 2)
01091               return;
01092        qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortByHashKeys);
01093 }
01094 
01095 
01102 const void *GetSearchPayload(const void *HashVoid)
01103 {
01104        return (*(HashKey**)HashVoid)->PL->Data;
01105 }
01106 
01114 void SortByPayload(HashList *Hash, CompareFunc SortBy)
01115 {
01116        if (Hash->nLookupTableItems < 2)
01117               return;
01118        qsort(Hash->LookupTable, Hash->nLookupTableItems, sizeof(HashKey*), SortBy);
01119        Hash->tainted = 1;
01120 }
01121 
01122 
01123 
01124 
01143 void reference_free_handler(void *ptr) 
01144 {
01145        return;
01146 }
01147 
01148 
01153 int HashLittle(const void *key, size_t length) {
01154        return (int)hashlittle(key, length, 1);
01155 }
01156 
01157 
01164 int ParseMSet(MSet **MSetList, StrBuf *MSetStr)
01165 {
01166        const char *POS = NULL, *SetPOS = NULL;
01167        StrBuf *OneSet;
01168        HashList *ThisMSet;
01169        long StartSet, EndSet;
01170        long *pEndSet;
01171        
01172        *MSetList = NULL;
01173        if ((MSetStr == NULL) || (StrLength(MSetStr) == 0))
01174            return 0;
01175            
01176        OneSet = NewStrBufPlain(NULL, StrLength(MSetStr));
01177 
01178        ThisMSet = NewHash(0, lFlathash);
01179 
01180        *MSetList = (MSet*) ThisMSet;
01181 
01182        /* an MSet is a coma separated value list. */
01183        StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
01184        do {
01185               SetPOS = NULL;
01186 
01187               /* One set may consist of two Numbers: Start + optional End */
01188               StartSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
01189               EndSet = 0; /* no range is our default. */
01190               /* do we have an end (aka range?) */
01191               if ((SetPOS != NULL) && (SetPOS != StrBufNOTNULL))
01192               {
01193                      if (*(SetPOS) == '*')
01194                             EndSet = LONG_MAX; /* ranges with '*' go until infinity */
01195                      else 
01196                             /* in other cases, get the EndPoint */
01197                             EndSet = StrBufExtractNext_long(OneSet, &SetPOS, ':');
01198               }
01199 
01200               pEndSet = (long*) malloc (sizeof(long));
01201               *pEndSet = EndSet;
01202 
01203               Put(ThisMSet, LKEY(StartSet), pEndSet, NULL);
01204               /* if we don't have another, we're done. */
01205               if (POS == StrBufNOTNULL)
01206                      break;
01207               StrBufExtract_NextToken(OneSet, MSetStr, &POS, ',');
01208        } while (1);
01209        FreeStrBuf(&OneSet);
01210 
01211        return 1;
01212 }
01213 
01220 int IsInMSetList(MSet *MSetList, long MsgNo)
01221 {
01222        /* basicaly we are a ... */
01223        long MemberPosition;
01224        HashList *Hash = (HashList*) MSetList;
01225        long HashAt;
01226        long EndAt;
01227        long StartAt;
01228 
01229        if (Hash == NULL)
01230               return 0;
01231        if (Hash->MemberSize == 0)
01232               return 0;
01234        HashAt = FindInHash(Hash, MsgNo);
01235        
01236        /* we're below the first entry, so not found. */
01237        if (HashAt < 0)
01238               return 0;
01239        /* upper edge? move to last item */
01240        if (HashAt >= Hash->nMembersUsed)
01241               HashAt = Hash->nMembersUsed - 1;
01242        /* Match? then we got it. */
01243        else if (Hash->LookupTable[HashAt]->Key == MsgNo)
01244               return 1;
01245        /* One above possible range start? we need to move to the lower one. */ 
01246        else if ((HashAt > 0) && 
01247                (Hash->LookupTable[HashAt]->Key > MsgNo))
01248               HashAt -=1;
01249 
01250        /* Fetch the actual data */
01251        StartAt = Hash->LookupTable[HashAt]->Key;
01252        MemberPosition = Hash->LookupTable[HashAt]->Position;
01253        EndAt = *(long*) Hash->Members[MemberPosition]->Data;
01254        if ((MsgNo >= StartAt) && (EndAt == LONG_MAX))
01255               return 1;
01256        /* no range? */
01257        if (EndAt == 0)
01258               return 0;
01259        /* inside of range? */
01260        if ((StartAt <= MsgNo) && (EndAt >= MsgNo))
01261               return 1;
01262        return 0;
01263 }
01264 
01265 
01271 void DeleteMSet(MSet **FreeMe)
01272 {
01273        DeleteHash((HashList**) FreeMe);
01274 }