Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(801)

Unified Diff: components/subresource_filter/core/common/knuth_morris_pratt.h

Issue 2153743002: Save failure function to FlatBuffer. (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: Add newline. Created 4 years, 5 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View side-by-side diff with in-line comments
Download patch
Index: components/subresource_filter/core/common/knuth_morris_pratt.h
diff --git a/components/subresource_filter/core/common/knuth_morris_pratt.h b/components/subresource_filter/core/common/knuth_morris_pratt.h
index 8e910e64009b42812de75fcdb59e7e72c77861fb..29e50e7307bdf4d5409c0e67d3685680aca5ea91 100644
--- a/components/subresource_filter/core/common/knuth_morris_pratt.h
+++ b/components/subresource_filter/core/common/knuth_morris_pratt.h
@@ -24,8 +24,12 @@
#include <functional>
#include <iterator>
+#include <limits>
+#include <type_traits>
#include <vector>
+#include "base/logging.h"
+#include "base/numerics/safe_conversions.h"
#include "base/strings/string_piece.h"
namespace subresource_filter {
@@ -34,10 +38,13 @@ namespace subresource_filter {
// |pattern| at the end of the |failure| vector. The EquivalentTo should be a
// bool(char, char) functor returning true iff the two characters are
// equivalent, and is required to be reflexive, symmetric and transitive.
-template <typename EquivalentTo = std::equal_to<char>>
+template <typename IntType, typename EquivalentTo = std::equal_to<char>>
void BuildFailureFunction(base::StringPiece pattern,
- std::vector<size_t>* failure,
+ std::vector<IntType>* failure,
EquivalentTo equivalent_to = EquivalentTo()) {
+ static_assert(std::is_unsigned<IntType>::value, "IntType is not unsigned.");
+ DCHECK_LE(pattern.size(), std::numeric_limits<IntType>::max());
+
if (pattern.empty())
return;
@@ -46,7 +53,7 @@ void BuildFailureFunction(base::StringPiece pattern,
for (size_t i = 1; i != pattern.size(); ++i) {
const char c = pattern[i];
- size_t prefix_match_size = failure->back();
+ IntType prefix_match_size = failure->back();
DCHECK_LT(prefix_match_size, i);
while (prefix_match_size && !equivalent_to(pattern[prefix_match_size], c))
prefix_match_size = (*failure)[base_index + prefix_match_size - 1];
@@ -71,13 +78,16 @@ void BuildFailureFunction(base::StringPiece pattern,
// The |failure| array is the failure function created by BuildFailureFunction
// with the same EquivalentTo and |pattern|, and containing at least
// pattern.size() values.
-template <typename EquivalentTo = std::equal_to<char>>
+template <typename IntType, typename EquivalentTo = std::equal_to<char>>
size_t FindOccurrence(base::StringPiece text,
base::StringPiece pattern,
- const size_t* failure,
- size_t prefix_match_size,
+ const IntType* failure,
+ IntType prefix_match_size,
EquivalentTo equivalent_to = EquivalentTo()) {
+ static_assert(std::is_unsigned<IntType>::value, "IntType is not unsigned.");
DCHECK_LE(prefix_match_size, pattern.size());
+ DCHECK_LE(pattern.size(), std::numeric_limits<IntType>::max());
+
if (prefix_match_size == pattern.size())
return 0;
@@ -95,27 +105,28 @@ size_t FindOccurrence(base::StringPiece text,
// Same as FindOccurrence, but starts the search from scratch, i.e. with
// prefix_match_size == 0.
-template <typename EquivalentTo = std::equal_to<char>>
+template <typename IntType, typename EquivalentTo = std::equal_to<char>>
size_t FindFirstOccurrence(base::StringPiece text,
base::StringPiece pattern,
- const size_t* failure,
+ const IntType* failure,
EquivalentTo equivalent_to = EquivalentTo()) {
- return FindOccurrence(text, pattern, failure, 0, equivalent_to);
+ return FindOccurrence(text, pattern, failure, static_cast<IntType>(0),
+ equivalent_to);
}
// Same as FindOccurrence, but preforms the search assuming the |text| starts
// right after a full match of the |pattern|. The returned value is either
// base::StringPiece::npos if no more occurrences found, or is within the range
// [1, text.size()] if there are occurrences apart from the virtual prefix.
-template <typename EquivalentTo = std::equal_to<char>>
+template <typename IntType, typename EquivalentTo = std::equal_to<char>>
size_t FindNextOccurrence(base::StringPiece text,
base::StringPiece pattern,
- const size_t* failure,
+ const IntType* failure,
EquivalentTo equivalent_to = EquivalentTo()) {
if (pattern.empty())
return text.empty() ? base::StringPiece::npos : 1;
- const size_t prefix_match_size = failure[pattern.size() - 1];
+ const IntType prefix_match_size = failure[pattern.size() - 1];
return FindOccurrence(text, pattern, failure, prefix_match_size,
equivalent_to);
}
@@ -124,10 +135,13 @@ size_t FindNextOccurrence(base::StringPiece text,
// with respect to EquivalentTo relation between characters, and iterate over
// them using an input iterator. The values pointed to by an iterator indicate
// positions of occurrences, i.e. indices of |text| characters coming *after*
-// the occurrences.
-template <typename EquivalentTo = std::equal_to<char>>
+// the occurrences. Out-of-range iterators are dereferenced to
+// base::StringPiece::npos.
+template <typename IntType, typename EquivalentTo = std::equal_to<char>>
class AllOccurrences {
public:
+ static_assert(std::is_unsigned<IntType>::value, "IntType is not unsigned.");
+
class Iterator : public std::iterator<std::input_iterator_tag, size_t> {
public:
bool operator==(const Iterator& rhs) const {
@@ -173,7 +187,7 @@ class AllOccurrences {
AllOccurrences(base::StringPiece text,
base::StringPiece pattern,
- const size_t* failure,
+ const IntType* failure,
EquivalentTo equivalent_to = EquivalentTo())
: text_(text),
pattern_(pattern),
@@ -198,7 +212,7 @@ class AllOccurrences {
base::StringPiece text_;
base::StringPiece pattern_;
- const size_t* failure_;
+ const IntType* failure_;
EquivalentTo equivalent_to_;
};
@@ -220,13 +234,14 @@ class AllOccurrences {
// // text[|match_end|-pattern.size()..|match_end|-1]
// ... process the |match_end| ...
// }
-template <typename EquivalentTo = std::equal_to<char>>
-AllOccurrences<EquivalentTo> CreateAllOccurrences(
+template <typename IntType, typename EquivalentTo = std::equal_to<char>>
+AllOccurrences<IntType, EquivalentTo> CreateAllOccurrences(
base::StringPiece text,
base::StringPiece pattern,
- const size_t* failure,
+ const IntType* failure,
EquivalentTo equivalent_to = EquivalentTo()) {
- return AllOccurrences<EquivalentTo>(text, pattern, failure, equivalent_to);
+ return AllOccurrences<IntType, EquivalentTo>(text, pattern, failure,
+ equivalent_to);
}
} // namespace subresource_filter

Powered by Google App Engine
This is Rietveld 408576698