base/string_piece.cc

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