2 * Copyright 2015 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)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
25 #include <type_traits>
27 // This file appears in two locations: inside fbcode and in the
28 // libstdc++ source code (when embedding fbstring as std::string).
29 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
30 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
31 #ifdef _LIBSTDCXX_FBSTRING
33 #pragma GCC system_header
35 // When used as std::string replacement always disable assertions.
38 #define FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
41 // Handle the cases where the fbcode version (folly/Malloc.h) is included
42 // either before or after this inclusion.
43 #ifdef FOLLY_MALLOC_H_
44 #undef FOLLY_MALLOC_H_
45 #include "basic_fbstring_malloc.h" // nolint
47 #include "basic_fbstring_malloc.h" // nolint
48 #undef FOLLY_MALLOC_H_
51 #else // !_LIBSTDCXX_FBSTRING
53 #include <folly/Portability.h>
55 // libc++ doesn't provide this header, nor does msvc
56 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
57 #include <bits/c++config.h>
65 #include <folly/Traits.h>
66 #include <folly/Malloc.h>
67 #include <folly/Hash.h>
68 #include <folly/ScopeGuard.h>
70 #if FOLLY_HAVE_DEPRECATED_ASSOC
71 #ifdef _GLIBCXX_SYMVER
72 #include <ext/hash_set>
73 #include <ext/hash_map>
79 // We defined these here rather than including Likely.h to avoid
80 // redefinition errors when fbstring is imported into libstdc++.
81 #if defined(__GNUC__) && __GNUC__ >= 4
82 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
83 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
85 #define FBSTRING_LIKELY(x) (x)
86 #define FBSTRING_UNLIKELY(x) (x)
89 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
90 #pragma GCC diagnostic push
91 #pragma GCC diagnostic ignored "-Wshadow"
93 // FBString cannot use throw when replacing std::string, though it may still
96 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
98 #ifdef _LIBSTDCXX_FBSTRING
99 namespace std _GLIBCXX_VISIBILITY(default) {
100 _GLIBCXX_BEGIN_NAMESPACE_VERSION
105 // Different versions of gcc/clang support different versions of
106 // the address sanitizer attribute. Unfortunately, this attribute
107 // has issues when inlining is used, so disable that as well.
108 #if defined(__clang__)
109 # if __has_feature(address_sanitizer)
110 # if __has_attribute(__no_sanitize__)
111 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
112 __attribute__((__no_sanitize__("address"), __noinline__))
113 # elif __has_attribute(__no_address_safety_analysis__)
114 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
115 __attribute__((__no_address_safety_analysis__, __noinline__))
116 # elif __has_attribute(__no_sanitize_address__)
117 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
118 __attribute__((__no_sanitize_address__, __noinline__))
121 #elif defined (__GNUC__) && \
123 (__GNUC_MINOR__ >= 8) && \
125 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
126 __attribute__((__no_address_safety_analysis__, __noinline__))
128 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
129 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
132 namespace fbstring_detail {
134 template <class InIt, class OutIt>
137 typename std::iterator_traits<InIt>::difference_type n,
139 for (; n != 0; --n, ++b, ++d) {
145 template <class Pod, class T>
146 inline void pod_fill(Pod* b, Pod* e, T c) {
147 assert(b && e && b <= e);
148 /*static*/ if (sizeof(T) == 1) {
151 auto const ee = b + ((e - b) & ~7u);
152 for (; b != ee; b += 8) {
163 for (; b != e; ++b) {
170 * Lightly structured memcpy, simplifies copying PODs and introduces
171 * some asserts. Unfortunately using this function may cause
172 * measurable overhead (presumably because it adjusts from a begin/end
173 * convention to a pointer/size convention, so it does some extra
174 * arithmetic even though the caller might have done the inverse
175 * adaptation outside).
178 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
180 assert(d >= e || d + (e - b) <= b);
181 memcpy(d, b, (e - b) * sizeof(Pod));
185 * Lightly structured memmove, simplifies copying PODs and introduces
189 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
191 memmove(d, b, (e - b) * sizeof(*b));
194 } // namespace fbstring_detail
197 * Defines a special acquisition method for constructing fbstring
198 * objects. AcquireMallocatedString means that the user passes a
199 * pointer to a malloc-allocated string that the fbstring object will
202 enum class AcquireMallocatedString {};
205 * fbstring_core_model is a mock-up type that defines all required
206 * signatures of a fbstring core. The fbstring class itself uses such
207 * a core object to implement all of the numerous member functions
208 * required by the standard.
210 * If you want to define a new core, copy the definition below and
211 * implement the primitives. Then plug the core into basic_fbstring as
212 * a template argument.
214 template <class Char>
215 class fbstring_core_model {
217 fbstring_core_model();
218 fbstring_core_model(const fbstring_core_model &);
219 ~fbstring_core_model();
220 // Returns a pointer to string's buffer (currently only contiguous
221 // strings are supported). The pointer is guaranteed to be valid
222 // until the next call to a non-const member function.
223 const Char * data() const;
224 // Much like data(), except the string is prepared to support
225 // character-level changes. This call is a signal for
226 // e.g. reference-counted implementation to fork the data. The
227 // pointer is guaranteed to be valid until the next call to a
228 // non-const member function.
229 Char * mutable_data();
230 // Returns a pointer to string's buffer and guarantees that a
231 // readable '\0' lies right after the buffer. The pointer is
232 // guaranteed to be valid until the next call to a non-const member
234 const Char * c_str() const;
235 // Shrinks the string by delta characters. Asserts that delta <=
237 void shrink(size_t delta);
238 // Expands the string by delta characters (i.e. after this call
239 // size() will report the old size() plus delta) but without
240 // initializing the expanded region. Returns a pointer to the memory
241 // to be initialized (the beginning of the expanded portion). The
242 // caller is expected to fill the expanded area appropriately.
243 Char* expand_noinit(size_t delta);
244 // Expands the string by one character and sets the last character
246 void push_back(Char c);
247 // Returns the string's size.
249 // Returns the string's capacity, i.e. maximum size that the string
250 // can grow to without reallocation. Note that for reference counted
251 // strings that's technically a lie - even assigning characters
252 // within the existing size would cause a reallocation.
253 size_t capacity() const;
254 // Returns true if the data underlying the string is actually shared
255 // across multiple strings (in a refcounted fashion).
256 bool isShared() const;
257 // Makes sure that at least minCapacity characters are available for
258 // the string without reallocation. For reference-counted strings,
259 // it should fork the data even if minCapacity < size().
260 void reserve(size_t minCapacity);
263 fbstring_core_model& operator=(const fbstring_core_model &);
268 * This is the core of the string. The code should work on 32- and
269 * 64-bit and both big- and little-endianan architectures with any
272 * The storage is selected as follows (assuming we store one-byte
273 * characters on a 64-bit machine): (a) "small" strings between 0 and
274 * 23 chars are stored in-situ without allocation (the rightmost byte
275 * stores the size); (b) "medium" strings from 24 through 254 chars
276 * are stored in malloc-allocated memory that is copied eagerly; (c)
277 * "large" strings of 255 chars and above are stored in a similar
278 * structure as medium arrays, except that the string is
279 * reference-counted and copied lazily. the reference count is
280 * allocated right before the character array.
282 * The discriminator between these three strategies sits in two
283 * bits of the rightmost char of the storage. If neither is set, then the
284 * string is small (and its length sits in the lower-order bits on
285 * little-endian or the high-order bits on big-endian of that
286 * rightmost character). If the MSb is set, the string is medium width.
287 * If the second MSb is set, then the string is large. On little-endian,
288 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
289 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
290 * and big-endian fbstring_core equivalent with merely different ops used
291 * to extract capacity/category.
293 template <class Char> class fbstring_core {
295 static constexpr bool kIsLittleEndian =
296 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
297 static constexpr bool kIsBigEndian =
298 __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__;
300 kIsLittleEndian || kIsBigEndian, "unable to identify endianness");
302 fbstring_core() noexcept { reset(); }
304 fbstring_core(const fbstring_core & rhs) {
305 assert(&rhs != this);
306 // Simplest case first: small strings are bitblitted
307 if (rhs.category() == Category::isSmall) {
308 static_assert(offsetof(MediumLarge, data_) == 0,
309 "fbstring layout failure");
310 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
311 "fbstring layout failure");
312 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
313 "fbstring layout failure");
314 // Just write the whole thing, don't look at details. In
315 // particular we need to copy capacity anyway because we want
316 // to set the size (don't forget that the last character,
317 // which stores a short string's length, is shared with the
318 // ml_.capacity field).
320 assert(category() == Category::isSmall && this->size() == rhs.size());
321 } else if (rhs.category() == Category::isLarge) {
322 // Large strings are just refcounted
324 RefCounted::incrementRefs(ml_.data_);
325 assert(category() == Category::isLarge && size() == rhs.size());
327 // Medium strings are copied eagerly. Don't forget to allocate
328 // one extra Char for the null terminator.
329 auto const allocSize =
330 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
331 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
332 fbstring_detail::pod_copy(rhs.ml_.data_,
334 rhs.ml_.data_ + rhs.ml_.size_ + 1,
336 // No need for writeTerminator() here, we copied one extra
337 // element just above.
338 ml_.size_ = rhs.ml_.size_;
339 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
340 assert(category() == Category::isMedium);
342 assert(size() == rhs.size());
343 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
346 fbstring_core(fbstring_core&& goner) noexcept {
349 if (goner.category() != Category::isSmall) {
350 // Clean goner's carcass
355 // NOTE(agallagher): The word-aligned copy path copies bytes which are
356 // outside the range of the string, and makes address sanitizer unhappy,
357 // so just disable it on this function.
358 fbstring_core(const Char *const data, const size_t size)
359 FBSTRING_DISABLE_ADDRESS_SANITIZER {
361 #ifndef _LIBSTDCXX_FBSTRING
363 assert(this->size() == size);
364 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
369 // Simplest case first: small strings are bitblitted
370 if (size <= maxSmallSize) {
371 // Layout is: Char* data_, size_t size_, size_t capacity_
372 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
373 "fbstring has unexpected size");
374 static_assert(sizeof(Char*) == sizeof(size_t),
375 "fbstring size assumption violation");
376 // sizeof(size_t) must be a power of 2
377 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
378 "fbstring size assumption violation");
380 // If data is aligned, use fast word-wise copying. Otherwise,
381 // use conservative memcpy.
382 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
383 fbstring_detail::pod_copy(data, data + size, small_);
385 // Copy one word (64 bits) at a time
386 const size_t byteSize = size * sizeof(Char);
387 if (byteSize > 2 * sizeof(size_t)) {
389 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
391 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
393 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
394 } else if (byteSize > sizeof(size_t)) {
397 } else if (size > 0) {
404 } else if (size <= maxMediumSize) {
405 // Medium strings are allocated normally. Don't forget to
406 // allocate one extra Char for the terminating null.
407 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
408 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
409 fbstring_detail::pod_copy(data, data + size, ml_.data_);
411 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
413 // Large strings are allocated differently
414 size_t effectiveCapacity = size;
415 auto const newRC = RefCounted::create(data, & effectiveCapacity);
416 ml_.data_ = newRC->data_;
418 ml_.setCapacity(effectiveCapacity, Category::isLarge);
423 ~fbstring_core() noexcept {
424 auto const c = category();
425 if (c == Category::isSmall) {
428 if (c == Category::isMedium) {
432 RefCounted::decrementRefs(ml_.data_);
435 // Snatches a previously mallocated string. The parameter "size"
436 // is the size of the string, and the parameter "allocatedSize"
437 // is the size of the mallocated block. The string must be
438 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
440 // So if you want a 2-character string, pass malloc(3) as "data",
441 // pass 2 as "size", and pass 3 as "allocatedSize".
442 fbstring_core(Char * const data,
444 const size_t allocatedSize,
445 AcquireMallocatedString) {
447 assert(allocatedSize >= size + 1);
448 assert(data[size] == '\0');
449 // Use the medium string storage
452 // Don't forget about null terminator
453 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
455 // No need for the memory
461 // swap below doesn't test whether &rhs == this (and instead
462 // potentially does extra work) on the premise that the rarity of
463 // that situation actually makes the check more expensive than is
465 void swap(fbstring_core & rhs) {
471 // In C++11 data() and c_str() are 100% equivalent.
472 const Char * data() const {
476 Char * mutable_data() {
477 auto const c = category();
478 if (c == Category::isSmall) {
481 assert(c == Category::isMedium || c == Category::isLarge);
482 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
484 size_t effectiveCapacity = ml_.capacity();
485 auto const newRC = RefCounted::create(& effectiveCapacity);
486 // If this fails, someone placed the wrong capacity in an
488 assert(effectiveCapacity >= ml_.capacity());
489 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
491 RefCounted::decrementRefs(ml_.data_);
492 ml_.data_ = newRC->data_;
493 // No need to call writeTerminator(), we have + 1 above.
498 const Char * c_str() const {
499 auto const c = category();
500 if (c == Category::isSmall) {
501 assert(small_[smallSize()] == '\0');
504 assert(c == Category::isMedium || c == Category::isLarge);
505 assert(ml_.data_[ml_.size_] == '\0');
509 void shrink(const size_t delta) {
510 if (category() == Category::isSmall) {
511 // Check for underflow
512 assert(delta <= smallSize());
513 setSmallSize(smallSize() - delta);
514 } else if (category() == Category::isMedium ||
515 RefCounted::refs(ml_.data_) == 1) {
516 // Medium strings and unique large strings need no special
518 assert(ml_.size_ >= delta);
522 assert(ml_.size_ >= delta);
523 // Shared large string, must make unique. This is because of the
524 // durn terminator must be written, which may trample the shared
527 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
529 // No need to write the terminator.
533 void reserve(size_t minCapacity) {
534 if (category() == Category::isLarge) {
536 if (RefCounted::refs(ml_.data_) > 1) {
537 // We must make it unique regardless; in-place reallocation is
538 // useless if the string is shared. In order to not surprise
539 // people, reserve the new block at current capacity or
540 // more. That way, a string's capacity never shrinks after a
542 minCapacity = std::max(minCapacity, ml_.capacity());
543 auto const newRC = RefCounted::create(& minCapacity);
544 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
546 // Done with the old data. No need to call writeTerminator(),
547 // we have + 1 above.
548 RefCounted::decrementRefs(ml_.data_);
549 ml_.data_ = newRC->data_;
550 ml_.setCapacity(minCapacity, Category::isLarge);
551 // size remains unchanged
553 // String is not shared, so let's try to realloc (if needed)
554 if (minCapacity > ml_.capacity()) {
555 // Asking for more memory
557 RefCounted::reallocate(ml_.data_, ml_.size_,
558 ml_.capacity(), minCapacity);
559 ml_.data_ = newRC->data_;
560 ml_.setCapacity(minCapacity, Category::isLarge);
563 assert(capacity() >= minCapacity);
565 } else if (category() == Category::isMedium) {
566 // String is not shared
567 if (minCapacity <= ml_.capacity()) {
568 return; // nothing to do, there's enough room
570 if (minCapacity <= maxMediumSize) {
571 // Keep the string at medium size. Don't forget to allocate
572 // one extra Char for the terminating null.
573 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
574 ml_.data_ = static_cast<Char *>(
577 ml_.size_ * sizeof(Char),
578 (ml_.capacity() + 1) * sizeof(Char),
581 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
583 // Conversion from medium to large string
584 fbstring_core nascent;
585 // Will recurse to another branch of this function
586 nascent.reserve(minCapacity);
587 nascent.ml_.size_ = ml_.size_;
588 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
592 assert(capacity() >= minCapacity);
595 assert(category() == Category::isSmall);
596 if (minCapacity > maxMediumSize) {
598 auto const newRC = RefCounted::create(& minCapacity);
599 auto const size = smallSize();
600 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
601 // No need for writeTerminator(), we wrote it above with + 1.
602 ml_.data_ = newRC->data_;
604 ml_.setCapacity(minCapacity, Category::isLarge);
605 assert(capacity() >= minCapacity);
606 } else if (minCapacity > maxSmallSize) {
608 // Don't forget to allocate one extra Char for the terminating null
609 auto const allocSizeBytes =
610 goodMallocSize((1 + minCapacity) * sizeof(Char));
611 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
612 auto const size = smallSize();
613 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
614 // No need for writeTerminator(), we wrote it above with + 1.
617 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
620 // Nothing to do, everything stays put
623 assert(capacity() >= minCapacity);
626 Char * expand_noinit(const size_t delta) {
627 // Strategy is simple: make room, then change size
628 assert(capacity() >= size());
630 if (category() == Category::isSmall) {
633 if (newSz <= maxSmallSize) {
640 newSz = ml_.size_ + delta;
641 if (newSz > capacity()) {
645 assert(capacity() >= newSz);
646 // Category can't be small - we took care of that above
647 assert(category() == Category::isMedium || category() == Category::isLarge);
650 assert(size() == newSz);
651 return ml_.data_ + sz;
654 void push_back(Char c) {
655 assert(capacity() >= size());
657 if (category() == Category::isSmall) {
659 if (sz < maxSmallSize) {
661 setSmallSize(sz + 1);
664 reserve(maxSmallSize * 2);
667 if (sz == capacity()) { // always true for isShared()
668 reserve(1 + sz * 3 / 2); // ensures not shared
672 assert(capacity() >= sz + 1);
673 // Category can't be small - we took care of that above
674 assert(category() == Category::isMedium || category() == Category::isLarge);
680 size_t size() const {
681 return category() == Category::isSmall ? smallSize() : ml_.size_;
684 size_t capacity() const {
685 switch (category()) {
686 case Category::isSmall:
688 case Category::isLarge:
689 // For large-sized strings, a multi-referenced chunk has no
690 // available capacity. This is because any attempt to append
691 // data would trigger a new allocation.
692 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
695 return ml_.capacity();
698 bool isShared() const {
699 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
702 void writeTerminator() {
703 if (category() == Category::isSmall) {
704 const auto s = smallSize();
705 if (s != maxSmallSize) {
709 ml_.data_[ml_.size_] = '\0';
715 fbstring_core & operator=(const fbstring_core & rhs);
717 // Equivalent to setSmallSize(0), but with specialized
718 // writeTerminator which doesn't re-check the category after
719 // capacity_ is overwritten.
721 // Only initialize the tag, will set the MSBs (i.e. the small
722 // string size) to zero too.
723 ml_.capacity_ = kIsLittleEndian
724 ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
727 assert(category() == Category::isSmall && size() == 0);
731 std::atomic<size_t> refCount_;
734 static RefCounted * fromData(Char * p) {
735 return static_cast<RefCounted*>(
737 static_cast<unsigned char*>(static_cast<void*>(p))
738 - sizeof(refCount_)));
741 static size_t refs(Char * p) {
742 return fromData(p)->refCount_.load(std::memory_order_acquire);
745 static void incrementRefs(Char * p) {
746 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
749 static void decrementRefs(Char * p) {
750 auto const dis = fromData(p);
751 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
758 static RefCounted * create(size_t * size) {
759 // Don't forget to allocate one extra Char for the terminating
760 // null. In this case, however, one Char is already part of the
762 const size_t allocSize = goodMallocSize(
763 sizeof(RefCounted) + *size * sizeof(Char));
764 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
765 result->refCount_.store(1, std::memory_order_release);
766 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
770 static RefCounted * create(const Char * data, size_t * size) {
771 const size_t effectiveSize = *size;
772 auto result = create(size);
773 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
777 static RefCounted * reallocate(Char *const data,
778 const size_t currentSize,
779 const size_t currentCapacity,
780 const size_t newCapacity) {
781 assert(newCapacity > 0 && newCapacity > currentSize);
782 auto const dis = fromData(data);
783 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
784 // Don't forget to allocate one extra Char for the terminating
785 // null. In this case, however, one Char is already part of the
787 auto result = static_cast<RefCounted*>(
789 sizeof(RefCounted) + currentSize * sizeof(Char),
790 sizeof(RefCounted) + currentCapacity * sizeof(Char),
791 sizeof(RefCounted) + newCapacity * sizeof(Char)));
792 assert(result->refCount_.load(std::memory_order_acquire) == 1);
797 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
800 enum class Category : category_type {
802 isMedium = kIsLittleEndian
803 ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
805 isLarge = kIsLittleEndian
806 ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
810 Category category() const {
811 // works for both big-endian and little-endian
812 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
820 size_t capacity() const {
821 return kIsLittleEndian
822 ? capacity_ & capacityExtractMask
826 void setCapacity(size_t cap, Category cat) {
827 capacity_ = kIsLittleEndian
828 ? cap | static_cast<category_type>(cat)
829 : (cap << 2) | static_cast<category_type>(cat);
834 Char small_[sizeof(MediumLarge) / sizeof(Char)];
839 lastChar = sizeof(MediumLarge) - 1,
840 maxSmallSize = lastChar / sizeof(Char),
841 maxMediumSize = 254 / sizeof(Char), // coincides with the small
842 // bin size in dlmalloc
843 categoryExtractMask = kIsLittleEndian
844 ? sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000
846 capacityExtractMask = kIsLittleEndian
847 ? ~categoryExtractMask
850 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
851 "Corrupt memory layout for fbstring.");
853 size_t smallSize() const {
854 assert(category() == Category::isSmall);
855 auto shift = kIsLittleEndian ? 0 : 2;
856 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
857 assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
858 return static_cast<size_t>(maxSmallSize) - smallShifted;
861 void setSmallSize(size_t s) {
862 // Warning: this should work with uninitialized strings too,
863 // so don't assume anything about the previous value of
864 // small_[maxSmallSize].
865 assert(s <= maxSmallSize);
866 small_[maxSmallSize] = kIsLittleEndian
868 : (maxSmallSize - s) << 2;
873 #ifndef _LIBSTDCXX_FBSTRING
875 * Dummy fbstring core that uses an actual std::string. This doesn't
876 * make any sense - it's just for testing purposes.
878 template <class Char>
879 class dummy_fbstring_core {
881 dummy_fbstring_core() {
883 dummy_fbstring_core(const dummy_fbstring_core& another)
884 : backend_(another.backend_) {
886 dummy_fbstring_core(const Char * s, size_t n)
889 void swap(dummy_fbstring_core & rhs) {
890 backend_.swap(rhs.backend_);
892 const Char * data() const {
893 return backend_.data();
895 Char * mutable_data() {
896 //assert(!backend_.empty());
897 return &*backend_.begin();
899 void shrink(size_t delta) {
900 assert(delta <= size());
901 backend_.resize(size() - delta);
903 Char * expand_noinit(size_t delta) {
904 auto const sz = size();
905 backend_.resize(size() + delta);
906 return backend_.data() + sz;
908 void push_back(Char c) {
909 backend_.push_back(c);
911 size_t size() const {
912 return backend_.size();
914 size_t capacity() const {
915 return backend_.capacity();
917 bool isShared() const {
920 void reserve(size_t minCapacity) {
921 backend_.reserve(minCapacity);
925 std::basic_string<Char> backend_;
927 #endif // !_LIBSTDCXX_FBSTRING
930 * This is the basic_string replacement. For conformity,
931 * basic_fbstring takes the same template parameters, plus the last
932 * one which is the core.
934 #ifdef _LIBSTDCXX_FBSTRING
935 template <typename E, class T, class A, class Storage>
937 template <typename E,
938 class T = std::char_traits<E>,
939 class A = std::allocator<E>,
940 class Storage = fbstring_core<E> >
942 class basic_fbstring {
946 void (*throw_exc)(const char*),
948 if (!condition) throw_exc(msg);
951 bool isSane() const {
954 empty() == (size() == 0) &&
955 empty() == (begin() == end()) &&
956 size() <= max_size() &&
957 capacity() <= max_size() &&
958 size() <= capacity() &&
959 begin()[size()] == '\0';
963 friend struct Invariant;
966 explicit Invariant(const basic_fbstring& s) : s_(s) {
973 const basic_fbstring& s_;
975 explicit Invariant(const basic_fbstring&) {}
977 Invariant& operator=(const Invariant&);
982 typedef T traits_type;
983 typedef typename traits_type::char_type value_type;
984 typedef A allocator_type;
985 typedef typename A::size_type size_type;
986 typedef typename A::difference_type difference_type;
988 typedef typename A::reference reference;
989 typedef typename A::const_reference const_reference;
990 typedef typename A::pointer pointer;
991 typedef typename A::const_pointer const_pointer;
994 typedef const E* const_iterator;
995 typedef std::reverse_iterator<iterator
996 #ifdef NO_ITERATOR_TRAITS
1000 typedef std::reverse_iterator<const_iterator
1001 #ifdef NO_ITERATOR_TRAITS
1004 > const_reverse_iterator;
1006 static const size_type npos; // = size_type(-1)
1009 static void procrustes(size_type& n, size_type nmax) {
1010 if (n > nmax) n = nmax;
1014 // C++11 21.4.2 construct/copy/destroy
1016 // Note: while the following two constructors can be (and previously were)
1017 // collapsed into one constructor written this way:
1019 // explicit basic_fbstring(const A& a = A()) noexcept { }
1021 // This can cause Clang (at least version 3.7) to fail with the error:
1022 // "chosen constructor is explicit in copy-initialization ...
1023 // in implicit initialization of field '(x)' with omitted initializer"
1025 // if used in a struct which is default-initialized. Hence the split into
1026 // these two separate constructors.
1028 basic_fbstring() noexcept : basic_fbstring(A()) {
1031 explicit basic_fbstring(const A&) noexcept {
1034 basic_fbstring(const basic_fbstring& str)
1035 : store_(str.store_) {
1039 basic_fbstring(basic_fbstring&& goner) noexcept
1040 : store_(std::move(goner.store_)) {
1043 #ifndef _LIBSTDCXX_FBSTRING
1044 // This is defined for compatibility with std::string
1045 /* implicit */ basic_fbstring(const std::string& str)
1046 : store_(str.data(), str.size()) {
1050 basic_fbstring(const basic_fbstring& str, size_type pos,
1051 size_type n = npos, const A& a = A()) {
1052 assign(str, pos, n);
1055 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1057 ? traits_type::length(s)
1058 : (std::__throw_logic_error(
1059 "basic_fbstring: null pointer initializer not valid"),
1063 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1067 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1068 auto const data = store_.expand_noinit(n);
1069 fbstring_detail::pod_fill(data, data + n, c);
1070 store_.writeTerminator();
1073 template <class InIt>
1074 basic_fbstring(InIt begin, InIt end,
1075 typename std::enable_if<
1076 !std::is_same<typename std::remove_const<InIt>::type,
1077 value_type*>::value, const A>::type & /*a*/ = A()) {
1081 // Specialization for const char*, const char*
1082 basic_fbstring(const value_type* b, const value_type* e)
1083 : store_(b, e - b) {
1086 // Nonstandard constructor
1087 basic_fbstring(value_type *s, size_type n, size_type c,
1088 AcquireMallocatedString a)
1089 : store_(s, n, c, a) {
1092 // Construction from initialization list
1093 basic_fbstring(std::initializer_list<value_type> il) {
1094 assign(il.begin(), il.end());
1097 ~basic_fbstring() noexcept {
1100 basic_fbstring& operator=(const basic_fbstring& lhs) {
1101 if (FBSTRING_UNLIKELY(&lhs == this)) {
1104 auto const oldSize = size();
1105 auto const srcSize = lhs.size();
1106 if (capacity() >= srcSize && !store_.isShared()) {
1107 // great, just copy the contents
1108 if (oldSize < srcSize)
1109 store_.expand_noinit(srcSize - oldSize);
1111 store_.shrink(oldSize - srcSize);
1112 assert(size() == srcSize);
1113 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1114 store_.writeTerminator();
1116 // need to reallocate, so we may as well create a brand new string
1117 basic_fbstring(lhs).swap(*this);
1123 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1124 if (FBSTRING_UNLIKELY(&goner == this)) {
1125 // Compatibility with std::basic_string<>,
1126 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1129 // No need of this anymore
1130 this->~basic_fbstring();
1131 // Move the goner into this
1132 new(&store_) fbstring_core<E>(std::move(goner.store_));
1136 #ifndef _LIBSTDCXX_FBSTRING
1137 // Compatibility with std::string
1138 basic_fbstring & operator=(const std::string & rhs) {
1139 return assign(rhs.data(), rhs.size());
1142 // Compatibility with std::string
1143 std::string toStdString() const {
1144 return std::string(data(), size());
1147 // A lot of code in fbcode still uses this method, so keep it here for now.
1148 const basic_fbstring& toStdString() const {
1153 basic_fbstring& operator=(const value_type* s) {
1157 basic_fbstring& operator=(value_type c) {
1159 store_.expand_noinit(1);
1160 } else if (store_.isShared()) {
1161 basic_fbstring(1, c).swap(*this);
1164 store_.shrink(size() - 1);
1166 *store_.mutable_data() = c;
1167 store_.writeTerminator();
1171 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1172 return assign(il.begin(), il.end());
1175 // C++11 21.4.3 iterators:
1176 iterator begin() { return store_.mutable_data(); }
1178 const_iterator begin() const { return store_.data(); }
1180 const_iterator cbegin() const { return begin(); }
1183 return store_.mutable_data() + store_.size();
1186 const_iterator end() const {
1187 return store_.data() + store_.size();
1190 const_iterator cend() const { return end(); }
1192 reverse_iterator rbegin() {
1193 return reverse_iterator(end());
1196 const_reverse_iterator rbegin() const {
1197 return const_reverse_iterator(end());
1200 const_reverse_iterator crbegin() const { return rbegin(); }
1202 reverse_iterator rend() {
1203 return reverse_iterator(begin());
1206 const_reverse_iterator rend() const {
1207 return const_reverse_iterator(begin());
1210 const_reverse_iterator crend() const { return rend(); }
1213 // C++11 21.4.5, element access:
1214 const value_type& front() const { return *begin(); }
1215 const value_type& back() const {
1217 // Should be begin()[size() - 1], but that branches twice
1218 return *(end() - 1);
1220 value_type& front() { return *begin(); }
1221 value_type& back() {
1223 // Should be begin()[size() - 1], but that branches twice
1224 return *(end() - 1);
1231 // C++11 21.4.4 capacity:
1232 size_type size() const { return store_.size(); }
1234 size_type length() const { return size(); }
1236 size_type max_size() const {
1237 return std::numeric_limits<size_type>::max();
1240 void resize(const size_type n, const value_type c = value_type()) {
1241 auto size = this->size();
1243 store_.shrink(size - n);
1245 // Do this in two steps to minimize slack memory copied (see
1247 auto const capacity = this->capacity();
1248 assert(capacity >= size);
1249 if (size < capacity) {
1250 auto delta = std::min(n, capacity) - size;
1251 store_.expand_noinit(delta);
1252 fbstring_detail::pod_fill(begin() + size, end(), c);
1255 store_.writeTerminator();
1260 auto const delta = n - size;
1261 store_.expand_noinit(delta);
1262 fbstring_detail::pod_fill(end() - delta, end(), c);
1263 store_.writeTerminator();
1265 assert(this->size() == n);
1268 size_type capacity() const { return store_.capacity(); }
1270 void reserve(size_type res_arg = 0) {
1271 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1272 store_.reserve(res_arg);
1275 void shrink_to_fit() {
1276 // Shrink only if slack memory is sufficiently large
1277 if (capacity() < size() * 3 / 2) {
1280 basic_fbstring(cbegin(), cend()).swap(*this);
1283 void clear() { resize(0); }
1285 bool empty() const { return size() == 0; }
1287 // C++11 21.4.5 element access:
1288 const_reference operator[](size_type pos) const {
1289 return *(begin() + pos);
1292 reference operator[](size_type pos) {
1293 return *(begin() + pos);
1296 const_reference at(size_type n) const {
1297 enforce(n <= size(), std::__throw_out_of_range, "");
1301 reference at(size_type n) {
1302 enforce(n < size(), std::__throw_out_of_range, "");
1306 // C++11 21.4.6 modifiers:
1307 basic_fbstring& operator+=(const basic_fbstring& str) {
1311 basic_fbstring& operator+=(const value_type* s) {
1315 basic_fbstring& operator+=(const value_type c) {
1320 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1325 basic_fbstring& append(const basic_fbstring& str) {
1327 auto desiredSize = size() + str.size();
1329 append(str.data(), str.size());
1330 assert(size() == desiredSize);
1334 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1336 const size_type sz = str.size();
1337 enforce(pos <= sz, std::__throw_out_of_range, "");
1338 procrustes(n, sz - pos);
1339 return append(str.data() + pos, n);
1342 basic_fbstring& append(const value_type* s, size_type n) {
1344 Invariant checker(*this);
1347 if (FBSTRING_UNLIKELY(!n)) {
1348 // Unlikely but must be done
1351 auto const oldSize = size();
1352 auto const oldData = data();
1353 // Check for aliasing (rare). We could use "<=" here but in theory
1354 // those do not work for pointers unless the pointers point to
1355 // elements in the same array. For that reason we use
1356 // std::less_equal, which is guaranteed to offer a total order
1357 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1359 std::less_equal<const value_type*> le;
1360 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1361 assert(le(s + n, oldData + oldSize));
1362 const size_type offset = s - oldData;
1363 store_.reserve(oldSize + n);
1364 // Restore the source
1365 s = data() + offset;
1367 // Warning! Repeated appends with short strings may actually incur
1368 // practically quadratic performance. Avoid that by pushing back
1369 // the first character (which ensures exponential growth) and then
1370 // appending the rest normally. Worst case the append may incur a
1371 // second allocation but that will be rare.
1374 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1375 assert(size() == oldSize + n + 1);
1379 basic_fbstring& append(const value_type* s) {
1380 return append(s, traits_type::length(s));
1383 basic_fbstring& append(size_type n, value_type c) {
1384 resize(size() + n, c);
1388 template<class InputIterator>
1389 basic_fbstring& append(InputIterator first, InputIterator last) {
1390 insert(end(), first, last);
1394 basic_fbstring& append(std::initializer_list<value_type> il) {
1395 return append(il.begin(), il.end());
1398 void push_back(const value_type c) { // primitive
1399 store_.push_back(c);
1402 basic_fbstring& assign(const basic_fbstring& str) {
1403 if (&str == this) return *this;
1404 return assign(str.data(), str.size());
1407 basic_fbstring& assign(basic_fbstring&& str) {
1408 return *this = std::move(str);
1411 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1413 const size_type sz = str.size();
1414 enforce(pos <= sz, std::__throw_out_of_range, "");
1415 procrustes(n, sz - pos);
1416 return assign(str.data() + pos, n);
1419 basic_fbstring& assign(const value_type* s, const size_type n) {
1420 Invariant checker(*this);
1423 std::copy(s, s + n, begin());
1425 assert(size() == n);
1427 const value_type *const s2 = s + size();
1428 std::copy(s, s2, begin());
1429 append(s2, n - size());
1430 assert(size() == n);
1432 store_.writeTerminator();
1433 assert(size() == n);
1437 basic_fbstring& assign(const value_type* s) {
1438 return assign(s, traits_type::length(s));
1441 basic_fbstring& assign(std::initializer_list<value_type> il) {
1442 return assign(il.begin(), il.end());
1445 template <class ItOrLength, class ItOrChar>
1446 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1447 return replace(begin(), end(), first_or_n, last_or_c);
1450 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1451 return insert(pos1, str.data(), str.size());
1454 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1455 size_type pos2, size_type n) {
1456 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1457 procrustes(n, str.length() - pos2);
1458 return insert(pos1, str.data() + pos2, n);
1461 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1462 enforce(pos <= length(), std::__throw_out_of_range, "");
1463 insert(begin() + pos, s, s + n);
1467 basic_fbstring& insert(size_type pos, const value_type* s) {
1468 return insert(pos, s, traits_type::length(s));
1471 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1472 enforce(pos <= length(), std::__throw_out_of_range, "");
1473 insert(begin() + pos, n, c);
1477 iterator insert(const_iterator p, const value_type c) {
1478 const size_type pos = p - begin();
1480 return begin() + pos;
1484 template <int i> class Selector {};
1486 iterator insertImplDiscr(const_iterator p,
1487 size_type n, value_type c, Selector<1>) {
1488 Invariant checker(*this);
1490 auto const pos = p - begin();
1491 assert(p >= begin() && p <= end());
1492 if (capacity() - size() < n) {
1493 const size_type sz = p - begin();
1494 reserve(size() + n);
1497 const iterator oldEnd = end();
1498 if (n < size_type(oldEnd - p)) {
1499 append(oldEnd - n, oldEnd);
1501 // reverse_iterator(oldEnd - n),
1502 // reverse_iterator(p),
1503 // reverse_iterator(oldEnd));
1504 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1506 std::fill(begin() + pos, begin() + pos + n, c);
1508 append(n - (end() - p), c);
1509 append(iterator(p), oldEnd);
1510 std::fill(iterator(p), oldEnd, c);
1512 store_.writeTerminator();
1513 return begin() + pos;
1516 template<class InputIter>
1517 iterator insertImplDiscr(const_iterator i,
1518 InputIter b, InputIter e, Selector<0>) {
1519 return insertImpl(i, b, e,
1520 typename std::iterator_traits<InputIter>::iterator_category());
1523 template <class FwdIterator>
1524 iterator insertImpl(const_iterator i,
1525 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1526 Invariant checker(*this);
1528 const size_type pos = i - begin();
1529 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1530 std::distance(s1, s2);
1532 using namespace fbstring_detail;
1533 assert(pos <= size());
1535 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1536 capacity() - size();
1538 // realloc the string
1539 reserve(size() + n2);
1542 if (pos + n2 <= size()) {
1543 const iterator tailBegin = end() - n2;
1544 store_.expand_noinit(n2);
1545 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1546 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1547 reverse_iterator(tailBegin + n2));
1548 std::copy(s1, s2, begin() + pos);
1551 const size_type old_size = size();
1552 std::advance(t, old_size - pos);
1553 const size_t newElems = std::distance(t, s2);
1554 store_.expand_noinit(n2);
1555 std::copy(t, s2, begin() + old_size);
1556 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1557 begin() + old_size + newElems);
1558 std::copy(s1, t, begin() + pos);
1560 store_.writeTerminator();
1561 return begin() + pos;
1564 template <class InputIterator>
1565 iterator insertImpl(const_iterator i,
1566 InputIterator b, InputIterator e,
1567 std::input_iterator_tag) {
1568 const auto pos = i - begin();
1569 basic_fbstring temp(begin(), i);
1570 for (; b != e; ++b) {
1573 temp.append(i, cend());
1575 return begin() + pos;
1579 template <class ItOrLength, class ItOrChar>
1580 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1581 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1582 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1585 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1586 return insert(p, il.begin(), il.end());
1589 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1590 Invariant checker(*this);
1592 enforce(pos <= length(), std::__throw_out_of_range, "");
1593 procrustes(n, length() - pos);
1594 std::copy(begin() + pos + n, end(), begin() + pos);
1595 resize(length() - n);
1599 iterator erase(iterator position) {
1600 const size_type pos(position - begin());
1601 enforce(pos <= size(), std::__throw_out_of_range, "");
1603 return begin() + pos;
1606 iterator erase(iterator first, iterator last) {
1607 const size_type pos(first - begin());
1608 erase(pos, last - first);
1609 return begin() + pos;
1612 // Replaces at most n1 chars of *this, starting with pos1 with the
1614 basic_fbstring& replace(size_type pos1, size_type n1,
1615 const basic_fbstring& str) {
1616 return replace(pos1, n1, str.data(), str.size());
1619 // Replaces at most n1 chars of *this, starting with pos1,
1620 // with at most n2 chars of str starting with pos2
1621 basic_fbstring& replace(size_type pos1, size_type n1,
1622 const basic_fbstring& str,
1623 size_type pos2, size_type n2) {
1624 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1625 return replace(pos1, n1, str.data() + pos2,
1626 std::min(n2, str.size() - pos2));
1629 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1630 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1631 return replace(pos, n1, s, traits_type::length(s));
1634 // Replaces at most n1 chars of *this, starting with pos, with n2
1637 // consolidated with
1639 // Replaces at most n1 chars of *this, starting with pos, with at
1640 // most n2 chars of str. str must have at least n2 chars.
1641 template <class StrOrLength, class NumOrChar>
1642 basic_fbstring& replace(size_type pos, size_type n1,
1643 StrOrLength s_or_n2, NumOrChar n_or_c) {
1644 Invariant checker(*this);
1646 enforce(pos <= size(), std::__throw_out_of_range, "");
1647 procrustes(n1, length() - pos);
1648 const iterator b = begin() + pos;
1649 return replace(b, b + n1, s_or_n2, n_or_c);
1652 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1653 return replace(i1, i2, str.data(), str.length());
1656 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1657 return replace(i1, i2, s, traits_type::length(s));
1661 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1662 const value_type* s, size_type n,
1665 assert(begin() <= i1 && i1 <= end());
1666 assert(begin() <= i2 && i2 <= end());
1667 return replace(i1, i2, s, s + n);
1670 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1671 size_type n2, value_type c, Selector<1>) {
1672 const size_type n1 = i2 - i1;
1674 std::fill(i1, i1 + n2, c);
1677 std::fill(i1, i2, c);
1678 insert(i2, n2 - n1, c);
1684 template <class InputIter>
1685 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1686 InputIter b, InputIter e,
1688 replaceImpl(i1, i2, b, e,
1689 typename std::iterator_traits<InputIter>::iterator_category());
1694 template <class FwdIterator>
1695 bool replaceAliased(iterator i1, iterator i2,
1696 FwdIterator s1, FwdIterator s2, std::false_type) {
1700 template <class FwdIterator>
1701 bool replaceAliased(iterator i1, iterator i2,
1702 FwdIterator s1, FwdIterator s2, std::true_type) {
1703 static const std::less_equal<const value_type*> le =
1704 std::less_equal<const value_type*>();
1705 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1709 // Aliased replace, copy to new string
1710 basic_fbstring temp;
1711 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1712 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1717 template <class FwdIterator>
1718 void replaceImpl(iterator i1, iterator i2,
1719 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1720 Invariant checker(*this);
1723 // Handle aliased replace
1724 if (replaceAliased(i1, i2, s1, s2,
1725 std::integral_constant<bool,
1726 std::is_same<FwdIterator, iterator>::value ||
1727 std::is_same<FwdIterator, const_iterator>::value>())) {
1731 auto const n1 = i2 - i1;
1733 auto const n2 = std::distance(s1, s2);
1738 std::copy(s1, s2, i1);
1742 fbstring_detail::copy_n(s1, n1, i1);
1743 std::advance(s1, n1);
1749 template <class InputIterator>
1750 void replaceImpl(iterator i1, iterator i2,
1751 InputIterator b, InputIterator e, std::input_iterator_tag) {
1752 basic_fbstring temp(begin(), i1);
1753 temp.append(b, e).append(i2, end());
1758 template <class T1, class T2>
1759 basic_fbstring& replace(iterator i1, iterator i2,
1760 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1762 num1 = std::numeric_limits<T1>::is_specialized,
1763 num2 = std::numeric_limits<T2>::is_specialized;
1764 return replaceImplDiscr(
1765 i1, i2, first_or_n_or_s, last_or_c_or_n,
1766 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1769 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1770 enforce(pos <= size(), std::__throw_out_of_range, "");
1771 procrustes(n, size() - pos);
1773 fbstring_detail::pod_copy(
1780 void swap(basic_fbstring& rhs) {
1781 store_.swap(rhs.store_);
1784 const value_type* c_str() const {
1785 return store_.c_str();
1788 const value_type* data() const { return c_str(); }
1790 allocator_type get_allocator() const {
1791 return allocator_type();
1794 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1795 return find(str.data(), pos, str.length());
1798 size_type find(const value_type* needle, const size_type pos,
1799 const size_type nsize) const {
1800 if (!nsize) return pos;
1801 auto const size = this->size();
1802 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1803 // that nsize + pos does not wrap around.
1804 if (nsize + pos > size || nsize + pos < pos) return npos;
1805 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1806 // the last characters first
1807 auto const haystack = data();
1808 auto const nsize_1 = nsize - 1;
1809 auto const lastNeedle = needle[nsize_1];
1811 // Boyer-Moore skip value for the last char in the needle. Zero is
1812 // not a valid value; skip will be computed the first time it's
1816 const E * i = haystack + pos;
1817 auto iEnd = haystack + size - nsize_1;
1820 // Boyer-Moore: match the last element in the needle
1821 while (i[nsize_1] != lastNeedle) {
1827 // Here we know that the last char matches
1828 // Continue in pedestrian mode
1829 for (size_t j = 0; ; ) {
1831 if (i[j] != needle[j]) {
1832 // Not found, we can skip
1833 // Compute the skip value lazily
1836 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1843 // Check if done searching
1846 return i - haystack;
1853 size_type find(const value_type* s, size_type pos = 0) const {
1854 return find(s, pos, traits_type::length(s));
1857 size_type find (value_type c, size_type pos = 0) const {
1858 return find(&c, pos, 1);
1861 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1862 return rfind(str.data(), pos, str.length());
1865 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1866 if (n > length()) return npos;
1867 pos = std::min(pos, length() - n);
1868 if (n == 0) return pos;
1870 const_iterator i(begin() + pos);
1872 if (traits_type::eq(*i, *s)
1873 && traits_type::compare(&*i, s, n) == 0) {
1876 if (i == begin()) break;
1881 size_type rfind(const value_type* s, size_type pos = npos) const {
1882 return rfind(s, pos, traits_type::length(s));
1885 size_type rfind(value_type c, size_type pos = npos) const {
1886 return rfind(&c, pos, 1);
1889 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1890 return find_first_of(str.data(), pos, str.length());
1893 size_type find_first_of(const value_type* s,
1894 size_type pos, size_type n) const {
1895 if (pos > length() || n == 0) return npos;
1896 const_iterator i(begin() + pos),
1898 for (; i != finish; ++i) {
1899 if (traits_type::find(s, n, *i) != 0) {
1906 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1907 return find_first_of(s, pos, traits_type::length(s));
1910 size_type find_first_of(value_type c, size_type pos = 0) const {
1911 return find_first_of(&c, pos, 1);
1914 size_type find_last_of (const basic_fbstring& str,
1915 size_type pos = npos) const {
1916 return find_last_of(str.data(), pos, str.length());
1919 size_type find_last_of (const value_type* s, size_type pos,
1920 size_type n) const {
1921 if (!empty() && n > 0) {
1922 pos = std::min(pos, length() - 1);
1923 const_iterator i(begin() + pos);
1925 if (traits_type::find(s, n, *i) != 0) {
1928 if (i == begin()) break;
1934 size_type find_last_of (const value_type* s,
1935 size_type pos = npos) const {
1936 return find_last_of(s, pos, traits_type::length(s));
1939 size_type find_last_of (value_type c, size_type pos = npos) const {
1940 return find_last_of(&c, pos, 1);
1943 size_type find_first_not_of(const basic_fbstring& str,
1944 size_type pos = 0) const {
1945 return find_first_not_of(str.data(), pos, str.size());
1948 size_type find_first_not_of(const value_type* s, size_type pos,
1949 size_type n) const {
1950 if (pos < length()) {
1954 for (; i != finish; ++i) {
1955 if (traits_type::find(s, n, *i) == 0) {
1963 size_type find_first_not_of(const value_type* s,
1964 size_type pos = 0) const {
1965 return find_first_not_of(s, pos, traits_type::length(s));
1968 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1969 return find_first_not_of(&c, pos, 1);
1972 size_type find_last_not_of(const basic_fbstring& str,
1973 size_type pos = npos) const {
1974 return find_last_not_of(str.data(), pos, str.length());
1977 size_type find_last_not_of(const value_type* s, size_type pos,
1978 size_type n) const {
1979 if (!this->empty()) {
1980 pos = std::min(pos, size() - 1);
1981 const_iterator i(begin() + pos);
1983 if (traits_type::find(s, n, *i) == 0) {
1986 if (i == begin()) break;
1992 size_type find_last_not_of(const value_type* s,
1993 size_type pos = npos) const {
1994 return find_last_not_of(s, pos, traits_type::length(s));
1997 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1998 return find_last_not_of(&c, pos, 1);
2001 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
2002 enforce(pos <= size(), std::__throw_out_of_range, "");
2003 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2006 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
2007 enforce(pos <= size(), std::__throw_out_of_range, "");
2009 if (n < size()) resize(n);
2010 return std::move(*this);
2013 int compare(const basic_fbstring& str) const {
2014 // FIX due to Goncalo N M de Carvalho July 18, 2005
2015 return compare(0, size(), str);
2018 int compare(size_type pos1, size_type n1,
2019 const basic_fbstring& str) const {
2020 return compare(pos1, n1, str.data(), str.size());
2023 int compare(size_type pos1, size_type n1,
2024 const value_type* s) const {
2025 return compare(pos1, n1, s, traits_type::length(s));
2028 int compare(size_type pos1, size_type n1,
2029 const value_type* s, size_type n2) const {
2030 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2031 procrustes(n1, size() - pos1);
2032 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2033 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2034 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2037 int compare(size_type pos1, size_type n1,
2038 const basic_fbstring& str,
2039 size_type pos2, size_type n2) const {
2040 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2041 return compare(pos1, n1, str.data() + pos2,
2042 std::min(n2, str.size() - pos2));
2045 // Code from Jean-Francois Bastien (03/26/2007)
2046 int compare(const value_type* s) const {
2047 // Could forward to compare(0, size(), s, traits_type::length(s))
2048 // but that does two extra checks
2049 const size_type n1(size()), n2(traits_type::length(s));
2050 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2051 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2059 // non-member functions
2061 template <typename E, class T, class A, class S>
2063 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2064 const basic_fbstring<E, T, A, S>& rhs) {
2066 basic_fbstring<E, T, A, S> result;
2067 result.reserve(lhs.size() + rhs.size());
2068 result.append(lhs).append(rhs);
2069 return std::move(result);
2073 template <typename E, class T, class A, class S>
2075 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2076 const basic_fbstring<E, T, A, S>& rhs) {
2077 return std::move(lhs.append(rhs));
2081 template <typename E, class T, class A, class S>
2083 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2084 basic_fbstring<E, T, A, S>&& rhs) {
2085 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2086 // Good, at least we don't need to reallocate
2087 return std::move(rhs.insert(0, lhs));
2089 // Meh, no go. Forward to operator+(const&, const&).
2090 auto const& rhsC = rhs;
2095 template <typename E, class T, class A, class S>
2097 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2098 basic_fbstring<E, T, A, S>&& rhs) {
2099 return std::move(lhs.append(rhs));
2103 template <typename E, class T, class A, class S>
2105 basic_fbstring<E, T, A, S> operator+(
2107 const basic_fbstring<E, T, A, S>& rhs) {
2109 basic_fbstring<E, T, A, S> result;
2110 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2111 result.reserve(len + rhs.size());
2112 result.append(lhs, len).append(rhs);
2117 template <typename E, class T, class A, class S>
2119 basic_fbstring<E, T, A, S> operator+(
2121 basic_fbstring<E, T, A, S>&& rhs) {
2123 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2124 if (rhs.capacity() >= len + rhs.size()) {
2125 // Good, at least we don't need to reallocate
2126 return std::move(rhs.insert(rhs.begin(), lhs, lhs + len));
2128 // Meh, no go. Do it by hand since we have len already.
2129 basic_fbstring<E, T, A, S> result;
2130 result.reserve(len + rhs.size());
2131 result.append(lhs, len).append(rhs);
2136 template <typename E, class T, class A, class S>
2138 basic_fbstring<E, T, A, S> operator+(
2140 const basic_fbstring<E, T, A, S>& rhs) {
2142 basic_fbstring<E, T, A, S> result;
2143 result.reserve(1 + rhs.size());
2144 result.push_back(lhs);
2150 template <typename E, class T, class A, class S>
2152 basic_fbstring<E, T, A, S> operator+(
2154 basic_fbstring<E, T, A, S>&& rhs) {
2156 if (rhs.capacity() > rhs.size()) {
2157 // Good, at least we don't need to reallocate
2158 return std::move(rhs.insert(rhs.begin(), lhs));
2160 // Meh, no go. Forward to operator+(E, const&).
2161 auto const& rhsC = rhs;
2166 template <typename E, class T, class A, class S>
2168 basic_fbstring<E, T, A, S> operator+(
2169 const basic_fbstring<E, T, A, S>& lhs,
2172 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2173 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2175 basic_fbstring<E, T, A, S> result;
2176 const size_type len = traits_type::length(rhs);
2177 result.reserve(lhs.size() + len);
2178 result.append(lhs).append(rhs, len);
2182 // C++11 21.4.8.1/10
2183 template <typename E, class T, class A, class S>
2185 basic_fbstring<E, T, A, S> operator+(
2186 basic_fbstring<E, T, A, S>&& lhs,
2189 return std::move(lhs += rhs);
2192 // C++11 21.4.8.1/11
2193 template <typename E, class T, class A, class S>
2195 basic_fbstring<E, T, A, S> operator+(
2196 const basic_fbstring<E, T, A, S>& lhs,
2199 basic_fbstring<E, T, A, S> result;
2200 result.reserve(lhs.size() + 1);
2202 result.push_back(rhs);
2206 // C++11 21.4.8.1/12
2207 template <typename E, class T, class A, class S>
2209 basic_fbstring<E, T, A, S> operator+(
2210 basic_fbstring<E, T, A, S>&& lhs,
2213 return std::move(lhs += rhs);
2216 template <typename E, class T, class A, class S>
2218 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2219 const basic_fbstring<E, T, A, S>& rhs) {
2220 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2222 template <typename E, class T, class A, class S>
2224 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2225 const basic_fbstring<E, T, A, S>& rhs) {
2226 return rhs == lhs; }
2228 template <typename E, class T, class A, class S>
2230 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2231 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2232 return lhs.compare(rhs) == 0; }
2234 template <typename E, class T, class A, class S>
2236 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2237 const basic_fbstring<E, T, A, S>& rhs) {
2238 return !(lhs == rhs); }
2240 template <typename E, class T, class A, class S>
2242 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2243 const basic_fbstring<E, T, A, S>& rhs) {
2244 return !(lhs == rhs); }
2246 template <typename E, class T, class A, class S>
2248 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2249 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2250 return !(lhs == rhs); }
2252 template <typename E, class T, class A, class S>
2254 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2255 const basic_fbstring<E, T, A, S>& rhs) {
2256 return lhs.compare(rhs) < 0; }
2258 template <typename E, class T, class A, class S>
2260 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2261 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2262 return lhs.compare(rhs) < 0; }
2264 template <typename E, class T, class A, class S>
2266 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2267 const basic_fbstring<E, T, A, S>& rhs) {
2268 return rhs.compare(lhs) > 0; }
2270 template <typename E, class T, class A, class S>
2272 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2273 const basic_fbstring<E, T, A, S>& rhs) {
2276 template <typename E, class T, class A, class S>
2278 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2279 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2282 template <typename E, class T, class A, class S>
2284 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2285 const basic_fbstring<E, T, A, S>& rhs) {
2288 template <typename E, class T, class A, class S>
2290 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2291 const basic_fbstring<E, T, A, S>& rhs) {
2292 return !(rhs < lhs); }
2294 template <typename E, class T, class A, class S>
2296 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2297 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2298 return !(rhs < lhs); }
2300 template <typename E, class T, class A, class S>
2302 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2303 const basic_fbstring<E, T, A, S>& rhs) {
2304 return !(rhs < lhs); }
2306 template <typename E, class T, class A, class S>
2308 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2309 const basic_fbstring<E, T, A, S>& rhs) {
2310 return !(lhs < rhs); }
2312 template <typename E, class T, class A, class S>
2314 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2315 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2316 return !(lhs < rhs); }
2318 template <typename E, class T, class A, class S>
2320 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2321 const basic_fbstring<E, T, A, S>& rhs) {
2322 return !(lhs < rhs);
2326 template <typename E, class T, class A, class S>
2327 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2331 // TODO: make this faster.
2332 template <typename E, class T, class A, class S>
2335 typename basic_fbstring<E, T, A, S>::value_type,
2336 typename basic_fbstring<E, T, A, S>::traits_type>&
2338 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2339 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2340 basic_fbstring<E, T, A, S>& str) {
2341 typename std::basic_istream<E, T>::sentry sentry(is);
2342 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2343 typename basic_fbstring<E, T, A, S>::traits_type>
2345 typedef typename __istream_type::ios_base __ios_base;
2346 size_t extracted = 0;
2347 auto err = __ios_base::goodbit;
2349 auto n = is.width();
2354 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2355 if (got == T::eof()) {
2356 err |= __ios_base::eofbit;
2360 if (isspace(got)) break;
2362 got = is.rdbuf()->snextc();
2366 err |= __ios_base::failbit;
2374 template <typename E, class T, class A, class S>
2376 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2377 typename basic_fbstring<E, T, A, S>::traits_type>&
2379 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2380 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2381 const basic_fbstring<E, T, A, S>& str) {
2383 typename std::basic_ostream<
2384 typename basic_fbstring<E, T, A, S>::value_type,
2385 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2387 typedef std::ostreambuf_iterator<
2388 typename basic_fbstring<E, T, A, S>::value_type,
2389 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2390 size_t __len = str.size();
2392 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2393 if (__pad_and_output(_Ip(os),
2395 __left ? str.data() + __len : str.data(),
2398 os.fill()).failed()) {
2399 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2402 #elif defined(_MSC_VER)
2403 // MSVC doesn't define __ostream_insert
2404 os.write(str.data(), str.size());
2406 std::__ostream_insert(os, str.data(), str.size());
2411 #ifndef _LIBSTDCXX_FBSTRING
2413 template <typename E, class T, class A, class S>
2415 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2416 typename basic_fbstring<E, T, A, S>::traits_type>&
2418 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2419 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2420 basic_fbstring<E, T, A, S>& str,
2421 typename basic_fbstring<E, T, A, S>::value_type delim) {
2422 // Use the nonstandard getdelim()
2423 char * buf = nullptr;
2426 // This looks quadratic but it really depends on realloc
2427 auto const newSize = size + 128;
2428 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2429 is.getline(buf + size, newSize - size, delim);
2430 if (is.bad() || is.eof() || !is.fail()) {
2431 // done by either failure, end of file, or normal read
2432 size += std::strlen(buf + size);
2435 // Here we have failed due to too short a buffer
2436 // Minus one to discount the terminating '\0'
2438 assert(buf[size] == 0);
2439 // Clear the error so we can continue reading
2442 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2443 AcquireMallocatedString());
2448 template <typename E, class T, class A, class S>
2450 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2451 typename basic_fbstring<E, T, A, S>::traits_type>&
2453 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2454 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2455 basic_fbstring<E, T, A, S>& str) {
2456 // Just forward to the version with a delimiter
2457 return getline(is, str, '\n');
2462 template <typename E1, class T, class A, class S>
2463 const typename basic_fbstring<E1, T, A, S>::size_type
2464 basic_fbstring<E1, T, A, S>::npos =
2465 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2467 #ifndef _LIBSTDCXX_FBSTRING
2468 // basic_string compatibility routines
2470 template <typename E, class T, class A, class S>
2472 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2473 const std::string& rhs) {
2474 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2477 template <typename E, class T, class A, class S>
2479 bool operator==(const std::string& lhs,
2480 const basic_fbstring<E, T, A, S>& rhs) {
2484 template <typename E, class T, class A, class S>
2486 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2487 const std::string& rhs) {
2488 return !(lhs == rhs);
2491 template <typename E, class T, class A, class S>
2493 bool operator!=(const std::string& lhs,
2494 const basic_fbstring<E, T, A, S>& rhs) {
2495 return !(lhs == rhs);
2498 #if !defined(_LIBSTDCXX_FBSTRING)
2499 typedef basic_fbstring<char> fbstring;
2502 // fbstring is relocatable
2503 template <class T, class R, class A, class S>
2504 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2507 _GLIBCXX_END_NAMESPACE_VERSION
2510 } // namespace folly
2512 #ifndef _LIBSTDCXX_FBSTRING
2514 // Hash functions to make fbstring usable with e.g. hash_map
2516 // Handle interaction with different C++ standard libraries, which
2517 // expect these types to be in different namespaces.
2519 #define FOLLY_FBSTRING_HASH1(T) \
2521 struct hash< ::folly::basic_fbstring<T> > { \
2522 size_t operator()(const ::folly::fbstring& s) const { \
2523 return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2527 // The C++11 standard says that these four are defined
2528 #define FOLLY_FBSTRING_HASH \
2529 FOLLY_FBSTRING_HASH1(char) \
2530 FOLLY_FBSTRING_HASH1(char16_t) \
2531 FOLLY_FBSTRING_HASH1(char32_t) \
2532 FOLLY_FBSTRING_HASH1(wchar_t)
2540 #if FOLLY_HAVE_DEPRECATED_ASSOC
2541 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2542 namespace __gnu_cxx {
2546 } // namespace __gnu_cxx
2547 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2548 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2550 #undef FOLLY_FBSTRING_HASH
2551 #undef FOLLY_FBSTRING_HASH1
2553 #endif // _LIBSTDCXX_FBSTRING
2555 #pragma GCC diagnostic pop
2557 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2559 #undef FBSTRING_LIKELY
2560 #undef FBSTRING_UNLIKELY
2562 #ifdef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2564 #undef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2565 #endif // FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2567 #endif // FOLLY_BASE_FBSTRING_H_