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