X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FRange.h;h=97a7f1d082ba213f6c2025a855199bb171bdd00d;hb=c495dd260d76ece28f44033a5c151d3c1ce747bd;hp=2ce83f8d6d0f068e25b7c3e0ebcd6e1d9f947132;hpb=80702b5d1ad84dd21cfa7c023810ec2c36991307;p=folly.git diff --git a/folly/Range.h b/folly/Range.h index 2ce83f8d..97a7f1d0 100644 --- a/folly/Range.h +++ b/folly/Range.h @@ -1,5 +1,5 @@ /* - * 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. @@ -17,13 +17,19 @@ // @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 @@ -45,6 +51,8 @@ #include #include #include +#include +#include // Ignore shadowing warnings within this file, so includers can use -Wshadow. #pragma GCC diagnostic push @@ -183,6 +191,9 @@ public: 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) { @@ -192,15 +203,14 @@ public: 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 ::type = 0> constexpr /* implicit */ Range(Iter str) - : b_(str), e_(str + strlen(str)) {} -#else - template ::type = 0> - /* implicit */ Range(Iter str) - : b_(str), e_(str + strlen(str)) {} -#endif + : b_(str), e_(str + constexpr_strlen(str)) {} + template ::const_type = 0> /* implicit */ Range(const std::string& str) : b_(str.data()), e_(b_ + str.size()) {} @@ -208,7 +218,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(); @@ -219,7 +229,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) { @@ -242,7 +252,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(); @@ -252,7 +262,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) { @@ -321,6 +331,9 @@ public: e_(other.end()) { } + Range& operator=(const Range& rhs) & = default; + Range& operator=(Range&& rhs) & = default; + void clear() { b_ = Iter(); e_ = Iter(); @@ -341,12 +354,16 @@ public: 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_; } @@ -410,16 +427,34 @@ 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]; } + // 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 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 @@ -432,18 +467,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_; @@ -454,14 +513,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); @@ -579,6 +630,22 @@ public: 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. @@ -822,8 +889,17 @@ 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); +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 @@ -909,12 +985,6 @@ operator>=(const T& lhs, const U& rhs) { return StringPiece(lhs) >= StringPiece(rhs); } -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 */ @@ -976,13 +1046,6 @@ size_t qfind(const Range& haystack, 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 = @@ -991,13 +1054,6 @@ inline size_t qfind_first_byte_of(const StringPiece haystack, 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 @@ -1031,9 +1087,6 @@ struct AsciiCaseInsensitive { } }; -extern const AsciiCaseSensitive asciiCaseSensitive; -extern const AsciiCaseInsensitive asciiCaseInsensitive; - template size_t qfind(const Range& haystack, const typename Range::value_type& needle) { @@ -1055,43 +1108,55 @@ 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) { - return qfind_first_of(haystack, needles, asciiCaseSensitive); + return qfind_first_of(haystack, needles, AsciiCaseSensitive()); } // specialization for StringPiece @@ -1108,10 +1173,28 @@ inline size_t qfind_first_of(const Range& haystack, return detail::qfind_first_byte_of(StringPiece(haystack), StringPiece(needles)); } + +template +struct hasher; + +template +struct hasher, + typename std::enable_if::value, void>::type> { + size_t operator()(folly::Range r) const { + return hash::SpookyHashV2::Hash64(r.begin(), r.size() * sizeof(T), 0); + } +}; + +/** + * 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_