Use PODArray<> for stacks and also for nodebyid in Prog::IsOnePass().
Change-Id: I3eddd456b45130f79caa016424763c4fd2ce7e69
Reviewed-on: https://code-review.googlesource.com/c/36830
Reviewed-by: Paul Wankadia <junyer@google.com>
diff --git a/re2/dfa.cc b/re2/dfa.cc
index 9bc8499..89b9b77 100644
--- a/re2/dfa.cc
+++ b/re2/dfa.cc
@@ -39,6 +39,7 @@
#include "util/logging.h"
#include "util/mix.h"
#include "util/mutex.h"
+#include "util/pod_array.h"
#include "util/sparse_set.h"
#include "util/strutil.h"
#include "re2/prog.h"
@@ -347,8 +348,7 @@
// Scratch areas, protected by mutex_.
Workq* q0_; // Two pre-allocated work queues.
Workq* q1_;
- int* astack_; // Pre-allocated stack for AddToQueue
- int nastack_;
+ PODArray<int> stack_; // Pre-allocated stack for AddToQueue
// State* cache. Many threads use and add to the cache simultaneously,
// holding cache_mutex_ for reading and mutex_ (above) when adding.
@@ -441,7 +441,6 @@
init_failed_(false),
q0_(NULL),
q1_(NULL),
- astack_(NULL),
mem_budget_(max_mem) {
if (ExtraDebug)
fprintf(stderr, "\nkind %d\n%s\n", (int)kind_, prog_->DumpUnanchored().c_str());
@@ -449,16 +448,16 @@
if (kind_ == Prog::kLongestMatch)
nmark = prog_->size();
// See DFA::AddToQueue() for why this is so.
- nastack_ = prog_->inst_count(kInstCapture) +
- prog_->inst_count(kInstEmptyWidth) +
- prog_->inst_count(kInstNop) +
- nmark + 1; // + 1 for start inst
+ int nstack = prog_->inst_count(kInstCapture) +
+ prog_->inst_count(kInstEmptyWidth) +
+ prog_->inst_count(kInstNop) +
+ nmark + 1; // + 1 for start inst
- // Account for space needed for DFA, q0, q1, astack.
+ // Account for space needed for DFA, q0, q1, stack.
mem_budget_ -= sizeof(DFA);
mem_budget_ -= (prog_->size() + nmark) *
(sizeof(int)+sizeof(int)) * 2; // q0, q1
- mem_budget_ -= nastack_ * sizeof(int); // astack
+ mem_budget_ -= nstack * sizeof(int); // stack
if (mem_budget_ < 0) {
init_failed_ = true;
return;
@@ -482,13 +481,12 @@
q0_ = new Workq(prog_->size(), nmark);
q1_ = new Workq(prog_->size(), nmark);
- astack_ = new int[nastack_];
+ stack_ = PODArray<int>(nstack);
}
DFA::~DFA() {
delete q0_;
delete q1_;
- delete[] astack_;
ClearCache();
}
@@ -826,7 +824,7 @@
// Adds ip to the work queue, following empty arrows according to flag.
void DFA::AddToQueue(Workq* q, int id, uint32_t flag) {
- // Use astack_ to hold our stack of instructions yet to process.
+ // Use stack_ to hold our stack of instructions yet to process.
// It was preallocated as follows:
// one entry per Capture;
// one entry per EmptyWidth; and
@@ -835,12 +833,12 @@
// perform. (Each instruction can be processed at most once.)
// When using marks, we also added nmark == prog_->size().
// (Otherwise, nmark == 0.)
- int* stk = astack_;
+ int* stk = stack_.data();
int nstk = 0;
stk[nstk++] = id;
while (nstk > 0) {
- DCHECK_LE(nstk, nastack_);
+ DCHECK_LE(nstk, stack_.size());
id = stk[--nstk];
Loop:
diff --git a/re2/nfa.cc b/re2/nfa.cc
index b2d5c0a..66ab882 100644
--- a/re2/nfa.cc
+++ b/re2/nfa.cc
@@ -34,6 +34,7 @@
#include "re2/prog.h"
#include "re2/regexp.h"
#include "util/logging.h"
+#include "util/pod_array.h"
#include "util/sparse_array.h"
#include "util/sparse_set.h"
#include "util/strutil.h"
@@ -115,20 +116,18 @@
inline void CopyCapture(const char** dst, const char** src);
- Prog* prog_; // underlying program
- int start_; // start instruction in program
- int ncapture_; // number of submatches to track
- bool longest_; // whether searching for longest match
- bool endmatch_; // whether match must end at text.end()
- const char* btext_; // beginning of text being matched (for FormatSubmatch)
- const char* etext_; // end of text being matched (for endmatch_)
- Threadq q0_, q1_; // pre-allocated for Search.
- const char** match_; // best match so far
- bool matched_; // any match so far?
- AddState* astack_; // pre-allocated for AddToThreadq
- int nastack_;
-
- Thread* free_threads_; // free list
+ Prog* prog_; // underlying program
+ int start_; // start instruction in program
+ int ncapture_; // number of submatches to track
+ bool longest_; // whether searching for longest match
+ bool endmatch_; // whether match must end at text.end()
+ const char* btext_; // beginning of text being matched (for FormatSubmatch)
+ const char* etext_; // end of text being matched (for endmatch_)
+ Threadq q0_, q1_; // pre-allocated for Search.
+ PODArray<AddState> stack_; // pre-allocated for AddToThreadq
+ Thread* free_threads_; // free list
+ const char** match_; // best match so far
+ bool matched_; // any match so far?
NFA(const NFA&) = delete;
NFA& operator=(const NFA&) = delete;
@@ -145,18 +144,17 @@
q0_.resize(prog_->size());
q1_.resize(prog_->size());
// See NFA::AddToThreadq() for why this is so.
- nastack_ = 2*prog_->inst_count(kInstCapture) +
- prog_->inst_count(kInstEmptyWidth) +
- prog_->inst_count(kInstNop) + 1; // + 1 for start inst
- astack_ = new AddState[nastack_];
+ int nstack = 2*prog_->inst_count(kInstCapture) +
+ prog_->inst_count(kInstEmptyWidth) +
+ prog_->inst_count(kInstNop) + 1; // + 1 for start inst
+ stack_ = PODArray<AddState>(nstack);
+ free_threads_ = NULL;
match_ = NULL;
matched_ = false;
- free_threads_ = NULL;
}
NFA::~NFA() {
delete[] match_;
- delete[] astack_;
Thread* next;
for (Thread* t = free_threads_; t; t = next) {
next = t->next;
@@ -211,19 +209,19 @@
if (id0 == 0)
return;
- // Use astack_ to hold our stack of instructions yet to process.
+ // Use stack_ to hold our stack of instructions yet to process.
// It was preallocated as follows:
// two entries per Capture;
// one entry per EmptyWidth; and
// one entry per Nop.
// This reflects the maximum number of stack pushes that each can
// perform. (Each instruction can be processed at most once.)
- AddState* stk = astack_;
+ AddState* stk = stack_.data();
int nstk = 0;
stk[nstk++] = AddState(id0);
while (nstk > 0) {
- DCHECK_LE(nstk, nastack_);
+ DCHECK_LE(nstk, stack_.size());
AddState a = stk[--nstk];
Loop:
diff --git a/re2/onepass.cc b/re2/onepass.cc
index 10dc642..7d39290 100644
--- a/re2/onepass.cc
+++ b/re2/onepass.cc
@@ -59,6 +59,7 @@
#include "util/util.h"
#include "util/logging.h"
+#include "util/pod_array.h"
#include "util/sparse_set.h"
#include "util/strutil.h"
#include "util/utf.h"
@@ -403,11 +404,11 @@
int stacksize = inst_count(kInstCapture) +
inst_count(kInstEmptyWidth) +
inst_count(kInstNop) + 1; // + 1 for start inst
- InstCond* stack = new InstCond[stacksize];
+ PODArray<InstCond> stack(stacksize);
int size = this->size();
- int* nodebyid = new int[size]; // indexed by ip
- memset(nodebyid, 0xFF, size*sizeof nodebyid[0]);
+ PODArray<int> nodebyid(size); // indexed by ip
+ memset(nodebyid.data(), 0xFF, size*sizeof nodebyid[0]);
// Originally, nodes was a uint8_t[maxnodes*statesize], but that was
// unnecessarily optimistic: why allocate a large amount of memory
@@ -613,14 +614,9 @@
dfa_mem_ -= nalloc*statesize;
onepass_nodes_ = new uint8_t[nalloc*statesize];
memmove(onepass_nodes_, nodes.data(), nalloc*statesize);
-
- delete[] stack;
- delete[] nodebyid;
return true;
fail:
- delete[] stack;
- delete[] nodebyid;
return false;
}
