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)
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 #pragma GCC diagnostic push
90 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
91 #pragma GCC diagnostic ignored "-Wshadow"
92 // GCC 4.9 has a false positive in setSmallSize (probably
93 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
94 // compile-time array bound checking.
95 #pragma GCC diagnostic ignored "-Warray-bounds"
97 // FBString cannot use throw when replacing std::string, though it may still
100 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
102 #ifdef _LIBSTDCXX_FBSTRING
103 namespace std _GLIBCXX_VISIBILITY(default) {
104 _GLIBCXX_BEGIN_NAMESPACE_VERSION
109 // Different versions of gcc/clang support different versions of
110 // the address sanitizer attribute. Unfortunately, this attribute
111 // has issues when inlining is used, so disable that as well.
112 #if defined(__clang__)
113 # if __has_feature(address_sanitizer)
114 # if __has_attribute(__no_sanitize__)
115 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
116 __attribute__((__no_sanitize__("address"), __noinline__))
117 # elif __has_attribute(__no_address_safety_analysis__)
118 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
119 __attribute__((__no_address_safety_analysis__, __noinline__))
120 # elif __has_attribute(__no_sanitize_address__)
121 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
122 __attribute__((__no_sanitize_address__, __noinline__))
125 #elif defined (__GNUC__) && \
127 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
128 __attribute__((__no_address_safety_analysis__, __noinline__))
130 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
131 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
134 namespace fbstring_detail {
136 template <class InIt, class OutIt>
139 typename std::iterator_traits<InIt>::difference_type n,
141 for (; n != 0; --n, ++b, ++d) {
147 template <class Pod, class T>
148 inline void pod_fill(Pod* b, Pod* e, T c) {
149 assert(b && e && b <= e);
150 /*static*/ if (sizeof(T) == 1) {
153 auto const ee = b + ((e - b) & ~7u);
154 for (; b != ee; b += 8) {
165 for (; b != e; ++b) {
172 * Lightly structured memcpy, simplifies copying PODs and introduces
173 * some asserts. Unfortunately using this function may cause
174 * measurable overhead (presumably because it adjusts from a begin/end
175 * convention to a pointer/size convention, so it does some extra
176 * arithmetic even though the caller might have done the inverse
177 * adaptation outside).
180 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
182 assert(d >= e || d + (e - b) <= b);
183 memcpy(d, b, (e - b) * sizeof(Pod));
187 * Lightly structured memmove, simplifies copying PODs and introduces
191 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
193 memmove(d, b, (e - b) * sizeof(*b));
196 } // namespace fbstring_detail
199 * Defines a special acquisition method for constructing fbstring
200 * objects. AcquireMallocatedString means that the user passes a
201 * pointer to a malloc-allocated string that the fbstring object will
204 enum class AcquireMallocatedString {};
207 * fbstring_core_model is a mock-up type that defines all required
208 * signatures of a fbstring core. The fbstring class itself uses such
209 * a core object to implement all of the numerous member functions
210 * required by the standard.
212 * If you want to define a new core, copy the definition below and
213 * implement the primitives. Then plug the core into basic_fbstring as
214 * a template argument.
216 template <class Char>
217 class fbstring_core_model {
219 fbstring_core_model();
220 fbstring_core_model(const fbstring_core_model &);
221 ~fbstring_core_model();
222 // Returns a pointer to string's buffer (currently only contiguous
223 // strings are supported). The pointer is guaranteed to be valid
224 // until the next call to a non-const member function.
225 const Char * data() const;
226 // Much like data(), except the string is prepared to support
227 // character-level changes. This call is a signal for
228 // e.g. reference-counted implementation to fork the data. The
229 // pointer is guaranteed to be valid until the next call to a
230 // non-const member function.
231 Char * mutable_data();
232 // Returns a pointer to string's buffer and guarantees that a
233 // readable '\0' lies right after the buffer. The pointer is
234 // guaranteed to be valid until the next call to a non-const member
236 const Char * c_str() const;
237 // Shrinks the string by delta characters. Asserts that delta <=
239 void shrink(size_t delta);
240 // Expands the string by delta characters (i.e. after this call
241 // size() will report the old size() plus delta) but without
242 // initializing the expanded region. The expanded region is
243 // zero-terminated. Returns a pointer to the memory to be
244 // initialized (the beginning of the expanded portion). The caller
245 // is expected to fill the expanded area appropriately.
246 Char* expand_noinit(size_t delta);
247 // Expands the string by one character and sets the last character
249 void push_back(Char c);
250 // Returns the string's size.
252 // Returns the string's capacity, i.e. maximum size that the string
253 // can grow to without reallocation. Note that for reference counted
254 // strings that's technically a lie - even assigning characters
255 // within the existing size would cause a reallocation.
256 size_t capacity() const;
257 // Returns true if the data underlying the string is actually shared
258 // across multiple strings (in a refcounted fashion).
259 bool isShared() const;
260 // Makes sure that at least minCapacity characters are available for
261 // the string without reallocation. For reference-counted strings,
262 // it should fork the data even if minCapacity < size().
263 void reserve(size_t minCapacity);
266 fbstring_core_model& operator=(const fbstring_core_model &);
271 * This is the core of the string. The code should work on 32- and
272 * 64-bit and both big- and little-endianan architectures with any
275 * The storage is selected as follows (assuming we store one-byte
276 * characters on a 64-bit machine): (a) "small" strings between 0 and
277 * 23 chars are stored in-situ without allocation (the rightmost byte
278 * stores the size); (b) "medium" strings from 24 through 254 chars
279 * are stored in malloc-allocated memory that is copied eagerly; (c)
280 * "large" strings of 255 chars and above are stored in a similar
281 * structure as medium arrays, except that the string is
282 * reference-counted and copied lazily. the reference count is
283 * allocated right before the character array.
285 * The discriminator between these three strategies sits in two
286 * bits of the rightmost char of the storage. If neither is set, then the
287 * string is small (and its length sits in the lower-order bits on
288 * little-endian or the high-order bits on big-endian of that
289 * rightmost character). If the MSb is set, the string is medium width.
290 * If the second MSb is set, then the string is large. On little-endian,
291 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
292 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
293 * and big-endian fbstring_core equivalent with merely different ops used
294 * to extract capacity/category.
296 template <class Char> class fbstring_core {
298 fbstring_core() noexcept { reset(); }
300 fbstring_core(const fbstring_core & rhs) {
301 assert(&rhs != this);
302 // Simplest case first: small strings are bitblitted
303 if (rhs.category() == Category::isSmall) {
304 static_assert(offsetof(MediumLarge, data_) == 0,
305 "fbstring layout failure");
306 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
307 "fbstring layout failure");
308 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
309 "fbstring layout failure");
310 // Just write the whole thing, don't look at details. In
311 // particular we need to copy capacity anyway because we want
312 // to set the size (don't forget that the last character,
313 // which stores a short string's length, is shared with the
314 // ml_.capacity field).
316 assert(category() == Category::isSmall && this->size() == rhs.size());
317 } else if (rhs.category() == Category::isLarge) {
318 // Large strings are just refcounted
320 RefCounted::incrementRefs(ml_.data_);
321 assert(category() == Category::isLarge && size() == rhs.size());
323 // Medium strings are copied eagerly. Don't forget to allocate
324 // one extra Char for the null terminator.
325 auto const allocSize =
326 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
327 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
328 // Also copies terminator.
329 fbstring_detail::pod_copy(rhs.ml_.data_,
330 rhs.ml_.data_ + rhs.ml_.size_ + 1,
332 ml_.size_ = rhs.ml_.size_;
333 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
334 assert(category() == Category::isMedium);
336 assert(size() == rhs.size());
337 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
340 fbstring_core(fbstring_core&& goner) noexcept {
343 if (goner.category() != Category::isSmall) {
344 // Clean goner's carcass
349 // NOTE(agallagher): The word-aligned copy path copies bytes which are
350 // outside the range of the string, and makes address sanitizer unhappy,
351 // so just disable it on this function.
352 fbstring_core(const Char *const data, const size_t size)
353 FBSTRING_DISABLE_ADDRESS_SANITIZER {
355 #ifndef _LIBSTDCXX_FBSTRING
357 assert(this->size() == size);
358 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
363 // Simplest case first: small strings are bitblitted
364 if (size <= maxSmallSize) {
365 // Layout is: Char* data_, size_t size_, size_t capacity_
366 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
367 "fbstring has unexpected size");
368 static_assert(sizeof(Char*) == sizeof(size_t),
369 "fbstring size assumption violation");
370 // sizeof(size_t) must be a power of 2
371 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
372 "fbstring size assumption violation");
374 // If data is aligned, use fast word-wise copying. Otherwise,
375 // use conservative memcpy.
376 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
377 fbstring_detail::pod_copy(data, data + size, small_);
379 // Copy one word at a time
380 const size_t byteSize = size * sizeof(Char);
381 constexpr size_t wordWidth = sizeof(size_t);
382 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
384 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
386 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
388 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
395 if (size <= maxMediumSize) {
396 // Medium strings are allocated normally. Don't forget to
397 // allocate one extra Char for the terminating null.
398 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
399 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
400 fbstring_detail::pod_copy(data, data + size, ml_.data_);
402 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
404 // Large strings are allocated differently
405 size_t effectiveCapacity = size;
406 auto const newRC = RefCounted::create(data, & effectiveCapacity);
407 ml_.data_ = newRC->data_;
409 ml_.setCapacity(effectiveCapacity, Category::isLarge);
411 ml_.data_[size] = '\0';
415 ~fbstring_core() noexcept {
416 auto const c = category();
417 if (c == Category::isSmall) {
420 if (c == Category::isMedium) {
424 RefCounted::decrementRefs(ml_.data_);
427 // Snatches a previously mallocated string. The parameter "size"
428 // is the size of the string, and the parameter "allocatedSize"
429 // is the size of the mallocated block. The string must be
430 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
432 // So if you want a 2-character string, pass malloc(3) as "data",
433 // pass 2 as "size", and pass 3 as "allocatedSize".
434 fbstring_core(Char * const data,
436 const size_t allocatedSize,
437 AcquireMallocatedString) {
439 assert(allocatedSize >= size + 1);
440 assert(data[size] == '\0');
441 // Use the medium string storage
444 // Don't forget about null terminator
445 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
447 // No need for the memory
453 // swap below doesn't test whether &rhs == this (and instead
454 // potentially does extra work) on the premise that the rarity of
455 // that situation actually makes the check more expensive than is
457 void swap(fbstring_core & rhs) {
463 // In C++11 data() and c_str() are 100% equivalent.
464 const Char * data() const {
468 Char * mutable_data() {
469 auto const c = category();
470 if (c == Category::isSmall) {
473 assert(c == Category::isMedium || c == Category::isLarge);
474 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
476 size_t effectiveCapacity = ml_.capacity();
477 auto const newRC = RefCounted::create(& effectiveCapacity);
478 // If this fails, someone placed the wrong capacity in an
480 assert(effectiveCapacity >= ml_.capacity());
481 // Also copies terminator.
482 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
484 RefCounted::decrementRefs(ml_.data_);
485 ml_.data_ = newRC->data_;
490 const Char * c_str() const {
491 auto const c = category();
492 if (c == Category::isSmall) {
493 assert(small_[smallSize()] == '\0');
496 assert(c == Category::isMedium || c == Category::isLarge);
497 assert(ml_.data_[ml_.size_] == '\0');
501 void shrink(const size_t delta) {
502 if (category() == Category::isSmall) {
503 // Check for underflow
504 assert(delta <= smallSize());
505 setSmallSize(smallSize() - delta);
506 } else if (category() == Category::isMedium ||
507 RefCounted::refs(ml_.data_) == 1) {
508 // Medium strings and unique large strings need no special
510 assert(ml_.size_ >= delta);
512 ml_.data_[ml_.size_] = '\0';
514 assert(ml_.size_ >= delta);
515 // Shared large string, must make unique. This is because of the
516 // durn terminator must be written, which may trample the shared
519 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
521 // No need to write the terminator.
525 void reserve(size_t minCapacity) {
526 if (category() == Category::isLarge) {
528 if (RefCounted::refs(ml_.data_) > 1) {
529 // We must make it unique regardless; in-place reallocation is
530 // useless if the string is shared. In order to not surprise
531 // people, reserve the new block at current capacity or
532 // more. That way, a string's capacity never shrinks after a
534 minCapacity = std::max(minCapacity, ml_.capacity());
535 auto const newRC = RefCounted::create(& minCapacity);
536 // Also copies terminator.
537 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
539 RefCounted::decrementRefs(ml_.data_);
540 ml_.data_ = newRC->data_;
541 ml_.setCapacity(minCapacity, Category::isLarge);
542 // size remains unchanged
544 // String is not shared, so let's try to realloc (if needed)
545 if (minCapacity > ml_.capacity()) {
546 // Asking for more memory
548 RefCounted::reallocate(ml_.data_, ml_.size_,
549 ml_.capacity(), minCapacity);
550 ml_.data_ = newRC->data_;
551 ml_.setCapacity(minCapacity, Category::isLarge);
553 assert(capacity() >= minCapacity);
555 } else if (category() == Category::isMedium) {
556 // String is not shared
557 if (minCapacity <= ml_.capacity()) {
558 return; // nothing to do, there's enough room
560 if (minCapacity <= maxMediumSize) {
561 // Keep the string at medium size. Don't forget to allocate
562 // one extra Char for the terminating null.
563 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
564 // Also copies terminator.
565 ml_.data_ = static_cast<Char *>(
568 (ml_.size_ + 1) * sizeof(Char),
569 (ml_.capacity() + 1) * sizeof(Char),
571 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
573 // Conversion from medium to large string
574 fbstring_core nascent;
575 // Will recurse to another branch of this function
576 nascent.reserve(minCapacity);
577 nascent.ml_.size_ = ml_.size_;
578 // Also copies terminator.
579 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
582 assert(capacity() >= minCapacity);
585 assert(category() == Category::isSmall);
586 if (minCapacity > maxMediumSize) {
588 auto const newRC = RefCounted::create(& minCapacity);
589 auto const size = smallSize();
590 // Also copies terminator.
591 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
592 ml_.data_ = newRC->data_;
594 ml_.setCapacity(minCapacity, Category::isLarge);
595 assert(capacity() >= minCapacity);
596 } else if (minCapacity > maxSmallSize) {
598 // Don't forget to allocate one extra Char for the terminating null
599 auto const allocSizeBytes =
600 goodMallocSize((1 + minCapacity) * sizeof(Char));
601 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
602 auto const size = smallSize();
603 // Also copies terminator.
604 fbstring_detail::pod_copy(small_, small_ + size + 1, pData);
607 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
610 // Nothing to do, everything stays put
613 assert(capacity() >= minCapacity);
616 Char * expand_noinit(const size_t delta) {
617 // Strategy is simple: make room, then change size
618 assert(capacity() >= size());
620 if (category() == Category::isSmall) {
623 if (newSz <= maxSmallSize) {
630 newSz = ml_.size_ + delta;
631 if (newSz > capacity()) {
635 assert(capacity() >= newSz);
636 // Category can't be small - we took care of that above
637 assert(category() == Category::isMedium || category() == Category::isLarge);
639 ml_.data_[newSz] = '\0';
640 assert(size() == newSz);
641 return ml_.data_ + sz;
644 void push_back(Char c) {
645 assert(capacity() >= size());
647 if (category() == Category::isSmall) {
649 if (FBSTRING_LIKELY(sz < maxSmallSize)) {
651 setSmallSize(sz + 1);
654 reserve(maxSmallSize * 2);
657 if (sz == capacity()) { // always true for isShared()
658 reserve(1 + sz * 3 / 2); // ensures not shared
662 assert(capacity() >= sz + 1);
663 // Category can't be small - we took care of that above
664 assert(category() == Category::isMedium || category() == Category::isLarge);
667 ml_.data_[sz + 1] = '\0';
670 size_t size() const {
671 return category() == Category::isSmall ? smallSize() : ml_.size_;
674 size_t capacity() const {
675 switch (category()) {
676 case Category::isSmall:
678 case Category::isLarge:
679 // For large-sized strings, a multi-referenced chunk has no
680 // available capacity. This is because any attempt to append
681 // data would trigger a new allocation.
682 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
685 return ml_.capacity();
688 bool isShared() const {
689 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
694 fbstring_core & operator=(const fbstring_core & rhs);
696 // Equivalent to setSmallSize(0) but a few ns faster in
699 ml_.capacity_ = kIsLittleEndian
700 ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
703 assert(category() == Category::isSmall && size() == 0);
707 std::atomic<size_t> refCount_;
710 static RefCounted * fromData(Char * p) {
711 return static_cast<RefCounted*>(
713 static_cast<unsigned char*>(static_cast<void*>(p))
714 - sizeof(refCount_)));
717 static size_t refs(Char * p) {
718 return fromData(p)->refCount_.load(std::memory_order_acquire);
721 static void incrementRefs(Char * p) {
722 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
725 static void decrementRefs(Char * p) {
726 auto const dis = fromData(p);
727 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
734 static RefCounted * create(size_t * size) {
735 // Don't forget to allocate one extra Char for the terminating
736 // null. In this case, however, one Char is already part of the
738 const size_t allocSize = goodMallocSize(
739 sizeof(RefCounted) + *size * sizeof(Char));
740 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
741 result->refCount_.store(1, std::memory_order_release);
742 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
746 static RefCounted * create(const Char * data, size_t * size) {
747 const size_t effectiveSize = *size;
748 auto result = create(size);
749 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
753 static RefCounted * reallocate(Char *const data,
754 const size_t currentSize,
755 const size_t currentCapacity,
756 const size_t newCapacity) {
757 assert(newCapacity > 0 && newCapacity > currentSize);
758 auto const dis = fromData(data);
759 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
760 // Don't forget to allocate one extra Char for the terminating
761 // null. In this case, however, one Char is already part of the
763 auto result = static_cast<RefCounted*>(
765 sizeof(RefCounted) + currentSize * sizeof(Char),
766 sizeof(RefCounted) + currentCapacity * sizeof(Char),
767 sizeof(RefCounted) + newCapacity * sizeof(Char)));
768 assert(result->refCount_.load(std::memory_order_acquire) == 1);
773 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
776 enum class Category : category_type {
778 isMedium = kIsLittleEndian
779 ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
781 isLarge = kIsLittleEndian
782 ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
786 Category category() const {
787 // works for both big-endian and little-endian
788 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
796 size_t capacity() const {
797 return kIsLittleEndian
798 ? capacity_ & capacityExtractMask
802 void setCapacity(size_t cap, Category cat) {
803 capacity_ = kIsLittleEndian
804 ? cap | static_cast<category_type>(cat)
805 : (cap << 2) | static_cast<category_type>(cat);
810 Char small_[sizeof(MediumLarge) / sizeof(Char)];
815 lastChar = sizeof(MediumLarge) - 1,
816 maxSmallSize = lastChar / sizeof(Char),
817 maxMediumSize = 254 / sizeof(Char), // coincides with the small
818 // bin size in dlmalloc
819 categoryExtractMask = kIsLittleEndian
820 ? sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000
822 capacityExtractMask = kIsLittleEndian
823 ? ~categoryExtractMask
826 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
827 "Corrupt memory layout for fbstring.");
829 size_t smallSize() const {
830 assert(category() == Category::isSmall);
831 constexpr auto shift = kIsLittleEndian ? 0 : 2;
832 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
833 assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
834 return static_cast<size_t>(maxSmallSize) - smallShifted;
837 void setSmallSize(size_t s) {
838 // Warning: this should work with uninitialized strings too,
839 // so don't assume anything about the previous value of
840 // small_[maxSmallSize].
841 assert(s <= maxSmallSize);
842 constexpr auto shift = kIsLittleEndian ? 0 : 2;
843 small_[maxSmallSize] = (maxSmallSize - s) << shift;
845 assert(category() == Category::isSmall && size() == s);
849 #ifndef _LIBSTDCXX_FBSTRING
851 * Dummy fbstring core that uses an actual std::string. This doesn't
852 * make any sense - it's just for testing purposes.
854 template <class Char>
855 class dummy_fbstring_core {
857 dummy_fbstring_core() {
859 dummy_fbstring_core(const dummy_fbstring_core& another)
860 : backend_(another.backend_) {
862 dummy_fbstring_core(const Char * s, size_t n)
865 void swap(dummy_fbstring_core & rhs) {
866 backend_.swap(rhs.backend_);
868 const Char * data() const {
869 return backend_.data();
871 Char * mutable_data() {
872 //assert(!backend_.empty());
873 return &*backend_.begin();
875 void shrink(size_t delta) {
876 assert(delta <= size());
877 backend_.resize(size() - delta);
879 Char * expand_noinit(size_t delta) {
880 auto const sz = size();
881 backend_.resize(size() + delta);
882 return backend_.data() + sz;
884 void push_back(Char c) {
885 backend_.push_back(c);
887 size_t size() const {
888 return backend_.size();
890 size_t capacity() const {
891 return backend_.capacity();
893 bool isShared() const {
896 void reserve(size_t minCapacity) {
897 backend_.reserve(minCapacity);
901 std::basic_string<Char> backend_;
903 #endif // !_LIBSTDCXX_FBSTRING
906 * This is the basic_string replacement. For conformity,
907 * basic_fbstring takes the same template parameters, plus the last
908 * one which is the core.
910 #ifdef _LIBSTDCXX_FBSTRING
911 template <typename E, class T, class A, class Storage>
913 template <typename E,
914 class T = std::char_traits<E>,
915 class A = std::allocator<E>,
916 class Storage = fbstring_core<E> >
918 class basic_fbstring {
922 void (*throw_exc)(const char*),
924 if (!condition) throw_exc(msg);
927 bool isSane() const {
930 empty() == (size() == 0) &&
931 empty() == (begin() == end()) &&
932 size() <= max_size() &&
933 capacity() <= max_size() &&
934 size() <= capacity() &&
935 begin()[size()] == '\0';
939 friend struct Invariant;
942 explicit Invariant(const basic_fbstring& s) : s_(s) {
949 const basic_fbstring& s_;
951 explicit Invariant(const basic_fbstring&) {}
953 Invariant& operator=(const Invariant&);
958 typedef T traits_type;
959 typedef typename traits_type::char_type value_type;
960 typedef A allocator_type;
961 typedef typename A::size_type size_type;
962 typedef typename A::difference_type difference_type;
964 typedef typename A::reference reference;
965 typedef typename A::const_reference const_reference;
966 typedef typename A::pointer pointer;
967 typedef typename A::const_pointer const_pointer;
970 typedef const E* const_iterator;
971 typedef std::reverse_iterator<iterator
972 #ifdef NO_ITERATOR_TRAITS
976 typedef std::reverse_iterator<const_iterator
977 #ifdef NO_ITERATOR_TRAITS
980 > const_reverse_iterator;
982 static const size_type npos; // = size_type(-1)
985 static void procrustes(size_type& n, size_type nmax) {
986 if (n > nmax) n = nmax;
990 // C++11 21.4.2 construct/copy/destroy
992 // Note: while the following two constructors can be (and previously were)
993 // collapsed into one constructor written this way:
995 // explicit basic_fbstring(const A& a = A()) noexcept { }
997 // This can cause Clang (at least version 3.7) to fail with the error:
998 // "chosen constructor is explicit in copy-initialization ...
999 // in implicit initialization of field '(x)' with omitted initializer"
1001 // if used in a struct which is default-initialized. Hence the split into
1002 // these two separate constructors.
1004 basic_fbstring() noexcept : basic_fbstring(A()) {
1007 explicit basic_fbstring(const A&) noexcept {
1010 basic_fbstring(const basic_fbstring& str)
1011 : store_(str.store_) {
1015 basic_fbstring(basic_fbstring&& goner) noexcept
1016 : store_(std::move(goner.store_)) {
1019 #ifndef _LIBSTDCXX_FBSTRING
1020 // This is defined for compatibility with std::string
1021 /* implicit */ basic_fbstring(const std::string& str)
1022 : store_(str.data(), str.size()) {
1026 basic_fbstring(const basic_fbstring& str,
1029 const A& /* a */ = A()) {
1030 assign(str, pos, n);
1033 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1035 ? traits_type::length(s)
1036 : (std::__throw_logic_error(
1037 "basic_fbstring: null pointer initializer not valid"),
1041 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1045 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1046 auto const pData = store_.expand_noinit(n);
1047 fbstring_detail::pod_fill(pData, pData + n, c);
1050 template <class InIt>
1051 basic_fbstring(InIt begin, InIt end,
1052 typename std::enable_if<
1053 !std::is_same<typename std::remove_const<InIt>::type,
1054 value_type*>::value, const A>::type & /*a*/ = A()) {
1058 // Specialization for const char*, const char*
1059 basic_fbstring(const value_type* b, const value_type* e)
1060 : store_(b, e - b) {
1063 // Nonstandard constructor
1064 basic_fbstring(value_type *s, size_type n, size_type c,
1065 AcquireMallocatedString a)
1066 : store_(s, n, c, a) {
1069 // Construction from initialization list
1070 basic_fbstring(std::initializer_list<value_type> il) {
1071 assign(il.begin(), il.end());
1074 ~basic_fbstring() noexcept {
1077 basic_fbstring& operator=(const basic_fbstring& lhs) {
1078 Invariant checker(*this);
1080 if (FBSTRING_UNLIKELY(&lhs == this)) {
1083 auto const oldSize = size();
1084 auto const srcSize = lhs.size();
1085 if (capacity() >= srcSize && !store_.isShared()) {
1086 // great, just copy the contents
1087 if (oldSize < srcSize) {
1088 store_.expand_noinit(srcSize - oldSize);
1090 store_.shrink(oldSize - srcSize);
1092 assert(size() == srcSize);
1093 auto srcData = lhs.data();
1094 fbstring_detail::pod_copy(
1095 srcData, srcData + srcSize, store_.mutable_data());
1097 // need to reallocate, so we may as well create a brand new string
1098 basic_fbstring(lhs).swap(*this);
1104 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1105 if (FBSTRING_UNLIKELY(&goner == this)) {
1106 // Compatibility with std::basic_string<>,
1107 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1110 // No need of this anymore
1111 this->~basic_fbstring();
1112 // Move the goner into this
1113 new(&store_) fbstring_core<E>(std::move(goner.store_));
1117 #ifndef _LIBSTDCXX_FBSTRING
1118 // Compatibility with std::string
1119 basic_fbstring & operator=(const std::string & rhs) {
1120 return assign(rhs.data(), rhs.size());
1123 // Compatibility with std::string
1124 std::string toStdString() const {
1125 return std::string(data(), size());
1128 // A lot of code in fbcode still uses this method, so keep it here for now.
1129 const basic_fbstring& toStdString() const {
1134 basic_fbstring& operator=(const value_type* s) {
1138 basic_fbstring& operator=(value_type c) {
1139 Invariant checker(*this);
1142 store_.expand_noinit(1);
1143 } else if (store_.isShared()) {
1144 basic_fbstring(1, c).swap(*this);
1147 store_.shrink(size() - 1);
1153 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1154 return assign(il.begin(), il.end());
1157 // C++11 21.4.3 iterators:
1158 iterator begin() { return store_.mutable_data(); }
1160 const_iterator begin() const { return store_.data(); }
1162 const_iterator cbegin() const { return begin(); }
1165 return store_.mutable_data() + store_.size();
1168 const_iterator end() const {
1169 return store_.data() + store_.size();
1172 const_iterator cend() const { return end(); }
1174 reverse_iterator rbegin() {
1175 return reverse_iterator(end());
1178 const_reverse_iterator rbegin() const {
1179 return const_reverse_iterator(end());
1182 const_reverse_iterator crbegin() const { return rbegin(); }
1184 reverse_iterator rend() {
1185 return reverse_iterator(begin());
1188 const_reverse_iterator rend() const {
1189 return const_reverse_iterator(begin());
1192 const_reverse_iterator crend() const { return rend(); }
1195 // C++11 21.4.5, element access:
1196 const value_type& front() const { return *begin(); }
1197 const value_type& back() const {
1199 // Should be begin()[size() - 1], but that branches twice
1200 return *(end() - 1);
1202 value_type& front() { return *begin(); }
1203 value_type& back() {
1205 // Should be begin()[size() - 1], but that branches twice
1206 return *(end() - 1);
1213 // C++11 21.4.4 capacity:
1214 size_type size() const { return store_.size(); }
1216 size_type length() const { return size(); }
1218 size_type max_size() const {
1219 return std::numeric_limits<size_type>::max();
1222 void resize(const size_type n, const value_type c = value_type()) {
1223 Invariant checker(*this);
1225 auto size = this->size();
1227 store_.shrink(size - n);
1229 auto const delta = n - size;
1230 auto pData = store_.expand_noinit(delta);
1231 fbstring_detail::pod_fill(pData, pData + delta, c);
1233 assert(this->size() == n);
1236 size_type capacity() const { return store_.capacity(); }
1238 void reserve(size_type res_arg = 0) {
1239 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1240 store_.reserve(res_arg);
1243 void shrink_to_fit() {
1244 // Shrink only if slack memory is sufficiently large
1245 if (capacity() < size() * 3 / 2) {
1248 basic_fbstring(cbegin(), cend()).swap(*this);
1251 void clear() { resize(0); }
1253 bool empty() const { return size() == 0; }
1255 // C++11 21.4.5 element access:
1256 const_reference operator[](size_type pos) const {
1257 return *(begin() + pos);
1260 reference operator[](size_type pos) {
1261 return *(begin() + pos);
1264 const_reference at(size_type n) const {
1265 enforce(n <= size(), std::__throw_out_of_range, "");
1269 reference at(size_type n) {
1270 enforce(n < size(), std::__throw_out_of_range, "");
1274 // C++11 21.4.6 modifiers:
1275 basic_fbstring& operator+=(const basic_fbstring& str) {
1279 basic_fbstring& operator+=(const value_type* s) {
1283 basic_fbstring& operator+=(const value_type c) {
1288 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1293 basic_fbstring& append(const basic_fbstring& str) {
1295 auto desiredSize = size() + str.size();
1297 append(str.data(), str.size());
1298 assert(size() == desiredSize);
1302 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1304 const size_type sz = str.size();
1305 enforce(pos <= sz, std::__throw_out_of_range, "");
1306 procrustes(n, sz - pos);
1307 return append(str.data() + pos, n);
1310 basic_fbstring& append(const value_type* s, size_type n) {
1311 Invariant checker(*this);
1313 if (FBSTRING_UNLIKELY(!n)) {
1314 // Unlikely but must be done
1317 auto const oldSize = size();
1318 auto const oldData = data();
1319 // Check for aliasing (rare). We could use "<=" here but in theory
1320 // those do not work for pointers unless the pointers point to
1321 // elements in the same array. For that reason we use
1322 // std::less_equal, which is guaranteed to offer a total order
1323 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1325 std::less_equal<const value_type*> le;
1326 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1327 assert(le(s + n, oldData + oldSize));
1328 const size_type offset = s - oldData;
1329 store_.reserve(oldSize + n);
1330 // Restore the source
1331 s = data() + offset;
1333 // Warning! Repeated appends with short strings may actually incur
1334 // practically quadratic performance. Avoid that by pushing back
1335 // the first character (which ensures exponential growth) and then
1336 // appending the rest normally. Worst case the append may incur a
1337 // second allocation but that will be rare.
1340 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1341 assert(size() == oldSize + n + 1);
1345 basic_fbstring& append(const value_type* s) {
1346 return append(s, traits_type::length(s));
1349 basic_fbstring& append(size_type n, value_type c) {
1350 resize(size() + n, c);
1354 template<class InputIterator>
1355 basic_fbstring& append(InputIterator first, InputIterator last) {
1356 insert(end(), first, last);
1360 basic_fbstring& append(std::initializer_list<value_type> il) {
1361 return append(il.begin(), il.end());
1364 void push_back(const value_type c) { // primitive
1365 store_.push_back(c);
1368 basic_fbstring& assign(const basic_fbstring& str) {
1369 if (&str == this) return *this;
1370 return assign(str.data(), str.size());
1373 basic_fbstring& assign(basic_fbstring&& str) {
1374 return *this = std::move(str);
1377 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1379 const size_type sz = str.size();
1380 enforce(pos <= sz, std::__throw_out_of_range, "");
1381 procrustes(n, sz - pos);
1382 return assign(str.data() + pos, n);
1385 basic_fbstring& assign(const value_type* s, const size_type n) {
1386 Invariant checker(*this);
1388 // s can alias this, we need to use pod_move.
1390 fbstring_detail::pod_move(s, s + n, store_.mutable_data());
1392 assert(size() == n);
1394 const value_type *const s2 = s + size();
1395 fbstring_detail::pod_move(s, s2, store_.mutable_data());
1396 append(s2, n - size());
1397 assert(size() == n);
1399 assert(size() == n);
1403 basic_fbstring& assign(const value_type* s) {
1404 return assign(s, traits_type::length(s));
1407 basic_fbstring& assign(std::initializer_list<value_type> il) {
1408 return assign(il.begin(), il.end());
1411 template <class ItOrLength, class ItOrChar>
1412 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1413 return replace(begin(), end(), first_or_n, last_or_c);
1416 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1417 return insert(pos1, str.data(), str.size());
1420 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1421 size_type pos2, size_type n) {
1422 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1423 procrustes(n, str.length() - pos2);
1424 return insert(pos1, str.data() + pos2, n);
1427 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1428 enforce(pos <= length(), std::__throw_out_of_range, "");
1429 insert(begin() + pos, s, s + n);
1433 basic_fbstring& insert(size_type pos, const value_type* s) {
1434 return insert(pos, s, traits_type::length(s));
1437 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1438 enforce(pos <= length(), std::__throw_out_of_range, "");
1439 insert(begin() + pos, n, c);
1443 iterator insert(const_iterator p, const value_type c) {
1444 const size_type pos = p - begin();
1446 return begin() + pos;
1449 #ifndef _LIBSTDCXX_FBSTRING
1451 typedef std::basic_istream<value_type, traits_type> istream_type;
1454 friend inline istream_type& getline(istream_type& is,
1455 basic_fbstring& str,
1457 Invariant checker(str);
1462 size_t avail = str.capacity() - size;
1463 // fbstring has 1 byte extra capacity for the null terminator,
1464 // and getline null-terminates the read string.
1465 is.getline(str.store_.expand_noinit(avail), avail + 1, delim);
1466 size += is.gcount();
1468 if (is.bad() || is.eof() || !is.fail()) {
1469 // Done by either failure, end of file, or normal read.
1470 if (!is.bad() && !is.eof()) {
1471 --size; // gcount() also accounts for the delimiter.
1477 assert(size == str.size());
1478 assert(size == str.capacity());
1479 // Start at minimum allocation 63 + terminator = 64.
1480 str.reserve(std::max<size_t>(63, 3 * size / 2));
1481 // Clear the error so we can continue reading.
1487 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1488 return getline(is, str, '\n');
1493 template <int i> class Selector {};
1495 iterator insertImplDiscr(const_iterator p,
1496 size_type n, value_type c, Selector<1>) {
1497 Invariant checker(*this);
1499 auto const pos = p - begin();
1500 assert(p >= begin() && p <= end());
1501 if (capacity() - size() < n) {
1502 const size_type sz = p - begin();
1503 reserve(size() + n);
1506 const iterator oldEnd = end();
1507 if (n < size_type(oldEnd - p)) {
1508 append(oldEnd - n, oldEnd);
1509 // Also copies terminator.
1510 fbstring_detail::pod_move(&*p, &*oldEnd - n + 1, begin() + pos + n);
1511 std::fill(begin() + pos, begin() + pos + n, c);
1513 append(n - (end() - p), c);
1514 append(iterator(p), oldEnd);
1515 std::fill(iterator(p), oldEnd, c);
1517 return begin() + pos;
1520 template<class InputIter>
1521 iterator insertImplDiscr(const_iterator i,
1522 InputIter b, InputIter e, Selector<0>) {
1523 return insertImpl(i, b, e,
1524 typename std::iterator_traits<InputIter>::iterator_category());
1527 template <class FwdIterator>
1528 iterator insertImpl(const_iterator i,
1529 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1530 Invariant checker(*this);
1532 const size_type pos = i - begin();
1533 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1534 std::distance(s1, s2);
1536 using namespace fbstring_detail;
1537 assert(pos <= size());
1539 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1540 capacity() - size();
1542 // realloc the string
1543 reserve(size() + n2);
1546 if (pos + n2 <= size()) {
1547 const iterator tailBegin = end() - n2;
1548 store_.expand_noinit(n2);
1549 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1550 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1551 reverse_iterator(tailBegin + n2));
1552 std::copy(s1, s2, begin() + pos);
1555 const size_type old_size = size();
1556 std::advance(t, old_size - pos);
1557 const size_t newElems = std::distance(t, s2);
1558 store_.expand_noinit(n2);
1559 std::copy(t, s2, begin() + old_size);
1560 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1561 begin() + old_size + newElems);
1562 std::copy(s1, t, begin() + pos);
1564 return begin() + pos;
1567 template <class InputIterator>
1568 iterator insertImpl(const_iterator i,
1569 InputIterator b, InputIterator e,
1570 std::input_iterator_tag) {
1571 const auto pos = i - begin();
1572 basic_fbstring temp(begin(), i);
1573 for (; b != e; ++b) {
1576 temp.append(i, cend());
1578 return begin() + pos;
1582 template <class ItOrLength, class ItOrChar>
1583 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1584 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1585 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1588 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1589 return insert(p, il.begin(), il.end());
1592 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1593 Invariant checker(*this);
1595 enforce(pos <= length(), std::__throw_out_of_range, "");
1596 procrustes(n, length() - pos);
1597 std::copy(begin() + pos + n, end(), begin() + pos);
1598 resize(length() - n);
1602 iterator erase(iterator position) {
1603 const size_type pos(position - begin());
1604 enforce(pos <= size(), std::__throw_out_of_range, "");
1606 return begin() + pos;
1609 iterator erase(iterator first, iterator last) {
1610 const size_type pos(first - begin());
1611 erase(pos, last - first);
1612 return begin() + pos;
1615 // Replaces at most n1 chars of *this, starting with pos1 with the
1617 basic_fbstring& replace(size_type pos1, size_type n1,
1618 const basic_fbstring& str) {
1619 return replace(pos1, n1, str.data(), str.size());
1622 // Replaces at most n1 chars of *this, starting with pos1,
1623 // with at most n2 chars of str starting with pos2
1624 basic_fbstring& replace(size_type pos1, size_type n1,
1625 const basic_fbstring& str,
1626 size_type pos2, size_type n2) {
1627 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1628 return replace(pos1, n1, str.data() + pos2,
1629 std::min(n2, str.size() - pos2));
1632 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1633 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1634 return replace(pos, n1, s, traits_type::length(s));
1637 // Replaces at most n1 chars of *this, starting with pos, with n2
1640 // consolidated with
1642 // Replaces at most n1 chars of *this, starting with pos, with at
1643 // most n2 chars of str. str must have at least n2 chars.
1644 template <class StrOrLength, class NumOrChar>
1645 basic_fbstring& replace(size_type pos, size_type n1,
1646 StrOrLength s_or_n2, NumOrChar n_or_c) {
1647 Invariant checker(*this);
1649 enforce(pos <= size(), std::__throw_out_of_range, "");
1650 procrustes(n1, length() - pos);
1651 const iterator b = begin() + pos;
1652 return replace(b, b + n1, s_or_n2, n_or_c);
1655 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1656 return replace(i1, i2, str.data(), str.length());
1659 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1660 return replace(i1, i2, s, traits_type::length(s));
1664 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1665 const value_type* s, size_type n,
1668 assert(begin() <= i1 && i1 <= end());
1669 assert(begin() <= i2 && i2 <= end());
1670 return replace(i1, i2, s, s + n);
1673 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1674 size_type n2, value_type c, Selector<1>) {
1675 const size_type n1 = i2 - i1;
1677 std::fill(i1, i1 + n2, c);
1680 std::fill(i1, i2, c);
1681 insert(i2, n2 - n1, c);
1687 template <class InputIter>
1688 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1689 InputIter b, InputIter e,
1691 replaceImpl(i1, i2, b, e,
1692 typename std::iterator_traits<InputIter>::iterator_category());
1697 template <class FwdIterator>
1698 bool replaceAliased(iterator /* i1 */,
1700 FwdIterator /* s1 */,
1701 FwdIterator /* s2 */,
1706 template <class FwdIterator>
1707 bool replaceAliased(iterator i1, iterator i2,
1708 FwdIterator s1, FwdIterator s2, std::true_type) {
1709 static const std::less_equal<const value_type*> le =
1710 std::less_equal<const value_type*>();
1711 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1715 // Aliased replace, copy to new string
1716 basic_fbstring temp;
1717 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1718 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1723 template <class FwdIterator>
1724 void replaceImpl(iterator i1, iterator i2,
1725 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1726 Invariant checker(*this);
1728 // Handle aliased replace
1729 if (replaceAliased(i1, i2, s1, s2,
1730 std::integral_constant<bool,
1731 std::is_same<FwdIterator, iterator>::value ||
1732 std::is_same<FwdIterator, const_iterator>::value>())) {
1736 auto const n1 = i2 - i1;
1738 auto const n2 = std::distance(s1, s2);
1743 std::copy(s1, s2, i1);
1747 fbstring_detail::copy_n(s1, n1, i1);
1748 std::advance(s1, n1);
1754 template <class InputIterator>
1755 void replaceImpl(iterator i1, iterator i2,
1756 InputIterator b, InputIterator e, std::input_iterator_tag) {
1757 basic_fbstring temp(begin(), i1);
1758 temp.append(b, e).append(i2, end());
1763 template <class T1, class T2>
1764 basic_fbstring& replace(iterator i1, iterator i2,
1765 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1767 num1 = std::numeric_limits<T1>::is_specialized,
1768 num2 = std::numeric_limits<T2>::is_specialized;
1769 return replaceImplDiscr(
1770 i1, i2, first_or_n_or_s, last_or_c_or_n,
1771 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1774 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1775 enforce(pos <= size(), std::__throw_out_of_range, "");
1776 procrustes(n, size() - pos);
1778 fbstring_detail::pod_copy(
1785 void swap(basic_fbstring& rhs) {
1786 store_.swap(rhs.store_);
1789 const value_type* c_str() const {
1790 return store_.c_str();
1793 const value_type* data() const { return c_str(); }
1795 allocator_type get_allocator() const {
1796 return allocator_type();
1799 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1800 return find(str.data(), pos, str.length());
1803 size_type find(const value_type* needle, const size_type pos,
1804 const size_type nsize) const {
1805 if (!nsize) return pos;
1806 auto const size = this->size();
1807 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1808 // that nsize + pos does not wrap around.
1809 if (nsize + pos > size || nsize + pos < pos) return npos;
1810 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1811 // the last characters first
1812 auto const haystack = data();
1813 auto const nsize_1 = nsize - 1;
1814 auto const lastNeedle = needle[nsize_1];
1816 // Boyer-Moore skip value for the last char in the needle. Zero is
1817 // not a valid value; skip will be computed the first time it's
1821 const E * i = haystack + pos;
1822 auto iEnd = haystack + size - nsize_1;
1825 // Boyer-Moore: match the last element in the needle
1826 while (i[nsize_1] != lastNeedle) {
1832 // Here we know that the last char matches
1833 // Continue in pedestrian mode
1834 for (size_t j = 0; ; ) {
1836 if (i[j] != needle[j]) {
1837 // Not found, we can skip
1838 // Compute the skip value lazily
1841 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1848 // Check if done searching
1851 return i - haystack;
1858 size_type find(const value_type* s, size_type pos = 0) const {
1859 return find(s, pos, traits_type::length(s));
1862 size_type find (value_type c, size_type pos = 0) const {
1863 return find(&c, pos, 1);
1866 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1867 return rfind(str.data(), pos, str.length());
1870 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1871 if (n > length()) return npos;
1872 pos = std::min(pos, length() - n);
1873 if (n == 0) return pos;
1875 const_iterator i(begin() + pos);
1877 if (traits_type::eq(*i, *s)
1878 && traits_type::compare(&*i, s, n) == 0) {
1881 if (i == begin()) break;
1886 size_type rfind(const value_type* s, size_type pos = npos) const {
1887 return rfind(s, pos, traits_type::length(s));
1890 size_type rfind(value_type c, size_type pos = npos) const {
1891 return rfind(&c, pos, 1);
1894 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1895 return find_first_of(str.data(), pos, str.length());
1898 size_type find_first_of(const value_type* s,
1899 size_type pos, size_type n) const {
1900 if (pos > length() || n == 0) return npos;
1901 const_iterator i(begin() + pos),
1903 for (; i != finish; ++i) {
1904 if (traits_type::find(s, n, *i) != 0) {
1911 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1912 return find_first_of(s, pos, traits_type::length(s));
1915 size_type find_first_of(value_type c, size_type pos = 0) const {
1916 return find_first_of(&c, pos, 1);
1919 size_type find_last_of (const basic_fbstring& str,
1920 size_type pos = npos) const {
1921 return find_last_of(str.data(), pos, str.length());
1924 size_type find_last_of (const value_type* s, size_type pos,
1925 size_type n) const {
1926 if (!empty() && n > 0) {
1927 pos = std::min(pos, length() - 1);
1928 const_iterator i(begin() + pos);
1930 if (traits_type::find(s, n, *i) != 0) {
1933 if (i == begin()) break;
1939 size_type find_last_of (const value_type* s,
1940 size_type pos = npos) const {
1941 return find_last_of(s, pos, traits_type::length(s));
1944 size_type find_last_of (value_type c, size_type pos = npos) const {
1945 return find_last_of(&c, pos, 1);
1948 size_type find_first_not_of(const basic_fbstring& str,
1949 size_type pos = 0) const {
1950 return find_first_not_of(str.data(), pos, str.size());
1953 size_type find_first_not_of(const value_type* s, size_type pos,
1954 size_type n) const {
1955 if (pos < length()) {
1959 for (; i != finish; ++i) {
1960 if (traits_type::find(s, n, *i) == 0) {
1968 size_type find_first_not_of(const value_type* s,
1969 size_type pos = 0) const {
1970 return find_first_not_of(s, pos, traits_type::length(s));
1973 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1974 return find_first_not_of(&c, pos, 1);
1977 size_type find_last_not_of(const basic_fbstring& str,
1978 size_type pos = npos) const {
1979 return find_last_not_of(str.data(), pos, str.length());
1982 size_type find_last_not_of(const value_type* s, size_type pos,
1983 size_type n) const {
1984 if (!this->empty()) {
1985 pos = std::min(pos, size() - 1);
1986 const_iterator i(begin() + pos);
1988 if (traits_type::find(s, n, *i) == 0) {
1991 if (i == begin()) break;
1997 size_type find_last_not_of(const value_type* s,
1998 size_type pos = npos) const {
1999 return find_last_not_of(s, pos, traits_type::length(s));
2002 size_type find_last_not_of (value_type c, size_type pos = npos) const {
2003 return find_last_not_of(&c, pos, 1);
2006 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
2007 enforce(pos <= size(), std::__throw_out_of_range, "");
2008 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2011 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
2012 enforce(pos <= size(), std::__throw_out_of_range, "");
2014 if (n < size()) resize(n);
2015 return std::move(*this);
2018 int compare(const basic_fbstring& str) const {
2019 // FIX due to Goncalo N M de Carvalho July 18, 2005
2020 return compare(0, size(), str);
2023 int compare(size_type pos1, size_type n1,
2024 const basic_fbstring& str) const {
2025 return compare(pos1, n1, str.data(), str.size());
2028 int compare(size_type pos1, size_type n1,
2029 const value_type* s) const {
2030 return compare(pos1, n1, s, traits_type::length(s));
2033 int compare(size_type pos1, size_type n1,
2034 const value_type* s, size_type n2) const {
2035 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2036 procrustes(n1, size() - pos1);
2037 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2038 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2039 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2042 int compare(size_type pos1, size_type n1,
2043 const basic_fbstring& str,
2044 size_type pos2, size_type n2) const {
2045 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2046 return compare(pos1, n1, str.data() + pos2,
2047 std::min(n2, str.size() - pos2));
2050 // Code from Jean-Francois Bastien (03/26/2007)
2051 int compare(const value_type* s) const {
2052 // Could forward to compare(0, size(), s, traits_type::length(s))
2053 // but that does two extra checks
2054 const size_type n1(size()), n2(traits_type::length(s));
2055 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2056 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2064 // non-member functions
2066 template <typename E, class T, class A, class S>
2068 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2069 const basic_fbstring<E, T, A, S>& rhs) {
2071 basic_fbstring<E, T, A, S> result;
2072 result.reserve(lhs.size() + rhs.size());
2073 result.append(lhs).append(rhs);
2074 return std::move(result);
2078 template <typename E, class T, class A, class S>
2080 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2081 const basic_fbstring<E, T, A, S>& rhs) {
2082 return std::move(lhs.append(rhs));
2086 template <typename E, class T, class A, class S>
2088 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2089 basic_fbstring<E, T, A, S>&& rhs) {
2090 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2091 // Good, at least we don't need to reallocate
2092 return std::move(rhs.insert(0, lhs));
2094 // Meh, no go. Forward to operator+(const&, const&).
2095 auto const& rhsC = rhs;
2100 template <typename E, class T, class A, class S>
2102 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2103 basic_fbstring<E, T, A, S>&& rhs) {
2104 return std::move(lhs.append(rhs));
2108 template <typename E, class T, class A, class S>
2110 basic_fbstring<E, T, A, S> operator+(
2112 const basic_fbstring<E, T, A, S>& rhs) {
2114 basic_fbstring<E, T, A, S> result;
2115 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2116 result.reserve(len + rhs.size());
2117 result.append(lhs, len).append(rhs);
2122 template <typename E, class T, class A, class S>
2124 basic_fbstring<E, T, A, S> operator+(
2126 basic_fbstring<E, T, A, S>&& rhs) {
2128 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2129 if (rhs.capacity() >= len + rhs.size()) {
2130 // Good, at least we don't need to reallocate
2131 rhs.insert(rhs.begin(), lhs, lhs + len);
2134 // Meh, no go. Do it by hand since we have len already.
2135 basic_fbstring<E, T, A, S> result;
2136 result.reserve(len + rhs.size());
2137 result.append(lhs, len).append(rhs);
2142 template <typename E, class T, class A, class S>
2144 basic_fbstring<E, T, A, S> operator+(
2146 const basic_fbstring<E, T, A, S>& rhs) {
2148 basic_fbstring<E, T, A, S> result;
2149 result.reserve(1 + rhs.size());
2150 result.push_back(lhs);
2156 template <typename E, class T, class A, class S>
2158 basic_fbstring<E, T, A, S> operator+(
2160 basic_fbstring<E, T, A, S>&& rhs) {
2162 if (rhs.capacity() > rhs.size()) {
2163 // Good, at least we don't need to reallocate
2164 rhs.insert(rhs.begin(), lhs);
2167 // Meh, no go. Forward to operator+(E, const&).
2168 auto const& rhsC = rhs;
2173 template <typename E, class T, class A, class S>
2175 basic_fbstring<E, T, A, S> operator+(
2176 const basic_fbstring<E, T, A, S>& lhs,
2179 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2180 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2182 basic_fbstring<E, T, A, S> result;
2183 const size_type len = traits_type::length(rhs);
2184 result.reserve(lhs.size() + len);
2185 result.append(lhs).append(rhs, len);
2189 // C++11 21.4.8.1/10
2190 template <typename E, class T, class A, class S>
2192 basic_fbstring<E, T, A, S> operator+(
2193 basic_fbstring<E, T, A, S>&& lhs,
2196 return std::move(lhs += rhs);
2199 // C++11 21.4.8.1/11
2200 template <typename E, class T, class A, class S>
2202 basic_fbstring<E, T, A, S> operator+(
2203 const basic_fbstring<E, T, A, S>& lhs,
2206 basic_fbstring<E, T, A, S> result;
2207 result.reserve(lhs.size() + 1);
2209 result.push_back(rhs);
2213 // C++11 21.4.8.1/12
2214 template <typename E, class T, class A, class S>
2216 basic_fbstring<E, T, A, S> operator+(
2217 basic_fbstring<E, T, A, S>&& lhs,
2220 return std::move(lhs += rhs);
2223 template <typename E, class T, class A, class S>
2225 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2226 const basic_fbstring<E, T, A, S>& rhs) {
2227 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2229 template <typename E, class T, class A, class S>
2231 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2232 const basic_fbstring<E, T, A, S>& rhs) {
2233 return rhs == lhs; }
2235 template <typename E, class T, class A, class S>
2237 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2238 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2239 return lhs.compare(rhs) == 0; }
2241 template <typename E, class T, class A, class S>
2243 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2244 const basic_fbstring<E, T, A, S>& rhs) {
2245 return !(lhs == rhs); }
2247 template <typename E, class T, class A, class S>
2249 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2250 const basic_fbstring<E, T, A, S>& rhs) {
2251 return !(lhs == rhs); }
2253 template <typename E, class T, class A, class S>
2255 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2256 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2257 return !(lhs == rhs); }
2259 template <typename E, class T, class A, class S>
2261 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2262 const basic_fbstring<E, T, A, S>& rhs) {
2263 return lhs.compare(rhs) < 0; }
2265 template <typename E, class T, class A, class S>
2267 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2268 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2269 return lhs.compare(rhs) < 0; }
2271 template <typename E, class T, class A, class S>
2273 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2274 const basic_fbstring<E, T, A, S>& rhs) {
2275 return rhs.compare(lhs) > 0; }
2277 template <typename E, class T, class A, class S>
2279 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2280 const basic_fbstring<E, T, A, S>& rhs) {
2283 template <typename E, class T, class A, class S>
2285 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2286 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2289 template <typename E, class T, class A, class S>
2291 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2292 const basic_fbstring<E, T, A, S>& rhs) {
2295 template <typename E, class T, class A, class S>
2297 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2298 const basic_fbstring<E, T, A, S>& rhs) {
2299 return !(rhs < lhs); }
2301 template <typename E, class T, class A, class S>
2303 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2304 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2305 return !(rhs < lhs); }
2307 template <typename E, class T, class A, class S>
2309 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2310 const basic_fbstring<E, T, A, S>& rhs) {
2311 return !(rhs < lhs); }
2313 template <typename E, class T, class A, class S>
2315 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2316 const basic_fbstring<E, T, A, S>& rhs) {
2317 return !(lhs < rhs); }
2319 template <typename E, class T, class A, class S>
2321 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2322 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2323 return !(lhs < rhs); }
2325 template <typename E, class T, class A, class S>
2327 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2328 const basic_fbstring<E, T, A, S>& rhs) {
2329 return !(lhs < rhs);
2333 template <typename E, class T, class A, class S>
2334 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2338 // TODO: make this faster.
2339 template <typename E, class T, class A, class S>
2342 typename basic_fbstring<E, T, A, S>::value_type,
2343 typename basic_fbstring<E, T, A, S>::traits_type>&
2345 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2346 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2347 basic_fbstring<E, T, A, S>& str) {
2348 typename std::basic_istream<E, T>::sentry sentry(is);
2349 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2350 typename basic_fbstring<E, T, A, S>::traits_type>
2352 typedef typename __istream_type::ios_base __ios_base;
2353 size_t extracted = 0;
2354 auto err = __ios_base::goodbit;
2356 auto n = is.width();
2361 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2362 if (got == T::eof()) {
2363 err |= __ios_base::eofbit;
2367 if (isspace(got)) break;
2369 got = is.rdbuf()->snextc();
2373 err |= __ios_base::failbit;
2381 template <typename E, class T, class A, class S>
2383 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2384 typename basic_fbstring<E, T, A, S>::traits_type>&
2386 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2387 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2388 const basic_fbstring<E, T, A, S>& str) {
2390 typename std::basic_ostream<
2391 typename basic_fbstring<E, T, A, S>::value_type,
2392 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2394 typedef std::ostreambuf_iterator<
2395 typename basic_fbstring<E, T, A, S>::value_type,
2396 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2397 size_t __len = str.size();
2399 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2400 if (__pad_and_output(_Ip(os),
2402 __left ? str.data() + __len : str.data(),
2405 os.fill()).failed()) {
2406 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2409 #elif defined(_MSC_VER)
2410 // MSVC doesn't define __ostream_insert
2411 os.write(str.data(), str.size());
2413 std::__ostream_insert(os, str.data(), str.size());
2418 template <typename E1, class T, class A, class S>
2419 const typename basic_fbstring<E1, T, A, S>::size_type
2420 basic_fbstring<E1, T, A, S>::npos =
2421 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2423 #ifndef _LIBSTDCXX_FBSTRING
2424 // basic_string compatibility routines
2426 template <typename E, class T, class A, class S>
2428 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2429 const std::string& rhs) {
2430 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2433 template <typename E, class T, class A, class S>
2435 bool operator==(const std::string& lhs,
2436 const basic_fbstring<E, T, A, S>& rhs) {
2440 template <typename E, class T, class A, class S>
2442 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2443 const std::string& rhs) {
2444 return !(lhs == rhs);
2447 template <typename E, class T, class A, class S>
2449 bool operator!=(const std::string& lhs,
2450 const basic_fbstring<E, T, A, S>& rhs) {
2451 return !(lhs == rhs);
2454 #if !defined(_LIBSTDCXX_FBSTRING)
2455 typedef basic_fbstring<char> fbstring;
2458 // fbstring is relocatable
2459 template <class T, class R, class A, class S>
2460 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2463 _GLIBCXX_END_NAMESPACE_VERSION
2466 } // namespace folly
2468 #ifndef _LIBSTDCXX_FBSTRING
2470 // Hash functions to make fbstring usable with e.g. hash_map
2472 // Handle interaction with different C++ standard libraries, which
2473 // expect these types to be in different namespaces.
2475 #define FOLLY_FBSTRING_HASH1(T) \
2477 struct hash< ::folly::basic_fbstring<T> > { \
2478 size_t operator()(const ::folly::fbstring& s) const { \
2479 return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2483 // The C++11 standard says that these four are defined
2484 #define FOLLY_FBSTRING_HASH \
2485 FOLLY_FBSTRING_HASH1(char) \
2486 FOLLY_FBSTRING_HASH1(char16_t) \
2487 FOLLY_FBSTRING_HASH1(char32_t) \
2488 FOLLY_FBSTRING_HASH1(wchar_t)
2496 #if FOLLY_HAVE_DEPRECATED_ASSOC
2497 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2498 namespace __gnu_cxx {
2502 } // namespace __gnu_cxx
2503 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2504 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2506 #undef FOLLY_FBSTRING_HASH
2507 #undef FOLLY_FBSTRING_HASH1
2509 #endif // _LIBSTDCXX_FBSTRING
2511 #pragma GCC diagnostic pop
2513 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2515 #undef FBSTRING_LIKELY
2516 #undef FBSTRING_UNLIKELY
2518 #ifdef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2520 #undef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2521 #endif // FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2523 #endif // FOLLY_BASE_FBSTRING_H_