From 141d3b5c2a93dd48096a13ce051d09eaf3ec0b4a Mon Sep 17 00:00:00 2001
From: sin <sin@2f30.org>
Date: Thu, 27 Mar 2014 11:20:17 +0000
Subject: [PATCH] remove struct elem entirely from hsearch.c

There are two changes here, both of which make sense to be done in a
single patch:

- Remove hash from struct elem and compute it at runtime wherever
  necessary.
- Eliminate struct elem and use ENTRY directly.

As a result we cut down on the memory usage as each element in the
hash table now contains only an ENTRY not an ENTRY + size_t for the
hash. The downside is that the hash needs to be computed at runtime.
---
 src/search/hsearch.c | 51 +++++++++++++++++++-------------------------
 1 file changed, 22 insertions(+), 29 deletions(-)

diff --git a/src/search/hsearch.c b/src/search/hsearch.c
index 88edb263..5c896511 100644
--- a/src/search/hsearch.c
+++ b/src/search/hsearch.c
@@ -16,13 +16,8 @@ with the posix api items cannot be iterated and length cannot be queried
 #define MINSIZE 8
 #define MAXSIZE ((size_t)-1/2 + 1)
 
-struct elem {
-	ENTRY item;
-	size_t hash;
-};
-
 struct __tab {
-	struct elem *elems;
+	ENTRY *entries;
 	size_t mask;
 	size_t used;
 };
@@ -47,26 +42,26 @@ static int resize(size_t nel, struct hsearch_data *htab)
 {
 	size_t newsize;
 	size_t i, j;
-	struct elem *e, *newe;
-	struct elem *oldtab = htab->__tab->elems;
-	struct elem *oldend = htab->__tab->elems + htab->__tab->mask + 1;
+	ENTRY *e, *newe;
+	ENTRY *oldtab = htab->__tab->entries;
+	ENTRY *oldend = htab->__tab->entries + htab->__tab->mask + 1;
 
 	if (nel > MAXSIZE)
 		nel = MAXSIZE;
 	for (newsize = MINSIZE; newsize < nel; newsize *= 2);
-	htab->__tab->elems = calloc(newsize, sizeof *htab->__tab->elems);
-	if (!htab->__tab->elems) {
-		htab->__tab->elems = oldtab;
+	htab->__tab->entries = calloc(newsize, sizeof *htab->__tab->entries);
+	if (!htab->__tab->entries) {
+		htab->__tab->entries = oldtab;
 		return 0;
 	}
 	htab->__tab->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->__tab->elems + (i & htab->__tab->mask);
-				if (!newe->item.key)
+		if (e->key) {
+			for (i=keyhash(e->key),j=1; ; i+=j++) {
+				newe = htab->__tab->entries + (i & htab->__tab->mask);
+				if (!newe->key)
 					break;
 			}
 			*newe = *e;
@@ -85,15 +80,14 @@ void hdestroy(void)
 	__hdestroy_r(&htab);
 }
 
-static struct elem *lookup(char *key, size_t hash, struct hsearch_data *htab)
+static ENTRY *lookup(char *key, size_t hash, struct hsearch_data *htab)
 {
 	size_t i, j;
-	struct elem *e;
+	ENTRY *e;
 
 	for (i=hash,j=1; ; i+=j++) {
-		e = htab->__tab->elems + (i & htab->__tab->mask);
-		if (!e->item.key ||
-		    (e->hash==hash && strcmp(e->item.key, key)==0))
+		e = htab->__tab->entries + (i & htab->__tab->mask);
+		if (!e->key || strcmp(e->key, key) == 0)
 			break;
 	}
 	return e;
@@ -125,7 +119,7 @@ weak_alias(__hcreate_r, hcreate_r);
 
 void __hdestroy_r(struct hsearch_data *htab)
 {
-	if (htab->__tab) free(htab->__tab->elems);
+	if (htab->__tab) free(htab->__tab->entries);
 	free(htab->__tab);
 	htab->__tab = 0;
 }
@@ -134,28 +128,27 @@ weak_alias(__hdestroy_r, hdestroy_r);
 int __hsearch_r(ENTRY item, ACTION action, ENTRY **retval, struct hsearch_data *htab)
 {
 	size_t hash = keyhash(item.key);
-	struct elem *e = lookup(item.key, hash, htab);
+	ENTRY *e = lookup(item.key, hash, htab);
 
-	if (e->item.key) {
-		*retval = &e->item;
+	if (e->key) {
+		*retval = e;
 		return 1;
 	}
 	if (action == FIND) {
 		*retval = 0;
 		return 0;
 	}
-	e->item = item;
-	e->hash = hash;
+	*e = item;
 	if (++htab->__tab->used > htab->__tab->mask - htab->__tab->mask/4) {
 		if (!resize(2*htab->__tab->used, htab)) {
 			htab->__tab->used--;
-			e->item.key = 0;
+			e->key = 0;
 			*retval = 0;
 			return 0;
 		}
 		e = lookup(item.key, hash, htab);
 	}
-	*retval = &e->item;
+	*retval = e;
 	return 1;
 }
 weak_alias(__hsearch_r, hsearch_r);
-- 
2.25.1