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