/*
- * Copyright 2016 Facebook, Inc.
+ * Copyright 2017 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#include <folly/portability/Constexpr.h>
#include <folly/portability/String.h>
-#include <algorithm>
#include <boost/operators.hpp>
+#include <glog/logging.h>
+#include <algorithm>
+#include <array>
#include <climits>
#include <cstddef>
#include <cstring>
-#include <glog/logging.h>
#include <iosfwd>
#include <stdexcept>
#include <string>
#include <folly/detail/RangeSse42.h>
// Ignore shadowing warnings within this file, so includers can use -Wshadow.
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wshadow"
+FOLLY_PUSH_WARNING
+FOLLY_GCC_DISABLE_WARNING("-Wshadow")
namespace folly {
-template <class T> class Range;
+template <class Iter> class Range;
/**
* Finds the first occurrence of needle in haystack. The algorithm is on
* as Boyer-Moore. On the upside, it does not do any upfront
* preprocessing and does not allocate memory.
*/
-template <class T, class Comp = std::equal_to<typename Range<T>::value_type>>
-inline size_t qfind(const Range<T> & haystack,
- const Range<T> & needle,
+template <class Iter,
+ class Comp = std::equal_to<typename Range<Iter>::value_type>>
+inline size_t qfind(const Range<Iter> & haystack,
+ const Range<Iter> & needle,
Comp eq = Comp());
/**
* offset reported to the beginning of haystack, or string::npos if
* needle wasn't found.
*/
-template <class T>
-size_t qfind(const Range<T> & haystack,
- const typename Range<T>::value_type& needle);
+template <class Iter>
+size_t qfind(const Range<Iter> & haystack,
+ const typename Range<Iter>::value_type& needle);
/**
* Finds the last occurrence of needle in haystack. The result is the
* offset reported to the beginning of haystack, or string::npos if
* needle wasn't found.
*/
-template <class T>
-size_t rfind(const Range<T> & haystack,
- const typename Range<T>::value_type& needle);
+template <class Iter>
+size_t rfind(const Range<Iter> & haystack,
+ const typename Range<Iter>::value_type& needle);
/**
* Finds the first occurrence of any element of needle in
* haystack. The algorithm is O(haystack.size() * needle.size()).
*/
-template <class T>
-inline size_t qfind_first_of(const Range<T> & haystack,
- const Range<T> & needle);
+template <class Iter>
+inline size_t qfind_first_of(const Range<Iter> & haystack,
+ const Range<Iter> & needle);
/**
* Small internal helper - returns the value just before an iterator.
typedef typename std::remove_reference<
typename std::iterator_traits<Iter>::reference>::type
value_type;
+ using difference_type = typename std::iterator_traits<Iter>::difference_type;
typedef typename std::iterator_traits<Iter>::reference reference;
/**
constexpr Range(Iter start, size_t size)
: b_(start), e_(start + size) { }
-# if !__clang__ || __CLANG_PREREQ(3, 7) // Clang 3.6 crashes on this line
/* implicit */ Range(std::nullptr_t) = delete;
-# endif
template <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
constexpr /* implicit */ Range(Iter str)
e_(other.end()) {
}
+ /**
+ * Allow explicit construction of Range() from a std::array of a
+ * convertible type.
+ *
+ * For instance, this allows constructing StringPiece from a
+ * std::array<char, N> or a std::array<const char, N>
+ */
+ template <
+ class T,
+ size_t N,
+ typename = typename std::enable_if<
+ std::is_convertible<const T*, Iter>::value>::type>
+ constexpr explicit Range(const std::array<T, N>& array)
+ : b_{array.empty() ? nullptr : &array.at(0)},
+ e_{array.empty() ? nullptr : &array.at(0) + N} {}
+ template <
+ class T,
+ size_t N,
+ typename =
+ typename std::enable_if<std::is_convertible<T*, Iter>::value>::type>
+ constexpr explicit Range(std::array<T, N>& array)
+ : b_{array.empty() ? nullptr : &array.at(0)},
+ e_{array.empty() ? nullptr : &array.at(0) + N} {}
+
Range& operator=(const Range& rhs) & = default;
Range& operator=(Range&& rhs) & = default;
+ template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
+ Range& operator=(std::string&& rhs) = delete;
+
void clear() {
b_ = Iter();
e_ = Iter();
return size_type(e_ - b_);
}
constexpr size_type walk_size() const {
- return std::distance(b_, e_);
+ return size_type(std::distance(b_, e_));
}
constexpr bool empty() const {
return b_ == e_;
return !empty() && front() == c;
}
+ template <class Comp>
+ bool startsWith(const const_range_type& other, Comp&& eq) const {
+ if (size() < other.size()) {
+ return false;
+ }
+ auto const trunc = subpiece(0, other.size());
+ return std::equal(
+ trunc.begin(), trunc.end(), other.begin(), std::forward<Comp>(eq));
+ }
+
/**
* Does this Range end with another range?
*/
return !empty() && back() == c;
}
+ template <class Comp>
+ bool endsWith(const const_range_type& other, Comp&& eq) const {
+ if (size() < other.size()) {
+ return false;
+ }
+ auto const trunc = subpiece(size() - other.size());
+ return std::equal(
+ trunc.begin(), trunc.end(), other.begin(), std::forward<Comp>(eq));
+ }
+
/**
* Remove the items in [b, e), as long as this subrange is at the beginning
* or end of the Range.
auto i = find(delimiter);
Range result(b_, i == std::string::npos ? size() : i);
- b_ = result.end() == e_ ? e_ : std::next(result.end(), delimiter.size());
+ b_ = result.end() == e_
+ ? e_
+ : std::next(
+ result.end(),
+ typename std::iterator_traits<Iter>::difference_type(
+ delimiter.size()));
return result;
}
template <class Iter>
const typename Range<Iter>::size_type Range<Iter>::npos = std::string::npos;
-template <class T>
-void swap(Range<T>& lhs, Range<T>& rhs) {
+template <class Iter>
+void swap(Range<Iter>& lhs, Range<Iter>& rhs) {
lhs.swap(rhs);
}
template <class T, size_t n>
constexpr Range<const T*> range(const std::array<T, n>& array) {
- using r = Range<const T*>;
- return array.empty() ? r{} : r(&array.at(0), &array.at(0) + n);
+ return Range<const T*>{array};
}
typedef Range<const char*> StringPiece;
* Templated comparison operators
*/
-template <class T>
-inline bool operator==(const Range<T>& lhs, const Range<T>& rhs) {
+template <class Iter>
+inline bool operator==(const Range<Iter>& lhs, const Range<Iter>& rhs) {
return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
}
-template <class T>
-inline bool operator<(const Range<T>& lhs, const Range<T>& rhs) {
+template <class Iter>
+inline bool operator<(const Range<Iter>& lhs, const Range<Iter>& rhs) {
return lhs.compare(rhs) < 0;
}
/**
* Finds substrings faster than brute force by borrowing from Boyer-Moore
*/
-template <class T, class Comp>
-size_t qfind(const Range<T>& haystack,
- const Range<T>& needle,
+template <class Iter, class Comp>
+size_t qfind(const Range<Iter>& haystack,
+ const Range<Iter>& needle,
Comp eq) {
// Don't use std::search, use a Boyer-Moore-like trick by comparing
// the last characters first
} // namespace detail
-template <class T, class Comp>
-size_t qfind_first_of(const Range<T> & haystack,
- const Range<T> & needles,
+template <class Iter, class Comp>
+size_t qfind_first_of(const Range<Iter> & haystack,
+ const Range<Iter> & needles,
Comp eq) {
auto ret = std::find_first_of(haystack.begin(), haystack.end(),
needles.begin(), needles.end(),
}
};
-template <class T>
-size_t qfind(const Range<T>& haystack,
- const typename Range<T>::value_type& needle) {
+template <class Iter>
+size_t qfind(const Range<Iter>& haystack,
+ const typename Range<Iter>::value_type& needle) {
auto pos = std::find(haystack.begin(), haystack.end(), needle);
return pos == haystack.end() ? std::string::npos : pos - haystack.data();
}
-template <class T>
-size_t rfind(const Range<T>& haystack,
- const typename Range<T>::value_type& needle) {
+template <class Iter>
+size_t rfind(const Range<Iter>& haystack,
+ const typename Range<Iter>::value_type& needle) {
for (auto i = haystack.size(); i-- > 0; ) {
if (haystack[i] == needle) {
return i;
return pos == nullptr ? std::string::npos : pos - haystack.data();
}
-template <class T>
-size_t qfind_first_of(const Range<T>& haystack,
- const Range<T>& needles) {
+template <class Iter>
+size_t qfind_first_of(const Range<Iter>& haystack,
+ const Range<Iter>& needles) {
return qfind_first_of(haystack, needles, AsciiCaseSensitive());
}
} // !namespace folly
-#pragma GCC diagnostic pop
+FOLLY_POP_WARNING
FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);