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 // When used in folly, assertions are not disabled.
62 #define FBSTRING_ASSERT(expr) assert(expr)
66 // We defined these here rather than including Likely.h to avoid
67 // redefinition errors when fbstring is imported into libstdc++.
68 #if defined(__GNUC__) && __GNUC__ >= 4
69 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
70 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
72 #define FBSTRING_LIKELY(x) (x)
73 #define FBSTRING_UNLIKELY(x) (x)
77 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
78 FOLLY_GCC_DISABLE_WARNING("-Wshadow")
79 // GCC 4.9 has a false positive in setSmallSize (probably
80 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
81 // compile-time array bound checking.
82 FOLLY_GCC_DISABLE_WARNING("-Warray-bounds")
84 // FBString cannot use throw when replacing std::string, though it may still
87 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
89 #ifdef _LIBSTDCXX_FBSTRING
90 namespace std _GLIBCXX_VISIBILITY(default) {
91 _GLIBCXX_BEGIN_NAMESPACE_VERSION
96 #if defined(__clang__)
97 # if __has_feature(address_sanitizer)
98 # define FBSTRING_SANITIZE_ADDRESS
100 #elif defined (__GNUC__) && \
101 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
103 # define FBSTRING_SANITIZE_ADDRESS
106 // When compiling with ASan, always heap-allocate the string even if
107 // it would fit in-situ, so that ASan can detect access to the string
108 // buffer after it has been invalidated (destroyed, resized, etc.).
109 // Note that this flag doesn't remove support for in-situ strings, as
110 // that would break ABI-compatibility and wouldn't allow linking code
111 // compiled with this flag with code compiled without.
112 #ifdef FBSTRING_SANITIZE_ADDRESS
113 # define FBSTRING_DISABLE_SSO true
115 # define FBSTRING_DISABLE_SSO false
118 namespace fbstring_detail {
120 template <class InIt, class OutIt>
121 inline std::pair<InIt, OutIt> copy_n(
123 typename std::iterator_traits<InIt>::difference_type n,
125 for (; n != 0; --n, ++b, ++d) {
128 return std::make_pair(b, d);
131 template <class Pod, class T>
132 inline void podFill(Pod* b, Pod* e, T c) {
133 FBSTRING_ASSERT(b && e && b <= e);
134 constexpr auto kUseMemset = sizeof(T) == 1;
135 /* static */ if (kUseMemset) {
136 memset(b, c, size_t(e - b));
138 auto const ee = b + ((e - b) & ~7u);
139 for (; b != ee; b += 8) {
150 for (; b != e; ++b) {
157 * Lightly structured memcpy, simplifies copying PODs and introduces
158 * some asserts. Unfortunately using this function may cause
159 * measurable overhead (presumably because it adjusts from a begin/end
160 * convention to a pointer/size convention, so it does some extra
161 * arithmetic even though the caller might have done the inverse
162 * adaptation outside).
165 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
166 FBSTRING_ASSERT(b != nullptr);
167 FBSTRING_ASSERT(e != nullptr);
168 FBSTRING_ASSERT(d != nullptr);
169 FBSTRING_ASSERT(e >= b);
170 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
171 memcpy(d, b, (e - b) * sizeof(Pod));
175 * Lightly structured memmove, simplifies copying PODs and introduces
179 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
180 FBSTRING_ASSERT(e >= b);
181 memmove(d, b, (e - b) * sizeof(*b));
185 #if defined(__GNUC__) // Clang also defines __GNUC__
186 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
187 #elif defined(_MSC_VER)
188 # define FBSTRING_ALWAYS_INLINE __forceinline
190 # define FBSTRING_ALWAYS_INLINE inline
193 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
194 #if defined(__GNUC__) // Clang also defines __GNUC__
195 __builtin_unreachable();
196 #elif defined(_MSC_VER)
199 // Well, it's better than nothing.
204 } // namespace fbstring_detail
207 * Defines a special acquisition method for constructing fbstring
208 * objects. AcquireMallocatedString means that the user passes a
209 * pointer to a malloc-allocated string that the fbstring object will
212 enum class AcquireMallocatedString {};
215 * fbstring_core_model is a mock-up type that defines all required
216 * signatures of a fbstring core. The fbstring class itself uses such
217 * a core object to implement all of the numerous member functions
218 * required by the standard.
220 * If you want to define a new core, copy the definition below and
221 * implement the primitives. Then plug the core into basic_fbstring as
222 * a template argument.
224 template <class Char>
225 class fbstring_core_model {
227 fbstring_core_model();
228 fbstring_core_model(const fbstring_core_model &);
229 ~fbstring_core_model();
230 // Returns a pointer to string's buffer (currently only contiguous
231 // strings are supported). The pointer is guaranteed to be valid
232 // until the next call to a non-const member function.
233 const Char * data() const;
234 // Much like data(), except the string is prepared to support
235 // character-level changes. This call is a signal for
236 // e.g. reference-counted implementation to fork the data. The
237 // pointer is guaranteed to be valid until the next call to a
238 // non-const member function.
240 // Returns a pointer to string's buffer and guarantees that a
241 // readable '\0' lies right after the buffer. The pointer is
242 // guaranteed to be valid until the next call to a non-const member
244 const Char * c_str() const;
245 // Shrinks the string by delta characters. Asserts that delta <=
247 void shrink(size_t delta);
248 // Expands the string by delta characters (i.e. after this call
249 // size() will report the old size() plus delta) but without
250 // initializing the expanded region. The expanded region is
251 // zero-terminated. Returns a pointer to the memory to be
252 // initialized (the beginning of the expanded portion). The caller
253 // is expected to fill the expanded area appropriately.
254 // If expGrowth is true, exponential growth is guaranteed.
255 // It is not guaranteed not to reallocate even if size() + delta <
256 // capacity(), so all references to the buffer are invalidated.
257 Char* expandNoinit(size_t delta, bool expGrowth);
258 // Expands the string by one character and sets the last character
260 void push_back(Char c);
261 // Returns the string's size.
263 // Returns the string's capacity, i.e. maximum size that the string
264 // can grow to without reallocation. Note that for reference counted
265 // strings that's technically a lie - even assigning characters
266 // within the existing size would cause a reallocation.
267 size_t capacity() const;
268 // Returns true if the data underlying the string is actually shared
269 // across multiple strings (in a refcounted fashion).
270 bool isShared() const;
271 // Makes sure that at least minCapacity characters are available for
272 // the string without reallocation. For reference-counted strings,
273 // it should fork the data even if minCapacity < size().
274 void reserve(size_t minCapacity);
277 fbstring_core_model& operator=(const fbstring_core_model &);
282 * This is the core of the string. The code should work on 32- and
283 * 64-bit and both big- and little-endianan architectures with any
286 * The storage is selected as follows (assuming we store one-byte
287 * characters on a 64-bit machine): (a) "small" strings between 0 and
288 * 23 chars are stored in-situ without allocation (the rightmost byte
289 * stores the size); (b) "medium" strings from 24 through 254 chars
290 * are stored in malloc-allocated memory that is copied eagerly; (c)
291 * "large" strings of 255 chars and above are stored in a similar
292 * structure as medium arrays, except that the string is
293 * reference-counted and copied lazily. the reference count is
294 * allocated right before the character array.
296 * The discriminator between these three strategies sits in two
297 * bits of the rightmost char of the storage. If neither is set, then the
298 * string is small (and its length sits in the lower-order bits on
299 * little-endian or the high-order bits on big-endian of that
300 * rightmost character). If the MSb is set, the string is medium width.
301 * If the second MSb is set, then the string is large. On little-endian,
302 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
303 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
304 * and big-endian fbstring_core equivalent with merely different ops used
305 * to extract capacity/category.
307 template <class Char> class fbstring_core {
309 // It's MSVC, so we just have to guess ... and allow an override
311 # ifdef FOLLY_ENDIAN_BE
312 static constexpr auto kIsLittleEndian = false;
314 static constexpr auto kIsLittleEndian = true;
317 static constexpr auto kIsLittleEndian =
318 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
321 fbstring_core() noexcept { reset(); }
323 fbstring_core(const fbstring_core & rhs) {
324 FBSTRING_ASSERT(&rhs != this);
325 switch (rhs.category()) {
326 case Category::isSmall:
329 case Category::isMedium:
332 case Category::isLarge:
336 fbstring_detail::assume_unreachable();
338 FBSTRING_ASSERT(size() == rhs.size());
339 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
342 fbstring_core(fbstring_core&& goner) noexcept {
345 // Clean goner's carcass
349 fbstring_core(const Char *const data,
351 bool disableSSO = FBSTRING_DISABLE_SSO) {
352 if (!disableSSO && size <= maxSmallSize) {
353 initSmall(data, size);
354 } else if (size <= maxMediumSize) {
355 initMedium(data, size);
357 initLarge(data, size);
359 FBSTRING_ASSERT(this->size() == size);
361 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
364 ~fbstring_core() noexcept {
365 if (category() == Category::isSmall) {
368 destroyMediumLarge();
371 // Snatches a previously mallocated string. The parameter "size"
372 // is the size of the string, and the parameter "allocatedSize"
373 // is the size of the mallocated block. The string must be
374 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
376 // So if you want a 2-character string, pass malloc(3) as "data",
377 // pass 2 as "size", and pass 3 as "allocatedSize".
378 fbstring_core(Char * const data,
380 const size_t allocatedSize,
381 AcquireMallocatedString) {
383 FBSTRING_ASSERT(allocatedSize >= size + 1);
384 FBSTRING_ASSERT(data[size] == '\0');
385 // Use the medium string storage
388 // Don't forget about null terminator
389 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
391 // No need for the memory
397 // swap below doesn't test whether &rhs == this (and instead
398 // potentially does extra work) on the premise that the rarity of
399 // that situation actually makes the check more expensive than is
401 void swap(fbstring_core & rhs) {
407 // In C++11 data() and c_str() are 100% equivalent.
408 const Char * data() const {
412 Char* mutableData() {
413 switch (category()) {
414 case Category::isSmall:
416 case Category::isMedium:
418 case Category::isLarge:
419 return mutableDataLarge();
421 fbstring_detail::assume_unreachable();
424 const Char* c_str() const {
425 const Char* ptr = ml_.data_;
426 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
427 ptr = (category() == Category::isSmall) ? small_ : ptr;
431 void shrink(const size_t delta) {
432 if (category() == Category::isSmall) {
434 } else if (category() == Category::isMedium ||
435 RefCounted::refs(ml_.data_) == 1) {
442 FOLLY_MALLOC_NOINLINE
443 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
444 switch (category()) {
445 case Category::isSmall:
446 reserveSmall(minCapacity, disableSSO);
448 case Category::isMedium:
449 reserveMedium(minCapacity);
451 case Category::isLarge:
452 reserveLarge(minCapacity);
455 fbstring_detail::assume_unreachable();
457 FBSTRING_ASSERT(capacity() >= minCapacity);
462 bool expGrowth = false,
463 bool disableSSO = FBSTRING_DISABLE_SSO);
465 void push_back(Char c) {
466 *expandNoinit(1, /* expGrowth = */ true) = c;
469 size_t size() const {
470 size_t ret = ml_.size_;
471 /* static */ if (kIsLittleEndian) {
472 // We can save a couple instructions, because the category is
473 // small iff the last char, as unsigned, is <= maxSmallSize.
474 typedef typename std::make_unsigned<Char>::type UChar;
475 auto maybeSmallSize = size_t(maxSmallSize) -
476 size_t(static_cast<UChar>(small_[maxSmallSize]));
477 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
478 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
480 ret = (category() == Category::isSmall) ? smallSize() : ret;
485 size_t capacity() const {
486 switch (category()) {
487 case Category::isSmall:
489 case Category::isLarge:
490 // For large-sized strings, a multi-referenced chunk has no
491 // available capacity. This is because any attempt to append
492 // data would trigger a new allocation.
493 if (RefCounted::refs(ml_.data_) > 1) {
498 return ml_.capacity();
501 bool isShared() const {
502 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
507 fbstring_core & operator=(const fbstring_core & rhs);
513 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
514 auto const c = category();
515 FBSTRING_ASSERT(c != Category::isSmall);
516 if (c == Category::isMedium) {
519 RefCounted::decrementRefs(ml_.data_);
524 std::atomic<size_t> refCount_;
527 constexpr static size_t getDataOffset() {
528 return offsetof(RefCounted, data_);
531 static RefCounted * fromData(Char * p) {
532 return static_cast<RefCounted*>(static_cast<void*>(
533 static_cast<unsigned char*>(static_cast<void*>(p)) -
537 static size_t refs(Char * p) {
538 return fromData(p)->refCount_.load(std::memory_order_acquire);
541 static void incrementRefs(Char * p) {
542 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
545 static void decrementRefs(Char * p) {
546 auto const dis = fromData(p);
547 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
548 FBSTRING_ASSERT(oldcnt > 0);
554 static RefCounted * create(size_t * size) {
555 const size_t allocSize =
556 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
557 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
558 result->refCount_.store(1, std::memory_order_release);
559 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
563 static RefCounted * create(const Char * data, size_t * size) {
564 const size_t effectiveSize = *size;
565 auto result = create(size);
566 if (FBSTRING_LIKELY(effectiveSize > 0)) {
567 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
572 static RefCounted * reallocate(Char *const data,
573 const size_t currentSize,
574 const size_t currentCapacity,
575 size_t * newCapacity) {
576 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
577 const size_t allocNewCapacity =
578 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
579 auto const dis = fromData(data);
580 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
581 auto result = static_cast<RefCounted*>(smartRealloc(
583 getDataOffset() + (currentSize + 1) * sizeof(Char),
584 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
586 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
587 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
592 typedef uint8_t category_type;
594 enum class Category : category_type {
596 isMedium = kIsLittleEndian ? 0x80 : 0x2,
597 isLarge = kIsLittleEndian ? 0x40 : 0x1,
600 Category category() const {
601 // works for both big-endian and little-endian
602 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
610 size_t capacity() const {
611 return kIsLittleEndian
612 ? capacity_ & capacityExtractMask
616 void setCapacity(size_t cap, Category cat) {
617 capacity_ = kIsLittleEndian
618 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
619 : (cap << 2) | static_cast<size_t>(cat);
624 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
625 Char small_[sizeof(MediumLarge) / sizeof(Char)];
629 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
630 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
631 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
632 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
633 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
634 constexpr static size_t capacityExtractMask = kIsLittleEndian
635 ? ~(size_t(categoryExtractMask) << kCategoryShift)
638 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
639 "Corrupt memory layout for fbstring.");
641 size_t smallSize() const {
642 FBSTRING_ASSERT(category() == Category::isSmall);
643 constexpr auto shift = kIsLittleEndian ? 0 : 2;
644 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
645 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
646 return static_cast<size_t>(maxSmallSize) - smallShifted;
649 void setSmallSize(size_t s) {
650 // Warning: this should work with uninitialized strings too,
651 // so don't assume anything about the previous value of
652 // small_[maxSmallSize].
653 FBSTRING_ASSERT(s <= maxSmallSize);
654 constexpr auto shift = kIsLittleEndian ? 0 : 2;
655 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
657 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
660 void copySmall(const fbstring_core&);
661 void copyMedium(const fbstring_core&);
662 void copyLarge(const fbstring_core&);
664 void initSmall(const Char* data, size_t size);
665 void initMedium(const Char* data, size_t size);
666 void initLarge(const Char* data, size_t size);
668 void reserveSmall(size_t minCapacity, bool disableSSO);
669 void reserveMedium(size_t minCapacity);
670 void reserveLarge(size_t minCapacity);
672 void shrinkSmall(size_t delta);
673 void shrinkMedium(size_t delta);
674 void shrinkLarge(size_t delta);
676 void unshare(size_t minCapacity = 0);
677 Char* mutableDataLarge();
680 template <class Char>
681 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
682 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
684 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
685 "fbstring layout failure");
687 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
688 "fbstring layout failure");
689 // Just write the whole thing, don't look at details. In
690 // particular we need to copy capacity anyway because we want
691 // to set the size (don't forget that the last character,
692 // which stores a short string's length, is shared with the
693 // ml_.capacity field).
696 category() == Category::isSmall && this->size() == rhs.size());
699 template <class Char>
700 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
701 const fbstring_core& rhs) {
702 // Medium strings are copied eagerly. Don't forget to allocate
703 // one extra Char for the null terminator.
704 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
705 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
706 // Also copies terminator.
707 fbstring_detail::podCopy(
708 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
709 ml_.size_ = rhs.ml_.size_;
710 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
711 FBSTRING_ASSERT(category() == Category::isMedium);
714 template <class Char>
715 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
716 const fbstring_core& rhs) {
717 // Large strings are just refcounted
719 RefCounted::incrementRefs(ml_.data_);
720 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
723 // Small strings are bitblitted
724 template <class Char>
725 inline void fbstring_core<Char>::initSmall(
726 const Char* const data, const size_t size) {
727 // Layout is: Char* data_, size_t size_, size_t capacity_
729 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
730 "fbstring has unexpected size");
732 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
733 // sizeof(size_t) must be a power of 2
735 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
736 "fbstring size assumption violation");
738 // If data is aligned, use fast word-wise copying. Otherwise,
739 // use conservative memcpy.
740 // The word-wise path reads bytes which are outside the range of
741 // the string, and makes ASan unhappy, so we disable it when
742 // compiling with ASan.
743 #ifndef FBSTRING_SANITIZE_ADDRESS
744 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
745 const size_t byteSize = size * sizeof(Char);
746 constexpr size_t wordWidth = sizeof(size_t);
747 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
749 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
751 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
753 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
761 fbstring_detail::podCopy(data, data + size, small_);
767 template <class Char>
768 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
769 const Char* const data, const size_t size) {
770 // Medium strings are allocated normally. Don't forget to
771 // allocate one extra Char for the terminating null.
772 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
773 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
774 if (FBSTRING_LIKELY(size > 0)) {
775 fbstring_detail::podCopy(data, data + size, ml_.data_);
778 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
779 ml_.data_[size] = '\0';
782 template <class Char>
783 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
784 const Char* const data, const size_t size) {
785 // Large strings are allocated differently
786 size_t effectiveCapacity = size;
787 auto const newRC = RefCounted::create(data, &effectiveCapacity);
788 ml_.data_ = newRC->data_;
790 ml_.setCapacity(effectiveCapacity, Category::isLarge);
791 ml_.data_[size] = '\0';
794 template <class Char>
795 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
796 size_t minCapacity) {
797 FBSTRING_ASSERT(category() == Category::isLarge);
798 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
799 auto const newRC = RefCounted::create(&effectiveCapacity);
800 // If this fails, someone placed the wrong capacity in an
802 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
803 // Also copies terminator.
804 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
805 RefCounted::decrementRefs(ml_.data_);
806 ml_.data_ = newRC->data_;
807 ml_.setCapacity(effectiveCapacity, Category::isLarge);
808 // size_ remains unchanged.
811 template <class Char>
812 inline Char* fbstring_core<Char>::mutableDataLarge() {
813 FBSTRING_ASSERT(category() == Category::isLarge);
814 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
820 template <class Char>
821 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
822 size_t minCapacity) {
823 FBSTRING_ASSERT(category() == Category::isLarge);
824 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
825 // We must make it unique regardless; in-place reallocation is
826 // useless if the string is shared. In order to not surprise
827 // people, reserve the new block at current capacity or
828 // more. That way, a string's capacity never shrinks after a
830 unshare(minCapacity);
832 // String is not shared, so let's try to realloc (if needed)
833 if (minCapacity > ml_.capacity()) {
834 // Asking for more memory
835 auto const newRC = RefCounted::reallocate(
836 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
837 ml_.data_ = newRC->data_;
838 ml_.setCapacity(minCapacity, Category::isLarge);
840 FBSTRING_ASSERT(capacity() >= minCapacity);
844 template <class Char>
845 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
846 const size_t minCapacity) {
847 FBSTRING_ASSERT(category() == Category::isMedium);
848 // String is not shared
849 if (minCapacity <= ml_.capacity()) {
850 return; // nothing to do, there's enough room
852 if (minCapacity <= maxMediumSize) {
853 // Keep the string at medium size. Don't forget to allocate
854 // one extra Char for the terminating null.
855 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
856 // Also copies terminator.
857 ml_.data_ = static_cast<Char*>(smartRealloc(
859 (ml_.size_ + 1) * sizeof(Char),
860 (ml_.capacity() + 1) * sizeof(Char),
862 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
864 // Conversion from medium to large string
865 fbstring_core nascent;
866 // Will recurse to another branch of this function
867 nascent.reserve(minCapacity);
868 nascent.ml_.size_ = ml_.size_;
869 // Also copies terminator.
870 fbstring_detail::podCopy(
871 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
873 FBSTRING_ASSERT(capacity() >= minCapacity);
877 template <class Char>
878 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
879 size_t minCapacity, const bool disableSSO) {
880 FBSTRING_ASSERT(category() == Category::isSmall);
881 if (!disableSSO && minCapacity <= maxSmallSize) {
883 // Nothing to do, everything stays put
884 } else if (minCapacity <= maxMediumSize) {
886 // Don't forget to allocate one extra Char for the terminating null
887 auto const allocSizeBytes =
888 goodMallocSize((1 + minCapacity) * sizeof(Char));
889 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
890 auto const size = smallSize();
891 // Also copies terminator.
892 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
895 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
898 auto const newRC = RefCounted::create(&minCapacity);
899 auto const size = smallSize();
900 // Also copies terminator.
901 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
902 ml_.data_ = newRC->data_;
904 ml_.setCapacity(minCapacity, Category::isLarge);
905 FBSTRING_ASSERT(capacity() >= minCapacity);
909 template <class Char>
910 inline Char* fbstring_core<Char>::expandNoinit(
912 bool expGrowth, /* = false */
913 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
914 // Strategy is simple: make room, then change size
915 FBSTRING_ASSERT(capacity() >= size());
917 if (category() == Category::isSmall) {
920 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
925 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
929 if (FBSTRING_UNLIKELY(newSz > capacity())) {
930 // ensures not shared
931 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
934 FBSTRING_ASSERT(capacity() >= newSz);
935 // Category can't be small - we took care of that above
937 category() == Category::isMedium || category() == Category::isLarge);
939 ml_.data_[newSz] = '\0';
940 FBSTRING_ASSERT(size() == newSz);
941 return ml_.data_ + sz;
944 template <class Char>
945 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
946 // Check for underflow
947 FBSTRING_ASSERT(delta <= smallSize());
948 setSmallSize(smallSize() - delta);
951 template <class Char>
952 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
953 // Medium strings and unique large strings need no special
955 FBSTRING_ASSERT(ml_.size_ >= delta);
957 ml_.data_[ml_.size_] = '\0';
960 template <class Char>
961 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
962 FBSTRING_ASSERT(ml_.size_ >= delta);
963 // Shared large string, must make unique. This is because of the
964 // durn terminator must be written, which may trample the shared
967 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
969 // No need to write the terminator.
972 #ifndef _LIBSTDCXX_FBSTRING
974 * Dummy fbstring core that uses an actual std::string. This doesn't
975 * make any sense - it's just for testing purposes.
977 template <class Char>
978 class dummy_fbstring_core {
980 dummy_fbstring_core() {
982 dummy_fbstring_core(const dummy_fbstring_core& another)
983 : backend_(another.backend_) {
985 dummy_fbstring_core(const Char * s, size_t n)
988 void swap(dummy_fbstring_core & rhs) {
989 backend_.swap(rhs.backend_);
991 const Char * data() const {
992 return backend_.data();
994 Char* mutableData() {
995 return const_cast<Char*>(backend_.data());
997 void shrink(size_t delta) {
998 FBSTRING_ASSERT(delta <= size());
999 backend_.resize(size() - delta);
1001 Char* expandNoinit(size_t delta) {
1002 auto const sz = size();
1003 backend_.resize(size() + delta);
1004 return backend_.data() + sz;
1006 void push_back(Char c) {
1007 backend_.push_back(c);
1009 size_t size() const {
1010 return backend_.size();
1012 size_t capacity() const {
1013 return backend_.capacity();
1015 bool isShared() const {
1018 void reserve(size_t minCapacity) {
1019 backend_.reserve(minCapacity);
1023 std::basic_string<Char> backend_;
1025 #endif // !_LIBSTDCXX_FBSTRING
1028 * This is the basic_string replacement. For conformity,
1029 * basic_fbstring takes the same template parameters, plus the last
1030 * one which is the core.
1032 #ifdef _LIBSTDCXX_FBSTRING
1033 template <typename E, class T, class A, class Storage>
1035 template <typename E,
1036 class T = std::char_traits<E>,
1037 class A = std::allocator<E>,
1038 class Storage = fbstring_core<E> >
1040 class basic_fbstring {
1041 static void enforce(
1043 void (*throw_exc)(const char*),
1050 bool isSane() const {
1053 empty() == (size() == 0) &&
1054 empty() == (begin() == end()) &&
1055 size() <= max_size() &&
1056 capacity() <= max_size() &&
1057 size() <= capacity() &&
1058 begin()[size()] == '\0';
1062 Invariant& operator=(const Invariant&) = delete;
1063 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1064 FBSTRING_ASSERT(s_.isSane());
1066 ~Invariant() noexcept {
1067 FBSTRING_ASSERT(s_.isSane());
1071 const basic_fbstring& s_;
1076 typedef T traits_type;
1077 typedef typename traits_type::char_type value_type;
1078 typedef A allocator_type;
1079 typedef typename A::size_type size_type;
1080 typedef typename A::difference_type difference_type;
1082 typedef typename A::reference reference;
1083 typedef typename A::const_reference const_reference;
1084 typedef typename A::pointer pointer;
1085 typedef typename A::const_pointer const_pointer;
1087 typedef E* iterator;
1088 typedef const E* const_iterator;
1089 typedef std::reverse_iterator<iterator
1090 #ifdef NO_ITERATOR_TRAITS
1094 typedef std::reverse_iterator<const_iterator
1095 #ifdef NO_ITERATOR_TRAITS
1098 > const_reverse_iterator;
1100 static constexpr size_type npos = size_type(-1);
1101 typedef std::true_type IsRelocatable;
1104 static void procrustes(size_type& n, size_type nmax) {
1110 static size_type traitsLength(const value_type* s);
1113 // C++11 21.4.2 construct/copy/destroy
1115 // Note: while the following two constructors can be (and previously were)
1116 // collapsed into one constructor written this way:
1118 // explicit basic_fbstring(const A& a = A()) noexcept { }
1120 // This can cause Clang (at least version 3.7) to fail with the error:
1121 // "chosen constructor is explicit in copy-initialization ...
1122 // in implicit initialization of field '(x)' with omitted initializer"
1124 // if used in a struct which is default-initialized. Hence the split into
1125 // these two separate constructors.
1127 basic_fbstring() noexcept : basic_fbstring(A()) {
1130 explicit basic_fbstring(const A&) noexcept {
1133 basic_fbstring(const basic_fbstring& str)
1134 : store_(str.store_) {
1138 basic_fbstring(basic_fbstring&& goner) noexcept
1139 : store_(std::move(goner.store_)) {
1142 #ifndef _LIBSTDCXX_FBSTRING
1143 // This is defined for compatibility with std::string
1144 /* implicit */ basic_fbstring(const std::string& str)
1145 : store_(str.data(), str.size()) {
1149 basic_fbstring(const basic_fbstring& str,
1152 const A& /* a */ = A()) {
1153 assign(str, pos, n);
1156 FOLLY_MALLOC_NOINLINE
1157 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1158 : store_(s, traitsLength(s)) {}
1160 FOLLY_MALLOC_NOINLINE
1161 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1165 FOLLY_MALLOC_NOINLINE
1166 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1167 auto const pData = store_.expandNoinit(n);
1168 fbstring_detail::podFill(pData, pData + n, c);
1171 template <class InIt>
1172 FOLLY_MALLOC_NOINLINE basic_fbstring(
1175 typename std::enable_if<
1176 !std::is_same<InIt, value_type*>::value,
1177 const A>::type& /*a*/ = A()) {
1181 // Specialization for const char*, const char*
1182 FOLLY_MALLOC_NOINLINE
1183 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1184 : store_(b, size_type(e - b)) {
1187 // Nonstandard constructor
1188 basic_fbstring(value_type *s, size_type n, size_type c,
1189 AcquireMallocatedString a)
1190 : store_(s, n, c, a) {
1193 // Construction from initialization list
1194 FOLLY_MALLOC_NOINLINE
1195 basic_fbstring(std::initializer_list<value_type> il) {
1196 assign(il.begin(), il.end());
1199 ~basic_fbstring() noexcept {}
1201 basic_fbstring& operator=(const basic_fbstring& lhs);
1204 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1206 #ifndef _LIBSTDCXX_FBSTRING
1207 // Compatibility with std::string
1208 basic_fbstring & operator=(const std::string & rhs) {
1209 return assign(rhs.data(), rhs.size());
1212 // Compatibility with std::string
1213 std::string toStdString() const {
1214 return std::string(data(), size());
1217 // A lot of code in fbcode still uses this method, so keep it here for now.
1218 const basic_fbstring& toStdString() const {
1223 basic_fbstring& operator=(const value_type* s) {
1227 // This actually goes directly against the C++ spec, but the
1228 // value_type overload is dangerous, so we're explicitly deleting
1229 // any overloads of operator= that could implicitly convert to
1231 // Note that we do need to explicitly specify the template types because
1232 // otherwise MSVC 2017 will aggressively pre-resolve value_type to
1233 // traits_type::char_type, which won't compare as equal when determining
1234 // which overload the implementation is referring to.
1235 // Also note that MSVC 2015 Update 3 requires us to explicitly specify the
1236 // namespace in-which to search for basic_fbstring, otherwise it tries to
1237 // look for basic_fbstring::basic_fbstring, which is just plain wrong.
1238 template <typename TP>
1239 typename std::enable_if<
1241 typename std::decay<TP>::type,
1242 typename folly::basic_fbstring<E, T, A, Storage>::value_type>::value,
1243 basic_fbstring<E, T, A, Storage>&>::type
1246 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1247 return assign(il.begin(), il.end());
1250 // C++11 21.4.3 iterators:
1252 return store_.mutableData();
1255 const_iterator begin() const {
1256 return store_.data();
1259 const_iterator cbegin() const {
1264 return store_.mutableData() + store_.size();
1267 const_iterator end() const {
1268 return store_.data() + store_.size();
1271 const_iterator cend() const { return end(); }
1273 reverse_iterator rbegin() {
1274 return reverse_iterator(end());
1277 const_reverse_iterator rbegin() const {
1278 return const_reverse_iterator(end());
1281 const_reverse_iterator crbegin() const { return rbegin(); }
1283 reverse_iterator rend() {
1284 return reverse_iterator(begin());
1287 const_reverse_iterator rend() const {
1288 return const_reverse_iterator(begin());
1291 const_reverse_iterator crend() const { return rend(); }
1294 // C++11 21.4.5, element access:
1295 const value_type& front() const { return *begin(); }
1296 const value_type& back() const {
1297 FBSTRING_ASSERT(!empty());
1298 // Should be begin()[size() - 1], but that branches twice
1299 return *(end() - 1);
1301 value_type& front() { return *begin(); }
1302 value_type& back() {
1303 FBSTRING_ASSERT(!empty());
1304 // Should be begin()[size() - 1], but that branches twice
1305 return *(end() - 1);
1308 FBSTRING_ASSERT(!empty());
1312 // C++11 21.4.4 capacity:
1313 size_type size() const { return store_.size(); }
1315 size_type length() const { return size(); }
1317 size_type max_size() const {
1318 return std::numeric_limits<size_type>::max();
1321 void resize(size_type n, value_type c = value_type());
1323 size_type capacity() const { return store_.capacity(); }
1325 void reserve(size_type res_arg = 0) {
1326 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1327 store_.reserve(res_arg);
1330 void shrink_to_fit() {
1331 // Shrink only if slack memory is sufficiently large
1332 if (capacity() < size() * 3 / 2) {
1335 basic_fbstring(cbegin(), cend()).swap(*this);
1338 void clear() { resize(0); }
1340 bool empty() const { return size() == 0; }
1342 // C++11 21.4.5 element access:
1343 const_reference operator[](size_type pos) const {
1344 return *(begin() + pos);
1347 reference operator[](size_type pos) {
1348 return *(begin() + pos);
1351 const_reference at(size_type n) const {
1352 enforce(n <= size(), std::__throw_out_of_range, "");
1356 reference at(size_type n) {
1357 enforce(n < size(), std::__throw_out_of_range, "");
1361 // C++11 21.4.6 modifiers:
1362 basic_fbstring& operator+=(const basic_fbstring& str) {
1366 basic_fbstring& operator+=(const value_type* s) {
1370 basic_fbstring& operator+=(const value_type c) {
1375 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1380 basic_fbstring& append(const basic_fbstring& str);
1383 append(const basic_fbstring& str, const size_type pos, size_type n);
1385 basic_fbstring& append(const value_type* s, size_type n);
1387 basic_fbstring& append(const value_type* s) {
1388 return append(s, traitsLength(s));
1391 basic_fbstring& append(size_type n, value_type c);
1393 template<class InputIterator>
1394 basic_fbstring& append(InputIterator first, InputIterator last) {
1395 insert(end(), first, last);
1399 basic_fbstring& append(std::initializer_list<value_type> il) {
1400 return append(il.begin(), il.end());
1403 void push_back(const value_type c) { // primitive
1404 store_.push_back(c);
1407 basic_fbstring& assign(const basic_fbstring& str) {
1408 if (&str == this) return *this;
1409 return assign(str.data(), str.size());
1412 basic_fbstring& assign(basic_fbstring&& str) {
1413 return *this = std::move(str);
1417 assign(const basic_fbstring& str, const size_type pos, size_type n);
1419 basic_fbstring& assign(const value_type* s, const size_type n);
1421 basic_fbstring& assign(const value_type* s) {
1422 return assign(s, traitsLength(s));
1425 basic_fbstring& assign(std::initializer_list<value_type> il) {
1426 return assign(il.begin(), il.end());
1429 template <class ItOrLength, class ItOrChar>
1430 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1431 return replace(begin(), end(), first_or_n, last_or_c);
1434 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1435 return insert(pos1, str.data(), str.size());
1438 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1439 size_type pos2, size_type n) {
1440 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1441 procrustes(n, str.length() - pos2);
1442 return insert(pos1, str.data() + pos2, n);
1445 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1446 enforce(pos <= length(), std::__throw_out_of_range, "");
1447 insert(begin() + pos, s, s + n);
1451 basic_fbstring& insert(size_type pos, const value_type* s) {
1452 return insert(pos, s, traitsLength(s));
1455 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1456 enforce(pos <= length(), std::__throw_out_of_range, "");
1457 insert(begin() + pos, n, c);
1461 iterator insert(const_iterator p, const value_type c) {
1462 const size_type pos = p - cbegin();
1464 return begin() + pos;
1467 #ifndef _LIBSTDCXX_FBSTRING
1469 typedef std::basic_istream<value_type, traits_type> istream_type;
1470 istream_type& getlineImpl(istream_type& is, value_type delim);
1473 friend inline istream_type& getline(istream_type& is,
1474 basic_fbstring& str,
1476 return str.getlineImpl(is, delim);
1479 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1480 return getline(is, str, '\n');
1486 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1488 template <class InputIter>
1490 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1492 template <class FwdIterator>
1493 iterator insertImpl(
1497 std::forward_iterator_tag);
1499 template <class InputIterator>
1500 iterator insertImpl(
1504 std::input_iterator_tag);
1507 template <class ItOrLength, class ItOrChar>
1508 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1509 using Sel = std::integral_constant<
1511 std::numeric_limits<ItOrLength>::is_specialized>;
1512 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1515 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1516 return insert(p, il.begin(), il.end());
1519 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1520 Invariant checker(*this);
1522 enforce(pos <= length(), std::__throw_out_of_range, "");
1523 procrustes(n, length() - pos);
1524 std::copy(begin() + pos + n, end(), begin() + pos);
1525 resize(length() - n);
1529 iterator erase(iterator position) {
1530 const size_type pos(position - begin());
1531 enforce(pos <= size(), std::__throw_out_of_range, "");
1533 return begin() + pos;
1536 iterator erase(iterator first, iterator last) {
1537 const size_type pos(first - begin());
1538 erase(pos, last - first);
1539 return begin() + pos;
1542 // Replaces at most n1 chars of *this, starting with pos1 with the
1544 basic_fbstring& replace(size_type pos1, size_type n1,
1545 const basic_fbstring& str) {
1546 return replace(pos1, n1, str.data(), str.size());
1549 // Replaces at most n1 chars of *this, starting with pos1,
1550 // with at most n2 chars of str starting with pos2
1551 basic_fbstring& replace(size_type pos1, size_type n1,
1552 const basic_fbstring& str,
1553 size_type pos2, size_type n2) {
1554 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1555 return replace(pos1, n1, str.data() + pos2,
1556 std::min(n2, str.size() - pos2));
1559 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1560 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1561 return replace(pos, n1, s, traitsLength(s));
1564 // Replaces at most n1 chars of *this, starting with pos, with n2
1567 // consolidated with
1569 // Replaces at most n1 chars of *this, starting with pos, with at
1570 // most n2 chars of str. str must have at least n2 chars.
1571 template <class StrOrLength, class NumOrChar>
1572 basic_fbstring& replace(size_type pos, size_type n1,
1573 StrOrLength s_or_n2, NumOrChar n_or_c) {
1574 Invariant checker(*this);
1576 enforce(pos <= size(), std::__throw_out_of_range, "");
1577 procrustes(n1, length() - pos);
1578 const iterator b = begin() + pos;
1579 return replace(b, b + n1, s_or_n2, n_or_c);
1582 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1583 return replace(i1, i2, str.data(), str.length());
1586 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1587 return replace(i1, i2, s, traitsLength(s));
1591 basic_fbstring& replaceImplDiscr(
1594 const value_type* s,
1596 std::integral_constant<int, 2>);
1598 basic_fbstring& replaceImplDiscr(
1603 std::integral_constant<int, 1>);
1605 template <class InputIter>
1606 basic_fbstring& replaceImplDiscr(
1611 std::integral_constant<int, 0>);
1614 template <class FwdIterator>
1615 bool replaceAliased(iterator /* i1 */,
1617 FwdIterator /* s1 */,
1618 FwdIterator /* s2 */,
1623 template <class FwdIterator>
1624 bool replaceAliased(
1631 template <class FwdIterator>
1637 std::forward_iterator_tag);
1639 template <class InputIterator>
1645 std::input_iterator_tag);
1648 template <class T1, class T2>
1649 basic_fbstring& replace(iterator i1, iterator i2,
1650 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1651 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1652 num2 = std::numeric_limits<T2>::is_specialized;
1654 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1655 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1658 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1659 enforce(pos <= size(), std::__throw_out_of_range, "");
1660 procrustes(n, size() - pos);
1663 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1668 void swap(basic_fbstring& rhs) {
1669 store_.swap(rhs.store_);
1672 const value_type* c_str() const {
1673 return store_.c_str();
1676 const value_type* data() const { return c_str(); }
1678 allocator_type get_allocator() const {
1679 return allocator_type();
1682 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1683 return find(str.data(), pos, str.length());
1686 size_type find(const value_type* needle, size_type pos, size_type nsize)
1689 size_type find(const value_type* s, size_type pos = 0) const {
1690 return find(s, pos, traitsLength(s));
1693 size_type find (value_type c, size_type pos = 0) const {
1694 return find(&c, pos, 1);
1697 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1698 return rfind(str.data(), pos, str.length());
1701 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1703 size_type rfind(const value_type* s, size_type pos = npos) const {
1704 return rfind(s, pos, traitsLength(s));
1707 size_type rfind(value_type c, size_type pos = npos) const {
1708 return rfind(&c, pos, 1);
1711 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1712 return find_first_of(str.data(), pos, str.length());
1715 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1718 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1719 return find_first_of(s, pos, traitsLength(s));
1722 size_type find_first_of(value_type c, size_type pos = 0) const {
1723 return find_first_of(&c, pos, 1);
1726 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1728 return find_last_of(str.data(), pos, str.length());
1731 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1733 size_type find_last_of (const value_type* s,
1734 size_type pos = npos) const {
1735 return find_last_of(s, pos, traitsLength(s));
1738 size_type find_last_of (value_type c, size_type pos = npos) const {
1739 return find_last_of(&c, pos, 1);
1742 size_type find_first_not_of(const basic_fbstring& str,
1743 size_type pos = 0) const {
1744 return find_first_not_of(str.data(), pos, str.size());
1747 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1750 size_type find_first_not_of(const value_type* s,
1751 size_type pos = 0) const {
1752 return find_first_not_of(s, pos, traitsLength(s));
1755 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1756 return find_first_not_of(&c, pos, 1);
1759 size_type find_last_not_of(const basic_fbstring& str,
1760 size_type pos = npos) const {
1761 return find_last_not_of(str.data(), pos, str.length());
1764 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1767 size_type find_last_not_of(const value_type* s,
1768 size_type pos = npos) const {
1769 return find_last_not_of(s, pos, traitsLength(s));
1772 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1773 return find_last_not_of(&c, pos, 1);
1776 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1777 enforce(pos <= size(), std::__throw_out_of_range, "");
1778 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1781 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1782 enforce(pos <= size(), std::__throw_out_of_range, "");
1787 return std::move(*this);
1790 int compare(const basic_fbstring& str) const {
1791 // FIX due to Goncalo N M de Carvalho July 18, 2005
1792 return compare(0, size(), str);
1795 int compare(size_type pos1, size_type n1,
1796 const basic_fbstring& str) const {
1797 return compare(pos1, n1, str.data(), str.size());
1800 int compare(size_type pos1, size_type n1,
1801 const value_type* s) const {
1802 return compare(pos1, n1, s, traitsLength(s));
1805 int compare(size_type pos1, size_type n1,
1806 const value_type* s, size_type n2) const {
1807 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1808 procrustes(n1, size() - pos1);
1809 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1810 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1811 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1814 int compare(size_type pos1, size_type n1,
1815 const basic_fbstring& str,
1816 size_type pos2, size_type n2) const {
1817 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1818 return compare(pos1, n1, str.data() + pos2,
1819 std::min(n2, str.size() - pos2));
1822 // Code from Jean-Francois Bastien (03/26/2007)
1823 int compare(const value_type* s) const {
1824 // Could forward to compare(0, size(), s, traitsLength(s))
1825 // but that does two extra checks
1826 const size_type n1(size()), n2(traitsLength(s));
1827 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1828 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1836 template <typename E, class T, class A, class S>
1837 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1838 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1839 return s ? traits_type::length(s)
1840 : (std::__throw_logic_error(
1841 "basic_fbstring: null pointer initializer not valid"),
1845 template <typename E, class T, class A, class S>
1846 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1847 const basic_fbstring& lhs) {
1848 Invariant checker(*this);
1850 if (FBSTRING_UNLIKELY(&lhs == this)) {
1854 return assign(lhs.data(), lhs.size());
1858 template <typename E, class T, class A, class S>
1859 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1860 basic_fbstring&& goner) noexcept {
1861 if (FBSTRING_UNLIKELY(&goner == this)) {
1862 // Compatibility with std::basic_string<>,
1863 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1866 // No need of this anymore
1867 this->~basic_fbstring();
1868 // Move the goner into this
1869 new (&store_) S(std::move(goner.store_));
1873 template <typename E, class T, class A, class S>
1874 template <typename TP>
1875 inline typename std::enable_if<
1877 typename std::decay<TP>::type,
1878 typename basic_fbstring<E, T, A, S>::value_type>::value,
1879 basic_fbstring<E, T, A, S>&>::type
1880 basic_fbstring<E, T, A, S>::operator=(TP c) {
1881 Invariant checker(*this);
1884 store_.expandNoinit(1);
1885 } else if (store_.isShared()) {
1886 basic_fbstring(1, c).swap(*this);
1889 store_.shrink(size() - 1);
1895 template <typename E, class T, class A, class S>
1896 inline void basic_fbstring<E, T, A, S>::resize(
1897 const size_type n, const value_type c /*= value_type()*/) {
1898 Invariant checker(*this);
1900 auto size = this->size();
1902 store_.shrink(size - n);
1904 auto const delta = n - size;
1905 auto pData = store_.expandNoinit(delta);
1906 fbstring_detail::podFill(pData, pData + delta, c);
1908 FBSTRING_ASSERT(this->size() == n);
1911 template <typename E, class T, class A, class S>
1912 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1913 const basic_fbstring& str) {
1915 auto desiredSize = size() + str.size();
1917 append(str.data(), str.size());
1918 FBSTRING_ASSERT(size() == desiredSize);
1922 template <typename E, class T, class A, class S>
1923 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1924 const basic_fbstring& str, const size_type pos, size_type n) {
1925 const size_type sz = str.size();
1926 enforce(pos <= sz, std::__throw_out_of_range, "");
1927 procrustes(n, sz - pos);
1928 return append(str.data() + pos, n);
1931 template <typename E, class T, class A, class S>
1932 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1933 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1934 Invariant checker(*this);
1936 if (FBSTRING_UNLIKELY(!n)) {
1937 // Unlikely but must be done
1940 auto const oldSize = size();
1941 auto const oldData = data();
1942 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1944 // Check for aliasing (rare). We could use "<=" here but in theory
1945 // those do not work for pointers unless the pointers point to
1946 // elements in the same array. For that reason we use
1947 // std::less_equal, which is guaranteed to offer a total order
1948 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1950 std::less_equal<const value_type*> le;
1951 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1952 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1953 // expandNoinit() could have moved the storage, restore the source.
1954 s = data() + (s - oldData);
1955 fbstring_detail::podMove(s, s + n, pData);
1957 fbstring_detail::podCopy(s, s + n, pData);
1960 FBSTRING_ASSERT(size() == oldSize + n);
1964 template <typename E, class T, class A, class S>
1965 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1966 size_type n, value_type c) {
1967 Invariant checker(*this);
1968 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1969 fbstring_detail::podFill(pData, pData + n, c);
1973 template <typename E, class T, class A, class S>
1974 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1975 const basic_fbstring& str, const size_type pos, size_type n) {
1976 const size_type sz = str.size();
1977 enforce(pos <= sz, std::__throw_out_of_range, "");
1978 procrustes(n, sz - pos);
1979 return assign(str.data() + pos, n);
1982 template <typename E, class T, class A, class S>
1983 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1984 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1985 Invariant checker(*this);
1989 } else if (size() >= n) {
1990 // s can alias this, we need to use podMove.
1991 fbstring_detail::podMove(s, s + n, store_.mutableData());
1992 store_.shrink(size() - n);
1993 FBSTRING_ASSERT(size() == n);
1995 // If n is larger than size(), s cannot alias this string's
1998 // Do not use exponential growth here: assign() should be tight,
1999 // to mirror the behavior of the equivalent constructor.
2000 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
2003 FBSTRING_ASSERT(size() == n);
2007 #ifndef _LIBSTDCXX_FBSTRING
2008 template <typename E, class T, class A, class S>
2009 inline typename basic_fbstring<E, T, A, S>::istream_type&
2010 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
2011 Invariant checker(*this);
2016 size_t avail = capacity() - size;
2017 // fbstring has 1 byte extra capacity for the null terminator,
2018 // and getline null-terminates the read string.
2019 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2020 size += is.gcount();
2022 if (is.bad() || is.eof() || !is.fail()) {
2023 // Done by either failure, end of file, or normal read.
2024 if (!is.bad() && !is.eof()) {
2025 --size; // gcount() also accounts for the delimiter.
2031 FBSTRING_ASSERT(size == this->size());
2032 FBSTRING_ASSERT(size == capacity());
2033 // Start at minimum allocation 63 + terminator = 64.
2034 reserve(std::max<size_t>(63, 3 * size / 2));
2035 // Clear the error so we can continue reading.
2042 template <typename E, class T, class A, class S>
2043 inline typename basic_fbstring<E, T, A, S>::size_type
2044 basic_fbstring<E, T, A, S>::find(
2045 const value_type* needle, const size_type pos, const size_type nsize)
2047 auto const size = this->size();
2048 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2049 // that nsize + pos does not wrap around.
2050 if (nsize + pos > size || nsize + pos < pos) {
2057 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2058 // the last characters first
2059 auto const haystack = data();
2060 auto const nsize_1 = nsize - 1;
2061 auto const lastNeedle = needle[nsize_1];
2063 // Boyer-Moore skip value for the last char in the needle. Zero is
2064 // not a valid value; skip will be computed the first time it's
2068 const E* i = haystack + pos;
2069 auto iEnd = haystack + size - nsize_1;
2072 // Boyer-Moore: match the last element in the needle
2073 while (i[nsize_1] != lastNeedle) {
2079 // Here we know that the last char matches
2080 // Continue in pedestrian mode
2081 for (size_t j = 0;;) {
2082 FBSTRING_ASSERT(j < nsize);
2083 if (i[j] != needle[j]) {
2084 // Not found, we can skip
2085 // Compute the skip value lazily
2088 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2095 // Check if done searching
2098 return i - haystack;
2105 template <typename E, class T, class A, class S>
2106 inline typename basic_fbstring<E, T, A, S>::iterator
2107 basic_fbstring<E, T, A, S>::insertImplDiscr(
2108 const_iterator i, size_type n, value_type c, std::true_type) {
2109 Invariant checker(*this);
2111 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2112 const size_type pos = i - cbegin();
2114 auto oldSize = size();
2115 store_.expandNoinit(n, /* expGrowth = */ true);
2117 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2118 fbstring_detail::podFill(b + pos, b + pos + n, c);
2123 template <typename E, class T, class A, class S>
2124 template <class InputIter>
2125 inline typename basic_fbstring<E, T, A, S>::iterator
2126 basic_fbstring<E, T, A, S>::insertImplDiscr(
2127 const_iterator i, InputIter b, InputIter e, std::false_type) {
2129 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2132 template <typename E, class T, class A, class S>
2133 template <class FwdIterator>
2134 inline typename basic_fbstring<E, T, A, S>::iterator
2135 basic_fbstring<E, T, A, S>::insertImpl(
2139 std::forward_iterator_tag) {
2140 Invariant checker(*this);
2142 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2143 const size_type pos = i - cbegin();
2144 auto n = std::distance(s1, s2);
2145 FBSTRING_ASSERT(n >= 0);
2147 auto oldSize = size();
2148 store_.expandNoinit(n, /* expGrowth = */ true);
2150 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2151 std::copy(s1, s2, b + pos);
2156 template <typename E, class T, class A, class S>
2157 template <class InputIterator>
2158 inline typename basic_fbstring<E, T, A, S>::iterator
2159 basic_fbstring<E, T, A, S>::insertImpl(
2163 std::input_iterator_tag) {
2164 const auto pos = i - cbegin();
2165 basic_fbstring temp(cbegin(), i);
2166 for (; b != e; ++b) {
2169 temp.append(i, cend());
2171 return begin() + pos;
2174 template <typename E, class T, class A, class S>
2175 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2178 const value_type* s,
2180 std::integral_constant<int, 2>) {
2181 FBSTRING_ASSERT(i1 <= i2);
2182 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2183 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2184 return replace(i1, i2, s, s + n);
2187 template <typename E, class T, class A, class S>
2188 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2193 std::integral_constant<int, 1>) {
2194 const size_type n1 = i2 - i1;
2196 std::fill(i1, i1 + n2, c);
2199 std::fill(i1, i2, c);
2200 insert(i2, n2 - n1, c);
2202 FBSTRING_ASSERT(isSane());
2206 template <typename E, class T, class A, class S>
2207 template <class InputIter>
2208 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2213 std::integral_constant<int, 0>) {
2214 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2215 replaceImpl(i1, i2, b, e, Cat());
2219 template <typename E, class T, class A, class S>
2220 template <class FwdIterator>
2221 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2222 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2223 std::less_equal<const value_type*> le{};
2224 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2228 // Aliased replace, copy to new string
2229 basic_fbstring temp;
2230 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2231 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2236 template <typename E, class T, class A, class S>
2237 template <class FwdIterator>
2238 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2243 std::forward_iterator_tag) {
2244 Invariant checker(*this);
2246 // Handle aliased replace
2247 using Sel = std::integral_constant<
2249 std::is_same<FwdIterator, iterator>::value ||
2250 std::is_same<FwdIterator, const_iterator>::value>;
2251 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2255 auto const n1 = i2 - i1;
2256 FBSTRING_ASSERT(n1 >= 0);
2257 auto const n2 = std::distance(s1, s2);
2258 FBSTRING_ASSERT(n2 >= 0);
2262 std::copy(s1, s2, i1);
2266 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2269 FBSTRING_ASSERT(isSane());
2272 template <typename E, class T, class A, class S>
2273 template <class InputIterator>
2274 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2279 std::input_iterator_tag) {
2280 basic_fbstring temp(begin(), i1);
2281 temp.append(b, e).append(i2, end());
2285 template <typename E, class T, class A, class S>
2286 inline typename basic_fbstring<E, T, A, S>::size_type
2287 basic_fbstring<E, T, A, S>::rfind(
2288 const value_type* s, size_type pos, size_type n) const {
2292 pos = std::min(pos, length() - n);
2297 const_iterator i(begin() + pos);
2299 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2309 template <typename E, class T, class A, class S>
2310 inline typename basic_fbstring<E, T, A, S>::size_type
2311 basic_fbstring<E, T, A, S>::find_first_of(
2312 const value_type* s, size_type pos, size_type n) const {
2313 if (pos > length() || n == 0) {
2316 const_iterator i(begin() + pos), finish(end());
2317 for (; i != finish; ++i) {
2318 if (traits_type::find(s, n, *i) != 0) {
2325 template <typename E, class T, class A, class S>
2326 inline typename basic_fbstring<E, T, A, S>::size_type
2327 basic_fbstring<E, T, A, S>::find_last_of(
2328 const value_type* s, size_type pos, size_type n) const {
2329 if (!empty() && n > 0) {
2330 pos = std::min(pos, length() - 1);
2331 const_iterator i(begin() + pos);
2333 if (traits_type::find(s, n, *i) != 0) {
2344 template <typename E, class T, class A, class S>
2345 inline typename basic_fbstring<E, T, A, S>::size_type
2346 basic_fbstring<E, T, A, S>::find_first_not_of(
2347 const value_type* s, size_type pos, size_type n) const {
2348 if (pos < length()) {
2349 const_iterator i(begin() + pos), finish(end());
2350 for (; i != finish; ++i) {
2351 if (traits_type::find(s, n, *i) == 0) {
2359 template <typename E, class T, class A, class S>
2360 inline typename basic_fbstring<E, T, A, S>::size_type
2361 basic_fbstring<E, T, A, S>::find_last_not_of(
2362 const value_type* s, size_type pos, size_type n) const {
2363 if (!this->empty()) {
2364 pos = std::min(pos, size() - 1);
2365 const_iterator i(begin() + pos);
2367 if (traits_type::find(s, n, *i) == 0) {
2378 // non-member functions
2380 template <typename E, class T, class A, class S>
2382 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2383 const basic_fbstring<E, T, A, S>& rhs) {
2385 basic_fbstring<E, T, A, S> result;
2386 result.reserve(lhs.size() + rhs.size());
2387 result.append(lhs).append(rhs);
2388 return std::move(result);
2392 template <typename E, class T, class A, class S>
2394 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2395 const basic_fbstring<E, T, A, S>& rhs) {
2396 return std::move(lhs.append(rhs));
2400 template <typename E, class T, class A, class S>
2402 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2403 basic_fbstring<E, T, A, S>&& rhs) {
2404 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2405 // Good, at least we don't need to reallocate
2406 return std::move(rhs.insert(0, lhs));
2408 // Meh, no go. Forward to operator+(const&, const&).
2409 auto const& rhsC = rhs;
2414 template <typename E, class T, class A, class S>
2416 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2417 basic_fbstring<E, T, A, S>&& rhs) {
2418 return std::move(lhs.append(rhs));
2422 template <typename E, class T, class A, class S>
2424 basic_fbstring<E, T, A, S> operator+(
2426 const basic_fbstring<E, T, A, S>& rhs) {
2428 basic_fbstring<E, T, A, S> result;
2429 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2430 result.reserve(len + rhs.size());
2431 result.append(lhs, len).append(rhs);
2436 template <typename E, class T, class A, class S>
2438 basic_fbstring<E, T, A, S> operator+(
2440 basic_fbstring<E, T, A, S>&& rhs) {
2442 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2443 if (rhs.capacity() >= len + rhs.size()) {
2444 // Good, at least we don't need to reallocate
2445 rhs.insert(rhs.begin(), lhs, lhs + len);
2448 // Meh, no go. Do it by hand since we have len already.
2449 basic_fbstring<E, T, A, S> result;
2450 result.reserve(len + rhs.size());
2451 result.append(lhs, len).append(rhs);
2456 template <typename E, class T, class A, class S>
2458 basic_fbstring<E, T, A, S> operator+(
2460 const basic_fbstring<E, T, A, S>& rhs) {
2462 basic_fbstring<E, T, A, S> result;
2463 result.reserve(1 + rhs.size());
2464 result.push_back(lhs);
2470 template <typename E, class T, class A, class S>
2472 basic_fbstring<E, T, A, S> operator+(
2474 basic_fbstring<E, T, A, S>&& rhs) {
2476 if (rhs.capacity() > rhs.size()) {
2477 // Good, at least we don't need to reallocate
2478 rhs.insert(rhs.begin(), lhs);
2481 // Meh, no go. Forward to operator+(E, const&).
2482 auto const& rhsC = rhs;
2487 template <typename E, class T, class A, class S>
2489 basic_fbstring<E, T, A, S> operator+(
2490 const basic_fbstring<E, T, A, S>& lhs,
2493 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2494 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2496 basic_fbstring<E, T, A, S> result;
2497 const size_type len = traits_type::length(rhs);
2498 result.reserve(lhs.size() + len);
2499 result.append(lhs).append(rhs, len);
2503 // C++11 21.4.8.1/10
2504 template <typename E, class T, class A, class S>
2506 basic_fbstring<E, T, A, S> operator+(
2507 basic_fbstring<E, T, A, S>&& lhs,
2510 return std::move(lhs += rhs);
2513 // C++11 21.4.8.1/11
2514 template <typename E, class T, class A, class S>
2516 basic_fbstring<E, T, A, S> operator+(
2517 const basic_fbstring<E, T, A, S>& lhs,
2520 basic_fbstring<E, T, A, S> result;
2521 result.reserve(lhs.size() + 1);
2523 result.push_back(rhs);
2527 // C++11 21.4.8.1/12
2528 template <typename E, class T, class A, class S>
2530 basic_fbstring<E, T, A, S> operator+(
2531 basic_fbstring<E, T, A, S>&& lhs,
2534 return std::move(lhs += rhs);
2537 template <typename E, class T, class A, class S>
2539 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2540 const basic_fbstring<E, T, A, S>& rhs) {
2541 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2543 template <typename E, class T, class A, class S>
2545 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2546 const basic_fbstring<E, T, A, S>& rhs) {
2547 return rhs == lhs; }
2549 template <typename E, class T, class A, class S>
2551 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2552 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2553 return lhs.compare(rhs) == 0; }
2555 template <typename E, class T, class A, class S>
2557 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2558 const basic_fbstring<E, T, A, S>& rhs) {
2559 return !(lhs == rhs); }
2561 template <typename E, class T, class A, class S>
2563 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2564 const basic_fbstring<E, T, A, S>& rhs) {
2565 return !(lhs == rhs); }
2567 template <typename E, class T, class A, class S>
2569 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2570 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2571 return !(lhs == rhs); }
2573 template <typename E, class T, class A, class S>
2575 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2576 const basic_fbstring<E, T, A, S>& rhs) {
2577 return lhs.compare(rhs) < 0; }
2579 template <typename E, class T, class A, class S>
2581 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2582 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2583 return lhs.compare(rhs) < 0; }
2585 template <typename E, class T, class A, class S>
2587 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2588 const basic_fbstring<E, T, A, S>& rhs) {
2589 return rhs.compare(lhs) > 0; }
2591 template <typename E, class T, class A, class S>
2593 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2594 const basic_fbstring<E, T, A, S>& rhs) {
2597 template <typename E, class T, class A, class S>
2599 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2600 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2603 template <typename E, class T, class A, class S>
2605 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2606 const basic_fbstring<E, T, A, S>& rhs) {
2609 template <typename E, class T, class A, class S>
2611 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2612 const basic_fbstring<E, T, A, S>& rhs) {
2613 return !(rhs < lhs); }
2615 template <typename E, class T, class A, class S>
2617 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2618 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2619 return !(rhs < lhs); }
2621 template <typename E, class T, class A, class S>
2623 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2624 const basic_fbstring<E, T, A, S>& rhs) {
2625 return !(rhs < lhs); }
2627 template <typename E, class T, class A, class S>
2629 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2630 const basic_fbstring<E, T, A, S>& rhs) {
2631 return !(lhs < rhs); }
2633 template <typename E, class T, class A, class S>
2635 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2636 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2637 return !(lhs < rhs); }
2639 template <typename E, class T, class A, class S>
2641 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2642 const basic_fbstring<E, T, A, S>& rhs) {
2643 return !(lhs < rhs);
2647 template <typename E, class T, class A, class S>
2648 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2652 // TODO: make this faster.
2653 template <typename E, class T, class A, class S>
2656 typename basic_fbstring<E, T, A, S>::value_type,
2657 typename basic_fbstring<E, T, A, S>::traits_type>&
2659 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2660 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2661 basic_fbstring<E, T, A, S>& str) {
2662 typedef std::basic_istream<
2663 typename basic_fbstring<E, T, A, S>::value_type,
2664 typename basic_fbstring<E, T, A, S>::traits_type>
2666 typename _istream_type::sentry sentry(is);
2667 size_t extracted = 0;
2668 auto err = _istream_type::goodbit;
2670 auto n = is.width();
2675 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2676 if (got == T::eof()) {
2677 err |= _istream_type::eofbit;
2685 got = is.rdbuf()->snextc();
2689 err |= _istream_type::failbit;
2697 template <typename E, class T, class A, class S>
2699 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2700 typename basic_fbstring<E, T, A, S>::traits_type>&
2702 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2703 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2704 const basic_fbstring<E, T, A, S>& str) {
2706 typedef std::basic_ostream<
2707 typename basic_fbstring<E, T, A, S>::value_type,
2708 typename basic_fbstring<E, T, A, S>::traits_type>
2710 typename _ostream_type::sentry _s(os);
2712 typedef std::ostreambuf_iterator<
2713 typename basic_fbstring<E, T, A, S>::value_type,
2714 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2715 size_t __len = str.size();
2717 (os.flags() & _ostream_type::adjustfield) == _ostream_type::left;
2718 if (__pad_and_output(_Ip(os),
2720 __left ? str.data() + __len : str.data(),
2723 os.fill()).failed()) {
2724 os.setstate(_ostream_type::badbit | _ostream_type::failbit);
2727 #elif defined(_MSC_VER)
2728 typedef decltype(os.precision()) streamsize;
2729 // MSVC doesn't define __ostream_insert
2730 os.write(str.data(), static_cast<streamsize>(str.size()));
2732 std::__ostream_insert(os, str.data(), str.size());
2737 template <typename E1, class T, class A, class S>
2738 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2739 basic_fbstring<E1, T, A, S>::npos;
2741 #ifndef _LIBSTDCXX_FBSTRING
2742 // basic_string compatibility routines
2744 template <typename E, class T, class A, class S, class A2>
2745 inline bool operator==(
2746 const basic_fbstring<E, T, A, S>& lhs,
2747 const std::basic_string<E, T, A2>& rhs) {
2748 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2751 template <typename E, class T, class A, class S, class A2>
2752 inline bool operator==(
2753 const std::basic_string<E, T, A2>& lhs,
2754 const basic_fbstring<E, T, A, S>& rhs) {
2758 template <typename E, class T, class A, class S, class A2>
2759 inline bool operator!=(
2760 const basic_fbstring<E, T, A, S>& lhs,
2761 const std::basic_string<E, T, A2>& rhs) {
2762 return !(lhs == rhs);
2765 template <typename E, class T, class A, class S, class A2>
2766 inline bool operator!=(
2767 const std::basic_string<E, T, A2>& lhs,
2768 const basic_fbstring<E, T, A, S>& rhs) {
2769 return !(lhs == rhs);
2772 template <typename E, class T, class A, class S, class A2>
2773 inline bool operator<(
2774 const basic_fbstring<E, T, A, S>& lhs,
2775 const std::basic_string<E, T, A2>& rhs) {
2776 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0;
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 std::basic_string<E, T, A2>& lhs,
2789 const basic_fbstring<E, T, A, S>& rhs) {
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 basic_fbstring<E, T, A, S>& lhs,
2803 const std::basic_string<E, T, A2>& rhs) {
2804 return !(lhs > 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 std::basic_string<E, T, A2>& lhs,
2817 const basic_fbstring<E, T, A, S>& 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 #if !defined(_LIBSTDCXX_FBSTRING)
2829 typedef basic_fbstring<char> fbstring;
2832 // fbstring is relocatable
2833 template <class T, class R, class A, class S>
2834 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2837 _GLIBCXX_END_NAMESPACE_VERSION
2840 } // namespace folly
2842 #ifndef _LIBSTDCXX_FBSTRING
2844 // Hash functions to make fbstring usable with e.g. hash_map
2846 // Handle interaction with different C++ standard libraries, which
2847 // expect these types to be in different namespaces.
2849 #define FOLLY_FBSTRING_HASH1(T) \
2851 struct hash< ::folly::basic_fbstring<T>> { \
2852 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2853 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2857 // The C++11 standard says that these four are defined
2858 #define FOLLY_FBSTRING_HASH \
2859 FOLLY_FBSTRING_HASH1(char) \
2860 FOLLY_FBSTRING_HASH1(char16_t) \
2861 FOLLY_FBSTRING_HASH1(char32_t) \
2862 FOLLY_FBSTRING_HASH1(wchar_t)
2870 #undef FOLLY_FBSTRING_HASH
2871 #undef FOLLY_FBSTRING_HASH1
2873 #endif // _LIBSTDCXX_FBSTRING
2877 #undef FBSTRING_DISABLE_SSO
2878 #undef FBSTRING_SANITIZE_ADDRESS
2880 #undef FBSTRING_LIKELY
2881 #undef FBSTRING_UNLIKELY
2882 #undef FBSTRING_ASSERT