/*
- * 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/FBString.h>
#include <folly/Portability.h>
#include <folly/SpookyHashV2.h>
+#include <folly/portability/BitsFunctexcept.h>
#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)
template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
Range(const std::string& str, std::string::size_type startFrom) {
if (UNLIKELY(startFrom > str.size())) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
b_ = str.data() + startFrom;
e_ = str.data() + str.size();
std::string::size_type startFrom,
std::string::size_type size) {
if (UNLIKELY(startFrom > str.size())) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
b_ = str.data() + startFrom;
if (str.size() - startFrom < size) {
template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
Range(const fbstring& str, fbstring::size_type startFrom) {
if (UNLIKELY(startFrom > str.size())) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
b_ = str.data() + startFrom;
e_ = str.data() + str.size();
Range(const fbstring& str, fbstring::size_type startFrom,
fbstring::size_type size) {
if (UNLIKELY(startFrom > str.size())) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
b_ = str.data() + startFrom;
if (str.size() - startFrom < size) {
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();
// Unfortunately current gcc versions have a bug causing it to reject
// this check in a constexpr function:
// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=71448
- return e_ - b_;
- }
- size_type walk_size() const {
- return std::distance(b_, e_);
- }
- bool empty() const { return b_ == e_; }
- Iter data() const { return b_; }
- Iter start() const { return b_; }
- Iter begin() const { return b_; }
- Iter end() const { return e_; }
- Iter cbegin() const { return b_; }
- Iter cend() const { return e_; }
+ return size_type(e_ - b_);
+ }
+ constexpr size_type walk_size() const {
+ return size_type(std::distance(b_, e_));
+ }
+ constexpr bool empty() const {
+ return b_ == e_;
+ }
+ constexpr Iter data() const {
+ return b_;
+ }
+ constexpr Iter start() const {
+ return b_;
+ }
+ constexpr Iter begin() const {
+ return b_;
+ }
+ constexpr Iter end() const {
+ return e_;
+ }
+ constexpr Iter cbegin() const {
+ return b_;
+ }
+ constexpr Iter cend() const {
+ return e_;
+ }
value_type& front() {
assert(b_ < e_);
return *b_;
const_range_type castToConst() const {
return const_range_type(*this);
- };
+ }
// Works only for Range<const char*> and Range<char*>
int compare(const const_range_type& o) const {
}
value_type& at(size_t i) {
- if (i >= size()) throw std::out_of_range("index out of range");
+ if (i >= size()) std::__throw_out_of_range("index out of range");
return b_[i];
}
const value_type& at(size_t i) const {
- if (i >= size()) throw std::out_of_range("index out of range");
+ if (i >= size()) std::__throw_out_of_range("index out of range");
return b_[i];
}
// (The above advice does not apply if you are targeting a 32-bit system.)
//
// Works only for Range<const char*> and Range<char*>
+ //
+ //
+ // ** WANT TO GET RID OF THIS LINT? **
+ //
+ // A) Use a better hash function (*cough*folly::Hash*cough*), but
+ // only if you don't serialize data in a format that depends on
+ // this formula (ie the writer and reader assume this exact hash
+ // function is used).
+ //
+ // B) If you have to use this exact function then make your own hasher
+ // object and copy the body over (see thrift example: D3972362).
+ // https://github.com/facebook/fbthrift/commit/f8ed502e24ab4a32a9d5f266580
+ FOLLY_DEPRECATED("Replace with folly::Hash if the hash is not serialized")
uint32_t hash() const {
// Taken from fbi/nstring.h:
// Quick and dirty bernstein hash...fine for short ascii strings
void advance(size_type n) {
if (UNLIKELY(n > size())) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
b_ += n;
}
void subtract(size_type n) {
if (UNLIKELY(n > size())) {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of range");
}
e_ -= n;
}
+ Range subpiece(size_type first, size_type length = npos) const {
+ if (UNLIKELY(first > size())) {
+ std::__throw_out_of_range("index out of range");
+ }
+
+ return Range(b_ + first, std::min(length, size() - first));
+ }
+
+ // unchecked versions
+ void uncheckedAdvance(size_type n) {
+ DCHECK_LE(n, size());
+ b_ += n;
+ }
+
+ void uncheckedSubtract(size_type n) {
+ DCHECK_LE(n, size());
+ e_ -= n;
+ }
+
+ Range uncheckedSubpiece(size_type first, size_type length = npos) const {
+ DCHECK_LE(first, size());
+ return Range(b_ + first, std::min(length, size() - first));
+ }
+
void pop_front() {
assert(b_ < e_);
++b_;
--e_;
}
- Range subpiece(size_type first, size_type length = npos) const {
- if (UNLIKELY(first > size())) {
- throw std::out_of_range("index out of range");
- }
-
- return Range(b_ + first, std::min(length, size() - first));
- }
-
// string work-alike functions
size_type find(const_range_type str) const {
return qfind(castToConst(), str);
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.
} else if (e == e_) {
e_ = b;
} else {
- throw std::out_of_range("index out of range");
+ std::__throw_out_of_range("index out of 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);
}
* Create a range from two iterators, with type deduction.
*/
template <class Iter>
-Range<Iter> range(Iter first, Iter last) {
+constexpr Range<Iter> range(Iter first, Iter last) {
return Range<Iter>(first, last);
}
* Creates a range to reference the contents of a contiguous-storage container.
*/
// Use pointers for types with '.data()' member
-template <class Collection,
- class T = typename std::remove_pointer<
- decltype(std::declval<Collection>().data())>::type>
-Range<T*> range(Collection&& v) {
+template <
+ class Collection,
+ class T = typename std::remove_pointer<
+ decltype(std::declval<Collection>().data())>::type>
+constexpr Range<T*> range(Collection&& v) {
return Range<T*>(v.data(), v.data() + v.size());
}
template <class T, size_t n>
-Range<T*> range(T (&array)[n]) {
+constexpr Range<T*> range(T (&array)[n]) {
return Range<T*>(array, array + n);
}
+template <class T, size_t n>
+constexpr Range<const T*> range(const std::array<T, n>& array) {
+ return Range<const T*>{array};
+}
+
typedef Range<const char*> StringPiece;
typedef Range<char*> MutableStringPiece;
typedef Range<const unsigned char*> ByteRange;
inline std::ostream& operator<<(std::ostream& os,
const StringPiece piece) {
- os.write(piece.start(), piece.size());
+ os.write(piece.start(), std::streamsize(piece.size()));
return os;
}
inline std::ostream& operator<<(std::ostream& os,
const MutableStringPiece piece) {
- os.write(piece.start(), piece.size());
+ os.write(piece.start(), std::streamsize(piece.size()));
return os;
}
* 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;
}
return StringPiece(lhs) >= StringPiece(rhs);
}
-// Do NOT use this, use SpookyHashV2 instead, see commment on hash() above.
-struct StringPieceHash {
- std::size_t operator()(const StringPiece str) const {
- return static_cast<std::size_t>(str.hash());
- }
-};
-
/**
* 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
// Check if done searching
if (++j == nsize) {
// Yay
- return i - haystack.begin();
+ return size_t(i - haystack.begin());
}
}
}
} // 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;
// specialization for StringPiece
template <>
inline size_t qfind(const Range<const char*>& haystack, const char& needle) {
+ // memchr expects a not-null pointer, early return if the range is empty.
+ if (haystack.empty()) {
+ return std::string::npos;
+ }
auto pos = static_cast<const char*>(
::memchr(haystack.data(), needle, haystack.size()));
return pos == nullptr ? std::string::npos : pos - haystack.data();
template <>
inline size_t rfind(const Range<const char*>& haystack, const char& needle) {
+ // memchr expects a not-null pointer, early return if the range is empty.
+ if (haystack.empty()) {
+ return std::string::npos;
+ }
auto pos = static_cast<const char*>(
::memrchr(haystack.data(), needle, haystack.size()));
return pos == nullptr ? std::string::npos : pos - haystack.data();
template <>
inline size_t qfind(const Range<const unsigned char*>& haystack,
const unsigned char& needle) {
+ // memchr expects a not-null pointer, early return if the range is empty.
+ if (haystack.empty()) {
+ return std::string::npos;
+ }
auto pos = static_cast<const unsigned char*>(
::memchr(haystack.data(), needle, haystack.size()));
return pos == nullptr ? std::string::npos : pos - haystack.data();
template <>
inline size_t rfind(const Range<const unsigned char*>& haystack,
const unsigned char& needle) {
+ // memchr expects a not-null pointer, early return if the range is empty.
+ if (haystack.empty()) {
+ return std::string::npos;
+ }
auto pos = static_cast<const unsigned char*>(
::memrchr(haystack.data(), needle, haystack.size()));
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());
}
}
};
+/**
+ * Ubiquitous helper template for knowing what's a string
+ */
+template <class T> struct IsSomeString {
+ enum { value = std::is_same<T, std::string>::value
+ || std::is_same<T, fbstring>::value };
+};
+
} // !namespace folly
-#pragma GCC diagnostic pop
+FOLLY_POP_WARNING
FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);