← Back to branch summary

~james-page/ubuntu/precise/nodejs/0.6.x-merge

« back to all changes in this revision

Viewing changes to deps/v8/src/string-search.h

  • Committer: James Page
  • Date: 2012-03-30 12:09:16 UTC
  • mfrom: (7.1.23 sid)
  • Revision ID: james.page@canonical.com-20120330120916-40hfu9o00qr5t87b
http://bugs.debian.org/639636
http://bugs.debian.org/650661
http://bugs.debian.org/658441
https://launchpad.net/bugs/892034
* Merge from Debian unstable:
  - New upstream release (LP: #892034).
  - This package is x86/arm only. Update control to match
  - d/patches/2009_increase_test_timeout.patch: Increased default test
    timeout from 60 to 120 seconds to support reliable execution of all
    tests on armhf/armel architectures.
  - d/patches/2005_expected_failing_tests.patch: 
    - Allow racey tests to fail: test-cluster-kill-workers,
      test-child-process-fork2 
    - Allow test-fs-watch to fail as LP buildd's don't support
      inotify.
    - Revert all other Ubuntu changes as no longer required.
* Update Standards-Version to 3.9.3.
* Patch wscript to enable build on mipsel arch, libv8 being available.
  Upstream does not support that arch, failure expected.
* test-cluster-kill-workers is expected to fail on armhf,
  Bug#660802 will be closed when test pass.
* test-buffer is expected to fail on armel,
  Bug#660800 will be closed when test pass.
* Add epoch to dependency on libev >= 1:4.11. Closes: bug#658441.
* Remove tools/doc because node-doc-generator has no license for now.
* Add copyright for doc/sh* files (shjs).
* source.lintian-overrides : source-contains-waf-binary tools/node-waf
  it is simply not the case here.
* test-stream-pipe-multi expected to timeout sometimes on busy builds. 
* New upstream release.
* Remove upstream patches.
* test-dgram-pingpong expected to timeout, the test itself is buggy.
* test-buffer expected to fail on armel, allow building package to make
  it easier to find the cause of the failure.
  Closes: bug#639636.
* Expect tests dgram-multicast and broadcast to fail.
  debian/patches/2005_expected_failing_tests.patch
* Drop dpkg-source local-options: Defaults since dpkg-source 1.16.1.
* New upstream release.
* Depend on libev-dev 4.11, see bug#657080.
* Bump dependency on openssl to 1.0.0g.
* Remove useless uv_loop_refcount from libuv,
  refreshed 2009_fix_shared_ev.patch.
* Apply to upstream patches landed after 0.6.10 release,
  to fix debugger repl and http client.
* New upstream release. Closes:bug#650661
* Repackage to remove non-dfsg font files ./deps/npm/html/*/*.ttf
* Remove unneeded bundled dependencies: lighter tarball,
  debian/copyright is easier to maintain.
* Drop unneeded build-dependency on scons.
* Depend on zlib1g, libc-ares, libev.
  Patches done to support building with those shared libs.
* Fix DEB_UPSTREAM_URL in debian/rules, and debian/watch.
* nodejs.pc file for pkgconfig is no more available.
* Build-depend on procps package, a test is using /bin/ps.
* Refreshed debian/patches/2005_expected_failing_tests.patch,
  only for tests that need networking.

Show diffs side-by-side

added added

removed removed

Lines of Context:
deps/v8/src/string-search.h
44
44
  // limit, we can fix the size of tables. For a needle longer than this limit,
45
45
  // search will not be optimal, since we only build tables for a suffix
46
46
  // of the string, but it is a safe approximation.
47
 
  static const int kBMMaxShift = 250;
 
47
  static const int kBMMaxShift = Isolate::kBMMaxShift;
48
48
 
49
49
  // Reduce alphabet to this size.
50
50
  // One of the tables used by Boyer-Moore and Boyer-Moore-Horspool has size
54
54
  // For needles using only characters in the same Unicode 256-code point page,
55
55
  // there is no search speed degradation.
56
56
  static const int kAsciiAlphabetSize = 128;
57
 
  static const int kUC16AlphabetSize = 256;
 
57
  static const int kUC16AlphabetSize = Isolate::kUC16AlphabetSize;
58
58
 
59
59
  // Bad-char shift table stored in the state. It's length is the alphabet size.
60
60
  // For patterns below this length, the skip length of Boyer-Moore is too short
69
69
    return String::IsAscii(string.start(), string.length());
70
70
  }
71
71
 
72
 
  // The following tables are shared by all searches.
73
 
  // TODO(lrn): Introduce a way for a pattern to keep its tables
74
 
  // between searches (e.g., for an Atom RegExp).
75
 
 
76
 
  // Store for the BoyerMoore(Horspool) bad char shift table.
77
 
  static int kBadCharShiftTable[kUC16AlphabetSize];
78
 
  // Store for the BoyerMoore good suffix shift table.
79
 
  static int kGoodSuffixShiftTable[kBMMaxShift + 1];
80
 
  // Table used temporarily while building the BoyerMoore good suffix
81
 
  // shift table.
82
 
  static int kSuffixTable[kBMMaxShift + 1];
 
72
  friend class Isolate;
83
73
};
84
74
 
85
75
 
86
76
template <typename PatternChar, typename SubjectChar>
87
77
class StringSearch : private StringSearchBase {
88
78
 public:
89
 
  explicit StringSearch(Vector<const PatternChar> pattern)
90
 
      : pattern_(pattern),
 
79
  StringSearch(Isolate* isolate, Vector<const PatternChar> pattern)
 
80
      : isolate_(isolate),
 
81
        pattern_(pattern),
91
82
        start_(Max(0, pattern.length() - kBMMaxShift)) {
92
83
    if (sizeof(PatternChar) > sizeof(SubjectChar)) {
93
84
      if (!IsAsciiString(pattern_)) {
175
166
    return bad_char_occurrence[equiv_class];
176
167
  }
177
168
 
 
169
  // The following tables are shared by all searches.
 
170
  // TODO(lrn): Introduce a way for a pattern to keep its tables
 
171
  // between searches (e.g., for an Atom RegExp).
 
172
 
 
173
  // Store for the BoyerMoore(Horspool) bad char shift table.
178
174
  // Return a table covering the last kBMMaxShift+1 positions of
179
175
  // pattern.
180
176
  int* bad_char_table() {
181
 
    return kBadCharShiftTable;
 
177
    return isolate_->bad_char_shift_table();
182
178
  }
183
179
 
 
180
  // Store for the BoyerMoore good suffix shift table.
184
181
  int* good_suffix_shift_table() {
185
182
    // Return biased pointer that maps the range  [start_..pattern_.length()
186
183
    // to the kGoodSuffixShiftTable array.
187
 
    return kGoodSuffixShiftTable - start_;
 
184
    return isolate_->good_suffix_shift_table() - start_;
188
185
  }
189
186
 
 
187
  // Table used temporarily while building the BoyerMoore good suffix
 
188
  // shift table.
190
189
  int* suffix_table() {
191
190
    // Return biased pointer that maps the range  [start_..pattern_.length()
192
191
    // to the kSuffixTable array.
193
 
    return kSuffixTable - start_;
 
192
    return isolate_->suffix_table() - start_;
194
193
  }
195
194
 
 
195
  Isolate* isolate_;
196
196
  // The pattern to search for.
197
197
  Vector<const PatternChar> pattern_;
198
198
  // Pointer to implementation of the search.
555
555
// object should be constructed once and the Search function then called
556
556
// for each search.
557
557
template <typename SubjectChar, typename PatternChar>
558
 
static int SearchString(Vector<const SubjectChar> subject,
 
558
static int SearchString(Isolate* isolate,
 
559
                        Vector<const SubjectChar> subject,
559
560
                        Vector<const PatternChar> pattern,
560
561
                        int start_index) {
561
 
  StringSearch<PatternChar, SubjectChar> search(pattern);
 
562
  StringSearch<PatternChar, SubjectChar> search(isolate, pattern);
562
563
  return search.Search(subject, start_index);
563
564
}
564
565