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