/*
- * Copyright 2012 Facebook, Inc.
+ * Copyright 2013 Facebook, Inc.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
#ifndef FOLLY_RANGE_H_
#define FOLLY_RANGE_H_
+#include "folly/Portability.h"
#include "folly/FBString.h"
#include <glog/logging.h>
#include <algorithm>
#include <cstring>
-#include <iostream>
+#include <iosfwd>
#include <string>
#include <stdexcept>
#include <type_traits>
#include <boost/operators.hpp>
-#include <boost/utility/enable_if.hpp>
-#include <boost/type_traits.hpp>
#include <bits/c++config.h>
+#include "folly/CpuId.h"
#include "folly/Traits.h"
+#include "folly/Likely.h"
+
+// Ignore shadowing warnings within this file, so includers can use -Wshadow.
+#pragma GCC diagnostic push
+#pragma GCC diagnostic ignored "-Wshadow"
namespace folly {
* as Boyer-Moore. On the upside, it does not do any upfront
* preprocessing and does not allocate memory.
*/
-template <class T>
+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);
+ const Range<T> & needle,
+ Comp eq = Comp());
/**
* Finds the first occurrence of needle in haystack. The result is the
size_t qfind(const Range<T> & haystack,
const typename Range<T>::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);
+
/**
* Finds the first occurrence of any element of needle in
* For random-access iterators, the value before is simply i[-1].
*/
template <class Iter>
-typename boost::enable_if_c<
- boost::is_same<typename std::iterator_traits<Iter>::iterator_category,
- std::random_access_iterator_tag>::value,
+typename std::enable_if<
+ std::is_same<typename std::iterator_traits<Iter>::iterator_category,
+ std::random_access_iterator_tag>::value,
typename std::iterator_traits<Iter>::reference>::type
value_before(Iter i) {
return i[-1];
* For all other iterators, we need to use the decrement operator.
*/
template <class Iter>
-typename boost::enable_if_c<
- !boost::is_same<typename std::iterator_traits<Iter>::iterator_category,
- std::random_access_iterator_tag>::value,
+typename std::enable_if<
+ !std::is_same<typename std::iterator_traits<Iter>::iterator_category,
+ std::random_access_iterator_tag>::value,
typename std::iterator_traits<Iter>::reference>::type
value_before(Iter i) {
return *--i;
typedef std::size_t size_type;
typedef Iter iterator;
typedef Iter const_iterator;
- typedef typename boost::remove_reference<
+ typedef typename std::remove_reference<
typename std::iterator_traits<Iter>::reference>::type
value_type;
typedef typename std::iterator_traits<Iter>::reference reference;
- typedef std::char_traits<value_type> traits_type;
+ typedef std::char_traits<typename std::remove_const<value_type>::type>
+ traits_type;
static const size_type npos;
Range() : b_(), e_() {
}
-private:
- static bool reachable(Iter b, Iter e, std::forward_iterator_tag) {
- for (; b != e; ++b) {
- LOG_EVERY_N(INFO, 100000) << __FILE__ ":" << __LINE__
- << " running reachability test ("
- << google::COUNTER << " iterations)...";
- }
- return true;
- }
-
- static bool reachable(Iter b, Iter e, std::random_access_iterator_tag) {
- return b <= e;
- }
-
public:
// Works for all iterators
- Range(Iter start, Iter end)
- : b_(start), e_(end) {
- assert(reachable(b_, e_,
- typename std::iterator_traits<Iter>::iterator_category()));
+ Range(Iter start, Iter end) : b_(start), e_(end) {
}
// Works only for random-access iterators
Range(Iter start, size_t size)
: b_(start), e_(start + size) { }
+#if FOLLY_HAVE_CONSTEXPR_STRLEN
+ // Works only for Range<const char*>
+ /* implicit */ constexpr Range(Iter str)
+ : b_(str), e_(str + strlen(str)) {}
+#else
// Works only for Range<const char*>
/* implicit */ Range(Iter str)
- : b_(str), e_(b_ + strlen(str)) {}
+ : b_(str), e_(str + strlen(str)) {}
+#endif
// Works only for Range<const char*>
/* implicit */ Range(const std::string& str)
: b_(str.data()), e_(b_ + str.size()) {}
// Works only for Range<const char*>
Range(const std::string& str, std::string::size_type startFrom) {
- CHECK_LE(startFrom, str.size());
+ if (UNLIKELY(startFrom > str.size())) {
+ throw std::out_of_range("index out of range");
+ }
b_ = str.data() + startFrom;
e_ = str.data() + str.size();
}
Range(const std::string& str,
std::string::size_type startFrom,
std::string::size_type size) {
- CHECK_LE(startFrom + size, str.size());
+ if (UNLIKELY(startFrom > str.size())) {
+ throw std::out_of_range("index out of range");
+ }
b_ = str.data() + startFrom;
- e_ = b_ + size;
+ if (str.size() - startFrom < size) {
+ e_ = str.data() + str.size();
+ } else {
+ e_ = b_ + size;
+ }
}
Range(const Range<Iter>& str,
size_t startFrom,
size_t size) {
- CHECK_LE(startFrom + size, str.size());
+ if (UNLIKELY(startFrom > str.size())) {
+ throw std::out_of_range("index out of range");
+ }
b_ = str.b_ + startFrom;
- e_ = b_ + size;
+ if (str.size() - startFrom < size) {
+ e_ = str.e_;
+ } else {
+ e_ = b_ + size;
+ }
}
// Works only for Range<const char*>
/* implicit */ Range(const fbstring& str)
: b_(str.data()), e_(b_ + str.size()) { }
// Works only for Range<const char*>
Range(const fbstring& str, fbstring::size_type startFrom) {
- CHECK_LE(startFrom, str.size());
+ if (UNLIKELY(startFrom > str.size())) {
+ throw std::out_of_range("index out of range");
+ }
b_ = str.data() + startFrom;
e_ = str.data() + str.size();
}
// Works only for Range<const char*>
Range(const fbstring& str, fbstring::size_type startFrom,
fbstring::size_type size) {
- CHECK_LE(startFrom + size, str.size());
+ if (UNLIKELY(startFrom > str.size())) {
+ throw std::out_of_range("index out of range");
+ }
b_ = str.data() + startFrom;
- e_ = b_ + size;
+ if (str.size() - startFrom < size) {
+ e_ = str.data() + str.size();
+ } else {
+ e_ = b_ + size;
+ }
}
// Allow implicit conversion from Range<const char*> (aka StringPiece) to
}
void advance(size_type n) {
- CHECK_LE(n, size());
+ if (UNLIKELY(n > size())) {
+ throw std::out_of_range("index out of range");
+ }
b_ += n;
}
void subtract(size_type n) {
- CHECK_LE(n, size());
+ if (UNLIKELY(n > size())) {
+ throw std::out_of_range("index out of range");
+ }
e_ -= n;
}
Range subpiece(size_type first,
size_type length = std::string::npos) const {
- CHECK_LE(first, size());
+ if (UNLIKELY(first > size())) {
+ throw std::out_of_range("index out of range");
+ }
return Range(b_ + first,
std::min<std::string::size_type>(length, size() - first));
}
return qfind(*this, c);
}
+ size_type rfind(value_type c) const {
+ return folly::rfind(*this, c);
+ }
+
size_type find(value_type c, size_t pos) const {
if (pos > size()) return std::string::npos;
size_type ret = qfind(subpiece(pos), c);
size_type find_first_of(Range needles, size_t pos) const {
if (pos > size()) return std::string::npos;
- size_type ret = qfind_first_of(pos ? subpiece(pos) : *this, needles);
+ size_type ret = qfind_first_of(subpiece(pos), needles);
return ret == npos ? ret : ret + pos;
}
struct ComparableAsStringPiece {
enum {
value =
- (
boost::is_convertible<A, StringPiece>::value
- && boost::is_same<B, StringPiece>::value)
+ (
std::is_convertible<A, StringPiece>::value
+ && std::is_same<B, StringPiece>::value)
||
- (boost::is_convertible<B, StringPiece>::value
- &&
boost::is_same<A, StringPiece>::value)
+ (std::is_convertible<B, StringPiece>::value
+ &&
std::is_same<A, StringPiece>::value)
};
};
*/
template <class T, class U>
typename
-boost::enable_if_c<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
operator==(const T& lhs, const U& rhs) {
return StringPiece(lhs) == StringPiece(rhs);
}
*/
template <class T, class U>
typename
-boost::enable_if_c<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
operator<(const T& lhs, const U& rhs) {
return StringPiece(lhs) < StringPiece(rhs);
}
*/
template <class T, class U>
typename
-boost::enable_if_c<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
operator>(const T& lhs, const U& rhs) {
return StringPiece(lhs) > StringPiece(rhs);
}
*/
template <class T, class U>
typename
-boost::enable_if_c<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
operator<=(const T& lhs, const U& rhs) {
return StringPiece(lhs) <= StringPiece(rhs);
}
*/
template <class T, class U>
typename
-boost::enable_if_c<detail::ComparableAsStringPiece<T, U>::value, bool>::type
+std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
operator>=(const T& lhs, const U& rhs) {
return StringPiece(lhs) >= StringPiece(rhs);
}
return std::string::npos;
}
+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 =
+ folly::CpuId().sse42() ? qfind_first_byte_of_sse42
+ : qfind_first_byte_of_nosse;
+ 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>
size_t qfind_first_of(const Range<T> & haystack,
- const Range<T> & needle,
+ const Range<T> & needles,
Comp eq) {
auto ret = std::find_first_of(haystack.begin(), haystack.end(),
- needle.begin(), needle.end(),
+ needles.begin(), needles.end(),
eq);
return ret == haystack.end() ? std::string::npos : ret - haystack.begin();
}
template <class T>
size_t qfind(const Range<T>& haystack,
- const Range<T>& needle) {
- return qfind(haystack, needle, asciiCaseSensitive);
+ const typename Range<T>::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 qfind(const Range<T>& haystack,
+size_t rfind(const Range<T>& haystack,
const typename Range<T>::value_type& needle) {
- auto pos = std::find(haystack.begin(), haystack.end(), needle);
- return pos == haystack.end() ? std::string::npos : pos - haystack.data();
+ for (auto i = haystack.size(); i-- > 0; ) {
+ if (haystack[i] == needle) {
+ return i;
+ }
+ }
+ return std::string::npos;
}
// specialization for StringPiece
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) {
+ 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,
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) {
+ 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>& needle) {
- return qfind_first_of(haystack, needle, asciiCaseSensitive);
+ const Range<T>& needles) {
+ return qfind_first_of(haystack, needles, asciiCaseSensitive);
}
+// specialization for StringPiece
+template <>
+inline size_t qfind_first_of(const Range<const char*>& haystack,
+ const Range<const char*>& needles) {
+ return detail::qfind_first_byte_of(haystack, needles);
+}
+
+// specialization for ByteRange
+template <>
+inline size_t qfind_first_of(const Range<const unsigned char*>& haystack,
+ const Range<const unsigned char*>& needles) {
+ return detail::qfind_first_byte_of(StringPiece(haystack),
+ StringPiece(needles));
+}
} // !namespace folly
+#pragma GCC diagnostic pop
+
FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);
#endif // FOLLY_RANGE_H_
projects / folly.git / blobdiff