1 // Copyright 2010-2018, Google Inc.
2 // All rights reserved.
3 //
4 // Redistribution and use in source and binary forms, with or without
5 // modification, are permitted provided that the following conditions are
6 // met:
7 //
8 // * Redistributions of source code must retain the above copyright
9 // notice, this list of conditions and the following disclaimer.
10 // * Redistributions in binary form must reproduce the above
11 // copyright notice, this list of conditions and the following disclaimer
12 // in the documentation and/or other materials provided with the
13 // distribution.
14 // * Neither the name of Google Inc. nor the names of its
15 // contributors may be used to endorse or promote products derived from
16 // this software without specific prior written permission.
17 //
18 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30 #include "base/string_piece.h"
31
32 #include <algorithm>
33 #include <cassert>
34 #include <climits>
35 #include <iostream>
36 #include <string>
37
38 namespace mozc {
39
40 using size_type = StringPiece::size_type;
41
operator <<(std::ostream & o,const StringPiece & piece)42 std::ostream &operator<<(std::ostream &o, const StringPiece &piece) {
43 o.write(piece.data(), static_cast<std::streamsize>(piece.size()));
44 return o;
45 }
46
CopyToString(string * target) const47 void StringPiece::CopyToString(string *target) const {
48 target->assign(!empty() ? data() : "", size());
49 }
50
AppendToString(string * target) const51 void StringPiece::AppendToString(string *target) const {
52 if (!empty()) {
53 target->append(data(), size());
54 }
55 }
56
copy(char * buf,size_type n,size_type pos) const57 size_type StringPiece::copy(char *buf, size_type n, size_type pos) const {
58 const size_type ret = std::min(length_ - pos, n);
59 memcpy(buf, ptr_ + pos, ret);
60 return ret;
61 }
62
find(const StringPiece & s,size_type pos) const63 size_type StringPiece::find(const StringPiece &s, size_type pos) const {
64 if (pos > length_) {
65 return npos;
66 }
67 if (s.length_ == 1) {
68 return find(s.ptr_[0], pos);
69 }
70 const char *result = std::search(ptr_ + pos, ptr_ + length_,
71 s.ptr_, s.ptr_ + s.length_);
72 const size_type xpos = result - ptr_;
73 return xpos + s.length_ <= length_ ? xpos : npos;
74 }
75
find(char c,size_type pos) const76 size_type StringPiece::find(char c, size_type pos) const {
77 if (pos >= length_) {
78 return npos;
79 }
80
81 const char *result = std::find(ptr_ + pos, ptr_ + length_, c);
82 return result != ptr_ + length_ ? result - ptr_ : npos;
83 }
84
rfind(const StringPiece & s,size_type pos) const85 size_type StringPiece::rfind(const StringPiece &s, size_type pos) const {
86 if (length_ < s.length_) {
87 return npos;
88 }
89
90 if (s.empty()) {
91 return std::min(length_, pos);
92 }
93
94 const char *last = ptr_ + std::min(length_ - s.length_, pos) + s.length_;
95 const char *result = std::find_end(ptr_, last, s.ptr_, s.ptr_ + s.length_);
96 return result != last ? result - ptr_ : npos;
97 }
98
rfind(char c,size_type pos) const99 size_type StringPiece::rfind(char c, size_type pos) const {
100 if (length_ == 0) {
101 return npos;
102 }
103
104 for (size_type i = std::min(pos, length_ - 1); ; --i) {
105 if (ptr_[i] == c) {
106 return i;
107 }
108 if (i == 0) {
109 break;
110 }
111 }
112 return npos;
113 }
114
115 // For each character in characters_wanted, sets the index corresponding
116 // to the ASCII code of that character to 1 in table. This is used by
117 // the find_.*_of methods below to tell whether or not a character is in
118 // the lookup table in constant time.
119 // The argument `table' must be an array that is large enough to hold all
120 // the possible values of an unsigned char. Thus it should be be declared
121 // as follows:
122 // bool table[UCHAR_MAX + 1]
BuildLookupTable(const StringPiece & characters_wanted,bool * table)123 static inline void BuildLookupTable(const StringPiece &characters_wanted,
124 bool* table) {
125 const size_type length = characters_wanted.length();
126 const char * const data = characters_wanted.data();
127 for (size_type i = 0; i < length; ++i) {
128 table[static_cast<unsigned char>(data[i])] = true;
129 }
130 }
131
find_first_of(const StringPiece & s,size_type pos) const132 size_type StringPiece::find_first_of(const StringPiece &s,
133 size_type pos) const {
134 if (length_ == 0 || s.length_ == 0) {
135 return npos;
136 }
137
138 // Avoid the cost of BuildLookupTable() for a single-character search.
139 if (s.length_ == 1) {
140 return find_first_of(s.ptr_[0], pos);
141 }
142
143 bool lookup[UCHAR_MAX + 1] = { false };
144 BuildLookupTable(s, lookup);
145 for (size_type i = pos; i < length_; ++i) {
146 if (lookup[static_cast<unsigned char>(ptr_[i])]) {
147 return i;
148 }
149 }
150 return npos;
151 }
152
find_first_not_of(const StringPiece & s,size_type pos) const153 size_type StringPiece::find_first_not_of(const StringPiece &s,
154 size_type pos) const {
155 if (length_ == 0) {
156 return npos;
157 }
158
159 if (s.length_ == 0) {
160 return 0;
161 }
162
163 // Avoid the cost of BuildLookupTable() for a single-character search.
164 if (s.length_ == 1) {
165 return find_first_not_of(s.ptr_[0], pos);
166 }
167
168 bool lookup[UCHAR_MAX + 1] = { false };
169 BuildLookupTable(s, lookup);
170 for (size_type i = pos; i < length_; ++i) {
171 if (!lookup[static_cast<unsigned char>(ptr_[i])]) {
172 return i;
173 }
174 }
175 return npos;
176 }
177
find_first_not_of(char c,size_type pos) const178 size_type StringPiece::find_first_not_of(char c, size_type pos) const {
179 for (; pos < length_; ++pos) {
180 if (ptr_[pos] != c) {
181 return pos;
182 }
183 }
184 return npos;
185 }
186
find_last_of(const StringPiece & s,size_type pos) const187 size_type StringPiece::find_last_of(const StringPiece &s,
188 size_type pos) const {
189 if (length_ == 0 || s.length_ == 0) {
190 return npos;
191 }
192
193 // Avoid the cost of BuildLookupTable() for a single-character search.
194 if (s.length_ == 1) {
195 return find_last_of(s.ptr_[0], pos);
196 }
197
198 bool lookup[UCHAR_MAX + 1] = { false };
199 BuildLookupTable(s, lookup);
200 for (size_type i = std::min(pos, length_ - 1); ; --i) {
201 if (lookup[static_cast<unsigned char>(ptr_[i])]) {
202 return i;
203 }
204 if (i == 0) {
205 break;
206 }
207 }
208 return npos;
209 }
210
find_last_not_of(const StringPiece & s,size_type pos) const211 size_type StringPiece::find_last_not_of(const StringPiece &s,
212 size_type pos) const {
213 if (length_ == 0) {
214 return npos;
215 }
216
217 size_type i = std::min(pos, length_ - 1);
218 if (s.length_ == 0) {
219 return i;
220 }
221
222 // Avoid the cost of BuildLookupTable() for a single-character search.
223 if (s.length_ == 1) {
224 return find_last_not_of(s.ptr_[0], pos);
225 }
226
227 bool lookup[UCHAR_MAX + 1] = { false };
228 BuildLookupTable(s, lookup);
229 for (; ; --i) {
230 if (!lookup[static_cast<unsigned char>(ptr_[i])])
231 return i;
232 if (i == 0)
233 break;
234 }
235 return npos;
236 }
237
find_last_not_of(char c,size_type pos) const238 size_type StringPiece::find_last_not_of(char c, size_type pos) const {
239 if (length_ == 0) {
240 return npos;
241 }
242
243 for (size_type i = std::min(pos, length_ - 1); ; --i) {
244 if (ptr_[i] != c)
245 return i;
246 if (i == 0)
247 break;
248 }
249 return npos;
250 }
251
substr(size_type pos,size_type n) const252 StringPiece StringPiece::substr(size_type pos, size_type n) const {
253 if (pos > length_) {
254 pos = length_;
255 }
256 if (n > length_ - pos) {
257 n = length_ - pos;
258 }
259 return StringPiece(ptr_ + pos, n);
260 }
261
262 const StringPiece::size_type StringPiece::npos = size_type(-1);
263
264 } // namespace mozc
265
266