Search text (within context) for prog_.
| 286 | |
| 287 | // Search text (within context) for prog_. |
| 288 | bool BitState::Search(const StringPiece& text, const StringPiece& context, |
| 289 | bool anchored, bool longest, |
| 290 | StringPiece* submatch, int nsubmatch) { |
| 291 | // Search parameters. |
| 292 | text_ = text; |
| 293 | context_ = context; |
| 294 | if (context_.data() == NULL) |
| 295 | context_ = text; |
| 296 | if (prog_->anchor_start() && context_.begin() != text.begin()) |
| 297 | return false; |
| 298 | if (prog_->anchor_end() && context_.end() != text.end()) |
| 299 | return false; |
| 300 | anchored_ = anchored || prog_->anchor_start(); |
| 301 | longest_ = longest || prog_->anchor_end(); |
| 302 | endmatch_ = prog_->anchor_end(); |
| 303 | submatch_ = submatch; |
| 304 | nsubmatch_ = nsubmatch; |
| 305 | for (int i = 0; i < nsubmatch_; i++) |
| 306 | submatch_[i] = StringPiece(); |
| 307 | |
| 308 | // Allocate scratch space. |
| 309 | int nvisited = prog_->list_count() * static_cast<int>(text.size()+1); |
| 310 | nvisited = (nvisited + kVisitedBits-1) / kVisitedBits; |
| 311 | visited_ = PODArray<uint64_t>(nvisited); |
| 312 | memset(visited_.data(), 0, nvisited*sizeof visited_[0]); |
| 313 | |
| 314 | int ncap = 2*nsubmatch; |
| 315 | if (ncap < 2) |
| 316 | ncap = 2; |
| 317 | cap_ = PODArray<const char*>(ncap); |
| 318 | memset(cap_.data(), 0, ncap*sizeof cap_[0]); |
| 319 | |
| 320 | // When sizeof(Job) == 16, we start with a nice round 1KiB. :) |
| 321 | job_ = PODArray<Job>(64); |
| 322 | |
| 323 | // Anchored search must start at text.begin(). |
| 324 | if (anchored_) { |
| 325 | cap_[0] = text.data(); |
| 326 | return TrySearch(prog_->start(), text.data()); |
| 327 | } |
| 328 | |
| 329 | // Unanchored search, starting from each possible text position. |
| 330 | // Notice that we have to try the empty string at the end of |
| 331 | // the text, so the loop condition is p <= text.end(), not p < text.end(). |
| 332 | // This looks like it's quadratic in the size of the text, |
| 333 | // but we are not clearing visited_ between calls to TrySearch, |
| 334 | // so no work is duplicated and it ends up still being linear. |
| 335 | const char* etext = text.data() + text.size(); |
| 336 | for (const char* p = text.data(); p <= etext; p++) { |
| 337 | // Try to use prefix accel (e.g. memchr) to skip ahead. |
| 338 | if (p < etext && prog_->can_prefix_accel()) { |
| 339 | p = reinterpret_cast<const char*>(prog_->PrefixAccel(p, etext - p)); |
| 340 | if (p == NULL) |
| 341 | p = etext; |
| 342 | } |
| 343 | |
| 344 | cap_[0] = p; |
| 345 | if (TrySearch(prog_->start(), p)) // Match must be leftmost; done. |
no test coverage detected