From 1cbd42cfe6fd2bcd8bca52aef4ee3a047d58ab6c Mon Sep 17 00:00:00 2001
From: Nathan Wagner <nw@hydaspes.if.org>
Date: Mon, 17 Sep 2018 12:05:35 +0000
Subject: [PATCH] fix table resize bug in jsw_hlib

---
 lib/jsw/jsw_hlib.c | 78 +++++++++++++++++++++++++++++++++++++---------
 1 file changed, 63 insertions(+), 15 deletions(-)

diff --git a/lib/jsw/jsw_hlib.c b/lib/jsw/jsw_hlib.c
index a3a7a13..4cd9f8f 100644
--- a/lib/jsw/jsw_hlib.c
+++ b/lib/jsw/jsw_hlib.c
@@ -6,9 +6,11 @@
       Added a cast for malloc to enable clean
       compilation as C++
 */
+#include <stdlib.h>
+#include <string.h>
+
 #include "jsw_hlib.h"
 
-#include <stdlib.h>
 
 typedef struct jsw_node {
   void            *key;  /* Key used for searching */
@@ -35,6 +37,25 @@ struct jsw_hash {
   itemrel_f    itemrel;  /* User defined item delete function */
 };
 
+static unsigned int default_hash(const void *key) {
+	const unsigned char *p = key;
+	unsigned h = 0;
+	int i;
+	int len = strlen((char *)p);
+
+	for (i = 0; i < len; i++) {
+		h += p[i];
+		h += (h << 10);
+		h ^= (h >> 6);
+	}
+
+	h += (h << 3);
+	h ^= (h >> 11);
+	h += (h << 15);
+
+	return h;
+}
+
 static jsw_node_t *new_node ( void *key, void *item, jsw_node_t *next )
 {
   jsw_node_t *node = malloc ( sizeof *node );
@@ -93,7 +114,7 @@ jsw_hash_t  *jsw_hnew ( size_t size, hash_f hash, cmp_f cmp,
   htab->capacity = size;
   htab->curri = 0;
   htab->currl = NULL;
-  htab->hash = hash;
+  htab->hash = hash ? hash : default_hash;
   htab->cmp = cmp;
   htab->keydup = keydup;
   htab->itemdup = itemdup;
@@ -154,6 +175,25 @@ void *jsw_hfind ( jsw_hash_t *htab, void *key )
   return NULL;
 }
 
+static int insert_item(jsw_head_t **table, jsw_node_t *item, unsigned int chain) {
+	/* Create a chain if the bucket is empty */
+	if ( table[chain] == NULL ) {
+		table[chain] = new_chain();
+	}
+
+	if ( table[chain] == NULL ) {
+		return 0;
+	}
+
+	/* Insert at the front of the chain */
+	item->next = table[chain]->first;
+	table[chain]->first = item;
+
+	++table[chain]->size;
+
+	return 1;
+}
+
 /*
   Insert an item with the selected key
 
@@ -271,28 +311,36 @@ int jsw_herase ( jsw_hash_t *htab, void *key )
 */
 int jsw_hresize ( jsw_hash_t *htab, size_t new_size )
 {
-  jsw_hash_t *new_htab;
   jsw_node_t *it;
+  jsw_head_t **newtable;
   size_t i;
+  unsigned int bucket;
 
-  /* Build a new hash table, then assign it to the old one */
-  new_htab = jsw_hnew ( new_size, htab->hash, htab->cmp,
-    htab->keydup, htab->itemdup, htab->keyrel, htab->itemrel );
+  if (new_size == htab->capacity) {
+	  return 1;
+  }
 
-  if ( new_htab == NULL )
-    return 0;
+  newtable = malloc(new_size * sizeof *htab->table);
+
+  if (!newtable) {
+	  return 0;
+  }
+
+  for(i=0; i < new_size; i++) {
+	  newtable[i] = 0;
+  }
 
   for ( i = 0; i < htab->capacity; i++ ) {
-    if ( htab->table[i] == NULL )
-      continue;
+	  if ( htab->table[i] == NULL ) continue;
 
-    for ( it = htab->table[i]->first; it != NULL; it = it->next )
-      jsw_hinsert ( new_htab, it->key, it->item );
+	  for ( it = htab->table[i]->first; it != NULL; it = it->next ) {
+		  bucket = htab->hash(it->key) % new_size;
+		  insert_item(newtable, it, bucket);
+	  }
   }
 
-  /* A hash table holds copies, so release the old table */
-  jsw_hdelete ( htab );
-  htab = new_htab;
+  htab->capacity = new_size;
+  htab->table = newtable;
 
   return 1;
 }
-- 
2.40.0