From 19e73705c5b734a5867b4308c880f8bb8762caa2 Mon Sep 17 00:00:00 2001 From: Ulya Trofimovich Date: Wed, 16 Mar 2016 13:54:23 +0000 Subject: [PATCH] Pack all stuff relevant to skeleton data generation in a struct. --- re2c/src/ir/skeleton/generate_data.cc | 109 +++++++++++++++----------- re2c/src/ir/skeleton/path.h | 12 ++- re2c/src/ir/skeleton/skeleton.cc | 11 +-- re2c/src/ir/skeleton/skeleton.h | 6 +- 4 files changed, 73 insertions(+), 65 deletions(-) diff --git a/re2c/src/ir/skeleton/generate_data.cc b/re2c/src/ir/skeleton/generate_data.cc index 7e1a582a..232a2c6f 100644 --- a/re2c/src/ir/skeleton/generate_data.cc +++ b/re2c/src/ir/skeleton/generate_data.cc @@ -46,7 +46,24 @@ namespace re2c // Paths are dumped to file as soon as generated and don't eat // heap space. The total size of path cover (measured in edges) // is O(N^2) where N is the number of edges in skeleton. -typedef u32lim_t<1024 * 1024 * 1024> covers_t; // ~1Gb +typedef u32lim_t<1024 * 1024 * 1024> cover_size_t; // ~1Gb + +struct cover_t +{ + FILE *input; + FILE *keys; + std::vector loops; + std::vector suffixes; + path_t prefix; + cover_size_t size; + + cover_t(FILE *fi, FILE *fk, size_t nnodes): + input(fi), keys(fk), loops(nnodes), + suffixes(nnodes), prefix(0), + size(cover_size_t::from32(0u)) {} + + FORBID_COPY(cover_t); +}; template static uintn_t to_le(uintn_t n) { @@ -74,9 +91,10 @@ template static void keygen(FILE *f, size_t count, delete[] keys; } -template static covers_t cover_one( - Skeleton &skel, FILE *input, FILE * keys, const path_t & path) +template static cover_size_t cover_one( + const Skeleton &skel, cover_t &cover) { + const path_t &path = cover.prefix; const size_t len = path.len(); size_t count = 0; @@ -84,8 +102,8 @@ template static covers_t cover_one( count = std::max (count, path.arc(skel, i).size()); } - const covers_t size = covers_t::from64(len) - * covers_t::from64(count); + const cover_size_t size = cover_size_t::from64(len) + * cover_size_t::from64(count); if (!size.overflow()) { // input const size_t buffer_size = size.uint32(); @@ -95,14 +113,16 @@ template static covers_t cover_one( const size_t width = arc.size(); for (size_t j = 0; j < count; ++j) { const size_t k = j % width; - buffer[j * len + i] = to_le(static_cast(arc[k])); + buffer[j * len + i] = to_le( + static_cast(arc[k])); } } - fwrite (buffer, sizeof(cunit_t), buffer_size, input); + fwrite (buffer, sizeof(cunit_t), buffer_size, cover.input); delete[] buffer; // keys - keygen(keys, count, len, path.len_matching(skel), path.match(skel)); + keygen(cover.keys, count, len, + path.len_matching(skel), path.match(skel)); } return size; @@ -137,29 +157,29 @@ template static covers_t cover_one( * See also note [counting skeleton edges]. * */ -template static void cover( - Skeleton &skel, - FILE *input, - FILE *keys, - path_t &prefix, - covers_t &size, +template static void gencover( + const Skeleton &skel, + cover_t &cover, size_t i) { const Node &node = skel.nodes[i]; - uint8_t &loop = skel.loops[i]; - suffix_t *&suffix = skel.suffixes[i]; + uint8_t &loop = cover.loops[i]; + suffix_t &suffix = cover.suffixes[i]; + path_t &prefix = cover.prefix; + cover_size_t &size = cover.size; - if (node.end() && suffix == NULL) { - suffix = new suffix_t; + if (node.end() && !suffix.init) { + suffix.init = true; } - if (suffix != NULL) + if (suffix.init) { - prefix.push_sfx(*suffix); - size = size + cover_one(skel, input, keys, prefix); - prefix.pop_sfx(*suffix); + prefix.push_sfx(suffix); + size = size + cover_one(skel, cover); + prefix.pop_sfx(suffix); } else if (loop < 2) { local_inc _(loop); + Node::arcs_t::const_iterator arc = node.arcs.begin(), end = node.arcs.end(); @@ -167,53 +187,49 @@ template static void cover( const size_t j = arc->first; prefix.push(j); - cover(skel, input, keys, prefix, size, j); + gencover(skel, cover, j); prefix.pop(); - const suffix_t *sfx = skel.suffixes[j]; - if (sfx != NULL && suffix == NULL) { - suffix = new suffix_t(*sfx); - suffix->push(j); + const suffix_t &sfx = cover.suffixes[j]; + if (sfx.init && !suffix.init) { + suffix = sfx; + suffix.push(j); } } } } -template static void generate_paths_cunit_key( - Skeleton &skel, FILE *input, FILE *keys) +template + static void generate_paths_cunit_key(const Skeleton &skel, cover_t &cover) { - path_t prefix(0); - covers_t size = covers_t::from32(0u); - - cover(skel, input, keys, prefix, size, 0); - - if (size.overflow()) { + gencover(skel, cover, 0); + if (cover.size.overflow()) { warning(NULL, skel.line, false, "DFA %sis too large: can only generate partial path cover", incond(skel.cond).c_str()); } } -template static void generate_paths_cunit( - Skeleton &skel, FILE *input, FILE *keys) +template + static void generate_paths_cunit(const Skeleton &skel, cover_t &cover) { switch (skel.sizeof_key) { - case 4: generate_paths_cunit_key(skel, input, keys); break; - case 2: generate_paths_cunit_key(skel, input, keys); break; - case 1: generate_paths_cunit_key(skel, input, keys); break; + case 4: generate_paths_cunit_key(skel, cover); break; + case 2: generate_paths_cunit_key(skel, cover); break; + case 1: generate_paths_cunit_key(skel, cover); break; } } -static void generate_paths(Skeleton &skel, FILE *input, FILE *keys) +static void generate_paths(const Skeleton &skel, cover_t &cover) { switch (opts->encoding.szCodeUnit()) { - case 4: generate_paths_cunit(skel, input, keys); break; - case 2: generate_paths_cunit(skel, input, keys); break; - case 1: generate_paths_cunit(skel, input, keys); break; + case 4: generate_paths_cunit(skel, cover); break; + case 2: generate_paths_cunit(skel, cover); break; + case 1: generate_paths_cunit(skel, cover); break; } } -void emit_data(Skeleton &skel, const char *fname) +void emit_data(const Skeleton &skel, const char *fname) { const std::string input_name = std::string(fname) + "." + skel.name + ".input"; FILE *input = fopen(input_name.c_str(), "wb"); @@ -228,7 +244,8 @@ void emit_data(Skeleton &skel, const char *fname) exit(1); } - generate_paths(skel, input, keys); + cover_t cover(input, keys, skel.nodes_count); + generate_paths(skel, cover); fclose(input); fclose(keys); diff --git a/re2c/src/ir/skeleton/path.h b/re2c/src/ir/skeleton/path.h index f5709c5e..6aa734a9 100644 --- a/re2c/src/ir/skeleton/path.h +++ b/re2c/src/ir/skeleton/path.h @@ -9,12 +9,16 @@ namespace re2c { -class suffix_t +struct suffix_t { + bool init; + +private: std::vector arcs; public: - suffix_t() : arcs() {} + + suffix_t(): init(false), arcs() {} void push(size_t i) { arcs.push_back(i); @@ -77,11 +81,11 @@ public: } const Node::arc_t& arc(const Skeleton &skel, size_t i) const { - return skel.nodes[arcs[i]].arcs[arcs[i + 1]]; + return skel.nodes[arcs[i]].arcs.find(arcs[i + 1])->second; } const Node::arcset_t& arcset(const Skeleton &skel, size_t i) const { - return skel.nodes[arcs[i]].arcsets[arcs[i + 1]]; + return skel.nodes[arcs[i]].arcsets.find(arcs[i + 1])->second; } void push(size_t n) { diff --git a/re2c/src/ir/skeleton/skeleton.cc b/re2c/src/ir/skeleton/skeleton.cc index 0664b108..ee6f2464 100644 --- a/re2c/src/ir/skeleton/skeleton.cc +++ b/re2c/src/ir/skeleton/skeleton.cc @@ -1,4 +1,3 @@ -#include #include #include "src/ir/dfa/dfa.h" @@ -64,14 +63,10 @@ Skeleton::Skeleton( line(dfa_line), nodes_count(dfa.states.size() + 1), // +1 for default state nodes(new Node[nodes_count]), - loops(new uint8_t[nodes_count]), - suffixes(new suffix_t*[nodes_count]), + loops(new uint8_t[nodes_count]()), sizeof_key(4), rules(rs) { - memset(loops, 0, sizeof(uint8_t) * nodes_count); - memset(suffixes, 0, sizeof(suffix_t*) * nodes_count); - const size_t nc = cs.size() - 1; // initialize skeleton nodes @@ -119,10 +114,6 @@ Skeleton::~Skeleton() { delete[] nodes; delete[] loops; - for (size_t i = 0; i < nodes_count; ++i) { - delete suffixes[i]; - } - delete[] suffixes; } uint32_t Skeleton::rule2key(rule_rank_t r) const diff --git a/re2c/src/ir/skeleton/skeleton.h b/re2c/src/ir/skeleton/skeleton.h index 856fd853..7b1ae6f6 100644 --- a/re2c/src/ir/skeleton/skeleton.h +++ b/re2c/src/ir/skeleton/skeleton.h @@ -21,7 +21,6 @@ namespace re2c struct dfa_t; struct OutputFile; struct path_t; -struct suffix_t; typedef local_increment_t local_inc; @@ -58,9 +57,6 @@ struct Skeleton // visit counters (for graph traversal) uint8_t *loops; - // paths to end node (for constructing path cover) - suffix_t **suffixes; - size_t sizeof_key; rules_t rules; @@ -90,7 +86,7 @@ uint32_t maxpath(Skeleton &skel); void warn_undefined_control_flow(Skeleton &skel); void fprint_default_path(FILE *f, const Skeleton &skel, const path_t &p); void warn_unreachable_nullable_rules(Skeleton &skel); -void emit_data(Skeleton &skel, const char *fname); +void emit_data(const Skeleton &skel, const char *fname); void emit_prolog(OutputFile & o); void emit_start(const Skeleton &skel, OutputFile &o, size_t maxfill, bool backup, bool backupctx, bool accept); -- 2.40.0