m + info: hash list

Signed-off-by: Mattias Andrée <maandree@operamail.com>

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