commit 8f09fa6a86fc7e05da9c416cdcbd58d7b2c142e9
author Paul Wankadia <junyer@google.com> Sun May 17 10:11:43 2020 -0700
committer Paul Wankadia <junyer@google.com> Sun May 17 17:13:34 2020 +0000
tree b5ee50c0a3d920e9c445cd85ec340563108439a5
parent 92c1f0ea254c37bec393b5fcf71ab7f8c7f6af90

Tidy up the code for NFA threads a bit more.

Change-Id: I17c188a622ed46ddd9bfacd6070a89edd21d8d18
Reviewed-on: https://code-review.googlesource.com/c/re2/+/56550
Reviewed-by: Paul Wankadia <junyer@google.com>

re2/nfa.cc

diff --git a/re2/nfa.cc b/re2/nfa.cc
index 3959a78..6ef918f 100644
--- a/re2/nfa.cc
+++ b/re2/nfa.cc
@@ -27,6 +27,7 @@
 #include <stdio.h>
 #include <string.h>
 #include <algorithm>
+#include <deque>
 #include <string>
 #include <utility>
 #include <vector>
@@ -120,7 +121,8 @@
   const char* etext_;         // end of text (for endmatch_)
   Threadq q0_, q1_;           // pre-allocated for Search.
   PODArray<AddState> stack_;  // pre-allocated for AddToThreadq
-  Thread* free_threads_;      // free list
+  std::deque<Thread> arena_;  // thread arena
+  Thread* freelist_;          // thread freelist
   const char** match_;        // best match so far
   bool matched_;              // any match so far?
 
@@ -143,31 +145,30 @@
                prog_->inst_count(kInstEmptyWidth) +
                prog_->inst_count(kInstNop) + 1;  // + 1 for start inst
   stack_ = PODArray<AddState>(nstack);
-  free_threads_ = NULL;
+  freelist_ = NULL;
   match_ = NULL;
   matched_ = false;
 }
 
 NFA::~NFA() {
   delete[] match_;
-  Thread* next;
-  for (Thread* t = free_threads_; t; t = next) {
-    next = t->next;
-    delete[] t->capture;
-    delete t;
-  }
+  for (const Thread& t : arena_)
+    delete[] t.capture;
 }
 
 NFA::Thread* NFA::AllocThread() {
-  Thread* t = free_threads_;
-  if (t == NULL) {
-    t = new Thread;
+  Thread* t = freelist_;
+  if (t != NULL) {
+    freelist_ = t->next;
     t->ref = 1;
-    t->capture = new const char*[ncapture_];
+    // We don't need to touch t->capture because
+    // the caller will immediately overwrite it.
     return t;
   }
-  free_threads_ = t->next;
+  arena_.emplace_back();
+  t = &arena_.back();
   t->ref = 1;
+  t->capture = new const char*[ncapture_];
   return t;
 }
 
@@ -178,14 +179,13 @@
 }
 
 void NFA::Decref(Thread* t) {
-  if (t == NULL)
-    return;
+  DCHECK(t != NULL);
   t->ref--;
   if (t->ref > 0)
     return;
   DCHECK_EQ(t->ref, 0);
-  t->next = free_threads_;
-  free_threads_ = t;
+  t->next = freelist_;
+  freelist_ = t;
 }
 
 // Follows all empty arrows from id0 and enqueues all the states reached.
@@ -367,8 +367,10 @@
           matched_ = true;
 
           Decref(t);
-          for (++i; i != runq->end(); ++i)
-            Decref(i->value());
+          for (++i; i != runq->end(); ++i) {
+            if (i->value() != NULL)
+              Decref(i->value());
+          }
           runq->clear();
           if (ip->greedy(prog_))
             return ip->out1();
@@ -411,8 +413,10 @@
           // worse than the one we just found: don't run the
           // rest of the current Threadq.
           Decref(t);
-          for (++i; i != runq->end(); ++i)
-            Decref(i->value());
+          for (++i; i != runq->end(); ++i) {
+            if (i->value() != NULL)
+              Decref(i->value());
+          }
           runq->clear();
           return 0;
         }
@@ -484,6 +488,7 @@
   }
 
   match_ = new const char*[ncapture_];
+  memset(match_, 0, ncapture_*sizeof match_[0]);
   matched_ = false;
 
   // For debugging prints.
@@ -500,7 +505,6 @@
   Threadq* nextq = &q1_;
   runq->clear();
   nextq->clear();
-  memset(&match_[0], 0, ncapture_*sizeof match_[0]);
 
   // Loop over the text, stepping the machine.
   for (const char* p = text.data();; p++) {
@@ -607,8 +611,10 @@
     }
   }
 
-  for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i)
-    Decref(i->value());
+  for (Threadq::iterator i = runq->begin(); i != runq->end(); ++i) {
+    if (i->value() != NULL)
+      Decref(i->value());
+  }
 
   if (matched_) {
     for (int i = 0; i < nsubmatch; i++)