aboutsummaryrefslogtreecommitdiff
path: root/xorg-server/Xext/hashtable.c
diff options
context:
space:
mode:
Diffstat (limited to 'xorg-server/Xext/hashtable.c')
-rw-r--r--xorg-server/Xext/hashtable.c291
1 files changed, 291 insertions, 0 deletions
diff --git a/xorg-server/Xext/hashtable.c b/xorg-server/Xext/hashtable.c
new file mode 100644
index 000000000..2adf92e56
--- /dev/null
+++ b/xorg-server/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");
+ }
+}