X-Git-Url: http://www.chiark.greenend.org.uk/ucgi/~mdw/git/mLib/blobdiff_plain/dd3c57bc8cac59e0d657ee665ce462988d27d714..18c831dcd0ae4d660c70ccac69d27ed2a97851be:/struct/hash.c

diff --git a/struct/hash.c b/struct/hash.c
new file mode 100644
index 0000000..d4df9b7
--- /dev/null
+++ b/struct/hash.c
@@ -0,0 +1,192 @@
+/* -*-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 -------------------------------------------------*/