chromium/base/substring_set_matcher/substring_set_matcher.cc

// Copyright 2013 The Chromium Authors
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#ifdef UNSAFE_BUFFERS_BUILD
// TODO(crbug.com/40284755): Remove this and spanify to fix the errors.
#pragma allow_unsafe_buffers
#endif

#include "base/substring_set_matcher/substring_set_matcher.h"

#include <stddef.h>

#include <algorithm>
#include <queue>

#ifdef __SSE2__
#include <immintrin.h>
#include "base/bits.h"
#endif

#include "base/check_op.h"
#include "base/containers/contains.h"
#include "base/containers/queue.h"
#include "base/numerics/checked_math.h"
#include "base/trace_event/memory_usage_estimator.h"  // no-presubmit-check

namespace base {

namespace {

// Compare MatcherStringPattern instances based on their string patterns.
bool ComparePatterns(const MatcherStringPattern* a,
                     const MatcherStringPattern* b) { … }

std::vector<const MatcherStringPattern*> GetVectorOfPointers(
    const std::vector<MatcherStringPattern>& patterns) { … }

}  // namespace

bool SubstringSetMatcher::Build(
    const std::vector<MatcherStringPattern>& patterns) { … }

bool SubstringSetMatcher::Build(
    std::vector<const MatcherStringPattern*> patterns) { … }

SubstringSetMatcher::SubstringSetMatcher() = default;
SubstringSetMatcher::~SubstringSetMatcher() = default;

bool SubstringSetMatcher::Match(
    const std::string& text,
    std::set<MatcherStringPattern::ID>* matches) const { … }

bool SubstringSetMatcher::AnyMatch(const std::string& text) const { … }

size_t SubstringSetMatcher::EstimateMemoryUsage() const { … }

// static
constexpr SubstringSetMatcher::NodeID SubstringSetMatcher::kInvalidNodeID;
constexpr SubstringSetMatcher::NodeID SubstringSetMatcher::kRootID;

SubstringSetMatcher::NodeID SubstringSetMatcher::GetTreeSize(
    const std::vector<const MatcherStringPattern*>& patterns) const { … }

void SubstringSetMatcher::BuildAhoCorasickTree(
    const SubstringPatternVector& patterns) { … }

void SubstringSetMatcher::InsertPatternIntoAhoCorasickTree(
    const MatcherStringPattern* pattern) { … }

void SubstringSetMatcher::CreateFailureAndOutputEdges() { … }

void SubstringSetMatcher::AccumulateMatchesForNode(
    const AhoCorasickNode* node,
    std::set<MatcherStringPattern::ID>* matches) const { … }

SubstringSetMatcher::AhoCorasickNode::AhoCorasickNode() { … }

SubstringSetMatcher::AhoCorasickNode::~AhoCorasickNode() { … }

SubstringSetMatcher::AhoCorasickNode::AhoCorasickNode(AhoCorasickNode&& other) { … }

SubstringSetMatcher::AhoCorasickNode&
SubstringSetMatcher::AhoCorasickNode::operator=(AhoCorasickNode&& other) { … }

SubstringSetMatcher::NodeID
SubstringSetMatcher::AhoCorasickNode::GetEdgeNoInline(uint32_t label) const { … }

void SubstringSetMatcher::AhoCorasickNode::SetEdge(uint32_t label,
                                                   NodeID node) { … }

void SubstringSetMatcher::AhoCorasickNode::SetFailure(NodeID node) { … }

size_t SubstringSetMatcher::AhoCorasickNode::EstimateMemoryUsage() const { … }

}  // namespace base