2 * Copyright 2012 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
24 fbstring's behavior can be configured via two macro definitions, as
25 follows. Normally, fbstring does not write a '\0' at the end of
26 each string whenever it changes the underlying characters. Instead,
27 it lazily writes the '\0' whenever either c_str() or data()
30 This is standard-compliant behavior and may save costs in some
31 circumstances. However, it may be surprising to some client code
32 because c_str() and data() are const member functions (fbstring
33 uses the "mutable" storage class for its own state).
35 In order to appease client code that expects fbstring to be
36 zero-terminated at all times, if the preprocessor symbol
37 FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
38 i.e. it goes the extra mile to guarantee a '\0' is always planted
39 at the end of its data.
41 On the contrary, if the desire is to debug faulty client code that
42 unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
43 emphatically NOT a zero) at the end of each string if
44 FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
45 writes the '\0', of course.)
47 The preprocessor symbols FBSTRING_PERVERSE and
48 FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
49 enforced during preprocessing.
52 //#define FBSTRING_PERVERSE
53 //#define FBSTRING_CONSERVATIVE
55 #ifdef FBSTRING_PERVERSE
56 #ifdef FBSTRING_CONSERVATIVE
57 #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
61 // This file appears in two locations: inside fbcode and in the
62 // libstdc++ source code (when embedding fbstring as std::string).
63 // To aid in this schizophrenic use, two macros are defined in
65 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
66 // gate use inside fbcode v. libstdc++
67 #include <bits/c++config.h>
69 #ifdef _LIBSTDCXX_FBSTRING
71 #pragma GCC system_header
73 // Handle the cases where the fbcode version (folly/Malloc.h) is included
74 // either before or after this inclusion.
75 #ifdef FOLLY_MALLOC_H_
76 #undef FOLLY_MALLOC_H_
77 #include "basic_fbstring_malloc.h"
79 #include "basic_fbstring_malloc.h"
80 #undef FOLLY_MALLOC_H_
83 #else // !_LIBSTDCXX_FBSTRING
89 #include "folly/Traits.h"
90 #include "folly/Likely.h"
91 #include "folly/Malloc.h"
92 #include "folly/Hash.h"
98 #include <type_traits>
100 #ifdef _LIBSTDCXX_FBSTRING
101 namespace std _GLIBCXX_VISIBILITY(default) {
102 _GLIBCXX_BEGIN_NAMESPACE_VERSION
107 namespace fbstring_detail {
109 template <class InIt, class OutIt>
112 typename std::iterator_traits<InIt>::difference_type n,
114 for (; n != 0; --n, ++b, ++d) {
115 assert((const void*)&*d != &*b);
121 template <class Pod, class T>
122 inline void pod_fill(Pod* b, Pod* e, T c) {
123 assert(b && e && b <= e);
124 /*static*/ if (sizeof(T) == 1) {
127 auto const ee = b + ((e - b) & ~7u);
128 for (; b != ee; b += 8) {
139 for (; b != e; ++b) {
146 * Lightly structured memcpy, simplifies copying PODs and introduces
147 * some asserts. Unfortunately using this function may cause
148 * measurable overhead (presumably because it adjusts from a begin/end
149 * convention to a pointer/size convention, so it does some extra
150 * arithmetic even though the caller might have done the inverse
151 * adaptation outside).
154 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
156 assert(d >= e || d + (e - b) <= b);
157 memcpy(d, b, (e - b) * sizeof(Pod));
161 * Lightly structured memmove, simplifies copying PODs and introduces
165 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
167 memmove(d, b, (e - b) * sizeof(*b));
170 } // namespace fbstring_detail
173 * Defines a special acquisition method for constructing fbstring
174 * objects. AcquireMallocatedString means that the user passes a
175 * pointer to a malloc-allocated string that the fbstring object will
178 enum class AcquireMallocatedString {};
181 * fbstring_core_model is a mock-up type that defines all required
182 * signatures of a fbstring core. The fbstring class itself uses such
183 * a core object to implement all of the numerous member functions
184 * required by the standard.
186 * If you want to define a new core, copy the definition below and
187 * implement the primitives. Then plug the core into basic_fbstring as
188 * a template argument.
190 template <class Char>
191 class fbstring_core_model {
193 fbstring_core_model();
194 fbstring_core_model(const fbstring_core_model &);
195 ~fbstring_core_model();
196 // Returns a pointer to string's buffer (currently only contiguous
197 // strings are supported). The pointer is guaranteed to be valid
198 // until the next call to a non-const member function.
199 const Char * data() const;
200 // Much like data(), except the string is prepared to support
201 // character-level changes. This call is a signal for
202 // e.g. reference-counted implementation to fork the data. The
203 // pointer is guaranteed to be valid until the next call to a
204 // non-const member function.
205 Char * mutable_data();
206 // Returns a pointer to string's buffer and guarantees that a
207 // readable '\0' lies right after the buffer. The pointer is
208 // guaranteed to be valid until the next call to a non-const member
210 const Char * c_str() const;
211 // Shrinks the string by delta characters. Asserts that delta <=
213 void shrink(size_t delta);
214 // Expands the string by delta characters (i.e. after this call
215 // size() will report the old size() plus delta) but without
216 // initializing the expanded region. Returns a pointer to the memory
217 // to be initialized (the beginning of the expanded portion). The
218 // caller is expected to fill the expanded area appropriately.
219 Char* expand_noinit(size_t delta);
220 // Expands the string by one character and sets the last character
222 void push_back(Char c);
223 // Returns the string's size.
225 // Returns the string's capacity, i.e. maximum size that the string
226 // can grow to without reallocation. Note that for reference counted
227 // strings that's technically a lie - even assigning characters
228 // within the existing size would cause a reallocation.
229 size_t capacity() const;
230 // Returns true if the data underlying the string is actually shared
231 // across multiple strings (in a refcounted fashion).
232 bool isShared() const;
233 // Makes sure that at least minCapacity characters are available for
234 // the string without reallocation. For reference-counted strings,
235 // it should fork the data even if minCapacity < size().
236 void reserve(size_t minCapacity);
239 fbstring_core_model& operator=(const fbstring_core_model &);
244 * gcc-4.7 throws what appears to be some false positive uninitialized
245 * warnings for the members of the MediumLarge struct. So, mute them here.
247 # pragma GCC diagnostic push
248 # pragma GCC diagnostic ignored "-Wuninitialized"
251 * This is the core of the string. The code should work on 32- and
252 * 64-bit architectures and with any Char size. Porting to big endian
253 * architectures would require some changes.
255 * The storage is selected as follows (assuming we store one-byte
256 * characters on a 64-bit machine): (a) "small" strings between 0 and
257 * 23 chars are stored in-situ without allocation (the rightmost byte
258 * stores the size); (b) "medium" strings from 24 through 254 chars
259 * are stored in malloc-allocated memory that is copied eagerly; (c)
260 * "large" strings of 255 chars and above are stored in a similar
261 * structure as medium arrays, except that the string is
262 * reference-counted and copied lazily. the reference count is
263 * allocated right before the character array.
265 * The discriminator between these three strategies sits in the two
266 * most significant bits of the rightmost char of the storage. If
267 * neither is set, then the string is small (and its length sits in
268 * the lower-order bits of that rightmost character). If the MSb is
269 * set, the string is medium width. If the second MSb is set, then the
272 template <class Char> class fbstring_core {
275 // Only initialize the tag, will set the MSBs (i.e. the small
276 // string size) to zero too
277 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
278 // or: setSmallSize(0);
280 assert(category() == isSmall && size() == 0);
283 fbstring_core(const fbstring_core & rhs) {
284 assert(&rhs != this);
285 // Simplest case first: small strings are bitblitted
286 if (rhs.category() == isSmall) {
287 assert(offsetof(MediumLarge, data_) == 0);
288 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
289 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
290 const size_t size = rhs.smallSize();
292 ml_.capacity_ = rhs.ml_.capacity_;
295 // Just write the whole thing, don't look at details. In
296 // particular we need to copy capacity anyway because we want
297 // to set the size (don't forget that the last character,
298 // which stores a short string's length, is shared with the
299 // ml_.capacity field).
302 assert(category() == isSmall && this->size() == rhs.size());
303 } else if (rhs.category() == isLarge) {
304 // Large strings are just refcounted
306 RefCounted::incrementRefs(ml_.data_);
307 assert(category() == isLarge && size() == rhs.size());
309 // Medium strings are copied eagerly. Don't forget to allocate
310 // one extra Char for the null terminator.
311 auto const allocSize =
312 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
313 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
314 fbstring_detail::pod_copy(rhs.ml_.data_,
316 rhs.ml_.data_ + rhs.ml_.size_ + 1,
318 // No need for writeTerminator() here, we copied one extra
319 // element just above.
320 ml_.size_ = rhs.ml_.size_;
321 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
322 assert(category() == isMedium);
324 assert(size() == rhs.size());
325 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
328 fbstring_core(fbstring_core&& goner) {
329 if (goner.category() == isSmall) {
330 // Just copy, leave the goner in peace
331 new(this) fbstring_core(goner.small_, goner.smallSize());
335 // Clean goner's carcass
336 goner.setSmallSize(0);
340 fbstring_core(const Char *const data, const size_t size) {
341 // Simplest case first: small strings are bitblitted
342 if (size <= maxSmallSize) {
343 // Layout is: Char* data_, size_t size_, size_t capacity_
344 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
345 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
346 // sizeof(size_t) must be a power of 2
347 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
349 // If data is aligned, use fast word-wise copying. Otherwise,
350 // use conservative memcpy.
351 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
352 fbstring_detail::pod_copy(data, data + size, small_);
354 // Copy one word (64 bits) at a time
355 const size_t byteSize = size * sizeof(Char);
356 if (byteSize > 2 * sizeof(size_t)) {
358 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
360 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
362 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
363 } else if (byteSize > sizeof(size_t)) {
366 } else if (size > 0) {
372 } else if (size <= maxMediumSize) {
373 // Medium strings are allocated normally. Don't forget to
374 // allocate one extra Char for the terminating null.
375 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
376 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
377 fbstring_detail::pod_copy(data, data + size, ml_.data_);
379 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
381 // Large strings are allocated differently
382 size_t effectiveCapacity = size;
383 auto const newRC = RefCounted::create(data, & effectiveCapacity);
384 ml_.data_ = newRC->data_;
386 ml_.capacity_ = effectiveCapacity | isLarge;
389 assert(this->size() == size);
390 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
394 auto const c = category();
402 RefCounted::decrementRefs(ml_.data_);
405 // Snatches a previously mallocated string. The parameter "size"
406 // is the size of the string, and the parameter "capacity" is the size
407 // of the mallocated block. The string must be \0-terminated, so
408 // data[size] == '\0' and capacity >= size + 1.
410 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
411 // "size", and pass 3 as "capacity".
412 fbstring_core(Char *const data, const size_t size,
413 const size_t capacity,
414 AcquireMallocatedString) {
416 assert(capacity > size);
417 assert(data[size] == '\0');
418 // Use the medium string storage
421 ml_.capacity_ = capacity | isMedium;
423 // No need for the memory
429 // swap below doesn't test whether &rhs == this (and instead
430 // potentially does extra work) on the premise that the rarity of
431 // that situation actually makes the check more expensive than is
433 void swap(fbstring_core & rhs) {
439 // In C++11 data() and c_str() are 100% equivalent.
440 const Char * data() const {
444 Char * mutable_data() {
445 auto const c = category();
449 assert(c == isMedium || c == isLarge);
450 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
452 size_t effectiveCapacity = ml_.capacity();
453 auto const newRC = RefCounted::create(& effectiveCapacity);
454 // If this fails, someone placed the wrong capacity in an
456 assert(effectiveCapacity >= ml_.capacity());
457 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
459 RefCounted::decrementRefs(ml_.data_);
460 ml_.data_ = newRC->data_;
461 // No need to call writeTerminator(), we have + 1 above.
466 const Char * c_str() const {
467 auto const c = category();
468 #ifdef FBSTRING_PERVERSE
470 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
471 || small_[smallSize()] == '\0');
472 small_[smallSize()] = '\0';
475 assert(c == isMedium || c == isLarge);
476 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
477 ml_.data_[ml_.size_] = '\0';
478 #elif defined(FBSTRING_CONSERVATIVE)
480 assert(small_[smallSize()] == '\0');
483 assert(c == isMedium || c == isLarge);
484 assert(ml_.data_[ml_.size_] == '\0');
487 small_[smallSize()] = '\0';
490 assert(c == isMedium || c == isLarge);
491 ml_.data_[ml_.size_] = '\0';
496 void shrink(const size_t delta) {
497 if (category() == isSmall) {
498 // Check for underflow
499 assert(delta <= smallSize());
500 setSmallSize(smallSize() - delta);
501 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
502 // Medium strings and unique large strings need no special
504 assert(ml_.size_ >= delta);
507 assert(ml_.size_ >= delta);
508 // Shared large string, must make unique. This is because of the
509 // durn terminator must be written, which may trample the shared
512 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
514 // No need to write the terminator.
520 void reserve(size_t minCapacity) {
521 if (category() == isLarge) {
523 if (RefCounted::refs(ml_.data_) > 1) {
524 // We must make it unique regardless; in-place reallocation is
525 // useless if the string is shared. In order to not surprise
526 // people, reserve the new block at current capacity or
527 // more. That way, a string's capacity never shrinks after a
529 minCapacity = std::max(minCapacity, ml_.capacity());
530 auto const newRC = RefCounted::create(& minCapacity);
531 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
533 // Done with the old data. No need to call writeTerminator(),
534 // we have + 1 above.
535 RefCounted::decrementRefs(ml_.data_);
536 ml_.data_ = newRC->data_;
537 ml_.capacity_ = minCapacity | isLarge;
538 // size remains unchanged
540 // String is not shared, so let's try to realloc (if needed)
541 if (minCapacity > ml_.capacity()) {
542 // Asking for more memory
544 RefCounted::reallocate(ml_.data_, ml_.size_,
545 ml_.capacity(), minCapacity);
546 ml_.data_ = newRC->data_;
547 ml_.capacity_ = minCapacity | isLarge;
550 assert(capacity() >= minCapacity);
552 } else if (category() == isMedium) {
553 // String is not shared
554 if (minCapacity <= ml_.capacity()) {
555 return; // nothing to do, there's enough room
557 if (minCapacity <= maxMediumSize) {
558 // Keep the string at medium size. Don't forget to allocate
559 // one extra Char for the terminating null.
560 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
561 ml_.data_ = static_cast<Char *>(
564 ml_.size_ * sizeof(Char),
565 ml_.capacity() * sizeof(Char),
568 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
570 // Conversion from medium to large string
571 fbstring_core nascent;
572 // Will recurse to another branch of this function
573 nascent.reserve(minCapacity);
574 nascent.ml_.size_ = ml_.size_;
575 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
579 assert(capacity() >= minCapacity);
582 assert(category() == isSmall);
583 if (minCapacity > maxMediumSize) {
585 auto const newRC = RefCounted::create(& minCapacity);
586 auto const size = smallSize();
587 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
588 // No need for writeTerminator(), we wrote it above with + 1.
589 ml_.data_ = newRC->data_;
591 ml_.capacity_ = minCapacity | isLarge;
592 assert(capacity() >= minCapacity);
593 } else if (minCapacity > maxSmallSize) {
595 // Don't forget to allocate one extra Char for the terminating null
596 auto const allocSizeBytes =
597 goodMallocSize((1 + minCapacity) * sizeof(Char));
598 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
599 auto const size = smallSize();
600 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
601 // No need for writeTerminator(), we wrote it above with + 1.
604 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
607 // Nothing to do, everything stays put
610 assert(capacity() >= minCapacity);
613 Char * expand_noinit(const size_t delta) {
614 // Strategy is simple: make room, then change size
615 assert(capacity() >= size());
617 if (category() == isSmall) {
620 if (newSz <= maxSmallSize) {
628 newSz = ml_.size_ + delta;
629 if (newSz > capacity()) {
633 assert(capacity() >= newSz);
634 // Category can't be small - we took care of that above
635 assert(category() == isMedium || category() == isLarge);
638 assert(size() == newSz);
639 return ml_.data_ + sz;
642 void push_back(Char c) {
643 assert(capacity() >= size());
645 if (category() == isSmall) {
647 if (sz < maxSmallSize) {
648 setSmallSize(sz + 1);
653 reserve(maxSmallSize * 2);
656 if (sz == capacity()) { // always true for isShared()
657 reserve(sz * 3 / 2); // ensures not shared
661 assert(capacity() >= sz + 1);
662 // Category can't be small - we took care of that above
663 assert(category() == isMedium || category() == isLarge);
669 size_t size() const {
670 return category() == isSmall ? smallSize() : ml_.size_;
673 size_t capacity() const {
674 switch (category()) {
678 // For large-sized strings, a multi-referenced chunk has no
679 // available capacity. This is because any attempt to append
680 // data would trigger a new allocation.
681 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
684 return ml_.capacity();
687 bool isShared() const {
688 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
691 #ifdef FBSTRING_PERVERSE
692 enum { TERMINATOR = '^' };
694 enum { TERMINATOR = '\0' };
697 void writeTerminator() {
698 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
699 if (category() == isSmall) {
700 const auto s = smallSize();
701 if (s != maxSmallSize) {
702 small_[s] = TERMINATOR;
705 ml_.data_[ml_.size_] = TERMINATOR;
712 fbstring_core & operator=(const fbstring_core & rhs);
719 size_t capacity() const {
720 return capacity_ & capacityExtractMask;
725 std::atomic<size_t> refCount_;
728 static RefCounted * fromData(Char * p) {
729 return static_cast<RefCounted*>(
731 static_cast<unsigned char*>(static_cast<void*>(p))
732 - sizeof(refCount_)));
735 static size_t refs(Char * p) {
736 return fromData(p)->refCount_.load(std::memory_order_acquire);
739 static void incrementRefs(Char * p) {
740 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
743 static void decrementRefs(Char * p) {
744 auto const dis = fromData(p);
745 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
752 static RefCounted * create(size_t * size) {
753 // Don't forget to allocate one extra Char for the terminating
754 // null. In this case, however, one Char is already part of the
756 const size_t allocSize = goodMallocSize(
757 sizeof(RefCounted) + *size * sizeof(Char));
758 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
759 result->refCount_.store(1, std::memory_order_release);
760 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
764 static RefCounted * create(const Char * data, size_t * size) {
765 const size_t effectiveSize = *size;
766 auto result = create(size);
767 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
771 static RefCounted * reallocate(Char *const data,
772 const size_t currentSize,
773 const size_t currentCapacity,
774 const size_t newCapacity) {
775 assert(newCapacity > 0 && newCapacity > currentSize);
776 auto const dis = fromData(data);
777 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
778 // Don't forget to allocate one extra Char for the terminating
779 // null. In this case, however, one Char is already part of the
781 auto result = static_cast<RefCounted*>(
783 sizeof(RefCounted) + currentSize * sizeof(Char),
784 sizeof(RefCounted) + currentCapacity * sizeof(Char),
785 sizeof(RefCounted) + newCapacity * sizeof(Char)));
786 assert(result->refCount_.load(std::memory_order_acquire) == 1);
792 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
793 mutable MediumLarge ml_;
797 lastChar = sizeof(MediumLarge) - 1,
798 maxSmallSize = lastChar / sizeof(Char),
799 maxMediumSize = 254 / sizeof(Char), // coincides with the small
800 // bin size in dlmalloc
801 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
802 capacityExtractMask = ~categoryExtractMask,
804 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
805 "Corrupt memory layout for fbstring.");
809 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
810 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
813 Category category() const {
814 // Assumes little endian
815 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
818 size_t smallSize() const {
819 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
820 return static_cast<size_t>(maxSmallSize)
821 - static_cast<size_t>(small_[maxSmallSize]);
824 void setSmallSize(size_t s) {
825 // Warning: this should work with uninitialized strings too,
826 // so don't assume anything about the previous value of
827 // small_[maxSmallSize].
828 assert(s <= maxSmallSize);
829 small_[maxSmallSize] = maxSmallSize - s;
833 # pragma GCC diagnostic pop
835 #ifndef _LIBSTDCXX_FBSTRING
837 * Dummy fbstring core that uses an actual std::string. This doesn't
838 * make any sense - it's just for testing purposes.
840 template <class Char>
841 class dummy_fbstring_core {
843 dummy_fbstring_core() {
845 dummy_fbstring_core(const dummy_fbstring_core& another)
846 : backend_(another.backend_) {
848 dummy_fbstring_core(const Char * s, size_t n)
851 void swap(dummy_fbstring_core & rhs) {
852 backend_.swap(rhs.backend_);
854 const Char * data() const {
855 return backend_.data();
857 Char * mutable_data() {
858 //assert(!backend_.empty());
859 return &*backend_.begin();
861 void shrink(size_t delta) {
862 assert(delta <= size());
863 backend_.resize(size() - delta);
865 Char * expand_noinit(size_t delta) {
866 auto const sz = size();
867 backend_.resize(size() + delta);
868 return backend_.data() + sz;
870 void push_back(Char c) {
871 backend_.push_back(c);
873 size_t size() const {
874 return backend_.size();
876 size_t capacity() const {
877 return backend_.capacity();
879 bool isShared() const {
882 void reserve(size_t minCapacity) {
883 backend_.reserve(minCapacity);
887 std::basic_string<Char> backend_;
889 #endif // !_LIBSTDCXX_FBSTRING
892 * This is the basic_string replacement. For conformity,
893 * basic_fbstring takes the same template parameters, plus the last
894 * one which is the core.
896 #ifdef _LIBSTDCXX_FBSTRING
897 template <typename E, class T, class A, class Storage>
899 template <typename E,
900 class T = std::char_traits<E>,
901 class A = std::allocator<E>,
902 class Storage = fbstring_core<E> >
904 class basic_fbstring {
908 void (*throw_exc)(const char*),
910 if (!condition) throw_exc(msg);
913 bool isSane() const {
916 empty() == (size() == 0) &&
917 empty() == (begin() == end()) &&
918 size() <= max_size() &&
919 capacity() <= max_size() &&
920 size() <= capacity() &&
921 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
925 friend struct Invariant;
928 explicit Invariant(const basic_fbstring& s) : s_(s) {
935 const basic_fbstring& s_;
937 explicit Invariant(const basic_fbstring&) {}
939 Invariant& operator=(const Invariant&);
944 typedef T traits_type;
945 typedef typename traits_type::char_type value_type;
946 typedef A allocator_type;
947 typedef typename A::size_type size_type;
948 typedef typename A::difference_type difference_type;
950 typedef typename A::reference reference;
951 typedef typename A::const_reference const_reference;
952 typedef typename A::pointer pointer;
953 typedef typename A::const_pointer const_pointer;
956 typedef const E* const_iterator;
957 typedef std::reverse_iterator<iterator
958 #ifdef NO_ITERATOR_TRAITS
962 typedef std::reverse_iterator<const_iterator
963 #ifdef NO_ITERATOR_TRAITS
966 > const_reverse_iterator;
968 static const size_type npos; // = size_type(-1)
971 static void procrustes(size_type& n, size_type nmax) {
972 if (n > nmax) n = nmax;
976 // 21.3.1 construct/copy/destroy
977 explicit basic_fbstring(const A& a = A()) {
980 basic_fbstring(const basic_fbstring& str)
981 : store_(str.store_) {
985 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
988 #ifndef _LIBSTDCXX_FBSTRING
989 // This is defined for compatibility with std::string
990 /* implicit */ basic_fbstring(const std::string& str)
991 : store_(str.data(), str.size()) {
995 basic_fbstring(const basic_fbstring& str, size_type pos,
996 size_type n = npos, const A& a = A()) {
1000 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1001 : store_(s, s ? traits_type::length(s) : ({
1002 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1003 err += ": null pointer initializer not valid";
1004 std::__throw_logic_error(err.c_str());
1009 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1013 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1014 auto const data = store_.expand_noinit(n);
1015 fbstring_detail::pod_fill(data, data + n, c);
1016 store_.writeTerminator();
1019 template <class InIt>
1020 basic_fbstring(InIt begin, InIt end,
1021 typename std::enable_if<
1022 !std::is_same<typename std::remove_const<InIt>::type,
1023 value_type*>::value, const A>::type & a = A()) {
1027 // Specialization for const char*, const char*
1028 basic_fbstring(const value_type* b, const value_type* e)
1029 : store_(b, e - b) {
1032 // Nonstandard constructor
1033 basic_fbstring(value_type *s, size_type n, size_type c,
1034 AcquireMallocatedString a)
1035 : store_(s, n, c, a) {
1041 basic_fbstring& operator=(const basic_fbstring & lhs) {
1045 auto const oldSize = size();
1046 auto const srcSize = lhs.size();
1047 if (capacity() >= srcSize && !store_.isShared()) {
1048 // great, just copy the contents
1049 if (oldSize < srcSize)
1050 store_.expand_noinit(srcSize - oldSize);
1052 store_.shrink(oldSize - srcSize);
1053 assert(size() == srcSize);
1054 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1055 store_.writeTerminator();
1057 // need to reallocate, so we may as well create a brand new string
1058 basic_fbstring(lhs).swap(*this);
1064 basic_fbstring& operator=(basic_fbstring&& goner) {
1065 // No need of this anymore
1066 this->~basic_fbstring();
1067 // Move the goner into this
1068 new(&store_) fbstring_core<E>(std::move(goner.store_));
1072 #ifndef _LIBSTDCXX_FBSTRING
1073 // Compatibility with std::string
1074 basic_fbstring & operator=(const std::string & rhs) {
1075 return assign(rhs.data(), rhs.size());
1078 // Compatibility with std::string
1079 std::string toStdString() const {
1080 return std::string(data(), size());
1083 // A lot of code in fbcode still uses this method, so keep it here for now.
1084 const basic_fbstring& toStdString() const {
1089 basic_fbstring& operator=(const value_type* s) {
1093 basic_fbstring& operator=(value_type c) {
1095 store_.expand_noinit(1);
1096 } else if (store_.isShared()) {
1097 basic_fbstring(1, c).swap(*this);
1100 store_.shrink(size() - 1);
1102 *store_.mutable_data() = c;
1103 store_.writeTerminator();
1107 // 21.3.2 iterators:
1108 iterator begin() { return store_.mutable_data(); }
1110 const_iterator begin() const { return store_.data(); }
1113 return store_.mutable_data() + store_.size();
1116 const_iterator end() const {
1117 return store_.data() + store_.size();
1120 reverse_iterator rbegin() {
1121 return reverse_iterator(end());
1124 const_reverse_iterator rbegin() const {
1125 return const_reverse_iterator(end());
1128 reverse_iterator rend() {
1129 return reverse_iterator(begin());
1132 const_reverse_iterator rend() const {
1133 return const_reverse_iterator(begin());
1137 // C++11 21.4.5, element access:
1138 const value_type& front() const { return *begin(); }
1139 const value_type& back() const {
1141 // Should be begin()[size() - 1], but that branches twice
1142 return *(end() - 1);
1144 value_type& front() { return *begin(); }
1145 value_type& back() {
1147 // Should be begin()[size() - 1], but that branches twice
1148 return *(end() - 1);
1156 size_type size() const { return store_.size(); }
1158 size_type length() const { return size(); }
1160 size_type max_size() const {
1161 return std::numeric_limits<size_type>::max();
1164 void resize(const size_type n, const value_type c = value_type()) {
1165 auto size = this->size();
1167 store_.shrink(size - n);
1169 // Do this in two steps to minimize slack memory copied (see
1171 auto const capacity = this->capacity();
1172 assert(capacity >= size);
1173 if (size < capacity) {
1174 auto delta = std::min(n, capacity) - size;
1175 store_.expand_noinit(delta);
1176 fbstring_detail::pod_fill(begin() + size, end(), c);
1179 store_.writeTerminator();
1184 auto const delta = n - size;
1185 store_.expand_noinit(delta);
1186 fbstring_detail::pod_fill(end() - delta, end(), c);
1187 store_.writeTerminator();
1189 assert(this->size() == n);
1192 size_type capacity() const { return store_.capacity(); }
1194 void reserve(size_type res_arg = 0) {
1195 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1196 store_.reserve(res_arg);
1199 void clear() { resize(0); }
1201 bool empty() const { return size() == 0; }
1203 // 21.3.4 element access:
1204 const_reference operator[](size_type pos) const {
1205 return *(c_str() + pos);
1208 reference operator[](size_type pos) {
1209 if (pos == size()) {
1210 // Just call c_str() to make sure '\0' is present
1213 return *(begin() + pos);
1216 const_reference at(size_type n) const {
1217 enforce(n <= size(), std::__throw_out_of_range, "");
1221 reference at(size_type n) {
1222 enforce(n < size(), std::__throw_out_of_range, "");
1226 // 21.3.5 modifiers:
1227 basic_fbstring& operator+=(const basic_fbstring& str) {
1231 basic_fbstring& operator+=(const value_type* s) {
1235 basic_fbstring& operator+=(const value_type c) {
1240 basic_fbstring& append(const basic_fbstring& str) {
1242 auto desiredSize = size() + str.size();
1244 append(str.data(), str.size());
1245 assert(size() == desiredSize);
1249 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1251 const size_type sz = str.size();
1252 enforce(pos <= sz, std::__throw_out_of_range, "");
1253 procrustes(n, sz - pos);
1254 return append(str.data() + pos, n);
1257 basic_fbstring& append(const value_type* s, size_type n) {
1259 Invariant checker(*this);
1263 // Unlikely but must be done
1266 auto const oldSize = size();
1267 auto const oldData = data();
1268 // Check for aliasing (rare). We could use "<=" here but in theory
1269 // those do not work for pointers unless the pointers point to
1270 // elements in the same array. For that reason we use
1271 // std::less_equal, which is guaranteed to offer a total order
1272 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1274 std::less_equal<const value_type*> le;
1275 if (UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1276 assert(le(s + n, oldData + oldSize));
1277 const size_type offset = s - oldData;
1278 store_.reserve(oldSize + n);
1279 // Restore the source
1280 s = data() + offset;
1282 // Warning! Repeated appends with short strings may actually incur
1283 // practically quadratic performance. Avoid that by pushing back
1284 // the first character (which ensures exponential growth) and then
1285 // appending the rest normally. Worst case the append may incur a
1286 // second allocation but that will be rare.
1289 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1290 assert(size() == oldSize + n + 1);
1294 basic_fbstring& append(const value_type* s) {
1295 return append(s, traits_type::length(s));
1298 basic_fbstring& append(size_type n, value_type c) {
1299 resize(size() + n, c);
1303 template<class InputIterator>
1304 basic_fbstring& append(InputIterator first, InputIterator last) {
1305 insert(end(), first, last);
1309 void push_back(const value_type c) { // primitive
1310 store_.push_back(c);
1313 basic_fbstring& assign(const basic_fbstring& str) {
1314 if (&str == this) return *this;
1315 return assign(str.data(), str.size());
1318 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1320 const size_type sz = str.size();
1321 enforce(pos <= sz, std::__throw_out_of_range, "");
1322 procrustes(n, sz - pos);
1323 return assign(str.data() + pos, n);
1326 basic_fbstring& assign(const value_type* s, const size_type n) {
1327 Invariant checker(*this);
1330 std::copy(s, s + n, begin());
1332 assert(size() == n);
1334 const value_type *const s2 = s + size();
1335 std::copy(s, s2, begin());
1336 append(s2, n - size());
1337 assert(size() == n);
1339 store_.writeTerminator();
1340 assert(size() == n);
1344 basic_fbstring& assign(const value_type* s) {
1345 return assign(s, traits_type::length(s));
1348 template <class ItOrLength, class ItOrChar>
1349 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1350 return replace(begin(), end(), first_or_n, last_or_c);
1353 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1354 return insert(pos1, str.data(), str.size());
1357 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1358 size_type pos2, size_type n) {
1359 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1360 procrustes(n, str.length() - pos2);
1361 return insert(pos1, str.data() + pos2, n);
1364 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1365 enforce(pos <= length(), std::__throw_out_of_range, "");
1366 insert(begin() + pos, s, s + n);
1370 basic_fbstring& insert(size_type pos, const value_type* s) {
1371 return insert(pos, s, traits_type::length(s));
1374 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1375 enforce(pos <= length(), std::__throw_out_of_range, "");
1376 insert(begin() + pos, n, c);
1380 iterator insert(const iterator p, const value_type c) {
1381 const size_type pos = p - begin();
1383 return begin() + pos;
1387 template <int i> class Selector {};
1389 basic_fbstring& insertImplDiscr(iterator p,
1390 size_type n, value_type c, Selector<1>) {
1391 Invariant checker(*this);
1393 assert(p >= begin() && p <= end());
1394 if (capacity() - size() < n) {
1395 const size_type sz = p - begin();
1396 reserve(size() + n);
1399 const iterator oldEnd = end();
1400 if( n < size_type(oldEnd - p)) {
1401 append(oldEnd - n, oldEnd);
1403 // reverse_iterator(oldEnd - n),
1404 // reverse_iterator(p),
1405 // reverse_iterator(oldEnd));
1406 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1407 std::fill(p, p + n, c);
1409 append(n - (end() - p), c);
1411 std::fill(p, oldEnd, c);
1413 store_.writeTerminator();
1417 template<class InputIter>
1418 basic_fbstring& insertImplDiscr(iterator i,
1419 InputIter b, InputIter e, Selector<0>) {
1421 typename std::iterator_traits<InputIter>::iterator_category());
1425 template <class FwdIterator>
1426 void insertImpl(iterator i,
1427 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1428 Invariant checker(*this);
1430 const size_type pos = i - begin();
1431 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1432 std::distance(s1, s2);
1434 using namespace fbstring_detail;
1435 assert(pos <= size());
1437 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1438 capacity() - size();
1440 // realloc the string
1441 reserve(size() + n2);
1444 if (pos + n2 <= size()) {
1445 const iterator tailBegin = end() - n2;
1446 store_.expand_noinit(n2);
1447 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1448 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1449 reverse_iterator(tailBegin + n2));
1450 std::copy(s1, s2, i);
1453 const size_type old_size = size();
1454 std::advance(t, old_size - pos);
1455 const size_t newElems = std::distance(t, s2);
1456 store_.expand_noinit(n2);
1457 std::copy(t, s2, begin() + old_size);
1458 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1459 begin() + old_size + newElems);
1460 std::copy(s1, t, i);
1462 store_.writeTerminator();
1465 template <class InputIterator>
1466 void insertImpl(iterator i,
1467 InputIterator b, InputIterator e, std::input_iterator_tag) {
1468 basic_fbstring temp(begin(), i);
1469 for (; b != e; ++b) {
1472 temp.append(i, end());
1477 template <class ItOrLength, class ItOrChar>
1478 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1479 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1480 insertImplDiscr(p, first_or_n, last_or_c, sel);
1483 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1484 Invariant checker(*this);
1486 enforce(pos <= length(), std::__throw_out_of_range, "");
1487 procrustes(n, length() - pos);
1488 std::copy(begin() + pos + n, end(), begin() + pos);
1489 resize(length() - n);
1493 iterator erase(iterator position) {
1494 const size_type pos(position - begin());
1495 enforce(pos <= size(), std::__throw_out_of_range, "");
1497 return begin() + pos;
1500 iterator erase(iterator first, iterator last) {
1501 const size_type pos(first - begin());
1502 erase(pos, last - first);
1503 return begin() + pos;
1506 // Replaces at most n1 chars of *this, starting with pos1 with the
1508 basic_fbstring& replace(size_type pos1, size_type n1,
1509 const basic_fbstring& str) {
1510 return replace(pos1, n1, str.data(), str.size());
1513 // Replaces at most n1 chars of *this, starting with pos1,
1514 // with at most n2 chars of str starting with pos2
1515 basic_fbstring& replace(size_type pos1, size_type n1,
1516 const basic_fbstring& str,
1517 size_type pos2, size_type n2) {
1518 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1519 return replace(pos1, n1, str.data() + pos2,
1520 std::min(n2, str.size() - pos2));
1523 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1524 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1525 return replace(pos, n1, s, traits_type::length(s));
1528 // Replaces at most n1 chars of *this, starting with pos, with n2
1531 // consolidated with
1533 // Replaces at most n1 chars of *this, starting with pos, with at
1534 // most n2 chars of str. str must have at least n2 chars.
1535 template <class StrOrLength, class NumOrChar>
1536 basic_fbstring& replace(size_type pos, size_type n1,
1537 StrOrLength s_or_n2, NumOrChar n_or_c) {
1538 Invariant checker(*this);
1540 enforce(pos <= size(), std::__throw_out_of_range, "");
1541 procrustes(n1, length() - pos);
1542 const iterator b = begin() + pos;
1543 return replace(b, b + n1, s_or_n2, n_or_c);
1546 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1547 return replace(i1, i2, str.data(), str.length());
1550 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1551 return replace(i1, i2, s, traits_type::length(s));
1555 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1556 const value_type* s, size_type n,
1559 assert(begin() <= i1 && i1 <= end());
1560 assert(begin() <= i2 && i2 <= end());
1561 return replace(i1, i2, s, s + n);
1564 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1565 size_type n2, value_type c, Selector<1>) {
1566 const size_type n1 = i2 - i1;
1568 std::fill(i1, i1 + n2, c);
1571 std::fill(i1, i2, c);
1572 insert(i2, n2 - n1, c);
1578 template <class InputIter>
1579 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1580 InputIter b, InputIter e,
1582 replaceImpl(i1, i2, b, e,
1583 typename std::iterator_traits<InputIter>::iterator_category());
1588 template <class FwdIterator, class P>
1589 bool replaceAliased(iterator i1, iterator i2,
1590 FwdIterator s1, FwdIterator s2, P*) {
1594 template <class FwdIterator>
1595 bool replaceAliased(iterator i1, iterator i2,
1596 FwdIterator s1, FwdIterator s2, value_type*) {
1597 static const std::less_equal<const value_type*> le =
1598 std::less_equal<const value_type*>();
1599 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1603 // Aliased replace, copy to new string
1604 basic_fbstring temp;
1605 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1606 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1612 template <class FwdIterator>
1613 void replaceImpl(iterator i1, iterator i2,
1614 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1615 Invariant checker(*this);
1618 // Handle aliased replace
1619 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1623 auto const n1 = i2 - i1;
1625 auto const n2 = std::distance(s1, s2);
1630 std::copy(s1, s2, i1);
1634 fbstring_detail::copy_n(s1, n1, i1);
1635 std::advance(s1, n1);
1641 template <class InputIterator>
1642 void replaceImpl(iterator i1, iterator i2,
1643 InputIterator b, InputIterator e, std::input_iterator_tag) {
1644 basic_fbstring temp(begin(), i1);
1645 temp.append(b, e).append(i2, end());
1650 template <class T1, class T2>
1651 basic_fbstring& replace(iterator i1, iterator i2,
1652 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1654 num1 = std::numeric_limits<T1>::is_specialized,
1655 num2 = std::numeric_limits<T2>::is_specialized;
1656 return replaceImplDiscr(
1657 i1, i2, first_or_n_or_s, last_or_c_or_n,
1658 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1661 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1662 enforce(pos <= size(), std::__throw_out_of_range, "");
1663 procrustes(n, size() - pos);
1665 fbstring_detail::pod_copy(
1672 void swap(basic_fbstring& rhs) {
1673 store_.swap(rhs.store_);
1676 // 21.3.6 string operations:
1677 const value_type* c_str() const {
1678 return store_.c_str();
1681 const value_type* data() const { return c_str(); }
1683 allocator_type get_allocator() const {
1684 return allocator_type();
1687 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1688 return find(str.data(), pos, str.length());
1691 size_type find(const value_type* needle, const size_type pos,
1692 const size_type nsize) const {
1693 if (!nsize) return pos;
1694 auto const size = this->size();
1695 if (nsize + pos > size) return npos;
1696 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1697 // the last characters first
1698 auto const haystack = data();
1699 auto const nsize_1 = nsize - 1;
1700 auto const lastNeedle = needle[nsize_1];
1702 // Boyer-Moore skip value for the last char in the needle. Zero is
1703 // not a valid value; skip will be computed the first time it's
1707 const E * i = haystack + pos;
1708 auto iEnd = haystack + size - nsize_1;
1711 // Boyer-Moore: match the last element in the needle
1712 while (i[nsize_1] != lastNeedle) {
1718 // Here we know that the last char matches
1719 // Continue in pedestrian mode
1720 for (size_t j = 0; ; ) {
1722 if (i[j] != needle[j]) {
1723 // Not found, we can skip
1724 // Compute the skip value lazily
1727 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1734 // Check if done searching
1737 return i - haystack;
1744 size_type find(const value_type* s, size_type pos = 0) const {
1745 return find(s, pos, traits_type::length(s));
1748 size_type find (value_type c, size_type pos = 0) const {
1749 return find(&c, pos, 1);
1752 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1753 return rfind(str.data(), pos, str.length());
1756 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1757 if (n > length()) return npos;
1758 pos = std::min(pos, length() - n);
1759 if (n == 0) return pos;
1761 const_iterator i(begin() + pos);
1763 if (traits_type::eq(*i, *s)
1764 && traits_type::compare(&*i, s, n) == 0) {
1767 if (i == begin()) break;
1772 size_type rfind(const value_type* s, size_type pos = npos) const {
1773 return rfind(s, pos, traits_type::length(s));
1776 size_type rfind(value_type c, size_type pos = npos) const {
1777 return rfind(&c, pos, 1);
1780 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1781 return find_first_of(str.data(), pos, str.length());
1784 size_type find_first_of(const value_type* s,
1785 size_type pos, size_type n) const {
1786 if (pos > length() || n == 0) return npos;
1787 const_iterator i(begin() + pos),
1789 for (; i != finish; ++i) {
1790 if (traits_type::find(s, n, *i) != 0) {
1797 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1798 return find_first_of(s, pos, traits_type::length(s));
1801 size_type find_first_of(value_type c, size_type pos = 0) const {
1802 return find_first_of(&c, pos, 1);
1805 size_type find_last_of (const basic_fbstring& str,
1806 size_type pos = npos) const {
1807 return find_last_of(str.data(), pos, str.length());
1810 size_type find_last_of (const value_type* s, size_type pos,
1811 size_type n) const {
1812 if (!empty() && n > 0) {
1813 pos = std::min(pos, length() - 1);
1814 const_iterator i(begin() + pos);
1816 if (traits_type::find(s, n, *i) != 0) {
1819 if (i == begin()) break;
1825 size_type find_last_of (const value_type* s,
1826 size_type pos = npos) const {
1827 return find_last_of(s, pos, traits_type::length(s));
1830 size_type find_last_of (value_type c, size_type pos = npos) const {
1831 return find_last_of(&c, pos, 1);
1834 size_type find_first_not_of(const basic_fbstring& str,
1835 size_type pos = 0) const {
1836 return find_first_not_of(str.data(), pos, str.size());
1839 size_type find_first_not_of(const value_type* s, size_type pos,
1840 size_type n) const {
1841 if (pos < length()) {
1845 for (; i != finish; ++i) {
1846 if (traits_type::find(s, n, *i) == 0) {
1854 size_type find_first_not_of(const value_type* s,
1855 size_type pos = 0) const {
1856 return find_first_not_of(s, pos, traits_type::length(s));
1859 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1860 return find_first_not_of(&c, pos, 1);
1863 size_type find_last_not_of(const basic_fbstring& str,
1864 size_type pos = npos) const {
1865 return find_last_not_of(str.data(), pos, str.length());
1868 size_type find_last_not_of(const value_type* s, size_type pos,
1869 size_type n) const {
1870 if (!this->empty()) {
1871 pos = std::min(pos, size() - 1);
1872 const_iterator i(begin() + pos);
1874 if (traits_type::find(s, n, *i) == 0) {
1877 if (i == begin()) break;
1883 size_type find_last_not_of(const value_type* s,
1884 size_type pos = npos) const {
1885 return find_last_not_of(s, pos, traits_type::length(s));
1888 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1889 return find_last_not_of(&c, pos, 1);
1892 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1893 enforce(pos <= size(), std::__throw_out_of_range, "");
1894 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1897 int compare(const basic_fbstring& str) const {
1898 // FIX due to Goncalo N M de Carvalho July 18, 2005
1899 return compare(0, size(), str);
1902 int compare(size_type pos1, size_type n1,
1903 const basic_fbstring& str) const {
1904 return compare(pos1, n1, str.data(), str.size());
1907 int compare(size_type pos1, size_type n1,
1908 const value_type* s) const {
1909 return compare(pos1, n1, s, traits_type::length(s));
1912 int compare(size_type pos1, size_type n1,
1913 const value_type* s, size_type n2) const {
1914 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1915 procrustes(n1, size() - pos1);
1916 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1917 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1918 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1921 int compare(size_type pos1, size_type n1,
1922 const basic_fbstring& str,
1923 size_type pos2, size_type n2) const {
1924 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1925 return compare(pos1, n1, str.data() + pos2,
1926 std::min(n2, str.size() - pos2));
1929 // Code from Jean-Francois Bastien (03/26/2007)
1930 int compare(const value_type* s) const {
1931 // Could forward to compare(0, size(), s, traits_type::length(s))
1932 // but that does two extra checks
1933 const size_type n1(size()), n2(traits_type::length(s));
1934 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1935 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1943 // non-member functions
1945 template <typename E, class T, class A, class S>
1947 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1948 const basic_fbstring<E, T, A, S>& rhs) {
1950 basic_fbstring<E, T, A, S> result;
1951 result.reserve(lhs.size() + rhs.size());
1952 result.append(lhs).append(rhs);
1953 return std::move(result);
1957 template <typename E, class T, class A, class S>
1959 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1960 const basic_fbstring<E, T, A, S>& rhs) {
1961 return std::move(lhs.append(rhs));
1965 template <typename E, class T, class A, class S>
1967 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1968 basic_fbstring<E, T, A, S>&& rhs) {
1969 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1970 // Good, at least we don't need to reallocate
1971 return std::move(rhs.insert(0, lhs));
1973 // Meh, no go. Forward to operator+(const&, const&).
1974 auto const& rhsC = rhs;
1979 template <typename E, class T, class A, class S>
1981 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1982 basic_fbstring<E, T, A, S>&& rhs) {
1983 return std::move(lhs.append(rhs));
1986 template <typename E, class T, class A, class S>
1988 basic_fbstring<E, T, A, S> operator+(
1989 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
1990 const basic_fbstring<E, T, A, S>& rhs) {
1992 basic_fbstring<E, T, A, S> result;
1993 const typename basic_fbstring<E, T, A, S>::size_type len =
1994 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
1995 result.reserve(len + rhs.size());
1996 result.append(lhs, len).append(rhs);
2000 template <typename E, class T, class A, class S>
2002 basic_fbstring<E, T, A, S> operator+(
2003 typename basic_fbstring<E, T, A, S>::value_type lhs,
2004 const basic_fbstring<E, T, A, S>& rhs) {
2006 basic_fbstring<E, T, A, S> result;
2007 result.reserve(1 + rhs.size());
2008 result.push_back(lhs);
2013 template <typename E, class T, class A, class S>
2015 basic_fbstring<E, T, A, S> operator+(
2016 const basic_fbstring<E, T, A, S>& lhs,
2017 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2019 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2020 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2022 basic_fbstring<E, T, A, S> result;
2023 const size_type len = traits_type::length(rhs);
2024 result.reserve(lhs.size() + len);
2025 result.append(lhs).append(rhs, len);
2029 template <typename E, class T, class A, class S>
2031 basic_fbstring<E, T, A, S> operator+(
2032 const basic_fbstring<E, T, A, S>& lhs,
2033 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2035 basic_fbstring<E, T, A, S> result;
2036 result.reserve(lhs.size() + 1);
2038 result.push_back(rhs);
2042 template <typename E, class T, class A, class S>
2044 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2045 const basic_fbstring<E, T, A, S>& rhs) {
2046 return lhs.compare(rhs) == 0; }
2048 template <typename E, class T, class A, class S>
2050 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2051 const basic_fbstring<E, T, A, S>& rhs) {
2052 return rhs == lhs; }
2054 template <typename E, class T, class A, class S>
2056 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2057 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2058 return lhs.compare(rhs) == 0; }
2060 template <typename E, class T, class A, class S>
2062 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2063 const basic_fbstring<E, T, A, S>& rhs) {
2064 return !(lhs == rhs); }
2066 template <typename E, class T, class A, class S>
2068 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2069 const basic_fbstring<E, T, A, S>& rhs) {
2070 return !(lhs == rhs); }
2072 template <typename E, class T, class A, class S>
2074 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2075 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2076 return !(lhs == rhs); }
2078 template <typename E, class T, class A, class S>
2080 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2081 const basic_fbstring<E, T, A, S>& rhs) {
2082 return lhs.compare(rhs) < 0; }
2084 template <typename E, class T, class A, class S>
2086 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2087 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2088 return lhs.compare(rhs) < 0; }
2090 template <typename E, class T, class A, class S>
2092 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2093 const basic_fbstring<E, T, A, S>& rhs) {
2094 return rhs.compare(lhs) > 0; }
2096 template <typename E, class T, class A, class S>
2098 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2099 const basic_fbstring<E, T, A, S>& rhs) {
2102 template <typename E, class T, class A, class S>
2104 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2105 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2108 template <typename E, class T, class A, class S>
2110 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2111 const basic_fbstring<E, T, A, S>& rhs) {
2114 template <typename E, class T, class A, class S>
2116 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2117 const basic_fbstring<E, T, A, S>& rhs) {
2118 return !(rhs < lhs); }
2120 template <typename E, class T, class A, class S>
2122 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2123 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2124 return !(rhs < lhs); }
2126 template <typename E, class T, class A, class S>
2128 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2129 const basic_fbstring<E, T, A, S>& rhs) {
2130 return !(rhs < lhs); }
2132 template <typename E, class T, class A, class S>
2134 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2135 const basic_fbstring<E, T, A, S>& rhs) {
2136 return !(lhs < rhs); }
2138 template <typename E, class T, class A, class S>
2140 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2141 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2142 return !(lhs < rhs); }
2144 template <typename E, class T, class A, class S>
2146 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2147 const basic_fbstring<E, T, A, S>& rhs) {
2148 return !(lhs < rhs);
2151 // subclause 21.3.7.8:
2152 template <typename E, class T, class A, class S>
2153 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2157 // TODO: make this faster.
2158 template <typename E, class T, class A, class S>
2161 typename basic_fbstring<E, T, A, S>::value_type,
2162 typename basic_fbstring<E, T, A, S>::traits_type>&
2164 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2165 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2166 basic_fbstring<E, T, A, S>& str) {
2167 typename std::basic_istream<E, T>::sentry sentry(is);
2168 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2169 typename basic_fbstring<E, T, A, S>::traits_type>
2171 typedef typename __istream_type::ios_base __ios_base;
2172 size_t extracted = 0;
2173 auto err = __ios_base::goodbit;
2175 auto n = is.width();
2180 auto got = is.rdbuf()->sgetc();
2181 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2182 // Whew. We get to store this guy
2184 got = is.rdbuf()->snextc();
2186 if (got == T::eof()) {
2187 err |= __ios_base::eofbit;
2192 err |= __ios_base::failbit;
2200 template <typename E, class T, class A, class S>
2202 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2203 typename basic_fbstring<E, T, A, S>::traits_type>&
2205 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2206 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2207 const basic_fbstring<E, T, A, S>& str) {
2208 os.write(str.data(), str.size());
2212 #ifndef _LIBSTDCXX_FBSTRING
2214 template <typename E, class T, class A, class S>
2216 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2217 typename basic_fbstring<E, T, A, S>::traits_type>&
2219 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2220 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2221 basic_fbstring<E, T, A, S>& str,
2222 typename basic_fbstring<E, T, A, S>::value_type delim) {
2223 // Use the nonstandard getdelim()
2227 // This looks quadratic but it really depends on realloc
2228 auto const newSize = size + 128;
2229 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2230 is.getline(buf + size, newSize - size, delim);
2231 if (is.bad() || is.eof() || !is.fail()) {
2232 // done by either failure, end of file, or normal read
2233 size += std::strlen(buf + size);
2236 // Here we have failed due to too short a buffer
2237 // Minus one to discount the terminating '\0'
2239 assert(buf[size] == 0);
2240 // Clear the error so we can continue reading
2243 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2244 AcquireMallocatedString());
2249 template <typename E, class T, class A, class S>
2251 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2252 typename basic_fbstring<E, T, A, S>::traits_type>&
2254 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2255 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2256 basic_fbstring<E, T, A, S>& str) {
2257 // Just forward to the version with a delimiter
2258 return getline(is, str, '\n');
2263 template <typename E1, class T, class A, class S>
2264 const typename basic_fbstring<E1, T, A, S>::size_type
2265 basic_fbstring<E1, T, A, S>::npos =
2266 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2268 #ifndef _LIBSTDCXX_FBSTRING
2269 // basic_string compatibility routines
2271 template <typename E, class T, class A, class S>
2273 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2274 const std::string& rhs) {
2275 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2278 template <typename E, class T, class A, class S>
2280 bool operator==(const std::string& lhs,
2281 const basic_fbstring<E, T, A, S>& rhs) {
2285 template <typename E, class T, class A, class S>
2287 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2288 const std::string& rhs) {
2289 return !(lhs == rhs);
2292 template <typename E, class T, class A, class S>
2294 bool operator!=(const std::string& lhs,
2295 const basic_fbstring<E, T, A, S>& rhs) {
2296 return !(lhs == rhs);
2299 #if !defined(_LIBSTDCXX_FBSTRING)
2300 typedef basic_fbstring<char> fbstring;
2303 // fbstring is relocatable
2304 template <class T, class R, class A, class S>
2305 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2308 _GLIBCXX_END_NAMESPACE_VERSION
2311 } // namespace folly
2313 #ifndef _LIBSTDCXX_FBSTRING
2317 struct hash< ::folly::fbstring> {
2318 size_t operator()(const ::folly::fbstring& s) const {
2319 return ::folly::hash::fnv32_buf(s.data(), s.size());
2324 #endif // _LIBSTDCXX_FBSTRING
2326 #endif // FOLLY_BASE_FBSTRING_H_