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>

2 files changed, 164 insertions, 1 deletions

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;
+}