X-Git-Url: http://plrg.eecs.uci.edu/git/?p=folly.git;a=blobdiff_plain;f=folly%2FRange.h;h=4a06491684549db077af179fb49270e4223375f8;hp=1d904faf8350419048a0a2c5c36233f6447b5c47;hb=8cb615a27594078056b2e4ec2350660e594f5a89;hpb=0598f628ecebc247ee37a7f566aea9c914045d26

diff --git a/folly/Range.h b/folly/Range.h
index 1d904faf..4a064916 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,14 +17,18 @@
 // @author Mark Rabkin (mrabkin@fb.com)
 // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
 
-#ifndef FOLLY_RANGE_H_
-#define FOLLY_RANGE_H_
+#pragma once
 
-#include <folly/Portability.h>
 #include <folly/FBString.h>
+#include <folly/Portability.h>
+#include <folly/SpookyHashV2.h>
+#include <folly/portability/Constexpr.h>
+#include <folly/portability/String.h>
+
 #include <algorithm>
 #include <boost/operators.hpp>
 #include <climits>
+#include <cstddef>
 #include <cstring>
 #include <glog/logging.h>
 #include <iosfwd>
@@ -46,6 +50,8 @@
 #include <folly/CpuId.h>
 #include <folly/Traits.h>
 #include <folly/Likely.h>
+#include <folly/detail/RangeCommon.h>
+#include <folly/detail/RangeSse42.h>
 
 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
 #pragma GCC diagnostic push
@@ -184,6 +190,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) {
@@ -193,15 +202,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 <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
   constexpr /* implicit */ Range(Iter str)
-      : b_(str), e_(str + strlen(str)) {}
-#else
-  template <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
-  /* implicit */ Range(Iter str)
-      : b_(str), e_(str + strlen(str)) {}
-#endif
+      : b_(str), e_(str + constexpr_strlen(str)) {}
+
   template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
   /* implicit */ Range(const std::string& str)
       : b_(str.data()), e_(b_ + str.size()) {}
@@ -322,6 +330,9 @@ public:
       e_(other.end()) {
   }
 
+  Range& operator=(const Range& rhs) & = default;
+  Range& operator=(Range&& rhs) & = default;
+
   void clear() {
     b_ = Iter();
     e_ = Iter();
@@ -342,12 +353,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_; }
@@ -420,6 +435,11 @@ public:
     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<const char*> and Range<char*>
   uint32_t hash() const {
     // Taken from fbi/nstring.h:
@@ -580,6 +600,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 {
+      throw std::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.
@@ -823,8 +859,17 @@ typedef Range<char*> MutableStringPiece;
 typedef Range<const unsigned char*> ByteRange;
 typedef Range<unsigned char*> 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
@@ -910,6 +955,7 @@ 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<std::size_t>(str.hash());
@@ -977,13 +1023,6 @@ size_t qfind(const Range<T>& 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 =
@@ -992,13 +1031,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 <class T, class Comp>
@@ -1032,9 +1064,6 @@ struct AsciiCaseInsensitive {
   }
 };
 
-extern const AsciiCaseSensitive asciiCaseSensitive;
-extern const AsciiCaseInsensitive asciiCaseInsensitive;
-
 template <class T>
 size_t qfind(const Range<T>& haystack,
              const typename Range<T>::value_type& needle) {
@@ -1061,14 +1090,12 @@ inline size_t qfind(const Range<const char*>& haystack, const char& needle) {
   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 <>
@@ -1079,7 +1106,6 @@ 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) {
@@ -1087,12 +1113,11 @@ inline size_t rfind(const Range<const unsigned char*>& haystack,
     ::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>& needles) {
-  return qfind_first_of(haystack, needles, asciiCaseSensitive);
+  return qfind_first_of(haystack, needles, AsciiCaseSensitive());
 }
 
 // specialization for StringPiece
@@ -1109,10 +1134,20 @@ inline size_t qfind_first_of(const Range<const unsigned char*>& haystack,
   return detail::qfind_first_byte_of(StringPiece(haystack),
                                      StringPiece(needles));
 }
+
+template<class Key, class Enable>
+struct hasher;
+
+template <class T>
+struct hasher<folly::Range<T*>,
+              typename std::enable_if<std::is_pod<T>::value, void>::type> {
+  size_t operator()(folly::Range<T*> r) const {
+    return hash::SpookyHashV2::Hash64(r.begin(), r.size() * sizeof(T), 0);
+  }
+};
+
 }  // !namespace folly
 
 #pragma GCC diagnostic pop
 
 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);
-
-#endif // FOLLY_RANGE_H_