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) {
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 (> 23 chars) are stored in
293 * malloc-allocated memory that is copied eagerly.
294 * There exists a third storage category: (c) "large", which has the
295 * copy-on-write optimization. COW was disallowed in C++11, so large is
296 * now deprecated in fbstring_core. fbstring_core no longer creates large
297 * strings, though still works with them. Later, large strings will be
298 * completely removed.
300 * The discriminator between these three strategies sits in two
301 * bits of the rightmost char of the storage. If neither is set, then the
302 * string is small (and its length sits in the lower-order bits on
303 * little-endian or the high-order bits on big-endian of that
304 * rightmost character). If the MSb is set, the string is medium width.
305 * If the second MSb is set, then the string is large. On little-endian,
306 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
307 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
308 * and big-endian fbstring_core equivalent with merely different ops used
309 * to extract capacity/category.
311 template <class Char> class fbstring_core {
313 // It's MSVC, so we just have to guess ... and allow an override
315 # ifdef FOLLY_ENDIAN_BE
316 static constexpr auto kIsLittleEndian = false;
318 static constexpr auto kIsLittleEndian = true;
321 static constexpr auto kIsLittleEndian =
322 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
325 fbstring_core() noexcept { reset(); }
327 fbstring_core(const fbstring_core & rhs) {
328 FBSTRING_ASSERT(&rhs != this);
329 if (rhs.category() == Category::isSmall) {
334 FBSTRING_ASSERT(size() == rhs.size());
335 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
338 fbstring_core(fbstring_core&& goner) noexcept {
341 // Clean goner's carcass
345 fbstring_core(const Char *const data,
347 bool disableSSO = FBSTRING_DISABLE_SSO) {
348 if (!disableSSO && size <= maxSmallSize) {
349 initSmall(data, size);
351 initMedium(data, size);
353 FBSTRING_ASSERT(this->size() == size);
355 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
358 ~fbstring_core() noexcept {
359 if (category() == Category::isSmall) {
362 destroyMediumLarge();
365 // Snatches a previously mallocated string. The parameter "size"
366 // is the size of the string, and the parameter "allocatedSize"
367 // is the size of the mallocated block. The string must be
368 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
370 // So if you want a 2-character string, pass malloc(3) as "data",
371 // pass 2 as "size", and pass 3 as "allocatedSize".
372 fbstring_core(Char * const data,
374 const size_t allocatedSize,
375 AcquireMallocatedString) {
377 FBSTRING_ASSERT(allocatedSize >= size + 1);
378 FBSTRING_ASSERT(data[size] == '\0');
379 // Use the medium string storage
382 // Don't forget about null terminator
383 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
385 // No need for the memory
391 // swap below doesn't test whether &rhs == this (and instead
392 // potentially does extra work) on the premise that the rarity of
393 // that situation actually makes the check more expensive than is
395 void swap(fbstring_core & rhs) {
401 // In C++11 data() and c_str() are 100% equivalent.
402 const Char * data() const {
406 Char* mutableData() {
407 switch (category()) {
408 case Category::isSmall:
410 case Category::isMedium:
412 case Category::isLarge:
413 return mutableDataLarge();
415 fbstring_detail::assume_unreachable();
418 const Char* c_str() const {
419 const Char* ptr = ml_.data_;
420 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
421 ptr = (category() == Category::isSmall) ? small_ : ptr;
425 void shrink(const size_t delta) {
426 if (category() == Category::isSmall) {
428 } else if (category() == Category::isMedium ||
429 RefCounted::refs(ml_.data_) == 1) {
436 FOLLY_MALLOC_NOINLINE
437 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
438 switch (category()) {
439 case Category::isSmall:
440 reserveSmall(minCapacity, disableSSO);
442 case Category::isMedium:
443 reserveMedium(minCapacity);
445 case Category::isLarge:
446 reserveLarge(minCapacity);
449 fbstring_detail::assume_unreachable();
451 FBSTRING_ASSERT(capacity() >= minCapacity);
456 bool expGrowth = false,
457 bool disableSSO = FBSTRING_DISABLE_SSO);
459 void push_back(Char c) {
460 *expandNoinit(1, /* expGrowth = */ true) = c;
463 size_t size() const {
464 size_t ret = ml_.size_;
465 /* static */ if (kIsLittleEndian) {
466 // We can save a couple instructions, because the category is
467 // small iff the last char, as unsigned, is <= maxSmallSize.
468 typedef typename std::make_unsigned<Char>::type UChar;
469 auto maybeSmallSize = size_t(maxSmallSize) -
470 size_t(static_cast<UChar>(small_[maxSmallSize]));
471 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
472 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
474 ret = (category() == Category::isSmall) ? smallSize() : ret;
479 size_t capacity() const {
480 switch (category()) {
481 case Category::isSmall:
483 case Category::isLarge:
484 // For large-sized strings, a multi-referenced chunk has no
485 // available capacity. This is because any attempt to append
486 // data would trigger a new allocation.
487 if (RefCounted::refs(ml_.data_) > 1) {
492 return ml_.capacity();
495 bool isShared() const {
496 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
501 fbstring_core & operator=(const fbstring_core & rhs);
507 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
508 auto const c = category();
509 FBSTRING_ASSERT(c != Category::isSmall);
510 if (c == Category::isMedium) {
513 RefCounted::decrementRefs(ml_.data_);
518 std::atomic<size_t> refCount_;
521 static RefCounted * fromData(Char * p) {
522 return static_cast<RefCounted*>(
524 static_cast<unsigned char*>(static_cast<void*>(p))
525 - sizeof(refCount_)));
528 static size_t refs(Char * p) {
529 return fromData(p)->refCount_.load(std::memory_order_acquire);
532 static void incrementRefs(Char * p) {
533 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
536 static void decrementRefs(Char * p) {
537 auto const dis = fromData(p);
538 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
539 FBSTRING_ASSERT(oldcnt > 0);
545 static RefCounted * create(size_t * size) {
546 // Don't forget to allocate one extra Char for the terminating
547 // null. In this case, however, one Char is already part of the
549 const size_t allocSize = goodMallocSize(
550 sizeof(RefCounted) + *size * sizeof(Char));
551 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
552 result->refCount_.store(1, std::memory_order_release);
553 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
557 static RefCounted * create(const Char * data, size_t * size) {
558 const size_t effectiveSize = *size;
559 auto result = create(size);
560 if (FBSTRING_LIKELY(effectiveSize > 0)) {
561 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
566 static RefCounted * reallocate(Char *const data,
567 const size_t currentSize,
568 const size_t currentCapacity,
569 const size_t newCapacity) {
570 FBSTRING_ASSERT(newCapacity > 0 && newCapacity > currentSize);
571 auto const dis = fromData(data);
572 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
573 // Don't forget to allocate one extra Char for the terminating
574 // null. In this case, however, one Char is already part of the
576 auto result = static_cast<RefCounted*>(
578 sizeof(RefCounted) + currentSize * sizeof(Char),
579 sizeof(RefCounted) + currentCapacity * sizeof(Char),
580 sizeof(RefCounted) + newCapacity * sizeof(Char)));
581 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
586 typedef uint8_t category_type;
588 enum class Category : category_type {
590 isMedium = kIsLittleEndian ? 0x80 : 0x2,
591 isLarge = kIsLittleEndian ? 0x40 : 0x1,
594 Category category() const {
595 // works for both big-endian and little-endian
596 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
604 size_t capacity() const {
605 return kIsLittleEndian
606 ? capacity_ & capacityExtractMask
610 void setCapacity(size_t cap, Category cat) {
611 FBSTRING_ASSERT(cat != Category::isLarge);
612 capacity_ = kIsLittleEndian
613 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
614 : (cap << 2) | static_cast<size_t>(cat);
619 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
620 Char small_[sizeof(MediumLarge) / sizeof(Char)];
624 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
625 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
626 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
627 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
628 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
629 constexpr static size_t capacityExtractMask = kIsLittleEndian
630 ? ~(size_t(categoryExtractMask) << kCategoryShift)
633 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
634 "Corrupt memory layout for fbstring.");
636 size_t smallSize() const {
637 FBSTRING_ASSERT(category() == Category::isSmall);
638 constexpr auto shift = kIsLittleEndian ? 0 : 2;
639 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
640 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
641 return static_cast<size_t>(maxSmallSize) - smallShifted;
644 void setSmallSize(size_t s) {
645 // Warning: this should work with uninitialized strings too,
646 // so don't assume anything about the previous value of
647 // small_[maxSmallSize].
648 FBSTRING_ASSERT(s <= maxSmallSize);
649 constexpr auto shift = kIsLittleEndian ? 0 : 2;
650 small_[maxSmallSize] = (maxSmallSize - s) << shift;
652 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
655 void makeSmall(const fbstring_core&);
656 void makeMedium(const fbstring_core&);
657 void makeLarge(const fbstring_core&);
659 void initSmall(const Char* data, size_t size);
660 void initMedium(const Char* data, size_t size);
661 void initLarge(const Char* data, size_t size);
663 void reserveSmall(size_t minCapacity, bool disableSSO);
664 void reserveMedium(size_t minCapacity);
665 void reserveLarge(size_t minCapacity);
667 void shrinkSmall(size_t delta);
668 void shrinkMedium(size_t delta);
669 void shrinkLarge(size_t delta);
671 void unshare(size_t minCapacity = 0);
672 Char* mutableDataLarge();
675 template <class Char>
676 inline void fbstring_core<Char>::makeSmall(const fbstring_core& rhs) {
677 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
679 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
680 "fbstring layout failure");
682 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
683 "fbstring layout failure");
684 // Just write the whole thing, don't look at details. In
685 // particular we need to copy capacity anyway because we want
686 // to set the size (don't forget that the last character,
687 // which stores a short string's length, is shared with the
688 // ml_.capacity field).
691 category() == Category::isSmall && this->size() == rhs.size());
694 template <class Char>
695 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::makeMedium(
696 const fbstring_core& rhs) {
697 // Medium strings are copied eagerly. Don't forget to allocate
698 // one extra Char for the null terminator.
699 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
700 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
701 // Also copies terminator.
702 fbstring_detail::podCopy(
703 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
704 ml_.size_ = rhs.ml_.size_;
705 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
706 FBSTRING_ASSERT(category() == Category::isMedium);
709 template <class Char>
710 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::makeLarge(
711 const fbstring_core& rhs) {
712 // Large strings are just refcounted
714 RefCounted::incrementRefs(ml_.data_);
715 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
718 // Small strings are bitblitted
719 template <class Char>
720 inline void fbstring_core<Char>::initSmall(
721 const Char* const data, const size_t size) {
722 // Layout is: Char* data_, size_t size_, size_t capacity_
724 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
725 "fbstring has unexpected size");
727 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
728 // sizeof(size_t) must be a power of 2
730 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
731 "fbstring size assumption violation");
733 // If data is aligned, use fast word-wise copying. Otherwise,
734 // use conservative memcpy.
735 // The word-wise path reads bytes which are outside the range of
736 // the string, and makes ASan unhappy, so we disable it when
737 // compiling with ASan.
738 #ifndef FBSTRING_SANITIZE_ADDRESS
739 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
740 const size_t byteSize = size * sizeof(Char);
741 constexpr size_t wordWidth = sizeof(size_t);
742 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
744 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
746 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
748 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
756 fbstring_detail::podCopy(data, data + size, small_);
762 template <class Char>
763 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
764 const Char* const data, const size_t size) {
765 // Medium strings are allocated normally. Don't forget to
766 // allocate one extra Char for the terminating null.
767 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
768 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
769 if (FBSTRING_LIKELY(size > 0)) {
770 fbstring_detail::podCopy(data, data + size, ml_.data_);
773 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
774 ml_.data_[size] = '\0';
777 template <class Char>
778 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
779 const Char* const data, const size_t size) {
780 // Large strings are allocated differently
781 size_t effectiveCapacity = size;
782 auto const newRC = RefCounted::create(data, &effectiveCapacity);
783 ml_.data_ = newRC->data_;
785 ml_.setCapacity(effectiveCapacity, Category::isLarge);
786 ml_.data_[size] = '\0';
789 template <class Char>
790 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
791 size_t minCapacity) {
792 FBSTRING_ASSERT(category() == Category::isLarge);
793 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
794 auto const newRC = RefCounted::create(&effectiveCapacity);
795 // If this fails, someone placed the wrong capacity in an
797 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
798 // Also copies terminator.
799 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
800 RefCounted::decrementRefs(ml_.data_);
801 ml_.data_ = newRC->data_;
802 ml_.setCapacity(effectiveCapacity, Category::isLarge);
803 // size_ remains unchanged.
806 template <class Char>
807 inline Char* fbstring_core<Char>::mutableDataLarge() {
808 FBSTRING_ASSERT(category() == Category::isLarge);
809 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
815 template <class Char>
816 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
817 size_t minCapacity) {
818 FBSTRING_ASSERT(category() == Category::isLarge);
819 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
820 // We must make it unique regardless; in-place reallocation is
821 // useless if the string is shared. In order to not surprise
822 // people, reserve the new block at current capacity or
823 // more. That way, a string's capacity never shrinks after a
825 unshare(minCapacity);
827 // String is not shared, so let's try to realloc (if needed)
828 if (minCapacity > ml_.capacity()) {
829 // Asking for more memory
830 auto const newRC = RefCounted::reallocate(
831 ml_.data_, ml_.size_, ml_.capacity(), minCapacity);
832 ml_.data_ = newRC->data_;
833 ml_.setCapacity(minCapacity, Category::isLarge);
835 FBSTRING_ASSERT(capacity() >= minCapacity);
839 template <class Char>
840 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
841 const size_t minCapacity) {
842 FBSTRING_ASSERT(category() == Category::isMedium);
843 // String is not shared
844 if (minCapacity <= ml_.capacity()) {
845 return; // nothing to do, there's enough room
847 // Keep the string at medium size. Don't forget to allocate
848 // one extra Char for the terminating null.
849 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
850 // Also copies terminator.
851 ml_.data_ = static_cast<Char*>(smartRealloc(
853 (ml_.size_ + 1) * sizeof(Char),
854 (ml_.capacity() + 1) * sizeof(Char),
856 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
859 template <class Char>
860 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
861 size_t minCapacity, const bool disableSSO) {
862 FBSTRING_ASSERT(category() == Category::isSmall);
863 if (!disableSSO && minCapacity <= maxSmallSize) {
865 // Nothing to do, everything stays put
868 // Don't forget to allocate one extra Char for the terminating null
869 auto const allocSizeBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
870 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
871 auto const size = smallSize();
872 // Also copies terminator.
873 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
876 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
879 template <class Char>
880 inline Char* fbstring_core<Char>::expandNoinit(
882 bool expGrowth, /* = false */
883 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
884 // Strategy is simple: make room, then change size
885 FBSTRING_ASSERT(capacity() >= size());
887 if (category() == Category::isSmall) {
890 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
895 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
899 if (FBSTRING_UNLIKELY(newSz > capacity())) {
900 // ensures not shared
901 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
904 FBSTRING_ASSERT(capacity() >= newSz);
905 // Category can't be small - we took care of that above
907 category() == Category::isMedium || category() == Category::isLarge);
909 ml_.data_[newSz] = '\0';
910 FBSTRING_ASSERT(size() == newSz);
911 return ml_.data_ + sz;
914 template <class Char>
915 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
916 // Check for underflow
917 FBSTRING_ASSERT(delta <= smallSize());
918 setSmallSize(smallSize() - delta);
921 template <class Char>
922 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
923 // Medium strings and unique large strings need no special
925 FBSTRING_ASSERT(ml_.size_ >= delta);
927 ml_.data_[ml_.size_] = '\0';
930 template <class Char>
931 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
932 FBSTRING_ASSERT(ml_.size_ >= delta);
933 // Shared large string, must make unique. This is because of the
934 // durn terminator must be written, which may trample the shared
937 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
939 // No need to write the terminator.
942 #ifndef _LIBSTDCXX_FBSTRING
944 * Dummy fbstring core that uses an actual std::string. This doesn't
945 * make any sense - it's just for testing purposes.
947 template <class Char>
948 class dummy_fbstring_core {
950 dummy_fbstring_core() {
952 dummy_fbstring_core(const dummy_fbstring_core& another)
953 : backend_(another.backend_) {
955 dummy_fbstring_core(const Char * s, size_t n)
958 void swap(dummy_fbstring_core & rhs) {
959 backend_.swap(rhs.backend_);
961 const Char * data() const {
962 return backend_.data();
964 Char* mutableData() {
965 return const_cast<Char*>(backend_.data());
967 void shrink(size_t delta) {
968 FBSTRING_ASSERT(delta <= size());
969 backend_.resize(size() - delta);
971 Char* expandNoinit(size_t delta) {
972 auto const sz = size();
973 backend_.resize(size() + delta);
974 return backend_.data() + sz;
976 void push_back(Char c) {
977 backend_.push_back(c);
979 size_t size() const {
980 return backend_.size();
982 size_t capacity() const {
983 return backend_.capacity();
985 bool isShared() const {
988 void reserve(size_t minCapacity) {
989 backend_.reserve(minCapacity);
993 std::basic_string<Char> backend_;
995 #endif // !_LIBSTDCXX_FBSTRING
998 * This is the basic_string replacement. For conformity,
999 * basic_fbstring takes the same template parameters, plus the last
1000 * one which is the core.
1002 #ifdef _LIBSTDCXX_FBSTRING
1003 template <typename E, class T, class A, class Storage>
1005 template <typename E,
1006 class T = std::char_traits<E>,
1007 class A = std::allocator<E>,
1008 class Storage = fbstring_core<E> >
1010 class basic_fbstring {
1011 static void enforce(
1013 void (*throw_exc)(const char*),
1020 bool isSane() const {
1023 empty() == (size() == 0) &&
1024 empty() == (begin() == end()) &&
1025 size() <= max_size() &&
1026 capacity() <= max_size() &&
1027 size() <= capacity() &&
1028 begin()[size()] == '\0';
1032 Invariant& operator=(const Invariant&) = delete;
1033 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1034 FBSTRING_ASSERT(s_.isSane());
1036 ~Invariant() noexcept {
1037 FBSTRING_ASSERT(s_.isSane());
1041 const basic_fbstring& s_;
1046 typedef T traits_type;
1047 typedef typename traits_type::char_type value_type;
1048 typedef A allocator_type;
1049 typedef typename A::size_type size_type;
1050 typedef typename A::difference_type difference_type;
1052 typedef typename A::reference reference;
1053 typedef typename A::const_reference const_reference;
1054 typedef typename A::pointer pointer;
1055 typedef typename A::const_pointer const_pointer;
1057 typedef E* iterator;
1058 typedef const E* const_iterator;
1059 typedef std::reverse_iterator<iterator
1060 #ifdef NO_ITERATOR_TRAITS
1064 typedef std::reverse_iterator<const_iterator
1065 #ifdef NO_ITERATOR_TRAITS
1068 > const_reverse_iterator;
1070 static constexpr size_type npos = size_type(-1);
1071 typedef std::true_type IsRelocatable;
1074 static void procrustes(size_type& n, size_type nmax) {
1080 static size_type traitsLength(const value_type* s);
1083 // C++11 21.4.2 construct/copy/destroy
1085 // Note: while the following two constructors can be (and previously were)
1086 // collapsed into one constructor written this way:
1088 // explicit basic_fbstring(const A& a = A()) noexcept { }
1090 // This can cause Clang (at least version 3.7) to fail with the error:
1091 // "chosen constructor is explicit in copy-initialization ...
1092 // in implicit initialization of field '(x)' with omitted initializer"
1094 // if used in a struct which is default-initialized. Hence the split into
1095 // these two separate constructors.
1097 basic_fbstring() noexcept : basic_fbstring(A()) {
1100 explicit basic_fbstring(const A&) noexcept {
1103 basic_fbstring(const basic_fbstring& str)
1104 : store_(str.store_) {
1108 basic_fbstring(basic_fbstring&& goner) noexcept
1109 : store_(std::move(goner.store_)) {
1112 #ifndef _LIBSTDCXX_FBSTRING
1113 // This is defined for compatibility with std::string
1114 /* implicit */ basic_fbstring(const std::string& str)
1115 : store_(str.data(), str.size()) {
1119 basic_fbstring(const basic_fbstring& str,
1122 const A& /* a */ = A()) {
1123 assign(str, pos, n);
1126 FOLLY_MALLOC_NOINLINE
1127 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1128 : store_(s, traitsLength(s)) {}
1130 FOLLY_MALLOC_NOINLINE
1131 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1135 FOLLY_MALLOC_NOINLINE
1136 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1137 auto const pData = store_.expandNoinit(n);
1138 fbstring_detail::podFill(pData, pData + n, c);
1141 template <class InIt>
1142 FOLLY_MALLOC_NOINLINE basic_fbstring(
1145 typename std::enable_if<
1146 !std::is_same<InIt, value_type*>::value,
1147 const A>::type& /*a*/ = A()) {
1151 // Specialization for const char*, const char*
1152 FOLLY_MALLOC_NOINLINE
1153 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1154 : store_(b, e - b) {
1157 // Nonstandard constructor
1158 basic_fbstring(value_type *s, size_type n, size_type c,
1159 AcquireMallocatedString a)
1160 : store_(s, n, c, a) {
1163 // Construction from initialization list
1164 FOLLY_MALLOC_NOINLINE
1165 basic_fbstring(std::initializer_list<value_type> il) {
1166 assign(il.begin(), il.end());
1169 ~basic_fbstring() noexcept {}
1171 basic_fbstring& operator=(const basic_fbstring& lhs);
1174 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1176 #ifndef _LIBSTDCXX_FBSTRING
1177 // Compatibility with std::string
1178 basic_fbstring & operator=(const std::string & rhs) {
1179 return assign(rhs.data(), rhs.size());
1182 // Compatibility with std::string
1183 std::string toStdString() const {
1184 return std::string(data(), size());
1187 // A lot of code in fbcode still uses this method, so keep it here for now.
1188 const basic_fbstring& toStdString() const {
1193 basic_fbstring& operator=(const value_type* s) {
1197 basic_fbstring& operator=(value_type c);
1199 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1200 return assign(il.begin(), il.end());
1203 // C++11 21.4.3 iterators:
1205 return store_.mutableData();
1208 const_iterator begin() const {
1209 return store_.data();
1212 const_iterator cbegin() const {
1217 return store_.mutableData() + store_.size();
1220 const_iterator end() const {
1221 return store_.data() + store_.size();
1224 const_iterator cend() const { return end(); }
1226 reverse_iterator rbegin() {
1227 return reverse_iterator(end());
1230 const_reverse_iterator rbegin() const {
1231 return const_reverse_iterator(end());
1234 const_reverse_iterator crbegin() const { return rbegin(); }
1236 reverse_iterator rend() {
1237 return reverse_iterator(begin());
1240 const_reverse_iterator rend() const {
1241 return const_reverse_iterator(begin());
1244 const_reverse_iterator crend() const { return rend(); }
1247 // C++11 21.4.5, element access:
1248 const value_type& front() const { return *begin(); }
1249 const value_type& back() const {
1250 FBSTRING_ASSERT(!empty());
1251 // Should be begin()[size() - 1], but that branches twice
1252 return *(end() - 1);
1254 value_type& front() { return *begin(); }
1255 value_type& back() {
1256 FBSTRING_ASSERT(!empty());
1257 // Should be begin()[size() - 1], but that branches twice
1258 return *(end() - 1);
1261 FBSTRING_ASSERT(!empty());
1265 // C++11 21.4.4 capacity:
1266 size_type size() const { return store_.size(); }
1268 size_type length() const { return size(); }
1270 size_type max_size() const {
1271 return std::numeric_limits<size_type>::max();
1274 void resize(size_type n, value_type c = value_type());
1276 size_type capacity() const { return store_.capacity(); }
1278 void reserve(size_type res_arg = 0) {
1279 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1280 store_.reserve(res_arg);
1283 void shrink_to_fit() {
1284 // Shrink only if slack memory is sufficiently large
1285 if (capacity() < size() * 3 / 2) {
1288 basic_fbstring(cbegin(), cend()).swap(*this);
1291 void clear() { resize(0); }
1293 bool empty() const { return size() == 0; }
1295 // C++11 21.4.5 element access:
1296 const_reference operator[](size_type pos) const {
1297 return *(begin() + pos);
1300 reference operator[](size_type pos) {
1301 return *(begin() + pos);
1304 const_reference at(size_type n) const {
1305 enforce(n <= size(), std::__throw_out_of_range, "");
1309 reference at(size_type n) {
1310 enforce(n < size(), std::__throw_out_of_range, "");
1314 // C++11 21.4.6 modifiers:
1315 basic_fbstring& operator+=(const basic_fbstring& str) {
1319 basic_fbstring& operator+=(const value_type* s) {
1323 basic_fbstring& operator+=(const value_type c) {
1328 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1333 basic_fbstring& append(const basic_fbstring& str);
1336 append(const basic_fbstring& str, const size_type pos, size_type n);
1338 basic_fbstring& append(const value_type* s, size_type n);
1340 basic_fbstring& append(const value_type* s) {
1341 return append(s, traitsLength(s));
1344 basic_fbstring& append(size_type n, value_type c);
1346 template<class InputIterator>
1347 basic_fbstring& append(InputIterator first, InputIterator last) {
1348 insert(end(), first, last);
1352 basic_fbstring& append(std::initializer_list<value_type> il) {
1353 return append(il.begin(), il.end());
1356 void push_back(const value_type c) { // primitive
1357 store_.push_back(c);
1360 basic_fbstring& assign(const basic_fbstring& str) {
1361 if (&str == this) return *this;
1362 return assign(str.data(), str.size());
1365 basic_fbstring& assign(basic_fbstring&& str) {
1366 return *this = std::move(str);
1370 assign(const basic_fbstring& str, const size_type pos, size_type n);
1372 basic_fbstring& assign(const value_type* s, const size_type n);
1374 basic_fbstring& assign(const value_type* s) {
1375 return assign(s, traitsLength(s));
1378 basic_fbstring& assign(std::initializer_list<value_type> il) {
1379 return assign(il.begin(), il.end());
1382 template <class ItOrLength, class ItOrChar>
1383 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1384 return replace(begin(), end(), first_or_n, last_or_c);
1387 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1388 return insert(pos1, str.data(), str.size());
1391 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1392 size_type pos2, size_type n) {
1393 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1394 procrustes(n, str.length() - pos2);
1395 return insert(pos1, str.data() + pos2, n);
1398 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1399 enforce(pos <= length(), std::__throw_out_of_range, "");
1400 insert(begin() + pos, s, s + n);
1404 basic_fbstring& insert(size_type pos, const value_type* s) {
1405 return insert(pos, s, traitsLength(s));
1408 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1409 enforce(pos <= length(), std::__throw_out_of_range, "");
1410 insert(begin() + pos, n, c);
1414 iterator insert(const_iterator p, const value_type c) {
1415 const size_type pos = p - cbegin();
1417 return begin() + pos;
1420 #ifndef _LIBSTDCXX_FBSTRING
1422 typedef std::basic_istream<value_type, traits_type> istream_type;
1423 istream_type& getlineImpl(istream_type& is, value_type delim);
1426 friend inline istream_type& getline(istream_type& is,
1427 basic_fbstring& str,
1429 return str.getlineImpl(is, delim);
1432 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1433 return getline(is, str, '\n');
1439 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1441 template <class InputIter>
1443 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1445 template <class FwdIterator>
1446 iterator insertImpl(
1450 std::forward_iterator_tag);
1452 template <class InputIterator>
1453 iterator insertImpl(
1457 std::input_iterator_tag);
1460 template <class ItOrLength, class ItOrChar>
1461 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1462 using Sel = std::integral_constant<
1464 std::numeric_limits<ItOrLength>::is_specialized>;
1465 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1468 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1469 return insert(p, il.begin(), il.end());
1472 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1473 Invariant checker(*this);
1475 enforce(pos <= length(), std::__throw_out_of_range, "");
1476 procrustes(n, length() - pos);
1477 std::copy(begin() + pos + n, end(), begin() + pos);
1478 resize(length() - n);
1482 iterator erase(iterator position) {
1483 const size_type pos(position - begin());
1484 enforce(pos <= size(), std::__throw_out_of_range, "");
1486 return begin() + pos;
1489 iterator erase(iterator first, iterator last) {
1490 const size_type pos(first - begin());
1491 erase(pos, last - first);
1492 return begin() + pos;
1495 // Replaces at most n1 chars of *this, starting with pos1 with the
1497 basic_fbstring& replace(size_type pos1, size_type n1,
1498 const basic_fbstring& str) {
1499 return replace(pos1, n1, str.data(), str.size());
1502 // Replaces at most n1 chars of *this, starting with pos1,
1503 // with at most n2 chars of str starting with pos2
1504 basic_fbstring& replace(size_type pos1, size_type n1,
1505 const basic_fbstring& str,
1506 size_type pos2, size_type n2) {
1507 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1508 return replace(pos1, n1, str.data() + pos2,
1509 std::min(n2, str.size() - pos2));
1512 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1513 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1514 return replace(pos, n1, s, traitsLength(s));
1517 // Replaces at most n1 chars of *this, starting with pos, with n2
1520 // consolidated with
1522 // Replaces at most n1 chars of *this, starting with pos, with at
1523 // most n2 chars of str. str must have at least n2 chars.
1524 template <class StrOrLength, class NumOrChar>
1525 basic_fbstring& replace(size_type pos, size_type n1,
1526 StrOrLength s_or_n2, NumOrChar n_or_c) {
1527 Invariant checker(*this);
1529 enforce(pos <= size(), std::__throw_out_of_range, "");
1530 procrustes(n1, length() - pos);
1531 const iterator b = begin() + pos;
1532 return replace(b, b + n1, s_or_n2, n_or_c);
1535 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1536 return replace(i1, i2, str.data(), str.length());
1539 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1540 return replace(i1, i2, s, traitsLength(s));
1544 basic_fbstring& replaceImplDiscr(
1547 const value_type* s,
1549 std::integral_constant<int, 2>);
1551 basic_fbstring& replaceImplDiscr(
1556 std::integral_constant<int, 1>);
1558 template <class InputIter>
1559 basic_fbstring& replaceImplDiscr(
1564 std::integral_constant<int, 0>);
1567 template <class FwdIterator>
1568 bool replaceAliased(iterator /* i1 */,
1570 FwdIterator /* s1 */,
1571 FwdIterator /* s2 */,
1576 template <class FwdIterator>
1577 bool replaceAliased(
1584 template <class FwdIterator>
1590 std::forward_iterator_tag);
1592 template <class InputIterator>
1598 std::input_iterator_tag);
1601 template <class T1, class T2>
1602 basic_fbstring& replace(iterator i1, iterator i2,
1603 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1604 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1605 num2 = std::numeric_limits<T2>::is_specialized;
1607 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1608 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1611 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1612 enforce(pos <= size(), std::__throw_out_of_range, "");
1613 procrustes(n, size() - pos);
1616 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1621 void swap(basic_fbstring& rhs) {
1622 store_.swap(rhs.store_);
1625 const value_type* c_str() const {
1626 return store_.c_str();
1629 const value_type* data() const { return c_str(); }
1631 allocator_type get_allocator() const {
1632 return allocator_type();
1635 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1636 return find(str.data(), pos, str.length());
1639 size_type find(const value_type* needle, size_type pos, size_type nsize)
1642 size_type find(const value_type* s, size_type pos = 0) const {
1643 return find(s, pos, traitsLength(s));
1646 size_type find (value_type c, size_type pos = 0) const {
1647 return find(&c, pos, 1);
1650 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1651 return rfind(str.data(), pos, str.length());
1654 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1656 size_type rfind(const value_type* s, size_type pos = npos) const {
1657 return rfind(s, pos, traitsLength(s));
1660 size_type rfind(value_type c, size_type pos = npos) const {
1661 return rfind(&c, pos, 1);
1664 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1665 return find_first_of(str.data(), pos, str.length());
1668 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1671 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1672 return find_first_of(s, pos, traitsLength(s));
1675 size_type find_first_of(value_type c, size_type pos = 0) const {
1676 return find_first_of(&c, pos, 1);
1679 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1681 return find_last_of(str.data(), pos, str.length());
1684 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1686 size_type find_last_of (const value_type* s,
1687 size_type pos = npos) const {
1688 return find_last_of(s, pos, traitsLength(s));
1691 size_type find_last_of (value_type c, size_type pos = npos) const {
1692 return find_last_of(&c, pos, 1);
1695 size_type find_first_not_of(const basic_fbstring& str,
1696 size_type pos = 0) const {
1697 return find_first_not_of(str.data(), pos, str.size());
1700 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1703 size_type find_first_not_of(const value_type* s,
1704 size_type pos = 0) const {
1705 return find_first_not_of(s, pos, traitsLength(s));
1708 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1709 return find_first_not_of(&c, pos, 1);
1712 size_type find_last_not_of(const basic_fbstring& str,
1713 size_type pos = npos) const {
1714 return find_last_not_of(str.data(), pos, str.length());
1717 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1720 size_type find_last_not_of(const value_type* s,
1721 size_type pos = npos) const {
1722 return find_last_not_of(s, pos, traitsLength(s));
1725 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1726 return find_last_not_of(&c, pos, 1);
1729 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1730 enforce(pos <= size(), std::__throw_out_of_range, "");
1731 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1734 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1735 enforce(pos <= size(), std::__throw_out_of_range, "");
1740 return std::move(*this);
1743 int compare(const basic_fbstring& str) const {
1744 // FIX due to Goncalo N M de Carvalho July 18, 2005
1745 return compare(0, size(), str);
1748 int compare(size_type pos1, size_type n1,
1749 const basic_fbstring& str) const {
1750 return compare(pos1, n1, str.data(), str.size());
1753 int compare(size_type pos1, size_type n1,
1754 const value_type* s) const {
1755 return compare(pos1, n1, s, traitsLength(s));
1758 int compare(size_type pos1, size_type n1,
1759 const value_type* s, size_type n2) const {
1760 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1761 procrustes(n1, size() - pos1);
1762 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1763 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1764 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1767 int compare(size_type pos1, size_type n1,
1768 const basic_fbstring& str,
1769 size_type pos2, size_type n2) const {
1770 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1771 return compare(pos1, n1, str.data() + pos2,
1772 std::min(n2, str.size() - pos2));
1775 // Code from Jean-Francois Bastien (03/26/2007)
1776 int compare(const value_type* s) const {
1777 // Could forward to compare(0, size(), s, traitsLength(s))
1778 // but that does two extra checks
1779 const size_type n1(size()), n2(traitsLength(s));
1780 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1781 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1789 template <typename E, class T, class A, class S>
1790 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1791 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1792 return s ? traits_type::length(s)
1793 : (std::__throw_logic_error(
1794 "basic_fbstring: null pointer initializer not valid"),
1798 template <typename E, class T, class A, class S>
1799 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1800 const basic_fbstring& lhs) {
1801 Invariant checker(*this);
1803 if (FBSTRING_UNLIKELY(&lhs == this)) {
1807 return assign(lhs.data(), lhs.size());
1811 template <typename E, class T, class A, class S>
1812 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1813 basic_fbstring&& goner) noexcept {
1814 if (FBSTRING_UNLIKELY(&goner == this)) {
1815 // Compatibility with std::basic_string<>,
1816 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1819 // No need of this anymore
1820 this->~basic_fbstring();
1821 // Move the goner into this
1822 new (&store_) S(std::move(goner.store_));
1826 template <typename E, class T, class A, class S>
1827 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1828 const value_type c) {
1829 Invariant checker(*this);
1832 store_.expandNoinit(1);
1833 } else if (store_.isShared()) {
1834 basic_fbstring(1, c).swap(*this);
1837 store_.shrink(size() - 1);
1843 template <typename E, class T, class A, class S>
1844 inline void basic_fbstring<E, T, A, S>::resize(
1845 const size_type n, const value_type c /*= value_type()*/) {
1846 Invariant checker(*this);
1848 auto size = this->size();
1850 store_.shrink(size - n);
1852 auto const delta = n - size;
1853 auto pData = store_.expandNoinit(delta);
1854 fbstring_detail::podFill(pData, pData + delta, c);
1856 FBSTRING_ASSERT(this->size() == n);
1859 template <typename E, class T, class A, class S>
1860 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1861 const basic_fbstring& str) {
1863 auto desiredSize = size() + str.size();
1865 append(str.data(), str.size());
1866 FBSTRING_ASSERT(size() == desiredSize);
1870 template <typename E, class T, class A, class S>
1871 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1872 const basic_fbstring& str, const size_type pos, size_type n) {
1873 const size_type sz = str.size();
1874 enforce(pos <= sz, std::__throw_out_of_range, "");
1875 procrustes(n, sz - pos);
1876 return append(str.data() + pos, n);
1879 template <typename E, class T, class A, class S>
1880 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1881 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1882 Invariant checker(*this);
1884 if (FBSTRING_UNLIKELY(!n)) {
1885 // Unlikely but must be done
1888 auto const oldSize = size();
1889 auto const oldData = data();
1890 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1892 // Check for aliasing (rare). We could use "<=" here but in theory
1893 // those do not work for pointers unless the pointers point to
1894 // elements in the same array. For that reason we use
1895 // std::less_equal, which is guaranteed to offer a total order
1896 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1898 std::less_equal<const value_type*> le;
1899 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1900 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1901 // expandNoinit() could have moved the storage, restore the source.
1902 s = data() + (s - oldData);
1903 fbstring_detail::podMove(s, s + n, pData);
1905 fbstring_detail::podCopy(s, s + n, pData);
1908 FBSTRING_ASSERT(size() == oldSize + n);
1912 template <typename E, class T, class A, class S>
1913 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1914 size_type n, value_type c) {
1915 Invariant checker(*this);
1916 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1917 fbstring_detail::podFill(pData, pData + n, c);
1921 template <typename E, class T, class A, class S>
1922 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1923 const basic_fbstring& str, const size_type pos, size_type n) {
1924 const size_type sz = str.size();
1925 enforce(pos <= sz, std::__throw_out_of_range, "");
1926 procrustes(n, sz - pos);
1927 return assign(str.data() + pos, n);
1930 template <typename E, class T, class A, class S>
1931 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1932 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1933 Invariant checker(*this);
1937 } else if (size() >= n) {
1938 // s can alias this, we need to use podMove.
1939 fbstring_detail::podMove(s, s + n, store_.mutableData());
1940 store_.shrink(size() - n);
1941 FBSTRING_ASSERT(size() == n);
1943 // If n is larger than size(), s cannot alias this string's
1946 // Do not use exponential growth here: assign() should be tight,
1947 // to mirror the behavior of the equivalent constructor.
1948 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
1951 FBSTRING_ASSERT(size() == n);
1955 #ifndef _LIBSTDCXX_FBSTRING
1956 template <typename E, class T, class A, class S>
1957 inline typename basic_fbstring<E, T, A, S>::istream_type&
1958 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
1959 Invariant checker(*this);
1964 size_t avail = capacity() - size;
1965 // fbstring has 1 byte extra capacity for the null terminator,
1966 // and getline null-terminates the read string.
1967 is.getline(store_.expandNoinit(avail), avail + 1, delim);
1968 size += is.gcount();
1970 if (is.bad() || is.eof() || !is.fail()) {
1971 // Done by either failure, end of file, or normal read.
1972 if (!is.bad() && !is.eof()) {
1973 --size; // gcount() also accounts for the delimiter.
1979 FBSTRING_ASSERT(size == this->size());
1980 FBSTRING_ASSERT(size == capacity());
1981 // Start at minimum allocation 63 + terminator = 64.
1982 reserve(std::max<size_t>(63, 3 * size / 2));
1983 // Clear the error so we can continue reading.
1990 template <typename E, class T, class A, class S>
1991 inline typename basic_fbstring<E, T, A, S>::size_type
1992 basic_fbstring<E, T, A, S>::find(
1993 const value_type* needle, const size_type pos, const size_type nsize)
1995 auto const size = this->size();
1996 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1997 // that nsize + pos does not wrap around.
1998 if (nsize + pos > size || nsize + pos < pos) {
2005 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2006 // the last characters first
2007 auto const haystack = data();
2008 auto const nsize_1 = nsize - 1;
2009 auto const lastNeedle = needle[nsize_1];
2011 // Boyer-Moore skip value for the last char in the needle. Zero is
2012 // not a valid value; skip will be computed the first time it's
2016 const E* i = haystack + pos;
2017 auto iEnd = haystack + size - nsize_1;
2020 // Boyer-Moore: match the last element in the needle
2021 while (i[nsize_1] != lastNeedle) {
2027 // Here we know that the last char matches
2028 // Continue in pedestrian mode
2029 for (size_t j = 0;;) {
2030 FBSTRING_ASSERT(j < nsize);
2031 if (i[j] != needle[j]) {
2032 // Not found, we can skip
2033 // Compute the skip value lazily
2036 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2043 // Check if done searching
2046 return i - haystack;
2053 template <typename E, class T, class A, class S>
2054 inline typename basic_fbstring<E, T, A, S>::iterator
2055 basic_fbstring<E, T, A, S>::insertImplDiscr(
2056 const_iterator i, size_type n, value_type c, std::true_type) {
2057 Invariant checker(*this);
2059 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2060 const size_type pos = i - cbegin();
2062 auto oldSize = size();
2063 store_.expandNoinit(n, /* expGrowth = */ true);
2065 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2066 fbstring_detail::podFill(b + pos, b + pos + n, c);
2071 template <typename E, class T, class A, class S>
2072 template <class InputIter>
2073 inline typename basic_fbstring<E, T, A, S>::iterator
2074 basic_fbstring<E, T, A, S>::insertImplDiscr(
2075 const_iterator i, InputIter b, InputIter e, std::false_type) {
2077 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2080 template <typename E, class T, class A, class S>
2081 template <class FwdIterator>
2082 inline typename basic_fbstring<E, T, A, S>::iterator
2083 basic_fbstring<E, T, A, S>::insertImpl(
2087 std::forward_iterator_tag) {
2088 Invariant checker(*this);
2090 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2091 const size_type pos = i - cbegin();
2092 auto n = std::distance(s1, s2);
2093 FBSTRING_ASSERT(n >= 0);
2095 auto oldSize = size();
2096 store_.expandNoinit(n, /* expGrowth = */ true);
2098 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2099 std::copy(s1, s2, b + pos);
2104 template <typename E, class T, class A, class S>
2105 template <class InputIterator>
2106 inline typename basic_fbstring<E, T, A, S>::iterator
2107 basic_fbstring<E, T, A, S>::insertImpl(
2111 std::input_iterator_tag) {
2112 const auto pos = i - cbegin();
2113 basic_fbstring temp(cbegin(), i);
2114 for (; b != e; ++b) {
2117 temp.append(i, cend());
2119 return begin() + pos;
2122 template <typename E, class T, class A, class S>
2123 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2126 const value_type* s,
2128 std::integral_constant<int, 2>) {
2129 FBSTRING_ASSERT(i1 <= i2);
2130 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2131 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2132 return replace(i1, i2, s, s + n);
2135 template <typename E, class T, class A, class S>
2136 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2141 std::integral_constant<int, 1>) {
2142 const size_type n1 = i2 - i1;
2144 std::fill(i1, i1 + n2, c);
2147 std::fill(i1, i2, c);
2148 insert(i2, n2 - n1, c);
2150 FBSTRING_ASSERT(isSane());
2154 template <typename E, class T, class A, class S>
2155 template <class InputIter>
2156 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2161 std::integral_constant<int, 0>) {
2162 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2163 replaceImpl(i1, i2, b, e, Cat());
2167 template <typename E, class T, class A, class S>
2168 template <class FwdIterator>
2169 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2170 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2171 std::less_equal<const value_type*> le{};
2172 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2176 // Aliased replace, copy to new string
2177 basic_fbstring temp;
2178 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2179 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2184 template <typename E, class T, class A, class S>
2185 template <class FwdIterator>
2186 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2191 std::forward_iterator_tag) {
2192 Invariant checker(*this);
2194 // Handle aliased replace
2195 using Sel = std::integral_constant<
2197 std::is_same<FwdIterator, iterator>::value ||
2198 std::is_same<FwdIterator, const_iterator>::value>;
2199 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2203 auto const n1 = i2 - i1;
2204 FBSTRING_ASSERT(n1 >= 0);
2205 auto const n2 = std::distance(s1, s2);
2206 FBSTRING_ASSERT(n2 >= 0);
2210 std::copy(s1, s2, i1);
2214 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2217 FBSTRING_ASSERT(isSane());
2220 template <typename E, class T, class A, class S>
2221 template <class InputIterator>
2222 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2227 std::input_iterator_tag) {
2228 basic_fbstring temp(begin(), i1);
2229 temp.append(b, e).append(i2, end());
2233 template <typename E, class T, class A, class S>
2234 inline typename basic_fbstring<E, T, A, S>::size_type
2235 basic_fbstring<E, T, A, S>::rfind(
2236 const value_type* s, size_type pos, size_type n) const {
2240 pos = std::min(pos, length() - n);
2245 const_iterator i(begin() + pos);
2247 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2257 template <typename E, class T, class A, class S>
2258 inline typename basic_fbstring<E, T, A, S>::size_type
2259 basic_fbstring<E, T, A, S>::find_first_of(
2260 const value_type* s, size_type pos, size_type n) const {
2261 if (pos > length() || n == 0) {
2264 const_iterator i(begin() + pos), finish(end());
2265 for (; i != finish; ++i) {
2266 if (traits_type::find(s, n, *i) != 0) {
2273 template <typename E, class T, class A, class S>
2274 inline typename basic_fbstring<E, T, A, S>::size_type
2275 basic_fbstring<E, T, A, S>::find_last_of(
2276 const value_type* s, size_type pos, size_type n) const {
2277 if (!empty() && n > 0) {
2278 pos = std::min(pos, length() - 1);
2279 const_iterator i(begin() + pos);
2281 if (traits_type::find(s, n, *i) != 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_not_of(
2295 const value_type* s, size_type pos, size_type n) const {
2296 if (pos < length()) {
2297 const_iterator i(begin() + pos), finish(end());
2298 for (; i != finish; ++i) {
2299 if (traits_type::find(s, n, *i) == 0) {
2307 template <typename E, class T, class A, class S>
2308 inline typename basic_fbstring<E, T, A, S>::size_type
2309 basic_fbstring<E, T, A, S>::find_last_not_of(
2310 const value_type* s, size_type pos, size_type n) const {
2311 if (!this->empty()) {
2312 pos = std::min(pos, size() - 1);
2313 const_iterator i(begin() + pos);
2315 if (traits_type::find(s, n, *i) == 0) {
2326 // non-member functions
2328 template <typename E, class T, class A, class S>
2330 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2331 const basic_fbstring<E, T, A, S>& rhs) {
2333 basic_fbstring<E, T, A, S> result;
2334 result.reserve(lhs.size() + rhs.size());
2335 result.append(lhs).append(rhs);
2336 return std::move(result);
2340 template <typename E, class T, class A, class S>
2342 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2343 const basic_fbstring<E, T, A, S>& rhs) {
2344 return std::move(lhs.append(rhs));
2348 template <typename E, class T, class A, class S>
2350 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2351 basic_fbstring<E, T, A, S>&& rhs) {
2352 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2353 // Good, at least we don't need to reallocate
2354 return std::move(rhs.insert(0, lhs));
2356 // Meh, no go. Forward to operator+(const&, const&).
2357 auto const& rhsC = rhs;
2362 template <typename E, class T, class A, class S>
2364 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2365 basic_fbstring<E, T, A, S>&& rhs) {
2366 return std::move(lhs.append(rhs));
2370 template <typename E, class T, class A, class S>
2372 basic_fbstring<E, T, A, S> operator+(
2374 const basic_fbstring<E, T, A, S>& rhs) {
2376 basic_fbstring<E, T, A, S> result;
2377 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2378 result.reserve(len + rhs.size());
2379 result.append(lhs, len).append(rhs);
2384 template <typename E, class T, class A, class S>
2386 basic_fbstring<E, T, A, S> operator+(
2388 basic_fbstring<E, T, A, S>&& rhs) {
2390 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2391 if (rhs.capacity() >= len + rhs.size()) {
2392 // Good, at least we don't need to reallocate
2393 rhs.insert(rhs.begin(), lhs, lhs + len);
2396 // Meh, no go. Do it by hand since we have len already.
2397 basic_fbstring<E, T, A, S> result;
2398 result.reserve(len + rhs.size());
2399 result.append(lhs, len).append(rhs);
2404 template <typename E, class T, class A, class S>
2406 basic_fbstring<E, T, A, S> operator+(
2408 const basic_fbstring<E, T, A, S>& rhs) {
2410 basic_fbstring<E, T, A, S> result;
2411 result.reserve(1 + rhs.size());
2412 result.push_back(lhs);
2418 template <typename E, class T, class A, class S>
2420 basic_fbstring<E, T, A, S> operator+(
2422 basic_fbstring<E, T, A, S>&& rhs) {
2424 if (rhs.capacity() > rhs.size()) {
2425 // Good, at least we don't need to reallocate
2426 rhs.insert(rhs.begin(), lhs);
2429 // Meh, no go. Forward to operator+(E, const&).
2430 auto const& rhsC = rhs;
2435 template <typename E, class T, class A, class S>
2437 basic_fbstring<E, T, A, S> operator+(
2438 const basic_fbstring<E, T, A, S>& lhs,
2441 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2442 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2444 basic_fbstring<E, T, A, S> result;
2445 const size_type len = traits_type::length(rhs);
2446 result.reserve(lhs.size() + len);
2447 result.append(lhs).append(rhs, len);
2451 // C++11 21.4.8.1/10
2452 template <typename E, class T, class A, class S>
2454 basic_fbstring<E, T, A, S> operator+(
2455 basic_fbstring<E, T, A, S>&& lhs,
2458 return std::move(lhs += rhs);
2461 // C++11 21.4.8.1/11
2462 template <typename E, class T, class A, class S>
2464 basic_fbstring<E, T, A, S> operator+(
2465 const basic_fbstring<E, T, A, S>& lhs,
2468 basic_fbstring<E, T, A, S> result;
2469 result.reserve(lhs.size() + 1);
2471 result.push_back(rhs);
2475 // C++11 21.4.8.1/12
2476 template <typename E, class T, class A, class S>
2478 basic_fbstring<E, T, A, S> operator+(
2479 basic_fbstring<E, T, A, S>&& lhs,
2482 return std::move(lhs += rhs);
2485 template <typename E, class T, class A, class S>
2487 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2488 const basic_fbstring<E, T, A, S>& rhs) {
2489 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2491 template <typename E, class T, class A, class S>
2493 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2494 const basic_fbstring<E, T, A, S>& rhs) {
2495 return rhs == lhs; }
2497 template <typename E, class T, class A, class S>
2499 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2500 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2501 return lhs.compare(rhs) == 0; }
2503 template <typename E, class T, class A, class S>
2505 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2506 const basic_fbstring<E, T, A, S>& rhs) {
2507 return !(lhs == rhs); }
2509 template <typename E, class T, class A, class S>
2511 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2512 const basic_fbstring<E, T, A, S>& rhs) {
2513 return !(lhs == rhs); }
2515 template <typename E, class T, class A, class S>
2517 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2518 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2519 return !(lhs == rhs); }
2521 template <typename E, class T, class A, class S>
2523 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2524 const basic_fbstring<E, T, A, S>& rhs) {
2525 return lhs.compare(rhs) < 0; }
2527 template <typename E, class T, class A, class S>
2529 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2530 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2531 return lhs.compare(rhs) < 0; }
2533 template <typename E, class T, class A, class S>
2535 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2536 const basic_fbstring<E, T, A, S>& rhs) {
2537 return rhs.compare(lhs) > 0; }
2539 template <typename E, class T, class A, class S>
2541 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2542 const basic_fbstring<E, T, A, S>& rhs) {
2545 template <typename E, class T, class A, class S>
2547 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2548 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2551 template <typename E, class T, class A, class S>
2553 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2554 const basic_fbstring<E, T, A, S>& rhs) {
2557 template <typename E, class T, class A, class S>
2559 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2560 const basic_fbstring<E, T, A, S>& rhs) {
2561 return !(rhs < lhs); }
2563 template <typename E, class T, class A, class S>
2565 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2566 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2567 return !(rhs < lhs); }
2569 template <typename E, class T, class A, class S>
2571 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2572 const basic_fbstring<E, T, A, S>& rhs) {
2573 return !(rhs < lhs); }
2575 template <typename E, class T, class A, class S>
2577 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2578 const basic_fbstring<E, T, A, S>& rhs) {
2579 return !(lhs < rhs); }
2581 template <typename E, class T, class A, class S>
2583 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2584 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2585 return !(lhs < rhs); }
2587 template <typename E, class T, class A, class S>
2589 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2590 const basic_fbstring<E, T, A, S>& rhs) {
2591 return !(lhs < rhs);
2595 template <typename E, class T, class A, class S>
2596 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2600 // TODO: make this faster.
2601 template <typename E, class T, class A, class S>
2604 typename basic_fbstring<E, T, A, S>::value_type,
2605 typename basic_fbstring<E, T, A, S>::traits_type>&
2607 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2608 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2609 basic_fbstring<E, T, A, S>& str) {
2610 typename std::basic_istream<E, T>::sentry sentry(is);
2611 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2612 typename basic_fbstring<E, T, A, S>::traits_type>
2614 typedef typename __istream_type::ios_base __ios_base;
2615 size_t extracted = 0;
2616 auto err = __ios_base::goodbit;
2618 auto n = is.width();
2623 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2624 if (got == T::eof()) {
2625 err |= __ios_base::eofbit;
2633 got = is.rdbuf()->snextc();
2637 err |= __ios_base::failbit;
2645 template <typename E, class T, class A, class S>
2647 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2648 typename basic_fbstring<E, T, A, S>::traits_type>&
2650 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2651 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2652 const basic_fbstring<E, T, A, S>& str) {
2654 typename std::basic_ostream<
2655 typename basic_fbstring<E, T, A, S>::value_type,
2656 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2658 typedef std::ostreambuf_iterator<
2659 typename basic_fbstring<E, T, A, S>::value_type,
2660 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2661 size_t __len = str.size();
2663 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2664 if (__pad_and_output(_Ip(os),
2666 __left ? str.data() + __len : str.data(),
2669 os.fill()).failed()) {
2670 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2673 #elif defined(_MSC_VER)
2674 // MSVC doesn't define __ostream_insert
2675 os.write(str.data(), str.size());
2677 std::__ostream_insert(os, str.data(), str.size());
2682 template <typename E1, class T, class A, class S>
2683 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2684 basic_fbstring<E1, T, A, S>::npos;
2686 #ifndef _LIBSTDCXX_FBSTRING
2687 // basic_string compatibility routines
2689 template <typename E, class T, class A, class S>
2691 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2692 const std::string& rhs) {
2693 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2696 template <typename E, class T, class A, class S>
2698 bool operator==(const std::string& lhs,
2699 const basic_fbstring<E, T, A, S>& rhs) {
2703 template <typename E, class T, class A, class S>
2705 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2706 const std::string& rhs) {
2707 return !(lhs == rhs);
2710 template <typename E, class T, class A, class S>
2712 bool operator!=(const std::string& lhs,
2713 const basic_fbstring<E, T, A, S>& rhs) {
2714 return !(lhs == rhs);
2717 #if !defined(_LIBSTDCXX_FBSTRING)
2718 typedef basic_fbstring<char> fbstring;
2721 // fbstring is relocatable
2722 template <class T, class R, class A, class S>
2723 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2726 _GLIBCXX_END_NAMESPACE_VERSION
2729 } // namespace folly
2731 #ifndef _LIBSTDCXX_FBSTRING
2733 // Hash functions to make fbstring usable with e.g. hash_map
2735 // Handle interaction with different C++ standard libraries, which
2736 // expect these types to be in different namespaces.
2738 #define FOLLY_FBSTRING_HASH1(T) \
2740 struct hash< ::folly::basic_fbstring<T>> { \
2741 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2742 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2746 // The C++11 standard says that these four are defined
2747 #define FOLLY_FBSTRING_HASH \
2748 FOLLY_FBSTRING_HASH1(char) \
2749 FOLLY_FBSTRING_HASH1(char16_t) \
2750 FOLLY_FBSTRING_HASH1(char32_t) \
2751 FOLLY_FBSTRING_HASH1(wchar_t)
2759 #if FOLLY_HAVE_DEPRECATED_ASSOC
2760 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2761 namespace __gnu_cxx {
2765 } // namespace __gnu_cxx
2766 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2767 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2769 #undef FOLLY_FBSTRING_HASH
2770 #undef FOLLY_FBSTRING_HASH1
2772 #endif // _LIBSTDCXX_FBSTRING
2774 #pragma GCC diagnostic pop
2776 #undef FBSTRING_DISABLE_SSO
2777 #undef FBSTRING_SANITIZE_ADDRESS
2779 #undef FBSTRING_LIKELY
2780 #undef FBSTRING_UNLIKELY
2781 #undef FBSTRING_ASSERT