--- /dev/null
+/* -*-c-*-
+ *
+ * $Id: hash.h,v 1.1 1999/08/02 14:45:48 mdw Exp $
+ *
+ * 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.
+ */
+
+/*----- Revision history --------------------------------------------------*
+ *
+ * $Log: hash.h,v $
+ * Revision 1.1 1999/08/02 14:45:48 mdw
+ * Break low-level hashtable code out from sym.
+ *
+ */
+
+#ifndef HASH_H
+#define HASH_H
+
+#ifdef __cplusplus
+ extern "C" {
+#endif
+
+/*----- Notes -------------------------------------------------------------*
+ *
+ * This isn't a complete implementation of anything. It's a collection of
+ * useful types and functions which will help when building hashtables of
+ * things. The general-purpose hashtable is provided by the @sym@ functions.
+ */
+
+/*----- Header files ------------------------------------------------------*/
+
+#include <stddef.h>
+
+#ifndef BITS_H
+# include "bits.h"
+#endif
+
+/*----- Data structures ---------------------------------------------------*/
+
+/* --- Hashtable basics --- *
+ *
+ * This contains the bare minimum to actually get anything useful done. In
+ * particular it doesn't maintain any weighting information: when to extend
+ * the table is left up to the particular implementation.
+ */
+
+typedef struct hash_table {
+ uint32 mask; /* Bit mask of hash bits */
+ struct hash_base **v; /* Vector of hash bins */
+} hash_table;
+
+/* --- A hashtable entry --- *
+ *
+ * This is the bare minimum of what needs to be remembered in each hashtable
+ * entry. Comparison of elements is left to the implementation, so I don't
+ * need to know anything about how to represent hash keys here.
+ */
+
+typedef struct hash_base {
+ struct hash_base *next; /* Next entry in hash bin */
+ uint32 hash; /* Hash value for this entry */
+} hash_base;
+
+/* --- A hashtable iterator --- */
+
+typedef struct hash_iter {
+ hash_table *t; /* Hashtable being iterated */
+ hash_base *p; /* Address of next item to return */
+ size_t i; /* Index of next hash bin to use */
+} hash_iter;
+
+/*----- Functions provided ------------------------------------------------*/
+
+/* --- @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.
+ */
+
+extern void hash_create(hash_table */*t*/, size_t /*n*/);
+
+/* --- @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.
+ */
+
+extern void hash_destroy(hash_table */*t*/);
+
+/* --- @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.
+ */
+
+#define HASH_BIN(t, hash) ((t)->v + ((hash) & (t)->mask))
+
+extern hash_base **hash_bin(hash_table */*t*/, uint32 /*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.
+ */
+
+extern int hash_extend(hash_table */*t*/);
+
+/* --- @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.
+ */
+
+extern void hash_remove(hash_table */*t*/, hash_base */*p*/);
+
+/* --- @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.
+ */
+
+#define HASH_MKITER(i_, t_) ((i_)->t = (t_), (i_)->p = 0, (i_)->i = 0)
+
+extern void hash_mkiter(hash_iter */*i*/, hash_table */*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.
+ */
+
+#define HASH_NEXT(i_, b_) do { \
+ hash_iter *_i = (i_); \
+ hash_base *_p; \
+ hash_table *_t = _i->t; \
+ uint32 _m = _t->mask; \
+ \
+ for (;;) { \
+ if (_i->p) { \
+ _p = _i->p; \
+ _i->p = _p->next; \
+ break; \
+ } else if (_i->i > _m) { \
+ _p = 0; \
+ break; \
+ } else \
+ _i->p = _t->v[_i->i++]; \
+ } \
+ (b_) = _p; \
+} while (0)
+
+extern hash_base *hash_next(hash_iter */*i*/);
+
+/*----- That's all, folks -------------------------------------------------*/
+
+#ifdef __cplusplus
+ }
+#endif
+
+#endif
~mdw / mLib / blobdiff