adding general purpose hash table
authorTobias Brunner <tobias@strongswan.org>
Wed, 3 Dec 2008 09:32:16 +0000 (09:32 -0000)
committerTobias Brunner <tobias@strongswan.org>
Wed, 3 Dec 2008 09:32:16 +0000 (09:32 -0000)
src/libstrongswan/Makefile.am
src/libstrongswan/utils/hashtable.c [new file with mode: 0644]
src/libstrongswan/utils/hashtable.h [new file with mode: 0644]

index 1423db5..1463d41 100644 (file)
@@ -47,6 +47,7 @@ utils/identification.c utils/identification.h \
 utils/iterator.h \
 utils/lexparser.c utils/lexparser.h \
 utils/linked_list.c utils/linked_list.h \
+utils/hashtable.c utils/hashtable.h \
 utils/enumerator.c utils/enumerator.h \
 utils/optionsfrom.c utils/optionsfrom.h \
 utils/mutex.c utils/mutex.h \
diff --git a/src/libstrongswan/utils/hashtable.c b/src/libstrongswan/utils/hashtable.c
new file mode 100644 (file)
index 0000000..37f37aa
--- /dev/null
@@ -0,0 +1,426 @@
+/*
+ * Copyright (C) 2008 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
+ * 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 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * 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.
+ *
+ * $Id$
+ */
+
+#include <utils/linked_list.h>
+
+#include "hashtable.h"
+
+/** The maximum capacity of the hash table (MUST be a power of 2) */
+#define MAX_CAPACITY (1 << 30)
+
+typedef struct pair_t pair_t;
+
+/**
+ * This pair holds a pointer to the key and value it represents.
+ */
+struct pair_t {
+       /**
+        * Key of a hash table item.
+        */
+       void *key;
+       
+       /**
+        * Value of a hash table item.
+        */
+       void *value;
+       
+       /**
+        * Cached hash (used in case of a resize).
+        */
+       u_int hash;
+};
+
+/**
+ * Creates an empty pair object.
+ */
+pair_t *pair_create(void *key, void *value, u_int hash)
+{
+       pair_t *this = malloc_thing(pair_t);
+       
+       this->key = key;
+       this->value = value;
+       this->hash = hash;
+       
+       return this;
+}
+
+typedef struct private_hashtable_t private_hashtable_t;
+
+/**
+ * Private data of a hashtable_t object.
+ *
+ */
+struct private_hashtable_t {
+       /**
+        * Public part of hash table.
+        */
+       hashtable_t public;
+       
+       /**
+        * The number of items in the hash table. 
+        */
+       u_int count;
+       
+       /**
+        * The current capacity of the hash table (always a power of 2).
+        */
+       u_int capacity;
+       
+       /**
+        * The current mask to calculate the row index (capacity - 1). 
+        */
+       u_int mask;
+       
+       /**
+        * The load factor.
+        */
+       float load_factor;
+       
+       /**
+        * The actual table.
+        */
+       linked_list_t **table;
+       
+       /**
+        * The hashing function.
+        */
+       hashtable_hash_t hash;
+       
+       /**
+        * The equality function.
+        */
+       hashtable_equals_t equals;
+};
+
+typedef struct private_enumerator_t private_enumerator_t;
+
+/**
+ * hash table enumerator implementation
+ */
+struct private_enumerator_t {
+
+       /**
+        * implements enumerator interface
+        */
+       enumerator_t enumerator;
+       
+       /**
+        * associated hash table
+        */
+       private_hashtable_t *table;
+       
+       /**
+        * current row index
+        */
+       u_int row;
+       
+       /**
+        * enumerator for the current row
+        */
+       enumerator_t *current;
+};
+
+/**
+ * Compare a pair in a list with the given key.
+ */
+static inline bool pair_equals(pair_t *pair, private_hashtable_t *this, void *key)
+{
+       return this->equals(key, pair->key);
+}
+
+/**
+ * This function returns the next-highest power of two for the given number.
+ * The algorithm works by setting all bits on the right-hand side of the most
+ * significant 1 to 1 and then increments the whole number so it rolls over
+ * to the nearest power of two. Note: returns 0 for n == 0
+ */
+static u_int get_nearest_powerof2(u_int n)
+{
+       u_int i;
+       --n;
+       for (--n, i = 1; i < sizeof(u_int) * 8; i <<= 1)
+       {
+               n |= n >> i;
+       }
+       return ++n;
+}
+
+/**
+ * Init hash table parameters
+ */
+static void init_hashtable(private_hashtable_t *this, u_int capacity)
+{
+       capacity = max(1, min(capacity, MAX_CAPACITY));
+       this->count = 0;
+       this->capacity = get_nearest_powerof2(capacity);
+       this->mask = this->capacity - 1;
+       this->load_factor = 0.75;
+       
+       this->table = (linked_list_t**)calloc(this->capacity, sizeof(linked_list_t*));
+       memset(this->table, 0, this->capacity * sizeof(linked_list_t*));
+}
+
+/**
+ * Double the size of the hash table and rehash all the elements.
+ */
+static void rehash(private_hashtable_t *this)
+{
+       u_int row;
+       u_int old_capacity = this->capacity;
+       linked_list_t **old_table = this->table;
+       
+       if (old_capacity >= MAX_CAPACITY)
+       {
+               return;
+       }
+       
+       init_hashtable(this, old_capacity << 1);
+       
+       for (row = 0; row < old_capacity; ++row)
+       {
+               linked_list_t *list;
+               if ((list = old_table[row]) != NULL)
+               {
+                       pair_t *pair;
+                       enumerator_t *enumerator = list->create_enumerator(list);
+                       while (enumerator->enumerate(enumerator, &pair))
+                       {
+                               linked_list_t *new_list;
+                               u_int new_row = pair->hash & this->mask;
+                               list->remove_at(list, enumerator);
+                               if ((new_list = this->table[new_row]) == NULL)
+                               {
+                                       new_list = this->table[new_row] = linked_list_create();
+                               }
+                               new_list->insert_last(new_list, pair);
+                       }
+                       enumerator->destroy(enumerator);
+                       list->destroy(list);
+               }
+       }
+       free(old_table);
+}
+
+/**
+ * Implementation of hashtable_t.put
+ */
+static void *put(private_hashtable_t *this, void *key, void *value)
+{
+       linked_list_t *list;
+       void *old_value = NULL;
+       u_int hash = this->hash(key);
+       u_int row = hash & this->mask;
+       
+       if ((list = this->table[row]) != NULL)
+       {
+               pair_t *pair;
+               enumerator_t *enumerator = list->create_enumerator(list);
+               while (enumerator->enumerate(enumerator, &pair))
+               {
+                       if (pair_equals(pair, this, key))
+                       {
+                               old_value = pair->value;
+                               pair->value = value;
+                               break;
+                       }
+               }
+               enumerator->destroy(enumerator);
+       }
+       else
+       {
+               list = this->table[row] = linked_list_create();
+       }
+       
+       if (!old_value)
+       {
+               list->insert_last(list, pair_create(key, value, hash));
+               this->count++;
+       }
+       
+       if (this->count >= this->capacity * this->load_factor)
+       {
+               rehash(this);
+       }
+       
+       return old_value;
+}
+       
+/**
+ * Implementation of hashtable_t.get  
+ */
+static void *get(private_hashtable_t *this, void *key)
+{
+       void *value = NULL;
+       linked_list_t *list;
+       u_int row = this->hash(key) & this->mask;
+       
+       if ((list = this->table[row]) != NULL)
+       {
+               pair_t *pair;
+               if (list->find_first(list, (linked_list_match_t)pair_equals,
+                               (void**)&pair, this, key) == SUCCESS)
+               {
+                       value = pair->value;
+               }
+       }
+       
+       return value;
+}
+       
+/**
+ * Implementation of hashtable_t.remove
+ */
+static void *remove(private_hashtable_t *this, void *key)
+{
+       void *value = NULL;
+       linked_list_t *list;
+       u_int row = this->hash(key) & this->mask;       
+       
+       if ((list = this->table[row]) != NULL)
+       {
+               pair_t *pair;
+               enumerator_t *enumerator = list->create_enumerator(list);
+               while (enumerator->enumerate(enumerator, &pair))
+               {
+                       if (pair_equals(pair, this, key))
+                       {
+                               list->remove_at(list, enumerator);
+                               value = pair->value;
+                               this->count--;
+                               free(pair);
+                               break;
+                       }
+               }
+               enumerator->destroy(enumerator);
+       }
+       
+       return value;
+}
+       
+/**
+ * Implementation of hashtable_t.get_count
+ */
+static u_int get_count(private_hashtable_t *this)
+{
+       return this->count;
+}
+
+/**
+ * Implementation of private_enumerator_t.enumerator.enumerate.
+ */
+static bool enumerate(private_enumerator_t *this, void **item)
+{
+       while (this->row < this->table->capacity)
+       {
+               if (this->current)
+               {
+                       pair_t *pair;
+                       if (this->current->enumerate(this->current, (void**)&pair))
+                       {
+                               *item = pair->value;
+                               return TRUE;
+                       }
+                       this->current->destroy(this->current);
+                       this->current = NULL;
+               }
+               else
+               {
+                       linked_list_t *list;
+                       if ((list = this->table->table[this->row]) != NULL)
+                       {
+                               this->current = list->create_enumerator(list);
+                               continue;
+                       }
+               }
+               this->row++;
+       }
+       return FALSE;
+}
+
+/**
+ * Implementation of private_enumerator_t.enumerator.destroy.
+ */
+static void enumerator_destroy(private_enumerator_t *this)
+{
+       if (this->current)
+       {
+               this->current->destroy(this->current);
+       }
+       free(this);
+}
+
+/**
+ * Implementation of hashtable_t.create_enumerator.
+ */
+static enumerator_t* create_enumerator(private_hashtable_t *this)
+{
+       private_enumerator_t *enumerator = malloc_thing(private_enumerator_t);
+       
+       enumerator->enumerator.enumerate = (void*)enumerate;
+       enumerator->enumerator.destroy = (void*)enumerator_destroy;
+       enumerator->table = this;
+       enumerator->row = 0;
+       enumerator->current = NULL;
+       
+       return &enumerator->enumerator;
+}
+       
+/**
+ * Implementation of hashtable_t.destroy
+ */
+static void destroy(private_hashtable_t *this)
+{
+       u_int row;
+       for (row = 0; row < this->capacity; ++row)
+       {
+               linked_list_t *list;
+               if ((list = this->table[row]) != NULL)
+               {
+                       list->destroy_function(list, free);
+               }
+       }
+       free(this->table);
+       free(this);
+}
+
+/*
+ * Described in header.
+ */
+hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
+                                                         u_int capacity)
+{
+       private_hashtable_t *this = malloc_thing(private_hashtable_t);
+
+       this->public.put = (void*(*)(hashtable_t*,void*,void*))put;
+       this->public.get = (void*(*)(hashtable_t*,void*))get; 
+       this->public.remove = (void*(*)(hashtable_t*,void*))remove;
+       this->public.get_count = (u_int(*)(hashtable_t*))get_count;
+       this->public.create_enumerator = (enumerator_t*(*)(hashtable_t*))create_enumerator;
+       this->public.destroy = (void(*)(hashtable_t*))destroy;
+       
+       this->count = 0;
+       this->capacity = 0;
+       this->mask = 0;
+       this->load_factor = 0;
+       this->table = NULL;
+       this->hash = hash;
+       this->equals = equals;
+       
+       init_hashtable(this, capacity);
+       
+       return &this->public;
+}
diff --git a/src/libstrongswan/utils/hashtable.h b/src/libstrongswan/utils/hashtable.h
new file mode 100644 (file)
index 0000000..f32da79
--- /dev/null
@@ -0,0 +1,116 @@
+/*
+ * Copyright (C) 2008 Tobias Brunner
+ * Hochschule fuer Technik Rapperswil
+ *
+ * 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 2 of the License, or (at your
+ * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
+ *
+ * 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.
+ *
+ * $Id$
+ */
+
+/**
+ * @defgroup hashtable hashtable
+ * @{ @ingroup utils
+ */
+
+#ifndef HASHTABLE_H_
+#define HASHTABLE_H_
+
+#include <utils/enumerator.h>
+
+typedef struct hashtable_t hashtable_t;
+
+/**
+ * Prototype for a function that computes the hash code from the given key.
+ *
+ * @param key                  key to hash
+ * @return                             hash code
+ */
+typedef u_int (*hashtable_hash_t)(void *key);
+
+/**
+ * Prototype for a function that compares the two keys for equality.
+ *
+ * @param key                  first key (the one we are looking for)
+ * @param other_key            second key
+ * @return                             TRUE if the keys are equal
+ */
+typedef bool (*hashtable_equals_t)(void *key, void *other_key);
+
+/**
+ * Class implementing a hash table.
+ *
+ * General purpose hash table. This hash table is not synchronized.
+ */
+struct hashtable_t {
+       
+       /**
+        * Create an enumerator over the hash table.
+        * 
+        * @return                      enumerator over hash table entries
+        */
+       enumerator_t *(*create_enumerator) (hashtable_t *this);
+       
+       /**
+        * Adds the given value with the given key to the hash table, if there
+        * exists no entry with that key. NULL is returned in this case.
+        * Otherwise the existing value is replaced and the function returns the
+        * old value.
+        * 
+        * @param key           the key to store
+        * @param value         the value to store
+        * @return                      NULL if no item was replaced, the old value otherwise
+        */
+       void *(*put) (hashtable_t *this, void *key, void *value);
+       
+       /**
+        * Returns the value with the given key, if the hash table contains such an
+        * entry, otherwise NULL is returned.
+        * 
+        * @param key           the key of the requested value
+        * @return                      the value, NULL if not found  
+        */
+       void *(*get) (hashtable_t *this, void *key);
+       
+       /**
+        * Removes the value with the given key from the hash table and returns the
+        * removed value (or NULL if no such value existed).
+        * 
+        * @param key           the key of the value to remove
+        * @return                      the removed value, NULL if not found
+        */
+       void *(*remove) (hashtable_t *this, void *key);
+       
+       /**
+        * Gets the number of items in the hash table.
+        * 
+        * @return                      number of items
+        */
+       u_int (*get_count) (hashtable_t *this);
+       
+       /**
+        * Destroys a hash table object.
+        */
+       void (*destroy) (hashtable_t *this);
+       
+};
+
+/**
+ * Creates an empty hash table object.
+ * 
+ * @param hash                 hash function
+ * @param equals               equals function
+ * @param capacity             initial capacity
+ * @return                             hashtable_t object.
+ */
+hashtable_t *hashtable_create(hashtable_hash_t hash, hashtable_equals_t equals,
+                                                         u_int capacity);
+
+#endif /* HASHTABLE_H_ @} */