From 16e96c79e83b7b6e71d50bd41e58fb0b9d787b5c Mon Sep 17 00:00:00 2001
From: Robert James Kaes <rjkaes@users.sourceforge.net>
Date: Mon, 13 May 2002 20:02:23 +0000
Subject: Thanks to Justin Guyett for making the hashmap_insert() function use
 a constant time insert.  Explanation: new enteries are added to the _front_
 of the chain, rather than search to the end.

---
 ChangeLog     |  2 ++
 src/hashmap.c | 45 +++++++++++++++++----------------------------
 2 files changed, 19 insertions(+), 28 deletions(-)

diff --git a/ChangeLog b/ChangeLog
index de65fbe..837f3c9 100644
--- a/ChangeLog
+++ b/ChangeLog
@@ -5,6 +5,8 @@
 	(hashmap_remove): Fixed a problem where an entry could have it's
 	"prev" pointer still pointing at freed memory.  Thanks to Justin
 	Guyett for finding and fixing this problem.
+	(hashmap_insert): Thanks to Justin Guyett for changing the code to
+	use a constant time insert.  Much cleaner _and_ faster.
 
 2002-05-10  Robert James Kaes  <rjkaes@flarenet.com>
 
diff --git a/src/hashmap.c b/src/hashmap.c
index 70e2417..18006c6 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -1,4 +1,4 @@
-/* $Id: hashmap.c,v 1.8 2002-05-13 18:47:46 rjkaes Exp $
+/* $Id: hashmap.c,v 1.9 2002-05-13 20:02:23 rjkaes Exp $
  *
  * A hashmap implementation.  The keys are case-insensitive NULL terminated
  * strings, and the data is arbitrary lumps of data.  Copies of both the
@@ -185,7 +185,7 @@ int
 hashmap_insert(hashmap_t map, const char *key,
 	       const void *data, size_t len)
 {
-	struct hashentry_s *ptr, *prevptr;
+	struct hashentry_s *ptr;
 	int hash;
 	char *key_copy;
 	void *data_copy;
@@ -223,40 +223,29 @@ hashmap_insert(hashmap_t map, const char *key,
 		data_copy = NULL;
 	}
 
-	ptr = map->buckets[hash];
-	if (ptr) {
-		/* There is already an entry, so tack onto the end */
-		while (ptr) {
-			prevptr = ptr;
-			ptr = ptr->next;
-		}
-
-		ptr = safecalloc(1, sizeof(struct hashentry_s));
-		if (!ptr)
-			goto MEM_ERROR_EXIT;
-
-		ptr->prev = prevptr;
-		ptr->next = NULL;
-		prevptr->next = ptr;
-	} else {
-		ptr = map->buckets[hash] = safecalloc(1, sizeof(struct hashentry_s));
-		if (!ptr)
-			goto MEM_ERROR_EXIT;
-
-		ptr->next = ptr->prev = NULL;
+	ptr = safemalloc(sizeof(struct hashentry_s));
+	if (!ptr) {
+		safefree(key_copy);
+		safefree(data_copy);
+		return -ENOMEM;
 	}
 
 	ptr->key = key_copy;
 	ptr->data = data_copy;
 	ptr->len = len;
 
+	/*
+	 * Put the entry at the beginning of the chain.  This is a constant
+	 * time insert.  Thanks to Justin Guyett for the code.
+	 */
+	ptr->prev = NULL;
+	ptr->next = map->buckets[hash];
+	map->buckets[hash] = ptr;
+	if (ptr->next)
+		ptr->next->prev = ptr;
+
 	map->end_iterator++;
 	return 0;
-
-  MEM_ERROR_EXIT:
-	safefree(key_copy);
-        safefree(data_copy);
-        return -ENOMEM;
 }
 
 /*
-- 
cgit v1.2.3