05-state-hash.patch

[Akim Demaille]

Index: ChangeLog
from  Akim Demaille  <address@hidden>
        Use hash.h for the state hash table.
        
        * src/LR0.c (STATE_HASH_SIZE, state_hash): Remove.
        (allocate_storage): Use state_hash_new.
        (free_storage): Use state_hash_free.
        (new_state, get_state): Adjust.
        * src/lalr.h, src/lalr.c (states): Move to...
        * src/states.h (state_t): Remove the `link' member, no longer
        used.
        * src/states.h, src/states.c: here.
        (state_hash_new, state_hash_free, state_hash_lookup)
        (state_hash_insert, states_free): New.
        * src/states.c (state_table, state_compare, state_hash): New.
        * src/output.c (output_actions): Do not free states now, since we
        still need to know the final_state number in `prepare', called
        afterwards.  Do it...
        * src/main.c (main): here: call states_free after `output'.
        
        
Index: src/LR0.c
--- src/LR0.c Sat, 29 Jun 2002 10:57:45 +0200 akim
+++ src/LR0.c Sat, 29 Jun 2002 12:38:07 +0200 akim
@@ -52,11 +52,6 @@
 static int *kernel_size = NULL;
 static item_number_t *kernel_items = NULL;
 
-/* hash table for states, to recognize equivalent ones.  */
-
-#define        STATE_HASH_SIZE 1009
-static state_t **state_hash = NULL;
-
 
 static void
 allocate_itemsets (void)
@@ -107,7 +102,7 @@
 
   shiftset = XCALLOC (state_number_t, nsyms);
   redset = XCALLOC (short, nrules + 1);
-  state_hash = XCALLOC (state_t *, STATE_HASH_SIZE);
+  state_hash_new ();
   shift_symbol = XCALLOC (symbol_number_t, nsyms);
 }
 
@@ -121,7 +116,7 @@
   free (kernel_base);
   free (kernel_size);
   XFREE (kernel_items);
-  free (state_hash);
+  state_hash_free ();
 }
 
 
@@ -185,6 +180,7 @@
             nstates, symbol, symbol_tag_get (symbols[symbol]));
 
   res = state_new (symbol, core_size, core);
+  state_hash_insert (res);
 
   /* If this is the eoftoken, and this is not the initial state, then
      this is the final state.  */
@@ -210,8 +206,6 @@
 static state_number_t
 get_state (symbol_number_t symbol, size_t core_size, item_number_t *core)
 {
-  int key;
-  size_t i;
   state_t *sp;
 
   if (trace_flag)
@@ -219,45 +213,9 @@
             this_state->number, symbol,
             symbol_tag_get (symbols[symbol]));
 
-  /* Add up the target state's active item numbers to get a hash key.
-     */
-  key = 0;
-  for (i = 0; i < core_size; ++i)
-    key += core[i];
-  key = key % STATE_HASH_SIZE;
-  sp = state_hash[key];
-
-  if (sp)
-    {
-      int found = 0;
-      while (!found)
-       {
-         if (sp->nitems == core_size)
-           {
-             found = 1;
-             for (i = 0; i < core_size; ++i)
-               if (core[i] != sp->items[i])
-                 found = 0;
-           }
-
-         if (!found)
-           {
-             if (sp->link)
-               {
-                 sp = sp->link;
-               }
-             else              /* bucket exhausted and no match */
-               {
-                 sp = sp->link = new_state (symbol, core_size, core);
-                 found = 1;
-               }
-           }
-       }
-    }
-  else                         /* bucket is empty */
-    {
-      state_hash[key] = sp = new_state (symbol, core_size, core);
-    }
+  sp = state_hash_lookup (core_size, core);
+  if (!sp)
+    sp = new_state (symbol, core_size, core);
 
   if (trace_flag)
     fprintf (stderr, "Exiting get_state => %d\n", sp->number);
@@ -385,6 +343,7 @@
       states[sp->number] = sp;
     }
 }
+
 
 /*-------------------------------------------------------------------.
 | Compute the nondeterministic finite state machine (see state.h for |
Index: src/lalr.c
--- src/lalr.c Sat, 29 Jun 2002 10:18:41 +0200 akim
+++ src/lalr.c Sat, 29 Jun 2002 12:16:48 +0200 akim
@@ -39,9 +39,6 @@
 #include "derives.h"
 #include "getargs.h"
 
-/* All the decorated states, indexed by the state number.  */
-state_t **states = NULL;
-
 rule_t **LArule = NULL;
 bitsetv LA = NULL;
 size_t nLA;
Index: src/lalr.h
--- src/lalr.h Sat, 29 Jun 2002 10:18:41 +0200 akim
+++ src/lalr.h Sat, 29 Jun 2002 12:17:16 +0200 akim
@@ -71,7 +71,4 @@
 extern bitsetv LA;
 
 
-/* All the states, indexed by the state number.  */
-extern state_t **states;
-
 #endif /* !LALR_H_ */
Index: src/main.c
--- src/main.c Fri, 14 Jun 2002 19:06:56 +0200 akim
+++ src/main.c Sat, 29 Jun 2002 12:16:10 +0200 akim
@@ -105,6 +105,7 @@
   /* Output the tables and the parser to ftable.  In file output.  */
   output ();
 
+  states_free ();
   reduce_free ();
   conflicts_free ();
   free_nullable ();
Index: src/output.c
--- src/output.c Sat, 29 Jun 2002 10:18:41 +0200 akim
+++ src/output.c Sat, 29 Jun 2002 12:20:42 +0200 akim
@@ -1132,8 +1132,6 @@
 static void
 output_actions (void)
 {
-  state_number_t i;
-
   /* That's a poor way to make sure the sizes are properly corelated,
      in particular the signedness is not taking into account, but it's
      not useless.  */
@@ -1165,15 +1163,6 @@
   output_conflicts ();
 
   output_check ();
-
-  for (i = 0; i < nstates; ++i)
-    {
-      free (states[i]->shifts);
-      XFREE (states[i]->reductions);
-      free (states[i]->errs);
-      free (states[i]);
-    }
-  XFREE (states);
 }
 
 
Index: src/state.c
--- src/state.c Sat, 29 Jun 2002 10:57:45 +0200 akim
+++ src/state.c Sat, 29 Jun 2002 12:39:10 +0200 akim
@@ -20,6 +20,8 @@
 
 
 #include "system.h"
+#include "hash.h"
+#include "complain.h"
 #include "gram.h"
 #include "state.h"
 
@@ -29,9 +31,9 @@
                        `-------------------*/
 
 
