string_piece.cc 8.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301
  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. #include "base/strings/string_piece.h"
  5. #include <algorithm>
  6. #include <climits>
  7. #include <limits>
  8. #include <ostream>
  9. #include <string>
  10. #include "base/strings/utf_string_conversions.h"
  11. #include "build/build_config.h"
  12. namespace base {
  13. namespace {
  14. // For each character in characters_wanted, sets the index corresponding
  15. // to the ASCII code of that character to 1 in table. This is used by
  16. // the find_.*_of methods below to tell whether or not a character is in
  17. // the lookup table in constant time.
  18. // The argument `table' must be an array that is large enough to hold all
  19. // the possible values of an unsigned char. Thus it should be be declared
  20. // as follows:
  21. // bool table[UCHAR_MAX + 1]
  22. inline void BuildLookupTable(StringPiece characters_wanted, bool* table) {
  23. const size_t length = characters_wanted.length();
  24. const char* const data = characters_wanted.data();
  25. for (size_t i = 0; i < length; ++i) {
  26. table[static_cast<unsigned char>(data[i])] = true;
  27. }
  28. }
  29. } // namespace
  30. // MSVC doesn't like complex extern templates and DLLs.
  31. #if !defined(COMPILER_MSVC)
  32. template class BasicStringPiece<char>;
  33. template class BasicStringPiece<char16_t>;
  34. template class BasicStringPiece<wchar_t>;
  35. #endif
  36. std::ostream& operator<<(std::ostream& o, StringPiece piece) {
  37. o.write(piece.data(), static_cast<std::streamsize>(piece.size()));
  38. return o;
  39. }
  40. std::ostream& operator<<(std::ostream& o, StringPiece16 piece) {
  41. return o << UTF16ToUTF8(piece);
  42. }
  43. std::ostream& operator<<(std::ostream& o, WStringPiece piece) {
  44. return o << WideToUTF8(piece);
  45. }
  46. namespace internal {
  47. template <typename T, typename CharT = typename T::value_type>
  48. size_t findT(T self, T s, size_t pos) {
  49. if (pos > self.size())
  50. return BasicStringPiece<CharT>::npos;
  51. typename BasicStringPiece<CharT>::const_iterator result =
  52. std::search(self.begin() + pos, self.end(), s.begin(), s.end());
  53. const size_t xpos =
  54. static_cast<size_t>(result - self.begin());
  55. return xpos + s.size() <= self.size() ? xpos : BasicStringPiece<CharT>::npos;
  56. }
  57. size_t find(StringPiece self, StringPiece s, size_t pos) {
  58. return findT(self, s, pos);
  59. }
  60. size_t find(StringPiece16 self, StringPiece16 s, size_t pos) {
  61. return findT(self, s, pos);
  62. }
  63. template <typename T, typename CharT = typename T::value_type>
  64. size_t rfindT(T self, T s, size_t pos) {
  65. if (self.size() < s.size())
  66. return BasicStringPiece<CharT>::npos;
  67. if (s.empty())
  68. return std::min(self.size(), pos);
  69. typename BasicStringPiece<CharT>::const_iterator last =
  70. self.begin() + std::min(self.size() - s.size(), pos) + s.size();
  71. typename BasicStringPiece<CharT>::const_iterator result =
  72. std::find_end(self.begin(), last, s.begin(), s.end());
  73. return result != last ? static_cast<size_t>(result - self.begin())
  74. : BasicStringPiece<CharT>::npos;
  75. }
  76. size_t rfind(StringPiece self, StringPiece s, size_t pos) {
  77. return rfindT(self, s, pos);
  78. }
  79. size_t rfind(StringPiece16 self, StringPiece16 s, size_t pos) {
  80. return rfindT(self, s, pos);
  81. }
  82. // 8-bit version using lookup table.
  83. size_t find_first_of(StringPiece self, StringPiece s, size_t pos) {
  84. if (self.size() == 0 || s.size() == 0)
  85. return StringPiece::npos;
  86. // Avoid the cost of BuildLookupTable() for a single-character search.
  87. if (s.size() == 1)
  88. return self.find(s.data()[0], pos);
  89. bool lookup[UCHAR_MAX + 1] = { false };
  90. BuildLookupTable(s, lookup);
  91. for (size_t i = pos; i < self.size(); ++i) {
  92. if (lookup[static_cast<unsigned char>(self.data()[i])]) {
  93. return i;
  94. }
  95. }
  96. return StringPiece::npos;
  97. }
  98. // Generic brute force version.
  99. template <typename T, typename CharT = typename T::value_type>
  100. size_t find_first_ofT(T self, T s, size_t pos) {
  101. // Use the faster std::find() if searching for a single character.
  102. typename BasicStringPiece<CharT>::const_iterator found =
  103. s.size() == 1 ? std::find(self.begin() + pos, self.end(), s[0])
  104. : std::find_first_of(self.begin() + pos, self.end(),
  105. s.begin(), s.end());
  106. if (found == self.end())
  107. return BasicStringPiece<CharT>::npos;
  108. return static_cast<size_t>(found - self.begin());
  109. }
  110. size_t find_first_of(StringPiece16 self, StringPiece16 s, size_t pos) {
  111. return find_first_ofT(self, s, pos);
  112. }
  113. // 8-bit version using lookup table.
  114. size_t find_first_not_of(StringPiece self, StringPiece s, size_t pos) {
  115. if (pos >= self.size())
  116. return StringPiece::npos;
  117. if (s.size() == 0)
  118. return pos;
  119. // Avoid the cost of BuildLookupTable() for a single-character search.
  120. if (s.size() == 1)
  121. return self.find_first_not_of(s.data()[0], pos);
  122. bool lookup[UCHAR_MAX + 1] = { false };
  123. BuildLookupTable(s, lookup);
  124. for (size_t i = pos; i < self.size(); ++i) {
  125. if (!lookup[static_cast<unsigned char>(self.data()[i])]) {
  126. return i;
  127. }
  128. }
  129. return StringPiece::npos;
  130. }
  131. // Generic brute-force version.
  132. template <typename T, typename CharT = typename T::value_type>
  133. size_t find_first_not_ofT(T self, T s, size_t pos) {
  134. if (self.size() == 0)
  135. return BasicStringPiece<CharT>::npos;
  136. for (size_t self_i = pos; self_i < self.size(); ++self_i) {
  137. bool found = false;
  138. for (auto c : s) {
  139. if (self[self_i] == c) {
  140. found = true;
  141. break;
  142. }
  143. }
  144. if (!found)
  145. return self_i;
  146. }
  147. return BasicStringPiece<CharT>::npos;
  148. }
  149. size_t find_first_not_of(StringPiece16 self, StringPiece16 s, size_t pos) {
  150. return find_first_not_ofT(self, s, pos);
  151. }
  152. // 8-bit version using lookup table.
  153. size_t find_last_of(StringPiece self, StringPiece s, size_t pos) {
  154. if (self.size() == 0 || s.size() == 0)
  155. return StringPiece::npos;
  156. // Avoid the cost of BuildLookupTable() for a single-character search.
  157. if (s.size() == 1)
  158. return self.rfind(s.data()[0], pos);
  159. bool lookup[UCHAR_MAX + 1] = { false };
  160. BuildLookupTable(s, lookup);
  161. for (size_t i = std::min(pos, self.size() - 1); ; --i) {
  162. if (lookup[static_cast<unsigned char>(self.data()[i])])
  163. return i;
  164. if (i == 0)
  165. break;
  166. }
  167. return StringPiece::npos;
  168. }
  169. // Generic brute-force version.
  170. template <typename T, typename CharT = typename T::value_type>
  171. size_t find_last_ofT(T self, T s, size_t pos) {
  172. if (self.size() == 0)
  173. return BasicStringPiece<CharT>::npos;
  174. for (size_t self_i = std::min(pos, self.size() - 1); ;
  175. --self_i) {
  176. for (auto c : s) {
  177. if (self.data()[self_i] == c)
  178. return self_i;
  179. }
  180. if (self_i == 0)
  181. break;
  182. }
  183. return BasicStringPiece<CharT>::npos;
  184. }
  185. size_t find_last_of(StringPiece16 self, StringPiece16 s, size_t pos) {
  186. return find_last_ofT(self, s, pos);
  187. }
  188. // 8-bit version using lookup table.
  189. size_t find_last_not_of(StringPiece self, StringPiece s, size_t pos) {
  190. if (self.size() == 0)
  191. return StringPiece::npos;
  192. size_t i = std::min(pos, self.size() - 1);
  193. if (s.size() == 0)
  194. return i;
  195. // Avoid the cost of BuildLookupTable() for a single-character search.
  196. if (s.size() == 1)
  197. return self.find_last_not_of(s.data()[0], pos);
  198. bool lookup[UCHAR_MAX + 1] = { false };
  199. BuildLookupTable(s, lookup);
  200. for (; ; --i) {
  201. if (!lookup[static_cast<unsigned char>(self.data()[i])])
  202. return i;
  203. if (i == 0)
  204. break;
  205. }
  206. return StringPiece::npos;
  207. }
  208. // Generic brute-force version.
  209. template <typename T, typename CharT = typename T::value_type>
  210. size_t find_last_not_ofT(T self, T s, size_t pos) {
  211. if (self.size() == 0)
  212. return StringPiece::npos;
  213. for (size_t self_i = std::min(pos, self.size() - 1); ; --self_i) {
  214. bool found = false;
  215. for (auto c : s) {
  216. if (self.data()[self_i] == c) {
  217. found = true;
  218. break;
  219. }
  220. }
  221. if (!found)
  222. return self_i;
  223. if (self_i == 0)
  224. break;
  225. }
  226. return BasicStringPiece<CharT>::npos;
  227. }
  228. size_t find_last_not_of(StringPiece16 self, StringPiece16 s, size_t pos) {
  229. return find_last_not_ofT(self, s, pos);
  230. }
  231. size_t find(WStringPiece self, WStringPiece s, size_t pos) {
  232. return findT(self, s, pos);
  233. }
  234. size_t rfind(WStringPiece self, WStringPiece s, size_t pos) {
  235. return rfindT(self, s, pos);
  236. }
  237. size_t find_first_of(WStringPiece self, WStringPiece s, size_t pos) {
  238. return find_first_ofT(self, s, pos);
  239. }
  240. size_t find_first_not_of(WStringPiece self, WStringPiece s, size_t pos) {
  241. return find_first_not_ofT(self, s, pos);
  242. }
  243. size_t find_last_of(WStringPiece self, WStringPiece s, size_t pos) {
  244. return find_last_ofT(self, s, pos);
  245. }
  246. size_t find_last_not_of(WStringPiece self, WStringPiece s, size_t pos) {
  247. return find_last_not_ofT(self, s, pos);
  248. }
  249. } // namespace internal
  250. } // namespace base