delete for hashtables

5 files changed, 157 insertions, 7 deletions

diff --git a/examples/hashtable/Makefile b/examples/hashtable/Makefile
index c06e482..5eaf054 100644
--- a/examples/hashtable/Makefile
+++ b/examples/hashtable/Makefile
@@ -1,9 +1,12 @@
 .PHONY: test clean
-TESTS=test_insert.test
+TESTS=test_insert.test test_insert_delete.test
 COMMON_OBJS=../test_common.o uns_hashtable.o
 .SUFFIXES: .test
 CFLAGS=-Wall -std=c89 -Werror -pedantic -fPIC -g -Iinclude
 
+libunshashtable.so: uns_hashtable.o
+	$(CC) -shared -I../../include $(CFLAGS) $< -o libunshashtable.so
+
 test: $(TESTS) $(COMMON_OBJS)
 	for i in $(TESTS); do \
 		LD_LIBRARY_PATH=$$(pwd)/../../ valgrind ./$$i || exit 1; \
@@ -17,4 +20,4 @@ test_insert.test: $(COMMON_OBJS)
 	$(CC) -I../../include $(CFLAGS) $< -c -o $@
 
 clean:
-	rm -f $(TESTS) $(COMMON_OBJS)
+	rm -f $(TESTS) $(COMMON_OBJS) libunshashtable.so
diff --git a/examples/hashtable/test_insert_delete.c b/examples/hashtable/test_insert_delete.c
new file mode 100644
index 0000000..7f02751
--- /dev/null
+++ b/examples/hashtable/test_insert_delete.c
@@ -0,0 +1,106 @@
+/* Copyright (c) 2024, Peter McGoron
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ *
+ * 1) Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2) Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
+ * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
+ * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
+ * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
+ * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
+ * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <assert.h>
+#include "uns.h"
+#include "uns_hashtable.h"
+#include "testnames.h"
+
+#define ARRLEN(a) (sizeof(a) /sizeof((a)[0]))
+
+/* Insert and delete in a way that invokes the garbage collector every
+ * so often. add 50 delete 10
+ */
+
+int test(struct uns_gc *gc)
+{
+	/* Keys and values will be stored as NUL terminated for simplicity. */
+	struct uns_ctr htbl = {0};
+	struct uns_ctr str = {0};
+	struct uns_ctr val = {0};
+	struct uns_ctr old_value = {0};
+	int i, j;
+	size_t slen;
+	int first_not_deleted = 0;
+
+	uns_root_add(gc, &htbl);
+	uns_root_add(gc, &str);
+	uns_root_add(gc, &val);
+	uns_root_add(gc, &old_value);
+
+	uns_hashtable_alloc_into(gc, &htbl, 32);
+
+	for (i = 0; i < ARRLEN(names); i++) {
+		printf("%d\r", i);
+		fflush(stdout);
+
+		slen = strlen(names[i]);
+		str.p = gc->alloc(gc, slen);
+		val.p = gc->alloc(gc, strlen(values[i]));
+		strcpy(str.p, names[i]);
+		strcpy(val.p, values[i]);
+
+		uns_hashtable_add(gc, &htbl, &str, slen, &val, &old_value);
+		assert(!old_value.p);
+
+		if (i % 50 == 0 && i != 0) {
+			for (j = first_not_deleted; j < first_not_deleted + 10; j++) {
+				uns_hashtable_del(gc, &htbl, (unsigned char *)names[j], strlen(names[j]), &old_value);
+				if (!old_value.p || strcmp(old_value.p, values[j]) != 0) {
+					printf("\n%s, %s\n", (char *)val.p, values[j]);
+					printf("\n%d-%d delete failed\n", i, j);
+					exit(1);
+				}
+			}
+			first_not_deleted += 10;
+		}
+
+		for (j = 0; j < ARRLEN(names); j++) {
+			uns_hashtable_search(gc, &htbl, (unsigned char*)names[j], strlen(names[j]),
+			                     &val);
+			if (j < first_not_deleted || j > i) {
+				if (val.p) {
+					printf("\n%d: %d should not exist\n", i, j);
+					exit(1);
+				}
+			} else if (j <= i && (!val.p || strcmp(val.p, values[j]) != 0)) {
+				printf("\n%s, %s\n", (char *)val.p, values[j]);
+				printf("\n%d-%d failed\n", i, j);
+				exit(1);
+			}
+		}
+	}
+	printf("\ndone\n");
+
+	uns_root_remove(gc, &old_value);
+	uns_root_remove(gc, &val);
+	uns_root_remove(gc, &str);
+	uns_root_remove(gc, &htbl);
+	gc->collect(gc);
+	return 0;
+}
diff --git a/examples/hashtable/uns_hashtable.c b/examples/hashtable/uns_hashtable.c
index 3721ab8..8dd36e7 100644
--- a/examples/hashtable/uns_hashtable.c
+++ b/examples/hashtable/uns_hashtable.c
@@ -51,6 +51,11 @@ static void set_size_t(struct uns_gc *gc, struct uns_ctr *root, size_t i, size_t
 	memcpy(p, &val, sizeof(val));
 }
 
