LibRCG  3.1.1
hashmap.h File Reference

Implementation of a hash table. More...

Go to the source code of this file.

Data Structures

struct  SHashNode
 Hash table node structure. More...
 
struct  SHashMap
 Hash table structure. More...
 

Typedefs

typedef SHashNodeHashNode
 Hash table node definition. More...
 
typedef SHashMapHashMap
 Hash table definition. More...
 

Functions

HashMap newHash (int size, float factor, int(*hash)(void *), int(*equals)(void *, void *))
 Creates a hash table. More...
 
int hashSetHash (HashMap hmap, int(*hash)(void *))
 Sets the hash function of a hash table. More...
 
int hashSetEquals (HashMap hmap, int(*equals)(void *, void *))
 Sets the comparison function of a hash table. More...
 
int hashSetFactor (HashMap hmap, int factor)
 Sets the load factor of a hash table. More...
 
void hashDelete (HashMap hmap)
 Deletes a hash table. More...
 
int hashInsert (HashMap hmap, void *key, void *value, int replace)
 Associates a value to a key in a hash table. More...
 
int hashRemove (HashMap hmap, void *key, void **value, void(*del)(void *))
 Removes the mapping for a key from a hash table. More...
 
int hashGet (HashMap hmap, void *key, void **value)
 Provides the mapping for a key from a hash table. More...
 
int hashSize (HashMap hmap)
 Returns the number of elements present in a hash table. More...
 
Iterator hashKeys (HashMap hmap)
 Creates an iterator from the keys of a hash table. More...
 
Iterator hashValues (HashMap hmap)
 Creates an iterator from the values of a hash table. More...
 

Detailed Description

Implementation of a hash table.

Provides functions to create and manipulate a hash table.

Collisions are handled using having a list for each buckets. When the number of elements is greater than a specified ratio of the number of buckets the hash table is resized.

To use this hash table you have to provide the following functions for the data type used for keys:

  • int hash(void *)

    Hash function (used by hashInsert, hashRemove, and hashGet). Generates a unique hash to a key. This function can be changed using function hashSetHash.

    E.g.:

    int hash(void* key)
    {
    int i,x;
    char* aux=key;
    for(i=0,x=0;i<32&&aux[i]!='\0';x+=aux[i],i++);
    return x;
    }

  • int keyEquals(void* key1,void* key2)

    Compares two keys (used by hashInsert, hashRemove, and hashGet). It should return 0 if key1 is equal to key2, and a value different from 0 otherwise. This function can be changed using function hashSetEquals.

    E.g.:

    int keyEquals(void* key1,void* key2)
    {
    if(key1&&key2) return srtcmp((char*)key1,(char*)key2);
    else !(key1==key2);
    }
Author
Rui Carlos Gonçalves
Version
3.0.1
Date
01/2014

Definition in file hashmap.h.

Typedef Documentation

typedef SHashMap* HashMap

Hash table definition.

Definition at line 101 of file hashmap.h.

typedef SHashNode* HashNode

Hash table node definition.

Definition at line 77 of file hashmap.h.

Function Documentation

void hashDelete ( HashMap  hmap)

Deletes a hash table.

Attention
This function only free the memory used by the hash table. It does not free the memory used by elements the hash table contains.
Parameters
hmapthe hash table to be deleted

Definition at line 110 of file hashmap.c.

int hashGet ( HashMap  hmap,
void *  key,
void **  value 
)

Provides the mapping for a key from a hash table.

If there is no mapping for the specified key, it will be put the value NULL at value. However, the NULL value may also say that the mapping for the specified key was NULL. Check the returned value in order to know whether the key was in the hash table.

Attention
This function puts at value a pointer to the mapping of the specified key. Changes to this value will affect the value in the hash table.
Parameters
hmapthe hash table
keykey whose mapping is to be provided
valuepointer where the mapping value will be put
Returns
0 if there was a mapping for the specified key
1 otherwise

Definition at line 193 of file hashmap.c.

int hashInsert ( HashMap  hmap,
void *  key,
void *  value,
int  replace 
)

Associates a value to a key in a hash table.

If the key already had a value, the replace argument specifies whether the new element should be added (it will be added only if replace!=0).

Parameters
hmapthe hash table
keythe key
valuethe value to be inserted
replacespecifies whether an old value shall be replaced
Returns
0 if the value was inserted
1 if the key already had a value
2 if an error occurred

Definition at line 129 of file hashmap.c.

Iterator hashKeys ( HashMap  hmap)

Creates an iterator from the keys of a hash table.

See Also
Iterator
Parameters
hmapthe hash map
Returns
NULL if an error occurred
the iterator otherwise

Definition at line 218 of file hashmap.c.

int hashRemove ( HashMap  hmap,
void *  key,
void **  value,
void(*)(void *)  del 
)

Removes the mapping for a key from a hash table.

Provides the value of the removed element if the value of elem is not NULL.

Attention
This function does not free the memory used by the removed element. To free the memory used by its key, you have to provide the argument del.
Parameters
hmapthe hash table
keykey whose mapping is to be removed
valuepointer where the removed element shall be put (or NULL)
delfunction to free the memory used by the key (or NULL)
Returns
0 if an element was removed from the specified position
1 otherwise

Definition at line 167 of file hashmap.c.

int hashSetEquals ( HashMap  hmap,
int(*)(void *, void *)  equals 
)

Sets the comparison function of a hash table.

Parameters
hmapthe hash table
equalsthe new comparison function
Returns
1 if equals was equal to NULL (no change was made)
0 otherwise

Definition at line 90 of file hashmap.c.

int hashSetFactor ( HashMap  hmap,
int  factor 
)

Sets the load factor of a hash table.

The new value must be greater than or equal to 0.1.

Parameters
hmapthe hash table
factorthe new load factor
Returns
1 if factor was less than 0.1 (no change was made)
0 otherwise

Definition at line 100 of file hashmap.c.

int hashSetHash ( HashMap  hmap,
int(*)(void *)  hash 
)

Sets the hash function of a hash table.

Parameters
hmapthe hash table
hashthe new hash function
Returns
1 if hash was equal to NULL (no change was made)
0 otherwise

Definition at line 80 of file hashmap.c.

int hashSize ( HashMap  hmap)

Returns the number of elements present in a hash table.

Parameters
hmapthe hash table
Returns
the number of elements present in the hash table

Definition at line 211 of file hashmap.c.

Iterator hashValues ( HashMap  hmap)

Creates an iterator from the values of a hash table.

See Also
Iterator
Parameters
hmapthe hash table
Returns
NULL if an error occurred
the iterator otherwise

Definition at line 239 of file hashmap.c.

HashMap newHash ( int  size,
float  factor,
int(*)(void *)  hash,
int(*)(void *, void *)  equals 
)

Creates a hash table.

The load factor (factor) specifies when the number of buckets should be increased (it will be increased when size > factor*length). The load factor must be greater than or equal to 0.1 (otherwise value 0.1 will be used).

Parameters
sizethe initial number of buckets
factorthe load factor
hashthe hash function
equalsthe comparison function
Returns
NULL if an error occurred
the new hash table otherwise

Definition at line 52 of file hashmap.c.

LibRCG © 2004-2015   Rui Carlos Gonçalves