GCC Code Coverage Report
Directory: ../ Exec Total Coverage
File: /home/iojs/build/workspace/node-test-commit-linux-coverage/nodes/benchmark/out/../src/string_search.h Lines: 246 255 96.5 %
Date: 2017-11-19 Branches: 162 270 60.0 %

Line Branch Exec Source
1
// Copyright 2011 the V8 project authors. All rights reserved.
2
// Use of this source code is governed by a BSD-style license that can be
3
// found in the LICENSE file.
4
5
#ifndef SRC_STRING_SEARCH_H_
6
#define SRC_STRING_SEARCH_H_
7
8
#if defined(NODE_WANT_INTERNALS) && NODE_WANT_INTERNALS
9
10
#include "node_internals.h"
11
#include <string.h>
12
13
namespace node {
14
namespace stringsearch {
15
16
17
// Returns the maximum of the two parameters.
18
template <typename T>
19
143
T Max(T a, T b) {
20
143
  return a < b ? b : a;
21
}
22
23
24
static const uint32_t kMaxOneByteCharCodeU = 0xff;
25
26
template <typename T>
27
class Vector {
28
 public:
29
215294
  Vector(T* data, size_t length, bool isForward)
30
215294
      : start_(data), length_(length), is_forward_(isForward) {
31



215294
    CHECK(length > 0 && data != nullptr);
32
215294
  }
33
34
  // Returns the start of the memory range.
35
  // For vector v this is NOT necessarily &v[0], see forward().
36
3434447
  const T* start() const { return start_; }
37
38
  // Returns the length of the vector, in characters.
39
7453544
  size_t length() const { return length_; }
40
41
  // Returns true if the Vector is front-to-back, false if back-to-front.
42
  // In the latter case, v[0] corresponds to the *end* of the memory range.
43
3434447
  size_t forward() const { return is_forward_; }
44
45
  // Access individual vector elements - checks bounds in debug mode.
46
45977628
  T& operator[](size_t index) const {
47
#ifdef DEBUG
48
    CHECK(index < length_);
49
#endif
50

45977628
    return start_[is_forward_ ? index : (length_ - index - 1)];
51
  }
52
53
 private:
54
  T* start_;
55
  size_t length_;
56
  bool is_forward_;
57
};
58
59
60
//---------------------------------------------------------------------
61
// String Search object.
62
//---------------------------------------------------------------------
63
64
// Class holding constants and methods that apply to all string search variants,
65
// independently of subject and pattern char size.
66
107647
class StringSearchBase {
67
 protected:
68
  // Cap on the maximal shift in the Boyer-Moore implementation. By setting a
69
  // limit, we can fix the size of tables. For a needle longer than this limit,
70
  // search will not be optimal, since we only build tables for a suffix
71
  // of the string, but it is a safe approximation.
72
  static const int kBMMaxShift = 250;
73
74
  // Reduce alphabet to this size.
75
  // One of the tables used by Boyer-Moore and Boyer-Moore-Horspool has size
76
  // proportional to the input alphabet. We reduce the alphabet size by
77
  // equating input characters modulo a smaller alphabet size. This gives
78
  // a potentially less efficient searching, but is a safe approximation.
79
  // For needles using only characters in the same Unicode 256-code point page,
80
  // there is no search speed degradation.
81
  static const int kLatin1AlphabetSize = 256;
82
  static const int kUC16AlphabetSize = 256;
83
84
  // Bad-char shift table stored in the state. It's length is the alphabet size.
85
  // For patterns below this length, the skip length of Boyer-Moore is too short
86
  // to compensate for the algorithmic overhead compared to simple brute force.
87
  static const int kBMMinPatternLength = 8;
88
89
  // Store for the BoyerMoore(Horspool) bad char shift table.
90
  static int kBadCharShiftTable[kUC16AlphabetSize];
91
  // Store for the BoyerMoore good suffix shift table.
92
  static int kGoodSuffixShiftTable[kBMMaxShift + 1];
93
  // Table used temporarily while building the BoyerMoore good suffix
94
  // shift table.
95
  static int kSuffixTable[kBMMaxShift + 1];
96
};
97
98
template <typename Char>
99
class StringSearch : private StringSearchBase {
100
 public:
101
107647
  explicit StringSearch(Vector<const Char> pattern)
102
107647
      : pattern_(pattern), start_(0) {
103

107647
    if (pattern.length() >= kBMMaxShift) {
104
11
      start_ = pattern.length() - kBMMaxShift;
105
    }
106
107
107647
    size_t pattern_length = pattern_.length();
108

107647
    CHECK_GT(pattern_length, 0);
109

107647
    if (pattern_length < kBMMinPatternLength) {
110

106972
      if (pattern_length == 1) {
111
100191
        strategy_ = &SingleCharSearch;
112
100191
        return;
113
      }
114
6781
      strategy_ = &LinearSearch;
115
6781
      return;
116
    }
117
675
    strategy_ = &InitialSearch;
118
  }
119
120
107647
  size_t Search(Vector<const Char> subject, size_t index) {
121
107647
    return strategy_(this, subject, index);
122
  }
123
124
27
  static inline int AlphabetSize() {
125
    if (sizeof(Char) == 1) {
126
      // Latin1 needle.
127
27
      return kLatin1AlphabetSize;
128
    } else {
129
      // UC16 needle.
130
      return kUC16AlphabetSize;
131
    }
132
133
    static_assert(sizeof(Char) == sizeof(uint8_t) ||
134
                  sizeof(Char) == sizeof(uint16_t),
135
                  "sizeof(Char) == sizeof(uint16_t) || sizeof(uint8_t)");
136
  }
137
138
 private:
139
  typedef size_t (*SearchFunction)(
140
      StringSearch<Char>*,
141
      Vector<const Char>,
142
      size_t);
143
144
  static size_t SingleCharSearch(StringSearch<Char>* search,
145
                                 Vector<const Char> subject,
146
                                 size_t start_index);
147
148
  static size_t LinearSearch(StringSearch<Char>* search,
149
                             Vector<const Char> subject,
150
                             size_t start_index);
151
152
  static size_t InitialSearch(StringSearch<Char>* search,
153
                              Vector<const Char> subject,
154
                              size_t start_index);
155
156
  static size_t BoyerMooreHorspoolSearch(
157
      StringSearch<Char>* search,
158
      Vector<const Char> subject,
159
      size_t start_index);
160
161
  static size_t BoyerMooreSearch(StringSearch<Char>* search,
162
                                 Vector<const Char> subject,
163
                                 size_t start_index);
164
165
  void PopulateBoyerMooreHorspoolTable();
166
167
  void PopulateBoyerMooreTable();
168
169
63983
  static inline int CharOccurrence(int* bad_char_occurrence,
170
                                   Char char_code) {
171
    if (sizeof(Char) == 1) {
172
63983
      return bad_char_occurrence[static_cast<int>(char_code)];
173
    }
174
    // Both pattern and subject are UC16. Reduce character to equivalence class.
175
    int equiv_class = char_code % kUC16AlphabetSize;
176
    return bad_char_occurrence[equiv_class];
177
  }
178
179
  // Store for the BoyerMoore(Horspool) bad char shift table.
180
  // Return a table covering the last kBMMaxShift+1 positions of
181
  // pattern.
182
57
  int* bad_char_table() { return kBadCharShiftTable; }
183
184
  // Store for the BoyerMoore good suffix shift table.
185
6
  int* good_suffix_shift_table() {
186
    // Return biased pointer that maps the range  [start_..pattern_.length()
187
    // to the kGoodSuffixShiftTable array.
188
6
    return kGoodSuffixShiftTable - start_;
189
  }
190
191
  // Table used temporarily while building the BoyerMoore good suffix
192
  // shift table.
193
3
  int* suffix_table() {
194
    // Return biased pointer that maps the range  [start_..pattern_.length()
195
    // to the kSuffixTable array.
196
3
    return kSuffixTable - start_;
197
  }
198
199
  // The pattern to search for.
200
  Vector<const Char> pattern_;
201
  // Pointer to implementation of the search.
202
  SearchFunction strategy_;
203
  // Cache value of Max(0, pattern_length() - kBMMaxShift)
204
  size_t start_;
205
};
206
207
208
template <typename T, typename U>
209
6960
inline T AlignDown(T value, U alignment) {
210
  return reinterpret_cast<T>(
211
6960
      (reinterpret_cast<uintptr_t>(value) & ~(alignment - 1)));
212
}
213
214
215
143
inline uint8_t GetHighestValueByte(uint16_t character) {
216
  return Max(static_cast<uint8_t>(character & 0xFF),
217
143
             static_cast<uint8_t>(character >> 8));
218
}
219
220
221
inline uint8_t GetHighestValueByte(uint8_t character) { return character; }
222
223
224
// Searches for a byte value in a memory buffer, back to front.
225
// Uses memrchr(3) on systems which support it, for speed.
226
// Falls back to a vanilla for loop on non-GNU systems such as Windows.
227
366239
inline const void* MemrchrFill(const void* haystack, uint8_t needle,
228
                               size_t haystack_len) {
229
#ifdef _GNU_SOURCE
230
366239
  return memrchr(haystack, needle, haystack_len);
231
#else
232
  const uint8_t* haystack8 = static_cast<const uint8_t*>(haystack);
233
  for (size_t i = haystack_len - 1; i != static_cast<size_t>(-1); i--) {
234
    if (haystack8[i] == needle) {
235
      return haystack8 + i;
236
    }
237
  }
238
  return nullptr;
239
#endif
240
}
241
242
243
// Finds the first occurrence of *two-byte* character pattern[0] in the string
244
// `subject`. Does not check that the whole pattern matches.
245
template <typename Char>
246
143
inline size_t FindFirstCharacter(Vector<const Char> pattern,
247
                                 Vector<const Char> subject, size_t index) {
248
143
  const Char pattern_first_char = pattern[0];
249
143
  const size_t max_n = (subject.length() - pattern.length() + 1);
250
251
  // For speed, search for the more `rare` of the two bytes in pattern[0]
252
  // using memchr / memrchr (which are much faster than a simple for loop).
253
143
  const uint8_t search_byte = GetHighestValueByte(pattern_first_char);
254
143
  size_t pos = index;
255
6828
  do {
256
6971
    const size_t bytes_to_search = (max_n - pos) * sizeof(Char);
257
    const void* void_pos;
258
6971
    if (subject.forward()) {
259
      // Assert that bytes_to_search won't overflow
260
6970
      CHECK_LE(pos, max_n);
261
6970
      CHECK_LE(max_n - pos, SIZE_MAX / sizeof(Char));
262
6970
      void_pos = memchr(subject.start() + pos, search_byte, bytes_to_search);
263
    } else {
264
1
      CHECK_LE(pos, subject.length());
265
1
      CHECK_LE(subject.length() - pos, SIZE_MAX / sizeof(Char));
266
1
      void_pos = MemrchrFill(subject.start() + pattern.length() - 1,
267
                             search_byte,
268
1
                             bytes_to_search);
269
    }
270
6971
    const Char* char_pos = static_cast<const Char*>(void_pos);
271
6971
    if (char_pos == nullptr)
272
11
      return subject.length();
273
274
    // Then, for each match, verify that the full two bytes match pattern[0].
275
6960
    char_pos = AlignDown(char_pos, sizeof(Char));
276
6960
    size_t raw_pos = static_cast<size_t>(char_pos - subject.start());
277
6960
    pos = subject.forward() ? raw_pos : (subject.length() - raw_pos - 1);
278
6960
    if (subject[pos] == pattern_first_char) {
279
      // Match found, hooray.
280
132
      return pos;
281
    }
282
    // Search byte matched, but the other byte of pattern[0] didn't. Keep going.
283
  } while (++pos < max_n);
284
285
  return subject.length();
286
}
287
288
289
// Finds the first occurrence of the byte pattern[0] in string `subject`.
290
// Does not verify that the whole pattern matches.
291
template <>
292
1711720
inline size_t FindFirstCharacter(Vector<const uint8_t> pattern,
293
                                 Vector<const uint8_t> subject,
294
                                 size_t index) {
295
1711720
  const uint8_t pattern_first_char = pattern[0];
296
1711720
  const size_t subj_len = subject.length();
297
1711720
  const size_t max_n = (subject.length() - pattern.length() + 1);
298
299
  const void* pos;
300
1711720
  if (subject.forward()) {
301
1345490
    pos = memchr(subject.start() + index, pattern_first_char, max_n - index);
302
  } else {
303
366230
    pos = MemrchrFill(subject.start() + pattern.length() - 1,
304
                      pattern_first_char,
305
732460
                      max_n - index);
306
  }
307
1711720
  const uint8_t* char_pos = static_cast<const uint8_t*>(pos);
308
1711720
  if (char_pos == nullptr) {
309
2924
    return subj_len;
310
  }
311
312
1708796
  size_t raw_pos = static_cast<size_t>(char_pos - subject.start());
313
1708796
  return subject.forward() ? raw_pos : (subj_len - raw_pos - 1);
314
}
315
316
//---------------------------------------------------------------------
317
// Single Character Pattern Search Strategy
318
//---------------------------------------------------------------------
319
320
template <typename Char>
321
100191
size_t StringSearch<Char>::SingleCharSearch(
322
    StringSearch<Char>* search,
323
    Vector<const Char> subject,
324
    size_t index) {
325

100191
  CHECK_EQ(1, search->pattern_.length());
326
100191
  return FindFirstCharacter(search->pattern_, subject, index);
327
}
328
329
//---------------------------------------------------------------------
330
// Linear Search Strategy
331
//---------------------------------------------------------------------
332
333
// Simple linear search for short patterns. Never bails out.
334
template <typename Char>
335
6781
size_t StringSearch<Char>::LinearSearch(
336
    StringSearch<Char>* search,
337
    Vector<const Char> subject,
338
    size_t index) {
339
6781
  Vector<const Char> pattern = search->pattern_;
340

6781
  CHECK_GT(pattern.length(), 1);
341
6781
  const size_t pattern_length = pattern.length();
342
6781
  const size_t n = subject.length() - pattern_length;
343

1237968
  for (size_t i = index; i <= n; i++) {
344
1237965
    i = FindFirstCharacter(pattern, subject, i);
345

1237965
    if (i == subject.length())
346
2897
      return subject.length();
347

1235068
    CHECK_LE(i, n);
348
349
1235068
    bool matches = true;
350

1293221
    for (size_t j = 1; j < pattern_length; j++) {
351

1289340
      if (pattern[j] != subject[i + j]) {
352
1231187
        matches = false;
353
1231187
        break;
354
      }
355
    }
356

1235068
    if (matches) {
357
3881
      return i;
358
    }
359
  }
360
3
  return subject.length();
361
}
362
363
//---------------------------------------------------------------------
364
// Boyer-Moore string search
365
//---------------------------------------------------------------------
366
367
template <typename Char>
368
3
size_t StringSearch<Char>::BoyerMooreSearch(
369
    StringSearch<Char>* search,
370
    Vector<const Char> subject,
371
    size_t start_index) {
372
3
  Vector<const Char> pattern = search->pattern_;
373
3
  const size_t subject_length = subject.length();
374
3
  const size_t pattern_length = pattern.length();
375
  // Only preprocess at most kBMMaxShift last characters of pattern.
376
3
  size_t start = search->start_;
377
378
3
  int* bad_char_occurrence = search->bad_char_table();
379
3
  int* good_suffix_shift = search->good_suffix_shift_table();
380
381
3
  Char last_char = pattern[pattern_length - 1];
382
3
  size_t index = start_index;
383
  // Continue search from i.
384

14366
  while (index <= subject_length - pattern_length) {
385
14363
    size_t j = pattern_length - 1;
386
    int c;
387

31794
    while (last_char != (c = subject[index + j])) {
388
3068
      int shift = j - CharOccurrence(bad_char_occurrence, c);
389
3068
      index += shift;
390

3068
      if (index > subject_length - pattern_length) {
391
        return subject.length();
392
      }
393
    }
394

7549468
    while (pattern[j] == (c = subject[index + j])) {
395

7520745
      if (j == 0) {
396
3
        return index;
397
      }
398
7520742
      j--;
399
    }
400

14360
    if (j < start) {
401
      // we have matched more than our tables allow us to be smart about.
402
      // Fall back on BMH shift.
403
2324
      index += pattern_length - 1 -
404
               CharOccurrence(bad_char_occurrence,
405
2324
                              static_cast<Char>(last_char));
406
    } else {
407
12036
      int gs_shift = good_suffix_shift[j + 1];
408
12036
      int bc_occ = CharOccurrence(bad_char_occurrence, c);
409
12036
      int shift = j - bc_occ;
410

12036
      if (gs_shift > shift) {
411
12036
        shift = gs_shift;
412
      }
413
12036
      index += shift;
414
    }
415
  }
416
417
  return subject.length();
418
}
419
420
template <typename Char>
421
3
void StringSearch<Char>::PopulateBoyerMooreTable() {
422
3
  const size_t pattern_length = pattern_.length();
423
3
  Vector<const Char> pattern = pattern_;
424
  // Only look at the last kBMMaxShift characters of pattern (from start_
425
  // to pattern_length).
426
3
  const size_t start = start_;
427
3
  const size_t length = pattern_length - start;
428
429
  // Biased tables so that we can use pattern indices as table indices,
430
  // even if we only cover the part of the pattern from offset start.
431
3
  int* shift_table = good_suffix_shift_table();
432
3
  int* suffix_table = this->suffix_table();
433
434
  // Initialize table.
435

753
  for (size_t i = start; i < pattern_length; i++) {
436
750
    shift_table[i] = length;
437
  }
438
3
  shift_table[pattern_length] = 1;
439
3
  suffix_table[pattern_length] = pattern_length + 1;
440
441

3
  if (pattern_length <= start) {
442
3
    return;
443
  }
444
445
  // Find suffixes.
446
3
  Char last_char = pattern_[pattern_length - 1];
447
3
  size_t suffix = pattern_length + 1;
448
  {
449
3
    size_t i = pattern_length;
450

711
    while (i > start) {
451
705
      Char c = pattern[i - 1];
452



1449
      while (suffix <= pattern_length && c != pattern[suffix - 1]) {
453

39
        if (static_cast<size_t>(shift_table[suffix]) == length) {
454
14
          shift_table[suffix] = suffix - i;
455
        }
456
39
        suffix = suffix_table[suffix];
457
      }
458
705
      suffix_table[--i] = --suffix;
459

705
      if (suffix == pattern_length) {
460
        // No suffix to extend, so we check against last_char only.
461



48
        while ((i > start) && (pattern[i - 1] != last_char)) {
462

42
          if (static_cast<size_t>(shift_table[pattern_length]) == length) {
463
            shift_table[pattern_length] = pattern_length - i;
464
          }
465
42
          suffix_table[--i] = pattern_length;
466
        }
467

3
        if (i > start) {
468
3
          suffix_table[--i] = --suffix;
469
        }
470
      }
471
    }
472
  }
473
  // Build shift table using suffixes.
474

3
  if (suffix < pattern_length) {
475

756
    for (size_t i = start; i <= pattern_length; i++) {
476

753
      if (static_cast<size_t>(shift_table[i]) == length) {
477
736
        shift_table[i] = suffix - start;
478
      }
479

753
      if (i == suffix) {
480
8
        suffix = suffix_table[suffix];
481
      }
482
    }
483
  }
484
}
485
486
//---------------------------------------------------------------------
487
// Boyer-Moore-Horspool string search.
488
//---------------------------------------------------------------------
489
490
template <typename Char>
491
27
size_t StringSearch<Char>::BoyerMooreHorspoolSearch(
492
    StringSearch<Char>* search,
493
    Vector<const Char> subject,
494
    size_t start_index) {
495
27
  Vector<const Char> pattern = search->pattern_;
496
27
  const size_t subject_length = subject.length();
497
27
  const size_t pattern_length = pattern.length();
498
27
  int* char_occurrences = search->bad_char_table();
499
27
  int64_t badness = -pattern_length;
500
501
  // How bad we are doing without a good-suffix table.
502
27
  Char last_char = pattern[pattern_length - 1];
503
  int last_char_shift =
504
      pattern_length - 1 -
505
27
      CharOccurrence(char_occurrences, static_cast<Char>(last_char));
506
507
  // Perform search
508
27
  size_t index = start_index;  // No matches found prior to this index.
509

31504
  while (index <= subject_length - pattern_length) {
510
31477
    size_t j = pattern_length - 1;
511
    int subject_char;
512

109480
    while (last_char != (subject_char = subject[index + j])) {
513
46528
      int bc_occ = CharOccurrence(char_occurrences, subject_char);
514
46528
      int shift = j - bc_occ;
515
46528
      index += shift;
516
46528
      badness += 1 - shift;  // at most zero, so badness cannot increase.
517

46528
      if (index > subject_length - pattern_length) {
518
2
        return subject_length;
519
      }
520
    }
521
31475
    j--;
522

2754114
    while (pattern[j] == (subject[index + j])) {
523

2691186
      if (j == 0) {
524
22
        return index;
525
      }
526
2691164
      j--;
527
    }
528
31453
    index += last_char_shift;
529
    // Badness increases by the number of characters we have
530
    // checked, and decreases by the number of characters we
531
    // can skip by shifting. It's a measure of how we are doing
532
    // compared to reading each character exactly once.
533
31453
    badness += (pattern_length - j) - last_char_shift;
534

31453
    if (badness > 0) {
535
3
      search->PopulateBoyerMooreTable();
536
3
      search->strategy_ = &BoyerMooreSearch;
537
3
      return BoyerMooreSearch(search, subject, index);
538
    }
539
  }
540
  return subject.length();
541
}
542
543
template <typename Char>
544
27
void StringSearch<Char>::PopulateBoyerMooreHorspoolTable() {
545
27
  const size_t pattern_length = pattern_.length();
546
547
27
  int* bad_char_occurrence = bad_char_table();
548
549
  // Only preprocess at most kBMMaxShift last characters of pattern.
550
27
  const size_t start = start_;
551
  // Run forwards to populate bad_char_table, so that *last* instance
552
  // of character equivalence class is the one registered.
553
  // Notice: Doesn't include the last character.
554
27
  const size_t table_size = AlphabetSize();
555

27
  if (start == 0) {
556
    // All patterns less than kBMMaxShift in length.
557
20
    memset(bad_char_occurrence, -1, table_size * sizeof(*bad_char_occurrence));
558
  } else {
559

1799
    for (size_t i = 0; i < table_size; i++) {
560
1792
      bad_char_occurrence[i] = start - 1;
561
    }
562
  }
563

2614
  for (size_t i = start; i < pattern_length - 1; i++) {
564
2587
    Char c = pattern_[i];
565
2587
    int bucket = (sizeof(Char) == 1) ? c : c % AlphabetSize();
566
2587
    bad_char_occurrence[bucket] = i;
567
  }
568
27
}
569
570
//---------------------------------------------------------------------
571
// Linear string search with bailout to BMH.
572
//---------------------------------------------------------------------
573
574
// Simple linear search for short patterns, which bails out if the string
575
// isn't found very early in the subject. Upgrades to BoyerMooreHorspool.
576
template <typename Char>
577
675
size_t StringSearch<Char>::InitialSearch(
578
    StringSearch<Char>* search,
579
    Vector<const Char> subject,
580
    size_t index) {
581
675
  Vector<const Char> pattern = search->pattern_;
582
675
  const size_t pattern_length = pattern.length();
583
  // Badness is a count of how much work we have done.  When we have
584
  // done enough work we decide it's probably worth switching to a better
585
  // algorithm.
586
675
  int64_t badness = -10 - (pattern_length << 2);
587
588
  // We know our pattern is at least 2 characters, we cache the first so
589
  // the common case of the first character not matching is faster.
590

373734
  for (size_t i = index, n = subject.length() - pattern_length; i <= n; i++) {
591
373734
    badness++;
592

373734
    if (badness <= 0) {
593
373707
      i = FindFirstCharacter(pattern, subject, i);
594

373707
      if (i == subject.length())
595
3
        return subject.length();
596

373704
      CHECK_LE(i, n);
597
373704
      size_t j = 1;
598

10159487
      do {
599

10532546
        if (pattern[j] != subject[i + j]) {
600
373059
          break;
601
        }
602
10159487
        j++;
603
      } while (j < pattern_length);
604

373704
      if (j == pattern_length) {
605
645
        return i;
606
      }
607
373059
      badness += j;
608
    } else {
609
27
      search->PopulateBoyerMooreHorspoolTable();
610
27
      search->strategy_ = &BoyerMooreHorspoolSearch;
611
27
      return BoyerMooreHorspoolSearch(search, subject, i);
612
    }
613
  }
614
  return subject.length();
615
}
616
617
// Perform a a single stand-alone search.
618
// If searching multiple times for the same pattern, a search
619
// object should be constructed once and the Search function then called
620
// for each search.
621
template <typename Char>
622
107647
size_t SearchString(Vector<const Char> subject,
623
                    Vector<const Char> pattern,
624
                    size_t start_index) {
625
107647
  StringSearch<Char> search(pattern);
626
107647
  return search.Search(subject, start_index);
627
}
628
}  // namespace stringsearch
629
}  // namespace node
630
631
namespace node {
632
using node::stringsearch::Vector;
633
634
template <typename Char>
635
107649
size_t SearchString(const Char* haystack,
636
                    size_t haystack_length,
637
                    const Char* needle,
638
                    size_t needle_length,
639
                    size_t start_index,
640
                    bool is_forward) {
641

107649
  if (haystack_length < needle_length) return haystack_length;
642
  // To do a reverse search (lastIndexOf instead of indexOf) without redundant
643
  // code, create two vectors that are reversed views into the input strings.
644
  // For example, v_needle[0] would return the *last* character of the needle.
645
  // So we're searching for the first instance of rev(needle) in rev(haystack)
646
  Vector<const Char> v_needle = Vector<const Char>(
647
107647
      needle, needle_length, is_forward);
648
  Vector<const Char> v_haystack = Vector<const Char>(
649
107647
      haystack, haystack_length, is_forward);
650
107647
  size_t diff = haystack_length - needle_length;
651
  size_t relative_start_index;
652

107647
  if (is_forward) {
653
107572
    relative_start_index = start_index;
654

75
  } else if (diff < start_index) {
655
31
    relative_start_index = 0;
656
  } else {
657
44
    relative_start_index = diff - start_index;
658
  }
659
  size_t pos = node::stringsearch::SearchString(
660
107647
      v_haystack, v_needle, relative_start_index);
661

107647
  if (pos == haystack_length) {
662
    // not found
663
2940
    return pos;
664
  }
665

104707
  return is_forward ? pos : (haystack_length - needle_length - pos);
666
}
667
668
template <size_t N>
669
6608
size_t SearchString(const char* haystack, size_t haystack_length,
670
                    const char (&needle)[N]) {
671
  return SearchString(
672
      reinterpret_cast<const uint8_t*>(haystack), haystack_length,
673
6608
      reinterpret_cast<const uint8_t*>(needle), N - 1, 0, true);
674
}
675
676
}  // namespace node
677
678
#endif  // defined(NODE_WANT_INTERNALS) && NODE_WANT_INTERNALS
679
680
#endif  // SRC_STRING_SEARCH_H_