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)
25 #include <type_traits>
27 // This file appears in two locations: inside fbcode and in the
28 // libstdc++ source code (when embedding fbstring as std::string).
29 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
30 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
31 #ifdef _LIBSTDCXX_FBSTRING
33 #pragma GCC system_header
35 #include "basic_fbstring_malloc.h"
37 // When used as std::string replacement always disable assertions.
38 #define FBSTRING_ASSERT(expr) /* empty */
40 #else // !_LIBSTDCXX_FBSTRING
42 #include <folly/Portability.h>
44 // libc++ doesn't provide this header, nor does msvc
45 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
46 #include <bits/c++config.h>
55 #include <folly/Hash.h>
56 #include <folly/Malloc.h>
57 #include <folly/Traits.h>
59 #if FOLLY_HAVE_DEPRECATED_ASSOC
60 #ifdef _GLIBCXX_SYMVER
61 #include <ext/hash_set>
62 #include <ext/hash_map>
66 // When used in folly, assertions are not disabled.
67 #define FBSTRING_ASSERT(expr) assert(expr)
71 // We defined these here rather than including Likely.h to avoid
72 // redefinition errors when fbstring is imported into libstdc++.
73 #if defined(__GNUC__) && __GNUC__ >= 4
74 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
75 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
77 #define FBSTRING_LIKELY(x) (x)
78 #define FBSTRING_UNLIKELY(x) (x)
81 #pragma GCC diagnostic push
82 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
83 #pragma GCC diagnostic ignored "-Wshadow"
84 // GCC 4.9 has a false positive in setSmallSize (probably
85 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
86 // compile-time array bound checking.
87 #pragma GCC diagnostic ignored "-Warray-bounds"
89 // FBString cannot use throw when replacing std::string, though it may still
92 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
94 #ifdef _LIBSTDCXX_FBSTRING
95 namespace std _GLIBCXX_VISIBILITY(default) {
96 _GLIBCXX_BEGIN_NAMESPACE_VERSION
101 #if defined(__clang__)
102 # if __has_feature(address_sanitizer)
103 # define FBSTRING_SANITIZE_ADDRESS
105 #elif defined (__GNUC__) && \
106 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
108 # define FBSTRING_SANITIZE_ADDRESS
111 // When compiling with ASan, always heap-allocate the string even if
112 // it would fit in-situ, so that ASan can detect access to the string
113 // buffer after it has been invalidated (destroyed, resized, etc.).
114 // Note that this flag doesn't remove support for in-situ strings, as
115 // that would break ABI-compatibility and wouldn't allow linking code
116 // compiled with this flag with code compiled without.
117 #ifdef FBSTRING_SANITIZE_ADDRESS
118 # define FBSTRING_DISABLE_SSO true
120 # define FBSTRING_DISABLE_SSO false
123 namespace fbstring_detail {
125 template <class InIt, class OutIt>
126 inline std::pair<InIt, OutIt> copy_n(
128 typename std::iterator_traits<InIt>::difference_type n,
130 for (; n != 0; --n, ++b, ++d) {
133 return std::make_pair(b, d);
136 template <class Pod, class T>
137 inline void podFill(Pod* b, Pod* e, T c) {
138 FBSTRING_ASSERT(b && e && b <= e);
139 /*static*/ if (sizeof(T) == 1) {
140 memset(b, c, size_t(e - b));
142 auto const ee = b + ((e - b) & ~7u);
143 for (; b != ee; b += 8) {
154 for (; b != e; ++b) {
161 * Lightly structured memcpy, simplifies copying PODs and introduces
162 * some asserts. Unfortunately using this function may cause
163 * measurable overhead (presumably because it adjusts from a begin/end
164 * convention to a pointer/size convention, so it does some extra
165 * arithmetic even though the caller might have done the inverse
166 * adaptation outside).
169 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
170 FBSTRING_ASSERT(b != nullptr);
171 FBSTRING_ASSERT(e != nullptr);
172 FBSTRING_ASSERT(d != nullptr);
173 FBSTRING_ASSERT(e >= b);
174 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
175 memcpy(d, b, (e - b) * sizeof(Pod));
179 * Lightly structured memmove, simplifies copying PODs and introduces
183 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
184 FBSTRING_ASSERT(e >= b);
185 memmove(d, b, (e - b) * sizeof(*b));
189 #if defined(__GNUC__) // Clang also defines __GNUC__
190 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
191 #elif defined(_MSC_VER)
192 # define FBSTRING_ALWAYS_INLINE __forceinline
194 # define FBSTRING_ALWAYS_INLINE inline
197 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
198 #if defined(__GNUC__) // Clang also defines __GNUC__
199 __builtin_unreachable();
200 #elif defined(_MSC_VER)
203 // Well, it's better than nothing.
208 } // namespace fbstring_detail
211 * Defines a special acquisition method for constructing fbstring
212 * objects. AcquireMallocatedString means that the user passes a
213 * pointer to a malloc-allocated string that the fbstring object will
216 enum class AcquireMallocatedString {};
219 * fbstring_core_model is a mock-up type that defines all required
220 * signatures of a fbstring core. The fbstring class itself uses such
221 * a core object to implement all of the numerous member functions
222 * required by the standard.
224 * If you want to define a new core, copy the definition below and
225 * implement the primitives. Then plug the core into basic_fbstring as
226 * a template argument.
228 template <class Char>
229 class fbstring_core_model {
231 fbstring_core_model();
232 fbstring_core_model(const fbstring_core_model &);
233 ~fbstring_core_model();
234 // Returns a pointer to string's buffer (currently only contiguous
235 // strings are supported). The pointer is guaranteed to be valid
236 // until the next call to a non-const member function.
237 const Char * data() const;
238 // Much like data(), except the string is prepared to support
239 // character-level changes. This call is a signal for
240 // e.g. reference-counted implementation to fork the data. The
241 // pointer is guaranteed to be valid until the next call to a
242 // non-const member function.
244 // Returns a pointer to string's buffer and guarantees that a
245 // readable '\0' lies right after the buffer. The pointer is
246 // guaranteed to be valid until the next call to a non-const member
248 const Char * c_str() const;
249 // Shrinks the string by delta characters. Asserts that delta <=
251 void shrink(size_t delta);
252 // Expands the string by delta characters (i.e. after this call
253 // size() will report the old size() plus delta) but without
254 // initializing the expanded region. The expanded region is
255 // zero-terminated. Returns a pointer to the memory to be
256 // initialized (the beginning of the expanded portion). The caller
257 // is expected to fill the expanded area appropriately.
258 // If expGrowth is true, exponential growth is guaranteed.
259 // It is not guaranteed not to reallocate even if size() + delta <
260 // capacity(), so all references to the buffer are invalidated.
261 Char* expandNoinit(size_t delta, bool expGrowth);
262 // Expands the string by one character and sets the last character
264 void push_back(Char c);
265 // Returns the string's size.
267 // Returns the string's capacity, i.e. maximum size that the string
268 // can grow to without reallocation. Note that for reference counted
269 // strings that's technically a lie - even assigning characters
270 // within the existing size would cause a reallocation.
271 size_t capacity() const;
272 // Returns true if the data underlying the string is actually shared
273 // across multiple strings (in a refcounted fashion).
274 bool isShared() const;
275 // Makes sure that at least minCapacity characters are available for
276 // the string without reallocation. For reference-counted strings,
277 // it should fork the data even if minCapacity < size().
278 void reserve(size_t minCapacity);
281 fbstring_core_model& operator=(const fbstring_core_model &);
286 * This is the core of the string. The code should work on 32- and
287 * 64-bit and both big- and little-endianan architectures with any
290 * The storage is selected as follows (assuming we store one-byte
291 * characters on a 64-bit machine): (a) "small" strings between 0 and
292 * 23 chars are stored in-situ without allocation (the rightmost byte
293 * stores the size); (b) "medium" strings from 24 through 254 chars
294 * are stored in malloc-allocated memory that is copied eagerly; (c)
295 * "large" strings of 255 chars and above are stored in a similar
296 * structure as medium arrays, except that the string is
297 * reference-counted and copied lazily. the reference count is
298 * allocated right before the character array.
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 switch (rhs.category()) {
330 case Category::isSmall:
333 case Category::isMedium:
336 case Category::isLarge:
340 fbstring_detail::assume_unreachable();
342 FBSTRING_ASSERT(size() == rhs.size());
343 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
346 fbstring_core(fbstring_core&& goner) noexcept {
349 // Clean goner's carcass
353 fbstring_core(const Char *const data,
355 bool disableSSO = FBSTRING_DISABLE_SSO) {
356 if (!disableSSO && size <= maxSmallSize) {
357 initSmall(data, size);
358 } else if (size <= maxMediumSize) {
359 initMedium(data, size);
361 initLarge(data, size);
363 FBSTRING_ASSERT(this->size() == size);
365 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
368 ~fbstring_core() noexcept {
369 if (category() == Category::isSmall) {
372 destroyMediumLarge();
375 // Snatches a previously mallocated string. The parameter "size"
376 // is the size of the string, and the parameter "allocatedSize"
377 // is the size of the mallocated block. The string must be
378 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
380 // So if you want a 2-character string, pass malloc(3) as "data",
381 // pass 2 as "size", and pass 3 as "allocatedSize".
382 fbstring_core(Char * const data,
384 const size_t allocatedSize,
385 AcquireMallocatedString) {
387 FBSTRING_ASSERT(allocatedSize >= size + 1);
388 FBSTRING_ASSERT(data[size] == '\0');
389 // Use the medium string storage
392 // Don't forget about null terminator
393 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
395 // No need for the memory
401 // swap below doesn't test whether &rhs == this (and instead
402 // potentially does extra work) on the premise that the rarity of
403 // that situation actually makes the check more expensive than is
405 void swap(fbstring_core & rhs) {
411 // In C++11 data() and c_str() are 100% equivalent.
412 const Char * data() const {
416 Char* mutableData() {
417 switch (category()) {
418 case Category::isSmall:
420 case Category::isMedium:
422 case Category::isLarge:
423 return mutableDataLarge();
425 fbstring_detail::assume_unreachable();
428 const Char* c_str() const {
429 const Char* ptr = ml_.data_;
430 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
431 ptr = (category() == Category::isSmall) ? small_ : ptr;
435 void shrink(const size_t delta) {
436 if (category() == Category::isSmall) {
438 } else if (category() == Category::isMedium ||
439 RefCounted::refs(ml_.data_) == 1) {
446 FOLLY_MALLOC_NOINLINE
447 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
448 switch (category()) {
449 case Category::isSmall:
450 reserveSmall(minCapacity, disableSSO);
452 case Category::isMedium:
453 reserveMedium(minCapacity);
455 case Category::isLarge:
456 reserveLarge(minCapacity);
459 fbstring_detail::assume_unreachable();
461 FBSTRING_ASSERT(capacity() >= minCapacity);
466 bool expGrowth = false,
467 bool disableSSO = FBSTRING_DISABLE_SSO);
469 void push_back(Char c) {
470 *expandNoinit(1, /* expGrowth = */ true) = c;
473 size_t size() const {
474 size_t ret = ml_.size_;
475 /* static */ if (kIsLittleEndian) {
476 // We can save a couple instructions, because the category is
477 // small iff the last char, as unsigned, is <= maxSmallSize.
478 typedef typename std::make_unsigned<Char>::type UChar;
479 auto maybeSmallSize = size_t(maxSmallSize) -
480 size_t(static_cast<UChar>(small_[maxSmallSize]));
481 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
482 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
484 ret = (category() == Category::isSmall) ? smallSize() : ret;
489 size_t capacity() const {
490 switch (category()) {
491 case Category::isSmall:
493 case Category::isLarge:
494 // For large-sized strings, a multi-referenced chunk has no
495 // available capacity. This is because any attempt to append
496 // data would trigger a new allocation.
497 if (RefCounted::refs(ml_.data_) > 1) {
502 return ml_.capacity();
505 bool isShared() const {
506 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
511 fbstring_core & operator=(const fbstring_core & rhs);
517 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
518 auto const c = category();
519 FBSTRING_ASSERT(c != Category::isSmall);
520 if (c == Category::isMedium) {
523 RefCounted::decrementRefs(ml_.data_);
528 std::atomic<size_t> refCount_;
531 constexpr static size_t getDataOffset() {
532 return offsetof(RefCounted, data_);
535 static RefCounted * fromData(Char * p) {
536 return static_cast<RefCounted*>(static_cast<void*>(
537 static_cast<unsigned char*>(static_cast<void*>(p)) -
541 static size_t refs(Char * p) {
542 return fromData(p)->refCount_.load(std::memory_order_acquire);
545 static void incrementRefs(Char * p) {
546 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
549 static void decrementRefs(Char * p) {
550 auto const dis = fromData(p);
551 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
552 FBSTRING_ASSERT(oldcnt > 0);
558 static RefCounted * create(size_t * size) {
559 const size_t allocSize =
560 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
561 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
562 result->refCount_.store(1, std::memory_order_release);
563 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
567 static RefCounted * create(const Char * data, size_t * size) {
568 const size_t effectiveSize = *size;
569 auto result = create(size);
570 if (FBSTRING_LIKELY(effectiveSize > 0)) {
571 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
576 static RefCounted * reallocate(Char *const data,
577 const size_t currentSize,
578 const size_t currentCapacity,
579 size_t * newCapacity) {
580 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
581 const size_t allocNewCapacity =
582 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
583 auto const dis = fromData(data);
584 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
585 auto result = static_cast<RefCounted*>(smartRealloc(
587 getDataOffset() + (currentSize + 1) * sizeof(Char),
588 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
590 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
591 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
596 typedef uint8_t category_type;
598 enum class Category : category_type {
600 isMedium = kIsLittleEndian ? 0x80 : 0x2,
601 isLarge = kIsLittleEndian ? 0x40 : 0x1,
604 Category category() const {
605 // works for both big-endian and little-endian
606 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
614 size_t capacity() const {
615 return kIsLittleEndian
616 ? capacity_ & capacityExtractMask
620 void setCapacity(size_t cap, Category cat) {
621 capacity_ = kIsLittleEndian
622 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
623 : (cap << 2) | static_cast<size_t>(cat);
628 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
629 Char small_[sizeof(MediumLarge) / sizeof(Char)];
633 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
634 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
635 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
636 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
637 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
638 constexpr static size_t capacityExtractMask = kIsLittleEndian
639 ? ~(size_t(categoryExtractMask) << kCategoryShift)
642 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
643 "Corrupt memory layout for fbstring.");
645 size_t smallSize() const {
646 FBSTRING_ASSERT(category() == Category::isSmall);
647 constexpr auto shift = kIsLittleEndian ? 0 : 2;
648 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
649 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
650 return static_cast<size_t>(maxSmallSize) - smallShifted;
653 void setSmallSize(size_t s) {
654 // Warning: this should work with uninitialized strings too,
655 // so don't assume anything about the previous value of
656 // small_[maxSmallSize].
657 FBSTRING_ASSERT(s <= maxSmallSize);
658 constexpr auto shift = kIsLittleEndian ? 0 : 2;
659 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
661 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
664 void copySmall(const fbstring_core&);
665 void copyMedium(const fbstring_core&);
666 void copyLarge(const fbstring_core&);
668 void initSmall(const Char* data, size_t size);
669 void initMedium(const Char* data, size_t size);
670 void initLarge(const Char* data, size_t size);
672 void reserveSmall(size_t minCapacity, bool disableSSO);
673 void reserveMedium(size_t minCapacity);
674 void reserveLarge(size_t minCapacity);
676 void shrinkSmall(size_t delta);
677 void shrinkMedium(size_t delta);
678 void shrinkLarge(size_t delta);
680 void unshare(size_t minCapacity = 0);
681 Char* mutableDataLarge();
684 template <class Char>
685 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
686 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
688 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
689 "fbstring layout failure");
691 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
692 "fbstring layout failure");
693 // Just write the whole thing, don't look at details. In
694 // particular we need to copy capacity anyway because we want
695 // to set the size (don't forget that the last character,
696 // which stores a short string's length, is shared with the
697 // ml_.capacity field).
700 category() == Category::isSmall && this->size() == rhs.size());
703 template <class Char>
704 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
705 const fbstring_core& rhs) {
706 // Medium strings are copied eagerly. Don't forget to allocate
707 // one extra Char for the null terminator.
708 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
709 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
710 // Also copies terminator.
711 fbstring_detail::podCopy(
712 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
713 ml_.size_ = rhs.ml_.size_;
714 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
715 FBSTRING_ASSERT(category() == Category::isMedium);
718 template <class Char>
719 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
720 const fbstring_core& rhs) {
721 // Large strings are just refcounted
723 RefCounted::incrementRefs(ml_.data_);
724 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
727 // Small strings are bitblitted
728 template <class Char>
729 inline void fbstring_core<Char>::initSmall(
730 const Char* const data, const size_t size) {
731 // Layout is: Char* data_, size_t size_, size_t capacity_
733 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
734 "fbstring has unexpected size");
736 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
737 // sizeof(size_t) must be a power of 2
739 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
740 "fbstring size assumption violation");
742 // If data is aligned, use fast word-wise copying. Otherwise,
743 // use conservative memcpy.
744 // The word-wise path reads bytes which are outside the range of
745 // the string, and makes ASan unhappy, so we disable it when
746 // compiling with ASan.
747 #ifndef FBSTRING_SANITIZE_ADDRESS
748 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
749 const size_t byteSize = size * sizeof(Char);
750 constexpr size_t wordWidth = sizeof(size_t);
751 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
753 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
755 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
757 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
765 fbstring_detail::podCopy(data, data + size, small_);
771 template <class Char>
772 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
773 const Char* const data, const size_t size) {
774 // Medium strings are allocated normally. Don't forget to
775 // allocate one extra Char for the terminating null.
776 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
777 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
778 if (FBSTRING_LIKELY(size > 0)) {
779 fbstring_detail::podCopy(data, data + size, ml_.data_);
782 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
783 ml_.data_[size] = '\0';
786 template <class Char>
787 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
788 const Char* const data, const size_t size) {
789 // Large strings are allocated differently
790 size_t effectiveCapacity = size;
791 auto const newRC = RefCounted::create(data, &effectiveCapacity);
792 ml_.data_ = newRC->data_;
794 ml_.setCapacity(effectiveCapacity, Category::isLarge);
795 ml_.data_[size] = '\0';
798 template <class Char>
799 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
800 size_t minCapacity) {
801 FBSTRING_ASSERT(category() == Category::isLarge);
802 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
803 auto const newRC = RefCounted::create(&effectiveCapacity);
804 // If this fails, someone placed the wrong capacity in an
806 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
807 // Also copies terminator.
808 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
809 RefCounted::decrementRefs(ml_.data_);
810 ml_.data_ = newRC->data_;
811 ml_.setCapacity(effectiveCapacity, Category::isLarge);
812 // size_ remains unchanged.
815 template <class Char>
816 inline Char* fbstring_core<Char>::mutableDataLarge() {
817 FBSTRING_ASSERT(category() == Category::isLarge);
818 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
824 template <class Char>
825 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
826 size_t minCapacity) {
827 FBSTRING_ASSERT(category() == Category::isLarge);
828 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
829 // We must make it unique regardless; in-place reallocation is
830 // useless if the string is shared. In order to not surprise
831 // people, reserve the new block at current capacity or
832 // more. That way, a string's capacity never shrinks after a
834 unshare(minCapacity);
836 // String is not shared, so let's try to realloc (if needed)
837 if (minCapacity > ml_.capacity()) {
838 // Asking for more memory
839 auto const newRC = RefCounted::reallocate(
840 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
841 ml_.data_ = newRC->data_;
842 ml_.setCapacity(minCapacity, Category::isLarge);
844 FBSTRING_ASSERT(capacity() >= minCapacity);
848 template <class Char>
849 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
850 const size_t minCapacity) {
851 FBSTRING_ASSERT(category() == Category::isMedium);
852 // String is not shared
853 if (minCapacity <= ml_.capacity()) {
854 return; // nothing to do, there's enough room
856 if (minCapacity <= maxMediumSize) {
857 // Keep the string at medium size. Don't forget to allocate
858 // one extra Char for the terminating null.
859 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
860 // Also copies terminator.
861 ml_.data_ = static_cast<Char*>(smartRealloc(
863 (ml_.size_ + 1) * sizeof(Char),
864 (ml_.capacity() + 1) * sizeof(Char),
866 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
868 // Conversion from medium to large string
869 fbstring_core nascent;
870 // Will recurse to another branch of this function
871 nascent.reserve(minCapacity);
872 nascent.ml_.size_ = ml_.size_;
873 // Also copies terminator.
874 fbstring_detail::podCopy(
875 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
877 FBSTRING_ASSERT(capacity() >= minCapacity);
881 template <class Char>
882 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
883 size_t minCapacity, const bool disableSSO) {
884 FBSTRING_ASSERT(category() == Category::isSmall);
885 if (!disableSSO && minCapacity <= maxSmallSize) {
887 // Nothing to do, everything stays put
888 } else if (minCapacity <= maxMediumSize) {
890 // Don't forget to allocate one extra Char for the terminating null
891 auto const allocSizeBytes =
892 goodMallocSize((1 + minCapacity) * sizeof(Char));
893 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
894 auto const size = smallSize();
895 // Also copies terminator.
896 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
899 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
902 auto const newRC = RefCounted::create(&minCapacity);
903 auto const size = smallSize();
904 // Also copies terminator.
905 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
906 ml_.data_ = newRC->data_;
908 ml_.setCapacity(minCapacity, Category::isLarge);
909 FBSTRING_ASSERT(capacity() >= minCapacity);
913 template <class Char>
914 inline Char* fbstring_core<Char>::expandNoinit(
916 bool expGrowth, /* = false */
917 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
918 // Strategy is simple: make room, then change size
919 FBSTRING_ASSERT(capacity() >= size());
921 if (category() == Category::isSmall) {
924 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
929 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
933 if (FBSTRING_UNLIKELY(newSz > capacity())) {
934 // ensures not shared
935 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
938 FBSTRING_ASSERT(capacity() >= newSz);
939 // Category can't be small - we took care of that above
941 category() == Category::isMedium || category() == Category::isLarge);
943 ml_.data_[newSz] = '\0';
944 FBSTRING_ASSERT(size() == newSz);
945 return ml_.data_ + sz;
948 template <class Char>
949 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
950 // Check for underflow
951 FBSTRING_ASSERT(delta <= smallSize());
952 setSmallSize(smallSize() - delta);
955 template <class Char>
956 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
957 // Medium strings and unique large strings need no special
959 FBSTRING_ASSERT(ml_.size_ >= delta);
961 ml_.data_[ml_.size_] = '\0';
964 template <class Char>
965 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
966 FBSTRING_ASSERT(ml_.size_ >= delta);
967 // Shared large string, must make unique. This is because of the
968 // durn terminator must be written, which may trample the shared
971 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
973 // No need to write the terminator.
976 #ifndef _LIBSTDCXX_FBSTRING
978 * Dummy fbstring core that uses an actual std::string. This doesn't
979 * make any sense - it's just for testing purposes.
981 template <class Char>
982 class dummy_fbstring_core {
984 dummy_fbstring_core() {
986 dummy_fbstring_core(const dummy_fbstring_core& another)
987 : backend_(another.backend_) {
989 dummy_fbstring_core(const Char * s, size_t n)
992 void swap(dummy_fbstring_core & rhs) {
993 backend_.swap(rhs.backend_);
995 const Char * data() const {
996 return backend_.data();
998 Char* mutableData() {
999 return const_cast<Char*>(backend_.data());
1001 void shrink(size_t delta) {
1002 FBSTRING_ASSERT(delta <= size());
1003 backend_.resize(size() - delta);
1005 Char* expandNoinit(size_t delta) {
1006 auto const sz = size();
1007 backend_.resize(size() + delta);
1008 return backend_.data() + sz;
1010 void push_back(Char c) {
1011 backend_.push_back(c);
1013 size_t size() const {
1014 return backend_.size();
1016 size_t capacity() const {
1017 return backend_.capacity();
1019 bool isShared() const {
1022 void reserve(size_t minCapacity) {
1023 backend_.reserve(minCapacity);
1027 std::basic_string<Char> backend_;
1029 #endif // !_LIBSTDCXX_FBSTRING
1032 * This is the basic_string replacement. For conformity,
1033 * basic_fbstring takes the same template parameters, plus the last
1034 * one which is the core.
1036 #ifdef _LIBSTDCXX_FBSTRING
1037 template <typename E, class T, class A, class Storage>
1039 template <typename E,
1040 class T = std::char_traits<E>,
1041 class A = std::allocator<E>,
1042 class Storage = fbstring_core<E> >
1044 class basic_fbstring {
1045 static void enforce(
1047 void (*throw_exc)(const char*),
1054 bool isSane() const {
1057 empty() == (size() == 0) &&
1058 empty() == (begin() == end()) &&
1059 size() <= max_size() &&
1060 capacity() <= max_size() &&
1061 size() <= capacity() &&
1062 begin()[size()] == '\0';
1066 Invariant& operator=(const Invariant&) = delete;
1067 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1068 FBSTRING_ASSERT(s_.isSane());
1070 ~Invariant() noexcept {
1071 FBSTRING_ASSERT(s_.isSane());
1075 const basic_fbstring& s_;
1080 typedef T traits_type;
1081 typedef typename traits_type::char_type value_type;
1082 typedef A allocator_type;
1083 typedef typename A::size_type size_type;
1084 typedef typename A::difference_type difference_type;
1086 typedef typename A::reference reference;
1087 typedef typename A::const_reference const_reference;
1088 typedef typename A::pointer pointer;
1089 typedef typename A::const_pointer const_pointer;
1091 typedef E* iterator;
1092 typedef const E* const_iterator;
1093 typedef std::reverse_iterator<iterator
1094 #ifdef NO_ITERATOR_TRAITS
1098 typedef std::reverse_iterator<const_iterator
1099 #ifdef NO_ITERATOR_TRAITS
1102 > const_reverse_iterator;
1104 static constexpr size_type npos = size_type(-1);
1105 typedef std::true_type IsRelocatable;
1108 static void procrustes(size_type& n, size_type nmax) {
1114 static size_type traitsLength(const value_type* s);
1117 // C++11 21.4.2 construct/copy/destroy
1119 // Note: while the following two constructors can be (and previously were)
1120 // collapsed into one constructor written this way:
1122 // explicit basic_fbstring(const A& a = A()) noexcept { }
1124 // This can cause Clang (at least version 3.7) to fail with the error:
1125 // "chosen constructor is explicit in copy-initialization ...
1126 // in implicit initialization of field '(x)' with omitted initializer"
1128 // if used in a struct which is default-initialized. Hence the split into
1129 // these two separate constructors.
1131 basic_fbstring() noexcept : basic_fbstring(A()) {
1134 explicit basic_fbstring(const A&) noexcept {
1137 basic_fbstring(const basic_fbstring& str)
1138 : store_(str.store_) {
1142 basic_fbstring(basic_fbstring&& goner) noexcept
1143 : store_(std::move(goner.store_)) {
1146 #ifndef _LIBSTDCXX_FBSTRING
1147 // This is defined for compatibility with std::string
1148 /* implicit */ basic_fbstring(const std::string& str)
1149 : store_(str.data(), str.size()) {
1153 basic_fbstring(const basic_fbstring& str,
1156 const A& /* a */ = A()) {
1157 assign(str, pos, n);
1160 FOLLY_MALLOC_NOINLINE
1161 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1162 : store_(s, traitsLength(s)) {}
1164 FOLLY_MALLOC_NOINLINE
1165 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1169 FOLLY_MALLOC_NOINLINE
1170 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1171 auto const pData = store_.expandNoinit(n);
1172 fbstring_detail::podFill(pData, pData + n, c);
1175 template <class InIt>
1176 FOLLY_MALLOC_NOINLINE basic_fbstring(
1179 typename std::enable_if<
1180 !std::is_same<InIt, value_type*>::value,
1181 const A>::type& /*a*/ = A()) {
1185 // Specialization for const char*, const char*
1186 FOLLY_MALLOC_NOINLINE
1187 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1188 : store_(b, size_type(e - b)) {
1191 // Nonstandard constructor
1192 basic_fbstring(value_type *s, size_type n, size_type c,
1193 AcquireMallocatedString a)
1194 : store_(s, n, c, a) {
1197 // Construction from initialization list
1198 FOLLY_MALLOC_NOINLINE
1199 basic_fbstring(std::initializer_list<value_type> il) {
1200 assign(il.begin(), il.end());
1203 ~basic_fbstring() noexcept {}
1205 basic_fbstring& operator=(const basic_fbstring& lhs);
1208 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1210 #ifndef _LIBSTDCXX_FBSTRING
1211 // Compatibility with std::string
1212 basic_fbstring & operator=(const std::string & rhs) {
1213 return assign(rhs.data(), rhs.size());
1216 // Compatibility with std::string
1217 std::string toStdString() const {
1218 return std::string(data(), size());
1221 // A lot of code in fbcode still uses this method, so keep it here for now.
1222 const basic_fbstring& toStdString() const {
1227 basic_fbstring& operator=(const value_type* s) {
1231 basic_fbstring& operator=(value_type c);
1233 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1234 return assign(il.begin(), il.end());
1237 // C++11 21.4.3 iterators:
1239 return store_.mutableData();
1242 const_iterator begin() const {
1243 return store_.data();
1246 const_iterator cbegin() const {
1251 return store_.mutableData() + store_.size();
1254 const_iterator end() const {
1255 return store_.data() + store_.size();
1258 const_iterator cend() const { return end(); }
1260 reverse_iterator rbegin() {
1261 return reverse_iterator(end());
1264 const_reverse_iterator rbegin() const {
1265 return const_reverse_iterator(end());
1268 const_reverse_iterator crbegin() const { return rbegin(); }
1270 reverse_iterator rend() {
1271 return reverse_iterator(begin());
1274 const_reverse_iterator rend() const {
1275 return const_reverse_iterator(begin());
1278 const_reverse_iterator crend() const { return rend(); }
1281 // C++11 21.4.5, element access:
1282 const value_type& front() const { return *begin(); }
1283 const value_type& back() const {
1284 FBSTRING_ASSERT(!empty());
1285 // Should be begin()[size() - 1], but that branches twice
1286 return *(end() - 1);
1288 value_type& front() { return *begin(); }
1289 value_type& back() {
1290 FBSTRING_ASSERT(!empty());
1291 // Should be begin()[size() - 1], but that branches twice
1292 return *(end() - 1);
1295 FBSTRING_ASSERT(!empty());
1299 // C++11 21.4.4 capacity:
1300 size_type size() const { return store_.size(); }
1302 size_type length() const { return size(); }
1304 size_type max_size() const {
1305 return std::numeric_limits<size_type>::max();
1308 void resize(size_type n, value_type c = value_type());
1310 size_type capacity() const { return store_.capacity(); }
1312 void reserve(size_type res_arg = 0) {
1313 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1314 store_.reserve(res_arg);
1317 void shrink_to_fit() {
1318 // Shrink only if slack memory is sufficiently large
1319 if (capacity() < size() * 3 / 2) {
1322 basic_fbstring(cbegin(), cend()).swap(*this);
1325 void clear() { resize(0); }
1327 bool empty() const { return size() == 0; }
1329 // C++11 21.4.5 element access:
1330 const_reference operator[](size_type pos) const {
1331 return *(begin() + pos);
1334 reference operator[](size_type pos) {
1335 return *(begin() + pos);
1338 const_reference at(size_type n) const {
1339 enforce(n <= size(), std::__throw_out_of_range, "");
1343 reference at(size_type n) {
1344 enforce(n < size(), std::__throw_out_of_range, "");
1348 // C++11 21.4.6 modifiers:
1349 basic_fbstring& operator+=(const basic_fbstring& str) {
1353 basic_fbstring& operator+=(const value_type* s) {
1357 basic_fbstring& operator+=(const value_type c) {
1362 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1367 basic_fbstring& append(const basic_fbstring& str);
1370 append(const basic_fbstring& str, const size_type pos, size_type n);
1372 basic_fbstring& append(const value_type* s, size_type n);
1374 basic_fbstring& append(const value_type* s) {
1375 return append(s, traitsLength(s));
1378 basic_fbstring& append(size_type n, value_type c);
1380 template<class InputIterator>
1381 basic_fbstring& append(InputIterator first, InputIterator last) {
1382 insert(end(), first, last);
1386 basic_fbstring& append(std::initializer_list<value_type> il) {
1387 return append(il.begin(), il.end());
1390 void push_back(const value_type c) { // primitive
1391 store_.push_back(c);
1394 basic_fbstring& assign(const basic_fbstring& str) {
1395 if (&str == this) return *this;
1396 return assign(str.data(), str.size());
1399 basic_fbstring& assign(basic_fbstring&& str) {
1400 return *this = std::move(str);
1404 assign(const basic_fbstring& str, const size_type pos, size_type n);
1406 basic_fbstring& assign(const value_type* s, const size_type n);
1408 basic_fbstring& assign(const value_type* s) {
1409 return assign(s, traitsLength(s));
1412 basic_fbstring& assign(std::initializer_list<value_type> il) {
1413 return assign(il.begin(), il.end());
1416 template <class ItOrLength, class ItOrChar>
1417 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1418 return replace(begin(), end(), first_or_n, last_or_c);
1421 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1422 return insert(pos1, str.data(), str.size());
1425 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1426 size_type pos2, size_type n) {
1427 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1428 procrustes(n, str.length() - pos2);
1429 return insert(pos1, str.data() + pos2, n);
1432 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1433 enforce(pos <= length(), std::__throw_out_of_range, "");
1434 insert(begin() + pos, s, s + n);
1438 basic_fbstring& insert(size_type pos, const value_type* s) {
1439 return insert(pos, s, traitsLength(s));
1442 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1443 enforce(pos <= length(), std::__throw_out_of_range, "");
1444 insert(begin() + pos, n, c);
1448 iterator insert(const_iterator p, const value_type c) {
1449 const size_type pos = p - cbegin();
1451 return begin() + pos;
1454 #ifndef _LIBSTDCXX_FBSTRING
1456 typedef std::basic_istream<value_type, traits_type> istream_type;
1457 istream_type& getlineImpl(istream_type& is, value_type delim);
1460 friend inline istream_type& getline(istream_type& is,
1461 basic_fbstring& str,
1463 return str.getlineImpl(is, delim);
1466 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1467 return getline(is, str, '\n');
1473 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1475 template <class InputIter>
1477 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1479 template <class FwdIterator>
1480 iterator insertImpl(
1484 std::forward_iterator_tag);
1486 template <class InputIterator>
1487 iterator insertImpl(
1491 std::input_iterator_tag);
1494 template <class ItOrLength, class ItOrChar>
1495 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1496 using Sel = std::integral_constant<
1498 std::numeric_limits<ItOrLength>::is_specialized>;
1499 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1502 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1503 return insert(p, il.begin(), il.end());
1506 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1507 Invariant checker(*this);
1509 enforce(pos <= length(), std::__throw_out_of_range, "");
1510 procrustes(n, length() - pos);
1511 std::copy(begin() + pos + n, end(), begin() + pos);
1512 resize(length() - n);
1516 iterator erase(iterator position) {
1517 const size_type pos(position - begin());
1518 enforce(pos <= size(), std::__throw_out_of_range, "");
1520 return begin() + pos;
1523 iterator erase(iterator first, iterator last) {
1524 const size_type pos(first - begin());
1525 erase(pos, last - first);
1526 return begin() + pos;
1529 // Replaces at most n1 chars of *this, starting with pos1 with the
1531 basic_fbstring& replace(size_type pos1, size_type n1,
1532 const basic_fbstring& str) {
1533 return replace(pos1, n1, str.data(), str.size());
1536 // Replaces at most n1 chars of *this, starting with pos1,
1537 // with at most n2 chars of str starting with pos2
1538 basic_fbstring& replace(size_type pos1, size_type n1,
1539 const basic_fbstring& str,
1540 size_type pos2, size_type n2) {
1541 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1542 return replace(pos1, n1, str.data() + pos2,
1543 std::min(n2, str.size() - pos2));
1546 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1547 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1548 return replace(pos, n1, s, traitsLength(s));
1551 // Replaces at most n1 chars of *this, starting with pos, with n2
1554 // consolidated with
1556 // Replaces at most n1 chars of *this, starting with pos, with at
1557 // most n2 chars of str. str must have at least n2 chars.
1558 template <class StrOrLength, class NumOrChar>
1559 basic_fbstring& replace(size_type pos, size_type n1,
1560 StrOrLength s_or_n2, NumOrChar n_or_c) {
1561 Invariant checker(*this);
1563 enforce(pos <= size(), std::__throw_out_of_range, "");
1564 procrustes(n1, length() - pos);
1565 const iterator b = begin() + pos;
1566 return replace(b, b + n1, s_or_n2, n_or_c);
1569 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1570 return replace(i1, i2, str.data(), str.length());
1573 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1574 return replace(i1, i2, s, traitsLength(s));
1578 basic_fbstring& replaceImplDiscr(
1581 const value_type* s,
1583 std::integral_constant<int, 2>);
1585 basic_fbstring& replaceImplDiscr(
1590 std::integral_constant<int, 1>);
1592 template <class InputIter>
1593 basic_fbstring& replaceImplDiscr(
1598 std::integral_constant<int, 0>);
1601 template <class FwdIterator>
1602 bool replaceAliased(iterator /* i1 */,
1604 FwdIterator /* s1 */,
1605 FwdIterator /* s2 */,
1610 template <class FwdIterator>
1611 bool replaceAliased(
1618 template <class FwdIterator>
1624 std::forward_iterator_tag);
1626 template <class InputIterator>
1632 std::input_iterator_tag);
1635 template <class T1, class T2>
1636 basic_fbstring& replace(iterator i1, iterator i2,
1637 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1638 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1639 num2 = std::numeric_limits<T2>::is_specialized;
1641 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1642 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1645 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1646 enforce(pos <= size(), std::__throw_out_of_range, "");
1647 procrustes(n, size() - pos);
1650 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1655 void swap(basic_fbstring& rhs) {
1656 store_.swap(rhs.store_);
1659 const value_type* c_str() const {
1660 return store_.c_str();
1663 const value_type* data() const { return c_str(); }
1665 allocator_type get_allocator() const {
1666 return allocator_type();
1669 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1670 return find(str.data(), pos, str.length());
1673 size_type find(const value_type* needle, size_type pos, size_type nsize)
1676 size_type find(const value_type* s, size_type pos = 0) const {
1677 return find(s, pos, traitsLength(s));
1680 size_type find (value_type c, size_type pos = 0) const {
1681 return find(&c, pos, 1);
1684 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1685 return rfind(str.data(), pos, str.length());
1688 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1690 size_type rfind(const value_type* s, size_type pos = npos) const {
1691 return rfind(s, pos, traitsLength(s));
1694 size_type rfind(value_type c, size_type pos = npos) const {
1695 return rfind(&c, pos, 1);
1698 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1699 return find_first_of(str.data(), pos, str.length());
1702 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1705 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1706 return find_first_of(s, pos, traitsLength(s));
1709 size_type find_first_of(value_type c, size_type pos = 0) const {
1710 return find_first_of(&c, pos, 1);
1713 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1715 return find_last_of(str.data(), pos, str.length());
1718 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1720 size_type find_last_of (const value_type* s,
1721 size_type pos = npos) const {
1722 return find_last_of(s, pos, traitsLength(s));
1725 size_type find_last_of (value_type c, size_type pos = npos) const {
1726 return find_last_of(&c, pos, 1);
1729 size_type find_first_not_of(const basic_fbstring& str,
1730 size_type pos = 0) const {
1731 return find_first_not_of(str.data(), pos, str.size());
1734 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1737 size_type find_first_not_of(const value_type* s,
1738 size_type pos = 0) const {
1739 return find_first_not_of(s, pos, traitsLength(s));
1742 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1743 return find_first_not_of(&c, pos, 1);
1746 size_type find_last_not_of(const basic_fbstring& str,
1747 size_type pos = npos) const {
1748 return find_last_not_of(str.data(), pos, str.length());
1751 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1754 size_type find_last_not_of(const value_type* s,
1755 size_type pos = npos) const {
1756 return find_last_not_of(s, pos, traitsLength(s));
1759 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1760 return find_last_not_of(&c, pos, 1);
1763 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1764 enforce(pos <= size(), std::__throw_out_of_range, "");
1765 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1768 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1769 enforce(pos <= size(), std::__throw_out_of_range, "");
1774 return std::move(*this);
1777 int compare(const basic_fbstring& str) const {
1778 // FIX due to Goncalo N M de Carvalho July 18, 2005
1779 return compare(0, size(), str);
1782 int compare(size_type pos1, size_type n1,
1783 const basic_fbstring& str) const {
1784 return compare(pos1, n1, str.data(), str.size());
1787 int compare(size_type pos1, size_type n1,
1788 const value_type* s) const {
1789 return compare(pos1, n1, s, traitsLength(s));
1792 int compare(size_type pos1, size_type n1,
1793 const value_type* s, size_type n2) const {
1794 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1795 procrustes(n1, size() - pos1);
1796 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1797 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1798 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1801 int compare(size_type pos1, size_type n1,
1802 const basic_fbstring& str,
1803 size_type pos2, size_type n2) const {
1804 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1805 return compare(pos1, n1, str.data() + pos2,
1806 std::min(n2, str.size() - pos2));
1809 // Code from Jean-Francois Bastien (03/26/2007)
1810 int compare(const value_type* s) const {
1811 // Could forward to compare(0, size(), s, traitsLength(s))
1812 // but that does two extra checks
1813 const size_type n1(size()), n2(traitsLength(s));
1814 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1815 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1823 template <typename E, class T, class A, class S>
1824 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1825 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1826 return s ? traits_type::length(s)
1827 : (std::__throw_logic_error(
1828 "basic_fbstring: null pointer initializer not valid"),
1832 template <typename E, class T, class A, class S>
1833 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1834 const basic_fbstring& lhs) {
1835 Invariant checker(*this);
1837 if (FBSTRING_UNLIKELY(&lhs == this)) {
1841 return assign(lhs.data(), lhs.size());
1845 template <typename E, class T, class A, class S>
1846 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1847 basic_fbstring&& goner) noexcept {
1848 if (FBSTRING_UNLIKELY(&goner == this)) {
1849 // Compatibility with std::basic_string<>,
1850 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1853 // No need of this anymore
1854 this->~basic_fbstring();
1855 // Move the goner into this
1856 new (&store_) S(std::move(goner.store_));
1860 template <typename E, class T, class A, class S>
1861 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1862 const value_type c) {
1863 Invariant checker(*this);
1866 store_.expandNoinit(1);
1867 } else if (store_.isShared()) {
1868 basic_fbstring(1, c).swap(*this);
1871 store_.shrink(size() - 1);
1877 template <typename E, class T, class A, class S>
1878 inline void basic_fbstring<E, T, A, S>::resize(
1879 const size_type n, const value_type c /*= value_type()*/) {
1880 Invariant checker(*this);
1882 auto size = this->size();
1884 store_.shrink(size - n);
1886 auto const delta = n - size;
1887 auto pData = store_.expandNoinit(delta);
1888 fbstring_detail::podFill(pData, pData + delta, c);
1890 FBSTRING_ASSERT(this->size() == n);
1893 template <typename E, class T, class A, class S>
1894 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1895 const basic_fbstring& str) {
1897 auto desiredSize = size() + str.size();
1899 append(str.data(), str.size());
1900 FBSTRING_ASSERT(size() == desiredSize);
1904 template <typename E, class T, class A, class S>
1905 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1906 const basic_fbstring& str, const size_type pos, size_type n) {
1907 const size_type sz = str.size();
1908 enforce(pos <= sz, std::__throw_out_of_range, "");
1909 procrustes(n, sz - pos);
1910 return append(str.data() + pos, n);
1913 template <typename E, class T, class A, class S>
1914 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1915 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1916 Invariant checker(*this);
1918 if (FBSTRING_UNLIKELY(!n)) {
1919 // Unlikely but must be done
1922 auto const oldSize = size();
1923 auto const oldData = data();
1924 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1926 // Check for aliasing (rare). We could use "<=" here but in theory
1927 // those do not work for pointers unless the pointers point to
1928 // elements in the same array. For that reason we use
1929 // std::less_equal, which is guaranteed to offer a total order
1930 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1932 std::less_equal<const value_type*> le;
1933 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1934 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1935 // expandNoinit() could have moved the storage, restore the source.
1936 s = data() + (s - oldData);
1937 fbstring_detail::podMove(s, s + n, pData);
1939 fbstring_detail::podCopy(s, s + n, pData);
1942 FBSTRING_ASSERT(size() == oldSize + n);
1946 template <typename E, class T, class A, class S>
1947 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1948 size_type n, value_type c) {
1949 Invariant checker(*this);
1950 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1951 fbstring_detail::podFill(pData, pData + n, c);
1955 template <typename E, class T, class A, class S>
1956 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1957 const basic_fbstring& str, const size_type pos, size_type n) {
1958 const size_type sz = str.size();
1959 enforce(pos <= sz, std::__throw_out_of_range, "");
1960 procrustes(n, sz - pos);
1961 return assign(str.data() + pos, n);
1964 template <typename E, class T, class A, class S>
1965 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1966 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1967 Invariant checker(*this);
1971 } else if (size() >= n) {
1972 // s can alias this, we need to use podMove.
1973 fbstring_detail::podMove(s, s + n, store_.mutableData());
1974 store_.shrink(size() - n);
1975 FBSTRING_ASSERT(size() == n);
1977 // If n is larger than size(), s cannot alias this string's
1980 // Do not use exponential growth here: assign() should be tight,
1981 // to mirror the behavior of the equivalent constructor.
1982 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
1985 FBSTRING_ASSERT(size() == n);
1989 #ifndef _LIBSTDCXX_FBSTRING
1990 template <typename E, class T, class A, class S>
1991 inline typename basic_fbstring<E, T, A, S>::istream_type&
1992 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
1993 Invariant checker(*this);
1998 size_t avail = capacity() - size;
1999 // fbstring has 1 byte extra capacity for the null terminator,
2000 // and getline null-terminates the read string.
2001 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2002 size += is.gcount();
2004 if (is.bad() || is.eof() || !is.fail()) {
2005 // Done by either failure, end of file, or normal read.
2006 if (!is.bad() && !is.eof()) {
2007 --size; // gcount() also accounts for the delimiter.
2013 FBSTRING_ASSERT(size == this->size());
2014 FBSTRING_ASSERT(size == capacity());
2015 // Start at minimum allocation 63 + terminator = 64.
2016 reserve(std::max<size_t>(63, 3 * size / 2));
2017 // Clear the error so we can continue reading.
2024 template <typename E, class T, class A, class S>
2025 inline typename basic_fbstring<E, T, A, S>::size_type
2026 basic_fbstring<E, T, A, S>::find(
2027 const value_type* needle, const size_type pos, const size_type nsize)
2029 auto const size = this->size();
2030 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2031 // that nsize + pos does not wrap around.
2032 if (nsize + pos > size || nsize + pos < pos) {
2039 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2040 // the last characters first
2041 auto const haystack = data();
2042 auto const nsize_1 = nsize - 1;
2043 auto const lastNeedle = needle[nsize_1];
2045 // Boyer-Moore skip value for the last char in the needle. Zero is
2046 // not a valid value; skip will be computed the first time it's
2050 const E* i = haystack + pos;
2051 auto iEnd = haystack + size - nsize_1;
2054 // Boyer-Moore: match the last element in the needle
2055 while (i[nsize_1] != lastNeedle) {
2061 // Here we know that the last char matches
2062 // Continue in pedestrian mode
2063 for (size_t j = 0;;) {
2064 FBSTRING_ASSERT(j < nsize);
2065 if (i[j] != needle[j]) {
2066 // Not found, we can skip
2067 // Compute the skip value lazily
2070 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2077 // Check if done searching
2080 return i - haystack;
2087 template <typename E, class T, class A, class S>
2088 inline typename basic_fbstring<E, T, A, S>::iterator
2089 basic_fbstring<E, T, A, S>::insertImplDiscr(
2090 const_iterator i, size_type n, value_type c, std::true_type) {
2091 Invariant checker(*this);
2093 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2094 const size_type pos = i - cbegin();
2096 auto oldSize = size();
2097 store_.expandNoinit(n, /* expGrowth = */ true);
2099 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2100 fbstring_detail::podFill(b + pos, b + pos + n, c);
2105 template <typename E, class T, class A, class S>
2106 template <class InputIter>
2107 inline typename basic_fbstring<E, T, A, S>::iterator
2108 basic_fbstring<E, T, A, S>::insertImplDiscr(
2109 const_iterator i, InputIter b, InputIter e, std::false_type) {
2111 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2114 template <typename E, class T, class A, class S>
2115 template <class FwdIterator>
2116 inline typename basic_fbstring<E, T, A, S>::iterator
2117 basic_fbstring<E, T, A, S>::insertImpl(
2121 std::forward_iterator_tag) {
2122 Invariant checker(*this);
2124 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2125 const size_type pos = i - cbegin();
2126 auto n = std::distance(s1, s2);
2127 FBSTRING_ASSERT(n >= 0);
2129 auto oldSize = size();
2130 store_.expandNoinit(n, /* expGrowth = */ true);
2132 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2133 std::copy(s1, s2, b + pos);
2138 template <typename E, class T, class A, class S>
2139 template <class InputIterator>
2140 inline typename basic_fbstring<E, T, A, S>::iterator
2141 basic_fbstring<E, T, A, S>::insertImpl(
2145 std::input_iterator_tag) {
2146 const auto pos = i - cbegin();
2147 basic_fbstring temp(cbegin(), i);
2148 for (; b != e; ++b) {
2151 temp.append(i, cend());
2153 return begin() + pos;
2156 template <typename E, class T, class A, class S>
2157 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2160 const value_type* s,
2162 std::integral_constant<int, 2>) {
2163 FBSTRING_ASSERT(i1 <= i2);
2164 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2165 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2166 return replace(i1, i2, s, s + n);
2169 template <typename E, class T, class A, class S>
2170 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2175 std::integral_constant<int, 1>) {
2176 const size_type n1 = i2 - i1;
2178 std::fill(i1, i1 + n2, c);
2181 std::fill(i1, i2, c);
2182 insert(i2, n2 - n1, c);
2184 FBSTRING_ASSERT(isSane());
2188 template <typename E, class T, class A, class S>
2189 template <class InputIter>
2190 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2195 std::integral_constant<int, 0>) {
2196 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2197 replaceImpl(i1, i2, b, e, Cat());
2201 template <typename E, class T, class A, class S>
2202 template <class FwdIterator>
2203 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2204 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2205 std::less_equal<const value_type*> le{};
2206 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2210 // Aliased replace, copy to new string
2211 basic_fbstring temp;
2212 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2213 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2218 template <typename E, class T, class A, class S>
2219 template <class FwdIterator>
2220 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2225 std::forward_iterator_tag) {
2226 Invariant checker(*this);
2228 // Handle aliased replace
2229 using Sel = std::integral_constant<
2231 std::is_same<FwdIterator, iterator>::value ||
2232 std::is_same<FwdIterator, const_iterator>::value>;
2233 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2237 auto const n1 = i2 - i1;
2238 FBSTRING_ASSERT(n1 >= 0);
2239 auto const n2 = std::distance(s1, s2);
2240 FBSTRING_ASSERT(n2 >= 0);
2244 std::copy(s1, s2, i1);
2248 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2251 FBSTRING_ASSERT(isSane());
2254 template <typename E, class T, class A, class S>
2255 template <class InputIterator>
2256 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2261 std::input_iterator_tag) {
2262 basic_fbstring temp(begin(), i1);
2263 temp.append(b, e).append(i2, end());
2267 template <typename E, class T, class A, class S>
2268 inline typename basic_fbstring<E, T, A, S>::size_type
2269 basic_fbstring<E, T, A, S>::rfind(
2270 const value_type* s, size_type pos, size_type n) const {
2274 pos = std::min(pos, length() - n);
2279 const_iterator i(begin() + pos);
2281 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2291 template <typename E, class T, class A, class S>
2292 inline typename basic_fbstring<E, T, A, S>::size_type
2293 basic_fbstring<E, T, A, S>::find_first_of(
2294 const value_type* s, size_type pos, size_type n) const {
2295 if (pos > length() || n == 0) {
2298 const_iterator i(begin() + pos), finish(end());
2299 for (; i != finish; ++i) {
2300 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_of(
2310 const value_type* s, size_type pos, size_type n) const {
2311 if (!empty() && n > 0) {
2312 pos = std::min(pos, length() - 1);
2313 const_iterator i(begin() + pos);
2315 if (traits_type::find(s, n, *i) != 0) {
2326 template <typename E, class T, class A, class S>
2327 inline typename basic_fbstring<E, T, A, S>::size_type
2328 basic_fbstring<E, T, A, S>::find_first_not_of(
2329 const value_type* s, size_type pos, size_type n) const {
2330 if (pos < length()) {
2331 const_iterator i(begin() + pos), finish(end());
2332 for (; i != finish; ++i) {
2333 if (traits_type::find(s, n, *i) == 0) {
2341 template <typename E, class T, class A, class S>
2342 inline typename basic_fbstring<E, T, A, S>::size_type
2343 basic_fbstring<E, T, A, S>::find_last_not_of(
2344 const value_type* s, size_type pos, size_type n) const {
2345 if (!this->empty()) {
2346 pos = std::min(pos, size() - 1);
2347 const_iterator i(begin() + pos);
2349 if (traits_type::find(s, n, *i) == 0) {
2360 // non-member functions
2362 template <typename E, class T, class A, class S>
2364 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2365 const basic_fbstring<E, T, A, S>& rhs) {
2367 basic_fbstring<E, T, A, S> result;
2368 result.reserve(lhs.size() + rhs.size());
2369 result.append(lhs).append(rhs);
2370 return std::move(result);
2374 template <typename E, class T, class A, class S>
2376 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2377 const basic_fbstring<E, T, A, S>& rhs) {
2378 return std::move(lhs.append(rhs));
2382 template <typename E, class T, class A, class S>
2384 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2385 basic_fbstring<E, T, A, S>&& rhs) {
2386 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2387 // Good, at least we don't need to reallocate
2388 return std::move(rhs.insert(0, lhs));
2390 // Meh, no go. Forward to operator+(const&, const&).
2391 auto const& rhsC = rhs;
2396 template <typename E, class T, class A, class S>
2398 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2399 basic_fbstring<E, T, A, S>&& rhs) {
2400 return std::move(lhs.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 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2412 result.reserve(len + rhs.size());
2413 result.append(lhs, len).append(rhs);
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 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2425 if (rhs.capacity() >= len + rhs.size()) {
2426 // Good, at least we don't need to reallocate
2427 rhs.insert(rhs.begin(), lhs, lhs + len);
2430 // Meh, no go. Do it by hand since we have len already.
2431 basic_fbstring<E, T, A, S> result;
2432 result.reserve(len + rhs.size());
2433 result.append(lhs, len).append(rhs);
2438 template <typename E, class T, class A, class S>
2440 basic_fbstring<E, T, A, S> operator+(
2442 const basic_fbstring<E, T, A, S>& rhs) {
2444 basic_fbstring<E, T, A, S> result;
2445 result.reserve(1 + rhs.size());
2446 result.push_back(lhs);
2452 template <typename E, class T, class A, class S>
2454 basic_fbstring<E, T, A, S> operator+(
2456 basic_fbstring<E, T, A, S>&& rhs) {
2458 if (rhs.capacity() > rhs.size()) {
2459 // Good, at least we don't need to reallocate
2460 rhs.insert(rhs.begin(), lhs);
2463 // Meh, no go. Forward to operator+(E, const&).
2464 auto const& rhsC = rhs;
2469 template <typename E, class T, class A, class S>
2471 basic_fbstring<E, T, A, S> operator+(
2472 const basic_fbstring<E, T, A, S>& lhs,
2475 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2476 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2478 basic_fbstring<E, T, A, S> result;
2479 const size_type len = traits_type::length(rhs);
2480 result.reserve(lhs.size() + len);
2481 result.append(lhs).append(rhs, len);
2485 // C++11 21.4.8.1/10
2486 template <typename E, class T, class A, class S>
2488 basic_fbstring<E, T, A, S> operator+(
2489 basic_fbstring<E, T, A, S>&& lhs,
2492 return std::move(lhs += rhs);
2495 // C++11 21.4.8.1/11
2496 template <typename E, class T, class A, class S>
2498 basic_fbstring<E, T, A, S> operator+(
2499 const basic_fbstring<E, T, A, S>& lhs,
2502 basic_fbstring<E, T, A, S> result;
2503 result.reserve(lhs.size() + 1);
2505 result.push_back(rhs);
2509 // C++11 21.4.8.1/12
2510 template <typename E, class T, class A, class S>
2512 basic_fbstring<E, T, A, S> operator+(
2513 basic_fbstring<E, T, A, S>&& lhs,
2516 return std::move(lhs += rhs);
2519 template <typename E, class T, class A, class S>
2521 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2522 const basic_fbstring<E, T, A, S>& rhs) {
2523 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2525 template <typename E, class T, class A, class S>
2527 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2528 const basic_fbstring<E, T, A, S>& rhs) {
2529 return rhs == lhs; }
2531 template <typename E, class T, class A, class S>
2533 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2534 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2535 return lhs.compare(rhs) == 0; }
2537 template <typename E, class T, class A, class S>
2539 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2540 const basic_fbstring<E, T, A, S>& rhs) {
2541 return !(lhs == rhs); }
2543 template <typename E, class T, class A, class S>
2545 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2546 const basic_fbstring<E, T, A, S>& rhs) {
2547 return !(lhs == rhs); }
2549 template <typename E, class T, class A, class S>
2551 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2552 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2553 return !(lhs == rhs); }
2555 template <typename E, class T, class A, class S>
2557 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2558 const basic_fbstring<E, T, A, S>& rhs) {
2559 return lhs.compare(rhs) < 0; }
2561 template <typename E, class T, class A, class S>
2563 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2564 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2565 return lhs.compare(rhs) < 0; }
2567 template <typename E, class T, class A, class S>
2569 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2570 const basic_fbstring<E, T, A, S>& rhs) {
2571 return rhs.compare(lhs) > 0; }
2573 template <typename E, class T, class A, class S>
2575 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2576 const basic_fbstring<E, T, A, S>& rhs) {
2579 template <typename E, class T, class A, class S>
2581 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2582 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2585 template <typename E, class T, class A, class S>
2587 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2588 const basic_fbstring<E, T, A, S>& rhs) {
2591 template <typename E, class T, class A, class S>
2593 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2594 const basic_fbstring<E, T, A, S>& rhs) {
2595 return !(rhs < lhs); }
2597 template <typename E, class T, class A, class S>
2599 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2600 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2601 return !(rhs < lhs); }
2603 template <typename E, class T, class A, class S>
2605 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2606 const basic_fbstring<E, T, A, S>& rhs) {
2607 return !(rhs < lhs); }
2609 template <typename E, class T, class A, class S>
2611 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2612 const basic_fbstring<E, T, A, S>& rhs) {
2613 return !(lhs < rhs); }
2615 template <typename E, class T, class A, class S>
2617 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2618 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2619 return !(lhs < rhs); }
2621 template <typename E, class T, class A, class S>
2623 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2624 const basic_fbstring<E, T, A, S>& rhs) {
2625 return !(lhs < rhs);
2629 template <typename E, class T, class A, class S>
2630 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2634 // TODO: make this faster.
2635 template <typename E, class T, class A, class S>
2638 typename basic_fbstring<E, T, A, S>::value_type,
2639 typename basic_fbstring<E, T, A, S>::traits_type>&
2641 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2642 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2643 basic_fbstring<E, T, A, S>& str) {
2644 typename std::basic_istream<E, T>::sentry sentry(is);
2645 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2646 typename basic_fbstring<E, T, A, S>::traits_type>
2648 typedef typename __istream_type::ios_base __ios_base;
2649 size_t extracted = 0;
2650 auto err = __ios_base::goodbit;
2652 auto n = is.width();
2657 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2658 if (got == T::eof()) {
2659 err |= __ios_base::eofbit;
2667 got = is.rdbuf()->snextc();
2671 err |= __ios_base::failbit;
2679 template <typename E, class T, class A, class S>
2681 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2682 typename basic_fbstring<E, T, A, S>::traits_type>&
2684 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2685 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2686 const basic_fbstring<E, T, A, S>& str) {
2688 typename std::basic_ostream<
2689 typename basic_fbstring<E, T, A, S>::value_type,
2690 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2692 typedef std::ostreambuf_iterator<
2693 typename basic_fbstring<E, T, A, S>::value_type,
2694 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2695 size_t __len = str.size();
2697 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2698 if (__pad_and_output(_Ip(os),
2700 __left ? str.data() + __len : str.data(),
2703 os.fill()).failed()) {
2704 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2707 #elif defined(_MSC_VER)
2708 // MSVC doesn't define __ostream_insert
2709 os.write(str.data(), std::streamsize(str.size()));
2711 std::__ostream_insert(os, str.data(), str.size());
2716 template <typename E1, class T, class A, class S>
2717 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2718 basic_fbstring<E1, T, A, S>::npos;
2720 #ifndef _LIBSTDCXX_FBSTRING
2721 // basic_string compatibility routines
2723 template <typename E, class T, class A, class S>
2725 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2726 const std::string& rhs) {
2727 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2730 template <typename E, class T, class A, class S>
2732 bool operator==(const std::string& lhs,
2733 const basic_fbstring<E, T, A, S>& rhs) {
2737 template <typename E, class T, class A, class S>
2739 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2740 const std::string& rhs) {
2741 return !(lhs == rhs);
2744 template <typename E, class T, class A, class S>
2746 bool operator!=(const std::string& lhs,
2747 const basic_fbstring<E, T, A, S>& rhs) {
2748 return !(lhs == rhs);
2751 #if !defined(_LIBSTDCXX_FBSTRING)
2752 typedef basic_fbstring<char> fbstring;
2755 // fbstring is relocatable
2756 template <class T, class R, class A, class S>
2757 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2760 _GLIBCXX_END_NAMESPACE_VERSION
2763 } // namespace folly
2765 #ifndef _LIBSTDCXX_FBSTRING
2767 // Hash functions to make fbstring usable with e.g. hash_map
2769 // Handle interaction with different C++ standard libraries, which
2770 // expect these types to be in different namespaces.
2772 #define FOLLY_FBSTRING_HASH1(T) \
2774 struct hash< ::folly::basic_fbstring<T>> { \
2775 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2776 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2780 // The C++11 standard says that these four are defined
2781 #define FOLLY_FBSTRING_HASH \
2782 FOLLY_FBSTRING_HASH1(char) \
2783 FOLLY_FBSTRING_HASH1(char16_t) \
2784 FOLLY_FBSTRING_HASH1(char32_t) \
2785 FOLLY_FBSTRING_HASH1(wchar_t)
2793 #if FOLLY_HAVE_DEPRECATED_ASSOC
2794 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2795 namespace __gnu_cxx {
2799 } // namespace __gnu_cxx
2800 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2801 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2803 #undef FOLLY_FBSTRING_HASH
2804 #undef FOLLY_FBSTRING_HASH1
2806 #endif // _LIBSTDCXX_FBSTRING
2808 #pragma GCC diagnostic pop
2810 #undef FBSTRING_DISABLE_SSO
2811 #undef FBSTRING_SANITIZE_ADDRESS
2813 #undef FBSTRING_LIKELY
2814 #undef FBSTRING_UNLIKELY
2815 #undef FBSTRING_ASSERT