diff options
| -rw-r--r-- | Makefile | 6 | ||||
| -rw-r--r-- | src/libmdsserver/fd-table.c | 317 | ||||
| -rw-r--r-- | src/libmdsserver/fd-table.h | 177 | ||||
| -rw-r--r-- | src/libmdsserver/hash-table.c | 1 | ||||
| -rw-r--r-- | src/libmdsserver/hash-table.h | 37 | ||||
| -rw-r--r-- | src/libmdsserver/table-common.h | 59 | ||||
| -rw-r--r-- | src/mds-server.c | 17 |
7 files changed, 567 insertions, 47 deletions
@@ -60,7 +60,7 @@ C_FLAGS = $(OPTIMISE) $(WARN) -std=$(STD) $(CPPFLAGS) $(CFLAGS) $(LDFLAGS) \ # Object files for the libary -LIBOBJ = linked-list hash-table +LIBOBJ = linked-list hash-table fd-table # Build rules. @@ -73,7 +73,7 @@ bin/%: obj/%.o bin/libmdsserver.so mkdir -p $(shell dirname $@) gcc $(C_FLAGS) -o $@ -Lbin -lmdsserver obj/$*.o -obj/%.o: src/%.c src/%.h src/config.h +obj/%.o: src/%.c src/*.h src/libmdsserver/*.h mkdir -p $(shell dirname $@) gcc $(C_FLAGS) -Isrc -c -o $@ $< @@ -82,7 +82,7 @@ bin/libmdsserver.so: $(foreach O,$(LIBOBJ),obj/libmdsserver/$(O).o) mkdir -p $(shell dirname $@) gcc $(C_FLAGS) -shared -o $@ $^ -obj/libmdsserver/%.o: src/libmdsserver/%.c src/libmdsserver/%.h +obj/libmdsserver/%.o: src/libmdsserver/%.c src/libmdsserver/*.h mkdir -p $(shell dirname $@) gcc $(C_FLAGS) -fPIC -c -o $@ $< diff --git a/src/libmdsserver/fd-table.c b/src/libmdsserver/fd-table.c new file mode 100644 index 0000000..0b11f5d --- /dev/null +++ b/src/libmdsserver/fd-table.c @@ -0,0 +1,317 @@ +/** + * mds — A micro-display server + * Copyright © 2014 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/>. + */ +#include "fd-table.h" + +#include <stdlib.h> +#include <string.h> +#include <errno.h> + + +/** + * Create a fd table + * + * @param this Memory slot in which to store the new fd table + * @param initial_capacity The initial capacity of the table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int fd_table_create_tuned(fd_table_t* restrict this, size_t initial_capacity) +{ + size_t bitcap; + + this->capacity = initial_capacity ? initial_capacity : 1; + this->size = 0; + + this->values = NULL; + this->used = NULL; + this->value_comparator = NULL; + + /* It is important that both allocations are done with calloc: + `this->used` must set all keys as unused at the initial state, + `this->values` must be initialised for marshaling and it helps + the time overhead of `fd_table_contains_value`. */ + + bitcap = (this->capacity + 63) / 64; + this->used = calloc(bitcap, sizeof(size_t)); + if (this->used == NULL) + return 1; + + this->values = calloc(this->capacity, sizeof(size_t)); + if (this->values == NULL) + return 1; + + return 0; +} + + +/** + * Release all resources in a fd table, should + * be done even if construction fails + * + * @param this The fd table + * @param keys_freer Function that frees a key, `NULL` if keys should not be freed + * @param values_freer Function that frees a value, `NULL` if value should not be freed + */ +void fd_table_destroy(fd_table_t* restrict this, free_func* key_freer, free_func* value_freer) +{ + if (((key_freer == NULL) && (value_freer == NULL)) || (this->used == NULL)) + { + if (this->values != NULL) + free(this->values); + + if (this->used != NULL) + free(this->used); + } + else + { + if (this->values != NULL) + { + size_t i; + for (i = 0; i < this->capacity; i++) + if (this->used[i / 64] & ((uint64_t)1 << (i % 64))) + { + if (key_freer != NULL) + key_freer(i); + if (value_freer != NULL) + value_freer(this->values[i]); + } + free(this->values); + } + free(this->used); + } +} + + +/** + * Check whether a value is stored in the table + * + * @param this The fd table + * @param value The value + * @return Whether the value is stored in the table + */ +int fd_table_contains_value(const fd_table_t* restrict this, size_t value) +{ + size_t i; + if (this->value_comparator == NULL) + { + for (i = 0; i < this->capacity; i++) + if (this->values[i] == value) + if (this->used[i / 64] & ((uint64_t)1 << (i % 64))) + return 1; + } + else + { + for (i = 0; i < this->capacity; i++) + if (this->used[i / 64] & ((uint64_t)1 << (i % 64))) + if (this->value_comparator(this->values[i], value)) + return 1; + } + return 0; +} + + +/** + * Check whether a key is used in the table + * + * @param this The fd table + * @param key The key + * @return Whether the key is used + */ +int fd_table_contains_key(const fd_table_t* restrict this, int key) +{ + return ((size_t)key < this->capacity) && (this->used[key / 64] & ((uint64_t)1 << (key % 64))); +} + + +/** + * Look up a value in the table + * + * @param this The fd table + * @param key The key associated with the value + * @return The value associated with the key, 0 if the key was not used + */ +size_t fd_table_get(const fd_table_t* restrict this, int key) +{ + if (fd_table_contains_key(this, key) == 0) + return 0; + return this->values[key]; +} + + +/** + * Add an entry to the table + * + * @param this The fd table + * @param key The key of the entry to add + * @param value The value of the entry to add + * @return The previous value associated with the key, 0 if the key was not used. + * 0 will also be returned on error, check the `errno` variable. + */ +size_t fd_table_put(fd_table_t* restrict this, int key, size_t value) +{ + if (fd_table_contains_key(this, key)) + { + size_t rc = fd_table_get(this, key); + this->values[key] = value; + return rc; + } + else + { + errno = 0; + if ((size_t)key >= this->capacity) + { + size_t old_bitcap, new_bitcap; + this->values = realloc(this->values, (this->capacity << 1) * sizeof(size_t)); + if (this->values == NULL) + return 0; + + memset(this->values + this->capacity, 0, this->capacity * sizeof(size_t)); + + old_bitcap = (this->capacity + 63) / 64; + this->capacity <<= 1; + new_bitcap = (this->capacity + 63) / 64; + + if (new_bitcap > old_bitcap) + { + this->used = realloc(this->used, new_bitcap * sizeof(size_t)); + if (this->used == NULL) + return 0; + + memset(this->used + old_bitcap, 0, (new_bitcap - old_bitcap) * sizeof(uint64_t)); + } + } + this->used[key / 64] |= (uint64_t)1 << (key % 64); + this->values[key] = value; + this->size++; + return 0; + } +} + + +/** + * Remove an entry in the table + * + * @param this The fd table + * @param key The key of the entry to remove + * @return The previous value associated with the key, 0 if the key was not used + */ +size_t fd_table_remove(fd_table_t* restrict this, int key) +{ + size_t rc = fd_table_get(this, key); + if (rc && fd_table_contains_key(this, key)) + { + this->used[key / 64] &= ~((uint64_t)1 << (key % 64)); + this->size--; + } + return rc; +} + + +/** + * Remove all entries in the table + * + * @param this The fd table + */ +void fd_table_clear(fd_table_t* restrict this) +{ + size_t bitcap; + this->size = 0; + bitcap = (this->capacity + 63) / 64; + memset(this->used, 0, bitcap * sizeof(uint64_t)); +} + + +/** + * Calculate the buffer size need to marshal a fd table + * + * @param this The fd table + * @return The number of bytes to allocate to the output buffer + */ +size_t fd_table_marshal_size(const fd_table_t* restrict this) +{ + size_t bitcap = (this->capacity + 63) / 64; + return (this->capacity + 2) * sizeof(size_t) + bitcap * sizeof(uint64_t); +} + + +/** + * Marshals a fd table + * + * @param this The fd table + * @param data Output buffer for the marshalled data + */ +void fd_table_marshal(const fd_table_t* restrict this, char* restrict data) +{ + size_t bitcap = (this->capacity + 63) / 64; + + ((size_t*)data)[0] = this->capacity; + ((size_t*)data)[1] = this->size; + data += 2 * sizeof(size_t) / sizeof(char); + + memcpy(data, this->values, this->capacity * sizeof(size_t)); + data += this->capacity * sizeof(size_t) / sizeof(char); + + memcpy(data, this->used, bitcap * sizeof(uint64_t)); +} + + +/** + * Unmarshals a fd table + * + * @param this Memory slot in which to store the new fd table + * @param data In buffer with the marshalled data + * @param remapper Function that translates values, `NULL` if not translation takes place + * @return Non-zero one error, errno will be set accordingly. + * Destroy the list on error. + */ +int fd_table_unmarshal(fd_table_t* restrict this, char* restrict data, remap_func* remapper) +{ + size_t bitcap; + + this->capacity = ((size_t*)data)[0]; + this->size = ((size_t*)data)[1]; + data += 2 * sizeof(size_t) / sizeof(char); + + this->values = NULL; + this->used = NULL; + this->value_comparator = NULL; + + this->values = malloc(this->capacity * sizeof(size_t)); + if (this->values == NULL) + return 1; + + bitcap = (this->capacity + 63) / 64; + this->used = malloc(bitcap * sizeof(size_t)); + if (this->used == NULL) + return 1; + + memcpy(this->values, data, this->capacity * sizeof(size_t)); + data += this->capacity * sizeof(size_t) / sizeof(char); + + memcpy(this->used, data, bitcap * sizeof(uint64_t)); + + if (remapper != NULL) + { + size_t i; + for (i = 0; i < this->capacity; i++) + if (this->used[i / 64] & ((uint64_t)1 << (i % 64))) + this->values[i] = remapper(this->values[i]); + } + + return 0; +} + diff --git a/src/libmdsserver/fd-table.h b/src/libmdsserver/fd-table.h new file mode 100644 index 0000000..79bd2dc --- /dev/null +++ b/src/libmdsserver/fd-table.h @@ -0,0 +1,177 @@ +/** + * mds — A micro-display server + * Copyright © 2014 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_FD_TABLE_H +#define MDS_LIBMDSSERVER_FD_TABLE_H + + +#include "table-common.h" + +#include <stdint.h> + + +/** + * Value lookup table optimised for file descriptors as keys + */ +typedef struct fd_table +{ + /** + * The table's capacity, i.e. how many entries that can be stored, + * in total, before its internal table needs to grow + */ + size_t capacity; + + /** + * The number of entries stored in the table + */ + size_t size; + + /** + * Map from keys to values + */ + size_t* values; + + /** + * Map from keys to whether that are in used, bit-packed + */ + uint64_t* used; + + /** + * Check whether two values are equal + * + * If this function pointer is `NULL`, the identity is used + * + * Be aware, this variable cannot be marshalled + */ + compare_func* value_comparator; + +} fd_table_t; + + + +/** + * Create a fd table + * + * @param this Memory slot in which to store the new fd table + * @param initial_capacity The initial capacity of the table + * @return Non-zero on error, `errno` will have been set accordingly + */ +int fd_table_create_tuned(fd_table_t* restrict this, size_t initial_capacity); + +/** + * Create a fd table + * + * @param this:fd_table_t* Memory slot in which to store the new fd table + * @return :int Non-zero on error, `errno` will have been set accordingly + */ +#define fd_table_create(this) \ + fd_table_create_tuned(this, 16) + +/** + * Release all resources in a fd table, should + * be done even if construction fails + * + * @param this The fd table + * @param keys_freer Function that frees a key, `NULL` if keys should not be freed + * @param values_freer Function that frees a value, `NULL` if value should not be freed + */ +void fd_table_destroy(fd_table_t* restrict this, free_func* key_freer, free_func* value_freer); + +/** + * Check whether a value is stored in the table + * + * @param this The fd table + * @param value The value + * @return Whether the value is stored in the table + */ +int fd_table_contains_value(const fd_table_t* restrict this, size_t value) __attribute__((pure)); + +/** + * Check whether a key is used in the table + * + * @param this The fd table + * @param key The key + * @return Whether the key is used + */ +int fd_table_contains_key(const fd_table_t* restrict this, int key) __attribute__((pure)); + +/** + * Look up a value in the table + * + * @param this The fd table + * @param key The key associated with the value + * @return The value associated with the key, 0 if the key was not used + */ +size_t fd_table_get(const fd_table_t* restrict this, int key) __attribute__((pure)); + +/** + * Add an entry to the table + * + * @param this The fd table + * @param key The key of the entry to add + * @param value The value of the entry to add + * @return The previous value associated with the key, 0 if the key was not used. + * 0 will also be returned on error, check the `errno` variable. + */ +size_t fd_table_put(fd_table_t* restrict this, int key, size_t value); + +/** + * Remove an entry in the table + * + * @param this The fd table + * @param key The key of the entry to remove + * @return The previous value associated with the key, 0 if the key was not used + */ +size_t fd_table_remove(fd_table_t* restrict this, int key); + +/** + * Remove all entries in the table + * + * @param this The fd table + */ +void fd_table_clear(fd_table_t* restrict this); + +/** + * Calculate the buffer size need to marshal a fd table + * + * @param this The fd table + * @return The number of bytes to allocate to the output buffer + */ +size_t fd_table_marshal_size(const fd_table_t* restrict this) __attribute__((pure)); + +/** + * Marshals a fd table + * + * @param this The fd table + * @param data Output buffer for the marshalled data + */ +void fd_table_marshal(const fd_table_t* restrict this, char* restrict data); + +/** + * Unmarshals a fd table + * + * @param this Memory slot in which to store the new fd table + * @param data In buffer with the marshalled data + * @param remapper Function that translates values, `NULL` if not translation takes place + * @return Non-zero one error, errno will be set accordingly. + * Destroy the list on error. + */ +int fd_table_unmarshal(fd_table_t* restrict this, char* restrict data, remap_func* remapper); + + +#endif + diff --git a/src/libmdsserver/hash-table.c b/src/libmdsserver/hash-table.c index b56600b..615f7f7 100644 --- a/src/libmdsserver/hash-table.c +++ b/src/libmdsserver/hash-table.c @@ -17,6 +17,7 @@ */ #include "hash-table.h" +#include <stdlib.h> #include <errno.h> diff --git a/src/libmdsserver/hash-table.h b/src/libmdsserver/hash-table.h index cf0af02..636d037 100644 --- a/src/libmdsserver/hash-table.h +++ b/src/libmdsserver/hash-table.h @@ -19,40 +19,7 @@ #define MDS_LIBMDSSERVER_HASH_TABLE_H -#include <stdlib.h> - - -/** - * A function that performs a comparison of two objects - * - * @param a The first object - * @param b The second object - * @return Whether the objects are equal - */ -typedef int compare_func(size_t a, size_t b); - -/** - * A function that hashes an object or a value - * - * @param value The object or value - * @return The hash of `value` - */ -typedef size_t hash_func(size_t value); - -/** - * A function that release an objects resources an frees it - * - * @param obj The object - */ -typedef void free_func(size_t obj); - -/** - * A function that translates a object into a new object - * - * @param obj The object - * @return obj The new object - */ -typedef size_t remap_func(size_t obj); +#include "table-common.h" /** @@ -84,7 +51,7 @@ typedef struct hash_entry /** - * Value lookup table based on hash value, that do not support `0` keys nor `0` values + * Value lookup table based on hash value, that do not support */ typedef struct hash_table { diff --git a/src/libmdsserver/table-common.h b/src/libmdsserver/table-common.h new file mode 100644 index 0000000..01a138c --- /dev/null +++ b/src/libmdsserver/table-common.h @@ -0,0 +1,59 @@ +/** + * mds — A micro-display server + * Copyright © 2014 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_TABLE_COMMON_H +#define MDS_LIBMDSSERVER_TABLE_COMMON_H + + +#include <stddef.h> + + +/** + * A function that performs a comparison of two objects + * + * @param a The first object + * @param b The second object + * @return Whether the objects are equal + */ +typedef int compare_func(size_t a, size_t b); + +/** + * A function that hashes an object or a value + * + * @param value The object or value + * @return The hash of `value` + */ +typedef size_t hash_func(size_t value); + +/** + * A function that release an objects resources an frees it + * + * @param obj The object + */ +typedef void free_func(size_t obj); + +/** + * A function that translates a object into a new object + * + * @param obj The object + * @return obj The new object + */ +typedef size_t remap_func(size_t obj); + + +#endif + diff --git a/src/mds-server.c b/src/mds-server.c index b0314f8..8ac2d03 100644 --- a/src/mds-server.c +++ b/src/mds-server.c @@ -19,8 +19,7 @@ #include "config.h" #include <libmdsserver/linked-list.h> -#include <libmdsserver/hash-table.h> -#include <libmdsserver/hash-help.h> +#include <libmdsserver/fd-table.h> #include <stdio.h> #include <string.h> @@ -70,7 +69,7 @@ static pthread_cond_t slave_cond; /** * Map from client socket file descriptor to all information (client_t) */ -static hash_table_t client_map; +static fd_table_t client_map; /** * List of client information (client_t) @@ -207,10 +206,10 @@ int main(int argc_, char** argv_) /* Create list and table of clients. */ - if (hash_table_create(&client_map)) + if (fd_table_create(&client_map)) { perror(*argv); - hash_table_destroy(&client_map, NULL, NULL); + fd_table_destroy(&client_map, NULL, NULL); return 1; } if (linked_list_create(&client_list, 32)) @@ -280,7 +279,7 @@ int main(int argc_, char** argv_) /* Release resources. */ - hash_table_destroy(&client_map, NULL, NULL); + fd_table_destroy(&client_map, NULL, NULL); linked_list_destroy(&client_list); return 0; @@ -318,8 +317,8 @@ void* slave_loop(void* data) goto fail; } - /* Add client to hash table. */ - tmp = hash_table_put(&client_map, (size_t)socket_fd, (size_t)(void*)information); + /* Add client to table. */ + tmp = fd_table_put(&client_map, socket_fd, (size_t)(void*)information); pthread_mutex_unlock(&slave_mutex); if ((tmp == 0) && errno) { @@ -338,7 +337,7 @@ void* slave_loop(void* data) close(socket_fd); if (information != NULL) free(information); - hash_table_remove(&client_map, (size_t)socket_fd); + fd_table_remove(&client_map, socket_fd); /* Unlist client and decrease the slave count. */ pthread_mutex_lock(&slave_mutex); |