X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=folly%2FRange.h;h=0076b07923bbb902bdc4b01266db8ca03f449da1;hb=e8d259542762e9611ce98724b14510c88dfa91dd;hp=8ab8ae5769869fa060f8793bf0d45468cb8ed8be;hpb=108473868b7d543fcb4f7108cbcc75dc871cd833;p=folly.git

diff --git a/folly/Range.h b/folly/Range.h
index 8ab8ae57..0076b079 100644
--- a/folly/Range.h
+++ b/folly/Range.h
@@ -1,5 +1,5 @@
 /*
- * Copyright 2016 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.
@@ -26,12 +26,13 @@
 #include <folly/portability/Constexpr.h>
 #include <folly/portability/String.h>
 
-#include <algorithm>
 #include <boost/operators.hpp>
+#include <glog/logging.h>
+#include <algorithm>
+#include <array>
 #include <climits>
 #include <cstddef>
 #include <cstring>
-#include <glog/logging.h>
 #include <iosfwd>
 #include <stdexcept>
 #include <string>
@@ -55,12 +56,12 @@
 #include <folly/detail/RangeSse42.h>
 
 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
-#pragma GCC diagnostic push
-#pragma GCC diagnostic ignored "-Wshadow"
+FOLLY_PUSH_WARNING
+FOLLY_GCC_DISABLE_WARNING("-Wshadow")
 
 namespace folly {
 
-template <class T> class Range;
+template <class Iter> class Range;
 
 /**
  * Finds the first occurrence of needle in haystack. The algorithm is on
@@ -68,9 +69,10 @@ template <class T> class Range;
  * as Boyer-Moore. On the upside, it does not do any upfront
  * preprocessing and does not allocate memory.
  */
-template <class T, class Comp = std::equal_to<typename Range<T>::value_type>>
-inline size_t qfind(const Range<T> & haystack,
-                    const Range<T> & needle,
+template <class Iter,
+          class Comp = std::equal_to<typename Range<Iter>::value_type>>
+inline size_t qfind(const Range<Iter> & haystack,
+                    const Range<Iter> & needle,
                     Comp eq = Comp());
 
 /**
@@ -78,27 +80,27 @@ inline size_t qfind(const Range<T> & haystack,
  * offset reported to the beginning of haystack, or string::npos if
  * needle wasn't found.
  */
-template <class T>
-size_t qfind(const Range<T> & haystack,
-             const typename Range<T>::value_type& needle);
+template <class Iter>
+size_t qfind(const Range<Iter> & haystack,
+             const typename Range<Iter>::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 <class T>
-size_t rfind(const Range<T> & haystack,
-             const typename Range<T>::value_type& needle);
+template <class Iter>
+size_t rfind(const Range<Iter> & haystack,
+             const typename Range<Iter>::value_type& needle);
 
 
 /**
  * Finds the first occurrence of any element of needle in
  * haystack. The algorithm is O(haystack.size() * needle.size()).
  */
-template <class T>
-inline size_t qfind_first_of(const Range<T> & haystack,
-                             const Range<T> & needle);
+template <class Iter>
+inline size_t qfind_first_of(const Range<Iter> & haystack,
+                             const Range<Iter> & needle);
 
 /**
  * Small internal helper - returns the value just before an iterator.
@@ -168,6 +170,7 @@ public:
   typedef typename std::remove_reference<
     typename std::iterator_traits<Iter>::reference>::type
   value_type;
+  using difference_type = typename std::iterator_traits<Iter>::difference_type;
   typedef typename std::iterator_traits<Iter>::reference reference;
 
   /**
@@ -203,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 <class T = Iter, typename detail::IsCharPointer<T>::type = 0>
   constexpr /* implicit */ Range(Iter str)
@@ -331,9 +332,36 @@ 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<char, N> or a std::array<const char, N>
+   */
+  template <
+      class T,
+      size_t N,
+      typename = typename std::enable_if<
+          std::is_convertible<const T*, Iter>::value>::type>
+  constexpr explicit Range(const std::array<T, N>& 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<std::is_convertible<T*, Iter>::value>::type>
+  constexpr explicit Range(std::array<T, N>& 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;
 
+  template <class T = Iter, typename detail::IsCharPointer<T>::const_type = 0>
+  Range& operator=(std::string&& rhs) = delete;
+
   void clear() {
     b_ = Iter();
     e_ = Iter();
@@ -361,10 +389,10 @@ public:
     // 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_;
+    return size_type(e_ - b_);
   }
   constexpr size_type walk_size() const {
-    return std::distance(b_, e_);
+    return size_type(std::distance(b_, e_));
   }
   constexpr bool empty() const {
     return b_ == e_;
@@ -633,6 +661,16 @@ public:
     return !empty() && front() == c;
   }
 
+  template <class Comp>
+  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<Comp>(eq));
+  }
+
   /**
    * Does this Range end with another range?
    */
@@ -644,6 +682,16 @@ public:
     return !empty() && back() == c;
   }
 
+  template <class Comp>
+  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<Comp>(eq));
+  }
+
   /**
    * Remove the items in [b, e), as long as this subrange is at the beginning
    * or end of the Range.
@@ -785,7 +833,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<Iter>::difference_type(
+                  delimiter.size()));
 
     return result;
   }
@@ -869,8 +922,8 @@ private:
 template <class Iter>
 const typename Range<Iter>::size_type Range<Iter>::npos = std::string::npos;
 
-template <class T>
-void swap(Range<T>& lhs, Range<T>& rhs) {
+template <class Iter>
+void swap(Range<Iter>& lhs, Range<Iter>& rhs) {
   lhs.swap(rhs);
 }
 
@@ -901,8 +954,7 @@ constexpr Range<T*> range(T (&array)[n]) {
 
 template <class T, size_t n>
 constexpr Range<const T*> range(const std::array<T, n>& array) {
-  using r = Range<const T*>;
-  return array.empty() ? r{} : r(&array.at(0), &array.at(0) + n);
+  return Range<const T*>{array};
 }
 
 typedef Range<const char*> StringPiece;
@@ -912,13 +964,13 @@ typedef Range<unsigned char*> 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;
 }
 
@@ -926,13 +978,13 @@ inline std::ostream& operator<<(std::ostream& os,
  * Templated comparison operators
  */
 
