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 #ifdef _GLIBCXX_SYMVER
104 #include <ext/hash_set>
105 #include <ext/hash_map>
110 // We defined these here rather than including Likely.h to avoid
111 // redefinition errors when fbstring is imported into libstdc++.
112 #if defined(__GNUC__) && __GNUC__ >= 4
113 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
114 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
116 #define FBSTRING_LIKELY(x) (x)
117 #define FBSTRING_UNLIKELY(x) (x)
120 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
121 #pragma GCC diagnostic push
122 #pragma GCC diagnostic ignored "-Wshadow"
124 // FBString cannot use throw when replacing std::string, though it may still
125 // use std::__throw_*
126 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
128 #ifdef _LIBSTDCXX_FBSTRING
129 namespace std _GLIBCXX_VISIBILITY(default) {
130 _GLIBCXX_BEGIN_NAMESPACE_VERSION
135 // Different versions of gcc/clang support different versions of
136 // the address sanitizer attribute. Unfortunately, this attribute
137 // has issues when inlining is used, so disable that as well.
138 #if defined(__clang__)
139 # if __has_feature(address_sanitizer)
140 # if __has_attribute(__no_address_safety_analysis__)
141 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
142 __attribute__((__no_address_safety_analysis__, __noinline__))
143 # elif __has_attribute(__no_sanitize_address__)
144 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
145 __attribute__((__no_sanitize_address__, __noinline__))
148 #elif defined (__GNUC__) && \
150 (__GNUC_MINOR__ >= 8) && \
152 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
153 __attribute__((__no_address_safety_analysis__, __noinline__))
155 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
156 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
159 namespace fbstring_detail {
161 template <class InIt, class OutIt>
164 typename std::iterator_traits<InIt>::difference_type n,
166 for (; n != 0; --n, ++b, ++d) {
172 template <class Pod, class T>
173 inline void pod_fill(Pod* b, Pod* e, T c) {
174 assert(b && e && b <= e);
175 /*static*/ if (sizeof(T) == 1) {
178 auto const ee = b + ((e - b) & ~7u);
179 for (; b != ee; b += 8) {
190 for (; b != e; ++b) {
197 * Lightly structured memcpy, simplifies copying PODs and introduces
198 * some asserts. Unfortunately using this function may cause
199 * measurable overhead (presumably because it adjusts from a begin/end
200 * convention to a pointer/size convention, so it does some extra
201 * arithmetic even though the caller might have done the inverse
202 * adaptation outside).
205 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
207 assert(d >= e || d + (e - b) <= b);
208 memcpy(d, b, (e - b) * sizeof(Pod));
212 * Lightly structured memmove, simplifies copying PODs and introduces
216 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
218 memmove(d, b, (e - b) * sizeof(*b));
221 } // namespace fbstring_detail
224 * Defines a special acquisition method for constructing fbstring
225 * objects. AcquireMallocatedString means that the user passes a
226 * pointer to a malloc-allocated string that the fbstring object will
229 enum class AcquireMallocatedString {};
232 * fbstring_core_model is a mock-up type that defines all required
233 * signatures of a fbstring core. The fbstring class itself uses such
234 * a core object to implement all of the numerous member functions
235 * required by the standard.
237 * If you want to define a new core, copy the definition below and
238 * implement the primitives. Then plug the core into basic_fbstring as
239 * a template argument.
241 template <class Char>
242 class fbstring_core_model {
244 fbstring_core_model();
245 fbstring_core_model(const fbstring_core_model &);
246 ~fbstring_core_model();
247 // Returns a pointer to string's buffer (currently only contiguous
248 // strings are supported). The pointer is guaranteed to be valid
249 // until the next call to a non-const member function.
250 const Char * data() const;
251 // Much like data(), except the string is prepared to support
252 // character-level changes. This call is a signal for
253 // e.g. reference-counted implementation to fork the data. The
254 // pointer is guaranteed to be valid until the next call to a
255 // non-const member function.
256 Char * mutable_data();
257 // Returns a pointer to string's buffer and guarantees that a
258 // readable '\0' lies right after the buffer. The pointer is
259 // guaranteed to be valid until the next call to a non-const member
261 const Char * c_str() const;
262 // Shrinks the string by delta characters. Asserts that delta <=
264 void shrink(size_t delta);
265 // Expands the string by delta characters (i.e. after this call
266 // size() will report the old size() plus delta) but without
267 // initializing the expanded region. Returns a pointer to the memory
268 // to be initialized (the beginning of the expanded portion). The
269 // caller is expected to fill the expanded area appropriately.
270 Char* expand_noinit(size_t delta);
271 // Expands the string by one character and sets the last character
273 void push_back(Char c);
274 // Returns the string's size.
276 // Returns the string's capacity, i.e. maximum size that the string
277 // can grow to without reallocation. Note that for reference counted
278 // strings that's technically a lie - even assigning characters
279 // within the existing size would cause a reallocation.
280 size_t capacity() const;
281 // Returns true if the data underlying the string is actually shared
282 // across multiple strings (in a refcounted fashion).
283 bool isShared() const;
284 // Makes sure that at least minCapacity characters are available for
285 // the string without reallocation. For reference-counted strings,
286 // it should fork the data even if minCapacity < size().
287 void reserve(size_t minCapacity);
290 fbstring_core_model& operator=(const fbstring_core_model &);
295 * gcc-4.7 throws what appears to be some false positive uninitialized
296 * warnings for the members of the MediumLarge struct. So, mute them here.
298 #if defined(__GNUC__) && !defined(__clang__)
299 # pragma GCC diagnostic push
300 # pragma GCC diagnostic ignored "-Wuninitialized"
304 * This is the core of the string. The code should work on 32- and
305 * 64-bit architectures and with any Char size. Porting to big endian
306 * architectures would require some changes.
308 * The storage is selected as follows (assuming we store one-byte
309 * characters on a 64-bit machine): (a) "small" strings between 0 and
310 * 23 chars are stored in-situ without allocation (the rightmost byte
311 * stores the size); (b) "medium" strings from 24 through 254 chars
312 * are stored in malloc-allocated memory that is copied eagerly; (c)
313 * "large" strings of 255 chars and above are stored in a similar
314 * structure as medium arrays, except that the string is
315 * reference-counted and copied lazily. the reference count is
316 * allocated right before the character array.
318 * The discriminator between these three strategies sits in the two
319 * most significant bits of the rightmost char of the storage. If
320 * neither is set, then the string is small (and its length sits in
321 * the lower-order bits of that rightmost character). If the MSb is
322 * set, the string is medium width. If the second MSb is set, then the
325 template <class Char> class fbstring_core {
327 fbstring_core() noexcept {
328 // Only initialize the tag, will set the MSBs (i.e. the small
329 // string size) to zero too
330 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
331 // or: setSmallSize(0);
333 assert(category() == isSmall && size() == 0);
336 fbstring_core(const fbstring_core & rhs) {
337 assert(&rhs != this);
338 // Simplest case first: small strings are bitblitted
339 if (rhs.category() == isSmall) {
340 assert(offsetof(MediumLarge, data_) == 0);
341 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
342 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
343 const size_t size = rhs.smallSize();
345 ml_.capacity_ = rhs.ml_.capacity_;
348 // Just write the whole thing, don't look at details. In
349 // particular we need to copy capacity anyway because we want
350 // to set the size (don't forget that the last character,
351 // which stores a short string's length, is shared with the
352 // ml_.capacity field).
355 assert(category() == isSmall && this->size() == rhs.size());
356 } else if (rhs.category() == isLarge) {
357 // Large strings are just refcounted
359 RefCounted::incrementRefs(ml_.data_);
360 assert(category() == isLarge && size() == rhs.size());
362 // Medium strings are copied eagerly. Don't forget to allocate
363 // one extra Char for the null terminator.
364 auto const allocSize =
365 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
366 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
367 fbstring_detail::pod_copy(rhs.ml_.data_,
369 rhs.ml_.data_ + rhs.ml_.size_ + 1,
371 // No need for writeTerminator() here, we copied one extra
372 // element just above.
373 ml_.size_ = rhs.ml_.size_;
374 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
375 assert(category() == isMedium);
377 assert(size() == rhs.size());
378 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
381 fbstring_core(fbstring_core&& goner) noexcept {
382 if (goner.category() == isSmall) {
383 // Just copy, leave the goner in peace
384 new(this) fbstring_core(goner.small_, goner.smallSize());
388 // Clean goner's carcass
389 goner.setSmallSize(0);
393 // NOTE(agallagher): The word-aligned copy path copies bytes which are
394 // outside the range of the string, and makes address sanitizer unhappy,
395 // so just disable it on this function.
396 fbstring_core(const Char *const data, const size_t size)
397 FBSTRING_DISABLE_ADDRESS_SANITIZER {
398 // Simplest case first: small strings are bitblitted
399 if (size <= maxSmallSize) {
400 // Layout is: Char* data_, size_t size_, size_t capacity_
401 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
402 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
403 // sizeof(size_t) must be a power of 2
404 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
406 // If data is aligned, use fast word-wise copying. Otherwise,
407 // use conservative memcpy.
408 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
409 fbstring_detail::pod_copy(data, data + size, small_);
411 // Copy one word (64 bits) at a time
412 const size_t byteSize = size * sizeof(Char);
413 if (byteSize > 2 * sizeof(size_t)) {
415 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
417 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
419 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
420 } else if (byteSize > sizeof(size_t)) {
423 } else if (size > 0) {
429 } else if (size <= maxMediumSize) {
430 // Medium strings are allocated normally. Don't forget to
431 // allocate one extra Char for the terminating null.
432 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
433 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
434 fbstring_detail::pod_copy(data, data + size, ml_.data_);
436 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
438 // Large strings are allocated differently
439 size_t effectiveCapacity = size;
440 auto const newRC = RefCounted::create(data, & effectiveCapacity);
441 ml_.data_ = newRC->data_;
443 ml_.capacity_ = effectiveCapacity | isLarge;
446 assert(this->size() == size);
447 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
450 ~fbstring_core() noexcept {
451 auto const c = category();
459 RefCounted::decrementRefs(ml_.data_);
462 // Snatches a previously mallocated string. The parameter "size"
463 // is the size of the string, and the parameter "allocatedSize"
464 // is the size of the mallocated block. The string must be
465 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
467 // So if you want a 2-character string, pass malloc(3) as "data",
468 // pass 2 as "size", and pass 3 as "allocatedSize".
469 fbstring_core(Char * const data,
471 const size_t allocatedSize,
472 AcquireMallocatedString) {
474 assert(allocatedSize >= size + 1);
475 assert(data[size] == '\0');
476 // Use the medium string storage
479 // Don't forget about null terminator
480 ml_.capacity_ = (allocatedSize - 1) | isMedium;
482 // No need for the memory
488 // swap below doesn't test whether &rhs == this (and instead
489 // potentially does extra work) on the premise that the rarity of
490 // that situation actually makes the check more expensive than is
492 void swap(fbstring_core & rhs) {
498 // In C++11 data() and c_str() are 100% equivalent.
499 const Char * data() const {
503 Char * mutable_data() {
504 auto const c = category();
508 assert(c == isMedium || c == isLarge);
509 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
511 size_t effectiveCapacity = ml_.capacity();
512 auto const newRC = RefCounted::create(& effectiveCapacity);
513 // If this fails, someone placed the wrong capacity in an
515 assert(effectiveCapacity >= ml_.capacity());
516 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
518 RefCounted::decrementRefs(ml_.data_);
519 ml_.data_ = newRC->data_;
520 // No need to call writeTerminator(), we have + 1 above.
525 const Char * c_str() const {
526 auto const c = category();
527 #ifdef FBSTRING_PERVERSE
529 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
530 || small_[smallSize()] == '\0');
531 small_[smallSize()] = '\0';
534 assert(c == isMedium || c == isLarge);
535 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
536 ml_.data_[ml_.size_] = '\0';
537 #elif defined(FBSTRING_CONSERVATIVE)
539 assert(small_[smallSize()] == '\0');
542 assert(c == isMedium || c == isLarge);
543 assert(ml_.data_[ml_.size_] == '\0');
546 small_[smallSize()] = '\0';
549 assert(c == isMedium || c == isLarge);
550 ml_.data_[ml_.size_] = '\0';
555 void shrink(const size_t delta) {
556 if (category() == isSmall) {
557 // Check for underflow
558 assert(delta <= smallSize());
559 setSmallSize(smallSize() - delta);
560 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
561 // Medium strings and unique large strings need no special
563 assert(ml_.size_ >= delta);
566 assert(ml_.size_ >= delta);
567 // Shared large string, must make unique. This is because of the
568 // durn terminator must be written, which may trample the shared
571 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
573 // No need to write the terminator.
579 void reserve(size_t minCapacity) {
580 if (category() == isLarge) {
582 if (RefCounted::refs(ml_.data_) > 1) {
583 // We must make it unique regardless; in-place reallocation is
584 // useless if the string is shared. In order to not surprise
585 // people, reserve the new block at current capacity or
586 // more. That way, a string's capacity never shrinks after a
588 minCapacity = std::max(minCapacity, ml_.capacity());
589 auto const newRC = RefCounted::create(& minCapacity);
590 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
592 // Done with the old data. No need to call writeTerminator(),
593 // we have + 1 above.
594 RefCounted::decrementRefs(ml_.data_);
595 ml_.data_ = newRC->data_;
596 ml_.capacity_ = minCapacity | isLarge;
597 // size remains unchanged
599 // String is not shared, so let's try to realloc (if needed)
600 if (minCapacity > ml_.capacity()) {
601 // Asking for more memory
603 RefCounted::reallocate(ml_.data_, ml_.size_,
604 ml_.capacity(), minCapacity);
605 ml_.data_ = newRC->data_;
606 ml_.capacity_ = minCapacity | isLarge;
609 assert(capacity() >= minCapacity);
611 } else if (category() == isMedium) {
612 // String is not shared
613 if (minCapacity <= ml_.capacity()) {
614 return; // nothing to do, there's enough room
616 if (minCapacity <= maxMediumSize) {
617 // Keep the string at medium size. Don't forget to allocate
618 // one extra Char for the terminating null.
619 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
620 ml_.data_ = static_cast<Char *>(
623 ml_.size_ * sizeof(Char),
624 (ml_.capacity() + 1) * sizeof(Char),
627 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
629 // Conversion from medium to large string
630 fbstring_core nascent;
631 // Will recurse to another branch of this function
632 nascent.reserve(minCapacity);
633 nascent.ml_.size_ = ml_.size_;
634 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
638 assert(capacity() >= minCapacity);
641 assert(category() == isSmall);
642 if (minCapacity > maxMediumSize) {
644 auto const newRC = RefCounted::create(& minCapacity);
645 auto const size = smallSize();
646 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
647 // No need for writeTerminator(), we wrote it above with + 1.
648 ml_.data_ = newRC->data_;
650 ml_.capacity_ = minCapacity | isLarge;
651 assert(capacity() >= minCapacity);
652 } else if (minCapacity > maxSmallSize) {
654 // Don't forget to allocate one extra Char for the terminating null
655 auto const allocSizeBytes =
656 goodMallocSize((1 + minCapacity) * sizeof(Char));
657 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
658 auto const size = smallSize();
659 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
660 // No need for writeTerminator(), we wrote it above with + 1.
663 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
666 // Nothing to do, everything stays put
669 assert(capacity() >= minCapacity);
672 Char * expand_noinit(const size_t delta) {
673 // Strategy is simple: make room, then change size
674 assert(capacity() >= size());
676 if (category() == isSmall) {
679 if (newSz <= maxSmallSize) {
687 newSz = ml_.size_ + delta;
688 if (newSz > capacity()) {
692 assert(capacity() >= newSz);
693 // Category can't be small - we took care of that above
694 assert(category() == isMedium || category() == isLarge);
697 assert(size() == newSz);
698 return ml_.data_ + sz;
701 void push_back(Char c) {
702 assert(capacity() >= size());
704 if (category() == isSmall) {
706 if (sz < maxSmallSize) {
707 setSmallSize(sz + 1);
712 reserve(maxSmallSize * 2);
715 if (sz == capacity()) { // always true for isShared()
716 reserve(1 + sz * 3 / 2); // ensures not shared
720 assert(capacity() >= sz + 1);
721 // Category can't be small - we took care of that above
722 assert(category() == isMedium || category() == isLarge);
728 size_t size() const {
729 return category() == isSmall ? smallSize() : ml_.size_;
732 size_t capacity() const {
733 switch (category()) {
737 // For large-sized strings, a multi-referenced chunk has no
738 // available capacity. This is because any attempt to append
739 // data would trigger a new allocation.
740 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
743 return ml_.capacity();
746 bool isShared() const {
747 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
750 #ifdef FBSTRING_PERVERSE
751 enum { TERMINATOR = '^' };
753 enum { TERMINATOR = '\0' };
756 void writeTerminator() {
757 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
758 if (category() == isSmall) {
759 const auto s = smallSize();
760 if (s != maxSmallSize) {
761 small_[s] = TERMINATOR;
764 ml_.data_[ml_.size_] = TERMINATOR;
771 fbstring_core & operator=(const fbstring_core & rhs);
778 size_t capacity() const {
779 return capacity_ & capacityExtractMask;
784 std::atomic<size_t> refCount_;
787 static RefCounted * fromData(Char * p) {
788 return static_cast<RefCounted*>(
790 static_cast<unsigned char*>(static_cast<void*>(p))
791 - sizeof(refCount_)));
794 static size_t refs(Char * p) {
795 return fromData(p)->refCount_.load(std::memory_order_acquire);
798 static void incrementRefs(Char * p) {
799 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
802 static void decrementRefs(Char * p) {
803 auto const dis = fromData(p);
804 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
811 static RefCounted * create(size_t * size) {
812 // Don't forget to allocate one extra Char for the terminating
813 // null. In this case, however, one Char is already part of the
815 const size_t allocSize = goodMallocSize(
816 sizeof(RefCounted) + *size * sizeof(Char));
817 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
818 result->refCount_.store(1, std::memory_order_release);
819 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
823 static RefCounted * create(const Char * data, size_t * size) {
824 const size_t effectiveSize = *size;
825 auto result = create(size);
826 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
830 static RefCounted * reallocate(Char *const data,
831 const size_t currentSize,
832 const size_t currentCapacity,
833 const size_t newCapacity) {
834 assert(newCapacity > 0 && newCapacity > currentSize);
835 auto const dis = fromData(data);
836 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
837 // Don't forget to allocate one extra Char for the terminating
838 // null. In this case, however, one Char is already part of the
840 auto result = static_cast<RefCounted*>(
842 sizeof(RefCounted) + currentSize * sizeof(Char),
843 sizeof(RefCounted) + currentCapacity * sizeof(Char),
844 sizeof(RefCounted) + newCapacity * sizeof(Char)));
845 assert(result->refCount_.load(std::memory_order_acquire) == 1);
851 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
852 mutable MediumLarge ml_;
856 lastChar = sizeof(MediumLarge) - 1,
857 maxSmallSize = lastChar / sizeof(Char),
858 maxMediumSize = 254 / sizeof(Char), // coincides with the small
859 // bin size in dlmalloc
860 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
861 capacityExtractMask = ~categoryExtractMask,
863 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
864 "Corrupt memory layout for fbstring.");
868 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
869 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
872 Category category() const {
873 // Assumes little endian
874 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
877 size_t smallSize() const {
878 assert(category() == isSmall &&
879 static_cast<size_t>(small_[maxSmallSize])
880 <= static_cast<size_t>(maxSmallSize));
881 return static_cast<size_t>(maxSmallSize)
882 - static_cast<size_t>(small_[maxSmallSize]);
885 void setSmallSize(size_t s) {
886 // Warning: this should work with uninitialized strings too,
887 // so don't assume anything about the previous value of
888 // small_[maxSmallSize].
889 assert(s <= maxSmallSize);
890 small_[maxSmallSize] = maxSmallSize - s;
894 #if defined(__GNUC__) && !defined(__clang__)
895 # pragma GCC diagnostic pop
898 #ifndef _LIBSTDCXX_FBSTRING
900 * Dummy fbstring core that uses an actual std::string. This doesn't
901 * make any sense - it's just for testing purposes.
903 template <class Char>
904 class dummy_fbstring_core {
906 dummy_fbstring_core() {
908 dummy_fbstring_core(const dummy_fbstring_core& another)
909 : backend_(another.backend_) {
911 dummy_fbstring_core(const Char * s, size_t n)
914 void swap(dummy_fbstring_core & rhs) {
915 backend_.swap(rhs.backend_);
917 const Char * data() const {
918 return backend_.data();
920 Char * mutable_data() {
921 //assert(!backend_.empty());
922 return &*backend_.begin();
924 void shrink(size_t delta) {
925 assert(delta <= size());
926 backend_.resize(size() - delta);
928 Char * expand_noinit(size_t delta) {
929 auto const sz = size();
930 backend_.resize(size() + delta);
931 return backend_.data() + sz;
933 void push_back(Char c) {
934 backend_.push_back(c);
936 size_t size() const {
937 return backend_.size();
939 size_t capacity() const {
940 return backend_.capacity();
942 bool isShared() const {
945 void reserve(size_t minCapacity) {
946 backend_.reserve(minCapacity);
950 std::basic_string<Char> backend_;
952 #endif // !_LIBSTDCXX_FBSTRING
955 * This is the basic_string replacement. For conformity,
956 * basic_fbstring takes the same template parameters, plus the last
957 * one which is the core.
959 #ifdef _LIBSTDCXX_FBSTRING
960 template <typename E, class T, class A, class Storage>
962 template <typename E,
963 class T = std::char_traits<E>,
964 class A = std::allocator<E>,
965 class Storage = fbstring_core<E> >
967 class basic_fbstring {
971 void (*throw_exc)(const char*),
973 if (!condition) throw_exc(msg);
976 bool isSane() const {
979 empty() == (size() == 0) &&
980 empty() == (begin() == end()) &&
981 size() <= max_size() &&
982 capacity() <= max_size() &&
983 size() <= capacity() &&
984 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
988 friend struct Invariant;
991 explicit Invariant(const basic_fbstring& s) : s_(s) {
998 const basic_fbstring& s_;
1000 explicit Invariant(const basic_fbstring&) {}
1002 Invariant& operator=(const Invariant&);
1007 typedef T traits_type;
1008 typedef typename traits_type::char_type value_type;
1009 typedef A allocator_type;
1010 typedef typename A::size_type size_type;
1011 typedef typename A::difference_type difference_type;
1013 typedef typename A::reference reference;
1014 typedef typename A::const_reference const_reference;
1015 typedef typename A::pointer pointer;
1016 typedef typename A::const_pointer const_pointer;
1018 typedef E* iterator;
1019 typedef const E* const_iterator;
1020 typedef std::reverse_iterator<iterator
1021 #ifdef NO_ITERATOR_TRAITS
1025 typedef std::reverse_iterator<const_iterator
1026 #ifdef NO_ITERATOR_TRAITS
1029 > const_reverse_iterator;
1031 static const size_type npos; // = size_type(-1)
1034 static void procrustes(size_type& n, size_type nmax) {
1035 if (n > nmax) n = nmax;
1039 // C++11 21.4.2 construct/copy/destroy
1040 explicit basic_fbstring(const A& a = A()) noexcept {
1043 basic_fbstring(const basic_fbstring& str)
1044 : store_(str.store_) {
1048 basic_fbstring(basic_fbstring&& goner) noexcept
1049 : store_(std::move(goner.store_)) {
1052 #ifndef _LIBSTDCXX_FBSTRING
1053 // This is defined for compatibility with std::string
1054 /* implicit */ basic_fbstring(const std::string& str)
1055 : store_(str.data(), str.size()) {
1059 basic_fbstring(const basic_fbstring& str, size_type pos,
1060 size_type n = npos, const A& a = A()) {
1061 assign(str, pos, n);
1064 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1066 ? traits_type::length(s)
1068 std::__throw_logic_error(
1069 "basic_fbstring: null pointer initializer not valid");
1074 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1078 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1079 auto const data = store_.expand_noinit(n);
1080 fbstring_detail::pod_fill(data, data + n, c);
1081 store_.writeTerminator();
1084 template <class InIt>
1085 basic_fbstring(InIt begin, InIt end,
1086 typename std::enable_if<
1087 !std::is_same<typename std::remove_const<InIt>::type,
1088 value_type*>::value, const A>::type & a = A()) {
1092 // Specialization for const char*, const char*
1093 basic_fbstring(const value_type* b, const value_type* e)
1094 : store_(b, e - b) {
1097 // Nonstandard constructor
1098 basic_fbstring(value_type *s, size_type n, size_type c,
1099 AcquireMallocatedString a)
1100 : store_(s, n, c, a) {
1103 // Construction from initialization list
1104 basic_fbstring(std::initializer_list<value_type> il) {
1105 assign(il.begin(), il.end());
1108 ~basic_fbstring() noexcept {
1111 basic_fbstring& operator=(const basic_fbstring& lhs) {
1112 if (FBSTRING_UNLIKELY(&lhs == this)) {
1115 auto const oldSize = size();
1116 auto const srcSize = lhs.size();
1117 if (capacity() >= srcSize && !store_.isShared()) {
1118 // great, just copy the contents
1119 if (oldSize < srcSize)
1120 store_.expand_noinit(srcSize - oldSize);
1122 store_.shrink(oldSize - srcSize);
1123 assert(size() == srcSize);
1124 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1125 store_.writeTerminator();
1127 // need to reallocate, so we may as well create a brand new string
1128 basic_fbstring(lhs).swap(*this);
1134 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1135 if (FBSTRING_UNLIKELY(&goner == this)) {
1136 // Compatibility with std::basic_string<>,
1137 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1140 // No need of this anymore
1141 this->~basic_fbstring();
1142 // Move the goner into this
1143 new(&store_) fbstring_core<E>(std::move(goner.store_));
1147 #ifndef _LIBSTDCXX_FBSTRING
1148 // Compatibility with std::string
1149 basic_fbstring & operator=(const std::string & rhs) {
1150 return assign(rhs.data(), rhs.size());
1153 // Compatibility with std::string
1154 std::string toStdString() const {
1155 return std::string(data(), size());
1158 // A lot of code in fbcode still uses this method, so keep it here for now.
1159 const basic_fbstring& toStdString() const {
1164 basic_fbstring& operator=(const value_type* s) {
1168 basic_fbstring& operator=(value_type c) {
1170 store_.expand_noinit(1);
1171 } else if (store_.isShared()) {
1172 basic_fbstring(1, c).swap(*this);
1175 store_.shrink(size() - 1);
1177 *store_.mutable_data() = c;
1178 store_.writeTerminator();
1182 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1183 return assign(il.begin(), il.end());
1186 // C++11 21.4.3 iterators:
1187 iterator begin() { return store_.mutable_data(); }
1189 const_iterator begin() const { return store_.data(); }
1191 const_iterator cbegin() const { return begin(); }
1194 return store_.mutable_data() + store_.size();
1197 const_iterator end() const {
1198 return store_.data() + store_.size();
1201 const_iterator cend() const { return end(); }
1203 reverse_iterator rbegin() {
1204 return reverse_iterator(end());
1207 const_reverse_iterator rbegin() const {
1208 return const_reverse_iterator(end());
1211 const_reverse_iterator crbegin() const { return rbegin(); }
1213 reverse_iterator rend() {
1214 return reverse_iterator(begin());
1217 const_reverse_iterator rend() const {
1218 return const_reverse_iterator(begin());
1221 const_reverse_iterator crend() const { return rend(); }
1224 // C++11 21.4.5, element access:
1225 const value_type& front() const { return *begin(); }
1226 const value_type& back() const {
1228 // Should be begin()[size() - 1], but that branches twice
1229 return *(end() - 1);
1231 value_type& front() { return *begin(); }
1232 value_type& back() {
1234 // Should be begin()[size() - 1], but that branches twice
1235 return *(end() - 1);
1242 // C++11 21.4.4 capacity:
1243 size_type size() const { return store_.size(); }
1245 size_type length() const { return size(); }
1247 size_type max_size() const {
1248 return std::numeric_limits<size_type>::max();
1251 void resize(const size_type n, const value_type c = value_type()) {
1252 auto size = this->size();
1254 store_.shrink(size - n);
1256 // Do this in two steps to minimize slack memory copied (see
1258 auto const capacity = this->capacity();
1259 assert(capacity >= size);
1260 if (size < capacity) {
1261 auto delta = std::min(n, capacity) - size;
1262 store_.expand_noinit(delta);
1263 fbstring_detail::pod_fill(begin() + size, end(), c);
1266 store_.writeTerminator();
1271 auto const delta = n - size;
1272 store_.expand_noinit(delta);
1273 fbstring_detail::pod_fill(end() - delta, end(), c);
1274 store_.writeTerminator();
1276 assert(this->size() == n);
1279 size_type capacity() const { return store_.capacity(); }
1281 void reserve(size_type res_arg = 0) {
1282 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1283 store_.reserve(res_arg);
1286 void shrink_to_fit() {
1287 // Shrink only if slack memory is sufficiently large
1288 if (capacity() < size() * 3 / 2) {
1291 basic_fbstring(cbegin(), cend()).swap(*this);
1294 void clear() { resize(0); }
1296 bool empty() const { return size() == 0; }
1298 // C++11 21.4.5 element access:
1299 const_reference operator[](size_type pos) const {
1300 return *(c_str() + pos);
1303 reference operator[](size_type pos) {
1304 if (pos == size()) {
1305 // Just call c_str() to make sure '\0' is present
1308 return *(begin() + pos);
1311 const_reference at(size_type n) const {
1312 enforce(n <= size(), std::__throw_out_of_range, "");
1316 reference at(size_type n) {
1317 enforce(n < size(), std::__throw_out_of_range, "");
1321 // C++11 21.4.6 modifiers:
1322 basic_fbstring& operator+=(const basic_fbstring& str) {
1326 basic_fbstring& operator+=(const value_type* s) {
1330 basic_fbstring& operator+=(const value_type c) {
1335 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1340 basic_fbstring& append(const basic_fbstring& str) {
1342 auto desiredSize = size() + str.size();
1344 append(str.data(), str.size());
1345 assert(size() == desiredSize);
1349 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1351 const size_type sz = str.size();
1352 enforce(pos <= sz, std::__throw_out_of_range, "");
1353 procrustes(n, sz - pos);
1354 return append(str.data() + pos, n);
1357 basic_fbstring& append(const value_type* s, size_type n) {
1359 Invariant checker(*this);
1362 if (FBSTRING_UNLIKELY(!n)) {
1363 // Unlikely but must be done
1366 auto const oldSize = size();
1367 auto const oldData = data();
1368 // Check for aliasing (rare). We could use "<=" here but in theory
1369 // those do not work for pointers unless the pointers point to
1370 // elements in the same array. For that reason we use
1371 // std::less_equal, which is guaranteed to offer a total order
1372 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1374 std::less_equal<const value_type*> le;
1375 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1376 assert(le(s + n, oldData + oldSize));
1377 const size_type offset = s - oldData;
1378 store_.reserve(oldSize + n);
1379 // Restore the source
1380 s = data() + offset;
1382 // Warning! Repeated appends with short strings may actually incur
1383 // practically quadratic performance. Avoid that by pushing back
1384 // the first character (which ensures exponential growth) and then
1385 // appending the rest normally. Worst case the append may incur a
1386 // second allocation but that will be rare.
1389 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1390 assert(size() == oldSize + n + 1);
1394 basic_fbstring& append(const value_type* s) {
1395 return append(s, traits_type::length(s));
1398 basic_fbstring& append(size_type n, value_type c) {
1399 resize(size() + n, c);
1403 template<class InputIterator>
1404 basic_fbstring& append(InputIterator first, InputIterator last) {
1405 insert(end(), first, last);
1409 basic_fbstring& append(std::initializer_list<value_type> il) {
1410 return append(il.begin(), il.end());
1413 void push_back(const value_type c) { // primitive
1414 store_.push_back(c);
1417 basic_fbstring& assign(const basic_fbstring& str) {
1418 if (&str == this) return *this;
1419 return assign(str.data(), str.size());
1422 basic_fbstring& assign(basic_fbstring&& str) {
1423 return *this = std::move(str);
1426 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1428 const size_type sz = str.size();
1429 enforce(pos <= sz, std::__throw_out_of_range, "");
1430 procrustes(n, sz - pos);
1431 return assign(str.data() + pos, n);
1434 basic_fbstring& assign(const value_type* s, const size_type n) {
1435 Invariant checker(*this);
1438 std::copy(s, s + n, begin());
1440 assert(size() == n);
1442 const value_type *const s2 = s + size();
1443 std::copy(s, s2, begin());
1444 append(s2, n - size());
1445 assert(size() == n);
1447 store_.writeTerminator();
1448 assert(size() == n);
1452 basic_fbstring& assign(const value_type* s) {
1453 return assign(s, traits_type::length(s));
1456 basic_fbstring& assign(std::initializer_list<value_type> il) {
1457 return assign(il.begin(), il.end());
1460 template <class ItOrLength, class ItOrChar>
1461 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1462 return replace(begin(), end(), first_or_n, last_or_c);
1465 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1466 return insert(pos1, str.data(), str.size());
1469 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1470 size_type pos2, size_type n) {
1471 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1472 procrustes(n, str.length() - pos2);
1473 return insert(pos1, str.data() + pos2, n);
1476 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1477 enforce(pos <= length(), std::__throw_out_of_range, "");
1478 insert(begin() + pos, s, s + n);
1482 basic_fbstring& insert(size_type pos, const value_type* s) {
1483 return insert(pos, s, traits_type::length(s));
1486 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1487 enforce(pos <= length(), std::__throw_out_of_range, "");
1488 insert(begin() + pos, n, c);
1492 iterator insert(const_iterator p, const value_type c) {
1493 const size_type pos = p - begin();
1495 return begin() + pos;
1499 template <int i> class Selector {};
1501 iterator insertImplDiscr(const_iterator p,
1502 size_type n, value_type c, Selector<1>) {
1503 Invariant checker(*this);
1505 auto const pos = p - begin();
1506 assert(p >= begin() && p <= end());
1507 if (capacity() - size() < n) {
1508 const size_type sz = p - begin();
1509 reserve(size() + n);
1512 const iterator oldEnd = end();
1513 if (n < size_type(oldEnd - p)) {
1514 append(oldEnd - n, oldEnd);
1516 // reverse_iterator(oldEnd - n),
1517 // reverse_iterator(p),
1518 // reverse_iterator(oldEnd));
1519 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1521 std::fill(begin() + pos, begin() + pos + n, c);
1523 append(n - (end() - p), c);
1524 append(iterator(p), oldEnd);
1525 std::fill(iterator(p), oldEnd, c);
1527 store_.writeTerminator();
1528 return begin() + pos;
1531 template<class InputIter>
1532 iterator insertImplDiscr(const_iterator i,
1533 InputIter b, InputIter e, Selector<0>) {
1534 return insertImpl(i, b, e,
1535 typename std::iterator_traits<InputIter>::iterator_category());
1538 template <class FwdIterator>
1539 iterator insertImpl(const_iterator i,
1540 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1541 Invariant checker(*this);
1543 const size_type pos = i - begin();
1544 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1545 std::distance(s1, s2);
1547 using namespace fbstring_detail;
1548 assert(pos <= size());
1550 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1551 capacity() - size();
1553 // realloc the string
1554 reserve(size() + n2);
1557 if (pos + n2 <= size()) {
1558 const iterator tailBegin = end() - n2;
1559 store_.expand_noinit(n2);
1560 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1561 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1562 reverse_iterator(tailBegin + n2));
1563 std::copy(s1, s2, begin() + pos);
1566 const size_type old_size = size();
1567 std::advance(t, old_size - pos);
1568 const size_t newElems = std::distance(t, s2);
1569 store_.expand_noinit(n2);
1570 std::copy(t, s2, begin() + old_size);
1571 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1572 begin() + old_size + newElems);
1573 std::copy(s1, t, begin() + pos);
1575 store_.writeTerminator();
1576 return begin() + pos;
1579 template <class InputIterator>
1580 iterator insertImpl(const_iterator i,
1581 InputIterator b, InputIterator e,
1582 std::input_iterator_tag) {
1583 const auto pos = i - begin();
1584 basic_fbstring temp(begin(), i);
1585 for (; b != e; ++b) {
1588 temp.append(i, cend());
1590 return begin() + pos;
1594 template <class ItOrLength, class ItOrChar>
1595 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1596 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1597 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1600 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1601 return insert(p, il.begin(), il.end());
1604 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1605 Invariant checker(*this);
1607 enforce(pos <= length(), std::__throw_out_of_range, "");
1608 procrustes(n, length() - pos);
1609 std::copy(begin() + pos + n, end(), begin() + pos);
1610 resize(length() - n);
1614 iterator erase(iterator position) {
1615 const size_type pos(position - begin());
1616 enforce(pos <= size(), std::__throw_out_of_range, "");
1618 return begin() + pos;
1621 iterator erase(iterator first, iterator last) {
1622 const size_type pos(first - begin());
1623 erase(pos, last - first);
1624 return begin() + pos;
1627 // Replaces at most n1 chars of *this, starting with pos1 with the
1629 basic_fbstring& replace(size_type pos1, size_type n1,
1630 const basic_fbstring& str) {
1631 return replace(pos1, n1, str.data(), str.size());
1634 // Replaces at most n1 chars of *this, starting with pos1,
1635 // with at most n2 chars of str starting with pos2
1636 basic_fbstring& replace(size_type pos1, size_type n1,
1637 const basic_fbstring& str,
1638 size_type pos2, size_type n2) {
1639 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1640 return replace(pos1, n1, str.data() + pos2,
1641 std::min(n2, str.size() - pos2));
1644 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1645 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1646 return replace(pos, n1, s, traits_type::length(s));
1649 // Replaces at most n1 chars of *this, starting with pos, with n2
1652 // consolidated with
1654 // Replaces at most n1 chars of *this, starting with pos, with at
1655 // most n2 chars of str. str must have at least n2 chars.
1656 template <class StrOrLength, class NumOrChar>
1657 basic_fbstring& replace(size_type pos, size_type n1,
1658 StrOrLength s_or_n2, NumOrChar n_or_c) {
1659 Invariant checker(*this);
1661 enforce(pos <= size(), std::__throw_out_of_range, "");
1662 procrustes(n1, length() - pos);
1663 const iterator b = begin() + pos;
1664 return replace(b, b + n1, s_or_n2, n_or_c);
1667 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1668 return replace(i1, i2, str.data(), str.length());
1671 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1672 return replace(i1, i2, s, traits_type::length(s));
1676 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1677 const value_type* s, size_type n,
1680 assert(begin() <= i1 && i1 <= end());
1681 assert(begin() <= i2 && i2 <= end());
1682 return replace(i1, i2, s, s + n);
1685 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1686 size_type n2, value_type c, Selector<1>) {
1687 const size_type n1 = i2 - i1;
1689 std::fill(i1, i1 + n2, c);
1692 std::fill(i1, i2, c);
1693 insert(i2, n2 - n1, c);
1699 template <class InputIter>
1700 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1701 InputIter b, InputIter e,
1703 replaceImpl(i1, i2, b, e,
1704 typename std::iterator_traits<InputIter>::iterator_category());
1709 template <class FwdIterator>
1710 bool replaceAliased(iterator i1, iterator i2,
1711 FwdIterator s1, FwdIterator s2, std::false_type) {
1715 template <class FwdIterator>
1716 bool replaceAliased(iterator i1, iterator i2,
1717 FwdIterator s1, FwdIterator s2, std::true_type) {
1718 static const std::less_equal<const value_type*> le =
1719 std::less_equal<const value_type*>();
1720 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1724 // Aliased replace, copy to new string
1725 basic_fbstring temp;
1726 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1727 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1732 template <class FwdIterator>
1733 void replaceImpl(iterator i1, iterator i2,
1734 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1735 Invariant checker(*this);
1738 // Handle aliased replace
1739 if (replaceAliased(i1, i2, s1, s2,
1740 std::integral_constant<bool,
1741 std::is_same<FwdIterator, iterator>::value ||
1742 std::is_same<FwdIterator, const_iterator>::value>())) {
1746 auto const n1 = i2 - i1;
1748 auto const n2 = std::distance(s1, s2);
1753 std::copy(s1, s2, i1);
1757 fbstring_detail::copy_n(s1, n1, i1);
1758 std::advance(s1, n1);
1764 template <class InputIterator>
1765 void replaceImpl(iterator i1, iterator i2,
1766 InputIterator b, InputIterator e, std::input_iterator_tag) {
1767 basic_fbstring temp(begin(), i1);
1768 temp.append(b, e).append(i2, end());
1773 template <class T1, class T2>
1774 basic_fbstring& replace(iterator i1, iterator i2,
1775 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1777 num1 = std::numeric_limits<T1>::is_specialized,
1778 num2 = std::numeric_limits<T2>::is_specialized;
1779 return replaceImplDiscr(
1780 i1, i2, first_or_n_or_s, last_or_c_or_n,
1781 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1784 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1785 enforce(pos <= size(), std::__throw_out_of_range, "");
1786 procrustes(n, size() - pos);
1788 fbstring_detail::pod_copy(
1795 void swap(basic_fbstring& rhs) {
1796 store_.swap(rhs.store_);
1799 const value_type* c_str() const {
1800 return store_.c_str();
1803 const value_type* data() const { return c_str(); }
1805 allocator_type get_allocator() const {
1806 return allocator_type();
1809 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1810 return find(str.data(), pos, str.length());
1813 size_type find(const value_type* needle, const size_type pos,
1814 const size_type nsize) const {
1815 if (!nsize) return pos;
1816 auto const size = this->size();
1817 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1818 // that nsize + pos does not wrap around.
1819 if (nsize + pos > size || nsize + pos < pos) return npos;
1820 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1821 // the last characters first
1822 auto const haystack = data();
1823 auto const nsize_1 = nsize - 1;
1824 auto const lastNeedle = needle[nsize_1];
1826 // Boyer-Moore skip value for the last char in the needle. Zero is
1827 // not a valid value; skip will be computed the first time it's
1831 const E * i = haystack + pos;
1832 auto iEnd = haystack + size - nsize_1;
1835 // Boyer-Moore: match the last element in the needle
1836 while (i[nsize_1] != lastNeedle) {
1842 // Here we know that the last char matches
1843 // Continue in pedestrian mode
1844 for (size_t j = 0; ; ) {
1846 if (i[j] != needle[j]) {
1847 // Not found, we can skip
1848 // Compute the skip value lazily
1851 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1858 // Check if done searching
1861 return i - haystack;
1868 size_type find(const value_type* s, size_type pos = 0) const {
1869 return find(s, pos, traits_type::length(s));
1872 size_type find (value_type c, size_type pos = 0) const {
1873 return find(&c, pos, 1);
1876 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1877 return rfind(str.data(), pos, str.length());
1880 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1881 if (n > length()) return npos;
1882 pos = std::min(pos, length() - n);
1883 if (n == 0) return pos;
1885 const_iterator i(begin() + pos);
1887 if (traits_type::eq(*i, *s)
1888 && traits_type::compare(&*i, s, n) == 0) {
1891 if (i == begin()) break;
1896 size_type rfind(const value_type* s, size_type pos = npos) const {
1897 return rfind(s, pos, traits_type::length(s));
1900 size_type rfind(value_type c, size_type pos = npos) const {
1901 return rfind(&c, pos, 1);
1904 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1905 return find_first_of(str.data(), pos, str.length());
1908 size_type find_first_of(const value_type* s,
1909 size_type pos, size_type n) const {
1910 if (pos > length() || n == 0) return npos;
1911 const_iterator i(begin() + pos),
1913 for (; i != finish; ++i) {
1914 if (traits_type::find(s, n, *i) != 0) {
1921 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1922 return find_first_of(s, pos, traits_type::length(s));
1925 size_type find_first_of(value_type c, size_type pos = 0) const {
1926 return find_first_of(&c, pos, 1);
1929 size_type find_last_of (const basic_fbstring& str,
1930 size_type pos = npos) const {
1931 return find_last_of(str.data(), pos, str.length());
1934 size_type find_last_of (const value_type* s, size_type pos,
1935 size_type n) const {
1936 if (!empty() && n > 0) {
1937 pos = std::min(pos, length() - 1);
1938 const_iterator i(begin() + pos);
1940 if (traits_type::find(s, n, *i) != 0) {
1943 if (i == begin()) break;
1949 size_type find_last_of (const value_type* s,
1950 size_type pos = npos) const {
1951 return find_last_of(s, pos, traits_type::length(s));
1954 size_type find_last_of (value_type c, size_type pos = npos) const {
1955 return find_last_of(&c, pos, 1);
1958 size_type find_first_not_of(const basic_fbstring& str,
1959 size_type pos = 0) const {
1960 return find_first_not_of(str.data(), pos, str.size());
1963 size_type find_first_not_of(const value_type* s, size_type pos,
1964 size_type n) const {
1965 if (pos < length()) {
1969 for (; i != finish; ++i) {
1970 if (traits_type::find(s, n, *i) == 0) {
1978 size_type find_first_not_of(const value_type* s,
1979 size_type pos = 0) const {
1980 return find_first_not_of(s, pos, traits_type::length(s));
1983 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1984 return find_first_not_of(&c, pos, 1);
1987 size_type find_last_not_of(const basic_fbstring& str,
1988 size_type pos = npos) const {
1989 return find_last_not_of(str.data(), pos, str.length());
1992 size_type find_last_not_of(const value_type* s, size_type pos,
1993 size_type n) const {
1994 if (!this->empty()) {
1995 pos = std::min(pos, size() - 1);
1996 const_iterator i(begin() + pos);
1998 if (traits_type::find(s, n, *i) == 0) {
2001 if (i == begin()) break;
2007 size_type find_last_not_of(const value_type* s,
2008 size_type pos = npos) const {
2009 return find_last_not_of(s, pos, traits_type::length(s));
2012 size_type find_last_not_of (value_type c, size_type pos = npos) const {
2013 return find_last_not_of(&c, pos, 1);
2016 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
2017 enforce(pos <= size(), std::__throw_out_of_range, "");
2018 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2021 int compare(const basic_fbstring& str) const {
2022 // FIX due to Goncalo N M de Carvalho July 18, 2005
2023 return compare(0, size(), str);
2026 int compare(size_type pos1, size_type n1,
2027 const basic_fbstring& str) const {
2028 return compare(pos1, n1, str.data(), str.size());
2031 int compare(size_type pos1, size_type n1,
2032 const value_type* s) const {
2033 return compare(pos1, n1, s, traits_type::length(s));
2036 int compare(size_type pos1, size_type n1,
2037 const value_type* s, size_type n2) const {
2038 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2039 procrustes(n1, size() - pos1);
2040 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2041 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2042 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2045 int compare(size_type pos1, size_type n1,
2046 const basic_fbstring& str,
2047 size_type pos2, size_type n2) const {
2048 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2049 return compare(pos1, n1, str.data() + pos2,
2050 std::min(n2, str.size() - pos2));
2053 // Code from Jean-Francois Bastien (03/26/2007)
2054 int compare(const value_type* s) const {
2055 // Could forward to compare(0, size(), s, traits_type::length(s))
2056 // but that does two extra checks
2057 const size_type n1(size()), n2(traits_type::length(s));
2058 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2059 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2067 // non-member functions
2069 template <typename E, class T, class A, class S>
2071 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2072 const basic_fbstring<E, T, A, S>& rhs) {
2074 basic_fbstring<E, T, A, S> result;
2075 result.reserve(lhs.size() + rhs.size());
2076 result.append(lhs).append(rhs);
2077 return std::move(result);
2081 template <typename E, class T, class A, class S>
2083 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2084 const basic_fbstring<E, T, A, S>& rhs) {
2085 return std::move(lhs.append(rhs));
2089 template <typename E, class T, class A, class S>
2091 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2092 basic_fbstring<E, T, A, S>&& rhs) {
2093 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2094 // Good, at least we don't need to reallocate
2095 return std::move(rhs.insert(0, lhs));
2097 // Meh, no go. Forward to operator+(const&, const&).
2098 auto const& rhsC = rhs;
2103 template <typename E, class T, class A, class S>
2105 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2106 basic_fbstring<E, T, A, S>&& rhs) {
2107 return std::move(lhs.append(rhs));
2110 template <typename E, class T, class A, class S>
2112 basic_fbstring<E, T, A, S> operator+(
2113 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2114 const basic_fbstring<E, T, A, S>& rhs) {
2116 basic_fbstring<E, T, A, S> result;
2117 const typename basic_fbstring<E, T, A, S>::size_type len =
2118 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2119 result.reserve(len + rhs.size());
2120 result.append(lhs, len).append(rhs);
2124 template <typename E, class T, class A, class S>
2126 basic_fbstring<E, T, A, S> operator+(
2127 typename basic_fbstring<E, T, A, S>::value_type lhs,
2128 const basic_fbstring<E, T, A, S>& rhs) {
2130 basic_fbstring<E, T, A, S> result;
2131 result.reserve(1 + rhs.size());
2132 result.push_back(lhs);
2137 template <typename E, class T, class A, class S>
2139 basic_fbstring<E, T, A, S> operator+(
2140 const basic_fbstring<E, T, A, S>& lhs,
2141 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2143 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2144 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2146 basic_fbstring<E, T, A, S> result;
2147 const size_type len = traits_type::length(rhs);
2148 result.reserve(lhs.size() + len);
2149 result.append(lhs).append(rhs, len);
2153 template <typename E, class T, class A, class S>
2155 basic_fbstring<E, T, A, S> operator+(
2156 const basic_fbstring<E, T, A, S>& lhs,
2157 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2159 basic_fbstring<E, T, A, S> result;
2160 result.reserve(lhs.size() + 1);
2162 result.push_back(rhs);
2166 template <typename E, class T, class A, class S>
2168 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2169 const basic_fbstring<E, T, A, S>& rhs) {
2170 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2172 template <typename E, class T, class A, class S>
2174 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2175 const basic_fbstring<E, T, A, S>& rhs) {
2176 return rhs == lhs; }
2178 template <typename E, class T, class A, class S>
2180 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2181 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2182 return lhs.compare(rhs) == 0; }
2184 template <typename E, class T, class A, class S>
2186 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2187 const basic_fbstring<E, T, A, S>& rhs) {
2188 return !(lhs == rhs); }
2190 template <typename E, class T, class A, class S>
2192 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2193 const basic_fbstring<E, T, A, S>& rhs) {
2194 return !(lhs == rhs); }
2196 template <typename E, class T, class A, class S>
2198 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2199 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2200 return !(lhs == rhs); }
2202 template <typename E, class T, class A, class S>
2204 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2205 const basic_fbstring<E, T, A, S>& rhs) {
2206 return lhs.compare(rhs) < 0; }
2208 template <typename E, class T, class A, class S>
2210 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2211 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2212 return lhs.compare(rhs) < 0; }
2214 template <typename E, class T, class A, class S>
2216 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2217 const basic_fbstring<E, T, A, S>& rhs) {
2218 return rhs.compare(lhs) > 0; }
2220 template <typename E, class T, class A, class S>
2222 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2223 const basic_fbstring<E, T, A, S>& rhs) {
2226 template <typename E, class T, class A, class S>
2228 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2229 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2232 template <typename E, class T, class A, class S>
2234 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2235 const basic_fbstring<E, T, A, S>& rhs) {
2238 template <typename E, class T, class A, class S>
2240 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2241 const basic_fbstring<E, T, A, S>& rhs) {
2242 return !(rhs < lhs); }
2244 template <typename E, class T, class A, class S>
2246 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2247 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2248 return !(rhs < lhs); }
2250 template <typename E, class T, class A, class S>
2252 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2253 const basic_fbstring<E, T, A, S>& rhs) {
2254 return !(rhs < lhs); }
2256 template <typename E, class T, class A, class S>
2258 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2259 const basic_fbstring<E, T, A, S>& rhs) {
2260 return !(lhs < rhs); }
2262 template <typename E, class T, class A, class S>
2264 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2265 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2266 return !(lhs < rhs); }
2268 template <typename E, class T, class A, class S>
2270 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2271 const basic_fbstring<E, T, A, S>& rhs) {
2272 return !(lhs < rhs);
2276 template <typename E, class T, class A, class S>
2277 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2281 // TODO: make this faster.
2282 template <typename E, class T, class A, class S>
2285 typename basic_fbstring<E, T, A, S>::value_type,
2286 typename basic_fbstring<E, T, A, S>::traits_type>&
2288 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2289 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2290 basic_fbstring<E, T, A, S>& str) {
2291 typename std::basic_istream<E, T>::sentry sentry(is);
2292 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2293 typename basic_fbstring<E, T, A, S>::traits_type>
2295 typedef typename __istream_type::ios_base __ios_base;
2296 size_t extracted = 0;
2297 auto err = __ios_base::goodbit;
2299 auto n = is.width();
2304 auto got = is.rdbuf()->sgetc();
2305 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2306 // Whew. We get to store this guy
2308 got = is.rdbuf()->snextc();
2310 if (got == T::eof()) {
2311 err |= __ios_base::eofbit;
2316 err |= __ios_base::failbit;
2324 template <typename E, class T, class A, class S>
2326 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2327 typename basic_fbstring<E, T, A, S>::traits_type>&
2329 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2330 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2331 const basic_fbstring<E, T, A, S>& str) {
2333 typename std::basic_ostream<
2334 typename basic_fbstring<E, T, A, S>::value_type,
2335 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2337 typedef std::ostreambuf_iterator<
2338 typename basic_fbstring<E, T, A, S>::value_type,
2339 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2340 size_t __len = str.size();
2342 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2343 if (__pad_and_output(_Ip(os),
2345 __left ? str.data() + __len : str.data(),
2348 os.fill()).failed()) {
2349 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2353 std::__ostream_insert(os, str.data(), str.size());
2358 #ifndef _LIBSTDCXX_FBSTRING
2360 template <typename E, class T, class A, class S>
2362 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2363 typename basic_fbstring<E, T, A, S>::traits_type>&
2365 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2366 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2367 basic_fbstring<E, T, A, S>& str,
2368 typename basic_fbstring<E, T, A, S>::value_type delim) {
2369 // Use the nonstandard getdelim()
2370 char * buf = nullptr;
2373 // This looks quadratic but it really depends on realloc
2374 auto const newSize = size + 128;
2375 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2376 is.getline(buf + size, newSize - size, delim);
2377 if (is.bad() || is.eof() || !is.fail()) {
2378 // done by either failure, end of file, or normal read
2379 size += std::strlen(buf + size);
2382 // Here we have failed due to too short a buffer
2383 // Minus one to discount the terminating '\0'
2385 assert(buf[size] == 0);
2386 // Clear the error so we can continue reading
2389 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2390 AcquireMallocatedString());
2395 template <typename E, class T, class A, class S>
2397 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2398 typename basic_fbstring<E, T, A, S>::traits_type>&
2400 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2401 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2402 basic_fbstring<E, T, A, S>& str) {
2403 // Just forward to the version with a delimiter
2404 return getline(is, str, '\n');
2409 template <typename E1, class T, class A, class S>
2410 const typename basic_fbstring<E1, T, A, S>::size_type
2411 basic_fbstring<E1, T, A, S>::npos =
2412 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2414 #ifndef _LIBSTDCXX_FBSTRING
2415 // basic_string compatibility routines
2417 template <typename E, class T, class A, class S>
2419 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2420 const std::string& rhs) {
2421 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2424 template <typename E, class T, class A, class S>
2426 bool operator==(const std::string& lhs,
2427 const basic_fbstring<E, T, A, S>& rhs) {
2431 template <typename E, class T, class A, class S>
2433 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2434 const std::string& rhs) {
2435 return !(lhs == rhs);
2438 template <typename E, class T, class A, class S>
2440 bool operator!=(const std::string& lhs,
2441 const basic_fbstring<E, T, A, S>& rhs) {
2442 return !(lhs == rhs);
2445 #if !defined(_LIBSTDCXX_FBSTRING)
2446 typedef basic_fbstring<char> fbstring;
2449 // fbstring is relocatable
2450 template <class T, class R, class A, class S>
2451 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2454 _GLIBCXX_END_NAMESPACE_VERSION
2457 } // namespace folly
2459 #ifndef _LIBSTDCXX_FBSTRING
2461 // Hash functions to make fbstring usable with e.g. hash_map
2463 // Handle interaction with different C++ standard libraries, which
2464 // expect these types to be in different namespaces.
2468 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2469 size_t operator()(const folly::basic_fbstring<C> & s) const {
2470 return hash<const C*>::operator()(s.c_str());
2475 struct hash< ::folly::fbstring> {
2476 size_t operator()(const ::folly::fbstring& s) const {
2477 return ::folly::hash::fnv32_buf(s.data(), s.size());
2483 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2484 namespace __gnu_cxx {
2487 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2488 size_t operator()(const folly::basic_fbstring<C> & s) const {
2489 return hash<const C*>::operator()(s.c_str());
2494 struct hash< ::folly::fbstring> {
2495 size_t operator()(const ::folly::fbstring& s) const {
2496 return ::folly::hash::fnv32_buf(s.data(), s.size());
2501 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2502 #endif // _LIBSTDCXX_FBSTRING
2504 #pragma GCC diagnostic pop
2506 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2508 #undef FBSTRING_LIKELY
2509 #undef FBSTRING_UNLIKELY
2511 #endif // FOLLY_BASE_FBSTRING_H_