1 /* 2 * Copyright (c) Facebook, Inc. and its affiliates. 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 #pragma once 21 22 #include <folly/Portability.h> 23 #include <folly/hash/SpookyHashV2.h> 24 #include <folly/lang/CString.h> 25 #include <folly/lang/Exception.h> 26 #include <folly/portability/Constexpr.h> 27 28 #include <algorithm> 29 #include <array> 30 #include <cassert> 31 #include <climits> 32 #include <cstddef> 33 #include <cstring> 34 #include <iosfwd> 35 #include <iterator> 36 #include <stdexcept> 37 #include <string> 38 #include <type_traits> 39 40 #if FOLLY_HAS_STRING_VIEW 41 #include <string_view> // @manual 42 #endif 43 44 #if __has_include(<fmt/format.h>) 45 #include <fmt/format.h> 46 #endif 47 48 #include <folly/CpuId.h> 49 #include <folly/Likely.h> 50 #include <folly/Traits.h> 51 #include <folly/detail/RangeCommon.h> 52 #include <folly/detail/RangeSse42.h> 53 54 // Ignore shadowing warnings within this file, so includers can use -Wshadow. 55 FOLLY_PUSH_WARNING 56 FOLLY_GNU_DISABLE_WARNING("-Wshadow") 57 58 namespace folly { 59 60 /** 61 * Ubiquitous helper template for knowing what's a string. 62 */ 63 template <class T> 64 struct IsSomeString : std::false_type {}; 65 66 template <typename Alloc> 67 struct IsSomeString<std::basic_string<char, std::char_traits<char>, Alloc>> 68 : std::true_type {}; 69 70 template <class Iter> 71 class Range; 72 73 /** 74 * Finds the first occurrence of needle in haystack. The algorithm is on 75 * average faster than O(haystack.size() * needle.size()) but not as fast 76 * as Boyer-Moore. On the upside, it does not do any upfront 77 * preprocessing and does not allocate memory. 78 */ 79 template < 80 class Iter, 81 class Comp = std::equal_to<typename Range<Iter>::value_type>> 82 inline size_t qfind( 83 const Range<Iter>& haystack, const Range<Iter>& needle, Comp eq = Comp()); 84 85 /** 86 * Finds the first occurrence of needle in haystack. The result is the 87 * offset reported to the beginning of haystack, or string::npos if 88 * needle wasn't found. 89 */ 90 template <class Iter> 91 size_t qfind( 92 const Range<Iter>& haystack, 93 const typename Range<Iter>::value_type& needle); 94 95 /** 96 * Finds the last occurrence of needle in haystack. The result is the 97 * offset reported to the beginning of haystack, or string::npos if 98 * needle wasn't found. 99 */ 100 template <class Iter> 101 size_t rfind( 102 const Range<Iter>& haystack, 103 const typename Range<Iter>::value_type& needle); 104 105 /** 106 * Finds the first occurrence of any element of needle in 107 * haystack. The algorithm is O(haystack.size() * needle.size()). 108 */ 109 template <class Iter> 110 inline size_t qfind_first_of( 111 const Range<Iter>& haystack, const Range<Iter>& needle); 112 113 /** 114 * Small internal helper - returns the value just before an iterator. 115 */ 116 namespace detail { 117 118 /* 119 * Use IsCharPointer<T>::type to enable const char* or char*. 120 * Use IsCharPointer<T>::const_type to enable only const char*. 121 */ 122 template <class T> 123 struct IsCharPointer {}; 124 125 template <> 126 struct IsCharPointer<char*> { 127 using type = int; 128 }; 129 130 template <> 131 struct IsCharPointer<const char*> { 132 using const_type = int; 133 using type = int; 134 }; 135 136 template <class T> 137 struct IsUnsignedCharPointer {}; 138 139 template <> 140 struct IsUnsignedCharPointer<unsigned char*> { 141 using type = int; 142 }; 143 144 template <> 145 struct IsUnsignedCharPointer<const unsigned char*> { 146 using const_type = int; 147 using type = int; 148 }; 149 150 } // namespace detail 151 152 /** 153 * Range abstraction keeping a pair of iterators. We couldn't use 154 * boost's similar range abstraction because we need an API identical 155 * with the former StringPiece class, which is used by a lot of other 156 * code. This abstraction does fulfill the needs of boost's 157 * range-oriented algorithms though. 158 * 159 * (Keep memory lifetime in mind when using this class, since it 160 * doesn't manage the data it refers to - just like an iterator 161 * wouldn't.) 162 */ 163 template <class Iter> 164 class Range { 165 private: 166 template <typename Alloc> 167 using string = std::basic_string<char, std::char_traits<char>, Alloc>; 168 169 public: 170 using size_type = std::size_t; 171 using iterator = Iter; 172 using const_iterator = Iter; 173 using value_type = typename std::remove_reference< 174 typename std::iterator_traits<Iter>::reference>::type; 175 using difference_type = typename std::iterator_traits<Iter>::difference_type; 176 using reference = typename std::iterator_traits<Iter>::reference; 177 178 /** 179 * For MutableStringPiece and MutableByteRange we define StringPiece 180 * and ByteRange as const_range_type (for everything else its just 181 * identity). We do that to enable operations such as find with 182 * args which are const. 183 */ 184 using const_range_type = typename std::conditional< 185 std::is_same<Iter, char*>::value || 186 std::is_same<Iter, unsigned char*>::value, 187 Range<const value_type*>, 188 Range<Iter>>::type; 189 190 using traits_type = 191 std::char_traits<typename std::remove_const<value_type>::type>; 192 193 static const size_type npos; 194 195 // Works for all iterators 196 constexpr Range() : b_(), e_() {} 197 198 constexpr Range(const Range&) = default; 199 constexpr Range(Range&&) = default; 200 201 public: 202 // Works for all iterators 203 constexpr Range(Iter start, Iter end) : b_(start), e_(end) {} 204 205 // Works only for random-access iterators 206 constexpr Range(Iter start, size_t size) : b_(start), e_(start + size) {} 207 208 /* implicit */ Range(std::nullptr_t) = delete; 209 210 constexpr /* implicit */ Range(Iter str) 211 : b_(str), e_(str + constexpr_strlen(str)) { 212 static_assert( 213 std::is_same<int, typename detail::IsCharPointer<Iter>::type>::value, 214 "This constructor is only available for character ranges"); 215 } 216 217 template < 218 class Alloc, 219 class T = Iter, 220 typename detail::IsCharPointer<T>::const_type = 0> 221 /* implicit */ Range(const string<Alloc>& str) 222 : b_(str.data()), e_(b_ + str.size()) {} 223 224 template < 225 class Alloc, 226 class T = Iter, 227 typename detail::IsCharPointer<T>::const_type = 0> 228 Range(const string<Alloc>& str, typename string<Alloc>::size_type startFrom) { 229 if (UNLIKELY(startFrom > str.size())) { 230 throw_exception<std::out_of_range>("index out of range"); 231 } 232 b_ = str.data() + startFrom; 233 e_ = str.data() + str.size(); 234 } 235 236 template < 237 class Alloc, 238 class T = Iter, 239 typename detail::IsCharPointer<T>::const_type = 0> 240 Range( 241 const string<Alloc>& str, 242 typename string<Alloc>::size_type startFrom, 243 typename string<Alloc>::size_type size) { 244 if (UNLIKELY(startFrom > str.size())) { 245 throw_exception<std::out_of_range>("index out of range"); 246 } 247 b_ = str.data() + startFrom; 248 if (str.size() - startFrom < size) { 249 e_ = str.data() + str.size(); 250 } else { 251 e_ = b_ + size; 252 } 253 } 254 255 Range(const Range& other, size_type first, size_type length = npos) 256 : Range(other.subpiece(first, length)) {} 257 258 template < 259 class Container, 260 class = typename std::enable_if< 261 std::is_same<Iter, typename Container::const_pointer>::value>::type, 262 class = decltype( 263 Iter(std::declval<Container const&>().data()), 264 Iter( 265 std::declval<Container const&>().data() + 266 std::declval<Container const&>().size()))> 267 /* implicit */ constexpr Range(Container const& container) 268 : Range(container.data(), container.size()) {} 269 270 template < 271 class Container, 272 class = typename std::enable_if< 273 std::is_same<Iter, typename Container::const_pointer>::value>::type, 274 class = decltype( 275 Iter(std::declval<Container const&>().data()), 276 Iter( 277 std::declval<Container const&>().data() + 278 std::declval<Container const&>().size()))> 279 Range(Container const& container, typename Container::size_type startFrom) { 280 auto const cdata = container.data(); 281 auto const csize = container.size(); 282 if (UNLIKELY(startFrom > csize)) { 283 throw_exception<std::out_of_range>("index out of range"); 284 } 285 b_ = cdata + startFrom; 286 e_ = cdata + csize; 287 } 288 289 template < 290 class Container, 291 class = typename std::enable_if< 292 std::is_same<Iter, typename Container::const_pointer>::value>::type, 293 class = decltype( 294 Iter(std::declval<Container const&>().data()), 295 Iter( 296 std::declval<Container const&>().data() + 297 std::declval<Container const&>().size()))> 298 Range( 299 Container const& container, 300 typename Container::size_type startFrom, 301 typename Container::size_type size) { 302 auto const cdata = container.data(); 303 auto const csize = container.size(); 304 if (UNLIKELY(startFrom > csize)) { 305 throw_exception<std::out_of_range>("index out of range"); 306 } 307 b_ = cdata + startFrom; 308 if (csize - startFrom < size) { 309 e_ = cdata + csize; 310 } else { 311 e_ = b_ + size; 312 } 313 } 314 315 // Allow explicit construction of ByteRange from std::string_view or 316 // std::string. Given that we allow implicit construction of ByteRange from 317 // StringPiece, it makes sense to allow this explicit construction, and avoids 318 // callers having to say ByteRange{StringPiece{str}} when they want a 319 // ByteRange pointing to data in a std::string. 320 template < 321 class Container, 322 class T = Iter, 323 typename detail::IsUnsignedCharPointer<T>::const_type = 0, 324 class = typename std::enable_if< 325 std::is_same<typename Container::const_pointer, const char*>::value 326 >::type, 327 class = decltype( 328 Iter(std::declval<Container const&>().data()), 329 Iter( 330 std::declval<Container const&>().data() + 331 std::declval<Container const&>().size()))> 332 explicit Range(const Container& str) 333 : b_(reinterpret_cast<Iter>(str.data())), e_(b_ + str.size()) {} 334 335 // Allow implicit conversion from Range<const char*> (aka StringPiece) to 336 // Range<const unsigned char*> (aka ByteRange), as they're both frequently 337 // used to represent ranges of bytes. Allow explicit conversion in the other 338 // direction. 339 template < 340 class OtherIter, 341 typename std::enable_if< 342 (std::is_same<Iter, const unsigned char*>::value && 343 (std::is_same<OtherIter, const char*>::value || 344 std::is_same<OtherIter, char*>::value)), 345 int>::type = 0> 346 /* implicit */ Range(const Range<OtherIter>& other) 347 : b_(reinterpret_cast<const unsigned char*>(other.begin())), 348 e_(reinterpret_cast<const unsigned char*>(other.end())) {} 349 350 template < 351 class OtherIter, 352 typename std::enable_if< 353 (std::is_same<Iter, unsigned char*>::value && 354 std::is_same<OtherIter, char*>::value), 355 int>::type = 0> 356 /* implicit */ Range(const Range<OtherIter>& other) 357 : b_(reinterpret_cast<unsigned char*>(other.begin())), 358 e_(reinterpret_cast<unsigned char*>(other.end())) {} 359 360 template < 361 class OtherIter, 362 typename std::enable_if< 363 (std::is_same<Iter, const char*>::value && 364 (std::is_same<OtherIter, const unsigned char*>::value || 365 std::is_same<OtherIter, unsigned char*>::value)), 366 int>::type = 0> 367 explicit Range(const Range<OtherIter>& other) 368 : b_(reinterpret_cast<const char*>(other.begin())), 369 e_(reinterpret_cast<const char*>(other.end())) {} 370 371 template < 372 class OtherIter, 373 typename std::enable_if< 374 (std::is_same<Iter, char*>::value && 375 std::is_same<OtherIter, unsigned char*>::value), 376 int>::type = 0> 377 explicit Range(const Range<OtherIter>& other) 378 : b_(reinterpret_cast<char*>(other.begin())), 379 e_(reinterpret_cast<char*>(other.end())) {} 380 381 // Allow implicit conversion from Range<From> to Range<To> if From is 382 // implicitly convertible to To. 383 template < 384 class OtherIter, 385 typename std::enable_if< 386 (!std::is_same<Iter, OtherIter>::value && 387 std::is_convertible<OtherIter, Iter>::value), 388 int>::type = 0> 389 constexpr /* implicit */ Range(const Range<OtherIter>& other) 390 : b_(other.begin()), e_(other.end()) {} 391 392 // Allow explicit conversion from Range<From> to Range<To> if From is 393 // explicitly convertible to To. 394 template < 395 class OtherIter, 396 typename std::enable_if< 397 (!std::is_same<Iter, OtherIter>::value && 398 !std::is_convertible<OtherIter, Iter>::value && 399 std::is_constructible<Iter, const OtherIter&>::value), 400 int>::type = 0> 401 constexpr explicit Range(const Range<OtherIter>& other) 402 : b_(other.begin()), e_(other.end()) {} 403 404 /** 405 * Allow explicit construction of Range() from a std::array of a 406 * convertible type. 407 * 408 * For instance, this allows constructing StringPiece from a 409 * std::array<char, N> or a std::array<const char, N> 410 */ 411 template < 412 class T, 413 size_t N, 414 typename = typename std::enable_if< 415 std::is_convertible<const T*, Iter>::value>::type> 416 constexpr explicit Range(const std::array<T, N>& array) 417 : b_{array.empty() ? nullptr : &array.at(0)}, 418 e_{array.empty() ? nullptr : &array.at(0) + N} {} 419 template < 420 class T, 421 size_t N, 422 typename = 423 typename std::enable_if<std::is_convertible<T*, Iter>::value>::type> 424 constexpr explicit Range(std::array<T, N>& array) 425 : b_{array.empty() ? nullptr : &array.at(0)}, 426 e_{array.empty() ? nullptr : &array.at(0) + N} {} 427 428 Range& operator=(const Range& rhs) & = default; 429 Range& operator=(Range&& rhs) & = default; 430 431 template < 432 class Alloc, 433 class T = Iter, 434 typename detail::IsCharPointer<T>::const_type = 0> 435 Range& operator=(string<Alloc>&& rhs) = delete; 436 437 void clear() { 438 b_ = Iter(); 439 e_ = Iter(); 440 } 441 442 void assign(Iter start, Iter end) { 443 b_ = start; 444 e_ = end; 445 } 446 447 void reset(Iter start, size_type size) { 448 b_ = start; 449 e_ = start + size; 450 } 451 452 // Works only for Range<const char*> 453 template <typename Alloc> 454 void reset(const string<Alloc>& str) { 455 reset(str.data(), str.size()); 456 } 457 458 constexpr size_type size() const { 459 #if __clang__ || !__GNUC__ || __GNUC__ >= 7 460 assert(b_ <= e_); 461 #endif 462 return size_type(e_ - b_); 463 } 464 constexpr size_type walk_size() const { 465 return size_type(std::distance(b_, e_)); 466 } 467 constexpr bool empty() const { return b_ == e_; } 468 constexpr Iter data() const { return b_; } 469 constexpr Iter start() const { return b_; } 470 constexpr Iter begin() const { return b_; } 471 constexpr Iter end() const { return e_; } 472 constexpr Iter cbegin() const { return b_; } 473 constexpr Iter cend() const { return e_; } 474 value_type& front() { 475 assert(b_ < e_); 476 return *b_; 477 } 478 value_type& back() { 479 assert(b_ < e_); 480 return *std::prev(e_); 481 } 482 const value_type& front() const { 483 assert(b_ < e_); 484 return *b_; 485 } 486 const value_type& back() const { 487 assert(b_ < e_); 488 return *std::prev(e_); 489 } 490 491 private: 492 // It would be nice to be able to implicit convert to any target type 493 // T for which either an (Iter, Iter) or (Iter, size_type) noexcept 494 // constructor was available, and explicitly convert to any target 495 // type for which those signatures were available but not noexcept. 496 // The problem is that this creates ambiguity when there is also a 497 // T constructor that takes a type U that is implicitly convertible 498 // from Range. 499 // 500 // To avoid ambiguity, we need to avoid having explicit operator T 501 // and implicit operator U coexist when T is constructible from U. 502 // U cannot be deduced when searching for operator T (and C++ won't 503 // perform an existential search for it), so we must limit the implicit 504 // target types to a finite set that we can enumerate. 505 // 506 // At the moment the set of implicit target types consists of just 507 // std::string_view (when it is available). 508 #if FOLLY_HAS_STRING_VIEW 509 struct NotStringView {}; 510 template <typename ValueType> 511 struct StringViewType 512 : std::conditional< 513 std::is_trivial<std::remove_const_t<ValueType>>::value, 514 std::basic_string_view<std::remove_const_t<ValueType>>, 515 NotStringView> {}; 516 517 template <typename Target> 518 struct IsConstructibleViaStringView 519 : Conjunction< 520 std::is_constructible< 521 _t<StringViewType<value_type>>, 522 Iter const&, 523 size_type>, 524 std::is_constructible<Target, _t<StringViewType<value_type>>>> {}; 525 #else 526 template <typename Target> 527 using IsConstructibleViaStringView = std::false_type; 528 #endif 529 530 public: 531 /// explicit operator conversion to any compatible type 532 /// 533 /// A compatible type is one which is constructible with an iterator and a 534 /// size (preferred), or a pair of iterators (fallback), passed by const-ref. 535 /// 536 /// Participates in overload resolution precisely when the target type is 537 /// compatible. This allows std::is_constructible compile-time checks to work. 538 template < 539 typename Tgt, 540 std::enable_if_t< 541 std::is_constructible<Tgt, Iter const&, size_type>::value && 542 !IsConstructibleViaStringView<Tgt>::value, 543 int> = 0> 544 constexpr explicit operator Tgt() const noexcept( 545 std::is_nothrow_constructible<Tgt, Iter const&, size_type>::value) { 546 return Tgt(b_, walk_size()); 547 } 548 template < 549 typename Tgt, 550 std::enable_if_t< 551 !std::is_constructible<Tgt, Iter const&, size_type>::value && 552 std::is_constructible<Tgt, Iter const&, Iter const&>::value && 553 !IsConstructibleViaStringView<Tgt>::value, 554 int> = 0> 555 constexpr explicit operator Tgt() const noexcept( 556 std::is_nothrow_constructible<Tgt, Iter const&, Iter const&>::value) { 557 return Tgt(b_, e_); 558 } 559 560 #if FOLLY_HAS_STRING_VIEW 561 /// implicit operator conversion to std::string_view 562 template < 563 typename Tgt, 564 typename ValueType = value_type, 565 std::enable_if_t< 566 StrictConjunction< 567 std::is_same<Tgt, _t<StringViewType<ValueType>>>, 568 std::is_constructible< 569 _t<StringViewType<ValueType>>, 570 Iter const&, 571 size_type>>::value, 572 int> = 0> 573 constexpr operator Tgt() const noexcept( 574 std::is_nothrow_constructible<Tgt, Iter const&, size_type>::value) { 575 return Tgt(b_, walk_size()); 576 } 577 #endif 578 579 /// explicit non-operator conversion to any compatible type 580 /// 581 /// A compatible type is one which is constructible with an iterator and a 582 /// size (preferred), or a pair of iterators (fallback), passed by const-ref. 583 /// 584 /// Participates in overload resolution precisely when the target type is 585 /// compatible. This allows is_invocable compile-time checks to work. 586 /// 587 /// Provided in addition to the explicit operator conversion to permit passing 588 /// additional arguments to the target type constructor. A canonical example 589 /// of an additional argument might be an allocator, where the target type is 590 /// some specialization of std::vector or std::basic_string in a context which 591 /// requires a non-default-constructed allocator. 592 template <typename Tgt, typename... Args> 593 constexpr std::enable_if_t< 594 std::is_constructible<Tgt, Iter const&, size_type>::value, 595 Tgt> 596 to(Args&&... args) const noexcept( 597 std::is_nothrow_constructible<Tgt, Iter const&, size_type, Args&&...>:: 598 value) { 599 return Tgt(b_, walk_size(), static_cast<Args&&>(args)...); 600 } 601 template <typename Tgt, typename... Args> 602 constexpr std::enable_if_t< 603 !std::is_constructible<Tgt, Iter const&, size_type>::value && 604 std::is_constructible<Tgt, Iter const&, Iter const&>::value, 605 Tgt> 606 to(Args&&... args) const noexcept( 607 std::is_nothrow_constructible<Tgt, Iter const&, Iter const&, Args&&...>:: 608 value) { 609 return Tgt(b_, e_, static_cast<Args&&>(args)...); 610 } 611 612 // Works only for Range<const char*> and Range<char*> 613 std::string str() const { return to<std::string>(); } 614 std::string toString() const { return to<std::string>(); } 615 616 const_range_type castToConst() const { return const_range_type(*this); } 617 618 int compare(const const_range_type& o) const { 619 const size_type tsize = this->size(); 620 const size_type osize = o.size(); 621 const size_type msize = std::min(tsize, osize); 622 int r = traits_type::compare(data(), o.data(), msize); 623 if (r == 0 && tsize != osize) { 624 // We check the signed bit of the subtraction and bit shift it 625 // to produce either 0 or 2. The subtraction yields the 626 // comparison values of either -1 or 1. 627 r = (static_cast<int>((osize - tsize) >> (CHAR_BIT * sizeof(size_t) - 1)) 628 << 1) - 629 1; 630 } 631 return r; 632 } 633 634 value_type& operator[](size_t i) { 635 assert(i < size()); 636 return b_[i]; 637 } 638 639 const value_type& operator[](size_t i) const { 640 assert(i < size()); 641 return b_[i]; 642 } 643 644 value_type& at(size_t i) { 645 if (i >= size()) { 646 throw_exception<std::out_of_range>("index out of range"); 647 } 648 return b_[i]; 649 } 650 651 const value_type& at(size_t i) const { 652 if (i >= size()) { 653 throw_exception<std::out_of_range>("index out of range"); 654 } 655 return b_[i]; 656 } 657 658 // Do NOT use this function, which was left behind for backwards 659 // compatibility. Use SpookyHashV2 instead -- it is faster, and produces 660 // a 64-bit hash, which means dramatically fewer collisions in large maps. 661 // (The above advice does not apply if you are targeting a 32-bit system.) 662 // 663 // Works only for Range<const char*> and Range<char*> 664 // 665 // 666 // ** WANT TO GET RID OF THIS LINT? ** 667 // 668 // A) Use a better hash function (*cough*folly::Hash*cough*), but 669 // only if you don't serialize data in a format that depends on 670 // this formula (ie the writer and reader assume this exact hash 671 // function is used). 672 // 673 // B) If you have to use this exact function then make your own hasher 674 // object and copy the body over (see thrift example: D3972362). 675 // https://github.com/facebook/fbthrift/commit/f8ed502e24ab4a32a9d5f266580 676 [[deprecated( 677 "Replace with folly::Hash if the hash is not serialized")]] uint32_t 678 hash() const { 679 // Taken from fbi/nstring.h: 680 // Quick and dirty bernstein hash...fine for short ascii strings 681 uint32_t hash = 5381; 682 for (size_t ix = 0; ix < size(); ix++) { 683 hash = ((hash << 5) + hash) + b_[ix]; 684 } 685 return hash; 686 } 687 688 void advance(size_type n) { 689 if (UNLIKELY(n > size())) { 690 throw_exception<std::out_of_range>("index out of range"); 691 } 692 b_ += n; 693 } 694 695 void subtract(size_type n) { 696 if (UNLIKELY(n > size())) { 697 throw_exception<std::out_of_range>("index out of range"); 698 } 699 e_ -= n; 700 } 701 702 // Returns a window into the current range, starting at first, and spans 703 // length characters (or until the end of the current range, whichever comes 704 // first). Throws if first is past the end of the current range. 705 Range subpiece(size_type first, size_type length = npos) const { 706 if (UNLIKELY(first > size())) { 707 throw_exception<std::out_of_range>("index out of range"); 708 } 709 710 return Range(b_ + first, std::min(length, size() - first)); 711 } 712 713 // unchecked versions 714 void uncheckedAdvance(size_type n) { 715 assert(n <= size()); 716 b_ += n; 717 } 718 719 void uncheckedSubtract(size_type n) { 720 assert(n <= size()); 721 e_ -= n; 722 } 723 724 Range uncheckedSubpiece(size_type first, size_type length = npos) const { 725 assert(first <= size()); 726 return Range(b_ + first, std::min(length, size() - first)); 727 } 728 729 void pop_front() { 730 assert(b_ < e_); 731 ++b_; 732 } 733 734 void pop_back() { 735 assert(b_ < e_); 736 --e_; 737 } 738 739 // string work-alike functions 740 size_type find(const_range_type str) const { 741 return qfind(castToConst(), str); 742 } 743 744 size_type find(const_range_type str, size_t pos) const { 745 if (pos > size()) { 746 return std::string::npos; 747 } 748 size_t ret = qfind(castToConst().subpiece(pos), str); 749 return ret == npos ? ret : ret + pos; 750 } 751 752 size_type find(Iter s, size_t pos, size_t n) const { 753 if (pos > size()) { 754 return std::string::npos; 755 } 756 auto forFinding = castToConst(); 757 size_t ret = qfind( 758 pos ? forFinding.subpiece(pos) : forFinding, const_range_type(s, n)); 759 return ret == npos ? ret : ret + pos; 760 } 761 762 // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor 763 size_type find(const Iter s) const { 764 return qfind(castToConst(), const_range_type(s)); 765 } 766 767 // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor 768 size_type find(const Iter s, size_t pos) const { 769 if (pos > size()) { 770 return std::string::npos; 771 } 772 size_type ret = qfind(castToConst().subpiece(pos), const_range_type(s)); 773 return ret == npos ? ret : ret + pos; 774 } 775 776 size_type find(value_type c) const { return qfind(castToConst(), c); } 777 778 size_type rfind(value_type c) const { return folly::rfind(castToConst(), c); } 779 780 size_type find(value_type c, size_t pos) const { 781 if (pos > size()) { 782 return std::string::npos; 783 } 784 size_type ret = qfind(castToConst().subpiece(pos), c); 785 return ret == npos ? ret : ret + pos; 786 } 787 788 size_type find_first_of(const_range_type needles) const { 789 return qfind_first_of(castToConst(), needles); 790 } 791 792 size_type find_first_of(const_range_type needles, size_t pos) const { 793 if (pos > size()) { 794 return std::string::npos; 795 } 796 size_type ret = qfind_first_of(castToConst().subpiece(pos), needles); 797 return ret == npos ? ret : ret + pos; 798 } 799 800 // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor 801 size_type find_first_of(Iter needles) const { 802 return find_first_of(const_range_type(needles)); 803 } 804 805 // Works only for Range<(const) (unsigned) char*> which have Range(Iter) ctor 806 size_type find_first_of(Iter needles, size_t pos) const { 807 return find_first_of(const_range_type(needles), pos); 808 } 809 810 size_type find_first_of(Iter needles, size_t pos, size_t n) const { 811 return find_first_of(const_range_type(needles, n), pos); 812 } 813 814 size_type find_first_of(value_type c) const { return find(c); } 815 816 size_type find_first_of(value_type c, size_t pos) const { 817 return find(c, pos); 818 } 819 820 /** 821 * Determine whether the range contains the given subrange or item. 822 * 823 * Note: Call find() directly if the index is needed. 824 */ 825 bool contains(const const_range_type& other) const { 826 return find(other) != std::string::npos; 827 } 828 829 bool contains(const value_type& other) const { 830 return find(other) != std::string::npos; 831 } 832 833 void swap(Range& rhs) { 834 std::swap(b_, rhs.b_); 835 std::swap(e_, rhs.e_); 836 } 837 838 /** 839 * Does this Range start with another range? 840 */ 841 bool startsWith(const const_range_type& other) const { 842 return size() >= other.size() && 843 castToConst().subpiece(0, other.size()) == other; 844 } 845 bool startsWith(value_type c) const { return !empty() && front() == c; } 846 847 template <class Comp> 848 bool startsWith(const const_range_type& other, Comp&& eq) const { 849 if (size() < other.size()) { 850 return false; 851 } 852 auto const trunc = subpiece(0, other.size()); 853 return std::equal( 854 trunc.begin(), trunc.end(), other.begin(), std::forward<Comp>(eq)); 855 } 856 857 /** 858 * Does this Range end with another range? 859 */ 860 bool endsWith(const const_range_type& other) const { 861 return size() >= other.size() && 862 castToConst().subpiece(size() - other.size()) == other; 863 } 864 bool endsWith(value_type c) const { return !empty() && back() == c; } 865 866 template <class Comp> 867 bool endsWith(const const_range_type& other, Comp&& eq) const { 868 if (size() < other.size()) { 869 return false; 870 } 871 auto const trunc = subpiece(size() - other.size()); 872 return std::equal( 873 trunc.begin(), trunc.end(), other.begin(), std::forward<Comp>(eq)); 874 } 875 876 template <class Comp> 877 bool equals(const const_range_type& other, Comp&& eq) const { 878 return size() == other.size() && 879 std::equal(begin(), end(), other.begin(), std::forward<Comp>(eq)); 880 } 881 882 /** 883 * Remove the items in [b, e), as long as this subrange is at the beginning 884 * or end of the Range. 885 * 886 * Required for boost::algorithm::trim() 887 */ 888 void erase(Iter b, Iter e) { 889 if (b == b_) { 890 b_ = e; 891 } else if (e == e_) { 892 e_ = b; 893 } else { 894 throw_exception<std::out_of_range>("index out of range"); 895 } 896 } 897 898 /** 899 * Remove the given prefix and return true if the range starts with the given 900 * prefix; return false otherwise. 901 */ 902 bool removePrefix(const const_range_type& prefix) { 903 return startsWith(prefix) && (b_ += prefix.size(), true); 904 } 905 bool removePrefix(value_type prefix) { 906 return startsWith(prefix) && (++b_, true); 907 } 908 909 /** 910 * Remove the given suffix and return true if the range ends with the given 911 * suffix; return false otherwise. 912 */ 913 bool removeSuffix(const const_range_type& suffix) { 914 return endsWith(suffix) && (e_ -= suffix.size(), true); 915 } 916 bool removeSuffix(value_type suffix) { 917 return endsWith(suffix) && (--e_, true); 918 } 919 920 /** 921 * Replaces the content of the range, starting at position 'pos', with 922 * contents of 'replacement'. Entire 'replacement' must fit into the 923 * range. Returns false if 'replacements' does not fit. Example use: 924 * 925 * char in[] = "buffer"; 926 * auto msp = MutableStringPiece(input); 927 * EXPECT_TRUE(msp.replaceAt(2, "tt")); 928 * EXPECT_EQ(msp, "butter"); 929 * 930 * // not enough space 931 * EXPECT_FALSE(msp.replace(msp.size() - 1, "rr")); 932 * EXPECT_EQ(msp, "butter"); // unchanged 933 */ 934 bool replaceAt(size_t pos, const_range_type replacement) { 935 if (size() < pos + replacement.size()) { 936 return false; 937 } 938 939 std::copy(replacement.begin(), replacement.end(), begin() + pos); 940 941 return true; 942 } 943 944 /** 945 * Replaces all occurrences of 'source' with 'dest'. Returns number 946 * of replacements made. Source and dest have to have the same 947 * length. Throws if the lengths are different. If 'source' is a 948 * pattern that is overlapping with itself, we perform sequential 949 * replacement: "aaaaaaa".replaceAll("aa", "ba") --> "bababaa" 950 * 951 * Example use: 952 * 953 * char in[] = "buffer"; 954 * auto msp = MutableStringPiece(input); 955 * EXPECT_EQ(msp.replaceAll("ff","tt"), 1); 956 * EXPECT_EQ(msp, "butter"); 957 */ 958 size_t replaceAll(const_range_type source, const_range_type dest) { 959 if (source.size() != dest.size()) { 960 throw_exception<std::invalid_argument>( 961 "replacement must have the same size as source"); 962 } 963 964 if (dest.empty()) { 965 return 0; 966 } 967 968 size_t pos = 0; 969 size_t num_replaced = 0; 970 size_type found = std::string::npos; 971 while ((found = find(source, pos)) != std::string::npos) { 972 replaceAt(found, dest); 973 pos += source.size(); 974 ++num_replaced; 975 } 976 977 return num_replaced; 978 } 979 980 /** 981 * Splits this `Range` `[b, e)` in the position `i` dictated by the next 982 * occurrence of `delimiter`. 983 * 984 * Returns a new `Range` `[b, i)` and adjusts this range to start right after 985 * the delimiter's position. This range will be empty if the delimiter is not 986 * found. If called on an empty `Range`, both this and the returned `Range` 987 * will be empty. 988 * 989 * Example: 990 * 991 * folly::StringPiece s("sample string for split_next"); 992 * auto p = s.split_step(' '); 993 * 994 * // prints "string for split_next" 995 * cout << s << endl; 996 * 997 * // prints "sample" 998 * cout << p << endl; 999 * 1000 * Example 2: 1001 * 1002 * void tokenize(StringPiece s, char delimiter) { 1003 * while (!s.empty()) { 1004 * cout << s.split_step(delimiter); 1005 * } 1006 * } 1007 * 1008 * @author: Marcelo Juchem <marcelo@fb.com> 1009 */ 1010 Range split_step(value_type delimiter) { 1011 auto i = std::find(b_, e_, delimiter); 1012 Range result(b_, i); 1013 1014 b_ = i == e_ ? e_ : std::next(i); 1015 1016 return result; 1017 } 1018 1019 Range split_step(Range delimiter) { 1020 auto i = find(delimiter); 1021 Range result(b_, i == std::string::npos ? size() : i); 1022 1023 b_ = result.end() == e_ 1024 ? e_ 1025 : std::next( 1026 result.end(), 1027 typename std::iterator_traits<Iter>::difference_type( 1028 delimiter.size())); 1029 1030 return result; 1031 } 1032 1033 /** 1034 * Convenience method that calls `split_step()` and passes the result to a 1035 * functor, returning whatever the functor does. Any additional arguments 1036 * `args` passed to this function are perfectly forwarded to the functor. 1037 * 1038 * Say you have a functor with this signature: 1039 * 1040 * Foo fn(Range r) { } 1041 * 1042 * `split_step()`'s return type will be `Foo`. It works just like: 1043 * 1044 * auto result = fn(myRange.split_step(' ')); 1045 * 1046 * A functor returning `void` is also supported. 1047 * 1048 * Example: 1049 * 1050 * void do_some_parsing(folly::StringPiece s) { 1051 * auto version = s.split_step(' ', [&](folly::StringPiece x) { 1052 * if (x.empty()) { 1053 * throw std::invalid_argument("empty string"); 1054 * } 1055 * return std::strtoull(x.begin(), x.end(), 16); 1056 * }); 1057 * 1058 * // ... 1059 * } 1060 * 1061 * struct Foo { 1062 * void parse(folly::StringPiece s) { 1063 * s.split_step(' ', parse_field, bar, 10); 1064 * s.split_step('\t', parse_field, baz, 20); 1065 * 1066 * auto const kludge = [](folly::StringPiece x, int &out, int def) { 1067 * if (x == "null") { 1068 * out = 0; 1069 * } else { 1070 * parse_field(x, out, def); 1071 * } 1072 * }; 1073 * 1074 * s.split_step('\t', kludge, gaz); 1075 * s.split_step(' ', kludge, foo); 1076 * } 1077 * 1078 * private: 1079 * int bar; 1080 * int baz; 1081 * int gaz; 1082 * int foo; 1083 * 1084 * static parse_field(folly::StringPiece s, int &out, int def) { 1085 * try { 1086 * out = folly::to<int>(s); 1087 * } catch (std::exception const &) { 1088 * value = def; 1089 * } 1090 * } 1091 * }; 1092 * 1093 * @author: Marcelo Juchem <marcelo@fb.com> 1094 */ 1095 template <typename TProcess, typename... Args> 1096 auto split_step(value_type delimiter, TProcess&& process, Args&&... args) 1097 -> decltype(process(std::declval<Range>(), std::forward<Args>(args)...)) { 1098 return process(split_step(delimiter), std::forward<Args>(args)...); 1099 } 1100 1101 template <typename TProcess, typename... Args> 1102 auto split_step(Range delimiter, TProcess&& process, Args&&... args) 1103 -> decltype(process(std::declval<Range>(), std::forward<Args>(args)...)) { 1104 return process(split_step(delimiter), std::forward<Args>(args)...); 1105 } 1106 1107 private: 1108 Iter b_; 1109 Iter e_; 1110 }; 1111 1112 template <class Iter> 1113 const typename Range<Iter>::size_type Range<Iter>::npos = std::string::npos; 1114 1115 template <class Iter> 1116 void swap(Range<Iter>& lhs, Range<Iter>& rhs) { 1117 lhs.swap(rhs); 1118 } 1119 1120 /** 1121 * Create a range from two iterators, with type deduction. 1122 */ 1123 template <class Iter> 1124 constexpr Range<Iter> range(Iter first, Iter last) { 1125 return Range<Iter>(first, last); 1126 } 1127 1128 /* 1129 * Creates a range to reference the contents of a contiguous-storage container. 1130 */ 1131 // Use pointers for types with '.data()' member 1132 template <class Collection> 1133 constexpr auto range(Collection& v) -> Range<decltype(v.data())> { 1134 return Range<decltype(v.data())>(v.data(), v.data() + v.size()); 1135 } 1136 template <class Collection> 1137 constexpr auto range(Collection const& v) -> Range<decltype(v.data())> { 1138 return Range<decltype(v.data())>(v.data(), v.data() + v.size()); 1139 } 1140 template <class Collection> 1141 constexpr auto crange(Collection const& v) -> Range<decltype(v.data())> { 1142 return Range<decltype(v.data())>(v.data(), v.data() + v.size()); 1143 } 1144 1145 template <class T, size_t n> 1146 constexpr Range<T*> range(T (&array)[n]) { 1147 return Range<T*>(array, array + n); 1148 } 1149 template <class T, size_t n> 1150 constexpr Range<T const*> range(T const (&array)[n]) { 1151 return Range<T const*>(array, array + n); 1152 } 1153 template <class T, size_t n> 1154 constexpr Range<T const*> crange(T const (&array)[n]) { 1155 return Range<T const*>(array, array + n); 1156 } 1157 1158 template <class T, size_t n> 1159 constexpr Range<T*> range(std::array<T, n>& array) { 1160 return Range<T*>{array}; 1161 } 1162 template <class T, size_t n> 1163 constexpr Range<T const*> range(std::array<T, n> const& array) { 1164 return Range<T const*>{array}; 1165 } 1166 template <class T, size_t n> 1167 constexpr Range<T const*> crange(std::array<T, n> const& array) { 1168 return Range<T const*>{array}; 1169 } 1170 1171 using StringPiece = Range<const char*>; 1172 using MutableStringPiece = Range<char*>; 1173 using ByteRange = Range<const unsigned char*>; 1174 using MutableByteRange = Range<unsigned char*>; 1175 1176 template <class C> 1177 std::basic_ostream<C>& operator<<( 1178 std::basic_ostream<C>& os, Range<C const*> piece) { 1179 using StreamSize = decltype(os.width()); 1180 os.write(piece.start(), static_cast<StreamSize>(piece.size())); 1181 return os; 1182 } 1183 1184 template <class C> 1185 std::basic_ostream<C>& operator<<(std::basic_ostream<C>& os, Range<C*> piece) { 1186 using StreamSize = decltype(os.width()); 1187 os.write(piece.start(), static_cast<StreamSize>(piece.size())); 1188 return os; 1189 } 1190 1191 /** 1192 * Templated comparison operators 1193 */ 1194 1195 template <class Iter> 1196 inline bool operator==(const Range<Iter>& lhs, const Range<Iter>& rhs) { 1197 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; 1198 } 1199 1200 template <class Iter> 1201 inline bool operator!=(const Range<Iter>& lhs, const Range<Iter>& rhs) { 1202 return !(operator==(lhs, rhs)); 1203 } 1204 1205 template <class Iter> 1206 inline bool operator<(const Range<Iter>& lhs, const Range<Iter>& rhs) { 1207 return lhs.compare(rhs) < 0; 1208 } 1209 1210 template <class Iter> 1211 inline bool operator<=(const Range<Iter>& lhs, const Range<Iter>& rhs) { 1212 return lhs.compare(rhs) <= 0; 1213 } 1214 1215 template <class Iter> 1216 inline bool operator>(const Range<Iter>& lhs, const Range<Iter>& rhs) { 1217 return lhs.compare(rhs) > 0; 1218 } 1219 1220 template <class Iter> 1221 inline bool operator>=(const Range<Iter>& lhs, const Range<Iter>& rhs) { 1222 return lhs.compare(rhs) >= 0; 1223 } 1224 1225 /** 1226 * Specializations of comparison operators for StringPiece 1227 */ 1228 1229 namespace detail { 1230 1231 template <class A, class B> 1232 struct ComparableAsStringPiece { 1233 enum { 1234 value = (std::is_convertible<A, StringPiece>::value && 1235 std::is_same<B, StringPiece>::value) || 1236 (std::is_convertible<B, StringPiece>::value && 1237 std::is_same<A, StringPiece>::value) 1238 }; 1239 }; 1240 1241 } // namespace detail 1242 1243 /** 1244 * operator== through conversion for Range<const char*> 1245 */ 1246 template <class T, class U> 1247 std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator==( 1248 const T& lhs, const U& rhs) { 1249 return StringPiece(lhs) == StringPiece(rhs); 1250 } 1251 1252 /** 1253 * operator!= through conversion for Range<const char*> 1254 */ 1255 template <class T, class U> 1256 std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator!=( 1257 const T& lhs, const U& rhs) { 1258 return StringPiece(lhs) != StringPiece(rhs); 1259 } 1260 1261 /** 1262 * operator< through conversion for Range<const char*> 1263 */ 1264 template <class T, class U> 1265 std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator<( 1266 const T& lhs, const U& rhs) { 1267 return StringPiece(lhs) < StringPiece(rhs); 1268 } 1269 1270 /** 1271 * operator> through conversion for Range<const char*> 1272 */ 1273 template <class T, class U> 1274 std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator>( 1275 const T& lhs, const U& rhs) { 1276 return StringPiece(lhs) > StringPiece(rhs); 1277 } 1278 1279 /** 1280 * operator< through conversion for Range<const char*> 1281 */ 1282 template <class T, class U> 1283 std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator<=( 1284 const T& lhs, const U& rhs) { 1285 return StringPiece(lhs) <= StringPiece(rhs); 1286 } 1287 1288 /** 1289 * operator> through conversion for Range<const char*> 1290 */ 1291 template <class T, class U> 1292 std::enable_if_t<detail::ComparableAsStringPiece<T, U>::value, bool> operator>=( 1293 const T& lhs, const U& rhs) { 1294 return StringPiece(lhs) >= StringPiece(rhs); 1295 } 1296 1297 /** 1298 * Finds substrings faster than brute force by borrowing from Boyer-Moore 1299 */ 1300 template <class Iter, class Comp> 1301 size_t qfind(const Range<Iter>& haystack, const Range<Iter>& needle, Comp eq) { 1302 // Don't use std::search, use a Boyer-Moore-like trick by comparing 1303 // the last characters first 1304 auto const nsize = needle.size(); 1305 if (haystack.size() < nsize) { 1306 return std::string::npos; 1307 } 1308 if (!nsize) { 1309 return 0; 1310 } 1311 auto const nsize_1 = nsize - 1; 1312 auto const lastNeedle = needle[nsize_1]; 1313 1314 // Boyer-Moore skip value for the last char in the needle. Zero is 1315 // not a valid value; skip will be computed the first time it's 1316 // needed. 1317 std::string::size_type skip = 0; 1318 1319 auto i = haystack.begin(); 1320 auto iEnd = haystack.end() - nsize_1; 1321 1322 while (i < iEnd) { 1323 // Boyer-Moore: match the last element in the needle 1324 while (!eq(i[nsize_1], lastNeedle)) { 1325 if (++i == iEnd) { 1326 // not found 1327 return std::string::npos; 1328 } 1329 } 1330 // Here we know that the last char matches 1331 // Continue in pedestrian mode 1332 for (size_t j = 0;;) { 1333 assert(j < nsize); 1334 if (!eq(i[j], needle[j])) { 1335 // Not found, we can skip 1336 // Compute the skip value lazily 1337 if (skip == 0) { 1338 skip = 1; 1339 while (skip <= nsize_1 && !eq(needle[nsize_1 - skip], lastNeedle)) { 1340 ++skip; 1341 } 1342 } 1343 i += skip; 1344 break; 1345 } 1346 // Check if done searching 1347 if (++j == nsize) { 1348 // Yay 1349 return size_t(i - haystack.begin()); 1350 } 1351 } 1352 } 1353 return std::string::npos; 1354 } 1355 1356 namespace detail { 1357 1358 inline size_t qfind_first_byte_of( 1359 const StringPiece haystack, const StringPiece needles) { 1360 static auto const qfind_first_byte_of_fn = folly::CpuId().sse42() 1361 ? qfind_first_byte_of_sse42 1362 : qfind_first_byte_of_nosse; 1363 return qfind_first_byte_of_fn(haystack, needles); 1364 } 1365 1366 } // namespace detail 1367 1368 template <class Iter, class Comp> 1369 size_t qfind_first_of( 1370 const Range<Iter>& haystack, const Range<Iter>& needles, Comp eq) { 1371 auto ret = std::find_first_of( 1372 haystack.begin(), haystack.end(), needles.begin(), needles.end(), eq); 1373 return ret == haystack.end() ? std::string::npos : ret - haystack.begin(); 1374 } 1375 1376 struct AsciiCaseSensitive { 1377 bool operator()(char lhs, char rhs) const { return lhs == rhs; } 1378 }; 1379 1380 /** 1381 * Check if two ascii characters are case insensitive equal. 1382 * The difference between the lower/upper case characters are the 6-th bit. 1383 * We also check they are alpha chars, in case of xor = 32. 1384 */ 1385 struct AsciiCaseInsensitive { 1386 bool operator()(char lhs, char rhs) const { 1387 char k = lhs ^ rhs; 1388 if (k == 0) { 1389 return true; 1390 } 1391 if (k != 32) { 1392 return false; 1393 } 1394 k = lhs | rhs; 1395 return (k >= 'a' && k <= 'z'); 1396 } 1397 }; 1398 1399 template <class Iter> 1400 size_t qfind( 1401 const Range<Iter>& haystack, 1402 const typename Range<Iter>::value_type& needle) { 1403 auto pos = std::find(haystack.begin(), haystack.end(), needle); 1404 return pos == haystack.end() ? std::string::npos : pos - haystack.data(); 1405 } 1406 1407 template <class Iter> 1408 size_t rfind( 1409 const Range<Iter>& haystack, 1410 const typename Range<Iter>::value_type& needle) { 1411 for (auto i = haystack.size(); i-- > 0;) { 1412 if (haystack[i] == needle) { 1413 return i; 1414 } 1415 } 1416 return std::string::npos; 1417 } 1418 1419 // specialization for StringPiece 1420 template <> 1421 inline size_t qfind(const Range<const char*>& haystack, const char& needle) { 1422 // memchr expects a not-null pointer, early return if the range is empty. 1423 if (haystack.empty()) { 1424 return std::string::npos; 1425 } 1426 auto pos = static_cast<const char*>( 1427 ::memchr(haystack.data(), needle, haystack.size())); 1428 return pos == nullptr ? std::string::npos : pos - haystack.data(); 1429 } 1430 1431 template <> 1432 inline size_t rfind(const Range<const char*>& haystack, const char& needle) { 1433 // memchr expects a not-null pointer, early return if the range is empty. 1434 if (haystack.empty()) { 1435 return std::string::npos; 1436 } 1437 auto pos = static_cast<const char*>( 1438 memrchr(haystack.data(), needle, haystack.size())); 1439 return pos == nullptr ? std::string::npos : pos - haystack.data(); 1440 } 1441 1442 // specialization for ByteRange 1443 template <> 1444 inline size_t qfind( 1445 const Range<const unsigned char*>& haystack, const unsigned char& needle) { 1446 // memchr expects a not-null pointer, early return if the range is empty. 1447 if (haystack.empty()) { 1448 return std::string::npos; 1449 } 1450 auto pos = static_cast<const unsigned char*>( 1451 ::memchr(haystack.data(), needle, haystack.size())); 1452 return pos == nullptr ? std::string::npos : pos - haystack.data(); 1453 } 1454 1455 template <> 1456 inline size_t rfind( 1457 const Range<const unsigned char*>& haystack, const unsigned char& needle) { 1458 // memchr expects a not-null pointer, early return if the range is empty. 1459 if (haystack.empty()) { 1460 return std::string::npos; 1461 } 1462 auto pos = static_cast<const unsigned char*>( 1463 memrchr(haystack.data(), needle, haystack.size())); 1464 return pos == nullptr ? std::string::npos : pos - haystack.data(); 1465 } 1466 1467 template <class Iter> 1468 size_t qfind_first_of(const Range<Iter>& haystack, const Range<Iter>& needles) { 1469 return qfind_first_of(haystack, needles, AsciiCaseSensitive()); 1470 } 1471 1472 // specialization for StringPiece 1473 template <> 1474 inline size_t qfind_first_of( 1475 const Range<const char*>& haystack, const Range<const char*>& needles) { 1476 return detail::qfind_first_byte_of(haystack, needles); 1477 } 1478 1479 // specialization for ByteRange 1480 template <> 1481 inline size_t qfind_first_of( 1482 const Range<const unsigned char*>& haystack, 1483 const Range<const unsigned char*>& needles) { 1484 return detail::qfind_first_byte_of( 1485 StringPiece(haystack), StringPiece(needles)); 1486 } 1487 1488 template <class Key, class Enable> 1489 struct hasher; 1490 1491 template <class T> 1492 struct hasher< 1493 folly::Range<T*>, 1494 std::enable_if_t<std::is_integral<T>::value, void>> { 1495 using folly_is_avalanching = std::true_type; 1496 1497 size_t operator()(folly::Range<T*> r) const { 1498 // std::is_integral<T> is too restrictive, but is sufficient to 1499 // guarantee we can just hash all of the underlying bytes to get a 1500 // suitable hash of T. Something like absl::is_uniquely_represented<T> 1501 // would be better. std::is_pod is not enough, because POD types 1502 // can contain pointers and padding. Also, floating point numbers 1503 // may be == without being bit-identical. size_t is less than 64 1504 // bits on some platforms. 1505 return static_cast<size_t>( 1506 hash::SpookyHashV2::Hash64(r.begin(), r.size() * sizeof(T), 0)); 1507 } 1508 }; 1509 1510 /** 1511 * _sp is a user-defined literal suffix to make an appropriate Range 1512 * specialization from a literal string. 1513 * 1514 * Modeled after C++17's `sv` suffix. 1515 */ 1516 inline namespace literals { 1517 inline namespace string_piece_literals { 1518 constexpr Range<char const*> operator"" _sp( 1519 char const* str, size_t len) noexcept { 1520 return Range<char const*>(str, len); 1521 } 1522 1523 #if defined(__cpp_char8_t) && __cpp_char8_t >= 201811L 1524 constexpr Range<char8_t const*> operator"" _sp( 1525 char8_t const* str, size_t len) noexcept { 1526 return Range<char8_t const*>(str, len); 1527 } 1528 #endif 1529 1530 constexpr Range<char16_t const*> operator"" _sp( 1531 char16_t const* str, size_t len) noexcept { 1532 return Range<char16_t const*>(str, len); 1533 } 1534 1535 constexpr Range<char32_t const*> operator"" _sp( 1536 char32_t const* str, size_t len) noexcept { 1537 return Range<char32_t const*>(str, len); 1538 } 1539 1540 constexpr Range<wchar_t const*> operator"" _sp( 1541 wchar_t const* str, size_t len) noexcept { 1542 return Range<wchar_t const*>(str, len); 1543 } 1544 } // namespace string_piece_literals 1545 } // namespace literals 1546 1547 } // namespace folly 1548 1549 // Avoid ambiguity in older fmt versions due to StringPiece's conversions. 1550 #if FMT_VERSION >= 70000 1551 namespace fmt { 1552 template <> 1553 struct formatter<folly::StringPiece> : private formatter<string_view> { 1554 using formatter<string_view>::parse; 1555 1556 template <typename Context> 1557 auto format(folly::StringPiece s, Context& ctx) { 1558 return formatter<string_view>::format({s.data(), s.size()}, ctx); 1559 } 1560 }; 1561 } // namespace fmt 1562 #endif 1563 1564 FOLLY_POP_WARNING 1565 1566 FOLLY_ASSUME_FBVECTOR_COMPATIBLE_1(folly::Range) 1567 1568 // Unfortunately it is not possible to forward declare enable_view under 1569 // MSVC 2019.8 due to compiler bugs, so we need to include the actual 1570 // definition if available. 1571 #if __has_include(<range/v3/range/concepts.hpp>) && defined(_MSC_VER) && _MSC_VER >= 1920 1572 #include <range/v3/range/concepts.hpp> // @manual 1573 #else 1574 namespace ranges { 1575 template <class T> 1576 extern const bool enable_view; 1577 } // namespace ranges 1578 #endif 1579 1580 // Tell the range-v3 library that this type should satisfy 1581 // the view concept (a lightweight, non-owning range). 1582 namespace ranges { 1583 template <class Iter> 1584 FOLLY_INLINE_VARIABLE constexpr bool enable_view<::folly::Range<Iter>> = true; 1585 } // namespace ranges 1586