X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FRange.h;h=9c9b68b26514712568ab2d1579dbdc5e63beeee3;hb=44ce72fdb5b5dca54f799f62c2e8c7791c2e2fcc;hp=ce235bef18ac0d33721bdfbc722956640cee1ae0;hpb=95ccc564c5c70715ca9d499e93147dc2f8d72b8f;p=folly.git diff --git a/folly/Range.h b/folly/Range.h index ce235bef..9c9b68b2 100644 --- a/folly/Range.h +++ b/folly/Range.h @@ -1,5 +1,5 @@ /* - * Copyright 2015 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. @@ -17,19 +17,22 @@ // @author Mark Rabkin (mrabkin@fb.com) // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com) -#ifndef FOLLY_RANGE_H_ -#define FOLLY_RANGE_H_ +#pragma once -#include #include +#include #include +#include +#include +#include -#include #include +#include +#include +#include #include #include #include -#include #include #include #include @@ -58,7 +61,7 @@ namespace folly { -template class Range; +template class Range; /** * Finds the first occurrence of needle in haystack. The algorithm is on @@ -66,9 +69,10 @@ template class Range; * as Boyer-Moore. On the upside, it does not do any upfront * preprocessing and does not allocate memory. */ -template ::value_type>> -inline size_t qfind(const Range & haystack, - const Range & needle, +template ::value_type>> +inline size_t qfind(const Range & haystack, + const Range & needle, Comp eq = Comp()); /** @@ -76,27 +80,27 @@ inline size_t qfind(const Range & haystack, * offset reported to the beginning of haystack, or string::npos if * needle wasn't found. */ -template -size_t qfind(const Range & haystack, - const typename Range::value_type& needle); +template +size_t qfind(const Range & haystack, + const typename Range::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 -size_t rfind(const Range & haystack, - const typename Range::value_type& needle); +template +size_t rfind(const Range & haystack, + const typename Range::value_type& needle); /** * Finds the first occurrence of any element of needle in * haystack. The algorithm is O(haystack.size() * needle.size()). */ -template -inline size_t qfind_first_of(const Range & haystack, - const Range & needle); +template +inline size_t qfind_first_of(const Range & haystack, + const Range & needle); /** * Small internal helper - returns the value just before an iterator. @@ -166,6 +170,7 @@ public: typedef typename std::remove_reference< typename std::iterator_traits::reference>::type value_type; + using difference_type = typename std::iterator_traits::difference_type; typedef typename std::iterator_traits::reference reference; /** @@ -201,9 +206,7 @@ public: 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 ::type = 0> constexpr /* implicit */ Range(Iter str) @@ -216,7 +219,7 @@ public: template ::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(); @@ -227,7 +230,7 @@ public: 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) { @@ -250,7 +253,7 @@ public: template ::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(); @@ -260,7 +263,7 @@ public: 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) { @@ -329,6 +332,30 @@ public: 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 or a std::array + */ + template < + class T, + size_t N, + typename = typename std::enable_if< + std::is_convertible::value>::type> + constexpr explicit Range(const std::array& 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::value>::type> + constexpr explicit Range(std::array& 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; @@ -352,21 +379,39 @@ public: reset(str.data(), str.size()); } - size_type size() const { - assert(b_ <= e_); - return e_ - b_; + 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 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_; } - size_type walk_size() const { - assert(b_ <= e_); - return std::distance(b_, e_); + 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_; } - 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_; } value_type& front() { assert(b_ < e_); return *b_; @@ -392,7 +437,7 @@ public: const_range_type castToConst() const { return const_range_type(*this); - }; + } // Works only for Range and Range int compare(const const_range_type& o) const { @@ -421,12 +466,12 @@ public: } 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]; } @@ -436,6 +481,19 @@ public: // (The above advice does not apply if you are targeting a 32-bit system.) // // Works only for Range and Range + // + // + // ** 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 @@ -448,18 +506,42 @@ public: 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_; @@ -470,14 +552,6 @@ public: --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); @@ -584,6 +658,16 @@ public: return !empty() && front() == c; } + template + 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(eq)); + } + /** * Does this Range end with another range? */ @@ -595,6 +679,32 @@ public: return !empty() && back() == c; } + template + 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(eq)); + } + + /** + * 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. @@ -720,7 +830,12 @@ public: 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::difference_type( + delimiter.size())); return result; } @@ -804,8 +919,8 @@ private: template const typename Range::size_type Range::npos = std::string::npos; -template -void swap(Range& lhs, Range& rhs) { +template +void swap(Range& lhs, Range& rhs) { lhs.swap(rhs); } @@ -813,7 +928,7 @@ void swap(Range& lhs, Range& rhs) { * Create a range from two iterators, with type deduction. */ template -Range range(Iter first, Iter last) { +constexpr Range range(Iter first, Iter last) { return Range(first, last); } @@ -821,18 +936,24 @@ Range range(Iter first, Iter last) { * Creates a range to reference the contents of a contiguous-storage container. */ // Use pointers for types with '.data()' member -template ().data())>::type> -Range range(Collection&& v) { +template < + class Collection, + class T = typename std::remove_pointer< + decltype(std::declval().data())>::type> +constexpr Range range(Collection&& v) { return Range(v.data(), v.data() + v.size()); } template -Range range(T (&array)[n]) { +constexpr Range range(T (&array)[n]) { return Range(array, array + n); } +template +constexpr Range range(const std::array& array) { + return Range{array}; +} + typedef Range StringPiece; typedef Range MutableStringPiece; typedef Range ByteRange; @@ -840,13 +961,13 @@ typedef Range MutableByteRange; 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; } @@ -854,13 +975,13 @@ inline std::ostream& operator<<(std::ostream& os, * Templated comparison operators */ -template -inline bool operator==(const Range& lhs, const Range& rhs) { +template +inline bool operator==(const Range& lhs, const Range& rhs) { return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; } -template -inline bool operator<(const Range& lhs, const Range& rhs) { +template +inline bool operator<(const Range& lhs, const Range& rhs) { return lhs.compare(rhs) < 0; } @@ -934,19 +1055,12 @@ operator>=(const T& lhs, const U& rhs) { 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(str.hash()); - } -}; - /** * Finds substrings faster than brute force by borrowing from Boyer-Moore */ -template -size_t qfind(const Range& haystack, - const Range& needle, +template +size_t qfind(const Range& haystack, + const Range& needle, Comp eq) { // Don't use std::search, use a Boyer-Moore-like trick by comparing // the last characters first @@ -993,7 +1107,7 @@ size_t qfind(const Range& haystack, // Check if done searching if (++j == nsize) { // Yay - return i - haystack.begin(); + return size_t(i - haystack.begin()); } } } @@ -1012,9 +1126,9 @@ inline size_t qfind_first_byte_of(const StringPiece haystack, } // namespace detail -template -size_t qfind_first_of(const Range & haystack, - const Range & needles, +template +size_t qfind_first_of(const Range & haystack, + const Range & needles, Comp eq) { auto ret = std::find_first_of(haystack.begin(), haystack.end(), needles.begin(), needles.end(), @@ -1043,16 +1157,16 @@ struct AsciiCaseInsensitive { } }; -template -size_t qfind(const Range& haystack, - const typename Range::value_type& needle) { +template +size_t qfind(const Range& haystack, + const typename Range::value_type& needle) { auto pos = std::find(haystack.begin(), haystack.end(), needle); return pos == haystack.end() ? std::string::npos : pos - haystack.data(); } -template -size_t rfind(const Range& haystack, - const typename Range::value_type& needle) { +template +size_t rfind(const Range& haystack, + const typename Range::value_type& needle) { for (auto i = haystack.size(); i-- > 0; ) { if (haystack[i] == needle) { return i; @@ -1064,42 +1178,54 @@ size_t rfind(const Range& haystack, // specialization for StringPiece template <> inline size_t qfind(const Range& 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( ::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& 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( ::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& 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( ::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& 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( ::memrchr(haystack.data(), needle, haystack.size())); return pos == nullptr ? std::string::npos : pos - haystack.data(); } -#endif -template -size_t qfind_first_of(const Range& haystack, - const Range& needles) { +template +size_t qfind_first_of(const Range& haystack, + const Range& needles) { return qfind_first_of(haystack, needles, AsciiCaseSensitive()); } @@ -1129,10 +1255,16 @@ struct hasher, } }; +/** + * Ubiquitous helper template for knowing what's a string + */ +template struct IsSomeString { + enum { value = std::is_same::value + || std::is_same::value }; +}; + } // !namespace folly #pragma GCC diagnostic pop FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range); - -#endif // FOLLY_RANGE_H_