chromium/v8/src/strings/string-search.h

// Copyright 2011 the V8 project authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifndef V8_STRINGS_STRING_SEARCH_H_
#define V8_STRINGS_STRING_SEARCH_H_

#include "src/base/strings.h"
#include "src/base/vector.h"
#include "src/execution/isolate.h"
#include "src/objects/string.h"

namespace v8 {
namespace internal {

//---------------------------------------------------------------------
// String Search object.
//---------------------------------------------------------------------

// Class holding constants and methods that apply to all string search variants,
// independently of subject and pattern char size.
class StringSearchBase { … };

template <typename PatternChar, typename SubjectChar>
class StringSearch : private StringSearchBase { … };

template <typename T, typename U>
inline T AlignDown(T value, U alignment) { … }

inline uint8_t GetHighestValueByte(base::uc16 character) { … }

inline uint8_t GetHighestValueByte(uint8_t character) { … }

template <typename PatternChar, typename SubjectChar>
inline int FindFirstCharacter(base::Vector<const PatternChar> pattern,
                              base::Vector<const SubjectChar> subject,
                              int index) { … }

//---------------------------------------------------------------------
// Single Character Pattern Search Strategy
//---------------------------------------------------------------------

template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::SingleCharSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    base::Vector<const SubjectChar> subject, int index) { … }

//---------------------------------------------------------------------
// Linear Search Strategy
//---------------------------------------------------------------------

template <typename PatternChar, typename SubjectChar>
inline bool CharCompare(const PatternChar* pattern, const SubjectChar* subject,
                        int length) { … }

// Simple linear search for short patterns. Never bails out.
template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::LinearSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    base::Vector<const SubjectChar> subject, int index) { … }

//---------------------------------------------------------------------
// Boyer-Moore string search
//---------------------------------------------------------------------

template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::BoyerMooreSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    base::Vector<const SubjectChar> subject, int start_index) { … }

template <typename PatternChar, typename SubjectChar>
void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreTable() { … }

//---------------------------------------------------------------------
// Boyer-Moore-Horspool string search.
//---------------------------------------------------------------------

template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::BoyerMooreHorspoolSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    base::Vector<const SubjectChar> subject, int start_index) { … }

template <typename PatternChar, typename SubjectChar>
void StringSearch<PatternChar, SubjectChar>::PopulateBoyerMooreHorspoolTable() { … }

//---------------------------------------------------------------------
// Linear string search with bailout to BMH.
//---------------------------------------------------------------------

// Simple linear search for short patterns, which bails out if the string
// isn't found very early in the subject. Upgrades to BoyerMooreHorspool.
template <typename PatternChar, typename SubjectChar>
int StringSearch<PatternChar, SubjectChar>::InitialSearch(
    StringSearch<PatternChar, SubjectChar>* search,
    base::Vector<const SubjectChar> subject, int index) { … }

// Perform a a single stand-alone search.
// If searching multiple times for the same pattern, a search
// object should be constructed once and the Search function then called
// for each search.
template <typename SubjectChar, typename PatternChar>
int SearchString(Isolate* isolate, base::Vector<const SubjectChar> subject,
                 base::Vector<const PatternChar> pattern, int start_index) { … }

// A wrapper function around SearchString that wraps raw pointers to the subject
// and pattern as vectors before calling SearchString. Used from the
// StringIndexOf builtin.
template <typename SubjectChar, typename PatternChar>
intptr_t SearchStringRaw(Isolate* isolate, const SubjectChar* subject_ptr,
                         int subject_length, const PatternChar* pattern_ptr,
                         int pattern_length, int start_index) { … }

}  // namespace internal
}  // namespace v8

#endif  // V8_STRINGS_STRING_SEARCH_H_