2 * Copyright 2014 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_
24 fbstring's behavior can be configured via two macro definitions, as
25 follows. Normally, fbstring does not write a '\0' at the end of
26 each string whenever it changes the underlying characters. Instead,
27 it lazily writes the '\0' whenever either c_str() or data()
30 This is standard-compliant behavior and may save costs in some
31 circumstances. However, it may be surprising to some client code
32 because c_str() and data() are const member functions (fbstring
33 uses the "mutable" storage class for its own state).
35 In order to appease client code that expects fbstring to be
36 zero-terminated at all times, if the preprocessor symbol
37 FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
38 i.e. it goes the extra mile to guarantee a '\0' is always planted
39 at the end of its data.
41 On the contrary, if the desire is to debug faulty client code that
42 unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
43 emphatically NOT a zero) at the end of each string if
44 FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
45 writes the '\0', of course.)
47 The preprocessor symbols FBSTRING_PERVERSE and
48 FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
49 enforced during preprocessing.
52 //#define FBSTRING_PERVERSE
53 //#define FBSTRING_CONSERVATIVE
55 #ifdef FBSTRING_PERVERSE
56 #ifdef FBSTRING_CONSERVATIVE
57 #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
63 #include <type_traits>
66 // libc++ doesn't provide this header
67 #ifndef _LIBCPP_VERSION
68 // This file appears in two locations: inside fbcode and in the
69 // libstdc++ source code (when embedding fbstring as std::string).
70 // To aid in this schizophrenic use, two macros are defined in
72 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
73 // gate use inside fbcode v. libstdc++
74 #include <bits/c++config.h>
77 #ifdef _LIBSTDCXX_FBSTRING
79 #pragma GCC system_header
81 // Handle the cases where the fbcode version (folly/Malloc.h) is included
82 // either before or after this inclusion.
83 #ifdef FOLLY_MALLOC_H_
84 #undef FOLLY_MALLOC_H_
85 #include "basic_fbstring_malloc.h"
87 #include "basic_fbstring_malloc.h"
88 #undef FOLLY_MALLOC_H_
91 #else // !_LIBSTDCXX_FBSTRING
97 #include "folly/Traits.h"
98 #include "folly/Malloc.h"
99 #include "folly/Hash.h"
101 #ifdef _GLIBCXX_SYMVER
102 #include <ext/hash_set>
103 #include <ext/hash_map>
108 // We defined these here rather than including Likely.h to avoid
109 // redefinition errors when fbstring is imported into libstdc++.
110 #if defined(__GNUC__) && __GNUC__ >= 4
111 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
112 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
114 #define FBSTRING_LIKELY(x) (x)
115 #define FBSTRING_UNLIKELY(x) (x)
118 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
119 #pragma GCC diagnostic push
120 #pragma GCC diagnostic ignored "-Wshadow"
122 // FBString cannot use throw when replacing std::string, though it may still
123 // use std::__throw_*
124 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
126 #ifdef _LIBSTDCXX_FBSTRING
127 namespace std _GLIBCXX_VISIBILITY(default) {
128 _GLIBCXX_BEGIN_NAMESPACE_VERSION
133 // Different versions of gcc/clang support different versions of
134 // the address sanitizer attribute. Unfortunately, this attribute
135 // has issues when inlining is used, so disable that as well.
136 #if defined(__clang__)
137 # if __has_feature(address_sanitizer)
138 # if __has_attribute(__no_address_safety_analysis__)
139 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
140 __attribute__((__no_address_safety_analysis__, __noinline__))
141 # elif __has_attribute(__no_sanitize_address__)
142 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
143 __attribute__((__no_sanitize_address__, __noinline__))
146 #elif defined (__GNUC__) && \
148 (__GNUC_MINOR__ >= 8) && \
150 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
151 __attribute__((__no_address_safety_analysis__, __noinline__))
153 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
154 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
157 namespace fbstring_detail {
159 template <class InIt, class OutIt>
162 typename std::iterator_traits<InIt>::difference_type n,
164 for (; n != 0; --n, ++b, ++d) {
170 template <class Pod, class T>
171 inline void pod_fill(Pod* b, Pod* e, T c) {
172 assert(b && e && b <= e);
173 /*static*/ if (sizeof(T) == 1) {
176 auto const ee = b + ((e - b) & ~7u);
177 for (; b != ee; b += 8) {
188 for (; b != e; ++b) {
195 * Lightly structured memcpy, simplifies copying PODs and introduces
196 * some asserts. Unfortunately using this function may cause
197 * measurable overhead (presumably because it adjusts from a begin/end
198 * convention to a pointer/size convention, so it does some extra
199 * arithmetic even though the caller might have done the inverse
200 * adaptation outside).
203 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
205 assert(d >= e || d + (e - b) <= b);
206 memcpy(d, b, (e - b) * sizeof(Pod));
210 * Lightly structured memmove, simplifies copying PODs and introduces
214 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
216 memmove(d, b, (e - b) * sizeof(*b));
219 } // namespace fbstring_detail
222 * Defines a special acquisition method for constructing fbstring
223 * objects. AcquireMallocatedString means that the user passes a
224 * pointer to a malloc-allocated string that the fbstring object will
227 enum class AcquireMallocatedString {};
230 * fbstring_core_model is a mock-up type that defines all required
231 * signatures of a fbstring core. The fbstring class itself uses such
232 * a core object to implement all of the numerous member functions
233 * required by the standard.
235 * If you want to define a new core, copy the definition below and
236 * implement the primitives. Then plug the core into basic_fbstring as
237 * a template argument.
239 template <class Char>
240 class fbstring_core_model {
242 fbstring_core_model();
243 fbstring_core_model(const fbstring_core_model &);
244 ~fbstring_core_model();
245 // Returns a pointer to string's buffer (currently only contiguous
246 // strings are supported). The pointer is guaranteed to be valid
247 // until the next call to a non-const member function.
248 const Char * data() const;
249 // Much like data(), except the string is prepared to support
250 // character-level changes. This call is a signal for
251 // e.g. reference-counted implementation to fork the data. The
252 // pointer is guaranteed to be valid until the next call to a
253 // non-const member function.
254 Char * mutable_data();
255 // Returns a pointer to string's buffer and guarantees that a
256 // readable '\0' lies right after the buffer. The pointer is
257 // guaranteed to be valid until the next call to a non-const member
259 const Char * c_str() const;
260 // Shrinks the string by delta characters. Asserts that delta <=
262 void shrink(size_t delta);
263 // Expands the string by delta characters (i.e. after this call
264 // size() will report the old size() plus delta) but without
265 // initializing the expanded region. Returns a pointer to the memory
266 // to be initialized (the beginning of the expanded portion). The
267 // caller is expected to fill the expanded area appropriately.
268 Char* expand_noinit(size_t delta);
269 // Expands the string by one character and sets the last character
271 void push_back(Char c);
272 // Returns the string's size.
274 // Returns the string's capacity, i.e. maximum size that the string
275 // can grow to without reallocation. Note that for reference counted
276 // strings that's technically a lie - even assigning characters
277 // within the existing size would cause a reallocation.
278 size_t capacity() const;
279 // Returns true if the data underlying the string is actually shared
280 // across multiple strings (in a refcounted fashion).
281 bool isShared() const;
282 // Makes sure that at least minCapacity characters are available for
283 // the string without reallocation. For reference-counted strings,
284 // it should fork the data even if minCapacity < size().
285 void reserve(size_t minCapacity);
288 fbstring_core_model& operator=(const fbstring_core_model &);
293 * gcc-4.7 throws what appears to be some false positive uninitialized
294 * warnings for the members of the MediumLarge struct. So, mute them here.
296 #if defined(__GNUC__) && !defined(__clang__)
297 # pragma GCC diagnostic push
298 # pragma GCC diagnostic ignored "-Wuninitialized"
302 * This is the core of the string. The code should work on 32- and
303 * 64-bit architectures and with any Char size. Porting to big endian
304 * architectures would require some changes.
306 * The storage is selected as follows (assuming we store one-byte
307 * characters on a 64-bit machine): (a) "small" strings between 0 and
308 * 23 chars are stored in-situ without allocation (the rightmost byte
309 * stores the size); (b) "medium" strings from 24 through 254 chars
310 * are stored in malloc-allocated memory that is copied eagerly; (c)
311 * "large" strings of 255 chars and above are stored in a similar
312 * structure as medium arrays, except that the string is
313 * reference-counted and copied lazily. the reference count is
314 * allocated right before the character array.
316 * The discriminator between these three strategies sits in the two
317 * most significant bits of the rightmost char of the storage. If
318 * neither is set, then the string is small (and its length sits in
319 * the lower-order bits of that rightmost character). If the MSb is
320 * set, the string is medium width. If the second MSb is set, then the
323 template <class Char> class fbstring_core {
325 fbstring_core() noexcept {
326 // Only initialize the tag, will set the MSBs (i.e. the small
327 // string size) to zero too
328 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
329 // or: setSmallSize(0);
331 assert(category() == isSmall && size() == 0);
334 fbstring_core(const fbstring_core & rhs) {
335 assert(&rhs != this);
336 // Simplest case first: small strings are bitblitted
337 if (rhs.category() == isSmall) {
338 assert(offsetof(MediumLarge, data_) == 0);
339 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
340 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
341 const size_t size = rhs.smallSize();
343 ml_.capacity_ = rhs.ml_.capacity_;
346 // Just write the whole thing, don't look at details. In
347 // particular we need to copy capacity anyway because we want
348 // to set the size (don't forget that the last character,
349 // which stores a short string's length, is shared with the
350 // ml_.capacity field).
353 assert(category() == isSmall && this->size() == rhs.size());
354 } else if (rhs.category() == isLarge) {
355 // Large strings are just refcounted
357 RefCounted::incrementRefs(ml_.data_);
358 assert(category() == isLarge && size() == rhs.size());
360 // Medium strings are copied eagerly. Don't forget to allocate
361 // one extra Char for the null terminator.
362 auto const allocSize =
363 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
364 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
365 fbstring_detail::pod_copy(rhs.ml_.data_,
367 rhs.ml_.data_ + rhs.ml_.size_ + 1,
369 // No need for writeTerminator() here, we copied one extra
370 // element just above.
371 ml_.size_ = rhs.ml_.size_;
372 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
373 assert(category() == isMedium);
375 assert(size() == rhs.size());
376 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
379 fbstring_core(fbstring_core&& goner) noexcept {
380 if (goner.category() == isSmall) {
381 // Just copy, leave the goner in peace
382 new(this) fbstring_core(goner.small_, goner.smallSize());
386 // Clean goner's carcass
387 goner.setSmallSize(0);
391 // NOTE(agallagher): The word-aligned copy path copies bytes which are
392 // outside the range of the string, and makes address sanitizer unhappy,
393 // so just disable it on this function.
394 fbstring_core(const Char *const data, const size_t size)
395 FBSTRING_DISABLE_ADDRESS_SANITIZER {
396 // Simplest case first: small strings are bitblitted
397 if (size <= maxSmallSize) {
398 // Layout is: Char* data_, size_t size_, size_t capacity_
399 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
400 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
401 // sizeof(size_t) must be a power of 2
402 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
404 // If data is aligned, use fast word-wise copying. Otherwise,
405 // use conservative memcpy.
406 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
407 fbstring_detail::pod_copy(data, data + size, small_);
409 // Copy one word (64 bits) at a time
410 const size_t byteSize = size * sizeof(Char);
411 if (byteSize > 2 * sizeof(size_t)) {
413 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
415 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
417 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
418 } else if (byteSize > sizeof(size_t)) {
421 } else if (size > 0) {
427 } else if (size <= maxMediumSize) {
428 // Medium strings are allocated normally. Don't forget to
429 // allocate one extra Char for the terminating null.
430 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
431 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
432 fbstring_detail::pod_copy(data, data + size, ml_.data_);
434 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
436 // Large strings are allocated differently
437 size_t effectiveCapacity = size;
438 auto const newRC = RefCounted::create(data, & effectiveCapacity);
439 ml_.data_ = newRC->data_;
441 ml_.capacity_ = effectiveCapacity | isLarge;
444 assert(this->size() == size);
445 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
448 ~fbstring_core() noexcept {
449 auto const c = category();
457 RefCounted::decrementRefs(ml_.data_);
460 // Snatches a previously mallocated string. The parameter "size"
461 // is the size of the string, and the parameter "allocatedSize"
462 // is the size of the mallocated block. The string must be
463 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
465 // So if you want a 2-character string, pass malloc(3) as "data",
466 // pass 2 as "size", and pass 3 as "allocatedSize".
467 fbstring_core(Char * const data,
469 const size_t allocatedSize,
470 AcquireMallocatedString) {
472 assert(allocatedSize >= size + 1);
473 assert(data[size] == '\0');
474 // Use the medium string storage
477 // Don't forget about null terminator
478 ml_.capacity_ = (allocatedSize - 1) | isMedium;
480 // No need for the memory
486 // swap below doesn't test whether &rhs == this (and instead
487 // potentially does extra work) on the premise that the rarity of
488 // that situation actually makes the check more expensive than is
490 void swap(fbstring_core & rhs) {
496 // In C++11 data() and c_str() are 100% equivalent.
497 const Char * data() const {
501 Char * mutable_data() {
502 auto const c = category();
506 assert(c == isMedium || c == isLarge);
507 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
509 size_t effectiveCapacity = ml_.capacity();
510 auto const newRC = RefCounted::create(& effectiveCapacity);
511 // If this fails, someone placed the wrong capacity in an
513 assert(effectiveCapacity >= ml_.capacity());
514 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
516 RefCounted::decrementRefs(ml_.data_);
517 ml_.data_ = newRC->data_;
518 // No need to call writeTerminator(), we have + 1 above.
523 const Char * c_str() const {
524 auto const c = category();
525 #ifdef FBSTRING_PERVERSE
527 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
528 || small_[smallSize()] == '\0');
529 small_[smallSize()] = '\0';
532 assert(c == isMedium || c == isLarge);
533 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
534 ml_.data_[ml_.size_] = '\0';
535 #elif defined(FBSTRING_CONSERVATIVE)
537 assert(small_[smallSize()] == '\0');
540 assert(c == isMedium || c == isLarge);
541 assert(ml_.data_[ml_.size_] == '\0');
544 small_[smallSize()] = '\0';
547 assert(c == isMedium || c == isLarge);
548 ml_.data_[ml_.size_] = '\0';
553 void shrink(const size_t delta) {
554 if (category() == isSmall) {
555 // Check for underflow
556 assert(delta <= smallSize());
557 setSmallSize(smallSize() - delta);
558 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
559 // Medium strings and unique large strings need no special
561 assert(ml_.size_ >= delta);
564 assert(ml_.size_ >= delta);
565 // Shared large string, must make unique. This is because of the
566 // durn terminator must be written, which may trample the shared
569 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
571 // No need to write the terminator.
577 void reserve(size_t minCapacity) {
578 if (category() == isLarge) {
580 if (RefCounted::refs(ml_.data_) > 1) {
581 // We must make it unique regardless; in-place reallocation is
582 // useless if the string is shared. In order to not surprise
583 // people, reserve the new block at current capacity or
584 // more. That way, a string's capacity never shrinks after a
586 minCapacity = std::max(minCapacity, ml_.capacity());
587 auto const newRC = RefCounted::create(& minCapacity);
588 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
590 // Done with the old data. No need to call writeTerminator(),
591 // we have + 1 above.
592 RefCounted::decrementRefs(ml_.data_);
593 ml_.data_ = newRC->data_;
594 ml_.capacity_ = minCapacity | isLarge;
595 // size remains unchanged
597 // String is not shared, so let's try to realloc (if needed)
598 if (minCapacity > ml_.capacity()) {
599 // Asking for more memory
601 RefCounted::reallocate(ml_.data_, ml_.size_,
602 ml_.capacity(), minCapacity);
603 ml_.data_ = newRC->data_;
604 ml_.capacity_ = minCapacity | isLarge;
607 assert(capacity() >= minCapacity);
609 } else if (category() == isMedium) {
610 // String is not shared
611 if (minCapacity <= ml_.capacity()) {
612 return; // nothing to do, there's enough room
614 if (minCapacity <= maxMediumSize) {
615 // Keep the string at medium size. Don't forget to allocate
616 // one extra Char for the terminating null.
617 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
618 ml_.data_ = static_cast<Char *>(
621 ml_.size_ * sizeof(Char),
622 (ml_.capacity() + 1) * sizeof(Char),
625 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
627 // Conversion from medium to large string
628 fbstring_core nascent;
629 // Will recurse to another branch of this function
630 nascent.reserve(minCapacity);
631 nascent.ml_.size_ = ml_.size_;
632 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
636 assert(capacity() >= minCapacity);
639 assert(category() == isSmall);
640 if (minCapacity > maxMediumSize) {
642 auto const newRC = RefCounted::create(& minCapacity);
643 auto const size = smallSize();
644 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
645 // No need for writeTerminator(), we wrote it above with + 1.
646 ml_.data_ = newRC->data_;
648 ml_.capacity_ = minCapacity | isLarge;
649 assert(capacity() >= minCapacity);
650 } else if (minCapacity > maxSmallSize) {
652 // Don't forget to allocate one extra Char for the terminating null
653 auto const allocSizeBytes =
654 goodMallocSize((1 + minCapacity) * sizeof(Char));
655 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
656 auto const size = smallSize();
657 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
658 // No need for writeTerminator(), we wrote it above with + 1.
661 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
664 // Nothing to do, everything stays put
667 assert(capacity() >= minCapacity);
670 Char * expand_noinit(const size_t delta) {
671 // Strategy is simple: make room, then change size
672 assert(capacity() >= size());
674 if (category() == isSmall) {
677 if (newSz <= maxSmallSize) {
685 newSz = ml_.size_ + delta;
686 if (newSz > capacity()) {
690 assert(capacity() >= newSz);
691 // Category can't be small - we took care of that above
692 assert(category() == isMedium || category() == isLarge);
695 assert(size() == newSz);
696 return ml_.data_ + sz;
699 void push_back(Char c) {
700 assert(capacity() >= size());
702 if (category() == isSmall) {
704 if (sz < maxSmallSize) {
705 setSmallSize(sz + 1);
710 reserve(maxSmallSize * 2);
713 if (sz == capacity()) { // always true for isShared()
714 reserve(1 + sz * 3 / 2); // ensures not shared
718 assert(capacity() >= sz + 1);
719 // Category can't be small - we took care of that above
720 assert(category() == isMedium || category() == isLarge);
726 size_t size() const {
727 return category() == isSmall ? smallSize() : ml_.size_;
730 size_t capacity() const {
731 switch (category()) {
735 // For large-sized strings, a multi-referenced chunk has no
736 // available capacity. This is because any attempt to append
737 // data would trigger a new allocation.
738 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
741 return ml_.capacity();
744 bool isShared() const {
745 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
748 #ifdef FBSTRING_PERVERSE
749 enum { TERMINATOR = '^' };
751 enum { TERMINATOR = '\0' };
754 void writeTerminator() {
755 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
756 if (category() == isSmall) {
757 const auto s = smallSize();
758 if (s != maxSmallSize) {
759 small_[s] = TERMINATOR;
762 ml_.data_[ml_.size_] = TERMINATOR;
769 fbstring_core & operator=(const fbstring_core & rhs);
776 size_t capacity() const {
777 return capacity_ & capacityExtractMask;
782 std::atomic<size_t> refCount_;
785 static RefCounted * fromData(Char * p) {
786 return static_cast<RefCounted*>(
788 static_cast<unsigned char*>(static_cast<void*>(p))
789 - sizeof(refCount_)));
792 static size_t refs(Char * p) {
793 return fromData(p)->refCount_.load(std::memory_order_acquire);
796 static void incrementRefs(Char * p) {
797 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
800 static void decrementRefs(Char * p) {
801 auto const dis = fromData(p);
802 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
809 static RefCounted * create(size_t * size) {
810 // Don't forget to allocate one extra Char for the terminating
811 // null. In this case, however, one Char is already part of the
813 const size_t allocSize = goodMallocSize(
814 sizeof(RefCounted) + *size * sizeof(Char));
815 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
816 result->refCount_.store(1, std::memory_order_release);
817 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
821 static RefCounted * create(const Char * data, size_t * size) {
822 const size_t effectiveSize = *size;
823 auto result = create(size);
824 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
828 static RefCounted * reallocate(Char *const data,
829 const size_t currentSize,
830 const size_t currentCapacity,
831 const size_t newCapacity) {
832 assert(newCapacity > 0 && newCapacity > currentSize);
833 auto const dis = fromData(data);
834 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
835 // Don't forget to allocate one extra Char for the terminating
836 // null. In this case, however, one Char is already part of the
838 auto result = static_cast<RefCounted*>(
840 sizeof(RefCounted) + currentSize * sizeof(Char),
841 sizeof(RefCounted) + currentCapacity * sizeof(Char),
842 sizeof(RefCounted) + newCapacity * sizeof(Char)));
843 assert(result->refCount_.load(std::memory_order_acquire) == 1);
849 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
850 mutable MediumLarge ml_;
854 lastChar = sizeof(MediumLarge) - 1,
855 maxSmallSize = lastChar / sizeof(Char),
856 maxMediumSize = 254 / sizeof(Char), // coincides with the small
857 // bin size in dlmalloc
858 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
859 capacityExtractMask = ~categoryExtractMask,
861 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
862 "Corrupt memory layout for fbstring.");
866 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
867 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
870 Category category() const {
871 // Assumes little endian
872 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
875 size_t smallSize() const {
876 assert(category() == isSmall &&
877 static_cast<size_t>(small_[maxSmallSize])
878 <= static_cast<size_t>(maxSmallSize));
879 return static_cast<size_t>(maxSmallSize)
880 - static_cast<size_t>(small_[maxSmallSize]);
883 void setSmallSize(size_t s) {
884 // Warning: this should work with uninitialized strings too,
885 // so don't assume anything about the previous value of
886 // small_[maxSmallSize].
887 assert(s <= maxSmallSize);
888 small_[maxSmallSize] = maxSmallSize - s;
892 #if defined(__GNUC__) && !defined(__clang__)
893 # pragma GCC diagnostic pop
896 #ifndef _LIBSTDCXX_FBSTRING
898 * Dummy fbstring core that uses an actual std::string. This doesn't
899 * make any sense - it's just for testing purposes.
901 template <class Char>
902 class dummy_fbstring_core {
904 dummy_fbstring_core() {
906 dummy_fbstring_core(const dummy_fbstring_core& another)
907 : backend_(another.backend_) {
909 dummy_fbstring_core(const Char * s, size_t n)
912 void swap(dummy_fbstring_core & rhs) {
913 backend_.swap(rhs.backend_);
915 const Char * data() const {
916 return backend_.data();
918 Char * mutable_data() {
919 //assert(!backend_.empty());
920 return &*backend_.begin();
922 void shrink(size_t delta) {
923 assert(delta <= size());
924 backend_.resize(size() - delta);
926 Char * expand_noinit(size_t delta) {
927 auto const sz = size();
928 backend_.resize(size() + delta);
929 return backend_.data() + sz;
931 void push_back(Char c) {
932 backend_.push_back(c);
934 size_t size() const {
935 return backend_.size();
937 size_t capacity() const {
938 return backend_.capacity();
940 bool isShared() const {
943 void reserve(size_t minCapacity) {
944 backend_.reserve(minCapacity);
948 std::basic_string<Char> backend_;
950 #endif // !_LIBSTDCXX_FBSTRING
953 * This is the basic_string replacement. For conformity,
954 * basic_fbstring takes the same template parameters, plus the last
955 * one which is the core.
957 #ifdef _LIBSTDCXX_FBSTRING
958 template <typename E, class T, class A, class Storage>
960 template <typename E,
961 class T = std::char_traits<E>,
962 class A = std::allocator<E>,
963 class Storage = fbstring_core<E> >
965 class basic_fbstring {
969 void (*throw_exc)(const char*),
971 if (!condition) throw_exc(msg);
974 bool isSane() const {
977 empty() == (size() == 0) &&
978 empty() == (begin() == end()) &&
979 size() <= max_size() &&
980 capacity() <= max_size() &&
981 size() <= capacity() &&
982 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
986 friend struct Invariant;
989 explicit Invariant(const basic_fbstring& s) : s_(s) {
996 const basic_fbstring& s_;
998 explicit Invariant(const basic_fbstring&) {}
1000 Invariant& operator=(const Invariant&);
1005 typedef T traits_type;
1006 typedef typename traits_type::char_type value_type;
1007 typedef A allocator_type;
1008 typedef typename A::size_type size_type;
1009 typedef typename A::difference_type difference_type;
1011 typedef typename A::reference reference;
1012 typedef typename A::const_reference const_reference;
1013 typedef typename A::pointer pointer;
1014 typedef typename A::const_pointer const_pointer;
1016 typedef E* iterator;
1017 typedef const E* const_iterator;
1018 typedef std::reverse_iterator<iterator
1019 #ifdef NO_ITERATOR_TRAITS
1023 typedef std::reverse_iterator<const_iterator
1024 #ifdef NO_ITERATOR_TRAITS
1027 > const_reverse_iterator;
1029 static const size_type npos; // = size_type(-1)
1032 static void procrustes(size_type& n, size_type nmax) {
1033 if (n > nmax) n = nmax;
1037 // C++11 21.4.2 construct/copy/destroy
1038 explicit basic_fbstring(const A& a = A()) noexcept {
1041 basic_fbstring(const basic_fbstring& str)
1042 : store_(str.store_) {
1046 basic_fbstring(basic_fbstring&& goner) noexcept
1047 : store_(std::move(goner.store_)) {
1050 #ifndef _LIBSTDCXX_FBSTRING
1051 // This is defined for compatibility with std::string
1052 /* implicit */ basic_fbstring(const std::string& str)
1053 : store_(str.data(), str.size()) {
1057 basic_fbstring(const basic_fbstring& str, size_type pos,
1058 size_type n = npos, const A& a = A()) {
1059 assign(str, pos, n);
1062 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1064 ? traits_type::length(s)
1066 std::__throw_logic_error(
1067 "basic_fbstring: null pointer initializer not valid");
1072 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1076 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1077 auto const data = store_.expand_noinit(n);
1078 fbstring_detail::pod_fill(data, data + n, c);
1079 store_.writeTerminator();
1082 template <class InIt>
1083 basic_fbstring(InIt begin, InIt end,
1084 typename std::enable_if<
1085 !std::is_same<typename std::remove_const<InIt>::type,
1086 value_type*>::value, const A>::type & a = A()) {
1090 // Specialization for const char*, const char*
1091 basic_fbstring(const value_type* b, const value_type* e)
1092 : store_(b, e - b) {
1095 // Nonstandard constructor
1096 basic_fbstring(value_type *s, size_type n, size_type c,
1097 AcquireMallocatedString a)
1098 : store_(s, n, c, a) {
1101 // Construction from initialization list
1102 basic_fbstring(std::initializer_list<value_type> il) {
1103 assign(il.begin(), il.end());
1106 ~basic_fbstring() noexcept {
1109 basic_fbstring& operator=(const basic_fbstring& lhs) {
1110 if (FBSTRING_UNLIKELY(&lhs == this)) {
1113 auto const oldSize = size();
1114 auto const srcSize = lhs.size();
1115 if (capacity() >= srcSize && !store_.isShared()) {
1116 // great, just copy the contents
1117 if (oldSize < srcSize)
1118 store_.expand_noinit(srcSize - oldSize);
1120 store_.shrink(oldSize - srcSize);
1121 assert(size() == srcSize);
1122 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1123 store_.writeTerminator();
1125 // need to reallocate, so we may as well create a brand new string
1126 basic_fbstring(lhs).swap(*this);
1132 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1133 if (FBSTRING_UNLIKELY(&goner == this)) {
1134 // Compatibility with std::basic_string<>,
1135 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1138 // No need of this anymore
1139 this->~basic_fbstring();
1140 // Move the goner into this
1141 new(&store_) fbstring_core<E>(std::move(goner.store_));
1145 #ifndef _LIBSTDCXX_FBSTRING
1146 // Compatibility with std::string
1147 basic_fbstring & operator=(const std::string & rhs) {
1148 return assign(rhs.data(), rhs.size());
1151 // Compatibility with std::string
1152 std::string toStdString() const {
1153 return std::string(data(), size());
1156 // A lot of code in fbcode still uses this method, so keep it here for now.
1157 const basic_fbstring& toStdString() const {
1162 basic_fbstring& operator=(const value_type* s) {
1166 basic_fbstring& operator=(value_type c) {
1168 store_.expand_noinit(1);
1169 } else if (store_.isShared()) {
1170 basic_fbstring(1, c).swap(*this);
1173 store_.shrink(size() - 1);
1175 *store_.mutable_data() = c;
1176 store_.writeTerminator();
1180 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1181 return assign(il.begin(), il.end());
1184 // C++11 21.4.3 iterators:
1185 iterator begin() { return store_.mutable_data(); }
1187 const_iterator begin() const { return store_.data(); }
1189 const_iterator cbegin() const { return begin(); }
1192 return store_.mutable_data() + store_.size();
1195 const_iterator end() const {
1196 return store_.data() + store_.size();
1199 const_iterator cend() const { return end(); }
1201 reverse_iterator rbegin() {
1202 return reverse_iterator(end());
1205 const_reverse_iterator rbegin() const {
1206 return const_reverse_iterator(end());
1209 const_reverse_iterator crbegin() const { return rbegin(); }
1211 reverse_iterator rend() {
1212 return reverse_iterator(begin());
1215 const_reverse_iterator rend() const {
1216 return const_reverse_iterator(begin());
1219 const_reverse_iterator crend() const { return rend(); }
1222 // C++11 21.4.5, element access:
1223 const value_type& front() const { return *begin(); }
1224 const value_type& back() const {
1226 // Should be begin()[size() - 1], but that branches twice
1227 return *(end() - 1);
1229 value_type& front() { return *begin(); }
1230 value_type& back() {
1232 // Should be begin()[size() - 1], but that branches twice
1233 return *(end() - 1);
1240 // C++11 21.4.4 capacity:
1241 size_type size() const { return store_.size(); }
1243 size_type length() const { return size(); }
1245 size_type max_size() const {
1246 return std::numeric_limits<size_type>::max();
1249 void resize(const size_type n, const value_type c = value_type()) {
1250 auto size = this->size();
1252 store_.shrink(size - n);
1254 // Do this in two steps to minimize slack memory copied (see
1256 auto const capacity = this->capacity();
1257 assert(capacity >= size);
1258 if (size < capacity) {
1259 auto delta = std::min(n, capacity) - size;
1260 store_.expand_noinit(delta);
1261 fbstring_detail::pod_fill(begin() + size, end(), c);
1264 store_.writeTerminator();
1269 auto const delta = n - size;
1270 store_.expand_noinit(delta);
1271 fbstring_detail::pod_fill(end() - delta, end(), c);
1272 store_.writeTerminator();
1274 assert(this->size() == n);
1277 size_type capacity() const { return store_.capacity(); }
1279 void reserve(size_type res_arg = 0) {
1280 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1281 store_.reserve(res_arg);
1284 void shrink_to_fit() {
1285 // Shrink only if slack memory is sufficiently large
1286 if (capacity() < size() * 3 / 2) {
1289 basic_fbstring(cbegin(), cend()).swap(*this);
1292 void clear() { resize(0); }
1294 bool empty() const { return size() == 0; }
1296 // C++11 21.4.5 element access:
1297 const_reference operator[](size_type pos) const {
1298 return *(c_str() + pos);
1301 reference operator[](size_type pos) {
1302 if (pos == size()) {
1303 // Just call c_str() to make sure '\0' is present
1306 return *(begin() + pos);
1309 const_reference at(size_type n) const {
1310 enforce(n <= size(), std::__throw_out_of_range, "");
1314 reference at(size_type n) {
1315 enforce(n < size(), std::__throw_out_of_range, "");
1319 // C++11 21.4.6 modifiers:
1320 basic_fbstring& operator+=(const basic_fbstring& str) {
1324 basic_fbstring& operator+=(const value_type* s) {
1328 basic_fbstring& operator+=(const value_type c) {
1333 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1338 basic_fbstring& append(const basic_fbstring& str) {
1340 auto desiredSize = size() + str.size();
1342 append(str.data(), str.size());
1343 assert(size() == desiredSize);
1347 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1349 const size_type sz = str.size();
1350 enforce(pos <= sz, std::__throw_out_of_range, "");
1351 procrustes(n, sz - pos);
1352 return append(str.data() + pos, n);
1355 basic_fbstring& append(const value_type* s, size_type n) {
1357 Invariant checker(*this);
1360 if (FBSTRING_UNLIKELY(!n)) {
1361 // Unlikely but must be done
1364 auto const oldSize = size();
1365 auto const oldData = data();
1366 // Check for aliasing (rare). We could use "<=" here but in theory
1367 // those do not work for pointers unless the pointers point to
1368 // elements in the same array. For that reason we use
1369 // std::less_equal, which is guaranteed to offer a total order
1370 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1372 std::less_equal<const value_type*> le;
1373 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1374 assert(le(s + n, oldData + oldSize));
1375 const size_type offset = s - oldData;
1376 store_.reserve(oldSize + n);
1377 // Restore the source
1378 s = data() + offset;
1380 // Warning! Repeated appends with short strings may actually incur
1381 // practically quadratic performance. Avoid that by pushing back
1382 // the first character (which ensures exponential growth) and then
1383 // appending the rest normally. Worst case the append may incur a
1384 // second allocation but that will be rare.
1387 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1388 assert(size() == oldSize + n + 1);
1392 basic_fbstring& append(const value_type* s) {
1393 return append(s, traits_type::length(s));
1396 basic_fbstring& append(size_type n, value_type c) {
1397 resize(size() + n, c);
1401 template<class InputIterator>
1402 basic_fbstring& append(InputIterator first, InputIterator last) {
1403 insert(end(), first, last);
1407 basic_fbstring& append(std::initializer_list<value_type> il) {
1408 return append(il.begin(), il.end());
1411 void push_back(const value_type c) { // primitive
1412 store_.push_back(c);
1415 basic_fbstring& assign(const basic_fbstring& str) {
1416 if (&str == this) return *this;
1417 return assign(str.data(), str.size());
1420 basic_fbstring& assign(basic_fbstring&& str) {
1421 return *this = std::move(str);
1424 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1426 const size_type sz = str.size();
1427 enforce(pos <= sz, std::__throw_out_of_range, "");
1428 procrustes(n, sz - pos);
1429 return assign(str.data() + pos, n);
1432 basic_fbstring& assign(const value_type* s, const size_type n) {
1433 Invariant checker(*this);
1436 std::copy(s, s + n, begin());
1438 assert(size() == n);
1440 const value_type *const s2 = s + size();
1441 std::copy(s, s2, begin());
1442 append(s2, n - size());
1443 assert(size() == n);
1445 store_.writeTerminator();
1446 assert(size() == n);
1450 basic_fbstring& assign(const value_type* s) {
1451 return assign(s, traits_type::length(s));
1454 basic_fbstring& assign(std::initializer_list<value_type> il) {
1455 return assign(il.begin(), il.end());
1458 template <class ItOrLength, class ItOrChar>
1459 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1460 return replace(begin(), end(), first_or_n, last_or_c);
1463 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1464 return insert(pos1, str.data(), str.size());
1467 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1468 size_type pos2, size_type n) {
1469 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1470 procrustes(n, str.length() - pos2);
1471 return insert(pos1, str.data() + pos2, n);
1474 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1475 enforce(pos <= length(), std::__throw_out_of_range, "");
1476 insert(begin() + pos, s, s + n);
1480 basic_fbstring& insert(size_type pos, const value_type* s) {
1481 return insert(pos, s, traits_type::length(s));
1484 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1485 enforce(pos <= length(), std::__throw_out_of_range, "");
1486 insert(begin() + pos, n, c);
1490 iterator insert(const_iterator p, const value_type c) {
1491 const size_type pos = p - begin();
1493 return begin() + pos;
1497 template <int i> class Selector {};
1499 iterator insertImplDiscr(const_iterator p,
1500 size_type n, value_type c, Selector<1>) {
1501 Invariant checker(*this);
1503 auto const pos = p - begin();
1504 assert(p >= begin() && p <= end());
1505 if (capacity() - size() < n) {
1506 const size_type sz = p - begin();
1507 reserve(size() + n);
1510 const iterator oldEnd = end();
1511 if (n < size_type(oldEnd - p)) {
1512 append(oldEnd - n, oldEnd);
1514 // reverse_iterator(oldEnd - n),
1515 // reverse_iterator(p),
1516 // reverse_iterator(oldEnd));
1517 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1519 std::fill(begin() + pos, begin() + pos + n, c);
1521 append(n - (end() - p), c);
1522 append(iterator(p), oldEnd);
1523 std::fill(iterator(p), oldEnd, c);
1525 store_.writeTerminator();
1526 return begin() + pos;
1529 template<class InputIter>
1530 iterator insertImplDiscr(const_iterator i,
1531 InputIter b, InputIter e, Selector<0>) {
1532 return insertImpl(i, b, e,
1533 typename std::iterator_traits<InputIter>::iterator_category());
1536 template <class FwdIterator>
1537 iterator insertImpl(const_iterator i,
1538 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1539 Invariant checker(*this);
1541 const size_type pos = i - begin();
1542 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1543 std::distance(s1, s2);
1545 using namespace fbstring_detail;
1546 assert(pos <= size());
1548 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1549 capacity() - size();
1551 // realloc the string
1552 reserve(size() + n2);
1555 if (pos + n2 <= size()) {
1556 const iterator tailBegin = end() - n2;
1557 store_.expand_noinit(n2);
1558 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1559 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1560 reverse_iterator(tailBegin + n2));
1561 std::copy(s1, s2, begin() + pos);
1564 const size_type old_size = size();
1565 std::advance(t, old_size - pos);
1566 const size_t newElems = std::distance(t, s2);
1567 store_.expand_noinit(n2);
1568 std::copy(t, s2, begin() + old_size);
1569 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1570 begin() + old_size + newElems);
1571 std::copy(s1, t, begin() + pos);
1573 store_.writeTerminator();
1574 return begin() + pos;
1577 template <class InputIterator>
1578 iterator insertImpl(const_iterator i,
1579 InputIterator b, InputIterator e,
1580 std::input_iterator_tag) {
1581 const auto pos = i - begin();
1582 basic_fbstring temp(begin(), i);
1583 for (; b != e; ++b) {
1586 temp.append(i, cend());
1588 return begin() + pos;
1592 template <class ItOrLength, class ItOrChar>
1593 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1594 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1595 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1598 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1599 return insert(p, il.begin(), il.end());
1602 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1603 Invariant checker(*this);
1605 enforce(pos <= length(), std::__throw_out_of_range, "");
1606 procrustes(n, length() - pos);
1607 std::copy(begin() + pos + n, end(), begin() + pos);
1608 resize(length() - n);
1612 iterator erase(iterator position) {
1613 const size_type pos(position - begin());
1614 enforce(pos <= size(), std::__throw_out_of_range, "");
1616 return begin() + pos;
1619 iterator erase(iterator first, iterator last) {
1620 const size_type pos(first - begin());
1621 erase(pos, last - first);
1622 return begin() + pos;
1625 // Replaces at most n1 chars of *this, starting with pos1 with the
1627 basic_fbstring& replace(size_type pos1, size_type n1,
1628 const basic_fbstring& str) {
1629 return replace(pos1, n1, str.data(), str.size());
1632 // Replaces at most n1 chars of *this, starting with pos1,
1633 // with at most n2 chars of str starting with pos2
1634 basic_fbstring& replace(size_type pos1, size_type n1,
1635 const basic_fbstring& str,
1636 size_type pos2, size_type n2) {
1637 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1638 return replace(pos1, n1, str.data() + pos2,
1639 std::min(n2, str.size() - pos2));
1642 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1643 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1644 return replace(pos, n1, s, traits_type::length(s));
1647 // Replaces at most n1 chars of *this, starting with pos, with n2
1650 // consolidated with
1652 // Replaces at most n1 chars of *this, starting with pos, with at
1653 // most n2 chars of str. str must have at least n2 chars.
1654 template <class StrOrLength, class NumOrChar>
1655 basic_fbstring& replace(size_type pos, size_type n1,
1656 StrOrLength s_or_n2, NumOrChar n_or_c) {
1657 Invariant checker(*this);
1659 enforce(pos <= size(), std::__throw_out_of_range, "");
1660 procrustes(n1, length() - pos);
1661 const iterator b = begin() + pos;
1662 return replace(b, b + n1, s_or_n2, n_or_c);
1665 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1666 return replace(i1, i2, str.data(), str.length());
1669 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1670 return replace(i1, i2, s, traits_type::length(s));
1674 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1675 const value_type* s, size_type n,
1678 assert(begin() <= i1 && i1 <= end());
1679 assert(begin() <= i2 && i2 <= end());
1680 return replace(i1, i2, s, s + n);
1683 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1684 size_type n2, value_type c, Selector<1>) {
1685 const size_type n1 = i2 - i1;
1687 std::fill(i1, i1 + n2, c);
1690 std::fill(i1, i2, c);
1691 insert(i2, n2 - n1, c);
1697 template <class InputIter>
1698 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1699 InputIter b, InputIter e,
1701 replaceImpl(i1, i2, b, e,
1702 typename std::iterator_traits<InputIter>::iterator_category());
1707 template <class FwdIterator>
1708 bool replaceAliased(iterator i1, iterator i2,
1709 FwdIterator s1, FwdIterator s2, std::false_type) {
1713 template <class FwdIterator>
1714 bool replaceAliased(iterator i1, iterator i2,
1715 FwdIterator s1, FwdIterator s2, std::true_type) {
1716 static const std::less_equal<const value_type*> le =
1717 std::less_equal<const value_type*>();
1718 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1722 // Aliased replace, copy to new string
1723 basic_fbstring temp;
1724 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1725 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1730 template <class FwdIterator>
1731 void replaceImpl(iterator i1, iterator i2,
1732 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1733 Invariant checker(*this);
1736 // Handle aliased replace
1737 if (replaceAliased(i1, i2, s1, s2,
1738 std::integral_constant<bool,
1739 std::is_same<FwdIterator, iterator>::value ||
1740 std::is_same<FwdIterator, const_iterator>::value>())) {
1744 auto const n1 = i2 - i1;
1746 auto const n2 = std::distance(s1, s2);
1751 std::copy(s1, s2, i1);
1755 fbstring_detail::copy_n(s1, n1, i1);
1756 std::advance(s1, n1);
1762 template <class InputIterator>
1763 void replaceImpl(iterator i1, iterator i2,
1764 InputIterator b, InputIterator e, std::input_iterator_tag) {
1765 basic_fbstring temp(begin(), i1);
1766 temp.append(b, e).append(i2, end());
1771 template <class T1, class T2>
1772 basic_fbstring& replace(iterator i1, iterator i2,
1773 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1775 num1 = std::numeric_limits<T1>::is_specialized,
1776 num2 = std::numeric_limits<T2>::is_specialized;
1777 return replaceImplDiscr(
1778 i1, i2, first_or_n_or_s, last_or_c_or_n,
1779 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1782 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1783 enforce(pos <= size(), std::__throw_out_of_range, "");
1784 procrustes(n, size() - pos);
1786 fbstring_detail::pod_copy(
1793 void swap(basic_fbstring& rhs) {
1794 store_.swap(rhs.store_);
1797 const value_type* c_str() const {
1798 return store_.c_str();
1801 const value_type* data() const { return c_str(); }
1803 allocator_type get_allocator() const {
1804 return allocator_type();
1807 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1808 return find(str.data(), pos, str.length());
1811 size_type find(const value_type* needle, const size_type pos,
1812 const size_type nsize) const {
1813 if (!nsize) return pos;
1814 auto const size = this->size();
1815 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1816 // that nsize + pos does not wrap around.
1817 if (nsize + pos > size || nsize + pos < pos) return npos;
1818 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1819 // the last characters first
1820 auto const haystack = data();
1821 auto const nsize_1 = nsize - 1;
1822 auto const lastNeedle = needle[nsize_1];
1824 // Boyer-Moore skip value for the last char in the needle. Zero is
1825 // not a valid value; skip will be computed the first time it's
1829 const E * i = haystack + pos;
1830 auto iEnd = haystack + size - nsize_1;
1833 // Boyer-Moore: match the last element in the needle
1834 while (i[nsize_1] != lastNeedle) {
1840 // Here we know that the last char matches
1841 // Continue in pedestrian mode
1842 for (size_t j = 0; ; ) {
1844 if (i[j] != needle[j]) {
1845 // Not found, we can skip
1846 // Compute the skip value lazily
1849 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1856 // Check if done searching
1859 return i - haystack;
1866 size_type find(const value_type* s, size_type pos = 0) const {
1867 return find(s, pos, traits_type::length(s));
1870 size_type find (value_type c, size_type pos = 0) const {
1871 return find(&c, pos, 1);
1874 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1875 return rfind(str.data(), pos, str.length());
1878 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1879 if (n > length()) return npos;
1880 pos = std::min(pos, length() - n);
1881 if (n == 0) return pos;
1883 const_iterator i(begin() + pos);
1885 if (traits_type::eq(*i, *s)
1886 && traits_type::compare(&*i, s, n) == 0) {
1889 if (i == begin()) break;
1894 size_type rfind(const value_type* s, size_type pos = npos) const {
1895 return rfind(s, pos, traits_type::length(s));
1898 size_type rfind(value_type c, size_type pos = npos) const {
1899 return rfind(&c, pos, 1);
1902 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1903 return find_first_of(str.data(), pos, str.length());
1906 size_type find_first_of(const value_type* s,
1907 size_type pos, size_type n) const {
1908 if (pos > length() || n == 0) return npos;
1909 const_iterator i(begin() + pos),
1911 for (; i != finish; ++i) {
1912 if (traits_type::find(s, n, *i) != 0) {
1919 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1920 return find_first_of(s, pos, traits_type::length(s));
1923 size_type find_first_of(value_type c, size_type pos = 0) const {
1924 return find_first_of(&c, pos, 1);
1927 size_type find_last_of (const basic_fbstring& str,
1928 size_type pos = npos) const {
1929 return find_last_of(str.data(), pos, str.length());
1932 size_type find_last_of (const value_type* s, size_type pos,
1933 size_type n) const {
1934 if (!empty() && n > 0) {
1935 pos = std::min(pos, length() - 1);
1936 const_iterator i(begin() + pos);
1938 if (traits_type::find(s, n, *i) != 0) {
1941 if (i == begin()) break;
1947 size_type find_last_of (const value_type* s,
1948 size_type pos = npos) const {
1949 return find_last_of(s, pos, traits_type::length(s));
1952 size_type find_last_of (value_type c, size_type pos = npos) const {
1953 return find_last_of(&c, pos, 1);
1956 size_type find_first_not_of(const basic_fbstring& str,
1957 size_type pos = 0) const {
1958 return find_first_not_of(str.data(), pos, str.size());
1961 size_type find_first_not_of(const value_type* s, size_type pos,
1962 size_type n) const {
1963 if (pos < length()) {
1967 for (; i != finish; ++i) {
1968 if (traits_type::find(s, n, *i) == 0) {
1976 size_type find_first_not_of(const value_type* s,
1977 size_type pos = 0) const {
1978 return find_first_not_of(s, pos, traits_type::length(s));
1981 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1982 return find_first_not_of(&c, pos, 1);
1985 size_type find_last_not_of(const basic_fbstring& str,
1986 size_type pos = npos) const {
1987 return find_last_not_of(str.data(), pos, str.length());
1990 size_type find_last_not_of(const value_type* s, size_type pos,
1991 size_type n) const {
1992 if (!this->empty()) {
1993 pos = std::min(pos, size() - 1);
1994 const_iterator i(begin() + pos);
1996 if (traits_type::find(s, n, *i) == 0) {
1999 if (i == begin()) break;
2005 size_type find_last_not_of(const value_type* s,
2006 size_type pos = npos) const {
2007 return find_last_not_of(s, pos, traits_type::length(s));
2010 size_type find_last_not_of (value_type c, size_type pos = npos) const {
2011 return find_last_not_of(&c, pos, 1);
2014 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
2015 enforce(pos <= size(), std::__throw_out_of_range, "");
2016 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2019 int compare(const basic_fbstring& str) const {
2020 // FIX due to Goncalo N M de Carvalho July 18, 2005
2021 return compare(0, size(), str);
2024 int compare(size_type pos1, size_type n1,
2025 const basic_fbstring& str) const {
2026 return compare(pos1, n1, str.data(), str.size());
2029 int compare(size_type pos1, size_type n1,
2030 const value_type* s) const {
2031 return compare(pos1, n1, s, traits_type::length(s));
2034 int compare(size_type pos1, size_type n1,
2035 const value_type* s, size_type n2) const {
2036 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2037 procrustes(n1, size() - pos1);
2038 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2039 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2040 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2043 int compare(size_type pos1, size_type n1,
2044 const basic_fbstring& str,
2045 size_type pos2, size_type n2) const {
2046 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2047 return compare(pos1, n1, str.data() + pos2,
2048 std::min(n2, str.size() - pos2));
2051 // Code from Jean-Francois Bastien (03/26/2007)
2052 int compare(const value_type* s) const {
2053 // Could forward to compare(0, size(), s, traits_type::length(s))
2054 // but that does two extra checks
2055 const size_type n1(size()), n2(traits_type::length(s));
2056 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2057 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2065 // non-member functions
2067 template <typename E, class T, class A, class S>
2069 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2070 const basic_fbstring<E, T, A, S>& rhs) {
2072 basic_fbstring<E, T, A, S> result;
2073 result.reserve(lhs.size() + rhs.size());
2074 result.append(lhs).append(rhs);
2075 return std::move(result);
2079 template <typename E, class T, class A, class S>
2081 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2082 const basic_fbstring<E, T, A, S>& rhs) {
2083 return std::move(lhs.append(rhs));
2087 template <typename E, class T, class A, class S>
2089 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2090 basic_fbstring<E, T, A, S>&& rhs) {
2091 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2092 // Good, at least we don't need to reallocate
2093 return std::move(rhs.insert(0, lhs));
2095 // Meh, no go. Forward to operator+(const&, const&).
2096 auto const& rhsC = rhs;
2101 template <typename E, class T, class A, class S>
2103 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2104 basic_fbstring<E, T, A, S>&& rhs) {
2105 return std::move(lhs.append(rhs));
2108 template <typename E, class T, class A, class S>
2110 basic_fbstring<E, T, A, S> operator+(
2111 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2112 const basic_fbstring<E, T, A, S>& rhs) {
2114 basic_fbstring<E, T, A, S> result;
2115 const typename basic_fbstring<E, T, A, S>::size_type len =
2116 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2117 result.reserve(len + rhs.size());
2118 result.append(lhs, len).append(rhs);
2122 template <typename E, class T, class A, class S>
2124 basic_fbstring<E, T, A, S> operator+(
2125 typename basic_fbstring<E, T, A, S>::value_type lhs,
2126 const basic_fbstring<E, T, A, S>& rhs) {
2128 basic_fbstring<E, T, A, S> result;
2129 result.reserve(1 + rhs.size());
2130 result.push_back(lhs);
2135 template <typename E, class T, class A, class S>
2137 basic_fbstring<E, T, A, S> operator+(
2138 const basic_fbstring<E, T, A, S>& lhs,
2139 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2141 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2142 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2144 basic_fbstring<E, T, A, S> result;
2145 const size_type len = traits_type::length(rhs);
2146 result.reserve(lhs.size() + len);
2147 result.append(lhs).append(rhs, len);
2151 template <typename E, class T, class A, class S>
2153 basic_fbstring<E, T, A, S> operator+(
2154 const basic_fbstring<E, T, A, S>& lhs,
2155 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2157 basic_fbstring<E, T, A, S> result;
2158 result.reserve(lhs.size() + 1);
2160 result.push_back(rhs);
2164 template <typename E, class T, class A, class S>
2166 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2167 const basic_fbstring<E, T, A, S>& rhs) {
2168 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2170 template <typename E, class T, class A, class S>
2172 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2173 const basic_fbstring<E, T, A, S>& rhs) {
2174 return rhs == lhs; }
2176 template <typename E, class T, class A, class S>
2178 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2179 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2180 return lhs.compare(rhs) == 0; }
2182 template <typename E, class T, class A, class S>
2184 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2185 const basic_fbstring<E, T, A, S>& rhs) {
2186 return !(lhs == rhs); }
2188 template <typename E, class T, class A, class S>
2190 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2191 const basic_fbstring<E, T, A, S>& rhs) {
2192 return !(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 typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2198 return !(lhs == rhs); }
2200 template <typename E, class T, class A, class S>
2202 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2203 const basic_fbstring<E, T, A, S>& rhs) {
2204 return lhs.compare(rhs) < 0; }
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 typename basic_fbstring<E, T, A, S>::value_type* lhs,
2215 const basic_fbstring<E, T, A, S>& rhs) {
2216 return rhs.compare(lhs) > 0; }
2218 template <typename E, class T, class A, class S>
2220 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2221 const basic_fbstring<E, T, A, S>& 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) {
2230 template <typename E, class T, class A, class S>
2232 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2233 const basic_fbstring<E, T, A, S>& rhs) {
2236 template <typename E, class T, class A, class S>
2238 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2239 const basic_fbstring<E, T, A, S>& rhs) {
2240 return !(rhs < lhs); }
2242 template <typename E, class T, class A, class S>
2244 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2245 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2246 return !(rhs < lhs); }
2248 template <typename E, class T, class A, class S>
2250 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2251 const basic_fbstring<E, T, A, S>& rhs) {
2252 return !(rhs < lhs); }
2254 template <typename E, class T, class A, class S>
2256 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2257 const basic_fbstring<E, T, A, S>& rhs) {
2258 return !(lhs < rhs); }
2260 template <typename E, class T, class A, class S>
2262 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2263 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2264 return !(lhs < rhs); }
2266 template <typename E, class T, class A, class S>
2268 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2269 const basic_fbstring<E, T, A, S>& rhs) {
2270 return !(lhs < rhs);
2274 template <typename E, class T, class A, class S>
2275 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2279 // TODO: make this faster.
2280 template <typename E, class T, class A, class S>
2283 typename basic_fbstring<E, T, A, S>::value_type,
2284 typename basic_fbstring<E, T, A, S>::traits_type>&
2286 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2287 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2288 basic_fbstring<E, T, A, S>& str) {
2289 typename std::basic_istream<E, T>::sentry sentry(is);
2290 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2291 typename basic_fbstring<E, T, A, S>::traits_type>
2293 typedef typename __istream_type::ios_base __ios_base;
2294 size_t extracted = 0;
2295 auto err = __ios_base::goodbit;
2297 auto n = is.width();
2302 auto got = is.rdbuf()->sgetc();
2303 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2304 // Whew. We get to store this guy
2306 got = is.rdbuf()->snextc();
2308 if (got == T::eof()) {
2309 err |= __ios_base::eofbit;
2314 err |= __ios_base::failbit;
2322 template <typename E, class T, class A, class S>
2324 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2325 typename basic_fbstring<E, T, A, S>::traits_type>&
2327 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2328 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2329 const basic_fbstring<E, T, A, S>& str) {
2331 typename std::basic_ostream<
2332 typename basic_fbstring<E, T, A, S>::value_type,
2333 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2335 typedef std::ostreambuf_iterator<
2336 typename basic_fbstring<E, T, A, S>::value_type,
2337 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2338 size_t __len = str.size();
2340 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2341 if (__pad_and_output(_Ip(os),
2343 __left ? str.data() + __len : str.data(),
2346 os.fill()).failed()) {
2347 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2351 std::__ostream_insert(os, str.data(), str.size());
2356 #ifndef _LIBSTDCXX_FBSTRING
2358 template <typename E, class T, class A, class S>
2360 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2361 typename basic_fbstring<E, T, A, S>::traits_type>&
2363 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2364 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2365 basic_fbstring<E, T, A, S>& str,
2366 typename basic_fbstring<E, T, A, S>::value_type delim) {
2367 // Use the nonstandard getdelim()
2368 char * buf = nullptr;
2371 // This looks quadratic but it really depends on realloc
2372 auto const newSize = size + 128;
2373 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2374 is.getline(buf + size, newSize - size, delim);
2375 if (is.bad() || is.eof() || !is.fail()) {
2376 // done by either failure, end of file, or normal read
2377 size += std::strlen(buf + size);
2380 // Here we have failed due to too short a buffer
2381 // Minus one to discount the terminating '\0'
2383 assert(buf[size] == 0);
2384 // Clear the error so we can continue reading
2387 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2388 AcquireMallocatedString());
2393 template <typename E, class T, class A, class S>
2395 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2396 typename basic_fbstring<E, T, A, S>::traits_type>&
2398 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2399 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2400 basic_fbstring<E, T, A, S>& str) {
2401 // Just forward to the version with a delimiter
2402 return getline(is, str, '\n');
2407 template <typename E1, class T, class A, class S>
2408 const typename basic_fbstring<E1, T, A, S>::size_type
2409 basic_fbstring<E1, T, A, S>::npos =
2410 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2412 #ifndef _LIBSTDCXX_FBSTRING
2413 // basic_string compatibility routines
2415 template <typename E, class T, class A, class S>
2417 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2418 const std::string& rhs) {
2419 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2422 template <typename E, class T, class A, class S>
2424 bool operator==(const std::string& lhs,
2425 const basic_fbstring<E, T, A, S>& rhs) {
2429 template <typename E, class T, class A, class S>
2431 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2432 const std::string& rhs) {
2433 return !(lhs == rhs);
2436 template <typename E, class T, class A, class S>
2438 bool operator!=(const std::string& lhs,
2439 const basic_fbstring<E, T, A, S>& rhs) {
2440 return !(lhs == rhs);
2443 #if !defined(_LIBSTDCXX_FBSTRING)
2444 typedef basic_fbstring<char> fbstring;
2447 // fbstring is relocatable
2448 template <class T, class R, class A, class S>
2449 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2452 _GLIBCXX_END_NAMESPACE_VERSION
2455 } // namespace folly
2457 #ifndef _LIBSTDCXX_FBSTRING
2459 // Hash functions to make fbstring usable with e.g. hash_map
2461 // Handle interaction with different C++ standard libraries, which
2462 // expect these types to be in different namespaces.
2466 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2467 size_t operator()(const folly::basic_fbstring<C> & s) const {
2468 return hash<const C*>::operator()(s.c_str());
2473 struct hash< ::folly::fbstring> {
2474 size_t operator()(const ::folly::fbstring& s) const {
2475 return ::folly::hash::fnv32_buf(s.data(), s.size());
2481 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2482 namespace __gnu_cxx {
2485 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2486 size_t operator()(const folly::basic_fbstring<C> & s) const {
2487 return hash<const C*>::operator()(s.c_str());
2492 struct hash< ::folly::fbstring> {
2493 size_t operator()(const ::folly::fbstring& s) const {
2494 return ::folly::hash::fnv32_buf(s.data(), s.size());
2499 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2500 #endif // _LIBSTDCXX_FBSTRING
2502 #pragma GCC diagnostic pop
2504 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2506 #undef FBSTRING_LIKELY
2507 #undef FBSTRING_UNLIKELY
2509 #endif // FOLLY_BASE_FBSTRING_H_