save headers in an ordered dictionary

due to the usage of a hashmap to store headers, when relaying them
to the other side the order was not prevented.
even though correct from a standards point-of-view, this caused
issues with various programs, and it allows to fingerprint the use
of tinyproxy.

to implement this, i imported the MIT-licensed hsearch.[ch] from
https://github.com/rofl0r/htab which was originally taken from
musl libc. it's a simple and efficient hashtable implementation
with far better performance characteristic than the one previously
used by tinyproxy. additionally it has an API much more well-suited
for this purpose.

orderedmap.[ch] was implemented from scratch to address this issue.
behind the scenes it uses an sblist to store string values, and a htab
to store keys and the indices into the sblist.
this allows us to iterate linearly over the sblist and then find the
corresponding key in the hash table, so the headers can be reproduced
in the order they were received.

closes #73

10 files changed, 434 insertions, 98 deletions

diff --git a/src/Makefile.am b/src/Makefile.am
index 50e645b..c3b8dca 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -49,6 +49,8 @@ tinyproxy_SOURCES = \
 	basicauth.c basicauth.h \
 	base64.c base64.h \
 	sblist.c sblist.h \
+	hsearch.c hsearch.h \
+	orderedmap.c orderedmap.h \
 	loop.c loop.h \
 	connect-ports.c connect-ports.h
 
