[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