Removed the hashmap_keys() function and added the "iterator" concept.

This required a bunch of changes to the source (like the inclusion of the
end_iterator member variable.)  All this was required by sites like Yahoo
which send out multiple "Set-Cookie" headers.  tinyproxy needs to handle
this situation correctly.

2 files changed, 229 insertions, 72 deletions

diff --git a/src/hashmap.c b/src/hashmap.c
index eb83749..fa827b4 100644
--- a/src/hashmap.c
+++ b/src/hashmap.c
@@ -1,4 +1,4 @@
-/* $Id: hashmap.c,v 1.5 2002-04-18 18:40:38 rjkaes Exp $
+/* $Id: hashmap.c,v 1.6 2002-04-25 18:55:56 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
@@ -28,7 +28,6 @@
 #include "tinyproxy.h"
 
 #include "hashmap.h"
-#include "vector.h"
 #include "utils.h"
 
 /*
@@ -47,6 +46,8 @@ struct hashentry_s {
 };
 struct hashmap_s {
 	unsigned int size;
+	hashmap_iter end_iterator;
+
 	struct hashentry_s **maps;
 };
 
@@ -107,6 +108,9 @@ hashmap_create(unsigned int nbuckets)
 		return NULL;
 	}
 
+	/* This points to "one" past the end of the hashmap. */
+	ptr->end_iterator = 0;
+
 	return ptr;
 }
 
