Back to index

libcitadel  8.12
Functions
Hashlist functions to access / put / delete items in(to) the list
Hashlist Key Value list implementation;
Collaboration diagram for Hashlist functions to access / put / delete items in(to) the list:

Functions

HashListNewHash (int Uniq, HashFunc F)
 instanciate a new hashlist
void DeleteHashContent (HashList **Hash)
 flush the members of a hashlist Crashing? do 'print *FreeMe->LookupTable[i]'
void DeleteHash (HashList **Hash)
 destroy a hashlist and all of its members Crashing? do 'print *FreeMe->LookupTable[i]'
void Put (HashList *Hash, const char *HKey, long HKLen, void *Data, DeleteHashDataFunc DeleteIt)
 Add a new / Replace an existing item in the Hash.
int GetHash (HashList *Hash, const char *HKey, long HKLen, void **Data)
 Lookup the Data associated with HKey.
int GetHashKeys (HashList *Hash, char ***List)
 get the Keys present in this hash, simila to array_keys() in PHP Attention: List remains to Hash! don't modify or free it!
HashPosGetNewHashPos (HashList *Hash, int StepWidth)
 creates a hash-linear iterator object
int GetHashPosFromKey (HashList *Hash, const char *HKey, long HKLen, HashPos *At)
 Set iterator object to point to key.
int DeleteEntryFromHash (HashList *Hash, HashPos *At)
 Delete from the Hash the entry at Position.
int GetHashPosCounter (HashList *Hash, HashPos *At)
 retrieve the counter from the itteratoor
void DeleteHashPos (HashPos **DelMe)
 frees a linear hash iterator
