2 * Copyright 2016 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
24 #include <type_traits>
26 // This file appears in two locations: inside fbcode and in the
27 // libstdc++ source code (when embedding fbstring as std::string).
28 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
29 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
30 #ifdef _LIBSTDCXX_FBSTRING
32 #pragma GCC system_header
34 // When used as std::string replacement always disable assertions.
37 #define FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
40 #include "basic_fbstring_malloc.h"
42 #else // !_LIBSTDCXX_FBSTRING
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>
61 #if FOLLY_HAVE_DEPRECATED_ASSOC
62 #ifdef _GLIBCXX_SYMVER
63 #include <ext/hash_set>
64 #include <ext/hash_map>
70 // We defined these here rather than including Likely.h to avoid
71 // redefinition errors when fbstring is imported into libstdc++.
72 #if defined(__GNUC__) && __GNUC__ >= 4
73 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
74 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
76 #define FBSTRING_LIKELY(x) (x)
77 #define FBSTRING_UNLIKELY(x) (x)
80 #pragma GCC diagnostic push
81 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
82 #pragma GCC diagnostic ignored "-Wshadow"
83 // GCC 4.9 has a false positive in setSmallSize (probably
84 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
85 // compile-time array bound checking.
86 #pragma GCC diagnostic ignored "-Warray-bounds"
88 // FBString cannot use throw when replacing std::string, though it may still
91 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
93 #ifdef _LIBSTDCXX_FBSTRING
94 namespace std _GLIBCXX_VISIBILITY(default) {
95 _GLIBCXX_BEGIN_NAMESPACE_VERSION
100 #if defined(__clang__)
101 # if __has_feature(address_sanitizer)
102 # define FBSTRING_SANITIZE_ADDRESS
104 #elif defined (__GNUC__) && \
105 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
107 # define FBSTRING_SANITIZE_ADDRESS
110 // When compiling with ASan, always heap-allocate the string even if
111 // it would fit in-situ, so that ASan can detect access to the string
112 // buffer after it has been invalidated (destroyed, resized, etc.).
113 // Note that this flag doesn't remove support for in-situ strings, as
114 // that would break ABI-compatibility and wouldn't allow linking code
115 // compiled with this flag with code compiled without.
116 #ifdef FBSTRING_SANITIZE_ADDRESS
117 # define FBSTRING_DISABLE_SSO true
119 # define FBSTRING_DISABLE_SSO false
122 namespace fbstring_detail {
124 template <class InIt, class OutIt>
125 inline std::pair<InIt, OutIt> copy_n(
127 typename std::iterator_traits<InIt>::difference_type n,
129 for (; n != 0; --n, ++b, ++d) {
132 return std::make_pair(b, d);
135 template <class Pod, class T>
136 inline void podFill(Pod* b, Pod* e, T c) {
137 assert(b && e && b <= e);
138 /*static*/ if (sizeof(T) == 1) {
141 auto const ee = b + ((e - b) & ~7u);
142 for (; b != ee; b += 8) {
153 for (; b != e; ++b) {
160 * Lightly structured memcpy, simplifies copying PODs and introduces
161 * some asserts. Unfortunately using this function may cause
162 * measurable overhead (presumably because it adjusts from a begin/end
163 * convention to a pointer/size convention, so it does some extra
164 * arithmetic even though the caller might have done the inverse
165 * adaptation outside).
168 inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
170 assert(d >= e || d + (e - b) <= b);
171 memcpy(d, b, (e - b) * sizeof(Pod));
175 * Lightly structured memmove, simplifies copying PODs and introduces
179 inline void podMove(const Pod* b, const Pod* e, Pod* d) {
181 memmove(d, b, (e - b) * sizeof(*b));
185 #if defined(__GNUC__) // Clang also defines __GNUC__
186 # define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
187 #elif defined(_MSC_VER)
188 # define FBSTRING_ALWAYS_INLINE __forceinline
190 # define FBSTRING_ALWAYS_INLINE inline
193 [[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
194 #if defined(__GNUC__) // Clang also defines __GNUC__
195 __builtin_unreachable();
196 #elif defined(_MSC_VER)
199 // Well, it's better than nothing.
204 } // namespace fbstring_detail
207 * Defines a special acquisition method for constructing fbstring
208 * objects. AcquireMallocatedString means that the user passes a
209 * pointer to a malloc-allocated string that the fbstring object will
212 enum class AcquireMallocatedString {};
215 * fbstring_core_model is a mock-up type that defines all required
216 * signatures of a fbstring core. The fbstring class itself uses such
217 * a core object to implement all of the numerous member functions
218 * required by the standard.
220 * If you want to define a new core, copy the definition below and
221 * implement the primitives. Then plug the core into basic_fbstring as
222 * a template argument.
224 template <class Char>
225 class fbstring_core_model {
227 fbstring_core_model();
228 fbstring_core_model(const fbstring_core_model &);
229 ~fbstring_core_model();
230 // Returns a pointer to string's buffer (currently only contiguous
231 // strings are supported). The pointer is guaranteed to be valid
232 // until the next call to a non-const member function.
233 const Char * data() const;
234 // Much like data(), except the string is prepared to support
235 // character-level changes. This call is a signal for
236 // e.g. reference-counted implementation to fork the data. The
237 // pointer is guaranteed to be valid until the next call to a
238 // non-const member function.
240 // Returns a pointer to string's buffer and guarantees that a
241 // readable '\0' lies right after the buffer. The pointer is
242 // guaranteed to be valid until the next call to a non-const member
244 const Char * c_str() const;
245 // Shrinks the string by delta characters. Asserts that delta <=
247 void shrink(size_t delta);
248 // Expands the string by delta characters (i.e. after this call
249 // size() will report the old size() plus delta) but without
250 // initializing the expanded region. The expanded region is
251 // zero-terminated. Returns a pointer to the memory to be
252 // initialized (the beginning of the expanded portion). The caller
253 // is expected to fill the expanded area appropriately.
254 // If expGrowth is true, exponential growth is guaranteed.
255 // It is not guaranteed not to reallocate even if size() + delta <
256 // capacity(), so all references to the buffer are invalidated.
257 Char* expandNoinit(size_t delta, bool expGrowth);
258 // Expands the string by one character and sets the last character
260 void push_back(Char c);
261 // Returns the string's size.
263 // Returns the string's capacity, i.e. maximum size that the string
264 // can grow to without reallocation. Note that for reference counted
265 // strings that's technically a lie - even assigning characters
266 // within the existing size would cause a reallocation.
267 size_t capacity() const;
268 // Returns true if the data underlying the string is actually shared
269 // across multiple strings (in a refcounted fashion).
270 bool isShared() const;
271 // Makes sure that at least minCapacity characters are available for
272 // the string without reallocation. For reference-counted strings,
273 // it should fork the data even if minCapacity < size().
274 void reserve(size_t minCapacity);
277 fbstring_core_model& operator=(const fbstring_core_model &);
282 * This is the core of the string. The code should work on 32- and
283 * 64-bit and both big- and little-endianan architectures with any
286 * The storage is selected as follows (assuming we store one-byte
287 * characters on a 64-bit machine): (a) "small" strings between 0 and
288 * 23 chars are stored in-situ without allocation (the rightmost byte
289 * stores the size); (b) "medium" strings from 24 through 254 chars
290 * are stored in malloc-allocated memory that is copied eagerly; (c)
291 * "large" strings of 255 chars and above are stored in a similar
292 * structure as medium arrays, except that the string is
293 * reference-counted and copied lazily. the reference count is
294 * allocated right before the character array.
296 * The discriminator between these three strategies sits in two
297 * bits of the rightmost char of the storage. If neither is set, then the
298 * string is small (and its length sits in the lower-order bits on
299 * little-endian or the high-order bits on big-endian of that
300 * rightmost character). If the MSb is set, the string is medium width.
301 * If the second MSb is set, then the string is large. On little-endian,
302 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
303 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
304 * and big-endian fbstring_core equivalent with merely different ops used
305 * to extract capacity/category.
307 template <class Char> class fbstring_core {
309 // It's MSVC, so we just have to guess ... and allow an override
311 # ifdef FOLLY_ENDIAN_BE
312 static constexpr auto kIsLittleEndian = false;
314 static constexpr auto kIsLittleEndian = true;
317 static constexpr auto kIsLittleEndian =
318 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
321 fbstring_core() noexcept { reset(); }
323 fbstring_core(const fbstring_core & rhs) {
324 assert(&rhs != this);
325 switch (rhs.category()) {
326 case Category::isSmall:
329 case Category::isMedium:
332 case Category::isLarge:
336 fbstring_detail::assume_unreachable();
338 assert(size() == rhs.size());
339 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
342 fbstring_core(fbstring_core&& goner) noexcept {
345 // Clean goner's carcass
349 fbstring_core(const Char *const data,
351 bool disableSSO = FBSTRING_DISABLE_SSO) {
352 if (!disableSSO && size <= maxSmallSize) {
353 initSmall(data, size);
354 } else if (size <= maxMediumSize) {
355 initMedium(data, size);
357 initLarge(data, size);
360 #ifndef _LIBSTDCXX_FBSTRING
361 assert(this->size() == size);
362 assert(size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
367 ~fbstring_core() noexcept {
368 auto const c = category();
369 if (c == Category::isSmall) {
372 if (c == Category::isMedium) {
376 RefCounted::decrementRefs(ml_.data_);
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 assert(allocatedSize >= size + 1);
392 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 auto const c = category();
434 if (c == Category::isSmall) {
435 assert(small_[smallSize()] == '\0');
438 assert(c == Category::isMedium || c == Category::isLarge);
439 assert(ml_.data_[ml_.size_] == '\0');
443 void shrink(const size_t delta) {
444 if (category() == Category::isSmall) {
446 } else if (category() == Category::isMedium ||
447 RefCounted::refs(ml_.data_) == 1) {
454 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
455 switch (category()) {
456 case Category::isSmall:
457 reserveSmall(minCapacity, disableSSO);
459 case Category::isMedium:
460 reserveMedium(minCapacity);
462 case Category::isLarge:
463 reserveLarge(minCapacity);
466 fbstring_detail::assume_unreachable();
468 assert(capacity() >= minCapacity);
473 bool expGrowth = false,
474 bool disableSSO = FBSTRING_DISABLE_SSO);
476 void push_back(Char c) {
477 *expandNoinit(1, /* expGrowth = */ true) = c;
480 size_t size() const {
481 return category() == Category::isSmall ? smallSize() : ml_.size_;
484 size_t capacity() const {
485 switch (category()) {
486 case Category::isSmall:
488 case Category::isLarge:
489 // For large-sized strings, a multi-referenced chunk has no
490 // available capacity. This is because any attempt to append
491 // data would trigger a new allocation.
492 if (RefCounted::refs(ml_.data_) > 1) {
497 return ml_.capacity();
500 bool isShared() const {
501 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
506 fbstring_core & operator=(const fbstring_core & rhs);
508 // Equivalent to setSmallSize(0) but a few ns faster in
511 ml_.capacity_ = kIsLittleEndian
512 ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
515 assert(category() == Category::isSmall && size() == 0);
519 std::atomic<size_t> refCount_;
522 static RefCounted * fromData(Char * p) {
523 return static_cast<RefCounted*>(
525 static_cast<unsigned char*>(static_cast<void*>(p))
526 - sizeof(refCount_)));
529 static size_t refs(Char * p) {
530 return fromData(p)->refCount_.load(std::memory_order_acquire);
533 static void incrementRefs(Char * p) {
534 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
537 static void decrementRefs(Char * p) {
538 auto const dis = fromData(p);
539 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
546 static RefCounted * create(size_t * size) {
547 // Don't forget to allocate one extra Char for the terminating
548 // null. In this case, however, one Char is already part of the
550 const size_t allocSize = goodMallocSize(
551 sizeof(RefCounted) + *size * sizeof(Char));
552 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
553 result->refCount_.store(1, std::memory_order_release);
554 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
558 static RefCounted * create(const Char * data, size_t * size) {
559 const size_t effectiveSize = *size;
560 auto result = create(size);
561 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
565 static RefCounted * reallocate(Char *const data,
566 const size_t currentSize,
567 const size_t currentCapacity,
568 const size_t newCapacity) {
569 assert(newCapacity > 0 && newCapacity > currentSize);
570 auto const dis = fromData(data);
571 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
572 // Don't forget to allocate one extra Char for the terminating
573 // null. In this case, however, one Char is already part of the
575 auto result = static_cast<RefCounted*>(
577 sizeof(RefCounted) + currentSize * sizeof(Char),
578 sizeof(RefCounted) + currentCapacity * sizeof(Char),
579 sizeof(RefCounted) + newCapacity * sizeof(Char)));
580 assert(result->refCount_.load(std::memory_order_acquire) == 1);
585 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
588 enum class Category : category_type {
590 isMedium = kIsLittleEndian
591 ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
593 isLarge = kIsLittleEndian
594 ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
598 Category category() const {
599 // works for both big-endian and little-endian
600 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
608 size_t capacity() const {
609 return kIsLittleEndian
610 ? capacity_ & capacityExtractMask
614 void setCapacity(size_t cap, Category cat) {
615 capacity_ = kIsLittleEndian
616 ? cap | static_cast<category_type>(cat)
617 : (cap << 2) | static_cast<category_type>(cat);
622 Char small_[sizeof(MediumLarge) / sizeof(Char)];
627 lastChar = sizeof(MediumLarge) - 1,
628 maxSmallSize = lastChar / sizeof(Char),
629 maxMediumSize = 254 / sizeof(Char), // coincides with the small
630 // bin size in dlmalloc
631 categoryExtractMask = kIsLittleEndian
632 ? sizeof(size_t) == 4 ? 0xC0000000 : size_t(0xC000000000000000)
634 capacityExtractMask = kIsLittleEndian
635 ? ~categoryExtractMask
638 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
639 "Corrupt memory layout for fbstring.");
641 size_t smallSize() const {
642 assert(category() == Category::isSmall);
643 constexpr auto shift = kIsLittleEndian ? 0 : 2;
644 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
645 assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
646 return static_cast<size_t>(maxSmallSize) - smallShifted;
649 void setSmallSize(size_t s) {
650 // Warning: this should work with uninitialized strings too,
651 // so don't assume anything about the previous value of
652 // small_[maxSmallSize].
653 assert(s <= maxSmallSize);
654 constexpr auto shift = kIsLittleEndian ? 0 : 2;
655 small_[maxSmallSize] = (maxSmallSize - s) << shift;
657 assert(category() == Category::isSmall && size() == s);
660 void copySmall(const fbstring_core&);
661 void copyMedium(const fbstring_core&);
662 void copyLarge(const fbstring_core&);
664 void initSmall(const Char* data, size_t size);
665 void initMedium(const Char* data, size_t size);
666 void initLarge(const Char* data, size_t size);
668 void reserveSmall(size_t minCapacity, bool disableSSO);
669 void reserveMedium(size_t minCapacity);
670 void reserveLarge(size_t minCapacity);
672 void shrinkSmall(size_t delta);
673 void shrinkMedium(size_t delta);
674 void shrinkLarge(size_t delta);
676 Char* mutableDataLarge();
679 template <class Char>
680 inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
681 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
683 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
684 "fbstring layout failure");
686 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
687 "fbstring layout failure");
688 // Just write the whole thing, don't look at details. In
689 // particular we need to copy capacity anyway because we want
690 // to set the size (don't forget that the last character,
691 // which stores a short string's length, is shared with the
692 // ml_.capacity field).
694 assert(category() == Category::isSmall && this->size() == rhs.size());
697 template <class Char>
698 inline void fbstring_core<Char>::copyMedium(const fbstring_core& rhs) {
699 // Medium strings are copied eagerly. Don't forget to allocate
700 // one extra Char for the null terminator.
701 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
702 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
703 // Also copies terminator.
704 fbstring_detail::podCopy(
705 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
706 ml_.size_ = rhs.ml_.size_;
707 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
708 assert(category() == Category::isMedium);
711 template <class Char>
712 inline void fbstring_core<Char>::copyLarge(const fbstring_core& rhs) {
713 // Large strings are just refcounted
715 RefCounted::incrementRefs(ml_.data_);
716 assert(category() == Category::isLarge && size() == rhs.size());
719 // Small strings are bitblitted
720 template <class Char>
721 inline void fbstring_core<Char>::initSmall(
722 const Char* const data, const size_t size) {
723 // Layout is: Char* data_, size_t size_, size_t capacity_
725 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
726 "fbstring has unexpected size");
728 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
729 // sizeof(size_t) must be a power of 2
731 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
732 "fbstring size assumption violation");
734 // If data is aligned, use fast word-wise copying. Otherwise,
735 // use conservative memcpy.
736 // The word-wise path reads bytes which are outside the range of
737 // the string, and makes ASan unhappy, so we disable it when
738 // compiling with ASan.
739 #ifndef FBSTRING_SANITIZE_ADDRESS
740 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
741 const size_t byteSize = size * sizeof(Char);
742 constexpr size_t wordWidth = sizeof(size_t);
743 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
745 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
747 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
749 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
757 fbstring_detail::podCopy(data, data + size, small_);
763 template <class Char>
764 inline void fbstring_core<Char>::initMedium(
765 const Char* const data, const size_t size) {
766 // Medium strings are allocated normally. Don't forget to
767 // allocate one extra Char for the terminating null.
768 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
769 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
770 fbstring_detail::podCopy(data, data + size, ml_.data_);
772 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
773 ml_.data_[size] = '\0';
776 template <class Char>
777 inline void fbstring_core<Char>::initLarge(
778 const Char* const data, const size_t size) {
779 // Large strings are allocated differently
780 size_t effectiveCapacity = size;
781 auto const newRC = RefCounted::create(data, &effectiveCapacity);
782 ml_.data_ = newRC->data_;
784 ml_.setCapacity(effectiveCapacity, Category::isLarge);
785 ml_.data_[size] = '\0';
788 template <class Char>
789 inline Char* fbstring_core<Char>::mutableDataLarge() {
790 assert(category() == Category::isLarge);
791 if (RefCounted::refs(ml_.data_) > 1) {
793 size_t effectiveCapacity = ml_.capacity();
794 auto const newRC = RefCounted::create(&effectiveCapacity);
795 // If this fails, someone placed the wrong capacity in an
797 assert(effectiveCapacity >= ml_.capacity());
798 // Also copies terminator.
799 fbstring_detail::podCopy(
800 ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
801 RefCounted::decrementRefs(ml_.data_);
802 ml_.data_ = newRC->data_;
807 template <class Char>
808 inline void fbstring_core<Char>::reserveLarge(size_t minCapacity) {
809 assert(category() == Category::isLarge);
811 if (RefCounted::refs(ml_.data_) > 1) {
812 // We must make it unique regardless; in-place reallocation is
813 // useless if the string is shared. In order to not surprise
814 // people, reserve the new block at current capacity or
815 // more. That way, a string's capacity never shrinks after a
817 minCapacity = std::max(minCapacity, ml_.capacity());
818 auto const newRC = RefCounted::create(&minCapacity);
819 // Also copies terminator.
820 fbstring_detail::podCopy(
821 ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
822 RefCounted::decrementRefs(ml_.data_);
823 ml_.data_ = newRC->data_;
824 ml_.setCapacity(minCapacity, Category::isLarge);
825 // size remains unchanged
827 // String is not shared, so let's try to realloc (if needed)
828 if (minCapacity > ml_.capacity()) {
829 // Asking for more memory
830 auto const newRC = RefCounted::reallocate(
831 ml_.data_, ml_.size_, ml_.capacity(), minCapacity);
832 ml_.data_ = newRC->data_;
833 ml_.setCapacity(minCapacity, Category::isLarge);
835 assert(capacity() >= minCapacity);
839 template <class Char>
840 inline void fbstring_core<Char>::reserveMedium(const size_t minCapacity) {
841 assert(category() == Category::isMedium);
842 // String is not shared
843 if (minCapacity <= ml_.capacity()) {
844 return; // nothing to do, there's enough room
846 if (minCapacity <= maxMediumSize) {
847 // Keep the string at medium size. Don't forget to allocate
848 // one extra Char for the terminating null.
849 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
850 // Also copies terminator.
851 ml_.data_ = static_cast<Char*>(smartRealloc(
853 (ml_.size_ + 1) * sizeof(Char),
854 (ml_.capacity() + 1) * sizeof(Char),
856 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
858 // Conversion from medium to large string
859 fbstring_core nascent;
860 // Will recurse to another branch of this function
861 nascent.reserve(minCapacity);
862 nascent.ml_.size_ = ml_.size_;
863 // Also copies terminator.
864 fbstring_detail::podCopy(
865 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
867 assert(capacity() >= minCapacity);
871 template <class Char>
872 inline void fbstring_core<Char>::reserveSmall(
873 size_t minCapacity, const bool disableSSO) {
874 assert(category() == Category::isSmall);
875 if (!disableSSO && minCapacity <= maxSmallSize) {
877 // Nothing to do, everything stays put
878 } else if (minCapacity <= maxMediumSize) {
880 // Don't forget to allocate one extra Char for the terminating null
881 auto const allocSizeBytes =
882 goodMallocSize((1 + minCapacity) * sizeof(Char));
883 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
884 auto const size = smallSize();
885 // Also copies terminator.
886 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
889 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
892 auto const newRC = RefCounted::create(&minCapacity);
893 auto const size = smallSize();
894 // Also copies terminator.
895 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
896 ml_.data_ = newRC->data_;
898 ml_.setCapacity(minCapacity, Category::isLarge);
899 assert(capacity() >= minCapacity);
903 template <class Char>
904 inline Char* fbstring_core<Char>::expandNoinit(
906 bool expGrowth, /* = false */
907 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
908 // Strategy is simple: make room, then change size
909 assert(capacity() >= size());
911 if (category() == Category::isSmall) {
914 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
919 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
923 if (FBSTRING_UNLIKELY(newSz > capacity())) {
924 // ensures not shared
925 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
928 assert(capacity() >= newSz);
929 // Category can't be small - we took care of that above
930 assert(category() == Category::isMedium || category() == Category::isLarge);
932 ml_.data_[newSz] = '\0';
933 assert(size() == newSz);
934 return ml_.data_ + sz;
937 template <class Char>
938 inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
939 // Check for underflow
940 assert(delta <= smallSize());
941 setSmallSize(smallSize() - delta);
944 template <class Char>
945 inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
946 // Medium strings and unique large strings need no special
948 assert(ml_.size_ >= delta);
950 ml_.data_[ml_.size_] = '\0';
953 template <class Char>
954 inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
955 assert(ml_.size_ >= delta);
956 // Shared large string, must make unique. This is because of the
957 // durn terminator must be written, which may trample the shared
960 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
962 // No need to write the terminator.
965 #ifndef _LIBSTDCXX_FBSTRING
967 * Dummy fbstring core that uses an actual std::string. This doesn't
968 * make any sense - it's just for testing purposes.
970 template <class Char>
971 class dummy_fbstring_core {
973 dummy_fbstring_core() {
975 dummy_fbstring_core(const dummy_fbstring_core& another)
976 : backend_(another.backend_) {
978 dummy_fbstring_core(const Char * s, size_t n)
981 void swap(dummy_fbstring_core & rhs) {
982 backend_.swap(rhs.backend_);
984 const Char * data() const {
985 return backend_.data();
987 Char* mutableData() {
988 return const_cast<Char*>(backend_.data());
990 void shrink(size_t delta) {
991 assert(delta <= size());
992 backend_.resize(size() - delta);
994 Char* expandNoinit(size_t delta) {
995 auto const sz = size();
996 backend_.resize(size() + delta);
997 return backend_.data() + sz;
999 void push_back(Char c) {
1000 backend_.push_back(c);
1002 size_t size() const {
1003 return backend_.size();
1005 size_t capacity() const {
1006 return backend_.capacity();
1008 bool isShared() const {
1011 void reserve(size_t minCapacity) {
1012 backend_.reserve(minCapacity);
1016 std::basic_string<Char> backend_;
1018 #endif // !_LIBSTDCXX_FBSTRING
1021 * This is the basic_string replacement. For conformity,
1022 * basic_fbstring takes the same template parameters, plus the last
1023 * one which is the core.
1025 #ifdef _LIBSTDCXX_FBSTRING
1026 template <typename E, class T, class A, class Storage>
1028 template <typename E,
1029 class T = std::char_traits<E>,
1030 class A = std::allocator<E>,
1031 class Storage = fbstring_core<E> >
1033 class basic_fbstring {
1035 static void enforce(
1037 void (*throw_exc)(const char*),
1044 bool isSane() const {
1047 empty() == (size() == 0) &&
1048 empty() == (begin() == end()) &&
1049 size() <= max_size() &&
1050 capacity() <= max_size() &&
1051 size() <= capacity() &&
1052 begin()[size()] == '\0';
1056 friend struct Invariant;
1058 Invariant& operator=(const Invariant&) = delete;
1060 explicit Invariant(const basic_fbstring& s) : s_(s) {
1061 assert(s_.isSane());
1064 assert(s_.isSane());
1067 const basic_fbstring& s_;
1069 explicit Invariant(const basic_fbstring&) {}
1075 typedef T traits_type;
1076 typedef typename traits_type::char_type value_type;
1077 typedef A allocator_type;
1078 typedef typename A::size_type size_type;
1079 typedef typename A::difference_type difference_type;
1081 typedef typename A::reference reference;
1082 typedef typename A::const_reference const_reference;
1083 typedef typename A::pointer pointer;
1084 typedef typename A::const_pointer const_pointer;
1086 typedef E* iterator;
1087 typedef const E* const_iterator;
1088 typedef std::reverse_iterator<iterator
1089 #ifdef NO_ITERATOR_TRAITS
1093 typedef std::reverse_iterator<const_iterator
1094 #ifdef NO_ITERATOR_TRAITS
1097 > const_reverse_iterator;
1099 static constexpr size_type npos = size_type(-1);
1100 typedef std::true_type IsRelocatable;
1103 static void procrustes(size_type& n, size_type nmax) {
1109 static size_type traitsLength(const value_type* s);
1112 // C++11 21.4.2 construct/copy/destroy
1114 // Note: while the following two constructors can be (and previously were)
1115 // collapsed into one constructor written this way:
1117 // explicit basic_fbstring(const A& a = A()) noexcept { }
1119 // This can cause Clang (at least version 3.7) to fail with the error:
1120 // "chosen constructor is explicit in copy-initialization ...
1121 // in implicit initialization of field '(x)' with omitted initializer"
1123 // if used in a struct which is default-initialized. Hence the split into
1124 // these two separate constructors.
1126 basic_fbstring() noexcept : basic_fbstring(A()) {
1129 explicit basic_fbstring(const A&) noexcept {
1132 basic_fbstring(const basic_fbstring& str)
1133 : store_(str.store_) {
1137 basic_fbstring(basic_fbstring&& goner) noexcept
1138 : store_(std::move(goner.store_)) {
1141 #ifndef _LIBSTDCXX_FBSTRING
1142 // This is defined for compatibility with std::string
1143 /* implicit */ basic_fbstring(const std::string& str)
1144 : store_(str.data(), str.size()) {
1148 basic_fbstring(const basic_fbstring& str,
1151 const A& /* a */ = A()) {
1152 assign(str, pos, n);
1155 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1156 : store_(s, basic_fbstring::traitsLength(s)) {
1159 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1163 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1164 auto const pData = store_.expandNoinit(n);
1165 fbstring_detail::podFill(pData, pData + n, c);
1168 template <class InIt>
1172 typename std::enable_if<
1173 !std::is_same<InIt, value_type*>::value,
1174 const A>::type& /*a*/ = A()) {
1178 // Specialization for const char*, const char*
1179 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1180 : store_(b, e - b) {
1183 // Nonstandard constructor
1184 basic_fbstring(value_type *s, size_type n, size_type c,
1185 AcquireMallocatedString a)
1186 : store_(s, n, c, a) {
1189 // Construction from initialization list
1190 basic_fbstring(std::initializer_list<value_type> il) {
1191 assign(il.begin(), il.end());
1194 ~basic_fbstring() noexcept {
1197 basic_fbstring& operator=(const basic_fbstring& lhs);
1200 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1202 #ifndef _LIBSTDCXX_FBSTRING
1203 // Compatibility with std::string
1204 basic_fbstring & operator=(const std::string & rhs) {
1205 return assign(rhs.data(), rhs.size());
1208 // Compatibility with std::string
1209 std::string toStdString() const {
1210 return std::string(data(), size());
1213 // A lot of code in fbcode still uses this method, so keep it here for now.
1214 const basic_fbstring& toStdString() const {
1219 basic_fbstring& operator=(const value_type* s) {
1223 basic_fbstring& operator=(value_type c);
1225 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1226 return assign(il.begin(), il.end());
1229 // C++11 21.4.3 iterators:
1231 return store_.mutableData();
1234 const_iterator begin() const {
1235 return store_.data();
1238 const_iterator cbegin() const {
1243 return store_.mutableData() + store_.size();
1246 const_iterator end() const {
1247 return store_.data() + store_.size();
1250 const_iterator cend() const { return end(); }
1252 reverse_iterator rbegin() {
1253 return reverse_iterator(end());
1256 const_reverse_iterator rbegin() const {
1257 return const_reverse_iterator(end());
1260 const_reverse_iterator crbegin() const { return rbegin(); }
1262 reverse_iterator rend() {
1263 return reverse_iterator(begin());
1266 const_reverse_iterator rend() const {
1267 return const_reverse_iterator(begin());
1270 const_reverse_iterator crend() const { return rend(); }
1273 // C++11 21.4.5, element access:
1274 const value_type& front() const { return *begin(); }
1275 const value_type& back() const {
1277 // Should be begin()[size() - 1], but that branches twice
1278 return *(end() - 1);
1280 value_type& front() { return *begin(); }
1281 value_type& back() {
1283 // Should be begin()[size() - 1], but that branches twice
1284 return *(end() - 1);
1291 // C++11 21.4.4 capacity:
1292 size_type size() const { return store_.size(); }
1294 size_type length() const { return size(); }
1296 size_type max_size() const {
1297 return std::numeric_limits<size_type>::max();
1300 void resize(size_type n, value_type c = value_type());
1302 size_type capacity() const { return store_.capacity(); }
1304 void reserve(size_type res_arg = 0) {
1305 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1306 store_.reserve(res_arg);
1309 void shrink_to_fit() {
1310 // Shrink only if slack memory is sufficiently large
1311 if (capacity() < size() * 3 / 2) {
1314 basic_fbstring(cbegin(), cend()).swap(*this);
1317 void clear() { resize(0); }
1319 bool empty() const { return size() == 0; }
1321 // C++11 21.4.5 element access:
1322 const_reference operator[](size_type pos) const {
1323 return *(begin() + pos);
1326 reference operator[](size_type pos) {
1327 return *(begin() + pos);
1330 const_reference at(size_type n) const {
1331 enforce(n <= size(), std::__throw_out_of_range, "");
1335 reference at(size_type n) {
1336 enforce(n < size(), std::__throw_out_of_range, "");
1340 // C++11 21.4.6 modifiers:
1341 basic_fbstring& operator+=(const basic_fbstring& str) {
1345 basic_fbstring& operator+=(const value_type* s) {
1349 basic_fbstring& operator+=(const value_type c) {
1354 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1359 basic_fbstring& append(const basic_fbstring& str);
1362 append(const basic_fbstring& str, const size_type pos, size_type n);
1364 basic_fbstring& append(const value_type* s, size_type n);
1366 basic_fbstring& append(const value_type* s) {
1367 return append(s, traits_type::length(s));
1370 basic_fbstring& append(size_type n, value_type c);
1372 template<class InputIterator>
1373 basic_fbstring& append(InputIterator first, InputIterator last) {
1374 insert(end(), first, last);
1378 basic_fbstring& append(std::initializer_list<value_type> il) {
1379 return append(il.begin(), il.end());
1382 void push_back(const value_type c) { // primitive
1383 store_.push_back(c);
1386 basic_fbstring& assign(const basic_fbstring& str) {
1387 if (&str == this) return *this;
1388 return assign(str.data(), str.size());
1391 basic_fbstring& assign(basic_fbstring&& str) {
1392 return *this = std::move(str);
1396 assign(const basic_fbstring& str, const size_type pos, size_type n);
1398 basic_fbstring& assign(const value_type* s, const size_type n);
1400 basic_fbstring& assign(const value_type* s) {
1401 return assign(s, traits_type::length(s));
1404 basic_fbstring& assign(std::initializer_list<value_type> il) {
1405 return assign(il.begin(), il.end());
1408 template <class ItOrLength, class ItOrChar>
1409 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1410 return replace(begin(), end(), first_or_n, last_or_c);
1413 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1414 return insert(pos1, str.data(), str.size());
1417 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1418 size_type pos2, size_type n) {
1419 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1420 procrustes(n, str.length() - pos2);
1421 return insert(pos1, str.data() + pos2, n);
1424 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1425 enforce(pos <= length(), std::__throw_out_of_range, "");
1426 insert(begin() + pos, s, s + n);
1430 basic_fbstring& insert(size_type pos, const value_type* s) {
1431 return insert(pos, s, traits_type::length(s));
1434 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1435 enforce(pos <= length(), std::__throw_out_of_range, "");
1436 insert(begin() + pos, n, c);
1440 iterator insert(const_iterator p, const value_type c) {
1441 const size_type pos = p - cbegin();
1443 return begin() + pos;
1446 #ifndef _LIBSTDCXX_FBSTRING
1448 typedef std::basic_istream<value_type, traits_type> istream_type;
1449 istream_type& getlineImpl(istream_type& is, value_type delim);
1452 friend inline istream_type& getline(istream_type& is,
1453 basic_fbstring& str,
1455 return str.getlineImpl(is, delim);
1458 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1459 return getline(is, str, '\n');
1465 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1467 template <class InputIter>
1469 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1471 template <class FwdIterator>
1472 iterator insertImpl(
1476 std::forward_iterator_tag);
1478 template <class InputIterator>
1479 iterator insertImpl(
1483 std::input_iterator_tag);
1486 template <class ItOrLength, class ItOrChar>
1487 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1488 using Sel = std::integral_constant<
1490 std::numeric_limits<ItOrLength>::is_specialized>;
1491 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1494 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1495 return insert(p, il.begin(), il.end());
1498 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1499 Invariant checker(*this);
1501 enforce(pos <= length(), std::__throw_out_of_range, "");
1502 procrustes(n, length() - pos);
1503 std::copy(begin() + pos + n, end(), begin() + pos);
1504 resize(length() - n);
1508 iterator erase(iterator position) {
1509 const size_type pos(position - begin());
1510 enforce(pos <= size(), std::__throw_out_of_range, "");
1512 return begin() + pos;
1515 iterator erase(iterator first, iterator last) {
1516 const size_type pos(first - begin());
1517 erase(pos, last - first);
1518 return begin() + pos;
1521 // Replaces at most n1 chars of *this, starting with pos1 with the
1523 basic_fbstring& replace(size_type pos1, size_type n1,
1524 const basic_fbstring& str) {
1525 return replace(pos1, n1, str.data(), str.size());
1528 // Replaces at most n1 chars of *this, starting with pos1,
1529 // with at most n2 chars of str starting with pos2
1530 basic_fbstring& replace(size_type pos1, size_type n1,
1531 const basic_fbstring& str,
1532 size_type pos2, size_type n2) {
1533 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1534 return replace(pos1, n1, str.data() + pos2,
1535 std::min(n2, str.size() - pos2));
1538 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1539 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1540 return replace(pos, n1, s, traits_type::length(s));
1543 // Replaces at most n1 chars of *this, starting with pos, with n2
1546 // consolidated with
1548 // Replaces at most n1 chars of *this, starting with pos, with at
1549 // most n2 chars of str. str must have at least n2 chars.
1550 template <class StrOrLength, class NumOrChar>
1551 basic_fbstring& replace(size_type pos, size_type n1,
1552 StrOrLength s_or_n2, NumOrChar n_or_c) {
1553 Invariant checker(*this);
1555 enforce(pos <= size(), std::__throw_out_of_range, "");
1556 procrustes(n1, length() - pos);
1557 const iterator b = begin() + pos;
1558 return replace(b, b + n1, s_or_n2, n_or_c);
1561 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1562 return replace(i1, i2, str.data(), str.length());
1565 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1566 return replace(i1, i2, s, traits_type::length(s));
1570 basic_fbstring& replaceImplDiscr(
1573 const value_type* s,
1575 std::integral_constant<int, 2>);
1577 basic_fbstring& replaceImplDiscr(
1582 std::integral_constant<int, 1>);
1584 template <class InputIter>
1585 basic_fbstring& replaceImplDiscr(
1590 std::integral_constant<int, 0>);
1593 template <class FwdIterator>
1594 bool replaceAliased(iterator /* i1 */,
1596 FwdIterator /* s1 */,
1597 FwdIterator /* s2 */,
1602 template <class FwdIterator>
1603 bool replaceAliased(
1610 template <class FwdIterator>
1616 std::forward_iterator_tag);
1618 template <class InputIterator>
1624 std::input_iterator_tag);
1627 template <class T1, class T2>
1628 basic_fbstring& replace(iterator i1, iterator i2,
1629 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1630 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1631 num2 = std::numeric_limits<T2>::is_specialized;
1633 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1634 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1637 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1638 enforce(pos <= size(), std::__throw_out_of_range, "");
1639 procrustes(n, size() - pos);
1642 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1647 void swap(basic_fbstring& rhs) {
1648 store_.swap(rhs.store_);
1651 const value_type* c_str() const {
1652 return store_.c_str();
1655 const value_type* data() const { return c_str(); }
1657 allocator_type get_allocator() const {
1658 return allocator_type();
1661 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1662 return find(str.data(), pos, str.length());
1665 size_type find(const value_type* needle, size_type pos, size_type nsize)
1668 size_type find(const value_type* s, size_type pos = 0) const {
1669 return find(s, pos, traits_type::length(s));
1672 size_type find (value_type c, size_type pos = 0) const {
1673 return find(&c, pos, 1);
1676 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1677 return rfind(str.data(), pos, str.length());
1680 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1682 size_type rfind(const value_type* s, size_type pos = npos) const {
1683 return rfind(s, pos, traits_type::length(s));
1686 size_type rfind(value_type c, size_type pos = npos) const {
1687 return rfind(&c, pos, 1);
1690 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1691 return find_first_of(str.data(), pos, str.length());
1694 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1697 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1698 return find_first_of(s, pos, traits_type::length(s));
1701 size_type find_first_of(value_type c, size_type pos = 0) const {
1702 return find_first_of(&c, pos, 1);
1705 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1707 return find_last_of(str.data(), pos, str.length());
1710 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1712 size_type find_last_of (const value_type* s,
1713 size_type pos = npos) const {
1714 return find_last_of(s, pos, traits_type::length(s));
1717 size_type find_last_of (value_type c, size_type pos = npos) const {
1718 return find_last_of(&c, pos, 1);
1721 size_type find_first_not_of(const basic_fbstring& str,
1722 size_type pos = 0) const {
1723 return find_first_not_of(str.data(), pos, str.size());
1726 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1729 size_type find_first_not_of(const value_type* s,
1730 size_type pos = 0) const {
1731 return find_first_not_of(s, pos, traits_type::length(s));
1734 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1735 return find_first_not_of(&c, pos, 1);
1738 size_type find_last_not_of(const basic_fbstring& str,
1739 size_type pos = npos) const {
1740 return find_last_not_of(str.data(), pos, str.length());
1743 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1746 size_type find_last_not_of(const value_type* s,
1747 size_type pos = npos) const {
1748 return find_last_not_of(s, pos, traits_type::length(s));
1751 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1752 return find_last_not_of(&c, pos, 1);
1755 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1756 enforce(pos <= size(), std::__throw_out_of_range, "");
1757 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1760 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1761 enforce(pos <= size(), std::__throw_out_of_range, "");
1766 return std::move(*this);
1769 int compare(const basic_fbstring& str) const {
1770 // FIX due to Goncalo N M de Carvalho July 18, 2005
1771 return compare(0, size(), str);
1774 int compare(size_type pos1, size_type n1,
1775 const basic_fbstring& str) const {
1776 return compare(pos1, n1, str.data(), str.size());
1779 int compare(size_type pos1, size_type n1,
1780 const value_type* s) const {
1781 return compare(pos1, n1, s, traits_type::length(s));
1784 int compare(size_type pos1, size_type n1,
1785 const value_type* s, size_type n2) const {
1786 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1787 procrustes(n1, size() - pos1);
1788 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1789 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1790 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1793 int compare(size_type pos1, size_type n1,
1794 const basic_fbstring& str,
1795 size_type pos2, size_type n2) const {
1796 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1797 return compare(pos1, n1, str.data() + pos2,
1798 std::min(n2, str.size() - pos2));
1801 // Code from Jean-Francois Bastien (03/26/2007)
1802 int compare(const value_type* s) const {
1803 // Could forward to compare(0, size(), s, traits_type::length(s))
1804 // but that does two extra checks
1805 const size_type n1(size()), n2(traits_type::length(s));
1806 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1807 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1815 template <typename E, class T, class A, class S>
1816 inline typename basic_fbstring<E, T, A, S>::size_type
1817 basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1818 return s ? traits_type::length(s)
1819 : (std::__throw_logic_error(
1820 "basic_fbstring: null pointer initializer not valid"),
1824 template <typename E, class T, class A, class S>
1825 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1826 const basic_fbstring& lhs) {
1827 Invariant checker(*this);
1829 if (FBSTRING_UNLIKELY(&lhs == this)) {
1833 return assign(lhs.data(), lhs.size());
1837 template <typename E, class T, class A, class S>
1838 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1839 basic_fbstring&& goner) noexcept {
1840 if (FBSTRING_UNLIKELY(&goner == this)) {
1841 // Compatibility with std::basic_string<>,
1842 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1845 // No need of this anymore
1846 this->~basic_fbstring();
1847 // Move the goner into this
1848 new (&store_) S(std::move(goner.store_));
1852 template <typename E, class T, class A, class S>
1853 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1854 const value_type c) {
1855 Invariant checker(*this);
1858 store_.expandNoinit(1);
1859 } else if (store_.isShared()) {
1860 basic_fbstring(1, c).swap(*this);
1863 store_.shrink(size() - 1);
1869 template <typename E, class T, class A, class S>
1870 inline void basic_fbstring<E, T, A, S>::resize(
1871 const size_type n, const value_type c /*= value_type()*/) {
1872 Invariant checker(*this);
1874 auto size = this->size();
1876 store_.shrink(size - n);
1878 auto const delta = n - size;
1879 auto pData = store_.expandNoinit(delta);
1880 fbstring_detail::podFill(pData, pData + delta, c);
1882 assert(this->size() == n);
1885 template <typename E, class T, class A, class S>
1886 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1887 const basic_fbstring& str) {
1889 auto desiredSize = size() + str.size();
1891 append(str.data(), str.size());
1892 assert(size() == desiredSize);
1896 template <typename E, class T, class A, class S>
1897 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1898 const basic_fbstring& str, const size_type pos, size_type n) {
1899 const size_type sz = str.size();
1900 enforce(pos <= sz, std::__throw_out_of_range, "");
1901 procrustes(n, sz - pos);
1902 return append(str.data() + pos, n);
1905 template <typename E, class T, class A, class S>
1906 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1907 const value_type* s, size_type n) {
1908 Invariant checker(*this);
1910 if (FBSTRING_UNLIKELY(!n)) {
1911 // Unlikely but must be done
1914 auto const oldSize = size();
1915 auto const oldData = data();
1916 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1918 // Check for aliasing (rare). We could use "<=" here but in theory
1919 // those do not work for pointers unless the pointers point to
1920 // elements in the same array. For that reason we use
1921 // std::less_equal, which is guaranteed to offer a total order
1922 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1924 std::less_equal<const value_type*> le;
1925 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1926 assert(le(s + n, oldData + oldSize));
1927 // expandNoinit() could have moved the storage, restore the source.
1928 s = data() + (s - oldData);
1929 fbstring_detail::podMove(s, s + n, pData);
1931 fbstring_detail::podCopy(s, s + n, pData);
1934 assert(size() == oldSize + n);
1938 template <typename E, class T, class A, class S>
1939 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1940 size_type n, value_type c) {
1941 Invariant checker(*this);
1942 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1943 fbstring_detail::podFill(pData, pData + n, c);
1947 template <typename E, class T, class A, class S>
1948 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1949 const basic_fbstring& str, const size_type pos, size_type n) {
1950 const size_type sz = str.size();
1951 enforce(pos <= sz, std::__throw_out_of_range, "");
1952 procrustes(n, sz - pos);
1953 return assign(str.data() + pos, n);
1956 template <typename E, class T, class A, class S>
1957 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
1958 const value_type* s, const size_type n) {
1959 Invariant checker(*this);
1961 // s can alias this, we need to use podMove.
1964 } else if (size() >= n) {
1965 // s can alias this, we need to use podMove.
1966 fbstring_detail::podMove(s, s + n, store_.mutableData());
1967 store_.shrink(size() - n);
1968 assert(size() == n);
1970 // If n is larger than size(), s cannot alias this string's
1973 // Do not use exponential growth here: assign() should be tight,
1974 // to mirror the behavior of the equivalent constructor.
1975 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
1978 assert(size() == n);
1982 #ifndef _LIBSTDCXX_FBSTRING
1983 template <typename E, class T, class A, class S>
1984 inline typename basic_fbstring<E, T, A, S>::istream_type&
1985 basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
1986 Invariant checker(*this);
1991 size_t avail = capacity() - size;
1992 // fbstring has 1 byte extra capacity for the null terminator,
1993 // and getline null-terminates the read string.
1994 is.getline(store_.expandNoinit(avail), avail + 1, delim);
1995 size += is.gcount();
1997 if (is.bad() || is.eof() || !is.fail()) {
1998 // Done by either failure, end of file, or normal read.
1999 if (!is.bad() && !is.eof()) {
2000 --size; // gcount() also accounts for the delimiter.
2006 assert(size == this->size());
2007 assert(size == capacity());
2008 // Start at minimum allocation 63 + terminator = 64.
2009 reserve(std::max<size_t>(63, 3 * size / 2));
2010 // Clear the error so we can continue reading.
2017 template <typename E, class T, class A, class S>
2018 inline typename basic_fbstring<E, T, A, S>::size_type
2019 basic_fbstring<E, T, A, S>::find(
2020 const value_type* needle, const size_type pos, const size_type nsize)
2022 auto const size = this->size();
2023 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2024 // that nsize + pos does not wrap around.
2025 if (nsize + pos > size || nsize + pos < pos) {
2032 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2033 // the last characters first
2034 auto const haystack = data();
2035 auto const nsize_1 = nsize - 1;
2036 auto const lastNeedle = needle[nsize_1];
2038 // Boyer-Moore skip value for the last char in the needle. Zero is
2039 // not a valid value; skip will be computed the first time it's
2043 const E* i = haystack + pos;
2044 auto iEnd = haystack + size - nsize_1;
2047 // Boyer-Moore: match the last element in the needle
2048 while (i[nsize_1] != lastNeedle) {
2054 // Here we know that the last char matches
2055 // Continue in pedestrian mode
2056 for (size_t j = 0;;) {
2058 if (i[j] != needle[j]) {
2059 // Not found, we can skip
2060 // Compute the skip value lazily
2063 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2070 // Check if done searching
2073 return i - haystack;
2080 template <typename E, class T, class A, class S>
2081 inline typename basic_fbstring<E, T, A, S>::iterator
2082 basic_fbstring<E, T, A, S>::insertImplDiscr(
2083 const_iterator i, size_type n, value_type c, std::true_type) {
2084 Invariant checker(*this);
2086 assert(i >= cbegin() && i <= cend());
2087 const size_type pos = i - cbegin();
2089 auto oldSize = size();
2090 store_.expandNoinit(n, /* expGrowth = */ true);
2092 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2093 fbstring_detail::podFill(b + pos, b + pos + n, c);
2098 template <typename E, class T, class A, class S>
2099 template <class InputIter>
2100 inline typename basic_fbstring<E, T, A, S>::iterator
2101 basic_fbstring<E, T, A, S>::insertImplDiscr(
2102 const_iterator i, InputIter b, InputIter e, std::false_type) {
2104 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2107 template <typename E, class T, class A, class S>
2108 template <class FwdIterator>
2109 inline typename basic_fbstring<E, T, A, S>::iterator
2110 basic_fbstring<E, T, A, S>::insertImpl(
2114 std::forward_iterator_tag) {
2115 Invariant checker(*this);
2117 assert(i >= cbegin() && i <= cend());
2118 const size_type pos = i - cbegin();
2119 auto n = std::distance(s1, s2);
2122 auto oldSize = size();
2123 store_.expandNoinit(n, /* expGrowth = */ true);
2125 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2126 std::copy(s1, s2, b + pos);
2131 template <typename E, class T, class A, class S>
2132 template <class InputIterator>
2133 inline typename basic_fbstring<E, T, A, S>::iterator
2134 basic_fbstring<E, T, A, S>::insertImpl(
2138 std::input_iterator_tag) {
2139 const auto pos = i - cbegin();
2140 basic_fbstring temp(cbegin(), i);
2141 for (; b != e; ++b) {
2144 temp.append(i, cend());
2146 return begin() + pos;
2149 template <typename E, class T, class A, class S>
2150 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2153 const value_type* s,
2155 std::integral_constant<int, 2>) {
2157 assert(begin() <= i1 && i1 <= end());
2158 assert(begin() <= i2 && i2 <= end());
2159 return replace(i1, i2, s, s + n);
2162 template <typename E, class T, class A, class S>
2163 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2168 std::integral_constant<int, 1>) {
2169 const size_type n1 = i2 - i1;
2171 std::fill(i1, i1 + n2, c);
2174 std::fill(i1, i2, c);
2175 insert(i2, n2 - n1, c);
2181 template <typename E, class T, class A, class S>
2182 template <class InputIter>
2183 inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2188 std::integral_constant<int, 0>) {
2189 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2190 replaceImpl(i1, i2, b, e, Cat());
2194 template <typename E, class T, class A, class S>
2195 template <class FwdIterator>
2196 inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2197 iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
2198 std::less_equal<const value_type*> le{};
2199 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2203 // Aliased replace, copy to new string
2204 basic_fbstring temp;
2205 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2206 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2211 template <typename E, class T, class A, class S>
2212 template <class FwdIterator>
2213 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2218 std::forward_iterator_tag) {
2219 Invariant checker(*this);
2221 // Handle aliased replace
2222 using Sel = std::integral_constant<
2224 std::is_same<FwdIterator, iterator>::value ||
2225 std::is_same<FwdIterator, const_iterator>::value>;
2226 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2230 auto const n1 = i2 - i1;
2232 auto const n2 = std::distance(s1, s2);
2237 std::copy(s1, s2, i1);
2241 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2247 template <typename E, class T, class A, class S>
2248 template <class InputIterator>
2249 inline void basic_fbstring<E, T, A, S>::replaceImpl(
2254 std::input_iterator_tag) {
2255 basic_fbstring temp(begin(), i1);
2256 temp.append(b, e).append(i2, end());
2260 template <typename E, class T, class A, class S>
2261 inline typename basic_fbstring<E, T, A, S>::size_type
2262 basic_fbstring<E, T, A, S>::rfind(
2263 const value_type* s, size_type pos, size_type n) const {
2267 pos = std::min(pos, length() - n);
2272 const_iterator i(begin() + pos);
2274 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2284 template <typename E, class T, class A, class S>
2285 inline typename basic_fbstring<E, T, A, S>::size_type
2286 basic_fbstring<E, T, A, S>::find_first_of(
2287 const value_type* s, size_type pos, size_type n) const {
2288 if (pos > length() || n == 0) {
2291 const_iterator i(begin() + pos), finish(end());
2292 for (; i != finish; ++i) {
2293 if (traits_type::find(s, n, *i) != 0) {
2300 template <typename E, class T, class A, class S>
2301 inline typename basic_fbstring<E, T, A, S>::size_type
2302 basic_fbstring<E, T, A, S>::find_last_of(
2303 const value_type* s, size_type pos, size_type n) const {
2304 if (!empty() && n > 0) {
2305 pos = std::min(pos, length() - 1);
2306 const_iterator i(begin() + pos);
2308 if (traits_type::find(s, n, *i) != 0) {
2319 template <typename E, class T, class A, class S>
2320 inline typename basic_fbstring<E, T, A, S>::size_type
2321 basic_fbstring<E, T, A, S>::find_first_not_of(
2322 const value_type* s, size_type pos, size_type n) const {
2323 if (pos < length()) {
2324 const_iterator i(begin() + pos), finish(end());
2325 for (; i != finish; ++i) {
2326 if (traits_type::find(s, n, *i) == 0) {
2334 template <typename E, class T, class A, class S>
2335 inline typename basic_fbstring<E, T, A, S>::size_type
2336 basic_fbstring<E, T, A, S>::find_last_not_of(
2337 const value_type* s, size_type pos, size_type n) const {
2338 if (!this->empty()) {
2339 pos = std::min(pos, size() - 1);
2340 const_iterator i(begin() + pos);
2342 if (traits_type::find(s, n, *i) == 0) {
2353 // non-member functions
2355 template <typename E, class T, class A, class S>
2357 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2358 const basic_fbstring<E, T, A, S>& rhs) {
2360 basic_fbstring<E, T, A, S> result;
2361 result.reserve(lhs.size() + rhs.size());
2362 result.append(lhs).append(rhs);
2363 return std::move(result);
2367 template <typename E, class T, class A, class S>
2369 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2370 const basic_fbstring<E, T, A, S>& rhs) {
2371 return std::move(lhs.append(rhs));
2375 template <typename E, class T, class A, class S>
2377 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2378 basic_fbstring<E, T, A, S>&& rhs) {
2379 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2380 // Good, at least we don't need to reallocate
2381 return std::move(rhs.insert(0, lhs));
2383 // Meh, no go. Forward to operator+(const&, const&).
2384 auto const& rhsC = rhs;
2389 template <typename E, class T, class A, class S>
2391 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2392 basic_fbstring<E, T, A, S>&& rhs) {
2393 return std::move(lhs.append(rhs));
2397 template <typename E, class T, class A, class S>
2399 basic_fbstring<E, T, A, S> operator+(
2401 const basic_fbstring<E, T, A, S>& rhs) {
2403 basic_fbstring<E, T, A, S> result;
2404 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2405 result.reserve(len + rhs.size());
2406 result.append(lhs, len).append(rhs);
2411 template <typename E, class T, class A, class S>
2413 basic_fbstring<E, T, A, S> operator+(
2415 basic_fbstring<E, T, A, S>&& rhs) {
2417 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2418 if (rhs.capacity() >= len + rhs.size()) {
2419 // Good, at least we don't need to reallocate
2420 rhs.insert(rhs.begin(), lhs, lhs + len);
2423 // Meh, no go. Do it by hand since we have len already.
2424 basic_fbstring<E, T, A, S> result;
2425 result.reserve(len + rhs.size());
2426 result.append(lhs, len).append(rhs);
2431 template <typename E, class T, class A, class S>
2433 basic_fbstring<E, T, A, S> operator+(
2435 const basic_fbstring<E, T, A, S>& rhs) {
2437 basic_fbstring<E, T, A, S> result;
2438 result.reserve(1 + rhs.size());
2439 result.push_back(lhs);
2445 template <typename E, class T, class A, class S>
2447 basic_fbstring<E, T, A, S> operator+(
2449 basic_fbstring<E, T, A, S>&& rhs) {
2451 if (rhs.capacity() > rhs.size()) {
2452 // Good, at least we don't need to reallocate
2453 rhs.insert(rhs.begin(), lhs);
2456 // Meh, no go. Forward to operator+(E, const&).
2457 auto const& rhsC = rhs;
2462 template <typename E, class T, class A, class S>
2464 basic_fbstring<E, T, A, S> operator+(
2465 const basic_fbstring<E, T, A, S>& lhs,
2468 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2469 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2471 basic_fbstring<E, T, A, S> result;
2472 const size_type len = traits_type::length(rhs);
2473 result.reserve(lhs.size() + len);
2474 result.append(lhs).append(rhs, len);
2478 // C++11 21.4.8.1/10
2479 template <typename E, class T, class A, class S>
2481 basic_fbstring<E, T, A, S> operator+(
2482 basic_fbstring<E, T, A, S>&& lhs,
2485 return std::move(lhs += rhs);
2488 // C++11 21.4.8.1/11
2489 template <typename E, class T, class A, class S>
2491 basic_fbstring<E, T, A, S> operator+(
2492 const basic_fbstring<E, T, A, S>& lhs,
2495 basic_fbstring<E, T, A, S> result;
2496 result.reserve(lhs.size() + 1);
2498 result.push_back(rhs);
2502 // C++11 21.4.8.1/12
2503 template <typename E, class T, class A, class S>
2505 basic_fbstring<E, T, A, S> operator+(
2506 basic_fbstring<E, T, A, S>&& lhs,
2509 return std::move(lhs += rhs);
2512 template <typename E, class T, class A, class S>
2514 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2515 const basic_fbstring<E, T, A, S>& rhs) {
2516 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2518 template <typename E, class T, class A, class S>
2520 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2521 const basic_fbstring<E, T, A, S>& rhs) {
2522 return rhs == lhs; }
2524 template <typename E, class T, class A, class S>
2526 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2527 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2528 return lhs.compare(rhs) == 0; }
2530 template <typename E, class T, class A, class S>
2532 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2533 const basic_fbstring<E, T, A, S>& rhs) {
2534 return !(lhs == rhs); }
2536 template <typename E, class T, class A, class S>
2538 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2539 const basic_fbstring<E, T, A, S>& rhs) {
2540 return !(lhs == rhs); }
2542 template <typename E, class T, class A, class S>
2544 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2545 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2546 return !(lhs == rhs); }
2548 template <typename E, class T, class A, class S>
2550 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2551 const basic_fbstring<E, T, A, S>& rhs) {
2552 return lhs.compare(rhs) < 0; }
2554 template <typename E, class T, class A, class S>
2556 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2557 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2558 return lhs.compare(rhs) < 0; }
2560 template <typename E, class T, class A, class S>
2562 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2563 const basic_fbstring<E, T, A, S>& rhs) {
2564 return rhs.compare(lhs) > 0; }
2566 template <typename E, class T, class A, class S>
2568 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2569 const basic_fbstring<E, T, A, S>& rhs) {
2572 template <typename E, class T, class A, class S>
2574 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2575 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2578 template <typename E, class T, class A, class S>
2580 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2581 const basic_fbstring<E, T, A, S>& rhs) {
2584 template <typename E, class T, class A, class S>
2586 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2587 const basic_fbstring<E, T, A, S>& rhs) {
2588 return !(rhs < lhs); }
2590 template <typename E, class T, class A, class S>
2592 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2593 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2594 return !(rhs < lhs); }
2596 template <typename E, class T, class A, class S>
2598 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2599 const basic_fbstring<E, T, A, S>& rhs) {
2600 return !(rhs < lhs); }
2602 template <typename E, class T, class A, class S>
2604 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2605 const basic_fbstring<E, T, A, S>& rhs) {
2606 return !(lhs < rhs); }
2608 template <typename E, class T, class A, class S>
2610 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2611 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2612 return !(lhs < rhs); }
2614 template <typename E, class T, class A, class S>
2616 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2617 const basic_fbstring<E, T, A, S>& rhs) {
2618 return !(lhs < rhs);
2622 template <typename E, class T, class A, class S>
2623 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2627 // TODO: make this faster.
2628 template <typename E, class T, class A, class S>
2631 typename basic_fbstring<E, T, A, S>::value_type,
2632 typename basic_fbstring<E, T, A, S>::traits_type>&
2634 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2635 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2636 basic_fbstring<E, T, A, S>& str) {
2637 typename std::basic_istream<E, T>::sentry sentry(is);
2638 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2639 typename basic_fbstring<E, T, A, S>::traits_type>
2641 typedef typename __istream_type::ios_base __ios_base;
2642 size_t extracted = 0;
2643 auto err = __ios_base::goodbit;
2645 auto n = is.width();
2650 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2651 if (got == T::eof()) {
2652 err |= __ios_base::eofbit;
2660 got = is.rdbuf()->snextc();
2664 err |= __ios_base::failbit;
2672 template <typename E, class T, class A, class S>
2674 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2675 typename basic_fbstring<E, T, A, S>::traits_type>&
2677 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2678 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2679 const basic_fbstring<E, T, A, S>& str) {
2681 typename std::basic_ostream<
2682 typename basic_fbstring<E, T, A, S>::value_type,
2683 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2685 typedef std::ostreambuf_iterator<
2686 typename basic_fbstring<E, T, A, S>::value_type,
2687 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2688 size_t __len = str.size();
2690 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2691 if (__pad_and_output(_Ip(os),
2693 __left ? str.data() + __len : str.data(),
2696 os.fill()).failed()) {
2697 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2700 #elif defined(_MSC_VER)
2701 // MSVC doesn't define __ostream_insert
2702 os.write(str.data(), str.size());
2704 std::__ostream_insert(os, str.data(), str.size());
2709 template <typename E1, class T, class A, class S>
2710 constexpr typename basic_fbstring<E1, T, A, S>::size_type
2711 basic_fbstring<E1, T, A, S>::npos;
2713 #ifndef _LIBSTDCXX_FBSTRING
2714 // basic_string compatibility routines
2716 template <typename E, class T, class A, class S>
2718 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2719 const std::string& rhs) {
2720 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2723 template <typename E, class T, class A, class S>
2725 bool operator==(const std::string& lhs,
2726 const basic_fbstring<E, T, A, S>& rhs) {
2730 template <typename E, class T, class A, class S>
2732 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2733 const std::string& rhs) {
2734 return !(lhs == rhs);
2737 template <typename E, class T, class A, class S>
2739 bool operator!=(const std::string& lhs,
2740 const basic_fbstring<E, T, A, S>& rhs) {
2741 return !(lhs == rhs);
2744 #if !defined(_LIBSTDCXX_FBSTRING)
2745 typedef basic_fbstring<char> fbstring;
2748 // fbstring is relocatable
2749 template <class T, class R, class A, class S>
2750 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2753 _GLIBCXX_END_NAMESPACE_VERSION
2756 } // namespace folly
2758 #ifndef _LIBSTDCXX_FBSTRING
2760 // Hash functions to make fbstring usable with e.g. hash_map
2762 // Handle interaction with different C++ standard libraries, which
2763 // expect these types to be in different namespaces.
2765 #define FOLLY_FBSTRING_HASH1(T) \
2767 struct hash< ::folly::basic_fbstring<T>> { \
2768 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2769 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2773 // The C++11 standard says that these four are defined
2774 #define FOLLY_FBSTRING_HASH \
2775 FOLLY_FBSTRING_HASH1(char) \
2776 FOLLY_FBSTRING_HASH1(char16_t) \
2777 FOLLY_FBSTRING_HASH1(char32_t) \
2778 FOLLY_FBSTRING_HASH1(wchar_t)
2786 #if FOLLY_HAVE_DEPRECATED_ASSOC
2787 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2788 namespace __gnu_cxx {
2792 } // namespace __gnu_cxx
2793 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2794 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2796 #undef FOLLY_FBSTRING_HASH
2797 #undef FOLLY_FBSTRING_HASH1
2799 #endif // _LIBSTDCXX_FBSTRING
2801 #pragma GCC diagnostic pop
2803 #undef FBSTRING_DISABLE_SSO
2804 #undef FBSTRING_SANITIZE_ADDRESS
2806 #undef FBSTRING_LIKELY
2807 #undef FBSTRING_UNLIKELY
2809 #ifdef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2811 #undef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2812 #endif // FOLLY_DEFINED_NDEBUG_FOR_FBSTRING