From cbd21e1da0d763225e7ea3594d4e6d8e96863790 Mon Sep 17 00:00:00 2001 From: Marvin Borner Date: Tue, 30 May 2023 23:05:30 +0200 Subject: Added hash-based approach --- inc/lib/hash.h | 14 ++++++++++++++ inc/lib/hashmap.h | 31 +++++++++++++++++++++++++++++++ inc/lib/list.h | 15 +++++++++++++++ inc/lib/queue.h | 23 +++++++++++++++++++++++ inc/map.h | 16 ++++++++++++++++ inc/parse.h | 2 +- inc/queue.h | 24 ------------------------ inc/sharing.h | 11 +++++++++++ inc/term.h | 13 +++++++++++-- 9 files changed, 122 insertions(+), 27 deletions(-) create mode 100644 inc/lib/hash.h create mode 100644 inc/lib/hashmap.h create mode 100644 inc/lib/list.h create mode 100644 inc/lib/queue.h create mode 100644 inc/map.h delete mode 100644 inc/queue.h create mode 100644 inc/sharing.h (limited to 'inc') 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 +// SPDX-License-Identifier: MIT + +#ifndef SHARING_HASH_H +#define SHARING_HASH_H + +#include +#include + +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 +#include +#include + +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 +// 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/lib/queue.h b/inc/lib/queue.h new file mode 100644 index 0000000..b0d22ef --- /dev/null +++ b/inc/lib/queue.h @@ -0,0 +1,23 @@ +// Copyright (c) 2023, Marvin Borner +// SPDX-License-Identifier: MIT + +#ifndef SHARING_QUEUE_H +#define SHARING_QUEUE_H + +struct queue_node { + void *data; + struct queue_node *next; +}; + +struct queue { + struct queue_node *head; + struct queue_node *tail; +}; + +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 +// SPDX-License-Identifier: MIT + +#ifndef SHARING_MAP_H +#define SHARING_MAP_H + +#include + +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 -struct term *parse_blc(char **term); +struct term_handle parse_blc(char **term); #endif diff --git a/inc/queue.h b/inc/queue.h deleted file mode 100644 index 5a704b4..0000000 --- a/inc/queue.h +++ /dev/null @@ -1,24 +0,0 @@ -// Copyright (c) 2023, Marvin Borner -// SPDX-License-Identifier: MIT - -#ifndef SHARING_QUEUE_H -#define SHARING_QUEUE_H - -#include - -struct queue_node { - void *data; - struct queue_node *next; -}; - -struct queue { - struct queue_node *head; - struct queue_node *tail; -}; - -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); - -#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 +// SPDX-License-Identifier: MIT + +#ifndef SHARING_SHARING_H +#define SHARING_SHARING_H + +#include + +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 -#include +#include +#include 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); -- cgit v1.2.3