-/*---------------------------------.
-| Create a new array of N shitfs.  |
-`---------------------------------*/
+/*---------------------------------------.
+| Create a new array of N shifts/gotos.  |
+`---------------------------------------*/
 
 #define SHIFTS_ALLOC(Nshifts)                                          \
   (shifts *) xcalloc ((unsigned) (sizeof (shifts)                      \
@@ -115,6 +117,10 @@
    accessing symbol: EOF.  */
 state_t *final_state = NULL;
 
+#define STATE_ALLOC(Nitems)                                            \
+  (state_t *) xcalloc ((unsigned) (sizeof (state_t)                    \
+                                  + (Nitems - 1) * sizeof (item_number_t)), 1)
+
 /*------------------------------------------------------------.
 | Create a new state with ACCESSING_SYMBOL, for those items.  |
 `------------------------------------------------------------*/
@@ -128,10 +134,6 @@
   if (nstates >= STATE_NUMBER_MAX)
     fatal (_("too many states (max %d)"), STATE_NUMBER_MAX);
 
-#define STATE_ALLOC(Nitems)                                            \
-  (state_t *) xcalloc ((unsigned) (sizeof (state_t)                    \
-                                  + (Nitems - 1) * sizeof (item_number_t)), 1)
-
   res = STATE_ALLOC (core_size);
   res->accessing_symbol = accessing_symbol;
   res->number = nstates;
@@ -175,4 +177,120 @@
                     --nlookaheads ? ", " : "");
       fprintf (out, "]");
     }
