From 7bb605ea778f20719858d6aa8569e385e252f934 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Mon, 8 Jun 2015 15:06:56 +0100 Subject: [PATCH] A better data structure for mapping 'yyaccept' values to DFA rule states. 'yyaccept' values must be continuous natural numbers starting from 0, so array indices represent them ideally. --- re2c/src/codegen/emit_action.cc | 59 ++++++++++++++------------------- re2c/src/codegen/emit_dfa.cc | 6 ++-- re2c/src/codegen/prepare_dfa.cc | 6 ++-- re2c/src/dfa/action.h | 10 +++--- re2c/src/dfa/dfa.cc | 2 +- re2c/src/dfa/dfa.h | 2 +- 6 files changed, 37 insertions(+), 48 deletions(-) diff --git a/re2c/src/codegen/emit_action.cc b/re2c/src/codegen/emit_action.cc index 66f0a3a2..c82f8b16 100644 --- a/re2c/src/codegen/emit_action.cc +++ b/re2c/src/codegen/emit_action.cc @@ -42,7 +42,7 @@ void emit_action case Action::MOVE: break; case Action::ACCEPT: - emit_accept (o, ind, readCh, s, * action.info.accept); + emit_accept (o, ind, readCh, s, * action.info.accepts); break; case Action::RULE: emit_rule (o, ind, s, action.info.rule, condName); @@ -149,26 +149,27 @@ void emit_save (OutputFile & o, uint32_t ind, bool & readCh, const State * const } } -void emit_accept_binary (OutputFile & o, uint32_t ind, bool & readCh, const State * const s, const accept_t & accept, uint32_t l, uint32_t r) +void emit_accept_binary (OutputFile & o, uint32_t ind, bool & readCh, const State * const s, const accept_t & accepts, uint32_t l, uint32_t r) { if (l < r) { const uint32_t m = (l + r) >> 1; o << indent(ind) << "if (" << mapCodeName["yyaccept"] << (r == l+1 ? " == " : " <= ") << m << ") {\n"; - emit_accept_binary (o, ++ind, readCh, s, accept, l, m); + emit_accept_binary (o, ++ind, readCh, s, accepts, l, m); o << indent(--ind) << "} else {\n"; - emit_accept_binary (o, ++ind, readCh, s, accept, m + 1, r); + emit_accept_binary (o, ++ind, readCh, s, accepts, m + 1, r); o << indent(--ind) << "}\n"; } else { - genGoTo(o, ind, s, accept.find(l)->second, readCh); + genGoTo(o, ind, s, accepts[l], readCh); } } -void emit_accept (OutputFile & o, uint32_t ind, bool & readCh, const State * const s, const accept_t & accept) +void emit_accept (OutputFile & o, uint32_t ind, bool & readCh, const State * const s, const accept_t & accepts) { - if (accept.size() > 0) + const uint32_t accepts_size = accepts.size (); + if (accepts_size > 0) { if (!DFlag) { @@ -181,61 +182,49 @@ void emit_accept (OutputFile & o, uint32_t ind, bool & readCh, const State * con readCh = false; } - if (accept.size() > 1) + if (accepts_size > 1) { - if (gFlag && accept.size() >= cGotoThreshold) + if (gFlag && accepts_size >= cGotoThreshold) { o << indent(ind++) << "{\n"; - o << indent(ind++) << "static void *" << mapCodeName["yytarget"] << "[" << accept.size() << "] = {\n"; - for (accept_t::const_iterator it = accept.begin(); it != accept.end(); ++it) + o << indent(ind++) << "static void *" << mapCodeName["yytarget"] << "[" << accepts_size << "] = {\n"; + for (uint32_t i = 0; i < accepts_size; ++i) { - o << indent(ind) << "&&" << labelPrefix << it->second->label << ",\n"; + o << indent(ind) << "&&" << labelPrefix << accepts[i]->label << ",\n"; } o << indent(--ind) << "};\n"; o << indent(ind) << "goto *" << mapCodeName["yytarget"] << "[" << mapCodeName["yyaccept"] << "];\n"; o << indent(--ind) << "}\n"; } - else if (sFlag || (accept.size() == 2 && !DFlag)) + else if (sFlag || (accepts_size == 2 && !DFlag)) { - emit_accept_binary (o, ind, readCh, s, accept, 0, accept.size() - 1); + emit_accept_binary (o, ind, readCh, s, accepts, 0, accepts_size - 1); } else if (DFlag) { - for (accept_t::const_iterator it = accept.begin(); it != accept.end(); ++it) + for (uint32_t i = 0; i < accepts_size; ++i) { - o << s->label << " -> " << it->second->label; - o << " [label=\"yyaccept=" << it->first << "\"]\n"; + o << s->label << " -> " << accepts[i]->label; + o << " [label=\"yyaccept=" << i << "\"]\n"; } } else { o << indent(ind) << "switch (" << mapCodeName["yyaccept"] << ") {\n"; - - accept_t::const_iterator it = accept.begin(), end = accept.end(); - - while (it != end) + for (uint32_t i = 0; i < accepts_size - 1; ++i) { - accept_t::const_iterator tmp = it; - - if (++it == end) - { - o << indent(ind) << "default:\t"; - } - else - { - o << indent(ind) << "case " << tmp->first << ": \t"; - } - - genGoTo(o, 0, s, tmp->second, readCh); + o << indent(ind) << "case " << i << ": \t"; + genGoTo(o, 0, s, accepts[i], readCh); } - + o << indent(ind) << "default:\t"; + genGoTo(o, 0, s, accepts.back (), readCh); o << indent(ind) << "}\n"; } } else { // no need to write if statement here since there is only case 0. - genGoTo(o, ind, s, accept.find(0)->second, readCh); + genGoTo(o, ind, s, accepts.front (), readCh); } } } diff --git a/re2c/src/codegen/emit_dfa.cc b/re2c/src/codegen/emit_dfa.cc index 001380cd..65148c9a 100644 --- a/re2c/src/codegen/emit_dfa.cc +++ b/re2c/src/codegen/emit_dfa.cc @@ -80,9 +80,9 @@ void DFA::count_used_labels (std::set & used, label_t start, label_t in { s->go.used_labels (used); } - for (accept_t::const_iterator i = accept_map.begin (); i != accept_map.end (); ++i) + for (accept_t::const_iterator i = accepts.begin (); i != accepts.end (); ++i) { - used.insert (i->second->label); + used.insert ((*i)->label); } // must go last: it needs the set of used labels if (used.count (head->label)) @@ -204,7 +204,7 @@ void DFA::emit(Output & output, uint32_t& ind, const RegExpMap* specMap, const s } // Generate code - const bool save_yyaccept = accept_map.size () > 1; + const bool save_yyaccept = accepts.size () > 1; for (State * s = head; s; s = s->next) { bool readCh = false; diff --git a/re2c/src/codegen/prepare_dfa.cc b/re2c/src/codegen/prepare_dfa.cc index 41d4317c..b908c178 100644 --- a/re2c/src/codegen/prepare_dfa.cc +++ b/re2c/src/codegen/prepare_dfa.cc @@ -234,7 +234,7 @@ void DFA::prepare(OutputFile & o, uint32_t & max_fill) if (saves[s->rule->accept] == ~0u) { saves[s->rule->accept] = nSaves++; - accept_map[saves[s->rule->accept]] = rules[s->rule->accept]; + accepts.push_back (rules[s->rule->accept]); } s->action.set_save (saves[s->rule->accept]); } @@ -242,11 +242,11 @@ void DFA::prepare(OutputFile & o, uint32_t & max_fill) } } delete [] saves; - if (accept_map.size () > 1) + if (accepts.size () > 1) { o.set_used_yyaccept (); } - default_state->action.set_accept (&accept_map); + default_state->action.set_accept (&accepts); } delete [] rules; diff --git a/re2c/src/dfa/action.h b/re2c/src/dfa/action.h index 87331d9a..0d33805a 100644 --- a/re2c/src/dfa/action.h +++ b/re2c/src/dfa/action.h @@ -1,7 +1,7 @@ #ifndef __ACTION__ #define __ACTION__ -#include +#include #include "src/codegen/label.h" #include "src/util/c99_stdint.h" @@ -24,7 +24,7 @@ struct Initial {} }; -typedef std::map accept_t; +typedef std::vector accept_t; class Action { @@ -42,7 +42,7 @@ public: { Initial * initial; uint32_t save; - const accept_t * accept; + const accept_t * accepts; const RuleOp * rule; } info; @@ -72,11 +72,11 @@ public: clear (); type = MOVE; } - void set_accept (const accept_t * accept) + void set_accept (const accept_t * accepts) { clear (); type = ACCEPT; - info.accept = accept; + info.accepts = accepts; } void set_rule (const RuleOp * const rule) { diff --git a/re2c/src/dfa/dfa.cc b/re2c/src/dfa/dfa.cc index a0a09091..922a893b 100644 --- a/re2c/src/dfa/dfa.cc +++ b/re2c/src/dfa/dfa.cc @@ -44,7 +44,7 @@ DFA::DFA(Ins *ins, uint32_t ni, uint32_t lb, uint32_t ub, const Char *rep) , toDo(NULL) , free_ins(ins) , free_rep(rep) - , accept_map () + , accepts () { Ins **work = new Ins * [ni + 1]; diff --git a/re2c/src/dfa/dfa.h b/re2c/src/dfa/dfa.h index 8609f91b..addfb220 100644 --- a/re2c/src/dfa/dfa.h +++ b/re2c/src/dfa/dfa.h @@ -24,7 +24,7 @@ public: const Char * free_rep; protected: - accept_t accept_map; + accept_t accepts; public: DFA (Ins *, uint32_t, uint32_t, uint32_t, const Char *); -- 2.40.0