diff options
| -rw-r--r-- | doc/info/mds.texinfo | 502 | ||||
| -rw-r--r-- | src/libmdsserver/hash-help.h | 4 | ||||
| -rw-r--r-- | src/libmdsserver/hash-table.h | 8 | ||||
| -rw-r--r-- | src/libmdsserver/table-common.h | 2 |
4 files changed, 194 insertions, 322 deletions
diff --git a/doc/info/mds.texinfo b/doc/info/mds.texinfo index ab043e6..4972253 100644 --- a/doc/info/mds.texinfo +++ b/doc/info/mds.texinfo @@ -1226,6 +1226,7 @@ However, @code{hash_table_unmarshal} and @menu * Client List:: The @code{client_list_t} data structure. * Linked List:: The @code{linked_list_t} data structure. +* Tables:: The @code{fd_table_t} and @code{hash_table_t} data structures. @end menu @@ -1445,349 +1446,220 @@ into the stream @code{output}. -@node GNU Free Documentation License -@appendix GNU Free Documentation License -@include fdl.texinfo - -@bye - - -/** - * Hash table entry - */ -typedef struct hash_entry -{ - /** - * A key - */ - size_t key; - - /** - * The value associated with the key - */ - size_t value; - - /** - * The truncated hash value of the key - */ - size_t hash; - - /** - * The next entry in the bucket - */ - struct hash_entry* next; - -} hash_entry_t; - - -/** - * Value lookup table based on hash value, that do not support - */ -typedef struct hash_table -{ - /** - * The table's capacity, i.e. the number of buckets - */ - size_t capacity; - - /** - * Entry buckets - */ - hash_entry_t** buckets; - - /** - * When, in the ratio of entries comparied to the capacity, to grow the table - */ - float load_factor; - - /** - * When, in the number of entries, to grow the table - */ - size_t threshold; - - /** - * The number of entries stored in the table - */ - size_t size; - - /** - * Check whether two values are equal - * - * If this function pointer is `NULL`, the identity is used - * - * Be aware, this variable cannot be marshalled - */ - compare_func* value_comparator; - - /** - * Check whether two keys are equal - * - * If this function pointer is `NULL`, the identity is used - * - * Be aware, this variable cannot be marshalled - */ - compare_func* key_comparator; - - /** - * Calculate the hash of a key - * - * If this function pointer is `NULL`, the identity hash is used - * - * Be aware, this variable cannot be marshalled - * - * @param key The key - * @return The hash of the key - */ - hash_func* hasher; - -} hash_table_t; - -/** - * Create a hash table - * - * @param this Memory slot in which to store the new hash table - * @param initial_capacity The initial capacity of the table - * @param load_factor The load factor of the table, i.e. when to grow the table - * @return Non-zero on error, `errno` will have been set accordingly - */ -int hash_table_create_fine_tuned(hash_table_t* restrict this, size_t initial_capacity, float load_factor); +@node Tables +@subsection Tables -/** - * Create a hash table - * - * @param this:hash_table_t* Memory slot in which to store the new hash table - * @param initial_capacity:size_t The initial capacity of the table - * @return :int Non-zero on error, `errno` will have been set accordingly - */ -#define hash_table_create_tuned(this, initial_capacity) \ - hash_table_create_fine_tuned(this, initial_capacity, 0.75f) +libmdsserver defines two similar data structures: +@code{fd_table_t} and @code{hash_table_t}. Whenever +a function exists for both data structures we will +write @code{X_table} instead of @code{fd_table} and +@code{hash_table}. Additionally, unless otherwise +stated, a function's parameter named @code{this} +will be of the type @code{hash_table_t*} if the +function's name start with @code{hash_table} and +@code{fd_table_t*} if the function's name start +with @code{fd_table}, with the @code{restrict} +modifier. -/** - * Create a hash table - * - * @param this:hash_table_t* Memory slot in which to store the new hash table - * @return :int Non-zero on error, `errno` will have been set accordingly - */ -#define hash_table_create(this) \ - hash_table_create_tuned(this, 16) - -/** - * Release all resources in a hash table, should - * be done even if construction fails - * - * @param this The hash table - * @param keys_freer Function that frees a key, `NULL` if keys should not be freed - * @param values_freer Function that frees a value, `NULL` if value should not be freed - */ -void hash_table_destroy(hash_table_t* restrict this, free_func* key_freer, free_func* value_freer); +@table @asis +@item @code{X_table_create} [(@code{this}) @arrow{} @code{int}] +Initialises @code{*this} so it can be used as a +table. Returns zero on and only on success. -/** - * Check whether a value is stored in the table - * - * @param this The hash table - * @param value The value - * @return Whether the value is stored in the table - */ -int hash_table_contains_value(const hash_table_t* restrict this, size_t value) __attribute__((pure)); +These functions are defined as macros. -/** - * Check whether a key is used in the table - * - * @param this The hash table - * @param key The key - * @return Whether the key is used - */ -int hash_table_contains_key(const hash_table_t* restrict this, size_t key) __attribute__((pure)); +@item @code{X_table_create_tuned} [(@code{this, size_t initial_capacity}) @arrow{} @code{int}] +Initialises @code{*this} so it can be used as a +table, and makes its initial capacity at least +@code{initial_capacity}. Returns zero on and only +on success. -/** - * Look up a value in the table - * - * @param this The hash table - * @param key The key associated with the value - * @return The value associated with the key, 0 if the key was not used - */ -size_t hash_table_get(const hash_table_t* restrict this, size_t key); +@code{hash_table_create_tuned} is defined as a macro. -/** - * Look up an entry in the table - * - * @param this The hash table - * @param key The key associated with the value - * @return The entry associated with the key, `NULL` if the key was not used - */ -hash_entry_t* hash_table_get_entry(const hash_table_t* restrict this, size_t key); +@item @code{hash_table_create_tuned} [(@code{this, size_t initial_capacity, float load_factor}) @arrow{} @code{int}] +Initialises @code{*this} so it can be used as a +table, and makes its initial capacity at least +@code{initial_capacity} and its load factor +@code{load_factor}. Returns zero on and only +on success. -/** - * Add an entry to the table - * - * @param this The hash table - * @param key The key of the entry to add - * @param value The value of the entry to add - * @return The previous value associated with the key, 0 if the key was not used. - * 0 will also be returned on error, check the `errno` variable. - */ -size_t hash_table_put(hash_table_t* restrict this, size_t key, size_t value); +@item @code{X_table_destroy} [(@code{this, free_func* key_freer, free_func* value_freer}) @arrow{} @code{void}] +Release all resources in the table @code{*this}, +but do not @code{free} @code{this} itself. +Should be called even if construction fails. +If @code{keys_freer} is not @code{NULL}, this +function will be called for each key. +If @code{values_freer} is not @code{NULL}, this +function will be called for each value. + +@item @code{X_table_contains_value} [(@code{const this, size_t value}) @arrow{} @code{int}] +Check whether the value @code{value} is stored +in the table @code{*this}. + +@item @code{X_table_contains_key} [(@code{const this, key}) @arrow{} @code{int}] +Check whether the key @code{code} is used in the +table @code{*this}. + +The data type for the parameter @code{key} is +@code{size_t} for @code{hash_table} and @code{int} +for @code{fd_table}. + +@item @code{X_table_get} [(@code{const this, key}) @arrow{} @code{size_t}] +Look up a value by its key @code{key} in the +table @code{*this}. Zero will be returned if +the key was not used. + +@item @code{hash_table_get_entry} [(@code{const this, size_t key}) @arrow{} @code{hash_entry_t*}] +Look up an entry by its key @code{key} in the +table @code{*this}. @code{NULL} will be returned +if the key was not used. + +@item @code{X_table_put} [(@code{this, key, size_t value}) @arrow{} @code{size_t}] +Map the value @code{value} to the key @code{key} +in the talbe @code{*this}. If a value was already +mapped to the key, that value will be returned, +otherwise zero will be returned. Zero will also +be returned on error. @code{errno} will be set to +zero on and only on success. + +The data type for the parameter @code{key} is +@code{size_t} for @code{hash_table} and @code{int} +for @code{fd_table}. + +@item @code{X_table_remove} [(@code{this, key}) @arrow{} @code{size_t}] +Unmaps the key @code{key} for the table @code{*this}. +If a value was mapped to the key, that value will +be returned, otherwise zero will be returned. + +The data type for the parameter @code{key} is +@code{size_t} for @code{hash_table} and @code{int} +for @code{fd_table}. + +@item @code{X_table_clear} [(@code{this}) @arrow{} @code{void}] +Unmaps all keys in the table @code{*this}. + +@item @code{X_table_unmarshal} [(@code{this, char* restrict data, remap_func* remapper}) @arrow{} @code{int}] +As described in @ref{Data Structures} but with one +additional parameter: @code{remapper}. If this +parameter is not @code{NULL} this function is used +to edit values. It will be called once for each +value and the output of the function will be used +inplace of the input value. +@end table -/** - * Remove an entry in the table - * - * @param this The hash table - * @param key The key of the entry to remove - * @return The previous value associated with the key, 0 if the key was not used - */ -size_t hash_table_remove(hash_table_t* restrict this, size_t key); +@file{<libmdsserver/hash-table.h>} also defines +as wrapper macro for the @code{for} keyword: -/** - * Remove all entries in the table - * - * @param this The hash table - */ -void hash_table_clear(hash_table_t* restrict this); +@table @asis +@item @code{foreach_hash_table_entry} [(@code{hash_table_t this, size_t i, hash_entry_t* entry})] +Iterates over entry element in the hash table +@code{*this}. On each iteration, the entry will +be stored to the variable @code{entry} and the +bucket index will be stored to the variable +@code{i}. -/** - * Wrapper for `for` keyword that iterates over entry element in a hash table - * - * @param table:hash_table_t The hans table - * @param i:size_t The variable to store the buckey index in at each iteration - * @param entry:hash_entry_t* The variable to store the entry in at each iteration - */ -#define foreach_hash_table_entry(table, i, entry) \ - for (i = 0; i < (table).capacity; i++) \ - for (entry = (table).buckets[i]; entry != NULL; entry = entry->next) +@example +void print_hash_table(hash_table_t* table) +@{ + hash_entry_t* entry; + size_t i; + foreach_hash_table_entry (*table, i, entry) + printf("%zu --> %zu\n", entry->key, entry->value); +@} +@end example -/** - * Unmarshals a hash table - * - * @param this Memory slot in which to store the new hash table - * @param data In buffer with the marshalled data - * @param remapper Function that translates values, `NULL` if not translation takes place - * @return Non-zero on error, errno will be set accordingly. - * Destroy the table on error. - */ -int hash_table_unmarshal(hash_table_t* restrict this, char* restrict data, remap_func* remapper); +Note the the data type for the parameter @code{this} +is not a popinter. +@end table +The structures @code{hash_table_t} and @code{fd_table_t} +contain the variable @code{value_comparator} which by +default is @code{NULL}. If this variable is set to @code{NULL}, +two values will be considered equal if and only if they are +numerically identical; otherwise two values will be considered +equal if and only if @code{value_comparator} returned a +non-zero value if those two values are used for the function's +arguments. The data type for @code{value_comparator} is +@code{compare_func*}. +@code{hash_table_t} also contains two other variables: +@table @code +@item compare_func* key_comparator +Identical to @code{value_comparator}, except it is used for +keys rather the values. + +@item hash_func* hasher +By default, the hash value for key is identical to the key +itself. However, if this variable is not @code{NULL}, it +will be used to calculate the hash value for keys. +@end table +There is a secondary data structure defined for hash tables: +@code{hash_entry_t} @{also known as @code{struct hash_entry}@}. +It is the data structure used for entries in a hash table. +@code{hash_entry_t} contain three variables you may be interested in: - /** - * The number of entries stored in the table - */ - size_t size; - - /** - * Map from keys to values - */ - size_t* values; - - /** - * Map from keys to whether that are in used, bit-packed - */ - uint64_t* used; - - /** - * Check whether two values are equal - * - * If this function pointer is `NULL`, the identity is used - * - * Be aware, this variable cannot be marshalled - */ - compare_func* value_comparator; +@table @code +@item size_t key +The key. -/** - * Create a fd table - * - * @param this Memory slot in which to store the new fd table - * @param initial_capacity The initial capacity of the table - * @return Non-zero on error, `errno` will have been set accordingly - */ -int fd_table_create_tuned(fd_table_t* restrict this, size_t initial_capacity); +@item size_t value +The value associated with the key. -/** - * Create a fd table - * - * @param this:fd_table_t* Memory slot in which to store the new fd table - * @return :int Non-zero on error, `errno` will have been set accordingly - */ -#define fd_table_create(this) \ - fd_table_create_tuned(this, 16) +@item size_t hash +The hash value of the key. +@end table -/** - * Release all resources in a fd table, should - * be done even if construction fails - * - * @param this The fd table - * @param keys_freer Function that frees a key, `NULL` if keys should not be freed - * @param values_freer Function that frees a value, `NULL` if value should not be freed - */ -void fd_table_destroy(fd_table_t* restrict this, free_func* key_freer, free_func* value_freer); +By inclusion of @file{<libmdsserver/table-common.h>}, +@file{<libmdsserver/hash-table.h>} and @file{<libmdsserver/fd-table.h>} +defines four @code{typedef} for function signatures: -/** - * Check whether a value is stored in the table - * - * @param this The fd table - * @param value The value - * @return Whether the value is stored in the table - */ -int fd_table_contains_value(const fd_table_t* restrict this, size_t value) __attribute__((pure)); +@table @asis +@item @code{compare_func} [(@code{size_t a, size_t b}) @arrow{} @code{int}] +A function that performs a comparison of two objects. +Should return non-zero if and only if @code{a} and +@code{b} are to be considered equal in the given +context. + +@item @code{hash_func} [(@code{size_t value}) @arrow{} @code{size_t}] +A function that hashes an object or a value. +Should return the hash value for @code{value}. + +@item @code{free_func} [(@code{size_t obj}) @arrow{} @code{void}] +A function that, to the extent that is appropriate, +releases the object @code{obj}'s resources and +@code{free}:s it. + +@item @code{remap_func} [(@code{size_t obj}) @arrow{} @code{size_t}] +A function that translates a object into a new object. +The function should return new object that should replace +the object @code{obj}. +@end table -/** - * Check whether a key is used in the table - * - * @param this The fd table - * @param key The key - * @return Whether the key is used - */ -int fd_table_contains_key(const fd_table_t* restrict this, int key) __attribute__((pure)); +If you are working with strings, you may consider +including the header file @file{<libmdsserver/hash-help.h>}. +It defines to useful functions: -/** - * Look up a value in the table - * - * @param this The fd table - * @param key The key associated with the value - * @return The value associated with the key, 0 if the key was not used - */ -size_t fd_table_get(const fd_table_t* restrict this, int key) __attribute__((pure)); +@table @asis +@item @code{string_hash} [(@code{const char* str}) @arrow{} @code{size_t}] +Calculate and returns the hash value of the string @code{str}. -/** - * Add an entry to the table - * - * @param this The fd table - * @param key The key of the entry to add - * @param value The value of the entry to add - * @return The previous value associated with the key, 0 if the key was not used. - * 0 will also be returned on error, check the `errno` variable. - */ -size_t fd_table_put(fd_table_t* restrict this, int key, size_t value); +@item @code{string_comparator} [(@code{char* str_a, char* str_b}) @arrow{} @code{int}] +Returns non-zero if either both @code{str_a} and @code{str_b} +are @code{NULL} or neither are @code{NULL} but are identical +strings by content upto their first NUL characters (or by address). +@end table -/** - * Remove an entry in the table - * - * @param this The fd table - * @param key The key of the entry to remove - * @return The previous value associated with the key, 0 if the key was not used - */ -size_t fd_table_remove(fd_table_t* restrict this, int key); +These functions are defined as pure and @code{static inline}. -/** - * Remove all entries in the table - * - * @param this The fd table - */ -void fd_table_clear(fd_table_t* restrict this); -/** - * Unmarshals a fd table - * - * @param this Memory slot in which to store the new fd table - * @param data In buffer with the marshalled data - * @param remapper Function that translates values, `NULL` if not translation takes place - * @return Non-zero on error, errno will be set accordingly. - * Destroy the table on error. - */ -int fd_table_unmarshal(fd_table_t* restrict this, char* restrict data, remap_func* remapper); +@node GNU Free Documentation License +@appendix GNU Free Documentation License +@include fdl.texinfo +@bye diff --git a/src/libmdsserver/hash-help.h b/src/libmdsserver/hash-help.h index ec08ada..cdee6d7 100644 --- a/src/libmdsserver/hash-help.h +++ b/src/libmdsserver/hash-help.h @@ -27,7 +27,7 @@ * Calculate the hash of a string * * @param str The string - * @return The hash of the string + * @return The hash of the string */ static inline size_t __attribute__((pure)) string_hash(const char* str) { @@ -42,7 +42,7 @@ static inline size_t __attribute__((pure)) string_hash(const char* str) /** - * Check whether two char* are of equal value + * Check whether two `char*` are of equal value * * @param str_a The first string * @param str_b The second string diff --git a/src/libmdsserver/hash-table.h b/src/libmdsserver/hash-table.h index 2f4d03b..789af20 100644 --- a/src/libmdsserver/hash-table.h +++ b/src/libmdsserver/hash-table.h @@ -222,13 +222,13 @@ void hash_table_clear(hash_table_t* restrict this); /** * Wrapper for `for` keyword that iterates over entry element in a hash table * - * @param table:hash_table_t The hans table + * @param this:hash_table_t The hash table * @param i:size_t The variable to store the buckey index in at each iteration * @param entry:hash_entry_t* The variable to store the entry in at each iteration */ -#define foreach_hash_table_entry(table, i, entry) \ - for (i = 0; i < (table).capacity; i++) \ - for (entry = (table).buckets[i]; entry != NULL; entry = entry->next) +#define foreach_hash_table_entry(this, i, entry) \ + for (i = 0; i < (this).capacity; i++) \ + for (entry = (this).buckets[i]; entry != NULL; entry = entry->next) /** * Calculate the buffer size need to marshal a hash table diff --git a/src/libmdsserver/table-common.h b/src/libmdsserver/table-common.h index 452b4e4..ae0e8e0 100644 --- a/src/libmdsserver/table-common.h +++ b/src/libmdsserver/table-common.h @@ -40,7 +40,7 @@ typedef int compare_func(size_t a, size_t b); typedef size_t hash_func(size_t value); /** - * A function that release an objects resources an frees it + * A function that releases an object's resources and `free`:s it * * @param obj The object */ |