2 * Copyright (C) 1996-2016 The Squid Software Foundation and contributors
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.
10 #include "base/CharacterSet.h"
11 #include "base/RefCount.h"
13 #include "sbuf/DetailedStats.h"
14 #include "sbuf/Exceptions.h"
15 #include "sbuf/OutOfBoundsException.h"
16 #include "sbuf/SBuf.h"
27 #if defined HAVE_VA_COPY
28 #define VA_COPY va_copy
29 #elif defined HAVE___VA_COPY
30 #define VA_COPY __va_copy
33 InstanceIdDefinitions(SBuf
, "SBuf");
35 SBufStats
SBuf::stats
;
36 const SBuf::size_type
SBuf::npos
;
37 const SBuf::size_type
SBuf::maxSize
;
40 : store_(GetStorePrototype()), off_(0), len_(0)
42 debugs(24, 8, id
<< " created");
47 SBuf::SBuf(const SBuf
&S
)
48 : store_(S
.store_
), off_(S
.off_
), len_(S
.len_
)
50 debugs(24, 8, id
<< " created from id " << S
.id
);
56 SBuf::SBuf(const std::string
&s
)
57 : store_(GetStorePrototype()), off_(0), len_(0)
59 debugs(24, 8, id
<< " created from std::string");
60 lowAppend(s
.data(),s
.length());
65 SBuf::SBuf(const char *S
, size_type n
)
66 : store_(GetStorePrototype()), off_(0), len_(0)
70 ++stats
.allocFromCString
;
74 SBuf::SBuf(const char *S
)
75 : store_(GetStorePrototype()), off_(0), len_(0)
79 ++stats
.allocFromCString
;
85 debugs(24, 8, id
<< " destructed");
87 recordSBufSizeAtDestruct(len_
);
91 SBuf::GetStorePrototype()
93 static MemBlob::Pointer InitialStore
= new MemBlob(0);
98 SBuf::assign(const SBuf
&S
)
100 debugs(24, 7, "assigning " << id
<< " from " << S
.id
);
101 if (&S
== this) //assignment to self. Noop.
111 SBuf::assign(const char *S
, size_type n
)
113 const Locker
blobKeeper(this, S
);
114 debugs(24, 6, id
<< " from c-string, n=" << n
<< ")");
116 return append(S
, n
); //bounds checked in append()
120 SBuf::reserveCapacity(size_type minCapacity
)
122 Must(minCapacity
<= maxSize
);
127 SBuf::rawSpace(size_type minSpace
)
129 Must(length() <= maxSize
- minSpace
);
130 debugs(24, 7, "reserving " << minSpace
<< " for " << id
);
132 // we're not concerned about RefCounts here,
133 // the store knows the last-used portion. If
134 // it's available, we're effectively claiming ownership
135 // of it. If it's not, we need to go away (realloc)
136 if (store_
->canAppend(off_
+len_
, minSpace
)) {
137 debugs(24, 7, id
<< " not growing");
140 // TODO: we may try to memmove before realloc'ing in order to avoid
141 // one allocation operation, if we're the sole owners of a MemBlob.
142 // Maybe some heuristic on off_ and length()?
143 cow(minSpace
+length());
151 //enabling this code path, the store will be freed and reinitialized
152 store_
= GetStorePrototype(); //uncomment to actually free storage upon clear()
154 //enabling this code path, we try to release the store without deallocating it.
155 // will be lazily reallocated if needed.
156 if (store_
->LockCount() == 1)
165 SBuf::append(const SBuf
&S
)
167 const Locker
blobKeeper(this, S
.buf());
168 return lowAppend(S
.buf(), S
.length());
172 SBuf::append(const char * S
, size_type Ssize
)
174 const Locker
blobKeeper(this, S
);
177 if (Ssize
== SBuf::npos
)
179 debugs(24, 7, "from c-string to id " << id
);
180 // coverity[access_dbuff_in_call]
181 return lowAppend(S
, Ssize
);
185 SBuf::append(const char c
)
187 return lowAppend(&c
, 1);
191 SBuf::Printf(const char *fmt
, ...)
193 // with printf() the fmt or an arg might be a dangerous char*
194 // NP: cant rely on vappendf() Locker because of clear()
195 const Locker
blobKeeper(this, buf());
206 SBuf::appendf(const char *fmt
, ...)
216 SBuf::vappendf(const char *fmt
, va_list vargs
)
218 // with (v)appendf() the fmt or an arg might be a dangerous char*
219 const Locker
blobKeeper(this, buf());
223 //reserve twice the format-string size, it's a likely heuristic
224 size_type requiredSpaceEstimate
= strlen(fmt
)*2;
226 char *space
= rawSpace(requiredSpaceEstimate
);
230 sz
= vsnprintf(space
, spaceSize(), fmt
, ap
);
233 sz
= vsnprintf(space
, spaceSize(), fmt
, vargs
);
236 /* check for possible overflow */
237 /* snprintf on Linux returns -1 on output errors, or the size
238 * that would have been written if enough space had been available */
239 /* vsnprintf is standard in C99 */
241 if (sz
>= static_cast<int>(spaceSize())) {
242 // not enough space on the first go, we now know how much we need
243 requiredSpaceEstimate
= sz
*2; // TODO: tune heuristics
244 space
= rawSpace(requiredSpaceEstimate
);
245 sz
= vsnprintf(space
, spaceSize(), fmt
, vargs
);
246 if (sz
< 0) // output error in vsnprintf
247 throw TextException("output error in second-go vsnprintf",__FILE__
,
251 if (sz
< 0) // output error in either vsnprintf
252 throw TextException("output error in vsnprintf",__FILE__
, __LINE__
);
254 // data was appended, update internal state
257 /* C99 specifies that the final '\0' is not counted in vsnprintf's
258 * return value. Older compilers/libraries might instead count it */
259 /* check whether '\0' was appended and counted */
260 static bool snPrintfTerminatorChecked
= false;
261 static bool snPrintfTerminatorCounted
= false;
262 if (!snPrintfTerminatorChecked
) {
264 snPrintfTerminatorCounted
= snprintf(testbuf
, sizeof(testbuf
),
266 snPrintfTerminatorChecked
= true;
268 if (snPrintfTerminatorCounted
) {
280 SBuf::print(std::ostream
&os
) const
282 os
.write(buf(), length());
288 SBuf::dump(std::ostream
&os
) const
293 os
<< ", offset:" << off_
297 os
<< '\'' << std::endl
;
300 // alternate implementation, based on Raw() API.
301 os
<< Raw("SBuf", buf(), length()) <<
303 ", offset:" << off_
<<
313 SBuf::setAt(size_type pos
, char toset
)
315 checkAccessBounds(pos
);
317 store_
->mem
[off_
+pos
] = toset
;
322 memcasecmp(const char *b1
, const char *b2
, SBuf::size_type len
)
326 rv
= tolower(*b1
)-tolower(*b2
);
337 SBuf::compare(const SBuf
&S
, const SBufCaseSensitive isCaseSensitive
, const size_type n
) const
340 debugs(24, 8, "length specified. substr and recurse");
341 return substr(0,n
).compare(S
.substr(0,n
),isCaseSensitive
);
344 const size_type byteCompareLen
= min(S
.length(), length());
347 debugs(24, 8, "comparing length " << byteCompareLen
);
348 if (isCaseSensitive
== caseSensitive
) {
349 rv
= memcmp(buf(), S
.buf(), byteCompareLen
);
351 rv
= memcasecmp(buf(), S
.buf(), byteCompareLen
);
354 debugs(24, 8, "result: " << rv
);
357 if (n
<= length() || n
<= S
.length()) {
358 debugs(24, 8, "same contents and bounded length. Equal");
361 if (length() == S
.length()) {
362 debugs(24, 8, "same contents and same length. Equal");
365 if (length() > S
.length()) {
366 debugs(24, 8, "lhs is longer than rhs. Result is 1");
369 debugs(24, 8, "rhs is longer than lhs. Result is -1");
374 SBuf::compare(const char *s
, const SBufCaseSensitive isCaseSensitive
, const size_type n
) const
376 // 0-length comparison is always true regardless of buffer states
382 // N-length compare MUST provide a non-NULL C-string pointer
385 // when this is a 0-length string, no need for any complexity.
391 // brute-force scan in order to avoid ever needing strlen() on a c-string.
393 const char *left
= buf();
394 const char *right
= s
;
396 // what area to scan.
397 // n may be npos, but we treat that as a huge positive value
398 size_type byteCount
= min(length(), n
);
400 // loop until we find a difference, a '\0', or reach the end of area to scan
401 if (isCaseSensitive
== caseSensitive
) {
402 while ((rv
= *left
- *right
++) == 0) {
403 if (*left
++ == '\0' || --byteCount
== 0)
407 while ((rv
= tolower(*left
) - tolower(*right
++)) == 0) {
408 if (*left
++ == '\0' || --byteCount
== 0)
413 // If we stopped scanning because we reached the end
414 // of buf() before we reached the end of s,
415 // pretend we have a 0-terminator there to compare.
416 // NP: the loop already incremented "right" ready for this comparison
417 if (!byteCount
&& length() < n
)
418 return '\0' - *right
;
420 // If we found a difference within the scan area,
421 // or we found a '\0',
422 // or all n characters were identical (and none was \0).
427 SBuf::startsWith(const SBuf
&S
, const SBufCaseSensitive isCaseSensitive
) const
429 debugs(24, 8, id
<< " startsWith " << S
.id
<< ", caseSensitive: " <<
431 if (length() < S
.length()) {
432 debugs(24, 8, "no, too short");
436 return (compare(S
, isCaseSensitive
, S
.length()) == 0);
440 SBuf::operator ==(const SBuf
& S
) const
442 debugs(24, 8, id
<< " == " << S
.id
);
443 if (length() != S
.length()) {
444 debugs(24, 8, "no, different lengths");
446 return false; //shortcut: must be equal length
448 if (store_
== S
.store_
&& off_
== S
.off_
) {
449 debugs(24, 8, "yes, same length and backing store");
451 return true; //shortcut: same store, offset and length
454 const bool rv
= (0 == memcmp(buf(), S
.buf(), length()));
455 debugs(24, 8, "returning " << rv
);
460 SBuf::operator !=(const SBuf
& S
) const
462 return !(*this == S
);
466 SBuf::consume(size_type n
)
471 n
= min(n
, length());
472 debugs(24, 8, id
<< " consume " << n
);
473 SBuf
rv(substr(0, n
));
479 SBufStats
& SBuf::GetStats()
485 SBuf::copy(char *dest
, size_type n
) const
487 size_type toexport
= min(n
,length());
488 memcpy(dest
, buf(), toexport
);
494 SBuf::rawContent() const
501 SBuf::forceSize(size_type newSize
)
503 debugs(24, 8, id
<< " force " << (newSize
> length() ? "grow" : "shrink") << " to length=" << newSize
);
505 Must(store_
->LockCount() == 1);
506 if (newSize
> min(maxSize
,store_
->capacity
-off_
))
507 throw SBufTooBigException(__FILE__
,__LINE__
);
509 store_
->size
= newSize
;
516 /* null-terminate the current buffer, by hand-appending a \0 at its tail but
517 * without increasing its length. May COW, the side-effect is to guarantee that
518 * the MemBlob's tail is availabe for us to use */
522 ++stats
.nulTerminate
;
527 SBuf::chop(size_type pos
, size_type n
)
529 if (pos
== npos
|| pos
> length())
532 if (n
== npos
|| (pos
+n
) > length())
535 // if there will be nothing left, reset the buffer while we can
536 if (pos
== length() || n
== 0) {
548 SBuf::trim(const SBuf
&toRemove
, bool atBeginning
, bool atEnd
)
552 const char *p
= bufEnd()-1;
553 while (!isEmpty() && memchr(toRemove
.buf(), *p
, toRemove
.length()) != NULL
) {
554 //current end-of-buf is in the searched set
560 const char *p
= buf();
561 while (!isEmpty() && memchr(toRemove
.buf(), *p
, toRemove
.length()) != NULL
) {
573 SBuf::substr(size_type pos
, size_type n
) const
576 rv
.chop(pos
, n
); //stats handled by callee
581 SBuf::find(char c
, size_type startPos
) const
585 if (startPos
== npos
) // can't find anything if we look past end of SBuf
588 // std::string returns npos if needle is outside hay
589 if (startPos
> length())
592 const void *i
= memchr(buf()+startPos
, (int)c
, (size_type
)length()-startPos
);
597 return (static_cast<const char *>(i
)-buf());
601 SBuf::find(const SBuf
&needle
, size_type startPos
) const
603 if (startPos
== npos
) { // can't find anything if we look past end of SBuf
608 // std::string allows needle to overhang hay but not start outside
609 if (startPos
> length()) {
614 // for empty needle std::string returns startPos
615 if (needle
.length() == 0) {
620 // if needle length is 1 use the char search
621 if (needle
.length() == 1)
622 return find(needle
[0], startPos
);
626 char *start
= buf()+startPos
;
627 char *lastPossible
= buf()+length()-needle
.length()+1;
628 char needleBegin
= needle
[0];
630 debugs(24, 7, "looking for " << needle
<< "starting at " << startPos
<<
632 while (start
< lastPossible
) {
634 debugs(24, 8, " begin=" << (void *) start
<<
635 ", lastPossible=" << (void*) lastPossible
);
636 tmp
= static_cast<char *>(memchr(start
, needleBegin
, lastPossible
-start
));
638 debugs(24, 8 , "First byte not found");
641 // lastPossible guarrantees no out-of-bounds with memcmp()
642 if (0 == memcmp(needle
.buf(), tmp
, needle
.length())) {
643 debugs(24, 8, "Found at " << (tmp
-buf()));
648 debugs(24, 8, "not found");
653 SBuf::rfind(const SBuf
&needle
, SBuf::size_type endPos
) const
655 // when the needle is 1 char, use the 1-char rfind()
656 if (needle
.length() == 1)
657 return rfind(needle
[0], endPos
);
661 // needle is bigger than haystack, impossible find
662 if (length() < needle
.length())
665 // if startPos is npos, std::string scans from the end of hay
666 if (endPos
== npos
|| endPos
> length()-needle
.length())
667 endPos
= length()-needle
.length();
669 // an empty needle found at the end of the haystack
670 if (needle
.length() == 0)
673 char *bufBegin
= buf();
674 char *cur
= bufBegin
+endPos
;
675 const char needleBegin
= needle
[0];
676 while (cur
>= bufBegin
) {
677 if (*cur
== needleBegin
) {
678 if (0 == memcmp(needle
.buf(), cur
, needle
.length())) {
689 SBuf::rfind(char c
, SBuf::size_type endPos
) const
693 // shortcut: haystack is empty, can't find anything by definition
697 // on npos input std::string compares last octet of hay
698 if (endPos
== npos
|| endPos
>= length()) {
701 // NP: off-by-one weirdness:
702 // endPos is an offset ... 0-based
703 // length() is a count ... 1-based
704 // memrhr() requires a 1-based count of space to scan.
711 const void *i
= memrchr(buf(), (int)c
, (size_type
)endPos
);
716 return (static_cast<const char *>(i
)-buf());
720 SBuf::findFirstOf(const CharacterSet
&set
, size_type startPos
) const
724 if (startPos
== npos
)
727 if (startPos
>= length())
730 debugs(24, 7, "first of characterset " << set
.name
<< " in id " << id
);
731 char *cur
= buf()+startPos
;
732 const char *bufend
= bufEnd();
733 while (cur
< bufend
) {
738 debugs(24, 7, "not found");
743 SBuf::findFirstNotOf(const CharacterSet
&set
, size_type startPos
) const
747 if (startPos
== npos
)
750 if (startPos
>= length())
753 debugs(24, 7, "first not of characterset " << set
.name
<< " in id " << id
);
754 char *cur
= buf()+startPos
;
755 const char *bufend
= bufEnd();
756 while (cur
< bufend
) {
761 debugs(24, 7, "not found");
766 SBuf::findLastOf(const CharacterSet
&set
, size_type endPos
) const
773 if (endPos
== npos
|| endPos
>= length())
774 endPos
= length() - 1;
776 debugs(24, 7, "last of characterset " << set
.name
<< " in id " << id
);
777 const char *start
= buf();
778 for (const char *cur
= start
+ endPos
; cur
>= start
; --cur
) {
782 debugs(24, 7, "not found");
787 SBuf::findLastNotOf(const CharacterSet
&set
, size_type endPos
) const
794 if (endPos
== npos
|| endPos
>= length())
795 endPos
= length() - 1;
797 debugs(24, 7, "last not of characterset " << set
.name
<< " in id " << id
);
798 const char *start
= buf();
799 for (const char *cur
= start
+ endPos
; cur
>= start
; --cur
) {
803 debugs(24, 7, "not found");
808 * TODO: borrow a sscanf implementation from Linux or similar?
809 * we'd really need a vsnscanf(3)... ? As an alternative, a
810 * light-regexp-like domain-specific syntax might be an idea.
813 SBuf::scanf(const char *format
, ...)
815 // with the format or an arg might be a dangerous char*
816 // that gets invalidated by c_str()
817 const Locker
blobKeeper(this, buf());
822 va_start(arg
, format
);
823 rv
= vsscanf(c_str(), format
, arg
);
831 debugs(24, 8, "\"" << *this << "\"");
832 for (size_type j
= 0; j
< length(); ++j
) {
833 const int c
= (*this)[j
];
835 setAt(j
, tolower(c
));
837 debugs(24, 8, "result: \"" << *this << "\"");
844 debugs(24, 8, "\"" << *this << "\"");
845 for (size_type j
= 0; j
< length(); ++j
) {
846 const int c
= (*this)[j
];
848 setAt(j
, toupper(c
));
850 debugs(24, 8, "result: \"" << *this << "\"");
855 * checks whether the requested 'pos' is within the bounds of the SBuf
856 * \throw OutOfBoundsException if access is out of bounds
859 SBuf::checkAccessBounds(size_type pos
) const
862 throw OutOfBoundsException(*this, pos
, __FILE__
, __LINE__
);
865 /** re-allocate the backing store of the SBuf.
867 * If there are contents in the SBuf, they will be copied over.
868 * NO verifications are made on the size parameters, it's up to the caller to
869 * make sure that the new size is big enough to hold the copied contents.
870 * The re-allocated storage MAY be bigger than the requested size due to size-chunking
871 * algorithms in MemBlock, it is guarranteed NOT to be smaller.
874 SBuf::reAlloc(size_type newsize
)
876 debugs(24, 8, id
<< " new size: " << newsize
);
877 if (newsize
> maxSize
)
878 throw SBufTooBigException(__FILE__
, __LINE__
);
879 MemBlob::Pointer newbuf
= new MemBlob(newsize
);
881 newbuf
->append(buf(), length());
885 debugs(24, 7, id
<< " new store capacity: " << store_
->capacity
);
889 SBuf::lowAppend(const char * memArea
, size_type areaSize
)
891 rawSpace(areaSize
); //called method also checks n <= maxSize()
892 store_
->append(memArea
, areaSize
);
899 * copy-on-write: make sure that we are the only holder of the backing store.
900 * If not, reallocate. If a new size is specified, and it is greater than the
901 * current length, the backing store will be extended as needed
904 SBuf::cow(SBuf::size_type newsize
)
906 debugs(24, 8, id
<< " new size:" << newsize
);
907 if (newsize
== npos
|| newsize
< length())
910 if (store_
->LockCount() == 1 && newsize
== length()) {
911 debugs(24, 8, id
<< " no cow needed");