m + info: hash list

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

1 files changed, 95 insertions, 65 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);\