Adding upstream version 2.8.5.upstream/2.8.5upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 232 insertions, 0 deletions

diff --git a/lib/hashtable.c b/lib/hashtable.c
new file mode 100644
index 0000000..85fbb04
--- /dev/null
+++ b/lib/hashtable.c
@@ -0,0 +1,232 @@
+/*
+ * hashtable.c: in core hash table routines.
+ *  
+ * Copyright (C) 1994, 1995 Graeme W. Wilford. (Wilf.)
+ * Copyright (C) 2002, 2003, 2004, 2005, 2007, 2008, 2009 Colin Watson.
+ *
+ * This file is part of man-db.
+ *
+ * man-db is free software; you can redistribute it and/or modify it
+ * under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 2 of the License, or
+ * (at your option) any later version.
+ *
+ * man-db 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 General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with man-db; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
+ *
+ * All of these routines except hashtable_free() can be found in K&R II.
+ *
+ * Sat Aug 20 15:01:02 BST 1994  Wilf. (G.Wilford@ee.surrey.ac.uk) 
+ */
+
+/* which hash function do we want ? */
+/* #define PROLOGUE */
+#define KRII 
+
+#ifdef HAVE_CONFIG_H
+#  include "config.h"
+#endif /* HAVE_CONFIG_H */
+
+#include <string.h>
+#include <stdlib.h>
+
+#include "manconfig.h"
+#include "hashtable.h"
+
+#if defined(PROLOGUE)
+#define HASHSIZE 2048
+#elif defined(KRII)
+#define HASHSIZE 2001
+#else
+#error hash function not defined
+#endif
+
+/* Return hash value for string. */
+static unsigned int hash (const char *s, size_t len)
+{
+	unsigned int hashval = 0;
+	size_t i;
+
+	for (i = 0; i < len && s[i]; ++i)
+#if defined(KRII)
+		hashval = s[i] + 31 * hashval;
+	return hashval % HASHSIZE;
+#elif defined(PROLOGUE)
+		hashval = (hashval << 1) + s[i];
+	return hashval & (HASHSIZE - 1);
+#endif
+}
+
+void null_hashtable_free (void *defn ATTRIBUTE_UNUSED)
+{
+}
+
+/* Create a hashtable. */
+struct hashtable *hashtable_create (hashtable_free_ptr free_defn)
+{
+	struct hashtable *ht = XMALLOC (struct hashtable);
+	ht->hashtab = XCALLOC (HASHSIZE, struct nlist *);
+	ht->unique = 0;
+	ht->identical = 0;
+	ht->free_defn = free_defn;
+	return ht;
+}
+
+/* Return pointer to hash entry structure containing s, or NULL if it
+ * doesn't exist.
+ */
+struct nlist *hashtable_lookup_structure (const struct hashtable *ht,
+					  const char *s, size_t len)
+{
+	struct nlist *np;
+
+	for (np = ht->hashtab[hash (s, len)]; np; np = np->next) {
+		if (strncmp (s, np->name, len) == 0)
+			return np;
+	}
+	return NULL;
+}
+
+/* Return pointer to definition of s, or NULL if it doesn't exist. */
+void *hashtable_lookup (const struct hashtable *ht, const char *s, size_t len)
+{
+	struct nlist *np = hashtable_lookup_structure (ht, s, len);
+	if (np)
+		return np->defn;
+	else
+		return NULL;
+}
+
+/* Return structure containing definition (never NULL). */
+struct nlist *hashtable_install (struct hashtable *ht,
+				 const char *name, size_t len, void *defn)
+{
+	struct nlist *np;
+
+	np = hashtable_lookup_structure (ht, name, len);
+	if (np) {
+		if (np->defn)
+			ht->free_defn (np->defn);
+	} else {
+		unsigned int hashval;
+
+		np = XMALLOC (struct nlist);
+		np->name = xstrndup (name, len);
+		hashval = hash (name, len);
+
+		/* record uniqueness if debugging */
+		if (debug_level) {
+			if (ht->hashtab[hashval])
+				ht->identical++;
+			else
+				ht->unique++;
+		}
+
+		/* point to last entry with this hash */
+		np->next = ht->hashtab[hashval];
+
+		/* attach to hashtab array */
+		ht->hashtab[hashval] = np;
+	}
+
+	np->defn = defn;
+
+	return np;
+}
+
+/* Remove structure containing name from the hash tree. */
+void hashtable_remove (struct hashtable *ht, const char *name, size_t len)
+{
+	struct nlist *np, *prev;
+	unsigned int hashval = hash (name, len);
+
+	for (np = ht->hashtab[hashval], prev = NULL; np;
+	     prev = np, np = np->next) {
+		if (strncmp (name, np->name, len) == 0) {
+			if (prev)
+				prev->next = np->next;
+			else
+				ht->hashtab[hashval] = np->next;
+			if (np->defn)
+				ht->free_defn (np->defn);
+			free (np->name);
+			free (np);
+			return;
+		}
+	}
+}
+
+struct hashtable_iter {
+	struct nlist **bucket;
+	struct nlist *np;
+};
+
+/* Iterate over hash.  Do not modify hash while iterating. */
+struct nlist *hashtable_iterate (const struct hashtable *ht,
+				 struct hashtable_iter **iterp)
+{
+	struct hashtable_iter *iter = *iterp;
+
+	if (!iter)
+		*iterp = iter = XZALLOC (struct hashtable_iter);
+
+	if (iter->np && iter->np->next)
+		return iter->np = iter->np->next;
+
+	if (iter->bucket)
+		++iter->bucket;
+	else
+		iter->bucket = ht->hashtab;
+
+	while (iter->bucket < ht->hashtab + HASHSIZE) {
+		if (*iter->bucket)
+			return iter->np = *iter->bucket;
+		++iter->bucket;
+	}
+
+	free (iter);
+	*iterp = NULL;
+	return NULL;
+}
+
+/* Free up the hash tree (garbage collection). Also call the free_defn()
+ * hook to free up values if necessary.
+ */
+void hashtable_free (struct hashtable *ht)
+{
+	int i;
+
+	if (!ht)
+		return;
+
+	debug ("hashtable_free: %d entries, %d (%d%%) unique\n",
+	       ht->unique + ht->identical,
+	       ht->unique,
+	       ht->unique ? (ht->unique * 100) / (ht->unique + ht->identical)
+	                  : 0);
+
+	for (i = 0; i < HASHSIZE; i++) {
+		struct nlist *np;
+
+		np = ht->hashtab[i];
+		while (np) {
+			struct nlist *next;
+
+			if (np->defn)
+				ht->free_defn (np->defn);
+			free (np->name);
+			next = np->next;
+			free (np);
+			np = next;
+		}
+	}
+
+	free (ht->hashtab);
+	free (ht);
+}