folly/Range.h

   1 /*
   2  * Copyright 2013 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/folly-config.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 #include <bits/c++config.h>
  34 #include "folly/CpuId.h"
  35 #include "folly/Traits.h"
  36
  37 namespace folly {
  38
  39 template <class T> class Range;
  40
  41 /**
  42  * Finds the first occurrence of needle in haystack. The algorithm is on
  43  * average faster than O(haystack.size() * needle.size()) but not as fast
  44  * as Boyer-Moore. On the upside, it does not do any upfront
  45  * preprocessing and does not allocate memory.
  46  */
  47 template <class T>
  48 inline size_t qfind(const Range<T> & haystack,
  49                     const Range<T> & needle);
  50
  51 /**
  52  * Finds the first occurrence of needle in haystack. The result is the
  53  * offset reported to the beginning of haystack, or string::npos if
  54  * needle wasn't found.
  55  */
  56 template <class T>
  57 size_t qfind(const Range<T> & haystack,
  58              const typename Range<T>::value_type& needle);
  59
  60
  61 /**
  62  * Finds the first occurrence of any element of needle in
  63  * haystack. The algorithm is O(haystack.size() * needle.size()).
  64  */
  65 template <class T>
  66 inline size_t qfind_first_of(const Range<T> & haystack,
  67                              const Range<T> & needle);
  68
  69 /**
  70  * Small internal helper - returns the value just before an iterator.
  71  */
  72 namespace detail {
  73
  74 /**
  75  * For random-access iterators, the value before is simply i[-1].
  76  */
  77 template <class Iter>
  78 typename std::enable_if<
  79   std::is_same<typename std::iterator_traits<Iter>::iterator_category,
  80                std::random_access_iterator_tag>::value,
  81   typename std::iterator_traits<Iter>::reference>::type
  82 value_before(Iter i) {
  83   return i[-1];
  84 }
  85
  86 /**
  87  * For all other iterators, we need to use the decrement operator.
  88  */
  89 template <class Iter>
  90 typename std::enable_if<
  91   !std::is_same<typename std::iterator_traits<Iter>::iterator_category,
  92                 std::random_access_iterator_tag>::value,
  93   typename std::iterator_traits<Iter>::reference>::type
  94 value_before(Iter i) {
  95   return *--i;
  96 }
  97
  98 } // namespace detail
  99
 100 /**
 101  * Range abstraction keeping a pair of iterators. We couldn't use
 102  * boost's similar range abstraction because we need an API identical
 103  * with the former StringPiece class, which is used by a lot of other
 104  * code. This abstraction does fulfill the needs of boost's
 105  * range-oriented algorithms though.
 106  *
 107  * (Keep memory lifetime in mind when using this class, since it
 108  * doesn't manage the data it refers to - just like an iterator
 109  * wouldn't.)
 110  */
 111 template <class Iter>
 112 class Range : private boost::totally_ordered<Range<Iter> > {
 113 public:
 114   typedef std::size_t size_type;
 115   typedef Iter iterator;
 116   typedef Iter const_iterator;
 117   typedef typename std::remove_reference<
 118     typename std::iterator_traits<Iter>::reference>::type
 119   value_type;
 120   typedef typename std::iterator_traits<Iter>::reference reference;
 121   typedef std::char_traits<value_type> traits_type;
 122
 123   static const size_type npos;
 124
 125   // Works for all iterators
 126   Range() : b_(), e_() {
 127   }
 128
 129 public:
 130   // Works for all iterators
 131   Range(Iter start, Iter end) : b_(start), e_(end) {
 132   }
 133
 134   // Works only for random-access iterators
 135   Range(Iter start, size_t size)
 136       : b_(start), e_(start + size) { }
 137
 138   // Works only for Range<const char*>
 139   /* implicit */ Range(Iter str)
 140       : b_(str), e_(b_ + strlen(str)) {}
 141   // Works only for Range<const char*>
 142   /* implicit */ Range(const std::string& str)
 143       : b_(str.data()), e_(b_ + str.size()) {}
 144   // Works only for Range<const char*>
 145   Range(const std::string& str, std::string::size_type startFrom) {
 146     CHECK_LE(startFrom, str.size());
 147     b_ = str.data() + startFrom;
 148     e_ = str.data() + str.size();
 149   }
 150   // Works only for Range<const char*>
 151   Range(const std::string& str,
 152         std::string::size_type startFrom,
 153         std::string::size_type size) {
 154     CHECK_LE(startFrom + size, str.size());
 155     b_ = str.data() + startFrom;
 156     e_ = b_ + size;
 157   }
 158   Range(const Range<Iter>& str,
 159         size_t startFrom,
 160         size_t size) {
 161     CHECK_LE(startFrom + size, str.size());
 162     b_ = str.b_ + startFrom;
 163     e_ = b_ + size;
 164   }
 165   // Works only for Range<const char*>
 166   /* implicit */ Range(const fbstring& str)
 167     : b_(str.data()), e_(b_ + str.size()) { }
 168   // Works only for Range<const char*>
 169   Range(const fbstring& str, fbstring::size_type startFrom) {
 170     CHECK_LE(startFrom, str.size());
 171     b_ = str.data() + startFrom;
 172     e_ = str.data() + str.size();
 173   }
 174   // Works only for Range<const char*>
 175   Range(const fbstring& str, fbstring::size_type startFrom,
 176         fbstring::size_type size) {
 177     CHECK_LE(startFrom + size, str.size());
 178     b_ = str.data() + startFrom;
 179     e_ = b_ + size;
 180   }
 181
 182   // Allow implicit conversion from Range<const char*> (aka StringPiece) to
 183   // Range<const unsigned char*> (aka ByteRange), as they're both frequently
 184   // used to represent ranges of bytes.  Allow explicit conversion in the other
 185   // direction.
 186   template <class OtherIter, typename std::enable_if<
 187       (std::is_same<Iter, const unsigned char*>::value &&
 188        std::is_same<OtherIter, const char*>::value), int>::type = 0>
 189   /* implicit */ Range(const Range<OtherIter>& other)
 190     : b_(reinterpret_cast<const unsigned char*>(other.begin())),
 191       e_(reinterpret_cast<const unsigned char*>(other.end())) {
 192   }
 193
 194   template <class OtherIter, typename std::enable_if<
 195       (std::is_same<Iter, const char*>::value &&
 196        std::is_same<OtherIter, const unsigned char*>::value), int>::type = 0>
 197   explicit Range(const Range<OtherIter>& other)
 198     : b_(reinterpret_cast<const char*>(other.begin())),
 199       e_(reinterpret_cast<const char*>(other.end())) {
 200   }
 201
 202   void clear() {
 203     b_ = Iter();
 204     e_ = Iter();
 205   }
 206
 207   void assign(Iter start, Iter end) {
 208     b_ = start;
 209     e_ = end;
 210   }
 211
 212   void reset(Iter start, size_type size) {
 213     b_ = start;
 214     e_ = start + size;
 215   }
 216
 217   // Works only for Range<const char*>
 218   void reset(const std::string& str) {
 219     reset(str.data(), str.size());
 220   }
 221
 222   size_type size() const {
 223     assert(b_ <= e_);
 224     return e_ - b_;
 225   }
 226   size_type walk_size() const {
 227     assert(b_ <= e_);
 228     return std::distance(b_, e_);
 229   }
 230   bool empty() const { return b_ == e_; }
 231   Iter data() const { return b_; }
 232   Iter start() const { return b_; }
 233   Iter begin() const { return b_; }
 234   Iter end() const { return e_; }
 235   Iter cbegin() const { return b_; }
 236   Iter cend() const { return e_; }
 237   value_type& front() {
 238     assert(b_ < e_);
 239     return *b_;
 240   }
 241   value_type& back() {
 242     assert(b_ < e_);
 243     return detail::value_before(e_);
 244   }
 245   const value_type& front() const {
 246     assert(b_ < e_);
 247     return *b_;
 248   }
 249   const value_type& back() const {
 250     assert(b_ < e_);
 251     return detail::value_before(e_);
 252   }
 253   // Works only for Range<const char*>
 254   std::string str() const { return std::string(b_, size()); }
 255   std::string toString() const { return str(); }
 256   // Works only for Range<const char*>
 257   fbstring fbstr() const { return fbstring(b_, size()); }
 258   fbstring toFbstring() const { return fbstr(); }
 259
 260   // Works only for Range<const char*>
 261   int compare(const Range& o) const {
 262     const size_type tsize = this->size();
 263     const size_type osize = o.size();
 264     const size_type msize = std::min(tsize, osize);
 265     int r = traits_type::compare(data(), o.data(), msize);
 266     if (r == 0) r = tsize - osize;
 267     return r;
 268   }
 269
 270   value_type& operator[](size_t i) {
 271     CHECK_GT(size(), i);
 272     return b_[i];
 273   }
 274
 275   const value_type& operator[](size_t i) const {
 276     CHECK_GT(size(), i);
 277     return b_[i];
 278   }
 279
 280   value_type& at(size_t i) {
 281     if (i >= size()) throw std::out_of_range("index out of range");
 282     return b_[i];
 283   }
 284
 285   const value_type& at(size_t i) const {
 286     if (i >= size()) throw std::out_of_range("index out of range");
 287     return b_[i];
 288   }
 289
 290   // Works only for Range<const char*>
 291   uint32_t hash() const {
 292     // Taken from fbi/nstring.h:
 293     //    Quick and dirty bernstein hash...fine for short ascii strings
 294     uint32_t hash = 5381;
 295     for (size_t ix = 0; ix < size(); ix++) {
 296       hash = ((hash << 5) + hash) + b_[ix];
 297     }
 298     return hash;
 299   }
 300
 301   void advance(size_type n) {
 302     CHECK_LE(n, size());
 303     b_ += n;
 304   }
 305
 306   void subtract(size_type n) {
 307     CHECK_LE(n, size());
 308     e_ -= n;
 309   }
 310
 311   void pop_front() {
 312     assert(b_ < e_);
 313     ++b_;
 314   }
 315
 316   void pop_back() {
 317     assert(b_ < e_);
 318     --e_;
 319   }
 320
 321   Range subpiece(size_type first,
 322                  size_type length = std::string::npos) const {
 323     CHECK_LE(first, size());
 324     return Range(b_ + first,
 325                  std::min<std::string::size_type>(length, size() - first));
 326   }
 327
 328   // string work-alike functions
 329   size_type find(Range str) const {
 330     return qfind(*this, str);
 331   }
 332
 333   size_type find(Range str, size_t pos) const {
 334     if (pos > size()) return std::string::npos;
 335     size_t ret = qfind(subpiece(pos), str);
 336     return ret == npos ? ret : ret + pos;
 337   }
 338
 339   size_type find(Iter s, size_t pos, size_t n) const {
 340     if (pos > size()) return std::string::npos;
 341     size_t ret = qfind(pos ? subpiece(pos) : *this, Range(s, n));
 342     return ret == npos ? ret : ret + pos;
 343   }
 344
 345   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 346   size_type find(const Iter s) const {
 347     return qfind(*this, Range(s));
 348   }
 349
 350   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 351   size_type find(const Iter s, size_t pos) const {
 352     if (pos > size()) return std::string::npos;
 353     size_type ret = qfind(subpiece(pos), Range(s));
 354     return ret == npos ? ret : ret + pos;
 355   }
 356
 357   size_type find(value_type c) const {
 358     return qfind(*this, c);
 359   }
 360
 361   size_type find(value_type c, size_t pos) const {
 362     if (pos > size()) return std::string::npos;
 363     size_type ret = qfind(subpiece(pos), c);
 364     return ret == npos ? ret : ret + pos;
 365   }
 366
 367   size_type find_first_of(Range needles) const {
 368     return qfind_first_of(*this, needles);
 369   }
 370
 371   size_type find_first_of(Range needles, size_t pos) const {
 372     if (pos > size()) return std::string::npos;
 373     size_type ret = qfind_first_of(subpiece(pos), needles);
 374     return ret == npos ? ret : ret + pos;
 375   }
 376
 377   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 378   size_type find_first_of(Iter needles) const {
 379     return find_first_of(Range(needles));
 380   }
 381
 382   // Works only for Range<const (unsigned) char*> which have Range(Iter) ctor
 383   size_type find_first_of(Iter needles, size_t pos) const {
 384     return find_first_of(Range(needles), pos);
 385   }
 386
 387   size_type find_first_of(Iter needles, size_t pos, size_t n) const {
 388     return find_first_of(Range(needles, n), pos);
 389   }
 390
 391   size_type find_first_of(value_type c) const {
 392     return find(c);
 393   }
 394
 395   size_type find_first_of(value_type c, size_t pos) const {
 396     return find(c, pos);
 397   }
 398
 399   void swap(Range& rhs) {
 400     std::swap(b_, rhs.b_);
 401     std::swap(e_, rhs.e_);
 402   }
 403
 404 private:
 405   Iter b_, e_;
 406 };
 407
 408 template <class Iter>
 409 const typename Range<Iter>::size_type Range<Iter>::npos = std::string::npos;
 410
 411 template <class T>
 412 void swap(Range<T>& lhs, Range<T>& rhs) {
 413   lhs.swap(rhs);
 414 }
 415
 416 /**
 417  * Create a range from two iterators, with type deduction.
 418  */
 419 template <class Iter>
 420 Range<Iter> makeRange(Iter first, Iter last) {
 421   return Range<Iter>(first, last);
 422 }
 423
 424 typedef Range<const char*> StringPiece;
 425 typedef Range<const unsigned char*> ByteRange;
 426
 427 std::ostream& operator<<(std::ostream& os, const StringPiece& piece);
 428
 429 /**
 430  * Templated comparison operators
 431  */
 432
 433 template <class T>
 434 inline bool operator==(const Range<T>& lhs, const Range<T>& rhs) {
 435   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
 436 }
 437
 438 template <class T>
 439 inline bool operator<(const Range<T>& lhs, const Range<T>& rhs) {
 440   return lhs.compare(rhs) < 0;
 441 }
 442
 443 /**
 444  * Specializations of comparison operators for StringPiece
 445  */
 446
 447 namespace detail {
 448
 449 template <class A, class B>
 450 struct ComparableAsStringPiece {
 451   enum {
 452     value =
 453     (std::is_convertible<A, StringPiece>::value
 454      && std::is_same<B, StringPiece>::value)
 455     ||
 456     (std::is_convertible<B, StringPiece>::value
 457      && std::is_same<A, StringPiece>::value)
 458   };
 459 };
 460
 461 } // namespace detail
 462
 463 /**
 464  * operator== through conversion for Range<const char*>
 465  */
 466 template <class T, class U>
 467 typename
 468 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 469 operator==(const T& lhs, const U& rhs) {
 470   return StringPiece(lhs) == StringPiece(rhs);
 471 }
 472
 473 /**
 474  * operator< through conversion for Range<const char*>
 475  */
 476 template <class T, class U>
 477 typename
 478 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 479 operator<(const T& lhs, const U& rhs) {
 480   return StringPiece(lhs) < StringPiece(rhs);
 481 }
 482
 483 /**
 484  * operator> through conversion for Range<const char*>
 485  */
 486 template <class T, class U>
 487 typename
 488 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 489 operator>(const T& lhs, const U& rhs) {
 490   return StringPiece(lhs) > StringPiece(rhs);
 491 }
 492
 493 /**
 494  * operator< through conversion for Range<const char*>
 495  */
 496 template <class T, class U>
 497 typename
 498 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 499 operator<=(const T& lhs, const U& rhs) {
 500   return StringPiece(lhs) <= StringPiece(rhs);
 501 }
 502
 503 /**
 504  * operator> through conversion for Range<const char*>
 505  */
 506 template <class T, class U>
 507 typename
 508 std::enable_if<detail::ComparableAsStringPiece<T, U>::value, bool>::type
 509 operator>=(const T& lhs, const U& rhs) {
 510   return StringPiece(lhs) >= StringPiece(rhs);
 511 }
 512
 513 struct StringPieceHash {
 514   std::size_t operator()(const StringPiece& str) const {
 515     return static_cast<std::size_t>(str.hash());
 516   }
 517 };
 518
 519 /**
 520  * Finds substrings faster than brute force by borrowing from Boyer-Moore
 521  */
 522 template <class T, class Comp>
 523 size_t qfind(const Range<T>& haystack,
 524              const Range<T>& needle,
 525              Comp eq) {
 526   // Don't use std::search, use a Boyer-Moore-like trick by comparing
 527   // the last characters first
 528   auto const nsize = needle.size();
 529   if (haystack.size() < nsize) {
 530     return std::string::npos;
 531   }
 532   if (!nsize) return 0;
 533   auto const nsize_1 = nsize - 1;
 534   auto const lastNeedle = needle[nsize_1];
 535
 536   // Boyer-Moore skip value for the last char in the needle. Zero is
 537   // not a valid value; skip will be computed the first time it's
 538   // needed.
 539   std::string::size_type skip = 0;
 540
 541   auto i = haystack.begin();
 542   auto iEnd = haystack.end() - nsize_1;
 543
 544   while (i < iEnd) {
 545     // Boyer-Moore: match the last element in the needle
 546     while (!eq(i[nsize_1], lastNeedle)) {
 547       if (++i == iEnd) {
 548         // not found
 549         return std::string::npos;
 550       }
 551     }
 552     // Here we know that the last char matches
 553     // Continue in pedestrian mode
 554     for (size_t j = 0; ; ) {
 555       assert(j < nsize);
 556       if (!eq(i[j], needle[j])) {
 557         // Not found, we can skip
 558         // Compute the skip value lazily
 559         if (skip == 0) {
 560           skip = 1;
 561           while (skip <= nsize_1 && !eq(needle[nsize_1 - skip], lastNeedle)) {
 562             ++skip;
 563           }
 564         }
 565         i += skip;
 566         break;
 567       }
 568       // Check if done searching
 569       if (++j == nsize) {
 570         // Yay
 571         return i - haystack.begin();
 572       }
 573     }
 574   }
 575   return std::string::npos;
 576 }
 577
 578 namespace detail {
 579
 580 size_t qfind_first_byte_of_nosse(const StringPiece& haystack,
 581                                  const StringPiece& needles);
 582
 583 #if FOLLY_HAVE_EMMINTRIN_H
 584 size_t qfind_first_byte_of_sse42(const StringPiece& haystack,
 585                                  const StringPiece& needles);
 586
 587 inline size_t qfind_first_byte_of(const StringPiece& haystack,
 588                                   const StringPiece& needles) {
 589   static auto const qfind_first_byte_of_fn =
 590     folly::CpuId().sse42() ? qfind_first_byte_of_sse42
 591                            : qfind_first_byte_of_nosse;
 592   return qfind_first_byte_of_fn(haystack, needles);
 593 }
 594
 595 #else
 596 inline size_t qfind_first_byte_of(const StringPiece& haystack,
 597                                   const StringPiece& needles) {
 598   return qfind_first_byte_of_nosse(haystack, needles);
 599 }
 600 #endif // FOLLY_HAVE_EMMINTRIN_H
 601
 602 } // namespace detail
 603
 604 template <class T, class Comp>
 605 size_t qfind_first_of(const Range<T> & haystack,
 606                       const Range<T> & needles,
 607                       Comp eq) {
 608   auto ret = std::find_first_of(haystack.begin(), haystack.end(),
 609                                 needles.begin(), needles.end(),
 610                                 eq);
 611   return ret == haystack.end() ? std::string::npos : ret - haystack.begin();
 612 }
 613
 614 struct AsciiCaseSensitive {
 615   bool operator()(char lhs, char rhs) const {
 616     return lhs == rhs;
 617   }
 618 };
 619
 620 struct AsciiCaseInsensitive {
 621   bool operator()(char lhs, char rhs) const {
 622     return toupper(lhs) == toupper(rhs);
 623   }
 624 };
 625
 626 extern const AsciiCaseSensitive asciiCaseSensitive;
 627 extern const AsciiCaseInsensitive asciiCaseInsensitive;
 628
 629 template <class T>
 630 size_t qfind(const Range<T>& haystack,
 631              const Range<T>& needle) {
 632   return qfind(haystack, needle, asciiCaseSensitive);
 633 }
 634
 635 template <class T>
 636 size_t qfind(const Range<T>& haystack,
 637              const typename Range<T>::value_type& needle) {
 638   auto pos = std::find(haystack.begin(), haystack.end(), needle);
 639   return pos == haystack.end() ? std::string::npos : pos - haystack.data();
 640 }
 641
 642 // specialization for StringPiece
 643 template <>
 644 inline size_t qfind(const Range<const char*>& haystack, const char& needle) {
 645   auto pos = static_cast<const char*>(
 646     ::memchr(haystack.data(), needle, haystack.size()));
 647   return pos == nullptr ? std::string::npos : pos - haystack.data();
 648 }
 649
 650 // specialization for ByteRange
 651 template <>
 652 inline size_t qfind(const Range<const unsigned char*>& haystack,
 653                     const unsigned char& needle) {
 654   auto pos = static_cast<const unsigned char*>(
 655     ::memchr(haystack.data(), needle, haystack.size()));
 656   return pos == nullptr ? std::string::npos : pos - haystack.data();
 657 }
 658
 659 template <class T>
 660 size_t qfind_first_of(const Range<T>& haystack,
 661                       const Range<T>& needles) {
 662   return qfind_first_of(haystack, needles, asciiCaseSensitive);
 663 }
 664
 665 // specialization for StringPiece
 666 template <>
 667 inline size_t qfind_first_of(const Range<const char*>& haystack,
 668                              const Range<const char*>& needles) {
 669   return detail::qfind_first_byte_of(haystack, needles);
 670 }
 671
 672 // specialization for ByteRange
 673 template <>
 674 inline size_t qfind_first_of(const Range<const unsigned char*>& haystack,
 675                              const Range<const unsigned char*>& needles) {
 676   return detail::qfind_first_byte_of(StringPiece(haystack),
 677                                      StringPiece(needles));
 678 }
 679 }  // !namespace folly
 680
 681 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range);
 682
 683 #endif // FOLLY_RANGE_H_