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 #include "folly/Portability.h"
68 // libc++ doesn't provide this header, nor does msvc
69 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
70 // This file appears in two locations: inside fbcode and in the
71 // libstdc++ source code (when embedding fbstring as std::string).
72 // To aid in this schizophrenic use, two macros are defined in
74 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
75 // gate use inside fbcode v. libstdc++
76 #include <bits/c++config.h>
79 #ifdef _LIBSTDCXX_FBSTRING
81 #pragma GCC system_header
83 // Handle the cases where the fbcode version (folly/Malloc.h) is included
84 // either before or after this inclusion.
85 #ifdef FOLLY_MALLOC_H_
86 #undef FOLLY_MALLOC_H_
87 #include "basic_fbstring_malloc.h"
89 #include "basic_fbstring_malloc.h"
90 #undef FOLLY_MALLOC_H_
93 #else // !_LIBSTDCXX_FBSTRING
99 #include "folly/Traits.h"
100 #include "folly/Malloc.h"
101 #include "folly/Hash.h"
103 #if FOLLY_HAVE_DEPRECATED_ASSOC
104 #ifdef _GLIBCXX_SYMVER
105 #include <ext/hash_set>
106 #include <ext/hash_map>
112 // We defined these here rather than including Likely.h to avoid
113 // redefinition errors when fbstring is imported into libstdc++.
114 #if defined(__GNUC__) && __GNUC__ >= 4
115 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
116 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
118 #define FBSTRING_LIKELY(x) (x)
119 #define FBSTRING_UNLIKELY(x) (x)
122 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
123 #pragma GCC diagnostic push
124 #pragma GCC diagnostic ignored "-Wshadow"
126 // FBString cannot use throw when replacing std::string, though it may still
127 // use std::__throw_*
128 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
130 #ifdef _LIBSTDCXX_FBSTRING
131 namespace std _GLIBCXX_VISIBILITY(default) {
132 _GLIBCXX_BEGIN_NAMESPACE_VERSION
137 // Different versions of gcc/clang support different versions of
138 // the address sanitizer attribute. Unfortunately, this attribute
139 // has issues when inlining is used, so disable that as well.
140 #if defined(__clang__)
141 # if __has_feature(address_sanitizer)
142 # if __has_attribute(__no_address_safety_analysis__)
143 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
144 __attribute__((__no_address_safety_analysis__, __noinline__))
145 # elif __has_attribute(__no_sanitize_address__)
146 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
147 __attribute__((__no_sanitize_address__, __noinline__))
150 #elif defined (__GNUC__) && \
152 (__GNUC_MINOR__ >= 8) && \
154 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
155 __attribute__((__no_address_safety_analysis__, __noinline__))
157 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
158 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
161 namespace fbstring_detail {
163 template <class InIt, class OutIt>
166 typename std::iterator_traits<InIt>::difference_type n,
168 for (; n != 0; --n, ++b, ++d) {
174 template <class Pod, class T>
175 inline void pod_fill(Pod* b, Pod* e, T c) {
176 assert(b && e && b <= e);
177 /*static*/ if (sizeof(T) == 1) {
180 auto const ee = b + ((e - b) & ~7u);
181 for (; b != ee; b += 8) {
192 for (; b != e; ++b) {
199 * Lightly structured memcpy, simplifies copying PODs and introduces
200 * some asserts. Unfortunately using this function may cause
201 * measurable overhead (presumably because it adjusts from a begin/end
202 * convention to a pointer/size convention, so it does some extra
203 * arithmetic even though the caller might have done the inverse
204 * adaptation outside).
207 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
209 assert(d >= e || d + (e - b) <= b);
210 memcpy(d, b, (e - b) * sizeof(Pod));
214 * Lightly structured memmove, simplifies copying PODs and introduces
218 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
220 memmove(d, b, (e - b) * sizeof(*b));
223 } // namespace fbstring_detail
226 * Defines a special acquisition method for constructing fbstring
227 * objects. AcquireMallocatedString means that the user passes a
228 * pointer to a malloc-allocated string that the fbstring object will
231 enum class AcquireMallocatedString {};
234 * fbstring_core_model is a mock-up type that defines all required
235 * signatures of a fbstring core. The fbstring class itself uses such
236 * a core object to implement all of the numerous member functions
237 * required by the standard.
239 * If you want to define a new core, copy the definition below and
240 * implement the primitives. Then plug the core into basic_fbstring as
241 * a template argument.
243 template <class Char>
244 class fbstring_core_model {
246 fbstring_core_model();
247 fbstring_core_model(const fbstring_core_model &);
248 ~fbstring_core_model();
249 // Returns a pointer to string's buffer (currently only contiguous
250 // strings are supported). The pointer is guaranteed to be valid
251 // until the next call to a non-const member function.
252 const Char * data() const;
253 // Much like data(), except the string is prepared to support
254 // character-level changes. This call is a signal for
255 // e.g. reference-counted implementation to fork the data. The
256 // pointer is guaranteed to be valid until the next call to a
257 // non-const member function.
258 Char * mutable_data();
259 // Returns a pointer to string's buffer and guarantees that a
260 // readable '\0' lies right after the buffer. The pointer is
261 // guaranteed to be valid until the next call to a non-const member
263 const Char * c_str() const;
264 // Shrinks the string by delta characters. Asserts that delta <=
266 void shrink(size_t delta);
267 // Expands the string by delta characters (i.e. after this call
268 // size() will report the old size() plus delta) but without
269 // initializing the expanded region. Returns a pointer to the memory
270 // to be initialized (the beginning of the expanded portion). The
271 // caller is expected to fill the expanded area appropriately.
272 Char* expand_noinit(size_t delta);
273 // Expands the string by one character and sets the last character
275 void push_back(Char c);
276 // Returns the string's size.
278 // Returns the string's capacity, i.e. maximum size that the string
279 // can grow to without reallocation. Note that for reference counted
280 // strings that's technically a lie - even assigning characters
281 // within the existing size would cause a reallocation.
282 size_t capacity() const;
283 // Returns true if the data underlying the string is actually shared
284 // across multiple strings (in a refcounted fashion).
285 bool isShared() const;
286 // Makes sure that at least minCapacity characters are available for
287 // the string without reallocation. For reference-counted strings,
288 // it should fork the data even if minCapacity < size().
289 void reserve(size_t minCapacity);
292 fbstring_core_model& operator=(const fbstring_core_model &);
297 * gcc-4.7 throws what appears to be some false positive uninitialized
298 * warnings for the members of the MediumLarge struct. So, mute them here.
300 #if defined(__GNUC__) && !defined(__clang__)
301 # pragma GCC diagnostic push
302 # pragma GCC diagnostic ignored "-Wuninitialized"
306 * This is the core of the string. The code should work on 32- and
307 * 64-bit architectures and with any Char size. Porting to big endian
308 * architectures would require some changes.
310 * The storage is selected as follows (assuming we store one-byte
311 * characters on a 64-bit machine): (a) "small" strings between 0 and
312 * 23 chars are stored in-situ without allocation (the rightmost byte
313 * stores the size); (b) "medium" strings from 24 through 254 chars
314 * are stored in malloc-allocated memory that is copied eagerly; (c)
315 * "large" strings of 255 chars and above are stored in a similar
316 * structure as medium arrays, except that the string is
317 * reference-counted and copied lazily. the reference count is
318 * allocated right before the character array.
320 * The discriminator between these three strategies sits in the two
321 * most significant bits of the rightmost char of the storage. If
322 * neither is set, then the string is small (and its length sits in
323 * the lower-order bits of that rightmost character). If the MSb is
324 * set, the string is medium width. If the second MSb is set, then the
327 template <class Char> class fbstring_core {
329 fbstring_core() noexcept {
330 // Only initialize the tag, will set the MSBs (i.e. the small
331 // string size) to zero too
332 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
333 // or: setSmallSize(0);
335 assert(category() == isSmall && size() == 0);
338 fbstring_core(const fbstring_core & rhs) {
339 assert(&rhs != this);
340 // Simplest case first: small strings are bitblitted
341 if (rhs.category() == isSmall) {
342 assert(offsetof(MediumLarge, data_) == 0);
343 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
344 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
345 const size_t size = rhs.smallSize();
347 ml_.capacity_ = rhs.ml_.capacity_;
350 // Just write the whole thing, don't look at details. In
351 // particular we need to copy capacity anyway because we want
352 // to set the size (don't forget that the last character,
353 // which stores a short string's length, is shared with the
354 // ml_.capacity field).
357 assert(category() == isSmall && this->size() == rhs.size());
358 } else if (rhs.category() == isLarge) {
359 // Large strings are just refcounted
361 RefCounted::incrementRefs(ml_.data_);
362 assert(category() == isLarge && size() == rhs.size());
364 // Medium strings are copied eagerly. Don't forget to allocate
365 // one extra Char for the null terminator.
366 auto const allocSize =
367 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
368 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
369 fbstring_detail::pod_copy(rhs.ml_.data_,
371 rhs.ml_.data_ + rhs.ml_.size_ + 1,
373 // No need for writeTerminator() here, we copied one extra
374 // element just above.
375 ml_.size_ = rhs.ml_.size_;
376 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
377 assert(category() == isMedium);
379 assert(size() == rhs.size());
380 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
383 fbstring_core(fbstring_core&& goner) noexcept {
384 if (goner.category() == isSmall) {
385 // Just copy, leave the goner in peace
386 new(this) fbstring_core(goner.small_, goner.smallSize());
390 // Clean goner's carcass
391 goner.setSmallSize(0);
395 // NOTE(agallagher): The word-aligned copy path copies bytes which are
396 // outside the range of the string, and makes address sanitizer unhappy,
397 // so just disable it on this function.
398 fbstring_core(const Char *const data, const size_t size)
399 FBSTRING_DISABLE_ADDRESS_SANITIZER {
400 // Simplest case first: small strings are bitblitted
401 if (size <= maxSmallSize) {
402 // Layout is: Char* data_, size_t size_, size_t capacity_
403 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
404 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
405 // sizeof(size_t) must be a power of 2
406 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
408 // If data is aligned, use fast word-wise copying. Otherwise,
409 // use conservative memcpy.
410 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
411 fbstring_detail::pod_copy(data, data + size, small_);
413 // Copy one word (64 bits) at a time
414 const size_t byteSize = size * sizeof(Char);
415 if (byteSize > 2 * sizeof(size_t)) {
417 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
419 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
421 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
422 } else if (byteSize > sizeof(size_t)) {
425 } else if (size > 0) {
431 } else if (size <= maxMediumSize) {
432 // Medium strings are allocated normally. Don't forget to
433 // allocate one extra Char for the terminating null.
434 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
435 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
436 fbstring_detail::pod_copy(data, data + size, ml_.data_);
438 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
440 // Large strings are allocated differently
441 size_t effectiveCapacity = size;
442 auto const newRC = RefCounted::create(data, & effectiveCapacity);
443 ml_.data_ = newRC->data_;
445 ml_.capacity_ = effectiveCapacity | isLarge;
448 assert(this->size() == size);
449 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
452 ~fbstring_core() noexcept {
453 auto const c = category();
461 RefCounted::decrementRefs(ml_.data_);
464 // Snatches a previously mallocated string. The parameter "size"
465 // is the size of the string, and the parameter "allocatedSize"
466 // is the size of the mallocated block. The string must be
467 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
469 // So if you want a 2-character string, pass malloc(3) as "data",
470 // pass 2 as "size", and pass 3 as "allocatedSize".
471 fbstring_core(Char * const data,
473 const size_t allocatedSize,
474 AcquireMallocatedString) {
476 assert(allocatedSize >= size + 1);
477 assert(data[size] == '\0');
478 // Use the medium string storage
481 // Don't forget about null terminator
482 ml_.capacity_ = (allocatedSize - 1) | isMedium;
484 // No need for the memory
490 // swap below doesn't test whether &rhs == this (and instead
491 // potentially does extra work) on the premise that the rarity of
492 // that situation actually makes the check more expensive than is
494 void swap(fbstring_core & rhs) {
500 // In C++11 data() and c_str() are 100% equivalent.
501 const Char * data() const {
505 Char * mutable_data() {
506 auto const c = category();
510 assert(c == isMedium || c == isLarge);
511 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
513 size_t effectiveCapacity = ml_.capacity();
514 auto const newRC = RefCounted::create(& effectiveCapacity);
515 // If this fails, someone placed the wrong capacity in an
517 assert(effectiveCapacity >= ml_.capacity());
518 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
520 RefCounted::decrementRefs(ml_.data_);
521 ml_.data_ = newRC->data_;
522 // No need to call writeTerminator(), we have + 1 above.
527 const Char * c_str() const {
528 auto const c = category();
529 #ifdef FBSTRING_PERVERSE
531 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
532 || small_[smallSize()] == '\0');
533 if (small_[smallSize()] != '\0') {
534 small_[smallSize()] = '\0';
538 assert(c == isMedium || c == isLarge);
539 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
540 if (ml_.data_[ml_.size_] != '\0') {
541 ml_.data_[ml_.size_] = '\0';
543 #elif defined(FBSTRING_CONSERVATIVE)
545 assert(small_[smallSize()] == '\0');
548 assert(c == isMedium || c == isLarge);
549 assert(ml_.data_[ml_.size_] == '\0');
552 if (small_[smallSize()] != '\0') {
553 small_[smallSize()] = '\0';
557 assert(c == isMedium || c == isLarge);
558 if (ml_.data_[ml_.size_] != '\0') {
559 ml_.data_[ml_.size_] = '\0';
565 void shrink(const size_t delta) {
566 if (category() == isSmall) {
567 // Check for underflow
568 assert(delta <= smallSize());
569 setSmallSize(smallSize() - delta);
570 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
571 // Medium strings and unique large strings need no special
573 assert(ml_.size_ >= delta);
576 assert(ml_.size_ >= delta);
577 // Shared large string, must make unique. This is because of the
578 // durn terminator must be written, which may trample the shared
581 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
583 // No need to write the terminator.
589 void reserve(size_t minCapacity) {
590 if (category() == isLarge) {
592 if (RefCounted::refs(ml_.data_) > 1) {
593 // We must make it unique regardless; in-place reallocation is
594 // useless if the string is shared. In order to not surprise
595 // people, reserve the new block at current capacity or
596 // more. That way, a string's capacity never shrinks after a
598 minCapacity = std::max(minCapacity, ml_.capacity());
599 auto const newRC = RefCounted::create(& minCapacity);
600 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
602 // Done with the old data. No need to call writeTerminator(),
603 // we have + 1 above.
604 RefCounted::decrementRefs(ml_.data_);
605 ml_.data_ = newRC->data_;
606 ml_.capacity_ = minCapacity | isLarge;
607 // size remains unchanged
609 // String is not shared, so let's try to realloc (if needed)
610 if (minCapacity > ml_.capacity()) {
611 // Asking for more memory
613 RefCounted::reallocate(ml_.data_, ml_.size_,
614 ml_.capacity(), minCapacity);
615 ml_.data_ = newRC->data_;
616 ml_.capacity_ = minCapacity | isLarge;
619 assert(capacity() >= minCapacity);
621 } else if (category() == isMedium) {
622 // String is not shared
623 if (minCapacity <= ml_.capacity()) {
624 return; // nothing to do, there's enough room
626 if (minCapacity <= maxMediumSize) {
627 // Keep the string at medium size. Don't forget to allocate
628 // one extra Char for the terminating null.
629 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
630 ml_.data_ = static_cast<Char *>(
633 ml_.size_ * sizeof(Char),
634 (ml_.capacity() + 1) * sizeof(Char),
637 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
639 // Conversion from medium to large string
640 fbstring_core nascent;
641 // Will recurse to another branch of this function
642 nascent.reserve(minCapacity);
643 nascent.ml_.size_ = ml_.size_;
644 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
648 assert(capacity() >= minCapacity);
651 assert(category() == isSmall);
652 if (minCapacity > maxMediumSize) {
654 auto const newRC = RefCounted::create(& minCapacity);
655 auto const size = smallSize();
656 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
657 // No need for writeTerminator(), we wrote it above with + 1.
658 ml_.data_ = newRC->data_;
660 ml_.capacity_ = minCapacity | isLarge;
661 assert(capacity() >= minCapacity);
662 } else if (minCapacity > maxSmallSize) {
664 // Don't forget to allocate one extra Char for the terminating null
665 auto const allocSizeBytes =
666 goodMallocSize((1 + minCapacity) * sizeof(Char));
667 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
668 auto const size = smallSize();
669 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
670 // No need for writeTerminator(), we wrote it above with + 1.
673 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
676 // Nothing to do, everything stays put
679 assert(capacity() >= minCapacity);
682 Char * expand_noinit(const size_t delta) {
683 // Strategy is simple: make room, then change size
684 assert(capacity() >= size());
686 if (category() == isSmall) {
689 if (newSz <= maxSmallSize) {
697 newSz = ml_.size_ + delta;
698 if (newSz > capacity()) {
702 assert(capacity() >= newSz);
703 // Category can't be small - we took care of that above
704 assert(category() == isMedium || category() == isLarge);
707 assert(size() == newSz);
708 return ml_.data_ + sz;
711 void push_back(Char c) {
712 assert(capacity() >= size());
714 if (category() == isSmall) {
716 if (sz < maxSmallSize) {
717 setSmallSize(sz + 1);
722 reserve(maxSmallSize * 2);
725 if (sz == capacity()) { // always true for isShared()
726 reserve(1 + sz * 3 / 2); // ensures not shared
730 assert(capacity() >= sz + 1);
731 // Category can't be small - we took care of that above
732 assert(category() == isMedium || category() == isLarge);
738 size_t size() const {
739 return category() == isSmall ? smallSize() : ml_.size_;
742 size_t capacity() const {
743 switch (category()) {
747 // For large-sized strings, a multi-referenced chunk has no
748 // available capacity. This is because any attempt to append
749 // data would trigger a new allocation.
750 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
753 return ml_.capacity();
756 bool isShared() const {
757 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
760 #ifdef FBSTRING_PERVERSE
761 enum { TERMINATOR = '^' };
763 enum { TERMINATOR = '\0' };
766 void writeTerminator() {
767 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
768 if (category() == isSmall) {
769 const auto s = smallSize();
770 if (s != maxSmallSize) {
771 small_[s] = TERMINATOR;
774 ml_.data_[ml_.size_] = TERMINATOR;
781 fbstring_core & operator=(const fbstring_core & rhs);
788 size_t capacity() const {
789 return capacity_ & capacityExtractMask;
794 std::atomic<size_t> refCount_;
797 static RefCounted * fromData(Char * p) {
798 return static_cast<RefCounted*>(
800 static_cast<unsigned char*>(static_cast<void*>(p))
801 - sizeof(refCount_)));
804 static size_t refs(Char * p) {
805 return fromData(p)->refCount_.load(std::memory_order_acquire);
808 static void incrementRefs(Char * p) {
809 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
812 static void decrementRefs(Char * p) {
813 auto const dis = fromData(p);
814 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
821 static RefCounted * create(size_t * size) {
822 // Don't forget to allocate one extra Char for the terminating
823 // null. In this case, however, one Char is already part of the
825 const size_t allocSize = goodMallocSize(
826 sizeof(RefCounted) + *size * sizeof(Char));
827 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
828 result->refCount_.store(1, std::memory_order_release);
829 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
833 static RefCounted * create(const Char * data, size_t * size) {
834 const size_t effectiveSize = *size;
835 auto result = create(size);
836 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
840 static RefCounted * reallocate(Char *const data,
841 const size_t currentSize,
842 const size_t currentCapacity,
843 const size_t newCapacity) {
844 assert(newCapacity > 0 && newCapacity > currentSize);
845 auto const dis = fromData(data);
846 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
847 // Don't forget to allocate one extra Char for the terminating
848 // null. In this case, however, one Char is already part of the
850 auto result = static_cast<RefCounted*>(
852 sizeof(RefCounted) + currentSize * sizeof(Char),
853 sizeof(RefCounted) + currentCapacity * sizeof(Char),
854 sizeof(RefCounted) + newCapacity * sizeof(Char)));
855 assert(result->refCount_.load(std::memory_order_acquire) == 1);
861 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
862 mutable MediumLarge ml_;
866 lastChar = sizeof(MediumLarge) - 1,
867 maxSmallSize = lastChar / sizeof(Char),
868 maxMediumSize = 254 / sizeof(Char), // coincides with the small
869 // bin size in dlmalloc
870 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
871 capacityExtractMask = ~categoryExtractMask,
873 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
874 "Corrupt memory layout for fbstring.");
878 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
879 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
882 Category category() const {
883 // Assumes little endian
884 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
887 size_t smallSize() const {
888 assert(category() == isSmall &&
889 static_cast<size_t>(small_[maxSmallSize])
890 <= static_cast<size_t>(maxSmallSize));
891 return static_cast<size_t>(maxSmallSize)
892 - static_cast<size_t>(small_[maxSmallSize]);
895 void setSmallSize(size_t s) {
896 // Warning: this should work with uninitialized strings too,
897 // so don't assume anything about the previous value of
898 // small_[maxSmallSize].
899 assert(s <= maxSmallSize);
900 small_[maxSmallSize] = maxSmallSize - s;
904 #if defined(__GNUC__) && !defined(__clang__)
905 # pragma GCC diagnostic pop
908 #ifndef _LIBSTDCXX_FBSTRING
910 * Dummy fbstring core that uses an actual std::string. This doesn't
911 * make any sense - it's just for testing purposes.
913 template <class Char>
914 class dummy_fbstring_core {
916 dummy_fbstring_core() {
918 dummy_fbstring_core(const dummy_fbstring_core& another)
919 : backend_(another.backend_) {
921 dummy_fbstring_core(const Char * s, size_t n)
924 void swap(dummy_fbstring_core & rhs) {
925 backend_.swap(rhs.backend_);
927 const Char * data() const {
928 return backend_.data();
930 Char * mutable_data() {
931 //assert(!backend_.empty());
932 return &*backend_.begin();
934 void shrink(size_t delta) {
935 assert(delta <= size());
936 backend_.resize(size() - delta);
938 Char * expand_noinit(size_t delta) {
939 auto const sz = size();
940 backend_.resize(size() + delta);
941 return backend_.data() + sz;
943 void push_back(Char c) {
944 backend_.push_back(c);
946 size_t size() const {
947 return backend_.size();
949 size_t capacity() const {
950 return backend_.capacity();
952 bool isShared() const {
955 void reserve(size_t minCapacity) {
956 backend_.reserve(minCapacity);
960 std::basic_string<Char> backend_;
962 #endif // !_LIBSTDCXX_FBSTRING
965 * This is the basic_string replacement. For conformity,
966 * basic_fbstring takes the same template parameters, plus the last
967 * one which is the core.
969 #ifdef _LIBSTDCXX_FBSTRING
970 template <typename E, class T, class A, class Storage>
972 template <typename E,
973 class T = std::char_traits<E>,
974 class A = std::allocator<E>,
975 class Storage = fbstring_core<E> >
977 class basic_fbstring {
981 void (*throw_exc)(const char*),
983 if (!condition) throw_exc(msg);
986 bool isSane() const {
989 empty() == (size() == 0) &&
990 empty() == (begin() == end()) &&
991 size() <= max_size() &&
992 capacity() <= max_size() &&
993 size() <= capacity() &&
994 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
998 friend struct Invariant;
1001 explicit Invariant(const basic_fbstring& s) : s_(s) {
1002 assert(s_.isSane());
1005 assert(s_.isSane());
1008 const basic_fbstring& s_;
1010 explicit Invariant(const basic_fbstring&) {}
1012 Invariant& operator=(const Invariant&);
1017 typedef T traits_type;
1018 typedef typename traits_type::char_type value_type;
1019 typedef A allocator_type;
1020 typedef typename A::size_type size_type;
1021 typedef typename A::difference_type difference_type;
1023 typedef typename A::reference reference;
1024 typedef typename A::const_reference const_reference;
1025 typedef typename A::pointer pointer;
1026 typedef typename A::const_pointer const_pointer;
1028 typedef E* iterator;
1029 typedef const E* const_iterator;
1030 typedef std::reverse_iterator<iterator
1031 #ifdef NO_ITERATOR_TRAITS
1035 typedef std::reverse_iterator<const_iterator
1036 #ifdef NO_ITERATOR_TRAITS
1039 > const_reverse_iterator;
1041 static const size_type npos; // = size_type(-1)
1044 static void procrustes(size_type& n, size_type nmax) {
1045 if (n > nmax) n = nmax;
1049 // C++11 21.4.2 construct/copy/destroy
1050 explicit basic_fbstring(const A& a = A()) noexcept {
1053 basic_fbstring(const basic_fbstring& str)
1054 : store_(str.store_) {
1058 basic_fbstring(basic_fbstring&& goner) noexcept
1059 : store_(std::move(goner.store_)) {
1062 #ifndef _LIBSTDCXX_FBSTRING
1063 // This is defined for compatibility with std::string
1064 /* implicit */ basic_fbstring(const std::string& str)
1065 : store_(str.data(), str.size()) {
1069 basic_fbstring(const basic_fbstring& str, size_type pos,
1070 size_type n = npos, const A& a = A()) {
1071 assign(str, pos, n);
1074 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1076 ? traits_type::length(s)
1078 std::__throw_logic_error(
1079 "basic_fbstring: null pointer initializer not valid");
1084 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1088 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1089 auto const data = store_.expand_noinit(n);
1090 fbstring_detail::pod_fill(data, data + n, c);
1091 store_.writeTerminator();
1094 template <class InIt>
1095 basic_fbstring(InIt begin, InIt end,
1096 typename std::enable_if<
1097 !std::is_same<typename std::remove_const<InIt>::type,
1098 value_type*>::value, const A>::type & a = A()) {
1102 // Specialization for const char*, const char*
1103 basic_fbstring(const value_type* b, const value_type* e)
1104 : store_(b, e - b) {
1107 // Nonstandard constructor
1108 basic_fbstring(value_type *s, size_type n, size_type c,
1109 AcquireMallocatedString a)
1110 : store_(s, n, c, a) {
1113 // Construction from initialization list
1114 basic_fbstring(std::initializer_list<value_type> il) {
1115 assign(il.begin(), il.end());
1118 ~basic_fbstring() noexcept {
1121 basic_fbstring& operator=(const basic_fbstring& lhs) {
1122 if (FBSTRING_UNLIKELY(&lhs == this)) {
1125 auto const oldSize = size();
1126 auto const srcSize = lhs.size();
1127 if (capacity() >= srcSize && !store_.isShared()) {
1128 // great, just copy the contents
1129 if (oldSize < srcSize)
1130 store_.expand_noinit(srcSize - oldSize);
1132 store_.shrink(oldSize - srcSize);
1133 assert(size() == srcSize);
1134 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1135 store_.writeTerminator();
1137 // need to reallocate, so we may as well create a brand new string
1138 basic_fbstring(lhs).swap(*this);
1144 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1145 if (FBSTRING_UNLIKELY(&goner == this)) {
1146 // Compatibility with std::basic_string<>,
1147 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1150 // No need of this anymore
1151 this->~basic_fbstring();
1152 // Move the goner into this
1153 new(&store_) fbstring_core<E>(std::move(goner.store_));
1157 #ifndef _LIBSTDCXX_FBSTRING
1158 // Compatibility with std::string
1159 basic_fbstring & operator=(const std::string & rhs) {
1160 return assign(rhs.data(), rhs.size());
1163 // Compatibility with std::string
1164 std::string toStdString() const {
1165 return std::string(data(), size());
1168 // A lot of code in fbcode still uses this method, so keep it here for now.
1169 const basic_fbstring& toStdString() const {
1174 basic_fbstring& operator=(const value_type* s) {
1178 basic_fbstring& operator=(value_type c) {
1180 store_.expand_noinit(1);
1181 } else if (store_.isShared()) {
1182 basic_fbstring(1, c).swap(*this);
1185 store_.shrink(size() - 1);
1187 *store_.mutable_data() = c;
1188 store_.writeTerminator();
1192 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1193 return assign(il.begin(), il.end());
1196 // C++11 21.4.3 iterators:
1197 iterator begin() { return store_.mutable_data(); }
1199 const_iterator begin() const { return store_.data(); }
1201 const_iterator cbegin() const { return begin(); }
1204 return store_.mutable_data() + store_.size();
1207 const_iterator end() const {
1208 return store_.data() + store_.size();
1211 const_iterator cend() const { return end(); }
1213 reverse_iterator rbegin() {
1214 return reverse_iterator(end());
1217 const_reverse_iterator rbegin() const {
1218 return const_reverse_iterator(end());
1221 const_reverse_iterator crbegin() const { return rbegin(); }
1223 reverse_iterator rend() {
1224 return reverse_iterator(begin());
1227 const_reverse_iterator rend() const {
1228 return const_reverse_iterator(begin());
1231 const_reverse_iterator crend() const { return rend(); }
1234 // C++11 21.4.5, element access:
1235 const value_type& front() const { return *begin(); }
1236 const value_type& back() const {
1238 // Should be begin()[size() - 1], but that branches twice
1239 return *(end() - 1);
1241 value_type& front() { return *begin(); }
1242 value_type& back() {
1244 // Should be begin()[size() - 1], but that branches twice
1245 return *(end() - 1);
1252 // C++11 21.4.4 capacity:
1253 size_type size() const { return store_.size(); }
1255 size_type length() const { return size(); }
1257 size_type max_size() const {
1258 return std::numeric_limits<size_type>::max();
1261 void resize(const size_type n, const value_type c = value_type()) {
1262 auto size = this->size();
1264 store_.shrink(size - n);
1266 // Do this in two steps to minimize slack memory copied (see
1268 auto const capacity = this->capacity();
1269 assert(capacity >= size);
1270 if (size < capacity) {
1271 auto delta = std::min(n, capacity) - size;
1272 store_.expand_noinit(delta);
1273 fbstring_detail::pod_fill(begin() + size, end(), c);
1276 store_.writeTerminator();
1281 auto const delta = n - size;
1282 store_.expand_noinit(delta);
1283 fbstring_detail::pod_fill(end() - delta, end(), c);
1284 store_.writeTerminator();
1286 assert(this->size() == n);
1289 size_type capacity() const { return store_.capacity(); }
1291 void reserve(size_type res_arg = 0) {
1292 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1293 store_.reserve(res_arg);
1296 void shrink_to_fit() {
1297 // Shrink only if slack memory is sufficiently large
1298 if (capacity() < size() * 3 / 2) {
1301 basic_fbstring(cbegin(), cend()).swap(*this);
1304 void clear() { resize(0); }
1306 bool empty() const { return size() == 0; }
1308 // C++11 21.4.5 element access:
1309 const_reference operator[](size_type pos) const {
1310 return *(c_str() + pos);
1313 reference operator[](size_type pos) {
1314 if (pos == size()) {
1315 // Just call c_str() to make sure '\0' is present
1318 return *(begin() + pos);
1321 const_reference at(size_type n) const {
1322 enforce(n <= size(), std::__throw_out_of_range, "");
1326 reference at(size_type n) {
1327 enforce(n < size(), std::__throw_out_of_range, "");
1331 // C++11 21.4.6 modifiers:
1332 basic_fbstring& operator+=(const basic_fbstring& str) {
1336 basic_fbstring& operator+=(const value_type* s) {
1340 basic_fbstring& operator+=(const value_type c) {
1345 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1350 basic_fbstring& append(const basic_fbstring& str) {
1352 auto desiredSize = size() + str.size();
1354 append(str.data(), str.size());
1355 assert(size() == desiredSize);
1359 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1361 const size_type sz = str.size();
1362 enforce(pos <= sz, std::__throw_out_of_range, "");
1363 procrustes(n, sz - pos);
1364 return append(str.data() + pos, n);
1367 basic_fbstring& append(const value_type* s, size_type n) {
1369 Invariant checker(*this);
1372 if (FBSTRING_UNLIKELY(!n)) {
1373 // Unlikely but must be done
1376 auto const oldSize = size();
1377 auto const oldData = data();
1378 // Check for aliasing (rare). We could use "<=" here but in theory
1379 // those do not work for pointers unless the pointers point to
1380 // elements in the same array. For that reason we use
1381 // std::less_equal, which is guaranteed to offer a total order
1382 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1384 std::less_equal<const value_type*> le;
1385 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1386 assert(le(s + n, oldData + oldSize));
1387 const size_type offset = s - oldData;
1388 store_.reserve(oldSize + n);
1389 // Restore the source
1390 s = data() + offset;
1392 // Warning! Repeated appends with short strings may actually incur
1393 // practically quadratic performance. Avoid that by pushing back
1394 // the first character (which ensures exponential growth) and then
1395 // appending the rest normally. Worst case the append may incur a
1396 // second allocation but that will be rare.
1399 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1400 assert(size() == oldSize + n + 1);
1404 basic_fbstring& append(const value_type* s) {
1405 return append(s, traits_type::length(s));
1408 basic_fbstring& append(size_type n, value_type c) {
1409 resize(size() + n, c);
1413 template<class InputIterator>
1414 basic_fbstring& append(InputIterator first, InputIterator last) {
1415 insert(end(), first, last);
1419 basic_fbstring& append(std::initializer_list<value_type> il) {
1420 return append(il.begin(), il.end());
1423 void push_back(const value_type c) { // primitive
1424 store_.push_back(c);
1427 basic_fbstring& assign(const basic_fbstring& str) {
1428 if (&str == this) return *this;
1429 return assign(str.data(), str.size());
1432 basic_fbstring& assign(basic_fbstring&& str) {
1433 return *this = std::move(str);
1436 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1438 const size_type sz = str.size();
1439 enforce(pos <= sz, std::__throw_out_of_range, "");
1440 procrustes(n, sz - pos);
1441 return assign(str.data() + pos, n);
1444 basic_fbstring& assign(const value_type* s, const size_type n) {
1445 Invariant checker(*this);
1448 std::copy(s, s + n, begin());
1450 assert(size() == n);
1452 const value_type *const s2 = s + size();
1453 std::copy(s, s2, begin());
1454 append(s2, n - size());
1455 assert(size() == n);
1457 store_.writeTerminator();
1458 assert(size() == n);
1462 basic_fbstring& assign(const value_type* s) {
1463 return assign(s, traits_type::length(s));
1466 basic_fbstring& assign(std::initializer_list<value_type> il) {
1467 return assign(il.begin(), il.end());
1470 template <class ItOrLength, class ItOrChar>
1471 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1472 return replace(begin(), end(), first_or_n, last_or_c);
1475 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1476 return insert(pos1, str.data(), str.size());
1479 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1480 size_type pos2, size_type n) {
1481 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1482 procrustes(n, str.length() - pos2);
1483 return insert(pos1, str.data() + pos2, n);
1486 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1487 enforce(pos <= length(), std::__throw_out_of_range, "");
1488 insert(begin() + pos, s, s + n);
1492 basic_fbstring& insert(size_type pos, const value_type* s) {
1493 return insert(pos, s, traits_type::length(s));
1496 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1497 enforce(pos <= length(), std::__throw_out_of_range, "");
1498 insert(begin() + pos, n, c);
1502 iterator insert(const_iterator p, const value_type c) {
1503 const size_type pos = p - begin();
1505 return begin() + pos;
1509 template <int i> class Selector {};
1511 iterator insertImplDiscr(const_iterator p,
1512 size_type n, value_type c, Selector<1>) {
1513 Invariant checker(*this);
1515 auto const pos = p - begin();
1516 assert(p >= begin() && p <= end());
1517 if (capacity() - size() < n) {
1518 const size_type sz = p - begin();
1519 reserve(size() + n);
1522 const iterator oldEnd = end();
1523 if (n < size_type(oldEnd - p)) {
1524 append(oldEnd - n, oldEnd);
1526 // reverse_iterator(oldEnd - n),
1527 // reverse_iterator(p),
1528 // reverse_iterator(oldEnd));
1529 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1531 std::fill(begin() + pos, begin() + pos + n, c);
1533 append(n - (end() - p), c);
1534 append(iterator(p), oldEnd);
1535 std::fill(iterator(p), oldEnd, c);
1537 store_.writeTerminator();
1538 return begin() + pos;
1541 template<class InputIter>
1542 iterator insertImplDiscr(const_iterator i,
1543 InputIter b, InputIter e, Selector<0>) {
1544 return insertImpl(i, b, e,
1545 typename std::iterator_traits<InputIter>::iterator_category());
1548 template <class FwdIterator>
1549 iterator insertImpl(const_iterator i,
1550 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1551 Invariant checker(*this);
1553 const size_type pos = i - begin();
1554 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1555 std::distance(s1, s2);
1557 using namespace fbstring_detail;
1558 assert(pos <= size());
1560 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1561 capacity() - size();
1563 // realloc the string
1564 reserve(size() + n2);
1567 if (pos + n2 <= size()) {
1568 const iterator tailBegin = end() - n2;
1569 store_.expand_noinit(n2);
1570 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1571 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1572 reverse_iterator(tailBegin + n2));
1573 std::copy(s1, s2, begin() + pos);
1576 const size_type old_size = size();
1577 std::advance(t, old_size - pos);
1578 const size_t newElems = std::distance(t, s2);
1579 store_.expand_noinit(n2);
1580 std::copy(t, s2, begin() + old_size);
1581 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1582 begin() + old_size + newElems);
1583 std::copy(s1, t, begin() + pos);
1585 store_.writeTerminator();
1586 return begin() + pos;
1589 template <class InputIterator>
1590 iterator insertImpl(const_iterator i,
1591 InputIterator b, InputIterator e,
1592 std::input_iterator_tag) {
1593 const auto pos = i - begin();
1594 basic_fbstring temp(begin(), i);
1595 for (; b != e; ++b) {
1598 temp.append(i, cend());
1600 return begin() + pos;
1604 template <class ItOrLength, class ItOrChar>
1605 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1606 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1607 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1610 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1611 return insert(p, il.begin(), il.end());
1614 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1615 Invariant checker(*this);
1617 enforce(pos <= length(), std::__throw_out_of_range, "");
1618 procrustes(n, length() - pos);
1619 std::copy(begin() + pos + n, end(), begin() + pos);
1620 resize(length() - n);
1624 iterator erase(iterator position) {
1625 const size_type pos(position - begin());
1626 enforce(pos <= size(), std::__throw_out_of_range, "");
1628 return begin() + pos;
1631 iterator erase(iterator first, iterator last) {
1632 const size_type pos(first - begin());
1633 erase(pos, last - first);
1634 return begin() + pos;
1637 // Replaces at most n1 chars of *this, starting with pos1 with the
1639 basic_fbstring& replace(size_type pos1, size_type n1,
1640 const basic_fbstring& str) {
1641 return replace(pos1, n1, str.data(), str.size());
1644 // Replaces at most n1 chars of *this, starting with pos1,
1645 // with at most n2 chars of str starting with pos2
1646 basic_fbstring& replace(size_type pos1, size_type n1,
1647 const basic_fbstring& str,
1648 size_type pos2, size_type n2) {
1649 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1650 return replace(pos1, n1, str.data() + pos2,
1651 std::min(n2, str.size() - pos2));
1654 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1655 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1656 return replace(pos, n1, s, traits_type::length(s));
1659 // Replaces at most n1 chars of *this, starting with pos, with n2
1662 // consolidated with
1664 // Replaces at most n1 chars of *this, starting with pos, with at
1665 // most n2 chars of str. str must have at least n2 chars.
1666 template <class StrOrLength, class NumOrChar>
1667 basic_fbstring& replace(size_type pos, size_type n1,
1668 StrOrLength s_or_n2, NumOrChar n_or_c) {
1669 Invariant checker(*this);
1671 enforce(pos <= size(), std::__throw_out_of_range, "");
1672 procrustes(n1, length() - pos);
1673 const iterator b = begin() + pos;
1674 return replace(b, b + n1, s_or_n2, n_or_c);
1677 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1678 return replace(i1, i2, str.data(), str.length());
1681 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1682 return replace(i1, i2, s, traits_type::length(s));
1686 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1687 const value_type* s, size_type n,
1690 assert(begin() <= i1 && i1 <= end());
1691 assert(begin() <= i2 && i2 <= end());
1692 return replace(i1, i2, s, s + n);
1695 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1696 size_type n2, value_type c, Selector<1>) {
1697 const size_type n1 = i2 - i1;
1699 std::fill(i1, i1 + n2, c);
1702 std::fill(i1, i2, c);
1703 insert(i2, n2 - n1, c);
1709 template <class InputIter>
1710 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1711 InputIter b, InputIter e,
1713 replaceImpl(i1, i2, b, e,
1714 typename std::iterator_traits<InputIter>::iterator_category());
1719 template <class FwdIterator>
1720 bool replaceAliased(iterator i1, iterator i2,
1721 FwdIterator s1, FwdIterator s2, std::false_type) {
1725 template <class FwdIterator>
1726 bool replaceAliased(iterator i1, iterator i2,
1727 FwdIterator s1, FwdIterator s2, std::true_type) {
1728 static const std::less_equal<const value_type*> le =
1729 std::less_equal<const value_type*>();
1730 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1734 // Aliased replace, copy to new string
1735 basic_fbstring temp;
1736 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1737 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1742 template <class FwdIterator>
1743 void replaceImpl(iterator i1, iterator i2,
1744 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1745 Invariant checker(*this);
1748 // Handle aliased replace
1749 if (replaceAliased(i1, i2, s1, s2,
1750 std::integral_constant<bool,
1751 std::is_same<FwdIterator, iterator>::value ||
1752 std::is_same<FwdIterator, const_iterator>::value>())) {
1756 auto const n1 = i2 - i1;
1758 auto const n2 = std::distance(s1, s2);
1763 std::copy(s1, s2, i1);
1767 fbstring_detail::copy_n(s1, n1, i1);
1768 std::advance(s1, n1);
1774 template <class InputIterator>
1775 void replaceImpl(iterator i1, iterator i2,
1776 InputIterator b, InputIterator e, std::input_iterator_tag) {
1777 basic_fbstring temp(begin(), i1);
1778 temp.append(b, e).append(i2, end());
1783 template <class T1, class T2>
1784 basic_fbstring& replace(iterator i1, iterator i2,
1785 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1787 num1 = std::numeric_limits<T1>::is_specialized,
1788 num2 = std::numeric_limits<T2>::is_specialized;
1789 return replaceImplDiscr(
1790 i1, i2, first_or_n_or_s, last_or_c_or_n,
1791 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1794 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1795 enforce(pos <= size(), std::__throw_out_of_range, "");
1796 procrustes(n, size() - pos);
1798 fbstring_detail::pod_copy(
1805 void swap(basic_fbstring& rhs) {
1806 store_.swap(rhs.store_);
1809 const value_type* c_str() const {
1810 return store_.c_str();
1813 const value_type* data() const { return c_str(); }
1815 allocator_type get_allocator() const {
1816 return allocator_type();
1819 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1820 return find(str.data(), pos, str.length());
1823 size_type find(const value_type* needle, const size_type pos,
1824 const size_type nsize) const {
1825 if (!nsize) return pos;
1826 auto const size = this->size();
1827 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1828 // that nsize + pos does not wrap around.
1829 if (nsize + pos > size || nsize + pos < pos) return npos;
1830 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1831 // the last characters first
1832 auto const haystack = data();
1833 auto const nsize_1 = nsize - 1;
1834 auto const lastNeedle = needle[nsize_1];
1836 // Boyer-Moore skip value for the last char in the needle. Zero is
1837 // not a valid value; skip will be computed the first time it's
1841 const E * i = haystack + pos;
1842 auto iEnd = haystack + size - nsize_1;
1845 // Boyer-Moore: match the last element in the needle
1846 while (i[nsize_1] != lastNeedle) {
1852 // Here we know that the last char matches
1853 // Continue in pedestrian mode
1854 for (size_t j = 0; ; ) {
1856 if (i[j] != needle[j]) {
1857 // Not found, we can skip
1858 // Compute the skip value lazily
1861 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1868 // Check if done searching
1871 return i - haystack;
1878 size_type find(const value_type* s, size_type pos = 0) const {
1879 return find(s, pos, traits_type::length(s));
1882 size_type find (value_type c, size_type pos = 0) const {
1883 return find(&c, pos, 1);
1886 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1887 return rfind(str.data(), pos, str.length());
1890 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1891 if (n > length()) return npos;
1892 pos = std::min(pos, length() - n);
1893 if (n == 0) return pos;
1895 const_iterator i(begin() + pos);
1897 if (traits_type::eq(*i, *s)
1898 && traits_type::compare(&*i, s, n) == 0) {
1901 if (i == begin()) break;
1906 size_type rfind(const value_type* s, size_type pos = npos) const {
1907 return rfind(s, pos, traits_type::length(s));
1910 size_type rfind(value_type c, size_type pos = npos) const {
1911 return rfind(&c, pos, 1);
1914 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1915 return find_first_of(str.data(), pos, str.length());
1918 size_type find_first_of(const value_type* s,
1919 size_type pos, size_type n) const {
1920 if (pos > length() || n == 0) return npos;
1921 const_iterator i(begin() + pos),
1923 for (; i != finish; ++i) {
1924 if (traits_type::find(s, n, *i) != 0) {
1931 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1932 return find_first_of(s, pos, traits_type::length(s));
1935 size_type find_first_of(value_type c, size_type pos = 0) const {
1936 return find_first_of(&c, pos, 1);
1939 size_type find_last_of (const basic_fbstring& str,
1940 size_type pos = npos) const {
1941 return find_last_of(str.data(), pos, str.length());
1944 size_type find_last_of (const value_type* s, size_type pos,
1945 size_type n) const {
1946 if (!empty() && n > 0) {
1947 pos = std::min(pos, length() - 1);
1948 const_iterator i(begin() + pos);
1950 if (traits_type::find(s, n, *i) != 0) {
1953 if (i == begin()) break;
1959 size_type find_last_of (const value_type* s,
1960 size_type pos = npos) const {
1961 return find_last_of(s, pos, traits_type::length(s));
1964 size_type find_last_of (value_type c, size_type pos = npos) const {
1965 return find_last_of(&c, pos, 1);
1968 size_type find_first_not_of(const basic_fbstring& str,
1969 size_type pos = 0) const {
1970 return find_first_not_of(str.data(), pos, str.size());
1973 size_type find_first_not_of(const value_type* s, size_type pos,
1974 size_type n) const {
1975 if (pos < length()) {
1979 for (; i != finish; ++i) {
1980 if (traits_type::find(s, n, *i) == 0) {
1988 size_type find_first_not_of(const value_type* s,
1989 size_type pos = 0) const {
1990 return find_first_not_of(s, pos, traits_type::length(s));
1993 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1994 return find_first_not_of(&c, pos, 1);
1997 size_type find_last_not_of(const basic_fbstring& str,
1998 size_type pos = npos) const {
1999 return find_last_not_of(str.data(), pos, str.length());
2002 size_type find_last_not_of(const value_type* s, size_type pos,
2003 size_type n) const {
2004 if (!this->empty()) {
2005 pos = std::min(pos, size() - 1);
2006 const_iterator i(begin() + pos);
2008 if (traits_type::find(s, n, *i) == 0) {
2011 if (i == begin()) break;
2017 size_type find_last_not_of(const value_type* s,
2018 size_type pos = npos) const {
2019 return find_last_not_of(s, pos, traits_type::length(s));
2022 size_type find_last_not_of (value_type c, size_type pos = npos) const {
2023 return find_last_not_of(&c, pos, 1);
2026 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
2027 enforce(pos <= size(), std::__throw_out_of_range, "");
2028 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2031 int compare(const basic_fbstring& str) const {
2032 // FIX due to Goncalo N M de Carvalho July 18, 2005
2033 return compare(0, size(), str);
2036 int compare(size_type pos1, size_type n1,
2037 const basic_fbstring& str) const {
2038 return compare(pos1, n1, str.data(), str.size());
2041 int compare(size_type pos1, size_type n1,
2042 const value_type* s) const {
2043 return compare(pos1, n1, s, traits_type::length(s));
2046 int compare(size_type pos1, size_type n1,
2047 const value_type* s, size_type n2) const {
2048 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2049 procrustes(n1, size() - pos1);
2050 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2051 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2052 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2055 int compare(size_type pos1, size_type n1,
2056 const basic_fbstring& str,
2057 size_type pos2, size_type n2) const {
2058 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2059 return compare(pos1, n1, str.data() + pos2,
2060 std::min(n2, str.size() - pos2));
2063 // Code from Jean-Francois Bastien (03/26/2007)
2064 int compare(const value_type* s) const {
2065 // Could forward to compare(0, size(), s, traits_type::length(s))
2066 // but that does two extra checks
2067 const size_type n1(size()), n2(traits_type::length(s));
2068 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2069 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2077 // non-member functions
2079 template <typename E, class T, class A, class S>
2081 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2082 const basic_fbstring<E, T, A, S>& rhs) {
2084 basic_fbstring<E, T, A, S> result;
2085 result.reserve(lhs.size() + rhs.size());
2086 result.append(lhs).append(rhs);
2087 return std::move(result);
2091 template <typename E, class T, class A, class S>
2093 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2094 const basic_fbstring<E, T, A, S>& rhs) {
2095 return std::move(lhs.append(rhs));
2099 template <typename E, class T, class A, class S>
2101 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2102 basic_fbstring<E, T, A, S>&& rhs) {
2103 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2104 // Good, at least we don't need to reallocate
2105 return std::move(rhs.insert(0, lhs));
2107 // Meh, no go. Forward to operator+(const&, const&).
2108 auto const& rhsC = rhs;
2113 template <typename E, class T, class A, class S>
2115 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2116 basic_fbstring<E, T, A, S>&& rhs) {
2117 return std::move(lhs.append(rhs));
2120 template <typename E, class T, class A, class S>
2122 basic_fbstring<E, T, A, S> operator+(
2123 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2124 const basic_fbstring<E, T, A, S>& rhs) {
2126 basic_fbstring<E, T, A, S> result;
2127 const typename basic_fbstring<E, T, A, S>::size_type len =
2128 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2129 result.reserve(len + rhs.size());
2130 result.append(lhs, len).append(rhs);
2134 template <typename E, class T, class A, class S>
2136 basic_fbstring<E, T, A, S> operator+(
2137 typename basic_fbstring<E, T, A, S>::value_type lhs,
2138 const basic_fbstring<E, T, A, S>& rhs) {
2140 basic_fbstring<E, T, A, S> result;
2141 result.reserve(1 + rhs.size());
2142 result.push_back(lhs);
2147 template <typename E, class T, class A, class S>
2149 basic_fbstring<E, T, A, S> operator+(
2150 const basic_fbstring<E, T, A, S>& lhs,
2151 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2153 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2154 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2156 basic_fbstring<E, T, A, S> result;
2157 const size_type len = traits_type::length(rhs);
2158 result.reserve(lhs.size() + len);
2159 result.append(lhs).append(rhs, len);
2163 template <typename E, class T, class A, class S>
2165 basic_fbstring<E, T, A, S> operator+(
2166 const basic_fbstring<E, T, A, S>& lhs,
2167 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2169 basic_fbstring<E, T, A, S> result;
2170 result.reserve(lhs.size() + 1);
2172 result.push_back(rhs);
2176 template <typename E, class T, class A, class S>
2178 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2179 const basic_fbstring<E, T, A, S>& rhs) {
2180 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2182 template <typename E, class T, class A, class S>
2184 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2185 const basic_fbstring<E, T, A, S>& rhs) {
2186 return rhs == lhs; }
2188 template <typename E, class T, class A, class S>
2190 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2191 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2192 return lhs.compare(rhs) == 0; }
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 == rhs); }
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 !(lhs == rhs); }
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 == rhs); }
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.compare(rhs) < 0; }
2218 template <typename E, class T, class A, class S>
2220 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2221 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2222 return lhs.compare(rhs) < 0; }
2224 template <typename E, class T, class A, class S>
2226 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2227 const basic_fbstring<E, T, A, S>& rhs) {
2228 return rhs.compare(lhs) > 0; }
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) {
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) {
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) {
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) {
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 typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2258 return !(rhs < lhs); }
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) {
2264 return !(rhs < lhs); }
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 !(lhs < rhs); }
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 !(lhs < rhs); }
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 !(lhs < rhs);
2286 template <typename E, class T, class A, class S>
2287 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2291 // TODO: make this faster.
2292 template <typename E, class T, class A, class S>
2295 typename basic_fbstring<E, T, A, S>::value_type,
2296 typename basic_fbstring<E, T, A, S>::traits_type>&
2298 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2299 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2300 basic_fbstring<E, T, A, S>& str) {
2301 typename std::basic_istream<E, T>::sentry sentry(is);
2302 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2303 typename basic_fbstring<E, T, A, S>::traits_type>
2305 typedef typename __istream_type::ios_base __ios_base;
2306 size_t extracted = 0;
2307 auto err = __ios_base::goodbit;
2309 auto n = is.width();
2314 auto got = is.rdbuf()->sgetc();
2315 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2316 // Whew. We get to store this guy
2318 got = is.rdbuf()->snextc();
2320 if (got == T::eof()) {
2321 err |= __ios_base::eofbit;
2326 err |= __ios_base::failbit;
2334 template <typename E, class T, class A, class S>
2336 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2337 typename basic_fbstring<E, T, A, S>::traits_type>&
2339 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2340 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2341 const basic_fbstring<E, T, A, S>& str) {
2343 typename std::basic_ostream<
2344 typename basic_fbstring<E, T, A, S>::value_type,
2345 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2347 typedef std::ostreambuf_iterator<
2348 typename basic_fbstring<E, T, A, S>::value_type,
2349 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2350 size_t __len = str.size();
2352 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2353 if (__pad_and_output(_Ip(os),
2355 __left ? str.data() + __len : str.data(),
2358 os.fill()).failed()) {
2359 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2363 std::__ostream_insert(os, str.data(), str.size());
2368 #ifndef _LIBSTDCXX_FBSTRING
2370 template <typename E, class T, class A, class S>
2372 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2373 typename basic_fbstring<E, T, A, S>::traits_type>&
2375 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2376 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2377 basic_fbstring<E, T, A, S>& str,
2378 typename basic_fbstring<E, T, A, S>::value_type delim) {
2379 // Use the nonstandard getdelim()
2380 char * buf = nullptr;
2383 // This looks quadratic but it really depends on realloc
2384 auto const newSize = size + 128;
2385 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2386 is.getline(buf + size, newSize - size, delim);
2387 if (is.bad() || is.eof() || !is.fail()) {
2388 // done by either failure, end of file, or normal read
2389 size += std::strlen(buf + size);
2392 // Here we have failed due to too short a buffer
2393 // Minus one to discount the terminating '\0'
2395 assert(buf[size] == 0);
2396 // Clear the error so we can continue reading
2399 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2400 AcquireMallocatedString());
2405 template <typename E, class T, class A, class S>
2407 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2408 typename basic_fbstring<E, T, A, S>::traits_type>&
2410 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2411 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2412 basic_fbstring<E, T, A, S>& str) {
2413 // Just forward to the version with a delimiter
2414 return getline(is, str, '\n');
2419 template <typename E1, class T, class A, class S>
2420 const typename basic_fbstring<E1, T, A, S>::size_type
2421 basic_fbstring<E1, T, A, S>::npos =
2422 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2424 #ifndef _LIBSTDCXX_FBSTRING
2425 // basic_string compatibility routines
2427 template <typename E, class T, class A, class S>
2429 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2430 const std::string& rhs) {
2431 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2434 template <typename E, class T, class A, class S>
2436 bool operator==(const std::string& lhs,
2437 const basic_fbstring<E, T, A, S>& rhs) {
2441 template <typename E, class T, class A, class S>
2443 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2444 const std::string& rhs) {
2445 return !(lhs == rhs);
2448 template <typename E, class T, class A, class S>
2450 bool operator!=(const std::string& lhs,
2451 const basic_fbstring<E, T, A, S>& rhs) {
2452 return !(lhs == rhs);
2455 #if !defined(_LIBSTDCXX_FBSTRING)
2456 typedef basic_fbstring<char> fbstring;
2459 // fbstring is relocatable
2460 template <class T, class R, class A, class S>
2461 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2464 _GLIBCXX_END_NAMESPACE_VERSION
2467 } // namespace folly
2469 #ifndef _LIBSTDCXX_FBSTRING
2471 // Hash functions to make fbstring usable with e.g. hash_map
2473 // Handle interaction with different C++ standard libraries, which
2474 // expect these types to be in different namespaces.
2478 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2479 size_t operator()(const folly::basic_fbstring<C> & s) const {
2480 return hash<const C*>::operator()(s.c_str());
2485 struct hash< ::folly::fbstring> {
2486 size_t operator()(const ::folly::fbstring& s) const {
2487 return ::folly::hash::fnv32_buf(s.data(), s.size());
2493 #if FOLLY_HAVE_DEPRECATED_ASSOC
2494 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2495 namespace __gnu_cxx {
2498 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2499 size_t operator()(const folly::basic_fbstring<C> & s) const {
2500 return hash<const C*>::operator()(s.c_str());
2505 struct hash< ::folly::fbstring> {
2506 size_t operator()(const ::folly::fbstring& s) const {
2507 return ::folly::hash::fnv32_buf(s.data(), s.size());
2512 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2513 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2515 #endif // _LIBSTDCXX_FBSTRING
2517 #pragma GCC diagnostic pop
2519 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2521 #undef FBSTRING_LIKELY
2522 #undef FBSTRING_UNLIKELY
2524 #endif // FOLLY_BASE_FBSTRING_H_