2 * Copyright 2017 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
26 #include <type_traits>
28 // This file appears in two locations: inside fbcode and in the
29 // libstdc++ source code (when embedding fbstring as std::string).
30 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
31 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
32 #ifdef _LIBSTDCXX_FBSTRING
34 #pragma GCC system_header
36 #include "basic_fbstring_malloc.h" // @manual
38 // When used as std::string replacement always disable assertions.
39 #define FBSTRING_ASSERT(expr) /* empty */
41 #else // !_LIBSTDCXX_FBSTRING
43 #include <folly/CppAttributes.h>
44 #include <folly/Portability.h>
46 // libc++ doesn't provide this header, nor does msvc
47 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
48 #include <bits/c++config.h>
57 #include <folly/Hash.h>
58 #include <folly/Malloc.h>
59 #include <folly/Traits.h>
60 #include <folly/portability/BitsFunctexcept.h>
62 // When used in folly, assertions are not disabled.
63 #define FBSTRING_ASSERT(expr) assert(expr)
67 // We defined these here rather than including Likely.h to avoid
68 // redefinition errors when fbstring is imported into libstdc++.
69 #if defined(__GNUC__) && __GNUC__ >= 4
70 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
71 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
73 #define FBSTRING_LIKELY(x) (x)
74 #define FBSTRING_UNLIKELY(x) (x)
78 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
79 FOLLY_GCC_DISABLE_WARNING("-Wshadow")
80 // GCC 4.9 has a false positive in setSmallSize (probably
81 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
82 // compile-time array bound checking.
83 FOLLY_GCC_DISABLE_WARNING("-Warray-bounds")
85 // FBString cannot use throw when replacing std::string, though it may still
88 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
90 #ifdef _LIBSTDCXX_FBSTRING
91 #define FOLLY_FBSTRING_BEGIN_NAMESPACE \
92 namespace std _GLIBCXX_VISIBILITY(default) { \
93 _GLIBCXX_BEGIN_NAMESPACE_VERSION
94 #define FOLLY_FBSTRING_END_NAMESPACE \
95 _GLIBCXX_END_NAMESPACE_VERSION \
98 #define FOLLY_FBSTRING_BEGIN_NAMESPACE namespace folly {
99 #define FOLLY_FBSTRING_END_NAMESPACE } // namespace folly
102 FOLLY_FBSTRING_BEGIN_NAMESPACE
104 #if defined(__clang__)
105 # if __has_feature(address_sanitizer)
106 # define FBSTRING_SANITIZE_ADDRESS
108 #elif defined (__GNUC__) && \
109 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
111 # define FBSTRING_SANITIZE_ADDRESS
114 // When compiling with ASan, always heap-allocate the string even if
115 // it would fit in-situ, so that ASan can detect access to the string
116 // buffer after it has been invalidated (destroyed, resized, etc.).
117 // Note that this flag doesn't remove support for in-situ strings, as
118 // that would break ABI-compatibility and wouldn't allow linking code
119 // compiled with this flag with code compiled without.
120 #ifdef FBSTRING_SANITIZE_ADDRESS
121 # define FBSTRING_DISABLE_SSO true
123 # define FBSTRING_DISABLE_SSO false
126 namespace fbstring_detail {
128 template <class InIt, class OutIt>
129 inline std::pair<InIt, OutIt> copy_n(
131 typename std::iterator_traits<InIt>::difference_type n,
133 for (; n != 0; --n, ++b, ++d) {
136 return std::make_pair(b, d);
139 template <class Pod, class T>
140 inline void podFill(Pod* b, Pod* e, T c) {
141 FBSTRING_ASSERT(b && e && b <= e);
142 constexpr auto kUseMemset = sizeof(T) == 1;
143 /* static */ if (kUseMemset) {
144 memset(b, c, size_t(e - b));
146 auto const ee = b + ((e - b) & ~7u);
147 for (; b != ee; b += 8) {
158 for (; b != e; ++b) {
165 * Lightly structured memcpy, simplifies copying PODs and introduces
166 * some asserts. Unfortunately using this function may cause
167 * measurable overhead (presumably because it adjusts from a begin/end
168 * convention to a pointer/size convention, so it does some extra
169 * arithmetic even though the caller might have done the inverse
170 * adaptation outside).
173 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
174 FBSTRING_ASSERT(b != nullptr);
175 FBSTRING_ASSERT(e != nullptr);
176 FBSTRING_ASSERT(d != nullptr);
177 FBSTRING_ASSERT(e >= b);
178 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
179 memcpy(d, b, (e - b) * sizeof(Pod));
183 * Lightly structured memmove, simplifies copying PODs and introduces
187 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
188 FBSTRING_ASSERT(e >= b);
189 memmove(d, b, (e - b) * sizeof(*b));
193 #if defined(__GNUC__) // Clang also defines __GNUC__
194 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
195 #elif defined(_MSC_VER)
196 # define FBSTRING_ALWAYS_INLINE __forceinline
198 # define FBSTRING_ALWAYS_INLINE inline
201 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
202 #if defined(__GNUC__) // Clang also defines __GNUC__
203 __builtin_unreachable();
204 #elif defined(_MSC_VER)
207 // Well, it's better than nothing.
212 } // namespace fbstring_detail
215 * Defines a special acquisition method for constructing fbstring
216 * objects. AcquireMallocatedString means that the user passes a
217 * pointer to a malloc-allocated string that the fbstring object will
220 enum class AcquireMallocatedString {};
223 * fbstring_core_model is a mock-up type that defines all required
224 * signatures of a fbstring core. The fbstring class itself uses such
225 * a core object to implement all of the numerous member functions
226 * required by the standard.
228 * If you want to define a new core, copy the definition below and
229 * implement the primitives. Then plug the core into basic_fbstring as
230 * a template argument.
232 template <class Char>
233 class fbstring_core_model {
235 fbstring_core_model();
236 fbstring_core_model(const fbstring_core_model &);
237 ~fbstring_core_model();
238 // Returns a pointer to string's buffer (currently only contiguous
239 // strings are supported). The pointer is guaranteed to be valid
240 // until the next call to a non-const member function.
241 const Char * data() const;
242 // Much like data(), except the string is prepared to support
243 // character-level changes. This call is a signal for
244 // e.g. reference-counted implementation to fork the data. The
245 // pointer is guaranteed to be valid until the next call to a
246 // non-const member function.
248 // Returns a pointer to string's buffer and guarantees that a
249 // readable '\0' lies right after the buffer. The pointer is
250 // guaranteed to be valid until the next call to a non-const member
252 const Char * c_str() const;
253 // Shrinks the string by delta characters. Asserts that delta <=
255 void shrink(size_t delta);
256 // Expands the string by delta characters (i.e. after this call
257 // size() will report the old size() plus delta) but without
258 // initializing the expanded region. The expanded region is
259 // zero-terminated. Returns a pointer to the memory to be
260 // initialized (the beginning of the expanded portion). The caller
261 // is expected to fill the expanded area appropriately.
262 // If expGrowth is true, exponential growth is guaranteed.
263 // It is not guaranteed not to reallocate even if size() + delta <
264 // capacity(), so all references to the buffer are invalidated.
265 Char* expandNoinit(size_t delta, bool expGrowth);
266 // Expands the string by one character and sets the last character
268 void push_back(Char c);
269 // Returns the string's size.
271 // Returns the string's capacity, i.e. maximum size that the string
272 // can grow to without reallocation. Note that for reference counted
273 // strings that's technically a lie - even assigning characters
274 // within the existing size would cause a reallocation.
275 size_t capacity() const;
276 // Returns true if the data underlying the string is actually shared
277 // across multiple strings (in a refcounted fashion).
278 bool isShared() const;
279 // Makes sure that at least minCapacity characters are available for
280 // the string without reallocation. For reference-counted strings,
281 // it should fork the data even if minCapacity < size().
282 void reserve(size_t minCapacity);
285 fbstring_core_model& operator=(const fbstring_core_model &);
290 * This is the core of the string. The code should work on 32- and
291 * 64-bit and both big- and little-endianan architectures with any
294 * The storage is selected as follows (assuming we store one-byte
295 * characters on a 64-bit machine): (a) "small" strings between 0 and
296 * 23 chars are stored in-situ without allocation (the rightmost byte
297 * stores the size); (b) "medium" strings from 24 through 254 chars
298 * are stored in malloc-allocated memory that is copied eagerly; (c)
299 * "large" strings of 255 chars and above are stored in a similar
300 * structure as medium arrays, except that the string is
301 * reference-counted and copied lazily. the reference count is
302 * allocated right before the character array.
304 * The discriminator between these three strategies sits in two
305 * bits of the rightmost char of the storage. If neither is set, then the
306 * string is small (and its length sits in the lower-order bits on
307 * little-endian or the high-order bits on big-endian of that
308 * rightmost character). If the MSb is set, the string is medium width.
309 * If the second MSb is set, then the string is large. On little-endian,
310 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
311 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
312 * and big-endian fbstring_core equivalent with merely different ops used
313 * to extract capacity/category.
315 template <class Char> class fbstring_core {
317 // It's MSVC, so we just have to guess ... and allow an override
319 # ifdef FOLLY_ENDIAN_BE
320 static constexpr auto kIsLittleEndian = false;
322 static constexpr auto kIsLittleEndian = true;
325 static constexpr auto kIsLittleEndian =
326 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
329 fbstring_core() noexcept { reset(); }
331 fbstring_core(const fbstring_core & rhs) {
332 FBSTRING_ASSERT(&rhs != this);
333 switch (rhs.category()) {
334 case Category::isSmall:
337 case Category::isMedium:
340 case Category::isLarge:
344 fbstring_detail::assume_unreachable();
346 FBSTRING_ASSERT(size() == rhs.size());
347 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
350 fbstring_core(fbstring_core&& goner) noexcept {
353 // Clean goner's carcass
357 fbstring_core(const Char *const data,
359 bool disableSSO = FBSTRING_DISABLE_SSO) {
360 if (!disableSSO && size <= maxSmallSize) {
361 initSmall(data, size);
362 } else if (size <= maxMediumSize) {
363 initMedium(data, size);
365 initLarge(data, size);
367 FBSTRING_ASSERT(this->size() == size);
369 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
372 ~fbstring_core() noexcept {
373 if (category() == Category::isSmall) {
376 destroyMediumLarge();
379 // Snatches a previously mallocated string. The parameter "size"
380 // is the size of the string, and the parameter "allocatedSize"
381 // is the size of the mallocated block. The string must be
382 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
384 // So if you want a 2-character string, pass malloc(3) as "data",
385 // pass 2 as "size", and pass 3 as "allocatedSize".
386 fbstring_core(Char * const data,
388 const size_t allocatedSize,
389 AcquireMallocatedString) {
391 FBSTRING_ASSERT(allocatedSize >= size + 1);
392 FBSTRING_ASSERT(data[size] == '\0');
393 // Use the medium string storage
396 // Don't forget about null terminator
397 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
399 // No need for the memory
405 // swap below doesn't test whether &rhs == this (and instead
406 // potentially does extra work) on the premise that the rarity of
407 // that situation actually makes the check more expensive than is
409 void swap(fbstring_core & rhs) {
415 // In C++11 data() and c_str() are 100% equivalent.
416 const Char * data() const {
420 Char* mutableData() {
421 switch (category()) {
422 case Category::isSmall:
424 case Category::isMedium:
426 case Category::isLarge:
427 return mutableDataLarge();
429 fbstring_detail::assume_unreachable();
432 const Char* c_str() const {
433 const Char* ptr = ml_.data_;
434 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
435 ptr = (category() == Category::isSmall) ? small_ : ptr;
439 void shrink(const size_t delta) {
440 if (category() == Category::isSmall) {
442 } else if (category() == Category::isMedium ||
443 RefCounted::refs(ml_.data_) == 1) {
450 FOLLY_MALLOC_NOINLINE
451 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
452 switch (category()) {
453 case Category::isSmall:
454 reserveSmall(minCapacity, disableSSO);
456 case Category::isMedium:
457 reserveMedium(minCapacity);
459 case Category::isLarge:
460 reserveLarge(minCapacity);
463 fbstring_detail::assume_unreachable();
465 FBSTRING_ASSERT(capacity() >= minCapacity);
470 bool expGrowth = false,
471 bool disableSSO = FBSTRING_DISABLE_SSO);
473 void push_back(Char c) {
474 *expandNoinit(1, /* expGrowth = */ true) = c;
477 size_t size() const {
478 size_t ret = ml_.size_;
479 /* static */ if (kIsLittleEndian) {
480 // We can save a couple instructions, because the category is
481 // small iff the last char, as unsigned, is <= maxSmallSize.
482 typedef typename std::make_unsigned<Char>::type UChar;
483 auto maybeSmallSize = size_t(maxSmallSize) -
484 size_t(static_cast<UChar>(small_[maxSmallSize]));
485 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
486 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
488 ret = (category() == Category::isSmall) ? smallSize() : ret;
493 size_t capacity() const {
494 switch (category()) {
495 case Category::isSmall:
497 case Category::isLarge:
498 // For large-sized strings, a multi-referenced chunk has no
499 // available capacity. This is because any attempt to append
500 // data would trigger a new allocation.
501 if (RefCounted::refs(ml_.data_) > 1) {
508 return ml_.capacity();
511 bool isShared() const {
512 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
517 fbstring_core & operator=(const fbstring_core & rhs);
523 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
524 auto const c = category();
525 FBSTRING_ASSERT(c != Category::isSmall);
526 if (c == Category::isMedium) {
529 RefCounted::decrementRefs(ml_.data_);
534 std::atomic<size_t> refCount_;
537 constexpr static size_t getDataOffset() {
538 return offsetof(RefCounted, data_);
541 static RefCounted * fromData(Char * p) {
542 return static_cast<RefCounted*>(static_cast<void*>(
543 static_cast<unsigned char*>(static_cast<void*>(p)) -
547 static size_t refs(Char * p) {
548 return fromData(p)->refCount_.load(std::memory_order_acquire);
551 static void incrementRefs(Char * p) {
552 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
555 static void decrementRefs(Char * p) {
556 auto const dis = fromData(p);
557 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
558 FBSTRING_ASSERT(oldcnt > 0);
564 static RefCounted * create(size_t * size) {
565 const size_t allocSize =
566 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
567 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
568 result->refCount_.store(1, std::memory_order_release);
569 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
573 static RefCounted * create(const Char * data, size_t * size) {
574 const size_t effectiveSize = *size;
575 auto result = create(size);
576 if (FBSTRING_LIKELY(effectiveSize > 0)) {
577 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
582 static RefCounted * reallocate(Char *const data,
583 const size_t currentSize,
584 const size_t currentCapacity,
585 size_t * newCapacity) {
586 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
587 const size_t allocNewCapacity =
588 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
589 auto const dis = fromData(data);
590 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
591 auto result = static_cast<RefCounted*>(smartRealloc(
593 getDataOffset() + (currentSize + 1) * sizeof(Char),
594 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
596 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
597 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
602 typedef uint8_t category_type;
604 enum class Category : category_type {
606 isMedium = kIsLittleEndian ? 0x80 : 0x2,
607 isLarge = kIsLittleEndian ? 0x40 : 0x1,
610 Category category() const {
611 // works for both big-endian and little-endian
612 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
620 size_t capacity() const {
621 return kIsLittleEndian
622 ? capacity_ & capacityExtractMask
626 void setCapacity(size_t cap, Category cat) {
627 capacity_ = kIsLittleEndian
628 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
629 : (cap << 2) | static_cast<size_t>(cat);
634 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
635 Char small_[sizeof(MediumLarge) / sizeof(Char)];
639 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
640 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
641 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
642 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
643 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
644 constexpr static size_t capacityExtractMask = kIsLittleEndian
645 ? ~(size_t(categoryExtractMask) << kCategoryShift)
648 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
649 "Corrupt memory layout for fbstring.");
651 size_t smallSize() const {
652 FBSTRING_ASSERT(category() == Category::isSmall);
653 constexpr auto shift = kIsLittleEndian ? 0 : 2;
654 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
655 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
656 return static_cast<size_t>(maxSmallSize) - smallShifted;
659 void setSmallSize(size_t s) {
660 // Warning: this should work with uninitialized strings too,
661 // so don't assume anything about the previous value of
662 // small_[maxSmallSize].
663 FBSTRING_ASSERT(s <= maxSmallSize);
664 constexpr auto shift = kIsLittleEndian ? 0 : 2;
665 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
667 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
670 void copySmall(const fbstring_core&);
671 void copyMedium(const fbstring_core&);
672 void copyLarge(const fbstring_core&);
674 void initSmall(const Char* data, size_t size);
675 void initMedium(const Char* data, size_t size);
676 void initLarge(const Char* data, size_t size);
678 void reserveSmall(size_t minCapacity, bool disableSSO);
679 void reserveMedium(size_t minCapacity);
680 void reserveLarge(size_t minCapacity);
682 void shrinkSmall(size_t delta);
683 void shrinkMedium(size_t delta);
684 void shrinkLarge(size_t delta);
686 void unshare(size_t minCapacity = 0);
687 Char* mutableDataLarge();
690 template <class Char>
691 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
692 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
694 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
695 "fbstring layout failure");
697 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
698 "fbstring layout failure");
699 // Just write the whole thing, don't look at details. In
700 // particular we need to copy capacity anyway because we want
701 // to set the size (don't forget that the last character,
702 // which stores a short string's length, is shared with the
703 // ml_.capacity field).
706 category() == Category::isSmall && this->size() == rhs.size());
709 template <class Char>
710 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
711 const fbstring_core& rhs) {
712 // Medium strings are copied eagerly. Don't forget to allocate
713 // one extra Char for the null terminator.
714 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
715 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
716 // Also copies terminator.
717 fbstring_detail::podCopy(
718 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
719 ml_.size_ = rhs.ml_.size_;
720 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
721 FBSTRING_ASSERT(category() == Category::isMedium);
724 template <class Char>
725 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
726 const fbstring_core& rhs) {
727 // Large strings are just refcounted
729 RefCounted::incrementRefs(ml_.data_);
730 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
733 // Small strings are bitblitted
734 template <class Char>
735 inline void fbstring_core<Char>::initSmall(
736 const Char* const data, const size_t size) {
737 // Layout is: Char* data_, size_t size_, size_t capacity_
739 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
740 "fbstring has unexpected size");
742 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
743 // sizeof(size_t) must be a power of 2
745 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
746 "fbstring size assumption violation");
748 // If data is aligned, use fast word-wise copying. Otherwise,
749 // use conservative memcpy.
750 // The word-wise path reads bytes which are outside the range of
751 // the string, and makes ASan unhappy, so we disable it when
752 // compiling with ASan.
753 #ifndef FBSTRING_SANITIZE_ADDRESS
754 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
755 const size_t byteSize = size * sizeof(Char);
756 constexpr size_t wordWidth = sizeof(size_t);
757 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
759 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
762 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
765 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
774 fbstring_detail::podCopy(data, data + size, small_);
780 template <class Char>
781 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
782 const Char* const data, const size_t size) {
783 // Medium strings are allocated normally. Don't forget to
784 // allocate one extra Char for the terminating null.
785 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
786 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
787 if (FBSTRING_LIKELY(size > 0)) {
788 fbstring_detail::podCopy(data, data + size, ml_.data_);
791 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
792 ml_.data_[size] = '\0';
795 template <class Char>
796 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
797 const Char* const data, const size_t size) {
798 // Large strings are allocated differently
799 size_t effectiveCapacity = size;
800 auto const newRC = RefCounted::create(data, &effectiveCapacity);
801 ml_.data_ = newRC->data_;
803 ml_.setCapacity(effectiveCapacity, Category::isLarge);
804 ml_.data_[size] = '\0';
807 template <class Char>
808 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
809 size_t minCapacity) {
810 FBSTRING_ASSERT(category() == Category::isLarge);
811 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
812 auto const newRC = RefCounted::create(&effectiveCapacity);
813 // If this fails, someone placed the wrong capacity in an
815 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
816 // Also copies terminator.
817 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
818 RefCounted::decrementRefs(ml_.data_);
819 ml_.data_ = newRC->data_;
820 ml_.setCapacity(effectiveCapacity, Category::isLarge);
821 // size_ remains unchanged.
824 template <class Char>
825 inline Char* fbstring_core<Char>::mutableDataLarge() {
826 FBSTRING_ASSERT(category() == Category::isLarge);
827 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
833 template <class Char>
834 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
835 size_t minCapacity) {
836 FBSTRING_ASSERT(category() == Category::isLarge);
837 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
838 // We must make it unique regardless; in-place reallocation is
839 // useless if the string is shared. In order to not surprise
840 // people, reserve the new block at current capacity or
841 // more. That way, a string's capacity never shrinks after a
843 unshare(minCapacity);
845 // String is not shared, so let's try to realloc (if needed)
846 if (minCapacity > ml_.capacity()) {
847 // Asking for more memory
848 auto const newRC = RefCounted::reallocate(
849 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
850 ml_.data_ = newRC->data_;
851 ml_.setCapacity(minCapacity, Category::isLarge);
853 FBSTRING_ASSERT(capacity() >= minCapacity);
857 template <class Char>
858 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
859 const size_t minCapacity) {
860 FBSTRING_ASSERT(category() == Category::isMedium);
861 // String is not shared
862 if (minCapacity <= ml_.capacity()) {
863 return; // nothing to do, there's enough room
865 if (minCapacity <= maxMediumSize) {
866 // Keep the string at medium size. Don't forget to allocate
867 // one extra Char for the terminating null.
868 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
869 // Also copies terminator.
870 ml_.data_ = static_cast<Char*>(smartRealloc(
872 (ml_.size_ + 1) * sizeof(Char),
873 (ml_.capacity() + 1) * sizeof(Char),
875 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
877 // Conversion from medium to large string
878 fbstring_core nascent;
879 // Will recurse to another branch of this function
880 nascent.reserve(minCapacity);
881 nascent.ml_.size_ = ml_.size_;
882 // Also copies terminator.
883 fbstring_detail::podCopy(
884 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
886 FBSTRING_ASSERT(capacity() >= minCapacity);
890 template <class Char>
891 FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
892 size_t minCapacity, const bool disableSSO) {
893 FBSTRING_ASSERT(category() == Category::isSmall);
894 if (!disableSSO && minCapacity <= maxSmallSize) {
896 // Nothing to do, everything stays put
897 } else if (minCapacity <= maxMediumSize) {
899 // Don't forget to allocate one extra Char for the terminating null
900 auto const allocSizeBytes =
901 goodMallocSize((1 + minCapacity) * sizeof(Char));
902 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
903 auto const size = smallSize();
904 // Also copies terminator.
905 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
908 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
911 auto const newRC = RefCounted::create(&minCapacity);
912 auto const size = smallSize();
913 // Also copies terminator.
914 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
915 ml_.data_ = newRC->data_;
917 ml_.setCapacity(minCapacity, Category::isLarge);
918 FBSTRING_ASSERT(capacity() >= minCapacity);
922 template <class Char>
923 inline Char* fbstring_core<Char>::expandNoinit(
925 bool expGrowth, /* = false */
926 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
927 // Strategy is simple: make room, then change size
928 FBSTRING_ASSERT(capacity() >= size());
930 if (category() == Category::isSmall) {
933 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
938 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
942 if (FBSTRING_UNLIKELY(newSz > capacity())) {
943 // ensures not shared
944 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
947 FBSTRING_ASSERT(capacity() >= newSz);
948 // Category can't be small - we took care of that above
950 category() == Category::isMedium || category() == Category::isLarge);
952 ml_.data_[newSz] = '\0';
953 FBSTRING_ASSERT(size() == newSz);
954 return ml_.data_ + sz;
957 template <class Char>
958 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
959 // Check for underflow
960 FBSTRING_ASSERT(delta <= smallSize());
961 setSmallSize(smallSize() - delta);
964 template <class Char>
965 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
966 // Medium strings and unique large strings need no special
968 FBSTRING_ASSERT(ml_.size_ >= delta);
970 ml_.data_[ml_.size_] = '\0';
973 template <class Char>
974 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
975 FBSTRING_ASSERT(ml_.size_ >= delta);
976 // Shared large string, must make unique. This is because of the
977 // durn terminator must be written, which may trample the shared
980 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
982 // No need to write the terminator.
985 #ifndef _LIBSTDCXX_FBSTRING
987 * Dummy fbstring core that uses an actual std::string. This doesn't
988 * make any sense - it's just for testing purposes.
990 template <class Char>
991 class dummy_fbstring_core {
993 dummy_fbstring_core() {
995 dummy_fbstring_core(const dummy_fbstring_core& another)
996 : backend_(another.backend_) {
998 dummy_fbstring_core(const Char * s, size_t n)
1001 void swap(dummy_fbstring_core & rhs) {
1002 backend_.swap(rhs.backend_);
1004 const Char * data() const {
1005 return backend_.data();
1007 Char* mutableData() {
1008 return const_cast<Char*>(backend_.data());
1010 void shrink(size_t delta) {
1011 FBSTRING_ASSERT(delta <= size());
1012 backend_.resize(size() - delta);
1014 Char* expandNoinit(size_t delta) {
1015 auto const sz = size();
1016 backend_.resize(size() + delta);
1017 return backend_.data() + sz;
1019 void push_back(Char c) {
1020 backend_.push_back(c);
1022 size_t size() const {
1023 return backend_.size();
1025 size_t capacity() const {
1026 return backend_.capacity();
1028 bool isShared() const {
1031 void reserve(size_t minCapacity) {
1032 backend_.reserve(minCapacity);
1036 std::basic_string<Char> backend_;
1038 #endif // !_LIBSTDCXX_FBSTRING
1041 * This is the basic_string replacement. For conformity,
1042 * basic_fbstring takes the same template parameters, plus the last
1043 * one which is the core.
1045 #ifdef _LIBSTDCXX_FBSTRING
1046 template <typename E, class T, class A, class Storage>
1048 template <typename E,
1049 class T = std::char_traits<E>,
1050 class A = std::allocator<E>,
1051 class Storage = fbstring_core<E> >
1053 class basic_fbstring {
1054 static void enforce(
1056 void (*throw_exc)(const char*),
1063 bool isSane() const {
1066 empty() == (size() == 0) &&
1067 empty() == (begin() == end()) &&
1068 size() <= max_size() &&
1069 capacity() <= max_size() &&
1070 size() <= capacity() &&
1071 begin()[size()] == '\0';
1075 Invariant& operator=(const Invariant&) = delete;
1076 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1077 FBSTRING_ASSERT(s_.isSane());
1079 ~Invariant() noexcept {
1080 FBSTRING_ASSERT(s_.isSane());
1084 const basic_fbstring& s_;
1089 typedef T traits_type;
1090 typedef typename traits_type::char_type value_type;
1091 typedef A allocator_type;
1092 typedef typename A::size_type size_type;
1093 typedef typename A::difference_type difference_type;
1095 typedef typename A::reference reference;
1096 typedef typename A::const_reference const_reference;
1097 typedef typename A::pointer pointer;
1098 typedef typename A::const_pointer const_pointer;
1100 typedef E* iterator;
1101 typedef const E* const_iterator;
1102 typedef std::reverse_iterator<iterator
1103 #ifdef NO_ITERATOR_TRAITS
1107 typedef std::reverse_iterator<const_iterator
1108 #ifdef NO_ITERATOR_TRAITS
1111 > const_reverse_iterator;
1113 static constexpr size_type npos = size_type(-1);
1114 typedef std::true_type IsRelocatable;
1117 static void procrustes(size_type& n, size_type nmax) {
1123 static size_type traitsLength(const value_type* s);
1126 // C++11 21.4.2 construct/copy/destroy
1128 // Note: while the following two constructors can be (and previously were)
1129 // collapsed into one constructor written this way:
1131 // explicit basic_fbstring(const A& a = A()) noexcept { }
1133 // This can cause Clang (at least version 3.7) to fail with the error:
1134 // "chosen constructor is explicit in copy-initialization ...
1135 // in implicit initialization of field '(x)' with omitted initializer"
1137 // if used in a struct which is default-initialized. Hence the split into
1138 // these two separate constructors.
1140 basic_fbstring() noexcept : basic_fbstring(A()) {
1143 explicit basic_fbstring(const A&) noexcept {
1146 basic_fbstring(const basic_fbstring& str)
1147 : store_(str.store_) {
1151 basic_fbstring(basic_fbstring&& goner) noexcept
1152 : store_(std::move(goner.store_)) {
1155 #ifndef _LIBSTDCXX_FBSTRING
1156 // This is defined for compatibility with std::string
1157 template <typename A2>
1158 /* implicit */ basic_fbstring(const std::basic_string<E, T, A2>& str)
1159 : store_(str.data(), str.size()) {}
1162 basic_fbstring(const basic_fbstring& str,
1165 const A& /* a */ = A()) {
1166 assign(str, pos, n);
1169 FOLLY_MALLOC_NOINLINE
1170 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1171 : store_(s, traitsLength(s)) {}
1173 FOLLY_MALLOC_NOINLINE
1174 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1178 FOLLY_MALLOC_NOINLINE
1179 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1180 auto const pData = store_.expandNoinit(n);
1181 fbstring_detail::podFill(pData, pData + n, c);
1184 template <class InIt>
1185 FOLLY_MALLOC_NOINLINE basic_fbstring(
1188 typename std::enable_if<
1189 !std::is_same<InIt, value_type*>::value,
1190 const A>::type& /*a*/ = A()) {
1194 // Specialization for const char*, const char*
1195 FOLLY_MALLOC_NOINLINE
1196 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1197 : store_(b, size_type(e - b)) {
1200 // Nonstandard constructor
1201 basic_fbstring(value_type *s, size_type n, size_type c,
1202 AcquireMallocatedString a)
1203 : store_(s, n, c, a) {
1206 // Construction from initialization list
1207 FOLLY_MALLOC_NOINLINE
1208 basic_fbstring(std::initializer_list<value_type> il) {
1209 assign(il.begin(), il.end());
1212 ~basic_fbstring() noexcept {}
1214 basic_fbstring& operator=(const basic_fbstring& lhs);
1217 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1219 #ifndef _LIBSTDCXX_FBSTRING
1220 // Compatibility with std::string
1221 template <typename A2>
1222 basic_fbstring& operator=(const std::basic_string<E, T, A2>& rhs) {
1223 return assign(rhs.data(), rhs.size());
1226 // Compatibility with std::string
1227 std::basic_string<E, T, A> toStdString() const {
1228 return std::basic_string<E, T, A>(data(), size());
1231 // A lot of code in fbcode still uses this method, so keep it here for now.
1232 const basic_fbstring& toStdString() const {
1237 basic_fbstring& operator=(const value_type* s) {
1241 // This actually goes directly against the C++ spec, but the
1242 // value_type overload is dangerous, so we're explicitly deleting
1243 // any overloads of operator= that could implicitly convert to
1245 // Note that we do need to explicitly specify the template types because
1246 // otherwise MSVC 2017 will aggressively pre-resolve value_type to
1247 // traits_type::char_type, which won't compare as equal when determining
1248 // which overload the implementation is referring to.
1249 // Also note that MSVC 2015 Update 3 requires us to explicitly specify the
1250 // namespace in-which to search for basic_fbstring, otherwise it tries to
1251 // look for basic_fbstring::basic_fbstring, which is just plain wrong.
1252 template <typename TP>
1253 typename std::enable_if<
1255 typename std::decay<TP>::type,
1256 typename folly::basic_fbstring<E, T, A, Storage>::value_type>::value,
1257 basic_fbstring<E, T, A, Storage>&>::type
1260 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1261 return assign(il.begin(), il.end());
1264 // C++11 21.4.3 iterators:
1266 return store_.mutableData();
1269 const_iterator begin() const {
1270 return store_.data();
1273 const_iterator cbegin() const {
1278 return store_.mutableData() + store_.size();
1281 const_iterator end() const {
1282 return store_.data() + store_.size();
1285 const_iterator cend() const { return end(); }
1287 reverse_iterator rbegin() {
1288 return reverse_iterator(end());
1291 const_reverse_iterator rbegin() const {
1292 return const_reverse_iterator(end());
1295 const_reverse_iterator crbegin() const { return rbegin(); }
1297 reverse_iterator rend() {
1298 return reverse_iterator(begin());
1301 const_reverse_iterator rend() const {
1302 return const_reverse_iterator(begin());
1305 const_reverse_iterator crend() const { return rend(); }
1308 // C++11 21.4.5, element access:
1309 const value_type& front() const { return *begin(); }
1310 const value_type& back() const {
1311 FBSTRING_ASSERT(!empty());
1312 // Should be begin()[size() - 1], but that branches twice
1313 return *(end() - 1);
1315 value_type& front() { return *begin(); }
1316 value_type& back() {
1317 FBSTRING_ASSERT(!empty());
1318 // Should be begin()[size() - 1], but that branches twice
1319 return *(end() - 1);
1322 FBSTRING_ASSERT(!empty());
1326 // C++11 21.4.4 capacity:
1327 size_type size() const { return store_.size(); }
1329 size_type length() const { return size(); }
1331 size_type max_size() const {
1332 return std::numeric_limits<size_type>::max();
1335 void resize(size_type n, value_type c = value_type());
1337 size_type capacity() const { return store_.capacity(); }
1339 void reserve(size_type res_arg = 0) {
1340 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1341 store_.reserve(res_arg);
1344 void shrink_to_fit() {
1345 // Shrink only if slack memory is sufficiently large
1346 if (capacity() < size() * 3 / 2) {
1349 basic_fbstring(cbegin(), cend()).swap(*this);
1352 void clear() { resize(0); }
1354 bool empty() const { return size() == 0; }
1356 // C++11 21.4.5 element access:
1357 const_reference operator[](size_type pos) const {
1358 return *(begin() + pos);
1361 reference operator[](size_type pos) {
1362 return *(begin() + pos);
1365 const_reference at(size_type n) const {
1366 enforce(n <= size(), std::__throw_out_of_range, "");
1370 reference at(size_type n) {
1371 enforce(n < size(), std::__throw_out_of_range, "");
1375 // C++11 21.4.6 modifiers:
1376 basic_fbstring& operator+=(const basic_fbstring& str) {
1380 basic_fbstring& operator+=(const value_type* s) {
1384 basic_fbstring& operator+=(const value_type c) {
1389 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1394 basic_fbstring& append(const basic_fbstring& str);
1397 append(const basic_fbstring& str, const size_type pos, size_type n);
1399 basic_fbstring& append(const value_type* s, size_type n);
1401 basic_fbstring& append(const value_type* s) {
1402 return append(s, traitsLength(s));
1405 basic_fbstring& append(size_type n, value_type c);
1407 template<class InputIterator>
1408 basic_fbstring& append(InputIterator first, InputIterator last) {
1409 insert(end(), first, last);
1413 basic_fbstring& append(std::initializer_list<value_type> il) {
1414 return append(il.begin(), il.end());
1417 void push_back(const value_type c) { // primitive
1418 store_.push_back(c);
1421 basic_fbstring& assign(const basic_fbstring& str) {
1422 if (&str == this) return *this;
1423 return assign(str.data(), str.size());
1426 basic_fbstring& assign(basic_fbstring&& str) {
1427 return *this = std::move(str);
1431 assign(const basic_fbstring& str, const size_type pos, size_type n);
1433 basic_fbstring& assign(const value_type* s, const size_type n);
1435 basic_fbstring& assign(const value_type* s) {
1436 return assign(s, traitsLength(s));
1439 basic_fbstring& assign(std::initializer_list<value_type> il) {
1440 return assign(il.begin(), il.end());
1443 template <class ItOrLength, class ItOrChar>
1444 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1445 return replace(begin(), end(), first_or_n, last_or_c);
1448 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1449 return insert(pos1, str.data(), str.size());
1452 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1453 size_type pos2, size_type n) {
1454 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1455 procrustes(n, str.length() - pos2);
1456 return insert(pos1, str.data() + pos2, n);
1459 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1460 enforce(pos <= length(), std::__throw_out_of_range, "");
1461 insert(begin() + pos, s, s + n);
1465 basic_fbstring& insert(size_type pos, const value_type* s) {
1466 return insert(pos, s, traitsLength(s));
1469 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1470 enforce(pos <= length(), std::__throw_out_of_range, "");
1471 insert(begin() + pos, n, c);
1475 iterator insert(const_iterator p, const value_type c) {
1476 const size_type pos = p - cbegin();
1478 return begin() + pos;
1481 #ifndef _LIBSTDCXX_FBSTRING
1483 typedef std::basic_istream<value_type, traits_type> istream_type;
1484 istream_type& getlineImpl(istream_type& is, value_type delim);
1487 friend inline istream_type& getline(istream_type& is,
1488 basic_fbstring& str,
1490 return str.getlineImpl(is, delim);
1493 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1494 return getline(is, str, '\n');
1500 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1502 template <class InputIter>
1504 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1506 template <class FwdIterator>
1507 iterator insertImpl(
1511 std::forward_iterator_tag);
1513 template <class InputIterator>
1514 iterator insertImpl(
1518 std::input_iterator_tag);
1521 template <class ItOrLength, class ItOrChar>
1522 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1523 using Sel = std::integral_constant<
1525 std::numeric_limits<ItOrLength>::is_specialized>;
1526 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1529 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1530 return insert(p, il.begin(), il.end());
1533 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1534 Invariant checker(*this);
1536 enforce(pos <= length(), std::__throw_out_of_range, "");
1537 procrustes(n, length() - pos);
1538 std::copy(begin() + pos + n, end(), begin() + pos);
1539 resize(length() - n);
1543 iterator erase(iterator position) {
1544 const size_type pos(position - begin());
1545 enforce(pos <= size(), std::__throw_out_of_range, "");
1547 return begin() + pos;
1550 iterator erase(iterator first, iterator last) {
1551 const size_type pos(first - begin());
1552 erase(pos, last - first);
1553 return begin() + pos;
1556 // Replaces at most n1 chars of *this, starting with pos1 with the
1558 basic_fbstring& replace(size_type pos1, size_type n1,
1559 const basic_fbstring& str) {
1560 return replace(pos1, n1, str.data(), str.size());
1563 // Replaces at most n1 chars of *this, starting with pos1,
1564 // with at most n2 chars of str starting with pos2
1565 basic_fbstring& replace(size_type pos1, size_type n1,
1566 const basic_fbstring& str,
1567 size_type pos2, size_type n2) {
1568 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1569 return replace(pos1, n1, str.data() + pos2,
1570 std::min(n2, str.size() - pos2));
1573 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1574 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1575 return replace(pos, n1, s, traitsLength(s));
1578 // Replaces at most n1 chars of *this, starting with pos, with n2
1581 // consolidated with
1583 // Replaces at most n1 chars of *this, starting with pos, with at
1584 // most n2 chars of str. str must have at least n2 chars.
1585 template <class StrOrLength, class NumOrChar>
1586 basic_fbstring& replace(size_type pos, size_type n1,
1587 StrOrLength s_or_n2, NumOrChar n_or_c) {
1588 Invariant checker(*this);
1590 enforce(pos <= size(), std::__throw_out_of_range, "");
1591 procrustes(n1, length() - pos);
1592 const iterator b = begin() + pos;
1593 return replace(b, b + n1, s_or_n2, n_or_c);
1596 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1597 return replace(i1, i2, str.data(), str.length());
1600 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1601 return replace(i1, i2, s, traitsLength(s));
1605 basic_fbstring& replaceImplDiscr(
1608 const value_type* s,
1610 std::integral_constant<int, 2>);
1612 basic_fbstring& replaceImplDiscr(
1617 std::integral_constant<int, 1>);
1619 template <class InputIter>
1620 basic_fbstring& replaceImplDiscr(
1625 std::integral_constant<int, 0>);
1628 template <class FwdIterator>
1629 bool replaceAliased(iterator /* i1 */,
1631 FwdIterator /* s1 */,
1632 FwdIterator /* s2 */,
1637 template <class FwdIterator>
1638 bool replaceAliased(
1645 template <class FwdIterator>
1651 std::forward_iterator_tag);
1653 template <class InputIterator>
1659 std::input_iterator_tag);
1662 template <class T1, class T2>
1663 basic_fbstring& replace(iterator i1, iterator i2,
1664 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1665 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1666 num2 = std::numeric_limits<T2>::is_specialized;
1668 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1669 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1672 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1673 enforce(pos <= size(), std::__throw_out_of_range, "");
1674 procrustes(n, size() - pos);
1677 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1682 void swap(basic_fbstring& rhs) {
1683 store_.swap(rhs.store_);
1686 const value_type* c_str() const {
1687 return store_.c_str();
1690 const value_type* data() const { return c_str(); }
1692 allocator_type get_allocator() const {
1693 return allocator_type();
1696 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1697 return find(str.data(), pos, str.length());
1700 size_type find(const value_type* needle, size_type pos, size_type nsize)
1703 size_type find(const value_type* s, size_type pos = 0) const {
1704 return find(s, pos, traitsLength(s));
1707 size_type find (value_type c, size_type pos = 0) const {
1708 return find(&c, pos, 1);
1711 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1712 return rfind(str.data(), pos, str.length());
1715 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1717 size_type rfind(const value_type* s, size_type pos = npos) const {
1718 return rfind(s, pos, traitsLength(s));
1721 size_type rfind(value_type c, size_type pos = npos) const {
1722 return rfind(&c, pos, 1);
1725 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1726 return find_first_of(str.data(), pos, str.length());
1729 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1732 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1733 return find_first_of(s, pos, traitsLength(s));
1736 size_type find_first_of(value_type c, size_type pos = 0) const {
1737 return find_first_of(&c, pos, 1);
1740 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1742 return find_last_of(str.data(), pos, str.length());
1745 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1747 size_type find_last_of (const value_type* s,
1748 size_type pos = npos) const {
1749 return find_last_of(s, pos, traitsLength(s));
1752 size_type find_last_of (value_type c, size_type pos = npos) const {
1753 return find_last_of(&c, pos, 1);
1756 size_type find_first_not_of(const basic_fbstring& str,
1757 size_type pos = 0) const {
1758 return find_first_not_of(str.data(), pos, str.size());
1761 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1764 size_type find_first_not_of(const value_type* s,
1765 size_type pos = 0) const {
1766 return find_first_not_of(s, pos, traitsLength(s));
1769 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1770 return find_first_not_of(&c, pos, 1);
1773 size_type find_last_not_of(const basic_fbstring& str,
1774 size_type pos = npos) const {
1775 return find_last_not_of(str.data(), pos, str.length());
1778 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1781 size_type find_last_not_of(const value_type* s,
1782 size_type pos = npos) const {
1783 return find_last_not_of(s, pos, traitsLength(s));
1786 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1787 return find_last_not_of(&c, pos, 1);
1790 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1791 enforce(pos <= size(), std::__throw_out_of_range, "");
1792 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1795 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1796 enforce(pos <= size(), std::__throw_out_of_range, "");
1801 return std::move(*this);
1804 int compare(const basic_fbstring& str) const {
1805 // FIX due to Goncalo N M de Carvalho July 18, 2005
1806 return compare(0, size(), str);
1809 int compare(size_type pos1, size_type n1,
1810 const basic_fbstring& str) const {
1811 return compare(pos1, n1, str.data(), str.size());
1814 int compare(size_type pos1, size_type n1,
1815 const value_type* s) const {
1816 return compare(pos1, n1, s, traitsLength(s));
1819 int compare(size_type pos1, size_type n1,
1820 const value_type* s, size_type n2) const {
1821 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1822 procrustes(n1, size() - pos1);
1823 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1824 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1825 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1828 int compare(size_type pos1, size_type n1,
1829 const basic_fbstring& str,
1830 size_type pos2, size_type n2) const {
1831 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1832 return compare(pos1, n1, str.data() + pos2,
1833 std::min(n2, str.size() - pos2));
1836 // Code from Jean-Francois Bastien (03/26/2007)
1837 int compare(const value_type* s) const {
1838 // Could forward to compare(0, size(), s, traitsLength(s))
1839 // but that does two extra checks
1840 const size_type n1(size()), n2(traitsLength(s));
1841 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1842 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1850 template <typename E, class T, class A, class S>
1851 FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1852 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1853 return s ? traits_type::length(s)
1854 : (std::__throw_logic_error(
1855 "basic_fbstring: null pointer initializer not valid"),
1859 template <typename E, class T, class A, class S>
1860 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1861 const basic_fbstring& lhs) {
1862 Invariant checker(*this);
1864 if (FBSTRING_UNLIKELY(&lhs == this)) {
1868 return assign(lhs.data(), lhs.size());
1872 template <typename E, class T, class A, class S>
1873 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1874 basic_fbstring&& goner) noexcept {
1875 if (FBSTRING_UNLIKELY(&goner == this)) {
1876 // Compatibility with std::basic_string<>,
1877 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1880 // No need of this anymore
1881 this->~basic_fbstring();
1882 // Move the goner into this
1883 new (&store_) S(std::move(goner.store_));
1887 template <typename E, class T, class A, class S>
1888 template <typename TP>
1889 inline typename std::enable_if<
1891 typename std::decay<TP>::type,
1892 typename basic_fbstring<E, T, A, S>::value_type>::value,
1893 basic_fbstring<E, T, A, S>&>::type
1894 basic_fbstring<E, T, A, S>::operator=(TP c) {
1895 Invariant checker(*this);
1898 store_.expandNoinit(1);
1899 } else if (store_.isShared()) {
1900 basic_fbstring(1, c).swap(*this);
1903 store_.shrink(size() - 1);
1909 template <typename E, class T, class A, class S>
1910 inline void basic_fbstring<E, T, A, S>::resize(
1911 const size_type n, const value_type c /*= value_type()*/) {
1912 Invariant checker(*this);
1914 auto size = this->size();
1916 store_.shrink(size - n);
1918 auto const delta = n - size;
1919 auto pData = store_.expandNoinit(delta);
1920 fbstring_detail::podFill(pData, pData + delta, c);
1922 FBSTRING_ASSERT(this->size() == n);
1925 template <typename E, class T, class A, class S>
1926 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1927 const basic_fbstring& str) {
1929 auto desiredSize = size() + str.size();
1931 append(str.data(), str.size());
1932 FBSTRING_ASSERT(size() == desiredSize);
1936 template <typename E, class T, class A, class S>
1937 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1938 const basic_fbstring& str, const size_type pos, size_type n) {
1939 const size_type sz = str.size();
1940 enforce(pos <= sz, std::__throw_out_of_range, "");
1941 procrustes(n, sz - pos);
1942 return append(str.data() + pos, n);
1945 template <typename E, class T, class A, class S>
1946 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1947 basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1948 Invariant checker(*this);
1950 if (FBSTRING_UNLIKELY(!n)) {
1951 // Unlikely but must be done
1954 auto const oldSize = size();
1955 auto const oldData = data();
1956 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1958 // Check for aliasing (rare). We could use "<=" here but in theory
1959 // those do not work for pointers unless the pointers point to
1960 // elements in the same array. For that reason we use
1961 // std::less_equal, which is guaranteed to offer a total order
1962 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1964 std::less_equal<const value_type*> le;
1965 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1966 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1967 // expandNoinit() could have moved the storage, restore the source.
1968 s = data() + (s - oldData);
1969 fbstring_detail::podMove(s, s + n, pData);
1971 fbstring_detail::podCopy(s, s + n, pData);
1974 FBSTRING_ASSERT(size() == oldSize + n);
1978 template <typename E, class T, class A, class S>
1979 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1980 size_type n, value_type c) {
1981 Invariant checker(*this);
1982 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1983 fbstring_detail::podFill(pData, pData + n, c);
1987 template <typename E, class T, class A, class S>
1988 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1989 const basic_fbstring& str, const size_type pos, size_type n) {
1990 const size_type sz = str.size();
1991 enforce(pos <= sz, std::__throw_out_of_range, "");
1992 procrustes(n, sz - pos);
1993 return assign(str.data() + pos, n);
1996 template <typename E, class T, class A, class S>
1997 FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1998 basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
1999 Invariant checker(*this);
2003 } else if (size() >= n) {
2004 // s can alias this, we need to use podMove.
2005 fbstring_detail::podMove(s, s + n, store_.mutableData());
2006 store_.shrink(size() - n);
2007 FBSTRING_ASSERT(size() == n);
2009 // If n is larger than size(), s cannot alias this string's
2012 // Do not use exponential growth here: assign() should be tight,
2013 // to mirror the behavior of the equivalent constructor.
2014 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
2017 FBSTRING_ASSERT(size() == n);
2021 #ifndef _LIBSTDCXX_FBSTRING
2022 template <typename E, class T, class A, class S>
2023 inline typename basic_fbstring<E, T, A, S>::istream_type&
2024 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
2025 Invariant checker(*this);
2030 size_t avail = capacity() - size;
2031 // fbstring has 1 byte extra capacity for the null terminator,
2032 // and getline null-terminates the read string.
2033 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2034 size += is.gcount();
2036 if (is.bad() || is.eof() || !is.fail()) {
2037 // Done by either failure, end of file, or normal read.
2038 if (!is.bad() && !is.eof()) {
2039 --size; // gcount() also accounts for the delimiter.
2045 FBSTRING_ASSERT(size == this->size());
2046 FBSTRING_ASSERT(size == capacity());
2047 // Start at minimum allocation 63 + terminator = 64.
2048 reserve(std::max<size_t>(63, 3 * size / 2));
2049 // Clear the error so we can continue reading.
2056 template <typename E, class T, class A, class S>
2057 inline typename basic_fbstring<E, T, A, S>::size_type
2058 basic_fbstring<E, T, A, S>::find(
2059 const value_type* needle, const size_type pos, const size_type nsize)
2061 auto const size = this->size();
2062 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2063 // that nsize + pos does not wrap around.
2064 if (nsize + pos > size || nsize + pos < pos) {
2071 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2072 // the last characters first
2073 auto const haystack = data();
2074 auto const nsize_1 = nsize - 1;
2075 auto const lastNeedle = needle[nsize_1];
2077 // Boyer-Moore skip value for the last char in the needle. Zero is
2078 // not a valid value; skip will be computed the first time it's
2082 const E* i = haystack + pos;
2083 auto iEnd = haystack + size - nsize_1;
2086 // Boyer-Moore: match the last element in the needle
2087 while (i[nsize_1] != lastNeedle) {
2093 // Here we know that the last char matches
2094 // Continue in pedestrian mode
2095 for (size_t j = 0;;) {
2096 FBSTRING_ASSERT(j < nsize);
2097 if (i[j] != needle[j]) {
2098 // Not found, we can skip
2099 // Compute the skip value lazily
2102 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2109 // Check if done searching
2112 return i - haystack;
2119 template <typename E, class T, class A, class S>
2120 inline typename basic_fbstring<E, T, A, S>::iterator
2121 basic_fbstring<E, T, A, S>::insertImplDiscr(
2122 const_iterator i, size_type n, value_type c, std::true_type) {
2123 Invariant checker(*this);
2125 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2126 const size_type pos = i - cbegin();
2128 auto oldSize = size();
2129 store_.expandNoinit(n, /* expGrowth = */ true);
2131 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2132 fbstring_detail::podFill(b + pos, b + pos + n, c);
2137 template <typename E, class T, class A, class S>
2138 template <class InputIter>
2139 inline typename basic_fbstring<E, T, A, S>::iterator
2140 basic_fbstring<E, T, A, S>::insertImplDiscr(
2141 const_iterator i, InputIter b, InputIter e, std::false_type) {
2143 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2146 template <typename E, class T, class A, class S>
2147 template <class FwdIterator>
2148 inline typename basic_fbstring<E, T, A, S>::iterator
2149 basic_fbstring<E, T, A, S>::insertImpl(
2153 std::forward_iterator_tag) {
2154 Invariant checker(*this);
2156 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2157 const size_type pos = i - cbegin();
2158 auto n = std::distance(s1, s2);
2159 FBSTRING_ASSERT(n >= 0);
2161 auto oldSize = size();
2162 store_.expandNoinit(n, /* expGrowth = */ true);
2164 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2165 std::copy(s1, s2, b + pos);
2170 template <typename E, class T, class A, class S>
2171 template <class InputIterator>
2172 inline typename basic_fbstring<E, T, A, S>::iterator
2173 basic_fbstring<E, T, A, S>::insertImpl(
2177 std::input_iterator_tag) {
2178 const auto pos = i - cbegin();
2179 basic_fbstring temp(cbegin(), i);
2180 for (; b != e; ++b) {
2183 temp.append(i, cend());
2185 return begin() + pos;
2188 template <typename E, class T, class A, class S>
2189 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2192 const value_type* s,
2194 std::integral_constant<int, 2>) {
2195 FBSTRING_ASSERT(i1 <= i2);
2196 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2197 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2198 return replace(i1, i2, s, s + n);
2201 template <typename E, class T, class A, class S>
2202 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2207 std::integral_constant<int, 1>) {
2208 const size_type n1 = i2 - i1;
2210 std::fill(i1, i1 + n2, c);
2213 std::fill(i1, i2, c);
2214 insert(i2, n2 - n1, c);
2216 FBSTRING_ASSERT(isSane());
2220 template <typename E, class T, class A, class S>
2221 template <class InputIter>
2222 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2227 std::integral_constant<int, 0>) {
2228 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2229 replaceImpl(i1, i2, b, e, Cat());
2233 template <typename E, class T, class A, class S>
2234 template <class FwdIterator>
2235 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2236 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2237 std::less_equal<const value_type*> le{};
2238 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2242 // Aliased replace, copy to new string
2243 basic_fbstring temp;
2244 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2245 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2250 template <typename E, class T, class A, class S>
2251 template <class FwdIterator>
2252 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2257 std::forward_iterator_tag) {
2258 Invariant checker(*this);
2260 // Handle aliased replace
2261 using Sel = std::integral_constant<
2263 std::is_same<FwdIterator, iterator>::value ||
2264 std::is_same<FwdIterator, const_iterator>::value>;
2265 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2269 auto const n1 = i2 - i1;
2270 FBSTRING_ASSERT(n1 >= 0);
2271 auto const n2 = std::distance(s1, s2);
2272 FBSTRING_ASSERT(n2 >= 0);
2276 std::copy(s1, s2, i1);
2280 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2283 FBSTRING_ASSERT(isSane());
2286 template <typename E, class T, class A, class S>
2287 template <class InputIterator>
2288 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2293 std::input_iterator_tag) {
2294 basic_fbstring temp(begin(), i1);
2295 temp.append(b, e).append(i2, end());
2299 template <typename E, class T, class A, class S>
2300 inline typename basic_fbstring<E, T, A, S>::size_type
2301 basic_fbstring<E, T, A, S>::rfind(
2302 const value_type* s, size_type pos, size_type n) const {
2306 pos = std::min(pos, length() - n);
2311 const_iterator i(begin() + pos);
2313 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2323 template <typename E, class T, class A, class S>
2324 inline typename basic_fbstring<E, T, A, S>::size_type
2325 basic_fbstring<E, T, A, S>::find_first_of(
2326 const value_type* s, size_type pos, size_type n) const {
2327 if (pos > length() || n == 0) {
2330 const_iterator i(begin() + pos), finish(end());
2331 for (; i != finish; ++i) {
2332 if (traits_type::find(s, n, *i) != 0) {
2339 template <typename E, class T, class A, class S>
2340 inline typename basic_fbstring<E, T, A, S>::size_type
2341 basic_fbstring<E, T, A, S>::find_last_of(
2342 const value_type* s, size_type pos, size_type n) const {
2343 if (!empty() && n > 0) {
2344 pos = std::min(pos, length() - 1);
2345 const_iterator i(begin() + pos);
2347 if (traits_type::find(s, n, *i) != 0) {
2358 template <typename E, class T, class A, class S>
2359 inline typename basic_fbstring<E, T, A, S>::size_type
2360 basic_fbstring<E, T, A, S>::find_first_not_of(
2361 const value_type* s, size_type pos, size_type n) const {
2362 if (pos < length()) {
2363 const_iterator i(begin() + pos), finish(end());
2364 for (; i != finish; ++i) {
2365 if (traits_type::find(s, n, *i) == 0) {
2373 template <typename E, class T, class A, class S>
2374 inline typename basic_fbstring<E, T, A, S>::size_type
2375 basic_fbstring<E, T, A, S>::find_last_not_of(
2376 const value_type* s, size_type pos, size_type n) const {
2377 if (!this->empty()) {
2378 pos = std::min(pos, size() - 1);
2379 const_iterator i(begin() + pos);
2381 if (traits_type::find(s, n, *i) == 0) {
2392 // non-member functions
2394 template <typename E, class T, class A, class S>
2396 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2397 const basic_fbstring<E, T, A, S>& rhs) {
2399 basic_fbstring<E, T, A, S> result;
2400 result.reserve(lhs.size() + rhs.size());
2401 result.append(lhs).append(rhs);
2402 return std::move(result);
2406 template <typename E, class T, class A, class S>
2408 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2409 const basic_fbstring<E, T, A, S>& rhs) {
2410 return std::move(lhs.append(rhs));
2414 template <typename E, class T, class A, class S>
2416 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2417 basic_fbstring<E, T, A, S>&& rhs) {
2418 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2419 // Good, at least we don't need to reallocate
2420 return std::move(rhs.insert(0, lhs));
2422 // Meh, no go. Forward to operator+(const&, const&).
2423 auto const& rhsC = rhs;
2428 template <typename E, class T, class A, class S>
2430 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2431 basic_fbstring<E, T, A, S>&& rhs) {
2432 return std::move(lhs.append(rhs));
2436 template <typename E, class T, class A, class S>
2438 basic_fbstring<E, T, A, S> operator+(
2440 const basic_fbstring<E, T, A, S>& rhs) {
2442 basic_fbstring<E, T, A, S> result;
2443 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2444 result.reserve(len + rhs.size());
2445 result.append(lhs, len).append(rhs);
2450 template <typename E, class T, class A, class S>
2452 basic_fbstring<E, T, A, S> operator+(
2454 basic_fbstring<E, T, A, S>&& rhs) {
2456 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2457 if (rhs.capacity() >= len + rhs.size()) {
2458 // Good, at least we don't need to reallocate
2459 rhs.insert(rhs.begin(), lhs, lhs + len);
2462 // Meh, no go. Do it by hand since we have len already.
2463 basic_fbstring<E, T, A, S> result;
2464 result.reserve(len + rhs.size());
2465 result.append(lhs, len).append(rhs);
2470 template <typename E, class T, class A, class S>
2472 basic_fbstring<E, T, A, S> operator+(
2474 const basic_fbstring<E, T, A, S>& rhs) {
2476 basic_fbstring<E, T, A, S> result;
2477 result.reserve(1 + rhs.size());
2478 result.push_back(lhs);
2484 template <typename E, class T, class A, class S>
2486 basic_fbstring<E, T, A, S> operator+(
2488 basic_fbstring<E, T, A, S>&& rhs) {
2490 if (rhs.capacity() > rhs.size()) {
2491 // Good, at least we don't need to reallocate
2492 rhs.insert(rhs.begin(), lhs);
2495 // Meh, no go. Forward to operator+(E, const&).
2496 auto const& rhsC = rhs;
2501 template <typename E, class T, class A, class S>
2503 basic_fbstring<E, T, A, S> operator+(
2504 const basic_fbstring<E, T, A, S>& lhs,
2507 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2508 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2510 basic_fbstring<E, T, A, S> result;
2511 const size_type len = traits_type::length(rhs);
2512 result.reserve(lhs.size() + len);
2513 result.append(lhs).append(rhs, len);
2517 // C++11 21.4.8.1/10
2518 template <typename E, class T, class A, class S>
2520 basic_fbstring<E, T, A, S> operator+(
2521 basic_fbstring<E, T, A, S>&& lhs,
2524 return std::move(lhs += rhs);
2527 // C++11 21.4.8.1/11
2528 template <typename E, class T, class A, class S>
2530 basic_fbstring<E, T, A, S> operator+(
2531 const basic_fbstring<E, T, A, S>& lhs,
2534 basic_fbstring<E, T, A, S> result;
2535 result.reserve(lhs.size() + 1);
2537 result.push_back(rhs);
2541 // C++11 21.4.8.1/12
2542 template <typename E, class T, class A, class S>
2544 basic_fbstring<E, T, A, S> operator+(
2545 basic_fbstring<E, T, A, S>&& lhs,
2548 return std::move(lhs += rhs);
2551 template <typename E, class T, class A, class S>
2553 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2554 const basic_fbstring<E, T, A, S>& rhs) {
2555 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2557 template <typename E, class T, class A, class S>
2559 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* 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 lhs.compare(rhs) == 0; }
2569 template <typename E, class T, class A, class S>
2571 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2572 const basic_fbstring<E, T, A, S>& rhs) {
2573 return !(lhs == rhs); }
2575 template <typename E, class T, class A, class S>
2577 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* 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 basic_fbstring<E, T, A, S>& lhs,
2590 const basic_fbstring<E, T, A, S>& rhs) {
2591 return lhs.compare(rhs) < 0; }
2593 template <typename E, class T, class A, class S>
2595 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2596 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2597 return lhs.compare(rhs) < 0; }
2599 template <typename E, class T, class A, class S>
2601 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2602 const basic_fbstring<E, T, A, S>& rhs) {
2603 return rhs.compare(lhs) > 0; }
2605 template <typename E, class T, class A, class S>
2607 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2608 const basic_fbstring<E, T, A, S>& rhs) {
2611 template <typename E, class T, class A, class S>
2613 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2614 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2617 template <typename E, class T, class A, class S>
2619 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2620 const basic_fbstring<E, T, A, S>& rhs) {
2623 template <typename E, class T, class A, class S>
2625 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2626 const basic_fbstring<E, T, A, S>& rhs) {
2627 return !(rhs < lhs); }
2629 template <typename E, class T, class A, class S>
2631 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2632 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2633 return !(rhs < lhs); }
2635 template <typename E, class T, class A, class S>
2637 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2638 const basic_fbstring<E, T, A, S>& rhs) {
2639 return !(rhs < lhs); }
2641 template <typename E, class T, class A, class S>
2643 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2644 const basic_fbstring<E, T, A, S>& rhs) {
2645 return !(lhs < rhs); }
2647 template <typename E, class T, class A, class S>
2649 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2650 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2651 return !(lhs < rhs); }
2653 template <typename E, class T, class A, class S>
2655 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2656 const basic_fbstring<E, T, A, S>& rhs) {
2657 return !(lhs < rhs);
2661 template <typename E, class T, class A, class S>
2662 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2666 // TODO: make this faster.
2667 template <typename E, class T, class A, class S>
2670 typename basic_fbstring<E, T, A, S>::value_type,
2671 typename basic_fbstring<E, T, A, S>::traits_type>&
2673 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2674 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2675 basic_fbstring<E, T, A, S>& str) {
2676 typedef std::basic_istream<
2677 typename basic_fbstring<E, T, A, S>::value_type,
2678 typename basic_fbstring<E, T, A, S>::traits_type>
2680 typename _istream_type::sentry sentry(is);
2681 size_t extracted = 0;
2682 auto err = _istream_type::goodbit;
2684 auto n = is.width();
2689 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2690 if (got == T::eof()) {
2691 err |= _istream_type::eofbit;
2699 got = is.rdbuf()->snextc();
2703 err |= _istream_type::failbit;
2711 template <typename E, class T, class A, class S>
2713 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2714 typename basic_fbstring<E, T, A, S>::traits_type>&
2716 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2717 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2718 const basic_fbstring<E, T, A, S>& str) {
2720 typedef std::basic_ostream<
2721 typename basic_fbstring<E, T, A, S>::value_type,
2722 typename basic_fbstring<E, T, A, S>::traits_type>
2724 typename _ostream_type::sentry _s(os);
2726 typedef std::ostreambuf_iterator<
2727 typename basic_fbstring<E, T, A, S>::value_type,
2728 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2729 size_t __len = str.size();
2731 (os.flags() & _ostream_type::adjustfield) == _ostream_type::left;
2732 if (__pad_and_output(_Ip(os),
2734 __left ? str.data() + __len : str.data(),
2737 os.fill()).failed()) {
2738 os.setstate(_ostream_type::badbit | _ostream_type::failbit);
2741 #elif defined(_MSC_VER)
2742 typedef decltype(os.precision()) streamsize;
2743 // MSVC doesn't define __ostream_insert
2744 os.write(str.data(), static_cast<streamsize>(str.size()));
2746 std::__ostream_insert(os, str.data(), str.size());
2751 template <typename E1, class T, class A, class S>
2752 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2753 basic_fbstring<E1, T, A, S>::npos;
2755 #ifndef _LIBSTDCXX_FBSTRING
2756 // basic_string compatibility routines
2758 template <typename E, class T, class A, class S, class A2>
2759 inline bool operator==(
2760 const basic_fbstring<E, T, A, S>& lhs,
2761 const std::basic_string<E, T, A2>& rhs) {
2762 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2765 template <typename E, class T, class A, class S, class A2>
2766 inline bool operator==(
2767 const std::basic_string<E, T, A2>& lhs,
2768 const basic_fbstring<E, T, A, S>& rhs) {
2772 template <typename E, class T, class A, class S, class A2>
2773 inline bool operator!=(
2774 const basic_fbstring<E, T, A, S>& lhs,
2775 const std::basic_string<E, T, A2>& rhs) {
2776 return !(lhs == rhs);
2779 template <typename E, class T, class A, class S, class A2>
2780 inline bool operator!=(
2781 const std::basic_string<E, T, A2>& lhs,
2782 const basic_fbstring<E, T, A, S>& rhs) {
2783 return !(lhs == rhs);
2786 template <typename E, class T, class A, class S, class A2>
2787 inline bool operator<(
2788 const basic_fbstring<E, T, A, S>& lhs,
2789 const std::basic_string<E, T, A2>& rhs) {
2790 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0;
2793 template <typename E, class T, class A, class S, class A2>
2794 inline bool operator>(
2795 const basic_fbstring<E, T, A, S>& lhs,
2796 const std::basic_string<E, T, A2>& rhs) {
2797 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) > 0;
2800 template <typename E, class T, class A, class S, class A2>
2801 inline bool operator<(
2802 const std::basic_string<E, T, A2>& lhs,
2803 const basic_fbstring<E, T, A, S>& rhs) {
2807 template <typename E, class T, class A, class S, class A2>
2808 inline bool operator>(
2809 const std::basic_string<E, T, A2>& lhs,
2810 const basic_fbstring<E, T, A, S>& rhs) {
2814 template <typename E, class T, class A, class S, class A2>
2815 inline bool operator<=(
2816 const basic_fbstring<E, T, A, S>& lhs,
2817 const std::basic_string<E, T, A2>& rhs) {
2818 return !(lhs > rhs);
2821 template <typename E, class T, class A, class S, class A2>
2822 inline bool operator>=(
2823 const basic_fbstring<E, T, A, S>& lhs,
2824 const std::basic_string<E, T, A2>& rhs) {
2825 return !(lhs < rhs);
2828 template <typename E, class T, class A, class S, class A2>
2829 inline bool operator<=(
2830 const std::basic_string<E, T, A2>& lhs,
2831 const basic_fbstring<E, T, A, S>& rhs) {
2832 return !(lhs > rhs);
2835 template <typename E, class T, class A, class S, class A2>
2836 inline bool operator>=(
2837 const std::basic_string<E, T, A2>& lhs,
2838 const basic_fbstring<E, T, A, S>& rhs) {
2839 return !(lhs < rhs);
2842 #if !defined(_LIBSTDCXX_FBSTRING)
2843 typedef basic_fbstring<char> fbstring;
2846 // fbstring is relocatable
2847 template <class T, class R, class A, class S>
2848 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2852 FOLLY_FBSTRING_END_NAMESPACE
2854 #ifndef _LIBSTDCXX_FBSTRING
2856 // Hash functions to make fbstring usable with e.g. hash_map
2858 // Handle interaction with different C++ standard libraries, which
2859 // expect these types to be in different namespaces.
2861 #define FOLLY_FBSTRING_HASH1(T) \
2863 struct hash< ::folly::basic_fbstring<T>> { \
2864 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2865 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2869 // The C++11 standard says that these four are defined
2870 #define FOLLY_FBSTRING_HASH \
2871 FOLLY_FBSTRING_HASH1(char) \
2872 FOLLY_FBSTRING_HASH1(char16_t) \
2873 FOLLY_FBSTRING_HASH1(char32_t) \
2874 FOLLY_FBSTRING_HASH1(wchar_t)
2882 #undef FOLLY_FBSTRING_HASH
2883 #undef FOLLY_FBSTRING_HASH1
2885 #endif // _LIBSTDCXX_FBSTRING
2889 #undef FBSTRING_DISABLE_SSO
2890 #undef FBSTRING_SANITIZE_ADDRESS
2892 #undef FBSTRING_LIKELY
2893 #undef FBSTRING_UNLIKELY
2894 #undef FBSTRING_ASSERT