int GetNextHashPos (HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
 Get the data located where HashPos Iterator points at, and Move HashPos one forward.
int GetHashPos (HashList *Hash, HashPos *At, long *HKLen, const char **HashKey, void **Data)
 Get the data located where HashPos Iterator points at.
int NextHashPos (HashList *Hash, HashPos *At)
 Move HashPos one forward.
int GetHashAt (HashList *Hash, long At, long *HKLen, const char **HashKey, void **Data)
 Get the data located where At points to note: you should prefer iterator operations instead of using me.
void reference_free_handler (void *ptr)
 given you've put char * into your hash as a payload, a sort function might look like this: int SortByChar(const void* First, const void* Second) { char a, b; a = (char) GetSearchPayload(First); b = (char) GetSearchPayload(Second); return strcmp (a, b); }

Function Documentation

int DeleteEntryFromHash ( HashList Hash,
HashPos At 
)

Delete from the Hash the entry at Position.

Parameters:
Hashthe list we reference
Atthe position within the Hash
Returns:
0 if not found

delete our hashing data

get rid of our payload

Definition at line 802 of file hash.c.

{
       Payload *FreeMe;
       if (Hash == NULL)
              return 0;

       /* if lockable, lock here */
       if ((Hash == NULL) || 
           (At->Position >= Hash->nLookupTableItems) || 
           (At->Position < 0) ||
           (At->Position > Hash->nLookupTableItems))
       {
              /* unlock... */
              return 0;
       }

       FreeMe = Hash->Members[Hash->LookupTable[At->Position]->Position];
       Hash->Members[Hash->LookupTable[At->Position]->Position] = NULL;


       if (Hash->LookupTable[At->Position] != NULL)
       {
              free(Hash->LookupTable[At->Position]->HashKey);
              free(Hash->LookupTable[At->Position]);
              if (At->Position < Hash->nLookupTableItems)
              {
                     memmove(&Hash->LookupTable[At->Position],
                            &Hash->LookupTable[At->Position + 1],
                            (Hash->nLookupTableItems - At->Position - 1) * 
                            sizeof(HashKey*));

                     Hash->LookupTable[Hash->nLookupTableItems - 1] = NULL;
              }
              else 
                     Hash->LookupTable[At->Position] = NULL;
              Hash->nLookupTableItems--;
       }
       /* unlock... */


       if (FreeMe != NULL)
       {
              DeleteHashPayload(FreeMe);
              free(FreeMe);
       }
       return 1;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void DeleteHash ( HashList **  Hash)

destroy a hashlist and all of its members Crashing? do 'print *FreeMe->LookupTable[i]'

Parameters:
HashHash to destroy. Is NULL'ed so you are shure its done.

now, free our arrays...

buye bye cruel world.

Definition at line 371 of file hash.c.

{
       HashList *FreeMe;

       FreeMe = *Hash;
       if (FreeMe == NULL)
              return;
       DeleteHashContent(Hash);
       free(FreeMe->LookupTable);
       free(FreeMe->Members);

       free (FreeMe);
       *Hash = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void DeleteHashContent ( HashList **  Hash)

flush the members of a hashlist Crashing? do 'print *FreeMe->LookupTable[i]'

Parameters:
HashHash to destroy. Is NULL'ed so you are shure its done.

get rid of our payload

delete our hashing data

did s.b. want an array of our keys? free them.

Definition at line 330 of file hash.c.

{
       int i;
       HashList *FreeMe;

       FreeMe = *Hash;
       if (FreeMe == NULL)
              return;
       /* even if there are sparse members already deleted... */
       for (i=0; i < FreeMe->nMembersUsed; i++)
       {
              if (FreeMe->Members[i] != NULL)
              {
                     DeleteHashPayload(FreeMe->Members[i]);
                     free(FreeMe->Members[i]);
              }
              if (FreeMe->LookupTable[i] != NULL)
              {
                     free(FreeMe->LookupTable[i]->HashKey);
                     free(FreeMe->LookupTable[i]);
              }
       }
       FreeMe->nMembersUsed = 0;
       FreeMe->tainted = 0;
       FreeMe->nLookupTableItems = 0;
       memset(FreeMe->Members, 0, sizeof(Payload*) * FreeMe->MemberSize);
       memset(FreeMe->LookupTable, 0, sizeof(HashKey*) * FreeMe->MemberSize);

       if (FreeMe->MyKeys != NULL)
              free(FreeMe->MyKeys);
}

Here is the call graph for this function:

Here is the caller graph for this function:

void DeleteHashPos ( HashPos **  DelMe)

frees a linear hash iterator

Definition at line 873 of file hash.c.

{
       if (*DelMe != NULL)
       {
              free(*DelMe);
              *DelMe = NULL;
       }
}

Here is the caller graph for this function:

int GetHash ( HashList Hash,
const char *  HKey,
long  HKLen,
void **  Data 
)

Lookup the Data associated with HKey.

Parameters:
Hashthe Hashlist to search in
HKeythe hashkey to look up
HKLenlength of HKey
Datareturns the Data associated with HKey
Returns:
0 if not found, 1 if.

first, find out were we could be...

< Not found at the lower edge?

< Not found at the upper edge?

< somewhere inbetween but no match?

GOTCHA!

Definition at line 675 of file hash.c.

{
       long HashBinKey;
       long HashAt;

       if (Hash == NULL)
              return 0;

       if (HKLen <= 0) {
              *Data = NULL;
              return  0;
       }
       HashBinKey = CalcHashKey(Hash, HKey, HKLen);
       HashAt = FindInHash(Hash, HashBinKey);
       if ((HashAt < 0) || 
           (HashAt >= Hash->nLookupTableItems) || 
           (Hash->LookupTable[HashAt]->Key != HashBinKey)) { 
              *Data = NULL;
              return 0;
       }
       else { 
              long MemberPosition;

              MemberPosition = Hash->LookupTable[HashAt]->Position;
              *Data = Hash->Members[MemberPosition]->Data;
              return 1;
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

int GetHashAt ( HashList Hash,
long  At,
long *  HKLen,
const char **  HashKey,
void **  Data 
)

Get the data located where At points to note: you should prefer iterator operations instead of using me.

Parameters:
Hashyour Hashlist peek from
Atget the item in the position At.
HKLenreturns Length of Hashkey Returned
HashKeyreturns the Hashkey corrosponding to HashPos
Datareturns the Data found at HashPos
Returns:
whether the item was found or not.

Definition at line 980 of file hash.c.

{
       long PayloadPos;

       if ((Hash == NULL) || 
           (At < 0) || 
           (At >= Hash->nLookupTableItems))
              return 0;
       *HKLen = Hash->LookupTable[At]->HKLen;
       *HashKey = Hash->LookupTable[At]->HashKey;
       PayloadPos = Hash->LookupTable[At]->Position;
       *Data = Hash->Members[PayloadPos]->Data;
       return 1;
}
int GetHashKeys ( HashList Hash,
char ***  List 
)

get the Keys present in this hash, simila to array_keys() in PHP Attention: List remains to Hash! don't modify or free it!

Parameters:
HashYour Hashlist to extract the keys from
Listreturns the list of hashkeys stored in Hash

Definition at line 718 of file hash.c.

{
       long i;
       if (Hash == NULL)
              return 0;
       if (Hash->MyKeys != NULL)
              free (Hash->MyKeys);

       Hash->MyKeys = (char**) malloc(sizeof(char*) * Hash->nLookupTableItems);
       for (i=0; i < Hash->nLookupTableItems; i++) {
       
              Hash->MyKeys[i] = Hash->LookupTable[i]->HashKey;
       }
       *List = (char**)Hash->MyKeys;
       return Hash->nLookupTableItems;
}
int GetHashPos ( HashList Hash,
HashPos At,
long *  HKLen,
const char **  HashKey,
void **  Data 
)

Get the data located where HashPos Iterator points at.

Parameters:
Hashyour Hashlist to follow
Atthe position retrieve the data from
HKLenreturns Length of Hashkey Returned
HashKeyreturns the Hashkey corrosponding to HashPos
Datareturns the Data found at HashPos
Returns:
whether the item was found or not.

Definition at line 926 of file hash.c.

{
       long PayloadPos;

       if ((Hash == NULL) || 
           (At->Position >= Hash->nLookupTableItems) || 
           (At->Position < 0) ||
           (At->Position > Hash->nLookupTableItems))
              return 0;
       *HKLen = Hash->LookupTable[At->Position]->HKLen;
       *HashKey = Hash->LookupTable[At->Position]->HashKey;
       PayloadPos = Hash->LookupTable[At->Position]->Position;
       *Data = Hash->Members[PayloadPos]->Data;

       return 1;
}
int GetHashPosCounter ( HashList Hash,
HashPos At 
)

retrieve the counter from the itteratoor

Parameters:
Hashwhich
Atthe Iterator to analyze
Returns:
the n'th hashposition we point at

Definition at line 859 of file hash.c.

{
       if ((Hash == NULL) || 
           (At->Position >= Hash->nLookupTableItems) || 
           (At->Position < 0) ||
           (At->Position > Hash->nLookupTableItems))
              return 0;
       return At->Position;
}
int GetHashPosFromKey ( HashList Hash,
const char *  HKey,
long  HKLen,
HashPos At 
)

Set iterator object to point to key.

If not found, don't change iterator

Parameters:
Hashthe list we reference
HKeykey to search for
HKLenlength of key
AtHashPos to update
Returns:
0 if not found

first, find out were we could be...

< Not found at the lower edge?

< Not found at the upper edge?

< somewhere inbetween but no match?

GOTCHA!

Definition at line 771 of file hash.c.

{
       long HashBinKey;
       long HashAt;

       if (Hash == NULL)
              return 0;

       if (HKLen <= 0) {
              return  0;
       }
       HashBinKey = CalcHashKey(Hash, HKey, HKLen);
       HashAt = FindInHash(Hash, HashBinKey);
       if ((HashAt < 0) || 
           (HashAt >= Hash->nLookupTableItems) || 
           (Hash->LookupTable[HashAt]->Key != HashBinKey)) { 
              return 0;
       }
       At->Position = HashAt;
       return 1;
}

Here is the call graph for this function:

HashPos* GetNewHashPos ( HashList Hash,
int  StepWidth 
)

creates a hash-linear iterator object

Parameters:
Hashthe list we reference
StepWidthin which step width should we iterate? If negative, the last position matching the step-raster is provided.
Returns:
the hash iterator

Definition at line 744 of file hash.c.

{
       HashPos *Ret;
       
       Ret = (HashPos*)malloc(sizeof(HashPos));
       if (StepWidth != 0)
              Ret->StepWidth = StepWidth;
       else
              Ret->StepWidth = 1;
       if (Ret->StepWidth <  0) {
              Ret->Position = Hash->nLookupTableItems - 1;
       }
       else {
              Ret->Position = 0;
       }
       return Ret;
}

Here is the caller graph for this function:

int GetNextHashPos ( HashList Hash,
HashPos At,
long *  HKLen,
const char **  HashKey,
void **  Data 
)

Get the data located where HashPos Iterator points at, and Move HashPos one forward.

Parameters:
Hashyour Hashlist to follow
Atthe position to retrieve the Item from and move forward afterwards
HKLenreturns Length of Hashkey Returned
HashKeyreturns the Hashkey corrosponding to HashPos
Datareturns the Data found at HashPos
Returns:
whether the item was found or not.

Definition at line 893 of file hash.c.

{
       long PayloadPos;

       if ((Hash == NULL) || 
           (At->Position >= Hash->nLookupTableItems) || 
           (At->Position < 0) ||
           (At->Position > Hash->nLookupTableItems))
              return 0;
       *HKLen = Hash->LookupTable[At->Position]->HKLen;
       *HashKey = Hash->LookupTable[At->Position]->HashKey;
       PayloadPos = Hash->LookupTable[At->Position]->Position;
       *Data = Hash->Members[PayloadPos]->Data;

       /* Position is NULL-Based, while Stepwidth is not... */
       if ((At->Position % abs(At->StepWidth)) == 0)
              At->Position += At->StepWidth;
       else 
              At->Position += ((At->Position) % abs(At->StepWidth)) * 
                     (At->StepWidth / abs(At->StepWidth));
       return 1;
}

Here is the caller graph for this function:

HashList* NewHash ( int  Uniq,
HashFunc  F 
)

instanciate a new hashlist

Returns:
the newly allocated list.

Definition at line 272 of file hash.c.

{
       HashList *NewList;
       NewList = malloc (sizeof(HashList));
       memset(NewList, 0, sizeof(HashList));

       NewList->Members = malloc(sizeof(Payload*) * 100);
       memset(NewList->Members, 0, sizeof(Payload*) * 100);

       NewList->LookupTable = malloc(sizeof(HashKey*) * 100);
       memset(NewList->LookupTable, 0, sizeof(HashKey*) * 100);

       NewList->MemberSize = 100;
       NewList->tainted = 0;
        NewList->uniq = Uniq;
       NewList->Algorithm = F;

       return NewList;
}

Here is the caller graph for this function:

int NextHashPos ( HashList Hash,
HashPos At 
)

Move HashPos one forward.

Parameters:
Hashyour Hashlist to follow
Atthe position to move forward
Returns:
whether there is a next item or not.

Definition at line 950 of file hash.c.

{
       if ((Hash == NULL) || 
           (At->Position >= Hash->nLookupTableItems) || 
           (At->Position < 0) ||
           (At->Position > Hash->nLookupTableItems))
              return 0;

       /* Position is NULL-Based, while Stepwidth is not... */
       if ((At->Position % abs(At->StepWidth)) == 0)
              At->Position += At->StepWidth;
       else 
              At->Position += ((At->Position) % abs(At->StepWidth)) * 
                     (At->StepWidth / abs(At->StepWidth));
       return !((At->Position >= Hash->nLookupTableItems) || 
               (At->Position < 0) ||
               (At->Position > Hash->nLookupTableItems));
}

Here is the caller graph for this function:

void Put ( HashList Hash,
const char *  HKey,
long  HKLen,
void *  Data,
DeleteHashDataFunc  DeleteIt 
)

Add a new / Replace an existing item in the Hash.

Parameters:
Hashthe list to manipulate
HKeythe hash-string to store Data under
HKLenLength of HKey
Datathe payload you want to associate with HKey
DeleteItif not free() should be used to delete Data set to NULL, else DeleteIt is used.

first, find out were we could fit in...

oh, we're brand new...

Insert Before?

Insert After?

Ok, we have a colision. replace it.

Definition at line 626 of file hash.c.

{
       long HashBinKey;
       long HashAt;

       if (Hash == NULL)
              return;

       HashBinKey = CalcHashKey(Hash, HKey, HKLen);
       HashAt = FindInHash(Hash, HashBinKey);

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

       if (Hash->LookupTable[HashAt] == NULL) {
              InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
       }
       else if (Hash->LookupTable[HashAt]->Key > HashBinKey) {
              InsertHashItem(Hash, HashAt, HashBinKey, HKey, HKLen, Data, DeleteIt);
       }
       else if (Hash->LookupTable[HashAt]->Key < HashBinKey) {
              InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
       }
       else { 
              if (Hash->uniq) {
                     long PayloadPos;
                     
                     PayloadPos = Hash->LookupTable[HashAt]->Position;
                     DeleteHashPayload(Hash->Members[PayloadPos]);
                     Hash->Members[PayloadPos]->Data = Data;
                     Hash->Members[PayloadPos]->Destructor = DeleteIt;
              }
              else {
                     InsertHashItem(Hash, HashAt + 1, HashBinKey, HKey, HKLen, Data, DeleteIt);
              }
       }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void reference_free_handler ( void *  ptr)

given you've put char * into your hash as a payload, a sort function might look like this: int SortByChar(const void* First, const void* Second) { char a, b; a = (char) GetSearchPayload(First); b = (char) GetSearchPayload(Second); return strcmp (a, b); }

Generic function to free a reference. since a reference actualy isn't needed to be freed, do nothing.

Definition at line 1143 of file hash.c.

{
       return;
}