* [1118363] Proxy reverse order of headers

  Changed the internal implementation of the hashmap to maintain the
  insert order if the same key is repeated.  The insertion is still
  constant since we keep track of the head and tail of the bucket
  chain.

1 files changed, 43 insertions, 41 deletions

diff --git a/src/hashmap.c b/src/hashmap.c
index f1806af..bf95ec2 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -1,4 +1,4 @@
-/* $Id: hashmap.c,v 1.14 2004-02-13 21:27:42 rjkaes Exp $
+/* $Id: hashmap.c,v 1.15 2005-05-03 20:34:54 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
@@ -44,11 +44,16 @@ struct hashentry_s {
 
 	struct hashentry_s *prev, *next;
 };
+
+struct hashbucket_s {
+        struct hashentry_s *head, *tail;
+};
+
 struct hashmap_s {
 	unsigned int size;
 	hashmap_iter end_iterator;
 
-	struct hashentry_s **buckets;
+	struct hashbucket_s *buckets;
 };
 
 /*
@@ -102,7 +107,7 @@ hashmap_create(unsigned int nbuckets)
 		return NULL;
 
 	ptr->size = nbuckets;
-	ptr->buckets = safecalloc(nbuckets, sizeof(struct hashentry_s *));
+	ptr->buckets = safecalloc(nbuckets, sizeof(struct hashbucket_s));
 	if (!ptr->buckets) {
 		safefree(ptr);
 		return NULL;
@@ -122,15 +127,15 @@ hashmap_create(unsigned int nbuckets)
  *          negative number is returned if "entry" was NULL
  */
 static inline int
-delete_hashbucket(struct hashentry_s* entry)
+delete_hashbucket(struct hashbucket_s* bucket)
 {
 	struct hashentry_s *nextptr;
 	struct hashentry_s *ptr;
 
-	if (entry == NULL)
+	if (bucket == NULL || bucket->head == NULL)
 		return -EINVAL;
 
-	ptr = entry;
+	ptr = bucket->head;
 	while (ptr) {
 		nextptr = ptr->next;
 		
@@ -159,9 +164,8 @@ hashmap_delete(hashmap_t map)
 		return -EINVAL;
 
 	for (i = 0; i != map->size; i++) {
-		if (map->buckets[i] != NULL) {
-			delete_hashbucket(map->buckets[i]);
-			map->buckets[i] = NULL;
+		if (map->buckets[i].head != NULL) {
+			delete_hashbucket(&map->buckets[i]);
 		}
 	}
 
@@ -234,15 +238,17 @@ hashmap_insert(hashmap_t map, const char *key,
 	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;
+        /*
+         * Now add the entry to the end of the bucket chain.
+         */
+        ptr->next = NULL;
+        ptr->prev = map->buckets[hash].tail;
+        if (map->buckets[hash].tail)
+                map->buckets[hash].tail->next = ptr;
+        
+        map->buckets[hash].tail = ptr;
+        if (!map->buckets[hash].head)
+                map->buckets[hash].head = ptr;
 
 	map->end_iterator++;
 	return 0;
@@ -314,7 +320,7 @@ hashmap_find(hashmap_t map, const char* key)
 	 * of a particular key.
 	 */
 	for (i = 0; i != map->size; i++) {
-		ptr = map->buckets[i];
+		ptr = map->buckets[i].head;
 
 		while (ptr) {
 			if (strcasecmp(ptr->key, key) == 0) {
@@ -354,7 +360,7 @@ hashmap_return_entry(hashmap_t map, hashmap_iter iter,
 		return -EINVAL;
 
 	for (i = 0; i != map->size; i++) {
-		ptr = map->buckets[i];
+		ptr = map->buckets[i].head;
 		while (ptr) {
 			if (count == iter) {
 				/* This is the data so return it */
@@ -392,7 +398,7 @@ hashmap_search(hashmap_t map, const char *key)
 	if (hash < 0)
 		return hash;
 
-	ptr = map->buckets[hash];
+	ptr = map->buckets[hash].head;
 
 	/* All right, there is an entry here, now see if it's the one we want */
 	while (ptr) {
@@ -427,7 +433,7 @@ hashmap_entry_by_key(hashmap_t map, const char* key, void** data)
 	if (hash < 0)
 		return hash;
 
-	ptr = map->buckets[hash];
+	ptr = map->buckets[hash].head;
 
 	while (ptr) {
 		if (strcasecmp(ptr->key, key) == 0) {
@@ -453,7 +459,7 @@ ssize_t
 hashmap_remove(hashmap_t map, const char *key)
 {
 	int hash;
-	struct hashentry_s* ptr;
+	struct hashentry_s *ptr, *next;
 	short int deleted = 0;
 
 	if (map == NULL || key == NULL)
@@ -463,25 +469,25 @@ hashmap_remove(hashmap_t map, const char *key)
 	if (hash < 0)
 		return hash;
 
-	ptr = map->buckets[hash];
+	ptr = map->buckets[hash].head;
 	while (ptr) {
 		if (strcasecmp(ptr->key, key) == 0) {
 			/*
 			 * Found the data, now need to remove everything
 			 * and update the hashmap.
 			 */
-			struct hashentry_s* prevptr = ptr->prev;
-			if (prevptr != NULL) {
-				prevptr->next = ptr->next;
-				if (ptr->next)
-					ptr->next->prev = prevptr;
-			} else {
-				/* Entry was first in map */
-				map->buckets[hash] = ptr->next;
-				if (ptr->next)
-					ptr->next->prev = NULL;
-			}
-
+                        next = ptr->next;
+                        
+                        if (ptr->prev)
+                                ptr->prev->next = ptr->next;
+                        if (ptr->next)
+                                ptr->next->prev = ptr->prev;
+
+                        if (map->buckets[hash].head == ptr)
+                                map->buckets[hash].head = ptr->next;
+                        if (map->buckets[hash].tail == ptr)
+                                map->buckets[hash].tail = ptr->prev;
+                        
 			safefree(ptr->key);
 			safefree(ptr->data);
 			safefree(ptr);
@@ -489,11 +495,7 @@ hashmap_remove(hashmap_t map, const char *key)
 			++deleted;
 			--map->end_iterator;
 
-			if (prevptr)
-				ptr = prevptr;
-			else
-				ptr = map->buckets[hash];
-
+                        ptr = next;
 			continue;
 		}