a little more is done

1 files changed, 85 insertions, 20 deletions

diff --git a/src/htgen.h b/src/htgen.h
index 0b03886..f3e57c3 100644
--- a/src/htgen.h
+++ b/src/htgen.h
@@ -17,7 +17,7 @@
 /* or define a static load factor: #define HT_LOADFACTOR (0.75f) */
 
 /* should take HT_VALTYPE_CREF and return HT_VALTYPE */
-#define HT_VAL_COPY(_val, _sz) _strdup(_val)
+#define HT_VAL_COPY(_val, _sz) strdup(_val)
 
 /* #define HT_VAL_STATIC_LEN sizeof(int) */
 #define HT_VAL_GUESS_LEN(_val) strlen(_val)
@@ -32,11 +32,15 @@
 /* bad equality function LOL */
 #define HT_KEY_EQ(_val1, _len1, _val2, _len2) (((_len1) == (_len2)) && !strcmp(_val1, _val2))
 
-#define HT_KEY_COPY(_key, _sz) (_strdup(_key))
+#define HT_KEY_COPY(_key, _sz) (strdup(_key))
 #define HT_KEY_FREE(_key) free(_key)
 
 /* #define HT_KEY_STATIC_LEN sizeof(int) */
 #define HT_KEY_GUESS_LEN(_val) strlen(_val)
+
+#define HT_KEY_FMT "%s"
+#define HT_VAL_FMT "%s"
+
 #else
 
 XXH64_hash_t ihash_hash_int(int i)
@@ -49,7 +53,7 @@ XXH64_hash_t ihash_hash_int(int i)
 #define HT_VALTYPE_CREF int
 
 #define HT_HASHTYPE XXH64_hash_t
-#define HT_VAL_HASH(_val, _sz) ihash_hash_int(_val)
+#define HT_KEY_HASH(_val, _sz) ihash_hash_int(_val)
 
 #define HT_VAL_COPY(_val, _sz) _val
 
@@ -57,10 +61,18 @@ XXH64_hash_t ihash_hash_int(int i)
 #define HT_VAL_STATIC_LEN sizeof(int)
 
 /* will receive two HT_KEYTYPEs */
-#define HT_KEY_EQ(_val1, _val2) ((_val1) == (_val2))
+#define HT_KEY_EQ(_val1, _sz1, _val2, _sz2) ((_val1) == (_val2))
 
 #define HT_KEYTYPE int
 #define HT_KEYTYPE_CREF int
+
+#define HT_KEY_COPY(_key, _sz) _key
+#define HT_KEY_FREE(_key)
+#define HT_KEY_STATIC_LEN sizeof(int)
+
+#define HT_KEY_FMT "%d"
+#define HT_VAL_FMT "%d"
+
 #endif
 
 #define HT_MALLOC(_sz) malloc(_sz)
@@ -98,6 +110,8 @@ HT__TYPE *HT__NS(create)(HT__CREATE_SIG);
 
 void HT__NS(free)(HT__TYPE *ht);
 
+void HT__NS(clear)(HT__TYPE *ht);
+
 HT_VALTYPE HT__NS(get)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found);
 HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found);
 
