src/sbuf/SBuf.cc

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