2 * Copyright 2017 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)
26 #include <type_traits>
28 // This file appears in two locations: inside fbcode and in the
29 // libstdc++ source code (when embedding fbstring as std::string).
30 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
31 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
32 #ifdef _LIBSTDCXX_FBSTRING
34 #pragma GCC system_header
36 #include "basic_fbstring_malloc.h"
38 // When used as std::string replacement always disable assertions.
39 #define FBSTRING_ASSERT(expr) /* empty */
41 #else // !_LIBSTDCXX_FBSTRING
43 #include <folly/Portability.h>
45 // libc++ doesn't provide this header, nor does msvc
46 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
47 #include <bits/c++config.h>
56 #include <folly/Hash.h>
57 #include <folly/Malloc.h>
58 #include <folly/Traits.h>
59 #include <folly/portability/BitsFunctexcept.h>
61 #if FOLLY_HAVE_DEPRECATED_ASSOC
62 #ifdef _GLIBCXX_SYMVER
63 #include <ext/hash_set>
64 #include <ext/hash_map>
68 // When used in folly, assertions are not disabled.
69 #define FBSTRING_ASSERT(expr) assert(expr)
73 // We defined these here rather than including Likely.h to avoid
74 // redefinition errors when fbstring is imported into libstdc++.
75 #if defined(__GNUC__) && __GNUC__ >= 4
76 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
77 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
79 #define FBSTRING_LIKELY(x) (x)
80 #define FBSTRING_UNLIKELY(x) (x)
84 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
85 FOLLY_GCC_DISABLE_WARNING("-Wshadow")
86 // GCC 4.9 has a false positive in setSmallSize (probably
87 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
88 // compile-time array bound checking.
89 FOLLY_GCC_DISABLE_WARNING("-Warray-bounds")
91 // FBString cannot use throw when replacing std::string, though it may still
94 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
96 #ifdef _LIBSTDCXX_FBSTRING
97 namespace std _GLIBCXX_VISIBILITY(default) {
98 _GLIBCXX_BEGIN_NAMESPACE_VERSION
103 #if defined(__clang__)
104 # if __has_feature(address_sanitizer)
105 # define FBSTRING_SANITIZE_ADDRESS
107 #elif defined (__GNUC__) && \
108 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
110 # define FBSTRING_SANITIZE_ADDRESS
113 // When compiling with ASan, always heap-allocate the string even if
114 // it would fit in-situ, so that ASan can detect access to the string
115 // buffer after it has been invalidated (destroyed, resized, etc.).
116 // Note that this flag doesn't remove support for in-situ strings, as
117 // that would break ABI-compatibility and wouldn't allow linking code
118 // compiled with this flag with code compiled without.
119 #ifdef FBSTRING_SANITIZE_ADDRESS
120 # define FBSTRING_DISABLE_SSO true
122 # define FBSTRING_DISABLE_SSO false
125 namespace fbstring_detail {
127 template <class InIt, class OutIt>
128 inline std::pair<InIt, OutIt> copy_n(
130 typename std::iterator_traits<InIt>::difference_type n,
132 for (; n != 0; --n, ++b, ++d) {
135 return std::make_pair(b, d);
138 template <class Pod, class T>
139 inline void podFill(Pod* b, Pod* e, T c) {
140 FBSTRING_ASSERT(b && e && b <= e);
141 constexpr auto kUseMemset = sizeof(T) == 1;
142 /* static */ if (kUseMemset) {
143 memset(b, c, size_t(e - b));
145 auto const ee = b + ((e - b) & ~7u);
146 for (; b != ee; b += 8) {
157 for (; b != e; ++b) {
164 * Lightly structured memcpy, simplifies copying PODs and introduces
165 * some asserts. Unfortunately using this function may cause
166 * measurable overhead (presumably because it adjusts from a begin/end
167 * convention to a pointer/size convention, so it does some extra
168 * arithmetic even though the caller might have done the inverse
169 * adaptation outside).
172 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
173 FBSTRING_ASSERT(b != nullptr);
174 FBSTRING_ASSERT(e != nullptr);
175 FBSTRING_ASSERT(d != nullptr);
176 FBSTRING_ASSERT(e >= b);
177 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
178 memcpy(d, b, (e - b) * sizeof(Pod));
182 * Lightly structured memmove, simplifies copying PODs and introduces
186 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
187 FBSTRING_ASSERT(e >= b);
188 memmove(d, b, (e - b) * sizeof(*b));
192 #if defined(__GNUC__) // Clang also defines __GNUC__
193 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
194 #elif defined(_MSC_VER)
195 # define FBSTRING_ALWAYS_INLINE __forceinline
197 # define FBSTRING_ALWAYS_INLINE inline
200 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
201 #if defined(__GNUC__) // Clang also defines __GNUC__
202 __builtin_unreachable();
203 #elif defined(_MSC_VER)
206 // Well, it's better than nothing.
211 } // namespace fbstring_detail
214 * Defines a special acquisition method for constructing fbstring
215 * objects. AcquireMallocatedString means that the user passes a
216 * pointer to a malloc-allocated string that the fbstring object will
219 enum class AcquireMallocatedString {};
222 * fbstring_core_model is a mock-up type that defines all required
223 * signatures of a fbstring core. The fbstring class itself uses such
224 * a core object to implement all of the numerous member functions
225 * required by the standard.
227 * If you want to define a new core, copy the definition below and
228 * implement the primitives. Then plug the core into basic_fbstring as
229 * a template argument.
231 template <class Char>
232 class fbstring_core_model {
234 fbstring_core_model();
235 fbstring_core_model(const fbstring_core_model &);
236 ~fbstring_core_model();
237 // Returns a pointer to string's buffer (currently only contiguous
238 // strings are supported). The pointer is guaranteed to be valid
239 // until the next call to a non-const member function.
240 const Char * data() const;
241 // Much like data(), except the string is prepared to support
242 // character-level changes. This call is a signal for
243 // e.g. reference-counted implementation to fork the data. The
244 // pointer is guaranteed to be valid until the next call to a
245 // non-const member function.
247 // Returns a pointer to string's buffer and guarantees that a
248 // readable '\0' lies right after the buffer. The pointer is
249 // guaranteed to be valid until the next call to a non-const member
251 const Char * c_str() const;
252 // Shrinks the string by delta characters. Asserts that delta <=
254 void shrink(size_t delta);
255 // Expands the string by delta characters (i.e. after this call
256 // size() will report the old size() plus delta) but without
257 // initializing the expanded region. The expanded region is
258 // zero-terminated. Returns a pointer to the memory to be
259 // initialized (the beginning of the expanded portion). The caller
260 // is expected to fill the expanded area appropriately.
261 // If expGrowth is true, exponential growth is guaranteed.
262 // It is not guaranteed not to reallocate even if size() + delta <
263 // capacity(), so all references to the buffer are invalidated.
264 Char* expandNoinit(size_t delta, bool expGrowth);
265 // Expands the string by one character and sets the last character
267 void push_back(Char c);
268 // Returns the string's size.
270 // Returns the string's capacity, i.e. maximum size that the string
271 // can grow to without reallocation. Note that for reference counted
272 // strings that's technically a lie - even assigning characters
273 // within the existing size would cause a reallocation.
274 size_t capacity() const;
275 // Returns true if the data underlying the string is actually shared
276 // across multiple strings (in a refcounted fashion).
277 bool isShared() const;
278 // Makes sure that at least minCapacity characters are available for
279 // the string without reallocation. For reference-counted strings,
280 // it should fork the data even if minCapacity < size().
281 void reserve(size_t minCapacity);
284 fbstring_core_model& operator=(const fbstring_core_model &);
289 * This is the core of the string. The code should work on 32- and
290 * 64-bit and both big- and little-endianan architectures with any
293 * The storage is selected as follows (assuming we store one-byte
294 * characters on a 64-bit machine): (a) "small" strings between 0 and
295 * 23 chars are stored in-situ without allocation (the rightmost byte
296 * stores the size); (b) "medium" strings from 24 through 254 chars
297 * are stored in malloc-allocated memory that is copied eagerly; (c)
298 * "large" strings of 255 chars and above are stored in a similar
299 * structure as medium arrays, except that the string is
300 * reference-counted and copied lazily. the reference count is
301 * allocated right before the character array.
303 * The discriminator between these three strategies sits in two
304 * bits of the rightmost char of the storage. If neither is set, then the
305 * string is small (and its length sits in the lower-order bits on
306 * little-endian or the high-order bits on big-endian of that
307 * rightmost character). If the MSb is set, the string is medium width.
308 * If the second MSb is set, then the string is large. On little-endian,
309 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
310 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
311 * and big-endian fbstring_core equivalent with merely different ops used
312 * to extract capacity/category.
314 template <class Char> class fbstring_core {
316 // It's MSVC, so we just have to guess ... and allow an override
318 # ifdef FOLLY_ENDIAN_BE
319 static constexpr auto kIsLittleEndian = false;
321 static constexpr auto kIsLittleEndian = true;
324 static constexpr auto kIsLittleEndian =
325 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
328 fbstring_core() noexcept { reset(); }
330 fbstring_core(const fbstring_core & rhs) {
331 FBSTRING_ASSERT(&rhs != this);
332 switch (rhs.category()) {
333 case Category::isSmall:
336 case Category::isMedium:
339 case Category::isLarge:
343 fbstring_detail::assume_unreachable();
345 FBSTRING_ASSERT(size() == rhs.size());
346 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
349 fbstring_core(fbstring_core&& goner) noexcept {
352 // Clean goner's carcass
356 fbstring_core(const Char *const data,
358 bool disableSSO = FBSTRING_DISABLE_SSO) {
359 if (!disableSSO && size <= maxSmallSize) {
360 initSmall(data, size);
361 } else if (size <= maxMediumSize) {
362 initMedium(data, size);
364 initLarge(data, size);
366 FBSTRING_ASSERT(this->size() == size);
368 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
371 ~fbstring_core() noexcept {
372 if (category() == Category::isSmall) {
375 destroyMediumLarge();
378 // Snatches a previously mallocated string. The parameter "size"
379 // is the size of the string, and the parameter "allocatedSize"
380 // is the size of the mallocated block. The string must be
381 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
383 // So if you want a 2-character string, pass malloc(3) as "data",
384 // pass 2 as "size", and pass 3 as "allocatedSize".
385 fbstring_core(Char * const data,
387 const size_t allocatedSize,
388 AcquireMallocatedString) {
390 FBSTRING_ASSERT(allocatedSize >= size + 1);
391 FBSTRING_ASSERT(data[size] == '\0');
392 // Use the medium string storage
395 // Don't forget about null terminator
396 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
398 // No need for the memory
404 // swap below doesn't test whether &rhs == this (and instead
405 // potentially does extra work) on the premise that the rarity of
406 // that situation actually makes the check more expensive than is
408 void swap(fbstring_core & rhs) {
414 // In C++11 data() and c_str() are 100% equivalent.
415 const Char * data() const {
419 Char* mutableData() {
420 switch (category()) {
421 case Category::isSmall:
423 case Category::isMedium:
425 case Category::isLarge:
426 return mutableDataLarge();
428 fbstring_detail::assume_unreachable();
431 const Char* c_str() const {
432 const Char* ptr = ml_.data_;
433 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
434 ptr = (category() == Category::isSmall) ? small_ : ptr;
438 void shrink(const size_t delta) {
439 if (category() == Category::isSmall) {
441 } else if (category() == Category::isMedium ||
442 RefCounted::refs(ml_.data_) == 1) {
449 FOLLY_MALLOC_NOINLINE
450 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
451 switch (category()) {
452 case Category::isSmall:
453 reserveSmall(minCapacity, disableSSO);
455 case Category::isMedium:
456 reserveMedium(minCapacity);
458 case Category::isLarge:
459 reserveLarge(minCapacity);
462 fbstring_detail::assume_unreachable();
464 FBSTRING_ASSERT(capacity() >= minCapacity);
469 bool expGrowth = false,
470 bool disableSSO = FBSTRING_DISABLE_SSO);
472 void push_back(Char c) {
473 *expandNoinit(1, /* expGrowth = */ true) = c;
476 size_t size() const {
477 size_t ret = ml_.size_;
478 /* static */ if (kIsLittleEndian) {
479 // We can save a couple instructions, because the category is
480 // small iff the last char, as unsigned, is <= maxSmallSize.
481 typedef typename std::make_unsigned<Char>::type UChar;
482 auto maybeSmallSize = size_t(maxSmallSize) -
483 size_t(static_cast<UChar>(small_[maxSmallSize]));
484 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
485 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
487 ret = (category() == Category::isSmall) ? smallSize() : ret;
492 size_t capacity() const {
493 switch (category()) {
494 case Category::isSmall:
496 case Category::isLarge:
497 // For large-sized strings, a multi-referenced chunk has no
498 // available capacity. This is because any attempt to append
499 // data would trigger a new allocation.
500 if (RefCounted::refs(ml_.data_) > 1) {
505 return ml_.capacity();
508 bool isShared() const {
509 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
514 fbstring_core & operator=(const fbstring_core & rhs);
520 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
521 auto const c = category();
522 FBSTRING_ASSERT(c != Category::isSmall);
523 if (c == Category::isMedium) {
526 RefCounted::decrementRefs(ml_.data_);
531 std::atomic<size_t> refCount_;
534 constexpr static size_t getDataOffset() {
535 return offsetof(RefCounted, data_);
538 static RefCounted * fromData(Char * p) {
539 return static_cast<RefCounted*>(static_cast<void*>(
540 static_cast<unsigned char*>(static_cast<void*>(p)) -
544 static size_t refs(Char * p) {
545 return fromData(p)->refCount_.load(std::memory_order_acquire);
548 static void incrementRefs(Char * p) {
549 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
552 static void decrementRefs(Char * p) {
553 auto const dis = fromData(p);
554 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
555 FBSTRING_ASSERT(oldcnt > 0);
561 static RefCounted * create(size_t * size) {
562 const size_t allocSize =
563 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
564 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
565 result->refCount_.store(1, std::memory_order_release);
566 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
570 static RefCounted * create(const Char * data, size_t * size) {
571 const size_t effectiveSize = *size;
572 auto result = create(size);
573 if (FBSTRING_LIKELY(effectiveSize > 0)) {
574 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
579 static RefCounted * reallocate(Char *const data,
580 const size_t currentSize,
581 const size_t currentCapacity,
582 size_t * newCapacity) {
583 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
584 const size_t allocNewCapacity =
585 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
586 auto const dis = fromData(data);
587 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
588 auto result = static_cast<RefCounted*>(smartRealloc(
590 getDataOffset() + (currentSize + 1) * sizeof(Char),
591 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
593 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
594 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
599 typedef uint8_t category_type;
601 enum class Category : category_type {
603 isMedium = kIsLittleEndian ? 0x80 : 0x2,
604 isLarge = kIsLittleEndian ? 0x40 : 0x1,
607 Category category() const {
608 // works for both big-endian and little-endian
609 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
617 size_t capacity() const {
618 return kIsLittleEndian
619 ? capacity_ & capacityExtractMask
623 void setCapacity(size_t cap, Category cat) {
624 capacity_ = kIsLittleEndian
625 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
626 : (cap << 2) | static_cast<size_t>(cat);
631 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
632 Char small_[sizeof(MediumLarge) / sizeof(Char)];
636 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
637 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
638 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
639 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
640 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
641 constexpr static size_t capacityExtractMask = kIsLittleEndian
642 ? ~(size_t(categoryExtractMask) << kCategoryShift)
645 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
646 "Corrupt memory layout for fbstring.");
648 size_t smallSize() const {
649 FBSTRING_ASSERT(category() == Category::isSmall);
650 constexpr auto shift = kIsLittleEndian ? 0 : 2;
651 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
652 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
653 return static_cast<size_t>(maxSmallSize) - smallShifted;
656 void setSmallSize(size_t s) {
657 // Warning: this should work with uninitialized strings too,
658 // so don't assume anything about the previous value of
659 // small_[maxSmallSize].
660 FBSTRING_ASSERT(s <= maxSmallSize);
661 constexpr auto shift = kIsLittleEndian ? 0 : 2;
662 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
664 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
667 void copySmall(const fbstring_core&);
668 void copyMedium(const fbstring_core&);
669 void copyLarge(const fbstring_core&);
671 void initSmall(const Char* data, size_t size);
672 void initMedium(const Char* data, size_t size);
673 void initLarge(const Char* data, size_t size);
675 void reserveSmall(size_t minCapacity, bool disableSSO);
676 void reserveMedium(size_t minCapacity);
677 void reserveLarge(size_t minCapacity);
679 void shrinkSmall(size_t delta);
680 void shrinkMedium(size_t delta);
681 void shrinkLarge(size_t delta);
683 void unshare(size_t minCapacity = 0);
684 Char* mutableDataLarge();
687 template <class Char>
688 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
689 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
691 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
692 "fbstring layout failure");
694 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
695 "fbstring layout failure");
696 // Just write the whole thing, don't look at details. In
697 // particular we need to copy capacity anyway because we want
698 // to set the size (don't forget that the last character,
699 // which stores a short string's length, is shared with the
700 // ml_.capacity field).
703 category() == Category::isSmall && this->size() == rhs.size());
706 template <class Char>
707 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
708 const fbstring_core& rhs) {
709 // Medium strings are copied eagerly. Don't forget to allocate
710 // one extra Char for the null terminator.
711 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
712 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
713 // Also copies terminator.
714 fbstring_detail::podCopy(
715 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
716 ml_.size_ = rhs.ml_.size_;
717 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
718 FBSTRING_ASSERT(category() == Category::isMedium);
721 template <class Char>
722 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
723 const fbstring_core& rhs) {
724 // Large strings are just refcounted
726 RefCounted::incrementRefs(ml_.data_);
727 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
730 // Small strings are bitblitted
731 template <class Char>
732 inline void fbstring_core<Char>::initSmall(
733 const Char* const data, const size_t size) {
734 // Layout is: Char* data_, size_t size_, size_t capacity_
736 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
737 "fbstring has unexpected size");
739 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
740 // sizeof(size_t) must be a power of 2
742 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
743 "fbstring size assumption violation");
745 // If data is aligned, use fast word-wise copying. Otherwise,
746 // use conservative memcpy.
747 // The word-wise path reads bytes which are outside the range of
748 // the string, and makes ASan unhappy, so we disable it when
749 // compiling with ASan.
750 #ifndef FBSTRING_SANITIZE_ADDRESS
751 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
752 const size_t byteSize = size * sizeof(Char);
753 constexpr size_t wordWidth = sizeof(size_t);
754 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
756 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
758 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
760 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
768 fbstring_detail::podCopy(data, data + size, small_);
774 template <class Char>
775 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
776 const Char* const data, const size_t size) {
777 // Medium strings are allocated normally. Don't forget to
778 // allocate one extra Char for the terminating null.
779 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
780 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
781 if (FBSTRING_LIKELY(size > 0)) {
782 fbstring_detail::podCopy(data, data + size, ml_.data_);
785 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
786 ml_.data_[size] = '\0';
789 template <class Char>
790 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
791 const Char* const data, const size_t size) {
792 // Large strings are allocated differently
793 size_t effectiveCapacity = size;
794 auto const newRC = RefCounted::create(data, &effectiveCapacity);
795 ml_.data_ = newRC->data_;
797 ml_.setCapacity(effectiveCapacity, Category::isLarge);
798 ml_.data_[size] = '\0';
801 template <class Char>
802 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
803 size_t minCapacity) {
804 FBSTRING_ASSERT(category() == Category::isLarge);
805 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
806 auto const newRC = RefCounted::create(&effectiveCapacity);
807 // If this fails, someone placed the wrong capacity in an
809 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
810 // Also copies terminator.
811 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
812 RefCounted::decrementRefs(ml_.data_);
813 ml_.data_ = newRC->data_;
814 ml_.setCapacity(effectiveCapacity, Category::isLarge);
815 // size_ remains unchanged.
818 template <class Char>
819 inline Char* fbstring_core<Char>::mutableDataLarge() {
820 FBSTRING_ASSERT(category() == Category::isLarge);
821 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
827 template <class Char>
828 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
829 size_t minCapacity) {
830 FBSTRING_ASSERT(category() == Category::isLarge);
831 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
832 // We must make it unique regardless; in-place reallocation is
833 // useless if the string is shared. In order to not surprise
834 // people, reserve the new block at current capacity or
835 // more. That way, a string's capacity never shrinks after a
837 unshare(minCapacity);
839 // String is not shared, so let's try to realloc (if needed)
840 if (minCapacity > ml_.capacity()) {
841 // Asking for more memory
842 auto const newRC = RefCounted::reallocate(
843 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
844 ml_.data_ = newRC->data_;
845 ml_.setCapacity(minCapacity, Category::isLarge);
847 FBSTRING_ASSERT(capacity() >= minCapacity);
851 template <class Char>
852 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
853 const size_t minCapacity) {
854 FBSTRING_ASSERT(category() == Category::isMedium);
855 // String is not shared
856 if (minCapacity <= ml_.capacity()) {
857 return; // nothing to do, there's enough room
859 if (minCapacity <= maxMediumSize) {
860 // Keep the string at medium size. Don't forget to allocate
861 // one extra Char for the terminating null.
862 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
863 // Also copies terminator.
864 ml_.data_ = static_cast<Char*>(smartRealloc(
866 (ml_.size_ + 1) * sizeof(Char),
867 (ml_.capacity() + 1) * sizeof(Char),
869 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
871 // Conversion from medium to large string
872 fbstring_core nascent;
873 // Will recurse to another branch of this function
874 nascent.reserve(minCapacity);
875 nascent.ml_.size_ = ml_.size_;
876 // Also copies terminator.
877 fbstring_detail::podCopy(
878 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
880 FBSTRING_ASSERT(capacity() >= minCapacity);
884 template <class Char>
885 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
886 size_t minCapacity, const bool disableSSO) {
887 FBSTRING_ASSERT(category() == Category::isSmall);
888 if (!disableSSO && minCapacity <= maxSmallSize) {
890 // Nothing to do, everything stays put
891 } else if (minCapacity <= maxMediumSize) {
893 // Don't forget to allocate one extra Char for the terminating null
894 auto const allocSizeBytes =
895 goodMallocSize((1 + minCapacity) * sizeof(Char));
896 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
897 auto const size = smallSize();
898 // Also copies terminator.
899 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
902 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
905 auto const newRC = RefCounted::create(&minCapacity);
906 auto const size = smallSize();
907 // Also copies terminator.
908 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
909 ml_.data_ = newRC->data_;
911 ml_.setCapacity(minCapacity, Category::isLarge);
912 FBSTRING_ASSERT(capacity() >= minCapacity);
916 template <class Char>
917 inline Char* fbstring_core<Char>::expandNoinit(
919 bool expGrowth, /* = false */
920 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
921 // Strategy is simple: make room, then change size
922 FBSTRING_ASSERT(capacity() >= size());
924 if (category() == Category::isSmall) {
927 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
932 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
936 if (FBSTRING_UNLIKELY(newSz > capacity())) {
937 // ensures not shared
938 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
941 FBSTRING_ASSERT(capacity() >= newSz);
942 // Category can't be small - we took care of that above
944 category() == Category::isMedium || category() == Category::isLarge);
946 ml_.data_[newSz] = '\0';
947 FBSTRING_ASSERT(size() == newSz);
948 return ml_.data_ + sz;
951 template <class Char>
952 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
953 // Check for underflow
954 FBSTRING_ASSERT(delta <= smallSize());
955 setSmallSize(smallSize() - delta);
958 template <class Char>
959 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
960 // Medium strings and unique large strings need no special
962 FBSTRING_ASSERT(ml_.size_ >= delta);
964 ml_.data_[ml_.size_] = '\0';
967 template <class Char>
968 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
969 FBSTRING_ASSERT(ml_.size_ >= delta);
970 // Shared large string, must make unique. This is because of the
971 // durn terminator must be written, which may trample the shared
974 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
976 // No need to write the terminator.
979 #ifndef _LIBSTDCXX_FBSTRING
981 * Dummy fbstring core that uses an actual std::string. This doesn't
982 * make any sense - it's just for testing purposes.
984 template <class Char>
985 class dummy_fbstring_core {
987 dummy_fbstring_core() {
989 dummy_fbstring_core(const dummy_fbstring_core& another)
990 : backend_(another.backend_) {
992 dummy_fbstring_core(const Char * s, size_t n)
995 void swap(dummy_fbstring_core & rhs) {
996 backend_.swap(rhs.backend_);
998 const Char * data() const {
999 return backend_.data();
1001 Char* mutableData() {
1002 return const_cast<Char*>(backend_.data());
1004 void shrink(size_t delta) {
1005 FBSTRING_ASSERT(delta <= size());
1006 backend_.resize(size() - delta);
1008 Char* expandNoinit(size_t delta) {
1009 auto const sz = size();
1010 backend_.resize(size() + delta);
1011 return backend_.data() + sz;
1013 void push_back(Char c) {
1014 backend_.push_back(c);
1016 size_t size() const {
1017 return backend_.size();
1019 size_t capacity() const {
1020 return backend_.capacity();
1022 bool isShared() const {
1025 void reserve(size_t minCapacity) {
1026 backend_.reserve(minCapacity);
1030 std::basic_string<Char> backend_;
1032 #endif // !_LIBSTDCXX_FBSTRING
1035 * This is the basic_string replacement. For conformity,
1036 * basic_fbstring takes the same template parameters, plus the last
1037 * one which is the core.
1039 #ifdef _LIBSTDCXX_FBSTRING
1040 template <typename E, class T, class A, class Storage>
1042 template <typename E,
1043 class T = std::char_traits<E>,
1044 class A = std::allocator<E>,
1045 class Storage = fbstring_core<E> >
1047 class basic_fbstring {
1048 static void enforce(
1050 void (*throw_exc)(const char*),
1057 bool isSane() const {
1060 empty() == (size() == 0) &&
1061 empty() == (begin() == end()) &&
1062 size() <= max_size() &&
1063 capacity() <= max_size() &&
1064 size() <= capacity() &&
1065 begin()[size()] == '\0';
1069 Invariant& operator=(const Invariant&) = delete;
1070 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1071 FBSTRING_ASSERT(s_.isSane());
1073 ~Invariant() noexcept {
1074 FBSTRING_ASSERT(s_.isSane());
1078 const basic_fbstring& s_;
1083 typedef T traits_type;
1084 typedef typename traits_type::char_type value_type;
1085 typedef A allocator_type;
1086 typedef typename A::size_type size_type;
1087 typedef typename A::difference_type difference_type;
1089 typedef typename A::reference reference;
1090 typedef typename A::const_reference const_reference;
1091 typedef typename A::pointer pointer;
1092 typedef typename A::const_pointer const_pointer;
1094 typedef E* iterator;
1095 typedef const E* const_iterator;
1096 typedef std::reverse_iterator<iterator
1097 #ifdef NO_ITERATOR_TRAITS
1101 typedef std::reverse_iterator<const_iterator
1102 #ifdef NO_ITERATOR_TRAITS
1105 > const_reverse_iterator;
1107 static constexpr size_type npos = size_type(-1);
1108 typedef std::true_type IsRelocatable;
1111 static void procrustes(size_type& n, size_type nmax) {
1117 static size_type traitsLength(const value_type* s);
1120 // C++11 21.4.2 construct/copy/destroy
1122 // Note: while the following two constructors can be (and previously were)
1123 // collapsed into one constructor written this way:
1125 // explicit basic_fbstring(const A& a = A()) noexcept { }
1127 // This can cause Clang (at least version 3.7) to fail with the error:
1128 // "chosen constructor is explicit in copy-initialization ...
1129 // in implicit initialization of field '(x)' with omitted initializer"
1131 // if used in a struct which is default-initialized. Hence the split into
1132 // these two separate constructors.
1134 basic_fbstring() noexcept : basic_fbstring(A()) {
1137 explicit basic_fbstring(const A&) noexcept {
1140 basic_fbstring(const basic_fbstring& str)
1141 : store_(str.store_) {
1145 basic_fbstring(basic_fbstring&& goner) noexcept
1146 : store_(std::move(goner.store_)) {
1149 #ifndef _LIBSTDCXX_FBSTRING
1150 // This is defined for compatibility with std::string
1151 /* implicit */ basic_fbstring(const std::string& str)
1152 : store_(str.data(), str.size()) {
1156 basic_fbstring(const basic_fbstring& str,
1159 const A& /* a */ = A()) {
1160 assign(str, pos, n);
1163 FOLLY_MALLOC_NOINLINE
1164 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1165 : store_(s, traitsLength(s)) {}
1167 FOLLY_MALLOC_NOINLINE
1168 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1172 FOLLY_MALLOC_NOINLINE
1173 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1174 auto const pData = store_.expandNoinit(n);
1175 fbstring_detail::podFill(pData, pData + n, c);
1178 template <class InIt>
1179 FOLLY_MALLOC_NOINLINE basic_fbstring(
1182 typename std::enable_if<
1183 !std::is_same<InIt, value_type*>::value,
1184 const A>::type& /*a*/ = A()) {
1188 // Specialization for const char*, const char*
1189 FOLLY_MALLOC_NOINLINE
1190 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1191 : store_(b, size_type(e - b)) {
1194 // Nonstandard constructor
1195 basic_fbstring(value_type *s, size_type n, size_type c,
1196 AcquireMallocatedString a)
1197 : store_(s, n, c, a) {
1200 // Construction from initialization list
1201 FOLLY_MALLOC_NOINLINE
1202 basic_fbstring(std::initializer_list<value_type> il) {
1203 assign(il.begin(), il.end());
1206 ~basic_fbstring() noexcept {}
1208 basic_fbstring& operator=(const basic_fbstring& lhs);
1211 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1213 #ifndef _LIBSTDCXX_FBSTRING
1214 // Compatibility with std::string
1215 basic_fbstring & operator=(const std::string & rhs) {
1216 return assign(rhs.data(), rhs.size());
1219 // Compatibility with std::string
1220 std::string toStdString() const {
1221 return std::string(data(), size());
1224 // A lot of code in fbcode still uses this method, so keep it here for now.
1225 const basic_fbstring& toStdString() const {
1230 basic_fbstring& operator=(const value_type* s) {
1234 // This actually goes directly against the C++ spec, but the
1235 // value_type overload is dangerous, so we're explicitly deleting
1236 // any overloads of operator= that could implicitly convert to
1238 // Note that we do need to explicitly specify the template types because
1239 // otherwise MSVC 2017 will aggressively pre-resolve value_type to
1240 // traits_type::char_type, which won't compare as equal when determining
1241 // which overload the implementation is referring to.
1242 // Also note that MSVC 2015 Update 3 requires us to explicitly specify the
1243 // namespace in-which to search for basic_fbstring, otherwise it tries to
1244 // look for basic_fbstring::basic_fbstring, which is just plain wrong.
1245 template <typename TP>
1246 typename std::enable_if<
1248 typename std::decay<TP>::type,
1249 typename folly::basic_fbstring<E, T, A, Storage>::value_type>::value,
1250 basic_fbstring<E, T, A, Storage>&>::type
1253 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1254 return assign(il.begin(), il.end());
1257 // C++11 21.4.3 iterators:
1259 return store_.mutableData();
1262 const_iterator begin() const {
1263 return store_.data();
1266 const_iterator cbegin() const {
1271 return store_.mutableData() + store_.size();
1274 const_iterator end() const {
1275 return store_.data() + store_.size();
1278 const_iterator cend() const { return end(); }
1280 reverse_iterator rbegin() {
1281 return reverse_iterator(end());
1284 const_reverse_iterator rbegin() const {
1285 return const_reverse_iterator(end());
1288 const_reverse_iterator crbegin() const { return rbegin(); }
1290 reverse_iterator rend() {
1291 return reverse_iterator(begin());
1294 const_reverse_iterator rend() const {
1295 return const_reverse_iterator(begin());
1298 const_reverse_iterator crend() const { return rend(); }
1301 // C++11 21.4.5, element access:
1302 const value_type& front() const { return *begin(); }
1303 const value_type& back() const {
1304 FBSTRING_ASSERT(!empty());
1305 // Should be begin()[size() - 1], but that branches twice
1306 return *(end() - 1);
1308 value_type& front() { return *begin(); }
1309 value_type& back() {
1310 FBSTRING_ASSERT(!empty());
1311 // Should be begin()[size() - 1], but that branches twice
1312 return *(end() - 1);
1315 FBSTRING_ASSERT(!empty());
1319 // C++11 21.4.4 capacity:
1320 size_type size() const { return store_.size(); }
1322 size_type length() const { return size(); }
1324 size_type max_size() const {
1325 return std::numeric_limits<size_type>::max();
1328 void resize(size_type n, value_type c = value_type());
1330 size_type capacity() const { return store_.capacity(); }
1332 void reserve(size_type res_arg = 0) {
1333 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1334 store_.reserve(res_arg);
1337 void shrink_to_fit() {
1338 // Shrink only if slack memory is sufficiently large
1339 if (capacity() < size() * 3 / 2) {
1342 basic_fbstring(cbegin(), cend()).swap(*this);
1345 void clear() { resize(0); }
1347 bool empty() const { return size() == 0; }
1349 // C++11 21.4.5 element access:
1350 const_reference operator[](size_type pos) const {
1351 return *(begin() + pos);
1354 reference operator[](size_type pos) {
1355 return *(begin() + pos);
1358 const_reference at(size_type n) const {
1359 enforce(n <= size(), std::__throw_out_of_range, "");
1363 reference at(size_type n) {
1364 enforce(n < size(), std::__throw_out_of_range, "");
1368 // C++11 21.4.6 modifiers:
1369 basic_fbstring& operator+=(const basic_fbstring& str) {
1373 basic_fbstring& operator+=(const value_type* s) {
1377 basic_fbstring& operator+=(const value_type c) {
1382 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1387 basic_fbstring& append(const basic_fbstring& str);
1390 append(const basic_fbstring& str, const size_type pos, size_type n);
1392 basic_fbstring& append(const value_type* s, size_type n);
1394 basic_fbstring& append(const value_type* s) {
1395 return append(s, traitsLength(s));
1398 basic_fbstring& append(size_type n, value_type c);
1400 template<class InputIterator>
1401 basic_fbstring& append(InputIterator first, InputIterator last) {
1402 insert(end(), first, last);
1406 basic_fbstring& append(std::initializer_list<value_type> il) {
1407 return append(il.begin(), il.end());
1410 void push_back(const value_type c) { // primitive
1411 store_.push_back(c);
1414 basic_fbstring& assign(const basic_fbstring& str) {
1415 if (&str == this) return *this;
1416 return assign(str.data(), str.size());
1419 basic_fbstring& assign(basic_fbstring&& str) {
1420 return *this = std::move(str);
1424 assign(const basic_fbstring& str, const size_type pos, size_type n);
1426 basic_fbstring& assign(const value_type* s, const size_type n);
1428 basic_fbstring& assign(const value_type* s) {
1429 return assign(s, traitsLength(s));
1432 basic_fbstring& assign(std::initializer_list<value_type> il) {
1433 return assign(il.begin(), il.end());
1436 template <class ItOrLength, class ItOrChar>
1437 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1438 return replace(begin(), end(), first_or_n, last_or_c);
1441 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1442 return insert(pos1, str.data(), str.size());
1445 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1446 size_type pos2, size_type n) {
1447 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1448 procrustes(n, str.length() - pos2);
1449 return insert(pos1, str.data() + pos2, n);
1452 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1453 enforce(pos <= length(), std::__throw_out_of_range, "");
1454 insert(begin() + pos, s, s + n);
1458 basic_fbstring& insert(size_type pos, const value_type* s) {
1459 return insert(pos, s, traitsLength(s));
1462 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1463 enforce(pos <= length(), std::__throw_out_of_range, "");
1464 insert(begin() + pos, n, c);
1468 iterator insert(const_iterator p, const value_type c) {
1469 const size_type pos = p - cbegin();
1471 return begin() + pos;
1474 #ifndef _LIBSTDCXX_FBSTRING
1476 typedef std::basic_istream<value_type, traits_type> istream_type;
1477 istream_type& getlineImpl(istream_type& is, value_type delim);
1480 friend inline istream_type& getline(istream_type& is,
1481 basic_fbstring& str,
1483 return str.getlineImpl(is, delim);
1486 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1487 return getline(is, str, '\n');
1493 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1495 template <class InputIter>
1497 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1499 template <class FwdIterator>
1500 iterator insertImpl(
1504 std::forward_iterator_tag);
1506 template <class InputIterator>
1507 iterator insertImpl(
1511 std::input_iterator_tag);
1514 template <class ItOrLength, class ItOrChar>
1515 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1516 using Sel = std::integral_constant<
1518 std::numeric_limits<ItOrLength>::is_specialized>;
1519 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1522 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1523 return insert(p, il.begin(), il.end());
1526 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1527 Invariant checker(*this);
1529 enforce(pos <= length(), std::__throw_out_of_range, "");
1530 procrustes(n, length() - pos);
1531 std::copy(begin() + pos + n, end(), begin() + pos);
1532 resize(length() - n);
1536 iterator erase(iterator position) {
1537 const size_type pos(position - begin());
1538 enforce(pos <= size(), std::__throw_out_of_range, "");
1540 return begin() + pos;
1543 iterator erase(iterator first, iterator last) {
1544 const size_type pos(first - begin());
1545 erase(pos, last - first);
1546 return begin() + pos;
1549 // Replaces at most n1 chars of *this, starting with pos1 with the
1551 basic_fbstring& replace(size_type pos1, size_type n1,
1552 const basic_fbstring& str) {
1553 return replace(pos1, n1, str.data(), str.size());
1556 // Replaces at most n1 chars of *this, starting with pos1,
1557 // with at most n2 chars of str starting with pos2
1558 basic_fbstring& replace(size_type pos1, size_type n1,
1559 const basic_fbstring& str,
1560 size_type pos2, size_type n2) {
1561 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1562 return replace(pos1, n1, str.data() + pos2,
1563 std::min(n2, str.size() - pos2));
1566 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1567 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1568 return replace(pos, n1, s, traitsLength(s));
1571 // Replaces at most n1 chars of *this, starting with pos, with n2
1574 // consolidated with
1576 // Replaces at most n1 chars of *this, starting with pos, with at
1577 // most n2 chars of str. str must have at least n2 chars.
1578 template <class StrOrLength, class NumOrChar>
1579 basic_fbstring& replace(size_type pos, size_type n1,
1580 StrOrLength s_or_n2, NumOrChar n_or_c) {
1581 Invariant checker(*this);
1583 enforce(pos <= size(), std::__throw_out_of_range, "");
1584 procrustes(n1, length() - pos);
1585 const iterator b = begin() + pos;
1586 return replace(b, b + n1, s_or_n2, n_or_c);
1589 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1590 return replace(i1, i2, str.data(), str.length());
1593 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1594 return replace(i1, i2, s, traitsLength(s));
1598 basic_fbstring& replaceImplDiscr(
1601 const value_type* s,
1603 std::integral_constant<int, 2>);
1605 basic_fbstring& replaceImplDiscr(
1610 std::integral_constant<int, 1>);
1612 template <class InputIter>
1613 basic_fbstring& replaceImplDiscr(
1618 std::integral_constant<int, 0>);
1621 template <class FwdIterator>
1622 bool replaceAliased(iterator /* i1 */,
1624 FwdIterator /* s1 */,
1625 FwdIterator /* s2 */,
1630 template <class FwdIterator>
1631 bool replaceAliased(
1638 template <class FwdIterator>
1644 std::forward_iterator_tag);
1646 template <class InputIterator>
1652 std::input_iterator_tag);
1655 template <class T1, class T2>
1656 basic_fbstring& replace(iterator i1, iterator i2,
1657 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1658 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1659 num2 = std::numeric_limits<T2>::is_specialized;
1661 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1662 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1665 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1666 enforce(pos <= size(), std::__throw_out_of_range, "");
1667 procrustes(n, size() - pos);
1670 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1675 void swap(basic_fbstring& rhs) {
1676 store_.swap(rhs.store_);
1679 const value_type* c_str() const {
1680 return store_.c_str();
1683 const value_type* data() const { return c_str(); }
1685 allocator_type get_allocator() const {
1686 return allocator_type();
1689 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1690 return find(str.data(), pos, str.length());
1693 size_type find(const value_type* needle, size_type pos, size_type nsize)
1696 size_type find(const value_type* s, size_type pos = 0) const {
1697 return find(s, pos, traitsLength(s));
1700 size_type find (value_type c, size_type pos = 0) const {
1701 return find(&c, pos, 1);
1704 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1705 return rfind(str.data(), pos, str.length());
1708 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1710 size_type rfind(const value_type* s, size_type pos = npos) const {
1711 return rfind(s, pos, traitsLength(s));
1714 size_type rfind(value_type c, size_type pos = npos) const {
1715 return rfind(&c, pos, 1);
1718 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1719 return find_first_of(str.data(), pos, str.length());
1722 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1725 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1726 return find_first_of(s, pos, traitsLength(s));
1729 size_type find_first_of(value_type c, size_type pos = 0) const {
1730 return find_first_of(&c, pos, 1);
1733 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1735 return find_last_of(str.data(), pos, str.length());
1738 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1740 size_type find_last_of (const value_type* s,
1741 size_type pos = npos) const {
1742 return find_last_of(s, pos, traitsLength(s));
1745 size_type find_last_of (value_type c, size_type pos = npos) const {
1746 return find_last_of(&c, pos, 1);
1749 size_type find_first_not_of(const basic_fbstring& str,
1750 size_type pos = 0) const {
1751 return find_first_not_of(str.data(), pos, str.size());
1754 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1757 size_type find_first_not_of(const value_type* s,
1758 size_type pos = 0) const {
1759 return find_first_not_of(s, pos, traitsLength(s));
1762 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1763 return find_first_not_of(&c, pos, 1);
1766 size_type find_last_not_of(const basic_fbstring& str,
1767 size_type pos = npos) const {
1768 return find_last_not_of(str.data(), pos, str.length());
1771 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1774 size_type find_last_not_of(const value_type* s,
1775 size_type pos = npos) const {
1776 return find_last_not_of(s, pos, traitsLength(s));
1779 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1780 return find_last_not_of(&c, pos, 1);
1783 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1784 enforce(pos <= size(), std::__throw_out_of_range, "");
1785 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1788 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1789 enforce(pos <= size(), std::__throw_out_of_range, "");
1794 return std::move(*this);
1797 int compare(const basic_fbstring& str) const {
1798 // FIX due to Goncalo N M de Carvalho July 18, 2005
1799 return compare(0, size(), str);
1802 int compare(size_type pos1, size_type n1,
1803 const basic_fbstring& str) const {
1804 return compare(pos1, n1, str.data(), str.size());
1807 int compare(size_type pos1, size_type n1,
1808 const value_type* s) const {
1809 return compare(pos1, n1, s, traitsLength(s));
1812 int compare(size_type pos1, size_type n1,
1813 const value_type* s, size_type n2) const {
1814 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1815 procrustes(n1, size() - pos1);
1816 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1817 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1818 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1821 int compare(size_type pos1, size_type n1,
1822 const basic_fbstring& str,
1823 size_type pos2, size_type n2) const {
1824 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1825 return compare(pos1, n1, str.data() + pos2,
1826 std::min(n2, str.size() - pos2));
1829 // Code from Jean-Francois Bastien (03/26/2007)
1830 int compare(const value_type* s) const {
1831 // Could forward to compare(0, size(), s, traitsLength(s))
1832 // but that does two extra checks
1833 const size_type n1(size()), n2(traitsLength(s));
1834 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1835 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1843 template <typename E, class T, class A, class S>
1844 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1845 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1846 return s ? traits_type::length(s)
1847 : (std::__throw_logic_error(
1848 "basic_fbstring: null pointer initializer not valid"),
1852 template <typename E, class T, class A, class S>
1853 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1854 const basic_fbstring& lhs) {
1855 Invariant checker(*this);
1857 if (FBSTRING_UNLIKELY(&lhs == this)) {
1861 return assign(lhs.data(), lhs.size());
1865 template <typename E, class T, class A, class S>
1866 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1867 basic_fbstring&& goner) noexcept {
1868 if (FBSTRING_UNLIKELY(&goner == this)) {
1869 // Compatibility with std::basic_string<>,
1870 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1873 // No need of this anymore
1874 this->~basic_fbstring();
1875 // Move the goner into this
1876 new (&store_) S(std::move(goner.store_));
1880 template <typename E, class T, class A, class S>
1881 template <typename TP>
1882 inline typename std::enable_if<
1884 typename std::decay<TP>::type,
1885 typename basic_fbstring<E, T, A, S>::value_type>::value,
1886 basic_fbstring<E, T, A, S>&>::type
1887 basic_fbstring<E, T, A, S>::operator=(TP c) {
1888 Invariant checker(*this);
1891 store_.expandNoinit(1);
1892 } else if (store_.isShared()) {
1893 basic_fbstring(1, c).swap(*this);
1896 store_.shrink(size() - 1);
1902 template <typename E, class T, class A, class S>
1903 inline void basic_fbstring<E, T, A, S>::resize(
1904 const size_type n, const value_type c /*= value_type()*/) {
1905 Invariant checker(*this);
1907 auto size = this->size();
1909 store_.shrink(size - n);
1911 auto const delta = n - size;
1912 auto pData = store_.expandNoinit(delta);
1913 fbstring_detail::podFill(pData, pData + delta, c);
1915 FBSTRING_ASSERT(this->size() == n);
1918 template <typename E, class T, class A, class S>
1919 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1920 const basic_fbstring& str) {
1922 auto desiredSize = size() + str.size();
1924 append(str.data(), str.size());
1925 FBSTRING_ASSERT(size() == desiredSize);
1929 template <typename E, class T, class A, class S>
1930 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1931 const basic_fbstring& str, const size_type pos, size_type n) {
1932 const size_type sz = str.size();
1933 enforce(pos <= sz, std::__throw_out_of_range, "");
1934 procrustes(n, sz - pos);
1935 return append(str.data() + pos, n);
1938 template <typename E, class T, class A, class S>
1939 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1940 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1941 Invariant checker(*this);
1943 if (FBSTRING_UNLIKELY(!n)) {
1944 // Unlikely but must be done
1947 auto const oldSize = size();
1948 auto const oldData = data();
1949 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1951 // Check for aliasing (rare). We could use "<=" here but in theory
1952 // those do not work for pointers unless the pointers point to
1953 // elements in the same array. For that reason we use
1954 // std::less_equal, which is guaranteed to offer a total order
1955 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1957 std::less_equal<const value_type*> le;
1958 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1959 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1960 // expandNoinit() could have moved the storage, restore the source.
1961 s = data() + (s - oldData);
1962 fbstring_detail::podMove(s, s + n, pData);
1964 fbstring_detail::podCopy(s, s + n, pData);
1967 FBSTRING_ASSERT(size() == oldSize + n);
1971 template <typename E, class T, class A, class S>
1972 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1973 size_type n, value_type c) {
1974 Invariant checker(*this);
1975 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1976 fbstring_detail::podFill(pData, pData + n, c);
1980 template <typename E, class T, class A, class S>
1981 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1982 const basic_fbstring& str, const size_type pos, size_type n) {
1983 const size_type sz = str.size();
1984 enforce(pos <= sz, std::__throw_out_of_range, "");
1985 procrustes(n, sz - pos);
1986 return assign(str.data() + pos, n);
1989 template <typename E, class T, class A, class S>
1990 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1991 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1992 Invariant checker(*this);
1996 } else if (size() >= n) {
1997 // s can alias this, we need to use podMove.
1998 fbstring_detail::podMove(s, s + n, store_.mutableData());
1999 store_.shrink(size() - n);
2000 FBSTRING_ASSERT(size() == n);
2002 // If n is larger than size(), s cannot alias this string's
2005 // Do not use exponential growth here: assign() should be tight,
2006 // to mirror the behavior of the equivalent constructor.
2007 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
2010 FBSTRING_ASSERT(size() == n);
2014 #ifndef _LIBSTDCXX_FBSTRING
2015 template <typename E, class T, class A, class S>
2016 inline typename basic_fbstring<E, T, A, S>::istream_type&
2017 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
2018 Invariant checker(*this);
2023 size_t avail = capacity() - size;
2024 // fbstring has 1 byte extra capacity for the null terminator,
2025 // and getline null-terminates the read string.
2026 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2027 size += is.gcount();
2029 if (is.bad() || is.eof() || !is.fail()) {
2030 // Done by either failure, end of file, or normal read.
2031 if (!is.bad() && !is.eof()) {
2032 --size; // gcount() also accounts for the delimiter.
2038 FBSTRING_ASSERT(size == this->size());
2039 FBSTRING_ASSERT(size == capacity());
2040 // Start at minimum allocation 63 + terminator = 64.
2041 reserve(std::max<size_t>(63, 3 * size / 2));
2042 // Clear the error so we can continue reading.
2049 template <typename E, class T, class A, class S>
2050 inline typename basic_fbstring<E, T, A, S>::size_type
2051 basic_fbstring<E, T, A, S>::find(
2052 const value_type* needle, const size_type pos, const size_type nsize)
2054 auto const size = this->size();
2055 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2056 // that nsize + pos does not wrap around.
2057 if (nsize + pos > size || nsize + pos < pos) {
2064 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2065 // the last characters first
2066 auto const haystack = data();
2067 auto const nsize_1 = nsize - 1;
2068 auto const lastNeedle = needle[nsize_1];
2070 // Boyer-Moore skip value for the last char in the needle. Zero is
2071 // not a valid value; skip will be computed the first time it's
2075 const E* i = haystack + pos;
2076 auto iEnd = haystack + size - nsize_1;
2079 // Boyer-Moore: match the last element in the needle
2080 while (i[nsize_1] != lastNeedle) {
2086 // Here we know that the last char matches
2087 // Continue in pedestrian mode
2088 for (size_t j = 0;;) {
2089 FBSTRING_ASSERT(j < nsize);
2090 if (i[j] != needle[j]) {
2091 // Not found, we can skip
2092 // Compute the skip value lazily
2095 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2102 // Check if done searching
2105 return i - haystack;
2112 template <typename E, class T, class A, class S>
2113 inline typename basic_fbstring<E, T, A, S>::iterator
2114 basic_fbstring<E, T, A, S>::insertImplDiscr(
2115 const_iterator i, size_type n, value_type c, std::true_type) {
2116 Invariant checker(*this);
2118 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2119 const size_type pos = i - cbegin();
2121 auto oldSize = size();
2122 store_.expandNoinit(n, /* expGrowth = */ true);
2124 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2125 fbstring_detail::podFill(b + pos, b + pos + n, c);
2130 template <typename E, class T, class A, class S>
2131 template <class InputIter>
2132 inline typename basic_fbstring<E, T, A, S>::iterator
2133 basic_fbstring<E, T, A, S>::insertImplDiscr(
2134 const_iterator i, InputIter b, InputIter e, std::false_type) {
2136 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2139 template <typename E, class T, class A, class S>
2140 template <class FwdIterator>
2141 inline typename basic_fbstring<E, T, A, S>::iterator
2142 basic_fbstring<E, T, A, S>::insertImpl(
2146 std::forward_iterator_tag) {
2147 Invariant checker(*this);
2149 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2150 const size_type pos = i - cbegin();
2151 auto n = std::distance(s1, s2);
2152 FBSTRING_ASSERT(n >= 0);
2154 auto oldSize = size();
2155 store_.expandNoinit(n, /* expGrowth = */ true);
2157 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2158 std::copy(s1, s2, b + pos);
2163 template <typename E, class T, class A, class S>
2164 template <class InputIterator>
2165 inline typename basic_fbstring<E, T, A, S>::iterator
2166 basic_fbstring<E, T, A, S>::insertImpl(
2170 std::input_iterator_tag) {
2171 const auto pos = i - cbegin();
2172 basic_fbstring temp(cbegin(), i);
2173 for (; b != e; ++b) {
2176 temp.append(i, cend());
2178 return begin() + pos;
2181 template <typename E, class T, class A, class S>
2182 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2185 const value_type* s,
2187 std::integral_constant<int, 2>) {
2188 FBSTRING_ASSERT(i1 <= i2);
2189 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2190 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2191 return replace(i1, i2, s, s + n);
2194 template <typename E, class T, class A, class S>
2195 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2200 std::integral_constant<int, 1>) {
2201 const size_type n1 = i2 - i1;
2203 std::fill(i1, i1 + n2, c);
2206 std::fill(i1, i2, c);
2207 insert(i2, n2 - n1, c);
2209 FBSTRING_ASSERT(isSane());
2213 template <typename E, class T, class A, class S>
2214 template <class InputIter>
2215 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2220 std::integral_constant<int, 0>) {
2221 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2222 replaceImpl(i1, i2, b, e, Cat());
2226 template <typename E, class T, class A, class S>
2227 template <class FwdIterator>
2228 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2229 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2230 std::less_equal<const value_type*> le{};
2231 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2235 // Aliased replace, copy to new string
2236 basic_fbstring temp;
2237 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2238 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2243 template <typename E, class T, class A, class S>
2244 template <class FwdIterator>
2245 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2250 std::forward_iterator_tag) {
2251 Invariant checker(*this);
2253 // Handle aliased replace
2254 using Sel = std::integral_constant<
2256 std::is_same<FwdIterator, iterator>::value ||
2257 std::is_same<FwdIterator, const_iterator>::value>;
2258 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2262 auto const n1 = i2 - i1;
2263 FBSTRING_ASSERT(n1 >= 0);
2264 auto const n2 = std::distance(s1, s2);
2265 FBSTRING_ASSERT(n2 >= 0);
2269 std::copy(s1, s2, i1);
2273 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2276 FBSTRING_ASSERT(isSane());
2279 template <typename E, class T, class A, class S>
2280 template <class InputIterator>
2281 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2286 std::input_iterator_tag) {
2287 basic_fbstring temp(begin(), i1);
2288 temp.append(b, e).append(i2, end());
2292 template <typename E, class T, class A, class S>
2293 inline typename basic_fbstring<E, T, A, S>::size_type
2294 basic_fbstring<E, T, A, S>::rfind(
2295 const value_type* s, size_type pos, size_type n) const {
2299 pos = std::min(pos, length() - n);
2304 const_iterator i(begin() + pos);
2306 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2316 template <typename E, class T, class A, class S>
2317 inline typename basic_fbstring<E, T, A, S>::size_type
2318 basic_fbstring<E, T, A, S>::find_first_of(
2319 const value_type* s, size_type pos, size_type n) const {
2320 if (pos > length() || n == 0) {
2323 const_iterator i(begin() + pos), finish(end());
2324 for (; i != finish; ++i) {
2325 if (traits_type::find(s, n, *i) != 0) {
2332 template <typename E, class T, class A, class S>
2333 inline typename basic_fbstring<E, T, A, S>::size_type
2334 basic_fbstring<E, T, A, S>::find_last_of(
2335 const value_type* s, size_type pos, size_type n) const {
2336 if (!empty() && n > 0) {
2337 pos = std::min(pos, length() - 1);
2338 const_iterator i(begin() + pos);
2340 if (traits_type::find(s, n, *i) != 0) {
2351 template <typename E, class T, class A, class S>
2352 inline typename basic_fbstring<E, T, A, S>::size_type
2353 basic_fbstring<E, T, A, S>::find_first_not_of(
2354 const value_type* s, size_type pos, size_type n) const {
2355 if (pos < length()) {
2356 const_iterator i(begin() + pos), finish(end());
2357 for (; i != finish; ++i) {
2358 if (traits_type::find(s, n, *i) == 0) {
2366 template <typename E, class T, class A, class S>
2367 inline typename basic_fbstring<E, T, A, S>::size_type
2368 basic_fbstring<E, T, A, S>::find_last_not_of(
2369 const value_type* s, size_type pos, size_type n) const {
2370 if (!this->empty()) {
2371 pos = std::min(pos, size() - 1);
2372 const_iterator i(begin() + pos);
2374 if (traits_type::find(s, n, *i) == 0) {
2385 // non-member functions
2387 template <typename E, class T, class A, class S>
2389 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2390 const basic_fbstring<E, T, A, S>& rhs) {
2392 basic_fbstring<E, T, A, S> result;
2393 result.reserve(lhs.size() + rhs.size());
2394 result.append(lhs).append(rhs);
2395 return std::move(result);
2399 template <typename E, class T, class A, class S>
2401 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2402 const basic_fbstring<E, T, A, S>& rhs) {
2403 return std::move(lhs.append(rhs));
2407 template <typename E, class T, class A, class S>
2409 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2410 basic_fbstring<E, T, A, S>&& rhs) {
2411 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2412 // Good, at least we don't need to reallocate
2413 return std::move(rhs.insert(0, lhs));
2415 // Meh, no go. Forward to operator+(const&, const&).
2416 auto const& rhsC = rhs;
2421 template <typename E, class T, class A, class S>
2423 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2424 basic_fbstring<E, T, A, S>&& rhs) {
2425 return std::move(lhs.append(rhs));
2429 template <typename E, class T, class A, class S>
2431 basic_fbstring<E, T, A, S> operator+(
2433 const basic_fbstring<E, T, A, S>& rhs) {
2435 basic_fbstring<E, T, A, S> result;
2436 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2437 result.reserve(len + rhs.size());
2438 result.append(lhs, len).append(rhs);
2443 template <typename E, class T, class A, class S>
2445 basic_fbstring<E, T, A, S> operator+(
2447 basic_fbstring<E, T, A, S>&& rhs) {
2449 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2450 if (rhs.capacity() >= len + rhs.size()) {
2451 // Good, at least we don't need to reallocate
2452 rhs.insert(rhs.begin(), lhs, lhs + len);
2455 // Meh, no go. Do it by hand since we have len already.
2456 basic_fbstring<E, T, A, S> result;
2457 result.reserve(len + rhs.size());
2458 result.append(lhs, len).append(rhs);
2463 template <typename E, class T, class A, class S>
2465 basic_fbstring<E, T, A, S> operator+(
2467 const basic_fbstring<E, T, A, S>& rhs) {
2469 basic_fbstring<E, T, A, S> result;
2470 result.reserve(1 + rhs.size());
2471 result.push_back(lhs);
2477 template <typename E, class T, class A, class S>
2479 basic_fbstring<E, T, A, S> operator+(
2481 basic_fbstring<E, T, A, S>&& rhs) {
2483 if (rhs.capacity() > rhs.size()) {
2484 // Good, at least we don't need to reallocate
2485 rhs.insert(rhs.begin(), lhs);
2488 // Meh, no go. Forward to operator+(E, const&).
2489 auto const& rhsC = rhs;
2494 template <typename E, class T, class A, class S>
2496 basic_fbstring<E, T, A, S> operator+(
2497 const basic_fbstring<E, T, A, S>& lhs,
2500 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2501 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2503 basic_fbstring<E, T, A, S> result;
2504 const size_type len = traits_type::length(rhs);
2505 result.reserve(lhs.size() + len);
2506 result.append(lhs).append(rhs, len);
2510 // C++11 21.4.8.1/10
2511 template <typename E, class T, class A, class S>
2513 basic_fbstring<E, T, A, S> operator+(
2514 basic_fbstring<E, T, A, S>&& lhs,
2517 return std::move(lhs += rhs);
2520 // C++11 21.4.8.1/11
2521 template <typename E, class T, class A, class S>
2523 basic_fbstring<E, T, A, S> operator+(
2524 const basic_fbstring<E, T, A, S>& lhs,
2527 basic_fbstring<E, T, A, S> result;
2528 result.reserve(lhs.size() + 1);
2530 result.push_back(rhs);
2534 // C++11 21.4.8.1/12
2535 template <typename E, class T, class A, class S>
2537 basic_fbstring<E, T, A, S> operator+(
2538 basic_fbstring<E, T, A, S>&& lhs,
2541 return std::move(lhs += rhs);
2544 template <typename E, class T, class A, class S>
2546 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2547 const basic_fbstring<E, T, A, S>& rhs) {
2548 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2550 template <typename E, class T, class A, class S>
2552 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2553 const basic_fbstring<E, T, A, S>& rhs) {
2554 return rhs == lhs; }
2556 template <typename E, class T, class A, class S>
2558 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2559 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2560 return lhs.compare(rhs) == 0; }
2562 template <typename E, class T, class A, class S>
2564 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2565 const basic_fbstring<E, T, A, S>& rhs) {
2566 return !(lhs == rhs); }
2568 template <typename E, class T, class A, class S>
2570 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2571 const basic_fbstring<E, T, A, S>& rhs) {
2572 return !(lhs == rhs); }
2574 template <typename E, class T, class A, class S>
2576 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2577 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2578 return !(lhs == rhs); }
2580 template <typename E, class T, class A, class S>
2582 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2583 const basic_fbstring<E, T, A, S>& rhs) {
2584 return lhs.compare(rhs) < 0; }
2586 template <typename E, class T, class A, class S>
2588 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2589 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2590 return lhs.compare(rhs) < 0; }
2592 template <typename E, class T, class A, class S>
2594 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2595 const basic_fbstring<E, T, A, S>& rhs) {
2596 return rhs.compare(lhs) > 0; }
2598 template <typename E, class T, class A, class S>
2600 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2601 const basic_fbstring<E, T, A, S>& rhs) {
2604 template <typename E, class T, class A, class S>
2606 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2607 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2610 template <typename E, class T, class A, class S>
2612 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2613 const basic_fbstring<E, T, A, S>& rhs) {
2616 template <typename E, class T, class A, class S>
2618 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2619 const basic_fbstring<E, T, A, S>& rhs) {
2620 return !(rhs < lhs); }
2622 template <typename E, class T, class A, class S>
2624 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2625 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2626 return !(rhs < lhs); }
2628 template <typename E, class T, class A, class S>
2630 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2631 const basic_fbstring<E, T, A, S>& rhs) {
2632 return !(rhs < lhs); }
2634 template <typename E, class T, class A, class S>
2636 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2637 const basic_fbstring<E, T, A, S>& rhs) {
2638 return !(lhs < rhs); }
2640 template <typename E, class T, class A, class S>
2642 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2643 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2644 return !(lhs < rhs); }
2646 template <typename E, class T, class A, class S>
2648 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2649 const basic_fbstring<E, T, A, S>& rhs) {
2650 return !(lhs < rhs);
2654 template <typename E, class T, class A, class S>
2655 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2659 // TODO: make this faster.
2660 template <typename E, class T, class A, class S>
2663 typename basic_fbstring<E, T, A, S>::value_type,
2664 typename basic_fbstring<E, T, A, S>::traits_type>&
2666 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2667 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2668 basic_fbstring<E, T, A, S>& str) {
2669 typedef std::basic_istream<
2670 typename basic_fbstring<E, T, A, S>::value_type,
2671 typename basic_fbstring<E, T, A, S>::traits_type>
2673 typename _istream_type::sentry sentry(is);
2674 size_t extracted = 0;
2675 auto err = _istream_type::goodbit;
2677 auto n = is.width();
2682 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2683 if (got == T::eof()) {
2684 err |= _istream_type::eofbit;
2692 got = is.rdbuf()->snextc();
2696 err |= _istream_type::failbit;
2704 template <typename E, class T, class A, class S>
2706 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2707 typename basic_fbstring<E, T, A, S>::traits_type>&
2709 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2710 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2711 const basic_fbstring<E, T, A, S>& str) {
2713 typedef std::basic_ostream<
2714 typename basic_fbstring<E, T, A, S>::value_type,
2715 typename basic_fbstring<E, T, A, S>::traits_type>
2717 typename _ostream_type::sentry _s(os);
2719 typedef std::ostreambuf_iterator<
2720 typename basic_fbstring<E, T, A, S>::value_type,
2721 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2722 size_t __len = str.size();
2724 (os.flags() & _ostream_type::adjustfield) == _ostream_type::left;
2725 if (__pad_and_output(_Ip(os),
2727 __left ? str.data() + __len : str.data(),
2730 os.fill()).failed()) {
2731 os.setstate(_ostream_type::badbit | _ostream_type::failbit);
2734 #elif defined(_MSC_VER)
2735 typedef decltype(os.precision()) streamsize;
2736 // MSVC doesn't define __ostream_insert
2737 os.write(str.data(), static_cast<streamsize>(str.size()));
2739 std::__ostream_insert(os, str.data(), str.size());
2744 template <typename E1, class T, class A, class S>
2745 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2746 basic_fbstring<E1, T, A, S>::npos;
2748 #ifndef _LIBSTDCXX_FBSTRING
2749 // basic_string compatibility routines
2751 template <typename E, class T, class A, class S, class A2>
2752 inline bool operator==(
2753 const basic_fbstring<E, T, A, S>& lhs,
2754 const std::basic_string<E, T, A2>& rhs) {
2755 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2758 template <typename E, class T, class A, class S, class A2>
2759 inline bool operator==(
2760 const std::basic_string<E, T, A2>& lhs,
2761 const basic_fbstring<E, T, A, S>& rhs) {
2765 template <typename E, class T, class A, class S, class A2>
2766 inline bool operator!=(
2767 const basic_fbstring<E, T, A, S>& lhs,
2768 const std::basic_string<E, T, A2>& rhs) {
2769 return !(lhs == rhs);
2772 template <typename E, class T, class A, class S, class A2>
2773 inline bool operator!=(
2774 const std::basic_string<E, T, A2>& lhs,
2775 const basic_fbstring<E, T, A, S>& rhs) {
2776 return !(lhs == rhs);
2779 template <typename E, class T, class A, class S, class A2>
2780 inline bool operator<(
2781 const basic_fbstring<E, T, A, S>& lhs,
2782 const std::basic_string<E, T, A2>& rhs) {
2783 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0;
2786 template <typename E, class T, class A, class S, class A2>
2787 inline bool operator>(
2788 const basic_fbstring<E, T, A, S>& lhs,
2789 const std::basic_string<E, T, A2>& rhs) {
2790 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) > 0;
2793 template <typename E, class T, class A, class S, class A2>
2794 inline bool operator<(
2795 const std::basic_string<E, T, A2>& lhs,
2796 const basic_fbstring<E, T, A, S>& rhs) {
2800 template <typename E, class T, class A, class S, class A2>
2801 inline bool operator>(
2802 const std::basic_string<E, T, A2>& lhs,
2803 const basic_fbstring<E, T, A, S>& rhs) {
2807 template <typename E, class T, class A, class S, class A2>
2808 inline bool operator<=(
2809 const basic_fbstring<E, T, A, S>& lhs,
2810 const std::basic_string<E, T, A2>& rhs) {
2811 return !(lhs > rhs);
2814 template <typename E, class T, class A, class S, class A2>
2815 inline bool operator>=(
2816 const basic_fbstring<E, T, A, S>& lhs,
2817 const std::basic_string<E, T, A2>& rhs) {
2818 return !(lhs < rhs);
2821 template <typename E, class T, class A, class S, class A2>
2822 inline bool operator<=(
2823 const std::basic_string<E, T, A2>& lhs,
2824 const basic_fbstring<E, T, A, S>& rhs) {
2825 return !(lhs > rhs);
2828 template <typename E, class T, class A, class S, class A2>
2829 inline bool operator>=(
2830 const std::basic_string<E, T, A2>& lhs,
2831 const basic_fbstring<E, T, A, S>& rhs) {
2832 return !(lhs < rhs);
2835 #if !defined(_LIBSTDCXX_FBSTRING)
2836 typedef basic_fbstring<char> fbstring;
2839 // fbstring is relocatable
2840 template <class T, class R, class A, class S>
2841 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2844 _GLIBCXX_END_NAMESPACE_VERSION
2847 } // namespace folly
2849 #ifndef _LIBSTDCXX_FBSTRING
2851 // Hash functions to make fbstring usable with e.g. hash_map
2853 // Handle interaction with different C++ standard libraries, which
2854 // expect these types to be in different namespaces.
2856 #define FOLLY_FBSTRING_HASH1(T) \
2858 struct hash< ::folly::basic_fbstring<T>> { \
2859 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2860 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2864 // The C++11 standard says that these four are defined
2865 #define FOLLY_FBSTRING_HASH \
2866 FOLLY_FBSTRING_HASH1(char) \
2867 FOLLY_FBSTRING_HASH1(char16_t) \
2868 FOLLY_FBSTRING_HASH1(char32_t) \
2869 FOLLY_FBSTRING_HASH1(wchar_t)
2877 #if FOLLY_HAVE_DEPRECATED_ASSOC
2878 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2879 namespace __gnu_cxx {
2883 } // namespace __gnu_cxx
2884 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2885 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2887 #undef FOLLY_FBSTRING_HASH
2888 #undef FOLLY_FBSTRING_HASH1
2890 #endif // _LIBSTDCXX_FBSTRING
2894 #undef FBSTRING_DISABLE_SSO
2895 #undef FBSTRING_SANITIZE_ADDRESS
2897 #undef FBSTRING_LIKELY
2898 #undef FBSTRING_UNLIKELY
2899 #undef FBSTRING_ASSERT