src/sbuf/SBuf.cc

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