diff options
| -rw-r--r-- | src/libmdsserver/hash-help.h | 2 | ||||
| -rw-r--r-- | src/libmdsserver/hash-list.h | 484 | ||||
| -rw-r--r-- | src/libmdsserver/linked-list.c | 2 | ||||
| -rw-r--r-- | src/mds-colour.c | 27 | ||||
| -rw-r--r-- | src/mds-colour.h | 71 |
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` |