[RFC] [PATCH 3/8] [xserver] dix: add a generic hashtable implementation
Tiago Vignatti
tiago.vignatti at nokia.com
Wed Dec 29 06:06:48 PST 2010
On Mon, Dec 27, 2010 at 04:56:57PM +0200, ext Erkki Sepp�l� wrote:
> 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.
>
> Reviewed-by: Rami Ylim??ki <rami.ylimaki at vincit.fi>
this patch doesn't apply on xserver, master branch. Make sure to build all of
them against so everyone can give a try easily.
Also, you are forgetting to put your Signed-off-by, giving you are sending
patches around.
> ---
> 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 5e2dad7..09080aa 100644
> --- a/dix/Makefile.am
> +++ b/dix/Makefile.am
> @@ -26,6 +26,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 13c5ae5..aa406db 100755
> --- a/hw/xfree86/loader/sdksyms.sh
> +++ b/hw/xfree86/loader/sdksyms.sh
> @@ -280,6 +280,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 e76de05..0c02b6b 100644
> --- a/include/Makefile.am
> +++ b/include/Makefile.am
> @@ -26,6 +26,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 6e72356..a977cd0 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
>
> _______________________________________________
> xorg-devel at lists.x.org: X.Org development
> Archives: http://lists.x.org/archives/xorg-devel
> Info: http://lists.x.org/mailman/listinfo/xorg-devel
Tiago
More information about the xorg-devel
mailing list