diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/free.c | 41 | ||||
| -rw-r--r-- | src/log.c | 4 | ||||
| -rw-r--r-- | src/main.c | 5 | ||||
| -rw-r--r-- | src/parse.c | 14 | ||||
| -rw-r--r-- | src/term.c | 25 | ||||
| -rw-r--r-- | src/tree.c | 61 |
6 files changed, 80 insertions, 70 deletions
diff --git a/src/free.c b/src/free.c deleted file mode 100644 index ecf1d9f..0000000 --- a/src/free.c +++ /dev/null @@ -1,41 +0,0 @@ -// Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> -// SPDX-License-Identifier: MIT - -#include <stdio.h> -#include <stdlib.h> - -#include <free.h> -#include <log.h> - -void free_term(struct term *term) -{ - switch (term->type) { - case ABS: - free_term(term->u.abs.term); - free(term); - break; - case APP: - free_term(term->u.app.lhs); - free_term(term->u.app.rhs); - free(term); - break; - case VAR: - free(term); - break; - case REF: - free(term); - break; - default: - fatal("invalid type %d\n", term->type); - } -} - -void free_bloc(struct bloc_parsed *bloc) -{ - for (size_t i = 0; i < bloc->length; i++) { - free_term(bloc->entries[i]); - } - - free(bloc->entries); - free(bloc); -} @@ -14,6 +14,8 @@ void debug(const char *format, ...) if (!debug_enabled) return; + fprintf(stderr, "[DEBUG] "); + va_list ap; va_start(ap, format); vfprintf(stderr, format, ap); @@ -27,6 +29,8 @@ void debug_enable(int enable) void fatal(const char *format, ...) { + fprintf(stderr, "[FATAL] "); + va_list ap; va_start(ap, format); vfprintf(stderr, format, ap); @@ -12,7 +12,6 @@ #include <tree.h> #include <parse.h> #include <build.h> -#include <free.h> // automatically generated using gengetopt #include "cmdline.h" @@ -25,7 +24,7 @@ static char *read_stdin(void) size_t size = 1; char *string = malloc(sizeof(char) * BUF_SIZE); if (!string) - return 0; + fatal("out of memory!\n"); string[0] = '\0'; while (fgets(buffer, BUF_SIZE, stdin)) { char *old = string; @@ -57,6 +56,8 @@ static char *read_file(const char *path) fseek(f, 0, SEEK_SET); char *string = malloc(fsize + 1); + if (!string) + fatal("out of memory!\n"); int ret = fread(string, fsize, 1, f); fclose(f); diff --git a/src/parse.c b/src/parse.c index b6645fd..9a8af45 100644 --- a/src/parse.c +++ b/src/parse.c @@ -111,6 +111,16 @@ struct bloc_parsed *parse_bloc(const void *bloc) return parsed; } +void free_bloc(struct bloc_parsed *bloc) +{ + for (size_t i = 0; i < bloc->length; i++) { + free_term(bloc->entries[i]); + } + + free(bloc->entries); + free(bloc); +} + static struct term *rec_bloc(struct term *term, struct bloc_parsed *bloc) { switch (term->type) { @@ -124,10 +134,8 @@ static struct term *rec_bloc(struct term *term, struct bloc_parsed *bloc) case VAR: break; case REF: - if (term->u.ref.index >= bloc->length) { + if (term->u.ref.index >= bloc->length) fatal("invalid entry reference\n"); - return 0; - } memcpy(term, bloc->entries[bloc->length - term->u.ref.index - 1], sizeof(*term)); @@ -12,7 +12,30 @@ struct term *new_term(term_type type) { struct term *term = malloc(sizeof(*term)); if (!term) - fatal("Out of memory!\n"); + fatal("out of memory!\n"); term->type = type; return term; } + +void free_term(struct term *term) +{ + switch (term->type) { + case ABS: + free_term(term->u.abs.term); + free(term); + break; + case APP: + free_term(term->u.app.lhs); + free_term(term->u.app.rhs); + free(term); + break; + case VAR: + free(term); + break; + case REF: + free(term); + break; + default: + fatal("invalid type %d\n", term->type); + } +} @@ -53,6 +53,8 @@ static struct list *list_end = 0; static struct list *list_add(struct list *list, void *data) { struct list *new = malloc(sizeof(*new)); + if (!new) + fatal("out of memory!\n"); new->next = list; new->data = data; new->val = list ? list->val + 1 : 1; // amount of trees in list @@ -79,10 +81,13 @@ static int hash_compare(const void *_a, const void *_b) } // applies the hash function to the tree's elements (similar to merkle trees) +// also creates a set of lists with deduplication candidates // TODO: as above: rethink hash choice static struct tree *build_tree(struct term *term, void **set) { struct tree *tree = malloc(sizeof(*tree)); + if (!tree) + fatal("out of memory!\n"); tree->type = term->type; tree->state = VALIDATED_TREE; tree->duplication_count = 1; @@ -120,6 +125,8 @@ static struct tree *build_tree(struct term *term, void **set) return tree; struct set_element *element = malloc(sizeof(*element)); + if (!element) + fatal("out of memory!\n"); element->hash = tree->hash; struct set_element **handle = tsearch(element, set, hash_compare); @@ -137,6 +144,8 @@ static struct tree *build_tree(struct term *term, void **set) static struct tree *clone_tree_root(struct tree *tree) { struct tree *new = malloc(sizeof(*new)); + if (!new) + fatal("out of memory!\n"); new->type = tree->type; new->hash = tree->hash; new->duplication_count = tree->duplication_count; @@ -226,6 +235,8 @@ static void ref_invalidated_tree(struct tree *tree) } } +// priority of candidate -> length of expression +// TODO: What about occurrence count (list length)? static pqueue_pri_t get_pri(void *a) { return ((struct tree *)((struct list *)a)->data)->size; @@ -240,14 +251,18 @@ struct list *tree_merge_duplicates(struct term *term) { debug("building the merkle tree and deduplication set\n"); + // get the deduplication candidates void *set = 0; build_tree(term, &set); if (!set) - return 0; + fatal("term too short\n"); // construct priority queue while deleting set + // ~> sorts the candidates by get_pri debug("constructing priority queue\n"); struct pqueue *prioritized = pqueue_init(2 << 15, cmp_pri, get_pri); + if (!prioritized) + fatal("can't create pqueue\n"); while (set) { struct set_element *element = *(struct set_element **)set; pqueue_insert(prioritized, element->list); @@ -265,33 +280,33 @@ struct list *tree_merge_duplicates(struct term *term) debug("iterating priority queue, invalidating duplicates\n"); struct list *iterator; while ((iterator = pqueue_pop(prioritized))) { + // only consider merging if they occur >1 times + if (iterator->val <= 1) + continue; + struct tree *head = iterator->data; + // skip if invalidated and not duplicated enough if (head->state != VALIDATED_TREE && - head->duplication_count >= - iterator->val) { // skip invalidated + head->duplication_count >= iterator->val) continue; - } - if (iterator->val > 1) { // needs merging - // clone root so it doesn't get replaced by a ref to itself - struct tree *cloned_head = clone_tree_root(head); - cloned_head->state = INVALIDATED_TREE; - final = list_add(final, cloned_head); - - // invalidate all subtrees - // invalidated trees will be replaced with a reference - struct list *list = iterator; - while (list) { - invalidate_tree(list->data, list->val); - - // keep a ref for later replacement - ((struct tree *)list->data)->state = - final->val - 1; - - invalidated = list_add(invalidated, list->data); - list = list->next; - } + // clone root so it doesn't get replaced by a ref to itself + struct tree *cloned_head = clone_tree_root(head); + cloned_head->state = INVALIDATED_TREE; + final = list_add(final, cloned_head); + + // invalidate all subtrees + // invalidated trees will be replaced with a reference + struct list *list = iterator; + while (list) { + invalidate_tree(list->data, list->val); + + // keep a ref for later replacement + ((struct tree *)list->data)->state = final->val - 1; + + invalidated = list_add(invalidated, list->data); + list = list->next; } } |