/*
- * Copyright 2014 Facebook, Inc.
+ * Copyright 2016 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
// @author Mark Rabkin (mrabkin@fb.com)
// @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
-#ifndef FOLLY_RANGE_H_
-#define FOLLY_RANGE_H_
+#pragma once
-#include <folly/Portability.h>
#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 <climits>
+#include <cstddef>
#include <cstring>
#include <glog/logging.h>
#include <iosfwd>
#include <folly/CpuId.h>
#include <folly/Traits.h>
#include <folly/Likely.h>
+#include <folly/detail/RangeCommon.h>
+#include <folly/detail/RangeSse42.h>
// Ignore shadowing warnings within this file, so includers can use -Wshadow.
#pragma GCC diagnostic push
constexpr Range() : b_(), e_() {
}
+ constexpr Range(const Range&) = default;
+ constexpr Range(Range&&) = default;
+
public:
// Works for all iterators
constexpr Range(Iter start, Iter end) : b_(start), e_(end) {
constexpr Range(Iter start, size_t size)
: b_(start), e_(start + size) { }
-#if FOLLY_HAVE_CONSTEXPR_STRLEN
+# 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)
- : b_(str), e_(str + strlen(str)) {}
-#else
- template <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
- /* implicit */ Range(Iter str)
- : b_(str), e_(str + strlen(str)) {}
-#endif
+ : b_(str), e_(str + constexpr_strlen(str)) {}
+
template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
/* implicit */ Range(const std::string& str)
: b_(str.data()), e_(b_ + str.size()) {}
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()) {
}
+ Range& operator=(const Range& rhs) & = default;
+ Range& operator=(Range&& rhs) & = default;
+
void clear() {
b_ = Iter();
e_ = Iter();
reset(str.data(), str.size());
}
- size_type size() const {
- assert(b_ <= e_);
+ constexpr size_type size() const {
+ // It would be nice to assert(b_ <= e_) here. This can be achieved even
+ // in a C++11 compatible constexpr function:
+ // http://ericniebler.com/2014/09/27/assert-and-constexpr-in-cxx11/
+ // 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 {
- assert(b_ <= e_);
return std::distance(b_, e_);
}
bool empty() const { return b_ == e_; }
const size_type osize = o.size();
const size_type msize = std::min(tsize, osize);
int r = traits_type::compare(data(), o.data(), msize);
- if (r == 0) r = tsize - osize;
+ if (r == 0 && tsize != osize) {
+ // We check the signed bit of the subtraction and bit shift it
+ // to produce either 0 or 2. The subtraction yields the
+ // comparison values of either -1 or 1.
+ r = (static_cast<int>(
+ (osize - tsize) >> (CHAR_BIT * sizeof(size_t) - 1)) << 1) - 1;
+ }
return r;
}
}
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];
}
+ // Do NOT use this function, which was left behind for backwards
+ // compatibility. Use SpookyHashV2 instead -- it is faster, and produces
+ // a 64-bit hash, which means dramatically fewer collisions in large maps.
+ // (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() && back() == c;
}
+ /**
+ * Remove the items in [b, e), as long as this subrange is at the beginning
+ * or end of the Range.
+ *
+ * Required for boost::algorithm::trim()
+ */
+ void erase(Iter b, Iter e) {
+ if (b == b_) {
+ b_ = e;
+ } else if (e == e_) {
+ e_ = b;
+ } else {
+ std::__throw_out_of_range("index out of range");
+ }
+ }
+
/**
* Remove the given prefix and return true if the range starts with the given
* prefix; return false otherwise.
typedef Range<const unsigned char*> ByteRange;
typedef Range<unsigned char*> MutableByteRange;
-std::ostream& operator<<(std::ostream& os, const StringPiece piece);
-std::ostream& operator<<(std::ostream& os, const MutableStringPiece piece);
+inline std::ostream& operator<<(std::ostream& os,
+ const StringPiece piece) {
+ os.write(piece.start(), piece.size());
+ return os;
+}
+
+inline std::ostream& operator<<(std::ostream& os,
+ const MutableStringPiece piece) {
+ os.write(piece.start(), piece.size());
+ return os;
+}
/**
* Templated comparison operators
return StringPiece(lhs) >= StringPiece(rhs);
}
-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
*/
namespace detail {
-size_t qfind_first_byte_of_nosse(const StringPiece haystack,
- const StringPiece needles);
-
-#if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
-size_t qfind_first_byte_of_sse42(const StringPiece haystack,
- const StringPiece needles);
-
inline size_t qfind_first_byte_of(const StringPiece haystack,
const StringPiece needles) {
static auto const qfind_first_byte_of_fn =
return qfind_first_byte_of_fn(haystack, needles);
}
-#else
-inline size_t qfind_first_byte_of(const StringPiece haystack,
- const StringPiece needles) {
- return qfind_first_byte_of_nosse(haystack, needles);
-}
-#endif // FOLLY_HAVE_EMMINTRIN_H
-
} // namespace detail
template <class T, class Comp>
}
};
-extern const AsciiCaseSensitive asciiCaseSensitive;
-extern const AsciiCaseInsensitive asciiCaseInsensitive;
-
template <class T>
size_t qfind(const Range<T>& haystack,
const typename Range<T>::value_type& needle) {
// 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();
}
-#if FOLLY_HAVE_MEMRCHR
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();
}
-#endif
// specialization for ByteRange
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();
}
-#if FOLLY_HAVE_MEMRCHR
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();
}
-#endif
template <class T>
size_t qfind_first_of(const Range<T>& haystack,
const Range<T>& needles) {
- return qfind_first_of(haystack, needles, asciiCaseSensitive);
+ return qfind_first_of(haystack, needles, AsciiCaseSensitive());
}
// specialization for StringPiece
return detail::qfind_first_byte_of(StringPiece(haystack),
StringPiece(needles));
}
+
+template<class Key, class Enable>
+struct hasher;
+
+template <class T>
+struct hasher<folly::Range<T*>,
+ typename std::enable_if<std::is_pod<T>::value, void>::type> {
+ size_t operator()(folly::Range<T*> r) const {
+ return hash::SpookyHashV2::Hash64(r.begin(), r.size() * sizeof(T), 0);
+ }
+};
+
+/**
+ * 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_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);
-
-#endif // FOLLY_RANGE_H_
projects / folly.git / blobdiff