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 static_assert(offsetof(MediumLarge, data_) == 0,
343 "fbstring layout failure");
344 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
345 "fbstring layout failure");
346 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
347 "fbstring layout failure");
348 const size_t size = rhs.smallSize();
350 ml_.capacity_ = rhs.ml_.capacity_;
353 // Just write the whole thing, don't look at details. In
354 // particular we need to copy capacity anyway because we want
355 // to set the size (don't forget that the last character,
356 // which stores a short string's length, is shared with the
357 // ml_.capacity field).
360 assert(category() == isSmall && this->size() == rhs.size());
361 } else if (rhs.category() == isLarge) {
362 // Large strings are just refcounted
364 RefCounted::incrementRefs(ml_.data_);
365 assert(category() == isLarge && size() == rhs.size());
367 // Medium strings are copied eagerly. Don't forget to allocate
368 // one extra Char for the null terminator.
369 auto const allocSize =
370 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
371 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
372 fbstring_detail::pod_copy(rhs.ml_.data_,
374 rhs.ml_.data_ + rhs.ml_.size_ + 1,
376 // No need for writeTerminator() here, we copied one extra
377 // element just above.
378 ml_.size_ = rhs.ml_.size_;
379 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
380 assert(category() == isMedium);
382 assert(size() == rhs.size());
383 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
386 fbstring_core(fbstring_core&& goner) noexcept {
387 if (goner.category() == isSmall) {
388 // Just copy, leave the goner in peace
389 new(this) fbstring_core(goner.small_, goner.smallSize());
393 // Clean goner's carcass
394 goner.setSmallSize(0);
398 // NOTE(agallagher): The word-aligned copy path copies bytes which are
399 // outside the range of the string, and makes address sanitizer unhappy,
400 // so just disable it on this function.
401 fbstring_core(const Char *const data, const size_t size)
402 FBSTRING_DISABLE_ADDRESS_SANITIZER {
403 // Simplest case first: small strings are bitblitted
404 if (size <= maxSmallSize) {
405 // Layout is: Char* data_, size_t size_, size_t capacity_
406 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
407 "fbstring has unexpected size");
408 static_assert(sizeof(Char*) == sizeof(size_t),
409 "fbstring size assumption violation");
410 // sizeof(size_t) must be a power of 2
411 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
412 "fbstring size assumption violation");
414 // If data is aligned, use fast word-wise copying. Otherwise,
415 // use conservative memcpy.
416 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
417 fbstring_detail::pod_copy(data, data + size, small_);
419 // Copy one word (64 bits) at a time
420 const size_t byteSize = size * sizeof(Char);
421 if (byteSize > 2 * sizeof(size_t)) {
423 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
425 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
427 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
428 } else if (byteSize > sizeof(size_t)) {
431 } else if (size > 0) {
437 } else if (size <= maxMediumSize) {
438 // Medium strings are allocated normally. Don't forget to
439 // allocate one extra Char for the terminating null.
440 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
441 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
442 fbstring_detail::pod_copy(data, data + size, ml_.data_);
444 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
446 // Large strings are allocated differently
447 size_t effectiveCapacity = size;
448 auto const newRC = RefCounted::create(data, & effectiveCapacity);
449 ml_.data_ = newRC->data_;
451 ml_.capacity_ = effectiveCapacity | isLarge;
454 assert(this->size() == size);
455 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
458 ~fbstring_core() noexcept {
459 auto const c = category();
467 RefCounted::decrementRefs(ml_.data_);
470 // Snatches a previously mallocated string. The parameter "size"
471 // is the size of the string, and the parameter "allocatedSize"
472 // is the size of the mallocated block. The string must be
473 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
475 // So if you want a 2-character string, pass malloc(3) as "data",
476 // pass 2 as "size", and pass 3 as "allocatedSize".
477 fbstring_core(Char * const data,
479 const size_t allocatedSize,
480 AcquireMallocatedString) {
482 assert(allocatedSize >= size + 1);
483 assert(data[size] == '\0');
484 // Use the medium string storage
487 // Don't forget about null terminator
488 ml_.capacity_ = (allocatedSize - 1) | isMedium;
490 // No need for the memory
496 // swap below doesn't test whether &rhs == this (and instead
497 // potentially does extra work) on the premise that the rarity of
498 // that situation actually makes the check more expensive than is
500 void swap(fbstring_core & rhs) {
506 // In C++11 data() and c_str() are 100% equivalent.
507 const Char * data() const {
511 Char * mutable_data() {
512 auto const c = category();
516 assert(c == isMedium || c == isLarge);
517 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
519 size_t effectiveCapacity = ml_.capacity();
520 auto const newRC = RefCounted::create(& effectiveCapacity);
521 // If this fails, someone placed the wrong capacity in an
523 assert(effectiveCapacity >= ml_.capacity());
524 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
526 RefCounted::decrementRefs(ml_.data_);
527 ml_.data_ = newRC->data_;
528 // No need to call writeTerminator(), we have + 1 above.
533 const Char * c_str() const {
534 auto const c = category();
535 #ifdef FBSTRING_PERVERSE
537 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
538 || small_[smallSize()] == '\0');
539 small_[smallSize()] = '\0';
542 assert(c == isMedium || c == isLarge);
543 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
544 ml_.data_[ml_.size_] = '\0';
545 #elif defined(FBSTRING_CONSERVATIVE)
547 assert(small_[smallSize()] == '\0');
550 assert(c == isMedium || c == isLarge);
551 assert(ml_.data_[ml_.size_] == '\0');
554 small_[smallSize()] = '\0';
557 assert(c == isMedium || c == isLarge);
558 ml_.data_[ml_.size_] = '\0';
563 void shrink(const size_t delta) {
564 if (category() == isSmall) {
565 // Check for underflow
566 assert(delta <= smallSize());
567 setSmallSize(smallSize() - delta);
568 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
569 // Medium strings and unique large strings need no special
571 assert(ml_.size_ >= delta);
574 assert(ml_.size_ >= delta);
575 // Shared large string, must make unique. This is because of the
576 // durn terminator must be written, which may trample the shared
579 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
581 // No need to write the terminator.
587 void reserve(size_t minCapacity) {
588 if (category() == isLarge) {
590 if (RefCounted::refs(ml_.data_) > 1) {
591 // We must make it unique regardless; in-place reallocation is
592 // useless if the string is shared. In order to not surprise
593 // people, reserve the new block at current capacity or
594 // more. That way, a string's capacity never shrinks after a
596 minCapacity = std::max(minCapacity, ml_.capacity());
597 auto const newRC = RefCounted::create(& minCapacity);
598 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
600 // Done with the old data. No need to call writeTerminator(),
601 // we have + 1 above.
602 RefCounted::decrementRefs(ml_.data_);
603 ml_.data_ = newRC->data_;
604 ml_.capacity_ = minCapacity | isLarge;
605 // size remains unchanged
607 // String is not shared, so let's try to realloc (if needed)
608 if (minCapacity > ml_.capacity()) {
609 // Asking for more memory
611 RefCounted::reallocate(ml_.data_, ml_.size_,
612 ml_.capacity(), minCapacity);
613 ml_.data_ = newRC->data_;
614 ml_.capacity_ = minCapacity | isLarge;
617 assert(capacity() >= minCapacity);
619 } else if (category() == isMedium) {
620 // String is not shared
621 if (minCapacity <= ml_.capacity()) {
622 return; // nothing to do, there's enough room
624 if (minCapacity <= maxMediumSize) {
625 // Keep the string at medium size. Don't forget to allocate
626 // one extra Char for the terminating null.
627 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
628 ml_.data_ = static_cast<Char *>(
631 ml_.size_ * sizeof(Char),
632 (ml_.capacity() + 1) * sizeof(Char),
635 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
637 // Conversion from medium to large string
638 fbstring_core nascent;
639 // Will recurse to another branch of this function
640 nascent.reserve(minCapacity);
641 nascent.ml_.size_ = ml_.size_;
642 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
646 assert(capacity() >= minCapacity);
649 assert(category() == isSmall);
650 if (minCapacity > maxMediumSize) {
652 auto const newRC = RefCounted::create(& minCapacity);
653 auto const size = smallSize();
654 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
655 // No need for writeTerminator(), we wrote it above with + 1.
656 ml_.data_ = newRC->data_;
658 ml_.capacity_ = minCapacity | isLarge;
659 assert(capacity() >= minCapacity);
660 } else if (minCapacity > maxSmallSize) {
662 // Don't forget to allocate one extra Char for the terminating null
663 auto const allocSizeBytes =
664 goodMallocSize((1 + minCapacity) * sizeof(Char));
665 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
666 auto const size = smallSize();
667 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
668 // No need for writeTerminator(), we wrote it above with + 1.
671 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
674 // Nothing to do, everything stays put
677 assert(capacity() >= minCapacity);
680 Char * expand_noinit(const size_t delta) {
681 // Strategy is simple: make room, then change size
682 assert(capacity() >= size());
684 if (category() == isSmall) {
687 if (newSz <= maxSmallSize) {
695 newSz = ml_.size_ + delta;
696 if (newSz > capacity()) {
700 assert(capacity() >= newSz);
701 // Category can't be small - we took care of that above
702 assert(category() == isMedium || category() == isLarge);
705 assert(size() == newSz);
706 return ml_.data_ + sz;
709 void push_back(Char c) {
710 assert(capacity() >= size());
712 if (category() == isSmall) {
714 if (sz < maxSmallSize) {
715 setSmallSize(sz + 1);
720 reserve(maxSmallSize * 2);
723 if (sz == capacity()) { // always true for isShared()
724 reserve(1 + sz * 3 / 2); // ensures not shared
728 assert(capacity() >= sz + 1);
729 // Category can't be small - we took care of that above
730 assert(category() == isMedium || category() == isLarge);
736 size_t size() const {
737 return category() == isSmall ? smallSize() : ml_.size_;
740 size_t capacity() const {
741 switch (category()) {
745 // For large-sized strings, a multi-referenced chunk has no
746 // available capacity. This is because any attempt to append
747 // data would trigger a new allocation.
748 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
751 return ml_.capacity();
754 bool isShared() const {
755 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
758 #ifdef FBSTRING_PERVERSE
759 enum { TERMINATOR = '^' };
761 enum { TERMINATOR = '\0' };
764 void writeTerminator() {
765 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
766 if (category() == isSmall) {
767 const auto s = smallSize();
768 if (s != maxSmallSize) {
769 small_[s] = TERMINATOR;
772 ml_.data_[ml_.size_] = TERMINATOR;
779 fbstring_core & operator=(const fbstring_core & rhs);
786 size_t capacity() const {
787 return capacity_ & capacityExtractMask;
792 std::atomic<size_t> refCount_;
795 static RefCounted * fromData(Char * p) {
796 return static_cast<RefCounted*>(
798 static_cast<unsigned char*>(static_cast<void*>(p))
799 - sizeof(refCount_)));
802 static size_t refs(Char * p) {
803 return fromData(p)->refCount_.load(std::memory_order_acquire);
806 static void incrementRefs(Char * p) {
807 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
810 static void decrementRefs(Char * p) {
811 auto const dis = fromData(p);
812 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
819 static RefCounted * create(size_t * size) {
820 // Don't forget to allocate one extra Char for the terminating
821 // null. In this case, however, one Char is already part of the
823 const size_t allocSize = goodMallocSize(
824 sizeof(RefCounted) + *size * sizeof(Char));
825 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
826 result->refCount_.store(1, std::memory_order_release);
827 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
831 static RefCounted * create(const Char * data, size_t * size) {
832 const size_t effectiveSize = *size;
833 auto result = create(size);
834 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
838 static RefCounted * reallocate(Char *const data,
839 const size_t currentSize,
840 const size_t currentCapacity,
841 const size_t newCapacity) {
842 assert(newCapacity > 0 && newCapacity > currentSize);
843 auto const dis = fromData(data);
844 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
845 // Don't forget to allocate one extra Char for the terminating
846 // null. In this case, however, one Char is already part of the
848 auto result = static_cast<RefCounted*>(
850 sizeof(RefCounted) + currentSize * sizeof(Char),
851 sizeof(RefCounted) + currentCapacity * sizeof(Char),
852 sizeof(RefCounted) + newCapacity * sizeof(Char)));
853 assert(result->refCount_.load(std::memory_order_acquire) == 1);
859 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
860 mutable MediumLarge ml_;
864 lastChar = sizeof(MediumLarge) - 1,
865 maxSmallSize = lastChar / sizeof(Char),
866 maxMediumSize = 254 / sizeof(Char), // coincides with the small
867 // bin size in dlmalloc
868 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
869 capacityExtractMask = ~categoryExtractMask,
871 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
872 "Corrupt memory layout for fbstring.");
876 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
877 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
880 Category category() const {
881 // Assumes little endian
882 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
885 size_t smallSize() const {
886 assert(category() == isSmall &&
887 static_cast<size_t>(small_[maxSmallSize])
888 <= static_cast<size_t>(maxSmallSize));
889 return static_cast<size_t>(maxSmallSize)
890 - static_cast<size_t>(small_[maxSmallSize]);
893 void setSmallSize(size_t s) {
894 // Warning: this should work with uninitialized strings too,
895 // so don't assume anything about the previous value of
896 // small_[maxSmallSize].
897 assert(s <= maxSmallSize);
898 small_[maxSmallSize] = maxSmallSize - s;
902 #if defined(__GNUC__) && !defined(__clang__)
903 # pragma GCC diagnostic pop
906 #ifndef _LIBSTDCXX_FBSTRING
908 * Dummy fbstring core that uses an actual std::string. This doesn't
909 * make any sense - it's just for testing purposes.
911 template <class Char>
912 class dummy_fbstring_core {
914 dummy_fbstring_core() {
916 dummy_fbstring_core(const dummy_fbstring_core& another)
917 : backend_(another.backend_) {
919 dummy_fbstring_core(const Char * s, size_t n)
922 void swap(dummy_fbstring_core & rhs) {
923 backend_.swap(rhs.backend_);
925 const Char * data() const {
926 return backend_.data();
928 Char * mutable_data() {
929 //assert(!backend_.empty());
930 return &*backend_.begin();
932 void shrink(size_t delta) {
933 assert(delta <= size());
934 backend_.resize(size() - delta);
936 Char * expand_noinit(size_t delta) {
937 auto const sz = size();
938 backend_.resize(size() + delta);
939 return backend_.data() + sz;
941 void push_back(Char c) {
942 backend_.push_back(c);
944 size_t size() const {
945 return backend_.size();
947 size_t capacity() const {
948 return backend_.capacity();
950 bool isShared() const {
953 void reserve(size_t minCapacity) {
954 backend_.reserve(minCapacity);
958 std::basic_string<Char> backend_;
960 #endif // !_LIBSTDCXX_FBSTRING
963 * This is the basic_string replacement. For conformity,
964 * basic_fbstring takes the same template parameters, plus the last
965 * one which is the core.
967 #ifdef _LIBSTDCXX_FBSTRING
968 template <typename E, class T, class A, class Storage>
970 template <typename E,
971 class T = std::char_traits<E>,
972 class A = std::allocator<E>,
973 class Storage = fbstring_core<E> >
975 class basic_fbstring {
979 void (*throw_exc)(const char*),
981 if (!condition) throw_exc(msg);
984 bool isSane() const {
987 empty() == (size() == 0) &&
988 empty() == (begin() == end()) &&
989 size() <= max_size() &&
990 capacity() <= max_size() &&
991 size() <= capacity() &&
992 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
996 friend struct Invariant;
999 explicit Invariant(const basic_fbstring& s) : s_(s) {
1000 assert(s_.isSane());
1003 assert(s_.isSane());
1006 const basic_fbstring& s_;
1008 explicit Invariant(const basic_fbstring&) {}
1010 Invariant& operator=(const Invariant&);
1015 typedef T traits_type;
1016 typedef typename traits_type::char_type value_type;
1017 typedef A allocator_type;
1018 typedef typename A::size_type size_type;
1019 typedef typename A::difference_type difference_type;
1021 typedef typename A::reference reference;
1022 typedef typename A::const_reference const_reference;
1023 typedef typename A::pointer pointer;
1024 typedef typename A::const_pointer const_pointer;
1026 typedef E* iterator;
1027 typedef const E* const_iterator;
1028 typedef std::reverse_iterator<iterator
1029 #ifdef NO_ITERATOR_TRAITS
1033 typedef std::reverse_iterator<const_iterator
1034 #ifdef NO_ITERATOR_TRAITS
1037 > const_reverse_iterator;
1039 static const size_type npos; // = size_type(-1)
1042 static void procrustes(size_type& n, size_type nmax) {
1043 if (n > nmax) n = nmax;
1047 // C++11 21.4.2 construct/copy/destroy
1048 explicit basic_fbstring(const A& a = A()) noexcept {
1051 basic_fbstring(const basic_fbstring& str)
1052 : store_(str.store_) {
1056 basic_fbstring(basic_fbstring&& goner) noexcept
1057 : store_(std::move(goner.store_)) {
1060 #ifndef _LIBSTDCXX_FBSTRING
1061 // This is defined for compatibility with std::string
1062 /* implicit */ basic_fbstring(const std::string& str)
1063 : store_(str.data(), str.size()) {
1067 basic_fbstring(const basic_fbstring& str, size_type pos,
1068 size_type n = npos, const A& a = A()) {
1069 assign(str, pos, n);
1072 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1074 ? traits_type::length(s)
1076 std::__throw_logic_error(
1077 "basic_fbstring: null pointer initializer not valid");
1082 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1086 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1087 auto const data = store_.expand_noinit(n);
1088 fbstring_detail::pod_fill(data, data + n, c);
1089 store_.writeTerminator();
1092 template <class InIt>
1093 basic_fbstring(InIt begin, InIt end,
1094 typename std::enable_if<
1095 !std::is_same<typename std::remove_const<InIt>::type,
1096 value_type*>::value, const A>::type & a = A()) {
1100 // Specialization for const char*, const char*
1101 basic_fbstring(const value_type* b, const value_type* e)
1102 : store_(b, e - b) {
1105 // Nonstandard constructor
1106 basic_fbstring(value_type *s, size_type n, size_type c,
1107 AcquireMallocatedString a)
1108 : store_(s, n, c, a) {
1111 // Construction from initialization list
1112 basic_fbstring(std::initializer_list<value_type> il) {
1113 assign(il.begin(), il.end());
1116 ~basic_fbstring() noexcept {
1119 basic_fbstring& operator=(const basic_fbstring& lhs) {
1120 if (FBSTRING_UNLIKELY(&lhs == this)) {
1123 auto const oldSize = size();
1124 auto const srcSize = lhs.size();
1125 if (capacity() >= srcSize && !store_.isShared()) {
1126 // great, just copy the contents
1127 if (oldSize < srcSize)
1128 store_.expand_noinit(srcSize - oldSize);
1130 store_.shrink(oldSize - srcSize);
1131 assert(size() == srcSize);
1132 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1133 store_.writeTerminator();
1135 // need to reallocate, so we may as well create a brand new string
1136 basic_fbstring(lhs).swap(*this);
1142 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1143 if (FBSTRING_UNLIKELY(&goner == this)) {
1144 // Compatibility with std::basic_string<>,
1145 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1148 // No need of this anymore
1149 this->~basic_fbstring();
1150 // Move the goner into this
1151 new(&store_) fbstring_core<E>(std::move(goner.store_));
1155 #ifndef _LIBSTDCXX_FBSTRING
1156 // Compatibility with std::string
1157 basic_fbstring & operator=(const std::string & rhs) {
1158 return assign(rhs.data(), rhs.size());
1161 // Compatibility with std::string
1162 std::string toStdString() const {
1163 return std::string(data(), size());
1166 // A lot of code in fbcode still uses this method, so keep it here for now.
1167 const basic_fbstring& toStdString() const {
1172 basic_fbstring& operator=(const value_type* s) {
1176 basic_fbstring& operator=(value_type c) {
1178 store_.expand_noinit(1);
1179 } else if (store_.isShared()) {
1180 basic_fbstring(1, c).swap(*this);
1183 store_.shrink(size() - 1);
1185 *store_.mutable_data() = c;
1186 store_.writeTerminator();
1190 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1191 return assign(il.begin(), il.end());
1194 // C++11 21.4.3 iterators:
1195 iterator begin() { return store_.mutable_data(); }
1197 const_iterator begin() const { return store_.data(); }
1199 const_iterator cbegin() const { return begin(); }
1202 return store_.mutable_data() + store_.size();
1205 const_iterator end() const {
1206 return store_.data() + store_.size();
1209 const_iterator cend() const { return end(); }
1211 reverse_iterator rbegin() {
1212 return reverse_iterator(end());
1215 const_reverse_iterator rbegin() const {
1216 return const_reverse_iterator(end());
1219 const_reverse_iterator crbegin() const { return rbegin(); }
1221 reverse_iterator rend() {
1222 return reverse_iterator(begin());
1225 const_reverse_iterator rend() const {
1226 return const_reverse_iterator(begin());
1229 const_reverse_iterator crend() const { return rend(); }
1232 // C++11 21.4.5, element access:
1233 const value_type& front() const { return *begin(); }
1234 const value_type& back() const {
1236 // Should be begin()[size() - 1], but that branches twice
1237 return *(end() - 1);
1239 value_type& front() { return *begin(); }
1240 value_type& back() {
1242 // Should be begin()[size() - 1], but that branches twice
1243 return *(end() - 1);
1250 // C++11 21.4.4 capacity:
1251 size_type size() const { return store_.size(); }
1253 size_type length() const { return size(); }
1255 size_type max_size() const {
1256 return std::numeric_limits<size_type>::max();
1259 void resize(const size_type n, const value_type c = value_type()) {
1260 auto size = this->size();
1262 store_.shrink(size - n);
1264 // Do this in two steps to minimize slack memory copied (see
1266 auto const capacity = this->capacity();
1267 assert(capacity >= size);
1268 if (size < capacity) {
1269 auto delta = std::min(n, capacity) - size;
1270 store_.expand_noinit(delta);
1271 fbstring_detail::pod_fill(begin() + size, end(), c);
1274 store_.writeTerminator();
1279 auto const delta = n - size;
1280 store_.expand_noinit(delta);
1281 fbstring_detail::pod_fill(end() - delta, end(), c);
1282 store_.writeTerminator();
1284 assert(this->size() == n);
1287 size_type capacity() const { return store_.capacity(); }
1289 void reserve(size_type res_arg = 0) {
1290 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1291 store_.reserve(res_arg);
1294 void shrink_to_fit() {
1295 // Shrink only if slack memory is sufficiently large
1296 if (capacity() < size() * 3 / 2) {
1299 basic_fbstring(cbegin(), cend()).swap(*this);
1302 void clear() { resize(0); }
1304 bool empty() const { return size() == 0; }
1306 // C++11 21.4.5 element access:
1307 const_reference operator[](size_type pos) const {
1308 return *(c_str() + pos);
1311 reference operator[](size_type pos) {
1312 if (pos == size()) {
1313 // Just call c_str() to make sure '\0' is present
1316 return *(begin() + pos);
1319 const_reference at(size_type n) const {
1320 enforce(n <= size(), std::__throw_out_of_range, "");
1324 reference at(size_type n) {
1325 enforce(n < size(), std::__throw_out_of_range, "");
1329 // C++11 21.4.6 modifiers:
1330 basic_fbstring& operator+=(const basic_fbstring& str) {
1334 basic_fbstring& operator+=(const value_type* s) {
1338 basic_fbstring& operator+=(const value_type c) {
1343 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1348 basic_fbstring& append(const basic_fbstring& str) {
1350 auto desiredSize = size() + str.size();
1352 append(str.data(), str.size());
1353 assert(size() == desiredSize);
1357 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1359 const size_type sz = str.size();
1360 enforce(pos <= sz, std::__throw_out_of_range, "");
1361 procrustes(n, sz - pos);
1362 return append(str.data() + pos, n);
1365 basic_fbstring& append(const value_type* s, size_type n) {
1367 Invariant checker(*this);
1370 if (FBSTRING_UNLIKELY(!n)) {
1371 // Unlikely but must be done
1374 auto const oldSize = size();
1375 auto const oldData = data();
1376 // Check for aliasing (rare). We could use "<=" here but in theory
1377 // those do not work for pointers unless the pointers point to
1378 // elements in the same array. For that reason we use
1379 // std::less_equal, which is guaranteed to offer a total order
1380 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1382 std::less_equal<const value_type*> le;
1383 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1384 assert(le(s + n, oldData + oldSize));
1385 const size_type offset = s - oldData;
1386 store_.reserve(oldSize + n);
1387 // Restore the source
1388 s = data() + offset;
1390 // Warning! Repeated appends with short strings may actually incur
1391 // practically quadratic performance. Avoid that by pushing back
1392 // the first character (which ensures exponential growth) and then
1393 // appending the rest normally. Worst case the append may incur a
1394 // second allocation but that will be rare.
1397 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1398 assert(size() == oldSize + n + 1);
1402 basic_fbstring& append(const value_type* s) {
1403 return append(s, traits_type::length(s));
1406 basic_fbstring& append(size_type n, value_type c) {
1407 resize(size() + n, c);
1411 template<class InputIterator>
1412 basic_fbstring& append(InputIterator first, InputIterator last) {
1413 insert(end(), first, last);
1417 basic_fbstring& append(std::initializer_list<value_type> il) {
1418 return append(il.begin(), il.end());
1421 void push_back(const value_type c) { // primitive
1422 store_.push_back(c);
1425 basic_fbstring& assign(const basic_fbstring& str) {
1426 if (&str == this) return *this;
1427 return assign(str.data(), str.size());
1430 basic_fbstring& assign(basic_fbstring&& str) {
1431 return *this = std::move(str);
1434 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1436 const size_type sz = str.size();
1437 enforce(pos <= sz, std::__throw_out_of_range, "");
1438 procrustes(n, sz - pos);
1439 return assign(str.data() + pos, n);
1442 basic_fbstring& assign(const value_type* s, const size_type n) {
1443 Invariant checker(*this);
1446 std::copy(s, s + n, begin());
1448 assert(size() == n);
1450 const value_type *const s2 = s + size();
1451 std::copy(s, s2, begin());
1452 append(s2, n - size());
1453 assert(size() == n);
1455 store_.writeTerminator();
1456 assert(size() == n);
1460 basic_fbstring& assign(const value_type* s) {
1461 return assign(s, traits_type::length(s));
1464 basic_fbstring& assign(std::initializer_list<value_type> il) {
1465 return assign(il.begin(), il.end());
1468 template <class ItOrLength, class ItOrChar>
1469 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1470 return replace(begin(), end(), first_or_n, last_or_c);
1473 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1474 return insert(pos1, str.data(), str.size());
1477 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1478 size_type pos2, size_type n) {
1479 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1480 procrustes(n, str.length() - pos2);
1481 return insert(pos1, str.data() + pos2, n);
1484 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1485 enforce(pos <= length(), std::__throw_out_of_range, "");
1486 insert(begin() + pos, s, s + n);
1490 basic_fbstring& insert(size_type pos, const value_type* s) {
1491 return insert(pos, s, traits_type::length(s));
1494 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1495 enforce(pos <= length(), std::__throw_out_of_range, "");
1496 insert(begin() + pos, n, c);
1500 iterator insert(const_iterator p, const value_type c) {
1501 const size_type pos = p - begin();
1503 return begin() + pos;
1507 template <int i> class Selector {};
1509 iterator insertImplDiscr(const_iterator p,
1510 size_type n, value_type c, Selector<1>) {
1511 Invariant checker(*this);
1513 auto const pos = p - begin();
1514 assert(p >= begin() && p <= end());
1515 if (capacity() - size() < n) {
1516 const size_type sz = p - begin();
1517 reserve(size() + n);
1520 const iterator oldEnd = end();
1521 if (n < size_type(oldEnd - p)) {
1522 append(oldEnd - n, oldEnd);
1524 // reverse_iterator(oldEnd - n),
1525 // reverse_iterator(p),
1526 // reverse_iterator(oldEnd));
1527 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1529 std::fill(begin() + pos, begin() + pos + n, c);
1531 append(n - (end() - p), c);
1532 append(iterator(p), oldEnd);
1533 std::fill(iterator(p), oldEnd, c);
1535 store_.writeTerminator();
1536 return begin() + pos;
1539 template<class InputIter>
1540 iterator insertImplDiscr(const_iterator i,
1541 InputIter b, InputIter e, Selector<0>) {
1542 return insertImpl(i, b, e,
1543 typename std::iterator_traits<InputIter>::iterator_category());
1546 template <class FwdIterator>
1547 iterator insertImpl(const_iterator i,
1548 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1549 Invariant checker(*this);
1551 const size_type pos = i - begin();
1552 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1553 std::distance(s1, s2);
1555 using namespace fbstring_detail;
1556 assert(pos <= size());
1558 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1559 capacity() - size();
1561 // realloc the string
1562 reserve(size() + n2);
1565 if (pos + n2 <= size()) {
1566 const iterator tailBegin = end() - n2;
1567 store_.expand_noinit(n2);
1568 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1569 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1570 reverse_iterator(tailBegin + n2));
1571 std::copy(s1, s2, begin() + pos);
1574 const size_type old_size = size();
1575 std::advance(t, old_size - pos);
1576 const size_t newElems = std::distance(t, s2);
1577 store_.expand_noinit(n2);
1578 std::copy(t, s2, begin() + old_size);
1579 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1580 begin() + old_size + newElems);
1581 std::copy(s1, t, begin() + pos);
1583 store_.writeTerminator();
1584 return begin() + pos;
1587 template <class InputIterator>
1588 iterator insertImpl(const_iterator i,
1589 InputIterator b, InputIterator e,
1590 std::input_iterator_tag) {
1591 const auto pos = i - begin();
1592 basic_fbstring temp(begin(), i);
1593 for (; b != e; ++b) {
1596 temp.append(i, cend());
1598 return begin() + pos;
1602 template <class ItOrLength, class ItOrChar>
1603 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1604 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1605 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1608 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1609 return insert(p, il.begin(), il.end());
1612 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1613 Invariant checker(*this);
1615 enforce(pos <= length(), std::__throw_out_of_range, "");
1616 procrustes(n, length() - pos);
1617 std::copy(begin() + pos + n, end(), begin() + pos);
1618 resize(length() - n);
1622 iterator erase(iterator position) {
1623 const size_type pos(position - begin());
1624 enforce(pos <= size(), std::__throw_out_of_range, "");
1626 return begin() + pos;
1629 iterator erase(iterator first, iterator last) {
1630 const size_type pos(first - begin());
1631 erase(pos, last - first);
1632 return begin() + pos;
1635 // Replaces at most n1 chars of *this, starting with pos1 with the
1637 basic_fbstring& replace(size_type pos1, size_type n1,
1638 const basic_fbstring& str) {
1639 return replace(pos1, n1, str.data(), str.size());
1642 // Replaces at most n1 chars of *this, starting with pos1,
1643 // with at most n2 chars of str starting with pos2
1644 basic_fbstring& replace(size_type pos1, size_type n1,
1645 const basic_fbstring& str,
1646 size_type pos2, size_type n2) {
1647 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1648 return replace(pos1, n1, str.data() + pos2,
1649 std::min(n2, str.size() - pos2));
1652 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1653 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1654 return replace(pos, n1, s, traits_type::length(s));
1657 // Replaces at most n1 chars of *this, starting with pos, with n2
1660 // consolidated with
1662 // Replaces at most n1 chars of *this, starting with pos, with at
1663 // most n2 chars of str. str must have at least n2 chars.
1664 template <class StrOrLength, class NumOrChar>
1665 basic_fbstring& replace(size_type pos, size_type n1,
1666 StrOrLength s_or_n2, NumOrChar n_or_c) {
1667 Invariant checker(*this);
1669 enforce(pos <= size(), std::__throw_out_of_range, "");
1670 procrustes(n1, length() - pos);
1671 const iterator b = begin() + pos;
1672 return replace(b, b + n1, s_or_n2, n_or_c);
1675 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1676 return replace(i1, i2, str.data(), str.length());
1679 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1680 return replace(i1, i2, s, traits_type::length(s));
1684 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1685 const value_type* s, size_type n,
1688 assert(begin() <= i1 && i1 <= end());
1689 assert(begin() <= i2 && i2 <= end());
1690 return replace(i1, i2, s, s + n);
1693 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1694 size_type n2, value_type c, Selector<1>) {
1695 const size_type n1 = i2 - i1;
1697 std::fill(i1, i1 + n2, c);
1700 std::fill(i1, i2, c);
1701 insert(i2, n2 - n1, c);
1707 template <class InputIter>
1708 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1709 InputIter b, InputIter e,
1711 replaceImpl(i1, i2, b, e,
1712 typename std::iterator_traits<InputIter>::iterator_category());
1717 template <class FwdIterator>
1718 bool replaceAliased(iterator i1, iterator i2,
1719 FwdIterator s1, FwdIterator s2, std::false_type) {
1723 template <class FwdIterator>
1724 bool replaceAliased(iterator i1, iterator i2,
1725 FwdIterator s1, FwdIterator s2, std::true_type) {
1726 static const std::less_equal<const value_type*> le =
1727 std::less_equal<const value_type*>();
1728 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1732 // Aliased replace, copy to new string
1733 basic_fbstring temp;
1734 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1735 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1740 template <class FwdIterator>
1741 void replaceImpl(iterator i1, iterator i2,
1742 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1743 Invariant checker(*this);
1746 // Handle aliased replace
1747 if (replaceAliased(i1, i2, s1, s2,
1748 std::integral_constant<bool,
1749 std::is_same<FwdIterator, iterator>::value ||
1750 std::is_same<FwdIterator, const_iterator>::value>())) {
1754 auto const n1 = i2 - i1;
1756 auto const n2 = std::distance(s1, s2);
1761 std::copy(s1, s2, i1);
1765 fbstring_detail::copy_n(s1, n1, i1);
1766 std::advance(s1, n1);
1772 template <class InputIterator>
1773 void replaceImpl(iterator i1, iterator i2,
1774 InputIterator b, InputIterator e, std::input_iterator_tag) {
1775 basic_fbstring temp(begin(), i1);
1776 temp.append(b, e).append(i2, end());
1781 template <class T1, class T2>
1782 basic_fbstring& replace(iterator i1, iterator i2,
1783 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1785 num1 = std::numeric_limits<T1>::is_specialized,
1786 num2 = std::numeric_limits<T2>::is_specialized;
1787 return replaceImplDiscr(
1788 i1, i2, first_or_n_or_s, last_or_c_or_n,
1789 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1792 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1793 enforce(pos <= size(), std::__throw_out_of_range, "");
1794 procrustes(n, size() - pos);
1796 fbstring_detail::pod_copy(
1803 void swap(basic_fbstring& rhs) {
1804 store_.swap(rhs.store_);
1807 const value_type* c_str() const {
1808 return store_.c_str();
1811 const value_type* data() const { return c_str(); }
1813 allocator_type get_allocator() const {
1814 return allocator_type();
1817 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1818 return find(str.data(), pos, str.length());
1821 size_type find(const value_type* needle, const size_type pos,
1822 const size_type nsize) const {
1823 if (!nsize) return pos;
1824 auto const size = this->size();
1825 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1826 // that nsize + pos does not wrap around.
1827 if (nsize + pos > size || nsize + pos < pos) return npos;
1828 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1829 // the last characters first
1830 auto const haystack = data();
1831 auto const nsize_1 = nsize - 1;
1832 auto const lastNeedle = needle[nsize_1];
1834 // Boyer-Moore skip value for the last char in the needle. Zero is
1835 // not a valid value; skip will be computed the first time it's
1839 const E * i = haystack + pos;
1840 auto iEnd = haystack + size - nsize_1;
1843 // Boyer-Moore: match the last element in the needle
1844 while (i[nsize_1] != lastNeedle) {
1850 // Here we know that the last char matches
1851 // Continue in pedestrian mode
1852 for (size_t j = 0; ; ) {
1854 if (i[j] != needle[j]) {
1855 // Not found, we can skip
1856 // Compute the skip value lazily
1859 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1866 // Check if done searching
1869 return i - haystack;
1876 size_type find(const value_type* s, size_type pos = 0) const {
1877 return find(s, pos, traits_type::length(s));
1880 size_type find (value_type c, size_type pos = 0) const {
1881 return find(&c, pos, 1);
1884 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1885 return rfind(str.data(), pos, str.length());
1888 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1889 if (n > length()) return npos;
1890 pos = std::min(pos, length() - n);
1891 if (n == 0) return pos;
1893 const_iterator i(begin() + pos);
1895 if (traits_type::eq(*i, *s)
1896 && traits_type::compare(&*i, s, n) == 0) {
1899 if (i == begin()) break;
1904 size_type rfind(const value_type* s, size_type pos = npos) const {
1905 return rfind(s, pos, traits_type::length(s));
1908 size_type rfind(value_type c, size_type pos = npos) const {
1909 return rfind(&c, pos, 1);
1912 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1913 return find_first_of(str.data(), pos, str.length());
1916 size_type find_first_of(const value_type* s,
1917 size_type pos, size_type n) const {
1918 if (pos > length() || n == 0) return npos;
1919 const_iterator i(begin() + pos),
1921 for (; i != finish; ++i) {
1922 if (traits_type::find(s, n, *i) != 0) {
1929 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1930 return find_first_of(s, pos, traits_type::length(s));
1933 size_type find_first_of(value_type c, size_type pos = 0) const {
1934 return find_first_of(&c, pos, 1);
1937 size_type find_last_of (const basic_fbstring& str,
1938 size_type pos = npos) const {
1939 return find_last_of(str.data(), pos, str.length());
1942 size_type find_last_of (const value_type* s, size_type pos,
1943 size_type n) const {
1944 if (!empty() && n > 0) {
1945 pos = std::min(pos, length() - 1);
1946 const_iterator i(begin() + pos);
1948 if (traits_type::find(s, n, *i) != 0) {
1951 if (i == begin()) break;
1957 size_type find_last_of (const value_type* s,
1958 size_type pos = npos) const {
1959 return find_last_of(s, pos, traits_type::length(s));
1962 size_type find_last_of (value_type c, size_type pos = npos) const {
1963 return find_last_of(&c, pos, 1);
1966 size_type find_first_not_of(const basic_fbstring& str,
1967 size_type pos = 0) const {
1968 return find_first_not_of(str.data(), pos, str.size());
1971 size_type find_first_not_of(const value_type* s, size_type pos,
1972 size_type n) const {
1973 if (pos < length()) {
1977 for (; i != finish; ++i) {
1978 if (traits_type::find(s, n, *i) == 0) {
1986 size_type find_first_not_of(const value_type* s,
1987 size_type pos = 0) const {
1988 return find_first_not_of(s, pos, traits_type::length(s));
1991 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1992 return find_first_not_of(&c, pos, 1);
1995 size_type find_last_not_of(const basic_fbstring& str,
1996 size_type pos = npos) const {
1997 return find_last_not_of(str.data(), pos, str.length());
2000 size_type find_last_not_of(const value_type* s, size_type pos,
2001 size_type n) const {
2002 if (!this->empty()) {
2003 pos = std::min(pos, size() - 1);
2004 const_iterator i(begin() + pos);
2006 if (traits_type::find(s, n, *i) == 0) {
2009 if (i == begin()) break;
2015 size_type find_last_not_of(const value_type* s,
2016 size_type pos = npos) const {
2017 return find_last_not_of(s, pos, traits_type::length(s));
2020 size_type find_last_not_of (value_type c, size_type pos = npos) const {
2021 return find_last_not_of(&c, pos, 1);
2024 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
2025 enforce(pos <= size(), std::__throw_out_of_range, "");
2026 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2029 int compare(const basic_fbstring& str) const {
2030 // FIX due to Goncalo N M de Carvalho July 18, 2005
2031 return compare(0, size(), str);
2034 int compare(size_type pos1, size_type n1,
2035 const basic_fbstring& str) const {
2036 return compare(pos1, n1, str.data(), str.size());
2039 int compare(size_type pos1, size_type n1,
2040 const value_type* s) const {
2041 return compare(pos1, n1, s, traits_type::length(s));
2044 int compare(size_type pos1, size_type n1,
2045 const value_type* s, size_type n2) const {
2046 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2047 procrustes(n1, size() - pos1);
2048 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2049 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2050 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2053 int compare(size_type pos1, size_type n1,
2054 const basic_fbstring& str,
2055 size_type pos2, size_type n2) const {
2056 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2057 return compare(pos1, n1, str.data() + pos2,
2058 std::min(n2, str.size() - pos2));
2061 // Code from Jean-Francois Bastien (03/26/2007)
2062 int compare(const value_type* s) const {
2063 // Could forward to compare(0, size(), s, traits_type::length(s))
2064 // but that does two extra checks
2065 const size_type n1(size()), n2(traits_type::length(s));
2066 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2067 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2075 // non-member functions
2077 template <typename E, class T, class A, class S>
2079 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2080 const basic_fbstring<E, T, A, S>& rhs) {
2082 basic_fbstring<E, T, A, S> result;
2083 result.reserve(lhs.size() + rhs.size());
2084 result.append(lhs).append(rhs);
2085 return std::move(result);
2089 template <typename E, class T, class A, class S>
2091 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2092 const basic_fbstring<E, T, A, S>& rhs) {
2093 return std::move(lhs.append(rhs));
2097 template <typename E, class T, class A, class S>
2099 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2100 basic_fbstring<E, T, A, S>&& rhs) {
2101 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2102 // Good, at least we don't need to reallocate
2103 return std::move(rhs.insert(0, lhs));
2105 // Meh, no go. Forward to operator+(const&, const&).
2106 auto const& rhsC = rhs;
2111 template <typename E, class T, class A, class S>
2113 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2114 basic_fbstring<E, T, A, S>&& rhs) {
2115 return std::move(lhs.append(rhs));
2118 template <typename E, class T, class A, class S>
2120 basic_fbstring<E, T, A, S> operator+(
2121 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2122 const basic_fbstring<E, T, A, S>& rhs) {
2124 basic_fbstring<E, T, A, S> result;
2125 const typename basic_fbstring<E, T, A, S>::size_type len =
2126 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2127 result.reserve(len + rhs.size());
2128 result.append(lhs, len).append(rhs);
2132 template <typename E, class T, class A, class S>
2134 basic_fbstring<E, T, A, S> operator+(
2135 typename basic_fbstring<E, T, A, S>::value_type lhs,
2136 const basic_fbstring<E, T, A, S>& rhs) {
2138 basic_fbstring<E, T, A, S> result;
2139 result.reserve(1 + rhs.size());
2140 result.push_back(lhs);
2145 template <typename E, class T, class A, class S>
2147 basic_fbstring<E, T, A, S> operator+(
2148 const basic_fbstring<E, T, A, S>& lhs,
2149 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2151 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2152 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2154 basic_fbstring<E, T, A, S> result;
2155 const size_type len = traits_type::length(rhs);
2156 result.reserve(lhs.size() + len);
2157 result.append(lhs).append(rhs, len);
2161 template <typename E, class T, class A, class S>
2163 basic_fbstring<E, T, A, S> operator+(
2164 const basic_fbstring<E, T, A, S>& lhs,
2165 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2167 basic_fbstring<E, T, A, S> result;
2168 result.reserve(lhs.size() + 1);
2170 result.push_back(rhs);
2174 template <typename E, class T, class A, class S>
2176 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2177 const basic_fbstring<E, T, A, S>& rhs) {
2178 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2180 template <typename E, class T, class A, class S>
2182 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2183 const basic_fbstring<E, T, A, S>& rhs) {
2184 return rhs == lhs; }
2186 template <typename E, class T, class A, class S>
2188 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2189 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2190 return lhs.compare(rhs) == 0; }
2192 template <typename E, class T, class A, class S>
2194 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2195 const basic_fbstring<E, T, A, S>& rhs) {
2196 return !(lhs == rhs); }
2198 template <typename E, class T, class A, class S>
2200 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2201 const basic_fbstring<E, T, A, S>& rhs) {
2202 return !(lhs == rhs); }
2204 template <typename E, class T, class A, class S>
2206 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2207 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2208 return !(lhs == rhs); }
2210 template <typename E, class T, class A, class S>
2212 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2213 const basic_fbstring<E, T, A, S>& rhs) {
2214 return lhs.compare(rhs) < 0; }
2216 template <typename E, class T, class A, class S>
2218 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2219 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2220 return lhs.compare(rhs) < 0; }
2222 template <typename E, class T, class A, class S>
2224 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2225 const basic_fbstring<E, T, A, S>& rhs) {
2226 return rhs.compare(lhs) > 0; }
2228 template <typename E, class T, class A, class S>
2230 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2231 const basic_fbstring<E, T, A, S>& rhs) {
2234 template <typename E, class T, class A, class S>
2236 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2237 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2240 template <typename E, class T, class A, class S>
2242 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2243 const basic_fbstring<E, T, A, S>& rhs) {
2246 template <typename E, class T, class A, class S>
2248 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2249 const basic_fbstring<E, T, A, S>& rhs) {
2250 return !(rhs < lhs); }
2252 template <typename E, class T, class A, class S>
2254 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2255 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2256 return !(rhs < lhs); }
2258 template <typename E, class T, class A, class S>
2260 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2261 const basic_fbstring<E, T, A, S>& rhs) {
2262 return !(rhs < lhs); }
2264 template <typename E, class T, class A, class S>
2266 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2267 const basic_fbstring<E, T, A, S>& rhs) {
2268 return !(lhs < rhs); }
2270 template <typename E, class T, class A, class S>
2272 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2273 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2274 return !(lhs < rhs); }
2276 template <typename E, class T, class A, class S>
2278 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2279 const basic_fbstring<E, T, A, S>& rhs) {
2280 return !(lhs < rhs);
2284 template <typename E, class T, class A, class S>
2285 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2289 // TODO: make this faster.
2290 template <typename E, class T, class A, class S>
2293 typename basic_fbstring<E, T, A, S>::value_type,
2294 typename basic_fbstring<E, T, A, S>::traits_type>&
2296 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2297 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2298 basic_fbstring<E, T, A, S>& str) {
2299 typename std::basic_istream<E, T>::sentry sentry(is);
2300 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2301 typename basic_fbstring<E, T, A, S>::traits_type>
2303 typedef typename __istream_type::ios_base __ios_base;
2304 size_t extracted = 0;
2305 auto err = __ios_base::goodbit;
2307 auto n = is.width();
2312 auto got = is.rdbuf()->sgetc();
2313 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2314 // Whew. We get to store this guy
2316 got = is.rdbuf()->snextc();
2318 if (got == T::eof()) {
2319 err |= __ios_base::eofbit;
2324 err |= __ios_base::failbit;
2332 template <typename E, class T, class A, class S>
2334 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2335 typename basic_fbstring<E, T, A, S>::traits_type>&
2337 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2338 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2339 const basic_fbstring<E, T, A, S>& str) {
2341 typename std::basic_ostream<
2342 typename basic_fbstring<E, T, A, S>::value_type,
2343 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2345 typedef std::ostreambuf_iterator<
2346 typename basic_fbstring<E, T, A, S>::value_type,
2347 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2348 size_t __len = str.size();
2350 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2351 if (__pad_and_output(_Ip(os),
2353 __left ? str.data() + __len : str.data(),
2356 os.fill()).failed()) {
2357 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2361 std::__ostream_insert(os, str.data(), str.size());
2366 #ifndef _LIBSTDCXX_FBSTRING
2368 template <typename E, class T, class A, class S>
2370 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2371 typename basic_fbstring<E, T, A, S>::traits_type>&
2373 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2374 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2375 basic_fbstring<E, T, A, S>& str,
2376 typename basic_fbstring<E, T, A, S>::value_type delim) {
2377 // Use the nonstandard getdelim()
2378 char * buf = nullptr;
2381 // This looks quadratic but it really depends on realloc
2382 auto const newSize = size + 128;
2383 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2384 is.getline(buf + size, newSize - size, delim);
2385 if (is.bad() || is.eof() || !is.fail()) {
2386 // done by either failure, end of file, or normal read
2387 size += std::strlen(buf + size);
2390 // Here we have failed due to too short a buffer
2391 // Minus one to discount the terminating '\0'
2393 assert(buf[size] == 0);
2394 // Clear the error so we can continue reading
2397 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2398 AcquireMallocatedString());
2403 template <typename E, class T, class A, class S>
2405 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2406 typename basic_fbstring<E, T, A, S>::traits_type>&
2408 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2409 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2410 basic_fbstring<E, T, A, S>& str) {
2411 // Just forward to the version with a delimiter
2412 return getline(is, str, '\n');
2417 template <typename E1, class T, class A, class S>
2418 const typename basic_fbstring<E1, T, A, S>::size_type
2419 basic_fbstring<E1, T, A, S>::npos =
2420 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2422 #ifndef _LIBSTDCXX_FBSTRING
2423 // basic_string compatibility routines
2425 template <typename E, class T, class A, class S>
2427 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2428 const std::string& rhs) {
2429 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2432 template <typename E, class T, class A, class S>
2434 bool operator==(const std::string& lhs,
2435 const basic_fbstring<E, T, A, S>& rhs) {
2439 template <typename E, class T, class A, class S>
2441 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2442 const std::string& rhs) {
2443 return !(lhs == rhs);
2446 template <typename E, class T, class A, class S>
2448 bool operator!=(const std::string& lhs,
2449 const basic_fbstring<E, T, A, S>& rhs) {
2450 return !(lhs == rhs);
2453 #if !defined(_LIBSTDCXX_FBSTRING)
2454 typedef basic_fbstring<char> fbstring;
2457 // fbstring is relocatable
2458 template <class T, class R, class A, class S>
2459 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2462 _GLIBCXX_END_NAMESPACE_VERSION
2465 } // namespace folly
2467 #ifndef _LIBSTDCXX_FBSTRING
2469 // Hash functions to make fbstring usable with e.g. hash_map
2471 // Handle interaction with different C++ standard libraries, which
2472 // expect these types to be in different namespaces.
2476 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2477 size_t operator()(const folly::basic_fbstring<C> & s) const {
2478 return hash<const C*>::operator()(s.c_str());
2483 struct hash< ::folly::fbstring> {
2484 size_t operator()(const ::folly::fbstring& s) const {
2485 return ::folly::hash::fnv32_buf(s.data(), s.size());
2491 #if FOLLY_HAVE_DEPRECATED_ASSOC
2492 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2493 namespace __gnu_cxx {
2496 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2497 size_t operator()(const folly::basic_fbstring<C> & s) const {
2498 return hash<const C*>::operator()(s.c_str());
2503 struct hash< ::folly::fbstring> {
2504 size_t operator()(const ::folly::fbstring& s) const {
2505 return ::folly::hash::fnv32_buf(s.data(), s.size());
2510 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2511 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2513 #endif // _LIBSTDCXX_FBSTRING
2515 #pragma GCC diagnostic pop
2517 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2519 #undef FBSTRING_LIKELY
2520 #undef FBSTRING_UNLIKELY
2522 #endif // FOLLY_BASE_FBSTRING_H_