need to stop abusing hash tables

Hash tables take too much space!
If I use hash tables, the length of the input will be severely
limited, to an unacceptable extent.  So we have to use arrays
instead.

4 files changed, 165 insertions, 39 deletions

diff --git a/src/test/check_bsr.c b/src/test/check_bsr.c
index 4a6ba4e..81a84a7 100644
--- a/src/test/check_bsr.c
+++ b/src/test/check_bsr.c
@@ -108,7 +108,7 @@ main(int UNUSED argc, char ** UNUSED argv)
 
   Grammar *g = new_grammar();
 
-  build_grammar(g, rules, names);
+  build_grammar(g, rules, names, NULL);
 
   print_grammar(g);
 
diff --git a/src/test/check_cnp.c b/src/test/check_cnp.c
index 7a0a325..91952ef 100644
--- a/src/test/check_cnp.c
+++ b/src/test/check_cnp.c
@@ -1,5 +1,17 @@
+#include "time.h"
 #include "../cnp.h"
 
+#define TIC do {                                \
+    clock_gettime(CLOCK_MONOTONIC_RAW, &tic);   \
+  } while (0)
+
+#define TOC do {                                        \
+    clock_gettime(CLOCK_MONOTONIC_RAW, &toc);           \
+    printf("\nTotal time = %f seconds\n",               \
+           (toc.tv_nsec - tic.tv_nsec) / 1000000000.0 + \
+           toc.tv_sec - tic.tv_sec);                    \
+  } while (0)
+
 #define READ_INTO_CPA(N, U, L, I, VA, VI, CP) do {      \
     U = new_utf8(N, L);                                 \
     I = get_info((str *)U, 0);                          \
@@ -34,6 +46,8 @@
     add_to_list(rules, rule);                                   \
   } while (0)
 