-template <class T>
-inline bool operator==(const Range<T>& lhs, const Range<T>& rhs) {
+template <class Iter>
+inline bool operator==(const Range<Iter>& lhs, const Range<Iter>& rhs) {
   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
 }
 
-template <class T>
-inline bool operator<(const Range<T>& lhs, const Range<T>& rhs) {
+template <class Iter>
+inline bool operator<(const Range<Iter>& lhs, const Range<Iter>& rhs) {
   return lhs.compare(rhs) < 0;
 }
 
@@ -1009,9 +1061,9 @@ operator>=(const T& lhs, const U& rhs) {
 /**
  * Finds substrings faster than brute force by borrowing from Boyer-Moore
  */
-template <class T, class Comp>
-size_t qfind(const Range<T>& haystack,
-             const Range<T>& needle,
+template <class Iter, class Comp>
+size_t qfind(const Range<Iter>& haystack,
+             const Range<Iter>& needle,
              Comp eq) {
   // Don't use std::search, use a Boyer-Moore-like trick by comparing
   // the last characters first
@@ -1058,7 +1110,7 @@ size_t qfind(const Range<T>& haystack,
       // Check if done searching
       if (++j == nsize) {
         // Yay
-        return i - haystack.begin();
+        return size_t(i - haystack.begin());
       }
     }
   }
@@ -1077,9 +1129,9 @@ inline size_t qfind_first_byte_of(const StringPiece haystack,
 
 } // namespace detail
 
-template <class T, class Comp>
-size_t qfind_first_of(const Range<T> & haystack,
-                      const Range<T> & needles,
+template <class Iter, class Comp>
+size_t qfind_first_of(const Range<Iter> & haystack,
+                      const Range<Iter> & needles,
                       Comp eq) {
   auto ret = std::find_first_of(haystack.begin(), haystack.end(),
                                 needles.begin(), needles.end(),
@@ -1108,16 +1160,16 @@ struct AsciiCaseInsensitive {
   }
 };
 
-template <class T>
-size_t qfind(const Range<T>& haystack,
-             const typename Range<T>::value_type& needle) {
+template <class Iter>
+size_t qfind(const Range<Iter>& haystack,
+             const typename Range<Iter>::value_type& needle) {
   auto pos = std::find(haystack.begin(), haystack.end(), needle);
   return pos == haystack.end() ? std::string::npos : pos - haystack.data();
 }
 
-template <class T>
-size_t rfind(const Range<T>& haystack,
-             const typename Range<T>::value_type& needle) {
+template <class Iter>
+size_t rfind(const Range<Iter>& haystack,
+             const typename Range<Iter>::value_type& needle) {
   for (auto i = haystack.size(); i-- > 0; ) {
     if (haystack[i] == needle) {
       return i;
@@ -1174,9 +1226,9 @@ inline size_t rfind(const Range<const unsigned char*>& haystack,
   return pos == nullptr ? std::string::npos : pos - haystack.data();
 }
 
-template <class T>
-size_t qfind_first_of(const Range<T>& haystack,
-                      const Range<T>& needles) {
+template <class Iter>
+size_t qfind_first_of(const Range<Iter>& haystack,
+                      const Range<Iter>& needles) {
   return qfind_first_of(haystack, needles, AsciiCaseSensitive());
 }
 
@@ -1216,6 +1268,6 @@ template <class T> struct IsSomeString {
 
 }  // !namespace folly
 
-#pragma GCC diagnostic pop
+FOLLY_POP_WARNING
 
 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);