@@ -184,6 +188,11 @@ hashmap_insert(hashmap_t map, const char *key,
 	char *key_copy;
 	void *data_copy;
 
+	assert(map != NULL);
+	assert(key != NULL);
+	assert(data != NULL);
+	assert(len > 0);
+
 	if (map == NULL || key == NULL)
 		return -EINVAL;
 	if (!data || len < 1)
@@ -238,23 +247,145 @@ hashmap_insert(hashmap_t map, const char *key,
 	ptr->data = data_copy;
 	ptr->len = len;
 
+	map->end_iterator++;
+
 	return 0;
 }
 
 /*
- * A pointer to data is returned based on a case-insensitive NULL terminated
- * "key".  If the "key" is not found, "data" is set to NULL.  A NULL "data"
- * argument indicates that the data associated with the key is to be ignored.
+ * Get an iterator to the first entry.
+ *
+ * Returns: an negative value upon error.
+ */
+hashmap_iter
+hashmap_first(hashmap_t map)
+{
+	if (!map)
+		return -EINVAL;
+
+	if (map->end_iterator == 0)
+		return -1;
+	else
+		return 0;
+}
+
+/*
+ * Checks to see if the iterator is pointing at the "end" of the entries.
+ *
+ * Returns: 1 if it is the end
+ *          0 otherwise
+ */
+int
+hashmap_is_end(hashmap_t map, hashmap_iter iter)
+{
+	assert(map != NULL);
+	assert(iter >= 0);
+
+	if (!map || iter < 0)
+		return -EINVAL;
+
+	if (iter == map->end_iterator)
+		return 1;
+	else
+		return 0;
+}
+
+/*
+ * Return a "pointer" to the first instance of the particular key.  It can
+ * be tested against hashmap_is_end() to see if the key was not found.
  *
  * Returns: negative upon an error
+ *          an "iterator" pointing at the first key
+ *          an "end-iterator" if the key wasn't found
+ */
+hashmap_iter
+hashmap_find(hashmap_t map, const char* key)
+{
+	unsigned int i;
+	hashmap_iter iter = 0;
+	struct hashentry_s* ptr;
+
+	assert(map != NULL);
+	assert(key != NULL);
+
+	if (!map || !key)
+		return -EINVAL;
+
+	/*
+	 * Loop through all the keys and look for the first occurance
+	 * of a particular key.
+	 */
+	for (i = 0; i < map->size; i++) {
+		ptr = map->maps[i];
+
+		while (ptr) {
+			if (strcasecmp(ptr->key, key) == 0) {
+				/* Found it, so return the current count */
+				return iter;
+			}
+
+			iter++;
+			ptr = ptr->next;
+		}
+	}
+
+	return iter;
+}
+
+/*
+ * Retrieve the data associated with a particular iterator.
+ *
+ * Returns: the length of the data block upon success
+ *          negative upon error
+ */
+ssize_t
+hashmap_return_entry(hashmap_t map, hashmap_iter iter,
+		     char** key, void** data)
+{
+	unsigned int i;
+	struct hashentry_s* ptr;
+	hashmap_iter count = 0;
+
+	assert(map != NULL);
+	assert(iter >= 0);
+	assert(iter != map->end_iterator);
+	assert(key != NULL);
+	assert(data != NULL);
+
+	if (!map || iter < 0 || !key || !data)
+		return -EINVAL;
+
+	for (i = 0; i < map->size; i++) {
+		ptr = map->maps[i];
+		while (ptr) {
+			if (count == iter) {
+				/* This is the data so return it */
+				*key = ptr->key;
+				*data = ptr->data;
+				return ptr->len;
+			}
+
+			ptr = ptr->next;
+			count++;
+		}
+	}
+
+	return -EFAULT;
+}
+
+/*
+ * Searches for _any_ occurrances of "key" within the hashmap.
+ * 
+ * Returns: negative upon an error
  *          zero if no key is found
- *          length of data if key is found.
+ *          count found
  */
 ssize_t
-hashmap_search(hashmap_t map, const char *key, void **data)
+hashmap_search(hashmap_t map, const char *key)
 {
 	int hash;
 	struct hashentry_s* ptr;
+	ssize_t count = 0;
 
 	if (map == NULL || key == NULL)
 		return -EINVAL;
@@ -267,78 +398,65 @@ hashmap_search(hashmap_t map, const char *key, void **data)
 
 	/* Okay, there is an entry here, now see if it's the one we want */
 	while (ptr) {
-		if (strcasecmp(ptr->key, key) == 0) {
-			/* Found it, return a pointer to the data */
-			if (data)
-				*data = ptr->data;
-			return ptr->len;
-		}
+		if (strcasecmp(ptr->key, key) == 0)
+			++count;
 
 		/* This entry didn't contain the key; move to the next one */
 		ptr = ptr->next;
 	}
 
-	/* The key was not found, so return NULL */
-	if (data)
-		*data = NULL;
-	return 0;
+	return count;
 }
 
 /*
- * Produce a vector of all the keys in the hashmap.
+ * Get the first entry (assuming there is more than one) for a particular
+ * key.  The data MUST be non-NULL.
  *
- * Returns: NULL upon error
- *          a valid vector_t if everything is fine
+ * Returns: negative upon error
+ *          zero if no entry is found
+ *          length of data for the entry
  */
-vector_t
-hashmap_keys(hashmap_t map)
+ssize_t
+hashmap_entry_by_key(hashmap_t map, const char* key, void** data)
 {
-	vector_t vector;
-	unsigned int i;
-	struct hashentry_s *ptr;
-
-	if (!map)
-		return NULL;
-
-	vector = vector_create();
-	if (!vector)
-		return NULL;
+	int hash;
+	struct hashentry_s* ptr;
 
-	/*
-	 * Iterate through all the entries and add the keys to the
-	 * vector.
-	 */
-	for (i = 0; i < map->size; i++) {
-		ptr = map->maps[i];
+	if (!map || !key || !data)
+		return -EINVAL;
+       
+	hash = hashfunc(key, map->size);
+	if (hash < 0)
+		return hash;
 
-		while (ptr) {
-			if (vector_insert(vector, ptr->key, strlen(ptr->key) + 1) < 0) {
-				/* There's a problem, so delete the vector */
-				vector_delete(vector);
-				return NULL;
-			}
+	ptr = map->maps[hash];
 
-			ptr = ptr->next;
+	while (ptr) {
+		if (strcasecmp(ptr->key, key) == 0) {
+			*data = ptr->data;
+			return ptr->len;
 		}
+
+		ptr = ptr->next;
 	}
 
-	return vector;
+	return 0;
 }
 
 /*
  * Go through the hashmap and remove the particular key.
- * NOTE: This _will_ invalidate any vectors which might have been created
- *       by the hashmap_keys() function.
+ * NOTE: This will invalidate any iterators which have been created.
  *
  * Remove: negative upon error
  *         0 if the key was not found
- *         1 if the entry was deleted
+ *         positive count of entries deleted
  */
 ssize_t
 hashmap_remove(hashmap_t map, const char *key)
 {
 	int hash;
 	struct hashentry_s* ptr;
+	short int deleted = 0;
 
 	if (map == NULL || key == NULL)
 		return -EINVAL;
@@ -368,8 +486,16 @@ hashmap_remove(hashmap_t map, const char *key)
 			safefree(ptr->key);
 			safefree(ptr->data);
 			safefree(ptr);
+			
+			++deleted;
+			--map->end_iterator;
+
+			if (prevptr)
+				ptr = prevptr;
+			else
+				ptr = map->maps[hash];
 
-			return 1;
+			continue;
 		}
 
 		/* This entry didn't contain the key; move to the next one */
@@ -377,5 +503,5 @@ hashmap_remove(hashmap_t map, const char *key)
 	}
 
 	/* The key was not found, so return 0 */
-	return 0;
+	return deleted;
 }
diff --git a/src/hashmap.h b/src/hashmap.h
index b0104c0..d56c46a 100644
--- a/src/hashmap.h
+++ b/src/hashmap.h
@@ -1,4 +1,4 @@
-/* $Id: hashmap.h,v 1.1 2002-04-07 21:30:02 rjkaes Exp $
+/* $Id: hashmap.h,v 1.2 2002-04-25 18:55:56 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
@@ -28,8 +28,6 @@
 #ifndef _HASHMAP_H
 #define _HASHMAP_H
 
-#include "vector.h"
-
 /* Allow the use in C++ code. */
 #if defined(__cplusplus)
 extern "C" {
@@ -41,6 +39,7 @@ extern "C" {
  * So, just use the hashmap_t like it's a cookie. :)
  */
 typedef struct hashmap_s* hashmap_t;
+typedef int hashmap_iter;
 
 /*
  * hashmap_create() takes one argument, which is the number of buckets to
@@ -62,36 +61,68 @@ extern int hashmap_insert(hashmap_t map, const char *key,
 			  const void *data, size_t len);
 
 /*
- * If a valid key is found in the hash map you will get a pointer to the
- * data stored in the hash map.  In other words, you have the power to change
- * the data a key is associated with, but do it responsibly since the
- * library doesn't take any steps to prevent you from messing up the hash
- * map.  Don't try to realloc or free the data though; doing so will break
- * the hashmap.  If you are only interested in whether the key is present
- * or not, supply a NULL for the "data" argument.
+ * Get an iterator to the first entry.
  *
- * Returns: negative on error
- *          zero if the key was not found
- *          positive (length of data) if key is found
+ * Returns: an negative value upon error.
  */
-extern ssize_t hashmap_search(hashmap_t map, const char *key, void **data);
+extern hashmap_iter hashmap_first(hashmap_t map);
 
 /*
- * Produce a vector of all the keys in the hashmap.
+ * Checks to see if the iterator is pointing at the "end" of the entries.
  *
- * Returns: NULL upon error
- *          a valid vector_t if everything is fine
+ * Returns: 1 if it is the end
+ *          0 otherwise
+ */
+extern int hashmap_is_end(hashmap_t map, hashmap_iter iter);
+
+/*
+ * Return a "pointer" to the first instance of the particular key.  It can
+ * be tested against hashmap_is_end() to see if the key was not found.
+ *
+ * Returns: negative upon an error
+ *          an "iterator" pointing at the first key
+ *          an "end-iterator" if the key wasn't found
+ */
+extern hashmap_iter hashmap_find(hashmap_t map, const char* key);
+
+/*
+ * Retrieve the key/data associated with a particular iterator.
+ * NOTE: These are pointers to the actual data, so don't mess around with them
+ *       too much.
+ *
+ * Returns: the length of the data block upon success
+ *          negative upon error
+ */
+extern ssize_t hashmap_return_entry(hashmap_t map, hashmap_iter iter,
+				    char** key, void** data);
+
+/*
+ * Get the first entry (assuming there is more than one) for a particular
+ * key.  The data MUST be non-NULL.
+ *
+ * Returns: negative upon error
+ *          zero if no entry is found
+ *          length of data for the entry
+ */
+extern ssize_t hashmap_entry_by_key(hashmap_t map, const char* key, void** data);
+
+/*
+ * Searches for _any_ occurrances of "key" within the hashmap and returns the
+ * number of matching entries.
+ * 
+ * Returns: negative upon an error
+ *          zero if no key is found
+ *          count found (positive value)
  */
-extern vector_t hashmap_keys(hashmap_t map);
+extern ssize_t hashmap_search(hashmap_t map, const char *key);
 
 /*
  * Go through the hashmap and remove the particular key.
- * NOTE: This _will_ invalidate any vectors which might have been created
- *       by the hashmap_keys() function.
+ * NOTE: This will invalidate any iterators which have been created.
  *
  * Remove: negative upon error
  *         0 if the key was not found
- *         1 if the entry was deleted
+ *         positive count of entries deleted
  */
 extern ssize_t hashmap_remove(hashmap_t map, const char *key);