summaryrefslogtreecommitdiffstats
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/htgen.h131
-rw-r--r--src/libmain.c24
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,26 +9,18 @@
#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);
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2025-12-06 05:40:17 +0000