work on mds-colour and list alternative to hash table

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

5 files changed, 574 insertions, 12 deletions

diff --git a/src/libmdsserver/hash-help.h b/src/libmdsserver/hash-help.h
index 8410370..2216434 100644
--- a/src/libmdsserver/hash-help.h
+++ b/src/libmdsserver/hash-help.h
@@ -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*`:s are of equal value
  * 
  * @param   str_a  The first string
  * @param   str_b  The second string
diff --git a/src/libmdsserver/hash-list.h b/src/libmdsserver/hash-list.h
new file mode 100644
index 0000000..1cc2b2e
--- /dev/null
+++ b/src/libmdsserver/hash-list.h
@@ -0,0 +1,484 @@
+/**
+ * mds — A micro-display server
+ * Copyright © 2014, 2015  Mattias Andrée (maandree@member.fsf.org)
+ * 
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ * 
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with this program.  If not, see <http://www.gnu.org/licenses/>.
+ */
+#ifndef MDS_LIBMDSSERVER_HASH_LIST_H
+#define MDS_LIBMDSSERVER_HASH_LIST_H
+
+
+#include <stddef.h>
+#include <stdint.h>
+#include <stdlib.h>
+#include <string.h>
+#include <errno.h>
+
+
+
+
+/**
+ * The default initial capacity
+ */
+#ifndef HASH_LIST_DEFAULT_INITIAL_CAPACITY
+# define HASH_LIST_DEFAULT_INITIAL_CAPACITY  128
+#endif
+
+
+#define HASH_LIST_HASH(key)  (this->hasher != NULL ? this->hasher(key) : (size_t)key)
+
+
+
+#define HASH_LIST_T_VERSION  0
+
+
+/**
+ * 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
+ */
+#define CREATE_HASH_LIST_SUBCLASS(T, KEY_T, CKEY_T, VALUE_T, COMPARER, SUBMARSHAL_MEASURER, SUBMARSHALLER, SUBUNMARSHALLER)\
+\
+\
+/**
+ * The datatype of the value
+ */\
+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);\
+\
+/**
+ * Function-type for the function responsible for comparing keys
+ * 
+ * The datatype for `COMPARER`
+ * 
+ * @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);\
+\
+/**
+ * Function-type for the function responsible for determining
+ * the marshal-size of an entry's key and value
+ * 
+ * The datatype for `SUBMARSHAL_MEASURER`
+ * 
+ * @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);\
+\
+/**
+ * Function-type for the function responsible for marshalling of an entry's key and value
+ * 
+ * The datatype for `SUBMARSHALLER`
+ * 
+ * @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);\
+\
+/**
+ * Function-type for the function responsible for unmarshalling of an entry's key and value
+ * 
+ * The datatype for `SUBUNMARSHALLER`
+ * 
+ * @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);\
+\
+\
+\
+/**
+ * Slot for a value in a hash list
+ */\
+typedef struct T##_entry\
+{\
+  /**
+   * The key of the entry, `NULL` if the slot is unused
+   */\
+  KEY_T key;\
+  \
+  /**
+   * Hash of `key`, undefined but initialised if the slot is unused
+   */\
+  size_t key_hash;\
+  \
+  /**
+   * The value of the entry
+   */\
+  T##_value_t value;\
+  \
+} T##_entry_t;\
+\
+\
+/**
+ * Slot for a value in a hash list
+ */
+typedef struct T\
+{\
+  /**
+   * The number of allocated slots
+   */\
+  size_t allocated;\
+  \
+  /**
+   * The number of unused slot that
+   * has previously be used
+   */\
+  size_t unused;\
+  \
+  /**
+   * The number of slots that have
+   * been used, even if no longer used
+   */\
+  size_t used;\
+  \
+  /**
+   * The slots
+   */\
+  T##_entry_t* slots;\
+  \
+  /**
+   * Function used to free keys and values of entries
+   * 
+   * The freeing is used if this fucntion pointer is `NULL`
+   * 
+   * Be aware, this variable cannot be marshalled
+   */\
+  T##_entry_free_func* freer;\
+  \
+  /**
+   * Calculate the hash of a key
+   * 
+   * If this function pointer is `NULL`, the identity hash is used
+   * 
+   * Be aware, this variable cannot be marshalled
+   */\
+  T##_key_hash_func* hasher;\
+  \
+} T##_t;\
+\
+\
+\
+/**
+ * Create a hash list
+ * 
+ * @param   this      Memory slot in which to store the new hash list
+ * @param   capacity  The minimum initial capacity of the hash list, 0 for default
+ * @return            Non-zero on error, `errno` will have been set accordingly
+ */\
+static inline int __attribute__((unused))\
+T##_create(T##_t* restrict this, size_t capacity)\
+{\
+  if (capacity == 0)\
+    capacity = HASH_LIST_DEFAULT_INITIAL_CAPACITY;\
+  \
+  this->freer = NULL;\
+  this->hasher = NULL;\
+  this->allocated = 0;\
+  this->unused = 0;\
+  this->used = 0;\
+  \
+  this->slots = malloc(capacity * sizeof(T##_t));\
+  if (this->slots == NULL)\
+    return -1;\
+  \
+  this->allocated = capacity;\
+}\
+\
+\
+/**
+ * Release all resources in a hash list
+ * 
+ * @param  this  The hash list
+ */\
+static inline void __attribute__((unused))\
+T##_destroy(T##_t* restrict this)\
+{\
+  size_t i, n;\
+  if (this->freer != NULL)\
+    for (i = 0, n = this->used; i < n; i++)\
+      if (this->slots[i].key)\
+	this->freer(this->slots + i);\
+  this->used = 0;\
+  this->unused = 0;\
+  this->allocated = 0;\
+  free(this->slots);\
+  this->slots = NULL;\
+}\
+\
+\
+/**
+ * Clone a hash list
+ * 
+ * @param   this  The hash list to clone
+ * @param   out   Memory slot in which to store the new hash list
+ * @return        Non-zero on error, `errno` will have been set accordingly
+ */\
+static inline int __attribute__((unused))\
+T##_clone(const T##_t* restrict this, T##_t* restrict out)\
+{\
+  if (T##_create(out, this->allocated) < 0)\
+    return -1;\
+  out->used = this->used;\
+  out->unused = this->unused;\
+  memcpy(out->slots, this->slots, this->used * sizeof(T##_entry_t));\
+}\
+\
+\
+/**
+ * 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.
+ * 
+ * @param   this  The list
+ * @return        Non-zero on error, `errno` will have
+ *                been set accordingly. Errors are non-fatal.
+ */\
+static inline int __attribute__((unused))\
+T##_pack(T##_t* restrict this)\
+{\
+  size_t i, j, n;\
+  T##_entry_t* slots = this->slots;\
+  \
+  if (this->unused > 0)\
+    {\
+      for (i = 0, j = 0, n = this->used; i < n; i++)\
+	if (slots[i].key != NULL)\
+	  slots[j++] = slots[i];\
+      \
+      this->used -= this->unused;\
+      this->unused = 0;\
+    }\
+  \
+  if (this->used < this->allocated)\
+    {\
+      slots = realloc(slots, this->used * sizeof(T##_entry_t));\
+      if (slots == NULL)\
+	return -1;\
+      this->slots = slots;\
+      this->allocated = this->used;\
+    }\
+  \
+  return 0;\
+}\
+\
+\
+/**
+ * Look up a value in a hash list
+ * 
+ * @param   this   The hash list
+ * @param   key    The key associated with the value, must not be `NULL`
+ * @param   value  Output parameter for the value
+ * @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)\
+{\
+  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))\
+	return *value = this->slots[i].value, 1;\
+  return 0;\
+}\
+\
+\
+/**
+ * Add an entry to a hash list
+ * 
+ * @param   this   The hash list
+ * @param   key    The key of the entry to add, must not be `NULL`
+ * @param   value  Pointer to the value of the entry to add,
+ *                 `NULL` if the entry should be removed instead
+ * @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)\
+{\
+  size_t i, n, empty = this->used, hash = HASH_LIST_HASH(key);\
+  T##_entry_t* slots = this->slots;\
+  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 (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;\
+	}\
+  if (value == NULL)\
+    return 0;\
+  if (empty == this->allocated)\
+    {\
+      if (empty >= SIZE_MAX >> 1)\
+	return errno = ENOMEM, -1;\
+      slots = realloc(slots, (empty << 1) * sizeof(T##_entry_t));\
+      if (slots == NULL)\
+	return -1;\
+      this->slots = slots;\
+      this->allocated <<= 1;\
+    }\
+  i = empty;\
+ put:\
+  slots[i].key = key;\
+  slots[i].key_hash = hash;\
+  slots[i].value = *value;\
+  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)\
+{\
+  T##_put(this, key, NULL);\
+}\
+\
+\
+/**
+ * Calculate the buffer size need to marshal a hash list
+ * 
+ * @param   this  The hash table
+ * @return        The number of bytes to allocate to the output buffer
+ */\
+static inline size_t __attribute__((unused))\
+T##_marshal_size(const T##_t* restrict this)\
+{\
+  size_t i, n = this->used;\
+  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);\
+  return rc + n * sizeof(char) + (n - this->unused) * sizeof(size_t);\
+}\
+\
+\
+/**
+ * Marshals a hash list
+ * 
+ * @param  this  The hash list
+ * @param  data  Output buffer for the marshalled data
+ */\
+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);\
+  buf_set_next(data, size_t, this->allocated);\
+  buf_set_next(data, size_t, this->unused);\
+  buf_set_next(data, size_t, this->used);\
+  \
+  for (i = 0; i < n; i++)\
+    if (this->slots[i].key != NULL)\
+      {\
+	buf_set_next(data, char, 1);\
+	buf_set_next(data, size_t, this->slots[i].key_hash);\
+	wrote = SUBMARSHALLER(this->slots + i, data);\
+	data += wrote / sizeof(char);\
+      }\
+    else\
+      buf_set_next(data, char, 0);\
+}\
+\
+\
+/**
+ * Unmarshals a hash list
+ * 
+ * @param   this      Memory slot in which to store the new hash list
+ * @param   data      In buffer with the marshalled data
+ * @return            Non-zero on error, `errno` will be set accordingly.
+ *                    Destroy the table on error.
+ */\
+static inline int __attribute__((unused))\
+T##_unmarshal(T##_t* restrict this, char* restrict data)\
+{\
+  size_t i, n, got;\
+  char used;\
+  \
+  /* buf_get(data, int, 0, HASH_LIST_T_VERSION); */\
+  buf_next(data, int, 1);\
+  \
+  buf_get_next(data, size_t, this->allocated);\
+  buf_get_next(data, size_t, this->unused);\
+  buf_get_next(data, size_t, this->used);\
+  \
+  this->slots = calloc(this->allocated, sizeof(T##_entry_t));\
+  if (this->slots == NULL)\
+    return -1;\
+  \
+  for (i = 0, n = this->used; i < n; i++)\
+    {\
+      buf_get_next(data, char, used);\
+      if (used == 0)\
+	continue;\
+      buf_set_next(data, size_t, this->slots[i].key_hash);\
+      got = SUBUNMARSHALLER(this->slots + i, data);\
+      if (got == 0)\
+	return -1;\
+      data += got / sizeof(char);\
+    }\
+  \
+  return 0;\
+}
+
+
+/**
+ * Wrapper for `for` keyword that iterates over entry element in a hash list
+ * 
+ * @param  this:hash_list_t         The hash lsit
+ * @param  i:size_t                 The variable to store the buckey index in at each iteration
+ * @param  entry:hash_list_enty_t*  The variable to store the entry in at each iteration
+ */
+#define foreach_hash_list_entry(this, i, entry)	\
+  for (i = 0; i < (this).used; i++)		\
+    if (entry = (this).slots, entry->keys != NULL)
+
+
+#endif
+
diff --git a/src/libmdsserver/linked-list.c b/src/libmdsserver/linked-list.c
index 07d604c..f94ea50 100644
--- a/src/libmdsserver/linked-list.c
+++ b/src/libmdsserver/linked-list.c
@@ -27,7 +27,7 @@
  * The default initial capacity
  */
 #ifndef LINKED_LIST_DEFAULT_INITIAL_CAPACITY
-#define LINKED_LIST_DEFAULT_INITIAL_CAPACITY  128
+# define LINKED_LIST_DEFAULT_INITIAL_CAPACITY  128
 #endif
 
 
diff --git a/src/mds-colour.c b/src/mds-colour.c
index bdc7aad..2f3e357 100644
--- a/src/mds-colour.c
+++ b/src/mds-colour.c
@@ -22,6 +22,8 @@
 #include <libmdsserver/macros.h>
 #include <libmdsserver/util.h>
 #include <libmdsserver/mds-message.h>
+#include <libmdsserver/hash-table.h>
+#include <libmdsserver/hash-help.h>
 
 #include <errno.h>
 #include <inttypes.h>
@@ -79,6 +81,11 @@ static char* send_buffer = NULL;
  */
 static size_t send_buffer_size = 0;
 
+/**
+ * List of all colours
+ */
+static colour_slot_t* colour_list = NULL;
+
 
 
 /**
@@ -129,7 +136,7 @@ int initialise_server(void)
   return 0;
  fail:
   xperror(*argv);
-  if (stage == 1)
+  if (stage >= 1)
     mds_message_destroy(&received);
   return 1;
 }
@@ -165,7 +172,9 @@ int postinitialise_server(void)
  */
 size_t marshal_server_size(void)
 {
-  return 2 * sizeof(int) + sizeof(uint32_t) + mds_message_marshal_size(&received);
+  size_t rc = 2 * sizeof(int) + sizeof(uint32_t);
+  rc += mds_message_marshal_size(&received);
+  return rc;
 }
 
 
@@ -180,7 +189,9 @@ int marshal_server(char* state_buf)
   buf_set_next(state_buf, int, MDS_COLOUR_VARS_VERSION);
   buf_set_next(state_buf, int, connected);
   buf_set_next(state_buf, uint32_t, message_id);
+  
   mds_message_marshal(&received, state_buf);
+  state_buf += mds_message_marshal_size(&received) / sizeof(char*);
   
   mds_message_destroy(&received);
   return 0;
@@ -240,6 +251,7 @@ int master_loop(void)
 	  danger = 0;
 	  free(send_buffer), send_buffer = NULL;
 	  send_buffer_size = 0;
+	  colour_list_pack(&colour_list);
 	}
       
       if (r = mds_message_read(&received, socket_fd), r == 0)
@@ -408,8 +420,8 @@ int handle_set_colour(const char* recv_name, const char* recv_remove, const char
 {
   uint64_t limit = UINT64_MAX;
   int remove_colour = 0;
+  colour_t colour;
   int bytes;
-  uint64_t red, green, blue;
   
   if      (recv_remove == NULL)            remove_colour = 0;
   else if (strequals(recv_remove, "yes"))  remove_colour = 1;
@@ -433,14 +445,15 @@ int handle_set_colour(const char* recv_name, const char* recv_remove, const char
       if (bytes < 8)
 	limit = (((uint64_t)1) << (bytes * 8)) - 1;
       
-      if (strict_atou64(recv_red, &red, 0, limit))
+      colour.bytes = bytes;
+      if (strict_atou64(recv_red, &(colour.red), 0, limit))
 	return eprint("got an invalid value on the Red-header, ignoring."), 0;
-      if (strict_atou64(recv_green, &green, 0, limit))
+      if (strict_atou64(recv_green, &(colour.green), 0, limit))
 	return eprint("got an invalid value on the Green-header, ignoring."), 0;
-      if (strict_atou64(recv_blue, &blue, 0, limit))
+      if (strict_atou64(recv_blue, &(colour.blue), 0, limit))
 	return eprint("got an invalid value on the Blue-header, ignoring."), 0;
       
-      /* TOOD set colour */
+      /* TODO set colour */
     }
   else
     {
diff --git a/src/mds-colour.h b/src/mds-colour.h
index 7820c76..49b07ec 100644
--- a/src/mds-colour.h
+++ b/src/mds-colour.h
@@ -21,6 +21,74 @@
 
 #include "mds-base.h"
 
+#include <stdint.h>
+
+
+
+/**
+ * Data structure for colour
+ */
+typedef struct colour
+{
+  /**
+   * The value of the red channel
+   */
+  uint64_t red;
+  
+  /**
+   * The value of the green channel
+   */
+  uint64_t green;
+  
+  /**
+   * The value of the blue channel
+   */
+  uint64_t blue;
+  
+  /**
+   * The number of bytes with which
+   * each channel is encoded
+   */
+  int bytes;
+  
+} 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
@@ -29,7 +97,6 @@
  */
 int handle_message(void);
 
-
 /**
  * Handle the received message after it has been
  * identified to contain `Command: list-colours`
@@ -42,7 +109,6 @@ int handle_message(void);
 int handle_list_colours(const char* recv_client_id, const char* recv_message_id,
 			const char* recv_include_values);
 
-
 /**
  * Handle the received message after it has been
  * identified to contain `Command: get-colour`
@@ -54,7 +120,6 @@ int handle_list_colours(const char* recv_client_id, const char* recv_message_id,
  */
 int handle_get_colour(const char* recv_client_id, const char* recv_message_id, const char* recv_name);
 
-
 /**
  * Handle the received message after it has been
  * identified to contain `Command: set-colour`