2 * Copyright 2015 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
25 #include <type_traits>
27 // This file appears in two locations: inside fbcode and in the
28 // libstdc++ source code (when embedding fbstring as std::string).
29 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
30 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
31 #ifdef _LIBSTDCXX_FBSTRING
33 #pragma GCC system_header
35 // Handle the cases where the fbcode version (folly/Malloc.h) is included
36 // either before or after this inclusion.
37 #ifdef FOLLY_MALLOC_H_
38 #undef FOLLY_MALLOC_H_
39 #include "basic_fbstring_malloc.h" // nolint
41 #include "basic_fbstring_malloc.h" // nolint
42 #undef FOLLY_MALLOC_H_
45 #else // !_LIBSTDCXX_FBSTRING
47 #include <folly/Portability.h>
49 // libc++ doesn't provide this header, nor does msvc
50 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
51 #include <bits/c++config.h>
59 #include <folly/Traits.h>
60 #include <folly/Malloc.h>
61 #include <folly/Hash.h>
62 #include <folly/ScopeGuard.h>
64 #if FOLLY_HAVE_DEPRECATED_ASSOC
65 #ifdef _GLIBCXX_SYMVER
66 #include <ext/hash_set>
67 #include <ext/hash_map>
73 // We defined these here rather than including Likely.h to avoid
74 // redefinition errors when fbstring is imported into libstdc++.
75 #if defined(__GNUC__) && __GNUC__ >= 4
76 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
77 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
79 #define FBSTRING_LIKELY(x) (x)
80 #define FBSTRING_UNLIKELY(x) (x)
83 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
84 #pragma GCC diagnostic push
85 #pragma GCC diagnostic ignored "-Wshadow"
87 // FBString cannot use throw when replacing std::string, though it may still
90 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
92 #ifdef _LIBSTDCXX_FBSTRING
93 namespace std _GLIBCXX_VISIBILITY(default) {
94 _GLIBCXX_BEGIN_NAMESPACE_VERSION
99 // Different versions of gcc/clang support different versions of
100 // the address sanitizer attribute. Unfortunately, this attribute
101 // has issues when inlining is used, so disable that as well.
102 #if defined(__clang__)
103 # if __has_feature(address_sanitizer)
104 # if __has_attribute(__no_address_safety_analysis__)
105 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
106 __attribute__((__no_address_safety_analysis__, __noinline__))
107 # elif __has_attribute(__no_sanitize_address__)
108 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
109 __attribute__((__no_sanitize_address__, __noinline__))
112 #elif defined (__GNUC__) && \
114 (__GNUC_MINOR__ >= 8) && \
116 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
117 __attribute__((__no_address_safety_analysis__, __noinline__))
119 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
120 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
123 namespace fbstring_detail {
125 template <class InIt, class OutIt>
128 typename std::iterator_traits<InIt>::difference_type n,
130 for (; n != 0; --n, ++b, ++d) {
136 template <class Pod, class T>
137 inline void pod_fill(Pod* b, Pod* e, T c) {
138 assert(b && e && b <= e);
139 /*static*/ if (sizeof(T) == 1) {
142 auto const ee = b + ((e - b) & ~7u);
143 for (; b != ee; b += 8) {
154 for (; b != e; ++b) {
161 * Lightly structured memcpy, simplifies copying PODs and introduces
162 * some asserts. Unfortunately using this function may cause
163 * measurable overhead (presumably because it adjusts from a begin/end
164 * convention to a pointer/size convention, so it does some extra
165 * arithmetic even though the caller might have done the inverse
166 * adaptation outside).
169 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
171 assert(d >= e || d + (e - b) <= b);
172 memcpy(d, b, (e - b) * sizeof(Pod));
176 * Lightly structured memmove, simplifies copying PODs and introduces
180 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
182 memmove(d, b, (e - b) * sizeof(*b));
185 } // namespace fbstring_detail
188 * Defines a special acquisition method for constructing fbstring
189 * objects. AcquireMallocatedString means that the user passes a
190 * pointer to a malloc-allocated string that the fbstring object will
193 enum class AcquireMallocatedString {};
196 * fbstring_core_model is a mock-up type that defines all required
197 * signatures of a fbstring core. The fbstring class itself uses such
198 * a core object to implement all of the numerous member functions
199 * required by the standard.
201 * If you want to define a new core, copy the definition below and
202 * implement the primitives. Then plug the core into basic_fbstring as
203 * a template argument.
205 template <class Char>
206 class fbstring_core_model {
208 fbstring_core_model();
209 fbstring_core_model(const fbstring_core_model &);
210 ~fbstring_core_model();
211 // Returns a pointer to string's buffer (currently only contiguous
212 // strings are supported). The pointer is guaranteed to be valid
213 // until the next call to a non-const member function.
214 const Char * data() const;
215 // Much like data(), except the string is prepared to support
216 // character-level changes. This call is a signal for
217 // e.g. reference-counted implementation to fork the data. The
218 // pointer is guaranteed to be valid until the next call to a
219 // non-const member function.
220 Char * mutable_data();
221 // Returns a pointer to string's buffer and guarantees that a
222 // readable '\0' lies right after the buffer. The pointer is
223 // guaranteed to be valid until the next call to a non-const member
225 const Char * c_str() const;
226 // Shrinks the string by delta characters. Asserts that delta <=
228 void shrink(size_t delta);
229 // Expands the string by delta characters (i.e. after this call
230 // size() will report the old size() plus delta) but without
231 // initializing the expanded region. Returns a pointer to the memory
232 // to be initialized (the beginning of the expanded portion). The
233 // caller is expected to fill the expanded area appropriately.
234 Char* expand_noinit(size_t delta);
235 // Expands the string by one character and sets the last character
237 void push_back(Char c);
238 // Returns the string's size.
240 // Returns the string's capacity, i.e. maximum size that the string
241 // can grow to without reallocation. Note that for reference counted
242 // strings that's technically a lie - even assigning characters
243 // within the existing size would cause a reallocation.
244 size_t capacity() const;
245 // Returns true if the data underlying the string is actually shared
246 // across multiple strings (in a refcounted fashion).
247 bool isShared() const;
248 // Makes sure that at least minCapacity characters are available for
249 // the string without reallocation. For reference-counted strings,
250 // it should fork the data even if minCapacity < size().
251 void reserve(size_t minCapacity);
254 fbstring_core_model& operator=(const fbstring_core_model &);
259 * gcc-4.7 throws what appears to be some false positive uninitialized
260 * warnings for the members of the MediumLarge struct. So, mute them here.
262 #if defined(__GNUC__) && !defined(__clang__)
263 # pragma GCC diagnostic push
264 # pragma GCC diagnostic ignored "-Wuninitialized"
268 * This is the core of the string. The code should work on 32- and
269 * 64-bit and both big- and little-endianan architectures with any
272 * The storage is selected as follows (assuming we store one-byte
273 * characters on a 64-bit machine): (a) "small" strings between 0 and
274 * 23 chars are stored in-situ without allocation (the rightmost byte
275 * stores the size); (b) "medium" strings from 24 through 254 chars
276 * are stored in malloc-allocated memory that is copied eagerly; (c)
277 * "large" strings of 255 chars and above are stored in a similar
278 * structure as medium arrays, except that the string is
279 * reference-counted and copied lazily. the reference count is
280 * allocated right before the character array.
282 * The discriminator between these three strategies sits in two
283 * bits of the rightmost char of the storage. If neither is set, then the
284 * string is small (and its length sits in the lower-order bits on
285 * little-endian or the high-order bits on big-endian of that
286 * rightmost character). If the MSb is set, the string is medium width.
287 * If the second MSb is set, then the string is large. On little-endian,
288 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
289 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
290 * and big-endian fbstring_core equivalent with merely different ops used
291 * to extract capacity/category.
293 template <class Char> class fbstring_core {
295 fbstring_core() noexcept {
296 // Only initialize the tag, will set the MSBs (i.e. the small
297 // string size) to zero too
298 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
299 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
300 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
301 ml_.capacity_ = maxSmallSize << 2;
303 #error Unable to identify target endianness
305 // or: setSmallSize(0);
307 assert(category() == Category::isSmall && size() == 0);
310 fbstring_core(const fbstring_core & rhs) {
311 assert(&rhs != this);
312 // Simplest case first: small strings are bitblitted
313 if (rhs.category() == Category::isSmall) {
314 static_assert(offsetof(MediumLarge, data_) == 0,
315 "fbstring layout failure");
316 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
317 "fbstring layout failure");
318 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
319 "fbstring layout failure");
320 const size_t size = rhs.smallSize();
322 ml_.capacity_ = rhs.ml_.capacity_;
325 // Just write the whole thing, don't look at details. In
326 // particular we need to copy capacity anyway because we want
327 // to set the size (don't forget that the last character,
328 // which stores a short string's length, is shared with the
329 // ml_.capacity field).
332 assert(category() == Category::isSmall && this->size() == rhs.size());
333 } else if (rhs.category() == Category::isLarge) {
334 // Large strings are just refcounted
336 RefCounted::incrementRefs(ml_.data_);
337 assert(category() == Category::isLarge && size() == rhs.size());
339 // Medium strings are copied eagerly. Don't forget to allocate
340 // one extra Char for the null terminator.
341 auto const allocSize =
342 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
343 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
344 fbstring_detail::pod_copy(rhs.ml_.data_,
346 rhs.ml_.data_ + rhs.ml_.size_ + 1,
348 // No need for writeTerminator() here, we copied one extra
349 // element just above.
350 ml_.size_ = rhs.ml_.size_;
351 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
352 assert(category() == Category::isMedium);
354 assert(size() == rhs.size());
355 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
358 fbstring_core(fbstring_core&& goner) noexcept {
359 if (goner.category() == Category::isSmall) {
360 // Just copy, leave the goner in peace
361 new(this) fbstring_core(goner.small_, goner.smallSize());
365 // Clean goner's carcass
366 goner.setSmallSize(0);
370 // NOTE(agallagher): The word-aligned copy path copies bytes which are
371 // outside the range of the string, and makes address sanitizer unhappy,
372 // so just disable it on this function.
373 fbstring_core(const Char *const data, const size_t size)
374 FBSTRING_DISABLE_ADDRESS_SANITIZER {
376 #ifndef _LIBSTDCXX_FBSTRING
378 assert(this->size() == size);
379 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
384 // Simplest case first: small strings are bitblitted
385 if (size <= maxSmallSize) {
386 // Layout is: Char* data_, size_t size_, size_t capacity_
387 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
388 "fbstring has unexpected size");
389 static_assert(sizeof(Char*) == sizeof(size_t),
390 "fbstring size assumption violation");
391 // sizeof(size_t) must be a power of 2
392 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
393 "fbstring size assumption violation");
395 // If data is aligned, use fast word-wise copying. Otherwise,
396 // use conservative memcpy.
397 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
398 fbstring_detail::pod_copy(data, data + size, small_);
400 // Copy one word (64 bits) at a time
401 const size_t byteSize = size * sizeof(Char);
402 if (byteSize > 2 * sizeof(size_t)) {
404 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
406 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
408 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
409 } else if (byteSize > sizeof(size_t)) {
412 } else if (size > 0) {
419 } else if (size <= maxMediumSize) {
420 // Medium strings are allocated normally. Don't forget to
421 // allocate one extra Char for the terminating null.
422 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
423 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
424 fbstring_detail::pod_copy(data, data + size, ml_.data_);
426 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
428 // Large strings are allocated differently
429 size_t effectiveCapacity = size;
430 auto const newRC = RefCounted::create(data, & effectiveCapacity);
431 ml_.data_ = newRC->data_;
433 ml_.setCapacity(effectiveCapacity, Category::isLarge);
438 ~fbstring_core() noexcept {
439 auto const c = category();
440 if (c == Category::isSmall) {
443 if (c == Category::isMedium) {
447 RefCounted::decrementRefs(ml_.data_);
450 // Snatches a previously mallocated string. The parameter "size"
451 // is the size of the string, and the parameter "allocatedSize"
452 // is the size of the mallocated block. The string must be
453 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
455 // So if you want a 2-character string, pass malloc(3) as "data",
456 // pass 2 as "size", and pass 3 as "allocatedSize".
457 fbstring_core(Char * const data,
459 const size_t allocatedSize,
460 AcquireMallocatedString) {
462 assert(allocatedSize >= size + 1);
463 assert(data[size] == '\0');
464 // Use the medium string storage
467 // Don't forget about null terminator
468 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
470 // No need for the memory
476 // swap below doesn't test whether &rhs == this (and instead
477 // potentially does extra work) on the premise that the rarity of
478 // that situation actually makes the check more expensive than is
480 void swap(fbstring_core & rhs) {
486 // In C++11 data() and c_str() are 100% equivalent.
487 const Char * data() const {
491 Char * mutable_data() {
492 auto const c = category();
493 if (c == Category::isSmall) {
496 assert(c == Category::isMedium || c == Category::isLarge);
497 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
499 size_t effectiveCapacity = ml_.capacity();
500 auto const newRC = RefCounted::create(& effectiveCapacity);
501 // If this fails, someone placed the wrong capacity in an
503 assert(effectiveCapacity >= ml_.capacity());
504 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
506 RefCounted::decrementRefs(ml_.data_);
507 ml_.data_ = newRC->data_;
508 // No need to call writeTerminator(), we have + 1 above.
513 const Char * c_str() const {
514 auto const c = category();
515 if (c == Category::isSmall) {
516 assert(small_[smallSize()] == '\0');
519 assert(c == Category::isMedium || c == Category::isLarge);
520 assert(ml_.data_[ml_.size_] == '\0');
524 void shrink(const size_t delta) {
525 if (category() == Category::isSmall) {
526 // Check for underflow
527 assert(delta <= smallSize());
528 setSmallSize(smallSize() - delta);
529 } else if (category() == Category::isMedium ||
530 RefCounted::refs(ml_.data_) == 1) {
531 // Medium strings and unique large strings need no special
533 assert(ml_.size_ >= delta);
537 assert(ml_.size_ >= delta);
538 // Shared large string, must make unique. This is because of the
539 // durn terminator must be written, which may trample the shared
542 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
544 // No need to write the terminator.
548 void reserve(size_t minCapacity) {
549 if (category() == Category::isLarge) {
551 if (RefCounted::refs(ml_.data_) > 1) {
552 // We must make it unique regardless; in-place reallocation is
553 // useless if the string is shared. In order to not surprise
554 // people, reserve the new block at current capacity or
555 // more. That way, a string's capacity never shrinks after a
557 minCapacity = std::max(minCapacity, ml_.capacity());
558 auto const newRC = RefCounted::create(& minCapacity);
559 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
561 // Done with the old data. No need to call writeTerminator(),
562 // we have + 1 above.
563 RefCounted::decrementRefs(ml_.data_);
564 ml_.data_ = newRC->data_;
565 ml_.setCapacity(minCapacity, Category::isLarge);
566 // size remains unchanged
568 // String is not shared, so let's try to realloc (if needed)
569 if (minCapacity > ml_.capacity()) {
570 // Asking for more memory
572 RefCounted::reallocate(ml_.data_, ml_.size_,
573 ml_.capacity(), minCapacity);
574 ml_.data_ = newRC->data_;
575 ml_.setCapacity(minCapacity, Category::isLarge);
578 assert(capacity() >= minCapacity);
580 } else if (category() == Category::isMedium) {
581 // String is not shared
582 if (minCapacity <= ml_.capacity()) {
583 return; // nothing to do, there's enough room
585 if (minCapacity <= maxMediumSize) {
586 // Keep the string at medium size. Don't forget to allocate
587 // one extra Char for the terminating null.
588 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
589 ml_.data_ = static_cast<Char *>(
592 ml_.size_ * sizeof(Char),
593 (ml_.capacity() + 1) * sizeof(Char),
596 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
598 // Conversion from medium to large string
599 fbstring_core nascent;
600 // Will recurse to another branch of this function
601 nascent.reserve(minCapacity);
602 nascent.ml_.size_ = ml_.size_;
603 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
607 assert(capacity() >= minCapacity);
610 assert(category() == Category::isSmall);
611 if (minCapacity > maxMediumSize) {
613 auto const newRC = RefCounted::create(& minCapacity);
614 auto const size = smallSize();
615 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
616 // No need for writeTerminator(), we wrote it above with + 1.
617 ml_.data_ = newRC->data_;
619 ml_.setCapacity(minCapacity, Category::isLarge);
620 assert(capacity() >= minCapacity);
621 } else if (minCapacity > maxSmallSize) {
623 // Don't forget to allocate one extra Char for the terminating null
624 auto const allocSizeBytes =
625 goodMallocSize((1 + minCapacity) * sizeof(Char));
626 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
627 auto const size = smallSize();
628 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
629 // No need for writeTerminator(), we wrote it above with + 1.
632 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
635 // Nothing to do, everything stays put
638 assert(capacity() >= minCapacity);
641 Char * expand_noinit(const size_t delta) {
642 // Strategy is simple: make room, then change size
643 assert(capacity() >= size());
645 if (category() == Category::isSmall) {
648 if (newSz <= maxSmallSize) {
655 newSz = ml_.size_ + delta;
656 if (newSz > capacity()) {
660 assert(capacity() >= newSz);
661 // Category can't be small - we took care of that above
662 assert(category() == Category::isMedium || category() == Category::isLarge);
665 assert(size() == newSz);
666 return ml_.data_ + sz;
669 void push_back(Char c) {
670 assert(capacity() >= size());
672 if (category() == Category::isSmall) {
674 if (sz < maxSmallSize) {
676 setSmallSize(sz + 1);
679 reserve(maxSmallSize * 2);
682 if (sz == capacity()) { // always true for isShared()
683 reserve(1 + sz * 3 / 2); // ensures not shared
687 assert(capacity() >= sz + 1);
688 // Category can't be small - we took care of that above
689 assert(category() == Category::isMedium || category() == Category::isLarge);
695 size_t size() const {
696 return category() == Category::isSmall ? smallSize() : ml_.size_;
699 size_t capacity() const {
700 switch (category()) {
701 case Category::isSmall:
703 case Category::isLarge:
704 // For large-sized strings, a multi-referenced chunk has no
705 // available capacity. This is because any attempt to append
706 // data would trigger a new allocation.
707 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
710 return ml_.capacity();
713 bool isShared() const {
714 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
717 void writeTerminator() {
718 if (category() == Category::isSmall) {
719 const auto s = smallSize();
720 if (s != maxSmallSize) {
724 ml_.data_[ml_.size_] = '\0';
730 fbstring_core & operator=(const fbstring_core & rhs);
733 std::atomic<size_t> refCount_;
736 static RefCounted * fromData(Char * p) {
737 return static_cast<RefCounted*>(
739 static_cast<unsigned char*>(static_cast<void*>(p))
740 - sizeof(refCount_)));
743 static size_t refs(Char * p) {
744 return fromData(p)->refCount_.load(std::memory_order_acquire);
747 static void incrementRefs(Char * p) {
748 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
751 static void decrementRefs(Char * p) {
752 auto const dis = fromData(p);
753 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
760 static RefCounted * create(size_t * size) {
761 // Don't forget to allocate one extra Char for the terminating
762 // null. In this case, however, one Char is already part of the
764 const size_t allocSize = goodMallocSize(
765 sizeof(RefCounted) + *size * sizeof(Char));
766 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
767 result->refCount_.store(1, std::memory_order_release);
768 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
772 static RefCounted * create(const Char * data, size_t * size) {
773 const size_t effectiveSize = *size;
774 auto result = create(size);
775 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
779 static RefCounted * reallocate(Char *const data,
780 const size_t currentSize,
781 const size_t currentCapacity,
782 const size_t newCapacity) {
783 assert(newCapacity > 0 && newCapacity > currentSize);
784 auto const dis = fromData(data);
785 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
786 // Don't forget to allocate one extra Char for the terminating
787 // null. In this case, however, one Char is already part of the
789 auto result = static_cast<RefCounted*>(
791 sizeof(RefCounted) + currentSize * sizeof(Char),
792 sizeof(RefCounted) + currentCapacity * sizeof(Char),
793 sizeof(RefCounted) + newCapacity * sizeof(Char)));
794 assert(result->refCount_.load(std::memory_order_acquire) == 1);
799 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
802 enum class Category : category_type {
804 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
805 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
806 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
807 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
811 #error Unable to identify target endianness
815 Category category() const {
816 // works for both big-endian and little-endian
817 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
825 size_t capacity() const {
826 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
827 return capacity_ & capacityExtractMask;
828 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
829 return capacity_ >> 2;
831 #error Unable to identify target endianness
835 void setCapacity(size_t cap, Category cat) {
836 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
837 capacity_ = cap | static_cast<category_type>(cat);
838 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
839 capacity_ = (cap << 2) | static_cast<category_type>(cat);
841 #error Unable to identify target endianness
847 Char small_[sizeof(MediumLarge) / sizeof(Char)];
852 lastChar = sizeof(MediumLarge) - 1,
853 maxSmallSize = lastChar / sizeof(Char),
854 maxMediumSize = 254 / sizeof(Char), // coincides with the small
855 // bin size in dlmalloc
856 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
857 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
858 capacityExtractMask = ~categoryExtractMask,
859 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
860 categoryExtractMask = 0x3,
862 #error Unable to identify target endianness
865 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
866 "Corrupt memory layout for fbstring.");
868 size_t smallSize() const {
869 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
870 assert(category() == Category::isSmall &&
871 static_cast<size_t>(small_[maxSmallSize])
872 <= static_cast<size_t>(maxSmallSize));
873 return static_cast<size_t>(maxSmallSize)
874 - static_cast<size_t>(small_[maxSmallSize]);
875 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
876 assert(category() == Category::isSmall &&
877 (static_cast<size_t>(small_[maxSmallSize]) >> 2)
878 <= static_cast<size_t>(maxSmallSize));
879 return static_cast<size_t>(maxSmallSize)
880 - (static_cast<size_t>(small_[maxSmallSize]) >> 2);
882 #error Unable to identify target endianness
886 void setSmallSize(size_t s) {
887 // Warning: this should work with uninitialized strings too,
888 // so don't assume anything about the previous value of
889 // small_[maxSmallSize].
890 assert(s <= maxSmallSize);
891 #if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
892 small_[maxSmallSize] = maxSmallSize - s;
893 #elif __BYTE_ORDER__ == __ORDER_BIG_ENDIAN__
894 small_[maxSmallSize] = (maxSmallSize - s) << 2;
896 #error Unable to identify target endianness
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()] == '\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)
1075 : (std::__throw_logic_error(
1076 "basic_fbstring: null pointer initializer not valid"),
1080 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1084 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1085 auto const data = store_.expand_noinit(n);
1086 fbstring_detail::pod_fill(data, data + n, c);
1087 store_.writeTerminator();
1090 template <class InIt>
1091 basic_fbstring(InIt begin, InIt end,
1092 typename std::enable_if<
1093 !std::is_same<typename std::remove_const<InIt>::type,
1094 value_type*>::value, const A>::type & /*a*/ = A()) {
1098 // Specialization for const char*, const char*
1099 basic_fbstring(const value_type* b, const value_type* e)
1100 : store_(b, e - b) {
1103 // Nonstandard constructor
1104 basic_fbstring(value_type *s, size_type n, size_type c,
1105 AcquireMallocatedString a)
1106 : store_(s, n, c, a) {
1109 // Construction from initialization list
1110 basic_fbstring(std::initializer_list<value_type> il) {
1111 assign(il.begin(), il.end());
1114 ~basic_fbstring() noexcept {
1117 basic_fbstring& operator=(const basic_fbstring& lhs) {
1118 if (FBSTRING_UNLIKELY(&lhs == this)) {
1121 auto const oldSize = size();
1122 auto const srcSize = lhs.size();
1123 if (capacity() >= srcSize && !store_.isShared()) {
1124 // great, just copy the contents
1125 if (oldSize < srcSize)
1126 store_.expand_noinit(srcSize - oldSize);
1128 store_.shrink(oldSize - srcSize);
1129 assert(size() == srcSize);
1130 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1131 store_.writeTerminator();
1133 // need to reallocate, so we may as well create a brand new string
1134 basic_fbstring(lhs).swap(*this);
1140 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1141 if (FBSTRING_UNLIKELY(&goner == this)) {
1142 // Compatibility with std::basic_string<>,
1143 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1146 // No need of this anymore
1147 this->~basic_fbstring();
1148 // Move the goner into this
1149 new(&store_) fbstring_core<E>(std::move(goner.store_));
1153 #ifndef _LIBSTDCXX_FBSTRING
1154 // Compatibility with std::string
1155 basic_fbstring & operator=(const std::string & rhs) {
1156 return assign(rhs.data(), rhs.size());
1159 // Compatibility with std::string
1160 std::string toStdString() const {
1161 return std::string(data(), size());
1164 // A lot of code in fbcode still uses this method, so keep it here for now.
1165 const basic_fbstring& toStdString() const {
1170 basic_fbstring& operator=(const value_type* s) {
1174 basic_fbstring& operator=(value_type c) {
1176 store_.expand_noinit(1);
1177 } else if (store_.isShared()) {
1178 basic_fbstring(1, c).swap(*this);
1181 store_.shrink(size() - 1);
1183 *store_.mutable_data() = c;
1184 store_.writeTerminator();
1188 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1189 return assign(il.begin(), il.end());
1192 // C++11 21.4.3 iterators:
1193 iterator begin() { return store_.mutable_data(); }
1195 const_iterator begin() const { return store_.data(); }
1197 const_iterator cbegin() const { return begin(); }
1200 return store_.mutable_data() + store_.size();
1203 const_iterator end() const {
1204 return store_.data() + store_.size();
1207 const_iterator cend() const { return end(); }
1209 reverse_iterator rbegin() {
1210 return reverse_iterator(end());
1213 const_reverse_iterator rbegin() const {
1214 return const_reverse_iterator(end());
1217 const_reverse_iterator crbegin() const { return rbegin(); }
1219 reverse_iterator rend() {
1220 return reverse_iterator(begin());
1223 const_reverse_iterator rend() const {
1224 return const_reverse_iterator(begin());
1227 const_reverse_iterator crend() const { return rend(); }
1230 // C++11 21.4.5, element access:
1231 const value_type& front() const { return *begin(); }
1232 const value_type& back() const {
1234 // Should be begin()[size() - 1], but that branches twice
1235 return *(end() - 1);
1237 value_type& front() { return *begin(); }
1238 value_type& back() {
1240 // Should be begin()[size() - 1], but that branches twice
1241 return *(end() - 1);
1248 // C++11 21.4.4 capacity:
1249 size_type size() const { return store_.size(); }
1251 size_type length() const { return size(); }
1253 size_type max_size() const {
1254 return std::numeric_limits<size_type>::max();
1257 void resize(const size_type n, const value_type c = value_type()) {
1258 auto size = this->size();
1260 store_.shrink(size - n);
1262 // Do this in two steps to minimize slack memory copied (see
1264 auto const capacity = this->capacity();
1265 assert(capacity >= size);
1266 if (size < capacity) {
1267 auto delta = std::min(n, capacity) - size;
1268 store_.expand_noinit(delta);
1269 fbstring_detail::pod_fill(begin() + size, end(), c);
1272 store_.writeTerminator();
1277 auto const delta = n - size;
1278 store_.expand_noinit(delta);
1279 fbstring_detail::pod_fill(end() - delta, end(), c);
1280 store_.writeTerminator();
1282 assert(this->size() == n);
1285 size_type capacity() const { return store_.capacity(); }
1287 void reserve(size_type res_arg = 0) {
1288 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1289 store_.reserve(res_arg);
1292 void shrink_to_fit() {
1293 // Shrink only if slack memory is sufficiently large
1294 if (capacity() < size() * 3 / 2) {
1297 basic_fbstring(cbegin(), cend()).swap(*this);
1300 void clear() { resize(0); }
1302 bool empty() const { return size() == 0; }
1304 // C++11 21.4.5 element access:
1305 const_reference operator[](size_type pos) const {
1306 return *(begin() + pos);
1309 reference operator[](size_type pos) {
1310 return *(begin() + pos);
1313 const_reference at(size_type n) const {
1314 enforce(n <= size(), std::__throw_out_of_range, "");
1318 reference at(size_type n) {
1319 enforce(n < size(), std::__throw_out_of_range, "");
1323 // C++11 21.4.6 modifiers:
1324 basic_fbstring& operator+=(const basic_fbstring& str) {
1328 basic_fbstring& operator+=(const value_type* s) {
1332 basic_fbstring& operator+=(const value_type c) {
1337 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1342 basic_fbstring& append(const basic_fbstring& str) {
1344 auto desiredSize = size() + str.size();
1346 append(str.data(), str.size());
1347 assert(size() == desiredSize);
1351 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1353 const size_type sz = str.size();
1354 enforce(pos <= sz, std::__throw_out_of_range, "");
1355 procrustes(n, sz - pos);
1356 return append(str.data() + pos, n);
1359 basic_fbstring& append(const value_type* s, size_type n) {
1361 Invariant checker(*this);
1364 if (FBSTRING_UNLIKELY(!n)) {
1365 // Unlikely but must be done
1368 auto const oldSize = size();
1369 auto const oldData = data();
1370 // Check for aliasing (rare). We could use "<=" here but in theory
1371 // those do not work for pointers unless the pointers point to
1372 // elements in the same array. For that reason we use
1373 // std::less_equal, which is guaranteed to offer a total order
1374 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1376 std::less_equal<const value_type*> le;
1377 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1378 assert(le(s + n, oldData + oldSize));
1379 const size_type offset = s - oldData;
1380 store_.reserve(oldSize + n);
1381 // Restore the source
1382 s = data() + offset;
1384 // Warning! Repeated appends with short strings may actually incur
1385 // practically quadratic performance. Avoid that by pushing back
1386 // the first character (which ensures exponential growth) and then
1387 // appending the rest normally. Worst case the append may incur a
1388 // second allocation but that will be rare.
1391 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1392 assert(size() == oldSize + n + 1);
1396 basic_fbstring& append(const value_type* s) {
1397 return append(s, traits_type::length(s));
1400 basic_fbstring& append(size_type n, value_type c) {
1401 resize(size() + n, c);
1405 template<class InputIterator>
1406 basic_fbstring& append(InputIterator first, InputIterator last) {
1407 insert(end(), first, last);
1411 basic_fbstring& append(std::initializer_list<value_type> il) {
1412 return append(il.begin(), il.end());
1415 void push_back(const value_type c) { // primitive
1416 store_.push_back(c);
1419 basic_fbstring& assign(const basic_fbstring& str) {
1420 if (&str == this) return *this;
1421 return assign(str.data(), str.size());
1424 basic_fbstring& assign(basic_fbstring&& str) {
1425 return *this = std::move(str);
1428 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1430 const size_type sz = str.size();
1431 enforce(pos <= sz, std::__throw_out_of_range, "");
1432 procrustes(n, sz - pos);
1433 return assign(str.data() + pos, n);
1436 basic_fbstring& assign(const value_type* s, const size_type n) {
1437 Invariant checker(*this);
1440 std::copy(s, s + n, begin());
1442 assert(size() == n);
1444 const value_type *const s2 = s + size();
1445 std::copy(s, s2, begin());
1446 append(s2, n - size());
1447 assert(size() == n);
1449 store_.writeTerminator();
1450 assert(size() == n);
1454 basic_fbstring& assign(const value_type* s) {
1455 return assign(s, traits_type::length(s));
1458 basic_fbstring& assign(std::initializer_list<value_type> il) {
1459 return assign(il.begin(), il.end());
1462 template <class ItOrLength, class ItOrChar>
1463 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1464 return replace(begin(), end(), first_or_n, last_or_c);
1467 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1468 return insert(pos1, str.data(), str.size());
1471 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1472 size_type pos2, size_type n) {
1473 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1474 procrustes(n, str.length() - pos2);
1475 return insert(pos1, str.data() + pos2, n);
1478 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1479 enforce(pos <= length(), std::__throw_out_of_range, "");
1480 insert(begin() + pos, s, s + n);
1484 basic_fbstring& insert(size_type pos, const value_type* s) {
1485 return insert(pos, s, traits_type::length(s));
1488 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1489 enforce(pos <= length(), std::__throw_out_of_range, "");
1490 insert(begin() + pos, n, c);
1494 iterator insert(const_iterator p, const value_type c) {
1495 const size_type pos = p - begin();
1497 return begin() + pos;
1501 template <int i> class Selector {};
1503 iterator insertImplDiscr(const_iterator p,
1504 size_type n, value_type c, Selector<1>) {
1505 Invariant checker(*this);
1507 auto const pos = p - begin();
1508 assert(p >= begin() && p <= end());
1509 if (capacity() - size() < n) {
1510 const size_type sz = p - begin();
1511 reserve(size() + n);
1514 const iterator oldEnd = end();
1515 if (n < size_type(oldEnd - p)) {
1516 append(oldEnd - n, oldEnd);
1518 // reverse_iterator(oldEnd - n),
1519 // reverse_iterator(p),
1520 // reverse_iterator(oldEnd));
1521 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1523 std::fill(begin() + pos, begin() + pos + n, c);
1525 append(n - (end() - p), c);
1526 append(iterator(p), oldEnd);
1527 std::fill(iterator(p), oldEnd, c);
1529 store_.writeTerminator();
1530 return begin() + pos;
1533 template<class InputIter>
1534 iterator insertImplDiscr(const_iterator i,
1535 InputIter b, InputIter e, Selector<0>) {
1536 return insertImpl(i, b, e,
1537 typename std::iterator_traits<InputIter>::iterator_category());
1540 template <class FwdIterator>
1541 iterator insertImpl(const_iterator i,
1542 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1543 Invariant checker(*this);
1545 const size_type pos = i - begin();
1546 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1547 std::distance(s1, s2);
1549 using namespace fbstring_detail;
1550 assert(pos <= size());
1552 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1553 capacity() - size();
1555 // realloc the string
1556 reserve(size() + n2);
1559 if (pos + n2 <= size()) {
1560 const iterator tailBegin = end() - n2;
1561 store_.expand_noinit(n2);
1562 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1563 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1564 reverse_iterator(tailBegin + n2));
1565 std::copy(s1, s2, begin() + pos);
1568 const size_type old_size = size();
1569 std::advance(t, old_size - pos);
1570 const size_t newElems = std::distance(t, s2);
1571 store_.expand_noinit(n2);
1572 std::copy(t, s2, begin() + old_size);
1573 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1574 begin() + old_size + newElems);
1575 std::copy(s1, t, begin() + pos);
1577 store_.writeTerminator();
1578 return begin() + pos;
1581 template <class InputIterator>
1582 iterator insertImpl(const_iterator i,
1583 InputIterator b, InputIterator e,
1584 std::input_iterator_tag) {
1585 const auto pos = i - begin();
1586 basic_fbstring temp(begin(), i);
1587 for (; b != e; ++b) {
1590 temp.append(i, cend());
1592 return begin() + pos;
1596 template <class ItOrLength, class ItOrChar>
1597 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1598 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1599 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1602 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1603 return insert(p, il.begin(), il.end());
1606 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1607 Invariant checker(*this);
1609 enforce(pos <= length(), std::__throw_out_of_range, "");
1610 procrustes(n, length() - pos);
1611 std::copy(begin() + pos + n, end(), begin() + pos);
1612 resize(length() - n);
1616 iterator erase(iterator position) {
1617 const size_type pos(position - begin());
1618 enforce(pos <= size(), std::__throw_out_of_range, "");
1620 return begin() + pos;
1623 iterator erase(iterator first, iterator last) {
1624 const size_type pos(first - begin());
1625 erase(pos, last - first);
1626 return begin() + pos;
1629 // Replaces at most n1 chars of *this, starting with pos1 with the
1631 basic_fbstring& replace(size_type pos1, size_type n1,
1632 const basic_fbstring& str) {
1633 return replace(pos1, n1, str.data(), str.size());
1636 // Replaces at most n1 chars of *this, starting with pos1,
1637 // with at most n2 chars of str starting with pos2
1638 basic_fbstring& replace(size_type pos1, size_type n1,
1639 const basic_fbstring& str,
1640 size_type pos2, size_type n2) {
1641 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1642 return replace(pos1, n1, str.data() + pos2,
1643 std::min(n2, str.size() - pos2));
1646 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1647 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1648 return replace(pos, n1, s, traits_type::length(s));
1651 // Replaces at most n1 chars of *this, starting with pos, with n2
1654 // consolidated with
1656 // Replaces at most n1 chars of *this, starting with pos, with at
1657 // most n2 chars of str. str must have at least n2 chars.
1658 template <class StrOrLength, class NumOrChar>
1659 basic_fbstring& replace(size_type pos, size_type n1,
1660 StrOrLength s_or_n2, NumOrChar n_or_c) {
1661 Invariant checker(*this);
1663 enforce(pos <= size(), std::__throw_out_of_range, "");
1664 procrustes(n1, length() - pos);
1665 const iterator b = begin() + pos;
1666 return replace(b, b + n1, s_or_n2, n_or_c);
1669 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1670 return replace(i1, i2, str.data(), str.length());
1673 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1674 return replace(i1, i2, s, traits_type::length(s));
1678 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1679 const value_type* s, size_type n,
1682 assert(begin() <= i1 && i1 <= end());
1683 assert(begin() <= i2 && i2 <= end());
1684 return replace(i1, i2, s, s + n);
1687 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1688 size_type n2, value_type c, Selector<1>) {
1689 const size_type n1 = i2 - i1;
1691 std::fill(i1, i1 + n2, c);
1694 std::fill(i1, i2, c);
1695 insert(i2, n2 - n1, c);
1701 template <class InputIter>
1702 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1703 InputIter b, InputIter e,
1705 replaceImpl(i1, i2, b, e,
1706 typename std::iterator_traits<InputIter>::iterator_category());
1711 template <class FwdIterator>
1712 bool replaceAliased(iterator i1, iterator i2,
1713 FwdIterator s1, FwdIterator s2, std::false_type) {
1717 template <class FwdIterator>
1718 bool replaceAliased(iterator i1, iterator i2,
1719 FwdIterator s1, FwdIterator s2, std::true_type) {
1720 static const std::less_equal<const value_type*> le =
1721 std::less_equal<const value_type*>();
1722 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1726 // Aliased replace, copy to new string
1727 basic_fbstring temp;
1728 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1729 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1734 template <class FwdIterator>
1735 void replaceImpl(iterator i1, iterator i2,
1736 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1737 Invariant checker(*this);
1740 // Handle aliased replace
1741 if (replaceAliased(i1, i2, s1, s2,
1742 std::integral_constant<bool,
1743 std::is_same<FwdIterator, iterator>::value ||
1744 std::is_same<FwdIterator, const_iterator>::value>())) {
1748 auto const n1 = i2 - i1;
1750 auto const n2 = std::distance(s1, s2);
1755 std::copy(s1, s2, i1);
1759 fbstring_detail::copy_n(s1, n1, i1);
1760 std::advance(s1, n1);
1766 template <class InputIterator>
1767 void replaceImpl(iterator i1, iterator i2,
1768 InputIterator b, InputIterator e, std::input_iterator_tag) {
1769 basic_fbstring temp(begin(), i1);
1770 temp.append(b, e).append(i2, end());
1775 template <class T1, class T2>
1776 basic_fbstring& replace(iterator i1, iterator i2,
1777 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1779 num1 = std::numeric_limits<T1>::is_specialized,
1780 num2 = std::numeric_limits<T2>::is_specialized;
1781 return replaceImplDiscr(
1782 i1, i2, first_or_n_or_s, last_or_c_or_n,
1783 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1786 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1787 enforce(pos <= size(), std::__throw_out_of_range, "");
1788 procrustes(n, size() - pos);
1790 fbstring_detail::pod_copy(
1797 void swap(basic_fbstring& rhs) {
1798 store_.swap(rhs.store_);
1801 const value_type* c_str() const {
1802 return store_.c_str();
1805 const value_type* data() const { return c_str(); }
1807 allocator_type get_allocator() const {
1808 return allocator_type();
1811 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1812 return find(str.data(), pos, str.length());
1815 size_type find(const value_type* needle, const size_type pos,
1816 const size_type nsize) const {
1817 if (!nsize) return pos;
1818 auto const size = this->size();
1819 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1820 // that nsize + pos does not wrap around.
1821 if (nsize + pos > size || nsize + pos < pos) return npos;
1822 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1823 // the last characters first
1824 auto const haystack = data();
1825 auto const nsize_1 = nsize - 1;
1826 auto const lastNeedle = needle[nsize_1];
1828 // Boyer-Moore skip value for the last char in the needle. Zero is
1829 // not a valid value; skip will be computed the first time it's
1833 const E * i = haystack + pos;
1834 auto iEnd = haystack + size - nsize_1;
1837 // Boyer-Moore: match the last element in the needle
1838 while (i[nsize_1] != lastNeedle) {
1844 // Here we know that the last char matches
1845 // Continue in pedestrian mode
1846 for (size_t j = 0; ; ) {
1848 if (i[j] != needle[j]) {
1849 // Not found, we can skip
1850 // Compute the skip value lazily
1853 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1860 // Check if done searching
1863 return i - haystack;
1870 size_type find(const value_type* s, size_type pos = 0) const {
1871 return find(s, pos, traits_type::length(s));
1874 size_type find (value_type c, size_type pos = 0) const {
1875 return find(&c, pos, 1);
1878 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1879 return rfind(str.data(), pos, str.length());
1882 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1883 if (n > length()) return npos;
1884 pos = std::min(pos, length() - n);
1885 if (n == 0) return pos;
1887 const_iterator i(begin() + pos);
1889 if (traits_type::eq(*i, *s)
1890 && traits_type::compare(&*i, s, n) == 0) {
1893 if (i == begin()) break;
1898 size_type rfind(const value_type* s, size_type pos = npos) const {
1899 return rfind(s, pos, traits_type::length(s));
1902 size_type rfind(value_type c, size_type pos = npos) const {
1903 return rfind(&c, pos, 1);
1906 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1907 return find_first_of(str.data(), pos, str.length());
1910 size_type find_first_of(const value_type* s,
1911 size_type pos, size_type n) const {
1912 if (pos > length() || n == 0) return npos;
1913 const_iterator i(begin() + pos),
1915 for (; i != finish; ++i) {
1916 if (traits_type::find(s, n, *i) != 0) {
1923 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1924 return find_first_of(s, pos, traits_type::length(s));
1927 size_type find_first_of(value_type c, size_type pos = 0) const {
1928 return find_first_of(&c, pos, 1);
1931 size_type find_last_of (const basic_fbstring& str,
1932 size_type pos = npos) const {
1933 return find_last_of(str.data(), pos, str.length());
1936 size_type find_last_of (const value_type* s, size_type pos,
1937 size_type n) const {
1938 if (!empty() && n > 0) {
1939 pos = std::min(pos, length() - 1);
1940 const_iterator i(begin() + pos);
1942 if (traits_type::find(s, n, *i) != 0) {
1945 if (i == begin()) break;
1951 size_type find_last_of (const value_type* s,
1952 size_type pos = npos) const {
1953 return find_last_of(s, pos, traits_type::length(s));
1956 size_type find_last_of (value_type c, size_type pos = npos) const {
1957 return find_last_of(&c, pos, 1);
1960 size_type find_first_not_of(const basic_fbstring& str,
1961 size_type pos = 0) const {
1962 return find_first_not_of(str.data(), pos, str.size());
1965 size_type find_first_not_of(const value_type* s, size_type pos,
1966 size_type n) const {
1967 if (pos < length()) {
1971 for (; i != finish; ++i) {
1972 if (traits_type::find(s, n, *i) == 0) {
1980 size_type find_first_not_of(const value_type* s,
1981 size_type pos = 0) const {
1982 return find_first_not_of(s, pos, traits_type::length(s));
1985 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1986 return find_first_not_of(&c, pos, 1);
1989 size_type find_last_not_of(const basic_fbstring& str,
1990 size_type pos = npos) const {
1991 return find_last_not_of(str.data(), pos, str.length());
1994 size_type find_last_not_of(const value_type* s, size_type pos,
1995 size_type n) const {
1996 if (!this->empty()) {
1997 pos = std::min(pos, size() - 1);
1998 const_iterator i(begin() + pos);
2000 if (traits_type::find(s, n, *i) == 0) {
2003 if (i == begin()) break;
2009 size_type find_last_not_of(const value_type* s,
2010 size_type pos = npos) const {
2011 return find_last_not_of(s, pos, traits_type::length(s));
2014 size_type find_last_not_of (value_type c, size_type pos = npos) const {
2015 return find_last_not_of(&c, pos, 1);
2018 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
2019 enforce(pos <= size(), std::__throw_out_of_range, "");
2020 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2023 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
2024 enforce(pos <= size(), std::__throw_out_of_range, "");
2026 if (n < size()) resize(n);
2027 return std::move(*this);
2030 int compare(const basic_fbstring& str) const {
2031 // FIX due to Goncalo N M de Carvalho July 18, 2005
2032 return compare(0, size(), str);
2035 int compare(size_type pos1, size_type n1,
2036 const basic_fbstring& str) const {
2037 return compare(pos1, n1, str.data(), str.size());
2040 int compare(size_type pos1, size_type n1,
2041 const value_type* s) const {
2042 return compare(pos1, n1, s, traits_type::length(s));
2045 int compare(size_type pos1, size_type n1,
2046 const value_type* s, size_type n2) const {
2047 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2048 procrustes(n1, size() - pos1);
2049 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2050 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2051 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2054 int compare(size_type pos1, size_type n1,
2055 const basic_fbstring& str,
2056 size_type pos2, size_type n2) const {
2057 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2058 return compare(pos1, n1, str.data() + pos2,
2059 std::min(n2, str.size() - pos2));
2062 // Code from Jean-Francois Bastien (03/26/2007)
2063 int compare(const value_type* s) const {
2064 // Could forward to compare(0, size(), s, traits_type::length(s))
2065 // but that does two extra checks
2066 const size_type n1(size()), n2(traits_type::length(s));
2067 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2068 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2076 // non-member functions
2078 template <typename E, class T, class A, class S>
2080 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2081 const basic_fbstring<E, T, A, S>& rhs) {
2083 basic_fbstring<E, T, A, S> result;
2084 result.reserve(lhs.size() + rhs.size());
2085 result.append(lhs).append(rhs);
2086 return std::move(result);
2090 template <typename E, class T, class A, class S>
2092 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2093 const basic_fbstring<E, T, A, S>& rhs) {
2094 return std::move(lhs.append(rhs));
2098 template <typename E, class T, class A, class S>
2100 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2101 basic_fbstring<E, T, A, S>&& rhs) {
2102 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2103 // Good, at least we don't need to reallocate
2104 return std::move(rhs.insert(0, lhs));
2106 // Meh, no go. Forward to operator+(const&, const&).
2107 auto const& rhsC = rhs;
2112 template <typename E, class T, class A, class S>
2114 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2115 basic_fbstring<E, T, A, S>&& rhs) {
2116 return std::move(lhs.append(rhs));
2120 template <typename E, class T, class A, class S>
2122 basic_fbstring<E, T, A, S> operator+(
2124 const basic_fbstring<E, T, A, S>& rhs) {
2126 basic_fbstring<E, T, A, S> result;
2127 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2128 result.reserve(len + rhs.size());
2129 result.append(lhs, len).append(rhs);
2134 template <typename E, class T, class A, class S>
2136 basic_fbstring<E, T, A, S> operator+(
2138 basic_fbstring<E, T, A, S>&& rhs) {
2140 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2141 if (rhs.capacity() >= len + rhs.size()) {
2142 // Good, at least we don't need to reallocate
2143 return std::move(rhs.insert(rhs.begin(), lhs, lhs + len));
2145 // Meh, no go. Do it by hand since we have len already.
2146 basic_fbstring<E, T, A, S> result;
2147 result.reserve(len + rhs.size());
2148 result.append(lhs, len).append(rhs);
2153 template <typename E, class T, class A, class S>
2155 basic_fbstring<E, T, A, S> operator+(
2157 const basic_fbstring<E, T, A, S>& rhs) {
2159 basic_fbstring<E, T, A, S> result;
2160 result.reserve(1 + rhs.size());
2161 result.push_back(lhs);
2167 template <typename E, class T, class A, class S>
2169 basic_fbstring<E, T, A, S> operator+(
2171 basic_fbstring<E, T, A, S>&& rhs) {
2173 if (rhs.capacity() > rhs.size()) {
2174 // Good, at least we don't need to reallocate
2175 return std::move(rhs.insert(rhs.begin(), lhs));
2177 // Meh, no go. Forward to operator+(E, const&).
2178 auto const& rhsC = rhs;
2183 template <typename E, class T, class A, class S>
2185 basic_fbstring<E, T, A, S> operator+(
2186 const basic_fbstring<E, T, A, S>& lhs,
2189 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2190 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2192 basic_fbstring<E, T, A, S> result;
2193 const size_type len = traits_type::length(rhs);
2194 result.reserve(lhs.size() + len);
2195 result.append(lhs).append(rhs, len);
2199 // C++11 21.4.8.1/10
2200 template <typename E, class T, class A, class S>
2202 basic_fbstring<E, T, A, S> operator+(
2203 basic_fbstring<E, T, A, S>&& lhs,
2206 return std::move(lhs += rhs);
2209 // C++11 21.4.8.1/11
2210 template <typename E, class T, class A, class S>
2212 basic_fbstring<E, T, A, S> operator+(
2213 const basic_fbstring<E, T, A, S>& lhs,
2216 basic_fbstring<E, T, A, S> result;
2217 result.reserve(lhs.size() + 1);
2219 result.push_back(rhs);
2223 // C++11 21.4.8.1/12
2224 template <typename E, class T, class A, class S>
2226 basic_fbstring<E, T, A, S> operator+(
2227 basic_fbstring<E, T, A, S>&& lhs,
2230 return std::move(lhs += rhs);
2233 template <typename E, class T, class A, class S>
2235 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2236 const basic_fbstring<E, T, A, S>& rhs) {
2237 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2239 template <typename E, class T, class A, class S>
2241 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2242 const basic_fbstring<E, T, A, S>& rhs) {
2243 return rhs == lhs; }
2245 template <typename E, class T, class A, class S>
2247 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2248 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2249 return lhs.compare(rhs) == 0; }
2251 template <typename E, class T, class A, class S>
2253 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2254 const basic_fbstring<E, T, A, S>& rhs) {
2255 return !(lhs == rhs); }
2257 template <typename E, class T, class A, class S>
2259 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2260 const basic_fbstring<E, T, A, S>& rhs) {
2261 return !(lhs == rhs); }
2263 template <typename E, class T, class A, class S>
2265 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2266 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2267 return !(lhs == rhs); }
2269 template <typename E, class T, class A, class S>
2271 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2272 const basic_fbstring<E, T, A, S>& rhs) {
2273 return lhs.compare(rhs) < 0; }
2275 template <typename E, class T, class A, class S>
2277 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2278 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2279 return lhs.compare(rhs) < 0; }
2281 template <typename E, class T, class A, class S>
2283 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2284 const basic_fbstring<E, T, A, S>& rhs) {
2285 return rhs.compare(lhs) > 0; }
2287 template <typename E, class T, class A, class S>
2289 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2290 const basic_fbstring<E, T, A, S>& rhs) {
2293 template <typename E, class T, class A, class S>
2295 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2296 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2299 template <typename E, class T, class A, class S>
2301 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2302 const basic_fbstring<E, T, A, S>& rhs) {
2305 template <typename E, class T, class A, class S>
2307 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2308 const basic_fbstring<E, T, A, S>& rhs) {
2309 return !(rhs < lhs); }
2311 template <typename E, class T, class A, class S>
2313 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2314 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2315 return !(rhs < lhs); }
2317 template <typename E, class T, class A, class S>
2319 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2320 const basic_fbstring<E, T, A, S>& rhs) {
2321 return !(rhs < lhs); }
2323 template <typename E, class T, class A, class S>
2325 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2326 const basic_fbstring<E, T, A, S>& rhs) {
2327 return !(lhs < rhs); }
2329 template <typename E, class T, class A, class S>
2331 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2332 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2333 return !(lhs < rhs); }
2335 template <typename E, class T, class A, class S>
2337 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2338 const basic_fbstring<E, T, A, S>& rhs) {
2339 return !(lhs < rhs);
2343 template <typename E, class T, class A, class S>
2344 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2348 // TODO: make this faster.
2349 template <typename E, class T, class A, class S>
2352 typename basic_fbstring<E, T, A, S>::value_type,
2353 typename basic_fbstring<E, T, A, S>::traits_type>&
2355 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2356 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2357 basic_fbstring<E, T, A, S>& str) {
2358 typename std::basic_istream<E, T>::sentry sentry(is);
2359 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2360 typename basic_fbstring<E, T, A, S>::traits_type>
2362 typedef typename __istream_type::ios_base __ios_base;
2363 size_t extracted = 0;
2364 auto err = __ios_base::goodbit;
2366 auto n = is.width();
2371 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2372 if (got == T::eof()) {
2373 err |= __ios_base::eofbit;
2377 if (isspace(got)) break;
2379 got = is.rdbuf()->snextc();
2383 err |= __ios_base::failbit;
2391 template <typename E, class T, class A, class S>
2393 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2394 typename basic_fbstring<E, T, A, S>::traits_type>&
2396 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2397 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2398 const basic_fbstring<E, T, A, S>& str) {
2400 typename std::basic_ostream<
2401 typename basic_fbstring<E, T, A, S>::value_type,
2402 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2404 typedef std::ostreambuf_iterator<
2405 typename basic_fbstring<E, T, A, S>::value_type,
2406 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2407 size_t __len = str.size();
2409 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2410 if (__pad_and_output(_Ip(os),
2412 __left ? str.data() + __len : str.data(),
2415 os.fill()).failed()) {
2416 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2419 #elif defined(_MSC_VER)
2420 // MSVC doesn't define __ostream_insert
2421 os.write(str.data(), str.size());
2423 std::__ostream_insert(os, str.data(), str.size());
2428 #ifndef _LIBSTDCXX_FBSTRING
2430 template <typename E, class T, class A, class S>
2432 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2433 typename basic_fbstring<E, T, A, S>::traits_type>&
2435 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2436 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2437 basic_fbstring<E, T, A, S>& str,
2438 typename basic_fbstring<E, T, A, S>::value_type delim) {
2439 // Use the nonstandard getdelim()
2440 char * buf = nullptr;
2443 // This looks quadratic but it really depends on realloc
2444 auto const newSize = size + 128;
2445 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2446 is.getline(buf + size, newSize - size, delim);
2447 if (is.bad() || is.eof() || !is.fail()) {
2448 // done by either failure, end of file, or normal read
2449 size += std::strlen(buf + size);
2452 // Here we have failed due to too short a buffer
2453 // Minus one to discount the terminating '\0'
2455 assert(buf[size] == 0);
2456 // Clear the error so we can continue reading
2459 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2460 AcquireMallocatedString());
2465 template <typename E, class T, class A, class S>
2467 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2468 typename basic_fbstring<E, T, A, S>::traits_type>&
2470 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2471 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2472 basic_fbstring<E, T, A, S>& str) {
2473 // Just forward to the version with a delimiter
2474 return getline(is, str, '\n');
2479 template <typename E1, class T, class A, class S>
2480 const typename basic_fbstring<E1, T, A, S>::size_type
2481 basic_fbstring<E1, T, A, S>::npos =
2482 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2484 #ifndef _LIBSTDCXX_FBSTRING
2485 // basic_string compatibility routines
2487 template <typename E, class T, class A, class S>
2489 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2490 const std::string& rhs) {
2491 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2494 template <typename E, class T, class A, class S>
2496 bool operator==(const std::string& lhs,
2497 const basic_fbstring<E, T, A, S>& rhs) {
2501 template <typename E, class T, class A, class S>
2503 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2504 const std::string& rhs) {
2505 return !(lhs == rhs);
2508 template <typename E, class T, class A, class S>
2510 bool operator!=(const std::string& lhs,
2511 const basic_fbstring<E, T, A, S>& rhs) {
2512 return !(lhs == rhs);
2515 #if !defined(_LIBSTDCXX_FBSTRING)
2516 typedef basic_fbstring<char> fbstring;
2519 // fbstring is relocatable
2520 template <class T, class R, class A, class S>
2521 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2524 _GLIBCXX_END_NAMESPACE_VERSION
2527 } // namespace folly
2529 #ifndef _LIBSTDCXX_FBSTRING
2531 // Hash functions to make fbstring usable with e.g. hash_map
2533 // Handle interaction with different C++ standard libraries, which
2534 // expect these types to be in different namespaces.
2536 #define FOLLY_FBSTRING_HASH1(T) \
2538 struct hash< ::folly::basic_fbstring<T> > { \
2539 size_t operator()(const ::folly::fbstring& s) const { \
2540 return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2544 // The C++11 standard says that these four are defined
2545 #define FOLLY_FBSTRING_HASH \
2546 FOLLY_FBSTRING_HASH1(char) \
2547 FOLLY_FBSTRING_HASH1(char16_t) \
2548 FOLLY_FBSTRING_HASH1(char32_t) \
2549 FOLLY_FBSTRING_HASH1(wchar_t)
2557 #if FOLLY_HAVE_DEPRECATED_ASSOC
2558 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2559 namespace __gnu_cxx {
2563 } // namespace __gnu_cxx
2564 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2565 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2567 #undef FOLLY_FBSTRING_HASH
2568 #undef FOLLY_FBSTRING_HASH1
2570 #endif // _LIBSTDCXX_FBSTRING
2572 #pragma GCC diagnostic pop
2574 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2576 #undef FBSTRING_LIKELY
2577 #undef FBSTRING_UNLIKELY
2579 #endif // FOLLY_BASE_FBSTRING_H_