gdsl_hash.3

书籍上的数据结构源代码

H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to get the size from 
.RE
.PP
\fBReturns:\fP
.RS 4
the number of elements of H (noted |H|). 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_get_entries_number()\fP 
.PP
gdsl_hash_fill_factor() 
.PP
\fBgdsl_hash_get_longest_list_size()\fP 
.RE
.PP

.SS "double gdsl_hash_get_fill_factor (const \fBgdsl_hash_t\fP H)"
.PP
Get the fill factor of a hashtable. 
.PP
\fBNote:\fP
.RS 4
Complexity: O( L ), where L = gdsl_hash_get_entries_number(H) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to use 
.RE
.PP
\fBReturns:\fP
.RS 4
The fill factor of H, computed as |H| / L 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_get_entries_number()\fP 
.PP
\fBgdsl_hash_get_longest_list_size()\fP 
.PP
\fBgdsl_hash_get_size()\fP 
.RE
.PP

.SS "\fBgdsl_hash_t\fP gdsl_hash_set_name (\fBgdsl_hash_t\fP H, const char * NEW_NAME)"
.PP
Set the name of a hashtable. 
.PP
Change the previous name of the hashtable H to a copy of NEW_NAME.
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to change the name 
.br
\fINEW_NAME\fP The new name of H 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified hashtable in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_get_name()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_hash_insert (\fBgdsl_hash_t\fP H, void * VALUE)"
.PP
Insert an element into a hashtable (PUSH). 
.PP
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:
.IP "\(bu" 2
its actual gdsl_hash_get_entries_number(H) (say N) is modified as N * 2 + 1
.IP "\(bu" 2
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 \fBgdsl_hash_alloc()\fP.
.PP
.PP
\fBNote:\fP
.RS 4
Complexity: O( 1 ) if gdsl_hash_get_lists_max_size(H) is not reached or if it is equal to zero 
.PP
Complexity: O ( gdsl_hash_modify (H) ) if gdsl_hash_get_lists_max_size(H) is reached, so H needs to grow 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to modify 
.br
\fIVALUE\fP The value used to make the new element to insert into H 
.RE
.PP
\fBReturns:\fP
.RS 4
the inserted element E in case of success. 
.PP
NULL in case of insufficient memory. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_alloc()\fP 
.PP
\fBgdsl_hash_remove()\fP 
.PP
\fBgdsl_hash_delete()\fP 
.PP
\fBgdsl_hash_get_size()\fP 
.PP
\fBgdsl_hash_get_entries_number()\fP 
.PP
\fBgdsl_hash_modify()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_hash_remove (\fBgdsl_hash_t\fP H, const char * KEY)"
.PP
Remove an element from a hashtable (POP). 
.PP
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.
.PP
\fBNote:\fP
.RS 4
Complexity: O( M ), where M is the average size of H's lists 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to modify 
.br
\fIKEY\fP The key used to find the element to remove 
.RE
.PP
\fBReturns:\fP
.RS 4
the first founded element equal to KEY in H in case is found. 
.PP
NULL in case no element equal to KEY is found in H. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_insert()\fP 
.PP
\fBgdsl_hash_search()\fP 
.PP
\fBgdsl_hash_delete()\fP 
.RE
.PP

.SS "\fBgdsl_hash_t\fP gdsl_hash_delete (\fBgdsl_hash_t\fP H, const char * KEY)"
.PP
Delete an element from a hashtable. 
.PP
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 \fBgdsl_hash_alloc()\fP, then H is returned.
.PP
\fBNote:\fP
.RS 4
Complexity: O( M ), where M is the average size of H's lists 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to modify 
.br
\fIKEY\fP The key used to find the element to remove 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified hashtable after removal of E if E was found. 
.PP
NULL if no element equal to KEY was found. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_insert()\fP 
.PP
\fBgdsl_hash_search()\fP 
.PP
\fBgdsl_hash_remove()\fP 
.RE
.PP