@@ -149,7 +163,7 @@ HT_VALTYPE HT__NS(swapn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VA
 #endif
 
 #ifndef HT_VAL_SENTINEL
-#define HT_VAL_SENTINEL((HT_VALTYPE)0)
+#define HT_VAL_SENTINEL ((HT_VALTYPE)0)
 #endif
 
 #define HT__HASHTYPE HT__NS(_hash_t)
@@ -187,6 +201,13 @@ struct HT__TAG {
 	HT__NODE *table;
 };
 
+size_t HT__NS(_next_po2)(size_t in)
+{
+  size_t n = 1;
+  while (n && n < in) n <<= 1;
+  return n;
+}
+
 HT__TYPE *HT__NS(new)(void)
 {
 #ifdef HT__LOADFACTOR_FIXED
@@ -211,7 +232,11 @@ HT__TYPE *HT__NS(create)(HT__CREATE_SIG)
 	ht->load_factor = load_factor;
 #endif
 
-	if (cap == 0) cap = 16;
+	if (cap == 0) {
+    cap = 16;
+  } else {
+    cap = HT__NS(_next_po2)(cap);
+  }
 
 	ht->capacity = cap;
 	ht->table = HT_CALLOC(cap, sizeof(HT__NODE));
@@ -229,24 +254,38 @@ cleanup:
 
 void HT__NS(free)(HT__TYPE *ht)
 {
-	/* TODO: free all elements */
 	if (!ht) return;
 
+  HT__NS(clear)(ht);
+
 	free(ht->table);
 	free(ht);
 }
 
-HT__NODE *HT__NS(_search)(HT__TYPE *ht, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, bool vacant)
+void HT__NS(clear)(HT__TYPE *ht)
+{
+  for (size_t idx = 0; idx < ht->capacity; ++idx) {
+    if (!ht->table[idx].full || ht->table[idx].deleted) continue;
+
+    HT_KEY_FREE(ht->table[idx].key);
+    HT_VAL_FREE(ht->table[idx].val);
+    ht->table[idx].full = false;
+  }
+
+  ht->asize = ht->rsize = 0;
+}
+
+HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, bool vacant)
 {
-	size_t tryidx = (size_t)((uintmax_t)hash % ht->capacity);
+	size_t tryidx = (size_t)((uintmax_t)hash % tablecap);
 	size_t start = tryidx;
 
 	HT__NODE *node;
 
-	fprintf(stderr, "debug: trying %zu for %s\n", tryidx, key);
+	fprintf(stderr, "debug: trying %zu for " HT_KEY_FMT "\n", tryidx, key);
 
 	do {
-		node = ht->table + tryidx;
+		node = table + tryidx;
 
 		if (node->full && !node->deleted && node->hash == hash && HT_KEY_EQ(node->key, HT__NODE_KEYLEN(node), key, keylen)) {
 			fprintf(stderr, "found node %zu: matches\n", tryidx);
@@ -260,7 +299,7 @@ HT__NODE *HT__NS(_search)(HT__TYPE *ht, const HT__HASHTYPE hash, HT_KEYTYPE_CREF
 			}
 		}
 
-		tryidx = (tryidx + 1) % ht->capacity;
+		tryidx = (tryidx + 1) % tablecap;
 	} while (tryidx != start);
 
 	return NULL;
@@ -326,6 +365,33 @@ int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_
 	return 0;
 }
 
+int HT__NS(_rehash)(HT__TYPE *ht, size_t newcap)
+{
+  HT__NODE *newtab = HT_CALLOC(newcap, sizeof(HT__NODE));
+  if (!newtab) return -1;
+
+  for (size_t idx = 0; idx < ht->capacity; ++idx) {
+    if (!ht->table[idx].full || ht->table[idx].deleted) continue;
+
+    HT__NODE *node = HT__NS(_search)(newtab, newcap, ht->table[idx].hash, ht->table[idx].key, HT__NODE_KEYLEN(ht->table + idx), true);
+    if (!node) goto cleanup;
+
+    memcpy(node, ht->table + idx, sizeof(HT__NODE));
+  }
+
+  HT_FREE(ht->table); /* point of no return */
+
+  ht->table = newtab;
+  ht->capacity = newcap;
+  ht->rsize = ht->asize;
+
+  return 0;
+
+cleanup:
+  HT_FREE(newtab);
+  return -1;
+}
+
 int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val)
 {
 	return HT__NS(putn)(ht, key, 0, val, 0);
@@ -333,17 +399,16 @@ int HT__NS(put)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val)
 
 int HT__NS(putn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen)
 {
+  if (ht->capacity * HT__LOADFACTOR(ht) < (ht->asize + 1)) {
+    if (HT__NS(_rehash)(ht, ht->capacity << 1) < 0) return -1;
+	}
+
 	if (!keylen) keylen = HT__GUESS_KEYLEN(key);
 	if (!vallen) vallen = HT__GUESS_VALLEN(val);
 
 	const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);
 
-	if (ht->capacity * HT__LOADFACTOR(ht) < (ht->asize + 1)) {
-		/* TODO: rehash */
-		fprintf(stderr, "Not rehashing (cap %zu, asize %zu)\n", ht->capacity, ht->asize);
-	}
-
-	HT__NODE *node = HT__NS(_search)(ht, hash, key, keylen, true);
+	HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, true);
 
 	if (!node) { /* no vacant slots found */
 		return -1; /* table is full or something! */
@@ -362,7 +427,7 @@ HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *
 	if (!keylen) keylen = HT__GUESS_KEYLEN(key);
 
 	const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen);
-	HT__NODE *node = HT__NS(_search)(ht, hash, key, keylen, false);
+	HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false);
 
 	if (!node) {
 		if (found) *found = false;
@@ -384,7 +449,7 @@ void HT__NS(_debug_table)(HT__TYPE *ht)
 			if (ht->table[n].deleted) {
 				fprintf(stderr, "(deleted)\n");
 			} else {
-				fprintf(stderr, "(full %s:%s)\n", ht->table[n].key, ht->table[n].val);
+				fprintf(stderr, "(full " HT_KEY_FMT ":" HT_VAL_FMT ")\n", ht->table[n].key, ht->table[n].val);
 			}
 		} else {
 			fprintf(stderr, "(empty)\n");