base/string_piece.cc

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