diff options
Diffstat (limited to '')
| -rw-r--r-- | src/libmdsserver/hash-list.h | 160 |
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);\ |