hashtable test

1 files changed, 62 insertions, 0 deletions

diff --git a/examples/hashtable/uns_hashtable.h b/examples/hashtable/uns_hashtable.h
new file mode 100644
index 0000000..d4bae24
--- /dev/null
+++ b/examples/hashtable/uns_hashtable.h
@@ -0,0 +1,62 @@
+#ifndef UNS_STRING_H
+#define UNS_STRING_H
+
+/* 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 "uns.h"
+
+/* Imperative hash tables with internal chaining.
+ *
+ * Internal chaining is inefficient, but it is a good showcase of garbage
+ * collection.
+ *
+ * Hashtable:
+ * [size][used][pointers to entries]
+ *               NULL or  |/---------------------------------------------\
+ *               [pointer to length][pointer to string][pointer to next] /
+ *                                                         | NULL or    /
+ *                                                         \-----------/
+ */
+
+void uns_hashtable_search(struct uns_gc *gc, struct uns_ctr *htbl,
+                          unsigned char *str, size_t string_len,
+                          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);
+void uns_hashtable_add(struct uns_gc *gc, struct uns_ctr *htbl,
+                       struct uns_ctr *string, size_t string_len,
+                       struct uns_ctr *value, struct uns_ctr *old_value);
+void uns_hashtable_resize(struct uns_gc *gc, struct uns_ctr *htbl, size_t newsize);
+
+#endif