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