1 | /* |
2 | * Copyright 2015-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 | #pragma once |
18 | |
19 | #include <algorithm> |
20 | #include <string> |
21 | |
22 | #include <glog/logging.h> |
23 | |
24 | #include <folly/Likely.h> |
25 | |
26 | namespace folly { |
27 | |
28 | namespace detail { |
29 | |
30 | /*** |
31 | * The qfind_first_byte_of_* functions are declared here, before Range.h, so |
32 | * they cannot take StringPiece values. But they're there to operate on |
33 | * StringPiece values. Dependency cycles: fun. |
34 | * |
35 | * StringPieceLite is here to break that dependency cycle. |
36 | */ |
37 | class StringPieceLite { |
38 | public: |
39 | StringPieceLite(const char* b, const char* e) : b_(b), e_(e) {} |
40 | template <typename Range> |
41 | /* implicit */ StringPieceLite(const Range& r) |
42 | : StringPieceLite(r.data(), r.data() + r.size()) {} |
43 | const char* data() const { |
44 | return b_; |
45 | } |
46 | const char* begin() const { |
47 | return b_; |
48 | } |
49 | const char* end() const { |
50 | return e_; |
51 | } |
52 | size_t size() const { |
53 | return size_t(e_ - b_); |
54 | } |
55 | bool empty() const { |
56 | return size() == 0; |
57 | } |
58 | const char& operator[](size_t i) const { |
59 | DCHECK_GT(size(), i); |
60 | return b_[i]; |
61 | } |
62 | template <typename Range> |
63 | explicit operator Range() const { |
64 | return Range(begin(), end()); |
65 | } |
66 | |
67 | private: |
68 | const char* b_; |
69 | const char* e_; |
70 | }; |
71 | |
72 | inline size_t qfind_first_byte_of_std( |
73 | const StringPieceLite haystack, |
74 | const StringPieceLite needles) { |
75 | auto ret = std::find_first_of( |
76 | haystack.begin(), |
77 | haystack.end(), |
78 | needles.begin(), |
79 | needles.end(), |
80 | [](char a, char b) { return a == b; }); |
81 | return ret == haystack.end() ? std::string::npos : ret - haystack.begin(); |
82 | } |
83 | |
84 | size_t qfind_first_byte_of_bitset( |
85 | const StringPieceLite haystack, |
86 | const StringPieceLite needles); |
87 | |
88 | size_t qfind_first_byte_of_byteset( |
89 | const StringPieceLite haystack, |
90 | const StringPieceLite needles); |
91 | |
92 | inline size_t qfind_first_byte_of_nosse( |
93 | const StringPieceLite haystack, |
94 | const StringPieceLite needles) { |
95 | if (UNLIKELY(needles.empty() || haystack.empty())) { |
96 | return std::string::npos; |
97 | } |
98 | // The thresholds below were empirically determined by benchmarking. |
99 | // This is not an exact science since it depends on the CPU, the size of |
100 | // needles, and the size of haystack. |
101 | if ((needles.size() >= 4 && haystack.size() <= 10) || |
102 | (needles.size() >= 16 && haystack.size() <= 64) || needles.size() >= 32) { |
103 | return qfind_first_byte_of_byteset(haystack, needles); |
104 | } |
105 | return qfind_first_byte_of_std(haystack, needles); |
106 | } |
107 | } // namespace detail |
108 | } // namespace folly |
109 | |