[RFC] [PATCH v2 7/12] [xserver] dix: add a generic hashtable implementation
Erkki Seppälä
erkki.seppala at vincit.fi
Fri Dec 31 05:32:45 PST 2010
The generic hashtable implementation adds a key-value container, that
keeps the key and value inside the hashtable structure and manages
their memory by itself. This data structure is best suited for
fixed-length keys and values.
One creates a new hash table with ht_create and disposes it with
ht_destroy. ht_create accepts the key and value sizes (in bytes) in
addition to the hashing and comparison functions to use. When adding
keys with ht_add, they will be copied into the hash and a pointer to
the value will be returned: data may be put into this structure (or if
the hash table is to be used as a set, one can just not put anything
in).
The hash table comes also with one generic hashing function plus a
comparison function to facilitate ease of use.
Signed-off-by: Erkki Seppälä <erkki.seppala at vincit.fi>
Reviewed-by: Rami Ylimäki <rami.ylimaki at vincit.fi>
---
dix/Makefile.am | 1 +
dix/hashtable.c | 240 ++++++++++++++++++++++++++++++++++++++++++
hw/xfree86/loader/sdksyms.sh | 1 +
include/Makefile.am | 1 +
include/hashtable.h | 113 ++++++++++++++++++++
test/Makefile.am | 3 +-
test/hashtabletest.c | 143 +++++++++++++++++++++++++
7 files changed, 501 insertions(+), 1 deletions(-)
create mode 100644 dix/hashtable.c
create mode 100644 include/hashtable.h
create mode 100644 test/hashtabletest.c
diff --git a/dix/Makefile.am b/dix/Makefile.am
index 59e512b..fe54e4c 100644
--- a/dix/Makefile.am
+++ b/dix/Makefile.am
@@ -27,6 +27,7 @@ libdix_la_SOURCES = \
globals.c \
glyphcurs.c \
grabs.c \
+ hashtable.c \
initatoms.c \
inpututils.c \
pixmap.c \
diff --git a/dix/hashtable.c b/dix/hashtable.c
new file mode 100644
index 0000000..3657625
--- /dev/null
+++ b/dix/hashtable.c
@@ -0,0 +1,240 @@
+#include <stdlib.h>
+#include "misc.h"
+#include "hashtable.h"
+
+#define INITHASHSIZE 6
+#define MAXHASHSIZE 11
+
+struct HashTableRec {
+ int keySize;
+ int dataSize;
+
+ int elements; /* number of elements inserted */
+ int bucketBits; /* number of buckets is 1 << bucketBits */
+ struct list *buckets; /* array of bucket list heads */
+
+ HashFunc hash;
+ HashCompareFunc compare;
+
+ pointer cdata;
+};
+
+typedef struct {
+ struct list l;
+ void *key;
+ void *data;
+} BucketRec, *BucketPtr;
+
+HashTable
+ht_create(int keySize,
+ int dataSize,
+ HashFunc hash,
+ HashCompareFunc compare,
+ pointer cdata)
+{
+ int c;
+ int numBuckets;
+ HashTable ht = malloc(sizeof(struct HashTableRec));
+
+ if (!ht) {
+ return NULL;
+ }
+
+ ht->keySize = keySize;
+ ht->dataSize = dataSize;
+ ht->hash = hash;
+ ht->compare = compare;
+ ht->elements = 0;
+ ht->bucketBits = INITHASHSIZE;
+ numBuckets = 1 << ht->bucketBits;
+ ht->buckets = malloc(numBuckets * sizeof(*ht->buckets));
+ ht->cdata = cdata;
+
+ if (ht->buckets) {
+ for (c = 0; c < numBuckets; ++c) {
+ list_init(&ht->buckets[c]);
+ }
+ return ht;
+ } else {
+ free(ht);
+ return NULL;
+ }
+}
+
+void
+ht_destroy(HashTable ht)
+{
+ int c;
+ BucketPtr it, tmp;
+ int numBuckets = 1 << ht->bucketBits;
+ for (c = 0; c < numBuckets; ++c) {
+ list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
+ list_del(&it->l);
+ free(it);
+ }
+ }
+ free(ht->buckets);
+}
+
+static Bool
+double_size(HashTable ht)
+{
+ struct list *newBuckets;
+ int numBuckets = 1 << ht->bucketBits;
+ int newBucketBits = ht->bucketBits + 1;
+ int newNumBuckets = 1 << newBucketBits;
+ int c;
+
+ newBuckets = malloc(newNumBuckets * sizeof(*ht->buckets));
+ if (newBuckets) {
+ for (c = 0; c < newNumBuckets; ++c) {
+ list_init(&newBuckets[c]);
+ }
+
+ for (c = 0; c < numBuckets; ++c) {
+ BucketPtr it, tmp;
+ list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
+ struct list *newBucket =
+ &newBuckets[ht->hash(ht->cdata, it->key, newBucketBits)];
+ list_del(&it->l);
+ list_add(&it->l, newBucket);
+ }
+ }
+ free(ht->buckets);
+
+ ht->buckets = newBuckets;
+ ht->bucketBits = newBucketBits;
+ return TRUE;
+ } else {
+ return FALSE;
+ }
+}
+
+pointer
+ht_add(HashTable ht, pointer key)
+{
+ unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
+ struct list *bucket = &ht->buckets[index];
+ BucketRec *elem = calloc(1, sizeof(BucketRec));
+ if (!elem) {
+ goto outOfMemory;
+ }
+ elem->key = malloc(ht->keySize);
+ if (!elem->key) {
+ goto outOfMemory;
+ }
+ /* we avoid signaling an out-of-memory error if dataSize is 0 */
+ elem->data = calloc(1, ht->dataSize);
+ if (ht->dataSize && !elem->data) {
+ goto outOfMemory;
+ }
+ list_add(&elem->l, bucket);
+ ++ht->elements;
+
+ memcpy(elem->key, key, ht->keySize);
+
+ if (ht->elements > 4 * (1 << ht->bucketBits) &&
+ ht->bucketBits < MAXHASHSIZE) {
+ if (!double_size(ht)) {
+ --ht->elements;
+ list_del(&elem->l);
+ goto outOfMemory;
+ }
+ }
+
+ /* if memory allocation has failed due to dataSize being 0, return
+ a "dummy" pointer pointing at the of the key */
+ return elem->data ? elem->data : ((char*) elem->key + ht->keySize);
+
+ outOfMemory:
+ if (elem) {
+ free(elem->key);
+ free(elem->data);
+ free(elem);
+ }
+
+ return NULL;
+}
+
+void
+ht_remove(HashTable ht, pointer key)
+{
+ unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
+ struct list *bucket = &ht->buckets[index];
+ BucketPtr it;
+
+ list_for_each_entry(it, bucket, l) {
+ if (ht->compare(ht->cdata, key, it->key) == 0) {
+ list_del(&it->l);
+ --ht->elements;
+ free(it->key);
+ free(it->data);
+ free(it);
+ return;
+ }
+ }
+}
+
+pointer
+ht_find(HashTable ht, pointer key)
+{
+ unsigned index = ht->hash(ht->cdata, key, ht->bucketBits);
+ struct list *bucket = &ht->buckets[index];
+ BucketPtr it;
+
+ list_for_each_entry(it, bucket, l) {
+ if (ht->compare(ht->cdata, key, it->key) == 0) {
+ return it->data ? it->data : ((char*) it->key + ht->keySize);
+ }
+ }
+
+ return NULL;
+}
+
+void
+ht_dump_distribution(HashTable ht)
+{
+ int c;
+ int numBuckets = 1 << ht->bucketBits;
+ for (c = 0; c < numBuckets; ++c) {
+ BucketPtr it;
+ int n = 0;
+
+ list_for_each_entry(it, &ht->buckets[c], l) {
+ ++n;
+ }
+ printf("%d: %d\n", c, n);
+ }
+}
+
+/* Picked the function from http://burtleburtle.net/bob/hash/doobs.html by
+ Bob Jenkins, which is released in public domain */
+static CARD32
+one_at_a_time_hash(const char *key, int len)
+{
+ CARD32 hash;
+ int i;
+ for (hash=0, i=0; i<len; ++i) {
+ hash += key[i];
+ hash += (hash << 10);
+ hash ^= (hash >> 6);
+ }
+ hash += (hash << 3);
+ hash ^= (hash >> 11);
+ hash += (hash << 15);
+ return hash;
+}
+
+unsigned
+ht_generic_hash(void *cdata, const void *ptr, int numBits)
+{
+ HtGenericHashSetupPtr setup = cdata;
+ return one_at_a_time_hash(ptr, setup->keySize) & ~((~0) << numBits);
+}
+
+int
+ht_generic_compare(void *cdata, const void *l, const void *r)
+{
+ HtGenericHashSetupPtr setup = cdata;
+ return memcmp(l, r, setup->keySize);
+}
diff --git a/hw/xfree86/loader/sdksyms.sh b/hw/xfree86/loader/sdksyms.sh
index f60b8ed..fb0a4bd 100755
--- a/hw/xfree86/loader/sdksyms.sh
+++ b/hw/xfree86/loader/sdksyms.sh
@@ -275,6 +275,7 @@ cat > sdksyms.c << EOF
#include "gc.h"
#include "gcstruct.h"
#include "globals.h"
+#include "hashtable.h"
#include "input.h"
#include "inputstr.h"
/* already included */
diff --git a/include/Makefile.am b/include/Makefile.am
index 42f0082..2dab490 100644
--- a/include/Makefile.am
+++ b/include/Makefile.am
@@ -25,6 +25,7 @@ sdk_HEADERS = \
gc.h \
gcstruct.h \
globals.h \
+ hashtable.h \
input.h \
inputstr.h \
list.h \
diff --git a/include/hashtable.h b/include/hashtable.h
new file mode 100644
index 0000000..303a30b
--- /dev/null
+++ b/include/hashtable.h
@@ -0,0 +1,113 @@
+#ifndef HASHTABLE_H
+#define HASHTABLE_H 1
+
+#include <dix-config.h>
+#include <X11/Xfuncproto.h>
+#include <X11/Xdefs.h>
+#include "list.h"
+
+/** @brief A hashing function.
+
+ @param[in/out] cdata Opaque data that can be passed to HtInit that will
+ eventually end up here
+ @param[in] ptr The data to be hashed. The size of the data, if
+ needed, can be configured via a record that can be
+ passed via cdata.
+ @param[in] numBits The number of bits this hash needs to have in the
+ resulting hash
+
+ @return A numBits-bit hash of the data
+*/
+typedef unsigned (*HashFunc)(void * cdata, const void * ptr, int numBits);
+
+/** @brief A comparison function for hashed keys.
+
+ @param[in/out] cdata Opaque data that ca be passed to Htinit that will
+ eventually end up here
+ @param[in] l The left side data to be compared
+ @param[in] r The right side data to be compared
+
+ @return -1 if l < r, 0 if l == r, 1 if l > r
+*/
+typedef int (*HashCompareFunc)(void * cdata, const void * l, const void * r);
+
+struct HashTableRec;
+
+typedef struct HashTableRec *HashTable;
+
+/** @brief A configuration for HtGenericHash */
+typedef struct {
+ int keySize;
+} HtGenericHashSetupRec, *HtGenericHashSetupPtr;
+
+/** @brief ht_create initalizes a hash table for a certain hash table
+ configuration
+
+ @param[out] ht The hash table structure to initialize
+ @param[in] keySize The key size in bytes
+ @param[in] dataSize The data size in bytes
+ @param[in] hash The hash function to use for hashing keys
+ @param[in] compare The comparison function for hashing keys
+ @param[in] cdata Opaque data that will be passed to hash and
+ comparison functions
+*/
+extern _X_EXPORT HashTable ht_create(int keySize,
+ int dataSize,
+ HashFunc hash,
+ HashCompareFunc compare,
+ pointer cdata);
+/** @brief HtDestruct deinitializes the structure. It does not free the
+ memory allocated to HashTableRec
+*/
+extern _X_EXPORT void ht_destroy(HashTable ht);
+
+/** @brief Adds a new key to the hash table. The key will be copied
+ and a pointer to the value will be returned. The data will
+ be initialized with zeroes.
+
+ @param[in/out] ht The hash table
+ @param[key] key The key. The contents of the key will be copied.
+
+ @return On error NULL is returned, otherwise a pointer to the data
+ associated with the newly inserted key.
+
+ @note If dataSize is 0, a pointer to the end of the key may be returned
+ to avoid returning NULL. Obviously the data pointed cannot be
+ modified, as implied by dataSize being 0.
+*/
+extern _X_EXPORT pointer ht_add(HashTable ht, pointer key);
+
+/** @brief Removes a key from the hash table along with its
+ associated data, which will be free'd.
+*/
+extern _X_EXPORT void ht_remove(HashTable ht, pointer key);
+
+/** @brief Finds the associated data of a key from the hash table.
+
+ @return If the key cannot be found, the function returns NULL.
+ Otherwise it returns a pointer to the data associated
+ with the key.
+
+ @note If dataSize == 0, this function may return NULL
+ even if the key has been inserted! If dataSize == NULL,
+ use HtMember instead to determine if a key has been
+ inserted.
+*/
+extern _X_EXPORT pointer ht_find(HashTable ht, pointer key);
+
+/** @brief A generic hash function */
+extern _X_EXPORT unsigned ht_generic_hash(void *cdata,
+ const void *ptr,
+ int numBits);
+
+/** @brief A generic comparison function. It compares data byte-wise. */
+extern _X_EXPORT int ht_generic_compare(void *cdata,
+ const void *l,
+ const void *r);
+
+/** @brief A debugging function that dumps the distribution of the
+ hash table: for each bucket, list the number of elements
+ contained within. */
+extern _X_EXPORT void ht_dump_distribution(HashTable ht);
+
+#endif // HASHTABLE_H
diff --git a/test/Makefile.am b/test/Makefile.am
index 456221e..fa24055 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -1,6 +1,6 @@
if UNITTESTS
SUBDIRS= . xi2
-check_PROGRAMS = xkb input xtest
+check_PROGRAMS = xkb input xtest hashtabletest
check_LTLIBRARIES = libxservertest.la
TESTS=$(check_PROGRAMS)
@@ -16,6 +16,7 @@ endif
xkb_LDADD=$(TEST_LDADD)
input_LDADD=$(TEST_LDADD)
xtest_LDADD=$(TEST_LDADD)
+hashtabletest_LDADD=$(TEST_LDADD)
libxservertest_la_LIBADD = \
$(XSERVER_LIBS) \
diff --git a/test/hashtabletest.c b/test/hashtabletest.c
new file mode 100644
index 0000000..d46cb3e
--- /dev/null
+++ b/test/hashtabletest.c
@@ -0,0 +1,143 @@
+#include <stdlib.h>
+#include <stdio.h>
+#include "hashtable.h"
+#include "resource.h"
+
+static int
+test1(void)
+{
+ HashTable h;
+ XID id;
+ int c;
+ int ok = 1;
+ const int numKeys = 420;
+
+ h = ht_create(sizeof(XID), sizeof(int), HashResourceID, CompareResourceID, NULL);
+
+ for (c = 0; c < numKeys; ++c) {
+ int *dest;
+ id = c;
+ dest = ht_add(h, &id);
+ if (dest) {
+ *dest = 2 * c;
+ }
+ }
+
+ printf("Distribution after insertion\n");
+ ht_dump_distribution(h);
+
+ for (c = 0; c < numKeys; ++c) {
+ XID id = c;
+ int* v = ht_find(h, &id);
+ if (v) {
+ if (*v == 2 * c) {
+ // ok
+ } else {
+ printf("Key %d doesn't have expected value %d but has %d instead\n",
+ c, 2 * c, *v);
+ ok = 0;
+ }
+ } else {
+ ok = 0;
+ printf("Cannot find key %d\n", c);
+ }
+ }
+
+ if (ok) {
+ printf("%d keys inserted and found\n", c);
+
+ for (c = 0; c < numKeys; ++c) {
+ XID id = c;
+ ht_remove(h, &id);
+ }
+
+ printf("Distribution after deletion\n");
+ ht_dump_distribution(h);
+ }
+
+ ht_destroy(h);
+
+ return ok;
+}
+
+static int
+test2(void)
+{
+ HashTable h;
+ XID id;
+ int c;
+ int ok = 1;
+ const int numKeys = 420;
+
+ h = ht_create(sizeof(XID), 0, HashResourceID, CompareResourceID, NULL);
+
+ for (c = 0; c < numKeys; ++c) {
+ id = c;
+ ht_add(h, &id);
+ }
+
+ for (c = 0; c < numKeys; ++c) {
+ XID id = c;
+ if (!ht_find(h, &id)) {
+ ok = 0;
+ printf("Cannot find key %d\n", c);
+ }
+ }
+
+ {
+ XID id = c + 1;
+ if (ht_find(h, &id)) {
+ ok = 0;
+ printf("Could find a key that shouldn't be there\n");
+ }
+ }
+
+ ht_destroy(h);
+
+ if (ok) {
+ printf("Test with empty keys OK\n");
+ } else {
+ printf("Test with empty keys FAILED\n");
+ }
+
+ return ok;
+}
+
+static int
+test3(void)
+{
+ int ok = 1;
+ HtGenericHashSetupRec hashSetup = {
+ .keySize = 4
+ };
+ HashTable h;
+ h = ht_create(4, 0, ht_generic_hash, ht_generic_compare, &hashSetup);
+
+ if (!ht_add(h, "helo") ||
+ !ht_add(h, "wrld")) {
+ printf("Could not insert keys\n");
+ }
+
+ if (!ht_find(h, "helo") ||
+ !ht_find(h, "wrld")) {
+ ok = 0;
+ printf("Could not find inserted keys\n");
+ }
+
+ printf("Hash distribution with two strings\n");
+ ht_dump_distribution(h);
+
+ ht_destroy(h);
+
+ return ok;
+}
+
+int
+main(void)
+{
+ int ok = test1();
+ ok = ok && test2();
+ ok = ok && test3();
+
+ return ok ? 0 : 1;
+}
--
1.7.0.4
More information about the xorg-devel
mailing list