X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FRange.h;h=f61c76e9d4b577bad5d072d6d2cddc605f0815c2;hb=8b05be27769e2e3d5d1681251953506c22f76b45;hp=daca42c97202207e8269296c64fa097a1f41e26e;hpb=10a3632117951cb83334903385d13a176e8ce14e;p=folly.git diff --git a/folly/Range.h b/folly/Range.h index daca42c9..f61c76e9 100644 --- a/folly/Range.h +++ b/folly/Range.h @@ -20,8 +20,8 @@ #ifndef FOLLY_RANGE_H_ #define FOLLY_RANGE_H_ -#include "folly/Portability.h" -#include "folly/FBString.h" +#include +#include #include #include #include @@ -31,8 +31,8 @@ #include #include -// libc++ doesn't provide this header -#if !FOLLY_USE_LIBCPP +// libc++ doesn't provide this header, nor does msvc +#ifdef FOLLY_HAVE_BITS_CXXCONFIG_H // This file appears in two locations: inside fbcode and in the // libstdc++ source code (when embedding fbstring as std::string). // To aid in this schizophrenic use, two macros are defined in @@ -42,9 +42,9 @@ #include #endif -#include "folly/CpuId.h" -#include "folly/Traits.h" -#include "folly/Likely.h" +#include +#include +#include // Ignore shadowing warnings within this file, so includers can use -Wshadow. #pragma GCC diagnostic push @@ -144,27 +144,40 @@ public: typename std::iterator_traits::reference>::type value_type; typedef typename std::iterator_traits::reference reference; + + /** + * For MutableStringPiece and MutableByteRange we define StringPiece + * and ByteRange as const_range_type (for everything else its just + * identity). We do that to enable operations such as find with + * args which are const. + */ + typedef typename std::conditional< + std::is_same::value + || std::is_same::value, + Range, + Range>::type const_range_type; + typedef std::char_traits::type> traits_type; static const size_type npos; // Works for all iterators - Range() : b_(), e_() { + constexpr Range() : b_(), e_() { } public: // Works for all iterators - Range(Iter start, Iter end) : b_(start), e_(end) { + constexpr Range(Iter start, Iter end) : b_(start), e_(end) { } // Works only for random-access iterators - Range(Iter start, size_t size) + constexpr Range(Iter start, size_t size) : b_(start), e_(start + size) { } #if FOLLY_HAVE_CONSTEXPR_STRLEN // Works only for Range - /* implicit */ constexpr Range(Iter str) + constexpr /* implicit */ Range(Iter str) : b_(str), e_(str + strlen(str)) {} #else // Works only for Range @@ -278,7 +291,7 @@ public: template ::value && std::is_convertible::value), int>::type = 0> - /* implicit */ Range(const Range& other) + constexpr /* implicit */ Range(const Range& other) : b_(other.begin()), e_(other.end()) { } @@ -289,7 +302,7 @@ public: (!std::is_same::value && !std::is_convertible::value && std::is_constructible::value), int>::type = 0> - explicit Range(const Range& other) + constexpr explicit Range(const Range& other) : b_(other.begin()), e_(other.end()) { } @@ -352,8 +365,12 @@ public: fbstring fbstr() const { return fbstring(b_, size()); } fbstring toFbstring() const { return fbstr(); } - // Works only for Range - int compare(const Range& o) const { + const_range_type castToConst() const { + return const_range_type(*this); + }; + + // Works only for Range (and Range) + int compare(const const_range_type& o) const { const size_type tsize = this->size(); const size_type osize = o.size(); const size_type msize = std::min(tsize, osize); @@ -427,70 +444,72 @@ public: } // string work-alike functions - size_type find(Range str) const { - return qfind(*this, str); + size_type find(const_range_type str) const { + return qfind(castToConst(), str); } - size_type find(Range str, size_t pos) const { + size_type find(const_range_type str, size_t pos) const { if (pos > size()) return std::string::npos; - size_t ret = qfind(subpiece(pos), str); + size_t ret = qfind(castToConst().subpiece(pos), str); return ret == npos ? ret : ret + pos; } size_type find(Iter s, size_t pos, size_t n) const { if (pos > size()) return std::string::npos; - size_t ret = qfind(pos ? subpiece(pos) : *this, Range(s, n)); + auto forFinding = castToConst(); + size_t ret = qfind( + pos ? forFinding.subpiece(pos) : forFinding, const_range_type(s, n)); return ret == npos ? ret : ret + pos; } - // Works only for Range which have Range(Iter) ctor + // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor size_type find(const Iter s) const { - return qfind(*this, Range(s)); + return qfind(castToConst(), const_range_type(s)); } - // Works only for Range which have Range(Iter) ctor + // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor size_type find(const Iter s, size_t pos) const { if (pos > size()) return std::string::npos; - size_type ret = qfind(subpiece(pos), Range(s)); + size_type ret = qfind(castToConst().subpiece(pos), const_range_type(s)); return ret == npos ? ret : ret + pos; } size_type find(value_type c) const { - return qfind(*this, c); + return qfind(castToConst(), c); } size_type rfind(value_type c) const { - return folly::rfind(*this, c); + return folly::rfind(castToConst(), 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 ret = qfind(castToConst().subpiece(pos), c); return ret == npos ? ret : ret + pos; } - size_type find_first_of(Range needles) const { - return qfind_first_of(*this, needles); + size_type find_first_of(const_range_type needles) const { + return qfind_first_of(castToConst(), needles); } - size_type find_first_of(Range needles, size_t pos) const { + size_type find_first_of(const_range_type needles, size_t pos) const { if (pos > size()) return std::string::npos; - size_type ret = qfind_first_of(subpiece(pos), needles); + size_type ret = qfind_first_of(castToConst().subpiece(pos), needles); return ret == npos ? ret : ret + pos; } - // Works only for Range which have Range(Iter) ctor + // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor size_type find_first_of(Iter needles) const { - return find_first_of(Range(needles)); + return find_first_of(const_range_type(needles)); } - // Works only for Range which have Range(Iter) ctor + // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor size_type find_first_of(Iter needles, size_t pos) const { - return find_first_of(Range(needles), pos); + return find_first_of(const_range_type(needles), pos); } size_type find_first_of(Iter needles, size_t pos, size_t n) const { - return find_first_of(Range(needles, n), pos); + return find_first_of(const_range_type(needles, n), pos); } size_type find_first_of(value_type c) const { @@ -501,6 +520,19 @@ public: return find(c, pos); } + /** + * Determine whether the range contains the given subrange or item. + * + * Note: Call find() directly if the index is needed. + */ + bool contains(const const_range_type& other) const { + return find(other) != std::string::npos; + } + + bool contains(const value_type& other) const { + return find(other) != std::string::npos; + } + void swap(Range& rhs) { std::swap(b_, rhs.b_); std::swap(e_, rhs.e_); @@ -509,8 +541,9 @@ public: /** * Does this Range start with another range? */ - bool startsWith(const Range& other) const { - return size() >= other.size() && subpiece(0, other.size()) == other; + bool startsWith(const const_range_type& other) const { + return size() >= other.size() + && castToConst().subpiece(0, other.size()) == other; } bool startsWith(value_type c) const { return !empty() && front() == c; @@ -519,8 +552,9 @@ public: /** * Does this Range end with another range? */ - bool endsWith(const Range& other) const { - return size() >= other.size() && subpiece(size() - other.size()) == other; + bool endsWith(const const_range_type& other) const { + return size() >= other.size() + && castToConst().subpiece(size() - other.size()) == other; } bool endsWith(value_type c) const { return !empty() && back() == c; @@ -530,7 +564,7 @@ public: * Remove the given prefix and return true if the range starts with the given * prefix; return false otherwise. */ - bool removePrefix(const Range& prefix) { + bool removePrefix(const const_range_type& prefix) { return startsWith(prefix) && (b_ += prefix.size(), true); } bool removePrefix(value_type prefix) { @@ -541,13 +575,73 @@ public: * Remove the given suffix and return true if the range ends with the given * suffix; return false otherwise. */ - bool removeSuffix(const Range& suffix) { + bool removeSuffix(const const_range_type& suffix) { return endsWith(suffix) && (e_ -= suffix.size(), true); } bool removeSuffix(value_type suffix) { return endsWith(suffix) && (--e_, true); } + /** + * Replaces the content of the range, starting at position 'pos', with + * contents of 'replacement'. Entire 'replacement' must fit into the + * range. Returns false if 'replacements' does not fit. Example use: + * + * char in[] = "buffer"; + * auto msp = MutablesStringPiece(input); + * EXPECT_TRUE(msp.replaceAt(2, "tt")); + * EXPECT_EQ(msp, "butter"); + * + * // not enough space + * EXPECT_FALSE(msp.replace(msp.size() - 1, "rr")); + * EXPECT_EQ(msp, "butter"); // unchanged + */ + bool replaceAt(size_t pos, const_range_type replacement) { + if (size() < pos + replacement.size()) { + return false; + } + + std::copy(replacement.begin(), replacement.end(), begin() + pos); + + return true; + } + + /** + * Replaces all occurences of 'source' with 'dest'. Returns number + * of replacements made. Source and dest have to have the same + * length. Throws if the lengths are different. If 'source' is a + * pattern that is overlapping with itself, we perform sequential + * replacement: "aaaaaaa".replaceAll("aa", "ba") --> "bababaa" + * + * Example use: + * + * char in[] = "buffer"; + * auto msp = MutablesStringPiece(input); + * EXPECT_EQ(msp.replaceAll("ff","tt"), 1); + * EXPECT_EQ(msp, "butter"); + */ + size_t replaceAll(const_range_type source, const_range_type dest) { + if (source.size() != dest.size()) { + throw std::invalid_argument( + "replacement must have the same size as source"); + } + + if (dest.empty()) { + return 0; + } + + size_t pos = 0; + size_t num_replaced = 0; + size_type found = std::string::npos; + while ((found = find(source, pos)) != std::string::npos) { + replaceAt(found, dest); + pos += source.size(); + ++num_replaced; + } + + return num_replaced; + } + /** * Splits this `Range` `[b, e)` in the position `i` dictated by the next * occurence of `delimiter`. @@ -562,10 +656,10 @@ public: * folly::StringPiece s("sample string for split_next"); * auto p = s.split_step(' '); * - * // prints "sample" + * // prints "string for split_next" * cout << s << endl; * - * // prints "string for split_next" + * // prints "sample" * cout << p << endl; * * Example 2: @@ -598,7 +692,8 @@ public: /** * Convenience method that calls `split_step()` and passes the result to a - * functor, returning whatever the functor does. + * functor, returning whatever the functor does. Any additional arguments + * `args` passed to this function are perfectly forwarded to the functor. * * Say you have a functor with this signature: * @@ -623,17 +718,49 @@ public: * // ... * } * + * struct Foo { + * void parse(folly::StringPiece s) { + * s.split_step(' ', parse_field, bar, 10); + * s.split_step('\t', parse_field, baz, 20); + * + * auto const kludge = [](folly::StringPiece x, int &out, int def) { + * if (x == "null") { + * out = 0; + * } else { + * parse_field(x, out, def); + * } + * }; + * + * s.split_step('\t', kludge, gaz); + * s.split_step(' ', kludge, foo); + * } + * + * private: + * int bar; + * int baz; + * int gaz; + * int foo; + * + * static parse_field(folly::StringPiece s, int &out, int def) { + * try { + * out = folly::to(s); + * } catch (std::exception const &) { + * value = def; + * } + * } + * }; + * * @author: Marcelo Juchem */ - template - auto split_step(value_type delimiter, TProcess &&process) - -> decltype(process(std::declval())) - { return process(split_step(delimiter)); } + template + auto split_step(value_type delimiter, TProcess &&process, Args &&...args) + -> decltype(process(std::declval(), std::forward(args)...)) + { return process(split_step(delimiter), std::forward(args)...); } - template - auto split_step(Range delimiter, TProcess &&process) - -> decltype(process(std::declval())) - { return process(split_step(delimiter)); } + template + auto split_step(Range delimiter, TProcess &&process, Args &&...args) + -> decltype(process(std::declval(), std::forward(args)...)) + { return process(split_step(delimiter), std::forward(args)...); } private: Iter b_, e_; @@ -676,7 +803,8 @@ typedef Range MutableStringPiece; typedef Range ByteRange; typedef Range MutableByteRange; -std::ostream& operator<<(std::ostream& os, const StringPiece& piece); +std::ostream& operator<<(std::ostream& os, const StringPiece piece); +std::ostream& operator<<(std::ostream& os, const MutableStringPiece piece); /** * Templated comparison operators @@ -763,7 +891,7 @@ operator>=(const T& lhs, const U& rhs) { } struct StringPieceHash { - std::size_t operator()(const StringPiece& str) const { + std::size_t operator()(const StringPiece str) const { return static_cast(str.hash()); } }; @@ -829,15 +957,15 @@ size_t qfind(const Range& haystack, namespace detail { -size_t qfind_first_byte_of_nosse(const StringPiece& haystack, - const StringPiece& needles); +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); +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) { +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; @@ -845,8 +973,8 @@ inline size_t qfind_first_byte_of(const StringPiece& haystack, } #else -inline size_t qfind_first_byte_of(const StringPiece& haystack, - const StringPiece& needles) { +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