Implemented a hash table with any type of keys

1 files changed, 102 insertions, 35 deletions

diff --git a/src/grammar.c b/src/grammar.c
index a24f9cb..bbc6934 100644
--- a/src/grammar.c
+++ b/src/grammar.c
@@ -558,6 +558,10 @@ nt_first(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
 
   ht *terminal_ht = NULL, *pred_ht = NULL;
 
+  NUM *temp = NULL;
+  T *tempT = NULL;
+  PT *tempPT = NULL;
+
   /* lazy macro */
 
 #define BREAKOUT k = string_len
@@ -568,30 +572,42 @@ nt_first(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
     for (NUM i = 0; i < left_len; i++) {
       Rule_group *rg = grammar_rule(g, (NT) i);
       NUM rg_length = rg_len(rg);
-
-      for (NUM j = 0; j < rg_length;) {
-        List *string = rg_nth(rg, j++);
+      /* fleprintf("rg_length = %ld\n", rg_length); */
+      for (NUM j = 0; j < rg_length; j++) {
+        List *string = rg_nth(rg, j);
         NUM string_len = list_length(string);
+        /* fleprintf("j = %ld, len = %ld\n", j, string_len); */
         TNT *top = NULL;
 
-        for (NUM k = 0; k < string_len;) {
-          top = (TNT *) list_nth(string, k++);
+        for (NUM k = 0; k < string_len; k++) {
+          top = (TNT *) list_nth(string, k);
 
           switch (top->type) {
           case TERMINAL:
+            SAFE_MALLOC(NUM, tempT, 1, return 1;);
+            *tempT = top->data.t;
             if (first &&
-                ht_find(terminal_hts+i, top->data.t) == NULL) {
+                ht_find(terminal_hts+i, tempT) == NULL) {
               changed = 1;
-              ht_insert(terminal_hts+i, top->data.t, (void*)1);
+              ht_insert(terminal_hts+i, tempT, (void*)1);
+              /* fleprintf("After insertion we find %p for %ld\n",
+               *           ht_find(terminal_hts+i, tempT),
+               *           *tempT); */
               BREAKOUT;
+            } else {
+              free(tempT);
             }
             break;
           case PREDICATE:
+            SAFE_MALLOC(NUM, tempPT, 1, return 1;);
+            *tempPT = top->data.pt;
             if (first &&
-                ht_find(predicate_hts+i, top->data.pt) == NULL) {
+                ht_find(predicate_hts+i, tempPT) == NULL) {
               changed = 1;
-              ht_insert(predicate_hts+i, top->data.pt, (void*)1);
+              ht_insert(predicate_hts+i, tempPT, (void*)1);
               BREAKOUT;
+            } else {
+              free(tempPT);
             }
             break;
           default:
@@ -602,13 +618,20 @@ nt_first(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
                found. */
 
             NUM len = ht_size(terminal_ht);
-            NUM *keys = ht_keys(terminal_ht);
+            void **keys = ht_keys(terminal_ht);
 
             for (NUM ell = 0; ell < len;) {
-              NUM key = *(keys+ell++);
-              if (ht_find(terminal_hts+i, key) == NULL) {
+              NUM *key = *(keys+ell++);
+              SAFE_MALLOC(NUM, temp, 1, return 1;);
+              *temp = *key;
+              /* fleprintf("i = %ld, j = %ld, ", i, j); */
+              if (ht_find(terminal_hts+i, temp) == NULL) {
+                /* eprintf("new item\n"); */
                 changed = 1;
-                ht_insert(terminal_hts+i, key, (void*)1);
+                ht_insert(terminal_hts+i, temp, (void*)1);
+              } else {
+                /* eprintf("already found for key = %ld\n", *temp); */
+                free(temp);
               }
             }
 
@@ -616,10 +639,17 @@ nt_first(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
             keys = ht_keys(pred_ht);
 
             for (NUM ell = 0; ell < len;) {
-              NUM key = *(keys+ell++);
-              if (ht_find(predicate_hts+i, key) == NULL) {
+              NUM *key = *(keys+ell++);
+              SAFE_MALLOC(NUM, temp, 1, return 1;);
+              *temp = *key;
+              /* fleprintf("i = %ld, j = %ld, ", i, j); */
+              if (ht_find(predicate_hts+i, temp) == NULL) {
+                /* eprintf("new item\n"); */
                 changed = 1;
-                ht_insert(predicate_hts+i, key, (void*)1);
+                ht_insert(predicate_hts+i, temp, (void*)1);
+              } else {
+                free(temp);
+                /* eprintf("already found for key = %ld\n", *temp); */
               }
             }
 
@@ -649,22 +679,34 @@ tnt_first(CC_MOD(ht *) terminal_hts, CC_MOD(ht *) predicate_hts,
 
   if (!tnt_len) return 0;
 
-  NUM temp_len = 0, *keys = NULL;
+  NUM temp_len = 0, **keys = NULL;
 
   TNT *top = NULL;
 
   NT current = 0;
 
+  NUM *temp = NULL;
+  T *tempT = NULL;
+  PT *tempPT = NULL;
+
   for (NUM i = 0; i < tnt_len; i++) {
     top = (TNT *) list_nth(tnts, i);
 
     switch (top->type) {
     case TERMINAL:
-      ht_insert(result_terminals, top->data.t, (void *)1);
+      if (ht_find(result_terminals, &(top->data.t)) == NULL) {
+        SAFE_MALLOC(T, tempT, 1, return 1;);
+        *tempT = top->data.t;
+        ht_insert(result_terminals, tempT, (void *)1);
+      }
       return 0;
       break;
     case PREDICATE:
-      ht_insert(result_predicates, top->data.pt, (void *)1);
+      if (ht_find(result_predicates, &(top->data.pt)) == NULL) {
+        SAFE_MALLOC(PT, tempPT, 1, return 1;);
+        *tempPT = top->data.pt;
+        ht_insert(result_predicates, tempPT, (void *)1);
+      }
       return 0;
       break;
     default:
@@ -676,16 +718,26 @@ tnt_first(CC_MOD(ht *) terminal_hts, CC_MOD(ht *) predicate_hts,
       }
 
       temp_len = ht_size(terminal_hts+current);
-      keys = ht_keys(terminal_hts+current);
+      keys = (NUM **) ht_keys(terminal_hts+current);
 
-      for (NUM j = 0; j < temp_len;)
-        ht_insert(result_terminals, *(keys+j++), (void *)1);
+      for (NUM j = 0; j < temp_len; j++) {
+        if (ht_find(result_terminals, *(keys+j)) == NULL) {
+          SAFE_MALLOC(NUM, temp, 1, return 1;);
+          *temp = **(keys+j);
+          ht_insert(result_terminals, temp, (void *)1);
+        }
+      }
 
       temp_len = ht_size(predicate_hts+current);
-      keys = ht_keys(predicate_hts+current);
+      keys = (NUM **) ht_keys(predicate_hts+current);
 
-      for (NUM j = 0; j < temp_len;)
-        ht_insert(result_predicates, *(keys+j++), (void *)1);
+      for (NUM j = 0; j < temp_len; j++) {
+        if (ht_find(result_predicates, *(keys+j)) == NULL) {
+          SAFE_MALLOC(NUM, temp, 1, return 1;);
+          *temp = **(keys+j);
+          ht_insert(result_predicates, temp, (void *)1);
+        }
+      }
 
       if (!(*(nts+current))) i = tnt_len;
 
@@ -702,13 +754,22 @@ nt_follow(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
           ht * const restrict result_terminals,
           ht * const restrict result_predicates)
 {
-  ht_insert(result_terminals, END_OF_INPUT, (void*)1);
+  NUM *tempN = NULL;
+
+  SAFE_MALLOC(NUM, tempN, 1, return 1;);
+  *tempN = END_OF_INPUT;
+
+  if (ht_find(result_terminals, tempN) == NULL) {
+    ht_insert(result_terminals, tempN, (void*)1);
+  } else {
+    free(tempN);
+  }
 
   NUM left_len = grammar_left_len(g);
 
   BOOL changed = 0, first = 1;
 
-  NUM ht_len = 0, *keys = NULL;
+  NUM ht_len = 0, **keys = NULL;
 
   List *temp = NULL;
 
@@ -782,28 +843,34 @@ nt_follow(CC_MOD(Grammar *) g, CCR_MOD(BOOL *) nts,
           add_to_follow:
 
             ht_len = ht_size(result_terminals+i);
-            keys = ht_keys(result_terminals+i);
+            keys = (NUM **) ht_keys(result_terminals+i);
 
             for (NUM ell = 0; ell < ht_len;) {
-              NUM key = *(keys+ell++);
+              SAFE_MALLOC(NUM, tempN, 1, return 1;);
+              *tempN = **(keys+ell++);
               if (ht_find(result_terminals+top->data.nt,
-                          key) == NULL) {
+                          tempN) == NULL) {
                 changed = 1;
                 ht_insert(result_terminals+top->data.nt,
-                          key, (void*)1);
+                          tempN, (void*)1);
+              } else {
+                free(tempN);
               }
             }
 
             ht_len = ht_size(result_predicates+i);
-            keys = ht_keys(result_predicates+i);
+            keys = (NUM **) ht_keys(result_predicates+i);
 
             for (NUM ell = 0; ell < ht_len;) {
-              NUM key = *(keys+ell++);
+              SAFE_MALLOC(NUM, tempN, 1, return 1;);
+              *tempN = **(keys+ell++);
               if (ht_find(result_predicates+top->data.nt,
-                          key) == NULL) {
+                          tempN) == NULL) {
                 changed = 1;
                 ht_insert(result_predicates+top->data.nt,
-                          key, (void*)1);
+                          tempN, (void*)1);
+              } else {
+                free(tempN);
               }
             }