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 38namespace google { 39namespace protobuf { 40std::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. 46void StringPiece::LogFatalSizeTooBig(size_t size, const char* details) { 47 GOOGLE_LOG(FATAL) << "size too big: " << size << " details: " << details; 48} 49 50StringPiece::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 56StringPiece::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 65void StringPiece::CopyToString(string* target) const { 66 target->assign(ptr_, length_); 67} 68 69void StringPiece::AppendToString(string* target) const { 70 target->append(ptr_, length_); 71} 72 73bool 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 82bool StringPiece::ConsumeFromEnd(StringPiece x) { 83 if (ends_with(x)) { 84 length_ -= x.length_; 85 return true; 86 } 87 return false; 88} 89 90stringpiece_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 98bool StringPiece::contains(StringPiece s) const { 99 return find(s, 0) != npos; 100} 101 102stringpiece_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 112stringpiece_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 121stringpiece_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. 132stringpiece_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] 153static 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 162stringpiece_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 180stringpiece_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 197stringpiece_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 209stringpiece_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 226stringpiece_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 246stringpiece_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 259StringPiece 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 265const StringPiece::size_type StringPiece::npos = size_type(-1); 266 267} // namespace protobuf 268} // namespace google 269