diff options
| -rw-r--r-- | src/Makefile.am | 14 | ||||
| -rw-r--r-- | src/bnf.bnf | 22 | ||||
| -rw-r--r-- | src/bsr.c | 602 | ||||
| -rw-r--r-- | src/bsr.h | 92 | ||||
| -rw-r--r-- | src/grammar.c | 7 | ||||
| -rw-r--r-- | src/grammar.h | 2 | ||||
| -rw-r--r-- | src/ht.c | 191 | ||||
| -rw-r--r-- | src/ht.h | 59 | ||||
| -rw-r--r-- | src/list.h | 1 | ||||
| -rw-r--r-- | src/test/check_bsr.c | 151 | ||||
| -rw-r--r-- | src/test/check_grammar.c | 1 | ||||
| -rw-r--r-- | src/test/check_ht.c | 187 | ||||
| -rw-r--r-- | src/util.h | 3 |
13 files changed, 1255 insertions, 77 deletions
diff --git a/src/Makefile.am b/src/Makefile.am index fe8be18..e4eae9e 100644 --- a/src/Makefile.am +++ b/src/Makefile.am @@ -2,9 +2,9 @@ AM_CFLAGS = -Wall -Wextra noinst_LIBRARIES = libeps.a libeps_a_SOURCES = grammar.c list.c util.c reader.c str.c \ -utf8.c dfa.c ht.c slr_table.c grammar.h \ -list.h util.h reader.h str_partial.h \ -str.h utf8.h dfa.h ht.h slr_table.h +utf8.c dfa.c ht.c bsr.c cnp.c \ +grammar.h list.h util.h reader.h str_partial.h \ +str.h utf8.h dfa.h ht.h bsr.h cnp.h libeps_a_CFLAGS = $(AM_CFLAGS) --pedantic @@ -22,7 +22,7 @@ CLEANFILES = TAGS # tests check_PROGRAMS = check_list check_grammar check_reader check_dfa \ -check_ht +check_ht check_bsr check_cnp check_list_SOURCES = test/check_list.c list.c @@ -36,6 +36,12 @@ check_dfa_SOURCES = test/check_dfa.c dfa.c list.c str.c utf8.c check_ht_SOURCES = test/check_ht.c ht.c +check_bsr_SOURCES = test/check_bsr.c bsr.c grammar.c list.c util.c \ +ht.c utf8.c str.c + +check_cnp_SOURCES = test/check_cnp.c cnp.c grammar.c list.c util.c \ +ht.c utf8.c str.c + TESTS = $(check_PROGRAMS) AM_COLOR_TESTS = always diff --git a/src/bnf.bnf b/src/bnf.bnf index 26e9861..df8ef3c 100644 --- a/src/bnf.bnf +++ b/src/bnf.bnf @@ -13,7 +13,7 @@ BNF: rules_section BNF: spaces: space spaces -spaces: +spaces: space space: " " space: "\t" @@ -27,7 +27,7 @@ empty: notnewlines: [notnewline] notnewlines notnewlines: -predicate_section: predicate empty "\n" empty predicate_section +predicate_section: predicate empty "\n" predicate_section predicate_section: predicate: "[" ids "]:" spaces class @@ -44,19 +44,23 @@ class: "^" positive_class positive_class: positive_specification positive_class positive_class: -positive_specification: notnewline -positive_specification: notnewline "-" notnewline +positive_specification: enotnewline +positive_specification: enotnewline "-" enotnewline -notnewline: [notnewline] -notnewline: "\\" [any] -notnewline: +# Extended not-newline, or escaped not-newline +enotnewline: [notnewline] +enotnewline: "\\" [any] -rules_section: rule empty "\n" empty rules_section +rules_section: rule empty "\n" rules_section rule: rule_name ":" spaces rule_rhs +rule: rule_name ":" rule_rhs rule_name: [notbracket] rule_name rule_name: -rule_rhs: ids spaces rule_rhs +spaces-or-escaped-newline: spaces +spaces-or-escaped-newline: "\\\n" + +rule_rhs: ids spaces-or-escaped-newline rule_rhs rule_rhs: @@ -1,3 +1,603 @@ +#include "list.h" +#include "util.h" +#include "ht.h" #include "bsr.h" +#include <stdio.h> +#include <string.h> +#include <stdarg.h> -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+1<k) printf(" "); + } + + printf(" · "); + + for (NUM m = k; m < list_length(LS); m++) { + print_tnt(*(list_array(LS)+m)); + if (m+1<list_length(LS)) printf(" "); + } + + printf(", %ld, %ld, %ld)", + (*(KEYS+n))->x, + **(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 + +} @@ -1,14 +1,16 @@ #ifndef BSR_H #define BSR_H +#include "util.h" +#include "grammar.h" /* This file implements the "Binary Subtree Representation" of a derivation forest. See the following paper for the miraculous details: Derivation representation using binary subtree sets - + by - + Elizabeth Scott, Adrian Johnstone and L.Thomas van Binsbergen. */ /* Note that there is an implementation of this GLL algorithm in the @@ -50,58 +52,54 @@ length of beta. The simplest way to implement this is to have two "sets", one for - each type. Each set is an array of arrays, where the root array's - indices correspond to non-terminals, and the leaf arrays correspond - to rules of that non-terminal. Then the rest is implemented - through hash-tables, whose keys are tuples of integers. For the - first type, the keys are the (i, k) pairs and the values are those - j. For the second, the keys are the (b, i, k) tupels and the - values are those j. The reason to use i and k as keys is that they - represent the left and the right extent of the BSR respectively, so - we index them in order to find them easily. In addition, this will - be useful if we want to extract SPPF out of a BSR set. + each type. But the two types need to be implemented in different + ways. For both types, we need to know if a BSR belongs to the set + in (almost) constnat time, so we exclude the possibility of linked + lists first. + + For the first type, we also need the ability to loop through all + BSRs of the form (X, ...) for a given non-terminal X. Further, we + need to index the left and the right extents in almost constant + time as well. So we represent the first type as an array of hash + tables, whose indices correspond to nonterminals. Each hash table + has as keys (i, k) and as values hash tables whose keys are those + (a, j) such that (X, a, i, j, k) belong to the set. + + For the second type, we require the capability to loop through all + BSRs of the form (X, a, b, ...) in a set for some given X, a, and + b. So we represent the second type as an array of arrays of arrays + of hash tables, whose array indices correspond to X, a, and b, + respectively. The hash tables have keys (i, k) and values those j + such that (X, a, b, i, j, k) belongs to the set. I don't know if there are better implementations. If I think of better ways in the future, I will re-implement the BSR sets. */ -/* Note that we also need to implement "process descriptors" for the - GLL parser. Since a process descriptor is of the form +typedef struct bsr_s bsr; - (X := beta . gamma, i, j, k), +bsr *new_bsr(BOOL * const restrict errorp, Grammar *g); - where X := beta gamma is a rule and i is the length of beta, we can - represent a process descriptor as +/* No flag to control the deletion, as the user cannot change how the + data is stored. */ +void destroy_bsr(bsr * const restrict bsrp); - (X, a, i, j, k), +/* the function in the paper */ + +/* 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); + +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); - i.e. as a first-type BSR set. But the meaning of the "i" is - different. - - However, we shall notice that there is a natural "grading" on the - process descriptors. The k-th grading consists of the descriptors - with the last element in the tuple equal to k. In the clustered - nonterminal parsing algorithm, the process descriptors that are - added as a consequence of dealing with a process descriptor of - grading k must be of grade greater than or equal to k. This means - that if all process descriptors of grade k have been processed and - the descriptors awaiting to be processed all have grades > k, then - we won't see any process descriptors of grade <= k again. So we - can actually keep a list of process descriptors that serve the role - of the set U_k in the afore-mentionned paper. This list - corresponds to the grading of the descriptors. This way we don't - need to store the k in the descriptor. Therefore a process - descriptor is represented as - - (X, a, i, j). - - Again we store an array of arrays corresponding to X and a. Thus - the hash table simply has keys i and values j. - - The main benefit of this is that after we find that all process - descriptors in R_k have been processed, we can free those - descriptors in U_k. I think this is a good way to lower the space - requirements of this algorithm. */ - -int place(int x); +/* Change to new line after LINE_LEN many elements. */ +void bsr_print(CCR_MOD(bsr *) b, CCR_MOD(Grammar *) g, NUM line_len); #endif diff --git a/src/grammar.c b/src/grammar.c index bbc6934..c12ddec 100644 --- a/src/grammar.c +++ b/src/grammar.c @@ -495,6 +495,13 @@ grammar_left_len(CCR_MOD(Grammar *)g) return list_length(g->names); } +P_ATTR +List * +grammar_names(CCR_MOD(Grammar *)g) +{ + return g->names; +} + /* A transitive closure algorithm */ void epsilon_nts(CC_MOD(Grammar *) g, BOOL * const restrict nts) diff --git a/src/grammar.h b/src/grammar.h index 956fdcd..8d6cb06 100644 --- a/src/grammar.h +++ b/src/grammar.h @@ -167,6 +167,8 @@ void destroy_grammar(void *grammar, int flag); NUM grammar_left_len(CCR_MOD(Grammar *)g); +List *grammar_names(CCR_MOD(Grammar *)g); + /* look up a rule */ Rule_group *grammar_rule(CCR_MOD(Grammar *) g, NT nt); @@ -99,6 +99,8 @@ new_ht(UNUM size, int nargs, ...) void destroy_ht(ht * restrict htp, HT_DESTROY_FLAG flag) { + if (htp == NULL) return; + switch (flag) { case DESTROY_KEY_SELF: case DESTROY_KEY_NO_SELF: @@ -214,6 +216,7 @@ ht_expand(ht *htp) #define PERTURBATION_SHIFT 5 /* On error return non-zero. */ +__attribute__((__hot__)) static BOOL ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result) { @@ -243,9 +246,6 @@ ht_probe(CC_MOD(ht *) htp, CC_MOD(void *) key, NUM *result) *result = ikey; - /* if (*((NUM*) key) == 3) { - * fleprintf("ikey = %ld, result = %ld\n", ikey, *result); - * } */ return 0; } @@ -357,3 +357,188 @@ ht_keys(CCR_MOD(ht *) htp) { return htp->keys; } + +/* Calculate binomial coefficients efficiently. + + The algorithm is adapted from the following website. + + <https://blog.plover.com/math/choose.html> */ + +UHC_ATTR +static NUM +binom(NUM n, int k) { + if (k < 1) { + fleprintf("Invalid k: %d\n", k); + return 0; + } + + NUM result = 1; + + for (int d = 1; d <= k;) { + result *= n--; + result /= d++; + } + + return result; +} + +/* REVIEW: I might want a faster hashing function in the future. + Consider using bit manipulations as shown in the following file. + + <http://burtleburtle.net/bob/c/lookup3.c> */ + +/* A generalization of Cantor's pairing functions. See Wikipedia for + more information. + + <https://en.wikipedia.org/wiki/Fueter–Pólya_theorem> + + The integer n determins the number of arguments, which are all of + type NUM. */ + +/* I later changed my mind and decided to use another pairing + function, the elegant pairing function of Szudzik. See the + following page for details. + + <http://szudzik.com/ElegantPairing.pdf> */ +UHC_ATTR +static NUM +pair(int n, ...) { + if (n < 1) { + fleprintf("Invalid n: %d\n", n); + return 0; + } + + va_list args; + + va_start(args, n); + + NUM result = va_arg(args, NUM), temp = 0; + + /* a simple fold */ + for (int i = 1; i < n; i++) { + temp = va_arg(args, NUM); + result = (result >= temp) ? + result * result + result + temp : + result + temp * temp; + } + + va_end(args); + + return result; +} + +HP_ATTR +static NUM +pair2_hf(CCR_MOD(void *) key) { + if (key == NULL) { + fleprintf0("Got NULL key!\n"); + return 0; + } + + NUM result = pair(2, ((pair2 *) key)->x, ((pair2 *) key)->y); + + /* fleprintf("Hash of (%ld, %ld) is %ld\n", + * ((pair2 *) key)->x, + * ((pair2 *) key)->y, + * result); */ + + return result; +} + +HP_ATTR +static BOOL +pair2_cf(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) { + if ((keya == NULL && keyb != NULL) || + (keyb == NULL && keya != NULL)) + return 0; + + if (keya == NULL && keyb == NULL) return 1; + + return ((pair2 *) keya)->x == ((pair2 *) keyb)->x && + ((pair2 *) keya)->y == ((pair2 *) keyb)->y; +} + +HP_ATTR +static NUM +pair3_hf(CCR_MOD(void *) key) { + if (key == NULL) { + fleprintf0("Got NULL key!\n"); + return 0; + } + + NUM result = + pair(3, + ((pair3 *) key)->x, + ((pair3 *) key)->y, + ((pair3 *) key)->z); + + /* fleprintf("Hash of (%ld, %ld, %ld) is %ld\n", + * ((pair3 *) key)->x, + * ((pair3 *) key)->y, + * ((pair3 *) key)->z, + * result); */ + + return result; +} + +HP_ATTR +static BOOL +pair3_cf(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) { + if ((keya == NULL && keyb != NULL) || + (keyb == NULL && keya != NULL)) + return 0; + + if (keya == NULL && keyb == NULL) return 1; + + return ((pair3 *) keya)->x == ((pair3 *) keyb)->x && + ((pair3 *) keya)->y == ((pair3 *) keyb)->y && + ((pair3 *) keya)->z == ((pair3 *) keyb)->z; +} + +HP_ATTR +static NUM +pair4_hf(CCR_MOD(void *) key) { + if (key == NULL) { + fleprintf0("Got NULL key!\n"); + return 0; + } + + NUM result = + pair(4, + ((pair4 *) key)->x, + ((pair4 *) key)->y, + ((pair4 *) key)->z, + ((pair4 *) key)->w); + + /* fleprintf("Hash of (%ld, %ld, %ld) is %ld\n", + * ((pair3 *) key)->x, + * ((pair3 *) key)->y, + * ((pair3 *) key)->z, + * result); */ + + return result; +} + +HP_ATTR +static BOOL +pair4_cf(CCR_MOD(void *) keya, CCR_MOD(void *) keyb) { + if ((keya == NULL && keyb != NULL) || + (keyb == NULL && keya != NULL)) + return 0; + + if (keya == NULL && keyb == NULL) return 1; + + return ((pair4 *) keya)->x == ((pair4 *) keyb)->x && + ((pair4 *) keya)->y == ((pair4 *) keyb)->y && + ((pair4 *) keya)->z == ((pair4 *) keyb)->z && + ((pair4 *) keya)->w == ((pair4 *) keyb)->w; +} + +ht * +new_ht2(UNUM size) { return new_ht(size, 2, pair2_hf, pair2_cf); } + +ht * +new_ht3(UNUM size) { return new_ht(size, 2, pair3_hf, pair3_cf); } + +ht * +new_ht4(UNUM size) { return new_ht(size, 2, pair4_hf, pair4_cf); } @@ -2,17 +2,16 @@ #define HT_H #include "util.h" -enum { HT_INIT_CAP = 256 }; +enum { HT_INIT_CAP = 1 << 8 }; -/* TODO: Modify the probing algorithm. Imitate the algorithm used by - python's hash tables. The source code of the python dict object - can be found in the following URL: +/* The algorithm here imitates the algorithm used by python's hash + tables. The source code of the python dict object can be found in + the following URL: <https://hg.python.org/cpython/file/52f68c95e025/Objects/dictobject.c#l33> */ -/* TODO: Generalize the type of the keys, so that we can use anything - as the key. The type of the keys should satisfy the following - conditions. +/* We can use anything as the key, except that the type of the keys + should satisfy the following conditions. - Hash-able: We must know how to produce the hash value of a key. @@ -27,6 +26,7 @@ typedef NUM (*hash_func_t) (CCR_MOD(void *)key); typedef BOOL (*compare_func_t) (CCR_MOD(void *)keya, CCR_MOD(void *)keyb); +/* FIXME: Hide this struct from the header file. */ struct ht_s { void **keys; void **values; @@ -60,7 +60,7 @@ ht *new_ht(UNUM size, int nargs, ...); and every of the other word's pointers. To free both keys and values pointers in the same manner, i.e. free both of the first pointers or free each and every pointers, use the option containing - "EVERY" or "EVERY_FIRST" respectively. */ + "EVERY_FIRST" or "EVERY" respectively. */ enum HT_DESTROY_FLAG_e { DESTROY_NONE_NO_SELF, DESTROY_NONE_SELF, @@ -108,4 +108,47 @@ BOOL ht_delete(ht * const restrict htp, void *key, P_ATTR void *ht_find(CCR_MOD(ht *) htp, void *key); +/* Pairing hash tables */ + +struct pair2_s { NUM x; NUM y; }; + +typedef struct pair2_s pair2; + +/* On error return NULL */ +ht *new_ht2(UNUM size); + +struct pair3_s { NUM x; NUM y; NUM z; }; + +typedef struct pair3_s pair3; + +/* On error return NULL */ +ht *new_ht3(UNUM size); + +struct pair4_s { NUM x; NUM y; NUM z; NUM w; }; + +typedef struct pair4_s pair4; + +ht *new_ht4(UNUM size); + +#define NEW_P2(P, X, Y, CLEAN) do { \ + SAFE_MALLOC(pair2, P, 1, CLEAN); \ + P->x = X; \ + P->y = Y; \ + } while (0) + +#define NEW_P3(P, X, Y, Z, CLEAN) do { \ + SAFE_MALLOC(pair3, P, 1, CLEAN); \ + P->x = X; \ + P->y = Y; \ + P->z = Z; \ + } while (0) + +#define NEW_P4(P, X, Y, Z, W, CLEAN) do { \ + SAFE_MALLOC(pair4, P, 1, CLEAN); \ + P->x = X; \ + P->y = Y; \ + P->z = Z; \ + P->w = W; \ + } while (0) + #endif @@ -78,7 +78,6 @@ void **list_array(List *ls); destroyed. */ List *array_to_list(void ** array, NUM size); - /* destroy the list: If ALL_FREE_P is 1, this frees every void pointers contained in the list; if it is 2, this frees the first pointer. In any case, the list is de-allocated. */ diff --git a/src/test/check_bsr.c b/src/test/check_bsr.c new file mode 100644 index 0000000..4a6ba4e --- /dev/null +++ b/src/test/check_bsr.c @@ -0,0 +1,151 @@ +#include <string.h> +#include <stdlib.h> +#include <stdio.h> +#include "util.h" +#include "str.h" +#include "utf8.h" +#include "grammar.h" +#include "list.h" +#include "../bsr.h" + +#define READ_INTO_CPA(N, U, I, VA, VI, CP) do { \ + U = new_utf8(N, 1); \ + I = get_info((str *)U, 0); \ + VA = MYALLOC(NUM, 1); \ + VI = 0; \ + for (NUM index = 0; \ + I.value >= 0 && index < str_length((str *) U); \ + index += I.step, VI++) { \ + I = get_info((str *)U, index); \ + *(VA+VI) = I.value; \ + } \ + CP = MYALLOC(cpa, 1); \ + CP->array = VA; \ + CP->size = VI; \ + add_to_list(names, CP); \ + destroy_str((str *)U, 1); \ + } while (0) + +#define READ_TNT_STRING(LEFT, FORMAT, LEN, ...) do { \ + tnt_string = new_tnt_string(FORMAT, LEN, __VA_ARGS__); \ + if (!tnt_string) { \ + fleprintf("left = %d, f = %s, l = %d, " \ + "cannot create tnt string\n", \ + LEFT, FORMAT, LEN); \ + map_list(rules, destroy_rule_and_free_all); \ + destroy_list(rules, 0); \ + map_list(names, destroy_cpa_and_free_all); \ + destroy_list(names, 0); \ + return 1; \ + } \ + rule = new_rule(LEFT, tnt_string); \ + add_to_list(rules, rule); \ + } while (0) + + +int +main(int UNUSED argc, char ** UNUSED argv) +{ + /* have a grammar for testing */ + List *tnt_string = NULL; + Rule *rule = NULL; + List *rules = new_list(); + List *names = new_list(); + + char *name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'E'; + + utf8* uname = NULL; + + str_info info = EMPTY_STR_INFO; + + NUM *varray = NULL; + NUM vindex = 0; + cpa *cpap = NULL; + + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); + + name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'T'; + + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); + + name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'F'; + + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); + + name = MYALLOC(char, 2); + *(name+1) = 0; + *name = 'D'; + + READ_INTO_CPA(name, uname, info, varray, vindex, cpap); + + READ_TNT_STRING(0, "n", 1, (NT) 1); + READ_TNT_STRING(0, "ntn", 3, (NT) 1, (T) 43, (NT) 1); + + READ_TNT_STRING(1, "n", 1, (NT) 2); + READ_TNT_STRING(1, "ntn", 3, (NT) 2, (T) 42, (NT) 2); + + READ_TNT_STRING(2, "n", 1, (NT) 3); + READ_TNT_STRING(2, "tnt", 3, (T) 40, (NT) 0, (T) 41); + + READ_TNT_STRING(3, "tn", 2, (T) 48, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 49, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 50, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 51, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 52, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 53, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 54, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 55, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 56, (NT) 3); + READ_TNT_STRING(3, "tn", 2, (T) 57, (NT) 3); + rule = new_rule(3, new_list()); + add_to_list(rules, rule); + + Grammar *g = new_grammar(); + + build_grammar(g, rules, names); + + print_grammar(g); + + + BOOL error = 0; + bsr *bsrp = new_bsr(&error, g); + + if (error) goto cleanup; + + bsr_add(g, bsrp, 0, 0, 1, 0, 1, 2); + bsr_add(g, bsrp, 0, 1, 1, 0, 1, 2); + bsr_add(g, bsrp, 0, 1, 2, 0, 1, 2); + + if (bsr_find(bsrp, g, &error, + 0, 0, 1, 0, 1, 2)) { + printf("Successfully found 0, 0, 1, 0, 1, 2\n"); + } else { + fleprintf0("Fail to find 0, 0, 1, 0, 1, 2\n"); + } + + if (bsr_find(bsrp, g, &error, + 0, 0, 1, 0, 1, 3)) { + fleprintf0("Accidentally found 0, 0, 1, 0, 1, 3\n"); + } else { + printf("Indeed cannot find 0, 0, 1, 0, 1, 3\n"); + } + + bsr_print(bsrp, g, 1); + + cleanup: + + destroy_grammar(g, 1); + + destroy_list(rules, 1); + + destroy_bsr(bsrp); + + return 0; + +} diff --git a/src/test/check_grammar.c b/src/test/check_grammar.c index 2b6c8f2..7e55681 100644 --- a/src/test/check_grammar.c +++ b/src/test/check_grammar.c @@ -147,7 +147,6 @@ main(UNUSED int argc, UNUSED char **argv) printf("\n\n"); - /* TODO: Check first and follow sets */ NUM left_len = grammar_left_len(g); BOOL *epsilon_array = NULL; ht *terminal_hts = NULL, *predicate_hts = NULL; diff --git a/src/test/check_ht.c b/src/test/check_ht.c index 0298087..b572549 100644 --- a/src/test/check_ht.c +++ b/src/test/check_ht.c @@ -23,9 +23,9 @@ int main(int UNUSED argc, char ** UNUSED argv) fleprintf("We found no value for key %ld\n", key); NUM size = ht_size(htp); - + fleprintf("The size of the hash table is %ld\n", size); - + for (NUM i = 0; i < size; i++) fleprintf("The %ld-th element has key %ld and value %ld\n", i, @@ -50,5 +50,188 @@ int main(int UNUSED argc, char ** UNUSED argv) } destroy_ht(htp, DESTROY_VALUE_SELF); + + /* Testing hash tables of pairs of integers. */ + + htp = new_ht2(10); + + pair2 *key2 = NULL; + + for (int i = 0; i < 10; i++) { + if (i>=2 && i % 2) { + NEW_P2(key2, i<<1, i, + destroy_ht(htp, DESTROY_KEY_SELF); + return 1;); + } else { + NEW_P2(key2, i, i<<1, + destroy_ht(htp, DESTROY_KEY_SELF); + return 1;); + } + if (ht_insert(htp, key2, (void*)1)) { + fleprintf0("Fail to insert\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } + } + + printf("Success!\n"); + + pair2 testk2 = { .x = 0, .y = 0 }; + + if (ht_find(htp, &testk2) == NULL) { + fleprintf0("Fail to find zero zero pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for zero zero pair\n", + ht_find(htp, &testk2)); + } + + testk2.x = 1; + testk2.y = 1; + + if (ht_find(htp, &testk2)) { + fleprintf0("Accidentally find one one pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for one one pair\n", + ht_find(htp, &testk2)); + } + + testk2.x = 1; + testk2.y = 2; + + if (ht_find(htp, &testk2) == NULL) { + fleprintf0("Fail to find one two pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for one two pair\n", + ht_find(htp, &testk2)); + } + + destroy_ht(htp, DESTROY_KEY_SELF); + + /* testing hash tables with pair3 keys */ + + htp = new_ht3(10); + + pair3 *key3 = NULL; + + for (int i = 0; i < 10; i++) { + NEW_P3(key3, i, i << 1, -i, + destroy_ht(htp, DESTROY_KEY_SELF); + return 1;); + + if (ht_insert(htp, key3, (void*)1)) { + fleprintf0("Fail to insert\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } + } + + printf("Success!\n"); + + pair3 testk3 = { .x = 0, .y = 0, .z = 0 }; + + if (ht_find(htp, &testk3) == NULL) { + fleprintf0("Fail to find zero pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for zero pair\n", + ht_find(htp, &testk3)); + } + + testk3.x = 1; + testk3.y = 2; + testk3.z = -1; + + if (ht_find(htp, &testk3) == NULL) { + fleprintf0("Fail to find one two minus one pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for one two minus one pair\n", + ht_find(htp, &testk3)); + } + + testk3.x = 1; + testk3.y = 2; + testk3.z = 1; + + if (ht_find(htp, &testk3)) { + fleprintf0("Accidentally find one two one pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for one two one pair\n", + ht_find(htp, &testk3)); + } + + destroy_ht(htp, DESTROY_KEY_SELF); + + /* testing hash tables with pair4 keys */ + + htp = new_ht4(10); + + pair4 *key4 = NULL; + + for (int i = 0; i < 10; i++) { + NEW_P4(key4, i, i << 1, -i, i+1, + destroy_ht(htp, DESTROY_KEY_SELF); + return 1;); + + if (ht_insert(htp, key4, (void*)1)) { + fleprintf0("Fail to insert\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } + } + + printf("Success!\n"); + + pair4 testk4 = { .x = 0, .y = 0, .z = 0, .w = 1 }; + + if (ht_find(htp, &testk4) == NULL) { + fleprintf0("Fail to find zero pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for zero pair\n", + ht_find(htp, &testk4)); + } + + testk4.x = 1; + testk4.y = 2; + testk4.z = -1; + testk4.w = 2; + + if (ht_find(htp, &testk4) == NULL) { + fleprintf0("Fail to find one two minus one pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for one two minus one two pair\n", + ht_find(htp, &testk4)); + } + + testk4.x = 1; + testk4.y = 2; + testk4.z = 1; + testk4.w = 2; + + if (ht_find(htp, &testk4)) { + fleprintf0("Accidentally find one two one two pair\n"); + destroy_ht(htp, DESTROY_KEY_SELF); + return 1; + } else { + printf("We find value %p for one two one two pair\n", + ht_find(htp, &testk4)); + } + + destroy_ht(htp, DESTROY_KEY_SELF); + return 0; } @@ -28,7 +28,8 @@ typedef unsigned char BOOL; #define UC_ATTR __attribute__((__unused__, __const__)) #define UH_ATTR __attribute__((__unused__, __hot__)) #define UHP_ATTR __attribute__((__unused__, __hot__, __pure__)) - +#define UHC_ATTR __attribute__((__unused__, __hot__, __const__)) +#define HP_ATTR __attribute__((__hot__, __pure__)) /* For convenient declarations */ #define CC_MOD(X) const X const #define CCR_MOD(X) const X const restrict |