src/sbuf/SBuf.cc

   1 /*
   2  * Copyright (C) 1996-2016 The Squid Software Foundation and contributors
   3  *
   4  * Squid software is distributed under GPLv2+ license and includes
   5  * contributions from numerous individuals and organizations.
   6  * Please see the COPYING and CONTRIBUTORS files for details.
   7  */
   8
   9 #include "squid.h"
  10 #include "base/CharacterSet.h"
  11 #include "base/RefCount.h"
  12 #include "Debug.h"
  13 #include "sbuf/DetailedStats.h"
  14 #include "sbuf/Exceptions.h"
  15 #include "sbuf/OutOfBoundsException.h"
  16 #include "sbuf/SBuf.h"
  17 #include "util.h"
  18
  19 #include <cstring>
  20 #include <functional>
  21 #include <iostream>
  22 #include <sstream>
  23
  24 #ifdef VA_COPY
  25 #undef VA_COPY
  26 #endif
  27 #if defined HAVE_VA_COPY
  28 #define VA_COPY va_copy
  29 #elif defined HAVE___VA_COPY
  30 #define VA_COPY __va_copy
  31 #endif
  32
  33 InstanceIdDefinitions(SBuf, "SBuf");
  34
  35 SBufStats SBuf::stats;
  36 const SBuf::size_type SBuf::npos;
  37 const SBuf::size_type SBuf::maxSize;
  38
  39 SBuf::SBuf()
  40     : store_(GetStorePrototype()), off_(0), len_(0)
  41 {
  42     debugs(24, 8, id << " created");
  43     ++stats.alloc;
  44     ++stats.live;
  45 }
  46
  47 SBuf::SBuf(const SBuf &S)
  48     : store_(S.store_), off_(S.off_), len_(S.len_)
  49 {
  50     debugs(24, 8, id << " created from id " << S.id);
  51     ++stats.alloc;
  52     ++stats.allocCopy;
  53     ++stats.live;
  54 }
  55
  56 SBuf::SBuf(const std::string &s)
  57     : store_(GetStorePrototype()), off_(0), len_(0)
  58 {
  59     debugs(24, 8, id << " created from std::string");
  60     lowAppend(s.data(),s.length());
  61     ++stats.alloc;
  62     ++stats.live;
  63 }
  64
  65 SBuf::SBuf(const char *S, size_type n)
  66     : store_(GetStorePrototype()), off_(0), len_(0)
  67 {
  68     append(S,n);
  69     ++stats.alloc;
  70     ++stats.allocFromCString;
  71     ++stats.live;
  72 }
  73
  74 SBuf::SBuf(const char *S)
  75     : store_(GetStorePrototype()), off_(0), len_(0)
  76 {
  77     append(S,npos);
  78     ++stats.alloc;
  79     ++stats.allocFromCString;
  80     ++stats.live;
  81 }
  82
  83 SBuf::~SBuf()
  84 {
  85     debugs(24, 8, id << " destructed");
  86     --stats.live;
  87     recordSBufSizeAtDestruct(len_);
  88 }
  89
  90 MemBlob::Pointer
  91 SBuf::GetStorePrototype()
  92 {
  93     static MemBlob::Pointer InitialStore = new MemBlob(0);
  94     return InitialStore;
  95 }
  96
  97 SBuf&
  98 SBuf::assign(const SBuf &S)
  99 {
 100     debugs(24, 7, "assigning " << id << " from " <<  S.id);
 101     if (&S == this) //assignment to self. Noop.
 102         return *this;
 103     ++stats.assignFast;
 104     store_ = S.store_;
 105     off_ = S.off_;
 106     len_ = S.len_;
 107     return *this;
 108 }
 109
 110 SBuf&
 111 SBuf::assign(const char *S, size_type n)
 112 {
 113     const Locker blobKeeper(this, S);
 114     debugs(24, 6, id << " from c-string, n=" << n << ")");
 115     clear();
 116     return append(S, n); //bounds checked in append()
 117 }
 118
 119 void
 120 SBuf::reserveCapacity(size_type minCapacity)
 121 {
 122     Must(minCapacity <= maxSize);
 123     cow(minCapacity);
 124 }
 125
 126 SBuf::size_type
 127 SBuf::reserve(const SBufReservationRequirements &req)
 128 {
 129     debugs(24, 8, id << " was: " << off_ << '+' << len_ << '+' << spaceSize() <<
 130            '=' << store_->capacity);
 131
 132     const bool mustRealloc = !req.allowShared && store_->LockCount() > 1;
 133
 134     if (!mustRealloc && spaceSize() >= req.minSpace)
 135         return spaceSize(); // the caller is content with what we have
 136
 137     /* only reallocation can make the caller happy */
 138
 139     if (!mustRealloc && len_ >= req.maxCapacity)
 140         return spaceSize(); // but we cannot reallocate
 141
 142     const size_type newSpace = std::min(req.idealSpace, maxSize - len_);
 143     reserveCapacity(std::min(len_ + newSpace, req.maxCapacity));
 144     debugs(24, 7, id << " now: " << off_ << '+' << len_ << '+' << spaceSize() <<
 145            '=' << store_->capacity);
 146     return spaceSize(); // reallocated and probably reserved enough space
 147 }
 148
 149 char *
 150 SBuf::rawSpace(size_type minSpace)
 151 {
 152     Must(length() <= maxSize - minSpace);
 153     debugs(24, 7, "reserving " << minSpace << " for " << id);
 154     ++stats.rawAccess;
 155     // we're not concerned about RefCounts here,
 156     // the store knows the last-used portion. If
 157     // it's available, we're effectively claiming ownership
 158     // of it. If it's not, we need to go away (realloc)
 159     if (store_->canAppend(off_+len_, minSpace)) {
 160         debugs(24, 7, id << " not growing");
 161         return bufEnd();
 162     }
 163     // TODO: we may try to memmove before realloc'ing in order to avoid
 164     //   one allocation operation, if we're the sole owners of a MemBlob.
 165     //   Maybe some heuristic on off_ and length()?
 166     cow(minSpace+length());
 167     return bufEnd();
 168 }
 169
 170 void
 171 SBuf::clear()
 172 {
 173 #if 0
 174     //enabling this code path, the store will be freed and reinitialized
 175     store_ = GetStorePrototype(); //uncomment to actually free storage upon clear()
 176 #else
 177     //enabling this code path, we try to release the store without deallocating it.
 178     // will be lazily reallocated if needed.
 179     if (store_->LockCount() == 1)
 180         store_->clear();
 181 #endif
 182     len_ = 0;
 183     off_ = 0;
 184     ++stats.clear;
 185 }
 186
 187 SBuf&
 188 SBuf::append(const SBuf &S)
 189 {
 190     const Locker blobKeeper(this, S.buf());
 191     return lowAppend(S.buf(), S.length());
 192 }
 193
 194 SBuf &
 195 SBuf::append(const char * S, size_type Ssize)
 196 {
 197     const Locker blobKeeper(this, S);
 198     if (S == NULL)
 199         return *this;
 200     if (Ssize == SBuf::npos)
 201         Ssize = strlen(S);
 202     debugs(24, 7, "from c-string to id " << id);
 203     // coverity[access_dbuff_in_call]
 204     return lowAppend(S, Ssize);
 205 }
 206
 207 SBuf &
 208 SBuf::append(const char c)
 209 {
 210     return lowAppend(&c, 1);
 211 }
 212
 213 SBuf&
 214 SBuf::Printf(const char *fmt, ...)
 215 {
 216     // with printf() the fmt or an arg might be a dangerous char*
 217     // NP: cant rely on vappendf() Locker because of clear()
 218     const Locker blobKeeper(this, buf());
 219
 220     va_list args;
 221     va_start(args, fmt);
 222     clear();
 223     vappendf(fmt, args);
 224     va_end(args);
 225     return *this;
 226 }
 227
 228 SBuf&
 229 SBuf::appendf(const char *fmt, ...)
 230 {
 231     va_list args;
 232     va_start(args, fmt);
 233     vappendf(fmt, args);
 234     va_end(args);
 235     return *this;
 236 }
 237
 238 SBuf&
 239 SBuf::vappendf(const char *fmt, va_list vargs)
 240 {
 241     // with (v)appendf() the fmt or an arg might be a dangerous char*
 242     const Locker blobKeeper(this, buf());
 243
 244     Must(fmt != NULL);
 245     int sz = 0;
 246     //reserve twice the format-string size, it's a likely heuristic
 247     size_type requiredSpaceEstimate = strlen(fmt)*2;
 248
 249     char *space = rawSpace(requiredSpaceEstimate);
 250 #ifdef VA_COPY
 251     va_list ap;
 252     VA_COPY(ap, vargs);
 253     sz = vsnprintf(space, spaceSize(), fmt, ap);
 254     va_end(ap);
 255 #else
 256     sz = vsnprintf(space, spaceSize(), fmt, vargs);
 257 #endif
 258
 259     /* check for possible overflow */
 260     /* snprintf on Linux returns -1 on output errors, or the size
 261      * that would have been written if enough space had been available */
 262     /* vsnprintf is standard in C99 */
 263
 264     if (sz >= static_cast<int>(spaceSize())) {
 265         // not enough space on the first go, we now know how much we need
 266         requiredSpaceEstimate = sz*2; // TODO: tune heuristics
 267         space = rawSpace(requiredSpaceEstimate);
 268         sz = vsnprintf(space, spaceSize(), fmt, vargs);
 269         if (sz < 0) // output error in vsnprintf
 270             throw TextException("output error in second-go vsnprintf",__FILE__,
 271                                 __LINE__);
 272     }
 273
 274     if (sz < 0) // output error in either vsnprintf
 275         throw TextException("output error in vsnprintf",__FILE__, __LINE__);
 276
 277     // data was appended, update internal state
 278     len_ += sz;
 279
 280     /* C99 specifies that the final '\0' is not counted in vsnprintf's
 281      * return value. Older compilers/libraries might instead count it */
 282     /* check whether '\0' was appended and counted */
 283     static bool snPrintfTerminatorChecked = false;
 284     static bool snPrintfTerminatorCounted = false;
 285     if (!snPrintfTerminatorChecked) {
 286         char testbuf[16];
 287         snPrintfTerminatorCounted = snprintf(testbuf, sizeof(testbuf),
 288                                              "%s", "1") == 2;
 289         snPrintfTerminatorChecked = true;
 290     }
 291     if (snPrintfTerminatorCounted) {
 292         --sz;
 293         --len_;
 294     }
 295
 296     store_->size += sz;
 297     ++stats.append;
 298
 299     return *this;
 300 }
 301
 302 std::ostream&
 303 SBuf::print(std::ostream &os) const
 304 {
 305     os.write(buf(), length());
 306     ++stats.toStream;
 307     return os;
 308 }
 309
 310 std::ostream&
 311 SBuf::dump(std::ostream &os) const
 312 {
 313     os << id
 314        << ": ";
 315     store_->dump(os);
 316     os << ", offset:" << off_
 317        << ", len:" << len_
 318        << ") : '";
 319     print(os);
 320     os << '\'' << std::endl;
 321     return os;
 322 # if 0
 323     // alternate implementation, based on Raw() API.
 324     os << Raw("SBuf", buf(), length()) <<
 325        ". id: " << id <<
 326        ", offset:" << off_ <<
 327        ", len:" << len_ <<
 328        ", store: ";
 329     store_->dump(os);
 330     os << std::endl;
 331     return os;
 332 #endif
 333 }
 334
 335 void
 336 SBuf::setAt(size_type pos, char toset)
 337 {
 338     checkAccessBounds(pos);
 339     cow();
 340     store_->mem[off_+pos] = toset;
 341     ++stats.setChar;
 342 }
 343
 344 static int
 345 memcasecmp(const char *b1, const char *b2, SBuf::size_type len)
 346 {
 347     int rv=0;
 348     while (len > 0) {
 349         rv = tolower(*b1)-tolower(*b2);
 350         if (rv != 0)
 351             return rv;
 352         ++b1;
 353         ++b2;
 354         --len;
 355     }
 356     return rv;
 357 }
 358
 359 int
 360 SBuf::compare(const SBuf &S, const SBufCaseSensitive isCaseSensitive, const size_type n) const
 361 {
 362     if (n != npos) {
 363         debugs(24, 8, "length specified. substr and recurse");
 364         return substr(0,n).compare(S.substr(0,n),isCaseSensitive);
 365     }
 366
 367     const size_type byteCompareLen = min(S.length(), length());
 368     ++stats.compareSlow;
 369     int rv = 0;
 370     debugs(24, 8, "comparing length " << byteCompareLen);
 371     if (isCaseSensitive == caseSensitive) {
 372         rv = memcmp(buf(), S.buf(), byteCompareLen);
 373     } else {
 374         rv = memcasecmp(buf(), S.buf(), byteCompareLen);
 375     }
 376     if (rv != 0) {
 377         debugs(24, 8, "result: " << rv);
 378         return rv;
 379     }
 380     if (n <= length() || n <= S.length()) {
 381         debugs(24, 8, "same contents and bounded length. Equal");
 382         return 0;
 383     }
 384     if (length() == S.length()) {
 385         debugs(24, 8, "same contents and same length. Equal");
 386         return 0;
 387     }
 388     if (length() > S.length()) {
 389         debugs(24, 8, "lhs is longer than rhs. Result is 1");
 390         return 1;
 391     }
 392     debugs(24, 8, "rhs is longer than lhs. Result is -1");
 393     return -1;
 394 }
 395
 396 int
 397 SBuf::compare(const char *s, const SBufCaseSensitive isCaseSensitive, const size_type n) const
 398 {
 399     // 0-length comparison is always true regardless of buffer states
 400     if (!n) {
 401         ++stats.compareFast;
 402         return 0;
 403     }
 404
 405     // N-length compare MUST provide a non-NULL C-string pointer
 406     assert(s);
 407
 408     // when this is a 0-length string, no need for any complexity.
 409     if (!length()) {
 410         ++stats.compareFast;
 411         return '\0' - *s;
 412     }
 413
 414     // brute-force scan in order to avoid ever needing strlen() on a c-string.
 415     ++stats.compareSlow;
 416     const char *left = buf();
 417     const char *right = s;
 418     int rv = 0;
 419     // what area to scan.
 420     // n may be npos, but we treat that as a huge positive value
 421     size_type byteCount = min(length(), n);
 422
 423     // loop until we find a difference, a '\0', or reach the end of area to scan
 424     if (isCaseSensitive == caseSensitive) {
 425         while ((rv = *left - *right++) == 0) {
 426             if (*left++ == '\0' || --byteCount == 0)
 427                 break;
 428         }
 429     } else {
 430         while ((rv = tolower(*left) - tolower(*right++)) == 0) {
 431             if (*left++ == '\0' || --byteCount == 0)
 432                 break;
 433         }
 434     }
 435
 436     // If we stopped scanning because we reached the end
 437     //  of buf() before we reached the end of s,
 438     // pretend we have a 0-terminator there to compare.
 439     // NP: the loop already incremented "right" ready for this comparison
 440     if (!byteCount && length() < n)
 441         return '\0' - *right;
 442
 443     // If we found a difference within the scan area,
 444     // or we found a '\0',
 445     // or all n characters were identical (and none was \0).
 446     return rv;
 447 }
 448
 449 bool
 450 SBuf::startsWith(const SBuf &S, const SBufCaseSensitive isCaseSensitive) const
 451 {
 452     debugs(24, 8, id << " startsWith " << S.id << ", caseSensitive: " <<
 453            isCaseSensitive);
 454     if (length() < S.length()) {
 455         debugs(24, 8, "no, too short");
 456         ++stats.compareFast;
 457         return false;
 458     }
 459     return (compare(S, isCaseSensitive, S.length()) == 0);
 460 }
 461
 462 bool
 463 SBuf::operator ==(const SBuf & S) const
 464 {
 465     debugs(24, 8, id << " == " << S.id);
 466     if (length() != S.length()) {
 467         debugs(24, 8, "no, different lengths");
 468         ++stats.compareFast;
 469         return false; //shortcut: must be equal length
 470     }
 471     if (store_ == S.store_ && off_ == S.off_) {
 472         debugs(24, 8, "yes, same length and backing store");
 473         ++stats.compareFast;
 474         return true;  //shortcut: same store, offset and length
 475     }
 476     ++stats.compareSlow;
 477     const bool rv = (0 == memcmp(buf(), S.buf(), length()));
 478     debugs(24, 8, "returning " << rv);
 479     return rv;
 480 }
 481
 482 bool
 483 SBuf::operator !=(const SBuf & S) const
 484 {
 485     return !(*this == S);
 486 }
 487
 488 SBuf
 489 SBuf::consume(size_type n)
 490 {
 491     if (n == npos)
 492         n = length();
 493     else
 494         n = min(n, length());
 495     debugs(24, 8, id << " consume " << n);
 496     SBuf rv(substr(0, n));
 497     chop(n);
 498     return rv;
 499 }
 500
 501 const
 502 SBufStats& SBuf::GetStats()
 503 {
 504     return stats;
 505 }
 506
 507 SBuf::size_type
 508 SBuf::copy(char *dest, size_type n) const
 509 {
 510     size_type toexport = min(n,length());
 511     memcpy(dest, buf(), toexport);
 512     ++stats.copyOut;
 513     return toexport;
 514 }
 515
 516 const char*
 517 SBuf::rawContent() const
 518 {
 519     ++stats.rawAccess;
 520     return buf();
 521 }
 522
 523 void
 524 SBuf::forceSize(size_type newSize)
 525 {
 526     debugs(24, 8, id << " force " << (newSize > length() ? "grow" : "shrink") << " to length=" << newSize);
 527
 528     Must(store_->LockCount() == 1);
 529     if (newSize > min(maxSize,store_->capacity-off_))
 530         throw SBufTooBigException(__FILE__,__LINE__);
 531     len_ = newSize;
 532     store_->size = newSize;
 533 }
 534
 535 const char*
 536 SBuf::c_str()
 537 {
 538     ++stats.rawAccess;
 539     /* null-terminate the current buffer, by hand-appending a \0 at its tail but
 540      * without increasing its length. May COW, the side-effect is to guarantee that
 541      * the MemBlob's tail is availabe for us to use */
 542     *rawSpace(1) = '\0';
 543     ++store_->size;
 544     ++stats.setChar;
 545     ++stats.nulTerminate;
 546     return buf();
 547 }
 548
 549 SBuf&
 550 SBuf::chop(size_type pos, size_type n)
 551 {
 552     if (pos == npos || pos > length())
 553         pos = length();
 554
 555     if (n == npos || (pos+n) > length())
 556         n = length() - pos;
 557
 558     // if there will be nothing left, reset the buffer while we can
 559     if (pos == length() || n == 0) {
 560         clear();
 561         return *this;
 562     }
 563
 564     ++stats.chop;
 565     off_ += pos;
 566     len_ = n;
 567     return *this;
 568 }
 569
 570 SBuf&
 571 SBuf::trim(const SBuf &toRemove, bool atBeginning, bool atEnd)
 572 {
 573     ++stats.trim;
 574     if (atEnd) {
 575         const char *p = bufEnd()-1;
 576         while (!isEmpty() && memchr(toRemove.buf(), *p, toRemove.length()) != NULL) {
 577             //current end-of-buf is in the searched set
 578             --len_;
 579             --p;
 580         }
 581     }
 582     if (atBeginning) {
 583         const char *p = buf();
 584         while (!isEmpty() && memchr(toRemove.buf(), *p, toRemove.length()) != NULL) {
 585             --len_;
 586             ++off_;
 587             ++p;
 588         }
 589     }
 590     if (isEmpty())
 591         clear();
 592     return *this;
 593 }
 594
 595 SBuf
 596 SBuf::substr(size_type pos, size_type n) const
 597 {
 598     SBuf rv(*this);
 599     rv.chop(pos, n); //stats handled by callee
 600     return rv;
 601 }
 602
 603 SBuf::size_type
 604 SBuf::find(char c, size_type startPos) const
 605 {
 606     ++stats.find;
 607
 608     if (startPos == npos) // can't find anything if we look past end of SBuf
 609         return npos;
 610
 611     // std::string returns npos if needle is outside hay
 612     if (startPos > length())
 613         return npos;
 614
 615     const void *i = memchr(buf()+startPos, (int)c, (size_type)length()-startPos);
 616
 617     if (i == NULL)
 618         return npos;
 619
 620     return (static_cast<const char *>(i)-buf());
 621 }
 622
 623 SBuf::size_type
 624 SBuf::find(const SBuf &needle, size_type startPos) const
 625 {
 626     if (startPos == npos) { // can't find anything if we look past end of SBuf
 627         ++stats.find;
 628         return npos;
 629     }
 630
 631     // std::string allows needle to overhang hay but not start outside
 632     if (startPos > length()) {
 633         ++stats.find;
 634         return npos;
 635     }
 636
 637     // for empty needle std::string returns startPos
 638     if (needle.length() == 0) {
 639         ++stats.find;
 640         return startPos;
 641     }
 642
 643     // if needle length is 1 use the char search
 644     if (needle.length() == 1)
 645         return find(needle[0], startPos);
 646
 647     ++stats.find;
 648
 649     char *start = buf()+startPos;
 650     char *lastPossible = buf()+length()-needle.length()+1;
 651     char needleBegin = needle[0];
 652
 653     debugs(24, 7, "looking for " << needle << "starting at " << startPos <<
 654            " in id " << id);
 655     while (start < lastPossible) {
 656         char *tmp;
 657         debugs(24, 8, " begin=" << (void *) start <<
 658                ", lastPossible=" << (void*) lastPossible );
 659         tmp = static_cast<char *>(memchr(start, needleBegin, lastPossible-start));
 660         if (tmp == NULL) {
 661             debugs(24, 8 , "First byte not found");
 662             return npos;
 663         }
 664         // lastPossible guarrantees no out-of-bounds with memcmp()
 665         if (0 == memcmp(needle.buf(), tmp, needle.length())) {
 666             debugs(24, 8, "Found at " << (tmp-buf()));
 667             return (tmp-buf());
 668         }
 669         start = tmp+1;
 670     }
 671     debugs(24, 8, "not found");
 672     return npos;
 673 }
 674
 675 SBuf::size_type
 676 SBuf::rfind(const SBuf &needle, SBuf::size_type endPos) const
 677 {
 678     // when the needle is 1 char, use the 1-char rfind()
 679     if (needle.length() == 1)
 680         return rfind(needle[0], endPos);
 681
 682     ++stats.find;
 683
 684     // needle is bigger than haystack, impossible find
 685     if (length() < needle.length())
 686         return npos;
 687
 688     // if startPos is npos, std::string scans from the end of hay
 689     if (endPos == npos || endPos > length()-needle.length())
 690         endPos = length()-needle.length();
 691
 692     // an empty needle found at the end of the haystack
 693     if (needle.length() == 0)
 694         return endPos;
 695
 696     char *bufBegin = buf();
 697     char *cur = bufBegin+endPos;
 698     const char needleBegin = needle[0];
 699     while (cur >= bufBegin) {
 700         if (*cur == needleBegin) {
 701             if (0 == memcmp(needle.buf(), cur, needle.length())) {
 702                 // found
 703                 return (cur-buf());
 704             }
 705         }
 706         --cur;
 707     }
 708     return npos;
 709 }
 710
 711 SBuf::size_type
 712 SBuf::rfind(char c, SBuf::size_type endPos) const
 713 {
 714     ++stats.find;
 715
 716     // shortcut: haystack is empty, can't find anything by definition
 717     if (length() == 0)
 718         return npos;
 719
 720     // on npos input std::string compares last octet of hay
 721     if (endPos == npos || endPos >= length()) {
 722         endPos = length();
 723     } else {
 724         // NP: off-by-one weirdness:
 725         // endPos is an offset ... 0-based
 726         // length() is a count ... 1-based
 727         // memrhr() requires a 1-based count of space to scan.
 728         ++endPos;
 729     }
 730
 731     if (length() == 0)
 732         return endPos;
 733
 734     const void *i = memrchr(buf(), (int)c, (size_type)endPos);
 735
 736     if (i == NULL)
 737         return npos;
 738
 739     return (static_cast<const char *>(i)-buf());
 740 }
 741
 742 SBuf::size_type
 743 SBuf::findFirstOf(const CharacterSet &set, size_type startPos) const
 744 {
 745     ++stats.find;
 746
 747     if (startPos == npos)
 748         return npos;
 749
 750     if (startPos >= length())
 751         return npos;
 752
 753     debugs(24, 7, "first of characterset " << set.name << " in id " << id);
 754     char *cur = buf()+startPos;
 755     const char *bufend = bufEnd();
 756     while (cur < bufend) {
 757         if (set[*cur])
 758             return cur-buf();
 759         ++cur;
 760     }
 761     debugs(24, 7, "not found");
 762     return npos;
 763 }
 764
 765 SBuf::size_type
 766 SBuf::findFirstNotOf(const CharacterSet &set, size_type startPos) const
 767 {
 768     ++stats.find;
 769
 770     if (startPos == npos)
 771         return npos;
 772
 773     if (startPos >= length())
 774         return npos;
 775
 776     debugs(24, 7, "first not of characterset " << set.name << " in id " << id);
 777     char *cur = buf()+startPos;
 778     const char *bufend = bufEnd();
 779     while (cur < bufend) {
 780         if (!set[*cur])
 781             return cur-buf();
 782         ++cur;
 783     }
 784     debugs(24, 7, "not found");
 785     return npos;
 786 }
 787
 788 SBuf::size_type
 789 SBuf::findLastOf(const CharacterSet &set, size_type endPos) const
 790 {
 791     ++stats.find;
 792
 793     if (isEmpty())
 794         return npos;
 795
 796     if (endPos == npos || endPos >= length())
 797         endPos = length() - 1;
 798
 799     debugs(24, 7, "last of characterset " << set.name << " in id " << id);
 800     const char *start = buf();
 801     for (const char *cur = start + endPos; cur >= start; --cur) {
 802         if (set[*cur])
 803             return cur - start;
 804     }
 805     debugs(24, 7, "not found");
 806     return npos;
 807 }
 808
 809 SBuf::size_type
 810 SBuf::findLastNotOf(const CharacterSet &set, size_type endPos) const
 811 {
 812     ++stats.find;
 813
 814     if (isEmpty())
 815         return npos;
 816
 817     if (endPos == npos || endPos >= length())
 818         endPos = length() - 1;
 819
 820     debugs(24, 7, "last not of characterset " << set.name << " in id " << id);
 821     const char *start = buf();
 822     for (const char *cur = start + endPos; cur >= start; --cur) {
 823         if (!set[*cur])
 824             return cur - start;
 825     }
 826     debugs(24, 7, "not found");
 827     return npos;
 828 }
 829
 830 void
 831 SBuf::toLower()
 832 {
 833     debugs(24, 8, "\"" << *this << "\"");
 834     for (size_type j = 0; j < length(); ++j) {
 835         const int c = (*this)[j];
 836         if (isupper(c))
 837             setAt(j, tolower(c));
 838     }
 839     debugs(24, 8, "result: \"" << *this << "\"");
 840     ++stats.caseChange;
 841 }
 842
 843 void
 844 SBuf::toUpper()
 845 {
 846     debugs(24, 8, "\"" << *this << "\"");
 847     for (size_type j = 0; j < length(); ++j) {
 848         const int c = (*this)[j];
 849         if (islower(c))
 850             setAt(j, toupper(c));
 851     }
 852     debugs(24, 8, "result: \"" << *this << "\"");
 853     ++stats.caseChange;
 854 }
 855
 856 /**
 857  * checks whether the requested 'pos' is within the bounds of the SBuf
 858  * \throw OutOfBoundsException if access is out of bounds
 859  */
 860 void
 861 SBuf::checkAccessBounds(size_type pos) const
 862 {
 863     if (pos >= length())
 864         throw OutOfBoundsException(*this, pos, __FILE__, __LINE__);
 865 }
 866
 867 /** re-allocate the backing store of the SBuf.
 868  *
 869  * If there are contents in the SBuf, they will be copied over.
 870  * NO verifications are made on the size parameters, it's up to the caller to
 871  * make sure that the new size is big enough to hold the copied contents.
 872  * The re-allocated storage MAY be bigger than the requested size due to size-chunking
 873  * algorithms in MemBlock, it is guarranteed NOT to be smaller.
 874  */
 875 void
 876 SBuf::reAlloc(size_type newsize)
 877 {
 878     debugs(24, 8, id << " new size: " << newsize);
 879     if (newsize > maxSize)
 880         throw SBufTooBigException(__FILE__, __LINE__);
 881     MemBlob::Pointer newbuf = new MemBlob(newsize);
 882     if (length() > 0)
 883         newbuf->append(buf(), length());
 884     store_ = newbuf;
 885     off_ = 0;
 886     ++stats.cowSlow;
 887     debugs(24, 7, id << " new store capacity: " << store_->capacity);
 888 }
 889
 890 SBuf&
 891 SBuf::lowAppend(const char * memArea, size_type areaSize)
 892 {
 893     rawSpace(areaSize); //called method also checks n <= maxSize()
 894     store_->append(memArea, areaSize);
 895     len_ += areaSize;
 896     ++stats.append;
 897     return *this;
 898 }
 899
 900 /**
 901  * copy-on-write: make sure that we are the only holder of the backing store.
 902  * If not, reallocate. If a new size is specified, and it is greater than the
 903  * current length, the backing store will be extended as needed
 904  */
 905 void
 906 SBuf::cow(SBuf::size_type newsize)
 907 {
 908     debugs(24, 8, id << " new size:" << newsize);
 909     if (newsize == npos || newsize < length())
 910         newsize = length();
 911
 912     if (store_->LockCount() == 1 && newsize == length()) {
 913         debugs(24, 8, id << " no cow needed");
 914         ++stats.cowFast;
 915         return;
 916     }
 917     reAlloc(newsize);
 918 }
 919