delete for hashtables

1 files changed, 45 insertions, 2 deletions

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);