Back to index

libcitadel  8.12
Functions
Hashlist internal functions
Hashlist Key Value list implementation;
Collaboration diagram for Hashlist internal functions:

Functions

static void DeleteHashPayload (Payload *Data)
 private destructor for one hash element.
void HDeleteHash (void *vHash)
 Destructor for nested hashes.
static void IncreaseHashSize (HashList *Hash)
 Private function to increase the hash size.
static void InsertHashItem (HashList *Hash, long HashPos, long HashBinKey, const char *HashKeyStr, long HKLen, void *Data, DeleteHashDataFunc Destructor)
 private function to add a new item to / replace an existing in - the hashlist if the hash list is full, its re-alloced with double size.
static long FindInHash (HashList *Hash, long HashBinKey)
 Private function to lookup the Item / the closest position to put it in.
static long CalcHashKey (HashList *Hash, const char *HKey, long HKLen)
 private abstract wrapper around the hashing algorithm

Function Documentation

static long CalcHashKey ( HashList Hash,
const char *  HKey,
long  HKLen 
) [inline, static]

private abstract wrapper around the hashing algorithm

Parameters:
HKeythe hash string
HKLenlength of HKey
Returns:
the calculated hash value

Definition at line 605 of file hash.c.

{
       if (Hash == NULL)
              return 0;

       if (Hash->Algorithm == NULL)
              return hashlittle(HKey, HKLen, 9283457);
       else
              return Hash->Algorithm(HKey, HKLen);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void DeleteHashPayload ( Payload Data) [static]

private destructor for one hash element.

Crashing? go one frame up and do 'print *FreeMe->LookupTable[i]'

Parameters:
Dataan element to free using the user provided destructor, or just plain free

do we have a destructor for our payload?

Definition at line 305 of file hash.c.

{
       if (Data->Destructor)
              Data->Destructor(Data->Data);
       else
              free(Data->Data);
}

Here is the caller graph for this function:

static long FindInHash ( HashList Hash,
long  HashBinKey 
) [static]

Private function to lookup the Item / the closest position to put it in.

Parameters:
HashOur Hash to manipulate
HashBinKeythe Hash-Number to lookup.
Returns:
the position (most closely) matching HashBinKey (-> Caller needs to compare! )

Did we find it?

are we Aproximating in big steps?

We are right next to our target, within 4 positions

Definition at line 522 of file hash.c.

{
       long SearchPos;
       long StepWidth;

       if (Hash == NULL)
              return 0;

       if (Hash->tainted)
              return FindInTaintedHash(Hash, HashBinKey);

       SearchPos = Hash->nLookupTableItems / 2;
       StepWidth = SearchPos / 2;
       while ((SearchPos > 0) && 
              (SearchPos < Hash->nLookupTableItems)) 
       {
              if (Hash->LookupTable[SearchPos]->Key == HashBinKey){
                     return SearchPos;
              }
              if (StepWidth > 1){
                     if (Hash->LookupTable[SearchPos]->Key > HashBinKey)
                            SearchPos -= StepWidth;
                     else
                            SearchPos += StepWidth;
                     StepWidth /= 2;                    
              }
              else { 
                     if (Hash->LookupTable[SearchPos]->Key > HashBinKey) {
                            if ((SearchPos > 0) && 
                                (Hash->LookupTable[SearchPos - 1]->Key < HashBinKey))
                                   return SearchPos;
                            SearchPos --;
                     }
                     else {
                            if ((SearchPos + 1 < Hash->nLookupTableItems) && 
                                (Hash->LookupTable[SearchPos + 1]->Key > HashBinKey))
                                   return SearchPos;
                            SearchPos ++;
                     }
                     StepWidth--;
              }
       }
       return SearchPos;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void HDeleteHash ( void *  vHash)

Destructor for nested hashes.

Definition at line 318 of file hash.c.

{
       HashList *FreeMe = (HashList*)vHash;
       DeleteHash(&FreeMe);
}

Here is the call graph for this function:

static void IncreaseHashSize ( HashList Hash) [static]

Private function to increase the hash size.

Parameters:
Hashthe Hasharray to increase

If we grew to much, this might be the place to rehash and shrink again. if ((Hash->NMembersUsed > Hash->nLookupTableItems) && ((Hash->NMembersUsed - Hash->nLookupTableItems) > (Hash->nLookupTableItems / 10))) {

}

double our payload area

double our hashtable area

Definition at line 393 of file hash.c.

{
       /* Ok, Our space is used up. Double the available space. */
       Payload **NewPayloadArea;
       HashKey **NewTable;
       
       if (Hash == NULL)
              return ;

       NewPayloadArea = (Payload**) malloc(sizeof(Payload*) * Hash->MemberSize * 2);
       memset(&NewPayloadArea[Hash->MemberSize], 0, sizeof(Payload*) * Hash->MemberSize);
       memcpy(NewPayloadArea, Hash->Members, sizeof(Payload*) * Hash->MemberSize);
       free(Hash->Members);
       Hash->Members = NewPayloadArea;
       
       NewTable = malloc(sizeof(HashKey*) * Hash->MemberSize * 2);
       memset(&NewTable[Hash->MemberSize], 0, sizeof(HashKey*) * Hash->MemberSize);
       memcpy(NewTable, Hash->LookupTable, sizeof(HashKey*) * Hash->MemberSize);
       free(Hash->LookupTable);
       Hash->LookupTable = NewTable;
       
       Hash->MemberSize *= 2;
}

Here is the caller graph for this function:

static void InsertHashItem ( HashList Hash,
long  HashPos,
long  HashBinKey,
const char *  HashKeyStr,
long  HKLen,
void *  Data,
DeleteHashDataFunc  Destructor 
) [static]

private function to add a new item to / replace an existing in - the hashlist if the hash list is full, its re-alloced with double size.

Parameters:
Hashour hashlist to manipulate
HashPoswhere should we insert / replace?
HashKeyStrthe Hash-String
HKLenlength of HashKeyStr
Datayour Payload to add
DestructorFunctionpointer to free Data. if NULL, default free() is used.

Arrange the payload

Arrange the hashkey

our payload is queued at the end...

but if we should be sorted into a specific place...

make space were we can fill us in

Definition at line 441 of file hash.c.

{
       Payload *NewPayloadItem;
       HashKey *NewHashKey;

       if (Hash == NULL)
              return;

       if (Hash->nMembersUsed >= Hash->MemberSize)
              IncreaseHashSize (Hash);

       NewPayloadItem = (Payload*) malloc (sizeof(Payload));
       NewPayloadItem->Data = Data;
       NewPayloadItem->Destructor = Destructor;
       NewHashKey = (HashKey*) malloc (sizeof(HashKey));
       NewHashKey->HashKey = (char *) malloc (HKLen + 1);
       NewHashKey->HKLen = HKLen;
       memcpy (NewHashKey->HashKey, HashKeyStr, HKLen + 1);
       NewHashKey->Key = HashBinKey;
       NewHashKey->PL = NewPayloadItem;
       NewHashKey->Position = Hash->nMembersUsed;
       if ((Hash->nLookupTableItems != 0) && 
           (HashPos != Hash->nLookupTableItems) ) {
              long ItemsAfter;

              ItemsAfter = Hash->nLookupTableItems - HashPos;
              if (ItemsAfter > 0)
              {
                     memmove(&Hash->LookupTable[HashPos + 1],
                            &Hash->LookupTable[HashPos],
                            ItemsAfter * sizeof(HashKey*));
              } 
       }
       
       Hash->Members[Hash->nMembersUsed] = NewPayloadItem;
       Hash->LookupTable[HashPos] = NewHashKey;
       Hash->nMembersUsed++;
       Hash->nLookupTableItems++;
}

Here is the call graph for this function:

Here is the caller graph for this function: