X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FRange.h;h=1f8c1782188a473c7a7e1de552cfffa9fc093119;hb=9b4749fd47c605c27b6973f317d7c4f3a0e101e9;hp=355b0855326deb902855a097564ec261ffe5500a;hpb=570ec3333e183881ffe326fe64c97605a92008d1;p=folly.git diff --git a/folly/Range.h b/folly/Range.h index 355b0855..1f8c1782 100644 --- a/folly/Range.h +++ b/folly/Range.h @@ -1,5 +1,5 @@ /* - * Copyright 2013 Facebook, Inc. + * Copyright 2014 Facebook, Inc. * * Licensed under the Apache License, Version 2.0 (the "License"); * you may not use this file except in compliance with the License. @@ -20,19 +20,35 @@ #ifndef FOLLY_RANGE_H_ #define FOLLY_RANGE_H_ -#include "folly/folly-config.h" -#include "folly/FBString.h" -#include +#include +#include #include +#include #include +#include #include -#include #include +#include #include -#include + +// 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 +// c++config.h: +// _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to +// gate use inside fbcode v. libstdc++ #include -#include "folly/CpuId.h" -#include "folly/Traits.h" +#endif + +#include +#include +#include + +// Ignore shadowing warnings within this file, so includers can use -Wshadow. +#pragma GCC diagnostic push +#pragma GCC diagnostic ignored "-Wshadow" namespace folly { @@ -44,9 +60,10 @@ template class Range; * as Boyer-Moore. On the upside, it does not do any upfront * preprocessing and does not allocate memory. */ -template +template ::value_type>> inline size_t qfind(const Range & haystack, - const Range & needle); + const Range & needle, + Comp eq = Comp()); /** * Finds the first occurrence of needle in haystack. The result is the @@ -57,6 +74,15 @@ 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); + /** * Finds the first occurrence of any element of needle in @@ -118,32 +144,55 @@ public: typename std::iterator_traits::reference>::type value_type; typedef typename std::iterator_traits::reference reference; - typedef std::char_traits traits_type; + + /** + * 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 + constexpr /* implicit */ Range(Iter str) + : b_(str), e_(str + strlen(str)) {} +#else // Works only for Range /* implicit */ Range(Iter str) - : b_(str), e_(b_ + strlen(str)) {} + : b_(str), e_(str + strlen(str)) {} +#endif // Works only for Range /* implicit */ Range(const std::string& str) : b_(str.data()), e_(b_ + str.size()) {} + // Works only for Range 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(); } @@ -151,32 +200,52 @@ public: 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& 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 /* implicit */ Range(const fbstring& str) : b_(str.data()), e_(b_ + str.size()) { } // Works only for Range 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 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 (aka StringPiece) to @@ -185,20 +254,59 @@ public: // direction. template ::value && - std::is_same::value), int>::type = 0> + (std::is_same::value || + std::is_same::value)), int>::type = 0> /* implicit */ Range(const Range& other) : b_(reinterpret_cast(other.begin())), e_(reinterpret_cast(other.end())) { } + template ::value && + std::is_same::value), int>::type = 0> + /* implicit */ Range(const Range& other) + : b_(reinterpret_cast(other.begin())), + e_(reinterpret_cast(other.end())) { + } + template ::value && - std::is_same::value), int>::type = 0> + (std::is_same::value || + std::is_same::value)), int>::type = 0> explicit Range(const Range& other) : b_(reinterpret_cast(other.begin())), e_(reinterpret_cast(other.end())) { } + template ::value && + std::is_same::value), int>::type = 0> + explicit Range(const Range& other) + : b_(reinterpret_cast(other.begin())), + e_(reinterpret_cast(other.end())) { + } + + // Allow implicit conversion from Range to Range if From is + // implicitly convertible to To. + template ::value && + std::is_convertible::value), int>::type = 0> + constexpr /* implicit */ Range(const Range& other) + : b_(other.begin()), + e_(other.end()) { + } + + // Allow explicit conversion from Range to Range if From is + // explicitly convertible to To. + template ::value && + !std::is_convertible::value && + std::is_constructible::value), int>::type = 0> + constexpr explicit Range(const Range& other) + : b_(other.begin()), + e_(other.end()) { + } + void clear() { b_ = Iter(); e_ = Iter(); @@ -257,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); @@ -268,12 +380,12 @@ public: } value_type& operator[](size_t i) { - CHECK_GT(size(), i); + DCHECK_GT(size(), i); return b_[i]; } const value_type& operator[](size_t i) const { - CHECK_GT(size(), i); + DCHECK_GT(size(), i); return b_[i]; } @@ -299,12 +411,16 @@ public: } 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; } @@ -320,72 +436,80 @@ public: 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(length, size() - first)); } // 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(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 { @@ -396,11 +520,248 @@ 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_); } + /** + * Does this Range start with another range? + */ + 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; + } + + /** + * Does this Range end with another range? + */ + 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; + } + + /** + * Remove the given prefix and return true if the range starts with the given + * prefix; return false otherwise. + */ + bool removePrefix(const const_range_type& prefix) { + return startsWith(prefix) && (b_ += prefix.size(), true); + } + bool removePrefix(value_type prefix) { + return startsWith(prefix) && (++b_, true); + } + + /** + * Remove the given suffix and return true if the range ends with the given + * suffix; return false otherwise. + */ + 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`. + * + * Returns a new `Range` `[b, i)` and adjusts this range to start right after + * the delimiter's position. This range will be empty if the delimiter is not + * found. If called on an empty `Range`, both this and the returned `Range` + * will be empty. + * + * Example: + * + * folly::StringPiece s("sample string for split_next"); + * auto p = s.split_step(' '); + * + * // prints "string for split_next" + * cout << s << endl; + * + * // prints "sample" + * cout << p << endl; + * + * Example 2: + * + * void tokenize(StringPiece s, char delimiter) { + * while (!s.empty()) { + * cout << s.split_step(delimiter); + * } + * } + * + * @author: Marcelo Juchem + */ + Range split_step(value_type delimiter) { + auto i = std::find(b_, e_, delimiter); + Range result(b_, i); + + b_ = i == e_ ? e_ : std::next(i); + + return result; + } + + Range split_step(Range delimiter) { + auto i = find(delimiter); + Range result(b_, i == std::string::npos ? size() : i); + + b_ = result.end() == e_ ? e_ : std::next(result.end(), delimiter.size()); + + return result; + } + + /** + * Convenience method that calls `split_step()` and passes the result to a + * 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: + * + * Foo fn(Range r) { } + * + * `split_step()`'s return type will be `Foo`. It works just like: + * + * auto result = fn(myRange.split_step(' ')); + * + * A functor returning `void` is also supported. + * + * Example: + * + * void do_some_parsing(folly::StringPiece s) { + * auto version = s.split_step(' ', [&](folly::StringPiece x) { + * if (x.empty()) { + * throw std::invalid_argument("empty string"); + * } + * return std::strtoull(x.begin(), x.end(), 16); + * }); + * + * // ... + * } + * + * 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, 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, Args &&...args) + -> decltype(process(std::declval(), std::forward(args)...)) + { return process(split_step(delimiter), std::forward(args)...); } + private: Iter b_, e_; }; @@ -417,14 +778,33 @@ void swap(Range& lhs, Range& rhs) { * Create a range from two iterators, with type deduction. */ template -Range makeRange(Iter first, Iter last) { +Range range(Iter first, Iter last) { return Range(first, 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) { + return Range(v.data(), v.data() + v.size()); +} + +template +Range range(T (&array)[n]) { + return Range(array, array + n); +} + typedef Range StringPiece; +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 MutableStringPiece& piece); /** * Templated comparison operators @@ -580,7 +960,7 @@ namespace detail { size_t qfind_first_byte_of_nosse(const StringPiece& haystack, const StringPiece& needles); -#if FOLLY_HAVE_EMMINTRIN_H +#if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6) size_t qfind_first_byte_of_sse42(const StringPiece& haystack, const StringPiece& needles); @@ -617,9 +997,18 @@ struct AsciiCaseSensitive { } }; +/** + * Check if two ascii characters are case insensitive equal. + * The difference between the lower/upper case characters are the 6-th bit. + * We also check they are alpha chars, in case of xor = 32. + */ struct AsciiCaseInsensitive { bool operator()(char lhs, char rhs) const { - return toupper(lhs) == toupper(rhs); + char k = lhs ^ rhs; + if (k == 0) return true; + if (k != 32) return false; + k = lhs | rhs; + return (k >= 'a' && k <= 'z'); } }; @@ -628,15 +1017,20 @@ extern const AsciiCaseInsensitive asciiCaseInsensitive; template size_t qfind(const Range& haystack, - const Range& needle) { - return qfind(haystack, needle, asciiCaseSensitive); + 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 qfind(const Range& haystack, +size_t rfind(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(); + for (auto i = haystack.size(); i-- > 0; ) { + if (haystack[i] == needle) { + return i; + } + } + return std::string::npos; } // specialization for StringPiece @@ -647,6 +1041,15 @@ inline size_t qfind(const Range& haystack, const char& needle) { return pos == nullptr ? std::string::npos : pos - haystack.data(); } +#if FOLLY_HAVE_MEMRCHR +template <> +inline size_t rfind(const Range& haystack, const char& needle) { + 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, @@ -656,6 +1059,16 @@ inline size_t qfind(const Range& haystack, 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) { + 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) { @@ -678,6 +1091,8 @@ inline size_t qfind_first_of(const Range& haystack, } } // !namespace folly +#pragma GCC diagnostic pop + FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range); #endif // FOLLY_RANGE_H_