summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--src/htgen.h105
-rw-r--r--src/libmain.c33
2 files changed, 118 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");
diff --git a/src/libmain.c b/src/libmain.c
index eca383a..0801969 100644
--- a/src/libmain.c
+++ b/src/libmain.c
@@ -7,15 +7,21 @@
#define HT_IMPLEMENTATIONS
#include "htgen.h"
+#if 1
int main(int argc, char **argv) {
shash_t *hash = shash_create(8, 0.75f);
printf("%d\n", shash_put(hash, "test1", "test2"));
printf("%d\n", shash_put(hash, "abc", "def"));
+ shash__debug_table(hash);
printf("%d\n", shash_put(hash, "amingus", "val"));
printf("%d\n", shash_put(hash, "afungus", "val2"));
printf("%d\n", shash_put(hash, "abungus", "val3"));
+ shash__debug_table(hash);
printf("%d\n", shash_put(hash, "lethalbumpany", "crewmate_sus"));
+ shash__debug_table(hash);
printf("%d\n", shash_put(hash, "uuuu", "something"));
+ printf("%d\n", shash_put(hash, "afungus", "val2"));
+ shash__debug_table(hash);
printf("%d\n", shash_put(hash, "99asdas", "please collide >:O"));
bool found = false;
@@ -23,6 +29,33 @@ int main(int argc, char **argv) {
printf("%s %d\n", val ? val : "(null)", found);
shash__debug_table(hash);
+
+ shash_free(hash);
return 0;
}
+#else
+
+int main(int argc, char **argv)
+{
+ ihash_t *hash = ihash_create(8, 0.75f);
+
+ printf("%d\n", ihash_put(hash, 1, 10));
+ ihash__debug_table(hash);
+ printf("%d\n", ihash_put(hash, 5, 20));
+ printf("%d\n", ihash_put(hash, 3, 19));
+ printf("%d\n", ihash_put(hash, 56, 101));
+ ihash__debug_table(hash);
+ printf("%d\n", ihash_put(hash, 90, 6));
+ printf("%d\n", ihash_put(hash, 2000, 1));
+ ihash__debug_table(hash);
+ printf("%d\n", ihash_put(hash, 4, 2020));
+
+ ihash__debug_table(hash);
+
+ ihash_free(hash);
+
+ return 0;
+}
+
+#endif
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-12-06 04:43:51 +0000