From fee76fa26ae69aa28935efd51a912a44d539523b Mon Sep 17 00:00:00 2001
From: Mattias Andrée <maandree@operamail.com>
Date: Tue, 22 Apr 2014 09:05:13 +0200
Subject: first draft of hash table implementation
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit
Signed-off-by: Mattias Andrée <maandree@operamail.com>
---
src/libmdsserver/hash-table.c | 392 ++++++++++++++++++++++++++++++++++++++++++
src/libmdsserver/hash-table.h | 254 +++++++++++++++++++++++++++
2 files changed, 646 insertions(+)
create mode 100644 src/libmdsserver/hash-table.c
create mode 100644 src/libmdsserver/hash-table.h
(limited to 'src')
diff --git a/src/libmdsserver/hash-table.c b/src/libmdsserver/hash-table.c
new file mode 100644
index 0000000..ba3f846
--- /dev/null
+++ b/src/libmdsserver/hash-table.c
@@ -0,0 +1,392 @@
+/**
+ * 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 "hash-table.h"
+
+
+/**
+ * Test if a key matches the key in a bucket
+ *
+ * @param T The instance of the hash table
+ * @param B The bucket
+ * @param K The key
+ * @param H The hash of the key
+ */
+#define TEST_KEY(T, B, K, H) \
+ ((B->key == K) || (T->key_comparator && (B->hash == H) && T->key_comparator(B->key, K)))
+
+
+/**
+ * Calculate the hash of a key
+ *
+ * @param this The hash table
+ * @param key The key to hash
+ * @return The hash of the key
+ */
+static inline long __attribute__((const)) hash(const hash_table_t* this, const void* key)
+{
+ return this->hasher ? this->hasher(key) : (long)key;
+}
+
+
+/**
+ * Truncates the hash of a key to constrain it to the buckets
+ *
+ * @param this The hash table
+ * @param key The key to hash
+ * @return A non-negative value less the the table's capacity
+ */
+static inline size_t __attribute__((pure)) truncate_hash(const hash_table_t* restrict this, long hash)
+{
+ return ((size_t)hash) % this->capacity;
+}
+
+
+/**
+ * Grow the table
+ *
+ * @param this The hash table
+ */
+static void rehash(hash_table_t* restrict this)
+{
+ hash_entry_t** old_buckets = this->buckets;
+ size_t old_capacity = this->capacity;
+ size_t i = old_capacity, index;
+ hash_entry_t* bucket;
+ hash_entry_t* destination;
+ hash_entry_t* next;
+
+ this->capacity = old_capacity * 2 + 1;
+ this->threshold = (size_t)((float)(this->capacity) * this->load_factor);
+ this->buckets = calloc(this->capacity, sizeof(hash_entry_t*));
+
+ while (i)
+ {
+ bucket = *(this->buckets + --i);
+ while (bucket)
+ {
+ index = truncate_hash(this, bucket->hash);
+ if ((destination = *(this->buckets + index)))
+ {
+ next = destination->next;
+ while (next)
+ {
+ destination = next;
+ next = destination->next;
+ }
+ destination->next = bucket;
+ }
+ else
+ *(this->buckets + index) = bucket;
+
+ next = bucket->next;
+ bucket->next = NULL;
+ bucket = next;
+ }
+ }
+
+ free(old_buckets);
+}
+
+
+/**
+ * Create a hash table
+ *
+ * @param this Memory slot in which to store the new hash table
+ * @param initial_capacity The initial capacity of the table
+ * @param load_factor The load factor of the table, i.e. when to grow the table
+ * @return Non-zero on error, `errno` will have been set accordingly
+ */
+int /**/__attribute__((const))/**/ hash_table_create_fine_tuned(hash_table_t* restrict this, size_t initial_capacity, float load_factor)
+{
+ (void) this; (void) initial_capacity; (void) load_factor; return 0; /* TODO */
+}
+
+
+/**
+ * Clone a hash table
+ *
+ * @param this The hash table to clone
+ * @param out Memory slot in which to store the new hash table
+ * @return Non-zero on error, `errno` will have been set accordingly
+ */
+int /**/__attribute__((const))/**/ hash_table_clone(const hash_table_t* restrict this, hash_table_t* restrict out)
+{
+ (void) this; (void) out; return 0; /* TODO */
+}
+
+
+/**
+ * Release all resources in a hash table, should
+ * be done even if construction fails
+ *
+ * @param this The hash table
+ * @param values Whether to free all stored values
+ * @param keys Whether to free all stored keys
+ */
+void hash_table_destroy(hash_table_t* restrict this, int values, int keys)
+{
+ size_t i = this->capacity;
+ hash_entry_t* bucket;
+ hash_entry_t* last;
+
+ if (this->buckets != NULL)
+ {
+ while (i)
+ {
+ bucket = *(this->buckets + --i);
+ while (bucket)
+ {
+ if (values)
+ free(bucket->value);
+ if (keys)
+ free(bucket->key);
+ bucket = (last = bucket)->next;
+ free(last);
+ }
+ }
+ free(this->buckets);
+ }
+}
+
+
+/**
+ * Check whether a value is stored in the table
+ *
+ * @param this The hash table
+ * @param value The value
+ * @return Whether the value is stored in the table
+ */
+int hash_table_contains_value(const hash_table_t* restrict this, void* restrict value)
+{
+ size_t i = this->capacity;
+ hash_entry_t* bucket;
+
+ while (i)
+ {
+ bucket = *(this->buckets + --i);
+ while (bucket)
+ {
+ if (bucket->value == value)
+ return 1;
+ if (this->value_comparator && this->value_comparator(bucket->value, value))
+ return 1;
+ bucket = bucket->next;
+ }
+ }
+
+ return 0;
+}
+
+
+/**
+ * Check whether a key is used in the table
+ *
+ * @param this The hash table
+ * @param key The key
+ * @return Whether the key is used
+ */
+int hash_table_contains_key(const hash_table_t* restrict this, void* restrict key)
+{
+ long key_hash = hash(this, key);
+ size_t index = truncate_hash(this, key_hash);
+ hash_entry_t* bucket = *(this->buckets + index);
+
+ while (bucket)
+ {
+ if (TEST_KEY(this, bucket, key, key_hash))
+ return 1;
+ bucket = bucket->next;
+ }
+
+ return 0;
+}
+
+
+/**
+ * Look up a value in the table
+ *
+ * @param this The hash table
+ * @param key The key associated with the value
+ * @return The value associated with the key, `NULL` i the key was not used
+ */
+void* hash_table_get(const hash_table_t* restrict this, const void* restrict key)
+{
+ long key_hash = hash(this, key);
+ size_t index = truncate_hash(this, key_hash);
+ hash_entry_t* bucket = *(this->buckets + index);
+
+ while (bucket)
+ {
+ if (TEST_KEY(this, bucket, key, key_hash))
+ return bucket->value;
+ bucket = bucket->next;
+ }
+
+ return NULL;
+}
+
+
+/**
+ * Add an entry to the table
+ *
+ * @param this The hash 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, `NULL` i the key was not used
+ */
+void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* restrict value)
+{
+ long key_hash = hash(this, key);
+ size_t index = truncate_hash(this, key_hash);
+ hash_entry_t* bucket = *(this->buckets + index);
+ void* rc;
+
+ while (bucket)
+ if (TEST_KEY(this, bucket, key, key_hash))
+ {
+ rc = bucket->value;
+ bucket->value = value;
+ return rc;
+ }
+ else
+ bucket = bucket->next;
+
+ if (++(this->size) > this->threshold)
+ {
+ rehash(this);
+ index = truncate_hash(this, key_hash);
+ }
+
+ bucket = malloc(sizeof(hash_entry_t)); /* TODO */
+ bucket->value = value;
+ bucket->key = key;
+ bucket->hash = key_hash;
+ bucket->next = *(this->buckets + index);
+ *(this->buckets + index) = bucket;
+
+ return NULL;
+}
+
+
+/**
+ * Remove an entry in the table
+ *
+ * @param this The hash table
+ * @param key The key of the entry to remove
+ * @return The previous value associated with the key, `NULL` i the key was not used
+ */
+void* hash_table_remove(hash_table_t* restrict this, const void* restrict key)
+{
+ long key_hash = hash(this, key);
+ size_t index = truncate_hash(this, key_hash);
+ hash_entry_t* bucket = *(this->buckets + index);
+ hash_entry_t* last = NULL;
+ void* rc;
+
+ while (bucket)
+ {
+ if (TEST_KEY(this, bucket, key, key_hash))
+ {
+ if (last == NULL)
+ *(this->buckets + index) = bucket->next;
+ else
+ last->next = bucket->next;
+ this->size--;
+ rc = bucket->value;
+ free(bucket);
+ return rc;
+ }
+ last = bucket;
+ bucket = bucket->next;
+ }
+
+ return NULL;
+}
+
+
+/**
+ * Remove all entries in the table
+ *
+ * @param this The hash table
+ */
+void hash_table_clear(hash_table_t* restrict this)
+{
+ hash_entry_t** buf;
+ hash_entry_t* bucket;
+ size_t i, ptr;
+
+ if (this->size)
+ {
+ buf = alloca((this->size + 1) * sizeof(hash_entry_t*));
+ i = this->capacity;
+ while (i)
+ {
+ bucket = *(this->buckets + --i);
+ ptr = 0;
+ *(buf + ptr++) = bucket;
+ while (bucket)
+ {
+ bucket = bucket->next;
+ *(buf + ptr++) = bucket;
+ }
+ while (ptr)
+ free(*(buf + --ptr));
+ *(this->buckets + i) = NULL;
+ }
+ this->size = 0;
+ }
+}
+
+
+/**
+ * Calculate the buffer size need to marshal a hash table
+ *
+ * @param this The hash table
+ * @return The number of bytes to allocate to the output buffer
+ */
+size_t /**/__attribute__((const))/**/ hash_table_marshal_size(const hash_table_t* restrict this)
+{
+ (void) this; return 0; /* TODO */
+}
+
+
+/**
+ * Marshals a hash table
+ *
+ * @param this The hash table
+ * @param data Output buffer for the marshalled data
+ */
+void /**/__attribute__((const))/**/ hash_table_marshal(const hash_table_t* restrict this, char* restrict data)
+{
+ (void) this; (void) data; /* TODO */
+}
+
+
+/**
+ * Unmarshals a hash table
+ *
+ * @param this Memory slot in which to store the new hash table
+ * @param data In buffer with the marshalled data
+ * @return Non-zero one error, errno will be set accordingly.
+ * Destroy the list on error.
+ */
+int /**/__attribute__((const))/**/ hash_table_unmarshal(hash_table_t* restrict this, char* restrict data)
+{
+ (void) this; (void) data; return 0; /* TODO */
+}
+
diff --git a/src/libmdsserver/hash-table.h b/src/libmdsserver/hash-table.h
new file mode 100644
index 0000000..8839a0d
--- /dev/null
+++ b/src/libmdsserver/hash-table.h
@@ -0,0 +1,254 @@
+/**
+ * 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_HASH_TABLE_H
+#define MDS_LIBMDSSERVER_HASH_TABLE_H
+
+
+#include <stdlib.h>
+
+
+/**
+ * Hash table entry
+ */
+typedef struct hash_entry
+{
+ /**
+ * A key
+ */
+ void* key;
+
+ /**
+ * The value associated with the key
+ */
+ void* value;
+
+ /**
+ * The truncated hash value of the key
+ */
+ long hash;
+
+ /**
+ * The next entry in the bucket
+ */
+ struct hash_entry* next;
+
+} hash_entry_t;
+
+
+/**
+ * Value lookup table based on hash value, that do not support `NULL` keys nor `NULL` values
+ */
+typedef struct hash_table
+{
+ /**
+ * The table's capacity, i.e. the number of buckets
+ */
+ size_t capacity;
+
+ /**
+ * Entry buckets
+ */
+ hash_entry_t** buckets;
+
+ /**
+ * When, in the ratio of entries comparied to the capacity, to grow the table
+ */
+ float load_factor;
+
+ /**
+ * When, in the number of entries, to grow the table
+ */
+ size_t threshold;
+
+ /**
+ * The number of entries stored in the table
+ */
+ size_t size;
+
+ /**
+ * Check whether two values are equal
+ *
+ * If this function pointer is `NULL`, the identity is used
+ *
+ * Be aware, this variable cannot be marshalled
+ *
+ * @param value_a The first value
+ * @param value_b The second value
+ * @return Whether the values are equals
+ */
+ int (*value_comparator)(const void* value_a, const void* value_b);
+
+ /**
+ * Check whether two keys are equal
+ *
+ * If this function pointer is `NULL`, the identity is used
+ *
+ * Be aware, this variable cannot be marshalled
+ *
+ * @param key_a The first key
+ * @param key_b The second key
+ * @return Whether the keys are equals
+ */
+ int (*key_comparator)(const void* key_a, const void* key_b);
+
+ /**
+ * Calculate the hash of a key
+ *
+ * If this function pointer is `NULL`, the identity hash is used
+ *
+ * Be aware, this variable cannot be marshalled
+ *
+ * @param key The key
+ * @return The hash of the key
+ */
+ long (*hasher)(const void* key);
+
+} hash_table_t;
+
+
+
+/**
+ * Create a hash table
+ *
+ * @param this Memory slot in which to store the new hash table
+ * @param initial_capacity The initial capacity of the table
+ * @param load_factor The load factor of the table, i.e. when to grow the table
+ * @return Non-zero on error, `errno` will have been set accordingly
+ */
+int hash_table_create_fine_tuned(hash_table_t* restrict this, size_t initial_capacity, float load_factor);
+
+/**
+ * Create a hash table
+ *
+ * @param this:hash_table_t* Memory slot in which to store the new hash table
+ * @param initial_capacity:size_t The initial capacity of the table
+ * @return :int Non-zero on error, `errno` will have been set accordingly
+ */
+#define hash_table_create_tuned(this, initial_capacity) \
+ hash_table_create_fine_tuned(this, initial_capacity, 0.75)
+
+/**
+ * Create a hash table
+ *
+ * @param this:hash_table_t* Memory slot in which to store the new hash table
+ * @return :int Non-zero on error, `errno` will have been set accordingly
+ */
+#define hash_table_create(this) \
+ hash_table_create_tuned(this, 16)
+
+/**
+ * Clone a hash table
+ *
+ * @param this The hash table to clone
+ * @param out Memory slot in which to store the new hash table
+ * @return Non-zero on error, `errno` will have been set accordingly
+ */
+int hash_table_clone(const hash_table_t* restrict this, hash_table_t* restrict out);
+
+/**
+ * Release all resources in a hash table, should
+ * be done even if construction fails
+ *
+ * @param this The hash table
+ * @param values Whether to free all stored values
+ * @param keys Whether to free all stored keys
+ */
+void hash_table_destroy(hash_table_t* restrict this, int values, int keys);
+
+/**
+ * Check whether a value is stored in the table
+ *
+ * @param this The hash table
+ * @param value The value
+ * @return Whether the value is stored in the table
+ */
+int hash_table_contains_value(const hash_table_t* restrict this, void* restrict value) __attribute__((pure));
+
+/**
+ * Check whether a key is used in the table
+ *
+ * @param this The hash table
+ * @param key The key
+ * @return Whether the key is used
+ */
+int hash_table_contains_key(const hash_table_t* restrict this, void* restrict key) __attribute__((pure));
+
+/**
+ * Look up a value in the table
+ *
+ * @param this The hash table
+ * @param key The key associated with the value
+ * @return The value associated with the key, `NULL` i the key was not used
+ */
+void* hash_table_get(const hash_table_t* restrict this, const void* restrict key);
+
+/**
+ * Add an entry to the table
+ *
+ * @param this The hash 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, `NULL` i the key was not used
+ */
+void* hash_table_put(hash_table_t* restrict this, void* restrict key, void* restrict value);
+
+/**
+ * Remove an entry in the table
+ *
+ * @param this The hash table
+ * @param key The key of the entry to remove
+ * @return The previous value associated with the key, `NULL` i the key was not used
+ */
+void* hash_table_remove(hash_table_t* restrict this, const void* restrict key);
+
+/**
+ * Remove all entries in the table
+ *
+ * @param this The hash table
+ */
+void hash_table_clear(hash_table_t* restrict this);
+
+/**
+ * Calculate the buffer size need to marshal a hash table
+ *
+ * @param this The hash table
+ * @return The number of bytes to allocate to the output buffer
+ */
+size_t hash_table_marshal_size(const hash_table_t* restrict this) __attribute__((pure));
+
+/**
+ * Marshals a hash table
+ *
+ * @param this The hash table
+ * @param data Output buffer for the marshalled data
+ */
+void hash_table_marshal(const hash_table_t* restrict this, char* restrict data);
+
+/**
+ * Unmarshals a hash table
+ *
+ * @param this Memory slot in which to store the new hash table
+ * @param data In buffer with the marshalled data
+ * @return Non-zero one error, errno will be set accordingly.
+ * Destroy the list on error.
+ */
+int hash_table_unmarshal(hash_table_t* restrict this, char* restrict data);
+
+
+#endif
+
--
cgit v1.2.3-70-g09d2