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 // Handle the cases where the fbcode version (folly/Malloc.h) is included
36 // either before or after this inclusion.
37 #ifdef FOLLY_MALLOC_H_
38 #undef FOLLY_MALLOC_H_
39 #include "basic_fbstring_malloc.h" // nolint
41 #include "basic_fbstring_malloc.h" // nolint
42 #undef FOLLY_MALLOC_H_
45 #else // !_LIBSTDCXX_FBSTRING
47 #include <folly/Portability.h>
49 // libc++ doesn't provide this header, nor does msvc
50 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
51 #include <bits/c++config.h>
59 #include <folly/Traits.h>
60 #include <folly/Malloc.h>
61 #include <folly/Hash.h>
62 #include <folly/ScopeGuard.h>
64 #if FOLLY_HAVE_DEPRECATED_ASSOC
65 #ifdef _GLIBCXX_SYMVER
66 #include <ext/hash_set>
67 #include <ext/hash_map>
73 // We defined these here rather than including Likely.h to avoid
74 // redefinition errors when fbstring is imported into libstdc++.
75 #if defined(__GNUC__) && __GNUC__ >= 4
76 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
77 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
79 #define FBSTRING_LIKELY(x) (x)
80 #define FBSTRING_UNLIKELY(x) (x)
83 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
84 #pragma GCC diagnostic push
85 #pragma GCC diagnostic ignored "-Wshadow"
87 // FBString cannot use throw when replacing std::string, though it may still
90 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
92 #ifdef _LIBSTDCXX_FBSTRING
93 namespace std _GLIBCXX_VISIBILITY(default) {
94 _GLIBCXX_BEGIN_NAMESPACE_VERSION
99 // Different versions of gcc/clang support different versions of
100 // the address sanitizer attribute. Unfortunately, this attribute
101 // has issues when inlining is used, so disable that as well.
102 #if defined(__clang__)
103 # if __has_feature(address_sanitizer)
104 # if __has_attribute(__no_sanitize__)
105 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
106 __attribute__((__no_sanitize__("address"), __noinline__))
107 # elif __has_attribute(__no_address_safety_analysis__)
108 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
109 __attribute__((__no_address_safety_analysis__, __noinline__))
110 # elif __has_attribute(__no_sanitize_address__)
111 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
112 __attribute__((__no_sanitize_address__, __noinline__))
115 #elif defined (__GNUC__) && \
117 (__GNUC_MINOR__ >= 8) && \
119 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
120 __attribute__((__no_address_safety_analysis__, __noinline__))
122 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
123 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
126 namespace fbstring_detail {
128 template <class InIt, class OutIt>
131 typename std::iterator_traits<InIt>::difference_type n,
133 for (; n != 0; --n, ++b, ++d) {
139 template <class Pod, class T>
140 inline void pod_fill(Pod* b, Pod* e, T c) {
141 assert(b && e && b <= e);
142 /*static*/ if (sizeof(T) == 1) {
145 auto const ee = b + ((e - b) & ~7u);
146 for (; b != ee; b += 8) {
157 for (; b != e; ++b) {
164 * Lightly structured memcpy, simplifies copying PODs and introduces
165 * some asserts. Unfortunately using this function may cause
166 * measurable overhead (presumably because it adjusts from a begin/end
167 * convention to a pointer/size convention, so it does some extra
168 * arithmetic even though the caller might have done the inverse
169 * adaptation outside).
172 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
174 assert(d >= e || d + (e - b) <= b);
175 memcpy(d, b, (e - b) * sizeof(Pod));
179 * Lightly structured memmove, simplifies copying PODs and introduces
183 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
185 memmove(d, b, (e - b) * sizeof(*b));
188 } // namespace fbstring_detail
191 * Defines a special acquisition method for constructing fbstring
192 * objects. AcquireMallocatedString means that the user passes a
193 * pointer to a malloc-allocated string that the fbstring object will
196 enum class AcquireMallocatedString {};
199 * fbstring_core_model is a mock-up type that defines all required
200 * signatures of a fbstring core. The fbstring class itself uses such
201 * a core object to implement all of the numerous member functions
202 * required by the standard.
204 * If you want to define a new core, copy the definition below and
205 * implement the primitives. Then plug the core into basic_fbstring as
206 * a template argument.
208 template <class Char>
209 class fbstring_core_model {
211 fbstring_core_model();
212 fbstring_core_model(const fbstring_core_model &);
213 ~fbstring_core_model();
214 // Returns a pointer to string's buffer (currently only contiguous
215 // strings are supported). The pointer is guaranteed to be valid
216 // until the next call to a non-const member function.
217 const Char * data() const;
218 // Much like data(), except the string is prepared to support
219 // character-level changes. This call is a signal for
220 // e.g. reference-counted implementation to fork the data. The
221 // pointer is guaranteed to be valid until the next call to a
222 // non-const member function.
223 Char * mutable_data();
224 // Returns a pointer to string's buffer and guarantees that a
225 // readable '\0' lies right after the buffer. The pointer is
226 // guaranteed to be valid until the next call to a non-const member
228 const Char * c_str() const;
229 // Shrinks the string by delta characters. Asserts that delta <=
231 void shrink(size_t delta);
232 // Expands the string by delta characters (i.e. after this call
233 // size() will report the old size() plus delta) but without
234 // initializing the expanded region. Returns a pointer to the memory
235 // to be initialized (the beginning of the expanded portion). The
236 // caller is expected to fill the expanded area appropriately.
237 Char* expand_noinit(size_t delta);
238 // Expands the string by one character and sets the last character
240 void push_back(Char c);
241 // Returns the string's size.
243 // Returns the string's capacity, i.e. maximum size that the string
244 // can grow to without reallocation. Note that for reference counted
245 // strings that's technically a lie - even assigning characters
246 // within the existing size would cause a reallocation.
247 size_t capacity() const;
248 // Returns true if the data underlying the string is actually shared
249 // across multiple strings (in a refcounted fashion).
250 bool isShared() const;
251 // Makes sure that at least minCapacity characters are available for
252 // the string without reallocation. For reference-counted strings,
253 // it should fork the data even if minCapacity < size().
254 void reserve(size_t minCapacity);
257 fbstring_core_model& operator=(const fbstring_core_model &);
262 * This is the core of the string. The code should work on 32- and
263 * 64-bit and both big- and little-endianan architectures with any
266 * The storage is selected as follows (assuming we store one-byte
267 * characters on a 64-bit machine): (a) "small" strings between 0 and
268 * 23 chars are stored in-situ without allocation (the rightmost byte
269 * stores the size); (b) "medium" strings from 24 through 254 chars
270 * are stored in malloc-allocated memory that is copied eagerly; (c)
271 * "large" strings of 255 chars and above are stored in a similar
272 * structure as medium arrays, except that the string is
273 * reference-counted and copied lazily. the reference count is
274 * allocated right before the character array.
276 * The discriminator between these three strategies sits in two
277 * bits of the rightmost char of the storage. If neither is set, then the
278 * string is small (and its length sits in the lower-order bits on
279 * little-endian or the high-order bits on big-endian of that
280 * rightmost character). If the MSb is set, the string is medium width.
281 * If the second MSb is set, then the string is large. On little-endian,
282 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
283 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
284 * and big-endian fbstring_core equivalent with merely different ops used
285 * to extract capacity/category.
287 template <class Char> class fbstring_core {
289 static constexpr bool kIsLittleEndian =
290 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
291 static constexpr bool kIsBigEndian =
292 __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__;
294 kIsLittleEndian || kIsBigEndian, "unable to identify endianness");
296 fbstring_core() noexcept { reset(); }
298 fbstring_core(const fbstring_core & rhs) {
299 assert(&rhs != this);
300 // Simplest case first: small strings are bitblitted
301 if (rhs.category() == Category::isSmall) {
302 static_assert(offsetof(MediumLarge, data_) == 0,
303 "fbstring layout failure");
304 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
305 "fbstring layout failure");
306 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
307 "fbstring layout failure");
308 // Just write the whole thing, don't look at details. In
309 // particular we need to copy capacity anyway because we want
310 // to set the size (don't forget that the last character,
311 // which stores a short string's length, is shared with the
312 // ml_.capacity field).
314 assert(category() == Category::isSmall && this->size() == rhs.size());
315 } else if (rhs.category() == Category::isLarge) {
316 // Large strings are just refcounted
318 RefCounted::incrementRefs(ml_.data_);
319 assert(category() == Category::isLarge && size() == rhs.size());
321 // Medium strings are copied eagerly. Don't forget to allocate
322 // one extra Char for the null terminator.
323 auto const allocSize =
324 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
325 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
326 fbstring_detail::pod_copy(rhs.ml_.data_,
328 rhs.ml_.data_ + rhs.ml_.size_ + 1,
330 // No need for writeTerminator() here, we copied one extra
331 // element just above.
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 (64 bits) at a time
380 const size_t byteSize = size * sizeof(Char);
381 if (byteSize > 2 * sizeof(size_t)) {
383 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
385 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
387 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
388 } else if (byteSize > sizeof(size_t)) {
391 } else if (size > 0) {
398 } else if (size <= maxMediumSize) {
399 // Medium strings are allocated normally. Don't forget to
400 // allocate one extra Char for the terminating null.
401 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
402 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
403 fbstring_detail::pod_copy(data, data + size, ml_.data_);
405 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
407 // Large strings are allocated differently
408 size_t effectiveCapacity = size;
409 auto const newRC = RefCounted::create(data, & effectiveCapacity);
410 ml_.data_ = newRC->data_;
412 ml_.setCapacity(effectiveCapacity, Category::isLarge);
417 ~fbstring_core() noexcept {
418 auto const c = category();
419 if (c == Category::isSmall) {
422 if (c == Category::isMedium) {
426 RefCounted::decrementRefs(ml_.data_);
429 // Snatches a previously mallocated string. The parameter "size"
430 // is the size of the string, and the parameter "allocatedSize"
431 // is the size of the mallocated block. The string must be
432 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
434 // So if you want a 2-character string, pass malloc(3) as "data",
435 // pass 2 as "size", and pass 3 as "allocatedSize".
436 fbstring_core(Char * const data,
438 const size_t allocatedSize,
439 AcquireMallocatedString) {
441 assert(allocatedSize >= size + 1);
442 assert(data[size] == '\0');
443 // Use the medium string storage
446 // Don't forget about null terminator
447 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
449 // No need for the memory
455 // swap below doesn't test whether &rhs == this (and instead
456 // potentially does extra work) on the premise that the rarity of
457 // that situation actually makes the check more expensive than is
459 void swap(fbstring_core & rhs) {
465 // In C++11 data() and c_str() are 100% equivalent.
466 const Char * data() const {
470 Char * mutable_data() {
471 auto const c = category();
472 if (c == Category::isSmall) {
475 assert(c == Category::isMedium || c == Category::isLarge);
476 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
478 size_t effectiveCapacity = ml_.capacity();
479 auto const newRC = RefCounted::create(& effectiveCapacity);
480 // If this fails, someone placed the wrong capacity in an
482 assert(effectiveCapacity >= ml_.capacity());
483 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
485 RefCounted::decrementRefs(ml_.data_);
486 ml_.data_ = newRC->data_;
487 // No need to call writeTerminator(), we have + 1 above.
492 const Char * c_str() const {
493 auto const c = category();
494 if (c == Category::isSmall) {
495 assert(small_[smallSize()] == '\0');
498 assert(c == Category::isMedium || c == Category::isLarge);
499 assert(ml_.data_[ml_.size_] == '\0');
503 void shrink(const size_t delta) {
504 if (category() == Category::isSmall) {
505 // Check for underflow
506 assert(delta <= smallSize());
507 setSmallSize(smallSize() - delta);
508 } else if (category() == Category::isMedium ||
509 RefCounted::refs(ml_.data_) == 1) {
510 // Medium strings and unique large strings need no special
512 assert(ml_.size_ >= delta);
516 assert(ml_.size_ >= delta);
517 // Shared large string, must make unique. This is because of the
518 // durn terminator must be written, which may trample the shared
521 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
523 // No need to write the terminator.
527 void reserve(size_t minCapacity) {
528 if (category() == Category::isLarge) {
530 if (RefCounted::refs(ml_.data_) > 1) {
531 // We must make it unique regardless; in-place reallocation is
532 // useless if the string is shared. In order to not surprise
533 // people, reserve the new block at current capacity or
534 // more. That way, a string's capacity never shrinks after a
536 minCapacity = std::max(minCapacity, ml_.capacity());
537 auto const newRC = RefCounted::create(& minCapacity);
538 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
540 // Done with the old data. No need to call writeTerminator(),
541 // we have + 1 above.
542 RefCounted::decrementRefs(ml_.data_);
543 ml_.data_ = newRC->data_;
544 ml_.setCapacity(minCapacity, Category::isLarge);
545 // size remains unchanged
547 // String is not shared, so let's try to realloc (if needed)
548 if (minCapacity > ml_.capacity()) {
549 // Asking for more memory
551 RefCounted::reallocate(ml_.data_, ml_.size_,
552 ml_.capacity(), minCapacity);
553 ml_.data_ = newRC->data_;
554 ml_.setCapacity(minCapacity, Category::isLarge);
557 assert(capacity() >= minCapacity);
559 } else if (category() == Category::isMedium) {
560 // String is not shared
561 if (minCapacity <= ml_.capacity()) {
562 return; // nothing to do, there's enough room
564 if (minCapacity <= maxMediumSize) {
565 // Keep the string at medium size. Don't forget to allocate
566 // one extra Char for the terminating null.
567 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
568 ml_.data_ = static_cast<Char *>(
571 ml_.size_ * sizeof(Char),
572 (ml_.capacity() + 1) * sizeof(Char),
575 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
577 // Conversion from medium to large string
578 fbstring_core nascent;
579 // Will recurse to another branch of this function
580 nascent.reserve(minCapacity);
581 nascent.ml_.size_ = ml_.size_;
582 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
586 assert(capacity() >= minCapacity);
589 assert(category() == Category::isSmall);
590 if (minCapacity > maxMediumSize) {
592 auto const newRC = RefCounted::create(& minCapacity);
593 auto const size = smallSize();
594 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
595 // No need for writeTerminator(), we wrote it above with + 1.
596 ml_.data_ = newRC->data_;
598 ml_.setCapacity(minCapacity, Category::isLarge);
599 assert(capacity() >= minCapacity);
600 } else if (minCapacity > maxSmallSize) {
602 // Don't forget to allocate one extra Char for the terminating null
603 auto const allocSizeBytes =
604 goodMallocSize((1 + minCapacity) * sizeof(Char));
605 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
606 auto const size = smallSize();
607 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
608 // No need for writeTerminator(), we wrote it above with + 1.
611 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
614 // Nothing to do, everything stays put
617 assert(capacity() >= minCapacity);
620 Char * expand_noinit(const size_t delta) {
621 // Strategy is simple: make room, then change size
622 assert(capacity() >= size());
624 if (category() == Category::isSmall) {
627 if (newSz <= maxSmallSize) {
634 newSz = ml_.size_ + delta;
635 if (newSz > capacity()) {
639 assert(capacity() >= newSz);
640 // Category can't be small - we took care of that above
641 assert(category() == Category::isMedium || category() == Category::isLarge);
644 assert(size() == newSz);
645 return ml_.data_ + sz;
648 void push_back(Char c) {
649 assert(capacity() >= size());
651 if (category() == Category::isSmall) {
653 if (sz < maxSmallSize) {
655 setSmallSize(sz + 1);
658 reserve(maxSmallSize * 2);
661 if (sz == capacity()) { // always true for isShared()
662 reserve(1 + sz * 3 / 2); // ensures not shared
666 assert(capacity() >= sz + 1);
667 // Category can't be small - we took care of that above
668 assert(category() == Category::isMedium || category() == Category::isLarge);
674 size_t size() const {
675 return category() == Category::isSmall ? smallSize() : ml_.size_;
678 size_t capacity() const {
679 switch (category()) {
680 case Category::isSmall:
682 case Category::isLarge:
683 // For large-sized strings, a multi-referenced chunk has no
684 // available capacity. This is because any attempt to append
685 // data would trigger a new allocation.
686 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
689 return ml_.capacity();
692 bool isShared() const {
693 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
696 void writeTerminator() {
697 if (category() == Category::isSmall) {
698 const auto s = smallSize();
699 if (s != maxSmallSize) {
703 ml_.data_[ml_.size_] = '\0';
709 fbstring_core & operator=(const fbstring_core & rhs);
711 // Equivalent to setSmallSize(0), but with specialized
712 // writeTerminator which doesn't re-check the category after
713 // capacity_ is overwritten.
715 // Only initialize the tag, will set the MSBs (i.e. the small
716 // string size) to zero too.
717 ml_.capacity_ = kIsLittleEndian
718 ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
721 assert(category() == Category::isSmall && size() == 0);
725 std::atomic<size_t> refCount_;
728 static RefCounted * fromData(Char * p) {
729 return static_cast<RefCounted*>(
731 static_cast<unsigned char*>(static_cast<void*>(p))
732 - sizeof(refCount_)));
735 static size_t refs(Char * p) {
736 return fromData(p)->refCount_.load(std::memory_order_acquire);
739 static void incrementRefs(Char * p) {
740 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
743 static void decrementRefs(Char * p) {
744 auto const dis = fromData(p);
745 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
752 static RefCounted * create(size_t * size) {
753 // Don't forget to allocate one extra Char for the terminating
754 // null. In this case, however, one Char is already part of the
756 const size_t allocSize = goodMallocSize(
757 sizeof(RefCounted) + *size * sizeof(Char));
758 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
759 result->refCount_.store(1, std::memory_order_release);
760 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
764 static RefCounted * create(const Char * data, size_t * size) {
765 const size_t effectiveSize = *size;
766 auto result = create(size);
767 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
771 static RefCounted * reallocate(Char *const data,
772 const size_t currentSize,
773 const size_t currentCapacity,
774 const size_t newCapacity) {
775 assert(newCapacity > 0 && newCapacity > currentSize);
776 auto const dis = fromData(data);
777 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
778 // Don't forget to allocate one extra Char for the terminating
779 // null. In this case, however, one Char is already part of the
781 auto result = static_cast<RefCounted*>(
783 sizeof(RefCounted) + currentSize * sizeof(Char),
784 sizeof(RefCounted) + currentCapacity * sizeof(Char),
785 sizeof(RefCounted) + newCapacity * sizeof(Char)));
786 assert(result->refCount_.load(std::memory_order_acquire) == 1);
791 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
794 enum class Category : category_type {
796 isMedium = kIsLittleEndian
797 ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
799 isLarge = kIsLittleEndian
800 ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
804 Category category() const {
805 // works for both big-endian and little-endian
806 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
814 size_t capacity() const {
815 return kIsLittleEndian
816 ? capacity_ & capacityExtractMask
820 void setCapacity(size_t cap, Category cat) {
821 capacity_ = kIsLittleEndian
822 ? cap | static_cast<category_type>(cat)
823 : (cap << 2) | static_cast<category_type>(cat);
828 Char small_[sizeof(MediumLarge) / sizeof(Char)];
833 lastChar = sizeof(MediumLarge) - 1,
834 maxSmallSize = lastChar / sizeof(Char),
835 maxMediumSize = 254 / sizeof(Char), // coincides with the small
836 // bin size in dlmalloc
837 categoryExtractMask = kIsLittleEndian
838 ? sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000
840 capacityExtractMask = kIsLittleEndian
841 ? ~categoryExtractMask
844 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
845 "Corrupt memory layout for fbstring.");
847 size_t smallSize() const {
848 assert(category() == Category::isSmall);
849 auto shift = kIsLittleEndian ? 0 : 2;
850 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
851 assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
852 return static_cast<size_t>(maxSmallSize) - smallShifted;
855 void setSmallSize(size_t s) {
856 // Warning: this should work with uninitialized strings too,
857 // so don't assume anything about the previous value of
858 // small_[maxSmallSize].
859 assert(s <= maxSmallSize);
860 small_[maxSmallSize] = kIsLittleEndian
862 : (maxSmallSize - s) << 2;
867 #ifndef _LIBSTDCXX_FBSTRING
869 * Dummy fbstring core that uses an actual std::string. This doesn't
870 * make any sense - it's just for testing purposes.
872 template <class Char>
873 class dummy_fbstring_core {
875 dummy_fbstring_core() {
877 dummy_fbstring_core(const dummy_fbstring_core& another)
878 : backend_(another.backend_) {
880 dummy_fbstring_core(const Char * s, size_t n)
883 void swap(dummy_fbstring_core & rhs) {
884 backend_.swap(rhs.backend_);
886 const Char * data() const {
887 return backend_.data();
889 Char * mutable_data() {
890 //assert(!backend_.empty());
891 return &*backend_.begin();
893 void shrink(size_t delta) {
894 assert(delta <= size());
895 backend_.resize(size() - delta);
897 Char * expand_noinit(size_t delta) {
898 auto const sz = size();
899 backend_.resize(size() + delta);
900 return backend_.data() + sz;
902 void push_back(Char c) {
903 backend_.push_back(c);
905 size_t size() const {
906 return backend_.size();
908 size_t capacity() const {
909 return backend_.capacity();
911 bool isShared() const {
914 void reserve(size_t minCapacity) {
915 backend_.reserve(minCapacity);
919 std::basic_string<Char> backend_;
921 #endif // !_LIBSTDCXX_FBSTRING
924 * This is the basic_string replacement. For conformity,
925 * basic_fbstring takes the same template parameters, plus the last
926 * one which is the core.
928 #ifdef _LIBSTDCXX_FBSTRING
929 template <typename E, class T, class A, class Storage>
931 template <typename E,
932 class T = std::char_traits<E>,
933 class A = std::allocator<E>,
934 class Storage = fbstring_core<E> >
936 class basic_fbstring {
940 void (*throw_exc)(const char*),
942 if (!condition) throw_exc(msg);
945 bool isSane() const {
948 empty() == (size() == 0) &&
949 empty() == (begin() == end()) &&
950 size() <= max_size() &&
951 capacity() <= max_size() &&
952 size() <= capacity() &&
953 begin()[size()] == '\0';
957 friend struct Invariant;
960 explicit Invariant(const basic_fbstring& s) : s_(s) {
967 const basic_fbstring& s_;
969 explicit Invariant(const basic_fbstring&) {}
971 Invariant& operator=(const Invariant&);
976 typedef T traits_type;
977 typedef typename traits_type::char_type value_type;
978 typedef A allocator_type;
979 typedef typename A::size_type size_type;
980 typedef typename A::difference_type difference_type;
982 typedef typename A::reference reference;
983 typedef typename A::const_reference const_reference;
984 typedef typename A::pointer pointer;
985 typedef typename A::const_pointer const_pointer;
988 typedef const E* const_iterator;
989 typedef std::reverse_iterator<iterator
990 #ifdef NO_ITERATOR_TRAITS
994 typedef std::reverse_iterator<const_iterator
995 #ifdef NO_ITERATOR_TRAITS
998 > const_reverse_iterator;
1000 static const size_type npos; // = size_type(-1)
1003 static void procrustes(size_type& n, size_type nmax) {
1004 if (n > nmax) n = nmax;
1008 // C++11 21.4.2 construct/copy/destroy
1009 explicit basic_fbstring(const A& /*a*/ = A()) noexcept {
1012 basic_fbstring(const basic_fbstring& str)
1013 : store_(str.store_) {
1017 basic_fbstring(basic_fbstring&& goner) noexcept
1018 : store_(std::move(goner.store_)) {
1021 #ifndef _LIBSTDCXX_FBSTRING
1022 // This is defined for compatibility with std::string
1023 /* implicit */ basic_fbstring(const std::string& str)
1024 : store_(str.data(), str.size()) {
1028 basic_fbstring(const basic_fbstring& str, size_type pos,
1029 size_type n = npos, 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 data = store_.expand_noinit(n);
1047 fbstring_detail::pod_fill(data, data + n, c);
1048 store_.writeTerminator();
1051 template <class InIt>
1052 basic_fbstring(InIt begin, InIt end,
1053 typename std::enable_if<
1054 !std::is_same<typename std::remove_const<InIt>::type,
1055 value_type*>::value, const A>::type & /*a*/ = A()) {
1059 // Specialization for const char*, const char*
1060 basic_fbstring(const value_type* b, const value_type* e)
1061 : store_(b, e - b) {
1064 // Nonstandard constructor
1065 basic_fbstring(value_type *s, size_type n, size_type c,
1066 AcquireMallocatedString a)
1067 : store_(s, n, c, a) {
1070 // Construction from initialization list
1071 basic_fbstring(std::initializer_list<value_type> il) {
1072 assign(il.begin(), il.end());
1075 ~basic_fbstring() noexcept {
1078 basic_fbstring& operator=(const basic_fbstring& lhs) {
1079 if (FBSTRING_UNLIKELY(&lhs == this)) {
1082 auto const oldSize = size();
1083 auto const srcSize = lhs.size();
1084 if (capacity() >= srcSize && !store_.isShared()) {
1085 // great, just copy the contents
1086 if (oldSize < srcSize)
1087 store_.expand_noinit(srcSize - oldSize);
1089 store_.shrink(oldSize - srcSize);
1090 assert(size() == srcSize);
1091 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1092 store_.writeTerminator();
1094 // need to reallocate, so we may as well create a brand new string
1095 basic_fbstring(lhs).swap(*this);
1101 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1102 if (FBSTRING_UNLIKELY(&goner == this)) {
1103 // Compatibility with std::basic_string<>,
1104 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1107 // No need of this anymore
1108 this->~basic_fbstring();
1109 // Move the goner into this
1110 new(&store_) fbstring_core<E>(std::move(goner.store_));
1114 #ifndef _LIBSTDCXX_FBSTRING
1115 // Compatibility with std::string
1116 basic_fbstring & operator=(const std::string & rhs) {
1117 return assign(rhs.data(), rhs.size());
1120 // Compatibility with std::string
1121 std::string toStdString() const {
1122 return std::string(data(), size());
1125 // A lot of code in fbcode still uses this method, so keep it here for now.
1126 const basic_fbstring& toStdString() const {
1131 basic_fbstring& operator=(const value_type* s) {
1135 basic_fbstring& operator=(value_type c) {
1137 store_.expand_noinit(1);
1138 } else if (store_.isShared()) {
1139 basic_fbstring(1, c).swap(*this);
1142 store_.shrink(size() - 1);
1144 *store_.mutable_data() = c;
1145 store_.writeTerminator();
1149 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1150 return assign(il.begin(), il.end());
1153 // C++11 21.4.3 iterators:
1154 iterator begin() { return store_.mutable_data(); }
1156 const_iterator begin() const { return store_.data(); }
1158 const_iterator cbegin() const { return begin(); }
1161 return store_.mutable_data() + store_.size();
1164 const_iterator end() const {
1165 return store_.data() + store_.size();
1168 const_iterator cend() const { return end(); }
1170 reverse_iterator rbegin() {
1171 return reverse_iterator(end());
1174 const_reverse_iterator rbegin() const {
1175 return const_reverse_iterator(end());
1178 const_reverse_iterator crbegin() const { return rbegin(); }
1180 reverse_iterator rend() {
1181 return reverse_iterator(begin());
1184 const_reverse_iterator rend() const {
1185 return const_reverse_iterator(begin());
1188 const_reverse_iterator crend() const { return rend(); }
1191 // C++11 21.4.5, element access:
1192 const value_type& front() const { return *begin(); }
1193 const value_type& back() const {
1195 // Should be begin()[size() - 1], but that branches twice
1196 return *(end() - 1);
1198 value_type& front() { return *begin(); }
1199 value_type& back() {
1201 // Should be begin()[size() - 1], but that branches twice
1202 return *(end() - 1);
1209 // C++11 21.4.4 capacity:
1210 size_type size() const { return store_.size(); }
1212 size_type length() const { return size(); }
1214 size_type max_size() const {
1215 return std::numeric_limits<size_type>::max();
1218 void resize(const size_type n, const value_type c = value_type()) {
1219 auto size = this->size();
1221 store_.shrink(size - n);
1223 // Do this in two steps to minimize slack memory copied (see
1225 auto const capacity = this->capacity();
1226 assert(capacity >= size);
1227 if (size < capacity) {
1228 auto delta = std::min(n, capacity) - size;
1229 store_.expand_noinit(delta);
1230 fbstring_detail::pod_fill(begin() + size, end(), c);
1233 store_.writeTerminator();
1238 auto const delta = n - size;
1239 store_.expand_noinit(delta);
1240 fbstring_detail::pod_fill(end() - delta, end(), c);
1241 store_.writeTerminator();
1243 assert(this->size() == n);
1246 size_type capacity() const { return store_.capacity(); }
1248 void reserve(size_type res_arg = 0) {
1249 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1250 store_.reserve(res_arg);
1253 void shrink_to_fit() {
1254 // Shrink only if slack memory is sufficiently large
1255 if (capacity() < size() * 3 / 2) {
1258 basic_fbstring(cbegin(), cend()).swap(*this);
1261 void clear() { resize(0); }
1263 bool empty() const { return size() == 0; }
1265 // C++11 21.4.5 element access:
1266 const_reference operator[](size_type pos) const {
1267 return *(begin() + pos);
1270 reference operator[](size_type pos) {
1271 return *(begin() + pos);
1274 const_reference at(size_type n) const {
1275 enforce(n <= size(), std::__throw_out_of_range, "");
1279 reference at(size_type n) {
1280 enforce(n < size(), std::__throw_out_of_range, "");
1284 // C++11 21.4.6 modifiers:
1285 basic_fbstring& operator+=(const basic_fbstring& str) {
1289 basic_fbstring& operator+=(const value_type* s) {
1293 basic_fbstring& operator+=(const value_type c) {
1298 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1303 basic_fbstring& append(const basic_fbstring& str) {
1305 auto desiredSize = size() + str.size();
1307 append(str.data(), str.size());
1308 assert(size() == desiredSize);
1312 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1314 const size_type sz = str.size();
1315 enforce(pos <= sz, std::__throw_out_of_range, "");
1316 procrustes(n, sz - pos);
1317 return append(str.data() + pos, n);
1320 basic_fbstring& append(const value_type* s, size_type n) {
1322 Invariant checker(*this);
1325 if (FBSTRING_UNLIKELY(!n)) {
1326 // Unlikely but must be done
1329 auto const oldSize = size();
1330 auto const oldData = data();
1331 // Check for aliasing (rare). We could use "<=" here but in theory
1332 // those do not work for pointers unless the pointers point to
1333 // elements in the same array. For that reason we use
1334 // std::less_equal, which is guaranteed to offer a total order
1335 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1337 std::less_equal<const value_type*> le;
1338 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1339 assert(le(s + n, oldData + oldSize));
1340 const size_type offset = s - oldData;
1341 store_.reserve(oldSize + n);
1342 // Restore the source
1343 s = data() + offset;
1345 // Warning! Repeated appends with short strings may actually incur
1346 // practically quadratic performance. Avoid that by pushing back
1347 // the first character (which ensures exponential growth) and then
1348 // appending the rest normally. Worst case the append may incur a
1349 // second allocation but that will be rare.
1352 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1353 assert(size() == oldSize + n + 1);
1357 basic_fbstring& append(const value_type* s) {
1358 return append(s, traits_type::length(s));
1361 basic_fbstring& append(size_type n, value_type c) {
1362 resize(size() + n, c);
1366 template<class InputIterator>
1367 basic_fbstring& append(InputIterator first, InputIterator last) {
1368 insert(end(), first, last);
1372 basic_fbstring& append(std::initializer_list<value_type> il) {
1373 return append(il.begin(), il.end());
1376 void push_back(const value_type c) { // primitive
1377 store_.push_back(c);
1380 basic_fbstring& assign(const basic_fbstring& str) {
1381 if (&str == this) return *this;
1382 return assign(str.data(), str.size());
1385 basic_fbstring& assign(basic_fbstring&& str) {
1386 return *this = std::move(str);
1389 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1391 const size_type sz = str.size();
1392 enforce(pos <= sz, std::__throw_out_of_range, "");
1393 procrustes(n, sz - pos);
1394 return assign(str.data() + pos, n);
1397 basic_fbstring& assign(const value_type* s, const size_type n) {
1398 Invariant checker(*this);
1401 std::copy(s, s + n, begin());
1403 assert(size() == n);
1405 const value_type *const s2 = s + size();
1406 std::copy(s, s2, begin());
1407 append(s2, n - size());
1408 assert(size() == n);
1410 store_.writeTerminator();
1411 assert(size() == n);
1415 basic_fbstring& assign(const value_type* s) {
1416 return assign(s, traits_type::length(s));
1419 basic_fbstring& assign(std::initializer_list<value_type> il) {
1420 return assign(il.begin(), il.end());
1423 template <class ItOrLength, class ItOrChar>
1424 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1425 return replace(begin(), end(), first_or_n, last_or_c);
1428 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1429 return insert(pos1, str.data(), str.size());
1432 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1433 size_type pos2, size_type n) {
1434 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1435 procrustes(n, str.length() - pos2);
1436 return insert(pos1, str.data() + pos2, n);
1439 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1440 enforce(pos <= length(), std::__throw_out_of_range, "");
1441 insert(begin() + pos, s, s + n);
1445 basic_fbstring& insert(size_type pos, const value_type* s) {
1446 return insert(pos, s, traits_type::length(s));
1449 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1450 enforce(pos <= length(), std::__throw_out_of_range, "");
1451 insert(begin() + pos, n, c);
1455 iterator insert(const_iterator p, const value_type c) {
1456 const size_type pos = p - begin();
1458 return begin() + pos;
1462 template <int i> class Selector {};
1464 iterator insertImplDiscr(const_iterator p,
1465 size_type n, value_type c, Selector<1>) {
1466 Invariant checker(*this);
1468 auto const pos = p - begin();
1469 assert(p >= begin() && p <= end());
1470 if (capacity() - size() < n) {
1471 const size_type sz = p - begin();
1472 reserve(size() + n);
1475 const iterator oldEnd = end();
1476 if (n < size_type(oldEnd - p)) {
1477 append(oldEnd - n, oldEnd);
1479 // reverse_iterator(oldEnd - n),
1480 // reverse_iterator(p),
1481 // reverse_iterator(oldEnd));
1482 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1484 std::fill(begin() + pos, begin() + pos + n, c);
1486 append(n - (end() - p), c);
1487 append(iterator(p), oldEnd);
1488 std::fill(iterator(p), oldEnd, c);
1490 store_.writeTerminator();
1491 return begin() + pos;
1494 template<class InputIter>
1495 iterator insertImplDiscr(const_iterator i,
1496 InputIter b, InputIter e, Selector<0>) {
1497 return insertImpl(i, b, e,
1498 typename std::iterator_traits<InputIter>::iterator_category());
1501 template <class FwdIterator>
1502 iterator insertImpl(const_iterator i,
1503 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1504 Invariant checker(*this);
1506 const size_type pos = i - begin();
1507 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1508 std::distance(s1, s2);
1510 using namespace fbstring_detail;
1511 assert(pos <= size());
1513 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1514 capacity() - size();
1516 // realloc the string
1517 reserve(size() + n2);
1520 if (pos + n2 <= size()) {
1521 const iterator tailBegin = end() - n2;
1522 store_.expand_noinit(n2);
1523 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1524 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1525 reverse_iterator(tailBegin + n2));
1526 std::copy(s1, s2, begin() + pos);
1529 const size_type old_size = size();
1530 std::advance(t, old_size - pos);
1531 const size_t newElems = std::distance(t, s2);
1532 store_.expand_noinit(n2);
1533 std::copy(t, s2, begin() + old_size);
1534 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1535 begin() + old_size + newElems);
1536 std::copy(s1, t, begin() + pos);
1538 store_.writeTerminator();
1539 return begin() + pos;
1542 template <class InputIterator>
1543 iterator insertImpl(const_iterator i,
1544 InputIterator b, InputIterator e,
1545 std::input_iterator_tag) {
1546 const auto pos = i - begin();
1547 basic_fbstring temp(begin(), i);
1548 for (; b != e; ++b) {
1551 temp.append(i, cend());
1553 return begin() + pos;
1557 template <class ItOrLength, class ItOrChar>
1558 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1559 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1560 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1563 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1564 return insert(p, il.begin(), il.end());
1567 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1568 Invariant checker(*this);
1570 enforce(pos <= length(), std::__throw_out_of_range, "");
1571 procrustes(n, length() - pos);
1572 std::copy(begin() + pos + n, end(), begin() + pos);
1573 resize(length() - n);
1577 iterator erase(iterator position) {
1578 const size_type pos(position - begin());
1579 enforce(pos <= size(), std::__throw_out_of_range, "");
1581 return begin() + pos;
1584 iterator erase(iterator first, iterator last) {
1585 const size_type pos(first - begin());
1586 erase(pos, last - first);
1587 return begin() + pos;
1590 // Replaces at most n1 chars of *this, starting with pos1 with the
1592 basic_fbstring& replace(size_type pos1, size_type n1,
1593 const basic_fbstring& str) {
1594 return replace(pos1, n1, str.data(), str.size());
1597 // Replaces at most n1 chars of *this, starting with pos1,
1598 // with at most n2 chars of str starting with pos2
1599 basic_fbstring& replace(size_type pos1, size_type n1,
1600 const basic_fbstring& str,
1601 size_type pos2, size_type n2) {
1602 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1603 return replace(pos1, n1, str.data() + pos2,
1604 std::min(n2, str.size() - pos2));
1607 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1608 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1609 return replace(pos, n1, s, traits_type::length(s));
1612 // Replaces at most n1 chars of *this, starting with pos, with n2
1615 // consolidated with
1617 // Replaces at most n1 chars of *this, starting with pos, with at
1618 // most n2 chars of str. str must have at least n2 chars.
1619 template <class StrOrLength, class NumOrChar>
1620 basic_fbstring& replace(size_type pos, size_type n1,
1621 StrOrLength s_or_n2, NumOrChar n_or_c) {
1622 Invariant checker(*this);
1624 enforce(pos <= size(), std::__throw_out_of_range, "");
1625 procrustes(n1, length() - pos);
1626 const iterator b = begin() + pos;
1627 return replace(b, b + n1, s_or_n2, n_or_c);
1630 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1631 return replace(i1, i2, str.data(), str.length());
1634 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1635 return replace(i1, i2, s, traits_type::length(s));
1639 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1640 const value_type* s, size_type n,
1643 assert(begin() <= i1 && i1 <= end());
1644 assert(begin() <= i2 && i2 <= end());
1645 return replace(i1, i2, s, s + n);
1648 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1649 size_type n2, value_type c, Selector<1>) {
1650 const size_type n1 = i2 - i1;
1652 std::fill(i1, i1 + n2, c);
1655 std::fill(i1, i2, c);
1656 insert(i2, n2 - n1, c);
1662 template <class InputIter>
1663 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1664 InputIter b, InputIter e,
1666 replaceImpl(i1, i2, b, e,
1667 typename std::iterator_traits<InputIter>::iterator_category());
1672 template <class FwdIterator>
1673 bool replaceAliased(iterator i1, iterator i2,
1674 FwdIterator s1, FwdIterator s2, std::false_type) {
1678 template <class FwdIterator>
1679 bool replaceAliased(iterator i1, iterator i2,
1680 FwdIterator s1, FwdIterator s2, std::true_type) {
1681 static const std::less_equal<const value_type*> le =
1682 std::less_equal<const value_type*>();
1683 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1687 // Aliased replace, copy to new string
1688 basic_fbstring temp;
1689 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1690 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1695 template <class FwdIterator>
1696 void replaceImpl(iterator i1, iterator i2,
1697 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1698 Invariant checker(*this);
1701 // Handle aliased replace
1702 if (replaceAliased(i1, i2, s1, s2,
1703 std::integral_constant<bool,
1704 std::is_same<FwdIterator, iterator>::value ||
1705 std::is_same<FwdIterator, const_iterator>::value>())) {
1709 auto const n1 = i2 - i1;
1711 auto const n2 = std::distance(s1, s2);
1716 std::copy(s1, s2, i1);
1720 fbstring_detail::copy_n(s1, n1, i1);
1721 std::advance(s1, n1);
1727 template <class InputIterator>
1728 void replaceImpl(iterator i1, iterator i2,
1729 InputIterator b, InputIterator e, std::input_iterator_tag) {
1730 basic_fbstring temp(begin(), i1);
1731 temp.append(b, e).append(i2, end());
1736 template <class T1, class T2>
1737 basic_fbstring& replace(iterator i1, iterator i2,
1738 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1740 num1 = std::numeric_limits<T1>::is_specialized,
1741 num2 = std::numeric_limits<T2>::is_specialized;
1742 return replaceImplDiscr(
1743 i1, i2, first_or_n_or_s, last_or_c_or_n,
1744 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1747 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1748 enforce(pos <= size(), std::__throw_out_of_range, "");
1749 procrustes(n, size() - pos);
1751 fbstring_detail::pod_copy(
1758 void swap(basic_fbstring& rhs) {
1759 store_.swap(rhs.store_);
1762 const value_type* c_str() const {
1763 return store_.c_str();
1766 const value_type* data() const { return c_str(); }
1768 allocator_type get_allocator() const {
1769 return allocator_type();
1772 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1773 return find(str.data(), pos, str.length());
1776 size_type find(const value_type* needle, const size_type pos,
1777 const size_type nsize) const {
1778 if (!nsize) return pos;
1779 auto const size = this->size();
1780 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1781 // that nsize + pos does not wrap around.
1782 if (nsize + pos > size || nsize + pos < pos) return npos;
1783 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1784 // the last characters first
1785 auto const haystack = data();
1786 auto const nsize_1 = nsize - 1;
1787 auto const lastNeedle = needle[nsize_1];
1789 // Boyer-Moore skip value for the last char in the needle. Zero is
1790 // not a valid value; skip will be computed the first time it's
1794 const E * i = haystack + pos;
1795 auto iEnd = haystack + size - nsize_1;
1798 // Boyer-Moore: match the last element in the needle
1799 while (i[nsize_1] != lastNeedle) {
1805 // Here we know that the last char matches
1806 // Continue in pedestrian mode
1807 for (size_t j = 0; ; ) {
1809 if (i[j] != needle[j]) {
1810 // Not found, we can skip
1811 // Compute the skip value lazily
1814 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1821 // Check if done searching
1824 return i - haystack;
1831 size_type find(const value_type* s, size_type pos = 0) const {
1832 return find(s, pos, traits_type::length(s));
1835 size_type find (value_type c, size_type pos = 0) const {
1836 return find(&c, pos, 1);
1839 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1840 return rfind(str.data(), pos, str.length());
1843 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1844 if (n > length()) return npos;
1845 pos = std::min(pos, length() - n);
1846 if (n == 0) return pos;
1848 const_iterator i(begin() + pos);
1850 if (traits_type::eq(*i, *s)
1851 && traits_type::compare(&*i, s, n) == 0) {
1854 if (i == begin()) break;
1859 size_type rfind(const value_type* s, size_type pos = npos) const {
1860 return rfind(s, pos, traits_type::length(s));
1863 size_type rfind(value_type c, size_type pos = npos) const {
1864 return rfind(&c, pos, 1);
1867 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1868 return find_first_of(str.data(), pos, str.length());
1871 size_type find_first_of(const value_type* s,
1872 size_type pos, size_type n) const {
1873 if (pos > length() || n == 0) return npos;
1874 const_iterator i(begin() + pos),
1876 for (; i != finish; ++i) {
1877 if (traits_type::find(s, n, *i) != 0) {
1884 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1885 return find_first_of(s, pos, traits_type::length(s));
1888 size_type find_first_of(value_type c, size_type pos = 0) const {
1889 return find_first_of(&c, pos, 1);
1892 size_type find_last_of (const basic_fbstring& str,
1893 size_type pos = npos) const {
1894 return find_last_of(str.data(), pos, str.length());
1897 size_type find_last_of (const value_type* s, size_type pos,
1898 size_type n) const {
1899 if (!empty() && n > 0) {
1900 pos = std::min(pos, length() - 1);
1901 const_iterator i(begin() + pos);
1903 if (traits_type::find(s, n, *i) != 0) {
1906 if (i == begin()) break;
1912 size_type find_last_of (const value_type* s,
1913 size_type pos = npos) const {
1914 return find_last_of(s, pos, traits_type::length(s));
1917 size_type find_last_of (value_type c, size_type pos = npos) const {
1918 return find_last_of(&c, pos, 1);
1921 size_type find_first_not_of(const basic_fbstring& str,
1922 size_type pos = 0) const {
1923 return find_first_not_of(str.data(), pos, str.size());
1926 size_type find_first_not_of(const value_type* s, size_type pos,
1927 size_type n) const {
1928 if (pos < length()) {
1932 for (; i != finish; ++i) {
1933 if (traits_type::find(s, n, *i) == 0) {
1941 size_type find_first_not_of(const value_type* s,
1942 size_type pos = 0) const {
1943 return find_first_not_of(s, pos, traits_type::length(s));
1946 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1947 return find_first_not_of(&c, pos, 1);
1950 size_type find_last_not_of(const basic_fbstring& str,
1951 size_type pos = npos) const {
1952 return find_last_not_of(str.data(), pos, str.length());
1955 size_type find_last_not_of(const value_type* s, size_type pos,
1956 size_type n) const {
1957 if (!this->empty()) {
1958 pos = std::min(pos, size() - 1);
1959 const_iterator i(begin() + pos);
1961 if (traits_type::find(s, n, *i) == 0) {
1964 if (i == begin()) break;
1970 size_type find_last_not_of(const value_type* s,
1971 size_type pos = npos) const {
1972 return find_last_not_of(s, pos, traits_type::length(s));
1975 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1976 return find_last_not_of(&c, pos, 1);
1979 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1980 enforce(pos <= size(), std::__throw_out_of_range, "");
1981 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1984 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1985 enforce(pos <= size(), std::__throw_out_of_range, "");
1987 if (n < size()) resize(n);
1988 return std::move(*this);
1991 int compare(const basic_fbstring& str) const {
1992 // FIX due to Goncalo N M de Carvalho July 18, 2005
1993 return compare(0, size(), str);
1996 int compare(size_type pos1, size_type n1,
1997 const basic_fbstring& str) const {
1998 return compare(pos1, n1, str.data(), str.size());
2001 int compare(size_type pos1, size_type n1,
2002 const value_type* s) const {
2003 return compare(pos1, n1, s, traits_type::length(s));
2006 int compare(size_type pos1, size_type n1,
2007 const value_type* s, size_type n2) const {
2008 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2009 procrustes(n1, size() - pos1);
2010 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2011 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2012 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2015 int compare(size_type pos1, size_type n1,
2016 const basic_fbstring& str,
2017 size_type pos2, size_type n2) const {
2018 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2019 return compare(pos1, n1, str.data() + pos2,
2020 std::min(n2, str.size() - pos2));
2023 // Code from Jean-Francois Bastien (03/26/2007)
2024 int compare(const value_type* s) const {
2025 // Could forward to compare(0, size(), s, traits_type::length(s))
2026 // but that does two extra checks
2027 const size_type n1(size()), n2(traits_type::length(s));
2028 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2029 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2037 // non-member functions
2039 template <typename E, class T, class A, class S>
2041 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2042 const basic_fbstring<E, T, A, S>& rhs) {
2044 basic_fbstring<E, T, A, S> result;
2045 result.reserve(lhs.size() + rhs.size());
2046 result.append(lhs).append(rhs);
2047 return std::move(result);
2051 template <typename E, class T, class A, class S>
2053 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2054 const basic_fbstring<E, T, A, S>& rhs) {
2055 return std::move(lhs.append(rhs));
2059 template <typename E, class T, class A, class S>
2061 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2062 basic_fbstring<E, T, A, S>&& rhs) {
2063 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2064 // Good, at least we don't need to reallocate
2065 return std::move(rhs.insert(0, lhs));
2067 // Meh, no go. Forward to operator+(const&, const&).
2068 auto const& rhsC = rhs;
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 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+(
2085 const basic_fbstring<E, T, A, S>& rhs) {
2087 basic_fbstring<E, T, A, S> result;
2088 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2089 result.reserve(len + rhs.size());
2090 result.append(lhs, len).append(rhs);
2095 template <typename E, class T, class A, class S>
2097 basic_fbstring<E, T, A, S> operator+(
2099 basic_fbstring<E, T, A, S>&& rhs) {
2101 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2102 if (rhs.capacity() >= len + rhs.size()) {
2103 // Good, at least we don't need to reallocate
2104 return std::move(rhs.insert(rhs.begin(), lhs, lhs + len));
2106 // Meh, no go. Do it by hand since we have len already.
2107 basic_fbstring<E, T, A, S> result;
2108 result.reserve(len + rhs.size());
2109 result.append(lhs, len).append(rhs);
2114 template <typename E, class T, class A, class S>
2116 basic_fbstring<E, T, A, S> operator+(
2118 const basic_fbstring<E, T, A, S>& rhs) {
2120 basic_fbstring<E, T, A, S> result;
2121 result.reserve(1 + rhs.size());
2122 result.push_back(lhs);
2128 template <typename E, class T, class A, class S>
2130 basic_fbstring<E, T, A, S> operator+(
2132 basic_fbstring<E, T, A, S>&& rhs) {
2134 if (rhs.capacity() > rhs.size()) {
2135 // Good, at least we don't need to reallocate
2136 return std::move(rhs.insert(rhs.begin(), lhs));
2138 // Meh, no go. Forward to operator+(E, const&).
2139 auto const& rhsC = rhs;
2144 template <typename E, class T, class A, class S>
2146 basic_fbstring<E, T, A, S> operator+(
2147 const basic_fbstring<E, T, A, S>& lhs,
2150 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2151 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2153 basic_fbstring<E, T, A, S> result;
2154 const size_type len = traits_type::length(rhs);
2155 result.reserve(lhs.size() + len);
2156 result.append(lhs).append(rhs, len);
2160 // C++11 21.4.8.1/10
2161 template <typename E, class T, class A, class S>
2163 basic_fbstring<E, T, A, S> operator+(
2164 basic_fbstring<E, T, A, S>&& lhs,
2167 return std::move(lhs += rhs);
2170 // C++11 21.4.8.1/11
2171 template <typename E, class T, class A, class S>
2173 basic_fbstring<E, T, A, S> operator+(
2174 const basic_fbstring<E, T, A, S>& lhs,
2177 basic_fbstring<E, T, A, S> result;
2178 result.reserve(lhs.size() + 1);
2180 result.push_back(rhs);
2184 // C++11 21.4.8.1/12
2185 template <typename E, class T, class A, class S>
2187 basic_fbstring<E, T, A, S> operator+(
2188 basic_fbstring<E, T, A, S>&& lhs,
2191 return std::move(lhs += rhs);
2194 template <typename E, class T, class A, class S>
2196 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2197 const basic_fbstring<E, T, A, S>& rhs) {
2198 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2200 template <typename E, class T, class A, class S>
2202 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2203 const basic_fbstring<E, T, A, S>& rhs) {
2204 return rhs == lhs; }
2206 template <typename E, class T, class A, class S>
2208 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2209 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2210 return lhs.compare(rhs) == 0; }
2212 template <typename E, class T, class A, class S>
2214 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2215 const basic_fbstring<E, T, A, S>& rhs) {
2216 return !(lhs == rhs); }
2218 template <typename E, class T, class A, class S>
2220 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2221 const basic_fbstring<E, T, A, S>& rhs) {
2222 return !(lhs == rhs); }
2224 template <typename E, class T, class A, class S>
2226 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2227 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2228 return !(lhs == rhs); }
2230 template <typename E, class T, class A, class S>
2232 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2233 const basic_fbstring<E, T, A, S>& rhs) {
2234 return lhs.compare(rhs) < 0; }
2236 template <typename E, class T, class A, class S>
2238 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2239 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2240 return lhs.compare(rhs) < 0; }
2242 template <typename E, class T, class A, class S>
2244 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2245 const basic_fbstring<E, T, A, S>& rhs) {
2246 return rhs.compare(lhs) > 0; }
2248 template <typename E, class T, class A, class S>
2250 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2251 const basic_fbstring<E, T, A, S>& rhs) {
2254 template <typename E, class T, class A, class S>
2256 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2257 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2260 template <typename E, class T, class A, class S>
2262 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2263 const basic_fbstring<E, T, A, S>& rhs) {
2266 template <typename E, class T, class A, class S>
2268 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2269 const basic_fbstring<E, T, A, S>& rhs) {
2270 return !(rhs < lhs); }
2272 template <typename E, class T, class A, class S>
2274 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2275 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2276 return !(rhs < lhs); }
2278 template <typename E, class T, class A, class S>
2280 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2281 const basic_fbstring<E, T, A, S>& rhs) {
2282 return !(rhs < lhs); }
2284 template <typename E, class T, class A, class S>
2286 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2287 const basic_fbstring<E, T, A, S>& rhs) {
2288 return !(lhs < rhs); }
2290 template <typename E, class T, class A, class S>
2292 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2293 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2294 return !(lhs < rhs); }
2296 template <typename E, class T, class A, class S>
2298 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2299 const basic_fbstring<E, T, A, S>& rhs) {
2300 return !(lhs < rhs);
2304 template <typename E, class T, class A, class S>
2305 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2309 // TODO: make this faster.
2310 template <typename E, class T, class A, class S>
2313 typename basic_fbstring<E, T, A, S>::value_type,
2314 typename basic_fbstring<E, T, A, S>::traits_type>&
2316 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2317 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2318 basic_fbstring<E, T, A, S>& str) {
2319 typename std::basic_istream<E, T>::sentry sentry(is);
2320 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2321 typename basic_fbstring<E, T, A, S>::traits_type>
2323 typedef typename __istream_type::ios_base __ios_base;
2324 size_t extracted = 0;
2325 auto err = __ios_base::goodbit;
2327 auto n = is.width();
2332 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2333 if (got == T::eof()) {
2334 err |= __ios_base::eofbit;
2338 if (isspace(got)) break;
2340 got = is.rdbuf()->snextc();
2344 err |= __ios_base::failbit;
2352 template <typename E, class T, class A, class S>
2354 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2355 typename basic_fbstring<E, T, A, S>::traits_type>&
2357 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2358 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2359 const basic_fbstring<E, T, A, S>& str) {
2361 typename std::basic_ostream<
2362 typename basic_fbstring<E, T, A, S>::value_type,
2363 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2365 typedef std::ostreambuf_iterator<
2366 typename basic_fbstring<E, T, A, S>::value_type,
2367 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2368 size_t __len = str.size();
2370 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2371 if (__pad_and_output(_Ip(os),
2373 __left ? str.data() + __len : str.data(),
2376 os.fill()).failed()) {
2377 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2380 #elif defined(_MSC_VER)
2381 // MSVC doesn't define __ostream_insert
2382 os.write(str.data(), str.size());
2384 std::__ostream_insert(os, str.data(), str.size());
2389 #ifndef _LIBSTDCXX_FBSTRING
2391 template <typename E, class T, class A, class S>
2393 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2394 typename basic_fbstring<E, T, A, S>::traits_type>&
2396 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2397 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2398 basic_fbstring<E, T, A, S>& str,
2399 typename basic_fbstring<E, T, A, S>::value_type delim) {
2400 // Use the nonstandard getdelim()
2401 char * buf = nullptr;
2404 // This looks quadratic but it really depends on realloc
2405 auto const newSize = size + 128;
2406 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2407 is.getline(buf + size, newSize - size, delim);
2408 if (is.bad() || is.eof() || !is.fail()) {
2409 // done by either failure, end of file, or normal read
2410 size += std::strlen(buf + size);
2413 // Here we have failed due to too short a buffer
2414 // Minus one to discount the terminating '\0'
2416 assert(buf[size] == 0);
2417 // Clear the error so we can continue reading
2420 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2421 AcquireMallocatedString());
2426 template <typename E, class T, class A, class S>
2428 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2429 typename basic_fbstring<E, T, A, S>::traits_type>&
2431 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2432 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2433 basic_fbstring<E, T, A, S>& str) {
2434 // Just forward to the version with a delimiter
2435 return getline(is, str, '\n');
2440 template <typename E1, class T, class A, class S>
2441 const typename basic_fbstring<E1, T, A, S>::size_type
2442 basic_fbstring<E1, T, A, S>::npos =
2443 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2445 #ifndef _LIBSTDCXX_FBSTRING
2446 // basic_string compatibility routines
2448 template <typename E, class T, class A, class S>
2450 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2451 const std::string& rhs) {
2452 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2455 template <typename E, class T, class A, class S>
2457 bool operator==(const std::string& lhs,
2458 const basic_fbstring<E, T, A, S>& rhs) {
2462 template <typename E, class T, class A, class S>
2464 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2465 const std::string& rhs) {
2466 return !(lhs == rhs);
2469 template <typename E, class T, class A, class S>
2471 bool operator!=(const std::string& lhs,
2472 const basic_fbstring<E, T, A, S>& rhs) {
2473 return !(lhs == rhs);
2476 #if !defined(_LIBSTDCXX_FBSTRING)
2477 typedef basic_fbstring<char> fbstring;
2480 // fbstring is relocatable
2481 template <class T, class R, class A, class S>
2482 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2485 _GLIBCXX_END_NAMESPACE_VERSION
2488 } // namespace folly
2490 #ifndef _LIBSTDCXX_FBSTRING
2492 // Hash functions to make fbstring usable with e.g. hash_map
2494 // Handle interaction with different C++ standard libraries, which
2495 // expect these types to be in different namespaces.
2497 #define FOLLY_FBSTRING_HASH1(T) \
2499 struct hash< ::folly::basic_fbstring<T> > { \
2500 size_t operator()(const ::folly::fbstring& s) const { \
2501 return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2505 // The C++11 standard says that these four are defined
2506 #define FOLLY_FBSTRING_HASH \
2507 FOLLY_FBSTRING_HASH1(char) \
2508 FOLLY_FBSTRING_HASH1(char16_t) \
2509 FOLLY_FBSTRING_HASH1(char32_t) \
2510 FOLLY_FBSTRING_HASH1(wchar_t)
2518 #if FOLLY_HAVE_DEPRECATED_ASSOC
2519 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2520 namespace __gnu_cxx {
2524 } // namespace __gnu_cxx
2525 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2526 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2528 #undef FOLLY_FBSTRING_HASH
2529 #undef FOLLY_FBSTRING_HASH1
2531 #endif // _LIBSTDCXX_FBSTRING
2533 #pragma GCC diagnostic pop
2535 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2537 #undef FBSTRING_LIKELY
2538 #undef FBSTRING_UNLIKELY
2540 #endif // FOLLY_BASE_FBSTRING_H_