From c7ca99d4b03860bb258914fbc228272031eec77c Mon Sep 17 00:00:00 2001 From: Akim Demaille Date: Sun, 30 Jun 2002 17:29:36 +0000 Subject: [PATCH] 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'. --- ChangeLog | 21 +++++++++ src/LR0.c | 55 +++------------------ src/lalr.c | 3 -- src/lalr.h | 3 -- src/main.c | 1 + src/output.c | 11 ----- src/state.c | 131 ++++++++++++++++++++++++++++++++++++++++++++++++--- src/state.h | 21 +++++++-- 8 files changed, 169 insertions(+), 77 deletions(-) diff --git a/ChangeLog b/ChangeLog index 4399b37f..dca1c01c 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,24 @@ +2002-06-30 Akim Demaille + + 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'. + + 2002-06-30 Akim Demaille * src/state.h, src/state.c (state_new): New, extracted from... diff --git a/src/LR0.c b/src/LR0.c index 8f1df0d3..72780632 100644 --- a/src/LR0.c +++ b/src/LR0.c @@ -52,11 +52,6 @@ static item_number_t **kernel_base = NULL; 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 @@ allocate_storage (void) 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_storage (void) free (kernel_base); free (kernel_size); XFREE (kernel_items); - free (state_hash); + state_hash_free (); } @@ -185,6 +180,7 @@ new_state (symbol_number_t symbol, size_t core_size, item_number_t *core) 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 @@ new_state (symbol_number_t symbol, size_t core_size, item_number_t *core) 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 @@ get_state (symbol_number_t symbol, size_t core_size, item_number_t *core) 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); @@ -386,6 +344,7 @@ set_states (void) } } + /*-------------------------------------------------------------------. | Compute the nondeterministic finite state machine (see state.h for | | details) from the grammar. | diff --git a/src/lalr.c b/src/lalr.c index efd62220..46a1886b 100644 --- a/src/lalr.c +++ b/src/lalr.c @@ -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; diff --git a/src/lalr.h b/src/lalr.h index 82719d40..da4ab1ae 100644 --- a/src/lalr.h +++ b/src/lalr.h @@ -71,7 +71,4 @@ extern rule_t **LArule; extern bitsetv LA; -/* All the states, indexed by the state number. */ -extern state_t **states; - #endif /* !LALR_H_ */ diff --git a/src/main.c b/src/main.c index 2eb8f150..c5f78d10 100644 --- a/src/main.c +++ b/src/main.c @@ -105,6 +105,7 @@ main (int argc, char *argv[]) /* Output the tables and the parser to ftable. In file output. */ output (); + states_free (); reduce_free (); conflicts_free (); free_nullable (); diff --git a/src/output.c b/src/output.c index d5339a76..c07695b2 100644 --- a/src/output.c +++ b/src/output.c @@ -1132,8 +1132,6 @@ output_check (void) 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_actions (void) 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); } diff --git a/src/state.c b/src/state.c index 3000f9dc..874c5863 100644 --- a/src/state.c +++ b/src/state.c @@ -20,6 +20,7 @@ #include "system.h" +#include "hash.h" #include "complain.h" #include "gram.h" #include "state.h" @@ -30,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) \ @@ -116,6 +117,10 @@ state_number_t nstates = 0; 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. | `------------------------------------------------------------*/ @@ -129,10 +134,6 @@ state_new (symbol_number_t accessing_symbol, 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; @@ -177,3 +178,119 @@ state_rule_lookaheads_print (state_t *state, rule_t *rule, FILE *out) 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); +} diff --git a/src/state.h b/src/state.h index e98e2c65..524bfc9c 100644 --- a/src/state.h +++ b/src/state.h @@ -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 @@ reductions *reductions_new PARAMS ((int n)); 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 @@ state_t *state_new PARAMS ((symbol_number_t accessing_symbol, 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_ */ -- 2.45.2