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 /*static*/ if (sizeof(T) == 1) {
141 memset(b, c, size_t(e - b));
143 auto const ee = b + ((e - b) & ~7u);
144 for (; b != ee; b += 8) {
155 for (; b != e; ++b) {
162 * Lightly structured memcpy, simplifies copying PODs and introduces
163 * some asserts. Unfortunately using this function may cause
164 * measurable overhead (presumably because it adjusts from a begin/end
165 * convention to a pointer/size convention, so it does some extra
166 * arithmetic even though the caller might have done the inverse
167 * adaptation outside).
170 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
171 FBSTRING_ASSERT(b != nullptr);
172 FBSTRING_ASSERT(e != nullptr);
173 FBSTRING_ASSERT(d != nullptr);
174 FBSTRING_ASSERT(e >= b);
175 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
176 memcpy(d, b, (e - b) * sizeof(Pod));
180 * Lightly structured memmove, simplifies copying PODs and introduces
184 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
185 FBSTRING_ASSERT(e >= b);
186 memmove(d, b, (e - b) * sizeof(*b));
190 #if defined(__GNUC__) // Clang also defines __GNUC__
191 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
192 #elif defined(_MSC_VER)
193 # define FBSTRING_ALWAYS_INLINE __forceinline
195 # define FBSTRING_ALWAYS_INLINE inline
198 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
199 #if defined(__GNUC__) // Clang also defines __GNUC__
200 __builtin_unreachable();
201 #elif defined(_MSC_VER)
204 // Well, it's better than nothing.
209 } // namespace fbstring_detail
212 * Defines a special acquisition method for constructing fbstring
213 * objects. AcquireMallocatedString means that the user passes a
214 * pointer to a malloc-allocated string that the fbstring object will
217 enum class AcquireMallocatedString {};
220 * fbstring_core_model is a mock-up type that defines all required
221 * signatures of a fbstring core. The fbstring class itself uses such
222 * a core object to implement all of the numerous member functions
223 * required by the standard.
225 * If you want to define a new core, copy the definition below and
226 * implement the primitives. Then plug the core into basic_fbstring as
227 * a template argument.
229 template <class Char>
230 class fbstring_core_model {
232 fbstring_core_model();
233 fbstring_core_model(const fbstring_core_model &);
234 ~fbstring_core_model();
235 // Returns a pointer to string's buffer (currently only contiguous
236 // strings are supported). The pointer is guaranteed to be valid
237 // until the next call to a non-const member function.
238 const Char * data() const;
239 // Much like data(), except the string is prepared to support
240 // character-level changes. This call is a signal for
241 // e.g. reference-counted implementation to fork the data. The
242 // pointer is guaranteed to be valid until the next call to a
243 // non-const member function.
245 // Returns a pointer to string's buffer and guarantees that a
246 // readable '\0' lies right after the buffer. The pointer is
247 // guaranteed to be valid until the next call to a non-const member
249 const Char * c_str() const;
250 // Shrinks the string by delta characters. Asserts that delta <=
252 void shrink(size_t delta);
253 // Expands the string by delta characters (i.e. after this call
254 // size() will report the old size() plus delta) but without
255 // initializing the expanded region. The expanded region is
256 // zero-terminated. Returns a pointer to the memory to be
257 // initialized (the beginning of the expanded portion). The caller
258 // is expected to fill the expanded area appropriately.
259 // If expGrowth is true, exponential growth is guaranteed.
260 // It is not guaranteed not to reallocate even if size() + delta <
261 // capacity(), so all references to the buffer are invalidated.
262 Char* expandNoinit(size_t delta, bool expGrowth);
263 // Expands the string by one character and sets the last character
265 void push_back(Char c);
266 // Returns the string's size.
268 // Returns the string's capacity, i.e. maximum size that the string
269 // can grow to without reallocation. Note that for reference counted
270 // strings that's technically a lie - even assigning characters
271 // within the existing size would cause a reallocation.
272 size_t capacity() const;
273 // Returns true if the data underlying the string is actually shared
274 // across multiple strings (in a refcounted fashion).
275 bool isShared() const;
276 // Makes sure that at least minCapacity characters are available for
277 // the string without reallocation. For reference-counted strings,
278 // it should fork the data even if minCapacity < size().
279 void reserve(size_t minCapacity);
282 fbstring_core_model& operator=(const fbstring_core_model &);
287 * This is the core of the string. The code should work on 32- and
288 * 64-bit and both big- and little-endianan architectures with any
291 * The storage is selected as follows (assuming we store one-byte
292 * characters on a 64-bit machine): (a) "small" strings between 0 and
293 * 23 chars are stored in-situ without allocation (the rightmost byte
294 * stores the size); (b) "medium" strings from 24 through 254 chars
295 * are stored in malloc-allocated memory that is copied eagerly; (c)
296 * "large" strings of 255 chars and above are stored in a similar
297 * structure as medium arrays, except that the string is
298 * reference-counted and copied lazily. the reference count is
299 * allocated right before the character array.
301 * The discriminator between these three strategies sits in two
302 * bits of the rightmost char of the storage. If neither is set, then the
303 * string is small (and its length sits in the lower-order bits on
304 * little-endian or the high-order bits on big-endian of that
305 * rightmost character). If the MSb is set, the string is medium width.
306 * If the second MSb is set, then the string is large. On little-endian,
307 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
308 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
309 * and big-endian fbstring_core equivalent with merely different ops used
310 * to extract capacity/category.
312 template <class Char> class fbstring_core {
314 // It's MSVC, so we just have to guess ... and allow an override
316 # ifdef FOLLY_ENDIAN_BE
317 static constexpr auto kIsLittleEndian = false;
319 static constexpr auto kIsLittleEndian = true;
322 static constexpr auto kIsLittleEndian =
323 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
326 fbstring_core() noexcept { reset(); }
328 fbstring_core(const fbstring_core & rhs) {
329 FBSTRING_ASSERT(&rhs != this);
330 switch (rhs.category()) {
331 case Category::isSmall:
334 case Category::isMedium:
337 case Category::isLarge:
341 fbstring_detail::assume_unreachable();
343 FBSTRING_ASSERT(size() == rhs.size());
344 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
347 fbstring_core(fbstring_core&& goner) noexcept {
350 // Clean goner's carcass
354 fbstring_core(const Char *const data,
356 bool disableSSO = FBSTRING_DISABLE_SSO) {
357 if (!disableSSO && size <= maxSmallSize) {
358 initSmall(data, size);
359 } else if (size <= maxMediumSize) {
360 initMedium(data, size);
362 initLarge(data, size);
364 FBSTRING_ASSERT(this->size() == size);
366 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
369 ~fbstring_core() noexcept {
370 if (category() == Category::isSmall) {
373 destroyMediumLarge();
376 // Snatches a previously mallocated string. The parameter "size"
377 // is the size of the string, and the parameter "allocatedSize"
378 // is the size of the mallocated block. The string must be
379 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
381 // So if you want a 2-character string, pass malloc(3) as "data",
382 // pass 2 as "size", and pass 3 as "allocatedSize".
383 fbstring_core(Char * const data,
385 const size_t allocatedSize,
386 AcquireMallocatedString) {
388 FBSTRING_ASSERT(allocatedSize >= size + 1);
389 FBSTRING_ASSERT(data[size] == '\0');
390 // Use the medium string storage
393 // Don't forget about null terminator
394 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
396 // No need for the memory
402 // swap below doesn't test whether &rhs == this (and instead
403 // potentially does extra work) on the premise that the rarity of
404 // that situation actually makes the check more expensive than is
406 void swap(fbstring_core & rhs) {
412 // In C++11 data() and c_str() are 100% equivalent.
413 const Char * data() const {
417 Char* mutableData() {
418 switch (category()) {
419 case Category::isSmall:
421 case Category::isMedium:
423 case Category::isLarge:
424 return mutableDataLarge();
426 fbstring_detail::assume_unreachable();
429 const Char* c_str() const {
430 const Char* ptr = ml_.data_;
431 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
432 ptr = (category() == Category::isSmall) ? small_ : ptr;
436 void shrink(const size_t delta) {
437 if (category() == Category::isSmall) {
439 } else if (category() == Category::isMedium ||
440 RefCounted::refs(ml_.data_) == 1) {
447 FOLLY_MALLOC_NOINLINE
448 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
449 switch (category()) {
450 case Category::isSmall:
451 reserveSmall(minCapacity, disableSSO);
453 case Category::isMedium:
454 reserveMedium(minCapacity);
456 case Category::isLarge:
457 reserveLarge(minCapacity);
460 fbstring_detail::assume_unreachable();
462 FBSTRING_ASSERT(capacity() >= minCapacity);
467 bool expGrowth = false,
468 bool disableSSO = FBSTRING_DISABLE_SSO);
470 void push_back(Char c) {
471 *expandNoinit(1, /* expGrowth = */ true) = c;
474 size_t size() const {
475 size_t ret = ml_.size_;
476 /* static */ if (kIsLittleEndian) {
477 // We can save a couple instructions, because the category is
478 // small iff the last char, as unsigned, is <= maxSmallSize.
479 typedef typename std::make_unsigned<Char>::type UChar;
480 auto maybeSmallSize = size_t(maxSmallSize) -
481 size_t(static_cast<UChar>(small_[maxSmallSize]));
482 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
483 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
485 ret = (category() == Category::isSmall) ? smallSize() : ret;
490 size_t capacity() const {
491 switch (category()) {
492 case Category::isSmall:
494 case Category::isLarge:
495 // For large-sized strings, a multi-referenced chunk has no
496 // available capacity. This is because any attempt to append
497 // data would trigger a new allocation.
498 if (RefCounted::refs(ml_.data_) > 1) {
503 return ml_.capacity();
506 bool isShared() const {
507 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
512 fbstring_core & operator=(const fbstring_core & rhs);
518 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
519 auto const c = category();
520 FBSTRING_ASSERT(c != Category::isSmall);
521 if (c == Category::isMedium) {
524 RefCounted::decrementRefs(ml_.data_);
529 std::atomic<size_t> refCount_;
532 constexpr static size_t getDataOffset() {
533 return offsetof(RefCounted, data_);
536 static RefCounted * fromData(Char * p) {
537 return static_cast<RefCounted*>(static_cast<void*>(
538 static_cast<unsigned char*>(static_cast<void*>(p)) -
542 static size_t refs(Char * p) {
543 return fromData(p)->refCount_.load(std::memory_order_acquire);
546 static void incrementRefs(Char * p) {
547 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
550 static void decrementRefs(Char * p) {
551 auto const dis = fromData(p);
552 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
553 FBSTRING_ASSERT(oldcnt > 0);
559 static RefCounted * create(size_t * size) {
560 const size_t allocSize =
561 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
562 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
563 result->refCount_.store(1, std::memory_order_release);
564 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
568 static RefCounted * create(const Char * data, size_t * size) {
569 const size_t effectiveSize = *size;
570 auto result = create(size);
571 if (FBSTRING_LIKELY(effectiveSize > 0)) {
572 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
577 static RefCounted * reallocate(Char *const data,
578 const size_t currentSize,
579 const size_t currentCapacity,
580 size_t * newCapacity) {
581 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
582 const size_t allocNewCapacity =
583 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
584 auto const dis = fromData(data);
585 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
586 auto result = static_cast<RefCounted*>(smartRealloc(
588 getDataOffset() + (currentSize + 1) * sizeof(Char),
589 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
591 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
592 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
597 typedef uint8_t category_type;
599 enum class Category : category_type {
601 isMedium = kIsLittleEndian ? 0x80 : 0x2,
602 isLarge = kIsLittleEndian ? 0x40 : 0x1,
605 Category category() const {
606 // works for both big-endian and little-endian
607 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
615 size_t capacity() const {
616 return kIsLittleEndian
617 ? capacity_ & capacityExtractMask
621 void setCapacity(size_t cap, Category cat) {
622 capacity_ = kIsLittleEndian
623 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
624 : (cap << 2) | static_cast<size_t>(cat);
629 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
630 Char small_[sizeof(MediumLarge) / sizeof(Char)];
634 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
635 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
636 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
637 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
638 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
639 constexpr static size_t capacityExtractMask = kIsLittleEndian
640 ? ~(size_t(categoryExtractMask) << kCategoryShift)
643 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
644 "Corrupt memory layout for fbstring.");
646 size_t smallSize() const {
647 FBSTRING_ASSERT(category() == Category::isSmall);
648 constexpr auto shift = kIsLittleEndian ? 0 : 2;
649 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
650 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
651 return static_cast<size_t>(maxSmallSize) - smallShifted;
654 void setSmallSize(size_t s) {
655 // Warning: this should work with uninitialized strings too,
656 // so don't assume anything about the previous value of
657 // small_[maxSmallSize].
658 FBSTRING_ASSERT(s <= maxSmallSize);
659 constexpr auto shift = kIsLittleEndian ? 0 : 2;
660 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
662 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
665 void copySmall(const fbstring_core&);
666 void copyMedium(const fbstring_core&);
667 void copyLarge(const fbstring_core&);
669 void initSmall(const Char* data, size_t size);
670 void initMedium(const Char* data, size_t size);
671 void initLarge(const Char* data, size_t size);
673 void reserveSmall(size_t minCapacity, bool disableSSO);
674 void reserveMedium(size_t minCapacity);
675 void reserveLarge(size_t minCapacity);
677 void shrinkSmall(size_t delta);
678 void shrinkMedium(size_t delta);
679 void shrinkLarge(size_t delta);
681 void unshare(size_t minCapacity = 0);
682 Char* mutableDataLarge();
685 template <class Char>
686 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
687 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
689 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
690 "fbstring layout failure");
692 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
693 "fbstring layout failure");
694 // Just write the whole thing, don't look at details. In
695 // particular we need to copy capacity anyway because we want
696 // to set the size (don't forget that the last character,
697 // which stores a short string's length, is shared with the
698 // ml_.capacity field).
701 category() == Category::isSmall && this->size() == rhs.size());
704 template <class Char>
705 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
706 const fbstring_core& rhs) {
707 // Medium strings are copied eagerly. Don't forget to allocate
708 // one extra Char for the null terminator.
709 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
710 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
711 // Also copies terminator.
712 fbstring_detail::podCopy(
713 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
714 ml_.size_ = rhs.ml_.size_;
715 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
716 FBSTRING_ASSERT(category() == Category::isMedium);
719 template <class Char>
720 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
721 const fbstring_core& rhs) {
722 // Large strings are just refcounted
724 RefCounted::incrementRefs(ml_.data_);
725 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
728 // Small strings are bitblitted
729 template <class Char>
730 inline void fbstring_core<Char>::initSmall(
731 const Char* const data, const size_t size) {
732 // Layout is: Char* data_, size_t size_, size_t capacity_
734 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
735 "fbstring has unexpected size");
737 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
738 // sizeof(size_t) must be a power of 2
740 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
741 "fbstring size assumption violation");
743 // If data is aligned, use fast word-wise copying. Otherwise,
744 // use conservative memcpy.
745 // The word-wise path reads bytes which are outside the range of
746 // the string, and makes ASan unhappy, so we disable it when
747 // compiling with ASan.
748 #ifndef FBSTRING_SANITIZE_ADDRESS
749 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
750 const size_t byteSize = size * sizeof(Char);
751 constexpr size_t wordWidth = sizeof(size_t);
752 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
754 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
756 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
758 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
766 fbstring_detail::podCopy(data, data + size, small_);
772 template <class Char>
773 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
774 const Char* const data, const size_t size) {
775 // Medium strings are allocated normally. Don't forget to
776 // allocate one extra Char for the terminating null.
777 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
778 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
779 if (FBSTRING_LIKELY(size > 0)) {
780 fbstring_detail::podCopy(data, data + size, ml_.data_);
783 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
784 ml_.data_[size] = '\0';
787 template <class Char>
788 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
789 const Char* const data, const size_t size) {
790 // Large strings are allocated differently
791 size_t effectiveCapacity = size;
792 auto const newRC = RefCounted::create(data, &effectiveCapacity);
793 ml_.data_ = newRC->data_;
795 ml_.setCapacity(effectiveCapacity, Category::isLarge);
796 ml_.data_[size] = '\0';
799 template <class Char>
800 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
801 size_t minCapacity) {
802 FBSTRING_ASSERT(category() == Category::isLarge);
803 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
804 auto const newRC = RefCounted::create(&effectiveCapacity);
805 // If this fails, someone placed the wrong capacity in an
807 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
808 // Also copies terminator.
809 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
810 RefCounted::decrementRefs(ml_.data_);
811 ml_.data_ = newRC->data_;
812 ml_.setCapacity(effectiveCapacity, Category::isLarge);
813 // size_ remains unchanged.
816 template <class Char>
817 inline Char* fbstring_core<Char>::mutableDataLarge() {
818 FBSTRING_ASSERT(category() == Category::isLarge);
819 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
825 template <class Char>
826 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
827 size_t minCapacity) {
828 FBSTRING_ASSERT(category() == Category::isLarge);
829 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
830 // We must make it unique regardless; in-place reallocation is
831 // useless if the string is shared. In order to not surprise
832 // people, reserve the new block at current capacity or
833 // more. That way, a string's capacity never shrinks after a
835 unshare(minCapacity);
837 // String is not shared, so let's try to realloc (if needed)
838 if (minCapacity > ml_.capacity()) {
839 // Asking for more memory
840 auto const newRC = RefCounted::reallocate(
841 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
842 ml_.data_ = newRC->data_;
843 ml_.setCapacity(minCapacity, Category::isLarge);
845 FBSTRING_ASSERT(capacity() >= minCapacity);
849 template <class Char>
850 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
851 const size_t minCapacity) {
852 FBSTRING_ASSERT(category() == Category::isMedium);
853 // String is not shared
854 if (minCapacity <= ml_.capacity()) {
855 return; // nothing to do, there's enough room
857 if (minCapacity <= maxMediumSize) {
858 // Keep the string at medium size. Don't forget to allocate
859 // one extra Char for the terminating null.
860 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
861 // Also copies terminator.
862 ml_.data_ = static_cast<Char*>(smartRealloc(
864 (ml_.size_ + 1) * sizeof(Char),
865 (ml_.capacity() + 1) * sizeof(Char),
867 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
869 // Conversion from medium to large string
870 fbstring_core nascent;
871 // Will recurse to another branch of this function
872 nascent.reserve(minCapacity);
873 nascent.ml_.size_ = ml_.size_;
874 // Also copies terminator.
875 fbstring_detail::podCopy(
876 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
878 FBSTRING_ASSERT(capacity() >= minCapacity);
882 template <class Char>
883 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
884 size_t minCapacity, const bool disableSSO) {
885 FBSTRING_ASSERT(category() == Category::isSmall);
886 if (!disableSSO && minCapacity <= maxSmallSize) {
888 // Nothing to do, everything stays put
889 } else if (minCapacity <= maxMediumSize) {
891 // Don't forget to allocate one extra Char for the terminating null
892 auto const allocSizeBytes =
893 goodMallocSize((1 + minCapacity) * sizeof(Char));
894 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
895 auto const size = smallSize();
896 // Also copies terminator.
897 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
900 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
903 auto const newRC = RefCounted::create(&minCapacity);
904 auto const size = smallSize();
905 // Also copies terminator.
906 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
907 ml_.data_ = newRC->data_;
909 ml_.setCapacity(minCapacity, Category::isLarge);
910 FBSTRING_ASSERT(capacity() >= minCapacity);
914 template <class Char>
915 inline Char* fbstring_core<Char>::expandNoinit(
917 bool expGrowth, /* = false */
918 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
919 // Strategy is simple: make room, then change size
920 FBSTRING_ASSERT(capacity() >= size());
922 if (category() == Category::isSmall) {
925 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
930 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
934 if (FBSTRING_UNLIKELY(newSz > capacity())) {
935 // ensures not shared
936 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
939 FBSTRING_ASSERT(capacity() >= newSz);
940 // Category can't be small - we took care of that above
942 category() == Category::isMedium || category() == Category::isLarge);
944 ml_.data_[newSz] = '\0';
945 FBSTRING_ASSERT(size() == newSz);
946 return ml_.data_ + sz;
949 template <class Char>
950 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
951 // Check for underflow
952 FBSTRING_ASSERT(delta <= smallSize());
953 setSmallSize(smallSize() - delta);
956 template <class Char>
957 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
958 // Medium strings and unique large strings need no special
960 FBSTRING_ASSERT(ml_.size_ >= delta);
962 ml_.data_[ml_.size_] = '\0';
965 template <class Char>
966 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
967 FBSTRING_ASSERT(ml_.size_ >= delta);
968 // Shared large string, must make unique. This is because of the
969 // durn terminator must be written, which may trample the shared
972 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
974 // No need to write the terminator.
977 #ifndef _LIBSTDCXX_FBSTRING
979 * Dummy fbstring core that uses an actual std::string. This doesn't
980 * make any sense - it's just for testing purposes.
982 template <class Char>
983 class dummy_fbstring_core {
985 dummy_fbstring_core() {
987 dummy_fbstring_core(const dummy_fbstring_core& another)
988 : backend_(another.backend_) {
990 dummy_fbstring_core(const Char * s, size_t n)
993 void swap(dummy_fbstring_core & rhs) {
994 backend_.swap(rhs.backend_);
996 const Char * data() const {
997 return backend_.data();
999 Char* mutableData() {
1000 return const_cast<Char*>(backend_.data());
1002 void shrink(size_t delta) {
1003 FBSTRING_ASSERT(delta <= size());
1004 backend_.resize(size() - delta);
1006 Char* expandNoinit(size_t delta) {
1007 auto const sz = size();
1008 backend_.resize(size() + delta);
1009 return backend_.data() + sz;
1011 void push_back(Char c) {
1012 backend_.push_back(c);
1014 size_t size() const {
1015 return backend_.size();
1017 size_t capacity() const {
1018 return backend_.capacity();
1020 bool isShared() const {
1023 void reserve(size_t minCapacity) {
1024 backend_.reserve(minCapacity);
1028 std::basic_string<Char> backend_;
1030 #endif // !_LIBSTDCXX_FBSTRING
1033 * This is the basic_string replacement. For conformity,
1034 * basic_fbstring takes the same template parameters, plus the last
1035 * one which is the core.
1037 #ifdef _LIBSTDCXX_FBSTRING
1038 template <typename E, class T, class A, class Storage>
1040 template <typename E,
1041 class T = std::char_traits<E>,
1042 class A = std::allocator<E>,
1043 class Storage = fbstring_core<E> >
1045 class basic_fbstring {
1046 static void enforce(
1048 void (*throw_exc)(const char*),
1055 bool isSane() const {
1058 empty() == (size() == 0) &&
1059 empty() == (begin() == end()) &&
1060 size() <= max_size() &&
1061 capacity() <= max_size() &&
1062 size() <= capacity() &&
1063 begin()[size()] == '\0';
1067 Invariant& operator=(const Invariant&) = delete;
1068 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1069 FBSTRING_ASSERT(s_.isSane());
1071 ~Invariant() noexcept {
1072 FBSTRING_ASSERT(s_.isSane());
1076 const basic_fbstring& s_;
1081 typedef T traits_type;
1082 typedef typename traits_type::char_type value_type;
1083 typedef A allocator_type;
1084 typedef typename A::size_type size_type;
1085 typedef typename A::difference_type difference_type;
1087 typedef typename A::reference reference;
1088 typedef typename A::const_reference const_reference;
1089 typedef typename A::pointer pointer;
1090 typedef typename A::const_pointer const_pointer;
1092 typedef E* iterator;
1093 typedef const E* const_iterator;
1094 typedef std::reverse_iterator<iterator
1095 #ifdef NO_ITERATOR_TRAITS
1099 typedef std::reverse_iterator<const_iterator
1100 #ifdef NO_ITERATOR_TRAITS
1103 > const_reverse_iterator;
1105 static constexpr size_type npos = size_type(-1);
1106 typedef std::true_type IsRelocatable;
1109 static void procrustes(size_type& n, size_type nmax) {
1115 static size_type traitsLength(const value_type* s);
1118 // C++11 21.4.2 construct/copy/destroy
1120 // Note: while the following two constructors can be (and previously were)
1121 // collapsed into one constructor written this way:
1123 // explicit basic_fbstring(const A& a = A()) noexcept { }
1125 // This can cause Clang (at least version 3.7) to fail with the error:
1126 // "chosen constructor is explicit in copy-initialization ...
1127 // in implicit initialization of field '(x)' with omitted initializer"
1129 // if used in a struct which is default-initialized. Hence the split into
1130 // these two separate constructors.
1132 basic_fbstring() noexcept : basic_fbstring(A()) {
1135 explicit basic_fbstring(const A&) noexcept {
1138 basic_fbstring(const basic_fbstring& str)
1139 : store_(str.store_) {
1143 basic_fbstring(basic_fbstring&& goner) noexcept
1144 : store_(std::move(goner.store_)) {
1147 #ifndef _LIBSTDCXX_FBSTRING
1148 // This is defined for compatibility with std::string
1149 /* implicit */ basic_fbstring(const std::string& str)
1150 : store_(str.data(), str.size()) {
1154 basic_fbstring(const basic_fbstring& str,
1157 const A& /* a */ = A()) {
1158 assign(str, pos, n);
1161 FOLLY_MALLOC_NOINLINE
1162 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1163 : store_(s, traitsLength(s)) {}
1165 FOLLY_MALLOC_NOINLINE
1166 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1170 FOLLY_MALLOC_NOINLINE
1171 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1172 auto const pData = store_.expandNoinit(n);
1173 fbstring_detail::podFill(pData, pData + n, c);
1176 template <class InIt>
1177 FOLLY_MALLOC_NOINLINE basic_fbstring(
1180 typename std::enable_if<
1181 !std::is_same<InIt, value_type*>::value,
1182 const A>::type& /*a*/ = A()) {
1186 // Specialization for const char*, const char*
1187 FOLLY_MALLOC_NOINLINE
1188 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1189 : store_(b, size_type(e - b)) {
1192 // Nonstandard constructor
1193 basic_fbstring(value_type *s, size_type n, size_type c,
1194 AcquireMallocatedString a)
1195 : store_(s, n, c, a) {
1198 // Construction from initialization list
1199 FOLLY_MALLOC_NOINLINE
1200 basic_fbstring(std::initializer_list<value_type> il) {
1201 assign(il.begin(), il.end());
1204 ~basic_fbstring() noexcept {}
1206 basic_fbstring& operator=(const basic_fbstring& lhs);
1209 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1211 #ifndef _LIBSTDCXX_FBSTRING
1212 // Compatibility with std::string
1213 basic_fbstring & operator=(const std::string & rhs) {
1214 return assign(rhs.data(), rhs.size());
1217 // Compatibility with std::string
1218 std::string toStdString() const {
1219 return std::string(data(), size());
1222 // A lot of code in fbcode still uses this method, so keep it here for now.
1223 const basic_fbstring& toStdString() const {
1228 basic_fbstring& operator=(const value_type* s) {
1232 basic_fbstring& operator=(value_type c);
1234 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1235 return assign(il.begin(), il.end());
1238 // C++11 21.4.3 iterators:
1240 return store_.mutableData();
1243 const_iterator begin() const {
1244 return store_.data();
1247 const_iterator cbegin() const {
1252 return store_.mutableData() + store_.size();
1255 const_iterator end() const {
1256 return store_.data() + store_.size();
1259 const_iterator cend() const { return end(); }
1261 reverse_iterator rbegin() {
1262 return reverse_iterator(end());
1265 const_reverse_iterator rbegin() const {
1266 return const_reverse_iterator(end());
1269 const_reverse_iterator crbegin() const { return rbegin(); }
1271 reverse_iterator rend() {
1272 return reverse_iterator(begin());
1275 const_reverse_iterator rend() const {
1276 return const_reverse_iterator(begin());
1279 const_reverse_iterator crend() const { return rend(); }
1282 // C++11 21.4.5, element access:
1283 const value_type& front() const { return *begin(); }
1284 const value_type& back() const {
1285 FBSTRING_ASSERT(!empty());
1286 // Should be begin()[size() - 1], but that branches twice
1287 return *(end() - 1);
1289 value_type& front() { return *begin(); }
1290 value_type& back() {
1291 FBSTRING_ASSERT(!empty());
1292 // Should be begin()[size() - 1], but that branches twice
1293 return *(end() - 1);
1296 FBSTRING_ASSERT(!empty());
1300 // C++11 21.4.4 capacity:
1301 size_type size() const { return store_.size(); }
1303 size_type length() const { return size(); }
1305 size_type max_size() const {
1306 return std::numeric_limits<size_type>::max();
1309 void resize(size_type n, value_type c = value_type());
1311 size_type capacity() const { return store_.capacity(); }
1313 void reserve(size_type res_arg = 0) {
1314 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1315 store_.reserve(res_arg);
1318 void shrink_to_fit() {
1319 // Shrink only if slack memory is sufficiently large
1320 if (capacity() < size() * 3 / 2) {
1323 basic_fbstring(cbegin(), cend()).swap(*this);
1326 void clear() { resize(0); }
1328 bool empty() const { return size() == 0; }
1330 // C++11 21.4.5 element access:
1331 const_reference operator[](size_type pos) const {
1332 return *(begin() + pos);
1335 reference operator[](size_type pos) {
1336 return *(begin() + pos);
1339 const_reference at(size_type n) const {
1340 enforce(n <= size(), std::__throw_out_of_range, "");
1344 reference at(size_type n) {
1345 enforce(n < size(), std::__throw_out_of_range, "");
1349 // C++11 21.4.6 modifiers:
1350 basic_fbstring& operator+=(const basic_fbstring& str) {
1354 basic_fbstring& operator+=(const value_type* s) {
1358 basic_fbstring& operator+=(const value_type c) {
1363 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1368 basic_fbstring& append(const basic_fbstring& str);
1371 append(const basic_fbstring& str, const size_type pos, size_type n);
1373 basic_fbstring& append(const value_type* s, size_type n);
1375 basic_fbstring& append(const value_type* s) {
1376 return append(s, traitsLength(s));
1379 basic_fbstring& append(size_type n, value_type c);
1381 template<class InputIterator>
1382 basic_fbstring& append(InputIterator first, InputIterator last) {
1383 insert(end(), first, last);
1387 basic_fbstring& append(std::initializer_list<value_type> il) {
1388 return append(il.begin(), il.end());
1391 void push_back(const value_type c) { // primitive
1392 store_.push_back(c);
1395 basic_fbstring& assign(const basic_fbstring& str) {
1396 if (&str == this) return *this;
1397 return assign(str.data(), str.size());
1400 basic_fbstring& assign(basic_fbstring&& str) {
1401 return *this = std::move(str);
1405 assign(const basic_fbstring& str, const size_type pos, size_type n);
1407 basic_fbstring& assign(const value_type* s, const size_type n);
1409 basic_fbstring& assign(const value_type* s) {
1410 return assign(s, traitsLength(s));
1413 basic_fbstring& assign(std::initializer_list<value_type> il) {
1414 return assign(il.begin(), il.end());
1417 template <class ItOrLength, class ItOrChar>
1418 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1419 return replace(begin(), end(), first_or_n, last_or_c);
1422 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1423 return insert(pos1, str.data(), str.size());
1426 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1427 size_type pos2, size_type n) {
1428 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1429 procrustes(n, str.length() - pos2);
1430 return insert(pos1, str.data() + pos2, n);
1433 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1434 enforce(pos <= length(), std::__throw_out_of_range, "");
1435 insert(begin() + pos, s, s + n);
1439 basic_fbstring& insert(size_type pos, const value_type* s) {
1440 return insert(pos, s, traitsLength(s));
1443 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1444 enforce(pos <= length(), std::__throw_out_of_range, "");
1445 insert(begin() + pos, n, c);
1449 iterator insert(const_iterator p, const value_type c) {
1450 const size_type pos = p - cbegin();
1452 return begin() + pos;
1455 #ifndef _LIBSTDCXX_FBSTRING
1457 typedef std::basic_istream<value_type, traits_type> istream_type;
1458 istream_type& getlineImpl(istream_type& is, value_type delim);
1461 friend inline istream_type& getline(istream_type& is,
1462 basic_fbstring& str,
1464 return str.getlineImpl(is, delim);
1467 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1468 return getline(is, str, '\n');
1474 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1476 template <class InputIter>
1478 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1480 template <class FwdIterator>
1481 iterator insertImpl(
1485 std::forward_iterator_tag);
1487 template <class InputIterator>
1488 iterator insertImpl(
1492 std::input_iterator_tag);
1495 template <class ItOrLength, class ItOrChar>
1496 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1497 using Sel = std::integral_constant<
1499 std::numeric_limits<ItOrLength>::is_specialized>;
1500 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1503 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1504 return insert(p, il.begin(), il.end());
1507 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1508 Invariant checker(*this);
1510 enforce(pos <= length(), std::__throw_out_of_range, "");
1511 procrustes(n, length() - pos);
1512 std::copy(begin() + pos + n, end(), begin() + pos);
1513 resize(length() - n);
1517 iterator erase(iterator position) {
1518 const size_type pos(position - begin());
1519 enforce(pos <= size(), std::__throw_out_of_range, "");
1521 return begin() + pos;
1524 iterator erase(iterator first, iterator last) {
1525 const size_type pos(first - begin());
1526 erase(pos, last - first);
1527 return begin() + pos;
1530 // Replaces at most n1 chars of *this, starting with pos1 with the
1532 basic_fbstring& replace(size_type pos1, size_type n1,
1533 const basic_fbstring& str) {
1534 return replace(pos1, n1, str.data(), str.size());
1537 // Replaces at most n1 chars of *this, starting with pos1,
1538 // with at most n2 chars of str starting with pos2
1539 basic_fbstring& replace(size_type pos1, size_type n1,
1540 const basic_fbstring& str,
1541 size_type pos2, size_type n2) {
1542 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1543 return replace(pos1, n1, str.data() + pos2,
1544 std::min(n2, str.size() - pos2));
1547 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1548 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1549 return replace(pos, n1, s, traitsLength(s));
1552 // Replaces at most n1 chars of *this, starting with pos, with n2
1555 // consolidated with
1557 // Replaces at most n1 chars of *this, starting with pos, with at
1558 // most n2 chars of str. str must have at least n2 chars.
1559 template <class StrOrLength, class NumOrChar>
1560 basic_fbstring& replace(size_type pos, size_type n1,
1561 StrOrLength s_or_n2, NumOrChar n_or_c) {
1562 Invariant checker(*this);
1564 enforce(pos <= size(), std::__throw_out_of_range, "");
1565 procrustes(n1, length() - pos);
1566 const iterator b = begin() + pos;
1567 return replace(b, b + n1, s_or_n2, n_or_c);
1570 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1571 return replace(i1, i2, str.data(), str.length());
1574 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1575 return replace(i1, i2, s, traitsLength(s));
1579 basic_fbstring& replaceImplDiscr(
1582 const value_type* s,
1584 std::integral_constant<int, 2>);
1586 basic_fbstring& replaceImplDiscr(
1591 std::integral_constant<int, 1>);
1593 template <class InputIter>
1594 basic_fbstring& replaceImplDiscr(
1599 std::integral_constant<int, 0>);
1602 template <class FwdIterator>
1603 bool replaceAliased(iterator /* i1 */,
1605 FwdIterator /* s1 */,
1606 FwdIterator /* s2 */,
1611 template <class FwdIterator>
1612 bool replaceAliased(
1619 template <class FwdIterator>
1625 std::forward_iterator_tag);
1627 template <class InputIterator>
1633 std::input_iterator_tag);
1636 template <class T1, class T2>
1637 basic_fbstring& replace(iterator i1, iterator i2,
1638 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1639 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1640 num2 = std::numeric_limits<T2>::is_specialized;
1642 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1643 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1646 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1647 enforce(pos <= size(), std::__throw_out_of_range, "");
1648 procrustes(n, size() - pos);
1651 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1656 void swap(basic_fbstring& rhs) {
1657 store_.swap(rhs.store_);
1660 const value_type* c_str() const {
1661 return store_.c_str();
1664 const value_type* data() const { return c_str(); }
1666 allocator_type get_allocator() const {
1667 return allocator_type();
1670 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1671 return find(str.data(), pos, str.length());
1674 size_type find(const value_type* needle, size_type pos, size_type nsize)
1677 size_type find(const value_type* s, size_type pos = 0) const {
1678 return find(s, pos, traitsLength(s));
1681 size_type find (value_type c, size_type pos = 0) const {
1682 return find(&c, pos, 1);
1685 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1686 return rfind(str.data(), pos, str.length());
1689 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1691 size_type rfind(const value_type* s, size_type pos = npos) const {
1692 return rfind(s, pos, traitsLength(s));
1695 size_type rfind(value_type c, size_type pos = npos) const {
1696 return rfind(&c, pos, 1);
1699 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1700 return find_first_of(str.data(), pos, str.length());
1703 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1706 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1707 return find_first_of(s, pos, traitsLength(s));
1710 size_type find_first_of(value_type c, size_type pos = 0) const {
1711 return find_first_of(&c, pos, 1);
1714 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1716 return find_last_of(str.data(), pos, str.length());
1719 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1721 size_type find_last_of (const value_type* s,
1722 size_type pos = npos) const {
1723 return find_last_of(s, pos, traitsLength(s));
1726 size_type find_last_of (value_type c, size_type pos = npos) const {
1727 return find_last_of(&c, pos, 1);
1730 size_type find_first_not_of(const basic_fbstring& str,
1731 size_type pos = 0) const {
1732 return find_first_not_of(str.data(), pos, str.size());
1735 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1738 size_type find_first_not_of(const value_type* s,
1739 size_type pos = 0) const {
1740 return find_first_not_of(s, pos, traitsLength(s));
1743 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1744 return find_first_not_of(&c, pos, 1);
1747 size_type find_last_not_of(const basic_fbstring& str,
1748 size_type pos = npos) const {
1749 return find_last_not_of(str.data(), pos, str.length());
1752 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1755 size_type find_last_not_of(const value_type* s,
1756 size_type pos = npos) const {
1757 return find_last_not_of(s, pos, traitsLength(s));
1760 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1761 return find_last_not_of(&c, pos, 1);
1764 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1765 enforce(pos <= size(), std::__throw_out_of_range, "");
1766 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1769 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1770 enforce(pos <= size(), std::__throw_out_of_range, "");
1775 return std::move(*this);
1778 int compare(const basic_fbstring& str) const {
1779 // FIX due to Goncalo N M de Carvalho July 18, 2005
1780 return compare(0, size(), str);
1783 int compare(size_type pos1, size_type n1,
1784 const basic_fbstring& str) const {
1785 return compare(pos1, n1, str.data(), str.size());
1788 int compare(size_type pos1, size_type n1,
1789 const value_type* s) const {
1790 return compare(pos1, n1, s, traitsLength(s));
1793 int compare(size_type pos1, size_type n1,
1794 const value_type* s, size_type n2) const {
1795 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1796 procrustes(n1, size() - pos1);
1797 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1798 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1799 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1802 int compare(size_type pos1, size_type n1,
1803 const basic_fbstring& str,
1804 size_type pos2, size_type n2) const {
1805 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1806 return compare(pos1, n1, str.data() + pos2,
1807 std::min(n2, str.size() - pos2));
1810 // Code from Jean-Francois Bastien (03/26/2007)
1811 int compare(const value_type* s) const {
1812 // Could forward to compare(0, size(), s, traitsLength(s))
1813 // but that does two extra checks
1814 const size_type n1(size()), n2(traitsLength(s));
1815 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1816 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1824 template <typename E, class T, class A, class S>
1825 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1826 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1827 return s ? traits_type::length(s)
1828 : (std::__throw_logic_error(
1829 "basic_fbstring: null pointer initializer not valid"),
1833 template <typename E, class T, class A, class S>
1834 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1835 const basic_fbstring& lhs) {
1836 Invariant checker(*this);
1838 if (FBSTRING_UNLIKELY(&lhs == this)) {
1842 return assign(lhs.data(), lhs.size());
1846 template <typename E, class T, class A, class S>
1847 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1848 basic_fbstring&& goner) noexcept {
1849 if (FBSTRING_UNLIKELY(&goner == this)) {
1850 // Compatibility with std::basic_string<>,
1851 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1854 // No need of this anymore
1855 this->~basic_fbstring();
1856 // Move the goner into this
1857 new (&store_) S(std::move(goner.store_));
1861 template <typename E, class T, class A, class S>
1862 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1863 const value_type c) {
1864 Invariant checker(*this);
1867 store_.expandNoinit(1);
1868 } else if (store_.isShared()) {
1869 basic_fbstring(1, c).swap(*this);
1872 store_.shrink(size() - 1);
1878 template <typename E, class T, class A, class S>
1879 inline void basic_fbstring<E, T, A, S>::resize(
1880 const size_type n, const value_type c /*= value_type()*/) {
1881 Invariant checker(*this);
1883 auto size = this->size();
1885 store_.shrink(size - n);
1887 auto const delta = n - size;
1888 auto pData = store_.expandNoinit(delta);
1889 fbstring_detail::podFill(pData, pData + delta, c);
1891 FBSTRING_ASSERT(this->size() == n);
1894 template <typename E, class T, class A, class S>
1895 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1896 const basic_fbstring& str) {
1898 auto desiredSize = size() + str.size();
1900 append(str.data(), str.size());
1901 FBSTRING_ASSERT(size() == desiredSize);
1905 template <typename E, class T, class A, class S>
1906 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1907 const basic_fbstring& str, const size_type pos, size_type n) {
1908 const size_type sz = str.size();
1909 enforce(pos <= sz, std::__throw_out_of_range, "");
1910 procrustes(n, sz - pos);
1911 return append(str.data() + pos, n);
1914 template <typename E, class T, class A, class S>
1915 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1916 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1917 Invariant checker(*this);
1919 if (FBSTRING_UNLIKELY(!n)) {
1920 // Unlikely but must be done
1923 auto const oldSize = size();
1924 auto const oldData = data();
1925 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1927 // Check for aliasing (rare). We could use "<=" here but in theory
1928 // those do not work for pointers unless the pointers point to
1929 // elements in the same array. For that reason we use
1930 // std::less_equal, which is guaranteed to offer a total order
1931 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1933 std::less_equal<const value_type*> le;
1934 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1935 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1936 // expandNoinit() could have moved the storage, restore the source.
1937 s = data() + (s - oldData);
1938 fbstring_detail::podMove(s, s + n, pData);
1940 fbstring_detail::podCopy(s, s + n, pData);
1943 FBSTRING_ASSERT(size() == oldSize + n);
1947 template <typename E, class T, class A, class S>
1948 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1949 size_type n, value_type c) {
1950 Invariant checker(*this);
1951 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1952 fbstring_detail::podFill(pData, pData + n, c);
1956 template <typename E, class T, class A, class S>
1957 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1958 const basic_fbstring& str, const size_type pos, size_type n) {
1959 const size_type sz = str.size();
1960 enforce(pos <= sz, std::__throw_out_of_range, "");
1961 procrustes(n, sz - pos);
1962 return assign(str.data() + pos, n);
1965 template <typename E, class T, class A, class S>
1966 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1967 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1968 Invariant checker(*this);
1972 } else if (size() >= n) {
1973 // s can alias this, we need to use podMove.
1974 fbstring_detail::podMove(s, s + n, store_.mutableData());
1975 store_.shrink(size() - n);
1976 FBSTRING_ASSERT(size() == n);
1978 // If n is larger than size(), s cannot alias this string's
1981 // Do not use exponential growth here: assign() should be tight,
1982 // to mirror the behavior of the equivalent constructor.
1983 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
1986 FBSTRING_ASSERT(size() == n);
1990 #ifndef _LIBSTDCXX_FBSTRING
1991 template <typename E, class T, class A, class S>
1992 inline typename basic_fbstring<E, T, A, S>::istream_type&
1993 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
1994 Invariant checker(*this);
1999 size_t avail = capacity() - size;
2000 // fbstring has 1 byte extra capacity for the null terminator,
2001 // and getline null-terminates the read string.
2002 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2003 size += is.gcount();
2005 if (is.bad() || is.eof() || !is.fail()) {
2006 // Done by either failure, end of file, or normal read.
2007 if (!is.bad() && !is.eof()) {
2008 --size; // gcount() also accounts for the delimiter.
2014 FBSTRING_ASSERT(size == this->size());
2015 FBSTRING_ASSERT(size == capacity());
2016 // Start at minimum allocation 63 + terminator = 64.
2017 reserve(std::max<size_t>(63, 3 * size / 2));
2018 // Clear the error so we can continue reading.
2025 template <typename E, class T, class A, class S>
2026 inline typename basic_fbstring<E, T, A, S>::size_type
2027 basic_fbstring<E, T, A, S>::find(
2028 const value_type* needle, const size_type pos, const size_type nsize)
2030 auto const size = this->size();
2031 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2032 // that nsize + pos does not wrap around.
2033 if (nsize + pos > size || nsize + pos < pos) {
2040 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2041 // the last characters first
2042 auto const haystack = data();
2043 auto const nsize_1 = nsize - 1;
2044 auto const lastNeedle = needle[nsize_1];
2046 // Boyer-Moore skip value for the last char in the needle. Zero is
2047 // not a valid value; skip will be computed the first time it's
2051 const E* i = haystack + pos;
2052 auto iEnd = haystack + size - nsize_1;
2055 // Boyer-Moore: match the last element in the needle
2056 while (i[nsize_1] != lastNeedle) {
2062 // Here we know that the last char matches
2063 // Continue in pedestrian mode
2064 for (size_t j = 0;;) {
2065 FBSTRING_ASSERT(j < nsize);
2066 if (i[j] != needle[j]) {
2067 // Not found, we can skip
2068 // Compute the skip value lazily
2071 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2078 // Check if done searching
2081 return i - haystack;
2088 template <typename E, class T, class A, class S>
2089 inline typename basic_fbstring<E, T, A, S>::iterator
2090 basic_fbstring<E, T, A, S>::insertImplDiscr(
2091 const_iterator i, size_type n, value_type c, std::true_type) {
2092 Invariant checker(*this);
2094 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2095 const size_type pos = i - cbegin();
2097 auto oldSize = size();
2098 store_.expandNoinit(n, /* expGrowth = */ true);
2100 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2101 fbstring_detail::podFill(b + pos, b + pos + n, c);
2106 template <typename E, class T, class A, class S>
2107 template <class InputIter>
2108 inline typename basic_fbstring<E, T, A, S>::iterator
2109 basic_fbstring<E, T, A, S>::insertImplDiscr(
2110 const_iterator i, InputIter b, InputIter e, std::false_type) {
2112 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2115 template <typename E, class T, class A, class S>
2116 template <class FwdIterator>
2117 inline typename basic_fbstring<E, T, A, S>::iterator
2118 basic_fbstring<E, T, A, S>::insertImpl(
2122 std::forward_iterator_tag) {
2123 Invariant checker(*this);
2125 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2126 const size_type pos = i - cbegin();
2127 auto n = std::distance(s1, s2);
2128 FBSTRING_ASSERT(n >= 0);
2130 auto oldSize = size();
2131 store_.expandNoinit(n, /* expGrowth = */ true);
2133 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2134 std::copy(s1, s2, b + pos);
2139 template <typename E, class T, class A, class S>
2140 template <class InputIterator>
2141 inline typename basic_fbstring<E, T, A, S>::iterator
2142 basic_fbstring<E, T, A, S>::insertImpl(
2146 std::input_iterator_tag) {
2147 const auto pos = i - cbegin();
2148 basic_fbstring temp(cbegin(), i);
2149 for (; b != e; ++b) {
2152 temp.append(i, cend());
2154 return begin() + pos;
2157 template <typename E, class T, class A, class S>
2158 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2161 const value_type* s,
2163 std::integral_constant<int, 2>) {
2164 FBSTRING_ASSERT(i1 <= i2);
2165 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2166 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2167 return replace(i1, i2, s, s + n);
2170 template <typename E, class T, class A, class S>
2171 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2176 std::integral_constant<int, 1>) {
2177 const size_type n1 = i2 - i1;
2179 std::fill(i1, i1 + n2, c);
2182 std::fill(i1, i2, c);
2183 insert(i2, n2 - n1, c);
2185 FBSTRING_ASSERT(isSane());
2189 template <typename E, class T, class A, class S>
2190 template <class InputIter>
2191 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2196 std::integral_constant<int, 0>) {
2197 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2198 replaceImpl(i1, i2, b, e, Cat());
2202 template <typename E, class T, class A, class S>
2203 template <class FwdIterator>
2204 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2205 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2206 std::less_equal<const value_type*> le{};
2207 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2211 // Aliased replace, copy to new string
2212 basic_fbstring temp;
2213 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2214 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2219 template <typename E, class T, class A, class S>
2220 template <class FwdIterator>
2221 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2226 std::forward_iterator_tag) {
2227 Invariant checker(*this);
2229 // Handle aliased replace
2230 using Sel = std::integral_constant<
2232 std::is_same<FwdIterator, iterator>::value ||
2233 std::is_same<FwdIterator, const_iterator>::value>;
2234 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2238 auto const n1 = i2 - i1;
2239 FBSTRING_ASSERT(n1 >= 0);
2240 auto const n2 = std::distance(s1, s2);
2241 FBSTRING_ASSERT(n2 >= 0);
2245 std::copy(s1, s2, i1);
2249 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2252 FBSTRING_ASSERT(isSane());
2255 template <typename E, class T, class A, class S>
2256 template <class InputIterator>
2257 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2262 std::input_iterator_tag) {
2263 basic_fbstring temp(begin(), i1);
2264 temp.append(b, e).append(i2, end());
2268 template <typename E, class T, class A, class S>
2269 inline typename basic_fbstring<E, T, A, S>::size_type
2270 basic_fbstring<E, T, A, S>::rfind(
2271 const value_type* s, size_type pos, size_type n) const {
2275 pos = std::min(pos, length() - n);
2280 const_iterator i(begin() + pos);
2282 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2292 template <typename E, class T, class A, class S>
2293 inline typename basic_fbstring<E, T, A, S>::size_type
2294 basic_fbstring<E, T, A, S>::find_first_of(
2295 const value_type* s, size_type pos, size_type n) const {
2296 if (pos > length() || n == 0) {
2299 const_iterator i(begin() + pos), finish(end());
2300 for (; i != finish; ++i) {
2301 if (traits_type::find(s, n, *i) != 0) {
2308 template <typename E, class T, class A, class S>
2309 inline typename basic_fbstring<E, T, A, S>::size_type
2310 basic_fbstring<E, T, A, S>::find_last_of(
2311 const value_type* s, size_type pos, size_type n) const {
2312 if (!empty() && n > 0) {
2313 pos = std::min(pos, length() - 1);
2314 const_iterator i(begin() + pos);
2316 if (traits_type::find(s, n, *i) != 0) {
2327 template <typename E, class T, class A, class S>
2328 inline typename basic_fbstring<E, T, A, S>::size_type
2329 basic_fbstring<E, T, A, S>::find_first_not_of(
2330 const value_type* s, size_type pos, size_type n) const {
2331 if (pos < length()) {
2332 const_iterator i(begin() + pos), finish(end());
2333 for (; i != finish; ++i) {
2334 if (traits_type::find(s, n, *i) == 0) {
2342 template <typename E, class T, class A, class S>
2343 inline typename basic_fbstring<E, T, A, S>::size_type
2344 basic_fbstring<E, T, A, S>::find_last_not_of(
2345 const value_type* s, size_type pos, size_type n) const {
2346 if (!this->empty()) {
2347 pos = std::min(pos, size() - 1);
2348 const_iterator i(begin() + pos);
2350 if (traits_type::find(s, n, *i) == 0) {
2361 // non-member functions
2363 template <typename E, class T, class A, class S>
2365 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2366 const basic_fbstring<E, T, A, S>& rhs) {
2368 basic_fbstring<E, T, A, S> result;
2369 result.reserve(lhs.size() + rhs.size());
2370 result.append(lhs).append(rhs);
2371 return std::move(result);
2375 template <typename E, class T, class A, class S>
2377 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2378 const basic_fbstring<E, T, A, S>& rhs) {
2379 return std::move(lhs.append(rhs));
2383 template <typename E, class T, class A, class S>
2385 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2386 basic_fbstring<E, T, A, S>&& rhs) {
2387 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2388 // Good, at least we don't need to reallocate
2389 return std::move(rhs.insert(0, lhs));
2391 // Meh, no go. Forward to operator+(const&, const&).
2392 auto const& rhsC = rhs;
2397 template <typename E, class T, class A, class S>
2399 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2400 basic_fbstring<E, T, A, S>&& rhs) {
2401 return std::move(lhs.append(rhs));
2405 template <typename E, class T, class A, class S>
2407 basic_fbstring<E, T, A, S> operator+(
2409 const basic_fbstring<E, T, A, S>& rhs) {
2411 basic_fbstring<E, T, A, S> result;
2412 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2413 result.reserve(len + rhs.size());
2414 result.append(lhs, len).append(rhs);
2419 template <typename E, class T, class A, class S>
2421 basic_fbstring<E, T, A, S> operator+(
2423 basic_fbstring<E, T, A, S>&& rhs) {
2425 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2426 if (rhs.capacity() >= len + rhs.size()) {
2427 // Good, at least we don't need to reallocate
2428 rhs.insert(rhs.begin(), lhs, lhs + len);
2431 // Meh, no go. Do it by hand since we have len already.
2432 basic_fbstring<E, T, A, S> result;
2433 result.reserve(len + rhs.size());
2434 result.append(lhs, len).append(rhs);
2439 template <typename E, class T, class A, class S>
2441 basic_fbstring<E, T, A, S> operator+(
2443 const basic_fbstring<E, T, A, S>& rhs) {
2445 basic_fbstring<E, T, A, S> result;
2446 result.reserve(1 + rhs.size());
2447 result.push_back(lhs);
2453 template <typename E, class T, class A, class S>
2455 basic_fbstring<E, T, A, S> operator+(
2457 basic_fbstring<E, T, A, S>&& rhs) {
2459 if (rhs.capacity() > rhs.size()) {
2460 // Good, at least we don't need to reallocate
2461 rhs.insert(rhs.begin(), lhs);
2464 // Meh, no go. Forward to operator+(E, const&).
2465 auto const& rhsC = rhs;
2470 template <typename E, class T, class A, class S>
2472 basic_fbstring<E, T, A, S> operator+(
2473 const basic_fbstring<E, T, A, S>& lhs,
2476 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2477 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2479 basic_fbstring<E, T, A, S> result;
2480 const size_type len = traits_type::length(rhs);
2481 result.reserve(lhs.size() + len);
2482 result.append(lhs).append(rhs, len);
2486 // C++11 21.4.8.1/10
2487 template <typename E, class T, class A, class S>
2489 basic_fbstring<E, T, A, S> operator+(
2490 basic_fbstring<E, T, A, S>&& lhs,
2493 return std::move(lhs += rhs);
2496 // C++11 21.4.8.1/11
2497 template <typename E, class T, class A, class S>
2499 basic_fbstring<E, T, A, S> operator+(
2500 const basic_fbstring<E, T, A, S>& lhs,
2503 basic_fbstring<E, T, A, S> result;
2504 result.reserve(lhs.size() + 1);
2506 result.push_back(rhs);
2510 // C++11 21.4.8.1/12
2511 template <typename E, class T, class A, class S>
2513 basic_fbstring<E, T, A, S> operator+(
2514 basic_fbstring<E, T, A, S>&& lhs,
2517 return std::move(lhs += rhs);
2520 template <typename E, class T, class A, class S>
2522 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2523 const basic_fbstring<E, T, A, S>& rhs) {
2524 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2526 template <typename E, class T, class A, class S>
2528 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2529 const basic_fbstring<E, T, A, S>& rhs) {
2530 return rhs == lhs; }
2532 template <typename E, class T, class A, class S>
2534 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2535 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2536 return lhs.compare(rhs) == 0; }
2538 template <typename E, class T, class A, class S>
2540 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2541 const basic_fbstring<E, T, A, S>& rhs) {
2542 return !(lhs == rhs); }
2544 template <typename E, class T, class A, class S>
2546 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2547 const basic_fbstring<E, T, A, S>& rhs) {
2548 return !(lhs == rhs); }
2550 template <typename E, class T, class A, class S>
2552 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2553 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2554 return !(lhs == rhs); }
2556 template <typename E, class T, class A, class S>
2558 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2559 const basic_fbstring<E, T, A, S>& rhs) {
2560 return lhs.compare(rhs) < 0; }
2562 template <typename E, class T, class A, class S>
2564 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2565 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2566 return lhs.compare(rhs) < 0; }
2568 template <typename E, class T, class A, class S>
2570 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2571 const basic_fbstring<E, T, A, S>& rhs) {
2572 return rhs.compare(lhs) > 0; }
2574 template <typename E, class T, class A, class S>
2576 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2577 const basic_fbstring<E, T, A, S>& rhs) {
2580 template <typename E, class T, class A, class S>
2582 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2583 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2586 template <typename E, class T, class A, class S>
2588 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2589 const basic_fbstring<E, T, A, S>& rhs) {
2592 template <typename E, class T, class A, class S>
2594 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2595 const basic_fbstring<E, T, A, S>& rhs) {
2596 return !(rhs < lhs); }
2598 template <typename E, class T, class A, class S>
2600 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2601 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2602 return !(rhs < lhs); }
2604 template <typename E, class T, class A, class S>
2606 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2607 const basic_fbstring<E, T, A, S>& rhs) {
2608 return !(rhs < lhs); }
2610 template <typename E, class T, class A, class S>
2612 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2613 const basic_fbstring<E, T, A, S>& rhs) {
2614 return !(lhs < rhs); }
2616 template <typename E, class T, class A, class S>
2618 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2619 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2620 return !(lhs < rhs); }
2622 template <typename E, class T, class A, class S>
2624 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2625 const basic_fbstring<E, T, A, S>& rhs) {
2626 return !(lhs < rhs);
2630 template <typename E, class T, class A, class S>
2631 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2635 // TODO: make this faster.
2636 template <typename E, class T, class A, class S>
2639 typename basic_fbstring<E, T, A, S>::value_type,
2640 typename basic_fbstring<E, T, A, S>::traits_type>&
2642 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2643 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2644 basic_fbstring<E, T, A, S>& str) {
2645 typename std::basic_istream<E, T>::sentry sentry(is);
2646 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2647 typename basic_fbstring<E, T, A, S>::traits_type>
2649 typedef typename __istream_type::ios_base __ios_base;
2650 size_t extracted = 0;
2651 auto err = __ios_base::goodbit;
2653 auto n = is.width();
2658 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2659 if (got == T::eof()) {
2660 err |= __ios_base::eofbit;
2668 got = is.rdbuf()->snextc();
2672 err |= __ios_base::failbit;
2680 template <typename E, class T, class A, class S>
2682 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2683 typename basic_fbstring<E, T, A, S>::traits_type>&
2685 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2686 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2687 const basic_fbstring<E, T, A, S>& str) {
2689 typename std::basic_ostream<
2690 typename basic_fbstring<E, T, A, S>::value_type,
2691 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2693 typedef std::ostreambuf_iterator<
2694 typename basic_fbstring<E, T, A, S>::value_type,
2695 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2696 size_t __len = str.size();
2698 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2699 if (__pad_and_output(_Ip(os),
2701 __left ? str.data() + __len : str.data(),
2704 os.fill()).failed()) {
2705 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2708 #elif defined(_MSC_VER)
2709 // MSVC doesn't define __ostream_insert
2710 os.write(str.data(), std::streamsize(str.size()));
2712 std::__ostream_insert(os, str.data(), str.size());
2717 template <typename E1, class T, class A, class S>
2718 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2719 basic_fbstring<E1, T, A, S>::npos;
2721 #ifndef _LIBSTDCXX_FBSTRING
2722 // basic_string compatibility routines
2724 template <typename E, class T, class A, class S>
2726 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2727 const std::string& rhs) {
2728 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2731 template <typename E, class T, class A, class S>
2733 bool operator==(const std::string& lhs,
2734 const basic_fbstring<E, T, A, S>& rhs) {
2738 template <typename E, class T, class A, class S>
2740 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2741 const std::string& rhs) {
2742 return !(lhs == rhs);
2745 template <typename E, class T, class A, class S>
2747 bool operator!=(const std::string& lhs,
2748 const basic_fbstring<E, T, A, S>& rhs) {
2749 return !(lhs == rhs);
2752 #if !defined(_LIBSTDCXX_FBSTRING)
2753 typedef basic_fbstring<char> fbstring;
2756 // fbstring is relocatable
2757 template <class T, class R, class A, class S>
2758 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2761 _GLIBCXX_END_NAMESPACE_VERSION
2764 } // namespace folly
2766 #ifndef _LIBSTDCXX_FBSTRING
2768 // Hash functions to make fbstring usable with e.g. hash_map
2770 // Handle interaction with different C++ standard libraries, which
2771 // expect these types to be in different namespaces.
2773 #define FOLLY_FBSTRING_HASH1(T) \
2775 struct hash< ::folly::basic_fbstring<T>> { \
2776 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2777 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2781 // The C++11 standard says that these four are defined
2782 #define FOLLY_FBSTRING_HASH \
2783 FOLLY_FBSTRING_HASH1(char) \
2784 FOLLY_FBSTRING_HASH1(char16_t) \
2785 FOLLY_FBSTRING_HASH1(char32_t) \
2786 FOLLY_FBSTRING_HASH1(wchar_t)
2794 #if FOLLY_HAVE_DEPRECATED_ASSOC
2795 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2796 namespace __gnu_cxx {
2800 } // namespace __gnu_cxx
2801 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2802 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2804 #undef FOLLY_FBSTRING_HASH
2805 #undef FOLLY_FBSTRING_HASH1
2807 #endif // _LIBSTDCXX_FBSTRING
2809 #pragma GCC diagnostic pop
2811 #undef FBSTRING_DISABLE_SSO
2812 #undef FBSTRING_SANITIZE_ADDRESS
2814 #undef FBSTRING_LIKELY
2815 #undef FBSTRING_UNLIKELY
2816 #undef FBSTRING_ASSERT