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