diff --git a/src/hsearch.c b/src/hsearch.c
new file mode 100644
index 0000000..0d022a2
--- /dev/null
+++ b/src/hsearch.c
@@ -0,0 +1,199 @@
+/*
+musl license, hsearch.c originally written by Szabolcs Nagy
+
+Copyright © 2005-2020 Rich Felker, et al.
+
+Permission is hereby granted, free of charge, to any person obtaining
+a copy of this software and associated documentation files (the
+"Software"), to deal in the Software without restriction, including
+without limitation the rights to use, copy, modify, merge, publish,
+distribute, sublicense, and/or sell copies of the Software, and to
+permit persons to whom the Software is furnished to do so, subject to
+the following conditions:
+
+The above copyright notice and this permission notice shall be
+included in all copies or substantial portions of the Software.
+
+THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
+IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
+CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
+TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
+SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
+*/
+
+#include <stdlib.h>
+#include <string.h>
+#include "hsearch.h"
+
+/*
+open addressing hash table with 2^n table size
+quadratic probing is used in case of hash collision
+tab indices and hash are size_t
+after resize fails with ENOMEM the state of tab is still usable
+*/
+
+typedef struct htab_entry {
+	char *key;
+	htab_value data;
+} htab_entry;
+
+struct elem {
+	htab_entry item;
+	size_t hash;
+};
+
+struct htab {
+	struct elem *elems;
+	size_t mask;
+	size_t used;
+};
+
+#define MINSIZE 8
+#define MAXSIZE ((size_t)-1/2 + 1)
+
+#define CASE_INSENSITIVE
+#ifdef CASE_INSENSITIVE
+#include <ctype.h>
+#include <strings.h>
+#define LOWER_OR_NOT(X) tolower(X)
+#define STRCMP(X, Y) strcasecmp(X, Y)
+#else
+#define LOWER_OR_NOT(X) X
+#define STRCMP(X, Y) strcmp(X, Y)
+#endif
+
+static size_t keyhash(const char *k)
+{
+	const unsigned char *p = (const void *)k;
+	size_t h = 0;
+
+	while (*p)
+		h = 31*h + LOWER_OR_NOT(*p++);
+	return h;
+}
+
+static int resize(struct htab *htab, size_t nel)
+{
+	size_t newsize;
+	size_t i, j;
+	struct elem *e, *newe;
+	struct elem *oldtab = htab->elems;
+	struct elem *oldend = htab->elems + htab->mask + 1;
+
+	if (nel > MAXSIZE)
+		nel = MAXSIZE;
+	for (newsize = MINSIZE; newsize < nel; newsize *= 2);
+	htab->elems = calloc(newsize, sizeof *htab->elems);
+	if (!htab->elems) {
+		htab->elems = oldtab;
+		return 0;
+	}
+	htab->mask = newsize - 1;
+	if (!oldtab)
+		return 1;
+	for (e = oldtab; e < oldend; e++)
+		if (e->item.key) {
+			for (i=e->hash,j=1; ; i+=j++) {
+				newe = htab->elems + (i & htab->mask);
+				if (!newe->item.key)
+					break;
+			}
+			*newe = *e;
+		}
+	free(oldtab);
+	return 1;
+}
+
+static struct elem *lookup(struct htab *htab, const char *key, size_t hash)
+{
+	size_t i, j;
+	struct elem *e;
+
+	for (i=hash,j=1; ; i+=j++) {
+		e = htab->elems + (i & htab->mask);
+		if (!e->item.key ||
+		    (e->hash==hash && STRCMP(e->item.key, key)==0))
+			break;
+	}
+	return e;
+}
+
+struct htab *htab_create(size_t nel)
+{
+	struct htab *r = calloc(1, sizeof *r);
+	if(r && !resize(r, nel)) {
+		free(r);
+		r = 0;
+	}
+	return r;
+}
+
+void htab_destroy(struct htab *htab)
+{
+	free(htab->elems);
+	free(htab);
+}
+
+static htab_entry *htab_find_item(struct htab *htab, const char* key)
+{
+	size_t hash = keyhash(key);
+	struct elem *e = lookup(htab, key, hash);
+
+	if (e->item.key) {
+		return &e->item;
+	}
+	return 0;
+}
+
+htab_value* htab_find(struct htab *htab, const char* key)
+{
+	htab_entry *i = htab_find_item(htab, key);
+	if(i) return &i->data;
+	return 0;
+}
+
+int htab_delete(struct htab *htab, const char* key)
+{
+	htab_entry *i = htab_find_item(htab, key);
+	if(!i) return 0;
+	i->key = 0;
+	return 1;
+}
+
+int htab_insert(struct htab *htab, char* key, htab_value value)
+{
+	size_t hash = keyhash(key);
+	struct elem *e = lookup(htab, key, hash);
+	if(e->item.key) {
+		/* it's not allowed to overwrite existing data */
+		return 0;
+	}
+
+	e->item.key = key;
+	e->item.data = value;
+	e->hash = hash;
+	if (++htab->used > htab->mask - htab->mask/4) {
+		if (!resize(htab, 2*htab->used)) {
+			htab->used--;
+			e->item.key = 0;
+			return 0;
+		}
+	}
+	return 1;
+}
+
+size_t htab_next(struct htab *htab, size_t iterator, char** key, htab_value **v)
+{
+	size_t i;
+	for(i=iterator;i<htab->mask+1;++i) {
+		struct elem *e = htab->elems + i;
+		if(e->item.key) {
+			*key = e->item.key;
+			*v = &e->item.data;
+			return i+1;
+		}
+	}
+	return 0;
+}
diff --git a/src/hsearch.h b/src/hsearch.h
new file mode 100644
index 0000000..ec81cc3
--- /dev/null
+++ b/src/hsearch.h
@@ -0,0 +1,21 @@
+#ifndef HSEARCH_H
+#define HSEARCH_H
+
+#include <stdlib.h>
+
+typedef union htab_value {
+	void *p;
+	size_t n;
+} htab_value;
+
+#define HTV_N(N) (htab_value) {.n = N}
+#define HTV_P(P) (htab_value) {.p = P}
+
+struct htab * htab_create(size_t);
+void htab_destroy(struct htab *);
+htab_value* htab_find(struct htab *, const char* key);
+int htab_insert(struct htab *, char*, htab_value);
+int htab_delete(struct htab *htab, const char* key);
+size_t htab_next(struct htab *, size_t iterator, char** key, htab_value **v);
+
+#endif
diff --git a/src/orderedmap.c b/src/orderedmap.c
new file mode 100644
index 0000000..4902be0
--- /dev/null
+++ b/src/orderedmap.c
@@ -0,0 +1,110 @@
+#ifdef HAVE_CONFIG_H
+#  include <config.h>
+#else
+#  define _ALL_SOURCE
+#  define _GNU_SOURCE
+#endif
+#include <string.h>
+#include "sblist.h"
+#include "orderedmap.h"
+
+static void orderedmap_destroy_contents(struct orderedmap *o) {
+	char **p, *q;
+	size_t i;
+	htab_value *v;
+	if(!o) return;
+	if(o->values) {
+		while(sblist_getsize(o->values)) {
+			p = sblist_get(o->values, 0);
+			if(p) free(*p);
+			sblist_delete(o->values, 0);
+		}
+		sblist_free(o->values);
+	}
+	if(o->map) {
+		i = 0;
+		while((i = htab_next(o->map, i, &q, &v)))
+			free(q);
+		htab_destroy(o->map);
+	}
+}
+
+struct orderedmap *orderedmap_create(size_t nbuckets) {
+	struct orderedmap o = {0}, *new;
+	o.values = sblist_new(sizeof(void*), 32);
+	if(!o.values) goto oom;
+	o.map = htab_create(nbuckets);
+	if(!o.map) goto oom;
+	new = malloc(sizeof o);
+	if(!new) goto oom;
+	memcpy(new, &o, sizeof o);
+	return new;
+	oom:;
+	orderedmap_destroy_contents(&o);
+	return 0;
+}
+
+void* orderedmap_destroy(struct orderedmap *o) {
+	orderedmap_destroy_contents(o);
+	free(o);
+	return 0;
+}
+
+int orderedmap_append(struct orderedmap *o, const char *key, char *value) {
+	size_t index;
+	char *nk, *nv;
+	nk = nv = 0;
+	nk = strdup(key);
+	nv = strdup(value);
+	if(!nk || !nv) goto oom;
+	index = sblist_getsize(o->values);
+	if(!sblist_add(o->values, &nv)) goto oom;
+	if(!htab_insert(o->map, nk, HTV_N(index))) {
+		sblist_delete(o->values, index);
+		goto oom;
+	}
+	return 1;
+oom:;
+	free(nk);
+	free(nv);
+	return 0;
+}
+
+char* orderedmap_find(struct orderedmap *o, const char *key) {
+	char **p;
+	htab_value *v = htab_find(o->map, key);
+	if(!v) return 0;
+	p = sblist_get(o->values, v->n);
+	return p?*p:0;
+}
+
+int orderedmap_remove(struct orderedmap *o, const char *key) {
+	size_t i;
+	char *lk;
+	htab_value *lv, *v = htab_find(o->map, key);
+	if(!v) return 0;
+	htab_delete(o->map, key);
+	sblist_delete(o->values, v->n);
+	i = 0;
+	while((i = htab_next(o->map, i, &lk, &lv))) {
+		if(lv->n > v->n) lv->n--;
+	}
+	return 1;
+}
+
+size_t orderedmap_next(struct orderedmap *o, size_t iter, char** key, char** value) {
+	size_t h_iter;
+	htab_value* hval;
+	char **p;
+	if(iter < sblist_getsize(o->values)) {
+		h_iter = 0;
+		while((h_iter = htab_next(o->map, h_iter, key, &hval))) {
+			if(hval->n == iter) {
+				p = sblist_get(o->values, iter);
+				*value = p?*p:0;
+				return iter+1;
+			}
+		}
+	}
+	return 0;
+}
diff --git a/src/orderedmap.h b/src/orderedmap.h
new file mode 100644
index 0000000..e3f4b0e
--- /dev/null
+++ b/src/orderedmap.h
@@ -0,0 +1,20 @@
+#ifndef ORDEREDMAP_H
+#define ORDEREDMAP_H
+
+#include <stdlib.h>
+#include "sblist.h"
+#include "hsearch.h"
+
+typedef struct orderedmap {
+	sblist* values;
+	struct htab *map;
+} *orderedmap;
+
+struct orderedmap *orderedmap_create(size_t nbuckets);
+void* orderedmap_destroy(struct orderedmap *o);
+int orderedmap_append(struct orderedmap *o, const char *key, char *value );
+char* orderedmap_find(struct orderedmap *o, const char *key);
+int orderedmap_remove(struct orderedmap *o, const char *key);
+size_t orderedmap_next(struct orderedmap *o, size_t iter, char** key, char** value);
+
+#endif
diff --git a/src/reqs.c b/src/reqs.c
index e3c59c1..47bb304 100644
--- a/src/reqs.c
+++ b/src/reqs.c
@@ -33,6 +33,7 @@
 #include "conns.h"
 #include "filter.h"
 #include "hashmap.h"