+#define GRAMMAR 2
+
 int
 main(int UNUSED argc, char ** UNUSED argv)
 {
@@ -44,9 +58,6 @@ main(int UNUSED argc, char ** UNUSED argv)
   List *names = new_list();
 
   char *name = MYALLOC(char, 2);
-  *(name+1) = 0;
-  *name = 'B';
-
   utf8* uname = NULL;
 
   str_info info = EMPTY_STR_INFO;
@@ -55,58 +66,166 @@ main(int UNUSED argc, char ** UNUSED argv)
   NUM vindex = 0;
   cpa *cpap = NULL;
 
-  READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
-
-  name = MYALLOC(char, 3);
-  *(name+1) = 0;
-  *name = 'U';
-
-  READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
-
-  /* name = MYALLOC(char, 2);
-   * *(name+1) = 0;
-   * *name = 'F';
-   *
-   * READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
-   *
-   * name = MYALLOC(char, 2);
-   * *(name+1) = 0;
-   * *name = 'D';
-   *
-   * READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap); */
-
-  READ_TNT_STRING(0, "nn", 2, (NT) 1, (NT) 0);
-  rule = new_rule(0, new_list());
-  add_to_list(rules, rule);
-
-  READ_TNT_STRING(1, "t", 1, (T) '>');
-  READ_TNT_STRING(1, "t", 1, (T) '<');
-  READ_TNT_STRING(1, "t", 1, (T) '+');
-  READ_TNT_STRING(1, "t", 1, (T) '-');
-  READ_TNT_STRING(1, "t", 1, (T) ',');
-  READ_TNT_STRING(1, "t", 1, (T) '.');
-  READ_TNT_STRING(1, "tnt", 3, (T) '[', (NT) 0, (T) ']');
+  switch (GRAMMAR) {
+  case 1:
+    *(name+1) = 0;
+    *name = 'S';
+
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    name = MYALLOC(char, 3);
+    *(name+1) = 0;
+    *name = 'A';
+
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    name = MYALLOC(char, 2);
+    *(name+1) = 0;
+    *name = 'B';
+
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    READ_TNT_STRING(0, "tnn", 3, (T) 'a', (NT) 1, (NT) 2);
+    READ_TNT_STRING(0, "tnt", 3, (T) 'a', (NT) 1, (T) 'b');
+
+    READ_TNT_STRING(1, "t", 1, (T) 'a');
+    READ_TNT_STRING(1, "t", 1, (T) 'c');
+    rule = new_rule(1, new_list());
+    add_to_list(rules, rule);
+
+    READ_TNT_STRING(2, "t", 1, (T) 'b');
+    READ_TNT_STRING(2, "nt", 2, (NT) 2, (T) 'c');
+    rule = new_rule(2, new_list());
+    add_to_list(rules, rule);
+    break;
+  case 2:
+    *(name+1) = 0;
+    *name = 'B';
+
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    name = MYALLOC(char, 2);
+    *(name+1) = 0;
+    *name = 'U';
+
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    READ_TNT_STRING(0, "nn", 2, (NT) 1, (NT) 0);
+    rule = new_rule(0, new_list());
+    add_to_list(rules, rule);
+
+    READ_TNT_STRING(1, "t", 1, (T) '>');
+    READ_TNT_STRING(1, "t", 1, (T) '<');
+    READ_TNT_STRING(1, "t", 1, (T) '+');
+    READ_TNT_STRING(1, "t", 1, (T) '-');
+    READ_TNT_STRING(1, "t", 1, (T) ',');
+    READ_TNT_STRING(1, "t", 1, (T) '.');
+    READ_TNT_STRING(1, "tnt", 3, (T) '[', (NT) 0, (T) ']');
+    break;
+  case 3:
+    *(name+1) = 0;
+    *name = 'S';
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    READ_TNT_STRING(0, "t", 1, (T) 'b');
+    READ_TNT_STRING(0, "nn", 2, (NT) 0, (NT) 0);
+    READ_TNT_STRING(0, "nnn", 3, (NT) 0, (NT) 0, (NT) 0);
+    break;
+  case 4:
+    *(name+1) = 0;
+    *name = 'S';
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    name = MYALLOC(char, 2);
+    *(name+1) = 0;
+    *name = 'T';
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    name = MYALLOC(char, 2);
+    *(name+1) = 0;
+    *name = 'U';
+    READ_INTO_CPA(name, uname, 1, info, varray, vindex, cpap);
+
+    READ_TNT_STRING(0, "nnn", 3, (NT) 0, (NT) 1, (NT) 2);
+    READ_TNT_STRING(1, "nnn", 3, (NT) 1, (NT) 2, (NT) 0);
+    READ_TNT_STRING(2, "nnn", 3, (NT) 2, (NT) 0, (NT) 1);
+    rule = new_rule(0, new_list());
+    add_to_list(rules, rule);
+    rule = new_rule(1, new_list());
+    add_to_list(rules, rule);
+    rule = new_rule(2, new_list());
+    add_to_list(rules, rule);
+    READ_TNT_STRING(0, "t", 1, (T) 'a');
+    break;
+  default:
+    fleprintf0("Forgot to assign grammar!\n");
+    break;
+  }
 
   Grammar *g = new_grammar();
 
-  build_grammar(g, rules, names);
+  build_grammar(g, rules, names, NULL);
 
   print_grammar(g);
 
-  utf8 *string = new_utf8("[,[.[+]]-]", 10);
+  utf8 *string = NULL;
+
+  switch (GRAMMAR) {
+  case 1:
+    string = new_utf8("aab", 3);
+    break;
+  case 2:
+    string = new_utf8("[+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><][+-[.,]><]", 100);
+    break;
+  case 3:
+    string = new_utf8("bbbbb", 5);
+    break;
+  case 4:
+    string = new_utf8("aaaaaaaaaaaa", 12);
+    break;
+  default:
+    fleprintf0("Forgot to assign input!\n");
+    break;
+  }
 
   printf("\nPrinting the input...\n%s\n", get_data((str *) string));
 
+  struct timespec tic, toc;
+  TIC;
+
   Environment *env = cnp_parse(g, (str *) string);
 
+  TOC;
+
   if (env) {
     if (!(env_error_p(env))) {
-      printf("Successfully parsed the input:\n");
+      BOOL error = 0;
+      ht *result = bsr_lookup
+        (env_bsrp(env), &error, 0, 0, str_length((str *) string));
+
+      if (error) {
+        printf("There are errors!\n");
+        goto destroy;
+      }
+
+      if (result && ht_size(result)) {
+        printf("\nSuccessfully parsed the input!\n");
+        for (NUM i = 0; i < ht_size(result); i++)
+          printf("(%d, %ld, %d, %ld, %ld)\n",
+                 0, (*((pair2 **) ht_keys(result)+i))->x,
+                 0, (*((pair2 **) ht_keys(result)+i))->y,
+                 str_length((str *) string));
+      } else {
+        printf("\nThe input does not parse!\n");
+      }
+
+      printf("\nAll BSRs follow:\n\n");
       bsr_print(env_bsrp(env), env_grammar(env), 1);
     } else {
       printf("There are errors!\n");
     }
 
+  destroy:
     destroy_env(env);
   }
 
diff --git a/src/test/check_grammar.c b/src/test/check_grammar.c
index 7e55681..e66b262 100644
--- a/src/test/check_grammar.c
+++ b/src/test/check_grammar.c
@@ -136,7 +136,7 @@ main(UNUSED int argc, UNUSED char **argv)
 
   Grammar *g = new_grammar();
 
-  build_grammar(g, rules, names);
+  build_grammar(g, rules, names, NULL);
 
   print_grammar(g);
 
diff --git a/src/test/check_pred.c b/src/test/check_pred.c
new file mode 100644
index 0000000..b0b95b3
--- /dev/null
+++ b/src/test/check_pred.c
@@ -0,0 +1,7 @@
+#include "../grammar.h"
+
+int
+main(int UNUSED argc, char ** UNUSED argv)
+{
+  return 77;
+}