diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.c | 6 | ||||
| -rw-r--r-- | src/map.c | 22 | ||||
| -rw-r--r-- | src/parse.c | 53 | ||||
| -rw-r--r-- | src/schedule.c | 36 |
4 files changed, 89 insertions, 28 deletions
@@ -7,6 +7,7 @@ #include <string.h> #include <map.h> +#include <schedule.h> #include <parse.h> #include <log.h> #include <lib/hash.h> @@ -54,8 +55,11 @@ int main(int argc, char *argv[]) char *orig_term = term; parse_blc(&term, 1); - free(orig_term); + + schedule_init(); + + schedule_destroy(); map_destroy(); return 0; } @@ -12,10 +12,10 @@ static struct hashmap *all_terms; static void deref_term(struct term *term) { if (term->type == ABS) { - deref_term(hashmap_get(all_terms, term->u.abs.term)); + deref_term(term->u.abs.term); } else if (term->type == APP) { - deref_term(hashmap_get(all_terms, term->u.app.lhs)); - deref_term(hashmap_get(all_terms, term->u.app.rhs)); + deref_term(term->u.app.lhs); + deref_term(term->u.app.rhs); } // TODO: remove from hashmap? @@ -51,3 +51,19 @@ void map_destroy(void) { hashmap_free(all_terms); } + +struct pqueue *map_to_pqueue(pqueue_cmp_pri_f cmppri, pqueue_get_pri_f getpri, + pqueue_set_pos_f setpos) +{ + size_t size = hashmap_count(all_terms) + 42; + struct pqueue *queue = pqueue_init(size, cmppri, getpri, setpos); + + size_t iter = 0; + void *iter_val; + while (hashmap_iter(all_terms, &iter, &iter_val)) { + struct term *term = *(struct term **)iter_val; + pqueue_insert(queue, term); + } + + return queue; +} diff --git a/src/parse.c b/src/parse.c index 24d2339..5445aea 100644 --- a/src/parse.c +++ b/src/parse.c @@ -8,9 +8,9 @@ #include <map.h> #include <log.h> -static int max_depth = 0; +static size_t max_depth = 0; -static struct term *new_term(term_type_t type, hash_t hash, int depth) +static struct term *new_term(term_type_t type, hash_t hash, size_t depth) { struct term *term = malloc(sizeof(*term)); if (!term) @@ -22,63 +22,68 @@ static struct term *new_term(term_type_t type, hash_t hash, int depth) return term; } -static hash_t abs_blc(char **term, int depth) +static void update_term(struct term *term, size_t depth) +{ + term->refs++; + if (depth < term->depth) // lower depths are more important + term->depth = depth; +} + +static struct term_handle abs_blc(char **term, size_t depth) { term_type_t res_type = ABS; - hash_t inner_hash = parse_blc(term, depth + 1); - hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), inner_hash); + struct term_handle inner = parse_blc(term, depth + 1); + hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), inner.hash); struct term *res_term; if ((res_term = map_get(res))) { - res_term->refs++; - res_term->depth = (res_term->depth + depth) / 2; + update_term(res_term, depth); } else { res_term = new_term(res_type, res, depth); - res_term->u.abs.term = inner_hash; + res_term->u.abs.term = inner.term; map_set(res_term, res); } - return res; + return (struct term_handle){ .term = res_term, .hash = res }; } -static hash_t app_blc(char **term, int depth) +static struct term_handle app_blc(char **term, size_t depth) { term_type_t res_type = APP; - hash_t lhs_hash = parse_blc(term, depth + 1); - hash_t rhs_hash = parse_blc(term, depth + 1); + struct term_handle lhs = parse_blc(term, depth + 1); + struct term_handle rhs = parse_blc(term, depth + 1); - hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), lhs_hash); - res = hash((uint8_t *)&res, sizeof(res), rhs_hash); + hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), lhs.hash); + res = hash((uint8_t *)&res, sizeof(res), rhs.hash); struct term *res_term; if ((res_term = map_get(res))) { - res_term->refs++; - res_term->depth = (res_term->depth + depth) / 2; + update_term(res_term, depth); } else { res_term = new_term(res_type, res, depth); - res_term->u.app.lhs = lhs_hash; - res_term->u.app.rhs = rhs_hash; + res_term->u.app.lhs = lhs.term; + res_term->u.app.rhs = rhs.term; map_set(res_term, res); } - return res; + return (struct term_handle){ .term = res_term, .hash = res }; } -static hash_t var_blc(int index, int depth) +static struct term_handle var_blc(int index, size_t depth) { term_type_t res_type = VAR; hash_t res = hash((uint8_t *)&res_type, sizeof(res_type), index); struct term *res_term; if ((res_term = map_get(res))) { - res_term->refs++; - res_term->depth = (res_term->depth + depth) / 2; + update_term(res_term, depth); } else { res_term = new_term(res_type, res, depth); res_term->u.var.index = index; map_set(res_term, res); } - return res; + + return (struct term_handle){ .term = res_term, .hash = res }; } int parse_get_max_depth(void) @@ -88,7 +93,7 @@ int parse_get_max_depth(void) // TODO: bit parse_bblc // TODO: BLoC support (needs entry reference index sth two passes) -hash_t parse_blc(char **term, int depth) +struct term_handle parse_blc(char **term, size_t depth) { if (depth > max_depth) max_depth = depth; diff --git a/src/schedule.c b/src/schedule.c index e69de29..e746a7f 100644 --- a/src/schedule.c +++ b/src/schedule.c @@ -0,0 +1,36 @@ +// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> +// SPDX-License-Identifier: MIT + +#include <schedule.h> +#include <lib/pqueue.h> +#include <parse.h> +#include <map.h> + +static struct pqueue *queue; + +static pqueue_pri_t get_pri(void *a) +{ + struct term *term = a; + return (parse_get_max_depth() - term->depth + 1) * term->refs; +} + +static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr) +{ + return next < curr; +} + +static void set_pos(void *a, size_t position) +{ + (void)a; + (void)position; +} + +void schedule_init(void) +{ + queue = map_to_pqueue(cmp_pri, get_pri, set_pos); +} + +void schedule_destroy(void) +{ + pqueue_free(queue); +} |