2 * Copyright 2016 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)
24 #include <type_traits>
26 // This file appears in two locations: inside fbcode and in the
27 // libstdc++ source code (when embedding fbstring as std::string).
28 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
29 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
30 #ifdef _LIBSTDCXX_FBSTRING
32 #pragma GCC system_header
34 // When used as std::string replacement always disable assertions.
37 #define FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
40 #include "basic_fbstring_malloc.h"
42 #else // !_LIBSTDCXX_FBSTRING
44 #include <folly/Portability.h>
46 // libc++ doesn't provide this header, nor does msvc
47 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
48 #include <bits/c++config.h>
56 #include <folly/Traits.h>
57 #include <folly/Malloc.h>
58 #include <folly/Hash.h>
59 #include <folly/ScopeGuard.h>
61 #if FOLLY_HAVE_DEPRECATED_ASSOC
62 #ifdef _GLIBCXX_SYMVER
63 #include <ext/hash_set>
64 #include <ext/hash_map>
70 // We defined these here rather than including Likely.h to avoid
71 // redefinition errors when fbstring is imported into libstdc++.
72 #if defined(__GNUC__) && __GNUC__ >= 4
73 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
74 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
76 #define FBSTRING_LIKELY(x) (x)
77 #define FBSTRING_UNLIKELY(x) (x)
80 #pragma GCC diagnostic push
81 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
82 #pragma GCC diagnostic ignored "-Wshadow"
83 // GCC 4.9 has a false positive in setSmallSize (probably
84 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
85 // compile-time array bound checking.
86 #pragma GCC diagnostic ignored "-Warray-bounds"
88 // FBString cannot use throw when replacing std::string, though it may still
91 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
93 #ifdef _LIBSTDCXX_FBSTRING
94 namespace std _GLIBCXX_VISIBILITY(default) {
95 _GLIBCXX_BEGIN_NAMESPACE_VERSION
100 #if defined(__clang__)
101 # if __has_feature(address_sanitizer)
102 # define FBSTRING_SANITIZE_ADDRESS
104 #elif defined (__GNUC__) && \
105 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
107 # define FBSTRING_SANITIZE_ADDRESS
110 // When compiling with ASan, always heap-allocate the string even if
111 // it would fit in-situ, so that ASan can detect access to the string
112 // buffer after it has been invalidated (destroyed, resized, etc.).
113 // Note that this flag doesn't remove support for in-situ strings, as
114 // that would break ABI-compatibility and wouldn't allow linking code
115 // compiled with this flag with code compiled without.
116 #ifdef FBSTRING_SANITIZE_ADDRESS
117 # define FBSTRING_DISABLE_SSO true
119 # define FBSTRING_DISABLE_SSO false
122 namespace fbstring_detail {
124 template <class InIt, class OutIt>
127 typename std::iterator_traits<InIt>::difference_type n,
129 for (; n != 0; --n, ++b, ++d) {
135 template <class Pod, class T>
136 inline void pod_fill(Pod* b, Pod* e, T c) {
137 assert(b && e && b <= e);
138 /*static*/ if (sizeof(T) == 1) {
141 auto const ee = b + ((e - b) & ~7u);
142 for (; b != ee; b += 8) {
153 for (; b != e; ++b) {
160 * Lightly structured memcpy, simplifies copying PODs and introduces
161 * some asserts. Unfortunately using this function may cause
162 * measurable overhead (presumably because it adjusts from a begin/end
163 * convention to a pointer/size convention, so it does some extra
164 * arithmetic even though the caller might have done the inverse
165 * adaptation outside).
168 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
170 assert(d >= e || d + (e - b) <= b);
171 memcpy(d, b, (e - b) * sizeof(Pod));
175 * Lightly structured memmove, simplifies copying PODs and introduces
179 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
181 memmove(d, b, (e - b) * sizeof(*b));
184 } // namespace fbstring_detail
187 * Defines a special acquisition method for constructing fbstring
188 * objects. AcquireMallocatedString means that the user passes a
189 * pointer to a malloc-allocated string that the fbstring object will
192 enum class AcquireMallocatedString {};
195 * fbstring_core_model is a mock-up type that defines all required
196 * signatures of a fbstring core. The fbstring class itself uses such
197 * a core object to implement all of the numerous member functions
198 * required by the standard.
200 * If you want to define a new core, copy the definition below and
201 * implement the primitives. Then plug the core into basic_fbstring as
202 * a template argument.
204 template <class Char>
205 class fbstring_core_model {
207 fbstring_core_model();
208 fbstring_core_model(const fbstring_core_model &);
209 ~fbstring_core_model();
210 // Returns a pointer to string's buffer (currently only contiguous
211 // strings are supported). The pointer is guaranteed to be valid
212 // until the next call to a non-const member function.
213 const Char * data() const;
214 // Much like data(), except the string is prepared to support
215 // character-level changes. This call is a signal for
216 // e.g. reference-counted implementation to fork the data. The
217 // pointer is guaranteed to be valid until the next call to a
218 // non-const member function.
219 Char * mutable_data();
220 // Returns a pointer to string's buffer and guarantees that a
221 // readable '\0' lies right after the buffer. The pointer is
222 // guaranteed to be valid until the next call to a non-const member
224 const Char * c_str() const;
225 // Shrinks the string by delta characters. Asserts that delta <=
227 void shrink(size_t delta);
228 // Expands the string by delta characters (i.e. after this call
229 // size() will report the old size() plus delta) but without
230 // initializing the expanded region. The expanded region is
231 // zero-terminated. Returns a pointer to the memory to be
232 // initialized (the beginning of the expanded portion). The caller
233 // is expected to fill the expanded area appropriately.
234 // If expGrowth is true, exponential growth is guaranteed.
235 // It is not guaranteed not to reallocate even if size() + delta <
236 // capacity(), so all references to the buffer are invalidated.
237 Char* expand_noinit(size_t delta, bool expGrowth);
238 // Expands the string by one character and sets the last character
240 void push_back(Char c);
241 // Returns the string's size.
243 // Returns the string's capacity, i.e. maximum size that the string
244 // can grow to without reallocation. Note that for reference counted
245 // strings that's technically a lie - even assigning characters
246 // within the existing size would cause a reallocation.
247 size_t capacity() const;
248 // Returns true if the data underlying the string is actually shared
249 // across multiple strings (in a refcounted fashion).
250 bool isShared() const;
251 // Makes sure that at least minCapacity characters are available for
252 // the string without reallocation. For reference-counted strings,
253 // it should fork the data even if minCapacity < size().
254 void reserve(size_t minCapacity);
257 fbstring_core_model& operator=(const fbstring_core_model &);
262 * This is the core of the string. The code should work on 32- and
263 * 64-bit and both big- and little-endianan architectures with any
266 * The storage is selected as follows (assuming we store one-byte
267 * characters on a 64-bit machine): (a) "small" strings between 0 and
268 * 23 chars are stored in-situ without allocation (the rightmost byte
269 * stores the size); (b) "medium" strings from 24 through 254 chars
270 * are stored in malloc-allocated memory that is copied eagerly; (c)
271 * "large" strings of 255 chars and above are stored in a similar
272 * structure as medium arrays, except that the string is
273 * reference-counted and copied lazily. the reference count is
274 * allocated right before the character array.
276 * The discriminator between these three strategies sits in two
277 * bits of the rightmost char of the storage. If neither is set, then the
278 * string is small (and its length sits in the lower-order bits on
279 * little-endian or the high-order bits on big-endian of that
280 * rightmost character). If the MSb is set, the string is medium width.
281 * If the second MSb is set, then the string is large. On little-endian,
282 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
283 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
284 * and big-endian fbstring_core equivalent with merely different ops used
285 * to extract capacity/category.
287 template <class Char> class fbstring_core {
289 // It's MSVC, so we just have to guess ... and allow an override
291 # ifdef FOLLY_ENDIAN_BE
292 static constexpr auto kIsLittleEndian = false;
294 static constexpr auto kIsLittleEndian = true;
297 static constexpr auto kIsLittleEndian =
298 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
301 fbstring_core() noexcept { reset(); }
303 fbstring_core(const fbstring_core & rhs) {
304 assert(&rhs != this);
305 // Simplest case first: small strings are bitblitted
306 if (rhs.category() == Category::isSmall) {
307 static_assert(offsetof(MediumLarge, data_) == 0,
308 "fbstring layout failure");
309 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
310 "fbstring layout failure");
311 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
312 "fbstring layout failure");
313 // Just write the whole thing, don't look at details. In
314 // particular we need to copy capacity anyway because we want
315 // to set the size (don't forget that the last character,
316 // which stores a short string's length, is shared with the
317 // ml_.capacity field).
319 assert(category() == Category::isSmall && this->size() == rhs.size());
320 } else if (rhs.category() == Category::isLarge) {
321 // Large strings are just refcounted
323 RefCounted::incrementRefs(ml_.data_);
324 assert(category() == Category::isLarge && size() == rhs.size());
326 // Medium strings are copied eagerly. Don't forget to allocate
327 // one extra Char for the null terminator.
328 auto const allocSize =
329 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
330 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
331 // Also copies terminator.
332 fbstring_detail::pod_copy(rhs.ml_.data_,
333 rhs.ml_.data_ + rhs.ml_.size_ + 1,
335 ml_.size_ = rhs.ml_.size_;
336 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
337 assert(category() == Category::isMedium);
339 assert(size() == rhs.size());
340 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
343 fbstring_core(fbstring_core&& goner) noexcept {
346 // Clean goner's carcass
350 fbstring_core(const Char *const data,
352 bool disableSSO = FBSTRING_DISABLE_SSO) {
354 #ifndef _LIBSTDCXX_FBSTRING
356 assert(this->size() == size);
357 assert(size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
362 // Simplest case first: small strings are bitblitted
363 if (!disableSSO && size <= maxSmallSize) {
364 // Layout is: Char* data_, size_t size_, size_t capacity_
365 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
366 "fbstring has unexpected size");
367 static_assert(sizeof(Char*) == sizeof(size_t),
368 "fbstring size assumption violation");
369 // sizeof(size_t) must be a power of 2
370 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
371 "fbstring size assumption violation");
373 // If data is aligned, use fast word-wise copying. Otherwise,
374 // use conservative memcpy.
375 // The word-wise path reads bytes which are outside the range of
376 // the string, and makes ASan unhappy, so we disable it when
377 // compiling with ASan.
378 #ifndef FBSTRING_SANITIZE_ADDRESS
379 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
380 const size_t byteSize = size * sizeof(Char);
381 constexpr size_t wordWidth = sizeof(size_t);
382 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
384 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
386 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
388 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
396 fbstring_detail::pod_copy(data, data + size, small_);
401 if (size <= maxMediumSize) {
402 // Medium strings are allocated normally. Don't forget to
403 // allocate one extra Char for the terminating null.
404 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
405 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
406 fbstring_detail::pod_copy(data, data + size, ml_.data_);
408 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
410 // Large strings are allocated differently
411 size_t effectiveCapacity = size;
412 auto const newRC = RefCounted::create(data, & effectiveCapacity);
413 ml_.data_ = newRC->data_;
415 ml_.setCapacity(effectiveCapacity, Category::isLarge);
417 ml_.data_[size] = '\0';
421 ~fbstring_core() noexcept {
422 auto const c = category();
423 if (c == Category::isSmall) {
426 if (c == Category::isMedium) {
430 RefCounted::decrementRefs(ml_.data_);
433 // Snatches a previously mallocated string. The parameter "size"
434 // is the size of the string, and the parameter "allocatedSize"
435 // is the size of the mallocated block. The string must be
436 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
438 // So if you want a 2-character string, pass malloc(3) as "data",
439 // pass 2 as "size", and pass 3 as "allocatedSize".
440 fbstring_core(Char * const data,
442 const size_t allocatedSize,
443 AcquireMallocatedString) {
445 assert(allocatedSize >= size + 1);
446 assert(data[size] == '\0');
447 // Use the medium string storage
450 // Don't forget about null terminator
451 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
453 // No need for the memory
459 // swap below doesn't test whether &rhs == this (and instead
460 // potentially does extra work) on the premise that the rarity of
461 // that situation actually makes the check more expensive than is
463 void swap(fbstring_core & rhs) {
469 // In C++11 data() and c_str() are 100% equivalent.
470 const Char * data() const {
474 Char * mutable_data() {
475 auto const c = category();
476 if (c == Category::isSmall) {
479 assert(c == Category::isMedium || c == Category::isLarge);
480 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
482 size_t effectiveCapacity = ml_.capacity();
483 auto const newRC = RefCounted::create(& effectiveCapacity);
484 // If this fails, someone placed the wrong capacity in an
486 assert(effectiveCapacity >= ml_.capacity());
487 // Also copies terminator.
488 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
490 RefCounted::decrementRefs(ml_.data_);
491 ml_.data_ = newRC->data_;
496 const Char * c_str() const {
497 auto const c = category();
498 if (c == Category::isSmall) {
499 assert(small_[smallSize()] == '\0');
502 assert(c == Category::isMedium || c == Category::isLarge);
503 assert(ml_.data_[ml_.size_] == '\0');
507 void shrink(const size_t delta) {
508 if (category() == Category::isSmall) {
509 // Check for underflow
510 assert(delta <= smallSize());
511 setSmallSize(smallSize() - delta);
512 } else if (category() == Category::isMedium ||
513 RefCounted::refs(ml_.data_) == 1) {
514 // Medium strings and unique large strings need no special
516 assert(ml_.size_ >= delta);
518 ml_.data_[ml_.size_] = '\0';
520 assert(ml_.size_ >= delta);
521 // Shared large string, must make unique. This is because of the
522 // durn terminator must be written, which may trample the shared
525 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
527 // No need to write the terminator.
531 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
532 if (category() == Category::isLarge) {
534 if (RefCounted::refs(ml_.data_) > 1) {
535 // We must make it unique regardless; in-place reallocation is
536 // useless if the string is shared. In order to not surprise
537 // people, reserve the new block at current capacity or
538 // more. That way, a string's capacity never shrinks after a
540 minCapacity = std::max(minCapacity, ml_.capacity());
541 auto const newRC = RefCounted::create(& minCapacity);
542 // Also copies terminator.
543 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
545 RefCounted::decrementRefs(ml_.data_);
546 ml_.data_ = newRC->data_;
547 ml_.setCapacity(minCapacity, Category::isLarge);
548 // size remains unchanged
550 // String is not shared, so let's try to realloc (if needed)
551 if (minCapacity > ml_.capacity()) {
552 // Asking for more memory
554 RefCounted::reallocate(ml_.data_, ml_.size_,
555 ml_.capacity(), minCapacity);
556 ml_.data_ = newRC->data_;
557 ml_.setCapacity(minCapacity, Category::isLarge);
559 assert(capacity() >= minCapacity);
561 } else if (category() == Category::isMedium) {
562 // String is not shared
563 if (minCapacity <= ml_.capacity()) {
564 return; // nothing to do, there's enough room
566 if (minCapacity <= maxMediumSize) {
567 // Keep the string at medium size. Don't forget to allocate
568 // one extra Char for the terminating null.
569 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
570 // Also copies terminator.
571 ml_.data_ = static_cast<Char *>(
574 (ml_.size_ + 1) * sizeof(Char),
575 (ml_.capacity() + 1) * sizeof(Char),
577 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
579 // Conversion from medium to large string
580 fbstring_core nascent;
581 // Will recurse to another branch of this function
582 nascent.reserve(minCapacity);
583 nascent.ml_.size_ = ml_.size_;
584 // Also copies terminator.
585 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
588 assert(capacity() >= minCapacity);
591 assert(category() == Category::isSmall);
592 if (!disableSSO && minCapacity <= maxSmallSize) {
594 // Nothing to do, everything stays put
595 } else if (minCapacity <= maxMediumSize) {
597 // Don't forget to allocate one extra Char for the terminating null
598 auto const allocSizeBytes =
599 goodMallocSize((1 + minCapacity) * sizeof(Char));
600 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
601 auto const size = smallSize();
602 // Also copies terminator.
603 fbstring_detail::pod_copy(small_, small_ + size + 1, pData);
606 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
609 auto const newRC = RefCounted::create(& minCapacity);
610 auto const size = smallSize();
611 // Also copies terminator.
612 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
613 ml_.data_ = newRC->data_;
615 ml_.setCapacity(minCapacity, Category::isLarge);
616 assert(capacity() >= minCapacity);
619 assert(capacity() >= minCapacity);
622 Char * expand_noinit(const size_t delta,
623 bool expGrowth = false,
624 bool disableSSO = FBSTRING_DISABLE_SSO) {
625 // Strategy is simple: make room, then change size
626 assert(capacity() >= size());
628 if (category() == Category::isSmall) {
631 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
635 reserve(expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz);
639 if (FBSTRING_UNLIKELY(newSz > capacity())) {
640 // ensures not shared
641 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
644 assert(capacity() >= newSz);
645 // Category can't be small - we took care of that above
646 assert(category() == Category::isMedium || category() == Category::isLarge);
648 ml_.data_[newSz] = '\0';
649 assert(size() == newSz);
650 return ml_.data_ + sz;
653 void push_back(Char c) {
654 *expand_noinit(1, /* expGrowth = */ true) = c;
657 size_t size() const {
658 return category() == Category::isSmall ? smallSize() : ml_.size_;
661 size_t capacity() const {
662 switch (category()) {
663 case Category::isSmall:
665 case Category::isLarge:
666 // For large-sized strings, a multi-referenced chunk has no
667 // available capacity. This is because any attempt to append
668 // data would trigger a new allocation.
669 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
672 return ml_.capacity();
675 bool isShared() const {
676 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
681 fbstring_core & operator=(const fbstring_core & rhs);
683 // Equivalent to setSmallSize(0) but a few ns faster in
686 ml_.capacity_ = kIsLittleEndian
687 ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
690 assert(category() == Category::isSmall && size() == 0);
694 std::atomic<size_t> refCount_;
697 static RefCounted * fromData(Char * p) {
698 return static_cast<RefCounted*>(
700 static_cast<unsigned char*>(static_cast<void*>(p))
701 - sizeof(refCount_)));
704 static size_t refs(Char * p) {
705 return fromData(p)->refCount_.load(std::memory_order_acquire);
708 static void incrementRefs(Char * p) {
709 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
712 static void decrementRefs(Char * p) {
713 auto const dis = fromData(p);
714 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
721 static RefCounted * create(size_t * size) {
722 // Don't forget to allocate one extra Char for the terminating
723 // null. In this case, however, one Char is already part of the
725 const size_t allocSize = goodMallocSize(
726 sizeof(RefCounted) + *size * sizeof(Char));
727 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
728 result->refCount_.store(1, std::memory_order_release);
729 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
733 static RefCounted * create(const Char * data, size_t * size) {
734 const size_t effectiveSize = *size;
735 auto result = create(size);
736 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
740 static RefCounted * reallocate(Char *const data,
741 const size_t currentSize,
742 const size_t currentCapacity,
743 const size_t newCapacity) {
744 assert(newCapacity > 0 && newCapacity > currentSize);
745 auto const dis = fromData(data);
746 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
747 // Don't forget to allocate one extra Char for the terminating
748 // null. In this case, however, one Char is already part of the
750 auto result = static_cast<RefCounted*>(
752 sizeof(RefCounted) + currentSize * sizeof(Char),
753 sizeof(RefCounted) + currentCapacity * sizeof(Char),
754 sizeof(RefCounted) + newCapacity * sizeof(Char)));
755 assert(result->refCount_.load(std::memory_order_acquire) == 1);
760 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
763 enum class Category : category_type {
765 isMedium = kIsLittleEndian
766 ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
768 isLarge = kIsLittleEndian
769 ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
773 Category category() const {
774 // works for both big-endian and little-endian
775 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
783 size_t capacity() const {
784 return kIsLittleEndian
785 ? capacity_ & capacityExtractMask
789 void setCapacity(size_t cap, Category cat) {
790 capacity_ = kIsLittleEndian
791 ? cap | static_cast<category_type>(cat)
792 : (cap << 2) | static_cast<category_type>(cat);
797 Char small_[sizeof(MediumLarge) / sizeof(Char)];
802 lastChar = sizeof(MediumLarge) - 1,
803 maxSmallSize = lastChar / sizeof(Char),
804 maxMediumSize = 254 / sizeof(Char), // coincides with the small
805 // bin size in dlmalloc
806 categoryExtractMask = kIsLittleEndian
807 ? sizeof(size_t) == 4 ? 0xC0000000 : size_t(0xC000000000000000)
809 capacityExtractMask = kIsLittleEndian
810 ? ~categoryExtractMask
813 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
814 "Corrupt memory layout for fbstring.");
816 size_t smallSize() const {
817 assert(category() == Category::isSmall);
818 constexpr auto shift = kIsLittleEndian ? 0 : 2;
819 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
820 assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
821 return static_cast<size_t>(maxSmallSize) - smallShifted;
824 void setSmallSize(size_t s) {
825 // Warning: this should work with uninitialized strings too,
826 // so don't assume anything about the previous value of
827 // small_[maxSmallSize].
828 assert(s <= maxSmallSize);
829 constexpr auto shift = kIsLittleEndian ? 0 : 2;
830 small_[maxSmallSize] = (maxSmallSize - s) << shift;
832 assert(category() == Category::isSmall && size() == s);
836 #ifndef _LIBSTDCXX_FBSTRING
838 * Dummy fbstring core that uses an actual std::string. This doesn't
839 * make any sense - it's just for testing purposes.
841 template <class Char>
842 class dummy_fbstring_core {
844 dummy_fbstring_core() {
846 dummy_fbstring_core(const dummy_fbstring_core& another)
847 : backend_(another.backend_) {
849 dummy_fbstring_core(const Char * s, size_t n)
852 void swap(dummy_fbstring_core & rhs) {
853 backend_.swap(rhs.backend_);
855 const Char * data() const {
856 return backend_.data();
858 Char * mutable_data() {
859 //assert(!backend_.empty());
860 return &*backend_.begin();
862 void shrink(size_t delta) {
863 assert(delta <= size());
864 backend_.resize(size() - delta);
866 Char * expand_noinit(size_t delta) {
867 auto const sz = size();
868 backend_.resize(size() + delta);
869 return backend_.data() + sz;
871 void push_back(Char c) {
872 backend_.push_back(c);
874 size_t size() const {
875 return backend_.size();
877 size_t capacity() const {
878 return backend_.capacity();
880 bool isShared() const {
883 void reserve(size_t minCapacity) {
884 backend_.reserve(minCapacity);
888 std::basic_string<Char> backend_;
890 #endif // !_LIBSTDCXX_FBSTRING
893 * This is the basic_string replacement. For conformity,
894 * basic_fbstring takes the same template parameters, plus the last
895 * one which is the core.
897 #ifdef _LIBSTDCXX_FBSTRING
898 template <typename E, class T, class A, class Storage>
900 template <typename E,
901 class T = std::char_traits<E>,
902 class A = std::allocator<E>,
903 class Storage = fbstring_core<E> >
905 class basic_fbstring {
909 void (*throw_exc)(const char*),
911 if (!condition) throw_exc(msg);
914 bool isSane() const {
917 empty() == (size() == 0) &&
918 empty() == (begin() == end()) &&
919 size() <= max_size() &&
920 capacity() <= max_size() &&
921 size() <= capacity() &&
922 begin()[size()] == '\0';
926 friend struct Invariant;
929 explicit Invariant(const basic_fbstring& s) : s_(s) {
936 const basic_fbstring& s_;
938 explicit Invariant(const basic_fbstring&) {}
940 Invariant& operator=(const Invariant&);
945 typedef T traits_type;
946 typedef typename traits_type::char_type value_type;
947 typedef A allocator_type;
948 typedef typename A::size_type size_type;
949 typedef typename A::difference_type difference_type;
951 typedef typename A::reference reference;
952 typedef typename A::const_reference const_reference;
953 typedef typename A::pointer pointer;
954 typedef typename A::const_pointer const_pointer;
957 typedef const E* const_iterator;
958 typedef std::reverse_iterator<iterator
959 #ifdef NO_ITERATOR_TRAITS
963 typedef std::reverse_iterator<const_iterator
964 #ifdef NO_ITERATOR_TRAITS
967 > const_reverse_iterator;
969 static const size_type npos; // = size_type(-1)
970 typedef std::true_type IsRelocatable;
973 static void procrustes(size_type& n, size_type nmax) {
974 if (n > nmax) n = nmax;
978 // C++11 21.4.2 construct/copy/destroy
980 // Note: while the following two constructors can be (and previously were)
981 // collapsed into one constructor written this way:
983 // explicit basic_fbstring(const A& a = A()) noexcept { }
985 // This can cause Clang (at least version 3.7) to fail with the error:
986 // "chosen constructor is explicit in copy-initialization ...
987 // in implicit initialization of field '(x)' with omitted initializer"
989 // if used in a struct which is default-initialized. Hence the split into
990 // these two separate constructors.
992 basic_fbstring() noexcept : basic_fbstring(A()) {
995 explicit basic_fbstring(const A&) noexcept {
998 basic_fbstring(const basic_fbstring& str)
999 : store_(str.store_) {
1003 basic_fbstring(basic_fbstring&& goner) noexcept
1004 : store_(std::move(goner.store_)) {
1007 #ifndef _LIBSTDCXX_FBSTRING
1008 // This is defined for compatibility with std::string
1009 /* implicit */ basic_fbstring(const std::string& str)
1010 : store_(str.data(), str.size()) {
1014 basic_fbstring(const basic_fbstring& str,
1017 const A& /* a */ = A()) {
1018 assign(str, pos, n);
1021 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1023 ? traits_type::length(s)
1024 : (std::__throw_logic_error(
1025 "basic_fbstring: null pointer initializer not valid"),
1029 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1033 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1034 auto const pData = store_.expand_noinit(n);
1035 fbstring_detail::pod_fill(pData, pData + n, c);
1038 template <class InIt>
1039 basic_fbstring(InIt begin, InIt end,
1040 typename std::enable_if<
1041 !std::is_same<typename std::remove_const<InIt>::type,
1042 value_type*>::value, const A>::type & /*a*/ = A()) {
1046 // Specialization for const char*, const char*
1047 basic_fbstring(const value_type* b, const value_type* e)
1048 : store_(b, e - b) {
1051 // Nonstandard constructor
1052 basic_fbstring(value_type *s, size_type n, size_type c,
1053 AcquireMallocatedString a)
1054 : store_(s, n, c, a) {
1057 // Construction from initialization list
1058 basic_fbstring(std::initializer_list<value_type> il) {
1059 assign(il.begin(), il.end());
1062 ~basic_fbstring() noexcept {
1065 basic_fbstring& operator=(const basic_fbstring& lhs) {
1066 Invariant checker(*this);
1068 if (FBSTRING_UNLIKELY(&lhs == this)) {
1072 return assign(lhs.data(), lhs.size());
1076 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1077 if (FBSTRING_UNLIKELY(&goner == this)) {
1078 // Compatibility with std::basic_string<>,
1079 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1082 // No need of this anymore
1083 this->~basic_fbstring();
1084 // Move the goner into this
1085 new (&store_) Storage(std::move(goner.store_));
1089 #ifndef _LIBSTDCXX_FBSTRING
1090 // Compatibility with std::string
1091 basic_fbstring & operator=(const std::string & rhs) {
1092 return assign(rhs.data(), rhs.size());
1095 // Compatibility with std::string
1096 std::string toStdString() const {
1097 return std::string(data(), size());
1100 // A lot of code in fbcode still uses this method, so keep it here for now.
1101 const basic_fbstring& toStdString() const {
1106 basic_fbstring& operator=(const value_type* s) {
1110 basic_fbstring& operator=(value_type c) {
1111 Invariant checker(*this);
1114 store_.expand_noinit(1);
1115 } else if (store_.isShared()) {
1116 basic_fbstring(1, c).swap(*this);
1119 store_.shrink(size() - 1);
1125 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1126 return assign(il.begin(), il.end());
1129 // C++11 21.4.3 iterators:
1130 iterator begin() { return store_.mutable_data(); }
1132 const_iterator begin() const { return store_.data(); }
1134 const_iterator cbegin() const { return begin(); }
1137 return store_.mutable_data() + store_.size();
1140 const_iterator end() const {
1141 return store_.data() + store_.size();
1144 const_iterator cend() const { return end(); }
1146 reverse_iterator rbegin() {
1147 return reverse_iterator(end());
1150 const_reverse_iterator rbegin() const {
1151 return const_reverse_iterator(end());
1154 const_reverse_iterator crbegin() const { return rbegin(); }
1156 reverse_iterator rend() {
1157 return reverse_iterator(begin());
1160 const_reverse_iterator rend() const {
1161 return const_reverse_iterator(begin());
1164 const_reverse_iterator crend() const { return rend(); }
1167 // C++11 21.4.5, element access:
1168 const value_type& front() const { return *begin(); }
1169 const value_type& back() const {
1171 // Should be begin()[size() - 1], but that branches twice
1172 return *(end() - 1);
1174 value_type& front() { return *begin(); }
1175 value_type& back() {
1177 // Should be begin()[size() - 1], but that branches twice
1178 return *(end() - 1);
1185 // C++11 21.4.4 capacity:
1186 size_type size() const { return store_.size(); }
1188 size_type length() const { return size(); }
1190 size_type max_size() const {
1191 return std::numeric_limits<size_type>::max();
1194 void resize(const size_type n, const value_type c = value_type()) {
1195 Invariant checker(*this);
1197 auto size = this->size();
1199 store_.shrink(size - n);
1201 auto const delta = n - size;
1202 auto pData = store_.expand_noinit(delta);
1203 fbstring_detail::pod_fill(pData, pData + delta, c);
1205 assert(this->size() == n);
1208 size_type capacity() const { return store_.capacity(); }
1210 void reserve(size_type res_arg = 0) {
1211 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1212 store_.reserve(res_arg);
1215 void shrink_to_fit() {
1216 // Shrink only if slack memory is sufficiently large
1217 if (capacity() < size() * 3 / 2) {
1220 basic_fbstring(cbegin(), cend()).swap(*this);
1223 void clear() { resize(0); }
1225 bool empty() const { return size() == 0; }
1227 // C++11 21.4.5 element access:
1228 const_reference operator[](size_type pos) const {
1229 return *(begin() + pos);
1232 reference operator[](size_type pos) {
1233 return *(begin() + pos);
1236 const_reference at(size_type n) const {
1237 enforce(n <= size(), std::__throw_out_of_range, "");
1241 reference at(size_type n) {
1242 enforce(n < size(), std::__throw_out_of_range, "");
1246 // C++11 21.4.6 modifiers:
1247 basic_fbstring& operator+=(const basic_fbstring& str) {
1251 basic_fbstring& operator+=(const value_type* s) {
1255 basic_fbstring& operator+=(const value_type c) {
1260 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1265 basic_fbstring& append(const basic_fbstring& str) {
1267 auto desiredSize = size() + str.size();
1269 append(str.data(), str.size());
1270 assert(size() == desiredSize);
1274 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1276 const size_type sz = str.size();
1277 enforce(pos <= sz, std::__throw_out_of_range, "");
1278 procrustes(n, sz - pos);
1279 return append(str.data() + pos, n);
1282 basic_fbstring& append(const value_type* s, size_type n) {
1283 Invariant checker(*this);
1285 if (FBSTRING_UNLIKELY(!n)) {
1286 // Unlikely but must be done
1289 auto const oldSize = size();
1290 auto const oldData = data();
1291 auto pData = store_.expand_noinit(n, /* expGrowth = */ true);
1293 // Check for aliasing (rare). We could use "<=" here but in theory
1294 // those do not work for pointers unless the pointers point to
1295 // elements in the same array. For that reason we use
1296 // std::less_equal, which is guaranteed to offer a total order
1297 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1299 std::less_equal<const value_type*> le;
1300 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1301 assert(le(s + n, oldData + oldSize));
1302 // expand_noinit() could have moved the storage, restore the source.
1303 s = data() + (s - oldData);
1304 fbstring_detail::pod_move(s, s + n, pData);
1306 fbstring_detail::pod_copy(s, s + n, pData);
1309 assert(size() == oldSize + n);
1313 basic_fbstring& append(const value_type* s) {
1314 return append(s, traits_type::length(s));
1317 basic_fbstring& append(size_type n, value_type c) {
1318 Invariant checker(*this);
1319 auto pData = store_.expand_noinit(n, /* expGrowth = */ true);
1320 fbstring_detail::pod_fill(pData, pData + n, c);
1324 template<class InputIterator>
1325 basic_fbstring& append(InputIterator first, InputIterator last) {
1326 insert(end(), first, last);
1330 basic_fbstring& append(std::initializer_list<value_type> il) {
1331 return append(il.begin(), il.end());
1334 void push_back(const value_type c) { // primitive
1335 store_.push_back(c);
1338 basic_fbstring& assign(const basic_fbstring& str) {
1339 if (&str == this) return *this;
1340 return assign(str.data(), str.size());
1343 basic_fbstring& assign(basic_fbstring&& str) {
1344 return *this = std::move(str);
1347 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1349 const size_type sz = str.size();
1350 enforce(pos <= sz, std::__throw_out_of_range, "");
1351 procrustes(n, sz - pos);
1352 return assign(str.data() + pos, n);
1355 basic_fbstring& assign(const value_type* s, const size_type n) {
1356 Invariant checker(*this);
1360 } else if (size() >= n) {
1361 // s can alias this, we need to use pod_move.
1362 fbstring_detail::pod_move(s, s + n, store_.mutable_data());
1363 store_.shrink(size() - n);
1364 assert(size() == n);
1366 // If n is larger than size(), s cannot alias this string's
1369 // Do not use exponential growth here: assign() should be tight,
1370 // to mirror the behavior of the equivalent constructor.
1371 fbstring_detail::pod_copy(s, s + n, store_.expand_noinit(n));
1374 assert(size() == n);
1378 basic_fbstring& assign(const value_type* s) {
1379 return assign(s, traits_type::length(s));
1382 basic_fbstring& assign(std::initializer_list<value_type> il) {
1383 return assign(il.begin(), il.end());
1386 template <class ItOrLength, class ItOrChar>
1387 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1388 return replace(begin(), end(), first_or_n, last_or_c);
1391 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1392 return insert(pos1, str.data(), str.size());
1395 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1396 size_type pos2, size_type n) {
1397 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1398 procrustes(n, str.length() - pos2);
1399 return insert(pos1, str.data() + pos2, n);
1402 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1403 enforce(pos <= length(), std::__throw_out_of_range, "");
1404 insert(begin() + pos, s, s + n);
1408 basic_fbstring& insert(size_type pos, const value_type* s) {
1409 return insert(pos, s, traits_type::length(s));
1412 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1413 enforce(pos <= length(), std::__throw_out_of_range, "");
1414 insert(begin() + pos, n, c);
1418 iterator insert(const_iterator p, const value_type c) {
1419 const size_type pos = p - cbegin();
1421 return begin() + pos;
1424 #ifndef _LIBSTDCXX_FBSTRING
1426 typedef std::basic_istream<value_type, traits_type> istream_type;
1429 friend inline istream_type& getline(istream_type& is,
1430 basic_fbstring& str,
1432 Invariant checker(str);
1437 size_t avail = str.capacity() - size;
1438 // fbstring has 1 byte extra capacity for the null terminator,
1439 // and getline null-terminates the read string.
1440 is.getline(str.store_.expand_noinit(avail), avail + 1, delim);
1441 size += is.gcount();
1443 if (is.bad() || is.eof() || !is.fail()) {
1444 // Done by either failure, end of file, or normal read.
1445 if (!is.bad() && !is.eof()) {
1446 --size; // gcount() also accounts for the delimiter.
1452 assert(size == str.size());
1453 assert(size == str.capacity());
1454 // Start at minimum allocation 63 + terminator = 64.
1455 str.reserve(std::max<size_t>(63, 3 * size / 2));
1456 // Clear the error so we can continue reading.
1462 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1463 return getline(is, str, '\n');
1468 template <int i> class Selector {};
1470 iterator insertImplDiscr(const_iterator i,
1471 size_type n, value_type c, Selector<1>) {
1472 Invariant checker(*this);
1474 assert(i >= cbegin() && i <= cend());
1475 const size_type pos = i - cbegin();
1477 auto oldSize = size();
1478 store_.expand_noinit(n, /* expGrowth = */ true);
1480 fbstring_detail::pod_move(b + pos, b + oldSize, b + pos + n);
1481 fbstring_detail::pod_fill(b + pos, b + pos + n, c);
1486 template<class InputIter>
1487 iterator insertImplDiscr(const_iterator i,
1488 InputIter b, InputIter e, Selector<0>) {
1489 return insertImpl(i, b, e,
1490 typename std::iterator_traits<InputIter>::iterator_category());
1493 template <class FwdIterator>
1494 iterator insertImpl(const_iterator i,
1497 std::forward_iterator_tag) {
1498 Invariant checker(*this);
1500 assert(i >= cbegin() && i <= cend());
1501 const size_type pos = i - cbegin();
1502 auto n = std::distance(s1, s2);
1505 auto oldSize = size();
1506 store_.expand_noinit(n, /* expGrowth = */ true);
1508 fbstring_detail::pod_move(b + pos, b + oldSize, b + pos + n);
1509 std::copy(s1, s2, b + pos);
1514 template <class InputIterator>
1515 iterator insertImpl(const_iterator i,
1516 InputIterator b, InputIterator e,
1517 std::input_iterator_tag) {
1518 const auto pos = i - cbegin();
1519 basic_fbstring temp(cbegin(), i);
1520 for (; b != e; ++b) {
1523 temp.append(i, cend());
1525 return begin() + pos;
1529 template <class ItOrLength, class ItOrChar>
1530 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1531 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1532 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1535 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1536 return insert(p, il.begin(), il.end());
1539 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1540 Invariant checker(*this);
1542 enforce(pos <= length(), std::__throw_out_of_range, "");
1543 procrustes(n, length() - pos);
1544 std::copy(begin() + pos + n, end(), begin() + pos);
1545 resize(length() - n);
1549 iterator erase(iterator position) {
1550 const size_type pos(position - begin());
1551 enforce(pos <= size(), std::__throw_out_of_range, "");
1553 return begin() + pos;
1556 iterator erase(iterator first, iterator last) {
1557 const size_type pos(first - begin());
1558 erase(pos, last - first);
1559 return begin() + pos;
1562 // Replaces at most n1 chars of *this, starting with pos1 with the
1564 basic_fbstring& replace(size_type pos1, size_type n1,
1565 const basic_fbstring& str) {
1566 return replace(pos1, n1, str.data(), str.size());
1569 // Replaces at most n1 chars of *this, starting with pos1,
1570 // with at most n2 chars of str starting with pos2
1571 basic_fbstring& replace(size_type pos1, size_type n1,
1572 const basic_fbstring& str,
1573 size_type pos2, size_type n2) {
1574 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1575 return replace(pos1, n1, str.data() + pos2,
1576 std::min(n2, str.size() - pos2));
1579 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1580 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1581 return replace(pos, n1, s, traits_type::length(s));
1584 // Replaces at most n1 chars of *this, starting with pos, with n2
1587 // consolidated with
1589 // Replaces at most n1 chars of *this, starting with pos, with at
1590 // most n2 chars of str. str must have at least n2 chars.
1591 template <class StrOrLength, class NumOrChar>
1592 basic_fbstring& replace(size_type pos, size_type n1,
1593 StrOrLength s_or_n2, NumOrChar n_or_c) {
1594 Invariant checker(*this);
1596 enforce(pos <= size(), std::__throw_out_of_range, "");
1597 procrustes(n1, length() - pos);
1598 const iterator b = begin() + pos;
1599 return replace(b, b + n1, s_or_n2, n_or_c);
1602 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1603 return replace(i1, i2, str.data(), str.length());
1606 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1607 return replace(i1, i2, s, traits_type::length(s));
1611 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1612 const value_type* s, size_type n,
1615 assert(begin() <= i1 && i1 <= end());
1616 assert(begin() <= i2 && i2 <= end());
1617 return replace(i1, i2, s, s + n);
1620 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1621 size_type n2, value_type c, Selector<1>) {
1622 const size_type n1 = i2 - i1;
1624 std::fill(i1, i1 + n2, c);
1627 std::fill(i1, i2, c);
1628 insert(i2, n2 - n1, c);
1634 template <class InputIter>
1635 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1636 InputIter b, InputIter e,
1638 replaceImpl(i1, i2, b, e,
1639 typename std::iterator_traits<InputIter>::iterator_category());
1644 template <class FwdIterator>
1645 bool replaceAliased(iterator /* i1 */,
1647 FwdIterator /* s1 */,
1648 FwdIterator /* s2 */,
1653 template <class FwdIterator>
1654 bool replaceAliased(iterator i1, iterator i2,
1655 FwdIterator s1, FwdIterator s2, std::true_type) {
1656 static const std::less_equal<const value_type*> le =
1657 std::less_equal<const value_type*>();
1658 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1662 // Aliased replace, copy to new string
1663 basic_fbstring temp;
1664 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1665 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1670 template <class FwdIterator>
1671 void replaceImpl(iterator i1, iterator i2,
1672 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1673 Invariant checker(*this);
1675 // Handle aliased replace
1676 if (replaceAliased(i1, i2, s1, s2,
1677 std::integral_constant<bool,
1678 std::is_same<FwdIterator, iterator>::value ||
1679 std::is_same<FwdIterator, const_iterator>::value>())) {
1683 auto const n1 = i2 - i1;
1685 auto const n2 = std::distance(s1, s2);
1690 std::copy(s1, s2, i1);
1694 fbstring_detail::copy_n(s1, n1, i1);
1695 std::advance(s1, n1);
1701 template <class InputIterator>
1702 void replaceImpl(iterator i1, iterator i2,
1703 InputIterator b, InputIterator e, std::input_iterator_tag) {
1704 basic_fbstring temp(begin(), i1);
1705 temp.append(b, e).append(i2, end());
1710 template <class T1, class T2>
1711 basic_fbstring& replace(iterator i1, iterator i2,
1712 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1714 num1 = std::numeric_limits<T1>::is_specialized,
1715 num2 = std::numeric_limits<T2>::is_specialized;
1716 return replaceImplDiscr(
1717 i1, i2, first_or_n_or_s, last_or_c_or_n,
1718 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1721 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1722 enforce(pos <= size(), std::__throw_out_of_range, "");
1723 procrustes(n, size() - pos);
1726 fbstring_detail::pod_copy(data() + pos, data() + pos + n, s);
1731 void swap(basic_fbstring& rhs) {
1732 store_.swap(rhs.store_);
1735 const value_type* c_str() const {
1736 return store_.c_str();
1739 const value_type* data() const { return c_str(); }
1741 allocator_type get_allocator() const {
1742 return allocator_type();
1745 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1746 return find(str.data(), pos, str.length());
1749 size_type find(const value_type* needle, const size_type pos,
1750 const size_type nsize) const {
1751 auto const size = this->size();
1752 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1753 // that nsize + pos does not wrap around.
1754 if (nsize + pos > size || nsize + pos < pos) return npos;
1756 if (nsize == 0) return pos;
1757 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1758 // the last characters first
1759 auto const haystack = data();
1760 auto const nsize_1 = nsize - 1;
1761 auto const lastNeedle = needle[nsize_1];
1763 // Boyer-Moore skip value for the last char in the needle. Zero is
1764 // not a valid value; skip will be computed the first time it's
1768 const E * i = haystack + pos;
1769 auto iEnd = haystack + size - nsize_1;
1772 // Boyer-Moore: match the last element in the needle
1773 while (i[nsize_1] != lastNeedle) {
1779 // Here we know that the last char matches
1780 // Continue in pedestrian mode
1781 for (size_t j = 0; ; ) {
1783 if (i[j] != needle[j]) {
1784 // Not found, we can skip
1785 // Compute the skip value lazily
1788 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1795 // Check if done searching
1798 return i - haystack;
1805 size_type find(const value_type* s, size_type pos = 0) const {
1806 return find(s, pos, traits_type::length(s));
1809 size_type find (value_type c, size_type pos = 0) const {
1810 return find(&c, pos, 1);
1813 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1814 return rfind(str.data(), pos, str.length());
1817 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1818 if (n > length()) return npos;
1819 pos = std::min(pos, length() - n);
1820 if (n == 0) return pos;
1822 const_iterator i(begin() + pos);
1824 if (traits_type::eq(*i, *s)
1825 && traits_type::compare(&*i, s, n) == 0) {
1828 if (i == begin()) break;
1833 size_type rfind(const value_type* s, size_type pos = npos) const {
1834 return rfind(s, pos, traits_type::length(s));
1837 size_type rfind(value_type c, size_type pos = npos) const {
1838 return rfind(&c, pos, 1);
1841 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1842 return find_first_of(str.data(), pos, str.length());
1845 size_type find_first_of(const value_type* s,
1846 size_type pos, size_type n) const {
1847 if (pos > length() || n == 0) return npos;
1848 const_iterator i(begin() + pos),
1850 for (; i != finish; ++i) {
1851 if (traits_type::find(s, n, *i) != 0) {
1858 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1859 return find_first_of(s, pos, traits_type::length(s));
1862 size_type find_first_of(value_type c, size_type pos = 0) const {
1863 return find_first_of(&c, pos, 1);
1866 size_type find_last_of (const basic_fbstring& str,
1867 size_type pos = npos) const {
1868 return find_last_of(str.data(), pos, str.length());
1871 size_type find_last_of (const value_type* s, size_type pos,
1872 size_type n) const {
1873 if (!empty() && n > 0) {
1874 pos = std::min(pos, length() - 1);
1875 const_iterator i(begin() + pos);
1877 if (traits_type::find(s, n, *i) != 0) {
1880 if (i == begin()) break;
1886 size_type find_last_of (const value_type* s,
1887 size_type pos = npos) const {
1888 return find_last_of(s, pos, traits_type::length(s));
1891 size_type find_last_of (value_type c, size_type pos = npos) const {
1892 return find_last_of(&c, pos, 1);
1895 size_type find_first_not_of(const basic_fbstring& str,
1896 size_type pos = 0) const {
1897 return find_first_not_of(str.data(), pos, str.size());
1900 size_type find_first_not_of(const value_type* s, size_type pos,
1901 size_type n) const {
1902 if (pos < length()) {
1906 for (; i != finish; ++i) {
1907 if (traits_type::find(s, n, *i) == 0) {
1915 size_type find_first_not_of(const value_type* s,
1916 size_type pos = 0) const {
1917 return find_first_not_of(s, pos, traits_type::length(s));
1920 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1921 return find_first_not_of(&c, pos, 1);
1924 size_type find_last_not_of(const basic_fbstring& str,
1925 size_type pos = npos) const {
1926 return find_last_not_of(str.data(), pos, str.length());
1929 size_type find_last_not_of(const value_type* s, size_type pos,
1930 size_type n) const {
1931 if (!this->empty()) {
1932 pos = std::min(pos, size() - 1);
1933 const_iterator i(begin() + pos);
1935 if (traits_type::find(s, n, *i) == 0) {
1938 if (i == begin()) break;
1944 size_type find_last_not_of(const value_type* s,
1945 size_type pos = npos) const {
1946 return find_last_not_of(s, pos, traits_type::length(s));
1949 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1950 return find_last_not_of(&c, pos, 1);
1953 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1954 enforce(pos <= size(), std::__throw_out_of_range, "");
1955 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1958 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1959 enforce(pos <= size(), std::__throw_out_of_range, "");
1961 if (n < size()) resize(n);
1962 return std::move(*this);
1965 int compare(const basic_fbstring& str) const {
1966 // FIX due to Goncalo N M de Carvalho July 18, 2005
1967 return compare(0, size(), str);
1970 int compare(size_type pos1, size_type n1,
1971 const basic_fbstring& str) const {
1972 return compare(pos1, n1, str.data(), str.size());
1975 int compare(size_type pos1, size_type n1,
1976 const value_type* s) const {
1977 return compare(pos1, n1, s, traits_type::length(s));
1980 int compare(size_type pos1, size_type n1,
1981 const value_type* s, size_type n2) const {
1982 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1983 procrustes(n1, size() - pos1);
1984 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1985 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1986 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1989 int compare(size_type pos1, size_type n1,
1990 const basic_fbstring& str,
1991 size_type pos2, size_type n2) const {
1992 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1993 return compare(pos1, n1, str.data() + pos2,
1994 std::min(n2, str.size() - pos2));
1997 // Code from Jean-Francois Bastien (03/26/2007)
1998 int compare(const value_type* s) const {
1999 // Could forward to compare(0, size(), s, traits_type::length(s))
2000 // but that does two extra checks
2001 const size_type n1(size()), n2(traits_type::length(s));
2002 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2003 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2011 // non-member functions
2013 template <typename E, class T, class A, class S>
2015 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2016 const basic_fbstring<E, T, A, S>& rhs) {
2018 basic_fbstring<E, T, A, S> result;
2019 result.reserve(lhs.size() + rhs.size());
2020 result.append(lhs).append(rhs);
2021 return std::move(result);
2025 template <typename E, class T, class A, class S>
2027 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2028 const basic_fbstring<E, T, A, S>& rhs) {
2029 return std::move(lhs.append(rhs));
2033 template <typename E, class T, class A, class S>
2035 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2036 basic_fbstring<E, T, A, S>&& rhs) {
2037 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2038 // Good, at least we don't need to reallocate
2039 return std::move(rhs.insert(0, lhs));
2041 // Meh, no go. Forward to operator+(const&, const&).
2042 auto const& rhsC = rhs;
2047 template <typename E, class T, class A, class S>
2049 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2050 basic_fbstring<E, T, A, S>&& rhs) {
2051 return std::move(lhs.append(rhs));
2055 template <typename E, class T, class A, class S>
2057 basic_fbstring<E, T, A, S> operator+(
2059 const basic_fbstring<E, T, A, S>& rhs) {
2061 basic_fbstring<E, T, A, S> result;
2062 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2063 result.reserve(len + rhs.size());
2064 result.append(lhs, len).append(rhs);
2069 template <typename E, class T, class A, class S>
2071 basic_fbstring<E, T, A, S> operator+(
2073 basic_fbstring<E, T, A, S>&& rhs) {
2075 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2076 if (rhs.capacity() >= len + rhs.size()) {
2077 // Good, at least we don't need to reallocate
2078 rhs.insert(rhs.begin(), lhs, lhs + len);
2081 // Meh, no go. Do it by hand since we have len already.
2082 basic_fbstring<E, T, A, S> result;
2083 result.reserve(len + rhs.size());
2084 result.append(lhs, len).append(rhs);
2089 template <typename E, class T, class A, class S>
2091 basic_fbstring<E, T, A, S> operator+(
2093 const basic_fbstring<E, T, A, S>& rhs) {
2095 basic_fbstring<E, T, A, S> result;
2096 result.reserve(1 + rhs.size());
2097 result.push_back(lhs);
2103 template <typename E, class T, class A, class S>
2105 basic_fbstring<E, T, A, S> operator+(
2107 basic_fbstring<E, T, A, S>&& rhs) {
2109 if (rhs.capacity() > rhs.size()) {
2110 // Good, at least we don't need to reallocate
2111 rhs.insert(rhs.begin(), lhs);
2114 // Meh, no go. Forward to operator+(E, const&).
2115 auto const& rhsC = rhs;
2120 template <typename E, class T, class A, class S>
2122 basic_fbstring<E, T, A, S> operator+(
2123 const basic_fbstring<E, T, A, S>& lhs,
2126 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2127 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2129 basic_fbstring<E, T, A, S> result;
2130 const size_type len = traits_type::length(rhs);
2131 result.reserve(lhs.size() + len);
2132 result.append(lhs).append(rhs, len);
2136 // C++11 21.4.8.1/10
2137 template <typename E, class T, class A, class S>
2139 basic_fbstring<E, T, A, S> operator+(
2140 basic_fbstring<E, T, A, S>&& lhs,
2143 return std::move(lhs += rhs);
2146 // C++11 21.4.8.1/11
2147 template <typename E, class T, class A, class S>
2149 basic_fbstring<E, T, A, S> operator+(
2150 const basic_fbstring<E, T, A, S>& lhs,
2153 basic_fbstring<E, T, A, S> result;
2154 result.reserve(lhs.size() + 1);
2156 result.push_back(rhs);
2160 // C++11 21.4.8.1/12
2161 template <typename E, class T, class A, class S>
2163 basic_fbstring<E, T, A, S> operator+(
2164 basic_fbstring<E, T, A, S>&& lhs,
2167 return std::move(lhs += rhs);
2170 template <typename E, class T, class A, class S>
2172 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2173 const basic_fbstring<E, T, A, S>& rhs) {
2174 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2176 template <typename E, class T, class A, class S>
2178 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2179 const basic_fbstring<E, T, A, S>& rhs) {
2180 return rhs == lhs; }
2182 template <typename E, class T, class A, class S>
2184 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2185 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2186 return lhs.compare(rhs) == 0; }
2188 template <typename E, class T, class A, class S>
2190 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2191 const basic_fbstring<E, T, A, S>& rhs) {
2192 return !(lhs == rhs); }
2194 template <typename E, class T, class A, class S>
2196 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2197 const basic_fbstring<E, T, A, S>& rhs) {
2198 return !(lhs == rhs); }
2200 template <typename E, class T, class A, class S>
2202 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2203 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2204 return !(lhs == rhs); }
2206 template <typename E, class T, class A, class S>
2208 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2209 const basic_fbstring<E, T, A, S>& rhs) {
2210 return lhs.compare(rhs) < 0; }
2212 template <typename E, class T, class A, class S>
2214 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2215 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2216 return lhs.compare(rhs) < 0; }
2218 template <typename E, class T, class A, class S>
2220 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2221 const basic_fbstring<E, T, A, S>& rhs) {
2222 return rhs.compare(lhs) > 0; }
2224 template <typename E, class T, class A, class S>
2226 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2227 const basic_fbstring<E, T, A, S>& rhs) {
2230 template <typename E, class T, class A, class S>
2232 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2233 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2236 template <typename E, class T, class A, class S>
2238 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2239 const basic_fbstring<E, T, A, S>& rhs) {
2242 template <typename E, class T, class A, class S>
2244 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2245 const basic_fbstring<E, T, A, S>& rhs) {
2246 return !(rhs < lhs); }
2248 template <typename E, class T, class A, class S>
2250 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2251 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2252 return !(rhs < lhs); }
2254 template <typename E, class T, class A, class S>
2256 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2257 const basic_fbstring<E, T, A, S>& rhs) {
2258 return !(rhs < lhs); }
2260 template <typename E, class T, class A, class S>
2262 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2263 const basic_fbstring<E, T, A, S>& rhs) {
2264 return !(lhs < rhs); }
2266 template <typename E, class T, class A, class S>
2268 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2269 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2270 return !(lhs < rhs); }
2272 template <typename E, class T, class A, class S>
2274 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2275 const basic_fbstring<E, T, A, S>& rhs) {
2276 return !(lhs < rhs);
2280 template <typename E, class T, class A, class S>
2281 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2285 // TODO: make this faster.
2286 template <typename E, class T, class A, class S>
2289 typename basic_fbstring<E, T, A, S>::value_type,
2290 typename basic_fbstring<E, T, A, S>::traits_type>&
2292 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2293 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2294 basic_fbstring<E, T, A, S>& str) {
2295 typename std::basic_istream<E, T>::sentry sentry(is);
2296 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2297 typename basic_fbstring<E, T, A, S>::traits_type>
2299 typedef typename __istream_type::ios_base __ios_base;
2300 size_t extracted = 0;
2301 auto err = __ios_base::goodbit;
2303 auto n = is.width();
2308 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2309 if (got == T::eof()) {
2310 err |= __ios_base::eofbit;
2314 if (isspace(got)) break;
2316 got = is.rdbuf()->snextc();
2320 err |= __ios_base::failbit;
2328 template <typename E, class T, class A, class S>
2330 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2331 typename basic_fbstring<E, T, A, S>::traits_type>&
2333 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2334 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2335 const basic_fbstring<E, T, A, S>& str) {
2337 typename std::basic_ostream<
2338 typename basic_fbstring<E, T, A, S>::value_type,
2339 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2341 typedef std::ostreambuf_iterator<
2342 typename basic_fbstring<E, T, A, S>::value_type,
2343 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2344 size_t __len = str.size();
2346 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2347 if (__pad_and_output(_Ip(os),
2349 __left ? str.data() + __len : str.data(),
2352 os.fill()).failed()) {
2353 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2356 #elif defined(_MSC_VER)
2357 // MSVC doesn't define __ostream_insert
2358 os.write(str.data(), str.size());
2360 std::__ostream_insert(os, str.data(), str.size());
2365 template <typename E1, class T, class A, class S>
2366 const typename basic_fbstring<E1, T, A, S>::size_type
2367 basic_fbstring<E1, T, A, S>::npos =
2368 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2370 #ifndef _LIBSTDCXX_FBSTRING
2371 // basic_string compatibility routines
2373 template <typename E, class T, class A, class S>
2375 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2376 const std::string& rhs) {
2377 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2380 template <typename E, class T, class A, class S>
2382 bool operator==(const std::string& lhs,
2383 const basic_fbstring<E, T, A, S>& rhs) {
2387 template <typename E, class T, class A, class S>
2389 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2390 const std::string& rhs) {
2391 return !(lhs == rhs);
2394 template <typename E, class T, class A, class S>
2396 bool operator!=(const std::string& lhs,
2397 const basic_fbstring<E, T, A, S>& rhs) {
2398 return !(lhs == rhs);
2401 #if !defined(_LIBSTDCXX_FBSTRING)
2402 typedef basic_fbstring<char> fbstring;
2405 // fbstring is relocatable
2406 template <class T, class R, class A, class S>
2407 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2410 _GLIBCXX_END_NAMESPACE_VERSION
2413 } // namespace folly
2415 #ifndef _LIBSTDCXX_FBSTRING
2417 // Hash functions to make fbstring usable with e.g. hash_map
2419 // Handle interaction with different C++ standard libraries, which
2420 // expect these types to be in different namespaces.
2422 #define FOLLY_FBSTRING_HASH1(T) \
2424 struct hash< ::folly::basic_fbstring<T>> { \
2425 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2426 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2430 // The C++11 standard says that these four are defined
2431 #define FOLLY_FBSTRING_HASH \
2432 FOLLY_FBSTRING_HASH1(char) \
2433 FOLLY_FBSTRING_HASH1(char16_t) \
2434 FOLLY_FBSTRING_HASH1(char32_t) \
2435 FOLLY_FBSTRING_HASH1(wchar_t)
2443 #if FOLLY_HAVE_DEPRECATED_ASSOC
2444 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2445 namespace __gnu_cxx {
2449 } // namespace __gnu_cxx
2450 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2451 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2453 #undef FOLLY_FBSTRING_HASH
2454 #undef FOLLY_FBSTRING_HASH1
2456 #endif // _LIBSTDCXX_FBSTRING
2458 #pragma GCC diagnostic pop
2460 #undef FBSTRING_DISABLE_SSO
2461 #undef FBSTRING_SANITIZE_ADDRESS
2463 #undef FBSTRING_LIKELY
2464 #undef FBSTRING_UNLIKELY
2466 #ifdef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2468 #undef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2469 #endif // FOLLY_DEFINED_NDEBUG_FOR_FBSTRING