folly/Range.h

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