1// Copyright (c) 2011 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 <algorithm>
7#include <ostream>
8
9#include "base/string_piece.h"
10
11namespace base {
12
13typedef StringPiece::size_type size_type;
14
15bool operator==(const StringPiece& x, const StringPiece& y) {
16  if (x.size() != y.size())
17    return false;
18
19  return StringPiece::wordmemcmp(x.data(), y.data(), x.size()) == 0;
20}
21
22void StringPiece::CopyToString(std::string* target) const {
23  target->assign(!empty() ? data() : "", size());
24}
25
26void StringPiece::AppendToString(std::string* target) const {
27  if (!empty())
28    target->append(data(), size());
29}
30
31size_type StringPiece::copy(char* buf, size_type n, size_type pos) const {
32  size_type ret = std::min(length_ - pos, n);
33  memcpy(buf, ptr_ + pos, ret);
34  return ret;
35}
36
37size_type StringPiece::find(const StringPiece& s, size_type pos) const {
38  if (pos > length_)
39    return npos;
40
41  const char* result = std::search(ptr_ + pos, ptr_ + length_,
42                                   s.ptr_, s.ptr_ + s.length_);
43  const size_type xpos = result - ptr_;
44  return xpos + s.length_ <= length_ ? xpos : npos;
45}
46
47size_type StringPiece::find(char c, size_type pos) const {
48  if (pos >= length_)
49    return npos;
50
51  const char* result = std::find(ptr_ + pos, ptr_ + length_, c);
52  return result != ptr_ + length_ ? static_cast<size_t>(result - ptr_) : npos;
53}
54
55size_type StringPiece::rfind(const StringPiece& s, size_type pos) const {
56  if (length_ < s.length_)
57    return npos;
58
59  if (s.empty())
60    return std::min(length_, pos);
61
62  const char* last = ptr_ + std::min(length_ - s.length_, pos) + s.length_;
63  const char* result = std::find_end(ptr_, last, s.ptr_, s.ptr_ + s.length_);
64  return result != last ? static_cast<size_t>(result - ptr_) : npos;
65}
66
67size_type StringPiece::rfind(char c, size_type pos) const {
68  if (length_ == 0)
69    return npos;
70
71  for (size_type i = std::min(pos, length_ - 1); ; --i) {
72    if (ptr_[i] == c)
73      return i;
74    if (i == 0)
75      break;
76  }
77  return npos;
78}
79
80// For each character in characters_wanted, sets the index corresponding
81// to the ASCII code of that character to 1 in table.  This is used by
82// the find_.*_of methods below to tell whether or not a character is in
83// the lookup table in constant time.
84// The argument `table' must be an array that is large enough to hold all
85// the possible values of an unsigned char.  Thus it should be be declared
86// as follows:
87//   bool table[UCHAR_MAX + 1]
88static inline void BuildLookupTable(const StringPiece& characters_wanted,
89                                    bool* table) {
90  const size_type length = characters_wanted.length();
91  const char* const data = characters_wanted.data();
92  for (size_type i = 0; i < length; ++i) {
93    table[static_cast<unsigned char>(data[i])] = true;
94  }
95}
96
97size_type StringPiece::find_first_of(const StringPiece& s,
98                                     size_type pos) const {
99  if (length_ == 0 || s.length_ == 0)
100    return npos;
101
102  // Avoid the cost of BuildLookupTable() for a single-character search.
103  if (s.length_ == 1)
104    return find_first_of(s.ptr_[0], pos);
105
106  bool lookup[UCHAR_MAX + 1] = { false };
107  BuildLookupTable(s, lookup);
108  for (size_type i = pos; i < length_; ++i) {
109    if (lookup[static_cast<unsigned char>(ptr_[i])]) {
110      return i;
111    }
112  }
113  return npos;
114}
115
116size_type StringPiece::find_first_not_of(const StringPiece& s,
117                                         size_type pos) const {
118  if (length_ == 0)
119    return npos;
120
121  if (s.length_ == 0)
122    return 0;
123
124  // Avoid the cost of BuildLookupTable() for a single-character search.
125  if (s.length_ == 1)
126    return find_first_not_of(s.ptr_[0], pos);
127
128  bool lookup[UCHAR_MAX + 1] = { false };
129  BuildLookupTable(s, lookup);
130  for (size_type i = pos; i < length_; ++i) {
131    if (!lookup[static_cast<unsigned char>(ptr_[i])]) {
132      return i;
133    }
134  }
135  return npos;
136}
137
138size_type StringPiece::find_first_not_of(char c, size_type pos) const {
139  if (length_ == 0)
140    return npos;
141
142  for (; pos < length_; ++pos) {
143    if (ptr_[pos] != c) {
144      return pos;
145    }
146  }
147  return npos;
148}
149
150size_type StringPiece::find_last_of(const StringPiece& s, size_type pos) const {
151  if (length_ == 0 || s.length_ == 0)
152    return npos;
153
154  // Avoid the cost of BuildLookupTable() for a single-character search.
155  if (s.length_ == 1)
156    return find_last_of(s.ptr_[0], pos);
157
158  bool lookup[UCHAR_MAX + 1] = { false };
159  BuildLookupTable(s, lookup);
160  for (size_type i = std::min(pos, length_ - 1); ; --i) {
161    if (lookup[static_cast<unsigned char>(ptr_[i])])
162      return i;
163    if (i == 0)
164      break;
165  }
166  return npos;
167}
168
169size_type StringPiece::find_last_not_of(const StringPiece& s,
170                                        size_type pos) const {
171  if (length_ == 0)
172    return npos;
173
174  size_type i = std::min(pos, length_ - 1);
175  if (s.length_ == 0)
176    return i;
177
178  // Avoid the cost of BuildLookupTable() for a single-character search.
179  if (s.length_ == 1)
180    return find_last_not_of(s.ptr_[0], pos);
181
182  bool lookup[UCHAR_MAX + 1] = { false };
183  BuildLookupTable(s, lookup);
184  for (; ; --i) {
185    if (!lookup[static_cast<unsigned char>(ptr_[i])])
186      return i;
187    if (i == 0)
188      break;
189  }
190  return npos;
191}
192
193size_type StringPiece::find_last_not_of(char c, size_type pos) const {
194  if (length_ == 0)
195    return npos;
196
197  for (size_type i = std::min(pos, length_ - 1); ; --i) {
198    if (ptr_[i] != c)
199      return i;
200    if (i == 0)
201      break;
202  }
203  return npos;
204}
205
206StringPiece StringPiece::substr(size_type pos, size_type n) const {
207  if (pos > length_) pos = length_;
208  if (n > length_ - pos) n = length_ - pos;
209  return StringPiece(ptr_ + pos, n);
210}
211
212const StringPiece::size_type StringPiece::npos = size_type(-1);
213
214}  // namespace base
215