delete for hashtables

1 files changed, 106 insertions, 0 deletions

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;
+}