1 // Copyright 2017 The Abseil Authors.
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/strings/string_view.h"
16
17 #ifndef ABSL_USES_STD_STRING_VIEW
18
19 #include <algorithm>
20 #include <climits>
21 #include <cstring>
22 #include <ostream>
23
24 #include "absl/strings/internal/memutil.h"
25
26 namespace absl {
27 ABSL_NAMESPACE_BEGIN
28
29 namespace {
WritePadding(std::ostream & o,size_t pad)30 void WritePadding(std::ostream& o, size_t pad) {
31 char fill_buf[32];
32 memset(fill_buf, o.fill(), sizeof(fill_buf));
33 while (pad) {
34 size_t n = std::min(pad, sizeof(fill_buf));
35 o.write(fill_buf, static_cast<std::streamsize>(n));
36 pad -= n;
37 }
38 }
39
40 class LookupTable {
41 public:
42 // For each character in wanted, sets the index corresponding
43 // to the ASCII code of that character. This is used by
44 // the find_.*_of methods below to tell whether or not a character is in
45 // the lookup table in constant time.
LookupTable(string_view wanted)46 explicit LookupTable(string_view wanted) {
47 for (char c : wanted) {
48 table_[Index(c)] = true;
49 }
50 }
operator [](char c) const51 bool operator[](char c) const { return table_[Index(c)]; }
52
53 private:
Index(char c)54 static unsigned char Index(char c) { return static_cast<unsigned char>(c); }
55 bool table_[UCHAR_MAX + 1] = {};
56 };
57
58 } // namespace
59
operator <<(std::ostream & o,string_view piece)60 std::ostream& operator<<(std::ostream& o, string_view piece) {
61 std::ostream::sentry sentry(o);
62 if (sentry) {
63 size_t lpad = 0;
64 size_t rpad = 0;
65 if (static_cast<size_t>(o.width()) > piece.size()) {
66 size_t pad = static_cast<size_t>(o.width()) - piece.size();
67 if ((o.flags() & o.adjustfield) == o.left) {
68 rpad = pad;
69 } else {
70 lpad = pad;
71 }
72 }
73 if (lpad) WritePadding(o, lpad);
74 o.write(piece.data(), static_cast<std::streamsize>(piece.size()));
75 if (rpad) WritePadding(o, rpad);
76 o.width(0);
77 }
78 return o;
79 }
80
find(string_view s,size_type pos) const81 string_view::size_type string_view::find(string_view s,
82 size_type pos) const noexcept {
83 if (empty() || pos > length_) {
84 if (empty() && pos == 0 && s.empty()) return 0;
85 return npos;
86 }
87 const char* result =
88 strings_internal::memmatch(ptr_ + pos, length_ - pos, s.ptr_, s.length_);
89 return result ? static_cast<size_type>(result - ptr_) : npos;
90 }
91
find(char c,size_type pos) const92 string_view::size_type string_view::find(char c, size_type pos) const noexcept {
93 if (empty() || pos >= length_) {
94 return npos;
95 }
96 const char* result =
97 static_cast<const char*>(memchr(ptr_ + pos, c, length_ - pos));
98 return result != nullptr ? static_cast<size_type>(result - ptr_) : npos;
99 }
100
rfind(string_view s,size_type pos) const101 string_view::size_type string_view::rfind(string_view s,
102 size_type pos) const noexcept {
103 if (length_ < s.length_) return npos;
104 if (s.empty()) return std::min(length_, pos);
105 const char* last = ptr_ + std::min(length_ - s.length_, pos) + s.length_;
106 const char* result = std::find_end(ptr_, last, s.ptr_, s.ptr_ + s.length_);
107 return result != last ? static_cast<size_type>(result - ptr_) : npos;
108 }
109
110 // Search range is [0..pos] inclusive. If pos == npos, search everything.
rfind(char c,size_type pos) const111 string_view::size_type string_view::rfind(char c,
112 size_type pos) const noexcept {
113 // Note: memrchr() is not available on Windows.
114 if (empty()) return npos;
115 for (size_type i = std::min(pos, length_ - 1);; --i) {
116 if (ptr_[i] == c) {
117 return i;
118 }
119 if (i == 0) break;
120 }
121 return npos;
122 }
123
find_first_of(string_view s,size_type pos) const124 string_view::size_type string_view::find_first_of(
125 string_view s, size_type pos) const noexcept {
126 if (empty() || s.empty()) {
127 return npos;
128 }
129 // Avoid the cost of LookupTable() for a single-character search.
130 if (s.length_ == 1) return find_first_of(s.ptr_[0], pos);
131 LookupTable tbl(s);
132 for (size_type i = pos; i < length_; ++i) {
133 if (tbl[ptr_[i]]) {
134 return i;
135 }
136 }
137 return npos;
138 }
139
find_first_not_of(string_view s,size_type pos) const140 string_view::size_type string_view::find_first_not_of(
141 string_view s, size_type pos) const noexcept {
142 if (empty()) return npos;
143 // Avoid the cost of LookupTable() for a single-character search.
144 if (s.length_ == 1) return find_first_not_of(s.ptr_[0], pos);
145 LookupTable tbl(s);
146 for (size_type i = pos; i < length_; ++i) {
147 if (!tbl[ptr_[i]]) {
148 return i;
149 }
150 }
151 return npos;
152 }
153
find_first_not_of(char c,size_type pos) const154 string_view::size_type string_view::find_first_not_of(
155 char c, size_type pos) const noexcept {
156 if (empty()) return npos;
157 for (; pos < length_; ++pos) {
158 if (ptr_[pos] != c) {
159 return pos;
160 }
161 }
162 return npos;
163 }
164
find_last_of(string_view s,size_type pos) const165 string_view::size_type string_view::find_last_of(string_view s,
166 size_type pos) const noexcept {
167 if (empty() || s.empty()) return npos;
168 // Avoid the cost of LookupTable() for a single-character search.
169 if (s.length_ == 1) return find_last_of(s.ptr_[0], pos);
170 LookupTable tbl(s);
171 for (size_type i = std::min(pos, length_ - 1);; --i) {
172 if (tbl[ptr_[i]]) {
173 return i;
174 }
175 if (i == 0) break;
176 }
177 return npos;
178 }
179
find_last_not_of(string_view s,size_type pos) const180 string_view::size_type string_view::find_last_not_of(
181 string_view s, size_type pos) const noexcept {
182 if (empty()) return npos;
183 size_type i = std::min(pos, length_ - 1);
184 if (s.empty()) return i;
185 // Avoid the cost of LookupTable() for a single-character search.
186 if (s.length_ == 1) return find_last_not_of(s.ptr_[0], pos);
187 LookupTable tbl(s);
188 for (;; --i) {
189 if (!tbl[ptr_[i]]) {
190 return i;
191 }
192 if (i == 0) break;
193 }
194 return npos;
195 }
196
find_last_not_of(char c,size_type pos) const197 string_view::size_type string_view::find_last_not_of(
198 char c, size_type pos) const noexcept {
199 if (empty()) return npos;
200 size_type i = std::min(pos, length_ - 1);
201 for (;; --i) {
202 if (ptr_[i] != c) {
203 return i;
204 }
205 if (i == 0) break;
206 }
207 return npos;
208 }
209
210
211 #ifdef ABSL_INTERNAL_NEED_REDUNDANT_CONSTEXPR_DECL
212 constexpr string_view::size_type string_view::npos;
213 constexpr string_view::size_type string_view::kMaxSize;
214 #endif
215
216 ABSL_NAMESPACE_END
217 } // namespace absl
218
219 #endif // ABSL_USES_STD_STRING_VIEW
220