[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
05-state-hash.patch
From: |
Akim Demaille |
Subject: |
05-state-hash.patch |
Date: |
Sun, 30 Jun 2002 19:26:48 +0200 |
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_ */
[Prev in Thread] |
Current Thread |
[Next in Thread] |
- 05-state-hash.patch,
Akim Demaille <=