string_piece.cc revision a1401311d1ab56c4ed0a474bd38c108f75cb0cd9 
1// Copyright (c) 2012 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4// Copied from strings/stringpiece.cc with modifications
5
6#include "base/strings/string_piece.h"
7
8#include <algorithm>
9#include <ostream>
10
11namespace base {
12namespace {
13
14// For each character in characters_wanted, sets the index corresponding
15// to the ASCII code of that character to 1 in table.  This is used by
16// the find_.*_of methods below to tell whether or not a character is in
17// the lookup table in constant time.
18// The argument `table' must be an array that is large enough to hold all
19// the possible values of an unsigned char.  Thus it should be be declared
20// as follows:
21//   bool table[UCHAR_MAX + 1]
22inline void BuildLookupTable(const StringPiece& characters_wanted,
23                             bool* table) {
24  const size_t length = characters_wanted.length();
25  const char* const data = characters_wanted.data();
26  for (size_t i = 0; i < length; ++i) {
27    table[static_cast<unsigned char>(data[i])] = true;
28  }
29}
30
31}  // namespace
32
33// MSVC doesn't like complex extern templates and DLLs.
34#if !defined(COMPILER_MSVC)
35template class BasicStringPiece<std::string>;
36template class BasicStringPiece<string16>;
37#endif
38
39bool operator==(const StringPiece& x, const StringPiece& y) {
40  if (x.size() != y.size())
41    return false;
42
43  return StringPiece::wordmemcmp(x.data(), y.data(), x.size()) == 0;
44}
45
46std::ostream& operator<<(std::ostream& o, const StringPiece& piece) {
47  o.write(piece.data(), static_cast<std::streamsize>(piece.size()));
48  return o;
49}
50
51namespace internal {
52
53template<typename STR>
54void CopyToStringT(const BasicStringPiece<STR>& self, STR* target) {
55  if (self.empty())
56    target->clear();
57  else
58    target->assign(self.data(), self.size());
59}
60
61void CopyToString(const StringPiece& self, std::string* target) {
62  CopyToStringT(self, target);
63}
64
65void CopyToString(const StringPiece16& self, string16* target) {
66  CopyToStringT(self, target);
67}
68
69template<typename STR>
70void AppendToStringT(const BasicStringPiece<STR>& self, STR* target) {
71  if (!self.empty())
72    target->append(self.data(), self.size());
73}
74
75void AppendToString(const StringPiece& self, std::string* target) {
76  AppendToStringT(self, target);
77}
78
79void AppendToString(const StringPiece16& self, string16* target) {
80  AppendToStringT(self, target);
81}
82
83template<typename STR>
84size_t copyT(const BasicStringPiece<STR>& self,
85             typename STR::value_type* buf,
86             size_t n,
87             size_t pos) {
88  size_t ret = std::min(self.size() - pos, n);
89  memcpy(buf, self.data() + pos, ret * sizeof(typename STR::value_type));
90  return ret;
91}
92
93size_t copy(const StringPiece& self, char* buf, size_t n, size_t pos) {
94  return copyT(self, buf, n, pos);
95}
96
97size_t copy(const StringPiece16& self, char16* buf, size_t n, size_t pos) {
98  return copyT(self, buf, n, pos);
99}
100
101template<typename STR>
102size_t findT(const BasicStringPiece<STR>& self,
103             const BasicStringPiece<STR>& s,
104             size_t pos) {
105  if (pos > self.size())
106    return BasicStringPiece<STR>::npos;
107
108  typename BasicStringPiece<STR>::const_iterator result =
109      std::search(self.begin() + pos, self.end(), s.begin(), s.end());
110  const size_t xpos =
111    static_cast<size_t>(result - self.begin());
112  return xpos + s.size() <= self.size() ? xpos : BasicStringPiece<STR>::npos;
113}
114
115size_t find(const StringPiece& self, const StringPiece& s, size_t pos) {
116  return findT(self, s, pos);
117}
118
119size_t find(const StringPiece16& self, const StringPiece16& s, size_t pos) {
120  return findT(self, s, pos);
121}
122
123template<typename STR>
124size_t findT(const BasicStringPiece<STR>& self,
125             typename STR::value_type c,
126             size_t pos) {
127  if (pos >= self.size())
128    return BasicStringPiece<STR>::npos;
129
130  typename BasicStringPiece<STR>::const_iterator result =
131      std::find(self.begin() + pos, self.end(), c);
132  return result != self.end() ?
133      static_cast<size_t>(result - self.begin()) : BasicStringPiece<STR>::npos;
134}
135
136size_t find(const StringPiece& self, char c, size_t pos) {
137  return findT(self, c, pos);
138}
139
140size_t find(const StringPiece16& self, char16 c, size_t pos) {
141  return findT(self, c, pos);
142}
143
144template<typename STR>
145size_t rfindT(const BasicStringPiece<STR>& self,
146              const BasicStringPiece<STR>& s,
147              size_t pos) {
148  if (self.size() < s.size())
149    return BasicStringPiece<STR>::npos;
150
151  if (s.empty())
152    return std::min(self.size(), pos);
153
154  typename BasicStringPiece<STR>::const_iterator last =
155      self.begin() + std::min(self.size() - s.size(), pos) + s.size();
156  typename BasicStringPiece<STR>::const_iterator result =
157      std::find_end(self.begin(), last, s.begin(), s.end());
158  return result != last ?
159      static_cast<size_t>(result - self.begin()) : BasicStringPiece<STR>::npos;
160}
161
162size_t rfind(const StringPiece& self, const StringPiece& s, size_t pos) {
163  return rfindT(self, s, pos);
164}
165
166size_t rfind(const StringPiece16& self, const StringPiece16& s, size_t pos) {
167  return rfindT(self, s, pos);
168}
169
170template<typename STR>
171size_t rfindT(const BasicStringPiece<STR>& self,
172              typename STR::value_type c,
173              size_t pos) {
174  if (self.size() == 0)
175    return BasicStringPiece<STR>::npos;
176
177  for (size_t i = std::min(pos, self.size() - 1); ;
178       --i) {
179    if (self.data()[i] == c)
180      return i;
181    if (i == 0)
182      break;
183  }
184  return BasicStringPiece<STR>::npos;
185}
186
187size_t rfind(const StringPiece& self, char c, size_t pos) {
188  return rfindT(self, c, pos);
189}
190
191size_t rfind(const StringPiece16& self, char16 c, size_t pos) {
192  return rfindT(self, c, pos);
193}
194
195// 8-bit version using lookup table.
196size_t find_first_of(const StringPiece& self,
197                     const StringPiece& s,
198                     size_t pos) {
199  if (self.size() == 0 || s.size() == 0)
200    return StringPiece::npos;
201
202  // Avoid the cost of BuildLookupTable() for a single-character search.
203  if (s.size() == 1)
204    return find(self, s.data()[0], pos);
205
206  bool lookup[UCHAR_MAX + 1] = { false };
207  BuildLookupTable(s, lookup);
208  for (size_t i = pos; i < self.size(); ++i) {
209    if (lookup[static_cast<unsigned char>(self.data()[i])]) {
210      return i;
211    }
212  }
213  return StringPiece::npos;
214}
215
216// 16-bit brute force version.
217size_t find_first_of(const StringPiece16& self,
218                     const StringPiece16& s,
219                     size_t pos) {
220  StringPiece16::const_iterator found =
221      std::find_first_of(self.begin() + pos, self.end(), s.begin(), s.end());
222  if (found == self.end())
223    return StringPiece16::npos;
224  return found - self.begin();
225}
226
227// 8-bit version using lookup table.
228size_t find_first_not_of(const StringPiece& self,
229                         const StringPiece& s,
230                         size_t pos) {
231  if (self.size() == 0)
232    return StringPiece::npos;
233
234  if (s.size() == 0)
235    return 0;
236
237  // Avoid the cost of BuildLookupTable() for a single-character search.
238  if (s.size() == 1)
239    return find_first_not_of(self, s.data()[0], pos);
240
241  bool lookup[UCHAR_MAX + 1] = { false };
242  BuildLookupTable(s, lookup);
243  for (size_t i = pos; i < self.size(); ++i) {
244    if (!lookup[static_cast<unsigned char>(self.data()[i])]) {
245      return i;
246    }
247  }
248  return StringPiece::npos;
249}
250
251// 16-bit brute-force version.
252BASE_EXPORT size_t find_first_not_of(const StringPiece16& self,
253                                     const StringPiece16& s,
254                                     size_t pos) {
255  if (self.size() == 0)
256    return StringPiece16::npos;
257
258  for (size_t self_i = pos; self_i < self.size(); ++self_i) {
259    bool found = false;
260    for (size_t s_i = 0; s_i < s.size(); ++s_i) {
261      if (self[self_i] == s[s_i]) {
262        found = true;
263        break;
264      }
265    }
266    if (!found)
267      return self_i;
268  }
269  return StringPiece16::npos;
270}
271
272template<typename STR>
273size_t find_first_not_ofT(const BasicStringPiece<STR>& self,
274                          typename STR::value_type c,
275                          size_t pos) {
276  if (self.size() == 0)
277    return BasicStringPiece<STR>::npos;
278
279  for (; pos < self.size(); ++pos) {
280    if (self.data()[pos] != c) {
281      return pos;
282    }
283  }
284  return BasicStringPiece<STR>::npos;
285}
286
287size_t find_first_not_of(const StringPiece& self,
288                         char c,
289                         size_t pos) {
290  return find_first_not_ofT(self, c, pos);
291}
292
293size_t find_first_not_of(const StringPiece16& self,
294                         char16 c,
295                         size_t pos) {
296  return find_first_not_ofT(self, c, pos);
297}
298
299// 8-bit version using lookup table.
300size_t find_last_of(const StringPiece& self, const StringPiece& s, size_t pos) {
301  if (self.size() == 0 || s.size() == 0)
302    return StringPiece::npos;
303
304  // Avoid the cost of BuildLookupTable() for a single-character search.
305  if (s.size() == 1)
306    return rfind(self, s.data()[0], pos);
307
308  bool lookup[UCHAR_MAX + 1] = { false };
309  BuildLookupTable(s, lookup);
310  for (size_t i = std::min(pos, self.size() - 1); ; --i) {
311    if (lookup[static_cast<unsigned char>(self.data()[i])])
312      return i;
313    if (i == 0)
314      break;
315  }
316  return StringPiece::npos;
317}
318
319// 16-bit brute-force version.
320size_t find_last_of(const StringPiece16& self,
321                    const StringPiece16& s,
322                    size_t pos) {
323  if (self.size() == 0)
324    return StringPiece16::npos;
325
326  for (size_t self_i = std::min(pos, self.size() - 1); ;
327       --self_i) {
328    for (size_t s_i = 0; s_i < s.size(); s_i++) {
329      if (self.data()[self_i] == s[s_i])
330        return self_i;
331    }
332    if (self_i == 0)
333      break;
334  }
335  return StringPiece16::npos;
336}
337
338// 8-bit version using lookup table.
339size_t find_last_not_of(const StringPiece& self,
340                        const StringPiece& s,
341                        size_t pos) {
342  if (self.size() == 0)
343    return StringPiece::npos;
344
345  size_t i = std::min(pos, self.size() - 1);
346  if (s.size() == 0)
347    return i;
348
349  // Avoid the cost of BuildLookupTable() for a single-character search.
350  if (s.size() == 1)
351    return find_last_not_of(self, s.data()[0], pos);
352
353  bool lookup[UCHAR_MAX + 1] = { false };
354  BuildLookupTable(s, lookup);
355  for (; ; --i) {
356    if (!lookup[static_cast<unsigned char>(self.data()[i])])
357      return i;
358    if (i == 0)
359      break;
360  }
361  return StringPiece::npos;
362}
363
364// 16-bit brute-force version.
365size_t find_last_not_of(const StringPiece16& self,
366                        const StringPiece16& s,
367                        size_t pos) {
368  if (self.size() == 0)
369    return StringPiece::npos;
370
371  for (size_t self_i = std::min(pos, self.size() - 1); ; --self_i) {
372    bool found = false;
373    for (size_t s_i = 0; s_i < s.size(); s_i++) {
374      if (self.data()[self_i] == s[s_i]) {
375        found = true;
376        break;
377      }
378    }
379    if (!found)
380      return self_i;
381    if (self_i == 0)
382      break;
383  }
384  return StringPiece16::npos;
385}
386
387template<typename STR>
388size_t find_last_not_ofT(const BasicStringPiece<STR>& self,
389                         typename STR::value_type c,
390                         size_t pos) {
391  if (self.size() == 0)
392    return BasicStringPiece<STR>::npos;
393
394  for (size_t i = std::min(pos, self.size() - 1); ; --i) {
395    if (self.data()[i] != c)
396      return i;
397    if (i == 0)
398      break;
399  }
400  return BasicStringPiece<STR>::npos;
401}
402
403size_t find_last_not_of(const StringPiece& self,
404                        char c,
405                        size_t pos) {
406  return find_last_not_ofT(self, c, pos);
407}
408
409size_t find_last_not_of(const StringPiece16& self,
410                        char16 c,
411                        size_t pos) {
412  return find_last_not_ofT(self, c, pos);
413}
414
415template<typename STR>
416BasicStringPiece<STR> substrT(const BasicStringPiece<STR>& self,
417                              size_t pos,
418                              size_t n) {
419  if (pos > self.size()) pos = self.size();
420  if (n > self.size() - pos) n = self.size() - pos;
421  return BasicStringPiece<STR>(self.data() + pos, n);
422}
423
424StringPiece substr(const StringPiece& self,
425                   size_t pos,
426                   size_t n) {
427  return substrT(self, pos, n);
428}
429
430StringPiece16 substr(const StringPiece16& self,
431                     size_t pos,
432                     size_t n) {
433  return substrT(self, pos, n);
434}
435
436}  // namespace internal
437}  // namespace base
438