diff options
| -rw-r--r-- | inc/build.h | 2 | ||||
| -rw-r--r-- | inc/pqueue.h | 106 | ||||
| -rw-r--r-- | inc/tree.h | 1 | ||||
| -rw-r--r-- | options.ggo | 4 | ||||
| -rw-r--r-- | src/build.c | 43 | ||||
| -rw-r--r-- | src/main.c | 9 | ||||
| -rw-r--r-- | src/parse.c | 4 | ||||
| -rw-r--r-- | src/pqueue.c | 154 | ||||
| -rw-r--r-- | src/print.c | 9 | ||||
| -rw-r--r-- | src/tree.c | 93 |
10 files changed, 351 insertions, 74 deletions
diff --git a/inc/build.h b/inc/build.h index 4e9d634..2d99f9d 100644 --- a/inc/build.h +++ b/inc/build.h @@ -6,7 +6,9 @@ #include <spec.h> #include <tree.h> +#include <parse.h> void write_bloc(struct list *table, const char *path); +void write_blc(struct bloc_parsed *bloc, const char *path); #endif diff --git a/inc/pqueue.h b/inc/pqueue.h new file mode 100644 index 0000000..3b4752d --- /dev/null +++ b/inc/pqueue.h @@ -0,0 +1,106 @@ +/* + * Copyright (c) 2014, Volkan Yazıcı <volkan.yazici@gmail.com> + * Copyright (c) 2014, Marvin Borner <dev@marvinborner.de> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR + * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +/** + * @file pqueue.h + * @brief Priority Queue function declarations + * + * @{ + */ + +#ifndef PQUEUE_H +#define PQUEUE_H + +#include <stddef.h> +#include <stdio.h> + +/** priority data type */ +typedef unsigned long long pqueue_pri_t; + +/** callback functions to get/set/compare the priority of an element */ +typedef pqueue_pri_t (*pqueue_get_pri_f)(void *a); +typedef int (*pqueue_cmp_pri_f)(pqueue_pri_t next, pqueue_pri_t curr); + +/** callback functions to get/set the position of an element */ +typedef size_t (*pqueue_get_pos_f)(void *a); +typedef void (*pqueue_set_pos_f)(void *a, size_t pos); + +/** debug callback function to print a entry */ +typedef void (*pqueue_print_entry_f)(FILE *out, void *a); + +/** the priority queue handle */ +struct pqueue { + size_t size; /**< number of elements in this queue */ + size_t avail; /**< slots available in this queue */ + size_t step; /**< growth stepping setting */ + pqueue_cmp_pri_f cmppri; /**< callback to compare nodes */ + pqueue_get_pri_f getpri; /**< callback to get priority of a node */ + void **d; /**< The actualy queue in binary heap form */ +}; + +/** + * initialize the queue + * + * @param n the initial estimate of the number of queue items for which memory + * should be preallocated + * @param cmppri The callback function to run to compare two elements + * This callback should return 0 for 'lower' and non-zero + * for 'higher', or vice versa if reverse priority is desired + * @param getpri the callback function to run to set a score to an element + * + * @return the handle or NULL for insufficent memory + */ +struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri, + pqueue_get_pri_f getpri); + +/** + * free all memory used by the queue + * @param q the queue + */ +void pqueue_free(struct pqueue *q); + +/** + * return the size of the queue. + * @param q the queue + */ +size_t pqueue_size(struct pqueue *q); + +/** + * insert an item into the queue. + * @param q the queue + * @param d the item + * @return 0 on success + */ +int pqueue_insert(struct pqueue *q, void *d); + +/** + * pop the highest-ranking item from the queue. + * @param q the queue + * @return NULL on error, otherwise the entry + */ +void *pqueue_pop(struct pqueue *q); + +#endif @@ -18,6 +18,7 @@ struct tree { uint32_t hash; int state; // zero or index to ref int size; // blc length + int duplication_count; // needed count to be considered for deduplication union { struct { struct tree *term; diff --git a/options.ggo b/options.ggo index ec082f3..10c30e3 100644 --- a/options.ggo +++ b/options.ggo @@ -3,7 +3,7 @@ version "1.0" purpose "Tool for converting to/from BLC and BLoC" option "input" i "input file" string required -option "output" o "output file" default="out.bloc" string optional -option "from-blc" b "convert from BLC to BLoC" flag on +option "output" o "output file" default="out" string optional +option "from-blc" b "convert from BLC to BLoC" flag off option "from-bloc" B "convert from BLoC to BLC" flag off option "dump" d "dump bloc file" dependon="from-bloc" flag off diff --git a/src/build.c b/src/build.c index 7867e31..d8a8146 100644 --- a/src/build.c +++ b/src/build.c @@ -6,8 +6,6 @@ #include <stdio.h> #include <build.h> -#include <free.h> -#include <parse.h> static void write_bit(char val, FILE *file, char *byte, int *bit) { @@ -84,3 +82,44 @@ void write_bloc(struct list *table, const char *path) fclose(file); } + +static void fprint_bloc_blc(struct term *term, struct bloc_parsed *bloc, + FILE *file) +{ + switch (term->type) { + case ABS: + fprintf(file, "00"); + fprint_bloc_blc(term->u.abs.term, bloc, file); + break; + case APP: + fprintf(file, "01"); + fprint_bloc_blc(term->u.app.lhs, bloc, file); + fprint_bloc_blc(term->u.app.rhs, bloc, file); + break; + case VAR: + for (int i = 0; i <= term->u.var.index; i++) + fprintf(file, "1"); + fprintf(file, "0"); + break; + case REF: + if (term->u.ref.index + 1 >= bloc->length) + fprintf(stderr, "invalid ref index %ld\n", + term->u.ref.index); + fprint_bloc_blc( + bloc->entries[bloc->length - term->u.ref.index - 2], + bloc, file); + break; + default: + fprintf(stderr, "invalid type %d\n", term->type); + } +} + +void write_blc(struct bloc_parsed *bloc, const char *path) +{ + FILE *file = fopen(path, "wb"); + + fprint_bloc_blc(bloc->entries[bloc->length - 1], bloc, file); + fprintf(file, "\n"); + + fclose(file); +} @@ -97,15 +97,16 @@ int main(int argc, char **argv) return 0; } - if (args.from_bloc_flag) { + if (args.from_bloc_flag && !args.from_blc_flag) { struct bloc_parsed *bloc = parse_bloc(input); if (args.dump_flag) print_bloc(bloc); - printf("%d\n", bloc->length); - // TODO: Write file as BLC + write_blc(bloc, args.output_arg); free(input); free_bloc(bloc); + return 0; } - return 0; + fprintf(stderr, "invalid options: use --help for information\n"); + return 1; } diff --git a/src/parse.c b/src/parse.c index ff01bf0..6e08d2e 100644 --- a/src/parse.c +++ b/src/parse.c @@ -127,7 +127,9 @@ static struct term *rec_bloc(struct term *term, struct bloc_parsed *bloc) fprintf(stderr, "invalid entry reference\n"); return 0; } - memcpy(term, bloc->entries[term->u.ref.index], sizeof(*term)); + memcpy(term, + bloc->entries[bloc->length - term->u.ref.index - 1], + sizeof(*term)); break; default: fprintf(stderr, "invalid type %d\n", term->type); diff --git a/src/pqueue.c b/src/pqueue.c new file mode 100644 index 0000000..8e7eca7 --- /dev/null +++ b/src/pqueue.c @@ -0,0 +1,154 @@ +/* + * Copyright (c) 2014, Volkan Yazıcı <volkan.yazici@gmail.com> + * Copyright (c) 2023, Marvin Borner <dev@marvinborner.de> + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions are met: + * + * 1. Redistributions of source code must retain the above copyright notice, this + * list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright notice, + * this list of conditions and the following disclaimer in the documentation + * and/or other materials provided with the distribution. + * + * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + * DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE FOR + * ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + * (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; + * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND + * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS + * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ + +#include <stdlib.h> +#include <stdio.h> +#include <string.h> + +#include <pqueue.h> + +#define left(i) ((i) << 1) +#define right(i) (((i) << 1) + 1) +#define parent(i) ((i) >> 1) + +struct pqueue *pqueue_init(size_t n, pqueue_cmp_pri_f cmppri, + pqueue_get_pri_f getpri) +{ + struct pqueue *q; + + if (!(q = malloc(sizeof(struct pqueue)))) + return NULL; + + /* Need to allocate n+1 elements since element 0 isn't used. */ + if (!(q->d = malloc((n + 1) * sizeof(void *)))) { + free(q); + return NULL; + } + + q->size = 1; + q->avail = q->step = (n + 1); /* see comment above about n+1 */ + q->cmppri = cmppri; + q->getpri = getpri; + + return q; +} + +void pqueue_free(struct pqueue *q) +{ + free(q->d); + free(q); +} + +size_t pqueue_size(struct pqueue *q) +{ + /* queue element 0 exists but doesn't count since it isn't used. */ + return (q->size - 1); +} + +static void bubble_up(struct pqueue *q, size_t i) +{ + size_t parent_node; + void *moving_node = q->d[i]; + pqueue_pri_t moving_pri = q->getpri(moving_node); + + for (parent_node = parent(i); + ((i > 1) && q->cmppri(q->getpri(q->d[parent_node]), moving_pri)); + i = parent_node, parent_node = parent(i)) { + q->d[i] = q->d[parent_node]; + } + + q->d[i] = moving_node; +} + +static size_t maxchild(struct pqueue *q, size_t i) +{ + size_t child_node = left(i); + + if (child_node >= q->size) + return 0; + + if ((child_node + 1) < q->size && + q->cmppri(q->getpri(q->d[child_node]), + q->getpri(q->d[child_node + 1]))) + child_node++; /* use right child instead of left */ + + return child_node; +} + +static void percolate_down(struct pqueue *q, size_t i) +{ + size_t child_node; + void *moving_node = q->d[i]; + pqueue_pri_t moving_pri = q->getpri(moving_node); + + while ((child_node = maxchild(q, i)) && + q->cmppri(moving_pri, q->getpri(q->d[child_node]))) { + q->d[i] = q->d[child_node]; + i = child_node; + } + + q->d[i] = moving_node; +} + +int pqueue_insert(struct pqueue *q, void *d) +{ + void *tmp; + size_t i; + size_t newsize; + + if (!q) + return 1; + + /* allocate more memory if necessary */ + if (q->size >= q->avail) { + newsize = q->size + q->step; + if (!(tmp = realloc(q->d, sizeof(void *) * newsize))) + return 1; + q->d = tmp; + q->avail = newsize; + } + + /* insert item */ + i = q->size++; + q->d[i] = d; + bubble_up(q, i); + + return 0; +} + +void *pqueue_pop(struct pqueue *q) +{ + void *head; + + if (!q || q->size == 1) + return NULL; + + head = q->d[1]; + q->d[1] = q->d[--q->size]; + percolate_down(q, 1); + + return head; +} diff --git a/src/print.c b/src/print.c index d6636c5..ddbb730 100644 --- a/src/print.c +++ b/src/print.c @@ -56,11 +56,14 @@ void print_blc(struct term *term) void print_bloc(struct bloc_parsed *bloc) { printf("\n=== START BLOC ===\n"); - printf("| number of entries: %ld\n", bloc->length); - for (size_t i = 0; i < bloc->length; i++) { - printf("| entry %ld: ", i); + printf("| entries:\t%ld\n", bloc->length); + for (size_t i = 0; i < bloc->length - 1; i++) { + printf("| entry %ld:\t", bloc->length - i - 2); print_bruijn(bloc->entries[i]); printf("\n"); } + printf("| final:\t"); + print_bruijn(bloc->entries[bloc->length - 1]); + printf("\n"); printf("=== END BLOC ===\n\n"); } @@ -10,6 +10,7 @@ #include <string.h> #include <stdlib.h> +#include <pqueue.h> #include <tree.h> static inline uint32_t murmur_32_scramble(uint32_t k) @@ -57,34 +58,6 @@ static struct list *list_add(struct list *list, void *data) return new; } -static struct list *list_add_prioritized(struct list *list, struct list *sub) -{ - struct list *new = malloc(sizeof(*new)); - /* new->val = ((struct tree *)sub->data)->size * sub->val; */ - new->val = ((struct tree *)sub->data)->size; - new->data = sub; - - if (!list) { - new->next = list; - return new; - } - - if (new->val >= list->val) { // insert at head - new->next = list; - return new; - } - - struct list *iterator = list; - while (iterator->next && new->val < iterator->next->val) { - iterator = iterator->next; - } - - new->next = iterator->next; - iterator->next = new; - - return list; -} - // element of the tsearch tree struct set_element { uint32_t hash; @@ -111,6 +84,7 @@ static struct tree *build_tree(struct term *term, void **set) struct tree *tree = malloc(sizeof(*tree)); tree->type = term->type; tree->state = VALIDATED_TREE; + tree->duplication_count = 1; switch (term->type) { case ABS: @@ -165,6 +139,7 @@ static struct tree *clone_tree_root(struct tree *tree) struct tree *new = malloc(sizeof(*new)); new->type = tree->type; new->hash = tree->hash; + new->duplication_count = tree->duplication_count; switch (tree->type) { case ABS: @@ -186,16 +161,17 @@ static struct tree *clone_tree_root(struct tree *tree) return new; } -static void invalidate_tree(struct tree *tree) +static void invalidate_tree(struct tree *tree, int duplication_count) { tree->state = INVALIDATED_TREE; + tree->duplication_count = duplication_count; switch (tree->type) { case ABS: - invalidate_tree(tree->u.abs.term); + invalidate_tree(tree->u.abs.term, duplication_count); break; case APP: - invalidate_tree(tree->u.app.lhs); - invalidate_tree(tree->u.app.rhs); + invalidate_tree(tree->u.app.lhs, duplication_count); + invalidate_tree(tree->u.app.rhs, duplication_count); break; case VAR: break; @@ -250,22 +226,14 @@ static void ref_invalidated_tree(struct tree *tree) } } -static void free_prioritized_list(struct list *list) +static pqueue_pri_t get_pri(void *a) { - struct list *iterator = list; - while (iterator) { - struct list *temp = iterator->next; - - struct list *subiter = iterator->data; - while (subiter) { - struct list *subtemp = subiter->next; - free(subiter); - subiter = subtemp; - } + return ((struct tree *)((struct list *)a)->data)->size; +} - free(iterator); - iterator = temp; - } +static int cmp_pri(pqueue_pri_t next, pqueue_pri_t curr) +{ + return next < curr; } struct list *tree_merge_duplicates(struct term *term) @@ -276,10 +244,10 @@ struct list *tree_merge_duplicates(struct term *term) return 0; // construct priority list while deleting set - struct list *prioritized = list_end; + struct pqueue *prioritized = pqueue_init(2 << 15, cmp_pri, get_pri); while (set) { struct set_element *element = *(struct set_element **)set; - prioritized = list_add_prioritized(prioritized, element->list); + pqueue_insert(prioritized, element->list); tdelete(element, &set, hash_compare); free(element); } @@ -287,30 +255,33 @@ struct list *tree_merge_duplicates(struct term *term) struct list *final = list_end; struct list *invalidated = list_end; - struct list *iterator = prioritized; - // add longest (=> blueprint/structure of expression) - final = list_add(final, ((struct list *)iterator->data)->data); - iterator = iterator->next; + struct list *longest = pqueue_pop(prioritized); + final = list_add(final, longest->data); - while (iterator) { - struct list *list = iterator->data; - struct tree *head = list->data; + struct list *iterator; + while ((iterator = pqueue_pop(prioritized))) { + struct tree *head = iterator->data; - if (head->state != VALIDATED_TREE) { // skip invalidated - iterator = iterator->next; + if (head->state != VALIDATED_TREE && + head->duplication_count >= + iterator->val) { // skip invalidated continue; } - if (list->val > 1) { // needs merging + 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); + invalidate_tree(list->data, list->val); + + // keep a ref for later replacement ((struct tree *)list->data)->state = final->val - 1; @@ -318,8 +289,6 @@ struct list *tree_merge_duplicates(struct term *term) list = list->next; } } - - iterator = iterator->next; } // destroy invalidated list and replace reffed subtrees @@ -332,7 +301,7 @@ struct list *tree_merge_duplicates(struct term *term) } // destroy prioritized list - free_prioritized_list(prioritized); + pqueue_free(prioritized); return final; } |