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 <[email protected]> --- 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
_______________________________________________ [email protected]: X.Org development Archives: http://lists.x.org/archives/xorg-devel Info: http://lists.x.org/mailman/listinfo/xorg-devel