+static void *index(struct uns_gc *gc, struct uns_ctr *htbl, size_t i)
+{
+	return gc->record_get_ptr(htbl->p, i + HTBL_HDR_LEN);
+}
+
 void uns_hashtable_alloc_into(struct uns_gc *gc, struct uns_ctr *r, size_t size)
 {
 	unsigned char *p;
@@ -144,12 +149,50 @@ static int search_for_container(struct uns_gc *gc, struct uns_ctr *htbl,
 	if (hash_out)
 		*hash_out = hash;
 
-	container->p = gc->record_get_ptr(htbl->p, hash + HTBL_HDR_LEN);
+	container->p = index(gc, htbl, hash);
 	if (!container->p)
 		return 0;
 	return search_container(gc, container, str, len);
 }
 
+/* This could be made better with internal pointers, but that is not
+ * portable.
+ */
+void uns_hashtable_del(struct uns_gc *gc, struct uns_ctr *htbl,
+                       unsigned char *str, size_t len,
+                       struct uns_ctr *old_value)
+{
+	size_t hash = fnv(str, len) % uns_hashtable_len(gc, htbl);
+	struct uns_ctr rec = {0};
+	struct uns_ctr prevptr = {0};
+
+	old_value->p = NULL;
+	rec.p = index(gc, htbl, hash);
+	if (!rec.p) {
+		return;
+	}
+
+	/* Special case: first pointer */
+	if (len == get_size_t(gc, &rec, LENGTH) &&
+	    memcmp(str, gc->record_get_ptr(rec.p, STRING), len) == 0) {
+		old_value->p = gc->record_get_ptr(rec.p, VALUE);
+		gc->record_set_ptr(htbl->p, HTBL_HDR_LEN + hash,
+		                   gc->record_get_ptr(rec.p, NEXT));
+	}
+
+	prevptr = rec;
+	for (rec.p = gc->record_get_ptr(rec.p, NEXT); rec.p;
+	     rec.p = gc->record_get_ptr(rec.p, NEXT)) {
+		if (len == get_size_t(gc, &rec, LENGTH)
+		    && memcmp(str, gc->record_get_ptr(rec.p, VALUE), len) == 0) {
+			old_value->p = gc->record_get_ptr(rec.p, VALUE);
+			gc->record_set_ptr(prevptr.p, NEXT,
+			                   gc->record_get_ptr(rec.p, NEXT));
+			return;
+		}
+	}
+}
+
 void uns_hashtable_search(struct uns_gc *gc, struct uns_ctr *htbl,
                           unsigned char *str, size_t string_len,
                           struct uns_ctr *found)
@@ -247,7 +290,7 @@ void uns_hashtable_resize(struct uns_gc *gc, struct uns_ctr *htbl, size_t newsiz
 	           uns_hashtable_used(gc, &newtbl));
 
 	for (i = 0; i < oldlen; i++)
-		add_for_ent(gc, &newtbl, gc->record_get_ptr(htbl->p, i + HTBL_HDR_LEN));
+		add_for_ent(gc, &newtbl, index(gc, htbl, i));
 
 	htbl->p = newtbl.p;
 	uns_root_remove(gc, &newtbl);
diff --git a/examples/hashtable/uns_hashtable.h b/examples/hashtable/uns_hashtable.h
index d4bae24..a9f16a3 100644
--- a/examples/hashtable/uns_hashtable.h
+++ b/examples/hashtable/uns_hashtable.h
@@ -46,11 +46,9 @@ void uns_hashtable_search(struct uns_gc *gc, struct uns_ctr *htbl,
                           struct uns_ctr *found);
 size_t uns_hashtable_used(struct uns_gc *gc, struct uns_ctr *htbl);
 size_t uns_hashtable_len(struct uns_gc *gc, struct uns_ctr *htbl);
-/*
 void uns_hashtable_del(struct uns_gc *gc, struct uns_ctr *htbl,
                        unsigned char *str, size_t string_len,
                        struct uns_ctr *old_value);
-*/
 
 /* The following functions may collect. */
 void uns_hashtable_alloc_into(struct uns_gc *gc, struct uns_ctr *r, size_t size);
diff --git a/examples/string/Makefile b/examples/string/Makefile
index 6ec8882..9693d5e 100644
--- a/examples/string/Makefile
+++ b/examples/string/Makefile
@@ -22,4 +22,4 @@ test_large.test: $(COMMON_OBJS)
 	$(CC) -I../../include $(CFLAGS) $< -c -o $@
 
 clean:
-	rm -f $(TESTS) $(COMMON_OBJS)
+	rm -f $(TESTS) $(COMMON_OBJS) libunsstring.so