From 470b35047e515fc7a48be54d7199152487709fb5 Mon Sep 17 00:00:00 2001 From: bigfoot547 Date: Wed, 31 Jan 2024 18:55:24 -0600 Subject: finish hash implementation (untested) --- src/htgen.h | 131 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++-- src/libmain.c | 24 ++++------- 2 files changed, 135 insertions(+), 20 deletions(-) diff --git a/src/htgen.h b/src/htgen.h index c12ed71..9101e01 100644 --- a/src/htgen.h +++ b/src/htgen.h @@ -21,6 +21,8 @@ /* #define HT_VAL_STATIC_LEN sizeof(int) */ #define HT_VAL_GUESS_LEN(_val) strlen(_val) + +/* this function shouldn't do anything if it is called with a value of HT_VAL_SENTINEL */ #define HT_VAL_FREE(_val) free(_val) #define HT_VAL_SENTINEL NULL @@ -29,7 +31,7 @@ #define HT_KEYTYPE_CREF const char * /* will receive two HT_KEYTYPEs */ -/* bad equality function LOL */ +/* bad equality function LOL (shouldn't use strcmp) */ #define HT_KEY_EQ(_val1, _len1, _val2, _len2) (((_len1) == (_len2)) && !strcmp(_val1, _val2)) #define HT_KEY_COPY(_key, _sz) (strdup(_key)) @@ -118,8 +120,11 @@ HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool * 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); -HT_VALTYPE HT__NS(swap)(HT__TYPE *ht, HT_KEYTYPE_CREF key, HT_VALTYPE_CREF val); -HT_VALTYPE HT__NS(swapn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t *vallen); +int HT__NS(remove)(HT__TYPE *ht, HT_KEYTYPE_CREF key); +int HT__NS(removen)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen); + +HT_VALTYPE HT__NS(pop)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found); +HT_VALTYPE HT__NS(popn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found); /* implementations */ @@ -275,6 +280,8 @@ void HT__NS(clear)(HT__TYPE *ht) ht->asize = ht->rsize = 0; } +#define HT__KEY_MATCH_EXACT(_node, _hash, _key, _keylen) (((_node)->hash == (_hash)) && (HT_KEY_EQ((_node)->key, HT__NODE_KEYLEN(_node), _key, _keylen))) + 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 % tablecap); @@ -287,7 +294,7 @@ HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE h do { node = table + tryidx; - if (node->full && !node->deleted && node->hash == hash && HT_KEY_EQ(node->key, HT__NODE_KEYLEN(node), key, keylen)) { + if (node->full && !node->deleted && HT__KEY_MATCH_EXACT(node, hash, key, keylen)) { fprintf(stderr, "found node %zu: matches\n", tryidx); return node; } @@ -305,6 +312,50 @@ HT__NODE *HT__NS(_search)(HT__NODE *table, size_t tablecap, const HT__HASHTYPE h return NULL; } +HT__NODE *HT__NS(_search_ahead)(HT__NODE *table, HT__NODE *start, size_t tablecap, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen) +{ + size_t startidx = (size_t)((uintmax_t)hash % tablecap); + size_t tryidx = ((start - table) + 1) % tablecap; + + HT__NODE *node; + + do { + node = table + tryidx; + + if (!node->full) return NULL; + + if (!node->deleted && HT__KEY_MATCH_EXACT(node, hash, key, keylen)) { + return node; + } + + tryidx = (tryidx + 1) % tablecap; + } while (tryidx != startidx); + + return NULL; +} + +int HT__NS(_node_erase)(HT__TYPE *ht, HT__NODE *node) +{ + if (!node->full || node->deleted) return 0; + node->deleted = true; + --ht->asize; + + HT_KEY_FREE(node->key); + HT_VAL_FREE(node->val); + + return 1; +} + +void HT__NS(_search_ahead_erase)(HT__TYPE *ht, HT__NODE *start) +{ + HT__NODE *found = HT__NS(_search_ahead)(ht->table, start, ht->capacity, start->hash, start->key, start->keylen); + if (!found) { + return; + } + + HT__NS(_node_erase)(ht, found); +} + int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_KEYTYPE_CREF key, size_t keylen, HT_VALTYPE_CREF val, size_t vallen) { if (node->full) { @@ -336,6 +387,8 @@ int HT__NS(_node_set)(HT__TYPE *ht, HT__NODE *node, const HT__HASHTYPE hash, HT_ node->deleted = false; /* node is now filled */ ++ht->asize; + + HT__NS(_search_ahead_erase)(ht, node); return 0; } @@ -438,6 +491,48 @@ HT_VALTYPE HT__NS(getn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool * return node->val; } +int HT__NS(remove)(HT__TYPE *ht, HT_KEYTYPE_CREF key) +{ + return HT__NS(removen)(ht, key, 0); +} + +int HT__NS(removen)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen) +{ + if (!keylen) keylen = HT__GUESS_KEYLEN(key); + + const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen); + HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false); + + if (!node) return 0; + + return HT__NS(_node_erase)(ht, node); +} + +HT_VALTYPE HT__NS(pop)(HT__TYPE *ht, HT_KEYTYPE_CREF key, bool *found) +{ + return HT__NS(popn)(ht, key, 0, found); +} + +HT_VALTYPE HT__NS(popn)(HT__TYPE *ht, HT_KEYTYPE_CREF key, size_t keylen, bool *found) +{ + if (!keylen) keylen = HT__GUESS_KEYLEN(key); + + const HT__HASHTYPE hash = HT_KEY_HASH(key, keylen); + HT__NODE *node = HT__NS(_search)(ht->table, ht->capacity, hash, key, keylen, false); + + if (!node) { + if (found) *found = false; + return NULL; + } + + if (found) *found = true; + + HT_VALTYPE val = node->val; + node->val = HT_VAL_SENTINEL; + HT__NS(_node_erase)(ht, node); + return val; +} + void HT__NS(_debug_table)(HT__TYPE *ht) { fprintf(stderr, HT__STR(HT__TYPE) " debug: cap: %zu, asize: %zu, rsize: %zu, lf: %f\n", @@ -458,3 +553,31 @@ void HT__NS(_debug_table)(HT__TYPE *ht) } #endif + +/* undefine all of the configuration parameters */ + +#undef HT_PREFIX +#undef HT_VALTYPE +#undef HT_VALTYPE_CREF + +#undef HT_HASHTYPE +#undef HT_KEY_HASH + +#undef HT_VAL_COPY +#undef HT_VAL_STATIC_LEN +#undef HT_VAL_GUESS_LEN + +#undef HT_VAL_FREE +#undef HT_VAL_SENTINEL + +#undef HT_KEYTYPE +#undef HT_KEYTYPE_CREF +#undef HT_KEY_EQ +#undef HT_KEY_COPY +#undef HT_KEY_FREE + +#undef HT_KEY_STATIC_LEN +#undef HT_KEY_GUESS_LEN + +#undef HT_KEY_FMT +#undef HT_VAL_FMT diff --git a/src/libmain.c b/src/libmain.c index a7b1e8b..25a340d 100644 --- a/src/libmain.c +++ b/src/libmain.c @@ -9,25 +9,17 @@ #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_t *hash = shash_create(4, 0.75f); + printf("%d\n", shash_put(hash, "test1", "value1")); + printf("%d\n", shash_put(hash, "testbro", "val2")); 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; - char *val = shash_getn(hash, "99asdas", 0, &found); - printf("%s %d\n", val ? val : "(null)", found); + char *oldval = shash_pop(hash, "test1", NULL); + printf("%s:%s\n", "test1", oldval); + free(oldval); + shash__debug_table(hash); + printf("%d\n", shash_put(hash, "testbro", "val3")); shash__debug_table(hash); shash_free(hash); -- cgit v1.2.3-70-g09d2