.SS "\fBgdsl_hash_t\fP gdsl_hash_modify (\fBgdsl_hash_t\fP H, ushort NEW_ENTRIES_NB, ushort NEW_LISTS_MAX_SIZE)"
.PP
Increase the dimensions of a hashtable. 
.PP
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 \fBgdsl_hash_insert()\fP.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
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) 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to modify 
.br
\fINEW_ENTRIES_NB\fP 
.br
\fINEW_LISTS_MAX_SIZE\fP 
.RE
.PP
\fBReturns:\fP
.RS 4
the modified hashtable H in case of success 
.PP
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 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_insert()\fP 
.PP
\fBgdsl_hash_get_entries_number()\fP 
.PP
\fBgdsl_hash_get_fill_factor()\fP 
.PP
\fBgdsl_hash_get_longest_list_size()\fP 
.PP
\fBgdsl_hash_get_lists_max_size()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_hash_search (const \fBgdsl_hash_t\fP H, const char * KEY)"
.PP
Search for a particular element into a hashtable (GET). 
.PP
Search the first element E equal to KEY in the hashtable H.
.PP
\fBNote:\fP
.RS 4
Complexity: O( M ), where M is the average size of H's lists 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to search the element in 
.br
\fIKEY\fP The key to compare H's elements with 
.RE
.PP
\fBReturns:\fP
.RS 4
the founded element E if it was found. 
.PP
NULL in case the searched element E was not found. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_insert()\fP 
.PP
\fBgdsl_hash_remove()\fP 
.PP
\fBgdsl_hash_delete()\fP 
.RE
.PP

.SS "\fBgdsl_element_t\fP gdsl_hash_map (const \fBgdsl_hash_t\fP H, \fBgdsl_map_func_t\fP MAP_F, void * USER_DATA)"
.PP
Parse a hashtable. 
.PP
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 \fBgdsl_hash_map()\fP stops and returns its last examinated element.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t & MAP_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to map 
.br
\fIMAP_F\fP The map function. 
.br
\fIUSER_DATA\fP User's datas passed to MAP_F 
.RE
.PP
\fBReturns:\fP
.RS 4
the first element for which MAP_F returns GDSL_MAP_STOP. 
.PP
NULL when the parsing is done. 
.RE
.PP

.SS "void gdsl_hash_write (const \fBgdsl_hash_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Write all the elements of a hashtable to a file. 
.PP
Write the elements of the hashtable H to OUTPUT_FILE, using WRITE_F function. Additionnal USER_DATA argument could be passed to WRITE_F.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL & WRITE_F != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write H's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_write_xml()\fP 
.PP
\fBgdsl_hash_dump()\fP 
.RE
.PP

.SS "void gdsl_hash_write_xml (const \fBgdsl_hash_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Write the content of a hashtable to a file into XML. 
.PP
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.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to write. 
.br
\fIWRITE_F\fP The write function. 
.br
\fIOUTPUT_FILE\fP The file where to write H's elements. 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F. 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_write()\fP 
.PP
\fBgdsl_hash_dump()\fP 
.RE
.PP

.SS "void gdsl_hash_dump (const \fBgdsl_hash_t\fP H, \fBgdsl_write_func_t\fP WRITE_F, FILE * OUTPUT_FILE, void * USER_DATA)"
.PP
Dump the internal structure of a hashtable to a file. 
.PP
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.
.PP
\fBNote:\fP
.RS 4
Complexity: O( |H| ) 
.RE
.PP
\fBPrecondition:\fP
.RS 4
H must be a valid gdsl_hash_t & OUTPUT_FILE != NULL 
.RE
.PP
\fBParameters:\fP
.RS 4
\fIH\fP The hashtable to write 
.br
\fIWRITE_F\fP The write function 
.br
\fIOUTPUT_FILE\fP The file where to write H's elements 
.br
\fIUSER_DATA\fP User's datas passed to WRITE_F 
.RE
.PP
\fBSee also:\fP
.RS 4
\fBgdsl_hash_write()\fP 
.PP
\fBgdsl_hash_write_xml()\fP 
.RE
.PP