+#include "orderedmap.h"
 #include "heap.h"
 #include "html-error.h"
 #include "log.h"
@@ -315,7 +316,7 @@ static int send_ssl_response (struct conn_s *connptr)
  * build a new request line. Finally connect to the remote server.
  */
 static struct request_s *process_request (struct conn_s *connptr,
-                                          hashmap_t hashofheaders)
+                                          orderedmap hashofheaders)
 {
         char *url;
         struct request_s *request;
@@ -596,7 +597,7 @@ static int add_xtinyproxy_header (struct conn_s *connptr)
  * can be retrieved and manipulated later.
  */
 static int
-add_header_to_connection (hashmap_t hashofheaders, char *header, size_t len)
+add_header_to_connection (orderedmap hashofheaders, char *header, size_t len)
 {
         char *sep;
 
@@ -614,7 +615,7 @@ add_header_to_connection (hashmap_t hashofheaders, char *header, size_t len)
         /* Calculate the new length of just the data */
         len -= sep - header - 1;
 
-        return hashmap_insert (hashofheaders, header, sep, len);
+        return orderedmap_append (hashofheaders, header, sep);
 }
 
 /*
@@ -627,7 +628,7 @@ add_header_to_connection (hashmap_t hashofheaders, char *header, size_t len)
 /*
  * Read all the headers from the stream
  */
-static int get_all_headers (int fd, hashmap_t hashofheaders)
+static int get_all_headers (int fd, orderedmap hashofheaders)
 {
         char *line = NULL;
         char *header = NULL;
@@ -720,7 +721,7 @@ static int get_all_headers (int fd, hashmap_t hashofheaders)
  * Extract the headers to remove.  These headers were listed in the Connection
  * and Proxy-Connection headers.
  */
-static int remove_connection_headers (hashmap_t hashofheaders)
+static int remove_connection_headers (orderedmap hashofheaders)
 {
         static const char *headers[] = {
                 "connection",
@@ -734,12 +735,13 @@ static int remove_connection_headers (hashmap_t hashofheaders)
 
         for (i = 0; i != (sizeof (headers) / sizeof (char *)); ++i) {
                 /* Look for the connection header.  If it's not found, return. */
-                len =
-                    hashmap_entry_by_key (hashofheaders, headers[i],
-                                          (void **) &data);
-                if (len <= 0)
+                data = orderedmap_find(hashofheaders, headers[i]);
+
+                if (!data)
                         return 0;
 
+                len = strlen(data);
+
                 /*
                  * Go through the data line and replace any special characters
                  * with a NULL.
@@ -754,7 +756,7 @@ static int remove_connection_headers (hashmap_t hashofheaders)
                  */
                 ptr = data;
                 while (ptr < data + len) {
-                        hashmap_remove (hashofheaders, ptr);
+                        orderedmap_remove (hashofheaders, ptr);
 
                         /* Advance ptr to the next token */
                         ptr += strlen (ptr) + 1;
@@ -763,7 +765,7 @@ static int remove_connection_headers (hashmap_t hashofheaders)
                 }
 
                 /* Now remove the connection header it self. */
-                hashmap_remove (hashofheaders, headers[i]);
+                orderedmap_remove (hashofheaders, headers[i]);
         }
 
         return 0;
@@ -773,16 +775,14 @@ static int remove_connection_headers (hashmap_t hashofheaders)
  * If there is a Content-Length header, then return the value; otherwise, return
  * a negative number.
  */
-static long get_content_length (hashmap_t hashofheaders)
+static long get_content_length (orderedmap hashofheaders)
 {
-        ssize_t len;
         char *data;
         long content_length = -1;
 
-        len =
-            hashmap_entry_by_key (hashofheaders, "content-length",
-                                  (void **) &data);
-        if (len > 0)
+        data = orderedmap_find (hashofheaders, "content-length");
+
+        if (data)
                 content_length = atol (data);
 
         return content_length;
@@ -796,10 +796,9 @@ static long get_content_length (hashmap_t hashofheaders)
  * purposes.
  */
 static int
-write_via_header (int fd, hashmap_t hashofheaders,
+write_via_header (int fd, orderedmap hashofheaders,
                   unsigned int major, unsigned int minor)
 {
-        ssize_t len;
         char hostname[512];
         char *data;
         int ret;
@@ -819,14 +818,14 @@ write_via_header (int fd, hashmap_t hashofheaders,
          * See if there is a "Via" header.  If so, again we need to do a bit
          * of processing.
          */
-        len = hashmap_entry_by_key (hashofheaders, "via", (void **) &data);
-        if (len > 0) {
+        data = orderedmap_find (hashofheaders, "via");
+        if (data) {
                 ret = write_message (fd,
                                      "Via: %s, %hu.%hu %s (%s/%s)\r\n",
                                      data, major, minor, hostname, PACKAGE,
                                      VERSION);
 
-                hashmap_remove (hashofheaders, "via");
+                orderedmap_remove (hashofheaders, "via");
         } else {
                 ret = write_message (fd,
                                      "Via: %hu.%hu %s (%s/%s)\r\n",
@@ -840,7 +839,7 @@ done:
 /*
  * Number of buckets to use internally in the hashmap.
  */
-#define HEADER_BUCKETS 256
+#define HEADER_BUCKETS 32
 
 /*
  * Here we loop through all the headers the client is sending. If we
@@ -849,7 +848,7 @@ done:
  *	- rjkaes
  */
 static int
-process_client_headers (struct conn_s *connptr, hashmap_t hashofheaders)
+process_client_headers (struct conn_s *connptr, orderedmap hashofheaders)
 {
         static const char *skipheaders[] = {
                 "host",
@@ -860,7 +859,7 @@ process_client_headers (struct conn_s *connptr, hashmap_t hashofheaders)
                 "upgrade"
         };
         int i;
-        hashmap_iter iter;
+        size_t iter;
         int ret = 0;
 
         char *data, *header;
@@ -893,7 +892,7 @@ process_client_headers (struct conn_s *connptr, hashmap_t hashofheaders)
          * Delete the headers listed in the skipheaders list
          */
         for (i = 0; i != (sizeof (skipheaders) / sizeof (char *)); i++) {
-                hashmap_remove (hashofheaders, skipheaders[i]);
+                orderedmap_remove (hashofheaders, skipheaders[i]);
         }
 
         /* Send, or add the Via header */
@@ -913,27 +912,22 @@ process_client_headers (struct conn_s *connptr, hashmap_t hashofheaders)
         /*
          * Output all the remaining headers to the remote machine.
          */
-        iter = hashmap_first (hashofheaders);
-        if (iter >= 0) {
-                for (; !hashmap_is_end (hashofheaders, iter); ++iter) {
-                        hashmap_return_entry (hashofheaders,
-                                              iter, &data, (void **) &header);
-
-                        if (!is_anonymous_enabled (config)
-                            || anonymous_search (config, data) > 0) {
-                                ret =
-                                    write_message (connptr->server_fd,
-                                                   "%s: %s\r\n", data, header);
-                                if (ret < 0) {
-                                        indicate_http_error (connptr, 503,
-                                                             "Could not send data to remote server",
-                                                             "detail",
-                                                             "A network error occurred while "
-                                                             "trying to write data to the "
-                                                             "remote web server.",
-                                                             NULL);
-                                        goto PULL_CLIENT_DATA;
-                                }
+        iter = 0;
+        while((iter = orderedmap_next(hashofheaders, iter, &data, &header))) {
+                if (!is_anonymous_enabled (config)
+                    || anonymous_search (config, data) > 0) {
+                        ret =
+                            write_message (connptr->server_fd,
+                                           "%s: %s\r\n", data, header);
+                        if (ret < 0) {
+                                indicate_http_error (connptr, 503,
+                                                     "Could not send data to remote server",
+                                                     "detail",
+                                                     "A network error occurred while "
+                                                     "trying to write data to the "
+                                                     "remote web server.",
+                                                     NULL);
+                                goto PULL_CLIENT_DATA;
                         }
                 }
         }
@@ -973,8 +967,8 @@ static int process_server_headers (struct conn_s *connptr)
 
         char *response_line;
 
-        hashmap_t hashofheaders;
-        hashmap_iter iter;
+        orderedmap hashofheaders;
+        size_t iter;
         char *data, *header;
         ssize_t len;
         int i;
@@ -1003,7 +997,7 @@ retry:
                 goto retry;
         }
 
-        hashofheaders = hashmap_create (HEADER_BUCKETS);
+        hashofheaders = orderedmap_create (HEADER_BUCKETS);
         if (!hashofheaders) {
                 safefree (response_line);
                 return -1;
@@ -1015,7 +1009,7 @@ retry:
         if (get_all_headers (connptr->server_fd, hashofheaders) < 0) {
                 log_message (LOG_WARNING,
                              "Could not retrieve all the headers from the remote server.");
-                hashmap_delete (hashofheaders);
+                orderedmap_destroy (hashofheaders);
                 safefree (response_line);
 
                 indicate_http_error (connptr, 503,
@@ -1034,7 +1028,7 @@ retry:
          * Instead we'll free all the memory and return.
          */
         if (connptr->protocol.major < 1) {
-                hashmap_delete (hashofheaders);
+                orderedmap_destroy (hashofheaders);
                 safefree (response_line);
                 return 0;
         }
@@ -1061,7 +1055,7 @@ retry:
          * Delete the headers listed in the skipheaders list
          */
         for (i = 0; i != (sizeof (skipheaders) / sizeof (char *)); i++) {
-                hashmap_remove (hashofheaders, skipheaders[i]);
+                orderedmap_remove (hashofheaders, skipheaders[i]);
         }
 
         /* Send, or add the Via header */
@@ -1083,8 +1077,7 @@ retry:
 
         /* Rewrite the HTTP redirect if needed */
         if (config->reversebaseurl &&
-            hashmap_entry_by_key (hashofheaders, "location",
-                                  (void **) &header) > 0) {
+            (header = orderedmap_find (hashofheaders, "location"))) {
 
                 /* Look for a matching entry in the reversepath list */
                 while (reverse) {
@@ -1109,7 +1102,7 @@ retry:
                                      "Rewriting HTTP redirect: %s -> %s%s%s",
                                      header, config->reversebaseurl,
                                      (reverse->path + 1), (header + len));
-                        hashmap_remove (hashofheaders, "location");
+                        orderedmap_remove (hashofheaders, "location");
                 }
         }
 #endif
@@ -1117,19 +1110,15 @@ retry:
         /*
          * All right, output all the remaining headers to the client.
          */
-        iter = hashmap_first (hashofheaders);
-        if (iter >= 0) {
-                for (; !hashmap_is_end (hashofheaders, iter); ++iter) {
-                        hashmap_return_entry (hashofheaders,
-                                              iter, &data, (void **) &header);
-
-                        ret = write_message (connptr->client_fd,
-                                             "%s: %s\r\n", data, header);
-                        if (ret < 0)
-                                goto ERROR_EXIT;
-                }
+        iter = 0;
+        while ((iter = orderedmap_next(hashofheaders, iter, &data, &header))) {
+
+                ret = write_message (connptr->client_fd,
+                                     "%s: %s\r\n", data, header);
+                if (ret < 0)
+                        goto ERROR_EXIT;
         }
-        hashmap_delete (hashofheaders);
+        orderedmap_destroy (hashofheaders);
 
         /* Write the final blank line to signify the end of the headers */
         if (safe_write (connptr->client_fd, "\r\n", 2) < 0)
@@ -1138,7 +1127,7 @@ retry:
         return 0;
 
 ERROR_EXIT:
-        hashmap_delete (hashofheaders);
+        orderedmap_destroy (hashofheaders);
         return -1;
 }
 
@@ -1532,7 +1521,7 @@ void handle_connection (int fd, union sockaddr_union* addr)
         struct conn_s *connptr;
         struct request_s *request = NULL;
         struct timeval tv;
-        hashmap_t hashofheaders = NULL;
+        orderedmap hashofheaders = NULL;
 
         char sock_ipaddr[IP_LENGTH];
         char peer_ipaddr[IP_LENGTH];
@@ -1597,7 +1586,7 @@ void handle_connection (int fd, union sockaddr_union* addr)
         /*
          * The "hashofheaders" store the client's headers.
          */
-        hashofheaders = hashmap_create (HEADER_BUCKETS);
+        hashofheaders = orderedmap_create (HEADER_BUCKETS);
         if (hashofheaders == NULL) {
                 update_stats (STAT_BADCONN);
                 indicate_http_error (connptr, 503, "Internal error",
@@ -1624,23 +1613,19 @@ void handle_connection (int fd, union sockaddr_union* addr)
         got_headers = 1;
 
         if (config->basicauth_list != NULL) {
-                ssize_t len;
                 char *authstring;
                 int failure = 1, stathost_connect = 0;
-                len = hashmap_entry_by_key (hashofheaders, "proxy-authorization",
-                                            (void **) &authstring);
-
-                if (len == 0 && config->stathost) {
-                        len = hashmap_entry_by_key (hashofheaders, "host",
-                                                    (void **) &authstring);
-                        if (len && !strncmp(authstring, config->stathost, strlen(config->stathost))) {
-                                len = hashmap_entry_by_key (hashofheaders, "authorization",
-                                                            (void **) &authstring);
+                authstring = orderedmap_find (hashofheaders, "proxy-authorization");
+
+                if (!authstring && config->stathost) {
+                        authstring = orderedmap_find (hashofheaders, "host");
+                        if (authstring && !strncmp(authstring, config->stathost, strlen(config->stathost))) {
+                                authstring = orderedmap_find (hashofheaders, "authorization");
                                 stathost_connect = 1;
-                        } else len = 0;
+                        } else authstring = 0;
                 }
 
-                if (len == 0) {
+                if (!authstring) {
                         if (stathost_connect) goto e401;
                         update_stats (STAT_DENIED);
                         indicate_http_error (connptr, 407, "Proxy Authentication Required",
@@ -1664,7 +1649,7 @@ e401:
                                              NULL);
                         HC_FAIL();
                 }
-                hashmap_remove (hashofheaders, "proxy-authorization");
+                orderedmap_remove (hashofheaders, "proxy-authorization");
         }
 
         /*
@@ -1675,9 +1660,7 @@ e401:
                 http_header_t *header = (http_header_t *)
                         vector_getentry (config->add_headers, i, NULL);
 
-                hashmap_insert (hashofheaders,
-                                header->name,
-                                header->value, strlen (header->value) + 1);
+                orderedmap_append (hashofheaders, header->name, header->value);
         }
 
         request = process_request (connptr, hashofheaders);
@@ -1755,7 +1738,7 @@ e401:
 
 done:
         free_request_struct (request);
-        hashmap_delete (hashofheaders);
+        orderedmap_destroy (hashofheaders);
         destroy_conn (connptr);
         return;
 #undef HC_FAIL
diff --git a/src/reverse-proxy.c b/src/reverse-proxy.c
index 32bd2a7..af58d56 100644
--- a/src/reverse-proxy.c
+++ b/src/reverse-proxy.c
@@ -111,7 +111,7 @@ void free_reversepath_list (struct reversepath *reverse)
 /*
  * Rewrite the URL for reverse proxying.
  */
-char *reverse_rewrite_url (struct conn_s *connptr, hashmap_t hashofheaders,
+char *reverse_rewrite_url (struct conn_s *connptr, orderedmap hashofheaders,
                            char *url)
 {
         char *rewrite_url = NULL;
@@ -130,9 +130,8 @@ char *reverse_rewrite_url (struct conn_s *connptr, hashmap_t hashofheaders,
                         strcpy (rewrite_url, reverse->url);
                         strcat (rewrite_url, url + strlen (reverse->path));
                 } else if (config->reversemagic
-                           && hashmap_entry_by_key (hashofheaders,
-                                                    "cookie",
-                                                    (void **) &cookie) > 0) {
+                           && (cookie = orderedmap_find (hashofheaders,
+                                                    "cookie"))) {
 
                         /* No match - try the magical tracking cookie next */
                         if ((cookieval = strstr (cookie, REVERSE_COOKIE "="))
diff --git a/src/reverse-proxy.h b/src/reverse-proxy.h
index 64b4acd..a2d6619 100644
--- a/src/reverse-proxy.h
+++ b/src/reverse-proxy.h
@@ -22,6 +22,7 @@
 #define TINYPROXY_REVERSE_PROXY_H
 
 #include "conns.h"
+#include "orderedmap.h"
 
 struct reversepath {
         struct reversepath *next;
@@ -37,6 +38,6 @@ extern struct reversepath *reversepath_get (char *url,
                                             struct reversepath *reverse);
 void free_reversepath_list (struct reversepath *reverse);
 extern char *reverse_rewrite_url (struct conn_s *connptr,
-                                  hashmap_t hashofheaders, char *url);
+                                  orderedmap hashofheaders, char *url);
 
 #endif
diff --git a/src/transparent-proxy.c b/src/transparent-proxy.c
index 2c1e069..e40bce2 100644
--- a/src/transparent-proxy.c
+++ b/src/transparent-proxy.c
@@ -53,7 +53,7 @@ static int build_url (char **url, const char *host, int port, const char *path)
 }
 
 int
-do_transparent_proxy (struct conn_s *connptr, hashmap_t hashofheaders,
+do_transparent_proxy (struct conn_s *connptr, orderedmap hashofheaders,
                       struct request_s *request, struct config_s *conf,
                       char **url)
 {
@@ -62,8 +62,8 @@ do_transparent_proxy (struct conn_s *connptr, hashmap_t hashofheaders,
         size_t ulen = strlen (*url);
         ssize_t i;
 
-        length = hashmap_entry_by_key (hashofheaders, "host", (void **) &data);
-        if (length <= 0) {
+        data = orderedmap_find (hashofheaders, "host");
+        if (!data) {
                 union sockaddr_union dest_addr;
                 const void *dest_inaddr;
                 char namebuf[INET6_ADDRSTRLEN+1];
@@ -102,6 +102,7 @@ do_transparent_proxy (struct conn_s *connptr, hashmap_t hashofheaders,
                              "process_request: trans IP %s %s for %d",
                              request->method, *url, connptr->client_fd);
         } else {
+                length = strlen (data);
                 request->host = (char *) safemalloc (length + 1);
                 if (sscanf (data, "%[^:]:%hu", request->host, &request->port) !=
                     2) {
diff --git a/src/transparent-proxy.h b/src/transparent-proxy.h
index 4fc3a4d..b56c446 100644
--- a/src/transparent-proxy.h
+++ b/src/transparent-proxy.h
@@ -26,11 +26,11 @@
 #ifdef TRANSPARENT_PROXY
 
 #include "conns.h"
-#include "hashmap.h"
+#include "orderedmap.h"
 #include "reqs.h"
 
 extern int do_transparent_proxy (struct conn_s *connptr,
-                                 hashmap_t hashofheaders,
+                                 orderedmap hashofheaders,
                                  struct request_s *request,
                                  struct config_s *config, char **url);