From 56f1e9974b7889d26f1ec53a8879e9191e121ec9 Mon Sep 17 00:00:00 2001
From: Ulya Trofimovich <skvadrik@gmail.com>
Date: Wed, 11 Mar 2015 15:46:52 +0000
Subject: [PATCH] Moved bitmap statistics counting inside of 'Go' class.
---
re2c/Makefile.am | 4 +-
re2c/code.cc | 70 +----------------------------------
re2c/code.h | 4 +-
re2c/dfa.cc | 11 ------
re2c/dfa.h | 51 +------------------------
re2c/go.cc | 96 ++++++++++++++++++++++++++++++++++++++++++++++++
re2c/go.h | 40 ++++++++++++++++++++
7 files changed, 145 insertions(+), 131 deletions(-)
create mode 100644 re2c/go.cc
create mode 100644 re2c/go.h
diff --git a/re2c/Makefile.am b/re2c/Makefile.am
index 03ce4ed0..b7ade844 100755
--- a/re2c/Makefile.am
+++ b/re2c/Makefile.am
@@ -2,10 +2,10 @@
bin_PROGRAMS = re2c
win_BINARIES = $(WINBUILDDIR)/re2c.exe
-re2c_SOURCES = cases.cc code.cc dfa.cc main.cc parser.cc actions.cc scanner.re substr.cc range.cc \
+re2c_SOURCES = cases.cc code.cc dfa.cc go.cc main.cc parser.cc actions.cc scanner.re substr.cc range.cc \
translate.cc scanner.cc mbo_getopt.cc print.cc input.cc input_api.cc output.cc \
enc.cc utf8.cc utf8_range.cc utf8_regexp.cc utf16.cc utf16_range.cc utf16_regexp.cc range_suffix.cc \
- basics.h cases.h code.h code_names.h dfa.h enc.h indent.h input.h input_api.h free_list.h globals.h ins.h \
+ basics.h cases.h code.h code_names.h dfa.h go.h enc.h indent.h input.h input_api.h free_list.h globals.h ins.h \
mbo_getopt.h parser.h print.h range.h range_suffix.h re.h \
scanner.h smart_ptr.h substr.h token.h output.h \
utf16.h utf16_range.h utf16_regexp.h utf8.h utf8_range.h utf8_regexp.h
diff --git a/re2c/code.cc b/re2c/code.cc
index 31191830..9f4df188 100644
--- a/re2c/code.cc
+++ b/re2c/code.cc
@@ -13,6 +13,7 @@
#include "cases.h"
#include "code.h"
#include "globals.h"
+#include "go.h"
#include "dfa.h"
#include "indent.h"
#include "input_api.h"
@@ -156,46 +157,6 @@ static void doGen(const Go *g, const State *s, uint *bm, uint f, uint m)
}
}
-// All spans in g1 that lead to s1 are pairwise equal to that in g2 leading to s2
-static bool matches(const Go *g1, const State *s1, const Go *g2, const State *s2)
-{
- Span *b1 = g1->span, *e1 = &b1[g1->nSpans];
- uint lb1 = 0;
- Span *b2 = g2->span, *e2 = &b2[g2->nSpans];
- uint lb2 = 0;
-
- for (;;)
- {
- for (; b1 < e1 && b1->to != s1; ++b1)
- {
- lb1 = b1->ub;
- }
-
- for (; b2 < e2 && b2->to != s2; ++b2)
- {
- lb2 = b2->ub;
- }
-
- if (b1 == e1)
- {
- return b2 == e2;
- }
-
- if (b2 == e2)
- {
- return false;
- }
-
- if (lb1 != lb2 || b1->ub != b2->ub)
- {
- return false;
- }
-
- ++b1;
- ++b2;
- }
-}
-
BitMap *BitMap::first = NULL;
BitMap::BitMap(const Go *g, const State *x)
@@ -974,34 +935,7 @@ static void genGoto (OutputFile & o, uint ind, const Go & go, const State *from,
return;
}
- uint dSpans = 0;
- uint nBitmaps = 0;
- for (uint i = 0; i < go.nSpans; ++i)
- {
- State *to = go.span[i].to;
-
- if (to && to->isBase)
- {
- const BitMap *b = BitMap::find(to);
-
- if (b && matches(b->go, b->on, &go, to))
- {
- go.bitmaps[i] = b;
- nBitmaps++;
- }
- else
- {
- go.bitmaps[i] = NULL;
- dSpans++;
- }
- }
- else
- {
- go.bitmaps[i] = NULL;
- dSpans++;
- }
- }
-
+ const uint dSpans = go.nSpans - go.hSpans - go.nBitmaps;
if (gFlag && (dSpans >= cGotoThreshold))
{
genCpGoto(o, ind, from, next, readCh, go.span, go.nSpans, go.hspan, go.hSpans);
diff --git a/re2c/code.h b/re2c/code.h
index 1227fb22..d1687075 100755
--- a/re2c/code.h
+++ b/re2c/code.h
@@ -3,11 +3,13 @@
#define _code_h
#include "re.h"
-#include "dfa.h"
namespace re2c
{
+struct Go;
+class State;
+
class BitMap
{
public:
diff --git a/re2c/dfa.cc b/re2c/dfa.cc
index 619aa00f..d9abf63b 100644
--- a/re2c/dfa.cc
+++ b/re2c/dfa.cc
@@ -9,17 +9,6 @@
namespace re2c
{
-uint Span::show(std::ostream &o, uint lb) const
-{
- if (to)
- {
- printSpan(o, lb, ub);
- o << " " << to->label << "; ";
- }
-
- return ub;
-}
-
std::ostream& operator<<(std::ostream &o, const State &s)
{
o << "state " << s.label;
diff --git a/re2c/dfa.h b/re2c/dfa.h
index d840e142..a415ebd9 100644
--- a/re2c/dfa.h
+++ b/re2c/dfa.h
@@ -4,6 +4,8 @@
#include <iosfwd>
#include <map>
+
+#include "go.h"
#include "re.h"
namespace re2c
@@ -152,55 +154,6 @@ private:
#endif
};
-class Span
-{
-
-public:
- uint ub;
- State *to;
-
-public:
- uint show(std::ostream&, uint) const;
-};
-
-class BitMap;
-
-struct Go
-{
- uint nSpans; // number of spans
- uint hSpans; // number of spans with upper bound > 0x100
- Span * span;
- Span * hspan;
- const BitMap ** bitmaps;
-
- Go ()
- : nSpans (0)
- , hSpans (0)
- , span (NULL)
- , hspan (NULL)
- , bitmaps (NULL)
- {}
-
- ~Go ()
- {
- delete [] bitmaps;
- }
-
- void init ()
- {
- for (uint i = 0; i < nSpans; ++i)
- {
- if (span[i].ub > 0x100)
- {
- hspan = &span[i];
- hSpans = nSpans - i;
- break;
- }
- }
- bitmaps = new const BitMap * [nSpans];
- }
-};
-
class State
{
diff --git a/re2c/go.cc b/re2c/go.cc
new file mode 100644
index 00000000..88d3c493
--- /dev/null
+++ b/re2c/go.cc
@@ -0,0 +1,96 @@
+#include "dfa.h"
+#include "go.h"
+#include "print.h"
+
+namespace re2c
+{
+
+uint Span::show (std::ostream & o, uint lb) const
+{
+ if (to)
+ {
+ printSpan(o, lb, ub);
+ o << " " << to->label << "; ";
+ }
+ return ub;
+}
+
+Go::Go ()
+ : nSpans (0)
+ , hSpans (0)
+ , span (NULL)
+ , hspan (NULL)
+ , nBitmaps (0)
+ , bitmaps (NULL)
+{}
+
+Go::~Go ()
+{
+ delete [] bitmaps;
+}
+
+void Go::init ()
+{
+ // initialize high (wide) spans
+ for (uint i = 0; i < nSpans; ++i)
+ {
+ if (span[i].ub > 0x100)
+ {
+ hspan = &span[i];
+ hSpans = nSpans - i;
+ break;
+ }
+ }
+ // initialize bitmaps
+ bitmaps = new const BitMap * [nSpans];
+ memset (bitmaps, 0, nSpans * sizeof (BitMap *));
+ for (uint i = 0; i < nSpans; ++i)
+ {
+ if (span[i].to && span[i].to->isBase)
+ {
+ const BitMap *b = BitMap::find (span[i].to);
+ if (b && matches(b->go, b->on, this, span[i].to))
+ {
+ bitmaps[i] = b;
+ nBitmaps++;
+ }
+ }
+ }
+}
+
+// All spans in g1 that lead to s1 are pairwise equal to that in g2 leading to s2
+bool matches(const Go * g1, const State * s1, const Go * g2, const State * s2)
+{
+ Span *b1 = g1->span, *e1 = &b1[g1->nSpans];
+ uint lb1 = 0;
+ Span *b2 = g2->span, *e2 = &b2[g2->nSpans];
+ uint lb2 = 0;
+
+ for (;;)
+ {
+ for (; b1 < e1 && b1->to != s1; ++b1)
+ {
+ lb1 = b1->ub;
+ }
+ for (; b2 < e2 && b2->to != s2; ++b2)
+ {
+ lb2 = b2->ub;
+ }
+ if (b1 == e1)
+ {
+ return b2 == e2;
+ }
+ if (b2 == e2)
+ {
+ return false;
+ }
+ if (lb1 != lb2 || b1->ub != b2->ub)
+ {
+ return false;
+ }
+ ++b1;
+ ++b2;
+ }
+}
+
+} // namespace re2c
diff --git a/re2c/go.h b/re2c/go.h
new file mode 100644
index 00000000..9a3603ba
--- /dev/null
+++ b/re2c/go.h
@@ -0,0 +1,40 @@
+#ifndef _go_h
+#define _go_h
+
+#include <iostream>
+
+#include "basics.h"
+#include "code.h"
+
+namespace re2c
+{
+
+class State;
+
+struct Span
+{
+ uint ub;
+ State * to;
+
+ uint show(std::ostream&, uint) const;
+};
+
+struct Go
+{
+ uint nSpans; // number of spans
+ uint hSpans; // number of spans with upper bound > 0x100
+ Span * span;
+ Span * hspan;
+ uint nBitmaps;
+ const BitMap ** bitmaps;
+
+ Go ();
+ ~Go ();
+ void init ();
+};
+
+bool matches(const Go * g1, const State * s1, const Go * g2, const State * s2);
+
+} // namespace re2c
+
+#endif // _go_h
--
2.40.0