add table optimised for file descriptors

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

6 files changed, 564 insertions, 44 deletions

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);