Use bitset operations when possible, not loops over bits.

* src/conflicts.c (set_conflicts, count_sr_conflicts): Use
bitset_or.
* src/print.c (print_reductions): Use bitset_and, bitset_andn.
* src/reduce.c (useless_nonterminals): Formatting changes.
* src/warshall.c (TC): Use bitset_or.

diff --git a/ChangeLog b/ChangeLog
index 90c608753f8312d2f33560c8ed6baae4de961ae3..c816b0076b015d724cadbd92262889d4ed4542f8 100644 (file)
--- a/ChangeLog
+++ b/ChangeLog
@@ -1,3 +1,14 @@
+2002-03-04  Akim Demaille  <akim@epita.fr>
+
+       Use bitset operations when possible, not loops over bits.
+
+       * src/conflicts.c (set_conflicts, count_sr_conflicts): Use
+       bitset_or.
+       * src/print.c (print_reductions): Use bitset_and, bitset_andn.
+       * src/reduce.c (useless_nonterminals): Formatting changes.
+       * src/warshall.c (TC): Use bitset_or.
+
+       
 2002-03-04  Akim Demaille  <akim@epita.fr>
 
        * src/lalr.h, src/lalr.c (tokensetsize): Remove, unused.

diff --git a/src/conflicts.c b/src/conflicts.c
index 6d9562bc72749e04956e9520d34ef40b85d7fe89..e08256a161b8b9e8ec6eab7a67afebe3e0660da6 100644 (file)
--- a/src/conflicts.c
+++ b/src/conflicts.c
@@ -186,14 +186,13 @@ set_conflicts (state_t *state)
      for conflicts not resolved above.  */
   for (i = 0; i < state->nlookaheads; ++i)
     {
+      /* FIXME: Here, I need something like `bitset_disjoint_p'. */
       for (j = 0; j < ntokens; ++j)
        if (bitset_test (LA[state->lookaheadsp + i], j)
            && bitset_test (lookaheadset, j))
          conflicts[state->number] = 1;
 
-      for (j = 0; j < ntokens; ++j)
-       if (bitset_test (LA[state->lookaheadsp + i], j))
-         bitset_set (lookaheadset, j);
+      bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);
     }
 }
 
