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>
60 #if FOLLY_HAVE_DEPRECATED_ASSOC
61 #ifdef _GLIBCXX_SYMVER
62 #include <ext/hash_set>
63 #include <ext/hash_map>
67 // When used in folly, assertions are not disabled.
68 #define FBSTRING_ASSERT(expr) assert(expr)
72 // We defined these here rather than including Likely.h to avoid
73 // redefinition errors when fbstring is imported into libstdc++.
74 #if defined(__GNUC__) && __GNUC__ >= 4
75 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
76 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
78 #define FBSTRING_LIKELY(x) (x)
79 #define FBSTRING_UNLIKELY(x) (x)
82 #pragma GCC diagnostic push
83 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
84 #pragma GCC diagnostic ignored "-Wshadow"
85 // GCC 4.9 has a false positive in setSmallSize (probably
86 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
87 // compile-time array bound checking.
88 #pragma GCC diagnostic ignored "-Warray-bounds"
90 // FBString cannot use throw when replacing std::string, though it may still
93 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
95 #ifdef _LIBSTDCXX_FBSTRING
96 namespace std _GLIBCXX_VISIBILITY(default) {
97 _GLIBCXX_BEGIN_NAMESPACE_VERSION
102 #if defined(__clang__)
103 # if __has_feature(address_sanitizer)
104 # define FBSTRING_SANITIZE_ADDRESS
106 #elif defined (__GNUC__) && \
107 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
109 # define FBSTRING_SANITIZE_ADDRESS
112 // When compiling with ASan, always heap-allocate the string even if
113 // it would fit in-situ, so that ASan can detect access to the string
114 // buffer after it has been invalidated (destroyed, resized, etc.).
115 // Note that this flag doesn't remove support for in-situ strings, as
116 // that would break ABI-compatibility and wouldn't allow linking code
117 // compiled with this flag with code compiled without.
118 #ifdef FBSTRING_SANITIZE_ADDRESS
119 # define FBSTRING_DISABLE_SSO true
121 # define FBSTRING_DISABLE_SSO false
124 namespace fbstring_detail {
126 template <class InIt, class OutIt>
127 inline std::pair<InIt, OutIt> copy_n(
129 typename std::iterator_traits<InIt>::difference_type n,
131 for (; n != 0; --n, ++b, ++d) {
134 return std::make_pair(b, d);
137 template <class Pod, class T>
138 inline void podFill(Pod* b, Pod* e, T c) {
139 FBSTRING_ASSERT(b && e && b <= e);
140 constexpr auto kUseMemset = sizeof(T) == 1;
141 /* static */ if (kUseMemset) {
142 memset(b, c, size_t(e - b));
144 auto const ee = b + ((e - b) & ~7u);
145 for (; b != ee; b += 8) {
156 for (; b != e; ++b) {
163 * Lightly structured memcpy, simplifies copying PODs and introduces
164 * some asserts. Unfortunately using this function may cause
165 * measurable overhead (presumably because it adjusts from a begin/end
166 * convention to a pointer/size convention, so it does some extra
167 * arithmetic even though the caller might have done the inverse
168 * adaptation outside).
171 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
172 FBSTRING_ASSERT(b != nullptr);
173 FBSTRING_ASSERT(e != nullptr);
174 FBSTRING_ASSERT(d != nullptr);
175 FBSTRING_ASSERT(e >= b);
176 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
177 memcpy(d, b, (e - b) * sizeof(Pod));
181 * Lightly structured memmove, simplifies copying PODs and introduces
185 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
186 FBSTRING_ASSERT(e >= b);
187 memmove(d, b, (e - b) * sizeof(*b));
191 #if defined(__GNUC__) // Clang also defines __GNUC__
192 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
193 #elif defined(_MSC_VER)
194 # define FBSTRING_ALWAYS_INLINE __forceinline
196 # define FBSTRING_ALWAYS_INLINE inline
199 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
200 #if defined(__GNUC__) // Clang also defines __GNUC__
201 __builtin_unreachable();
202 #elif defined(_MSC_VER)
205 // Well, it's better than nothing.
210 } // namespace fbstring_detail
213 * Defines a special acquisition method for constructing fbstring
214 * objects. AcquireMallocatedString means that the user passes a
215 * pointer to a malloc-allocated string that the fbstring object will
218 enum class AcquireMallocatedString {};
221 * fbstring_core_model is a mock-up type that defines all required
222 * signatures of a fbstring core. The fbstring class itself uses such
223 * a core object to implement all of the numerous member functions
224 * required by the standard.
226 * If you want to define a new core, copy the definition below and
227 * implement the primitives. Then plug the core into basic_fbstring as
228 * a template argument.
230 template <class Char>
231 class fbstring_core_model {
233 fbstring_core_model();
234 fbstring_core_model(const fbstring_core_model &);
235 ~fbstring_core_model();
236 // Returns a pointer to string's buffer (currently only contiguous
237 // strings are supported). The pointer is guaranteed to be valid
238 // until the next call to a non-const member function.
239 const Char * data() const;
240 // Much like data(), except the string is prepared to support
241 // character-level changes. This call is a signal for
242 // e.g. reference-counted implementation to fork the data. The
243 // pointer is guaranteed to be valid until the next call to a
244 // non-const member function.
246 // Returns a pointer to string's buffer and guarantees that a
247 // readable '\0' lies right after the buffer. The pointer is
248 // guaranteed to be valid until the next call to a non-const member
250 const Char * c_str() const;
251 // Shrinks the string by delta characters. Asserts that delta <=
253 void shrink(size_t delta);
254 // Expands the string by delta characters (i.e. after this call
255 // size() will report the old size() plus delta) but without
256 // initializing the expanded region. The expanded region is
257 // zero-terminated. Returns a pointer to the memory to be
258 // initialized (the beginning of the expanded portion). The caller
259 // is expected to fill the expanded area appropriately.
260 // If expGrowth is true, exponential growth is guaranteed.
261 // It is not guaranteed not to reallocate even if size() + delta <
262 // capacity(), so all references to the buffer are invalidated.
263 Char* expandNoinit(size_t delta, bool expGrowth);
264 // Expands the string by one character and sets the last character
266 void push_back(Char c);
267 // Returns the string's size.
269 // Returns the string's capacity, i.e. maximum size that the string
270 // can grow to without reallocation. Note that for reference counted
271 // strings that's technically a lie - even assigning characters
272 // within the existing size would cause a reallocation.
273 size_t capacity() const;
274 // Returns true if the data underlying the string is actually shared
275 // across multiple strings (in a refcounted fashion).
276 bool isShared() const;
277 // Makes sure that at least minCapacity characters are available for
278 // the string without reallocation. For reference-counted strings,
279 // it should fork the data even if minCapacity < size().
280 void reserve(size_t minCapacity);
283 fbstring_core_model& operator=(const fbstring_core_model &);
288 * This is the core of the string. The code should work on 32- and
289 * 64-bit and both big- and little-endianan architectures with any
292 * The storage is selected as follows (assuming we store one-byte
293 * characters on a 64-bit machine): (a) "small" strings between 0 and
294 * 23 chars are stored in-situ without allocation (the rightmost byte
295 * stores the size); (b) "medium" strings from 24 through 254 chars
296 * are stored in malloc-allocated memory that is copied eagerly; (c)
297 * "large" strings of 255 chars and above are stored in a similar
298 * structure as medium arrays, except that the string is
299 * reference-counted and copied lazily. the reference count is
300 * allocated right before the character array.
302 * The discriminator between these three strategies sits in two
303 * bits of the rightmost char of the storage. If neither is set, then the
304 * string is small (and its length sits in the lower-order bits on
305 * little-endian or the high-order bits on big-endian of that
306 * rightmost character). If the MSb is set, the string is medium width.
307 * If the second MSb is set, then the string is large. On little-endian,
308 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
309 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
310 * and big-endian fbstring_core equivalent with merely different ops used
311 * to extract capacity/category.
313 template <class Char> class fbstring_core {
315 // It's MSVC, so we just have to guess ... and allow an override
317 # ifdef FOLLY_ENDIAN_BE
318 static constexpr auto kIsLittleEndian = false;
320 static constexpr auto kIsLittleEndian = true;
323 static constexpr auto kIsLittleEndian =
324 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
327 fbstring_core() noexcept { reset(); }
329 fbstring_core(const fbstring_core & rhs) {
330 FBSTRING_ASSERT(&rhs != this);
331 switch (rhs.category()) {
332 case Category::isSmall:
335 case Category::isMedium:
338 case Category::isLarge:
342 fbstring_detail::assume_unreachable();
344 FBSTRING_ASSERT(size() == rhs.size());
345 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
348 fbstring_core(fbstring_core&& goner) noexcept {
351 // Clean goner's carcass
355 fbstring_core(const Char *const data,
357 bool disableSSO = FBSTRING_DISABLE_SSO) {
358 if (!disableSSO && size <= maxSmallSize) {
359 initSmall(data, size);
360 } else if (size <= maxMediumSize) {
361 initMedium(data, size);
363 initLarge(data, size);
365 FBSTRING_ASSERT(this->size() == size);
367 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
370 ~fbstring_core() noexcept {
371 if (category() == Category::isSmall) {
374 destroyMediumLarge();
377 // Snatches a previously mallocated string. The parameter "size"
378 // is the size of the string, and the parameter "allocatedSize"
379 // is the size of the mallocated block. The string must be
380 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
382 // So if you want a 2-character string, pass malloc(3) as "data",
383 // pass 2 as "size", and pass 3 as "allocatedSize".
384 fbstring_core(Char * const data,
386 const size_t allocatedSize,
387 AcquireMallocatedString) {
389 FBSTRING_ASSERT(allocatedSize >= size + 1);
390 FBSTRING_ASSERT(data[size] == '\0');
391 // Use the medium string storage
394 // Don't forget about null terminator
395 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
397 // No need for the memory
403 // swap below doesn't test whether &rhs == this (and instead
404 // potentially does extra work) on the premise that the rarity of
405 // that situation actually makes the check more expensive than is
407 void swap(fbstring_core & rhs) {
413 // In C++11 data() and c_str() are 100% equivalent.
414 const Char * data() const {
418 Char* mutableData() {
419 switch (category()) {
420 case Category::isSmall:
422 case Category::isMedium:
424 case Category::isLarge:
425 return mutableDataLarge();
427 fbstring_detail::assume_unreachable();
430 const Char* c_str() const {
431 const Char* ptr = ml_.data_;
432 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
433 ptr = (category() == Category::isSmall) ? small_ : ptr;
437 void shrink(const size_t delta) {
438 if (category() == Category::isSmall) {
440 } else if (category() == Category::isMedium ||
441 RefCounted::refs(ml_.data_) == 1) {
448 FOLLY_MALLOC_NOINLINE
449 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
450 switch (category()) {
451 case Category::isSmall:
452 reserveSmall(minCapacity, disableSSO);
454 case Category::isMedium:
455 reserveMedium(minCapacity);
457 case Category::isLarge:
458 reserveLarge(minCapacity);
461 fbstring_detail::assume_unreachable();
463 FBSTRING_ASSERT(capacity() >= minCapacity);
468 bool expGrowth = false,
469 bool disableSSO = FBSTRING_DISABLE_SSO);
471 void push_back(Char c) {
472 *expandNoinit(1, /* expGrowth = */ true) = c;
475 size_t size() const {
476 size_t ret = ml_.size_;
477 /* static */ if (kIsLittleEndian) {
478 // We can save a couple instructions, because the category is
479 // small iff the last char, as unsigned, is <= maxSmallSize.
480 typedef typename std::make_unsigned<Char>::type UChar;
481 auto maybeSmallSize = size_t(maxSmallSize) -
482 size_t(static_cast<UChar>(small_[maxSmallSize]));
483 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
484 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
486 ret = (category() == Category::isSmall) ? smallSize() : ret;
491 size_t capacity() const {
492 switch (category()) {
493 case Category::isSmall:
495 case Category::isLarge:
496 // For large-sized strings, a multi-referenced chunk has no
497 // available capacity. This is because any attempt to append
498 // data would trigger a new allocation.
499 if (RefCounted::refs(ml_.data_) > 1) {
504 return ml_.capacity();
507 bool isShared() const {
508 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
513 fbstring_core & operator=(const fbstring_core & rhs);
519 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
520 auto const c = category();
521 FBSTRING_ASSERT(c != Category::isSmall);
522 if (c == Category::isMedium) {
525 RefCounted::decrementRefs(ml_.data_);
530 std::atomic<size_t> refCount_;
533 constexpr static size_t getDataOffset() {
534 return offsetof(RefCounted, data_);
537 static RefCounted * fromData(Char * p) {
538 return static_cast<RefCounted*>(static_cast<void*>(
539 static_cast<unsigned char*>(static_cast<void*>(p)) -
543 static size_t refs(Char * p) {
544 return fromData(p)->refCount_.load(std::memory_order_acquire);
547 static void incrementRefs(Char * p) {
548 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
551 static void decrementRefs(Char * p) {
552 auto const dis = fromData(p);
553 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
554 FBSTRING_ASSERT(oldcnt > 0);
560 static RefCounted * create(size_t * size) {
561 const size_t allocSize =
562 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
563 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
564 result->refCount_.store(1, std::memory_order_release);
565 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
569 static RefCounted * create(const Char * data, size_t * size) {
570 const size_t effectiveSize = *size;
571 auto result = create(size);
572 if (FBSTRING_LIKELY(effectiveSize > 0)) {
573 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
578 static RefCounted * reallocate(Char *const data,
579 const size_t currentSize,
580 const size_t currentCapacity,
581 size_t * newCapacity) {
582 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
583 const size_t allocNewCapacity =
584 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
585 auto const dis = fromData(data);
586 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
587 auto result = static_cast<RefCounted*>(smartRealloc(
589 getDataOffset() + (currentSize + 1) * sizeof(Char),
590 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
592 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
593 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
598 typedef uint8_t category_type;
600 enum class Category : category_type {
602 isMedium = kIsLittleEndian ? 0x80 : 0x2,
603 isLarge = kIsLittleEndian ? 0x40 : 0x1,
606 Category category() const {
607 // works for both big-endian and little-endian
608 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
616 size_t capacity() const {
617 return kIsLittleEndian
618 ? capacity_ & capacityExtractMask
622 void setCapacity(size_t cap, Category cat) {
623 capacity_ = kIsLittleEndian
624 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
625 : (cap << 2) | static_cast<size_t>(cat);
630 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
631 Char small_[sizeof(MediumLarge) / sizeof(Char)];
635 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
636 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
637 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
638 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
639 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
640 constexpr static size_t capacityExtractMask = kIsLittleEndian
641 ? ~(size_t(categoryExtractMask) << kCategoryShift)
644 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
645 "Corrupt memory layout for fbstring.");
647 size_t smallSize() const {
648 FBSTRING_ASSERT(category() == Category::isSmall);
649 constexpr auto shift = kIsLittleEndian ? 0 : 2;
650 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
651 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
652 return static_cast<size_t>(maxSmallSize) - smallShifted;
655 void setSmallSize(size_t s) {
656 // Warning: this should work with uninitialized strings too,
657 // so don't assume anything about the previous value of
658 // small_[maxSmallSize].
659 FBSTRING_ASSERT(s <= maxSmallSize);
660 constexpr auto shift = kIsLittleEndian ? 0 : 2;
661 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
663 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
666 void copySmall(const fbstring_core&);
667 void copyMedium(const fbstring_core&);
668 void copyLarge(const fbstring_core&);
670 void initSmall(const Char* data, size_t size);
671 void initMedium(const Char* data, size_t size);
672 void initLarge(const Char* data, size_t size);
674 void reserveSmall(size_t minCapacity, bool disableSSO);
675 void reserveMedium(size_t minCapacity);
676 void reserveLarge(size_t minCapacity);
678 void shrinkSmall(size_t delta);
679 void shrinkMedium(size_t delta);
680 void shrinkLarge(size_t delta);
682 void unshare(size_t minCapacity = 0);
683 Char* mutableDataLarge();
686 template <class Char>
687 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
688 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
690 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
691 "fbstring layout failure");
693 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
694 "fbstring layout failure");
695 // Just write the whole thing, don't look at details. In
696 // particular we need to copy capacity anyway because we want
697 // to set the size (don't forget that the last character,
698 // which stores a short string's length, is shared with the
699 // ml_.capacity field).
702 category() == Category::isSmall && this->size() == rhs.size());
705 template <class Char>
706 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
707 const fbstring_core& rhs) {
708 // Medium strings are copied eagerly. Don't forget to allocate
709 // one extra Char for the null terminator.
710 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
711 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
712 // Also copies terminator.
713 fbstring_detail::podCopy(
714 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
715 ml_.size_ = rhs.ml_.size_;
716 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
717 FBSTRING_ASSERT(category() == Category::isMedium);
720 template <class Char>
721 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
722 const fbstring_core& rhs) {
723 // Large strings are just refcounted
725 RefCounted::incrementRefs(ml_.data_);
726 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
729 // Small strings are bitblitted
730 template <class Char>
731 inline void fbstring_core<Char>::initSmall(
732 const Char* const data, const size_t size) {
733 // Layout is: Char* data_, size_t size_, size_t capacity_
735 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
736 "fbstring has unexpected size");
738 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
739 // sizeof(size_t) must be a power of 2
741 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
742 "fbstring size assumption violation");
744 // If data is aligned, use fast word-wise copying. Otherwise,
745 // use conservative memcpy.
746 // The word-wise path reads bytes which are outside the range of
747 // the string, and makes ASan unhappy, so we disable it when
748 // compiling with ASan.
749 #ifndef FBSTRING_SANITIZE_ADDRESS
750 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
751 const size_t byteSize = size * sizeof(Char);
752 constexpr size_t wordWidth = sizeof(size_t);
753 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
755 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
757 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
759 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
767 fbstring_detail::podCopy(data, data + size, small_);
773 template <class Char>
774 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
775 const Char* const data, const size_t size) {
776 // Medium strings are allocated normally. Don't forget to
777 // allocate one extra Char for the terminating null.
778 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
779 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
780 if (FBSTRING_LIKELY(size > 0)) {
781 fbstring_detail::podCopy(data, data + size, ml_.data_);
784 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
785 ml_.data_[size] = '\0';
788 template <class Char>
789 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
790 const Char* const data, const size_t size) {
791 // Large strings are allocated differently
792 size_t effectiveCapacity = size;
793 auto const newRC = RefCounted::create(data, &effectiveCapacity);
794 ml_.data_ = newRC->data_;
796 ml_.setCapacity(effectiveCapacity, Category::isLarge);
797 ml_.data_[size] = '\0';
800 template <class Char>
801 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
802 size_t minCapacity) {
803 FBSTRING_ASSERT(category() == Category::isLarge);
804 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
805 auto const newRC = RefCounted::create(&effectiveCapacity);
806 // If this fails, someone placed the wrong capacity in an
808 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
809 // Also copies terminator.
810 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
811 RefCounted::decrementRefs(ml_.data_);
812 ml_.data_ = newRC->data_;
813 ml_.setCapacity(effectiveCapacity, Category::isLarge);
814 // size_ remains unchanged.
817 template <class Char>
818 inline Char* fbstring_core<Char>::mutableDataLarge() {
819 FBSTRING_ASSERT(category() == Category::isLarge);
820 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
826 template <class Char>
827 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
828 size_t minCapacity) {
829 FBSTRING_ASSERT(category() == Category::isLarge);
830 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
831 // We must make it unique regardless; in-place reallocation is
832 // useless if the string is shared. In order to not surprise
833 // people, reserve the new block at current capacity or
834 // more. That way, a string's capacity never shrinks after a
836 unshare(minCapacity);
838 // String is not shared, so let's try to realloc (if needed)
839 if (minCapacity > ml_.capacity()) {
840 // Asking for more memory
841 auto const newRC = RefCounted::reallocate(
842 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
843 ml_.data_ = newRC->data_;
844 ml_.setCapacity(minCapacity, Category::isLarge);
846 FBSTRING_ASSERT(capacity() >= minCapacity);
850 template <class Char>
851 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
852 const size_t minCapacity) {
853 FBSTRING_ASSERT(category() == Category::isMedium);
854 // String is not shared
855 if (minCapacity <= ml_.capacity()) {
856 return; // nothing to do, there's enough room
858 if (minCapacity <= maxMediumSize) {
859 // Keep the string at medium size. Don't forget to allocate
860 // one extra Char for the terminating null.
861 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
862 // Also copies terminator.
863 ml_.data_ = static_cast<Char*>(smartRealloc(
865 (ml_.size_ + 1) * sizeof(Char),
866 (ml_.capacity() + 1) * sizeof(Char),
868 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
870 // Conversion from medium to large string
871 fbstring_core nascent;
872 // Will recurse to another branch of this function
873 nascent.reserve(minCapacity);
874 nascent.ml_.size_ = ml_.size_;
875 // Also copies terminator.
876 fbstring_detail::podCopy(
877 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
879 FBSTRING_ASSERT(capacity() >= minCapacity);
883 template <class Char>
884 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
885 size_t minCapacity, const bool disableSSO) {
886 FBSTRING_ASSERT(category() == Category::isSmall);
887 if (!disableSSO && minCapacity <= maxSmallSize) {
889 // Nothing to do, everything stays put
890 } else if (minCapacity <= maxMediumSize) {
892 // Don't forget to allocate one extra Char for the terminating null
893 auto const allocSizeBytes =
894 goodMallocSize((1 + minCapacity) * sizeof(Char));
895 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
896 auto const size = smallSize();
897 // Also copies terminator.
898 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
901 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
904 auto const newRC = RefCounted::create(&minCapacity);
905 auto const size = smallSize();
906 // Also copies terminator.
907 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
908 ml_.data_ = newRC->data_;
910 ml_.setCapacity(minCapacity, Category::isLarge);
911 FBSTRING_ASSERT(capacity() >= minCapacity);
915 template <class Char>
916 inline Char* fbstring_core<Char>::expandNoinit(
918 bool expGrowth, /* = false */
919 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
920 // Strategy is simple: make room, then change size
921 FBSTRING_ASSERT(capacity() >= size());
923 if (category() == Category::isSmall) {
926 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
931 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
935 if (FBSTRING_UNLIKELY(newSz > capacity())) {
936 // ensures not shared
937 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
940 FBSTRING_ASSERT(capacity() >= newSz);
941 // Category can't be small - we took care of that above
943 category() == Category::isMedium || category() == Category::isLarge);
945 ml_.data_[newSz] = '\0';
946 FBSTRING_ASSERT(size() == newSz);
947 return ml_.data_ + sz;
950 template <class Char>
951 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
952 // Check for underflow
953 FBSTRING_ASSERT(delta <= smallSize());
954 setSmallSize(smallSize() - delta);
957 template <class Char>
958 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
959 // Medium strings and unique large strings need no special
961 FBSTRING_ASSERT(ml_.size_ >= delta);
963 ml_.data_[ml_.size_] = '\0';
966 template <class Char>
967 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
968 FBSTRING_ASSERT(ml_.size_ >= delta);
969 // Shared large string, must make unique. This is because of the
970 // durn terminator must be written, which may trample the shared
973 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
975 // No need to write the terminator.
978 #ifndef _LIBSTDCXX_FBSTRING
980 * Dummy fbstring core that uses an actual std::string. This doesn't
981 * make any sense - it's just for testing purposes.
983 template <class Char>
984 class dummy_fbstring_core {
986 dummy_fbstring_core() {
988 dummy_fbstring_core(const dummy_fbstring_core& another)
989 : backend_(another.backend_) {
991 dummy_fbstring_core(const Char * s, size_t n)
994 void swap(dummy_fbstring_core & rhs) {
995 backend_.swap(rhs.backend_);
997 const Char * data() const {
998 return backend_.data();
1000 Char* mutableData() {
1001 return const_cast<Char*>(backend_.data());
1003 void shrink(size_t delta) {
1004 FBSTRING_ASSERT(delta <= size());
1005 backend_.resize(size() - delta);
1007 Char* expandNoinit(size_t delta) {
1008 auto const sz = size();
1009 backend_.resize(size() + delta);
1010 return backend_.data() + sz;
1012 void push_back(Char c) {
1013 backend_.push_back(c);
1015 size_t size() const {
1016 return backend_.size();
1018 size_t capacity() const {
1019 return backend_.capacity();
1021 bool isShared() const {
1024 void reserve(size_t minCapacity) {
1025 backend_.reserve(minCapacity);
1029 std::basic_string<Char> backend_;
1031 #endif // !_LIBSTDCXX_FBSTRING
1034 * This is the basic_string replacement. For conformity,
1035 * basic_fbstring takes the same template parameters, plus the last
1036 * one which is the core.
1038 #ifdef _LIBSTDCXX_FBSTRING
1039 template <typename E, class T, class A, class Storage>
1041 template <typename E,
1042 class T = std::char_traits<E>,
1043 class A = std::allocator<E>,
1044 class Storage = fbstring_core<E> >
1046 class basic_fbstring {
1047 static void enforce(
1049 void (*throw_exc)(const char*),
1056 bool isSane() const {
1059 empty() == (size() == 0) &&
1060 empty() == (begin() == end()) &&
1061 size() <= max_size() &&
1062 capacity() <= max_size() &&
1063 size() <= capacity() &&
1064 begin()[size()] == '\0';
1068 Invariant& operator=(const Invariant&) = delete;
1069 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1070 FBSTRING_ASSERT(s_.isSane());
1072 ~Invariant() noexcept {
1073 FBSTRING_ASSERT(s_.isSane());
1077 const basic_fbstring& s_;
1082 typedef T traits_type;
1083 typedef typename traits_type::char_type value_type;
1084 typedef A allocator_type;
1085 typedef typename A::size_type size_type;
1086 typedef typename A::difference_type difference_type;
1088 typedef typename A::reference reference;
1089 typedef typename A::const_reference const_reference;
1090 typedef typename A::pointer pointer;
1091 typedef typename A::const_pointer const_pointer;
1093 typedef E* iterator;
1094 typedef const E* const_iterator;
1095 typedef std::reverse_iterator<iterator
1096 #ifdef NO_ITERATOR_TRAITS
1100 typedef std::reverse_iterator<const_iterator
1101 #ifdef NO_ITERATOR_TRAITS
1104 > const_reverse_iterator;
1106 static constexpr size_type npos = size_type(-1);
1107 typedef std::true_type IsRelocatable;
1110 static void procrustes(size_type& n, size_type nmax) {
1116 static size_type traitsLength(const value_type* s);
1119 // C++11 21.4.2 construct/copy/destroy
1121 // Note: while the following two constructors can be (and previously were)
1122 // collapsed into one constructor written this way:
1124 // explicit basic_fbstring(const A& a = A()) noexcept { }
1126 // This can cause Clang (at least version 3.7) to fail with the error:
1127 // "chosen constructor is explicit in copy-initialization ...
1128 // in implicit initialization of field '(x)' with omitted initializer"
1130 // if used in a struct which is default-initialized. Hence the split into
1131 // these two separate constructors.
1133 basic_fbstring() noexcept : basic_fbstring(A()) {
1136 explicit basic_fbstring(const A&) noexcept {
1139 basic_fbstring(const basic_fbstring& str)
1140 : store_(str.store_) {
1144 basic_fbstring(basic_fbstring&& goner) noexcept
1145 : store_(std::move(goner.store_)) {
1148 #ifndef _LIBSTDCXX_FBSTRING
1149 // This is defined for compatibility with std::string
1150 /* implicit */ basic_fbstring(const std::string& str)
1151 : store_(str.data(), str.size()) {
1155 basic_fbstring(const basic_fbstring& str,
1158 const A& /* a */ = A()) {
1159 assign(str, pos, n);
1162 FOLLY_MALLOC_NOINLINE
1163 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1164 : store_(s, traitsLength(s)) {}
1166 FOLLY_MALLOC_NOINLINE
1167 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1171 FOLLY_MALLOC_NOINLINE
1172 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1173 auto const pData = store_.expandNoinit(n);
1174 fbstring_detail::podFill(pData, pData + n, c);
1177 template <class InIt>
1178 FOLLY_MALLOC_NOINLINE basic_fbstring(
1181 typename std::enable_if<
1182 !std::is_same<InIt, value_type*>::value,
1183 const A>::type& /*a*/ = A()) {
1187 // Specialization for const char*, const char*
1188 FOLLY_MALLOC_NOINLINE
1189 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1190 : store_(b, size_type(e - b)) {
1193 // Nonstandard constructor
1194 basic_fbstring(value_type *s, size_type n, size_type c,
1195 AcquireMallocatedString a)
1196 : store_(s, n, c, a) {
1199 // Construction from initialization list
1200 FOLLY_MALLOC_NOINLINE
1201 basic_fbstring(std::initializer_list<value_type> il) {
1202 assign(il.begin(), il.end());
1205 ~basic_fbstring() noexcept {}
1207 basic_fbstring& operator=(const basic_fbstring& lhs);
1210 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1212 #ifndef _LIBSTDCXX_FBSTRING
1213 // Compatibility with std::string
1214 basic_fbstring & operator=(const std::string & rhs) {
1215 return assign(rhs.data(), rhs.size());
1218 // Compatibility with std::string
1219 std::string toStdString() const {
1220 return std::string(data(), size());
1223 // A lot of code in fbcode still uses this method, so keep it here for now.
1224 const basic_fbstring& toStdString() const {
1229 basic_fbstring& operator=(const value_type* s) {
1233 // This actually goes directly against the C++ spec, but the
1234 // value_type overload is dangerous, so we're explicitly deleting
1235 // any overloads of operator= that could implicitly convert to
1237 // Note that we do need to explicitly specify the template types because
1238 // otherwise MSVC 2017 will aggressively pre-resolve value_type to
1239 // traits_type::char_type, which won't compare as equal when determining
1240 // which overload the implementation is referring to.
1241 // Also note that MSVC 2015 Update 3 requires us to explicitly specify the
1242 // namespace in-which to search for basic_fbstring, otherwise it tries to
1243 // look for basic_fbstring::basic_fbstring, which is just plain wrong.
1244 template <typename TP>
1245 typename std::enable_if<
1247 typename std::decay<TP>::type,
1248 typename folly::basic_fbstring<E, T, A, Storage>::value_type>::value,
1249 basic_fbstring<E, T, A, Storage>&>::type
1252 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1253 return assign(il.begin(), il.end());
1256 // C++11 21.4.3 iterators:
1258 return store_.mutableData();
1261 const_iterator begin() const {
1262 return store_.data();
1265 const_iterator cbegin() const {
1270 return store_.mutableData() + store_.size();
1273 const_iterator end() const {
1274 return store_.data() + store_.size();
1277 const_iterator cend() const { return end(); }
1279 reverse_iterator rbegin() {
1280 return reverse_iterator(end());
1283 const_reverse_iterator rbegin() const {
1284 return const_reverse_iterator(end());
1287 const_reverse_iterator crbegin() const { return rbegin(); }
1289 reverse_iterator rend() {
1290 return reverse_iterator(begin());
1293 const_reverse_iterator rend() const {
1294 return const_reverse_iterator(begin());
1297 const_reverse_iterator crend() const { return rend(); }
1300 // C++11 21.4.5, element access:
1301 const value_type& front() const { return *begin(); }
1302 const value_type& back() const {
1303 FBSTRING_ASSERT(!empty());
1304 // Should be begin()[size() - 1], but that branches twice
1305 return *(end() - 1);
1307 value_type& front() { return *begin(); }
1308 value_type& back() {
1309 FBSTRING_ASSERT(!empty());
1310 // Should be begin()[size() - 1], but that branches twice
1311 return *(end() - 1);
1314 FBSTRING_ASSERT(!empty());
1318 // C++11 21.4.4 capacity:
1319 size_type size() const { return store_.size(); }
1321 size_type length() const { return size(); }
1323 size_type max_size() const {
1324 return std::numeric_limits<size_type>::max();
1327 void resize(size_type n, value_type c = value_type());
1329 size_type capacity() const { return store_.capacity(); }
1331 void reserve(size_type res_arg = 0) {
1332 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1333 store_.reserve(res_arg);
1336 void shrink_to_fit() {
1337 // Shrink only if slack memory is sufficiently large
1338 if (capacity() < size() * 3 / 2) {
1341 basic_fbstring(cbegin(), cend()).swap(*this);
1344 void clear() { resize(0); }
1346 bool empty() const { return size() == 0; }
1348 // C++11 21.4.5 element access:
1349 const_reference operator[](size_type pos) const {
1350 return *(begin() + pos);
1353 reference operator[](size_type pos) {
1354 return *(begin() + pos);
1357 const_reference at(size_type n) const {
1358 enforce(n <= size(), std::__throw_out_of_range, "");
1362 reference at(size_type n) {
1363 enforce(n < size(), std::__throw_out_of_range, "");
1367 // C++11 21.4.6 modifiers:
1368 basic_fbstring& operator+=(const basic_fbstring& str) {
1372 basic_fbstring& operator+=(const value_type* s) {
1376 basic_fbstring& operator+=(const value_type c) {
1381 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1386 basic_fbstring& append(const basic_fbstring& str);
1389 append(const basic_fbstring& str, const size_type pos, size_type n);
1391 basic_fbstring& append(const value_type* s, size_type n);
1393 basic_fbstring& append(const value_type* s) {
1394 return append(s, traitsLength(s));
1397 basic_fbstring& append(size_type n, value_type c);
1399 template<class InputIterator>
1400 basic_fbstring& append(InputIterator first, InputIterator last) {
1401 insert(end(), first, last);
1405 basic_fbstring& append(std::initializer_list<value_type> il) {
1406 return append(il.begin(), il.end());
1409 void push_back(const value_type c) { // primitive
1410 store_.push_back(c);
1413 basic_fbstring& assign(const basic_fbstring& str) {
1414 if (&str == this) return *this;
1415 return assign(str.data(), str.size());
1418 basic_fbstring& assign(basic_fbstring&& str) {
1419 return *this = std::move(str);
1423 assign(const basic_fbstring& str, const size_type pos, size_type n);
1425 basic_fbstring& assign(const value_type* s, const size_type n);
1427 basic_fbstring& assign(const value_type* s) {
1428 return assign(s, traitsLength(s));
1431 basic_fbstring& assign(std::initializer_list<value_type> il) {
1432 return assign(il.begin(), il.end());
1435 template <class ItOrLength, class ItOrChar>
1436 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1437 return replace(begin(), end(), first_or_n, last_or_c);
1440 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1441 return insert(pos1, str.data(), str.size());
1444 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1445 size_type pos2, size_type n) {
1446 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1447 procrustes(n, str.length() - pos2);
1448 return insert(pos1, str.data() + pos2, n);
1451 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1452 enforce(pos <= length(), std::__throw_out_of_range, "");
1453 insert(begin() + pos, s, s + n);
1457 basic_fbstring& insert(size_type pos, const value_type* s) {
1458 return insert(pos, s, traitsLength(s));
1461 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1462 enforce(pos <= length(), std::__throw_out_of_range, "");
1463 insert(begin() + pos, n, c);
1467 iterator insert(const_iterator p, const value_type c) {
1468 const size_type pos = p - cbegin();
1470 return begin() + pos;
1473 #ifndef _LIBSTDCXX_FBSTRING
1475 typedef std::basic_istream<value_type, traits_type> istream_type;
1476 istream_type& getlineImpl(istream_type& is, value_type delim);
1479 friend inline istream_type& getline(istream_type& is,
1480 basic_fbstring& str,
1482 return str.getlineImpl(is, delim);
1485 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1486 return getline(is, str, '\n');
1492 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1494 template <class InputIter>
1496 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1498 template <class FwdIterator>
1499 iterator insertImpl(
1503 std::forward_iterator_tag);
1505 template <class InputIterator>
1506 iterator insertImpl(
1510 std::input_iterator_tag);
1513 template <class ItOrLength, class ItOrChar>
1514 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1515 using Sel = std::integral_constant<
1517 std::numeric_limits<ItOrLength>::is_specialized>;
1518 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1521 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1522 return insert(p, il.begin(), il.end());
1525 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1526 Invariant checker(*this);
1528 enforce(pos <= length(), std::__throw_out_of_range, "");
1529 procrustes(n, length() - pos);
1530 std::copy(begin() + pos + n, end(), begin() + pos);
1531 resize(length() - n);
1535 iterator erase(iterator position) {
1536 const size_type pos(position - begin());
1537 enforce(pos <= size(), std::__throw_out_of_range, "");
1539 return begin() + pos;
1542 iterator erase(iterator first, iterator last) {
1543 const size_type pos(first - begin());
1544 erase(pos, last - first);
1545 return begin() + pos;
1548 // Replaces at most n1 chars of *this, starting with pos1 with the
1550 basic_fbstring& replace(size_type pos1, size_type n1,
1551 const basic_fbstring& str) {
1552 return replace(pos1, n1, str.data(), str.size());
1555 // Replaces at most n1 chars of *this, starting with pos1,
1556 // with at most n2 chars of str starting with pos2
1557 basic_fbstring& replace(size_type pos1, size_type n1,
1558 const basic_fbstring& str,
1559 size_type pos2, size_type n2) {
1560 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1561 return replace(pos1, n1, str.data() + pos2,
1562 std::min(n2, str.size() - pos2));
1565 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1566 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1567 return replace(pos, n1, s, traitsLength(s));
1570 // Replaces at most n1 chars of *this, starting with pos, with n2
1573 // consolidated with
1575 // Replaces at most n1 chars of *this, starting with pos, with at
1576 // most n2 chars of str. str must have at least n2 chars.
1577 template <class StrOrLength, class NumOrChar>
1578 basic_fbstring& replace(size_type pos, size_type n1,
1579 StrOrLength s_or_n2, NumOrChar n_or_c) {
1580 Invariant checker(*this);
1582 enforce(pos <= size(), std::__throw_out_of_range, "");
1583 procrustes(n1, length() - pos);
1584 const iterator b = begin() + pos;
1585 return replace(b, b + n1, s_or_n2, n_or_c);
1588 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1589 return replace(i1, i2, str.data(), str.length());
1592 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1593 return replace(i1, i2, s, traitsLength(s));
1597 basic_fbstring& replaceImplDiscr(
1600 const value_type* s,
1602 std::integral_constant<int, 2>);
1604 basic_fbstring& replaceImplDiscr(
1609 std::integral_constant<int, 1>);
1611 template <class InputIter>
1612 basic_fbstring& replaceImplDiscr(
1617 std::integral_constant<int, 0>);
1620 template <class FwdIterator>
1621 bool replaceAliased(iterator /* i1 */,
1623 FwdIterator /* s1 */,
1624 FwdIterator /* s2 */,
1629 template <class FwdIterator>
1630 bool replaceAliased(
1637 template <class FwdIterator>
1643 std::forward_iterator_tag);
1645 template <class InputIterator>
1651 std::input_iterator_tag);
1654 template <class T1, class T2>
1655 basic_fbstring& replace(iterator i1, iterator i2,
1656 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1657 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1658 num2 = std::numeric_limits<T2>::is_specialized;
1660 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1661 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1664 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1665 enforce(pos <= size(), std::__throw_out_of_range, "");
1666 procrustes(n, size() - pos);
1669 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1674 void swap(basic_fbstring& rhs) {
1675 store_.swap(rhs.store_);
1678 const value_type* c_str() const {
1679 return store_.c_str();
1682 const value_type* data() const { return c_str(); }
1684 allocator_type get_allocator() const {
1685 return allocator_type();
1688 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1689 return find(str.data(), pos, str.length());
1692 size_type find(const value_type* needle, size_type pos, size_type nsize)
1695 size_type find(const value_type* s, size_type pos = 0) const {
1696 return find(s, pos, traitsLength(s));
1699 size_type find (value_type c, size_type pos = 0) const {
1700 return find(&c, pos, 1);
1703 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1704 return rfind(str.data(), pos, str.length());
1707 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1709 size_type rfind(const value_type* s, size_type pos = npos) const {
1710 return rfind(s, pos, traitsLength(s));
1713 size_type rfind(value_type c, size_type pos = npos) const {
1714 return rfind(&c, pos, 1);
1717 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1718 return find_first_of(str.data(), pos, str.length());
1721 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1724 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1725 return find_first_of(s, pos, traitsLength(s));
1728 size_type find_first_of(value_type c, size_type pos = 0) const {
1729 return find_first_of(&c, pos, 1);
1732 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1734 return find_last_of(str.data(), pos, str.length());
1737 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1739 size_type find_last_of (const value_type* s,
1740 size_type pos = npos) const {
1741 return find_last_of(s, pos, traitsLength(s));
1744 size_type find_last_of (value_type c, size_type pos = npos) const {
1745 return find_last_of(&c, pos, 1);
1748 size_type find_first_not_of(const basic_fbstring& str,
1749 size_type pos = 0) const {
1750 return find_first_not_of(str.data(), pos, str.size());
1753 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1756 size_type find_first_not_of(const value_type* s,
1757 size_type pos = 0) const {
1758 return find_first_not_of(s, pos, traitsLength(s));
1761 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1762 return find_first_not_of(&c, pos, 1);
1765 size_type find_last_not_of(const basic_fbstring& str,
1766 size_type pos = npos) const {
1767 return find_last_not_of(str.data(), pos, str.length());
1770 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1773 size_type find_last_not_of(const value_type* s,
1774 size_type pos = npos) const {
1775 return find_last_not_of(s, pos, traitsLength(s));
1778 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1779 return find_last_not_of(&c, pos, 1);
1782 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1783 enforce(pos <= size(), std::__throw_out_of_range, "");
1784 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1787 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1788 enforce(pos <= size(), std::__throw_out_of_range, "");
1793 return std::move(*this);
1796 int compare(const basic_fbstring& str) const {
1797 // FIX due to Goncalo N M de Carvalho July 18, 2005
1798 return compare(0, size(), str);
1801 int compare(size_type pos1, size_type n1,
1802 const basic_fbstring& str) const {
1803 return compare(pos1, n1, str.data(), str.size());
1806 int compare(size_type pos1, size_type n1,
1807 const value_type* s) const {
1808 return compare(pos1, n1, s, traitsLength(s));
1811 int compare(size_type pos1, size_type n1,
1812 const value_type* s, size_type n2) const {
1813 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1814 procrustes(n1, size() - pos1);
1815 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1816 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1817 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1820 int compare(size_type pos1, size_type n1,
1821 const basic_fbstring& str,
1822 size_type pos2, size_type n2) const {
1823 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1824 return compare(pos1, n1, str.data() + pos2,
1825 std::min(n2, str.size() - pos2));
1828 // Code from Jean-Francois Bastien (03/26/2007)
1829 int compare(const value_type* s) const {
1830 // Could forward to compare(0, size(), s, traitsLength(s))
1831 // but that does two extra checks
1832 const size_type n1(size()), n2(traitsLength(s));
1833 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1834 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1842 template <typename E, class T, class A, class S>
1843 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1844 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1845 return s ? traits_type::length(s)
1846 : (std::__throw_logic_error(
1847 "basic_fbstring: null pointer initializer not valid"),
1851 template <typename E, class T, class A, class S>
1852 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1853 const basic_fbstring& lhs) {
1854 Invariant checker(*this);
1856 if (FBSTRING_UNLIKELY(&lhs == this)) {
1860 return assign(lhs.data(), lhs.size());
1864 template <typename E, class T, class A, class S>
1865 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1866 basic_fbstring&& goner) noexcept {
1867 if (FBSTRING_UNLIKELY(&goner == this)) {
1868 // Compatibility with std::basic_string<>,
1869 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1872 // No need of this anymore
1873 this->~basic_fbstring();
1874 // Move the goner into this
1875 new (&store_) S(std::move(goner.store_));
1879 template <typename E, class T, class A, class S>
1880 template <typename TP>
1881 inline typename std::enable_if<
1883 typename std::decay<TP>::type,
1884 typename basic_fbstring<E, T, A, S>::value_type>::value,
1885 basic_fbstring<E, T, A, S>&>::type
1886 basic_fbstring<E, T, A, S>::operator=(TP c) {
1887 Invariant checker(*this);
1890 store_.expandNoinit(1);
1891 } else if (store_.isShared()) {
1892 basic_fbstring(1, c).swap(*this);
1895 store_.shrink(size() - 1);
1901 template <typename E, class T, class A, class S>
1902 inline void basic_fbstring<E, T, A, S>::resize(
1903 const size_type n, const value_type c /*= value_type()*/) {
1904 Invariant checker(*this);
1906 auto size = this->size();
1908 store_.shrink(size - n);
1910 auto const delta = n - size;
1911 auto pData = store_.expandNoinit(delta);
1912 fbstring_detail::podFill(pData, pData + delta, c);
1914 FBSTRING_ASSERT(this->size() == n);
1917 template <typename E, class T, class A, class S>
1918 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1919 const basic_fbstring& str) {
1921 auto desiredSize = size() + str.size();
1923 append(str.data(), str.size());
1924 FBSTRING_ASSERT(size() == desiredSize);
1928 template <typename E, class T, class A, class S>
1929 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1930 const basic_fbstring& str, const size_type pos, size_type n) {
1931 const size_type sz = str.size();
1932 enforce(pos <= sz, std::__throw_out_of_range, "");
1933 procrustes(n, sz - pos);
1934 return append(str.data() + pos, n);
1937 template <typename E, class T, class A, class S>
1938 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1939 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1940 Invariant checker(*this);
1942 if (FBSTRING_UNLIKELY(!n)) {
1943 // Unlikely but must be done
1946 auto const oldSize = size();
1947 auto const oldData = data();
1948 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1950 // Check for aliasing (rare). We could use "<=" here but in theory
1951 // those do not work for pointers unless the pointers point to
1952 // elements in the same array. For that reason we use
1953 // std::less_equal, which is guaranteed to offer a total order
1954 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1956 std::less_equal<const value_type*> le;
1957 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1958 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1959 // expandNoinit() could have moved the storage, restore the source.
1960 s = data() + (s - oldData);
1961 fbstring_detail::podMove(s, s + n, pData);
1963 fbstring_detail::podCopy(s, s + n, pData);
1966 FBSTRING_ASSERT(size() == oldSize + n);
1970 template <typename E, class T, class A, class S>
1971 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1972 size_type n, value_type c) {
1973 Invariant checker(*this);
1974 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1975 fbstring_detail::podFill(pData, pData + n, c);
1979 template <typename E, class T, class A, class S>
1980 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1981 const basic_fbstring& str, const size_type pos, size_type n) {
1982 const size_type sz = str.size();
1983 enforce(pos <= sz, std::__throw_out_of_range, "");
1984 procrustes(n, sz - pos);
1985 return assign(str.data() + pos, n);
1988 template <typename E, class T, class A, class S>
1989 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1990 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1991 Invariant checker(*this);
1995 } else if (size() >= n) {
1996 // s can alias this, we need to use podMove.
1997 fbstring_detail::podMove(s, s + n, store_.mutableData());
1998 store_.shrink(size() - n);
1999 FBSTRING_ASSERT(size() == n);
2001 // If n is larger than size(), s cannot alias this string's
2004 // Do not use exponential growth here: assign() should be tight,
2005 // to mirror the behavior of the equivalent constructor.
2006 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
2009 FBSTRING_ASSERT(size() == n);
2013 #ifndef _LIBSTDCXX_FBSTRING
2014 template <typename E, class T, class A, class S>
2015 inline typename basic_fbstring<E, T, A, S>::istream_type&
2016 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
2017 Invariant checker(*this);
2022 size_t avail = capacity() - size;
2023 // fbstring has 1 byte extra capacity for the null terminator,
2024 // and getline null-terminates the read string.
2025 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2026 size += is.gcount();
2028 if (is.bad() || is.eof() || !is.fail()) {
2029 // Done by either failure, end of file, or normal read.
2030 if (!is.bad() && !is.eof()) {
2031 --size; // gcount() also accounts for the delimiter.
2037 FBSTRING_ASSERT(size == this->size());
2038 FBSTRING_ASSERT(size == capacity());
2039 // Start at minimum allocation 63 + terminator = 64.
2040 reserve(std::max<size_t>(63, 3 * size / 2));
2041 // Clear the error so we can continue reading.
2048 template <typename E, class T, class A, class S>
2049 inline typename basic_fbstring<E, T, A, S>::size_type
2050 basic_fbstring<E, T, A, S>::find(
2051 const value_type* needle, const size_type pos, const size_type nsize)
2053 auto const size = this->size();
2054 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2055 // that nsize + pos does not wrap around.
2056 if (nsize + pos > size || nsize + pos < pos) {
2063 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2064 // the last characters first
2065 auto const haystack = data();
2066 auto const nsize_1 = nsize - 1;
2067 auto const lastNeedle = needle[nsize_1];
2069 // Boyer-Moore skip value for the last char in the needle. Zero is
2070 // not a valid value; skip will be computed the first time it's
2074 const E* i = haystack + pos;
2075 auto iEnd = haystack + size - nsize_1;
2078 // Boyer-Moore: match the last element in the needle
2079 while (i[nsize_1] != lastNeedle) {
2085 // Here we know that the last char matches
2086 // Continue in pedestrian mode
2087 for (size_t j = 0;;) {
2088 FBSTRING_ASSERT(j < nsize);
2089 if (i[j] != needle[j]) {
2090 // Not found, we can skip
2091 // Compute the skip value lazily
2094 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2101 // Check if done searching
2104 return i - haystack;
2111 template <typename E, class T, class A, class S>
2112 inline typename basic_fbstring<E, T, A, S>::iterator
2113 basic_fbstring<E, T, A, S>::insertImplDiscr(
2114 const_iterator i, size_type n, value_type c, std::true_type) {
2115 Invariant checker(*this);
2117 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2118 const size_type pos = i - cbegin();
2120 auto oldSize = size();
2121 store_.expandNoinit(n, /* expGrowth = */ true);
2123 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2124 fbstring_detail::podFill(b + pos, b + pos + n, c);
2129 template <typename E, class T, class A, class S>
2130 template <class InputIter>
2131 inline typename basic_fbstring<E, T, A, S>::iterator
2132 basic_fbstring<E, T, A, S>::insertImplDiscr(
2133 const_iterator i, InputIter b, InputIter e, std::false_type) {
2135 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2138 template <typename E, class T, class A, class S>
2139 template <class FwdIterator>
2140 inline typename basic_fbstring<E, T, A, S>::iterator
2141 basic_fbstring<E, T, A, S>::insertImpl(
2145 std::forward_iterator_tag) {
2146 Invariant checker(*this);
2148 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2149 const size_type pos = i - cbegin();
2150 auto n = std::distance(s1, s2);
2151 FBSTRING_ASSERT(n >= 0);
2153 auto oldSize = size();
2154 store_.expandNoinit(n, /* expGrowth = */ true);
2156 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2157 std::copy(s1, s2, b + pos);
2162 template <typename E, class T, class A, class S>
2163 template <class InputIterator>
2164 inline typename basic_fbstring<E, T, A, S>::iterator
2165 basic_fbstring<E, T, A, S>::insertImpl(
2169 std::input_iterator_tag) {
2170 const auto pos = i - cbegin();
2171 basic_fbstring temp(cbegin(), i);
2172 for (; b != e; ++b) {
2175 temp.append(i, cend());
2177 return begin() + pos;
2180 template <typename E, class T, class A, class S>
2181 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2184 const value_type* s,
2186 std::integral_constant<int, 2>) {
2187 FBSTRING_ASSERT(i1 <= i2);
2188 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2189 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2190 return replace(i1, i2, s, s + n);
2193 template <typename E, class T, class A, class S>
2194 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2199 std::integral_constant<int, 1>) {
2200 const size_type n1 = i2 - i1;
2202 std::fill(i1, i1 + n2, c);
2205 std::fill(i1, i2, c);
2206 insert(i2, n2 - n1, c);
2208 FBSTRING_ASSERT(isSane());
2212 template <typename E, class T, class A, class S>
2213 template <class InputIter>
2214 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2219 std::integral_constant<int, 0>) {
2220 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2221 replaceImpl(i1, i2, b, e, Cat());
2225 template <typename E, class T, class A, class S>
2226 template <class FwdIterator>
2227 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2228 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2229 std::less_equal<const value_type*> le{};
2230 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2234 // Aliased replace, copy to new string
2235 basic_fbstring temp;
2236 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2237 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2242 template <typename E, class T, class A, class S>
2243 template <class FwdIterator>
2244 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2249 std::forward_iterator_tag) {
2250 Invariant checker(*this);
2252 // Handle aliased replace
2253 using Sel = std::integral_constant<
2255 std::is_same<FwdIterator, iterator>::value ||
2256 std::is_same<FwdIterator, const_iterator>::value>;
2257 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2261 auto const n1 = i2 - i1;
2262 FBSTRING_ASSERT(n1 >= 0);
2263 auto const n2 = std::distance(s1, s2);
2264 FBSTRING_ASSERT(n2 >= 0);
2268 std::copy(s1, s2, i1);
2272 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2275 FBSTRING_ASSERT(isSane());
2278 template <typename E, class T, class A, class S>
2279 template <class InputIterator>
2280 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2285 std::input_iterator_tag) {
2286 basic_fbstring temp(begin(), i1);
2287 temp.append(b, e).append(i2, end());
2291 template <typename E, class T, class A, class S>
2292 inline typename basic_fbstring<E, T, A, S>::size_type
2293 basic_fbstring<E, T, A, S>::rfind(
2294 const value_type* s, size_type pos, size_type n) const {
2298 pos = std::min(pos, length() - n);
2303 const_iterator i(begin() + pos);
2305 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2315 template <typename E, class T, class A, class S>
2316 inline typename basic_fbstring<E, T, A, S>::size_type
2317 basic_fbstring<E, T, A, S>::find_first_of(
2318 const value_type* s, size_type pos, size_type n) const {
2319 if (pos > length() || n == 0) {
2322 const_iterator i(begin() + pos), finish(end());
2323 for (; i != finish; ++i) {
2324 if (traits_type::find(s, n, *i) != 0) {
2331 template <typename E, class T, class A, class S>
2332 inline typename basic_fbstring<E, T, A, S>::size_type
2333 basic_fbstring<E, T, A, S>::find_last_of(
2334 const value_type* s, size_type pos, size_type n) const {
2335 if (!empty() && n > 0) {
2336 pos = std::min(pos, length() - 1);
2337 const_iterator i(begin() + pos);
2339 if (traits_type::find(s, n, *i) != 0) {
2350 template <typename E, class T, class A, class S>
2351 inline typename basic_fbstring<E, T, A, S>::size_type
2352 basic_fbstring<E, T, A, S>::find_first_not_of(
2353 const value_type* s, size_type pos, size_type n) const {
2354 if (pos < length()) {
2355 const_iterator i(begin() + pos), finish(end());
2356 for (; i != finish; ++i) {
2357 if (traits_type::find(s, n, *i) == 0) {
2365 template <typename E, class T, class A, class S>
2366 inline typename basic_fbstring<E, T, A, S>::size_type
2367 basic_fbstring<E, T, A, S>::find_last_not_of(
2368 const value_type* s, size_type pos, size_type n) const {
2369 if (!this->empty()) {
2370 pos = std::min(pos, size() - 1);
2371 const_iterator i(begin() + pos);
2373 if (traits_type::find(s, n, *i) == 0) {
2384 // non-member functions
2386 template <typename E, class T, class A, class S>
2388 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2389 const basic_fbstring<E, T, A, S>& rhs) {
2391 basic_fbstring<E, T, A, S> result;
2392 result.reserve(lhs.size() + rhs.size());
2393 result.append(lhs).append(rhs);
2394 return std::move(result);
2398 template <typename E, class T, class A, class S>
2400 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2401 const basic_fbstring<E, T, A, S>& rhs) {
2402 return std::move(lhs.append(rhs));
2406 template <typename E, class T, class A, class S>
2408 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2409 basic_fbstring<E, T, A, S>&& rhs) {
2410 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2411 // Good, at least we don't need to reallocate
2412 return std::move(rhs.insert(0, lhs));
2414 // Meh, no go. Forward to operator+(const&, const&).
2415 auto const& rhsC = rhs;
2420 template <typename E, class T, class A, class S>
2422 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2423 basic_fbstring<E, T, A, S>&& rhs) {
2424 return std::move(lhs.append(rhs));
2428 template <typename E, class T, class A, class S>
2430 basic_fbstring<E, T, A, S> operator+(
2432 const basic_fbstring<E, T, A, S>& rhs) {
2434 basic_fbstring<E, T, A, S> result;
2435 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2436 result.reserve(len + rhs.size());
2437 result.append(lhs, len).append(rhs);
2442 template <typename E, class T, class A, class S>
2444 basic_fbstring<E, T, A, S> operator+(
2446 basic_fbstring<E, T, A, S>&& rhs) {
2448 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2449 if (rhs.capacity() >= len + rhs.size()) {
2450 // Good, at least we don't need to reallocate
2451 rhs.insert(rhs.begin(), lhs, lhs + len);
2454 // Meh, no go. Do it by hand since we have len already.
2455 basic_fbstring<E, T, A, S> result;
2456 result.reserve(len + rhs.size());
2457 result.append(lhs, len).append(rhs);
2462 template <typename E, class T, class A, class S>
2464 basic_fbstring<E, T, A, S> operator+(
2466 const basic_fbstring<E, T, A, S>& rhs) {
2468 basic_fbstring<E, T, A, S> result;
2469 result.reserve(1 + rhs.size());
2470 result.push_back(lhs);
2476 template <typename E, class T, class A, class S>
2478 basic_fbstring<E, T, A, S> operator+(
2480 basic_fbstring<E, T, A, S>&& rhs) {
2482 if (rhs.capacity() > rhs.size()) {
2483 // Good, at least we don't need to reallocate
2484 rhs.insert(rhs.begin(), lhs);
2487 // Meh, no go. Forward to operator+(E, const&).
2488 auto const& rhsC = rhs;
2493 template <typename E, class T, class A, class S>
2495 basic_fbstring<E, T, A, S> operator+(
2496 const basic_fbstring<E, T, A, S>& lhs,
2499 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2500 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2502 basic_fbstring<E, T, A, S> result;
2503 const size_type len = traits_type::length(rhs);
2504 result.reserve(lhs.size() + len);
2505 result.append(lhs).append(rhs, len);
2509 // C++11 21.4.8.1/10
2510 template <typename E, class T, class A, class S>
2512 basic_fbstring<E, T, A, S> operator+(
2513 basic_fbstring<E, T, A, S>&& lhs,
2516 return std::move(lhs += rhs);
2519 // C++11 21.4.8.1/11
2520 template <typename E, class T, class A, class S>
2522 basic_fbstring<E, T, A, S> operator+(
2523 const basic_fbstring<E, T, A, S>& lhs,
2526 basic_fbstring<E, T, A, S> result;
2527 result.reserve(lhs.size() + 1);
2529 result.push_back(rhs);
2533 // C++11 21.4.8.1/12
2534 template <typename E, class T, class A, class S>
2536 basic_fbstring<E, T, A, S> operator+(
2537 basic_fbstring<E, T, A, S>&& lhs,
2540 return std::move(lhs += rhs);
2543 template <typename E, class T, class A, class S>
2545 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2546 const basic_fbstring<E, T, A, S>& rhs) {
2547 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2549 template <typename E, class T, class A, class S>
2551 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2552 const basic_fbstring<E, T, A, S>& rhs) {
2553 return rhs == lhs; }
2555 template <typename E, class T, class A, class S>
2557 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2558 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2559 return lhs.compare(rhs) == 0; }
2561 template <typename E, class T, class A, class S>
2563 bool operator!=(const basic_fbstring<E, T, A, S>& 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 typename basic_fbstring<E, T, A, S>::value_type* lhs,
2570 const basic_fbstring<E, T, A, S>& 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 typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2577 return !(lhs == rhs); }
2579 template <typename E, class T, class A, class S>
2581 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2582 const basic_fbstring<E, T, A, S>& rhs) {
2583 return lhs.compare(rhs) < 0; }
2585 template <typename E, class T, class A, class S>
2587 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2588 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2589 return lhs.compare(rhs) < 0; }
2591 template <typename E, class T, class A, class S>
2593 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2594 const basic_fbstring<E, T, A, S>& rhs) {
2595 return rhs.compare(lhs) > 0; }
2597 template <typename E, class T, class A, class S>
2599 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2600 const basic_fbstring<E, T, A, S>& rhs) {
2603 template <typename E, class T, class A, class S>
2605 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2606 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2609 template <typename E, class T, class A, class S>
2611 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2612 const basic_fbstring<E, T, A, S>& rhs) {
2615 template <typename E, class T, class A, class S>
2617 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2618 const basic_fbstring<E, T, A, S>& rhs) {
2619 return !(rhs < lhs); }
2621 template <typename E, class T, class A, class S>
2623 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2624 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2625 return !(rhs < lhs); }
2627 template <typename E, class T, class A, class S>
2629 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2630 const basic_fbstring<E, T, A, S>& rhs) {
2631 return !(rhs < lhs); }
2633 template <typename E, class T, class A, class S>
2635 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2636 const basic_fbstring<E, T, A, S>& rhs) {
2637 return !(lhs < rhs); }
2639 template <typename E, class T, class A, class S>
2641 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2642 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2643 return !(lhs < rhs); }
2645 template <typename E, class T, class A, class S>
2647 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2648 const basic_fbstring<E, T, A, S>& rhs) {
2649 return !(lhs < rhs);
2653 template <typename E, class T, class A, class S>
2654 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2658 // TODO: make this faster.
2659 template <typename E, class T, class A, class S>
2662 typename basic_fbstring<E, T, A, S>::value_type,
2663 typename basic_fbstring<E, T, A, S>::traits_type>&
2665 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2666 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2667 basic_fbstring<E, T, A, S>& str) {
2668 typedef std::basic_istream<
2669 typename basic_fbstring<E, T, A, S>::value_type,
2670 typename basic_fbstring<E, T, A, S>::traits_type>
2672 typename _istream_type::sentry sentry(is);
2673 size_t extracted = 0;
2674 auto err = _istream_type::goodbit;
2676 auto n = is.width();
2681 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2682 if (got == T::eof()) {
2683 err |= _istream_type::eofbit;
2691 got = is.rdbuf()->snextc();
2695 err |= _istream_type::failbit;
2703 template <typename E, class T, class A, class S>
2705 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2706 typename basic_fbstring<E, T, A, S>::traits_type>&
2708 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2709 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2710 const basic_fbstring<E, T, A, S>& str) {
2712 typedef std::basic_ostream<
2713 typename basic_fbstring<E, T, A, S>::value_type,
2714 typename basic_fbstring<E, T, A, S>::traits_type>
2716 typename _ostream_type::sentry _s(os);
2718 typedef std::ostreambuf_iterator<
2719 typename basic_fbstring<E, T, A, S>::value_type,
2720 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2721 size_t __len = str.size();
2723 (os.flags() & _ostream_type::adjustfield) == _ostream_type::left;
2724 if (__pad_and_output(_Ip(os),
2726 __left ? str.data() + __len : str.data(),
2729 os.fill()).failed()) {
2730 os.setstate(_ostream_type::badbit | _ostream_type::failbit);
2733 #elif defined(_MSC_VER)
2734 typedef decltype(os.precision()) streamsize;
2735 // MSVC doesn't define __ostream_insert
2736 os.write(str.data(), static_cast<streamsize>(str.size()));
2738 std::__ostream_insert(os, str.data(), str.size());
2743 template <typename E1, class T, class A, class S>
2744 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2745 basic_fbstring<E1, T, A, S>::npos;
2747 #ifndef _LIBSTDCXX_FBSTRING
2748 // basic_string compatibility routines
2750 template <typename E, class T, class A, class S, class A2>
2751 inline bool operator==(
2752 const basic_fbstring<E, T, A, S>& lhs,
2753 const std::basic_string<E, T, A2>& rhs) {
2754 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2757 template <typename E, class T, class A, class S, class A2>
2758 inline bool operator==(
2759 const std::basic_string<E, T, A2>& lhs,
2760 const basic_fbstring<E, T, A, S>& rhs) {
2764 template <typename E, class T, class A, class S, class A2>
2765 inline bool operator!=(
2766 const basic_fbstring<E, T, A, S>& lhs,
2767 const std::basic_string<E, T, A2>& rhs) {
2768 return !(lhs == rhs);
2771 template <typename E, class T, class A, class S, class A2>
2772 inline bool operator!=(
2773 const std::basic_string<E, T, A2>& lhs,
2774 const basic_fbstring<E, T, A, S>& rhs) {
2775 return !(lhs == rhs);
2778 template <typename E, class T, class A, class S, class A2>
2779 inline bool operator<(
2780 const basic_fbstring<E, T, A, S>& lhs,
2781 const std::basic_string<E, T, A2>& rhs) {
2782 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0;
2785 template <typename E, class T, class A, class S, class A2>
2786 inline bool operator>(
2787 const basic_fbstring<E, T, A, S>& lhs,
2788 const std::basic_string<E, T, A2>& rhs) {
2789 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) > 0;
2792 template <typename E, class T, class A, class S, class A2>
2793 inline bool operator<(
2794 const std::basic_string<E, T, A2>& lhs,
2795 const basic_fbstring<E, T, A, S>& rhs) {
2799 template <typename E, class T, class A, class S, class A2>
2800 inline bool operator>(
2801 const std::basic_string<E, T, A2>& lhs,
2802 const basic_fbstring<E, T, A, S>& rhs) {
2806 template <typename E, class T, class A, class S, class A2>
2807 inline bool operator<=(
2808 const basic_fbstring<E, T, A, S>& lhs,
2809 const std::basic_string<E, T, A2>& rhs) {
2810 return !(lhs > rhs);
2813 template <typename E, class T, class A, class S, class A2>
2814 inline bool operator>=(
2815 const basic_fbstring<E, T, A, S>& lhs,
2816 const std::basic_string<E, T, A2>& rhs) {
2817 return !(lhs < rhs);
2820 template <typename E, class T, class A, class S, class A2>
2821 inline bool operator<=(
2822 const std::basic_string<E, T, A2>& lhs,
2823 const basic_fbstring<E, T, A, S>& rhs) {
2824 return !(lhs > rhs);
2827 template <typename E, class T, class A, class S, class A2>
2828 inline bool operator>=(
2829 const std::basic_string<E, T, A2>& lhs,
2830 const basic_fbstring<E, T, A, S>& rhs) {
2831 return !(lhs < rhs);
2834 #if !defined(_LIBSTDCXX_FBSTRING)
2835 typedef basic_fbstring<char> fbstring;
2838 // fbstring is relocatable
2839 template <class T, class R, class A, class S>
2840 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2843 _GLIBCXX_END_NAMESPACE_VERSION
2846 } // namespace folly
2848 #ifndef _LIBSTDCXX_FBSTRING
2850 // Hash functions to make fbstring usable with e.g. hash_map
2852 // Handle interaction with different C++ standard libraries, which
2853 // expect these types to be in different namespaces.
2855 #define FOLLY_FBSTRING_HASH1(T) \
2857 struct hash< ::folly::basic_fbstring<T>> { \
2858 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2859 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2863 // The C++11 standard says that these four are defined
2864 #define FOLLY_FBSTRING_HASH \
2865 FOLLY_FBSTRING_HASH1(char) \
2866 FOLLY_FBSTRING_HASH1(char16_t) \
2867 FOLLY_FBSTRING_HASH1(char32_t) \
2868 FOLLY_FBSTRING_HASH1(wchar_t)
2876 #if FOLLY_HAVE_DEPRECATED_ASSOC
2877 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2878 namespace __gnu_cxx {
2882 } // namespace __gnu_cxx
2883 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2884 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2886 #undef FOLLY_FBSTRING_HASH
2887 #undef FOLLY_FBSTRING_HASH1
2889 #endif // _LIBSTDCXX_FBSTRING
2891 #pragma GCC diagnostic pop
2893 #undef FBSTRING_DISABLE_SSO
2894 #undef FBSTRING_SANITIZE_ADDRESS
2896 #undef FBSTRING_LIKELY
2897 #undef FBSTRING_UNLIKELY
2898 #undef FBSTRING_ASSERT