Xext: add a generic hashtable implementation

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. It also has a custom
hashing and comparison functions for hashing resource IDs with
HashXID.

Reviewed-by: Rami Ylimäki <rami.ylimaki@vincit.fi>
Signed-off-by: Erkki Seppälä <erkki.seppala@vincit.fi>

5 files changed, 593 insertions, 2 deletions

diff --git a/Xext/Makefile.am b/Xext/Makefile.am
index cb432e00e..5929a3e49 100644
--- a/Xext/Makefile.am
+++ b/Xext/Makefile.am
@@ -50,7 +50,7 @@ MODULE_SRCS  += $(XV_SRCS)
 endif
 
 # XResource extension: lets clients get data about per-client resource usage
-RES_SRCS = xres.c
+RES_SRCS = hashtable.c xres.c
 if RES
 MODULE_SRCS  += $(RES_SRCS)
 endif
diff --git a/Xext/hashtable.c b/Xext/hashtable.c
new file mode 100644
index 000000000..2adf92e56
--- /dev/null
+++ b/Xext/hashtable.c
@@ -0,0 +1,291 @@
+#include <stdlib.h>
+#include "misc.h"
+#include "hashtable.h"
+
+/* HashResourceID */
+#include "resource.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 xorg_list *buckets;  /* array of bucket list heads */
+
+    HashFunc        hash;
+    HashCompareFunc compare;
+
+    pointer         cdata;
+};
+
+typedef struct {
+    struct xorg_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) {
+            xorg_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) {
+        xorg_list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
+            xorg_list_del(&it->l);
+            free(it);
+        }
+    }
+    free(ht->buckets);
+}
+
+static Bool
+double_size(HashTable ht)
+{
+    struct xorg_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) {
+            xorg_list_init(&newBuckets[c]);
+        }
+
+        for (c = 0; c < numBuckets; ++c) {
+            BucketPtr it, tmp;
+            xorg_list_for_each_entry_safe(it, tmp, &ht->buckets[c], l) {
+                struct xorg_list *newBucket =
+                    &newBuckets[ht->hash(ht->cdata, it->key, newBucketBits)];
+                xorg_list_del(&it->l);
+                xorg_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 xorg_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;
+    }
+    xorg_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;
+            xorg_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 xorg_list *bucket = &ht->buckets[index];
+    BucketPtr it;
+
+    xorg_list_for_each_entry(it, bucket, l) {
+        if (ht->compare(ht->cdata, key, it->key) == 0) {
+            xorg_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 xorg_list *bucket = &ht->buckets[index];
+    BucketPtr it;
+
+    xorg_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;
+
+        xorg_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 void *data, int len)
+{
+    CARD32 hash;
+    int i;
+    const char *key = data;
+    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);
+}
+
+unsigned
+ht_resourceid_hash(void * cdata, const void * data, int numBits)
+{
+    const XID* idPtr = data;
+    XID id = *idPtr & RESOURCE_ID_MASK;
+    (void) cdata;
+    return HashResourceID(id, numBits);
+}
+
+int
+ht_resourceid_compare(void* cdata, const void* a, const void* b)
+{
+    const XID* xa = a;
+    const XID* xb = b;
+    (void) cdata;
+    return
+        *xa < *xb ? -1 :
+        *xa > *xb ? 1 :
+        0;
+}
+
+void
+ht_dump_contents(HashTable ht,
+                 void (*print_key)(void *opaque, void *key),
+                 void (*print_value)(void *opaque, void *value),
+                 void* opaque)
+{
+    int c;
+    int numBuckets = 1 << ht->bucketBits;
+    for (c = 0; c < numBuckets; ++c) {
+        BucketPtr it;
+        int n = 0;
+
+        printf("%d: ", c);
+        xorg_list_for_each_entry(it, &ht->buckets[c], l) {
+            if (n > 0) {
+                printf(", ");
+            }
+            print_key(opaque, it->key);
+            printf("->");
+            print_value(opaque, it->data);
+            ++n;
+        }
+        printf("\n");
+    }
+}
diff --git a/Xext/hashtable.h b/Xext/hashtable.h
new file mode 100644
index 000000000..5d1598425
--- /dev/null
+++ b/Xext/hashtable.h
@@ -0,0 +1,137 @@
+#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);
+
+/** @brief  A debugging function that dumps the contents of the hash
+            table: for each bucket, list the elements contained
+            within. */
+extern _X_EXPORT void ht_dump_contents(HashTable ht,
+                                       void (*print_key)(void *opaque, void *key),
+                                       void (*print_value)(void *opaque, void *value),
+                                       void* opaque);
+
+/** @brief  A hashing function to be used for hashing resource IDs when
+            used with HashTables. It makes no use of cdata, so that can
+            be NULL. It uses HashXID underneath, and should HashXID be
+            unable to hash the value, it switches into using the generic
+            hash function. */
+extern _X_EXPORT unsigned ht_resourceid_hash(void *cdata,
+                                             const void * data,
+                                             int numBits);
+
+/** @brief  A comparison function to be used for comparing resource
+            IDs when used with HashTables. It makes no use of cdata,
+            so that can be NULL. */
+extern _X_EXPORT int ht_resourceid_compare(void *cdata,
+                                           const void *a,
+                                           const void *b);
+
+#endif // HASHTABLE_H
diff --git a/test/Makefile.am b/test/Makefile.am
index eb6147021..8c7e412c3 100644
--- a/test/Makefile.am
+++ b/test/Makefile.am
@@ -5,7 +5,7 @@ if XORG
 # Tests that require at least some DDX functions in order to fully link
 # For now, requires xf86 ddx, could be adjusted to use another
 SUBDIRS += xi2
-noinst_PROGRAMS += xkb input xtest misc fixes xfree86
+noinst_PROGRAMS += xkb input xtest misc fixes xfree86  hashtabletest
 endif
 check_LTLIBRARIES = libxservertest.la
 
@@ -36,6 +36,7 @@ misc_LDADD=$(TEST_LDADD)
 fixes_LDADD=$(TEST_LDADD)
 xfree86_LDADD=$(TEST_LDADD)
 touch_LDADD=$(TEST_LDADD)
+hashtabletest_LDADD=$(TEST_LDADD) ../Xext/hashtable.c
 
 libxservertest_la_LIBADD = $(XSERVER_LIBS)
 if XORG
diff --git a/test/hashtabletest.c b/test/hashtabletest.c
new file mode 100644
index 000000000..64c7091fc
--- /dev/null
+++ b/test/hashtabletest.c
@@ -0,0 +1,162 @@
+#include <misc.h>
+#include <stdlib.h>
+#include <stdio.h>
+#include "hashtable.h"
+#include "resource.h"
+
+static void
+print_xid(void* ptr, void* v)
+{
+    XID *x = v;
+    printf("%ld", *x);
+}
+
+static void
+print_int(void* ptr, void* v)
+{
+    int *x = v;
+    printf("%d", *x);
+}
+
+static int
+test1(void)
+{
+    HashTable h;
+    XID id;
+    int c;
+    int ok = 1;
+    const int numKeys = 420;
+
+    printf("test1\n");
+    h = ht_create(sizeof(XID), sizeof(int), ht_resourceid_hash, ht_resourceid_compare, 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);
+    ht_dump_contents(h, print_xid, print_int, NULL);
+
+    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;
+
+    printf("test2\n");
+    h = ht_create(sizeof(XID), 0, ht_resourceid_hash, ht_resourceid_compare, 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;
+    printf("test3\n");
+    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;
+}