folly/Range.h

   1 /*
   2  * Copyright 2014 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // @author Mark Rabkin (mrabkin@fb.com)
  18 // @author Andrei Alexandrescu (andrei.alexandrescu@fb.com)
  19
  20 #ifndef FOLLY_RANGE_H_
  21 #define FOLLY_RANGE_H_
  22
  23 #include "folly/Portability.h"
  24 #include "folly/FBString.h"
  25 #include <glog/logging.h>
  26 #include <algorithm>
  27 #include <cstring>
  28 #include <iosfwd>
  29 #include <string>
  30 #include <stdexcept>
  31 #include <type_traits>
  32 #include <boost/operators.hpp>
  33
  34 // libc++ doesn't provide this header
  35 #if !FOLLY_USE_LIBCPP
  36 // This file appears in two locations: inside fbcode and in the
  37 // libstdc++ source code (when embedding fbstring as std::string).
  38 // To aid in this schizophrenic use, two macros are defined in
  39 // c++config.h:
  40 //   _LIBSTDCXX_FBSTRING - Set inside libstdc++.  This is useful to
  41 //      gate use inside fbcode v. libstdc++
  42 #include <bits/c++config.h>
  43 #endif
  44
  45 #include "folly/CpuId.h"
  46 #include "folly/Traits.h"
  47 #include "folly/Likely.h"
  48
  49 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
  50 #pragma GCC diagnostic push
  51 #pragma GCC diagnostic ignored "-Wshadow"
  52
  53 namespace folly {
  54
  55 template <class T> class Range;
  56
  57 /**
  58  * Finds the first occurrence of needle in haystack. The algorithm is on
  59  * average faster than O(haystack.size() * needle.size()) but not as fast
  60  * as Boyer-Moore. On the upside, it does not do any upfront
  61  * preprocessing and does not allocate memory.
  62  */
  63 template <class T, class Comp = std::equal_to<typename Range<T>::value_type>>
  64 inline size_t qfind(const Range<T> & haystack,
  65                     const Range<T> & needle,
  66                     Comp eq = Comp());
  67
  68 /**
  69  * Finds the first occurrence of needle in haystack. The result is the
  70  * offset reported to the beginning of haystack, or string::npos if
  71  * needle wasn't found.
  72  */
  73 template <class T>
  74 size_t qfind(const Range<T> & haystack,
  75              const typename Range<T>::value_type& needle);
  76
  77 /**
  78  * Finds the last occurrence of needle in haystack. The result is the
  79  * offset reported to the beginning of haystack, or string::npos if
  80  * needle wasn't found.
  81  */
  82 template <class T>
  83 size_t rfind(const Range<T> & haystack,
  84              const typename Range<T>::value_type& needle);
  85
  86
  87 /**
  88  * Finds the first occurrence of any element of needle in
  89  * haystack. The algorithm is O(haystack.size() * needle.size()).
  90  */
  91 template <class T>
  92 inline size_t qfind_first_of(const Range<T> & haystack,
  93                              const Range<T> & needle);
  94
  95 /**
  96  * Small internal helper - returns the value just before an iterator.
  97  */
  98 namespace detail {
  99
 100 /**
 101  * For random-access iterators, the value before is simply i[-1].
 102  */
 103 template <class Iter>
 104 typename std::enable_if<
 105   std::is_same<typename std::iterator_traits<Iter>::iterator_category,
 106                std::random_access_iterator_tag>::value,
 107   typename std::iterator_traits<Iter>::reference>::type
 108 value_before(Iter i) {
 109   return i[-1];
 110 }
 111
 112 /**
 113  * For all other iterators, we need to use the decrement operator.
 114  */
 115 template <class Iter>
 116 typename std::enable_if<
 117   !std::is_same<typename std::iterator_traits<Iter>::iterator_category,
 118                 std::random_access_iterator_tag>::value,
 119   typename std::iterator_traits<Iter>::reference>::type
 120 value_before(Iter i) {
 121   return *--i;
 122 }
 123
 124 } // namespace detail
 125
 126 /**
 127  * Range abstraction keeping a pair of iterators. We couldn't use
 128  * boost's similar range abstraction because we need an API identical
 129  * with the former StringPiece class, which is used by a lot of other
 130  * code. This abstraction does fulfill the needs of boost's
 131  * range-oriented algorithms though.
 132  *
 133  * (Keep memory lifetime in mind when using this class, since it
 134  * doesn't manage the data it refers to - just like an iterator
 135  * wouldn't.)
 136  */
 137 template <class Iter>
 138 class Range : private boost::totally_ordered<Range<Iter> > {
 139 public:
 140   typedef std::size_t size_type;
 141   typedef Iter iterator;
 142   typedef Iter const_iterator;
 143   typedef typename std::remove_reference<
 144     typename std::iterator_traits<Iter>::reference>::type
 145   value_type;
 146   typedef typename std::iterator_traits<Iter>::reference reference;
 147   typedef std::char_traits<typename std::remove_const<value_type>::type>
 148     traits_type;
 149
 150   static const size_type npos;
 151
 152   // Works for all iterators
 153   Range() : b_(), e_() {
 154   }
 155
 156 public:
 157   // Works for all iterators
 158   Range(Iter start, Iter end) : b_(start), e_(end) {
 159   }
 160
 161   // Works only for random-access iterators
 162   Range(Iter start, size_t size)
 163       : b_(start), e_(start + size) { }
 164
 165 #if FOLLY_HAVE_CONSTEXPR_STRLEN
 166   // Works only for Range<const char*>
 167   /* implicit */ constexpr Range(Iter str)
 168       : b_(str), e_(str + strlen(str)) {}
 169 #else
 170   // Works only for Range<const char*>
 171   /* implicit */ Range(Iter str)
 172       : b_(str), e_(str + strlen(str)) {}
 173 #endif
 174   // Works only for Range<const char*>
 175   /* implicit */ Range(const std::string& str)
 176       : b_(str.data()), e_(b_ + str.size()) {}
 177   // Works only for Range<const char*>
 178   Range(const std::string& str, std::string::size_type startFrom) {
 179     if (UNLIKELY(startFrom > str.size())) {
 180       throw std::out_of_range("index out of range");
 181     }
 182     b_ = str.data() + startFrom;
 183     e_ = str.data() + str.size();
 184   }
 185   // Works only for Range<const char*>
 186   Range(const std::string& str,
 187         std::string::size_type startFrom,
 188         std::string::size_type size) {
 189     if (UNLIKELY(startFrom > str.size())) {
 190       throw std::out_of_range("index out of range");
 191     }
 192     b_ = str.data() + startFrom;
 193     if (str.size() - startFrom < size) {
 194       e_ = str.data() + str.size();
 195     } else {
 196       e_ = b_ + size;
 197     }
 198   }
 199   Range(const Range<Iter>& str,
 200         size_t startFrom,
 201         size_t size) {
 202     if (UNLIKELY(startFrom > str.size())) {
 203       throw std::out_of_range("index out of range");
 204     }
 205     b_ = str.b_ + startFrom;
 206     if (str.size() - startFrom < size) {
 207       e_ = str.e_;
 208     } else {
 209       e_ = b_ + size;
 210     }
 211   }
 212   // Works only for Range<const char*>
 213   /* implicit */ Range(const fbstring& str)
 214     : b_(str.data()), e_(b_ + str.size()) { }
 215   // Works only for Range<const char*>
 216   Range(const fbstring& str, fbstring::size_type startFrom) {
 217     if (UNLIKELY(startFrom > str.size())) {
 218       throw std::out_of_range("index out of range");
 219     }
 220     b_ = str.data() + startFrom;
 221     e_ = str.data() + str.size();
 222   }
 223   // Works only for Range<const char*>
 224   Range(const fbstring& str, fbstring::size_type startFrom,
 225         fbstring::size_type size) {
 226     if (UNLIKELY(startFrom > str.size())) {
 227       throw std::out_of_range("index out of range");
 228     }
 229     b_ = str.data() + startFrom;
 230     if (str.size() - startFrom < size) {
 231       e_ = str.data() + str.size();
 232     } else {
 233       e_ = b_ + size;
 234     }
 235   }
 236
 237   // Allow implicit conversion from Range<const char*> (aka StringPiece) to
 238   // Range<const unsigned char*> (aka ByteRange), as they're both frequently
 239   // used to represent ranges of bytes.  Allow explicit conversion in the other
 240   // direction.
 241   template <class OtherIter, typename std::enable_if<
 242       (std::is_same<Iter, const unsigned char*>::value &&
 243        (std::is_same<OtherIter, const char*>::value ||
 244         std::is_same<OtherIter, char*>::value)), int>::type = 0>
 245   /* implicit */ Range(const Range<OtherIter>& other)
 246     : b_(reinterpret_cast<const unsigned char*>(other.begin())),
 247       e_(reinterpret_cast<const unsigned char*>(other.end())) {
 248   }
 249
 250   template <class OtherIter, typename std::enable_if<
 251       (std::is_same<Iter, unsigned char*>::value &&
 252        std::is_same<OtherIter, char*>::value), int>::type = 0>
 253   /* implicit */ Range(const Range<OtherIter>& other)
 254     : b_(reinterpret_cast<unsigned char*>(other.begin())),
 255       e_(reinterpret_cast<unsigned char*>(other.end())) {
 256   }
 257
 258   template <class OtherIter, typename std::enable_if<
 259       (std::is_same<Iter, const char*>::value &&
 260        (std::is_same<OtherIter, const unsigned char*>::value ||
 261         std::is_same<OtherIter, unsigned char*>::value)), int>::type = 0>
 262   explicit Range(const Range<OtherIter>& other)
 263     : b_(reinterpret_cast<const char*>(other.begin())),
 264       e_(reinterpret_cast<const char*>(other.end())) {
 265   }
 266
 267   template <class OtherIter, typename std::enable_if<
 268       (std::is_same<Iter, char*>::value &&
 269        std::is_same<OtherIter, unsigned char*>::value), int>::type = 0>
 270   explicit Range(const Range<OtherIter>& other)
 271     : b_(reinterpret_cast<char*>(other.begin())),
 272       e_(reinterpret_cast<char*>(other.end())) {
 273   }
 274
 275   // Allow implicit conversion from Range<From> to Range<To> if From is
 276   // implicitly convertible to To.
 277   template <class OtherIter, typename std::enable_if<
 278      (!std::is_same<Iter, OtherIter>::value &&
 279       std::is_convertible<OtherIter, Iter>::value), int>::type = 0>
 280   /* implicit */ Range(const Range<OtherIter>& other)
 281     : b_(other.begin()),
 282       e_(other.end()) {
 283   }
 284
 285   // Allow explicit conversion from Range<From> to Range<To> if From is
 286   // explicitly convertible to To.
 287   template <class OtherIter, typename std::enable_if<
 288     (!std::is_same<Iter, OtherIter>::value &&
 289      !std::is_convertible<OtherIter, Iter>::value &&
 290      std::is_constructible<Iter, const OtherIter&>::value), int>::type = 0>
 291   explicit Range(const Range<OtherIter>& other)
 292     : b_(other.begin()),
 293       e_(other.end()) {
 294   }
 295
 296   void clear() {
 297     b_ = Iter();
 298     e_ = Iter();
 299   }
 300
 301   void assign(Iter start, Iter end) {
 302     b_ = start;
 303     e_ = end;
 304   }
 305
 306   void reset(Iter start, size_type size) {
 307     b_ = start;
 308     e_ = start + size;
 309   }
 310
 311   // Works only for Range<const char*>
 312   void reset(const std::string& str) {
 313     reset(str.data(), str.size());
 314   }
 315
 316   size_type size() const {
 317     assert(b_ <= e_);
 318     return e_ - b_;
 319   }
 320   size_type walk_size() const {
 321     assert(b_ <= e_);
 322     return std::distance(b_, e_);
 323   }
 324   bool empty() const { return b_ == e_; }
 325   Iter data() const { return b_; }
 326   Iter start() const { return b_; }
 327   Iter begin() const { return b_; }
 328   Iter end() const { return e_; }
 329   Iter cbegin() const { return b_; }
 330   Iter cend() const { return e_; }
 331   value_type& front() {
 332     assert(b_ < e_);
 333     return *b_;
 334   }
 335   value_type& back() {
 336     assert(b_ < e_);
 337     return detail::value_before(e_);
 338   }
 339   const value_type& front() const {
 340     assert(b_ < e_);
 341     return *b_;
 342   }
 343   const value_type& back() const {
 344     assert(b_ < e_);
 345     return detail::value_before(e_);
 346   }
 347   // Works only for Range<const char*>
 348   std::string str() const { return std::string(b_, size()); }
 349   std::string toString() const { return str(); }
 350   // Works only for Range<const char*>
 351   fbstring fbstr() const { return fbstring(b_, size()); }
 352   fbstring toFbstring() const { return fbstr(); }
 353
 354   // Works only for Range<const char*>
 355   int compare(const Range& o) const {
 356     const size_type tsize = this->size();
 357     const size_type osize = o.size();
 358     const size_type msize = std::min(tsize, osize);
 359     int r = traits_type::compare(data(), o.data(), msize);
 360     if (r == 0) r = tsize - osize;
 361     return r;
 362   }
 363
 364   value_type& operator[](size_t i) {
 365     DCHECK_GT(size(), i);
 366     return b_[i];
 367   }
 368
 369   const value_type& operator[](size_t i) const {
 370     DCHECK_GT(size(), i);
 371     return b_[i];
 372   }
 373
 374   value_type& at(size_t i) {
 375     if (i >= size()) throw std::out_of_range("index out of range");
 376     return b_[i];
 377   }
 378
 379   const value_type& at(size_t i) const {
 380     if (i >= size()) throw std::out_of_range("index out of range");
 381     return b_[i];
 382   }
 383
 384   // Works only for Range<const char*>
 385   uint32_t hash() const {
 386     // Taken from fbi/nstring.h:
 387     //    Quick and dirty bernstein hash...fine for short ascii strings
 388     uint32_t hash = 5381;
 389     for (size_t ix = 0; ix < size(); ix++) {
 390       hash = ((hash << 5) + hash) + b_[ix];
 391     }
 392     return hash;
 393   }
 394
 395   void advance(size_type n) {
 396     if (UNLIKELY(n > size())) {
 397       throw std::out_of_range("index out of range");
 398     }
 399     b_ += n;
 400   }
 401
 402   void subtract(size_type n) {
 403     if (UNLIKELY(n > size())) {
 404       throw std::out_of_range("index out of range");
 405     }
 406     e_ -= n;
 407   }
 408
 409   void pop_front() {
 410     assert(b_ < e_);
 411     ++b_;
 412   }
 413
 414   void pop_back() {
 415     assert(b_ < e_);
 416     --e_;
 417   }
 418
 419   Range subpiece(size_type first,
 420                  size_type length = std::string::npos) const {
 421     if (UNLIKELY(first > size())) {
 422       throw std::out_of_range("index out of range");
 423     }
 424     return Range(b_ + first,
 425                  std::min<std::string::size_type>(length, size() - first));
 426   }
 427
 428   // string work-alike functions
 429   size_type find(Range str) const {
 430     return qfind(*this, str);
 431   }
 432
 433   size_type find(Range str, size_t pos) const {
 434     if (pos > size()) return std::string::npos;
 435     size_t ret = qfind(subpiece(pos), str);
 436     return ret == npos ? ret : ret + pos;
 437   }
 438
 439   size_type find(Iter s, size_t pos, size_t n) const {
 440     if (pos > size()) return std::string::npos;
 441     size_t ret = qfind(pos ? subpiece(pos) : *this, Range(s, n));
 442     return ret == npos ? ret : ret + pos;
 443   }
 444
 445   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 446   size_type find(const Iter s) const {
 447     return qfind(*this, Range(s));
 448   }
 449
 450   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 451   size_type find(const Iter s, size_t pos) const {
 452     if (pos > size()) return std::string::npos;
 453     size_type ret = qfind(subpiece(pos), Range(s));
 454     return ret == npos ? ret : ret + pos;
 455   }
 456
 457   size_type find(value_type c) const {
 458     return qfind(*this, c);
 459   }
 460
 461   size_type rfind(value_type c) const {
 462     return folly::rfind(*this, c);
 463   }
 464
 465   size_type find(value_type c, size_t pos) const {
 466     if (pos > size()) return std::string::npos;
 467     size_type ret = qfind(subpiece(pos), c);
 468     return ret == npos ? ret : ret + pos;
 469   }
 470
 471   size_type find_first_of(Range needles) const {
 472     return qfind_first_of(*this, needles);
 473   }
 474
 475   size_type find_first_of(Range needles, size_t pos) const {
 476     if (pos > size()) return std::string::npos;
 477     size_type ret = qfind_first_of(subpiece(pos), needles);
 478     return ret == npos ? ret : ret + pos;
 479   }
 480
 481   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 482   size_type find_first_of(Iter needles) const {
 483     return find_first_of(Range(needles));
 484   }
 485
 486   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 487   size_type find_first_of(Iter needles, size_t pos) const {
 488     return find_first_of(Range(needles), pos);
 489   }
 490
 491   size_type find_first_of(Iter needles, size_t pos, size_t n) const {
 492     return find_first_of(Range(needles, n), pos);
 493   }
 494
 495   size_type find_first_of(value_type c) const {
 496     return find(c);
 497   }
 498
 499   size_type find_first_of(value_type c, size_t pos) const {
 500     return find(c, pos);
 501   }
 502
 503   void swap(Range& rhs) {
 504     std::swap(b_, rhs.b_);
 505     std::swap(e_, rhs.e_);
 506   }
 507
 508   /**
 509    * Does this Range start with another range?
 510    */
 511   bool startsWith(const Range& other) const {
 512     return size() >= other.size() && subpiece(0, other.size()) == other;
 513   }
 514   bool startsWith(value_type c) const {
 515     return !empty() && front() == c;
 516   }
 517
 518   /**
 519    * Does this Range end with another range?
 520    */
 521   bool endsWith(const Range& other) const {
 522     return size() >= other.size() && subpiece(size() - other.size()) == other;
 523   }
 524   bool endsWith(value_type c) const {
 525     return !empty() && back() == c;
 526   }
 527
 528   /**
 529    * Remove the given prefix and return true if the range starts with the given
 530    * prefix; return false otherwise.
 531    */
 532   bool removePrefix(const Range& prefix) {
 533     return startsWith(prefix) && (b_ += prefix.size(), true);
 534   }
 535   bool removePrefix(value_type prefix) {
 536     return startsWith(prefix) && (++b_, true);
 537   }
 538
 539   /**
 540    * Remove the given suffix and return true if the range ends with the given
 541    * suffix; return false otherwise.
 542    */
 543   bool removeSuffix(const Range& suffix) {
 544     return endsWith(suffix) && (e_ -= suffix.size(), true);
 545   }
 546   bool removeSuffix(value_type suffix) {
 547     return endsWith(suffix) && (--e_, true);
 548   }
 549
 550   /**
 551    * Splits this `Range` `[b, e)` in the position `i` dictated by the next
 552    * occurence of `delimiter`.
 553    *
 554    * Returns a new `Range` `[b, i)` and adjusts this range to start right after
 555    * the delimiter's position. This range will be empty if the delimiter is not
 556    * found. If called on an empty `Range`, both this and the returned `Range`
 557    * will be empty.
 558    *
 559    * Example:
 560    *
 561    *  folly::StringPiece s("sample string for split_next");
 562    *  auto p = s.split_step(' ');
 563    *
 564    *  // prints "sample"
 565    *  cout << s << endl;
 566    *
 567    *  // prints "string for split_next"
 568    *  cout << p << endl;
 569    *
 570    * Example 2:
 571    *
 572    *  void tokenize(StringPiece s, char delimiter) {
 573    *    while (!s.empty()) {
 574    *      cout << s.split_step(delimiter);
 575    *    }
 576    *  }
 577    *
 578    * @author: Marcelo Juchem <marcelo@fb.com>
 579    */
 580   Range split_step(value_type delimiter) {
 581     auto i = std::find(b_, e_, delimiter);
 582     Range result(b_, i);
 583
 584     b_ = i == e_ ? e_ : std::next(i);
 585
 586     return result;
 587   }
 588
 589   Range split_step(Range delimiter) {
 590     auto i = find(delimiter);
 591     Range result(b_, i == std::string::npos ? size() : i);
 592
 593     b_ = result.end() == e_ ? e_ : std::next(result.end(), delimiter.size());
 594
 595     return result;
 596   }
 597
 598   /**
 599    * Convenience method that calls `split_step()` and passes the result to a
 600    * functor, returning whatever the functor does.
 601    *
 602    * Say you have a functor with this signature:
 603    *
 604    *  Foo fn(Range r) { }
 605    *
 606    * `split_step()`'s return type will be `Foo`. It works just like:
 607    *
 608    *  auto result = fn(myRange.split_step(' '));
 609    *
 610    * A functor returning `void` is also supported.
 611    *
 612    * Example:
 613    *
 614    *  void do_some_parsing(folly::StringPiece s) {
 615    *    auto version = s.split_step(' ', [&](folly::StringPiece x) {
 616    *      if (x.empty()) {
 617    *        throw std::invalid_argument("empty string");
 618    *      }
 619    *      return std::strtoull(x.begin(), x.end(), 16);
 620    *    });
 621    *
 622    *    // ...
 623    *  }
 624    *
 625    * @author: Marcelo Juchem <marcelo@fb.com>
 626    */
 627   template <typename TProcess>
 628   auto split_step(value_type delimiter, TProcess &&process)
 629     -> decltype(process(std::declval<Range>()))
 630   { return process(split_step(delimiter)); }
 631
 632   template <typename TProcess>
 633   auto split_step(Range delimiter, TProcess &&process)
 634     -> decltype(process(std::declval<Range>()))
 635   { return process(split_step(delimiter)); }
 636
 637 private:
 638   Iter b_, e_;
 639 };
 640
 641 template <class Iter>
 642 const typename Range<Iter>::size_type Range<Iter>::npos = std::string::npos;
 643
 644 template <class T>
 645 void swap(Range<T>& lhs, Range<T>& rhs) {
 646   lhs.swap(rhs);
 647 }
 648
 649 /**
 650  * Create a range from two iterators, with type deduction.
 651  */
 652 template <class Iter>
 653 Range<Iter> makeRange(Iter first, Iter last) {
 654   return Range<Iter>(first, last);
 655 }
 656
 657 typedef Range<const char*> StringPiece;
 658 typedef Range<char*> MutableStringPiece;
 659 typedef Range<const unsigned char*> ByteRange;
 660 typedef Range<unsigned char*> MutableByteRange;
 661
 662 std::ostream& operator<<(std::ostream& os, const StringPiece& piece);
 663
 664 /**
 665  * Templated comparison operators
 666  */
 667
 668 template <class T>
 669 inline bool operator==(const Range<T>& lhs, const Range<T>& rhs) {
 670   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
 671 }
 672
 673 template <class T>
 674 inline bool operator<(const Range<T>& lhs, const Range<T>& rhs) {
 675   return lhs.compare(rhs) < 0;
 676 }
 677
 678 /**
 679  * Specializations of comparison operators for StringPiece
 680  */
 681
 682 namespace detail {
 683
 684 template <class A, class B>
 685 struct ComparableAsStringPiece {
 686   enum {
 687     value =
 688     (std::is_convertible<A, StringPiece>::value
 689      && std::is_same<B, StringPiece>::value)
 690     ||
 691     (std::is_convertible<B, StringPiece>::value
 692      && std::is_same<A, StringPiece>::value)
 693   };
 694 };
 695
 696 } // namespace detail
 697
 698 /**
 699  * operator== through conversion for Range<const char*>
 700  */
 701 template <class T, class U>
 702 typename
 703 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 704 operator==(const T& lhs, const U& rhs) {
 705   return StringPiece(lhs) == StringPiece(rhs);
 706 }
 707
 708 /**
 709  * operator< through conversion for Range<const char*>
 710  */
 711 template <class T, class U>
 712 typename
 713 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 714 operator<(const T& lhs, const U& rhs) {
 715   return StringPiece(lhs) < StringPiece(rhs);
 716 }
 717
 718 /**
 719  * operator> through conversion for Range<const char*>
 720  */
 721 template <class T, class U>
 722 typename
 723 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 724 operator>(const T& lhs, const U& rhs) {
 725   return StringPiece(lhs) > StringPiece(rhs);
 726 }
 727
 728 /**
 729  * operator< through conversion for Range<const char*>
 730  */
 731 template <class T, class U>
 732 typename
 733 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 734 operator<=(const T& lhs, const U& rhs) {
 735   return StringPiece(lhs) <= StringPiece(rhs);
 736 }
 737
 738 /**
 739  * operator> through conversion for Range<const char*>
 740  */
 741 template <class T, class U>
 742 typename
 743 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 744 operator>=(const T& lhs, const U& rhs) {
 745   return StringPiece(lhs) >= StringPiece(rhs);
 746 }
 747
 748 struct StringPieceHash {
 749   std::size_t operator()(const StringPiece& str) const {
 750     return static_cast<std::size_t>(str.hash());
 751   }
 752 };
 753
 754 /**
 755  * Finds substrings faster than brute force by borrowing from Boyer-Moore
 756  */
 757 template <class T, class Comp>
 758 size_t qfind(const Range<T>& haystack,
 759              const Range<T>& needle,
 760              Comp eq) {
 761   // Don't use std::search, use a Boyer-Moore-like trick by comparing
 762   // the last characters first
 763   auto const nsize = needle.size();
 764   if (haystack.size() < nsize) {
 765     return std::string::npos;
 766   }
 767   if (!nsize) return 0;
 768   auto const nsize_1 = nsize - 1;
 769   auto const lastNeedle = needle[nsize_1];
 770
 771   // Boyer-Moore skip value for the last char in the needle. Zero is
 772   // not a valid value; skip will be computed the first time it's
 773   // needed.
 774   std::string::size_type skip = 0;
 775
 776   auto i = haystack.begin();
 777   auto iEnd = haystack.end() - nsize_1;
 778
 779   while (i < iEnd) {
 780     // Boyer-Moore: match the last element in the needle
 781     while (!eq(i[nsize_1], lastNeedle)) {
 782       if (++i == iEnd) {
 783         // not found
 784         return std::string::npos;
 785       }
 786     }
 787     // Here we know that the last char matches
 788     // Continue in pedestrian mode
 789     for (size_t j = 0; ; ) {
 790       assert(j < nsize);
 791       if (!eq(i[j], needle[j])) {
 792         // Not found, we can skip
 793         // Compute the skip value lazily
 794         if (skip == 0) {
 795           skip = 1;
 796           while (skip <= nsize_1 && !eq(needle[nsize_1 - skip], lastNeedle)) {
 797             ++skip;
 798           }
 799         }
 800         i += skip;
 801         break;
 802       }
 803       // Check if done searching
 804       if (++j == nsize) {
 805         // Yay
 806         return i - haystack.begin();
 807       }
 808     }
 809   }
 810   return std::string::npos;
 811 }
 812
 813 namespace detail {
 814
 815 size_t qfind_first_byte_of_nosse(const StringPiece& haystack,
 816                                  const StringPiece& needles);
 817
 818 #if FOLLY_HAVE_EMMINTRIN_H && __GNUC_PREREQ(4, 6)
 819 size_t qfind_first_byte_of_sse42(const StringPiece& haystack,
 820                                  const StringPiece& needles);
 821
 822 inline size_t qfind_first_byte_of(const StringPiece& haystack,
 823                                   const StringPiece& needles) {
 824   static auto const qfind_first_byte_of_fn =
 825     folly::CpuId().sse42() ? qfind_first_byte_of_sse42
 826                            : qfind_first_byte_of_nosse;
 827   return qfind_first_byte_of_fn(haystack, needles);
 828 }
 829
 830 #else
 831 inline size_t qfind_first_byte_of(const StringPiece& haystack,
 832                                   const StringPiece& needles) {
 833   return qfind_first_byte_of_nosse(haystack, needles);
 834 }
 835 #endif // FOLLY_HAVE_EMMINTRIN_H
 836
 837 } // namespace detail
 838
 839 template <class T, class Comp>
 840 size_t qfind_first_of(const Range<T> & haystack,
 841                       const Range<T> & needles,
 842                       Comp eq) {
 843   auto ret = std::find_first_of(haystack.begin(), haystack.end(),
 844                                 needles.begin(), needles.end(),
 845                                 eq);
 846   return ret == haystack.end() ? std::string::npos : ret - haystack.begin();
 847 }
 848
 849 struct AsciiCaseSensitive {
 850   bool operator()(char lhs, char rhs) const {
 851     return lhs == rhs;
 852   }
 853 };
 854
 855 struct AsciiCaseInsensitive {
 856   bool operator()(char lhs, char rhs) const {
 857     return toupper(lhs) == toupper(rhs);
 858   }
 859 };
 860
 861 extern const AsciiCaseSensitive asciiCaseSensitive;
 862 extern const AsciiCaseInsensitive asciiCaseInsensitive;
 863
 864 template <class T>
 865 size_t qfind(const Range<T>& haystack,
 866              const typename Range<T>::value_type& needle) {
 867   auto pos = std::find(haystack.begin(), haystack.end(), needle);
 868   return pos == haystack.end() ? std::string::npos : pos - haystack.data();
 869 }
 870
 871 template <class T>
 872 size_t rfind(const Range<T>& haystack,
 873              const typename Range<T>::value_type& needle) {
 874   for (auto i = haystack.size(); i-- > 0; ) {
 875     if (haystack[i] == needle) {
 876       return i;
 877     }
 878   }
 879   return std::string::npos;
 880 }
 881
 882 // specialization for StringPiece
 883 template <>
 884 inline size_t qfind(const Range<const char*>& haystack, const char& needle) {
 885   auto pos = static_cast<const char*>(
 886     ::memchr(haystack.data(), needle, haystack.size()));
 887   return pos == nullptr ? std::string::npos : pos - haystack.data();
 888 }
 889
 890 #if FOLLY_HAVE_MEMRCHR
 891 template <>
 892 inline size_t rfind(const Range<const char*>& haystack, const char& needle) {
 893   auto pos = static_cast<const char*>(
 894     ::memrchr(haystack.data(), needle, haystack.size()));
 895   return pos == nullptr ? std::string::npos : pos - haystack.data();
 896 }
 897 #endif
 898
 899 // specialization for ByteRange
 900 template <>
 901 inline size_t qfind(const Range<const unsigned char*>& haystack,
 902                     const unsigned char& needle) {
 903   auto pos = static_cast<const unsigned char*>(
 904     ::memchr(haystack.data(), needle, haystack.size()));
 905   return pos == nullptr ? std::string::npos : pos - haystack.data();
 906 }
 907
 908 #if FOLLY_HAVE_MEMRCHR
 909 template <>
 910 inline size_t rfind(const Range<const unsigned char*>& haystack,
 911                     const unsigned char& needle) {
 912   auto pos = static_cast<const unsigned char*>(
 913     ::memrchr(haystack.data(), needle, haystack.size()));
 914   return pos == nullptr ? std::string::npos : pos - haystack.data();
 915 }
 916 #endif
 917
 918 template <class T>
 919 size_t qfind_first_of(const Range<T>& haystack,
 920                       const Range<T>& needles) {
 921   return qfind_first_of(haystack, needles, asciiCaseSensitive);
 922 }
 923
 924 // specialization for StringPiece
 925 template <>
 926 inline size_t qfind_first_of(const Range<const char*>& haystack,
 927                              const Range<const char*>& needles) {
 928   return detail::qfind_first_byte_of(haystack, needles);
 929 }
 930
 931 // specialization for ByteRange
 932 template <>
 933 inline size_t qfind_first_of(const Range<const unsigned char*>& haystack,
 934                              const Range<const unsigned char*>& needles) {
 935   return detail::qfind_first_byte_of(StringPiece(haystack),
 936                                      StringPiece(needles));
 937 }
 938 }  // !namespace folly
 939
 940 #pragma GCC diagnostic pop
 941
 942 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);
 943
 944 #endif // FOLLY_RANGE_H_