@@ -220,7 +219,7 @@ solve_conflicts (void)
 static int
 count_sr_conflicts (state_t *state)
 {
-  int i, k;
+  int i;
   int src_count = 0;
   shifts *shiftp = state->shifts;
 
@@ -235,9 +234,7 @@ count_sr_conflicts (state_t *state)
       bitset_set (shiftset, SHIFT_SYMBOL (shiftp, i));
 
   for (i = 0; i < state->nlookaheads; ++i)
-    for (k = 0; k < ntokens; ++k)
-      if (bitset_test (LA[state->lookaheadsp + i], k))
-       bitset_set (lookaheadset, k);
+    bitset_or (lookaheadset, lookaheadset, LA[state->lookaheadsp + i]);
 
   bitset_and (lookaheadset, lookaheadset, shiftset);
 

diff --git a/src/print.c b/src/print.c
index 17823f8ea401c721bcff8cc90148df32cdab65b0..6dd25096a0037978334ccdcb949f591cf5a88e9d 100644 (file)
--- a/src/print.c
+++ b/src/print.c
@@ -215,12 +215,7 @@ print_reductions (FILE *out, state_t *state)
     {
       int default_rule = LAruleno[state->lookaheadsp];
 
-      for (i = 0; i < ntokens; ++i)
-       if (bitset_test (LA[state->lookaheadsp], i)
-           && bitset_test (shiftset, i))
-         bitset_set (lookaheadset, i);
-       else
-         bitset_reset (lookaheadset, i);
+      bitset_and (lookaheadset, LA[state->lookaheadsp], shiftset);
 
       for (i = 0; i < ntokens; i++)
        if (bitset_test (lookaheadset, i))
@@ -241,14 +236,9 @@ print_reductions (FILE *out, state_t *state)
        for (i = 0; i < state->nlookaheads; ++i)
          {
            int count = 0;
-           int j, k;
+           int j;
 
-           for (k = 0; k < ntokens; ++k)
-             if (bitset_test (LA[state->lookaheadsp + i], k)
-                 && ! bitset_test (shiftset, k))
-               bitset_set (lookaheadset, k);
-             else
-               bitset_reset (lookaheadset, k);
+           bitset_andn (lookaheadset, LA[state->lookaheadsp + i], shiftset);
 
            for (j = 0; j < ntokens; j++)
              if (bitset_test (lookaheadset, j))
@@ -277,39 +267,37 @@ print_reductions (FILE *out, state_t *state)
          int count = bitset_test (shiftset, i);
 
          for (j = 0; j < state->nlookaheads; ++j)
-           {
-             if (bitset_test (LA[state->lookaheadsp + j], i))
-               {
-                 if (count == 0)
-                   {
-                     if (state->lookaheadsp + j != default_LA)
-                       fprintf (out,
-                                _("    %-4s\treduce using rule %d (%s)\n"),
-                                escape (symbols[i]->tag),
-                                LAruleno[state->lookaheadsp + j] - 1,
-                                escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
-                     else
-                       defaulted = 1;
-
-                     count++;
-                   }
-                 else
-                   {
-                     if (defaulted)
-                       fprintf (out,
-                                _("    %-4s\treduce using rule %d (%s)\n"),
-                                escape (symbols[i]->tag),
-                                LAruleno[default_LA] - 1,
-                                escape2 (symbols[rules[LAruleno[default_LA]].lhs]->tag));
-                     defaulted = 0;
+           if (bitset_test (LA[state->lookaheadsp + j], i))
+             {
+               if (count == 0)
+                 {
+                   if (state->lookaheadsp + j != default_LA)
                      fprintf (out,
-                              _("    %-4s\t[reduce using rule %d (%s)]\n"),
+                              _("    %-4s\treduce using rule %d (%s)\n"),
                               escape (symbols[i]->tag),
                               LAruleno[state->lookaheadsp + j] - 1,
                               escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
-                   }
-               }
-           }
+                   else
+                     defaulted = 1;
+
+                   count++;
+                 }
+               else
+                 {
+                   if (defaulted)
+                     fprintf (out,
+                              _("    %-4s\treduce using rule %d (%s)\n"),
+                              escape (symbols[i]->tag),
+                              LAruleno[default_LA] - 1,
+                              escape2 (symbols[rules[LAruleno[default_LA]].lhs]->tag));
+                   defaulted = 0;
+                   fprintf (out,
+                            _("    %-4s\t[reduce using rule %d (%s)]\n"),
+                            escape (symbols[i]->tag),
+                            LAruleno[state->lookaheadsp + j] - 1,
+                            escape2 (symbols[rules[LAruleno[state->lookaheadsp + j]].lhs]->tag));
+                 }
+             }
        }
 
       if (default_LA >= 0)

diff --git a/src/reduce.c b/src/reduce.c
index 05d15d23297c198ac3f98ffdb7e1d4b7ba737e2e..973e5edea4ebe25c8a4159ff4bf2366fb81e5196 100644 (file)
--- a/src/reduce.c
+++ b/src/reduce.c
@@ -126,16 +126,12 @@ useless_nonterminals (void)
     {
       bitset_copy (Np, N);
       for (i = 1; i <= nrules; i++)
-       {
-         if (!bitset_test (P, i))
-           {
-             if (useful_production (i, N))
-               {
-                 bitset_set (Np, rules[i].lhs - ntokens);
-                 bitset_set (P, i);
-               }
-           }
-       }
+       if (!bitset_test (P, i)
+           && useful_production (i, N))
+         {
+           bitset_set (Np, rules[i].lhs - ntokens);
+           bitset_set (P, i);
+         }
       if (bitset_equal_p (N, Np))
        break;
       Ns = Np;

diff --git a/src/warshall.c b/src/warshall.c
index ff41d5ba9ddefd398b0392ddac9f8f381eaf4f69..c962bc7fdb6577046ca037a48519ea9a25d1c0aa 100644 (file)
--- a/src/warshall.c
+++ b/src/warshall.c
@@ -79,7 +79,7 @@ bitmatrix_print (const char *title, bitset *matrix, size_t size)
 static void
 TC (bitset *matrix, int n)
 {
-  int i, j, k;
+  int i, j;
 
   if (trace_flag)
     bitmatrix_print ("TC: Input", matrix, n);
@@ -90,9 +90,7 @@ TC (bitset *matrix, int n)
   for (i = 0; i < n; ++i)
     for (j = 0; j < n; ++j)
       if (bitset_test (matrix[j], i))
-       for (k = 0; k < n; ++k)
-         if (bitset_test (matrix[i], k))
-           bitset_set (matrix[j], k);
+       bitset_or (matrix[j], matrix[j], matrix[i]);
 
   if (trace_flag)
     bitmatrix_print ("TC: Output", matrix, n);