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