From 510b10b96b546fcc6c6b6be85050305ddd192a41 Mon Sep 17 00:00:00 2001 From: JSDurand Date: Sat, 5 Feb 2022 17:30:11 +0800 Subject: replace some hash table usage by tuples Previously I used hash tables, which consume too much memory. Now the critical parts are replaced by a new hand-written library called "tuple.h". Now we can easily parse larger inputs. I haven't tested its limits, though. --- src/tuple.c | 629 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 629 insertions(+) create mode 100644 src/tuple.c (limited to 'src/tuple.c') diff --git a/src/tuple.c b/src/tuple.c new file mode 100644 index 0000000..92f2e6a --- /dev/null +++ b/src/tuple.c @@ -0,0 +1,629 @@ +#include +#include "tuple.h" + +#define TUP(N, M) struct PASTER(tuple, N, _s) { \ + struct PASTER(tuple, M, _s) *array; \ + BOOL initialized; \ + } + +/* "lengthed" tuple */ +#define LTUP(N) struct PASTER(luple, N, _s) { \ + struct PASTER(tuple, N, _s) tuple; \ + NUM *lengths; \ + } + +#define CONSTRUCT(N, M) UNUSED static \ + PASTER(tuple, N,) *PASTER \ + (new, _tuple, N)() { \ + PASTER(tuple, N,) *result = NULL; \ + SAFE_CALLOC(PASTER(tuple, N,), result, 1, return NULL;); \ + return result; \ + } \ + MY_Static_MES("To require a semicolon!") + +#define LONSTRUCT(N) PASTER(luple, N,) *PASTER \ + (new_luple, N,)(NUM *len) { \ + PASTER(luple, N,) *result = NULL; \ + SAFE_CALLOC(PASTER(luple, N,), result, 1, return NULL;); \ + result->lengths = len; \ + return result; \ + } \ + MY_Static_MES("To require a semicolon!") + +#define DESTRUCT(N, M) static void PASTER(destroy_tuple, N,) \ + (PASTER(tuple, N,) tup, NUM *len) { \ + if (!(tup.initialized)) return; \ + for (NUM PASTER(i, N,) = 0; \ + PASTER(i, N,) < *len; \ + PASTER(i, N,)++) { \ + PASTER(destroy_tuple, M,)(*(tup.array+PASTER(i, N,)), \ + len+1); \ + } \ + free(tup.array); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define LESTRUCT(N) void PASTER(destroy_luple, N,) \ + (PASTER(luple, N,) *lup) { \ + if (lup == NULL) return; \ + PASTER(destroy_tuple, N,)(lup->tuple, lup->lengths); \ + free(lup->lengths); \ + free(lup); \ + } \ + MY_Static_MES("To require a semicolon!") + +/* NOTE: The function call return should be the last thing in the + function body, so that GCC knows to perform tail-call optimization, + with optimization level at least 2 I guess. */ +#define ADDT(N, M) static BOOL PASTER(add_to_tuple, N,) \ + (PASTER(tuple, N,) *tup, NUM *len, \ + PASTER(pair, N,) label, NUM val) { \ + if (label.x < 0 || label.x >= *len) { \ + fleprintf("Invalid label = %ld, len = %ld\n", \ + label.x, *len); \ + goto cleanup; \ + } \ + if (!(tup->initialized)) { \ + SAFE_CALLOC \ + (PASTER(tuple, M,), tup->array, *len, goto cleanup;); \ + tup->initialized = 1; \ + } \ + PASTER(pair, M,) newlabel = (PASTER(pair, M,)) { 0 }; \ + PASTER(COPY_PAIR, M,)(newlabel, label); \ + goto success; \ + cleanup: \ + return 1; \ + success: \ + return PASTER(add_to_tuple, M,) \ + (tup->array+label.x, len+1, newlabel, val); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define ADDL(N) BOOL PASTER(add_to_luple, N,) \ + (PASTER(luple, N,) *lup, PASTER(pair, N,) label, \ + NUM val) { \ + return PASTER(add_to_tuple, N,) \ + ((PASTER(tuple, N,) *) lup, lup->lengths, label, val); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define INDEXT(N, M) HP_ATTR static NUM * \ + PASTER(tuple, N, _find) \ + (PASTER(tuple, N,) *tup, NUM *len, \ + PASTER(pair, N,) label) { \ + if (!(tup->initialized)) return NULL; \ + if (label.x < 0 || label.x >= *len) return NULL; \ + PASTER(pair, M,) newlabel = (PASTER(pair, M,)) { 0 }; \ + PASTER(COPY_PAIR, M,)(newlabel, label); \ + return PASTER(tuple, M, _find) \ + (tup->array+label.x, len+1, newlabel); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define INDEXL(N) HP_ATTR NUM *PASTER(luple, N, _find) \ + (PASTER(luple, N,) *lup, PASTER(pair, N,) label) { \ + return PASTER(tuple, N, _find) \ + ((PASTER(tuple, N,) *) lup, lup->lengths, label); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define INDEXPT(N, M, P, Q) HP_ATTR static BOOL \ + PASTER(PASTER(tuple, N, _pf), _, M) \ + (PASTER(tuple, N,) *tup, NUM *len, \ + PASTER(pair, M,) label) { \ + if (!(tup->initialized)) return 0; \ + if (label.x < 0 || label.x >= *len) return 0; \ + PASTER(pair, Q,) newlabel = (PASTER(pair, Q,)) { 0 }; \ + PASTER(COPY_PAIR, Q,)(newlabel, label); \ + return PASTER(PASTER(tuple, P, _pf), _, Q) \ + (tup->array+label.x, len+1, newlabel); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define INDEXPL(N, M) HP_ATTR BOOL \ + PASTER(PASTER(luple, N, _pf), _, M) \ + (PASTER(luple, N,) *lup, PASTER(pair, M,) label) { \ + return PASTER(PASTER(tuple, N, _pf), _, M) \ + ((PASTER(tuple, N,) *) lup, lup->lengths, label); \ + } \ + MY_Static_MES("To require a semicolon!") + +#define LENGHL(N) P_ATTR NUM *PASTER(luple, N, _len) \ + (PASTER(luple, N,) *lup) { \ + return lup->lengths; \ + } \ + MY_Static_MES("To require a semicolon!") + +/* TODO: Memory report */ + +struct tuple1_s { + NUM *array; + BOOL initialized; +}; + +TUP(2, 1); +TUP(3, 2); +TUP(4, 3); +TUP(5, 4); +TUP(6, 5); + +LTUP(2); +LTUP(3); +LTUP(4); +LTUP(5); +LTUP(6); + +UNUSED +static tuple1 * +new_tuple1(NUM len) +{ + tuple1 *result = NULL; + SAFE_CALLOC(tuple1, result, 1, return NULL;); + SAFE_CALLOC(NUM, result->array, len, free(result); return NULL;); + return result; +} + +CONSTRUCT(2, 1); +CONSTRUCT(3, 2); + +tuple4 * +new_tuple4() +{ + tuple4 *result = NULL; + SAFE_CALLOC(tuple4, result, 1, return NULL;); + return result; +} + +CONSTRUCT(5, 4); +CONSTRUCT(6, 5); + +LONSTRUCT(2); +LONSTRUCT(3); +LONSTRUCT(4); +LONSTRUCT(5); +LONSTRUCT(6); + +static void +destroy_tuple1(tuple1 tup, NUM * UNUSED len) { + if (!(tup.initialized)) return; + free(tup.array); +} + +DESTRUCT(2, 1); +DESTRUCT(3, 2); + +void +destroy_tuple4(tuple4 tup, NUM *len) +{ + if (!(tup.initialized)) return; + for (NUM i4 = 0; i4 < *len; i4++) + destroy_tuple3(*(tup.array+i4), len+1); + free(tup.array); +} + +DESTRUCT(5, 4); +DESTRUCT(6, 5); + +LESTRUCT(2); +LESTRUCT(3); +LESTRUCT(4); +LESTRUCT(5); +LESTRUCT(6); + +static BOOL +add_to_tuple1(tuple1 *tup, NUM *len, pair1 label, NUM val) +{ + if (!(tup->initialized)) { + SAFE_CALLOC(NUM, tup->array, *len, goto cleanup;); + } + tup->initialized = 1; + + if (label < 0 || label >= *len) { + fleprintf("Invalid label = %ld, len = %ld\n", + label, *len); + goto cleanup; + } + + *(tup->array+label) = val; + + return 0; + + cleanup: + return 1; +} + +static BOOL +add_to_tuple2(tuple2 *tup, NUM *len, pair2 label, NUM val) +{ + if (label.x < 0 || label.x >= *len) { + fleprintf("Invalid label = %ld, len = %ld\n", + label.x, *len); + goto cleanup; + } + + if (!(tup->initialized)) { + SAFE_CALLOC(tuple1, tup->array, *len, goto cleanup;); + tup->initialized = 1; + } + + pair1 newlabel = label.y; + + goto success; + + cleanup: + return 1; + + success: + return add_to_tuple1(tup->array+label.x, len+1, newlabel, val); +} + +ADDT(3, 2); +ADDT(4, 3); +ADDT(5, 4); +ADDT(6, 5); + +ADDL(2); +ADDL(3); +ADDL(4); +ADDL(5); +ADDL(6); + +H_ATTR +static BOOL +add_to_tuple_6_pt_2(tuple6 *tup, NUM *len, pair2 label) +{ + if (label.x < 0 || label.x >= *len) { + fleprintf("Invalid label = %ld, len = %ld\n", label.x, *len); + goto cleanup; + } + + if (!(tup->initialized)) { + SAFE_CALLOC(tuple5, tup->array, *len, goto cleanup;); + tup->initialized = 1; + } + + if (!((tup->array+label.x)->initialized)) { + SAFE_CALLOC(tuple4, (tup->array+label.x)->array, *(len+1), + goto cleanup;); + (tup->array+label.x)->initialized = 1; + } + + if (label.y < 0 || label.y >= *(len+1)) { + fleprintf("Invalid label = %ld, len = %ld\n", label.y, *(len+1)); + goto cleanup; + } + + if (!(((tup->array+label.x)->array+label.y)->initialized)) { + SAFE_CALLOC(tuple3, + ((tup->array+label.x)->array+label.y)->array, + *(len+1), goto cleanup;); + ((tup->array+label.x)->array+label.y)->initialized = 1; + } + + goto success; + + cleanup: + return 1; + + success: + return 0; +} + +H_ATTR +BOOL +add_to_luple6_pt_2(luple6 *lup, pair2 label) +{ + return add_to_tuple_6_pt_2((tuple6 *) lup, lup->lengths, label); +} + +HP_ATTR +static NUM * +tuple1_find(tuple1 *tup, NUM *len, NUM label) +{ + if (!(tup->initialized)) return NULL; + if (label < 0 || label >= *len) return NULL; + return tup->array+label; +} + +HP_ATTR +static NUM * +tuple2_find(tuple2 *tup, NUM *len, pair2 label) +{ + if (!(tup->initialized)) return NULL; + if (label.x < 0 || label.x >= *len) return NULL; + + return tuple1_find(tup->array+label.x, len+1, label.y); +} + +INDEXT(3, 2); +INDEXT(4, 3); +INDEXT(5, 4); +INDEXT(6, 5); + +INDEXL(2); +INDEXL(3); +INDEXL(4); +INDEXL(5); +INDEXL(6); + +HP_ATTR +static BOOL +tuple5_pf_1(tuple5 *tup, NUM *len, NUM label) +{ + if (!(tup->initialized)) return 0; + if (label < 0 || label >= *len) return 0; + + return (tup->array+label)->initialized; +} + +HP_ATTR +static BOOL +tuple6_pf_2(tuple6 *tup, NUM *len, pair2 label) +{ + if (!(tup->initialized)) return 0; + if (label.x < 0 || label.x >= *len) return 0; + NUM newlabel = label.y; + + return tuple5_pf_1(tup->array+label.x, len+1, newlabel); +} + +INDEXPL(6, 2); + +HP_ATTR +static BOOL +tuple3_pf_1(tuple3 *tup, NUM *len, NUM label) +{ + if (!(tup->initialized)) return 0; + if (label < 0 || label >= *len) return 0; + + return (tup->array+label)->initialized; +} + +HP_ATTR +static BOOL +tuple4_pf_2(tuple4 *tup, NUM *len, pair2 label) +{ + if (!(tup->initialized)) return 0; + if (label.x < 0 || label.x >= *len) return 0; + NUM newlabel = label.y; + + return tuple3_pf_1(tup->array+label.x, len+1, newlabel); +} + +INDEXPT(5, 3, 4, 2); + +INDEXPL(5, 3); + +HP_ATTR +static BOOL +tuple2_pf_1(tuple2 *tup, NUM *len, NUM label) +{ + if (!(tup->initialized)) return 0; + if (label < 0 || label >= *len) return 0; + + return (tup->array+label)->initialized; +} + +HP_ATTR +static BOOL +tuple3_pf_2(tuple3 *tup, NUM *len, pair2 label) +{ + if (!(tup->initialized)) return 0; + if (label.x < 0 || label.x >= *len) return 0; + NUM newlabel = label.y; + + return tuple2_pf_1(tup->array+label.x, len+1, newlabel); +} + +INDEXPL(3, 2); + +LENGHL(2); +LENGHL(3); +LENGHL(4); +LENGHL(5); +LENGHL(6); + +H_ATTR +static void +tuple3_map_2(tuple3 *tup, NUM *len, pair2 label, map_pair3_t fn) +{ + if (!(tup->initialized)) return; + if (label.x < 0 || label.x >= *len) return; + +#define AR (tup->array+label.x) +#define ARR (AR->array+label.y) +#define ARRR (ARR->array+i) + + if (!(AR->initialized)) return; + + if (label.y < 0 || label.y >= *(len+1)) return; + + if (!(ARR->initialized)) return; + + for (NUM i = 0; i < *(len+2); i++) + if (*ARRR) fn((pair3) { label.x, label.y, i }); + +#undef AR +#undef ARR +#undef ARRR + +} + +H_ATTR +static void +tuple6_map_2(tuple6 *tup, NUM *len, pair2 label, + NUM max, map_pair6_t fn) +{ + if (!(tup->initialized)) return; + if (label.x < 0 || label.x >= *len) return; + + tuple5 *AR1 = (tup->array+label.x); + + if (!(AR1->initialized)) return; + + if (label.y < 0 || label.y >= *(len+1)) return; + + tuple4 *AR2 = (AR1->array+label.y); + + if (!(AR2->initialized)) return; + + max = (max < 0 || max+1 >= *(len+5)) ? *(len+5) : max+1; + + for (NUM i = 0; i < *(len+2); i++) { + tuple3 *AR3 = (AR2->array+i); + if (!(AR3->initialized)) continue; + + for (NUM j = 0; j < *(len+3); j++) { + tuple2 *AR4 = (AR3->array+j); + if (!(AR4->initialized)) continue; + + for (NUM k = 0; k < *(len+4); k++) { + tuple1 *AR5 = (AR4->array+k); + if (!(AR5->initialized)) continue; + + for (NUM ell = 0; ell < max; ell++) { + if (*(AR5->array+ell)) + fn((pair6) { label.x, label.y, i, j, k, ell }); + } + } + } + } +} + +H_ATTR +static void +tuple6_map_5(tuple6 *tup, NUM *len, pair5 label, map_pair6_t fn) +{ + if (!(tup->initialized)) return; + if (label.x < 0 || label.x >= *len) return; + + tuple5 *AR1 = (tup->array+label.x); + + if (!(AR1->initialized)) return; + + if (label.y < 0 || label.y >= *(len+1)) return; + + tuple4 *AR2 = (AR1->array+label.y); + + if (!(AR2->initialized)) return; + + if (label.z < 0 || label.z >= *(len+2)) return; + + tuple3 *AR3 = (AR2->array+label.z); + + if (!(AR3->initialized)) return; + + if (label.u < 0 || label.u >= *(len+3)) return; + + tuple2 *AR4 = (AR3->array+label.u); + + if (!(AR4->initialized)) return; + + if (label.v < 0 || label.v >= *(len+4)) return; + + tuple1 *AR5 = (AR4->array+label.v); + + if (!(AR5->initialized)) return; + + for (NUM i = 0; i < *(len+5); i++) { + if (*(AR5->array+i)) + fn((pair6) { label.x, label.y, label.z, label.u, label.v, i }); + } +} + +H_ATTR +void +tuple5_map_3(tuple5 *tup, NUM *len, pair3 label, map_pair5_t fn) +{ + if (!(tup->initialized)) return; + + if (label.x < 0 || label.x >= *len) return; + + tuple4 *AR1 = tup->array+label.x; + + if (!(AR1->initialized)) return; + + if (label.y < 0 || label.y >= *(len+1)) return; + + tuple3 *AR2 = AR1->array+label.y; + + if (!(AR2->initialized)) return; + + if (label.z < 0 || label.z >= *(len+2)) return; + + tuple2 *AR3 = AR2->array+label.z; + + if (!(AR3->initialized)) return; + + for (NUM i = 0; i < *(len+3); i++) { + tuple1 *AR4 = AR3->array+i; + + if (!(AR4->initialized)) continue; + + for (NUM j = 0; j < *(len+4); j++) { + if (*(AR4->array+j)) + fn((pair5) { label.x, label.y, label.z, i, j }); + } + } +} + +H_ATTR +void +luple5_map_3(luple5 *lup, pair3 label, map_pair5_t fn) +{ + tuple5_map_3((tuple5 *) lup, lup->lengths, label, fn); +} + +H_ATTR +void +luple3_map_2(luple3 *lup, pair2 label, map_pair3_t fn) +{ + tuple3_map_2((tuple3 *) lup, lup->lengths, label, fn); +} + +H_ATTR +void +luple6_map_2(luple6 *lup, pair2 label, NUM max, map_pair6_t fn) +{ + tuple6_map_2((tuple6 *) lup, lup->lengths, label, max, fn); +} + +H_ATTR +void +luple6_map_5(luple6 *lup, pair5 label, map_pair6_t fn) +{ + tuple6_map_5((tuple6 *) lup, lup->lengths, label, fn); +} + +H_ATTR +void +luple5_free_1(luple5 *lup, NUM label) +{ + if (lup == NULL) return; + + tuple5 *tuple = (tuple5 *) lup; + + if (!(tuple->initialized)) return; + + if (label < 0 || label >= *(lup->lengths)) return; + + if (!((tuple->array+label)->initialized)) return; + + destroy_tuple4(*(tuple->array+label), lup->lengths+1); + + (tuple->array+label)->initialized = 0; +} + +#undef TUP +#undef LTUP +#undef CONSTRUCT +#undef LONSTRUCT +#undef DESTRUCT +#undef LESTRUCT +#undef ADDT +#undef ADDL +#undef INDEXT +#undef INDEXL +#undef INDEXPT +#undef INDEXPL +#undef LENTHL -- cgit v1.2.3-18-g5258