From e8e1c91b40c9c82a0fd8373746a7b8cfb130f467 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Fri, 28 Jan 2022 11:16:16 +0800 Subject: BSR A prototype of BSR is roughly finished. --- src/bsr.c | 602 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 601 insertions(+), 1 deletion(-) (limited to 'src/bsr.c') diff --git a/src/bsr.c b/src/bsr.c index 908309f..e737d7a 100644 --- a/src/bsr.c +++ b/src/bsr.c @@ -1,3 +1,603 @@ +#include "list.h" +#include "util.h" +#include "ht.h" #include "bsr.h" +#include +#include +#include -int place(int x) { return x; } +typedef struct first_type_bsr_s first_type_bsr; +typedef struct second_type_bsr_s second_type_bsr; + +typedef struct first_type_array_element_s first_type_array_element; + +/* The keys of the table are (i, k) and values are hash tables whose + keys are (a, j) such that (X, a, i, j, k) belongs to the set. */ +struct first_type_array_element_s { + ht *table; + BOOL initialized; +}; + +struct first_type_bsr_s { + NUM len; + first_type_array_element *array; +}; + +/* Arrrrgh! */ +typedef struct second_arrarrarr_element_s second_arrarrarr_element; + +/* The keys are (i, k) and the values are hash tables whose keys are + those j such that + + (X, a, c, i, j, k) + + belongs to the set. */ +struct second_arrarrarr_element_s { + ht *table; + BOOL initialized; +}; + +typedef struct second_array_array_element_s \ +second_array_array_element; + +struct second_array_array_element_s { + NUM len; + second_arrarrarr_element *array; + BOOL initialized; +}; + +typedef struct second_type_array_element_s second_type_array_element; + +struct second_type_array_element_s { + NUM len; + second_array_array_element *array; + BOOL initialized; +}; + +struct second_type_bsr_s { + NUM len; + second_type_array_element *array; +}; + +struct bsr_s { + /* bsr_type type; */ + /* union { */ + first_type_bsr f; + second_type_bsr s; + /* } data; */ +}; + +bsr * +new_bsr(BOOL * const restrict errorp, Grammar *g) +{ + NUM left_len = grammar_left_len(g); + + bsr *bsrp = NULL; + SAFE_MALLOC(bsr, bsrp, 1, *errorp = 1; return NULL;); + + /* first type */ + bsrp->f.len = left_len; + SAFE_MALLOC(first_type_array_element, + bsrp->f.array, bsrp->f.len, goto cleanup;); + + /* ensure every bit is zero, including the initialized field */ + memset(bsrp->f.array, 0, + sizeof(first_type_array_element) * bsrp->f.len); + + /* second type */ + bsrp->s.len = left_len; + SAFE_MALLOC(second_type_array_element, + bsrp->s.array, bsrp->s.len, goto cleanup;); + memset(bsrp->s.array, 0, + sizeof(second_type_array_element) * bsrp->s.len); + + for (NUM i = 0; i < left_len; i++) + (bsrp->s.array+i)->len = rg_len(grammar_rule(g, i)); + + return bsrp; + + cleanup: + *errorp = 1; + + if (bsrp->f.array) free(bsrp->f.array); + if (bsrp->s.array) free(bsrp->s.array); + if (bsrp) free(bsrp); + + return NULL; +} + +void +destroy_bsr(bsr * const restrict bsrp) +{ + /* destroy first type */ + for (NUM i = 0; i < bsrp->f.len; i++) { +#define ELEMENT (bsrp->f.array+i) + if (ELEMENT->initialized) { + /* destroy every hash table values as well */ + +#define HTS ((ht **) ht_values(ELEMENT->table)) + + for (NUM j = 0; j < ht_size(ELEMENT->table); j++) + destroy_ht(*(HTS+j), DESTROY_KEY_SELF); + + destroy_ht(ELEMENT->table, DESTROY_KEY_SELF); + } + } + +#undef ELEMENT +#undef HTS + + free(bsrp->f.array); + + /* destroy second type */ + + for (NUM i = 0; i < bsrp->s.len; i++) { + +#define ELEMENT (bsrp->s.array+i) + + if (ELEMENT->initialized) { + for (NUM j = 0; j < ELEMENT->len; j++) { + +#define SELE (ELEMENT->array+j) + + if (SELE->initialized) { + for (NUM k = 0; k < SELE->len; k++) { + +#define HELE (SELE->array+k) + + if (HELE->initialized) { + +#define HTS ((ht **) ht_values(HELE->table)) + + for (NUM ell = 0; ell < ht_size(HELE->table); ell++) + destroy_ht(*(HTS+ell), DESTROY_KEY_SELF); + + destroy_ht(HELE->table, DESTROY_KEY_SELF); + } + } + + free(SELE->array); + } + } + + free(ELEMENT->array); + } + } + +#undef ELEMENT +#undef SELE +#undef HELE +#undef HTS + + free(bsrp->s.array); + + free(bsrp); +} + +/* X = non-terminal index, a = index of alternate, c = length of + prefix */ + +/* i = left-extent of X, and j = right-extent. k = the left-extent of + the right-most terminal or non-terminal in the alternate + corresponding to a. */ + +BOOL +bsr_add(CCR_MOD(Grammar *) g, bsr * const restrict b, + NUM X, NUM a, NUM c, NUM i, NUM k, NUM j) +{ + if (X < 0 || X >= b->f.len) { + fleprintf("Invalid X: %ld\n", X); + return 1; + } + + if (c > list_length(rg_nth(grammar_rule(g, X), a)) || c < 0) { + fleprintf("Invalid c: %ld\n", c); + return 1; + } + + BOOL errorp = 0; + + ht *value_table = NULL; + + pair2 *p2 = NULL, p21 = { 0 }, p22 = { 0 }; + + NUM *p1 = NULL, p11 = 0; + + if (c == list_length(rg_nth(grammar_rule(g, X), a))) { + /* first type BSR */ + /* fleprintf0("First type\n"); */ + +#define ARR (b->f.array+X) + + if (!(ARR->initialized)) { + ARR->initialized = 1; + ARR->table = new_ht2(HT_INIT_CAP); + + if (ARR->table == NULL) { + fleprintf0("Fail to get new ht\n"); + goto cleanup; + } + + value_table = new_ht2(HT_INIT_CAP); + + if (value_table == NULL) { + fleprintf0("Fail to get new ht\n"); + goto cleanup; + } + + NEW_P2(p2, a, k, goto cleanup;); + if (ht_insert(value_table, p2, (void*)1)) goto cleanup; + + NEW_P2(p2, i, j, goto cleanup;); + + if (ht_insert(ARR->table, p2, value_table)) goto cleanup; + /* don't destroy the pointers once they have been inserted */ + value_table = NULL; + p2 = NULL; + } else { + p21.x = i; + p21.y = j; + + if (ht_find(ARR->table, &p21) == NULL) { + value_table = new_ht2(HT_INIT_CAP); + + if (value_table == NULL) { + fleprintf0("Fail to get new ht\n"); + goto cleanup; + } + + NEW_P2(p2, a, k, goto cleanup;); + if (ht_insert(value_table, p2, (void*)1)) goto cleanup; + + NEW_P2(p2, i, j, goto cleanup;); + if (ht_insert(ARR->table, p2, value_table)) goto cleanup; + + /* don't destroy the pointers once they have been inserted */ + value_table = NULL; + p2 = NULL; + } else { + p22.x = a; + p22.y = k; + + if (ht_find(ht_find(ARR->table, &p21), &p22) == NULL) { + NEW_P2(p2, a, k, goto cleanup;); + if (ht_insert(ht_find(ARR->table, &p21), p2, (void*)1)) + goto cleanup; + + /* don't destroy the pointer once it has been inserted */ + p2 = NULL; + } else { + /* this element is already present */ + } + } + } + +#undef ARR + + } else { + /* second type BSR */ + /* fleprintf0("Second type\n"); */ + +#define AR (b->s.array+X) + + if (!(AR->initialized)) { + SAFE_MALLOC(second_array_array_element, + AR->array, AR->len, + goto cleanup;); + memset(AR->array, 0, + sizeof(second_array_array_element)*(AR->len)); + AR->initialized = 1; + } + +#define ARR (AR->array+a) + + if (a < 0 || a >= rg_len(grammar_rule(g, X))) { + fleprintf("Invalid a: %ld\n", a); + goto cleanup; + } + + ARR->len = list_length(rg_nth(grammar_rule(g, X), a)); + + if (!(ARR->initialized)) { + SAFE_MALLOC(second_arrarrarr_element, + ARR->array, ARR->len, + goto cleanup;); + memset(ARR->array, 0, + sizeof(second_arrarrarr_element)*(ARR->len)); + ARR->initialized = 1; + } + +#define ARRR (ARR->array+c) + + if (!(ARRR->initialized)) { + ARRR->table = new_ht2(HT_INIT_CAP); + + if (ARRR->table == NULL) { + fleprintf0("Fail to get new ht\n"); + goto cleanup; + } + + ARRR->initialized = 1; + } + + p21.x = i; + p21.y = j; + + if (ht_find(ARRR->table, &p21) == NULL) { + value_table = new_ht(HT_INIT_CAP, 0); + + if (value_table == NULL) { + fleprintf0("Fail to get new ht\n"); + goto cleanup; + } + + NEW_P2(p2, i, j, goto cleanup;); + + if (ht_insert(ARRR->table, p2, value_table)) { + fleprintf0("Fail to insert into table\n"); + goto cleanup; + } + value_table = NULL; + p2 = NULL; + } + + p11 = k; + + if (ht_find(ht_find(ARRR->table, &p21), + &p11) == NULL) { + SAFE_MALLOC(NUM, p1, 1, goto cleanup;); + *p1 = k; + if (ht_insert(ht_find(ARRR->table, &p21), + p1, (void *)1)) { + fleprintf0("Fail to insert into table\n"); + goto cleanup; + } + p1 = NULL; + } + +#undef AR +#undef ARR +#undef ARRR + } + + goto success; + + cleanup: + errorp = 1; + + success: + + if (value_table) destroy_ht(value_table, DESTROY_KEY_SELF); + if (p2) free(p2); + if (p1) free(p1); + + return errorp; +} + +BOOL +bsr_find(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, + BOOL * const restrict errorp, + NUM X, NUM a, NUM c, NUM i, NUM k, NUM j) +{ + *errorp = 0; + BOOL result = 0; + + if (X < 0 || X >= b->f.len) { + fleprintf("Invalid X: %ld\n", X); + goto cleanup; + } + + if (a < 0 || a >= rg_len(grammar_rule(g, X))) { + fleprintf("Invalid a: %ld\n", a); + goto cleanup; + } + + if (c < 0 || c > list_length(rg_nth(grammar_rule(g, X), a))) { + fleprintf("Invalid c: %ld\n", c); + goto cleanup; + } + + pair2 p21 = { 0 }, p22 = { 0 }; + NUM p11 = 0; + + if (c == list_length(rg_nth(grammar_rule(g, X), a))) { + /* first type */ +#define ARR (b->f.array+X) + + if (!(ARR->initialized)) { + goto success; + } else { + p21.x = i; + p21.y = j; + + if (ht_find(ARR->table, &p21) == NULL) { + goto success; + } else { + p22.x = a; + p22.y = k; + + if (ht_find(ht_find(ARR->table, &p21), &p22) == NULL) { + goto success; + } else { + result = 1; + goto success; + } + } + } + +#undef ARR + + } else { + /* second type */ + +#define AR (b->s.array+X) + + if (!(AR->initialized)) { + goto success; + } + +#define ARR (AR->array+a) + + ARR->len = list_length(rg_nth(grammar_rule(g, X), a)); + + if (!(ARR->initialized)) goto success; + +#define ARRR (ARR->array+c) + + if (!(ARRR->initialized)) goto success; + + p21.x = i; + p21.y = j; + + if (ht_find(ARRR->table, &p21) == NULL) goto success; + + p11 = k; + + if (ht_find(ht_find(ARRR->table, &p21), &p11) == NULL) + goto success; + + result = 1; + + goto success; + + #undef AR + #undef ARR + #undef ARRR + } + + cleanup: + *errorp = 1; + + success: + return result; +} + +void +bsr_print(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, NUM line_len) +{ + printf("Printing a BSR set...\n"); + + NUM count = 0; + + /* print first type BSR */ + for (NUM i = 0; i < b->f.len; i++) { + +#define ELEMENT (b->f.array+i) + + if (ELEMENT->initialized) { + +#define KEYS ((pair2 **) ht_keys(ELEMENT->table)) +#define VALUES ((ht **) ht_values(ELEMENT->table)) +#define SIZE (ht_size(ELEMENT->table)) + + for (NUM j = 0; j < SIZE; j++) { + +#define VALUE_TABLE (*(VALUES+j)) +#define VALUE_TABLE_KEYS ((pair2 **) ht_keys(VALUE_TABLE)) + + for (NUM k = 0; k < ht_size(VALUE_TABLE); k++) { + count++; + printf("("); + print_name(list_nth(grammar_names(g), i)); + printf(" := "); + map_list + (rg_nth + (grammar_rule(g, i), + (*(VALUE_TABLE_KEYS+k))->x), + print_tnt); + printf(", %ld, %ld, %ld)", + (*(KEYS+j))->x, + (*(VALUE_TABLE_KEYS+k))->y, + (*(KEYS+j))->y); + + if (count == line_len) { + count = 0; + printf("\n"); + } else { + printf(", "); + } + } + } + } + } + +#undef ELEMENT +#undef KEYS +#undef VALUES +#undef SIZE +#undef VALUE_TABLE +#undef VALUE_TABLE_KEYS + + for (NUM i = 0; i < b->s.len; i++) { + +#define ELEMENT (b->s.array+i) + + if (!(ELEMENT->initialized)) continue; + + for (NUM j = 0; j < ELEMENT->len; j++) { + +#define SELE (ELEMENT->array+j) + + if (!(SELE->initialized)) continue; + + for (NUM k = 0; k < SELE->len; k++) { + +#define HELE (SELE->array+k) + + if (!(HELE->initialized)) continue; + +#define KEYS ((pair2 **) ht_keys(HELE->table)) +#define VALUES ((ht **) ht_values(HELE->table)) + + for (NUM n = 0; n < ht_size(HELE->table); n++) { + for (NUM ell = 0; ell < ht_size(*(VALUES+n)); ell++) { + +#define VALUE_KEYS ((NUM **) ht_keys(*(VALUES+n))) + + count++; + printf("("); + print_name(list_nth(grammar_names(g), i)); + printf(" := "); + +#define LS rg_nth(grammar_rule(g, i), j) + + for (NUM m = 0; m < k; m++) { + print_tnt(*(list_array(LS)+m)); + if (m+1x, + **(VALUE_KEYS+ell), + (*(KEYS+n))->y); + + if (count == line_len) { + count = 0; + printf("\n"); + } else { + printf(", "); + } + } + } + } + } + } + + printf("\n"); + +#undef ELEMENT +#undef SELE +#undef HELE +#undef KEYS +#undef VALUES +#undef VALUE_KEYS +#undef LS + +} -- cgit v1.2.3-18-g5258