summaryrefslogtreecommitdiff
path: root/src/htable.h
diff options
context:
space:
mode:
Diffstat (limited to 'src/htable.h')
-rw-r--r--src/htable.h392
1 files changed, 392 insertions, 0 deletions
diff --git a/src/htable.h b/src/htable.h
new file mode 100644
index 0000000..31e9d2f
--- /dev/null
+++ b/src/htable.h
@@ -0,0 +1,392 @@
+/* $Id: htable.h,v 1.1 2008/11/08 19:05:15 culot Exp $ */
+
+/*
+ * Copyright (c) 2008 Frederic Culot <frederic@culot.org>
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * - Redistributions of source code must retain the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ * copyright notice, this list of conditions and the
+ * following disclaimer in the documentation and/or other
+ * materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#ifndef HTABLE_H
+#define HTABLE_H
+
+#include <stdint.h>
+#include <string.h>
+
+/*
+ * This file defines data structures for hash tables.
+ *
+ * Hash tables are ideal for applications with datasets needing lots of adding,
+ * searching or removal, as those are normally constant-time operations.
+ * The primary operation it supports efficiently is a lookup: given a key (e.g.
+ * a person's name), find the corresponding value (e.g. that person's telephone
+ * number). It works by transforming the key using a hash function into a hash,
+ * a number that is used as an index in an array to locate the desired location
+ * ("bucket") where the values should be.
+ *
+ * Hash tables support the efficient insertion of new entries, in expected O(1)
+ * time. The time spent in searching depends on the hash function and the load
+ * of the hash table; both insertion and search approach O(1) time with well
+ * chosen values and hashes.
+ *
+ * The collision resolution technique used here is direct chaining, implemented
+ * using singly linked lists (the worst-case time is O(n)).
+ *
+ * This was chosen because performance degradation is linear as the table
+ * fills, so there is almost no need to resize table
+ * (for example, a chaining hash table containing twice its recommended
+ * capacity of data would only be about twice as slow on average as the same
+ * table at its recommended capacity).
+ */
+
+#define HTABLE_HEAD(name, size, type) \
+struct name { \
+ uint32_t noitems; /* Number of items stored in hash table. */ \
+ uint32_t nosingle; /* Number of items alone in their bucket. */ \
+ uint32_t nofreebkts; /* Number of free buckets. */ \
+ struct type *bkts[size]; /* Pointers to user-defined data structures. */ \
+}
+
+#define HTABLE_ENTRY(type) \
+struct { \
+ struct type *next; /* To build the bucket chain list. */ \
+}
+
+#define HTABLE_SIZE(head) \
+ (sizeof (*(head)->bkts) ? sizeof ((head)->bkts) / sizeof (*(head)->bkts) : 0)
+
+#define HTABLE_COUNT(head) \
+ ((head)->noitems ? (head)->noitems : 0)
+
+#define HTABLE_EMPTY(head) \
+ (HTABLE_COUNT((head)) == 0 ? 1 : 0)
+
+#define HTABLE_COLLS(head) \
+ ((head)->noitems ? 100.0 - 100 * (head)->nosingle / (head)->noitems : 0)
+
+#define HTABLE_LOAD(head) \
+ (HTABLE_SIZE((head)) ? \
+ 100.0 - 100.0 * (head)->nofreebkts / HTABLE_SIZE((head)) : 0)
+
+#define HTABLE_INITIALIZER(head) \
+ { 0, /* noitems */ \
+ 0, /* nosingle */ \
+ HTABLE_SIZE((head)) /* nofreebkts */ \
+ }
+
+#define HTABLE_INIT(head) do { \
+ bzero ((head), sizeof (*(head))); \
+ (head)->nofreebkts = HTABLE_SIZE((head)); \
+} while (0)
+
+/*
+ * Generate prototypes.
+ */
+#define HTABLE_PROTOTYPE(name, type) \
+struct type *name##_HTABLE_INSERT(struct name *, struct type *); \
+struct type *name##_HTABLE_REMOVE(struct name *, struct type *); \
+struct type *name##_HTABLE_LOOKUP(struct name *, struct type *);
+
+/*
+ * Generate function bodies.
+ */
+#define HTABLE_GENERATE(name, type, key, cmp) \
+uint32_t \
+name##_HTABLE_FIND_BKT(struct name *head, struct type *elm) \
+{ \
+ uint32_t __bkt; \
+ char *__key; \
+ int __len; \
+ \
+ (key) (elm, &__key, &__len); \
+ HTABLE_HASH(__key, __len, HTABLE_SIZE(head), __bkt); \
+ \
+ return __bkt; \
+} \
+ \
+int \
+name##_HTABLE_CHAIN_LEN(struct name *head, uint32_t bkt) \
+{ \
+ struct type *__bktp; \
+ int __len; \
+ \
+ __len = 0; \
+ for (__bktp = (head)->bkts[(bkt)]; __bktp != NULL; __bktp = __bktp->next) \
+ __len++; \
+ \
+ return __len; \
+} \
+ \
+struct type * \
+name##_HTABLE_INSERT(struct name *head, struct type *elm) \
+{ \
+ struct type *__bktp, **__bktpp; \
+ uint32_t __bkt, __pos; \
+ \
+ __pos = 0; \
+ __bkt = name##_HTABLE_FIND_BKT(head, elm); \
+ __bktpp = &head->bkts[__bkt]; \
+ while ((__bktp = *__bktpp)) \
+ { \
+ if (!(cmp)(elm, __bktp)) \
+ return __bktp; \
+ else \
+ { \
+ __pos++; \
+ __bktpp = &__bktp->next; \
+ } \
+ } \
+ __bktp = elm; \
+ __bktp->next = NULL; \
+ *__bktpp = __bktp; \
+ head->noitems++; \
+ switch (__pos) \
+ { \
+ case 0: \
+ head->nosingle++; \
+ head->nofreebkts--; \
+ break; \
+ case 1: \
+ head->nosingle--; \
+ break; \
+ default: \
+ break; \
+ } \
+ \
+ return __bktp; \
+} \
+ \
+struct type * \
+name##_HTABLE_REMOVE(struct name *head, struct type *elm) \
+{ \
+ struct type *__bktp, **__bktpp; \
+ uint32_t __bkt, __pos; \
+ \
+ __pos = 0; \
+ __bkt = name##_HTABLE_FIND_BKT(head, elm); \
+ __bktpp = &head->bkts[__bkt]; \
+ while ((__bktp = *__bktpp)) \
+ { \
+ if (!(cmp)(elm, __bktp)) \
+ { \
+ *__bktpp = __bktp->next; \
+ elm = __bktp; \
+ head->noitems--; \
+ if (__pos <= 1) /* Need to scan list to know if we have */ \
+ { /* a free bucket or a single item. */ \
+ int __len; \
+ \
+ __len = name##_HTABLE_CHAIN_LEN(head, __bkt); \
+ switch (__len) \
+ { \
+ case 0: \
+ head->nofreebkts++; \
+ head->nosingle--; \
+ break; \
+ case 1: \
+ head->nosingle++; \
+ break; \
+ } \
+ } \
+ return elm; \
+ } \
+ __pos++; \
+ __bktpp = &__bktp->next; \
+ } \
+ return NULL; \
+} \
+ \
+struct type * \
+name##_HTABLE_LOOKUP(struct name *head, struct type *elm) \
+{ \
+ struct type *__bktp, **__bktpp; \
+ uint32_t __bkt; \
+ \
+ __bkt = name##_HTABLE_FIND_BKT(head, elm); \
+ __bktpp = &head->bkts[__bkt]; \
+ while ((__bktp = *__bktpp)) \
+ { \
+ if (!(cmp)(elm, __bktp)) \
+ return __bktp; \
+ else \
+ __bktpp = &__bktp->next; \
+ } \
+ \
+ return NULL; \
+} \
+ \
+struct type * \
+name##_HTABLE_FIRST_FROM(struct name *head, int bkt) \
+{ \
+ struct type *__bktp; \
+ \
+ while (bkt < HTABLE_SIZE(head)) \
+ { \
+ if ((__bktp = head->bkts[bkt])) \
+ return __bktp; \
+ else \
+ bkt++; \
+ } \
+ \
+ return NULL; \
+} \
+ \
+struct type * \
+name##_HTABLE_NEXT(struct name *head, struct type *elm) \
+{ \
+ struct type *__elmp, *__bktp, **__bktpp; \
+ uint32_t __bkt; \
+ \
+ __elmp = NULL; \
+ __bkt = name##_HTABLE_FIND_BKT(head, elm); \
+ __bktpp = &head->bkts[__bkt]; \
+ while ((__bktp = *__bktpp)) \
+ { \
+ if (!(cmp)(elm, __bktp)) \
+ { \
+ __elmp = __bktp; \
+ break; \
+ } \
+ else \
+ __bktpp = &__bktp->next; \
+ } \
+ \
+ if (!__elmp) \
+ return NULL; \
+ else if (__elmp->next) \
+ return __elmp->next; \
+ else \
+ return name##_HTABLE_FIRST_FROM(head, ++__bkt); \
+}
+
+#define FIRST_BKT 0
+
+#define HTABLE_INSERT(name, x, y) name##_HTABLE_INSERT(x, y)
+#define HTABLE_REMOVE(name, x, y) name##_HTABLE_REMOVE(x, y)
+#define HTABLE_LOOKUP(name, x, y) name##_HTABLE_LOOKUP(x, y)
+#define HTABLE_FIRST_FROM(name, x, y) (HTABLE_EMPTY(x) ? NULL \
+ : name##_HTABLE_FIRST_FROM(x, y))
+#define HTABLE_FIRST(name, x) HTABLE_FIRST_FROM(name, x, FIRST_BKT)
+#define HTABLE_NEXT(name, x, y) (HTABLE_EMPTY(x) ? NULL \
+ : name##_HTABLE_NEXT(x, y))
+
+#define HTABLE_FOREACH(x, name, head) \
+ for ((x) = HTABLE_FIRST(name, head); \
+ (x) != NULL; \
+ (x) = HTABLE_NEXT(name, head, x))
+
+/*
+ * Hash functions.
+ */
+#ifdef HASH_FUNCTION
+#define HTABLE_HASH HASH_FUNCTION
+#else
+#define HTABLE_HASH HASH_JEN
+#endif
+
+#define HASH_JEN_MIX(a, b, c) do { \
+ a -= b; a -= c; a ^= (c >> 13); \
+ b -= c; b -= a; b ^= (a << 8); \
+ c -= a; c -= b; c ^= (b >> 13); \
+ a -= b; a -= c; a ^= (c >> 12); \
+ b -= c; b -= a; b ^= (a << 16); \
+ c -= a; c -= b; c ^= (b >> 5); \
+ a -= b; a -= c; a ^= (c >> 3); \
+ b -= c; b -= a; b ^= (a << 10); \
+ c -= a; c -= b; c ^= (b >> 15); \
+} while (0)
+
+#define HASH_JEN(key, keylen, num_bkts, bkt) do { \
+ register uint32_t i, j, k, hash; \
+ \
+ hash = 0xfeedbeef; \
+ i = j = 0x9e3779b9; \
+ k = keylen; \
+ while (k >= 12) \
+ { \
+ i += (key[0] + ((unsigned)key[1] << 8) \
+ + ((unsigned)key[2] << 16) \
+ + ((unsigned)key[3] << 24)); \
+ j += (key[4] + ((unsigned)key[5] << 8) \
+ + ((unsigned)key[6] << 16) \
+ + ((unsigned)key[7] << 24 )); \
+ hash += (key[8] + ((unsigned)key[9] << 8) \
+ + ((unsigned)key[10] << 16) \
+ + ((unsigned)key[11] << 24)); \
+ \
+ HASH_JEN_MIX (i, j, hash); \
+ \
+ key += 12; \
+ k -= 12; \
+ } \
+ hash += keylen; \
+ switch (k) \
+ { \
+ case 11: \
+ hash += ((unsigned)key[10] << 24); \
+ case 10: \
+ hash += ((unsigned)key[9] << 16); \
+ case 9: \
+ hash += ((unsigned)key[8] << 8); \
+ case 8: \
+ j += ((unsigned)key[7] << 24); \
+ case 7: \
+ j += ((unsigned)key[6] << 16); \
+ case 6: \
+ j += ((unsigned)key[5] << 8); \
+ case 5: \
+ j += key[4]; \
+ case 4: \
+ i += ((unsigned)key[3] << 24); \
+ case 3: \
+ i += ((unsigned)key[2] << 16); \
+ case 2: \
+ i += ((unsigned)key[1] << 8); \
+ case 1: \
+ i += key[0]; \
+ } \
+ HASH_JEN_MIX (i, j, hash); \
+ bkt = hash % (num_bkts); \
+} while (0)
+
+#define HASH_OAT(key, keylen, num_bkts, bkt) do { \
+ register uint32_t hash; \
+ int i; \
+ \
+ hash = 0; \
+ for (i = 0; i < keylen; i++) \
+ { \
+ hash += key[i]; \
+ hash += (hash << 10); \
+ hash ^= (hash >> 6); \
+ } \
+ hash += (hash << 3); \
+ hash ^= (hash >> 11); \
+ hash += (hash << 15); \
+ bkt = hash % (num_bkts); \
+} while (0)
+
+#endif /* !HTABLE_H */
generated by cgit v1.2.3 (git 2.25.1) at 2024-12-23 01:00:27 +0000