gdsl  1.7
Hashtable manipulation module

Typedefs

typedef struct hash_table * gdsl_hash_t
 GDSL hashtable type.
typedef const char *(* gdsl_key_func_t )(void *VALUE)
 GDSL hashtable key function type.
typedef ulong(* gdsl_hash_func_t )(const char *KEY)
 GDSL hashtable hash function type.

Functions

ulong gdsl_hash (const char *KEY)
 Computes a hash value from a NULL terminated character string.
gdsl_hash_t gdsl_hash_alloc (const char *NAME, gdsl_alloc_func_t ALLOC_F, gdsl_free_func_t FREE_F, gdsl_key_func_t KEY_F, gdsl_hash_func_t HASH_F, ushort INITIAL_ENTRIES_NB)
 Create a new hashtable.
void gdsl_hash_free (gdsl_hash_t H)
 Destroy a hashtable.
void gdsl_hash_flush (gdsl_hash_t H)
 Flush a hashtable.
const char * gdsl_hash_get_name (const gdsl_hash_t H)
 Get the name of a hashtable.
ushort gdsl_hash_get_entries_number (const gdsl_hash_t H)
 Get the number of entries of a hashtable.
ushort gdsl_hash_get_lists_max_size (const gdsl_hash_t H)
 Get the max number of elements allowed in each entry of a hashtable.
ushort gdsl_hash_get_longest_list_size (const gdsl_hash_t H)
 Get the number of elements of the longest list entry of a hashtable.
ulong gdsl_hash_get_size (const gdsl_hash_t H)
 Get the size of a hashtable.
double gdsl_hash_get_fill_factor (const gdsl_hash_t H)
 Get the fill factor of a hashtable.
gdsl_hash_t gdsl_hash_set_name (gdsl_hash_t H, const char *NEW_NAME)
 Set the name of a hashtable.
gdsl_element_t gdsl_hash_insert (gdsl_hash_t H, void *VALUE)
 Insert an element into a hashtable (PUSH).
gdsl_element_t gdsl_hash_remove (gdsl_hash_t H, const char *KEY)
 Remove an element from a hashtable (POP).
gdsl_hash_t gdsl_hash_delete (gdsl_hash_t H, const char *KEY)
 Delete an element from a hashtable.
gdsl_hash_t gdsl_hash_modify (gdsl_hash_t H, ushort NEW_ENTRIES_NB, ushort NEW_LISTS_MAX_SIZE)
 Increase the dimensions of a hashtable.
gdsl_element_t gdsl_hash_search (const gdsl_hash_t H, const char *KEY)
 Search for a particular element into a hashtable (GET).
gdsl_element_t gdsl_hash_map (const gdsl_hash_t H, gdsl_map_func_t MAP_F, void *USER_DATA)
 Parse a hashtable.
