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