diff options
Diffstat (limited to '')
| -rw-r--r-- | doc/info/mds.texinfo | 379 | ||||
| -rw-r--r-- | src/libmdsserver/hash-list.h | 160 | ||||
| -rw-r--r-- | src/mds-colour.c | 89 | ||||
| -rw-r--r-- | src/mds-colour.h | 48 |
4 files changed, 532 insertions, 144 deletions
diff --git a/doc/info/mds.texinfo b/doc/info/mds.texinfo index af1aafb..0b6f62f 100644 --- a/doc/info/mds.texinfo +++ b/doc/info/mds.texinfo @@ -6846,10 +6846,23 @@ In the header file defines a data structure for message between the server or client and the master server, with the capability of reading for a socket. + +@item @code{hash_list} @{abstract@} +@tpindex @code{hash_list} +@cpindex Lists, hash +@cpindex Hash lists +@cpindex Tables, hash +@cpindex Maps, hash +@cpindex Dictionary, hash +@cpindex Hash table +In the header file @file{<libmdsserver/hash-list.h>}, +libmdsserver defines an abstract class known as hash list. +It is intended as an alternative to hash tables, where +the number of stored elements is low. @end table These data structures share a common set of associated -function. However, they do not use the same functions; +methods. However, they do not use the same methods; they are identical except they are are named with the associated data structure. We will use @code{X_t} as an example. @@ -6893,7 +6906,7 @@ in @code{*out}. @sgindex @code{SIGUSR1} @sgindex @code{SIGUPDATE} Calculates the exact allocate size needed for the -parameter @code{data} in the function @code{X_marshal} +parameter @code{data} in the method @code{X_marshal} if called with the same @code{this} parameter. @item @code{X_marshal} [(@code{const X_t* restrict this, char* restrict data}) @arrow{} @code{void}] @@ -6944,12 +6957,12 @@ However, @code{hash_table_unmarshal} and * 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. +* Hash List:: The @code{hash_list} abstract data structure. * Message Structure:: The @code{mds_message_t} data structure. @end menu -@page @node Client List @subsection Client List @@ -6973,19 +6986,19 @@ grow when needed, but it is a good idea to tell it how many elements you are planning to populate it with. -@code{client_list_t} has two associated functions for +@code{client_list_t} has two associated methods for manipulating its content: @table @asis @item @code{client_list_add} [(@code{client_list_t* restrict this, uint64_t client}) @arrow{} @code{int}] @fnindex @code{client_list_add} -This function will add the element @code{client} to +This method will add the element @code{client} to the list @code{*this}, and return zero on and only on success. @item @code{client_list_remove} [(@code{client_list_t* restrict this, uint64_t client}) @arrow{} @code{void}] @fnindex @code{client_list_remove} -This function will remove exactly one occurrence, +This method will remove exactly one occurrence, provided that there is at least one occurrence, of the element @code{client} for the list @code{*this}. @end table @@ -7089,7 +7102,7 @@ grow when needed, but it is a good idea to tell it how many elements you are planning to populate it with. -There are five functions adding and removing items to +There are five methods adding and removing items to and from a linked list: @table @asis @@ -7127,7 +7140,7 @@ Remove the node @code{node} from the list The data type for @code{this} is @code{linked_list_t*} with the @code{restrict} modifier for these and all -other @code{linked_list_t} functions. +other @code{linked_list_t} methods. Note that if the node @code{this->edge} is removed, the list become circularly linked and the sentinel @@ -7194,7 +7207,7 @@ Note that the data type for @code{this} in the macro is not a pointer. @end table -There is also a function intended for debugging: +There is also a method intended for debugging: @table @asis @item @code{linked_list_dump} [(@code{linked_list_t* restrict this, FILE* restrict output}) @arrow{} @code{void}] @@ -7222,13 +7235,13 @@ the stream @code{output}. @cpindex Hash table 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 +method 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 +stated, a method's parameter named @code{this} will +be of the type @code{hash_table_t*} if the method's name start with @code{hash_table} and -@code{fd_table_t*} if the function's name start with +@code{fd_table_t*} if the method's name start with @code{fd_table}, with the @code{restrict} modifier. @table @asis @@ -7238,7 +7251,7 @@ name start with @code{hash_table} and Initialises @code{*this} so it can be used as a table. Returns zero on and only on success. -These functions are defined as macros. +These methods are defined as macros. @item @code{X_table_create_tuned} [(@code{this, size_t initial_capacity}) @arrow{} @code{int}] @fnindex @code{hash_table_create_tuned} @@ -7264,9 +7277,9 @@ success. 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 +@code{keys_freer} is not @code{NULL}, this method will be called for each key. If @code{values_freer} -is not @code{NULL}, this function will be called for +is not @code{NULL}, this method will be called for each value. @item @code{X_table_contains_value} [(@code{const this, size_t value}) @arrow{} @code{int}] @@ -7333,9 +7346,9 @@ Unmaps all keys in the table @code{*this}. @fnindex @code{fd_table_unmarshal} 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 +parameter is not @code{NULL} this method is used to edit values. It will be called once for each value -and the output of the function will be used inplace +and the output of the method will be used inplace of the input value. @end table @@ -7346,7 +7359,7 @@ wrapper macro for the @code{for}-keyword: @item @code{foreach_hash_table_entry} [(@code{hash_table_t this, size_t i, hash_entry_t* entry})] @fnindex @code{foreach_hash_table_entry} Iterates over entry element in the hash table -@code{*this}. On each iteration, the entry will be +@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}. @@ -7374,8 +7387,8 @@ void print_hash_table(hash_table_t* table) @end example @end ifclear -Note the the data type for the parameter @code{this} -is not a popinter. +Note that the data type for the parameter @code{this} +is not a pointer. @end table @vrindex @code{value_comparator} @@ -7389,7 +7402,7 @@ 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 +those two values are used for the method's arguments. The data type for @code{value_comparator} is @code{compare_func*}. @@ -7433,38 +7446,38 @@ The hash value of the key. By inclusion of @file{<libmdsserver/table-common.h>}, @file{<libmdsserver/hash-table.h>} and @file{<libmdsserver/fd-table.h>} defines four -@code{typedef}:s for function signatures: +@code{typedef}:s for method signatures: @table @asis @item @code{compare_func} [(@code{size_t a, size_t b}) @arrow{} @code{int}] @tpindex @code{compare_func} -A function that performs a comparison of two objects. +A method 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}] @tpindex @code{hash_func} -A function that hashes an object or a value. Should +A method 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}] @tpindex @code{free_func} -A function that, to the extent that is appropriate, +A method 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}] @tpindex @code{remap_func} -A function that translates a object into a new object. -The function should return new object that should +A method that translates a object into a new object. +The method should return new object that should replace the object @code{obj}. @end table If you are working with strings, you may consider including the header file @file{<libmdsserver/hash-help.h>}. It defines to -useful functions: +useful methods: @table @asis @item @code{string_hash} [(@code{const char* str}) @arrow{} @code{size_t}] @@ -7481,11 +7494,301 @@ Returns non-zero if either both @code{str_a} and their first NUL characters (or by address.) @end table -These functions are defined as pure and +These methods are defined as pure and @code{static inline}. +@node Hash List +@subsection Hash List + +@tpindex @code{hash_list} +@cpindex List, hash +@cpindex Hash list +@cpindex Tables, hash +@cpindex Maps, hash +@cpindex Dictionary, hash +@cpindex Hash table +@code{hash_list} is an abstract data structure, +provided as an alternative to hash tables with +a low number of elements. @code{hash_list} is a +associated dynamic list, with hash keys, that +keeps removed slot free for reuse until they +are as many as the occupied slots. + +@fnindex @code{CREATE_HASH_LIST_SUBCLASS} +To use @code{hash_list}, a concrete subclass of +it must be created. To do this, call the macro +@code{CREATE_HASH_LIST_SUBCLASS}. It takes four +parameters: + +@enumerate 1 +@item +The name of the subclass, this must not be a string, +but rather formated as an identifier. This text +will replace the @code{hash_list} in all that the +macro defines. + +@item +@tpindex @code{KEY_T} +The data type of the keys. We will hence refer to +this as @code{KEY_T}. + +@item +A @code{const} version of the data type of the keys. +We will hence refer to this as @code{const KEY_T}. + +@item +@tpindex @code{VALUE_T} +The data type of the values. We will hence refer to +this as @code{VALUE_T}. It is however internally +type-defined as @code{hash_list_value_t}, but this +is not guaranteed to be true in the future. +@end enumerate + +@code{CREATE_HASH_LIST_SUBCLASS} will define two +structures, two method type definitions, four +@code{static inline} methods for the creator +of the subclass to implement, and a set of methods, +as well as one auxiliary type definition@footnote{This +type definition would be @code{hash_list_value_t} as +specified above.}. + +@tpindex @code{hash_list_entry_t} +@tpindex @code{struct hash_list_entry} +The first structure is called @code{hash_list_entry_t} +@{also known as @code{struct hash_list_entry}@}. Keep in +mind that @code{hash_list} is replaced by the first +argument in the call to @code{CREATE_HASH_LIST_SUBCLASS}. +This structure represents a entry, or slot, the hash list, +it contains three elements: + +@table @asis +@item @code{key} [@code{KEY_T}] +The key of the entry. Will be @code{NULL} if the slot +is unused; a @code{NULL} on a key is disallowed. +Note that @code{NULL} is equivalent to zero if the +data type is numeral primitively. + +@item @code{key_hash} [@code{size_t}] +The hash of the key. This element is transparent to the +user of the class. + +@item @code{value} [@code{VALUE_T}] +The value. +@end table + +@tpindex @code{hash_list_t} +@tpindex @code{struct hash_list} +The other structure is called @code{hash_list_t} +@{also known as @code{struct hash_list}@}. This +structure represents the entire hash list. It contains +six elements: + +@table @asis +@item @code{allocated} [@code{size_t}] +The number of allocated slots. This element is +transparent to the user of the class. + +@item @code{unused} [@code{size_t}] +The number of unused slot that has previously be used. +This element is transparent to the user of the class. + +@item @code{used} [@code{size_t}] +The number of slots that have been used, even if +no longer used. This element is transparent to the +user of the class. + +@item @code{slots} [@code{hash_list_entry_t*}] +The allocation for the slots. This element is +transparent to the user of the class. + +@item @code{freer} [@code{hash_list_entry_free_func*}] +@tpindex @code{hash_list_entry_free_func} +Method used to free keys and values of entries. +If left @code{NULL}, no keys or values are freed. +This value must be set after @code{hash_list_create} +or @code{hash_list_unmarshal} is called, not before. + +@item @code{hasher} [@code{hash_list_key_hash_func*}] +@tpindex @code{hash_list_key_hash_func} +method used to calculate the hash of a key. +If left @code{NULL}, the identity hash is used, that +is, the address of the key, or if it is numeral, it +is casted to @code{size_t}. +This value must be set after @code{hash_list_create} +or @code{hash_list_unmarshal} is called, not before. +@end table + +The two method-type definitions are: +@table @asis +@item @code{hash_list_entry_free_func} [(@code{hash_list_entry_t* entry}) @arrow{} @code{void}] +@tpindex @code{hash_list_entry_free_func} +The method shall free the key and value, if defined +in such a way that they can be freed. It is guaranteed +that neither @code{entry} or @code{entry->key} are +@code{NULL}. + +@item @code{hash_list_key_hash_func} [(@code{const KEY_T key}) @arrow{} @code{size_t}] +@tpindex @code{hash_list_key_hash_func} +The method shall return the hash of the @code{key}. +It is guaranteed that @code{key} is not @code{NULL}. +@end table + +There are five methods specific to @code{hash_list_t}. +The @code{this}-parameter's data type for this methods +are @code{hash_list_t*} with the @code{restrict} modifier. + +@table @asis +@item @code{hash_list_create} [(@code{this, size_t capacity}) @arrow{} @code{int}] +@fnindex @code{hash_list_create} +Create a hash list, and store it in @code{this}. +The hash list's initial capacity will be at least the value @code{capacity}. +If, however, @code{capacity} is zero, a default capacity will be used. +Zero is returned on success, @code{-1} is returned on error. + +@item @code{hash_list_pack} [(@code{this}) @arrow{} @code{int}] +@fnindex @code{hash_list_pack} +Pack the list so that there are no reusable positions, and +reduce the capacity to the smallest capacity that can be used. +This method has linear time complexity and constant memory +complexity. Zero is returned on success, @code{-1} is returned +on error. Errors are however non-fatal and can be ignored, +it only means that the capacity could not be reduces, because +a called to @code{realloc} failed. + +@item @code{hash_list_get} [(@code{const this, const KEY_T key, VALUE_T* restrict value}) @arrow{} @code{int}] +@fnindex @code{hash_list_get} +Look up a value, with the key @code{key}, in the hash list +@code{this}. The found value will be stored in @code{*value}. +This method cannot fail, therefore it cannot return a value +indicating that it failed. Instead it returns one if the +entry was found and nought if it was not found. + +@item @code{hash_list_put} [(@code{this, KEY_T key, const VALUE_T* restrict value}) @arrow{} @code{int}] +@fnindex @code{hash_list_put} +Store the value stored in @code{*value} to the hash list +@code{this}. The value will be stored with the key @code{key}. +If a value with this key already exists, that entry will +be freed and replaced. @code{key} will be stored in the +hash list, and the caller is not longer responsble for freeing +it unless the call to this function fails. Zero is returned +on success, @code{-1} is returned on error. + +If however @code{value} is @code{NULL}, the entry with the +key @code{key} will be removed if it exists. And zero is +always returned. The caller will be responsible for freeing +@code{key} in this case. + +@item @code{hash_list_remove} [(@code{this, const KEY_T key}) @arrow{} @code{void}] +@fnindex @code{hash_list_remove} +Calling this function is equivalent to calling +@code{hash_list_put} with the last argument being @code{NULL}. +However, it allows the key to be stored with @code{const} and +it does not have a return value. +@end table + +Keep in mind that the methods +@itemize @bullet{} +@item @code{hash_list_destroy} +@item @code{hash_list_clone} +@item @code{hash_list_marshal_size} +@item @code{hash_list_marshal} +@item @code{hash_list_unmarshal} +@end itemize +also have @code{hash_list} exchanged with whatever +is in the first argument of the on the call to +@code{CREATE_HASH_LIST_SUBCLASS}. +Additionally @code{hash_list_clone} cannot clone +keys or values that are pointers. So if freeing +method is set, you need to manually clone keys +and values after calling @code{hash_list_clone}. + +@code{CREATE_HASH_LIST_SUBCLASS} also defines the +prototypes for four functions the user of the class +is required to implement. This four functions are +defined with @code{static inline}. The @code{entry} +parameter is defined with the type +@code{hash_list_entry_t*}@footnote{Keep in mind +that @code{hash_list} is replaced with the value +of the first argument in @code{CREATE_HASH_LIST_SUBCLASS}}. + +@table @asis +@item @code{hash_list_key_comparer} [(@code{const KEY_T key_a, const KEY_T key_b}) @arrow{} @code{int}] +@fnindex @code{hash_list_key_comparer} +Compare two keys, @code{key_a} and @code{key_b}. The +function shall return zero on inequality and non-zero +on equality. + +@item @code{hash_list_submarshal_size} [(@code{const entry}) @arrow{} @code{size_t}] +@fnindex @code{hash_list_submarshal_size} +The function shall return the number of bytes required +to marshal @code{entry->key} and @code{entry->value}. + +@item @code{hash_list_submarshal} [(@code{const entry, char* restrict data}) @arrow{} @code{size_t}] +@fnindex @code{hash_list_submarshal} +The function shall marshal @code{entry->key} and +@code{entry->value} into the buffer @code{data}. +The function shall then return the number of +written bytes, that is, the value returned by +@code{hash_list_submarshal_size}. + +@item @code{hash_list_subunmarshal} [(@code{entry, char* restrict data}) @arrow{} @code{size_t}] +@fnindex @code{hash_list_subunmarshal} +The function shall unmarshal the key and value +of an entry stored in the beginning of @code{data}. +The unmarshaled key and value should be stored +to @code{entry->key} and @code{entry->value}, +respectively. The function shall then return the +number of read bytes, that is, the value +@code{hash_list_submarshal_size} returned when +the marshal took place, or equivalently, the +will it would return after the unmarshalling. +The function shall return zero on error. +@end table + +@file{<libmdsserver/hash-list.h>} also defines a +macro that is uneffected by @code{CREATE_HASH_LIST_SUBCLASS}. + +@table @asis +@item @code{foreach_hash_list_entry} [(@code{hash_list_t this, size_t i, hash_list_entry_t* entry})] +This marcro is a warpper for the @code{for}-keyword. +It iterates over entry element in the hash list @code{this}. +On each iteration, the entry (used slots) will be stored +to the variable @code{entry}. The variable @code{i} defined +as a @code{size_t} must be available for the macro to use +freely. + +@ifset AFOURPAPER_OR_USLETTER_OR_SMALLBOOK_WITH_SMALLFONT +@example +void print_hash_list(hash_list_t* table) +@{ + hash_list_entry_t* entry; + size_t i; + foreach_hash_table_entry (*table, i, entry) + printf("%zu --> %zu\n", entry->key, entry->value); +@} +@end example +@end ifset +@ifclear AFOURPAPER_OR_USLETTER_OR_SMALLBOOK_WITH_SMALLFONT +@example +void print_hash_list(hash_list_t* table) +@{ + hash_list_entry_t* entry; + size_t i; + foreach_hash_lsit_entry (*table, i, entry) + printf("%zu --> %zu\n", entry->key, + entry->value); +@} +@end example +@end ifclear + +Note thay the data type for the parameter @code{this} +is not a pointer. +@end table + + + @node Message Structure @subsection Message Structure @@ -7517,9 +7820,9 @@ The length of the message's payload. This value will be the same as the value of the @code{Length}-header. @end table -There are six functions specific to +There are six methods specific to @code{mds_message_t}. The @code{this}-parameter's -data type for this functions are @code{mds_message_t*} +data type for this methods are @code{mds_message_t*} with the @code{restrict} modifier. @table @asis @@ -7532,7 +7835,7 @@ using @code{mds_message_destroy}. @item @code{mds_message_zero_initialise} [(@code{this}) @arrow{} @code{void}] @fnindex @code{mds_message_zero_initialise} -This function is similar to +This method is similar to @code{mds_message_initialise}, however it cannot fail and thus have no return value. The difference it is action is that it will not allocate an internal @@ -7558,13 +7861,13 @@ be recovered from. @item @code{mds_message_compose_size} [(@code{const this}) @arrow{} @code{size_t}] @fnindex @code{mds_message_compose_size} -This function is to @code{mds_message_compose} as +This method is to @code{mds_message_compose} as @code{mds_message_marshal_size} is to @code{mds_message_marshal}. @item @code{mds_message_compose} [(@code{const this, char* restrict data}) @arrow{} @code{void}] @fnindex @code{mds_message_compose} -This function is similar to +This method is similar to @code{mds_message_marshal}. The only difference is that it will not store internal data and instead create a message that can be broadcasted in the @@ -10835,7 +11138,7 @@ It is typically rendered as a thick plus-sign. @cpindex Tables, resize @cpindex Columns, resize @cpindex Resize table columns -This cursor is used to indicate the the cursor is +This cursor is used to indicate that the cursor is within a region that allows it rat to be used to resize a column. @@ -10880,7 +11183,7 @@ horizontally towards it. @cpindex Tables, resize @cpindex Rows, resize @cpindex Resize table rows -This cursor is used to indicate the the cursor is +This cursor is used to indicate that the cursor is within a region that allows it rat to be used to resize a column. @@ -11876,7 +12179,7 @@ own. Any server, or even client, running in this display will effectively be running in all of the displays connected to the metadisplay. -The idea of the the metadisplay server came from the +The idea of the metadisplay server came from the idea of letting the user have the clipboard shared across any number of @emph{selected} display servers. Rather than having a clipboard server written diff --git a/src/libmdsserver/hash-list.h b/src/libmdsserver/hash-list.h index 1cc2b2e..dfc4489 100644 --- a/src/libmdsserver/hash-list.h +++ b/src/libmdsserver/hash-list.h @@ -19,6 +19,8 @@ #define MDS_LIBMDSSERVER_HASH_LIST_H +#include "macros.h" + #include <stddef.h> #include <stdint.h> #include <stdlib.h> @@ -46,16 +48,24 @@ /** * Create a subclass of hash_list * - * @param T The replacement text for `hash_list` - * @param KEY_T The data type of the keys - * @param CKEY_T `const` version of `KEY_T` - * @param VALUE_T The data type of the values - * @param COMPARER Subclass specific key comparer - * @param SUBMARSHAL_MEASURER Subclass specific marshal-size calculation helper - * @param SUBMARSHALLER Subclass specific marshal helper - * @param SUBUNMARSHALLER Subclass specific unmarshal helper + * @param T The replacement text for `hash_list` + * @param KEY_T The datatype of the keys + * @param CKEY_T `const` version of `KEY_T` + * @param VALUE_T The datatype of the values */ -#define CREATE_HASH_LIST_SUBCLASS(T, KEY_T, CKEY_T, VALUE_T, COMPARER, SUBMARSHAL_MEASURER, SUBMARSHALLER, SUBUNMARSHALLER)\ +#define CREATE_HASH_LIST_SUBCLASS(T, KEY_T, CKEY_T, VALUE_T)\ +\ +\ +/** + * Slot for a value in a hash list + */\ +struct T##_entry;\ +\ +/** + * Slot for a value in a hash list + */\ +struct T;\ +\ \ \ /** @@ -63,55 +73,55 @@ */\ typedef VALUE_T T##_value_t;\ \ -\ /** * Function-type for the function responsible for freeing the key and value of an entry * * @param entry The entry, will never be `NULL`, any only used entries will be passed */\ -typedef void T##_entry_free_func(T##_entry_t* entry);\ +typedef void T##_entry_free_func(struct T##_entry* entry);\ \ /** - * Function-type for the function responsible for comparing keys + * Function-type for the function responsible for hashing keys * - * The datatype for `COMPARER` + * @param key The key, will never be `NULL` + * @return The hash of the key + */\ +typedef size_t T##_key_hash_func(CKEY_T key);\ +\ +\ +\ +/** + * Comparing keys * * @param key_a The first key, will never be `NULL` * @param key_b The second key, will never be `NULL` * @return Whether the keys are equal */\ -typedef int T##_key_compare_func(CKEY_T key_a, CKEY_T key_a);\ +static inline int T##_key_comparer(CKEY_T key_a, CKEY_T key_b);\ \ /** - * Function-type for the function responsible for determining - * the marshal-size of an entry's key and value - * - * The datatype for `SUBMARSHAL_MEASURER` + * Determine the marshal-size of an entry's key and value * * @param entry The entry, will never be `NULL`, any only used entries will be passed * @return The marshal-size of the entry's key and value */\ -typedef size_t T##_entry_marshal_size_func(const T##_entry_t* entry);\ +static inline size_t T##_submarshal_size(const struct T##_entry* entry);\ \ /** - * Function-type for the function responsible for marshalling of an entry's key and value - * - * The datatype for `SUBMARSHALLER` + * Marshal an entry's key and value * * @param entry The entry, will never be `NULL`, any only used entries will be passed * @return The marshal-size of the entry's key and value */\ -typedef size_t T##_entry_marshal_func(const T##_entry_t* entry, char* restrict data);\ +static inline size_t T##_submarshal(const struct T##_entry* entry, char* restrict data);\ \ /** - * Function-type for the function responsible for unmarshalling of an entry's key and value - * - * The datatype for `SUBUNMARSHALLER` + * Unmarshal an entry's key and value * * @param entry The entry, will never be `NULL`, any only used entries will be passed * @return The number of read bytes, zero on error */\ -typedef size_t T##_entry_unmarshal_func(T##_entry_t* entry, char* restrict data);\ +static inline size_t T##_subunmarshal(struct T##_entry* entry, char* restrict data);\ \ \ \ @@ -139,8 +149,8 @@ typedef struct T##_entry\ \ \ /** - * Slot for a value in a hash list - */ + * The data structure of the hash list + */\ typedef struct T\ {\ /** @@ -168,14 +178,14 @@ typedef struct T\ /** * Function used to free keys and values of entries * - * The freeing is used if this fucntion pointer is `NULL` + * The freeing is not used if this function pointer is `NULL` * * Be aware, this variable cannot be marshalled */\ T##_entry_free_func* freer;\ \ /** - * Calculate the hash of a key + * Function used to calculate the hash of a key * * If this function pointer is `NULL`, the identity hash is used * @@ -211,6 +221,7 @@ T##_create(T##_t* restrict this, size_t capacity)\ return -1;\ \ this->allocated = capacity;\ + return 0;\ }\ \ \ @@ -302,18 +313,44 @@ T##_pack(T##_t* restrict this)\ * @return Whether the key was found, error is impossible */\ static inline int __attribute__((unused))\ -T##_get(T##_t* restrict this, CKEY_T key, T##_value_t* value)\ +T##_get(const T##_t* restrict this, CKEY_T key, T##_value_t* restrict value)\ {\ size_t i, n, hash = HASH_LIST_HASH(key);\ for (i = 0, n = this->used; i < n; i++)\ if ((this->slots[i].key_hash == hash) && this->slots[i].key)\ - if (COMPARER(this->slots[i].key, key))\ + if (T##_key_comparer(this->slots[i].key, key))\ return *value = this->slots[i].value, 1;\ return 0;\ }\ \ \ /** + * Remove an entry from a hash list + * + * @param this The hash list + * @param key The key of the entry to remove, must not be `NULL` + */\ +static inline void __attribute__((unused))\ +T##_remove(T##_t* restrict this, CKEY_T key)\ +{\ + size_t i, n, hash = HASH_LIST_HASH(key);\ + T##_entry_t* slots = this->slots;\ + for (i = 0, n = this->used; i < n; i++)\ + if ((slots[i].key_hash == hash) && (slots[i].key != NULL))\ + if (T##_key_comparer(slots[i].key, key))\ + {\ + if (this->freer != NULL)\ + this->freer(slots + i);\ + slots[i].key = NULL;\ + this->unused++;\ + if ((this->unused >> 1) >= this->used)\ + T##_pack(this);\ + return;\ + }\ +}\ +\ +\ +/** * Add an entry to a hash list * * @param this The hash list @@ -323,31 +360,32 @@ T##_get(T##_t* restrict this, CKEY_T key, T##_value_t* value)\ * @return Non-zero on error, `errno` will have been set accordingly */\ static inline int __attribute__((unused))\ -T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* value)\ +T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* restrict value)\ {\ - size_t i, n, empty = this->used, hash = HASH_LIST_HASH(key);\ + size_t i, n, empty, hash;\ T##_entry_t* slots = this->slots;\ + \ + /* Remove entry if no value is passed */\ + if (value == NULL)\ + {\ + T##_remove(this, key);\ + return 0;\ + }\ + \ + /* Find an unused slot or the current slot */\ + empty = this->used, hash = HASH_LIST_HASH(key);\ for (i = 0, n = this->used; i < n; i++)\ if (slots[i].key == NULL)\ empty = i;\ else if (slots[i].key_hash == hash)\ - if (COMPARER(slots[i].key, key))\ + if (T##_key_comparer(slots[i].key, key))\ {\ if (this->freer != NULL)\ this->freer(slots + i);\ - if (value == NULL)\ - {\ - slots[i].key = NULL;\ - this->unused++;\ - if (this->unused >= this->used)\ - T##_pack(this);\ - return 0;\ - }\ - else\ - goto put;\ + goto put;\ }\ - if (value == NULL)\ - return 0;\ + \ + /* Grow slot allocation is required */\ if (empty == this->allocated)\ {\ if (empty >= SIZE_MAX >> 1)\ @@ -358,6 +396,8 @@ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* value)\ this->slots = slots;\ this->allocated <<= 1;\ }\ + \ + /* Store entry */\ i = empty;\ put:\ slots[i].key = key;\ @@ -368,19 +408,6 @@ T##_put(T##_t* restrict this, KEY_T key, const T##_value_t* value)\ \ \ /** - * Remove an entry from a hash list - * - * @param this The hash list - * @param key The key of the entry to remove, must not be `NULL` - */\ -static inline void __attribute__((unused))\ -T##_remove(T##_t* restrict this, CKEY_T key)\ -{\ - T##_put(this, key, NULL);\ -}\ -\ -\ -/** * Calculate the buffer size need to marshal a hash list * * @param this The hash table @@ -393,7 +420,7 @@ T##_marshal_size(const T##_t* restrict this)\ size_t rc = sizeof(int) + 3 * sizeof(size_t);\ for (i = 0; i < n; i++)\ if (this->slots[i].key != NULL)\ - rc += SUBMARSHAL_MEASURER(this->slots + i);\ + rc += T##_submarshal_size(this->slots + i);\ return rc + n * sizeof(char) + (n - this->unused) * sizeof(size_t);\ }\ \ @@ -406,7 +433,7 @@ T##_marshal_size(const T##_t* restrict this)\ */\ static inline void __attribute__((unused))\ T##_marshal(const T##_t* restrict this, char* restrict data)\ -{ +{\ size_t wrote, i, n = this->used;\ \ buf_set_next(data, int, HASH_LIST_T_VERSION);\ @@ -419,7 +446,7 @@ T##_marshal(const T##_t* restrict this, char* restrict data)\ {\ buf_set_next(data, char, 1);\ buf_set_next(data, size_t, this->slots[i].key_hash);\ - wrote = SUBMARSHALLER(this->slots + i, data);\ + wrote = T##_submarshal(this->slots + i, data);\ data += wrote / sizeof(char);\ }\ else\ @@ -441,6 +468,9 @@ T##_unmarshal(T##_t* restrict this, char* restrict data)\ size_t i, n, got;\ char used;\ \ + this->freer = NULL;\ + this->hasher = NULL;\ + \ /* buf_get(data, int, 0, HASH_LIST_T_VERSION); */\ buf_next(data, int, 1);\ \ @@ -458,7 +488,7 @@ T##_unmarshal(T##_t* restrict this, char* restrict data)\ if (used == 0)\ continue;\ buf_set_next(data, size_t, this->slots[i].key_hash);\ - got = SUBUNMARSHALLER(this->slots + i, data);\ + got = T##_subunmarshal(this->slots + i, data);\ if (got == 0)\ return -1;\ data += got / sizeof(char);\ diff --git a/src/mds-colour.c b/src/mds-colour.c index 2f3e357..2bee831 100644 --- a/src/mds-colour.c +++ b/src/mds-colour.c @@ -22,7 +22,7 @@ #include <libmdsserver/macros.h> #include <libmdsserver/util.h> #include <libmdsserver/mds-message.h> -#include <libmdsserver/hash-table.h> +#include <libmdsserver/hash-list.h> #include <libmdsserver/hash-help.h> #include <errno.h> @@ -84,7 +84,7 @@ static size_t send_buffer_size = 0; /** * List of all colours */ -static colour_slot_t* colour_list = NULL; +static colour_list_t colours; @@ -130,14 +130,15 @@ int initialise_server(void) "Command: set-colour\n"; fail_if (full_send(message, strlen(message))); - fail_if (server_initialised() < 0); stage++; + fail_if (server_initialised() < 0); stage++;; + fail_if (colour_list_create(&colours, 64) < 0); stage++; fail_if (mds_message_initialise(&received)); return 0; fail: xperror(*argv); - if (stage >= 1) - mds_message_destroy(&received); + if (stage >= 2) colour_list_destroy(&colours); + if (stage >= 1) mds_message_destroy(&received); return 1; } @@ -150,6 +151,9 @@ int initialise_server(void) */ int postinitialise_server(void) { + colours.freer = colour_list_entry_free; + colours.hasher = string_hash; + if (connected) return 0; @@ -251,7 +255,7 @@ int master_loop(void) danger = 0; free(send_buffer), send_buffer = NULL; send_buffer_size = 0; - colour_list_pack(&colour_list); + colour_list_pack(&colours); } if (r = mds_message_read(&received, socket_fd), r == 0) @@ -479,3 +483,76 @@ void received_info(int signo) iprintf("send buffer size: %zu bytes", send_buffer_size); } + +/** + * Comparing keys + * + * @param key_a The first key, will never be `NULL` + * @param key_b The second key, will never be `NULL` + * @return Whether the keys are equal + */ +static inline int colour_list_key_comparer(const char* key_a, const char* key_b) +{ + return !strcmp(key_a, key_b); +} + + +/** + * Determine the marshal-size of an entry's key and value + * + * @param entry The entry, will never be `NULL`, any only used entries will be passed + * @return The marshal-size of the entry's key and value + */ +static inline size_t colour_list_submarshal_size(const colour_list_entry_t* entry) +{ + return sizeof(colour_t) + (strlen(entry->key) + 1) * sizeof(char); +} + + +/** + * Marshal an entry's key and value + * + * @param entry The entry, will never be `NULL`, any only used entries will be passed + * @return The marshal-size of the entry's key and value + */ +static inline size_t colour_list_submarshal(const colour_list_entry_t* entry, char* restrict data) +{ + size_t n = (strlen(entry->key) + 1) * sizeof(char); + memcpy(data, &(entry->value), sizeof(colour_t)); + data += sizeof(colour_t) / sizeof(char); + memcpy(data, entry->key, n); + return sizeof(colour_t) + n; +} + + +/** + * Unmarshal an entry's key and value + * + * @param entry The entry, will never be `NULL`, any only used entries will be passed + * @return The number of read bytes, zero on error + */ +static inline size_t colour_list_subunmarshal(colour_list_entry_t* entry, char* restrict data) +{ + size_t n = 0; + memcpy(&(entry->value), data, sizeof(colour_t)); + data += sizeof(colour_t) / sizeof(char); + while (data[n++]); + n *= sizeof(char); + entry->key = malloc(n); + if (entry->key == NULL) + return 0; + memcpy(entry->key, data, n); + return sizeof(colour_t) + n; +} + + +/** + * Free the key and value of an entry in a colour list + * + * @param entry The entry + */ +void colour_list_entry_free(colour_list_entry_t* entry) +{ + free(entry->key); +} + diff --git a/src/mds-colour.h b/src/mds-colour.h index 49b07ec..c833c53 100644 --- a/src/mds-colour.h +++ b/src/mds-colour.h @@ -21,6 +21,8 @@ #include "mds-base.h" +#include <libmdsserver/hash-list.h> + #include <stdint.h> @@ -54,41 +56,6 @@ typedef struct colour } colour_t; -/** - * Slot for a colour in a list of colours - */ -typedef struct colour_slot -{ - /** - * The name of the colour, `NULL` if the slot is unused - */ - char* name; - - /** - * The index of the next unused slot, - * only used on unused slot - */ - size_t next_unused; - - /** - * The index of the previous unused slot, - * only used on unused slot - */ - size_t prev_unused; - - /** - * The hash of `name` - */ - size_t name_hash; - - /** - * The value of the colour - */ - colour_t colour; - -} colour_slot_t; - - /** * Handle the received message @@ -136,5 +103,16 @@ int handle_set_colour(const char* recv_name, const char* recv_remove, const char const char* recv_red, const char* recv_green, const char* recv_blue); +CREATE_HASH_LIST_SUBCLASS(colour_list, char* restrict, const char* restrict, colour_t) + + +/** + * Free the key and value of an entry in a colour list + * + * @param entry The entry + */ +void colour_list_entry_free(colour_list_entry_t* entry); + + #endif |