void gdsl_hash_write (const gdsl_hash_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write all the elements of a hashtable to a file.
void gdsl_hash_write_xml (const gdsl_hash_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Write the content of a hashtable to a file into XML.
void gdsl_hash_dump (const gdsl_hash_t H, gdsl_write_func_t WRITE_F, FILE *OUTPUT_FILE, void *USER_DATA)
 Dump the internal structure of a hashtable to a file.

Typedef Documentation

typedef struct hash_table* gdsl_hash_t

GDSL hashtable type.

This type is voluntary opaque. Variables of this kind could'nt be directly used, but by the functions of this module.

Definition at line 54 of file gdsl_hash.h.

typedef const char*(* gdsl_key_func_t)(void *VALUE)

GDSL hashtable key function type.

Postcondition:
Returned value must be != "" && != NULL.
Parameters:
VALUEThe value used to get the key from
Returns:
The key associated to the VALUE.

Definition at line 62 of file gdsl_hash.h.

typedef ulong(* gdsl_hash_func_t)(const char *KEY)

GDSL hashtable hash function type.

Parameters:
KEYthe key used to compute the hash code.
Returns:
The hashed value computed from KEY.

Definition at line 70 of file gdsl_hash.h.


Function Documentation

ulong gdsl_hash ( const char *  KEY)

Computes a hash value from a NULL terminated character string.

This function computes a hash value from the NULL terminated KEY string.

Note:
Complexity: O ( |key| )
Precondition:
KEY must be NULL-terminated.
Parameters:
KEYThe NULL terminated string to compute the key from
Returns:
the hash code computed from KEY.
gdsl_hash_t gdsl_hash_alloc ( const char *  NAME,
gdsl_alloc_func_t  ALLOC_F,
gdsl_free_func_t  FREE_F,
gdsl_key_func_t  KEY_F,
gdsl_hash_func_t  HASH_F,
ushort  INITIAL_ENTRIES_NB 
)

Create a new hashtable.

Allocate a new hashtable data structure which name is set to a copy of NAME. The new hashtable will contain initially INITIAL_ENTRIES_NB lists. This value could be (only) increased with gdsl_hash_modify() function. Until this function is called, then all H's lists entries have no size limit. The function pointers ALLOC_F and FREE_F could be used to respectively, alloc and free elements in the hashtable. The KEY_F function must provide a unique key associated to its argument. The HASH_F function must compute a hash code from its argument. These pointers could be set to NULL to use the default ones:

  • the default ALLOC_F simply returns its argument
  • the default FREE_F does nothing
  • the default KEY_F simply returns its argument
  • the default HASH_F is gdsl_hash() above
Note:
Complexity: O( 1 )
Precondition:
nothing.
Parameters:
NAMEThe name of the new hashtable to create
ALLOC_FFunction to alloc element when inserting it in the hashtable
FREE_FFunction to free element when deleting it from the hashtable
KEY_FFunction to get the key from an element
HASH_FFunction used to compute the hash value.
INITIAL_ENTRIES_NBInitial number of entries of the hashtable
Returns:
the newly allocated hashtable in case of success.
NULL in case of insufficient memory.
See also:
gdsl_hash_free()
gdsl_hash_flush()
gdsl_hash_insert()
gdsl_hash_modify()

Destroy a hashtable.

Deallocate all the elements of the hashtable H by calling H's FREE_F function passed to gdsl_hash_alloc(). The name of H is deallocated and H is deallocated itself too.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to destroy
See also:
gdsl_hash_alloc()
gdsl_hash_flush()

Flush a hashtable.

Deallocate all the elements of the hashtable H by calling H's FREE_F function passed to gdsl_hash_alloc(). H is not deallocated itself and H's name is not modified.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to flush
See also:
gdsl_hash_alloc()
gdsl_hash_free()
const char* gdsl_hash_get_name ( const gdsl_hash_t  H)

Get the name of a hashtable.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_hash_t
Postcondition:
The returned string MUST NOT be freed.
Parameters:
HThe hashtable to get the name from
Returns:
the name of the hashtable H.
See also:
gdsl_hash_set_name()

Get the number of entries of a hashtable.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to use.
Returns:
the number of lists entries of the hashtable H.
See also:
gdsl_hash_get_size()
gdsl_hash_fill_factor()

Get the max number of elements allowed in each entry of a hashtable.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to use.
Returns:
0 if no lists max size was set before (ie. no limit for H's entries).
the max number of elements for each entry of the hashtable H, if the function gdsl_hash_modify() was used with a NEW_LISTS_MAX_SIZE greather than the actual one.
See also:
gdsl_hash_fill_factor()
gdsl_hash_get_entries_number()
gdsl_hash_get_longest_list_size()
gdsl_hash_modify()

Get the number of elements of the longest list entry of a hashtable.

Note:
Complexity: O( L ), where L = gdsl_hash_get_entries_number(H)
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to use.
Returns:
the number of elements of the longest list entry of the hashtable H.
See also:
gdsl_hash_get_size()
gdsl_hash_fill_factor()
gdsl_hash_get_entries_number()
gdsl_hash_get_lists_max_size()

Get the size of a hashtable.

Note:
Complexity: O( L ), where L = gdsl_hash_get_entries_number(H)
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to get the size from
Returns:
the number of elements of H (noted |H|).
See also:
gdsl_hash_get_entries_number()
gdsl_hash_fill_factor()
gdsl_hash_get_longest_list_size()

Get the fill factor of a hashtable.

Note:
Complexity: O( L ), where L = gdsl_hash_get_entries_number(H)
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to use
Returns:
The fill factor of H, computed as |H| / L
See also:
gdsl_hash_get_entries_number()
gdsl_hash_get_longest_list_size()
gdsl_hash_get_size()
gdsl_hash_t gdsl_hash_set_name ( gdsl_hash_t  H,
const char *  NEW_NAME 
)

Set the name of a hashtable.

Change the previous name of the hashtable H to a copy of NEW_NAME.

Note:
Complexity: O( 1 )
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to change the name
NEW_NAMEThe new name of H
Returns:
the modified hashtable in case of success.
NULL in case of insufficient memory.
See also:
gdsl_hash_get_name()
gdsl_element_t gdsl_hash_insert ( gdsl_hash_t  H,
void *  VALUE 
)

Insert an element into a hashtable (PUSH).

Allocate a new element E by calling H's ALLOC_F function on VALUE. The key K of the new element E is computed using KEY_F called on E. If the value of gdsl_hash_get_lists_max_size(H) is not reached, or if it is equal to zero, then the insertion is simple. Otherwise, H is re-organized as follow:

  • its actual gdsl_hash_get_entries_number(H) (say N) is modified as N * 2 + 1
  • its actual gdsl_hash_get_lists_max_size(H) (say M) is modified as M * 2 The element E is then inserted into H at the entry computed by HASH_F( K ) modulo gdsl_hash_get_entries_number(H). ALLOC_F, KEY_F and HASH_F are the function pointers passed to gdsl_hash_alloc().
Note:
Complexity: O( 1 ) if gdsl_hash_get_lists_max_size(H) is not reached or if it is equal to zero
Complexity: O ( gdsl_hash_modify (H) ) if gdsl_hash_get_lists_max_size(H) is reached, so H needs to grow
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to modify
VALUEThe value used to make the new element to insert into H
Returns:
the inserted element E in case of success.
NULL in case of insufficient memory.
See also:
gdsl_hash_alloc()
gdsl_hash_remove()
gdsl_hash_delete()
gdsl_hash_get_size()
gdsl_hash_get_entries_number()
gdsl_hash_modify()
gdsl_element_t gdsl_hash_remove ( gdsl_hash_t  H,
const char *  KEY 
)

Remove an element from a hashtable (POP).

Search into the hashtable H for the first element E equal to KEY. If E is found, it is removed from H and then returned.

Note:
Complexity: O( M ), where M is the average size of H's lists
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to modify
KEYThe key used to find the element to remove
Returns:
the first founded element equal to KEY in H in case is found.
NULL in case no element equal to KEY is found in H.
See also:
gdsl_hash_insert()
gdsl_hash_search()
gdsl_hash_delete()
gdsl_hash_t gdsl_hash_delete ( gdsl_hash_t  H,
const char *  KEY 
)

Delete an element from a hashtable.

Remove from he hashtable H the first founded element E equal to KEY. If E is found, it is removed from H and E is deallocated using H's FREE_F function passed to gdsl_hash_alloc(), then H is returned.

Note:
Complexity: O( M ), where M is the average size of H's lists
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to modify
KEYThe key used to find the element to remove
Returns:
the modified hashtable after removal of E if E was found.
NULL if no element equal to KEY was found.
See also:
gdsl_hash_insert()
gdsl_hash_search()
gdsl_hash_remove()
gdsl_hash_t gdsl_hash_modify ( gdsl_hash_t  H,
ushort  NEW_ENTRIES_NB,
ushort  NEW_LISTS_MAX_SIZE 
)

Increase the dimensions of a hashtable.

The hashtable H is re-organized to have NEW_ENTRIES_NB lists entries. Each entry is limited to NEW_LISTS_MAX_SIZE elements. After a call to this function, all insertions into H will make H automatically growing if needed. The grow is needed each time an insertion makes an entry list to reach NEW_LISTS_MAX_SIZE elements. In this case, H will be reorganized automatically by gdsl_hash_insert().

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t & NEW_ENTRIES_NB > gdsl_hash_get_entries_number(H) & NEW_LISTS_MAX_SIZE > gdsl_hash_get_lists_max_size(H)
Parameters:
HThe hashtable to modify
NEW_ENTRIES_NB
NEW_LISTS_MAX_SIZE
Returns:
the modified hashtable H in case of success
NULL in case of failure, or in case NEW_ENTRIES_NB <= gdsl_hash_get_entries_number(H) or in case NEW_LISTS_MAX_SIZE <= gdsl_hash_get_lists_max_size(H) in these cases, H is not modified
See also:
gdsl_hash_insert()
gdsl_hash_get_entries_number()
gdsl_hash_get_fill_factor()
gdsl_hash_get_longest_list_size()
gdsl_hash_get_lists_max_size()
gdsl_element_t gdsl_hash_search ( const gdsl_hash_t  H,
const char *  KEY 
)

Search for a particular element into a hashtable (GET).

Search the first element E equal to KEY in the hashtable H.

Note:
Complexity: O( M ), where M is the average size of H's lists
Precondition:
H must be a valid gdsl_hash_t
Parameters:
HThe hashtable to search the element in
KEYThe key to compare H's elements with
Returns:
the founded element E if it was found.
NULL in case the searched element E was not found.
See also:
gdsl_hash_insert()
gdsl_hash_remove()
gdsl_hash_delete()
gdsl_element_t gdsl_hash_map ( const gdsl_hash_t  H,
gdsl_map_func_t  MAP_F,
void *  USER_DATA 
)

Parse a hashtable.

Parse all elements of the hashtable H. The MAP_F function is called on each H's element with USER_DATA argument. If MAP_F returns GDSL_MAP_STOP then gdsl_hash_map() stops and returns its last examinated element.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t & MAP_F != NULL
Parameters:
HThe hashtable to map
MAP_FThe map function.
USER_DATAUser's datas passed to MAP_F
Returns:
the first element for which MAP_F returns GDSL_MAP_STOP.
NULL when the parsing is done.
void gdsl_hash_write ( const gdsl_hash_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write all the elements of a hashtable to a file.

Write the elements of the hashtable H to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL & WRITE_F != NULL
Parameters:
HThe hashtable to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write H's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_hash_write_xml()
gdsl_hash_dump()
void gdsl_hash_write_xml ( const gdsl_hash_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Write the content of a hashtable to a file into XML.

Write the elements of the hashtable H to OUTPUT_FILE, into XML language. If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL
Parameters:
HThe hashtable to write.
WRITE_FThe write function.
OUTPUT_FILEThe file where to write H's elements.
USER_DATAUser's datas passed to WRITE_F.
See also:
gdsl_hash_write()
gdsl_hash_dump()
void gdsl_hash_dump ( const gdsl_hash_t  H,
gdsl_write_func_t  WRITE_F,
FILE *  OUTPUT_FILE,
void *  USER_DATA 
)

Dump the internal structure of a hashtable to a file.

Dump the structure of the hashtable H to OUTPUT_FILE. If WRITE_F != NULL, then uses WRITE_F to write H's elements to OUTPUT_FILE. Additionnal USER_DATA argument could be passed to WRITE_F.

Note:
Complexity: O( |H| )
Precondition:
H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL
Parameters:
HThe hashtable to write
WRITE_FThe write function
OUTPUT_FILEThe file where to write H's elements
USER_DATAUser's datas passed to WRITE_F
See also:
gdsl_hash_write()
gdsl_hash_write_xml()