Added hash-based approach

8 files changed, 100 insertions, 5 deletions

diff --git a/inc/lib/hash.h b/inc/lib/hash.h
new file mode 100644
index 0000000..7cfad83
--- /dev/null
+++ b/inc/lib/hash.h
@@ -0,0 +1,14 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_HASH_H
+#define SHARING_HASH_H
+
+#include <stdint.h>
+#include <stddef.h>
+
+typedef uint64_t hash_t;
+
+hash_t hash(void *data, size_t len, uint64_t seed);
+
+#endif
diff --git a/inc/lib/hashmap.h b/inc/lib/hashmap.h
new file mode 100644
index 0000000..db70bdd
--- /dev/null
+++ b/inc/lib/hashmap.h
@@ -0,0 +1,31 @@
+// Copyright 2020 Joshua J Baker. All rights reserved.
+// Copyright 2023 Marvin Borner
+// Use of this source code is governed by an MIT-style
+// license that can be found in the LICENSE file.
+
+#ifndef SHARING_HASHMAP_H
+#define SHARING_HASHMAP_H
+
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdint.h>
+
+struct hashmap;
+
+struct hashmap *hashmap_new(size_t elsize, size_t cap,
+			    void (*elfree)(void *item));
+
+void hashmap_free(struct hashmap *map);
+void hashmap_clear(struct hashmap *map, bool update_cap);
+size_t hashmap_count(struct hashmap *map);
+bool hashmap_oom(struct hashmap *map);
+void *hashmap_probe(struct hashmap *map, uint64_t position);
+bool hashmap_scan(struct hashmap *map, bool (*iter)(void *item));
+bool hashmap_iter(struct hashmap *map, size_t *i, void **item);
+
+void *hashmap_get(struct hashmap *map, uint64_t hash);
+void *hashmap_delete(struct hashmap *map, uint64_t hash);
+void *hashmap_set(struct hashmap *map, void *item, uint64_t hash);
+void hashmap_set_grow_by_power(struct hashmap *map, size_t power);
+
+#endif
diff --git a/inc/lib/list.h b/inc/lib/list.h
new file mode 100644
index 0000000..b57d85b
--- /dev/null
+++ b/inc/lib/list.h
@@ -0,0 +1,15 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_LIST_H
+#define SHARING_LIST_H
+
+struct list {
+	void *data;
+	struct list *next;
+};
+
+struct list *list_add(struct list *list, void *data);
+void list_free(struct list *list);
+
+#endif
diff --git a/inc/queue.h b/inc/lib/queue.h
index 5a704b4..b0d22ef 100644
--- a/inc/queue.h
+++ b/inc/lib/queue.h
@@ -4,8 +4,6 @@
 #ifndef SHARING_QUEUE_H
 #define SHARING_QUEUE_H
 
-#include <stddef.h>
-
 struct queue_node {
 	void *data;
 	struct queue_node *next;
@@ -20,5 +18,6 @@ struct queue *queue_new(void);
 void queue_free(struct queue *queue);
 void queue_push(struct queue *queue, void *data);
 void *queue_pop(struct queue *queue);
+int queue_empty(struct queue *queue);
 
 #endif
diff --git a/inc/map.h b/inc/map.h
new file mode 100644
index 0000000..84d1ae5
--- /dev/null
+++ b/inc/map.h
@@ -0,0 +1,16 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_MAP_H
+#define SHARING_MAP_H
+
+#include <lib/hash.h>
+
+struct term *map_get(hash_t hash);
+void map_set(struct term *term, hash_t hash);
+void map_delete(struct term *term);
+void map_initialize(void);
+void map_destroy(void);
+void map_foreach(void (*func)(struct term *));
+
+#endif
diff --git a/inc/parse.h b/inc/parse.h
index 451647f..2b881e6 100644
--- a/inc/parse.h
+++ b/inc/parse.h
@@ -6,6 +6,6 @@
 
 #include <term.h>
 
-struct term *parse_blc(char **term);
+struct term_handle parse_blc(char **term);
 
 #endif
diff --git a/inc/sharing.h b/inc/sharing.h
new file mode 100644
index 0000000..7be84f4
--- /dev/null
+++ b/inc/sharing.h
@@ -0,0 +1,11 @@
+// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de>
+// SPDX-License-Identifier: MIT
+
+#ifndef SHARING_SHARING_H
+#define SHARING_SHARING_H
+
+#include <term.h>
+
+void blind_check(void);
+
+#endif
diff --git a/inc/term.h b/inc/term.h
index 3bc94eb..fe4b6b8 100644
--- a/inc/term.h
+++ b/inc/term.h
@@ -6,15 +6,24 @@
 
 #include <stddef.h>
 
-#include <queue.h>
+#include <lib/hash.h>
+#include <lib/queue.h>
 
 typedef enum { INV, ABS, APP, VAR } term_type_t;
 
+struct term_handle {
+	struct term *term;
+	hash_t hash;
+};
+
 struct term {
 	term_type_t type;
+	hash_t hash;
 	struct term *canonic;
 	char building;
 	struct queue *queue;
+	struct list *parents;
+	struct list *neighbours;
 	union {
 		struct {
 			struct term *term;
@@ -29,7 +38,7 @@ struct term {
 	} u;
 };
 
-struct term *term_new(term_type_t type);
+struct term *term_new(term_type_t type, hash_t hash);
 void term_free(struct term *term);
 void term_print(struct term *term);