2 * Copyright 2016 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)
24 #include <type_traits>
26 // This file appears in two locations: inside fbcode and in the
27 // libstdc++ source code (when embedding fbstring as std::string).
28 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
29 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
30 #ifdef _LIBSTDCXX_FBSTRING
32 #pragma GCC system_header
34 #include "basic_fbstring_malloc.h"
36 // When used as std::string replacement always disable assertions.
37 #define FBSTRING_ASSERT(expr) /* empty */
39 #else // !_LIBSTDCXX_FBSTRING
41 #include <folly/Portability.h>
43 // libc++ doesn't provide this header, nor does msvc
44 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
45 #include <bits/c++config.h>
54 #include <folly/Hash.h>
55 #include <folly/Malloc.h>
56 #include <folly/Traits.h>
58 #if FOLLY_HAVE_DEPRECATED_ASSOC
59 #ifdef _GLIBCXX_SYMVER
60 #include <ext/hash_set>
61 #include <ext/hash_map>
65 // When used in folly, assertions are not disabled.
66 #define FBSTRING_ASSERT(expr) assert(expr)
70 // We defined these here rather than including Likely.h to avoid
71 // redefinition errors when fbstring is imported into libstdc++.
72 #if defined(__GNUC__) && __GNUC__ >= 4
73 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
74 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
76 #define FBSTRING_LIKELY(x) (x)
77 #define FBSTRING_UNLIKELY(x) (x)
80 #pragma GCC diagnostic push
81 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
82 #pragma GCC diagnostic ignored "-Wshadow"
83 // GCC 4.9 has a false positive in setSmallSize (probably
84 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
85 // compile-time array bound checking.
86 #pragma GCC diagnostic ignored "-Warray-bounds"
88 // FBString cannot use throw when replacing std::string, though it may still
91 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
93 #ifdef _LIBSTDCXX_FBSTRING
94 namespace std _GLIBCXX_VISIBILITY(default) {
95 _GLIBCXX_BEGIN_NAMESPACE_VERSION
100 #if defined(__clang__)
101 # if __has_feature(address_sanitizer)
102 # define FBSTRING_SANITIZE_ADDRESS
104 #elif defined (__GNUC__) && \
105 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
107 # define FBSTRING_SANITIZE_ADDRESS
110 // When compiling with ASan, always heap-allocate the string even if
111 // it would fit in-situ, so that ASan can detect access to the string
112 // buffer after it has been invalidated (destroyed, resized, etc.).
113 // Note that this flag doesn't remove support for in-situ strings, as
114 // that would break ABI-compatibility and wouldn't allow linking code
115 // compiled with this flag with code compiled without.
116 #ifdef FBSTRING_SANITIZE_ADDRESS
117 # define FBSTRING_DISABLE_SSO true
119 # define FBSTRING_DISABLE_SSO false
122 namespace fbstring_detail {
124 template <class InIt, class OutIt>
125 inline std::pair<InIt, OutIt> copy_n(
127 typename std::iterator_traits<InIt>::difference_type n,
129 for (; n != 0; --n, ++b, ++d) {
132 return std::make_pair(b, d);
135 template <class Pod, class T>
136 inline void podFill(Pod* b, Pod* e, T c) {
137 FBSTRING_ASSERT(b && e && b <= e);
138 /*static*/ if (sizeof(T) == 1) {
139 memset(b, c, size_t(e - b));
141 auto const ee = b + ((e - b) & ~7u);
142 for (; b != ee; b += 8) {
153 for (; b != e; ++b) {
160 * Lightly structured memcpy, simplifies copying PODs and introduces
161 * some asserts. Unfortunately using this function may cause
162 * measurable overhead (presumably because it adjusts from a begin/end
163 * convention to a pointer/size convention, so it does some extra
164 * arithmetic even though the caller might have done the inverse
165 * adaptation outside).
168 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
169 FBSTRING_ASSERT(b != nullptr);
170 FBSTRING_ASSERT(e != nullptr);
171 FBSTRING_ASSERT(d != nullptr);
172 FBSTRING_ASSERT(e >= b);
173 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
174 memcpy(d, b, (e - b) * sizeof(Pod));
178 * Lightly structured memmove, simplifies copying PODs and introduces
182 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
183 FBSTRING_ASSERT(e >= b);
184 memmove(d, b, (e - b) * sizeof(*b));
188 #if defined(__GNUC__) // Clang also defines __GNUC__
189 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
190 #elif defined(_MSC_VER)
191 # define FBSTRING_ALWAYS_INLINE __forceinline
193 # define FBSTRING_ALWAYS_INLINE inline
196 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
197 #if defined(__GNUC__) // Clang also defines __GNUC__
198 __builtin_unreachable();
199 #elif defined(_MSC_VER)
202 // Well, it's better than nothing.
207 } // namespace fbstring_detail
210 * Defines a special acquisition method for constructing fbstring
211 * objects. AcquireMallocatedString means that the user passes a
212 * pointer to a malloc-allocated string that the fbstring object will
215 enum class AcquireMallocatedString {};
218 * fbstring_core_model is a mock-up type that defines all required
219 * signatures of a fbstring core. The fbstring class itself uses such
220 * a core object to implement all of the numerous member functions
221 * required by the standard.
223 * If you want to define a new core, copy the definition below and
224 * implement the primitives. Then plug the core into basic_fbstring as
225 * a template argument.
227 template <class Char>
228 class fbstring_core_model {
230 fbstring_core_model();
231 fbstring_core_model(const fbstring_core_model &);
232 ~fbstring_core_model();
233 // Returns a pointer to string's buffer (currently only contiguous
234 // strings are supported). The pointer is guaranteed to be valid
235 // until the next call to a non-const member function.
236 const Char * data() const;
237 // Much like data(), except the string is prepared to support
238 // character-level changes. This call is a signal for
239 // e.g. reference-counted implementation to fork the data. The
240 // pointer is guaranteed to be valid until the next call to a
241 // non-const member function.
243 // Returns a pointer to string's buffer and guarantees that a
244 // readable '\0' lies right after the buffer. The pointer is
245 // guaranteed to be valid until the next call to a non-const member
247 const Char * c_str() const;
248 // Shrinks the string by delta characters. Asserts that delta <=
250 void shrink(size_t delta);
251 // Expands the string by delta characters (i.e. after this call
252 // size() will report the old size() plus delta) but without
253 // initializing the expanded region. The expanded region is
254 // zero-terminated. Returns a pointer to the memory to be
255 // initialized (the beginning of the expanded portion). The caller
256 // is expected to fill the expanded area appropriately.
257 // If expGrowth is true, exponential growth is guaranteed.
258 // It is not guaranteed not to reallocate even if size() + delta <
259 // capacity(), so all references to the buffer are invalidated.
260 Char* expandNoinit(size_t delta, bool expGrowth);
261 // Expands the string by one character and sets the last character
263 void push_back(Char c);
264 // Returns the string's size.
266 // Returns the string's capacity, i.e. maximum size that the string
267 // can grow to without reallocation. Note that for reference counted
268 // strings that's technically a lie - even assigning characters
269 // within the existing size would cause a reallocation.
270 size_t capacity() const;
271 // Returns true if the data underlying the string is actually shared
272 // across multiple strings (in a refcounted fashion).
273 bool isShared() const;
274 // Makes sure that at least minCapacity characters are available for
275 // the string without reallocation. For reference-counted strings,
276 // it should fork the data even if minCapacity < size().
277 void reserve(size_t minCapacity);
280 fbstring_core_model& operator=(const fbstring_core_model &);
285 * This is the core of the string. The code should work on 32- and
286 * 64-bit and both big- and little-endianan architectures with any
289 * The storage is selected as follows (assuming we store one-byte
290 * characters on a 64-bit machine): (a) "small" strings between 0 and
291 * 23 chars are stored in-situ without allocation (the rightmost byte
292 * stores the size); (b) "medium" strings from 24 through 254 chars
293 * are stored in malloc-allocated memory that is copied eagerly; (c)
294 * "large" strings of 255 chars and above are stored in a similar
295 * structure as medium arrays, except that the string is
296 * reference-counted and copied lazily. the reference count is
297 * allocated right before the character array.
299 * The discriminator between these three strategies sits in two
300 * bits of the rightmost char of the storage. If neither is set, then the
301 * string is small (and its length sits in the lower-order bits on
302 * little-endian or the high-order bits on big-endian of that
303 * rightmost character). If the MSb is set, the string is medium width.
304 * If the second MSb is set, then the string is large. On little-endian,
305 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
306 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
307 * and big-endian fbstring_core equivalent with merely different ops used
308 * to extract capacity/category.
310 template <class Char> class fbstring_core {
312 // It's MSVC, so we just have to guess ... and allow an override
314 # ifdef FOLLY_ENDIAN_BE
315 static constexpr auto kIsLittleEndian = false;
317 static constexpr auto kIsLittleEndian = true;
320 static constexpr auto kIsLittleEndian =
321 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
324 fbstring_core() noexcept { reset(); }
326 fbstring_core(const fbstring_core & rhs) {
327 FBSTRING_ASSERT(&rhs != this);
328 switch (rhs.category()) {
329 case Category::isSmall:
332 case Category::isMedium:
335 case Category::isLarge:
339 fbstring_detail::assume_unreachable();
341 FBSTRING_ASSERT(size() == rhs.size());
342 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
345 fbstring_core(fbstring_core&& goner) noexcept {
348 // Clean goner's carcass
352 fbstring_core(const Char *const data,
354 bool disableSSO = FBSTRING_DISABLE_SSO) {
355 if (!disableSSO && size <= maxSmallSize) {
356 initSmall(data, size);
357 } else if (size <= maxMediumSize) {
358 initMedium(data, size);
360 initLarge(data, size);
362 FBSTRING_ASSERT(this->size() == size);
364 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
367 ~fbstring_core() noexcept {
368 if (category() == Category::isSmall) {
371 destroyMediumLarge();
374 // Snatches a previously mallocated string. The parameter "size"
375 // is the size of the string, and the parameter "allocatedSize"
376 // is the size of the mallocated block. The string must be
377 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
379 // So if you want a 2-character string, pass malloc(3) as "data",
380 // pass 2 as "size", and pass 3 as "allocatedSize".
381 fbstring_core(Char * const data,
383 const size_t allocatedSize,
384 AcquireMallocatedString) {
386 FBSTRING_ASSERT(allocatedSize >= size + 1);
387 FBSTRING_ASSERT(data[size] == '\0');
388 // Use the medium string storage
391 // Don't forget about null terminator
392 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
394 // No need for the memory
400 // swap below doesn't test whether &rhs == this (and instead
401 // potentially does extra work) on the premise that the rarity of
402 // that situation actually makes the check more expensive than is
404 void swap(fbstring_core & rhs) {
410 // In C++11 data() and c_str() are 100% equivalent.
411 const Char * data() const {
415 Char* mutableData() {
416 switch (category()) {
417 case Category::isSmall:
419 case Category::isMedium:
421 case Category::isLarge:
422 return mutableDataLarge();
424 fbstring_detail::assume_unreachable();
427 const Char* c_str() const {
428 const Char* ptr = ml_.data_;
429 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
430 ptr = (category() == Category::isSmall) ? small_ : ptr;
434 void shrink(const size_t delta) {
435 if (category() == Category::isSmall) {
437 } else if (category() == Category::isMedium ||
438 RefCounted::refs(ml_.data_) == 1) {
445 FOLLY_MALLOC_NOINLINE
446 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
447 switch (category()) {
448 case Category::isSmall:
449 reserveSmall(minCapacity, disableSSO);
451 case Category::isMedium:
452 reserveMedium(minCapacity);
454 case Category::isLarge:
455 reserveLarge(minCapacity);
458 fbstring_detail::assume_unreachable();
460 FBSTRING_ASSERT(capacity() >= minCapacity);
465 bool expGrowth = false,
466 bool disableSSO = FBSTRING_DISABLE_SSO);
468 void push_back(Char c) {
469 *expandNoinit(1, /* expGrowth = */ true) = c;
472 size_t size() const {
473 size_t ret = ml_.size_;
474 /* static */ if (kIsLittleEndian) {
475 // We can save a couple instructions, because the category is
476 // small iff the last char, as unsigned, is <= maxSmallSize.
477 typedef typename std::make_unsigned<Char>::type UChar;
478 auto maybeSmallSize = size_t(maxSmallSize) -
479 size_t(static_cast<UChar>(small_[maxSmallSize]));
480 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
481 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
483 ret = (category() == Category::isSmall) ? smallSize() : ret;
488 size_t capacity() const {
489 switch (category()) {
490 case Category::isSmall:
492 case Category::isLarge:
493 // For large-sized strings, a multi-referenced chunk has no
494 // available capacity. This is because any attempt to append
495 // data would trigger a new allocation.
496 if (RefCounted::refs(ml_.data_) > 1) {
501 return ml_.capacity();
504 bool isShared() const {
505 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
510 fbstring_core & operator=(const fbstring_core & rhs);
516 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
517 auto const c = category();
518 FBSTRING_ASSERT(c != Category::isSmall);
519 if (c == Category::isMedium) {
522 RefCounted::decrementRefs(ml_.data_);
527 std::atomic<size_t> refCount_;
530 static RefCounted * fromData(Char * p) {
531 return static_cast<RefCounted*>(
533 static_cast<unsigned char*>(static_cast<void*>(p))
534 - sizeof(refCount_)));
537 static size_t refs(Char * p) {
538 return fromData(p)->refCount_.load(std::memory_order_acquire);
541 static void incrementRefs(Char * p) {
542 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
545 static void decrementRefs(Char * p) {
546 auto const dis = fromData(p);
547 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
548 FBSTRING_ASSERT(oldcnt > 0);
554 static RefCounted * create(size_t * size) {
555 // Don't forget to allocate one extra Char for the terminating
556 // null. In this case, however, one Char is already part of the
558 const size_t allocSize = goodMallocSize(
559 sizeof(RefCounted) + *size * sizeof(Char));
560 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
561 result->refCount_.store(1, std::memory_order_release);
562 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
566 static RefCounted * create(const Char * data, size_t * size) {
567 const size_t effectiveSize = *size;
568 auto result = create(size);
569 if (FBSTRING_LIKELY(effectiveSize > 0)) {
570 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
575 static RefCounted * reallocate(Char *const data,
576 const size_t currentSize,
577 const size_t currentCapacity,
578 const size_t newCapacity) {
579 FBSTRING_ASSERT(newCapacity > 0 && newCapacity > currentSize);
580 auto const dis = fromData(data);
581 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
582 // Don't forget to allocate one extra Char for the terminating
583 // null. In this case, however, one Char is already part of the
585 auto result = static_cast<RefCounted*>(
587 sizeof(RefCounted) + currentSize * sizeof(Char),
588 sizeof(RefCounted) + currentCapacity * sizeof(Char),
589 sizeof(RefCounted) + newCapacity * sizeof(Char)));
590 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
595 typedef uint8_t category_type;
597 enum class Category : category_type {
599 isMedium = kIsLittleEndian ? 0x80 : 0x2,
600 isLarge = kIsLittleEndian ? 0x40 : 0x1,
603 Category category() const {
604 // works for both big-endian and little-endian
605 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
613 size_t capacity() const {
614 return kIsLittleEndian
615 ? capacity_ & capacityExtractMask
619 void setCapacity(size_t cap, Category cat) {
620 capacity_ = kIsLittleEndian
621 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
622 : (cap << 2) | static_cast<size_t>(cat);
627 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
628 Char small_[sizeof(MediumLarge) / sizeof(Char)];
632 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
633 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
634 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
635 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
636 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
637 constexpr static size_t capacityExtractMask = kIsLittleEndian
638 ? ~(size_t(categoryExtractMask) << kCategoryShift)
641 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
642 "Corrupt memory layout for fbstring.");
644 size_t smallSize() const {
645 FBSTRING_ASSERT(category() == Category::isSmall);
646 constexpr auto shift = kIsLittleEndian ? 0 : 2;
647 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
648 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
649 return static_cast<size_t>(maxSmallSize) - smallShifted;
652 void setSmallSize(size_t s) {
653 // Warning: this should work with uninitialized strings too,
654 // so don't assume anything about the previous value of
655 // small_[maxSmallSize].
656 FBSTRING_ASSERT(s <= maxSmallSize);
657 constexpr auto shift = kIsLittleEndian ? 0 : 2;
658 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
660 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
663 void copySmall(const fbstring_core&);
664 void copyMedium(const fbstring_core&);
665 void copyLarge(const fbstring_core&);
667 void initSmall(const Char* data, size_t size);
668 void initMedium(const Char* data, size_t size);
669 void initLarge(const Char* data, size_t size);
671 void reserveSmall(size_t minCapacity, bool disableSSO);
672 void reserveMedium(size_t minCapacity);
673 void reserveLarge(size_t minCapacity);
675 void shrinkSmall(size_t delta);
676 void shrinkMedium(size_t delta);
677 void shrinkLarge(size_t delta);
679 void unshare(size_t minCapacity = 0);
680 Char* mutableDataLarge();
683 template <class Char>
684 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
685 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
687 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
688 "fbstring layout failure");
690 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
691 "fbstring layout failure");
692 // Just write the whole thing, don't look at details. In
693 // particular we need to copy capacity anyway because we want
694 // to set the size (don't forget that the last character,
695 // which stores a short string's length, is shared with the
696 // ml_.capacity field).
699 category() == Category::isSmall && this->size() == rhs.size());
702 template <class Char>
703 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
704 const fbstring_core& rhs) {
705 // Medium strings are copied eagerly. Don't forget to allocate
706 // one extra Char for the null terminator.
707 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
708 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
709 // Also copies terminator.
710 fbstring_detail::podCopy(
711 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
712 ml_.size_ = rhs.ml_.size_;
713 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
714 FBSTRING_ASSERT(category() == Category::isMedium);
717 template <class Char>
718 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
719 const fbstring_core& rhs) {
720 // Large strings are just refcounted
722 RefCounted::incrementRefs(ml_.data_);
723 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
726 // Small strings are bitblitted
727 template <class Char>
728 inline void fbstring_core<Char>::initSmall(
729 const Char* const data, const size_t size) {
730 // Layout is: Char* data_, size_t size_, size_t capacity_
732 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
733 "fbstring has unexpected size");
735 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
736 // sizeof(size_t) must be a power of 2
738 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
739 "fbstring size assumption violation");
741 // If data is aligned, use fast word-wise copying. Otherwise,
742 // use conservative memcpy.
743 // The word-wise path reads bytes which are outside the range of
744 // the string, and makes ASan unhappy, so we disable it when
745 // compiling with ASan.
746 #ifndef FBSTRING_SANITIZE_ADDRESS
747 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
748 const size_t byteSize = size * sizeof(Char);
749 constexpr size_t wordWidth = sizeof(size_t);
750 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
752 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
754 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
756 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
764 fbstring_detail::podCopy(data, data + size, small_);
770 template <class Char>
771 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
772 const Char* const data, const size_t size) {
773 // Medium strings are allocated normally. Don't forget to
774 // allocate one extra Char for the terminating null.
775 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
776 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
777 if (FBSTRING_LIKELY(size > 0)) {
778 fbstring_detail::podCopy(data, data + size, ml_.data_);
781 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
782 ml_.data_[size] = '\0';
785 template <class Char>
786 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
787 const Char* const data, const size_t size) {
788 // Large strings are allocated differently
789 size_t effectiveCapacity = size;
790 auto const newRC = RefCounted::create(data, &effectiveCapacity);
791 ml_.data_ = newRC->data_;
793 ml_.setCapacity(effectiveCapacity, Category::isLarge);
794 ml_.data_[size] = '\0';
797 template <class Char>
798 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
799 size_t minCapacity) {
800 FBSTRING_ASSERT(category() == Category::isLarge);
801 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
802 auto const newRC = RefCounted::create(&effectiveCapacity);
803 // If this fails, someone placed the wrong capacity in an
805 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
806 // Also copies terminator.
807 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
808 RefCounted::decrementRefs(ml_.data_);
809 ml_.data_ = newRC->data_;
810 ml_.setCapacity(effectiveCapacity, Category::isLarge);
811 // size_ remains unchanged.
814 template <class Char>
815 inline Char* fbstring_core<Char>::mutableDataLarge() {
816 FBSTRING_ASSERT(category() == Category::isLarge);
817 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
823 template <class Char>
824 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
825 size_t minCapacity) {
826 FBSTRING_ASSERT(category() == Category::isLarge);
827 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
828 // We must make it unique regardless; in-place reallocation is
829 // useless if the string is shared. In order to not surprise
830 // people, reserve the new block at current capacity or
831 // more. That way, a string's capacity never shrinks after a
833 unshare(minCapacity);
835 // String is not shared, so let's try to realloc (if needed)
836 if (minCapacity > ml_.capacity()) {
837 // Asking for more memory
838 auto const newRC = RefCounted::reallocate(
839 ml_.data_, ml_.size_, ml_.capacity(), minCapacity);
840 ml_.data_ = newRC->data_;
841 ml_.setCapacity(minCapacity, Category::isLarge);
843 FBSTRING_ASSERT(capacity() >= minCapacity);
847 template <class Char>
848 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
849 const size_t minCapacity) {
850 FBSTRING_ASSERT(category() == Category::isMedium);
851 // String is not shared
852 if (minCapacity <= ml_.capacity()) {
853 return; // nothing to do, there's enough room
855 if (minCapacity <= maxMediumSize) {
856 // Keep the string at medium size. Don't forget to allocate
857 // one extra Char for the terminating null.
858 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
859 // Also copies terminator.
860 ml_.data_ = static_cast<Char*>(smartRealloc(
862 (ml_.size_ + 1) * sizeof(Char),
863 (ml_.capacity() + 1) * sizeof(Char),
865 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
867 // Conversion from medium to large string
868 fbstring_core nascent;
869 // Will recurse to another branch of this function
870 nascent.reserve(minCapacity);
871 nascent.ml_.size_ = ml_.size_;
872 // Also copies terminator.
873 fbstring_detail::podCopy(
874 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
876 FBSTRING_ASSERT(capacity() >= minCapacity);
880 template <class Char>
881 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
882 size_t minCapacity, const bool disableSSO) {
883 FBSTRING_ASSERT(category() == Category::isSmall);
884 if (!disableSSO && minCapacity <= maxSmallSize) {
886 // Nothing to do, everything stays put
887 } else if (minCapacity <= maxMediumSize) {
889 // Don't forget to allocate one extra Char for the terminating null
890 auto const allocSizeBytes =
891 goodMallocSize((1 + minCapacity) * sizeof(Char));
892 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
893 auto const size = smallSize();
894 // Also copies terminator.
895 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
898 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
901 auto const newRC = RefCounted::create(&minCapacity);
902 auto const size = smallSize();
903 // Also copies terminator.
904 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
905 ml_.data_ = newRC->data_;
907 ml_.setCapacity(minCapacity, Category::isLarge);
908 FBSTRING_ASSERT(capacity() >= minCapacity);
912 template <class Char>
913 inline Char* fbstring_core<Char>::expandNoinit(
915 bool expGrowth, /* = false */
916 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
917 // Strategy is simple: make room, then change size
918 FBSTRING_ASSERT(capacity() >= size());
920 if (category() == Category::isSmall) {
923 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
928 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
932 if (FBSTRING_UNLIKELY(newSz > capacity())) {
933 // ensures not shared
934 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
937 FBSTRING_ASSERT(capacity() >= newSz);
938 // Category can't be small - we took care of that above
940 category() == Category::isMedium || category() == Category::isLarge);
942 ml_.data_[newSz] = '\0';
943 FBSTRING_ASSERT(size() == newSz);
944 return ml_.data_ + sz;
947 template <class Char>
948 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
949 // Check for underflow
950 FBSTRING_ASSERT(delta <= smallSize());
951 setSmallSize(smallSize() - delta);
954 template <class Char>
955 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
956 // Medium strings and unique large strings need no special
958 FBSTRING_ASSERT(ml_.size_ >= delta);
960 ml_.data_[ml_.size_] = '\0';
963 template <class Char>
964 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
965 FBSTRING_ASSERT(ml_.size_ >= delta);
966 // Shared large string, must make unique. This is because of the
967 // durn terminator must be written, which may trample the shared
970 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
972 // No need to write the terminator.
975 #ifndef _LIBSTDCXX_FBSTRING
977 * Dummy fbstring core that uses an actual std::string. This doesn't
978 * make any sense - it's just for testing purposes.
980 template <class Char>
981 class dummy_fbstring_core {
983 dummy_fbstring_core() {
985 dummy_fbstring_core(const dummy_fbstring_core& another)
986 : backend_(another.backend_) {
988 dummy_fbstring_core(const Char * s, size_t n)
991 void swap(dummy_fbstring_core & rhs) {
992 backend_.swap(rhs.backend_);
994 const Char * data() const {
995 return backend_.data();
997 Char* mutableData() {
998 return const_cast<Char*>(backend_.data());
1000 void shrink(size_t delta) {
1001 FBSTRING_ASSERT(delta <= size());
1002 backend_.resize(size() - delta);
1004 Char* expandNoinit(size_t delta) {
1005 auto const sz = size();
1006 backend_.resize(size() + delta);
1007 return backend_.data() + sz;
1009 void push_back(Char c) {
1010 backend_.push_back(c);
1012 size_t size() const {
1013 return backend_.size();
1015 size_t capacity() const {
1016 return backend_.capacity();
1018 bool isShared() const {
1021 void reserve(size_t minCapacity) {
1022 backend_.reserve(minCapacity);
1026 std::basic_string<Char> backend_;
1028 #endif // !_LIBSTDCXX_FBSTRING
1031 * This is the basic_string replacement. For conformity,
1032 * basic_fbstring takes the same template parameters, plus the last
1033 * one which is the core.
1035 #ifdef _LIBSTDCXX_FBSTRING
1036 template <typename E, class T, class A, class Storage>
1038 template <typename E,
1039 class T = std::char_traits<E>,
1040 class A = std::allocator<E>,
1041 class Storage = fbstring_core<E> >
1043 class basic_fbstring {
1044 static void enforce(
1046 void (*throw_exc)(const char*),
1053 bool isSane() const {
1056 empty() == (size() == 0) &&
1057 empty() == (begin() == end()) &&
1058 size() <= max_size() &&
1059 capacity() <= max_size() &&
1060 size() <= capacity() &&
1061 begin()[size()] == '\0';
1065 Invariant& operator=(const Invariant&) = delete;
1066 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1067 FBSTRING_ASSERT(s_.isSane());
1069 ~Invariant() noexcept {
1070 FBSTRING_ASSERT(s_.isSane());
1074 const basic_fbstring& s_;
1079 typedef T traits_type;
1080 typedef typename traits_type::char_type value_type;
1081 typedef A allocator_type;
1082 typedef typename A::size_type size_type;
1083 typedef typename A::difference_type difference_type;
1085 typedef typename A::reference reference;
1086 typedef typename A::const_reference const_reference;
1087 typedef typename A::pointer pointer;
1088 typedef typename A::const_pointer const_pointer;
1090 typedef E* iterator;
1091 typedef const E* const_iterator;
1092 typedef std::reverse_iterator<iterator
1093 #ifdef NO_ITERATOR_TRAITS
1097 typedef std::reverse_iterator<const_iterator
1098 #ifdef NO_ITERATOR_TRAITS
1101 > const_reverse_iterator;
1103 static constexpr size_type npos = size_type(-1);
1104 typedef std::true_type IsRelocatable;
1107 static void procrustes(size_type& n, size_type nmax) {
1113 static size_type traitsLength(const value_type* s);
1116 // C++11 21.4.2 construct/copy/destroy
1118 // Note: while the following two constructors can be (and previously were)
1119 // collapsed into one constructor written this way:
1121 // explicit basic_fbstring(const A& a = A()) noexcept { }
1123 // This can cause Clang (at least version 3.7) to fail with the error:
1124 // "chosen constructor is explicit in copy-initialization ...
1125 // in implicit initialization of field '(x)' with omitted initializer"
1127 // if used in a struct which is default-initialized. Hence the split into
1128 // these two separate constructors.
1130 basic_fbstring() noexcept : basic_fbstring(A()) {
1133 explicit basic_fbstring(const A&) noexcept {
1136 basic_fbstring(const basic_fbstring& str)
1137 : store_(str.store_) {
1141 basic_fbstring(basic_fbstring&& goner) noexcept
1142 : store_(std::move(goner.store_)) {
1145 #ifndef _LIBSTDCXX_FBSTRING
1146 // This is defined for compatibility with std::string
1147 /* implicit */ basic_fbstring(const std::string& str)
1148 : store_(str.data(), str.size()) {
1152 basic_fbstring(const basic_fbstring& str,
1155 const A& /* a */ = A()) {
1156 assign(str, pos, n);
1159 FOLLY_MALLOC_NOINLINE
1160 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1161 : store_(s, traitsLength(s)) {}
1163 FOLLY_MALLOC_NOINLINE
1164 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1168 FOLLY_MALLOC_NOINLINE
1169 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1170 auto const pData = store_.expandNoinit(n);
1171 fbstring_detail::podFill(pData, pData + n, c);
1174 template <class InIt>
1175 FOLLY_MALLOC_NOINLINE basic_fbstring(
1178 typename std::enable_if<
1179 !std::is_same<InIt, value_type*>::value,
1180 const A>::type& /*a*/ = A()) {
1184 // Specialization for const char*, const char*
1185 FOLLY_MALLOC_NOINLINE
1186 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1187 : store_(b, size_type(e - b)) {
1190 // Nonstandard constructor
1191 basic_fbstring(value_type *s, size_type n, size_type c,
1192 AcquireMallocatedString a)
1193 : store_(s, n, c, a) {
1196 // Construction from initialization list
1197 FOLLY_MALLOC_NOINLINE
1198 basic_fbstring(std::initializer_list<value_type> il) {
1199 assign(il.begin(), il.end());
1202 ~basic_fbstring() noexcept {}
1204 basic_fbstring& operator=(const basic_fbstring& lhs);
1207 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1209 #ifndef _LIBSTDCXX_FBSTRING
1210 // Compatibility with std::string
1211 basic_fbstring & operator=(const std::string & rhs) {
1212 return assign(rhs.data(), rhs.size());
1215 // Compatibility with std::string
1216 std::string toStdString() const {
1217 return std::string(data(), size());
1220 // A lot of code in fbcode still uses this method, so keep it here for now.
1221 const basic_fbstring& toStdString() const {
1226 basic_fbstring& operator=(const value_type* s) {
1230 basic_fbstring& operator=(value_type c);
1232 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1233 return assign(il.begin(), il.end());
1236 // C++11 21.4.3 iterators:
1238 return store_.mutableData();
1241 const_iterator begin() const {
1242 return store_.data();
1245 const_iterator cbegin() const {
1250 return store_.mutableData() + store_.size();
1253 const_iterator end() const {
1254 return store_.data() + store_.size();
1257 const_iterator cend() const { return end(); }
1259 reverse_iterator rbegin() {
1260 return reverse_iterator(end());
1263 const_reverse_iterator rbegin() const {
1264 return const_reverse_iterator(end());
1267 const_reverse_iterator crbegin() const { return rbegin(); }
1269 reverse_iterator rend() {
1270 return reverse_iterator(begin());
1273 const_reverse_iterator rend() const {
1274 return const_reverse_iterator(begin());
1277 const_reverse_iterator crend() const { return rend(); }
1280 // C++11 21.4.5, element access:
1281 const value_type& front() const { return *begin(); }
1282 const value_type& back() const {
1283 FBSTRING_ASSERT(!empty());
1284 // Should be begin()[size() - 1], but that branches twice
1285 return *(end() - 1);
1287 value_type& front() { return *begin(); }
1288 value_type& back() {
1289 FBSTRING_ASSERT(!empty());
1290 // Should be begin()[size() - 1], but that branches twice
1291 return *(end() - 1);
1294 FBSTRING_ASSERT(!empty());
1298 // C++11 21.4.4 capacity:
1299 size_type size() const { return store_.size(); }
1301 size_type length() const { return size(); }
1303 size_type max_size() const {
1304 return std::numeric_limits<size_type>::max();
1307 void resize(size_type n, value_type c = value_type());
1309 size_type capacity() const { return store_.capacity(); }
1311 void reserve(size_type res_arg = 0) {
1312 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1313 store_.reserve(res_arg);
1316 void shrink_to_fit() {
1317 // Shrink only if slack memory is sufficiently large
1318 if (capacity() < size() * 3 / 2) {
1321 basic_fbstring(cbegin(), cend()).swap(*this);
1324 void clear() { resize(0); }
1326 bool empty() const { return size() == 0; }
1328 // C++11 21.4.5 element access:
1329 const_reference operator[](size_type pos) const {
1330 return *(begin() + pos);
1333 reference operator[](size_type pos) {
1334 return *(begin() + pos);
1337 const_reference at(size_type n) const {
1338 enforce(n <= size(), std::__throw_out_of_range, "");
1342 reference at(size_type n) {
1343 enforce(n < size(), std::__throw_out_of_range, "");
1347 // C++11 21.4.6 modifiers:
1348 basic_fbstring& operator+=(const basic_fbstring& str) {
1352 basic_fbstring& operator+=(const value_type* s) {
1356 basic_fbstring& operator+=(const value_type c) {
1361 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1366 basic_fbstring& append(const basic_fbstring& str);
1369 append(const basic_fbstring& str, const size_type pos, size_type n);
1371 basic_fbstring& append(const value_type* s, size_type n);
1373 basic_fbstring& append(const value_type* s) {
1374 return append(s, traitsLength(s));
1377 basic_fbstring& append(size_type n, value_type c);
1379 template<class InputIterator>
1380 basic_fbstring& append(InputIterator first, InputIterator last) {
1381 insert(end(), first, last);
1385 basic_fbstring& append(std::initializer_list<value_type> il) {
1386 return append(il.begin(), il.end());
1389 void push_back(const value_type c) { // primitive
1390 store_.push_back(c);
1393 basic_fbstring& assign(const basic_fbstring& str) {
1394 if (&str == this) return *this;
1395 return assign(str.data(), str.size());
1398 basic_fbstring& assign(basic_fbstring&& str) {
1399 return *this = std::move(str);
1403 assign(const basic_fbstring& str, const size_type pos, size_type n);
1405 basic_fbstring& assign(const value_type* s, const size_type n);
1407 basic_fbstring& assign(const value_type* s) {
1408 return assign(s, traitsLength(s));
1411 basic_fbstring& assign(std::initializer_list<value_type> il) {
1412 return assign(il.begin(), il.end());
1415 template <class ItOrLength, class ItOrChar>
1416 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1417 return replace(begin(), end(), first_or_n, last_or_c);
1420 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1421 return insert(pos1, str.data(), str.size());
1424 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1425 size_type pos2, size_type n) {
1426 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1427 procrustes(n, str.length() - pos2);
1428 return insert(pos1, str.data() + pos2, n);
1431 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1432 enforce(pos <= length(), std::__throw_out_of_range, "");
1433 insert(begin() + pos, s, s + n);
1437 basic_fbstring& insert(size_type pos, const value_type* s) {
1438 return insert(pos, s, traitsLength(s));
1441 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1442 enforce(pos <= length(), std::__throw_out_of_range, "");
1443 insert(begin() + pos, n, c);
1447 iterator insert(const_iterator p, const value_type c) {
1448 const size_type pos = p - cbegin();
1450 return begin() + pos;
1453 #ifndef _LIBSTDCXX_FBSTRING
1455 typedef std::basic_istream<value_type, traits_type> istream_type;
1456 istream_type& getlineImpl(istream_type& is, value_type delim);
1459 friend inline istream_type& getline(istream_type& is,
1460 basic_fbstring& str,
1462 return str.getlineImpl(is, delim);
1465 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1466 return getline(is, str, '\n');
1472 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1474 template <class InputIter>
1476 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1478 template <class FwdIterator>
1479 iterator insertImpl(
1483 std::forward_iterator_tag);
1485 template <class InputIterator>
1486 iterator insertImpl(
1490 std::input_iterator_tag);
1493 template <class ItOrLength, class ItOrChar>
1494 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1495 using Sel = std::integral_constant<
1497 std::numeric_limits<ItOrLength>::is_specialized>;
1498 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1501 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1502 return insert(p, il.begin(), il.end());
1505 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1506 Invariant checker(*this);
1508 enforce(pos <= length(), std::__throw_out_of_range, "");
1509 procrustes(n, length() - pos);
1510 std::copy(begin() + pos + n, end(), begin() + pos);
1511 resize(length() - n);
1515 iterator erase(iterator position) {
1516 const size_type pos(position - begin());
1517 enforce(pos <= size(), std::__throw_out_of_range, "");
1519 return begin() + pos;
1522 iterator erase(iterator first, iterator last) {
1523 const size_type pos(first - begin());
1524 erase(pos, last - first);
1525 return begin() + pos;
1528 // Replaces at most n1 chars of *this, starting with pos1 with the
1530 basic_fbstring& replace(size_type pos1, size_type n1,
1531 const basic_fbstring& str) {
1532 return replace(pos1, n1, str.data(), str.size());
1535 // Replaces at most n1 chars of *this, starting with pos1,
1536 // with at most n2 chars of str starting with pos2
1537 basic_fbstring& replace(size_type pos1, size_type n1,
1538 const basic_fbstring& str,
1539 size_type pos2, size_type n2) {
1540 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1541 return replace(pos1, n1, str.data() + pos2,
1542 std::min(n2, str.size() - pos2));
1545 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1546 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1547 return replace(pos, n1, s, traitsLength(s));
1550 // Replaces at most n1 chars of *this, starting with pos, with n2
1553 // consolidated with
1555 // Replaces at most n1 chars of *this, starting with pos, with at
1556 // most n2 chars of str. str must have at least n2 chars.
1557 template <class StrOrLength, class NumOrChar>
1558 basic_fbstring& replace(size_type pos, size_type n1,
1559 StrOrLength s_or_n2, NumOrChar n_or_c) {
1560 Invariant checker(*this);
1562 enforce(pos <= size(), std::__throw_out_of_range, "");
1563 procrustes(n1, length() - pos);
1564 const iterator b = begin() + pos;
1565 return replace(b, b + n1, s_or_n2, n_or_c);
1568 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1569 return replace(i1, i2, str.data(), str.length());
1572 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1573 return replace(i1, i2, s, traitsLength(s));
1577 basic_fbstring& replaceImplDiscr(
1580 const value_type* s,
1582 std::integral_constant<int, 2>);
1584 basic_fbstring& replaceImplDiscr(
1589 std::integral_constant<int, 1>);
1591 template <class InputIter>
1592 basic_fbstring& replaceImplDiscr(
1597 std::integral_constant<int, 0>);
1600 template <class FwdIterator>
1601 bool replaceAliased(iterator /* i1 */,
1603 FwdIterator /* s1 */,
1604 FwdIterator /* s2 */,
1609 template <class FwdIterator>
1610 bool replaceAliased(
1617 template <class FwdIterator>
1623 std::forward_iterator_tag);
1625 template <class InputIterator>
1631 std::input_iterator_tag);
1634 template <class T1, class T2>
1635 basic_fbstring& replace(iterator i1, iterator i2,
1636 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1637 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1638 num2 = std::numeric_limits<T2>::is_specialized;
1640 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1641 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1644 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1645 enforce(pos <= size(), std::__throw_out_of_range, "");
1646 procrustes(n, size() - pos);
1649 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1654 void swap(basic_fbstring& rhs) {
1655 store_.swap(rhs.store_);
1658 const value_type* c_str() const {
1659 return store_.c_str();
1662 const value_type* data() const { return c_str(); }
1664 allocator_type get_allocator() const {
1665 return allocator_type();
1668 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1669 return find(str.data(), pos, str.length());
1672 size_type find(const value_type* needle, size_type pos, size_type nsize)
1675 size_type find(const value_type* s, size_type pos = 0) const {
1676 return find(s, pos, traitsLength(s));
1679 size_type find (value_type c, size_type pos = 0) const {
1680 return find(&c, pos, 1);
1683 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1684 return rfind(str.data(), pos, str.length());
1687 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1689 size_type rfind(const value_type* s, size_type pos = npos) const {
1690 return rfind(s, pos, traitsLength(s));
1693 size_type rfind(value_type c, size_type pos = npos) const {
1694 return rfind(&c, pos, 1);
1697 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1698 return find_first_of(str.data(), pos, str.length());
1701 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1704 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1705 return find_first_of(s, pos, traitsLength(s));
1708 size_type find_first_of(value_type c, size_type pos = 0) const {
1709 return find_first_of(&c, pos, 1);
1712 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1714 return find_last_of(str.data(), pos, str.length());
1717 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1719 size_type find_last_of (const value_type* s,
1720 size_type pos = npos) const {
1721 return find_last_of(s, pos, traitsLength(s));
1724 size_type find_last_of (value_type c, size_type pos = npos) const {
1725 return find_last_of(&c, pos, 1);
1728 size_type find_first_not_of(const basic_fbstring& str,
1729 size_type pos = 0) const {
1730 return find_first_not_of(str.data(), pos, str.size());
1733 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1736 size_type find_first_not_of(const value_type* s,
1737 size_type pos = 0) const {
1738 return find_first_not_of(s, pos, traitsLength(s));
1741 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1742 return find_first_not_of(&c, pos, 1);
1745 size_type find_last_not_of(const basic_fbstring& str,
1746 size_type pos = npos) const {
1747 return find_last_not_of(str.data(), pos, str.length());
1750 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1753 size_type find_last_not_of(const value_type* s,
1754 size_type pos = npos) const {
1755 return find_last_not_of(s, pos, traitsLength(s));
1758 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1759 return find_last_not_of(&c, pos, 1);
1762 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1763 enforce(pos <= size(), std::__throw_out_of_range, "");
1764 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1767 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1768 enforce(pos <= size(), std::__throw_out_of_range, "");
1773 return std::move(*this);
1776 int compare(const basic_fbstring& str) const {
1777 // FIX due to Goncalo N M de Carvalho July 18, 2005
1778 return compare(0, size(), str);
1781 int compare(size_type pos1, size_type n1,
1782 const basic_fbstring& str) const {
1783 return compare(pos1, n1, str.data(), str.size());
1786 int compare(size_type pos1, size_type n1,
1787 const value_type* s) const {
1788 return compare(pos1, n1, s, traitsLength(s));
1791 int compare(size_type pos1, size_type n1,
1792 const value_type* s, size_type n2) const {
1793 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1794 procrustes(n1, size() - pos1);
1795 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1796 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1797 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1800 int compare(size_type pos1, size_type n1,
1801 const basic_fbstring& str,
1802 size_type pos2, size_type n2) const {
1803 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1804 return compare(pos1, n1, str.data() + pos2,
1805 std::min(n2, str.size() - pos2));
1808 // Code from Jean-Francois Bastien (03/26/2007)
1809 int compare(const value_type* s) const {
1810 // Could forward to compare(0, size(), s, traitsLength(s))
1811 // but that does two extra checks
1812 const size_type n1(size()), n2(traitsLength(s));
1813 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1814 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1822 template <typename E, class T, class A, class S>
1823 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1824 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1825 return s ? traits_type::length(s)
1826 : (std::__throw_logic_error(
1827 "basic_fbstring: null pointer initializer not valid"),
1831 template <typename E, class T, class A, class S>
1832 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1833 const basic_fbstring& lhs) {
1834 Invariant checker(*this);
1836 if (FBSTRING_UNLIKELY(&lhs == this)) {
1840 return assign(lhs.data(), lhs.size());
1844 template <typename E, class T, class A, class S>
1845 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1846 basic_fbstring&& goner) noexcept {
1847 if (FBSTRING_UNLIKELY(&goner == this)) {
1848 // Compatibility with std::basic_string<>,
1849 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1852 // No need of this anymore
1853 this->~basic_fbstring();
1854 // Move the goner into this
1855 new (&store_) S(std::move(goner.store_));
1859 template <typename E, class T, class A, class S>
1860 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1861 const value_type c) {
1862 Invariant checker(*this);
1865 store_.expandNoinit(1);
1866 } else if (store_.isShared()) {
1867 basic_fbstring(1, c).swap(*this);
1870 store_.shrink(size() - 1);
1876 template <typename E, class T, class A, class S>
1877 inline void basic_fbstring<E, T, A, S>::resize(
1878 const size_type n, const value_type c /*= value_type()*/) {
1879 Invariant checker(*this);
1881 auto size = this->size();
1883 store_.shrink(size - n);
1885 auto const delta = n - size;
1886 auto pData = store_.expandNoinit(delta);
1887 fbstring_detail::podFill(pData, pData + delta, c);
1889 FBSTRING_ASSERT(this->size() == n);
1892 template <typename E, class T, class A, class S>
1893 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1894 const basic_fbstring& str) {
1896 auto desiredSize = size() + str.size();
1898 append(str.data(), str.size());
1899 FBSTRING_ASSERT(size() == desiredSize);
1903 template <typename E, class T, class A, class S>
1904 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1905 const basic_fbstring& str, const size_type pos, size_type n) {
1906 const size_type sz = str.size();
1907 enforce(pos <= sz, std::__throw_out_of_range, "");
1908 procrustes(n, sz - pos);
1909 return append(str.data() + pos, n);
1912 template <typename E, class T, class A, class S>
1913 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1914 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1915 Invariant checker(*this);
1917 if (FBSTRING_UNLIKELY(!n)) {
1918 // Unlikely but must be done
1921 auto const oldSize = size();
1922 auto const oldData = data();
1923 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1925 // Check for aliasing (rare). We could use "<=" here but in theory
1926 // those do not work for pointers unless the pointers point to
1927 // elements in the same array. For that reason we use
1928 // std::less_equal, which is guaranteed to offer a total order
1929 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1931 std::less_equal<const value_type*> le;
1932 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1933 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1934 // expandNoinit() could have moved the storage, restore the source.
1935 s = data() + (s - oldData);
1936 fbstring_detail::podMove(s, s + n, pData);
1938 fbstring_detail::podCopy(s, s + n, pData);
1941 FBSTRING_ASSERT(size() == oldSize + n);
1945 template <typename E, class T, class A, class S>
1946 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1947 size_type n, value_type c) {
1948 Invariant checker(*this);
1949 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1950 fbstring_detail::podFill(pData, pData + n, c);
1954 template <typename E, class T, class A, class S>
1955 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1956 const basic_fbstring& str, const size_type pos, size_type n) {
1957 const size_type sz = str.size();
1958 enforce(pos <= sz, std::__throw_out_of_range, "");
1959 procrustes(n, sz - pos);
1960 return assign(str.data() + pos, n);
1963 template <typename E, class T, class A, class S>
1964 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1965 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1966 Invariant checker(*this);
1970 } else if (size() >= n) {
1971 // s can alias this, we need to use podMove.
1972 fbstring_detail::podMove(s, s + n, store_.mutableData());
1973 store_.shrink(size() - n);
1974 FBSTRING_ASSERT(size() == n);
1976 // If n is larger than size(), s cannot alias this string's
1979 // Do not use exponential growth here: assign() should be tight,
1980 // to mirror the behavior of the equivalent constructor.
1981 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
1984 FBSTRING_ASSERT(size() == n);
1988 #ifndef _LIBSTDCXX_FBSTRING
1989 template <typename E, class T, class A, class S>
1990 inline typename basic_fbstring<E, T, A, S>::istream_type&
1991 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
1992 Invariant checker(*this);
1997 size_t avail = capacity() - size;
1998 // fbstring has 1 byte extra capacity for the null terminator,
1999 // and getline null-terminates the read string.
2000 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2001 size += is.gcount();
2003 if (is.bad() || is.eof() || !is.fail()) {
2004 // Done by either failure, end of file, or normal read.
2005 if (!is.bad() && !is.eof()) {
2006 --size; // gcount() also accounts for the delimiter.
2012 FBSTRING_ASSERT(size == this->size());
2013 FBSTRING_ASSERT(size == capacity());
2014 // Start at minimum allocation 63 + terminator = 64.
2015 reserve(std::max<size_t>(63, 3 * size / 2));
2016 // Clear the error so we can continue reading.
2023 template <typename E, class T, class A, class S>
2024 inline typename basic_fbstring<E, T, A, S>::size_type
2025 basic_fbstring<E, T, A, S>::find(
2026 const value_type* needle, const size_type pos, const size_type nsize)
2028 auto const size = this->size();
2029 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2030 // that nsize + pos does not wrap around.
2031 if (nsize + pos > size || nsize + pos < pos) {
2038 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2039 // the last characters first
2040 auto const haystack = data();
2041 auto const nsize_1 = nsize - 1;
2042 auto const lastNeedle = needle[nsize_1];
2044 // Boyer-Moore skip value for the last char in the needle. Zero is
2045 // not a valid value; skip will be computed the first time it's
2049 const E* i = haystack + pos;
2050 auto iEnd = haystack + size - nsize_1;
2053 // Boyer-Moore: match the last element in the needle
2054 while (i[nsize_1] != lastNeedle) {
2060 // Here we know that the last char matches
2061 // Continue in pedestrian mode
2062 for (size_t j = 0;;) {
2063 FBSTRING_ASSERT(j < nsize);
2064 if (i[j] != needle[j]) {
2065 // Not found, we can skip
2066 // Compute the skip value lazily
2069 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2076 // Check if done searching
2079 return i - haystack;
2086 template <typename E, class T, class A, class S>
2087 inline typename basic_fbstring<E, T, A, S>::iterator
2088 basic_fbstring<E, T, A, S>::insertImplDiscr(
2089 const_iterator i, size_type n, value_type c, std::true_type) {
2090 Invariant checker(*this);
2092 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2093 const size_type pos = i - cbegin();
2095 auto oldSize = size();
2096 store_.expandNoinit(n, /* expGrowth = */ true);
2098 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2099 fbstring_detail::podFill(b + pos, b + pos + n, c);
2104 template <typename E, class T, class A, class S>
2105 template <class InputIter>
2106 inline typename basic_fbstring<E, T, A, S>::iterator
2107 basic_fbstring<E, T, A, S>::insertImplDiscr(
2108 const_iterator i, InputIter b, InputIter e, std::false_type) {
2110 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2113 template <typename E, class T, class A, class S>
2114 template <class FwdIterator>
2115 inline typename basic_fbstring<E, T, A, S>::iterator
2116 basic_fbstring<E, T, A, S>::insertImpl(
2120 std::forward_iterator_tag) {
2121 Invariant checker(*this);
2123 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2124 const size_type pos = i - cbegin();
2125 auto n = std::distance(s1, s2);
2126 FBSTRING_ASSERT(n >= 0);
2128 auto oldSize = size();
2129 store_.expandNoinit(n, /* expGrowth = */ true);
2131 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2132 std::copy(s1, s2, b + pos);
2137 template <typename E, class T, class A, class S>
2138 template <class InputIterator>
2139 inline typename basic_fbstring<E, T, A, S>::iterator
2140 basic_fbstring<E, T, A, S>::insertImpl(
2144 std::input_iterator_tag) {
2145 const auto pos = i - cbegin();
2146 basic_fbstring temp(cbegin(), i);
2147 for (; b != e; ++b) {
2150 temp.append(i, cend());
2152 return begin() + pos;
2155 template <typename E, class T, class A, class S>
2156 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2159 const value_type* s,
2161 std::integral_constant<int, 2>) {
2162 FBSTRING_ASSERT(i1 <= i2);
2163 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2164 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2165 return replace(i1, i2, s, s + n);
2168 template <typename E, class T, class A, class S>
2169 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2174 std::integral_constant<int, 1>) {
2175 const size_type n1 = i2 - i1;
2177 std::fill(i1, i1 + n2, c);
2180 std::fill(i1, i2, c);
2181 insert(i2, n2 - n1, c);
2183 FBSTRING_ASSERT(isSane());
2187 template <typename E, class T, class A, class S>
2188 template <class InputIter>
2189 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2194 std::integral_constant<int, 0>) {
2195 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2196 replaceImpl(i1, i2, b, e, Cat());
2200 template <typename E, class T, class A, class S>
2201 template <class FwdIterator>
2202 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2203 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2204 std::less_equal<const value_type*> le{};
2205 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2209 // Aliased replace, copy to new string
2210 basic_fbstring temp;
2211 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2212 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2217 template <typename E, class T, class A, class S>
2218 template <class FwdIterator>
2219 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2224 std::forward_iterator_tag) {
2225 Invariant checker(*this);
2227 // Handle aliased replace
2228 using Sel = std::integral_constant<
2230 std::is_same<FwdIterator, iterator>::value ||
2231 std::is_same<FwdIterator, const_iterator>::value>;
2232 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2236 auto const n1 = i2 - i1;
2237 FBSTRING_ASSERT(n1 >= 0);
2238 auto const n2 = std::distance(s1, s2);
2239 FBSTRING_ASSERT(n2 >= 0);
2243 std::copy(s1, s2, i1);
2247 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2250 FBSTRING_ASSERT(isSane());
2253 template <typename E, class T, class A, class S>
2254 template <class InputIterator>
2255 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2260 std::input_iterator_tag) {
2261 basic_fbstring temp(begin(), i1);
2262 temp.append(b, e).append(i2, end());
2266 template <typename E, class T, class A, class S>
2267 inline typename basic_fbstring<E, T, A, S>::size_type
2268 basic_fbstring<E, T, A, S>::rfind(
2269 const value_type* s, size_type pos, size_type n) const {
2273 pos = std::min(pos, length() - n);
2278 const_iterator i(begin() + pos);
2280 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2290 template <typename E, class T, class A, class S>
2291 inline typename basic_fbstring<E, T, A, S>::size_type
2292 basic_fbstring<E, T, A, S>::find_first_of(
2293 const value_type* s, size_type pos, size_type n) const {
2294 if (pos > length() || n == 0) {
2297 const_iterator i(begin() + pos), finish(end());
2298 for (; i != finish; ++i) {
2299 if (traits_type::find(s, n, *i) != 0) {
2306 template <typename E, class T, class A, class S>
2307 inline typename basic_fbstring<E, T, A, S>::size_type
2308 basic_fbstring<E, T, A, S>::find_last_of(
2309 const value_type* s, size_type pos, size_type n) const {
2310 if (!empty() && n > 0) {
2311 pos = std::min(pos, length() - 1);
2312 const_iterator i(begin() + pos);
2314 if (traits_type::find(s, n, *i) != 0) {
2325 template <typename E, class T, class A, class S>
2326 inline typename basic_fbstring<E, T, A, S>::size_type
2327 basic_fbstring<E, T, A, S>::find_first_not_of(
2328 const value_type* s, size_type pos, size_type n) const {
2329 if (pos < length()) {
2330 const_iterator i(begin() + pos), finish(end());
2331 for (; i != finish; ++i) {
2332 if (traits_type::find(s, n, *i) == 0) {
2340 template <typename E, class T, class A, class S>
2341 inline typename basic_fbstring<E, T, A, S>::size_type
2342 basic_fbstring<E, T, A, S>::find_last_not_of(
2343 const value_type* s, size_type pos, size_type n) const {
2344 if (!this->empty()) {
2345 pos = std::min(pos, size() - 1);
2346 const_iterator i(begin() + pos);
2348 if (traits_type::find(s, n, *i) == 0) {
2359 // non-member functions
2361 template <typename E, class T, class A, class S>
2363 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2364 const basic_fbstring<E, T, A, S>& rhs) {
2366 basic_fbstring<E, T, A, S> result;
2367 result.reserve(lhs.size() + rhs.size());
2368 result.append(lhs).append(rhs);
2369 return std::move(result);
2373 template <typename E, class T, class A, class S>
2375 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2376 const basic_fbstring<E, T, A, S>& rhs) {
2377 return std::move(lhs.append(rhs));
2381 template <typename E, class T, class A, class S>
2383 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2384 basic_fbstring<E, T, A, S>&& rhs) {
2385 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2386 // Good, at least we don't need to reallocate
2387 return std::move(rhs.insert(0, lhs));
2389 // Meh, no go. Forward to operator+(const&, const&).
2390 auto const& rhsC = rhs;
2395 template <typename E, class T, class A, class S>
2397 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2398 basic_fbstring<E, T, A, S>&& rhs) {
2399 return std::move(lhs.append(rhs));
2403 template <typename E, class T, class A, class S>
2405 basic_fbstring<E, T, A, S> operator+(
2407 const basic_fbstring<E, T, A, S>& rhs) {
2409 basic_fbstring<E, T, A, S> result;
2410 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2411 result.reserve(len + rhs.size());
2412 result.append(lhs, len).append(rhs);
2417 template <typename E, class T, class A, class S>
2419 basic_fbstring<E, T, A, S> operator+(
2421 basic_fbstring<E, T, A, S>&& rhs) {
2423 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2424 if (rhs.capacity() >= len + rhs.size()) {
2425 // Good, at least we don't need to reallocate
2426 rhs.insert(rhs.begin(), lhs, lhs + len);
2429 // Meh, no go. Do it by hand since we have len already.
2430 basic_fbstring<E, T, A, S> result;
2431 result.reserve(len + rhs.size());
2432 result.append(lhs, len).append(rhs);
2437 template <typename E, class T, class A, class S>
2439 basic_fbstring<E, T, A, S> operator+(
2441 const basic_fbstring<E, T, A, S>& rhs) {
2443 basic_fbstring<E, T, A, S> result;
2444 result.reserve(1 + rhs.size());
2445 result.push_back(lhs);
2451 template <typename E, class T, class A, class S>
2453 basic_fbstring<E, T, A, S> operator+(
2455 basic_fbstring<E, T, A, S>&& rhs) {
2457 if (rhs.capacity() > rhs.size()) {
2458 // Good, at least we don't need to reallocate
2459 rhs.insert(rhs.begin(), lhs);
2462 // Meh, no go. Forward to operator+(E, const&).
2463 auto const& rhsC = rhs;
2468 template <typename E, class T, class A, class S>
2470 basic_fbstring<E, T, A, S> operator+(
2471 const basic_fbstring<E, T, A, S>& lhs,
2474 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2475 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2477 basic_fbstring<E, T, A, S> result;
2478 const size_type len = traits_type::length(rhs);
2479 result.reserve(lhs.size() + len);
2480 result.append(lhs).append(rhs, len);
2484 // C++11 21.4.8.1/10
2485 template <typename E, class T, class A, class S>
2487 basic_fbstring<E, T, A, S> operator+(
2488 basic_fbstring<E, T, A, S>&& lhs,
2491 return std::move(lhs += rhs);
2494 // C++11 21.4.8.1/11
2495 template <typename E, class T, class A, class S>
2497 basic_fbstring<E, T, A, S> operator+(
2498 const basic_fbstring<E, T, A, S>& lhs,
2501 basic_fbstring<E, T, A, S> result;
2502 result.reserve(lhs.size() + 1);
2504 result.push_back(rhs);
2508 // C++11 21.4.8.1/12
2509 template <typename E, class T, class A, class S>
2511 basic_fbstring<E, T, A, S> operator+(
2512 basic_fbstring<E, T, A, S>&& lhs,
2515 return std::move(lhs += rhs);
2518 template <typename E, class T, class A, class S>
2520 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2521 const basic_fbstring<E, T, A, S>& rhs) {
2522 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2524 template <typename E, class T, class A, class S>
2526 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2527 const basic_fbstring<E, T, A, S>& rhs) {
2528 return rhs == lhs; }
2530 template <typename E, class T, class A, class S>
2532 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2533 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2534 return lhs.compare(rhs) == 0; }
2536 template <typename E, class T, class A, class S>
2538 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2539 const basic_fbstring<E, T, A, S>& rhs) {
2540 return !(lhs == rhs); }
2542 template <typename E, class T, class A, class S>
2544 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2545 const basic_fbstring<E, T, A, S>& rhs) {
2546 return !(lhs == rhs); }
2548 template <typename E, class T, class A, class S>
2550 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2551 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2552 return !(lhs == rhs); }
2554 template <typename E, class T, class A, class S>
2556 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2557 const basic_fbstring<E, T, A, S>& rhs) {
2558 return lhs.compare(rhs) < 0; }
2560 template <typename E, class T, class A, class S>
2562 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2563 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2564 return lhs.compare(rhs) < 0; }
2566 template <typename E, class T, class A, class S>
2568 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2569 const basic_fbstring<E, T, A, S>& rhs) {
2570 return rhs.compare(lhs) > 0; }
2572 template <typename E, class T, class A, class S>
2574 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2575 const basic_fbstring<E, T, A, S>& rhs) {
2578 template <typename E, class T, class A, class S>
2580 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2581 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2584 template <typename E, class T, class A, class S>
2586 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2587 const basic_fbstring<E, T, A, S>& rhs) {
2590 template <typename E, class T, class A, class S>
2592 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2593 const basic_fbstring<E, T, A, S>& rhs) {
2594 return !(rhs < lhs); }
2596 template <typename E, class T, class A, class S>
2598 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2599 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2600 return !(rhs < lhs); }
2602 template <typename E, class T, class A, class S>
2604 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2605 const basic_fbstring<E, T, A, S>& rhs) {
2606 return !(rhs < lhs); }
2608 template <typename E, class T, class A, class S>
2610 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2611 const basic_fbstring<E, T, A, S>& rhs) {
2612 return !(lhs < rhs); }
2614 template <typename E, class T, class A, class S>
2616 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2617 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2618 return !(lhs < rhs); }
2620 template <typename E, class T, class A, class S>
2622 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2623 const basic_fbstring<E, T, A, S>& rhs) {
2624 return !(lhs < rhs);
2628 template <typename E, class T, class A, class S>
2629 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2633 // TODO: make this faster.
2634 template <typename E, class T, class A, class S>
2637 typename basic_fbstring<E, T, A, S>::value_type,
2638 typename basic_fbstring<E, T, A, S>::traits_type>&
2640 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2641 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2642 basic_fbstring<E, T, A, S>& str) {
2643 typename std::basic_istream<E, T>::sentry sentry(is);
2644 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2645 typename basic_fbstring<E, T, A, S>::traits_type>
2647 typedef typename __istream_type::ios_base __ios_base;
2648 size_t extracted = 0;
2649 auto err = __ios_base::goodbit;
2651 auto n = is.width();
2656 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2657 if (got == T::eof()) {
2658 err |= __ios_base::eofbit;
2666 got = is.rdbuf()->snextc();
2670 err |= __ios_base::failbit;
2678 template <typename E, class T, class A, class S>
2680 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2681 typename basic_fbstring<E, T, A, S>::traits_type>&
2683 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2684 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2685 const basic_fbstring<E, T, A, S>& str) {
2687 typename std::basic_ostream<
2688 typename basic_fbstring<E, T, A, S>::value_type,
2689 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2691 typedef std::ostreambuf_iterator<
2692 typename basic_fbstring<E, T, A, S>::value_type,
2693 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2694 size_t __len = str.size();
2696 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2697 if (__pad_and_output(_Ip(os),
2699 __left ? str.data() + __len : str.data(),
2702 os.fill()).failed()) {
2703 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2706 #elif defined(_MSC_VER)
2707 // MSVC doesn't define __ostream_insert
2708 os.write(str.data(), std::streamsize(str.size()));
2710 std::__ostream_insert(os, str.data(), str.size());
2715 template <typename E1, class T, class A, class S>
2716 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2717 basic_fbstring<E1, T, A, S>::npos;
2719 #ifndef _LIBSTDCXX_FBSTRING
2720 // basic_string compatibility routines
2722 template <typename E, class T, class A, class S>
2724 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2725 const std::string& rhs) {
2726 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2729 template <typename E, class T, class A, class S>
2731 bool operator==(const std::string& lhs,
2732 const basic_fbstring<E, T, A, S>& rhs) {
2736 template <typename E, class T, class A, class S>
2738 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2739 const std::string& rhs) {
2740 return !(lhs == rhs);
2743 template <typename E, class T, class A, class S>
2745 bool operator!=(const std::string& lhs,
2746 const basic_fbstring<E, T, A, S>& rhs) {
2747 return !(lhs == rhs);
2750 #if !defined(_LIBSTDCXX_FBSTRING)
2751 typedef basic_fbstring<char> fbstring;
2754 // fbstring is relocatable
2755 template <class T, class R, class A, class S>
2756 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2759 _GLIBCXX_END_NAMESPACE_VERSION
2762 } // namespace folly
2764 #ifndef _LIBSTDCXX_FBSTRING
2766 // Hash functions to make fbstring usable with e.g. hash_map
2768 // Handle interaction with different C++ standard libraries, which
2769 // expect these types to be in different namespaces.
2771 #define FOLLY_FBSTRING_HASH1(T) \
2773 struct hash< ::folly::basic_fbstring<T>> { \
2774 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2775 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2779 // The C++11 standard says that these four are defined
2780 #define FOLLY_FBSTRING_HASH \
2781 FOLLY_FBSTRING_HASH1(char) \
2782 FOLLY_FBSTRING_HASH1(char16_t) \
2783 FOLLY_FBSTRING_HASH1(char32_t) \
2784 FOLLY_FBSTRING_HASH1(wchar_t)
2792 #if FOLLY_HAVE_DEPRECATED_ASSOC
2793 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2794 namespace __gnu_cxx {
2798 } // namespace __gnu_cxx
2799 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2800 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2802 #undef FOLLY_FBSTRING_HASH
2803 #undef FOLLY_FBSTRING_HASH1
2805 #endif // _LIBSTDCXX_FBSTRING
2807 #pragma GCC diagnostic pop
2809 #undef FBSTRING_DISABLE_SSO
2810 #undef FBSTRING_SANITIZE_ADDRESS
2812 #undef FBSTRING_LIKELY
2813 #undef FBSTRING_UNLIKELY
2814 #undef FBSTRING_ASSERT