Initial import

1 files changed, 326 insertions, 0 deletions

diff --git a/src/hashtable.c b/src/hashtable.c
new file mode 100644
index 0000000..f95c849
--- /dev/null
+++ b/src/hashtable.c
@@ -0,0 +1,326 @@
+/*
+ * Copyright (c) 2009 Petri Lehtinen <petri@digip.org>
+ *
+ * This library is free software; you can redistribute it and/or modify
+ * it under the terms of the MIT license. See LICENSE for details.
+ */
+
+#include <stdlib.h>
+#include "hashtable.h"
+
+#define container_of(ptr_, type_, member_)                      \
+    ((type_ *)((char *)ptr_ - (size_t)&((type_ *)0)->member_))
+
+typedef struct list_t {
+  struct list_t *prev;
+  struct list_t *next;
+} list_t;
+
+typedef struct {
+    void *key;
+    void *value;
+    unsigned int hash;
+    list_t list;
+} pair_t;
+
+#define list_to_pair(list_)  container_of(list_, pair_t, list)
+
+typedef struct {
+    list_t *first;
+    list_t *last;
+} bucket_t;
+
+struct hashtable {
+    unsigned int size;
+    bucket_t *buckets;
+    unsigned int num_buckets;  /* index to primes[] */
+    list_t list;
+
+    key_hash_fn hash_key;
+    key_cmp_fn cmp_keys;  /* returns non-zero for equal keys */
+    free_fn free_key;
+    free_fn free_value;
+};
+
+static inline void list_init(list_t *list)
+{
+    list->next = list;
+    list->prev = list;
+}
+
+static inline void list_insert(list_t *list, list_t *node)
+{
+    node->next = list;
+    node->prev = list->prev;
+    list->prev->next = node;
+    list->prev = node;
+}
+
+static inline void list_remove(list_t *list)
+{
+    list->prev->next = list->next;
+    list->next->prev = list->prev;
+}
+
+static inline int bucket_is_empty(hashtable_t *hashtable, bucket_t *bucket)
+{
+    return bucket->first == &hashtable->list && bucket->first == bucket->last;
+}
+
+static void insert_to_bucket(hashtable_t *hashtable, bucket_t *bucket,
+                             list_t *list)
+{
+    if(bucket_is_empty(hashtable, bucket))
+    {
+        list_insert(&hashtable->list, list);
+        bucket->first = bucket->last = list;
+    }
+    else
+    {
+        list_insert(bucket->first, list);
+        bucket->first = list;
+    }
+}
+
+static unsigned int primes[] = {
+    5, 13, 23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289, 24593,
+    49157, 98317, 196613, 393241, 786433, 1572869, 3145739, 6291469,
+    12582917, 25165843, 50331653, 100663319, 201326611, 402653189,
+    805306457, 1610612741
+};
+static const unsigned int num_primes = sizeof(primes) / sizeof(unsigned int);
+
+static inline unsigned int num_buckets(hashtable_t *hashtable)
+{
+    return primes[hashtable->num_buckets];
+}
+
+
+static pair_t *hashtable_find_pair(hashtable_t *hashtable, bucket_t *bucket,
+                                   const void *key, unsigned int hash)
+{
+    list_t *list;
+    pair_t *pair;
+
+    if(bucket_is_empty(hashtable, bucket))
+        return NULL;
+
+    list = bucket->first;
+    while(1)
+    {
+        pair = list_to_pair(list);
+        if(pair->hash == hash && hashtable->cmp_keys(pair->key, key))
+            return pair;
+
+        if(list == bucket->last)
+            break;
+
+        list = list->next;
+    }
+
+    return NULL;
+}
+
+/* returns 0 on success, -1 if key was not found */
+static int hashtable_do_del(hashtable_t *hashtable,
+                            const void *key, unsigned int hash)
+{
+    pair_t *pair;
+    bucket_t *bucket;
+    unsigned int index;
+
+    index = hash % num_buckets(hashtable);
+    bucket = &hashtable->buckets[index];
+
+    pair = hashtable_find_pair(hashtable, bucket, key, hash);
+    if(!pair)
+        return -1;
+
+    if(&pair->list == bucket->first && &pair->list == bucket->last)
+        bucket->first = bucket->last = &hashtable->list;
+
+    else if(&pair->list == bucket->first)
+        bucket->first = pair->list.next;
+
+    else if(&pair->list == bucket->last)
+        bucket->last = pair->list.prev;
+
+    list_remove(&pair->list);
+
+    if(hashtable->free_key)
+        hashtable->free_key(pair->key);
+    if(hashtable->free_value)
+        hashtable->free_value(pair->value);
+
+    free(pair);
+    hashtable->size--;
+
+    return 0;
+}
+
+static int hashtable_do_rehash(hashtable_t *hashtable)
+{
+    list_t *list, *next;
+    pair_t *pair;
+    unsigned int i, index, new_size;
+
+    free(hashtable->buckets);
+
+    hashtable->num_buckets++;
+    new_size = num_buckets(hashtable);
+
+    hashtable->buckets = malloc(new_size * sizeof(bucket_t));
+    if(!hashtable->buckets)
+        return -1;
+
+    for(i = 0; i < num_buckets(hashtable); i++)
+    {
+        hashtable->buckets[i].first = hashtable->buckets[i].last =
+            &hashtable->list;
+    }
+
+    list = hashtable->list.next;
+    list_init(&hashtable->list);
+
+    for(; list != &hashtable->list; list = next) {
+        next = list->next;
+        pair = list_to_pair(list);
+        index = pair->hash % new_size;
+        insert_to_bucket(hashtable, &hashtable->buckets[index], &pair->list);
+    }
+
+    return 0;
+}
+
+
+hashtable_t *hashtable_new(key_hash_fn hash_key, key_cmp_fn cmp_keys,
+                           free_fn free_key, free_fn free_value)
+{
+    unsigned int i;
+    hashtable_t *hashtable = malloc(sizeof(hashtable_t));
+    if(!hashtable)
+        return NULL;
+
+    hashtable->size = 0;
+    hashtable->num_buckets = 0;  /* index to primes[] */
+    hashtable->buckets = malloc(num_buckets(hashtable) * sizeof(bucket_t));
+    if(!hashtable->buckets)
+    {
+        free(hashtable);
+        return NULL;
+    }
+    list_init(&hashtable->list);
+
+    hashtable->hash_key = hash_key;
+    hashtable->cmp_keys = cmp_keys;
+    hashtable->free_key = free_key;
+    hashtable->free_value = free_value;
+
+    for(i = 0; i < num_buckets(hashtable); i++)
+    {
+        hashtable->buckets[i].first = hashtable->buckets[i].last =
+            &hashtable->list;
+    }
+
+    return hashtable;
+}
+
+void hashtable_free(hashtable_t *hashtable)
+{
+    list_t *list, *next;
+    pair_t *pair;
+    for(list = hashtable->list.next; list != &hashtable->list; list = next)
+    {
+        next = list->next;
+        pair = list_to_pair(list);
+        if(hashtable->free_key)
+            hashtable->free_key(pair->key);
+        if(hashtable->free_value)
+            hashtable->free_value(pair->value);
+        free(pair);
+    }
+
+    free(hashtable->buckets);
+    free(hashtable);
+}
+
+int hashtable_set(hashtable_t *hashtable, void *key, void *value)
+{
+    pair_t *pair;
+    bucket_t *bucket;
+    unsigned int hash, index;
+
+    hash = hashtable->hash_key(key);
+
+    /* if the key already exists, delete it */
+    hashtable_do_del(hashtable, key, hash);
+
+    /* rehash if the load ratio exceeds 1 */
+    if(hashtable->size >= num_buckets(hashtable))
+        if(hashtable_do_rehash(hashtable))
+            return -1;
+
+    pair = malloc(sizeof(pair_t));
+    if(!pair)
+        return -1;
+
+    pair->key = key;
+    pair->value = value;
+    pair->hash = hash;
+
+    index = hash % num_buckets(hashtable);
+    bucket = &hashtable->buckets[index];
+
+    list_init(&pair->list);
+    insert_to_bucket(hashtable, bucket, &pair->list);
+
+    hashtable->size++;
+    return 0;
+}
+
+void *hashtable_get(hashtable_t *hashtable, const void *key)
+{
+    pair_t *pair;
+    unsigned int hash;
+    bucket_t *bucket;
+
+    hash = hashtable->hash_key(key);
+    bucket = &hashtable->buckets[hash % num_buckets(hashtable)];
+
+    pair = hashtable_find_pair(hashtable, bucket, key, hash);
+    if(!pair)
+        return NULL;
+
+    return pair->value;
+}
+
+int hashtable_del(hashtable_t *hashtable, const void *key)
+{
+    unsigned int hash = hashtable->hash_key(key);
+    return hashtable_do_del(hashtable, key, hash);
+}
+
+void *hashtable_iter(hashtable_t *hashtable)
+{
+    return hashtable_iter_next(hashtable, &hashtable->list);
+}
+
+void *hashtable_iter_next(hashtable_t *hashtable, void *iter)
+{
+    list_t *list = (list_t *)iter;
+    if(list->next == &hashtable->list)
+        return NULL;
+    return list->next;
+}
+
+void *hashtable_iter_key(void *iter)
+{
+    pair_t *pair = list_to_pair((list_t *)iter);
+    return pair->key;
+}
+
+void *hashtable_iter_value(void *iter)
+{
+    pair_t *pair = list_to_pair((list_t *)iter);
+    return pair->value;
+}