--- /dev/null
+/* -*-c-*-
+ *
+ * General hashtable infrastructure
+ *
+ * (c) 1999 Straylight/Edgeware
+ */
+
+/*----- Licensing notice --------------------------------------------------*
+ *
+ * This file is part of the mLib utilities library.
+ *
+ * mLib is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU Library General Public License as
+ * published by the Free Software Foundation; either version 2 of the
+ * License, or (at your option) any later version.
+ *
+ * mLib is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
+ * GNU Library General Public License for more details.
+ *
+ * You should have received a copy of the GNU Library General Public
+ * License along with mLib; if not, write to the Free
+ * Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
+ * MA 02111-1307, USA.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "alloc.h"
+#include "arena.h"
+#include "bits.h"
+#include "exc.h"
+#include "hash.h"
+
+/*----- Main code ---------------------------------------------------------*/
+
+/* --- @hash_create@ --- *
+ *
+ * Arguments: @hash_table *t@ = pointer to hashtable to initialize
+ * @size_t n@ = number of bins to allocate (zero initially)
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a hashtable with a given number of bins. The
+ * bins are initially empty. The number of bins must be a power
+ * of two. This is not checked.
+ */
+
+void hash_create(hash_table *t, size_t n)
+{
+ hash_base **v;
+
+ t->a = arena_global;
+ t->v = x_alloc(t->a, n * sizeof(hash_base *));
+ t->mask = n - 1;
+ for (v = t->v; n; v++, n--)
+ *v = 0;
+}
+
+/* --- @hash_destroy@ --- *
+ *
+ * Arguments: @hash_table *t@ = pointer to hashtable to destroy
+ *
+ * Returns: ---
+ *
+ * Use: Frees a hashtable. The items are not freed: they are the
+ * responsibility of the implementation.
+ */
+
+void hash_destroy(hash_table *t) { x_free(t->a, t->v); }
+
+/* --- @hash_bin@ --- *
+ *
+ * Arguments: @hash_table *t@ = pointer to hashtable
+ * @uint32 hash@ = hash value to look up
+ *
+ * Returns: Pointer to the bin's list head.
+ *
+ * Use: Given a hash value return the address of the appropriate list
+ * head. It is safe to remove the current entry from the table.
+ */
+
+hash_base **hash_bin(hash_table *t, uint32 hash)
+ { return (HASH_BIN(t, hash)); }
+
+/* --- @hash_extend@ --- *
+ *
+ * Arguments: @hash_table *t@ = pointer to hashtable to extend
+ *
+ * Returns: Nonzero if extension was successful.
+ *
+ * Use: Extends a hashtable. The number of bins is doubled and the
+ * entries are redistributed.
+ */
+
+int hash_extend(hash_table *t)
+{
+ hash_base **v;
+ uint32 m = t->mask + 1;
+ size_t i;
+
+ /* --- Allocate a new hash bin vector --- */
+
+ if ((v = A_REALLOC(t->a, t->v,
+ 2 * m * sizeof(hash_base *),
+ m * sizeof(hash_base *))) == 0) {
+ return (0);
+ }
+ t->v = v;
+ t->mask = (m * 2) - 1;
+
+ /* --- Wander through the table rehashing things --- */
+
+ for (i = 0; i < m; i++) {
+ hash_base **p = v + i;
+ hash_base **q = p + m;
+
+ while (*p) {
+ if (!((*p)->hash & m))
+ p = &(*p)->next;
+ else {
+ *q = *p;
+ q = &(*q)->next;
+ *p = (*p)->next;
+ }
+ }
+ *p = 0;
+ *q = 0;
+ }
+
+ return (1);
+}
+
+/* --- @hash_remove@ --- *
+ *
+ * Arguments: @hash_table *t@ = pointer to hashtable
+ * @hash_base *p@ = pointer to item to remove
+ *
+ * Returns: ---
+ *
+ * Use: Removes an item from a hashtable. The item itself is not
+ * freed, although it is removed from the data structure and is
+ * safe to free.
+ */
+
+void hash_remove(hash_table *t, hash_base *p)
+{
+ hash_base **b = HASH_BIN(t, p->hash);
+ while (*b) {
+ if (*b == p) {
+ *b = p->next;
+ return;
+ }
+ b = &(*b)->next;
+ }
+ return;
+}
+
+/* --- @hash_mkiter@ --- *
+ *
+ * Arguments: @hash_iter *i@ = pointer to iterator to create
+ * @hash_table *t@ = pointer to hashtable to iterate
+ *
+ * Returns: ---
+ *
+ * Use: Initializes a hashtable iterator.
+ */
+
+void hash_mkiter(hash_iter *i, hash_table *t) { HASH_MKITER(i, t); }
+
+/* --- @hash_next@ --- *
+ *
+ * Arguments: @hash_iter *i@ = pointer to iterator
+ *
+ * Returns: Pointer to the next hashtable entry found, or null.
+ *
+ * Use: Returns the next entry from the hashtable.
+ */
+
+hash_base *hash_next(hash_iter *i)
+{
+ hash_base *b;
+ HASH_NEXT(i, b);
+ return (b);
+}
+
+/*----- That's all, folks -------------------------------------------------*/