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_HAVE_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
26namespace absl {
27
28namespace {
29void WritePadding(std::ostream& o, size_t pad) {
30 char fill_buf[32];
31 memset(fill_buf, o.fill(), sizeof(fill_buf));
32 while (pad) {
33 size_t n = std::min(pad, sizeof(fill_buf));
34 o.write(fill_buf, n);
35 pad -= n;
36 }
37}
38
39class LookupTable {
40 public:
41 // For each character in wanted, sets the index corresponding
42 // to the ASCII code of that character. This is used by
43 // the find_.*_of methods below to tell whether or not a character is in
44 // the lookup table in constant time.
45 explicit LookupTable(string_view wanted) {
46 for (char c : wanted) {
47 table_[Index(c)] = true;
48 }
49 }
50 bool operator[](char c) const { return table_[Index(c)]; }
51
52 private:
53 static unsigned char Index(char c) { return static_cast<unsigned char>(c); }
54 bool table_[UCHAR_MAX + 1] = {};
55};
56
57} // namespace
58
59std::ostream& operator<<(std::ostream& o, string_view piece) {
60 std::ostream::sentry sentry(o);
61 if (sentry) {
62 size_t lpad = 0;
63 size_t rpad = 0;
64 if (static_cast<size_t>(o.width()) > piece.size()) {
65 size_t pad = o.width() - piece.size();
66 if ((o.flags() & o.adjustfield) == o.left) {
67 rpad = pad;
68 } else {
69 lpad = pad;
70 }
71 }
72 if (lpad) WritePadding(o, lpad);
73 o.write(piece.data(), piece.size());
74 if (rpad) WritePadding(o, rpad);
75 o.width(0);
76 }
77 return o;
78}
79
80string_view::size_type string_view::copy(char* buf, size_type n,
81 size_type pos) const {
82 size_type ulen = length_;
83 assert(pos <= ulen);
84 size_type rlen = std::min(ulen - pos, n);
85 if (rlen > 0) {
86 const char* start = ptr_ + pos;
87 std::copy(start, start + rlen, buf);
88 }
89 return rlen;
90}
91
92string_view::size_type string_view::find(string_view s, size_type pos) const
93 noexcept {
94 if (empty() || pos > length_) {
95 if (empty() && pos == 0 && s.empty()) return 0;
96 return npos;
97 }
98 const char* result =
99 strings_internal::memmatch(ptr_ + pos, length_ - pos, s.ptr_, s.length_);
100 return result ? result - ptr_ : npos;
101}
102
103string_view::size_type string_view::find(char c, size_type pos) const noexcept {
104 if (empty() || pos >= length_) {
105 return npos;
106 }
107 const char* result =
108 static_cast<const char*>(memchr(ptr_ + pos, c, length_ - pos));
109 return result != nullptr ? result - ptr_ : npos;
110}
111
112string_view::size_type string_view::rfind(string_view s, size_type pos) const
113 noexcept {
114 if (length_ < s.length_) return npos;
115 if (s.empty()) return std::min(length_, pos);
116 const char* last = ptr_ + std::min(length_ - s.length_, pos) + s.length_;
117 const char* result = std::find_end(ptr_, last, s.ptr_, s.ptr_ + s.length_);
118 return result != last ? result - ptr_ : npos;
119}
120
121// Search range is [0..pos] inclusive. If pos == npos, search everything.
122string_view::size_type string_view::rfind(char c, size_type pos) const
123 noexcept {
124 // Note: memrchr() is not available on Windows.
125 if (empty()) return npos;
126 for (size_type i = std::min(pos, length_ - 1);; --i) {
127 if (ptr_[i] == c) {
128 return i;
129 }
130 if (i == 0) break;
131 }
132 return npos;
133}
134
135string_view::size_type string_view::find_first_of(string_view s,
136 size_type pos) const
137 noexcept {
138 if (empty() || s.empty()) {
139 return npos;
140 }
141 // Avoid the cost of LookupTable() for a single-character search.
142 if (s.length_ == 1) return find_first_of(s.ptr_[0], pos);
143 LookupTable tbl(s);
144 for (size_type i = pos; i < length_; ++i) {
145 if (tbl[ptr_[i]]) {
146 return i;
147 }
148 }
149 return npos;
150}
151
152string_view::size_type string_view::find_first_not_of(string_view s,
153 size_type pos) const
154 noexcept {
155 if (empty()) return npos;
156 // Avoid the cost of LookupTable() for a single-character search.
157 if (s.length_ == 1) return find_first_not_of(s.ptr_[0], pos);
158 LookupTable tbl(s);
159 for (size_type i = pos; i < length_; ++i) {
160 if (!tbl[ptr_[i]]) {
161 return i;
162 }
163 }
164 return npos;
165}
166
167string_view::size_type string_view::find_first_not_of(char c,
168 size_type pos) const
169 noexcept {
170 if (empty()) return npos;
171 for (; pos < length_; ++pos) {
172 if (ptr_[pos] != c) {
173 return pos;
174 }
175 }
176 return npos;
177}
178
179string_view::size_type string_view::find_last_of(string_view s,
180 size_type pos) const noexcept {
181 if (empty() || s.empty()) return npos;
182 // Avoid the cost of LookupTable() for a single-character search.
183 if (s.length_ == 1) return find_last_of(s.ptr_[0], pos);
184 LookupTable tbl(s);
185 for (size_type i = std::min(pos, length_ - 1);; --i) {
186 if (tbl[ptr_[i]]) {
187 return i;
188 }
189 if (i == 0) break;
190 }
191 return npos;
192}
193
194string_view::size_type string_view::find_last_not_of(string_view s,
195 size_type pos) const
196 noexcept {
197 if (empty()) return npos;
198 size_type i = std::min(pos, length_ - 1);
199 if (s.empty()) return i;
200 // Avoid the cost of LookupTable() for a single-character search.
201 if (s.length_ == 1) return find_last_not_of(s.ptr_[0], pos);
202 LookupTable tbl(s);
203 for (;; --i) {
204 if (!tbl[ptr_[i]]) {
205 return i;
206 }
207 if (i == 0) break;
208 }
209 return npos;
210}
211
212string_view::size_type string_view::find_last_not_of(char c,
213 size_type pos) const
214 noexcept {
215 if (empty()) return npos;
216 size_type i = std::min(pos, length_ - 1);
217 for (;; --i) {
218 if (ptr_[i] != c) {
219 return i;
220 }
221 if (i == 0) break;
222 }
223 return npos;
224}
225
226// MSVC has non-standard behavior that implicitly creates definitions for static
227// const members. These implicit definitions conflict with explicit out-of-class
228// member definitions that are required by the C++ standard, resulting in
229// LNK1169 "multiply defined" errors at link time. __declspec(selectany) asks
230// MSVC to choose only one definition for the symbol it decorates. See details
231// at https://msdn.microsoft.com/en-us/library/34h23df8(v=vs.100).aspx
232#ifdef _MSC_VER
233#define ABSL_STRING_VIEW_SELECTANY __declspec(selectany)
234#else
235#define ABSL_STRING_VIEW_SELECTANY
236#endif
237
238ABSL_STRING_VIEW_SELECTANY
239constexpr string_view::size_type string_view::npos;
240ABSL_STRING_VIEW_SELECTANY
241constexpr string_view::size_type string_view::kMaxSize;
242
243} // namespace absl
244
245#endif // ABSL_HAVE_STD_STRING_VIEW
246