m + info: hash list

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

3 files changed, 191 insertions, 106 deletions

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