+}
+
+
+/*----------------------.
+| A state hash table.  |
+`----------------------*/
+
+/* Initial capacity of states hash table.  */
+#define HT_INITIAL_CAPACITY 257
+
+static struct hash_table *state_table = NULL;
+
+/* Two states are equal if they have the same core items.  */
+static bool
+state_compare (const state_t *s1, const state_t *s2)
+{
+  int i;
+
+  if (s1->nitems != s2->nitems)
+    return FALSE;
+
+  for (i = 0; i < s1->nitems; ++i)
+    if (s1->items[i] != s2->items[i])
+      return FALSE;
+
+  return TRUE;
+}
+
+static unsigned int
+state_hash (const state_t *state, unsigned int tablesize)
+{
+  /* Add up the state's item numbers to get a hash key.  */
+  int key = 0;
+  int i;
+  for (i = 0; i < state->nitems; ++i)
+    key += state->items[i];
+  return key % tablesize;
+}
+
+
+/*-------------------------------.
+| Create the states hash table.  |
+`-------------------------------*/
+
+void
+state_hash_new (void)
+{
+  state_table = hash_initialize (HT_INITIAL_CAPACITY,
+                                NULL,
+                                (Hash_hasher) state_hash,
+                                (Hash_comparator) state_compare,
+                                (Hash_data_freer) NULL);
+}
+
+
+/*---------------------------------------------.
+| Free the states hash table, not the states.  |
+`---------------------------------------------*/
+
+void
+state_hash_free (void)
+{
+  hash_free (state_table);
+}
+
+
+/*---------------------------------------.
+| Insert STATE in the state hash table.  |
+`---------------------------------------*/
+
+void
+state_hash_insert (state_t *state)
+{
+  hash_insert (state_table, state);
+}
+
+
+/*------------------------------------------------------------------.
+| Find the state associated to the CORE, and return it.  If it does |
+| not exist yet, return NULL.                                       |
+`------------------------------------------------------------------*/
+
+state_t *
+state_hash_lookup (size_t core_size, item_number_t *core)
+{
+  state_t *probe = STATE_ALLOC (core_size);
+  state_t *entry;
+
+  probe->nitems = core_size;
+  memcpy (probe->items, core, core_size * sizeof (core[0]));
+  entry = hash_lookup (state_table, probe);
+  free (probe);
+  return entry;
+}
+
+/* All the decorated states, indexed by the state number.  */
+state_t **states = NULL;
+
+
+/*----------------------.
+| Free all the states.  |
+`----------------------*/
+
+void
+states_free (void)
+{
+  state_number_t i;
+
+  for (i = 0; i < nstates; ++i)
+    {
+      free (states[i]->shifts);
+      XFREE (states[i]->reductions);
+      free (states[i]->errs);
+      free (states[i]);
+    }
+  XFREE (states);
 }
Index: src/state.h
--- src/state.h Sat, 29 Jun 2002 10:57:45 +0200 akim
+++ src/state.h Sat, 29 Jun 2002 12:36:28 +0200 akim
@@ -44,10 +44,6 @@
    Each core contains a vector of NITEMS items which are the indices
    in the RITEMS vector of the items that are selected in this state.
 
-   The link field is used for chaining symbols that hash states by
-   their itemsets.  This is for recognizing equivalent states and
-   combining them when the states are generated.
-
    The two types of transitions are shifts (push the lookahead token
    and read another) and reductions (combine the last n things on the
    stack via a rule, replace them with the symbol that the rule
@@ -180,7 +176,6 @@
 typedef struct state_s
 {
   struct state_s *next;
-  struct state_s *link;
 
   state_number_t number;
   symbol_number_t accessing_symbol;
@@ -220,4 +215,20 @@
 void state_rule_lookaheads_print PARAMS ((state_t *state, rule_t *rule,
                                          FILE *out));
 
+/* Create/destroy the states hash table.  */
+void state_hash_new PARAMS ((void));
+void state_hash_free PARAMS ((void));
+
+/* Find the state associated to the CORE, and return it.  If it does
+   not exist yet, return NULL.  */
+state_t *state_hash_lookup PARAMS ((size_t core_size, item_number_t *core));
+
+/* Insert STATE in the state hash table.  */
+void state_hash_insert PARAMS ((state_t *state));
+
+/* All the states, indexed by the state number.  */
+extern state_t **states;
+
+/* Free all the states.  */
+void states_free PARAMS ((void));
 #endif /* !STATE_H_ */