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.

1 files changed, 629 insertions, 0 deletions

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 <stdio.h>
+#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