aboutsummaryrefslogtreecommitdiff
path: root/src
diff options
context:
space:
mode:
Diffstat (limited to 'src')
-rw-r--r--src/hamt.c461
-rw-r--r--src/main.c82
-rw-r--r--src/murmur3.c40
-rw-r--r--src/parse.c3
-rw-r--r--src/reducer.c243
-rw-r--r--src/term.c6
6 files changed, 652 insertions, 183 deletions
diff --git a/src/hamt.c b/src/hamt.c
new file mode 100644
index 0000000..f9bd8b2
--- /dev/null
+++ b/src/hamt.c
@@ -0,0 +1,461 @@
+#include "hamt.h"
+
+#include <assert.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+/* Pointer tagging */
+#define HAMT_TAG_MASK 0x3 /* last two bits */
+#define HAMT_TAG_VALUE 0x1
+#define tagged(__p) (hamt_node *)((uintptr_t)__p | HAMT_TAG_VALUE)
+#define untagged(__p) (hamt_node *)((uintptr_t)__p & ~HAMT_TAG_MASK)
+#define is_value(__p) (((uintptr_t)__p & HAMT_TAG_MASK) == HAMT_TAG_VALUE)
+
+/* Bit fiddling */
+#define index_clear_bit(_index, _n) _index & ~(1ul << _n)
+#define index_set_bit(_index, _n) _index | (1ul << _n)
+
+/* Node data structure */
+#define TABLE(a) a->as.table.ptr
+#define INDEX(a) a->as.table.index
+#define VALUE(a) a->as.kv.value
+#define KEY(a) a->as.kv.key
+
+/* Memory management */
+#define mem_alloc(ator, size) (ator)->malloc(size)
+#define mem_realloc(ator, ptr, size) (ator)->realloc(ptr, size)
+#define mem_free(ator, ptr) (ator)->free(ptr)
+/* Default allocator uses system malloc */
+struct hamt_allocator hamt_allocator_default = { malloc, realloc, free };
+
+typedef struct hamt_node {
+ union {
+ struct {
+ void *value; /* tagged pointer */
+ const void *key;
+ } kv;
+ struct {
+ struct hamt_node *ptr;
+ uint32_t index;
+ } table;
+ } as;
+} hamt_node;
+
+struct hamt_stats {
+ size_t table_sizes[32];
+};
+
+/* Opaque user-facing implementation */
+struct hamt_impl {
+ struct hamt_node *root;
+ size_t size;
+ hamt_key_hash_fn key_hash;
+ hamt_cmp_fn key_cmp;
+ struct hamt_allocator *ator;
+ struct hamt_stats stats;
+};
+
+/* hash_stateing w/ state management */
+typedef struct hash_state {
+ const void *key;
+ hamt_key_hash_fn hash_fn;
+ uint32_t hash;
+ size_t depth;
+ size_t shift;
+} hash_state;
+
+/* Search results */
+typedef enum {
+ SEARCH_SUCCESS,
+ SEARCH_FAIL_NOTFOUND,
+ SEARCH_FAIL_KEYMISMATCH
+} search_status;
+
+typedef struct search_result {
+ search_status status;
+ hamt_node *anchor;
+ hamt_node *value;
+ hash_state *hash;
+} search_result;
+
+/* Removal results */
+typedef enum { REMOVE_SUCCESS, REMOVE_GATHERED, REMOVE_NOTFOUND } remove_status;
+
+typedef struct remove_result {
+ remove_status status;
+ void *value;
+} remove_result;
+
+typedef struct path_result {
+ union {
+ search_result sr;
+ remove_result rr;
+ } u;
+ hamt_node *root;
+} path_result;
+
+static inline hash_state *hash_next(hash_state *h)
+{
+ h->depth += 1;
+ h->shift += 5;
+ if (h->shift > 30) {
+ h->hash = h->hash_fn(h->key, h->depth / 5);
+ h->shift = 0;
+ }
+ return h;
+}
+
+static inline uint32_t hash_get_index(const hash_state *h)
+{
+ return (h->hash >> h->shift) & 0x1f;
+}
+
+static int get_popcount(uint32_t n)
+{
+ return __builtin_popcount(n);
+}
+
+static int get_pos(uint32_t sparse_index, uint32_t bitmap)
+{
+ return get_popcount(bitmap & ((1ul << sparse_index) - 1));
+}
+
+static inline bool has_index(const hamt_node *anchor, size_t index)
+{
+ assert(anchor && "anchor must not be NULL");
+ assert(index < 32 && "index must not be larger than 31");
+ return INDEX(anchor) & (1ul << index);
+}
+
+static hamt_node *table_allocate(struct hamt_impl *h, size_t size)
+{
+ if (size)
+ h->stats.table_sizes[size - 1] += 1;
+ return (hamt_node *)mem_alloc(h->ator, (size * sizeof(hamt_node)));
+}
+
+static void table_free(struct hamt_impl *h, hamt_node *ptr, size_t size)
+{
+ mem_free(h->ator, ptr);
+ if (size)
+ h->stats.table_sizes[size - 1] -= 1;
+}
+
+static hamt_node *table_extend(struct hamt_impl *h, hamt_node *anchor,
+ size_t n_rows, uint32_t index, uint32_t pos)
+{
+ hamt_node *new_table = table_allocate(h, n_rows + 1);
+ if (!new_table)
+ return NULL;
+ if (n_rows > 0) {
+ /* copy over table */
+ memcpy(&new_table[0], &TABLE(anchor)[0],
+ pos * sizeof(hamt_node));
+ /* note: this works since (n_rows - pos) == 0 for cases
+ * where we're adding the new k/v pair at the end (i.e. memcpy(a, b, 0)
+ * is a nop) */
+ memcpy(&new_table[pos + 1], &TABLE(anchor)[pos],
+ (n_rows - pos) * sizeof(hamt_node));
+ }
+ assert(!is_value(VALUE(anchor)) && "URGS");
+ table_free(h, TABLE(anchor), n_rows);
+ TABLE(anchor) = new_table;
+ INDEX(anchor) |= (1ul << index);
+ return anchor;
+}
+
+static hamt_node *table_shrink(struct hamt_impl *h, hamt_node *anchor,
+ size_t n_rows, uint32_t index, uint32_t pos)
+{
+ /* debug assertions */
+ assert(anchor && "Anchor cannot be NULL");
+ assert(!is_value(VALUE(anchor)) &&
+ "Invariant: shrinking a table requires an internal node");
+
+ hamt_node *new_table = NULL;
+ uint32_t new_index = 0;
+ if (n_rows > 0) {
+ new_table = table_allocate(h, n_rows - 1);
+ if (!new_table)
+ return NULL;
+ new_index = INDEX(anchor) & ~(1ul << index);
+ memcpy(&new_table[0], &TABLE(anchor)[0],
+ pos * sizeof(hamt_node));
+ memcpy(&new_table[pos], &TABLE(anchor)[pos + 1],
+ (n_rows - pos - 1) * sizeof(hamt_node));
+ }
+ table_free(h, TABLE(anchor), n_rows);
+ INDEX(anchor) = new_index;
+ TABLE(anchor) = new_table;
+ return anchor;
+}
+
+static hamt_node *table_gather(struct hamt_impl *h, hamt_node *anchor,
+ uint32_t pos)
+{
+ /* debug assertions */
+ assert(anchor && "Anchor cannot be NULL");
+ assert(!is_value(VALUE(anchor)) &&
+ "Invariant: gathering a table requires an internal anchor");
+ assert((pos == 0 || pos == 1) && "pos must be 0 or 1");
+
+ int n_rows = get_popcount(INDEX(anchor));
+ assert((n_rows == 2 || n_rows == 1) &&
+ "Table must have size 1 or 2 to gather");
+ hamt_node *table = TABLE(anchor);
+ KEY(anchor) = table[pos].as.kv.key;
+ VALUE(anchor) = table[pos].as.kv.value; /* already tagged */
+ table_free(h, table, n_rows);
+ return anchor;
+}
+
+static hamt_node *table_dup(struct hamt_impl *h, hamt_node *anchor)
+{
+ int n_rows = get_popcount(INDEX(anchor));
+ hamt_node *new_table = table_allocate(h, n_rows);
+ if (new_table && TABLE(anchor)) {
+ memcpy(&new_table[0], &TABLE(anchor)[0],
+ n_rows * sizeof(hamt_node));
+ }
+ return new_table;
+}
+
+HAMT hamt_create(hamt_key_hash_fn key_hash, hamt_cmp_fn key_cmp,
+ struct hamt_allocator *ator)
+{
+ struct hamt_impl *trie = mem_alloc(ator, sizeof(struct hamt_impl));
+ trie->ator = ator;
+ trie->root = mem_alloc(ator, sizeof(hamt_node));
+ memset(trie->root, 0, sizeof(hamt_node));
+ trie->size = 0;
+ trie->key_hash = key_hash;
+ trie->key_cmp = key_cmp;
+ // memset(trie->stats.table_sizes, 0, 32*sizeof(size_t));
+ trie->stats = (struct hamt_stats){ .table_sizes = { 0 } };
+ return trie;
+}
+
+static HAMT hamt_dup(HAMT h)
+{
+ struct hamt_impl *trie = mem_alloc(h->ator, sizeof(struct hamt_impl));
+ trie->ator = h->ator;
+ trie->root = mem_alloc(h->ator, sizeof(hamt_node));
+ memcpy(trie->root, h->root, sizeof(hamt_node));
+ trie->size = h->size;
+ trie->key_hash = h->key_hash;
+ trie->key_cmp = h->key_cmp;
+ memcpy(&trie->stats, &h->stats, sizeof(struct hamt_stats));
+ return trie;
+}
+
+static const hamt_node *insert_kv(struct hamt_impl *h, hamt_node *anchor,
+ hash_state *hash, void *key, void *value)
+{
+ /* calculate position in new table */
+ uint32_t ix = hash_get_index(hash);
+ uint32_t new_index = INDEX(anchor) | (1ul << ix);
+ int pos = get_pos(ix, new_index);
+ /* extend table */
+ size_t n_rows = get_popcount(INDEX(anchor));
+ anchor = table_extend(h, anchor, n_rows, ix, pos);
+ if (!anchor)
+ return NULL;
+ hamt_node *new_table = TABLE(anchor);
+ /* set new k/v pair */
+ new_table[pos].as.kv.key = key;
+ new_table[pos].as.kv.value = tagged(value);
+ /* return a pointer to the inserted k/v pair */
+ return &new_table[pos];
+}
+
+static const hamt_node *insert_table(struct hamt_impl *h, hamt_node *anchor,
+ hash_state *hash, void *key, void *value)
+{
+ /* FIXME: check for alloc failure and bail out correctly (deleting the
+ * incomplete subtree */
+
+ /* Collect everything we know about the existing value */
+ hash_state *x_hash =
+ &(hash_state){ .key = KEY(anchor),
+ .hash_fn = hash->hash_fn,
+ .hash = hash->hash_fn(KEY(anchor),
+ hash->depth / 5),
+ .depth = hash->depth,
+ .shift = hash->shift };
+ void *x_value = VALUE(anchor); /* tagged (!) value ptr */
+ /* increase depth until the hashes diverge, building a list
+ * of tables along the way */
+ hash_state *next_hash = hash_next(hash);
+ hash_state *x_next_hash = hash_next(x_hash);
+ uint32_t next_index = hash_get_index(next_hash);
+ uint32_t x_next_index = hash_get_index(x_next_hash);
+ while (x_next_index == next_index) {
+ TABLE(anchor) = table_allocate(h, 1);
+ INDEX(anchor) = (1ul << next_index);
+ next_hash = hash_next(next_hash);
+ x_next_hash = hash_next(x_next_hash);
+ next_index = hash_get_index(next_hash);
+ x_next_index = hash_get_index(x_next_hash);
+ anchor = TABLE(anchor);
+ }
+ /* the hashes are different, let's allocate a table with two
+ * entries to store the existing and new values */
+ TABLE(anchor) = table_allocate(h, 2);
+ INDEX(anchor) = (1ul << next_index) | (1ul << x_next_index);
+ /* determine the proper position in the allocated table */
+ int x_pos = get_pos(x_next_index, INDEX(anchor));
+ int pos = get_pos(next_index, INDEX(anchor));
+ /* fill in the existing value; no need to tag the value pointer
+ * since it is already tagged. */
+ TABLE(anchor)[x_pos].as.kv.key = (const void *)x_hash->key;
+ TABLE(anchor)[x_pos].as.kv.value = x_value;
+ /* fill in the new key/value pair, tagging the pointer to the
+ * new value to mark it as a value ptr */
+ TABLE(anchor)[pos].as.kv.key = key;
+ TABLE(anchor)[pos].as.kv.value = tagged(value);
+
+ return &TABLE(anchor)[pos];
+}
+
+static search_result search_recursive(struct hamt_impl *h, hamt_node *anchor,
+ hash_state *hash, hamt_cmp_fn cmp_eq,
+ const void *key, hamt_node *path)
+{
+ assert(!is_value(VALUE(anchor)) &&
+ "Invariant: path copy requires an internal node");
+ hamt_node *copy = path;
+ if (path) {
+ /* copy the table we're pointing to */
+ TABLE(copy) = table_dup(h, anchor);
+ INDEX(copy) = INDEX(anchor);
+ assert(!is_value(VALUE(copy)) &&
+ "Copy caused a leaf/internal switch");
+ } else {
+ copy = anchor;
+ }
+
+ /* determine the expected index in table */
+ uint32_t expected_index = hash_get_index(hash);
+ /* check if the expected index is set */
+ if (has_index(copy, expected_index)) {
+ /* if yes, get the compact index to address the array */
+ int pos = get_pos(expected_index, INDEX(copy));
+ /* index into the table and check what type of entry we're looking at */
+ hamt_node *next = &TABLE(copy)[pos];
+ if (is_value(VALUE(next))) {
+ if ((*cmp_eq)(key, KEY(next)) == 0) {
+ /* keys match */
+ search_result result = { .status =
+ SEARCH_SUCCESS,
+ .anchor = copy,
+ .value = next,
+ .hash = hash };
+ return result;
+ }
+ /* not found: same hash but different key */
+ search_result result = {
+ .status = SEARCH_FAIL_KEYMISMATCH,
+ .anchor = copy,
+ .value = next,
+ .hash = hash
+ };
+ return result;
+ } else {
+ /* For table entries, recurse to the next level */
+ assert(TABLE(next) != NULL &&
+ "invariant: table ptrs must not be NULL");
+ return search_recursive(h, next, hash_next(hash),
+ cmp_eq, key,
+ path ? next : NULL);
+ }
+ }
+ /* expected index is not set, terminate search */
+ search_result result = { .status = SEARCH_FAIL_NOTFOUND,
+ .anchor = copy,
+ .value = NULL,
+ .hash = hash };
+ return result;
+}
+
+void *hamt_get(const HAMT trie, void *key)
+{
+ hash_state *hash = &(hash_state){ .key = key,
+ .hash_fn = trie->key_hash,
+ .hash = trie->key_hash(key, 0),
+ .depth = 0,
+ .shift = 0 };
+ search_result sr = search_recursive(trie, trie->root, hash,
+ trie->key_cmp, key, NULL);
+ if (sr.status == SEARCH_SUCCESS) {
+ return untagged(sr.VALUE(value));
+ }
+ return NULL;
+}
+
+static path_result search(struct hamt_impl *h, hamt_node *anchor,
+ hash_state *hash, hamt_cmp_fn cmp_eq, const void *key)
+{
+ path_result pr;
+ pr.root = mem_alloc(h->ator, sizeof(hamt_node));
+ pr.u.sr = search_recursive(h, anchor, hash, cmp_eq, key, pr.root);
+ return pr;
+}
+
+HAMT hamt_pset(HAMT h, void *key, void *value)
+{
+ hash_state *hash = &(hash_state){ .key = key,
+ .hash_fn = h->key_hash,
+ .hash = h->key_hash(key, 0),
+ .depth = 0,
+ .shift = 0 };
+ HAMT cp = hamt_dup(h);
+ path_result pr = search(h, h->root, hash, h->key_cmp, key);
+ cp->root = pr.root;
+ switch (pr.u.sr.status) {
+ case SEARCH_SUCCESS:
+ pr.u.sr.VALUE(value) = tagged(value);
+ break;
+ case SEARCH_FAIL_NOTFOUND:
+ if (insert_kv(h, pr.u.sr.anchor, pr.u.sr.hash, key, value) !=
+ NULL) {
+ cp->size += 1;
+ }
+ break;
+ case SEARCH_FAIL_KEYMISMATCH:
+ if (insert_table(h, pr.u.sr.value, pr.u.sr.hash, key, value) !=
+ NULL) {
+ cp->size += 1;
+ }
+ break;
+ default:
+ fprintf(stderr, "Invalid result status\n");
+ }
+ return cp;
+}
+
+/* delete recursively from anchor */
+static void delete_recursive(struct hamt_impl *h, hamt_node *anchor)
+{
+ if (TABLE(anchor)) {
+ assert(!is_value(VALUE(anchor)) &&
+ "delete requires an internal node");
+ size_t n = get_popcount(INDEX(anchor));
+ for (size_t i = 0; i < n; ++i) {
+ if (!is_value(TABLE(anchor)[i].as.kv.value)) {
+ delete_recursive(h, &TABLE(anchor)[i]);
+ }
+ }
+ table_free(h, TABLE(anchor), n);
+ TABLE(anchor) = NULL;
+ }
+}
+
+void hamt_delete(HAMT h)
+{
+ delete_recursive(h, h->root);
+ mem_free(h->ator, h->root);
+ mem_free(h->ator, h);
+}
diff --git a/src/main.c b/src/main.c
index b0cfff4..c9e7b09 100644
--- a/src/main.c
+++ b/src/main.c
@@ -1,4 +1,4 @@
-// vim: nowrap
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
#include <stdio.h>
@@ -7,30 +7,35 @@
#include <reducer.h>
#ifndef TEST
+static void callback(int i, char ch)
+{
+ printf("%d: %c\n", i, ch);
+}
+
int main(void)
{
- struct term *term = parse(
- "((([([(1 [((1 1) 0)])] [(1 [((1 1) 0)])])] [[[((([((0 [[[[[0]]]]]) [[1]])] 0) [[0]]) ((([((((0 [[1]]) [[[0]]]) [[[0]]]) [0])] 1) [[0]]) (([[[((0 2) 1)]]] ([(0 [[1]])] 0)) ((2 ([([(0 [[0]])] ((((0 (([[[((0 2) 1)]]] [[[[3]]]]) [[[[(2 3)]]]])) [(0 [[(([[[((0 2) 1)]]] ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 0))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(1 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1))]])]) [(0 [[(([[[((0 2) 1)]]] ([[[[[(0 ((((4 3) 2) 1) 0))]]]]] 1)) ([[[[[(2 ((((4 3) 2) 1) 0))]]]]] 1))]])]))] 1)) ([(0 [[0]])] 0)))))]]]) [[[[(0 (2 (1 3)))]]]]) (([([(1 [((1 1) 0)])] [(1 [((1 1) 0)])])] [[((([([(1 [((1 1) 0)])] [(1 [((1 1) 0)])])] [[[((([((0 [[[[[0]]]]]) [[1]])] 1) 0) (([[[((0 2) 1)]]] ([(0 [[1]])] 1)) ((2 ([(0 [[0]])] 1)) 0)))]]]) 0) (1 0))]]) [((0 [((0 [[1]]) [((0 [[0]]) [((0 [[0]]) [((0 [[0]]) [((0 [[0]]) [((0 [[1]]) [((0 [[1]]) [((0 [[0]]) [[0]])])])])])])])])]) [((0 [((0 [[0]]) [((0 [[1]]) [((0 [[0]]) [((0 [[0]]) [((0 [[0]]) [((0 [[1]]) [((0 [[1]]) [((0 [[0]]) [[0]])])])])])])])])]) [[0]])])]))");
- // 1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-1-2-6-1-2-6-1-3-2-5-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-3-2-5-6-2-5-6-2-6-3-1-1-2-6-2-6-2-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-AAH-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1-2-6-1-3-3-1
- // 1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-1-2-6-1-2-6-1-3-2-5-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-2-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-3-2-5-6-2-5-6-2-6-3-1-1-2-6-2-6-2-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-AAH-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-3-2-5-6-1-3-1-3-2-5-6-1-3-3-1-1-2-6-2-6-2-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-2-6-3-2-5-6-2-6-3-3-3-3-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-3-4-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-3-2-5-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-3-2-5-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-2-5-5-6-2-5-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-2-6-3-2-5-6-2-6-3-3-3-3-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-3-4-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-4-6-2-6-2-6-2-6-1-3-3-2-5-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-4-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-2-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-2-5-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-3-2-5-5-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-7-1-1-4-9-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-1-1-4-9-2-7-2-7-4-11-5-11-5-10-9-2-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-9-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-3-1-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-1-2-6-1-3-4-5-6-1-1-3-2-5-6-2-6-3-2-5-5-5-5-6-2-6-3-2-5-6-2-6-3-3-3-3-1-3-2-5-6-1-1-3-4-5-6-1-4-6-2-6-1-1-1-2-6-1-2-6-1-3-2-5-6-2-6-2-6-1-1-1-2-6-1-1-3-3-3-3-4-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-2-6-2-6-2-5-5-5-5-5-5-5-5-5-6-1-1-3-2-5-6-2-6-2-6-2-6-2-6-3-1-1-1-2-6-1-1-1-1-3-3-3-1-2-6-1-2-6-1-3-1-1-1-1-3-4-5-6-2-6-2-6-2-6-1-3-2-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-3-2-5-5-6-1-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-1-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-1-1-2-6-2-6-2-5-5-5-5-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-1-1-2-6-2-6-2-5-6-1-1-3-2-5-6-2-6-3-3-1-2-6-2-5-5-5-5-5-6-2-6-2-6-2-6-1-3-2-5-6-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-3-1-1-1-1-3-3-3-1-2-6-2-5-5-5-6-2-6-2-6-2-6-1-3-4-5-6-3-1-1-1-1-3-3-3-2-5-5-5-6-2-6-2-6-2-6-3-3-3-3-2-5-5-5-5-5-5-5-6-2-6-3-2-5-5-5-7-2-7-4-11-5-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5-10-11-5
+ // Benchmarking test for memory leaks and stack overflows, will probably not return: "([(((0 [[((0 1) 0)]]) [(0 0)]) 0)] [[(1 (1 0))]])"
+ struct term *term =
+ parse("([(((0 [[((0 1) 0)]]) [(0 0)]) 0)] [[(1 (1 0))]])");
- /* print_scheme(term); */
printf("\nReduced:\n");
- reduce(term);
- /* print_term(reduced); */
+ struct term *reduced = reduce(term, callback);
+ to_bruijn(reduced);
+ print_term(reduced);
printf("\n");
free_term(term);
- /* free_term(reduced); */
+ free_term(reduced);
return 0;
}
#else
-#define TESTS 2
+#define TESTS 6
#define TESTDIR "./tests/"
#include <stdlib.h>
#include <string.h>
#include <errno.h>
#include <time.h>
+#include <gc.h>
static char *read_file(const char *path)
{
@@ -58,18 +63,32 @@ static char *read_file(const char *path)
return string;
}
+// global vars suck I know but how could I do it any other way?
+static struct {
+ struct term *in;
+ struct term *res;
+ struct term *red;
+ char *trans;
+ struct {
+ int alpha;
+ int trans;
+ } equivalency;
+} tests[TESTS] = { 0 };
+static int current = 0;
+
+static void callback(int i, char ch)
+{
+ if (ch != tests[current].trans[i]) {
+ fprintf(stderr, "Transition deviation at index %d!\n", i);
+ tests[current].equivalency.trans = 0;
+ }
+ /* printf("%d: %c\n", i, ch); */
+}
+
int main(void)
{
- struct {
- struct term *in;
- struct term *res;
- struct term *red;
- char *trans;
- struct {
- int alpha;
- int trans;
- } equivalency;
- } tests[TESTS] = { 0 };
+ GC_INIT();
+
char in_template[] = TESTDIR "x.in";
char red_template[] = TESTDIR "x.red";
char trans_template[] = TESTDIR "x.trans";
@@ -89,30 +108,35 @@ int main(void)
tests[i].red = parse(red);
to_bruijn(tests[i].red);
free(red);
+
+ tests[i].equivalency.trans = 1;
}
clock_t begin = clock();
- for (int i = 0; i < TESTS; i++)
- tests[i].res = reduce(tests[i].in);
+ for (current = 0; current < TESTS; current++) {
+ tests[current].res = reduce(tests[current].in, callback);
+ printf("Test %d done\n", current + 1);
+ }
clock_t end = clock();
for (int i = 0; i < TESTS; i++) {
to_bruijn(tests[i].res);
tests[i].equivalency.alpha =
alpha_equivalency(tests[i].res, tests[i].red);
- tests[i].equivalency.trans = 1; // TODO
+ free(tests[i].in);
+ free(tests[i].res);
+ free(tests[i].red);
}
printf("=== SUMMARY ===\n");
printf("Reduced tests in %.5fs\n",
(double)(end - begin) / CLOCKS_PER_SEC);
for (int i = 0; i < TESTS; i++) {
- if (!tests[i].equivalency.alpha ||
- !tests[i].equivalency.trans) {
- printf("Test %d: [failed]\n\talpha-equivalency: %d\n\ttrans-equivalency: %d\n",
- i, tests[i].equivalency.alpha,
- tests[i].equivalency.trans);
- }
+ if (tests[i].equivalency.alpha && tests[i].equivalency.trans)
+ continue;
+ printf("Test %d: [failed]\n\talpha-equivalency: %d\n\ttrans-equivalency: %d\n",
+ i + 1, tests[i].equivalency.alpha,
+ tests[i].equivalency.trans);
}
}
#endif
diff --git a/src/murmur3.c b/src/murmur3.c
new file mode 100644
index 0000000..bb1f666
--- /dev/null
+++ b/src/murmur3.c
@@ -0,0 +1,40 @@
+#include "murmur3.h"
+
+#include <string.h>
+
+static inline uint32_t murmur_32_scramble(uint32_t k)
+{
+ k *= 0xcc9e2d51;
+ k = (k << 15) | (k >> 17);
+ k *= 0x1b873593;
+ return k;
+}
+
+uint32_t murmur3_32(const uint8_t *key, size_t len, uint32_t seed)
+{
+ uint32_t h = seed;
+ uint32_t k;
+ /* Read in groups of 4. */
+ for (size_t i = len >> 2; i; i--) {
+ memcpy(&k, key, sizeof(uint32_t));
+ key += sizeof(uint32_t);
+ h ^= murmur_32_scramble(k);
+ h = (h << 13) | (h >> 19);
+ h = h * 5 + 0xe6546b64;
+ }
+ /* Read the rest. */
+ k = 0;
+ for (size_t i = len & 3; i; i--) {
+ k <<= 8;
+ k |= key[i - 1];
+ }
+ h ^= murmur_32_scramble(k);
+ /* Finalize. */
+ h ^= len;
+ h ^= h >> 16;
+ h *= 0x85ebca6b;
+ h ^= h >> 13;
+ h *= 0xc2b2ae35;
+ h ^= h >> 16;
+ return h;
+}
diff --git a/src/parse.c b/src/parse.c
index 23b6a2f..33ca556 100644
--- a/src/parse.c
+++ b/src/parse.c
@@ -1,4 +1,5 @@
-// Just for debugging purposes
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// Just for testing purposes
// -> parses custom bruijn syntax
#include <stdio.h>
diff --git a/src/reducer.c b/src/reducer.c
index 2a44fcc..546a550 100644
--- a/src/reducer.c
+++ b/src/reducer.c
@@ -1,9 +1,15 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
// based on the RKNL abstract machine
+
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
+#include <string.h>
#include <reducer.h>
+#include <gc.h>
+#include <murmur3.h>
+#include <hamt.h>
#include <term.h>
struct stack {
@@ -11,19 +17,9 @@ struct stack {
struct stack *next;
};
-#define STORE_SIZE 128 // hashmap // TODO: Optimize?
-struct store {
- struct stack *stack;
-};
-
-struct store_data {
- int key;
- void *data;
-};
-
struct closure {
struct term *term;
- struct store (*store)[STORE_SIZE];
+ HAMT store;
};
struct box {
@@ -41,7 +37,7 @@ struct conf {
union {
struct { // closure
struct term *term;
- struct store (*store)[STORE_SIZE];
+ HAMT store;
struct stack *stack;
} econf; // blue
@@ -63,91 +59,16 @@ static struct stack *stack_push(struct stack *stack, void *data)
struct stack *new = malloc(sizeof(*new));
new->data = data;
new->next = stack;
- printf("Pushing %p to %p => %p\n", data, (void *)stack, (void *)new);
return new;
}
static struct stack *stack_next(struct stack *stack)
{
- printf("Popping %p => %p\n", (void *)stack, (void *)stack->next);
return stack->next;
}
-// no deep cloning for now // TODO: deep clone needed?
-static struct stack *stack_clone(struct stack *stack)
-{
- struct stack *new = 0;
- struct stack *iterator = stack;
- while (iterator) {
- new = stack_push(new, iterator->data);
- iterator = stack_next(iterator);
- }
- return new;
-}
-
-// no deep cloning for now // TODO: deep clone needed?
-static struct store (*store_clone(struct store (*store)[STORE_SIZE]))[STORE_SIZE]
-{
- struct store(*new)[STORE_SIZE] =
- calloc(1, STORE_SIZE * sizeof(struct store));
-
- for (int key = 0; key < STORE_SIZE; key++) {
- struct store *list = &(*store)[key % STORE_SIZE];
- if (list->stack)
- (*new)[key].stack = stack_clone(list->stack);
- }
- return new;
-}
-
-static int store_replace(struct store (*store)[STORE_SIZE], int key, void *data)
-{
- struct store *elem = &(*store)[key % STORE_SIZE];
- struct stack *iterator = elem->stack;
- while (iterator) {
- struct store_data *keyed = iterator->data;
- if (keyed->key == key) {
- keyed->data = data;
- printf("Replaced %d\n", key);
- return 1;
- }
- iterator = stack_next(iterator);
- }
- return 0;
-}
-
-static struct store (*store_push(struct store (*store)[STORE_SIZE], int key,
- void *data))[STORE_SIZE]
-{
- printf("Storing %p with %d (%d)\n", data, key, key % STORE_SIZE);
- if (store_replace(store, key, data))
- return store;
- struct store *elem = &(*store)[key % STORE_SIZE];
- struct store_data *keyed = malloc(sizeof(*keyed));
- keyed->key = key;
- keyed->data = data;
- elem->stack = stack_push(elem->stack, keyed);
- return store;
-}
-
-static void *store_get(struct store (*store)[STORE_SIZE], int key)
-{
- printf("Wanting %d (%d)\n", key, key % STORE_SIZE);
- struct store *elem = &(*store)[key % STORE_SIZE];
- struct stack *iterator = elem->stack;
- while (iterator) {
- struct store_data *keyed = iterator->data;
- if (keyed->key == key) {
- printf("Got it: %p\n", keyed->data);
- return keyed->data;
- }
- iterator = stack_next(iterator);
- }
- printf("Couldn't find it. Anyways..\n");
- return 0; // => unbound variable
-}
-
-static void econf(struct conf *conf, struct term *term,
- struct store (*store)[STORE_SIZE], struct stack *stack)
+static void econf(struct conf *conf, struct term *term, HAMT store,
+ struct stack *stack)
{
conf->type = ECONF;
conf->u.econf.term = term;
@@ -162,12 +83,11 @@ static void cconf(struct conf *conf, struct stack *stack, struct term *term)
conf->u.cconf.term = term;
}
-static int transition_1(struct term **term, struct store (**store)[STORE_SIZE],
- struct stack **stack)
+static int transition_1(struct term **term, HAMT *store, struct stack **stack)
{
struct closure *closure = malloc(sizeof(*closure));
closure->term = (*term)->u.app.rhs;
- closure->store = store_clone(*store);
+ closure->store = *store;
struct term *app = new_term(APP);
app->u.app.lhs = new_term(VAR);
@@ -177,24 +97,19 @@ static int transition_1(struct term **term, struct store (**store)[STORE_SIZE],
*term = (*term)->u.app.lhs;
*store = *store;
*stack = stack_push(*stack, app);
+
return 0;
}
-static int transition_2(struct stack **stack, struct term **term,
- struct store (**store)[STORE_SIZE])
+static int transition_2(struct stack **stack, struct term **term, HAMT store)
{
struct box *box = malloc(sizeof(*box));
box->state = TODO;
box->term = 0;
- // TODO: necessary?
- struct term *abs = new_term(ABS);
- abs->u.abs.name = (*term)->u.abs.name;
- abs->u.abs.term = (*term)->u.abs.term;
-
struct closure *closure = malloc(sizeof(*closure));
- closure->term = abs;
- closure->store = store_clone(*store);
+ closure->term = *term;
+ closure->store = store;
struct cache *cache = malloc(sizeof(*cache));
cache->box = box;
@@ -204,17 +119,16 @@ static int transition_2(struct stack **stack, struct term **term,
*stack = *stack;
*term = new_term(CACHE);
(*term)->u.other = cache;
+
return 0;
}
-static int transition_3(struct term **term, struct store (**store)[STORE_SIZE],
- struct stack **stack, struct box *box)
+static int transition_3(struct term **term, HAMT *store, struct stack **stack,
+ struct box *box)
{
assert(box->term->type == CLOSURE);
struct closure *closure = box->term->u.other;
- print_term(closure->term);
- printf("\n");
struct cache *cache = malloc(sizeof(*cache));
cache->box = box;
@@ -226,6 +140,8 @@ static int transition_3(struct term **term, struct store (**store)[STORE_SIZE],
*term = closure->term;
*store = closure->store;
*stack = stack_push(*stack, cache_term);
+
+ free(closure);
return 0;
}
@@ -240,7 +156,6 @@ static int transition_4(struct stack **stack, struct term **term,
static int transition_5(struct stack **stack, struct term **term,
struct cache *cache)
{
- printf("Setting %p\n", (void *)cache->box);
cache->box->state = DONE;
cache->box->term = *term;
@@ -249,23 +164,21 @@ static int transition_5(struct stack **stack, struct term **term,
return 0;
}
-static int transition_6(struct term **term, struct store (**store)[STORE_SIZE],
- struct stack **stack, struct term *peek_term,
- struct closure *closure)
+static int transition_6(struct term **term, HAMT *store, struct stack **stack,
+ struct term *peek_term, struct closure *closure)
{
struct box *box = malloc(sizeof(*box));
box->state = TODO;
box->term = peek_term->u.app.rhs;
*term = closure->term->u.abs.term;
- *store = store_push(closure->store, closure->term->u.abs.name, box);
+ *store = hamt_pset(closure->store, &closure->term->u.abs.name, box);
*stack = stack_next(*stack);
return 0;
}
-static int transition_7(struct term **term, struct store (**store)[STORE_SIZE],
- struct stack **stack, struct box *box,
- struct closure *closure)
+static int transition_7(struct term **term, HAMT *store, struct stack **stack,
+ struct box *box, struct closure *closure)
{
int x = name_generator();
@@ -286,7 +199,8 @@ static int transition_7(struct term **term, struct store (**store)[STORE_SIZE],
abs->u.abs.term = new_term(VAR);
*term = closure->term->u.abs.term;
- *store = store_push(closure->store, closure->term->u.abs.name, var_box);
+ *store = hamt_pset(closure->store, (void *)&closure->term->u.abs.name,
+ var_box);
*stack = stack_push(*stack, cache_term);
*stack = stack_push(*stack, abs);
return 0;
@@ -300,8 +214,8 @@ static int transition_8(struct stack **stack, struct term **term,
return 0;
}
-static int transition_9(struct term **term, struct store (**store)[STORE_SIZE],
- struct stack **stack, struct term *peek_term)
+static int transition_9(struct term **term, HAMT *store, struct stack **stack,
+ struct term *peek_term)
{
struct closure *closure = peek_term->u.app.rhs->u.other;
@@ -339,41 +253,40 @@ static int transition_11(struct stack **stack, struct term **term,
return 0;
}
-static int transition_closure(struct conf *conf)
+static int transition_closure(struct conf *conf, int i,
+ void (*callback)(int, char))
{
struct term *term = conf->u.econf.term;
- struct store(*store)[STORE_SIZE] = conf->u.econf.store;
+ HAMT store = conf->u.econf.store;
struct stack *stack = conf->u.econf.stack;
- printf("ECONF: %p %p %p\n", (void *)term, (void *)store, (void *)stack);
int ret = 1;
switch (term->type) {
case APP: // (1)
- printf("(1)\n");
+ callback(i, '1');
ret = transition_1(&term, &store, &stack);
econf(conf, term, store, stack);
return ret;
case ABS: // (2)
- printf("(2)\n");
- ret = transition_2(&stack, &term, &store);
+ callback(i, '2');
+ ret = transition_2(&stack, &term, store);
cconf(conf, stack, term);
return ret;
case VAR:;
- struct box *box = store_get(store, term->u.var.name);
+ /* printf("%p\n", hamt_get); */
+ struct box *box = hamt_get(store, &term->u.var.name);
if (!box) {
box = malloc(sizeof(*box));
box->state = DONE;
- // TODO: Using term directly is probably fine
- box->term = new_term(VAR);
- box->term->u.var.name = term->u.var.name;
+ box->term = term;
}
if (box->state == TODO) { // (3)
- printf("(3)\n");
+ callback(i, '3');
ret = transition_3(&term, &store, &stack, box);
econf(conf, term, store, stack);
return ret;
} else if (box->state == DONE) { // (4)
- printf("(4)\n");
+ callback(i, '4');
ret = transition_4(&stack, &term, box);
cconf(conf, stack, term);
return ret;
@@ -386,11 +299,11 @@ static int transition_closure(struct conf *conf)
}
}
-static int transition_computed(struct conf *conf)
+static int transition_computed(struct conf *conf, int i,
+ void (*callback)(int, char))
{
struct stack *stack = conf->u.cconf.stack;
struct term *term = conf->u.cconf.term;
- printf("CCONF: %p %p\n", (void *)stack, (void *)term);
if (!stack) {
fprintf(stderr, "Invalid stack!\n");
return 1;
@@ -401,7 +314,7 @@ static int transition_computed(struct conf *conf)
struct cache *cache = peek_term->u.other;
struct term *cache_term = cache->term;
if (cache_term->type == VAR && !cache_term->u.var.name) {
- printf("(5)\n");
+ callback(i, '5');
ret = transition_5(&stack, &term, cache);
cconf(conf, stack, term);
return ret;
@@ -414,8 +327,8 @@ static int transition_computed(struct conf *conf)
struct closure *closure =
((struct cache *)term->u.other)->term->u.other;
if (closure->term->type == ABS) {
- printf("(6)\n");
- struct store(*store)[STORE_SIZE];
+ callback(i, '6');
+ HAMT store;
ret = transition_6(&term, &store, &stack, peek_term,
closure);
econf(conf, term, store, stack);
@@ -429,14 +342,14 @@ static int transition_computed(struct conf *conf)
((struct cache *)term->u.other)->term->u.other;
if (closure->term->type == ABS && box->state == TODO &&
!box->term) { // (7)
- printf("(7)\n");
- struct store(*store)[STORE_SIZE];
+ callback(i, '7');
+ HAMT store;
ret = transition_7(&term, &store, &stack, box, closure);
econf(conf, term, store, stack);
return ret;
}
if (closure->term->type == ABS && box->state == DONE) { // (8)
- printf("(8)\n");
+ callback(i, '8');
ret = transition_8(&stack, &term, box);
cconf(conf, stack, term);
return ret;
@@ -446,8 +359,8 @@ static int transition_computed(struct conf *conf)
peek_term->u.app.lhs->type == VAR &&
!peek_term->u.app.lhs->u.var.name &&
peek_term->u.app.rhs->type == CLOSURE) { // (9)
- printf("(9)\n");
- struct store(*store)[STORE_SIZE];
+ callback(i, '9');
+ HAMT store;
ret = transition_9(&term, &store, &stack, peek_term);
econf(conf, term, store, stack);
return ret;
@@ -455,7 +368,7 @@ static int transition_computed(struct conf *conf)
if (peek_term && peek_term->type == APP &&
peek_term->u.app.rhs->type == VAR &&
!peek_term->u.app.rhs->u.var.name) { // (10)
- printf("(10)\n");
+ callback(i, 'A');
ret = transition_10(&stack, &term, peek_term);
cconf(conf, stack, term);
return ret;
@@ -463,7 +376,7 @@ static int transition_computed(struct conf *conf)
if (peek_term && peek_term->type == ABS &&
peek_term->u.abs.term->type == VAR &&
!peek_term->u.abs.term->u.var.name) { // (11)
- printf("(11)\n");
+ callback(i, 'B');
ret = transition_11(&stack, &term, peek_term);
cconf(conf, stack, term);
return ret;
@@ -476,35 +389,63 @@ static int transition_computed(struct conf *conf)
return 1;
}
-static int transition(struct conf *conf)
+static int transition(struct conf *conf, int i, void (*callback)(int, char))
{
if (conf->type == ECONF) {
- return transition_closure(conf);
+ return transition_closure(conf, i, callback);
} else if (conf->type == CCONF) {
- return transition_computed(conf);
+ return transition_computed(conf, i, callback);
}
fprintf(stderr, "Invalid transition state %x\n", conf->type);
return 1;
}
-static struct conf *for_each_state(struct conf *conf)
+static struct conf *for_each_state(struct conf *conf, int i,
+ void (*callback)(int, char))
{
- int ret = transition(conf);
- return ret ? conf : for_each_state(conf);
+ int ret = 0;
+ while (!ret)
+ ret = transition(conf, i++, callback);
+ return conf;
}
-struct term *reduce(struct term *term)
+static int hash_var_equal(const void *lhs, const void *rhs)
{
+ /* return memcmp(lhs, rhs, sizeof(int)); */
+ return *(const int *)lhs != *(const int *)rhs;
+}
+
+static uint32_t hash_var(const void *key, const size_t gen)
+{
+ return murmur3_32((const uint8_t *)key, sizeof(int), gen);
+}
+
+static void nop(void *addr)
+{
+ (void)nop;
+}
+
+struct term *reduce(struct term *term, void (*callback)(int, char))
+{
+ /* GC_set_find_leak(1); */
+ /* GC_INIT(); */
+
struct stack stack = { 0 };
- struct store store[STORE_SIZE] = { 0 };
+
+ struct hamt_allocator allocator = { GC_malloc, GC_realloc, nop };
+ HAMT store = hamt_create(hash_var, hash_var_equal, &allocator);
+ /* HAMT store = hamt_create(hash_var, hash_var_equal, &hamt_allocator_default); */
struct conf conf = {
.type = ECONF,
.u.econf.term = term,
- .u.econf.store = &store,
+ .u.econf.store = store,
.u.econf.stack = &stack,
};
- for_each_state(&conf);
+ for_each_state(&conf, 0, callback);
assert(conf.type == CCONF);
- return duplicate_term(conf.u.cconf.term);
+
+ struct term *ret = duplicate_term(conf.u.cconf.term);
+ hamt_delete(store);
+ return ret;
}
diff --git a/src/term.c b/src/term.c
index 5189073..67b6855 100644
--- a/src/term.c
+++ b/src/term.c
@@ -1,3 +1,5 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+
#include <stdlib.h>
#include <assert.h>
#include <stdio.h>
@@ -6,7 +8,7 @@
static int name_generator(void)
{
- static int current = 0x424242; // TODO: idk?
+ static int current = 0x4242; // TODO: idk?
return current++;
}
@@ -121,7 +123,7 @@ struct term *duplicate_term(struct term *term)
default:
fprintf(stderr, "Invalid type %d\n", term->type);
}
- return 0;
+ return term;
}
int alpha_equivalency(struct term *a, struct term *b)