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 // Handle the cases where the fbcode version (folly/Malloc.h) is included
41 // either before or after this inclusion.
42 #ifdef FOLLY_MALLOC_H_
43 #undef FOLLY_MALLOC_H_
44 #include "basic_fbstring_malloc.h" // nolint
46 #include "basic_fbstring_malloc.h" // nolint
47 #undef FOLLY_MALLOC_H_
50 #else // !_LIBSTDCXX_FBSTRING
52 #include <folly/Portability.h>
54 // libc++ doesn't provide this header, nor does msvc
55 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
56 #include <bits/c++config.h>
64 #include <folly/Traits.h>
65 #include <folly/Malloc.h>
66 #include <folly/Hash.h>
67 #include <folly/ScopeGuard.h>
69 #if FOLLY_HAVE_DEPRECATED_ASSOC
70 #ifdef _GLIBCXX_SYMVER
71 #include <ext/hash_set>
72 #include <ext/hash_map>
78 // We defined these here rather than including Likely.h to avoid
79 // redefinition errors when fbstring is imported into libstdc++.
80 #if defined(__GNUC__) && __GNUC__ >= 4
81 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
82 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
84 #define FBSTRING_LIKELY(x) (x)
85 #define FBSTRING_UNLIKELY(x) (x)
88 #pragma GCC diagnostic push
89 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
90 #pragma GCC diagnostic ignored "-Wshadow"
91 // GCC 4.9 has a false positive in setSmallSize (probably
92 // https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
93 // compile-time array bound checking.
94 #pragma GCC diagnostic ignored "-Warray-bounds"
96 // FBString cannot use throw when replacing std::string, though it may still
99 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
101 #ifdef _LIBSTDCXX_FBSTRING
102 namespace std _GLIBCXX_VISIBILITY(default) {
103 _GLIBCXX_BEGIN_NAMESPACE_VERSION
108 #if defined(__clang__)
109 # if __has_feature(address_sanitizer)
110 # define FBSTRING_SANITIZE_ADDRESS
112 #elif defined (__GNUC__) && \
113 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
115 # define FBSTRING_SANITIZE_ADDRESS
118 // When compiling with ASan, always heap-allocate the string even if
119 // it would fit in-situ, so that ASan can detect access to the string
120 // buffer after it has been invalidated (destroyed, resized, etc.).
121 // Note that this flag doesn't remove support for in-situ strings, as
122 // that would break ABI-compatibility and wouldn't allow linking code
123 // compiled with this flag with code compiled without.
124 #ifdef FBSTRING_SANITIZE_ADDRESS
125 # define FBSTRING_DISABLE_SSO true
127 # define FBSTRING_DISABLE_SSO false
130 namespace fbstring_detail {
132 template <class InIt, class OutIt>
135 typename std::iterator_traits<InIt>::difference_type n,
137 for (; n != 0; --n, ++b, ++d) {
143 template <class Pod, class T>
144 inline void pod_fill(Pod* b, Pod* e, T c) {
145 assert(b && e && b <= e);
146 /*static*/ if (sizeof(T) == 1) {
149 auto const ee = b + ((e - b) & ~7u);
150 for (; b != ee; b += 8) {
161 for (; b != e; ++b) {
168 * Lightly structured memcpy, simplifies copying PODs and introduces
169 * some asserts. Unfortunately using this function may cause
170 * measurable overhead (presumably because it adjusts from a begin/end
171 * convention to a pointer/size convention, so it does some extra
172 * arithmetic even though the caller might have done the inverse
173 * adaptation outside).
176 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
178 assert(d >= e || d + (e - b) <= b);
179 memcpy(d, b, (e - b) * sizeof(Pod));
183 * Lightly structured memmove, simplifies copying PODs and introduces
187 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
189 memmove(d, b, (e - b) * sizeof(*b));
192 } // namespace fbstring_detail
195 * Defines a special acquisition method for constructing fbstring
196 * objects. AcquireMallocatedString means that the user passes a
197 * pointer to a malloc-allocated string that the fbstring object will
200 enum class AcquireMallocatedString {};
203 * fbstring_core_model is a mock-up type that defines all required
204 * signatures of a fbstring core. The fbstring class itself uses such
205 * a core object to implement all of the numerous member functions
206 * required by the standard.
208 * If you want to define a new core, copy the definition below and
209 * implement the primitives. Then plug the core into basic_fbstring as
210 * a template argument.
212 template <class Char>
213 class fbstring_core_model {
215 fbstring_core_model();
216 fbstring_core_model(const fbstring_core_model &);
217 ~fbstring_core_model();
218 // Returns a pointer to string's buffer (currently only contiguous
219 // strings are supported). The pointer is guaranteed to be valid
220 // until the next call to a non-const member function.
221 const Char * data() const;
222 // Much like data(), except the string is prepared to support
223 // character-level changes. This call is a signal for
224 // e.g. reference-counted implementation to fork the data. The
225 // pointer is guaranteed to be valid until the next call to a
226 // non-const member function.
227 Char * mutable_data();
228 // Returns a pointer to string's buffer and guarantees that a
229 // readable '\0' lies right after the buffer. The pointer is
230 // guaranteed to be valid until the next call to a non-const member
232 const Char * c_str() const;
233 // Shrinks the string by delta characters. Asserts that delta <=
235 void shrink(size_t delta);
236 // Expands the string by delta characters (i.e. after this call
237 // size() will report the old size() plus delta) but without
238 // initializing the expanded region. The expanded region is
239 // zero-terminated. Returns a pointer to the memory to be
240 // initialized (the beginning of the expanded portion). The caller
241 // is expected to fill the expanded area appropriately.
242 // If expGrowth is true, exponential growth is guaranteed.
243 // It is not guaranteed not to reallocate even if size() + delta <
244 // capacity(), so all references to the buffer are invalidated.
245 Char* expand_noinit(size_t delta, bool expGrowth);
246 // Expands the string by one character and sets the last character
248 void push_back(Char c);
249 // Returns the string's size.
251 // Returns the string's capacity, i.e. maximum size that the string
252 // can grow to without reallocation. Note that for reference counted
253 // strings that's technically a lie - even assigning characters
254 // within the existing size would cause a reallocation.
255 size_t capacity() const;
256 // Returns true if the data underlying the string is actually shared
257 // across multiple strings (in a refcounted fashion).
258 bool isShared() const;
259 // Makes sure that at least minCapacity characters are available for
260 // the string without reallocation. For reference-counted strings,
261 // it should fork the data even if minCapacity < size().
262 void reserve(size_t minCapacity);
265 fbstring_core_model& operator=(const fbstring_core_model &);
270 * This is the core of the string. The code should work on 32- and
271 * 64-bit and both big- and little-endianan architectures with any
274 * The storage is selected as follows (assuming we store one-byte
275 * characters on a 64-bit machine): (a) "small" strings between 0 and
276 * 23 chars are stored in-situ without allocation (the rightmost byte
277 * stores the size); (b) "medium" strings from 24 through 254 chars
278 * are stored in malloc-allocated memory that is copied eagerly; (c)
279 * "large" strings of 255 chars and above are stored in a similar
280 * structure as medium arrays, except that the string is
281 * reference-counted and copied lazily. the reference count is
282 * allocated right before the character array.
284 * The discriminator between these three strategies sits in two
285 * bits of the rightmost char of the storage. If neither is set, then the
286 * string is small (and its length sits in the lower-order bits on
287 * little-endian or the high-order bits on big-endian of that
288 * rightmost character). If the MSb is set, the string is medium width.
289 * If the second MSb is set, then the string is large. On little-endian,
290 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
291 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
292 * and big-endian fbstring_core equivalent with merely different ops used
293 * to extract capacity/category.
295 template <class Char> class fbstring_core {
297 // It's MSVC, so we just have to guess ... and allow an override
299 # ifdef FOLLY_ENDIAN_BE
300 static constexpr auto kIsLittleEndian = false;
302 static constexpr auto kIsLittleEndian = true;
305 static constexpr auto kIsLittleEndian =
306 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
309 fbstring_core() noexcept { reset(); }
311 fbstring_core(const fbstring_core & rhs) {
312 assert(&rhs != this);
313 // Simplest case first: small strings are bitblitted
314 if (rhs.category() == Category::isSmall) {
315 static_assert(offsetof(MediumLarge, data_) == 0,
316 "fbstring layout failure");
317 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
318 "fbstring layout failure");
319 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
320 "fbstring layout failure");
321 // Just write the whole thing, don't look at details. In
322 // particular we need to copy capacity anyway because we want
323 // to set the size (don't forget that the last character,
324 // which stores a short string's length, is shared with the
325 // ml_.capacity field).
327 assert(category() == Category::isSmall && this->size() == rhs.size());
328 } else if (rhs.category() == Category::isLarge) {
329 // Large strings are just refcounted
331 RefCounted::incrementRefs(ml_.data_);
332 assert(category() == Category::isLarge && size() == rhs.size());
334 // Medium strings are copied eagerly. Don't forget to allocate
335 // one extra Char for the null terminator.
336 auto const allocSize =
337 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
338 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
339 // Also copies terminator.
340 fbstring_detail::pod_copy(rhs.ml_.data_,
341 rhs.ml_.data_ + rhs.ml_.size_ + 1,
343 ml_.size_ = rhs.ml_.size_;
344 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
345 assert(category() == Category::isMedium);
347 assert(size() == rhs.size());
348 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
351 fbstring_core(fbstring_core&& goner) noexcept {
354 // Clean goner's carcass
358 fbstring_core(const Char *const data,
360 bool disableSSO = FBSTRING_DISABLE_SSO) {
362 #ifndef _LIBSTDCXX_FBSTRING
364 assert(this->size() == size);
365 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
370 // Simplest case first: small strings are bitblitted
371 if (!disableSSO && size <= maxSmallSize) {
372 // Layout is: Char* data_, size_t size_, size_t capacity_
373 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
374 "fbstring has unexpected size");
375 static_assert(sizeof(Char*) == sizeof(size_t),
376 "fbstring size assumption violation");
377 // sizeof(size_t) must be a power of 2
378 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
379 "fbstring size assumption violation");
381 // If data is aligned, use fast word-wise copying. Otherwise,
382 // use conservative memcpy.
383 // The word-wise path reads bytes which are outside the range of
384 // the string, and makes ASan unhappy, so we disable it when
385 // compiling with ASan.
386 #ifndef FBSTRING_SANITIZE_ADDRESS
387 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
388 const size_t byteSize = size * sizeof(Char);
389 constexpr size_t wordWidth = sizeof(size_t);
390 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
392 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
394 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
396 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
403 fbstring_detail::pod_copy(data, data + size, small_);
407 if (size <= maxMediumSize) {
408 // Medium strings are allocated normally. Don't forget to
409 // allocate one extra Char for the terminating null.
410 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
411 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
412 fbstring_detail::pod_copy(data, data + size, ml_.data_);
414 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
416 // Large strings are allocated differently
417 size_t effectiveCapacity = size;
418 auto const newRC = RefCounted::create(data, & effectiveCapacity);
419 ml_.data_ = newRC->data_;
421 ml_.setCapacity(effectiveCapacity, Category::isLarge);
423 ml_.data_[size] = '\0';
427 ~fbstring_core() noexcept {
428 auto const c = category();
429 if (c == Category::isSmall) {
432 if (c == Category::isMedium) {
436 RefCounted::decrementRefs(ml_.data_);
439 // Snatches a previously mallocated string. The parameter "size"
440 // is the size of the string, and the parameter "allocatedSize"
441 // is the size of the mallocated block. The string must be
442 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
444 // So if you want a 2-character string, pass malloc(3) as "data",
445 // pass 2 as "size", and pass 3 as "allocatedSize".
446 fbstring_core(Char * const data,
448 const size_t allocatedSize,
449 AcquireMallocatedString) {
451 assert(allocatedSize >= size + 1);
452 assert(data[size] == '\0');
453 // Use the medium string storage
456 // Don't forget about null terminator
457 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
459 // No need for the memory
465 // swap below doesn't test whether &rhs == this (and instead
466 // potentially does extra work) on the premise that the rarity of
467 // that situation actually makes the check more expensive than is
469 void swap(fbstring_core & rhs) {
475 // In C++11 data() and c_str() are 100% equivalent.
476 const Char * data() const {
480 Char * mutable_data() {
481 auto const c = category();
482 if (c == Category::isSmall) {
485 assert(c == Category::isMedium || c == Category::isLarge);
486 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
488 size_t effectiveCapacity = ml_.capacity();
489 auto const newRC = RefCounted::create(& effectiveCapacity);
490 // If this fails, someone placed the wrong capacity in an
492 assert(effectiveCapacity >= ml_.capacity());
493 // Also copies terminator.
494 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
496 RefCounted::decrementRefs(ml_.data_);
497 ml_.data_ = newRC->data_;
502 const Char * c_str() const {
503 auto const c = category();
504 if (c == Category::isSmall) {
505 assert(small_[smallSize()] == '\0');
508 assert(c == Category::isMedium || c == Category::isLarge);
509 assert(ml_.data_[ml_.size_] == '\0');
513 void shrink(const size_t delta) {
514 if (category() == Category::isSmall) {
515 // Check for underflow
516 assert(delta <= smallSize());
517 setSmallSize(smallSize() - delta);
518 } else if (category() == Category::isMedium ||
519 RefCounted::refs(ml_.data_) == 1) {
520 // Medium strings and unique large strings need no special
522 assert(ml_.size_ >= delta);
524 ml_.data_[ml_.size_] = '\0';
526 assert(ml_.size_ >= delta);
527 // Shared large string, must make unique. This is because of the
528 // durn terminator must be written, which may trample the shared
531 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
533 // No need to write the terminator.
537 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
538 if (category() == Category::isLarge) {
540 if (RefCounted::refs(ml_.data_) > 1) {
541 // We must make it unique regardless; in-place reallocation is
542 // useless if the string is shared. In order to not surprise
543 // people, reserve the new block at current capacity or
544 // more. That way, a string's capacity never shrinks after a
546 minCapacity = std::max(minCapacity, ml_.capacity());
547 auto const newRC = RefCounted::create(& minCapacity);
548 // Also copies terminator.
549 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
551 RefCounted::decrementRefs(ml_.data_);
552 ml_.data_ = newRC->data_;
553 ml_.setCapacity(minCapacity, Category::isLarge);
554 // size remains unchanged
556 // String is not shared, so let's try to realloc (if needed)
557 if (minCapacity > ml_.capacity()) {
558 // Asking for more memory
560 RefCounted::reallocate(ml_.data_, ml_.size_,
561 ml_.capacity(), minCapacity);
562 ml_.data_ = newRC->data_;
563 ml_.setCapacity(minCapacity, Category::isLarge);
565 assert(capacity() >= minCapacity);
567 } else if (category() == Category::isMedium) {
568 // String is not shared
569 if (minCapacity <= ml_.capacity()) {
570 return; // nothing to do, there's enough room
572 if (minCapacity <= maxMediumSize) {
573 // Keep the string at medium size. Don't forget to allocate
574 // one extra Char for the terminating null.
575 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
576 // Also copies terminator.
577 ml_.data_ = static_cast<Char *>(
580 (ml_.size_ + 1) * sizeof(Char),
581 (ml_.capacity() + 1) * sizeof(Char),
583 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
585 // Conversion from medium to large string
586 fbstring_core nascent;
587 // Will recurse to another branch of this function
588 nascent.reserve(minCapacity);
589 nascent.ml_.size_ = ml_.size_;
590 // Also copies terminator.
591 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
594 assert(capacity() >= minCapacity);
597 assert(category() == Category::isSmall);
598 if (!disableSSO && minCapacity <= maxSmallSize) {
600 // Nothing to do, everything stays put
601 } else if (minCapacity <= maxMediumSize) {
603 // Don't forget to allocate one extra Char for the terminating null
604 auto const allocSizeBytes =
605 goodMallocSize((1 + minCapacity) * sizeof(Char));
606 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
607 auto const size = smallSize();
608 // Also copies terminator.
609 fbstring_detail::pod_copy(small_, small_ + size + 1, pData);
612 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
615 auto const newRC = RefCounted::create(& minCapacity);
616 auto const size = smallSize();
617 // Also copies terminator.
618 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
619 ml_.data_ = newRC->data_;
621 ml_.setCapacity(minCapacity, Category::isLarge);
622 assert(capacity() >= minCapacity);
625 assert(capacity() >= minCapacity);
628 Char * expand_noinit(const size_t delta,
629 bool expGrowth = false,
630 bool disableSSO = FBSTRING_DISABLE_SSO) {
631 // Strategy is simple: make room, then change size
632 assert(capacity() >= size());
634 if (category() == Category::isSmall) {
637 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
641 reserve(expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz);
645 if (FBSTRING_UNLIKELY(newSz > capacity())) {
646 // ensures not shared
647 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
650 assert(capacity() >= newSz);
651 // Category can't be small - we took care of that above
652 assert(category() == Category::isMedium || category() == Category::isLarge);
654 ml_.data_[newSz] = '\0';
655 assert(size() == newSz);
656 return ml_.data_ + sz;
659 void push_back(Char c) {
660 *expand_noinit(1, /* expGrowth = */ true) = c;
663 size_t size() const {
664 return category() == Category::isSmall ? smallSize() : ml_.size_;
667 size_t capacity() const {
668 switch (category()) {
669 case Category::isSmall:
671 case Category::isLarge:
672 // For large-sized strings, a multi-referenced chunk has no
673 // available capacity. This is because any attempt to append
674 // data would trigger a new allocation.
675 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
678 return ml_.capacity();
681 bool isShared() const {
682 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
687 fbstring_core & operator=(const fbstring_core & rhs);
689 // Equivalent to setSmallSize(0) but a few ns faster in
692 ml_.capacity_ = kIsLittleEndian
693 ? maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)))
696 assert(category() == Category::isSmall && size() == 0);
700 std::atomic<size_t> refCount_;
703 static RefCounted * fromData(Char * p) {
704 return static_cast<RefCounted*>(
706 static_cast<unsigned char*>(static_cast<void*>(p))
707 - sizeof(refCount_)));
710 static size_t refs(Char * p) {
711 return fromData(p)->refCount_.load(std::memory_order_acquire);
714 static void incrementRefs(Char * p) {
715 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
718 static void decrementRefs(Char * p) {
719 auto const dis = fromData(p);
720 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
727 static RefCounted * create(size_t * size) {
728 // Don't forget to allocate one extra Char for the terminating
729 // null. In this case, however, one Char is already part of the
731 const size_t allocSize = goodMallocSize(
732 sizeof(RefCounted) + *size * sizeof(Char));
733 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
734 result->refCount_.store(1, std::memory_order_release);
735 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
739 static RefCounted * create(const Char * data, size_t * size) {
740 const size_t effectiveSize = *size;
741 auto result = create(size);
742 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
746 static RefCounted * reallocate(Char *const data,
747 const size_t currentSize,
748 const size_t currentCapacity,
749 const size_t newCapacity) {
750 assert(newCapacity > 0 && newCapacity > currentSize);
751 auto const dis = fromData(data);
752 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
753 // Don't forget to allocate one extra Char for the terminating
754 // null. In this case, however, one Char is already part of the
756 auto result = static_cast<RefCounted*>(
758 sizeof(RefCounted) + currentSize * sizeof(Char),
759 sizeof(RefCounted) + currentCapacity * sizeof(Char),
760 sizeof(RefCounted) + newCapacity * sizeof(Char)));
761 assert(result->refCount_.load(std::memory_order_acquire) == 1);
766 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
769 enum class Category : category_type {
771 isMedium = kIsLittleEndian
772 ? sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000
774 isLarge = kIsLittleEndian
775 ? sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000
779 Category category() const {
780 // works for both big-endian and little-endian
781 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
789 size_t capacity() const {
790 return kIsLittleEndian
791 ? capacity_ & capacityExtractMask
795 void setCapacity(size_t cap, Category cat) {
796 capacity_ = kIsLittleEndian
797 ? cap | static_cast<category_type>(cat)
798 : (cap << 2) | static_cast<category_type>(cat);
803 Char small_[sizeof(MediumLarge) / sizeof(Char)];
808 lastChar = sizeof(MediumLarge) - 1,
809 maxSmallSize = lastChar / sizeof(Char),
810 maxMediumSize = 254 / sizeof(Char), // coincides with the small
811 // bin size in dlmalloc
812 categoryExtractMask = kIsLittleEndian
813 ? sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000
815 capacityExtractMask = kIsLittleEndian
816 ? ~categoryExtractMask
819 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
820 "Corrupt memory layout for fbstring.");
822 size_t smallSize() const {
823 assert(category() == Category::isSmall);
824 constexpr auto shift = kIsLittleEndian ? 0 : 2;
825 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
826 assert(static_cast<size_t>(maxSmallSize) >= smallShifted);
827 return static_cast<size_t>(maxSmallSize) - smallShifted;
830 void setSmallSize(size_t s) {
831 // Warning: this should work with uninitialized strings too,
832 // so don't assume anything about the previous value of
833 // small_[maxSmallSize].
834 assert(s <= maxSmallSize);
835 constexpr auto shift = kIsLittleEndian ? 0 : 2;
836 small_[maxSmallSize] = (maxSmallSize - s) << shift;
838 assert(category() == Category::isSmall && size() == s);
842 #ifndef _LIBSTDCXX_FBSTRING
844 * Dummy fbstring core that uses an actual std::string. This doesn't
845 * make any sense - it's just for testing purposes.
847 template <class Char>
848 class dummy_fbstring_core {
850 dummy_fbstring_core() {
852 dummy_fbstring_core(const dummy_fbstring_core& another)
853 : backend_(another.backend_) {
855 dummy_fbstring_core(const Char * s, size_t n)
858 void swap(dummy_fbstring_core & rhs) {
859 backend_.swap(rhs.backend_);
861 const Char * data() const {
862 return backend_.data();
864 Char * mutable_data() {
865 //assert(!backend_.empty());
866 return &*backend_.begin();
868 void shrink(size_t delta) {
869 assert(delta <= size());
870 backend_.resize(size() - delta);
872 Char * expand_noinit(size_t delta) {
873 auto const sz = size();
874 backend_.resize(size() + delta);
875 return backend_.data() + sz;
877 void push_back(Char c) {
878 backend_.push_back(c);
880 size_t size() const {
881 return backend_.size();
883 size_t capacity() const {
884 return backend_.capacity();
886 bool isShared() const {
889 void reserve(size_t minCapacity) {
890 backend_.reserve(minCapacity);
894 std::basic_string<Char> backend_;
896 #endif // !_LIBSTDCXX_FBSTRING
899 * This is the basic_string replacement. For conformity,
900 * basic_fbstring takes the same template parameters, plus the last
901 * one which is the core.
903 #ifdef _LIBSTDCXX_FBSTRING
904 template <typename E, class T, class A, class Storage>
906 template <typename E,
907 class T = std::char_traits<E>,
908 class A = std::allocator<E>,
909 class Storage = fbstring_core<E> >
911 class basic_fbstring {
915 void (*throw_exc)(const char*),
917 if (!condition) throw_exc(msg);
920 bool isSane() const {
923 empty() == (size() == 0) &&
924 empty() == (begin() == end()) &&
925 size() <= max_size() &&
926 capacity() <= max_size() &&
927 size() <= capacity() &&
928 begin()[size()] == '\0';
932 friend struct Invariant;
935 explicit Invariant(const basic_fbstring& s) : s_(s) {
942 const basic_fbstring& s_;
944 explicit Invariant(const basic_fbstring&) {}
946 Invariant& operator=(const Invariant&);
951 typedef T traits_type;
952 typedef typename traits_type::char_type value_type;
953 typedef A allocator_type;
954 typedef typename A::size_type size_type;
955 typedef typename A::difference_type difference_type;
957 typedef typename A::reference reference;
958 typedef typename A::const_reference const_reference;
959 typedef typename A::pointer pointer;
960 typedef typename A::const_pointer const_pointer;
963 typedef const E* const_iterator;
964 typedef std::reverse_iterator<iterator
965 #ifdef NO_ITERATOR_TRAITS
969 typedef std::reverse_iterator<const_iterator
970 #ifdef NO_ITERATOR_TRAITS
973 > const_reverse_iterator;
975 static const size_type npos; // = size_type(-1)
976 typedef std::true_type IsRelocatable;
979 static void procrustes(size_type& n, size_type nmax) {
980 if (n > nmax) n = nmax;
984 // C++11 21.4.2 construct/copy/destroy
986 // Note: while the following two constructors can be (and previously were)
987 // collapsed into one constructor written this way:
989 // explicit basic_fbstring(const A& a = A()) noexcept { }
991 // This can cause Clang (at least version 3.7) to fail with the error:
992 // "chosen constructor is explicit in copy-initialization ...
993 // in implicit initialization of field '(x)' with omitted initializer"
995 // if used in a struct which is default-initialized. Hence the split into
996 // these two separate constructors.
998 basic_fbstring() noexcept : basic_fbstring(A()) {
1001 explicit basic_fbstring(const A&) noexcept {
1004 basic_fbstring(const basic_fbstring& str)
1005 : store_(str.store_) {
1009 basic_fbstring(basic_fbstring&& goner) noexcept
1010 : store_(std::move(goner.store_)) {
1013 #ifndef _LIBSTDCXX_FBSTRING
1014 // This is defined for compatibility with std::string
1015 /* implicit */ basic_fbstring(const std::string& str)
1016 : store_(str.data(), str.size()) {
1020 basic_fbstring(const basic_fbstring& str,
1023 const A& /* a */ = A()) {
1024 assign(str, pos, n);
1027 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1029 ? traits_type::length(s)
1030 : (std::__throw_logic_error(
1031 "basic_fbstring: null pointer initializer not valid"),
1035 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1039 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1040 auto const pData = store_.expand_noinit(n);
1041 fbstring_detail::pod_fill(pData, pData + n, c);
1044 template <class InIt>
1045 basic_fbstring(InIt begin, InIt end,
1046 typename std::enable_if<
1047 !std::is_same<typename std::remove_const<InIt>::type,
1048 value_type*>::value, const A>::type & /*a*/ = A()) {
1052 // Specialization for const char*, const char*
1053 basic_fbstring(const value_type* b, const value_type* e)
1054 : store_(b, e - b) {
1057 // Nonstandard constructor
1058 basic_fbstring(value_type *s, size_type n, size_type c,
1059 AcquireMallocatedString a)
1060 : store_(s, n, c, a) {
1063 // Construction from initialization list
1064 basic_fbstring(std::initializer_list<value_type> il) {
1065 assign(il.begin(), il.end());
1068 ~basic_fbstring() noexcept {
1071 basic_fbstring& operator=(const basic_fbstring& lhs) {
1072 Invariant checker(*this);
1074 if (FBSTRING_UNLIKELY(&lhs == this)) {
1077 auto const oldSize = size();
1078 auto const srcSize = lhs.size();
1079 if (capacity() >= srcSize && !store_.isShared()) {
1080 // great, just copy the contents
1081 if (oldSize < srcSize) {
1082 store_.expand_noinit(srcSize - oldSize);
1084 store_.shrink(oldSize - srcSize);
1086 assert(size() == srcSize);
1087 auto srcData = lhs.data();
1088 fbstring_detail::pod_copy(
1089 srcData, srcData + srcSize, store_.mutable_data());
1091 // need to reallocate, so we may as well create a brand new string
1092 basic_fbstring(lhs).swap(*this);
1098 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1099 if (FBSTRING_UNLIKELY(&goner == this)) {
1100 // Compatibility with std::basic_string<>,
1101 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1104 // No need of this anymore
1105 this->~basic_fbstring();
1106 // Move the goner into this
1107 new(&store_) fbstring_core<E>(std::move(goner.store_));
1111 #ifndef _LIBSTDCXX_FBSTRING
1112 // Compatibility with std::string
1113 basic_fbstring & operator=(const std::string & rhs) {
1114 return assign(rhs.data(), rhs.size());
1117 // Compatibility with std::string
1118 std::string toStdString() const {
1119 return std::string(data(), size());
1122 // A lot of code in fbcode still uses this method, so keep it here for now.
1123 const basic_fbstring& toStdString() const {
1128 basic_fbstring& operator=(const value_type* s) {
1132 basic_fbstring& operator=(value_type c) {
1133 Invariant checker(*this);
1136 store_.expand_noinit(1);
1137 } else if (store_.isShared()) {
1138 basic_fbstring(1, c).swap(*this);
1141 store_.shrink(size() - 1);
1147 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1148 return assign(il.begin(), il.end());
1151 // C++11 21.4.3 iterators:
1152 iterator begin() { return store_.mutable_data(); }
1154 const_iterator begin() const { return store_.data(); }
1156 const_iterator cbegin() const { return begin(); }
1159 return store_.mutable_data() + store_.size();
1162 const_iterator end() const {
1163 return store_.data() + store_.size();
1166 const_iterator cend() const { return end(); }
1168 reverse_iterator rbegin() {
1169 return reverse_iterator(end());
1172 const_reverse_iterator rbegin() const {
1173 return const_reverse_iterator(end());
1176 const_reverse_iterator crbegin() const { return rbegin(); }
1178 reverse_iterator rend() {
1179 return reverse_iterator(begin());
1182 const_reverse_iterator rend() const {
1183 return const_reverse_iterator(begin());
1186 const_reverse_iterator crend() const { return rend(); }
1189 // C++11 21.4.5, element access:
1190 const value_type& front() const { return *begin(); }
1191 const value_type& back() const {
1193 // Should be begin()[size() - 1], but that branches twice
1194 return *(end() - 1);
1196 value_type& front() { return *begin(); }
1197 value_type& back() {
1199 // Should be begin()[size() - 1], but that branches twice
1200 return *(end() - 1);
1207 // C++11 21.4.4 capacity:
1208 size_type size() const { return store_.size(); }
1210 size_type length() const { return size(); }
1212 size_type max_size() const {
1213 return std::numeric_limits<size_type>::max();
1216 void resize(const size_type n, const value_type c = value_type()) {
1217 Invariant checker(*this);
1219 auto size = this->size();
1221 store_.shrink(size - n);
1223 auto const delta = n - size;
1224 auto pData = store_.expand_noinit(delta);
1225 fbstring_detail::pod_fill(pData, pData + delta, c);
1227 assert(this->size() == n);
1230 size_type capacity() const { return store_.capacity(); }
1232 void reserve(size_type res_arg = 0) {
1233 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1234 store_.reserve(res_arg);
1237 void shrink_to_fit() {
1238 // Shrink only if slack memory is sufficiently large
1239 if (capacity() < size() * 3 / 2) {
1242 basic_fbstring(cbegin(), cend()).swap(*this);
1245 void clear() { resize(0); }
1247 bool empty() const { return size() == 0; }
1249 // C++11 21.4.5 element access:
1250 const_reference operator[](size_type pos) const {
1251 return *(begin() + pos);
1254 reference operator[](size_type pos) {
1255 return *(begin() + pos);
1258 const_reference at(size_type n) const {
1259 enforce(n <= size(), std::__throw_out_of_range, "");
1263 reference at(size_type n) {
1264 enforce(n < size(), std::__throw_out_of_range, "");
1268 // C++11 21.4.6 modifiers:
1269 basic_fbstring& operator+=(const basic_fbstring& str) {
1273 basic_fbstring& operator+=(const value_type* s) {
1277 basic_fbstring& operator+=(const value_type c) {
1282 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1287 basic_fbstring& append(const basic_fbstring& str) {
1289 auto desiredSize = size() + str.size();
1291 append(str.data(), str.size());
1292 assert(size() == desiredSize);
1296 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1298 const size_type sz = str.size();
1299 enforce(pos <= sz, std::__throw_out_of_range, "");
1300 procrustes(n, sz - pos);
1301 return append(str.data() + pos, n);
1304 basic_fbstring& append(const value_type* s, size_type n) {
1305 Invariant checker(*this);
1307 if (FBSTRING_UNLIKELY(!n)) {
1308 // Unlikely but must be done
1311 auto const oldSize = size();
1312 auto const oldData = data();
1313 // Check for aliasing (rare). We could use "<=" here but in theory
1314 // those do not work for pointers unless the pointers point to
1315 // elements in the same array. For that reason we use
1316 // std::less_equal, which is guaranteed to offer a total order
1317 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1319 std::less_equal<const value_type*> le;
1320 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1321 assert(le(s + n, oldData + oldSize));
1322 const size_type offset = s - oldData;
1323 store_.reserve(oldSize + n);
1324 // Restore the source
1325 s = data() + offset;
1328 fbstring_detail::pod_copy(
1329 s, s + n, store_.expand_noinit(n, /* expGrowth = */ true));
1330 assert(size() == oldSize + n);
1334 basic_fbstring& append(const value_type* s) {
1335 return append(s, traits_type::length(s));
1338 basic_fbstring& append(size_type n, value_type c) {
1339 resize(size() + n, c);
1343 template<class InputIterator>
1344 basic_fbstring& append(InputIterator first, InputIterator last) {
1345 insert(end(), first, last);
1349 basic_fbstring& append(std::initializer_list<value_type> il) {
1350 return append(il.begin(), il.end());
1353 void push_back(const value_type c) { // primitive
1354 store_.push_back(c);
1357 basic_fbstring& assign(const basic_fbstring& str) {
1358 if (&str == this) return *this;
1359 return assign(str.data(), str.size());
1362 basic_fbstring& assign(basic_fbstring&& str) {
1363 return *this = std::move(str);
1366 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1368 const size_type sz = str.size();
1369 enforce(pos <= sz, std::__throw_out_of_range, "");
1370 procrustes(n, sz - pos);
1371 return assign(str.data() + pos, n);
1374 basic_fbstring& assign(const value_type* s, const size_type n) {
1375 Invariant checker(*this);
1377 // s can alias this, we need to use pod_move.
1379 fbstring_detail::pod_move(s, s + n, store_.mutable_data());
1381 assert(size() == n);
1383 const value_type *const s2 = s + size();
1384 fbstring_detail::pod_move(s, s2, store_.mutable_data());
1385 append(s2, n - size());
1386 assert(size() == n);
1388 assert(size() == n);
1392 basic_fbstring& assign(const value_type* s) {
1393 return assign(s, traits_type::length(s));
1396 basic_fbstring& assign(std::initializer_list<value_type> il) {
1397 return assign(il.begin(), il.end());
1400 template <class ItOrLength, class ItOrChar>
1401 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1402 return replace(begin(), end(), first_or_n, last_or_c);
1405 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1406 return insert(pos1, str.data(), str.size());
1409 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1410 size_type pos2, size_type n) {
1411 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1412 procrustes(n, str.length() - pos2);
1413 return insert(pos1, str.data() + pos2, n);
1416 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1417 enforce(pos <= length(), std::__throw_out_of_range, "");
1418 insert(begin() + pos, s, s + n);
1422 basic_fbstring& insert(size_type pos, const value_type* s) {
1423 return insert(pos, s, traits_type::length(s));
1426 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1427 enforce(pos <= length(), std::__throw_out_of_range, "");
1428 insert(begin() + pos, n, c);
1432 iterator insert(const_iterator p, const value_type c) {
1433 const size_type pos = p - begin();
1435 return begin() + pos;
1438 #ifndef _LIBSTDCXX_FBSTRING
1440 typedef std::basic_istream<value_type, traits_type> istream_type;
1443 friend inline istream_type& getline(istream_type& is,
1444 basic_fbstring& str,
1446 Invariant checker(str);
1451 size_t avail = str.capacity() - size;
1452 // fbstring has 1 byte extra capacity for the null terminator,
1453 // and getline null-terminates the read string.
1454 is.getline(str.store_.expand_noinit(avail), avail + 1, delim);
1455 size += is.gcount();
1457 if (is.bad() || is.eof() || !is.fail()) {
1458 // Done by either failure, end of file, or normal read.
1459 if (!is.bad() && !is.eof()) {
1460 --size; // gcount() also accounts for the delimiter.
1466 assert(size == str.size());
1467 assert(size == str.capacity());
1468 // Start at minimum allocation 63 + terminator = 64.
1469 str.reserve(std::max<size_t>(63, 3 * size / 2));
1470 // Clear the error so we can continue reading.
1476 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1477 return getline(is, str, '\n');
1482 template <int i> class Selector {};
1484 iterator insertImplDiscr(const_iterator i,
1485 size_type n, value_type c, Selector<1>) {
1486 Invariant checker(*this);
1488 assert(i >= begin() && i <= end());
1489 const size_type pos = i - begin();
1491 auto oldSize = size();
1492 store_.expand_noinit(n, /* expGrowth = */ true);
1494 fbstring_detail::pod_move(b + pos, b + oldSize, b + pos + n);
1495 fbstring_detail::pod_fill(b + pos, b + pos + n, c);
1500 template<class InputIter>
1501 iterator insertImplDiscr(const_iterator i,
1502 InputIter b, InputIter e, Selector<0>) {
1503 return insertImpl(i, b, e,
1504 typename std::iterator_traits<InputIter>::iterator_category());
1507 template <class FwdIterator>
1508 iterator insertImpl(const_iterator i,
1511 std::forward_iterator_tag) {
1512 Invariant checker(*this);
1514 assert(i >= begin() && i <= end());
1515 const size_type pos = i - begin();
1516 auto n = std::distance(s1, s2);
1519 auto oldSize = size();
1520 store_.expand_noinit(n, /* expGrowth = */ true);
1522 fbstring_detail::pod_move(b + pos, b + oldSize, b + pos + n);
1523 std::copy(s1, s2, b + pos);
1528 template <class InputIterator>
1529 iterator insertImpl(const_iterator i,
1530 InputIterator b, InputIterator e,
1531 std::input_iterator_tag) {
1532 const auto pos = i - begin();
1533 basic_fbstring temp(begin(), i);
1534 for (; b != e; ++b) {
1537 temp.append(i, cend());
1539 return begin() + pos;
1543 template <class ItOrLength, class ItOrChar>
1544 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1545 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1546 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1549 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1550 return insert(p, il.begin(), il.end());
1553 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1554 Invariant checker(*this);
1556 enforce(pos <= length(), std::__throw_out_of_range, "");
1557 procrustes(n, length() - pos);
1558 std::copy(begin() + pos + n, end(), begin() + pos);
1559 resize(length() - n);
1563 iterator erase(iterator position) {
1564 const size_type pos(position - begin());
1565 enforce(pos <= size(), std::__throw_out_of_range, "");
1567 return begin() + pos;
1570 iterator erase(iterator first, iterator last) {
1571 const size_type pos(first - begin());
1572 erase(pos, last - first);
1573 return begin() + pos;
1576 // Replaces at most n1 chars of *this, starting with pos1 with the
1578 basic_fbstring& replace(size_type pos1, size_type n1,
1579 const basic_fbstring& str) {
1580 return replace(pos1, n1, str.data(), str.size());
1583 // Replaces at most n1 chars of *this, starting with pos1,
1584 // with at most n2 chars of str starting with pos2
1585 basic_fbstring& replace(size_type pos1, size_type n1,
1586 const basic_fbstring& str,
1587 size_type pos2, size_type n2) {
1588 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1589 return replace(pos1, n1, str.data() + pos2,
1590 std::min(n2, str.size() - pos2));
1593 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1594 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1595 return replace(pos, n1, s, traits_type::length(s));
1598 // Replaces at most n1 chars of *this, starting with pos, with n2
1601 // consolidated with
1603 // Replaces at most n1 chars of *this, starting with pos, with at
1604 // most n2 chars of str. str must have at least n2 chars.
1605 template <class StrOrLength, class NumOrChar>
1606 basic_fbstring& replace(size_type pos, size_type n1,
1607 StrOrLength s_or_n2, NumOrChar n_or_c) {
1608 Invariant checker(*this);
1610 enforce(pos <= size(), std::__throw_out_of_range, "");
1611 procrustes(n1, length() - pos);
1612 const iterator b = begin() + pos;
1613 return replace(b, b + n1, s_or_n2, n_or_c);
1616 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1617 return replace(i1, i2, str.data(), str.length());
1620 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1621 return replace(i1, i2, s, traits_type::length(s));
1625 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1626 const value_type* s, size_type n,
1629 assert(begin() <= i1 && i1 <= end());
1630 assert(begin() <= i2 && i2 <= end());
1631 return replace(i1, i2, s, s + n);
1634 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1635 size_type n2, value_type c, Selector<1>) {
1636 const size_type n1 = i2 - i1;
1638 std::fill(i1, i1 + n2, c);
1641 std::fill(i1, i2, c);
1642 insert(i2, n2 - n1, c);
1648 template <class InputIter>
1649 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1650 InputIter b, InputIter e,
1652 replaceImpl(i1, i2, b, e,
1653 typename std::iterator_traits<InputIter>::iterator_category());
1658 template <class FwdIterator>
1659 bool replaceAliased(iterator /* i1 */,
1661 FwdIterator /* s1 */,
1662 FwdIterator /* s2 */,
1667 template <class FwdIterator>
1668 bool replaceAliased(iterator i1, iterator i2,
1669 FwdIterator s1, FwdIterator s2, std::true_type) {
1670 static const std::less_equal<const value_type*> le =
1671 std::less_equal<const value_type*>();
1672 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1676 // Aliased replace, copy to new string
1677 basic_fbstring temp;
1678 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1679 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1684 template <class FwdIterator>
1685 void replaceImpl(iterator i1, iterator i2,
1686 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1687 Invariant checker(*this);
1689 // Handle aliased replace
1690 if (replaceAliased(i1, i2, s1, s2,
1691 std::integral_constant<bool,
1692 std::is_same<FwdIterator, iterator>::value ||
1693 std::is_same<FwdIterator, const_iterator>::value>())) {
1697 auto const n1 = i2 - i1;
1699 auto const n2 = std::distance(s1, s2);
1704 std::copy(s1, s2, i1);
1708 fbstring_detail::copy_n(s1, n1, i1);
1709 std::advance(s1, n1);
1715 template <class InputIterator>
1716 void replaceImpl(iterator i1, iterator i2,
1717 InputIterator b, InputIterator e, std::input_iterator_tag) {
1718 basic_fbstring temp(begin(), i1);
1719 temp.append(b, e).append(i2, end());
1724 template <class T1, class T2>
1725 basic_fbstring& replace(iterator i1, iterator i2,
1726 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1728 num1 = std::numeric_limits<T1>::is_specialized,
1729 num2 = std::numeric_limits<T2>::is_specialized;
1730 return replaceImplDiscr(
1731 i1, i2, first_or_n_or_s, last_or_c_or_n,
1732 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1735 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1736 enforce(pos <= size(), std::__throw_out_of_range, "");
1737 procrustes(n, size() - pos);
1739 fbstring_detail::pod_copy(
1746 void swap(basic_fbstring& rhs) {
1747 store_.swap(rhs.store_);
1750 const value_type* c_str() const {
1751 return store_.c_str();
1754 const value_type* data() const { return c_str(); }
1756 allocator_type get_allocator() const {
1757 return allocator_type();
1760 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1761 return find(str.data(), pos, str.length());
1764 size_type find(const value_type* needle, const size_type pos,
1765 const size_type nsize) const {
1766 if (!nsize) return pos;
1767 auto const size = this->size();
1768 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1769 // that nsize + pos does not wrap around.
1770 if (nsize + pos > size || nsize + pos < pos) return npos;
1771 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1772 // the last characters first
1773 auto const haystack = data();
1774 auto const nsize_1 = nsize - 1;
1775 auto const lastNeedle = needle[nsize_1];
1777 // Boyer-Moore skip value for the last char in the needle. Zero is
1778 // not a valid value; skip will be computed the first time it's
1782 const E * i = haystack + pos;
1783 auto iEnd = haystack + size - nsize_1;
1786 // Boyer-Moore: match the last element in the needle
1787 while (i[nsize_1] != lastNeedle) {
1793 // Here we know that the last char matches
1794 // Continue in pedestrian mode
1795 for (size_t j = 0; ; ) {
1797 if (i[j] != needle[j]) {
1798 // Not found, we can skip
1799 // Compute the skip value lazily
1802 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1809 // Check if done searching
1812 return i - haystack;
1819 size_type find(const value_type* s, size_type pos = 0) const {
1820 return find(s, pos, traits_type::length(s));
1823 size_type find (value_type c, size_type pos = 0) const {
1824 return find(&c, pos, 1);
1827 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1828 return rfind(str.data(), pos, str.length());
1831 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1832 if (n > length()) return npos;
1833 pos = std::min(pos, length() - n);
1834 if (n == 0) return pos;
1836 const_iterator i(begin() + pos);
1838 if (traits_type::eq(*i, *s)
1839 && traits_type::compare(&*i, s, n) == 0) {
1842 if (i == begin()) break;
1847 size_type rfind(const value_type* s, size_type pos = npos) const {
1848 return rfind(s, pos, traits_type::length(s));
1851 size_type rfind(value_type c, size_type pos = npos) const {
1852 return rfind(&c, pos, 1);
1855 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1856 return find_first_of(str.data(), pos, str.length());
1859 size_type find_first_of(const value_type* s,
1860 size_type pos, size_type n) const {
1861 if (pos > length() || n == 0) return npos;
1862 const_iterator i(begin() + pos),
1864 for (; i != finish; ++i) {
1865 if (traits_type::find(s, n, *i) != 0) {
1872 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1873 return find_first_of(s, pos, traits_type::length(s));
1876 size_type find_first_of(value_type c, size_type pos = 0) const {
1877 return find_first_of(&c, pos, 1);
1880 size_type find_last_of (const basic_fbstring& str,
1881 size_type pos = npos) const {
1882 return find_last_of(str.data(), pos, str.length());
1885 size_type find_last_of (const value_type* s, size_type pos,
1886 size_type n) const {
1887 if (!empty() && n > 0) {
1888 pos = std::min(pos, length() - 1);
1889 const_iterator i(begin() + pos);
1891 if (traits_type::find(s, n, *i) != 0) {
1894 if (i == begin()) break;
1900 size_type find_last_of (const value_type* s,
1901 size_type pos = npos) const {
1902 return find_last_of(s, pos, traits_type::length(s));
1905 size_type find_last_of (value_type c, size_type pos = npos) const {
1906 return find_last_of(&c, pos, 1);
1909 size_type find_first_not_of(const basic_fbstring& str,
1910 size_type pos = 0) const {
1911 return find_first_not_of(str.data(), pos, str.size());
1914 size_type find_first_not_of(const value_type* s, size_type pos,
1915 size_type n) const {
1916 if (pos < length()) {
1920 for (; i != finish; ++i) {
1921 if (traits_type::find(s, n, *i) == 0) {
1929 size_type find_first_not_of(const value_type* s,
1930 size_type pos = 0) const {
1931 return find_first_not_of(s, pos, traits_type::length(s));
1934 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1935 return find_first_not_of(&c, pos, 1);
1938 size_type find_last_not_of(const basic_fbstring& str,
1939 size_type pos = npos) const {
1940 return find_last_not_of(str.data(), pos, str.length());
1943 size_type find_last_not_of(const value_type* s, size_type pos,
1944 size_type n) const {
1945 if (!this->empty()) {
1946 pos = std::min(pos, size() - 1);
1947 const_iterator i(begin() + pos);
1949 if (traits_type::find(s, n, *i) == 0) {
1952 if (i == begin()) break;
1958 size_type find_last_not_of(const value_type* s,
1959 size_type pos = npos) const {
1960 return find_last_not_of(s, pos, traits_type::length(s));
1963 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1964 return find_last_not_of(&c, pos, 1);
1967 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1968 enforce(pos <= size(), std::__throw_out_of_range, "");
1969 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1972 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1973 enforce(pos <= size(), std::__throw_out_of_range, "");
1975 if (n < size()) resize(n);
1976 return std::move(*this);
1979 int compare(const basic_fbstring& str) const {
1980 // FIX due to Goncalo N M de Carvalho July 18, 2005
1981 return compare(0, size(), str);
1984 int compare(size_type pos1, size_type n1,
1985 const basic_fbstring& str) const {
1986 return compare(pos1, n1, str.data(), str.size());
1989 int compare(size_type pos1, size_type n1,
1990 const value_type* s) const {
1991 return compare(pos1, n1, s, traits_type::length(s));
1994 int compare(size_type pos1, size_type n1,
1995 const value_type* s, size_type n2) const {
1996 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1997 procrustes(n1, size() - pos1);
1998 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1999 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2000 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2003 int compare(size_type pos1, size_type n1,
2004 const basic_fbstring& str,
2005 size_type pos2, size_type n2) const {
2006 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2007 return compare(pos1, n1, str.data() + pos2,
2008 std::min(n2, str.size() - pos2));
2011 // Code from Jean-Francois Bastien (03/26/2007)
2012 int compare(const value_type* s) const {
2013 // Could forward to compare(0, size(), s, traits_type::length(s))
2014 // but that does two extra checks
2015 const size_type n1(size()), n2(traits_type::length(s));
2016 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2017 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2025 // non-member functions
2027 template <typename E, class T, class A, class S>
2029 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2030 const basic_fbstring<E, T, A, S>& rhs) {
2032 basic_fbstring<E, T, A, S> result;
2033 result.reserve(lhs.size() + rhs.size());
2034 result.append(lhs).append(rhs);
2035 return std::move(result);
2039 template <typename E, class T, class A, class S>
2041 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2042 const basic_fbstring<E, T, A, S>& rhs) {
2043 return std::move(lhs.append(rhs));
2047 template <typename E, class T, class A, class S>
2049 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2050 basic_fbstring<E, T, A, S>&& rhs) {
2051 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2052 // Good, at least we don't need to reallocate
2053 return std::move(rhs.insert(0, lhs));
2055 // Meh, no go. Forward to operator+(const&, const&).
2056 auto const& rhsC = rhs;
2061 template <typename E, class T, class A, class S>
2063 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2064 basic_fbstring<E, T, A, S>&& rhs) {
2065 return std::move(lhs.append(rhs));
2069 template <typename E, class T, class A, class S>
2071 basic_fbstring<E, T, A, S> operator+(
2073 const basic_fbstring<E, T, A, S>& rhs) {
2075 basic_fbstring<E, T, A, S> result;
2076 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2077 result.reserve(len + rhs.size());
2078 result.append(lhs, len).append(rhs);
2083 template <typename E, class T, class A, class S>
2085 basic_fbstring<E, T, A, S> operator+(
2087 basic_fbstring<E, T, A, S>&& rhs) {
2089 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2090 if (rhs.capacity() >= len + rhs.size()) {
2091 // Good, at least we don't need to reallocate
2092 rhs.insert(rhs.begin(), lhs, lhs + len);
2095 // Meh, no go. Do it by hand since we have len already.
2096 basic_fbstring<E, T, A, S> result;
2097 result.reserve(len + rhs.size());
2098 result.append(lhs, len).append(rhs);
2103 template <typename E, class T, class A, class S>
2105 basic_fbstring<E, T, A, S> operator+(
2107 const basic_fbstring<E, T, A, S>& rhs) {
2109 basic_fbstring<E, T, A, S> result;
2110 result.reserve(1 + rhs.size());
2111 result.push_back(lhs);
2117 template <typename E, class T, class A, class S>
2119 basic_fbstring<E, T, A, S> operator+(
2121 basic_fbstring<E, T, A, S>&& rhs) {
2123 if (rhs.capacity() > rhs.size()) {
2124 // Good, at least we don't need to reallocate
2125 rhs.insert(rhs.begin(), lhs);
2128 // Meh, no go. Forward to operator+(E, const&).
2129 auto const& rhsC = rhs;
2134 template <typename E, class T, class A, class S>
2136 basic_fbstring<E, T, A, S> operator+(
2137 const basic_fbstring<E, T, A, S>& lhs,
2140 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2141 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2143 basic_fbstring<E, T, A, S> result;
2144 const size_type len = traits_type::length(rhs);
2145 result.reserve(lhs.size() + len);
2146 result.append(lhs).append(rhs, len);
2150 // C++11 21.4.8.1/10
2151 template <typename E, class T, class A, class S>
2153 basic_fbstring<E, T, A, S> operator+(
2154 basic_fbstring<E, T, A, S>&& lhs,
2157 return std::move(lhs += rhs);
2160 // C++11 21.4.8.1/11
2161 template <typename E, class T, class A, class S>
2163 basic_fbstring<E, T, A, S> operator+(
2164 const basic_fbstring<E, T, A, S>& lhs,
2167 basic_fbstring<E, T, A, S> result;
2168 result.reserve(lhs.size() + 1);
2170 result.push_back(rhs);
2174 // C++11 21.4.8.1/12
2175 template <typename E, class T, class A, class S>
2177 basic_fbstring<E, T, A, S> operator+(
2178 basic_fbstring<E, T, A, S>&& lhs,
2181 return std::move(lhs += rhs);
2184 template <typename E, class T, class A, class S>
2186 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2187 const basic_fbstring<E, T, A, S>& rhs) {
2188 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2190 template <typename E, class T, class A, class S>
2192 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2193 const basic_fbstring<E, T, A, S>& rhs) {
2194 return rhs == lhs; }
2196 template <typename E, class T, class A, class S>
2198 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2199 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2200 return lhs.compare(rhs) == 0; }
2202 template <typename E, class T, class A, class S>
2204 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2205 const basic_fbstring<E, T, A, S>& rhs) {
2206 return !(lhs == rhs); }
2208 template <typename E, class T, class A, class S>
2210 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2211 const basic_fbstring<E, T, A, S>& rhs) {
2212 return !(lhs == rhs); }
2214 template <typename E, class T, class A, class S>
2216 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2217 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2218 return !(lhs == rhs); }
2220 template <typename E, class T, class A, class S>
2222 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2223 const basic_fbstring<E, T, A, S>& rhs) {
2224 return lhs.compare(rhs) < 0; }
2226 template <typename E, class T, class A, class S>
2228 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2229 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2230 return lhs.compare(rhs) < 0; }
2232 template <typename E, class T, class A, class S>
2234 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2235 const basic_fbstring<E, T, A, S>& rhs) {
2236 return rhs.compare(lhs) > 0; }
2238 template <typename E, class T, class A, class S>
2240 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2241 const basic_fbstring<E, T, A, S>& rhs) {
2244 template <typename E, class T, class A, class S>
2246 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2247 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2250 template <typename E, class T, class A, class S>
2252 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2253 const basic_fbstring<E, T, A, S>& rhs) {
2256 template <typename E, class T, class A, class S>
2258 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2259 const basic_fbstring<E, T, A, S>& rhs) {
2260 return !(rhs < lhs); }
2262 template <typename E, class T, class A, class S>
2264 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2265 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2266 return !(rhs < lhs); }
2268 template <typename E, class T, class A, class S>
2270 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2271 const basic_fbstring<E, T, A, S>& rhs) {
2272 return !(rhs < lhs); }
2274 template <typename E, class T, class A, class S>
2276 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2277 const basic_fbstring<E, T, A, S>& rhs) {
2278 return !(lhs < rhs); }
2280 template <typename E, class T, class A, class S>
2282 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2283 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2284 return !(lhs < rhs); }
2286 template <typename E, class T, class A, class S>
2288 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2289 const basic_fbstring<E, T, A, S>& rhs) {
2290 return !(lhs < rhs);
2294 template <typename E, class T, class A, class S>
2295 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2299 // TODO: make this faster.
2300 template <typename E, class T, class A, class S>
2303 typename basic_fbstring<E, T, A, S>::value_type,
2304 typename basic_fbstring<E, T, A, S>::traits_type>&
2306 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2307 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2308 basic_fbstring<E, T, A, S>& str) {
2309 typename std::basic_istream<E, T>::sentry sentry(is);
2310 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2311 typename basic_fbstring<E, T, A, S>::traits_type>
2313 typedef typename __istream_type::ios_base __ios_base;
2314 size_t extracted = 0;
2315 auto err = __ios_base::goodbit;
2317 auto n = is.width();
2322 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2323 if (got == T::eof()) {
2324 err |= __ios_base::eofbit;
2328 if (isspace(got)) break;
2330 got = is.rdbuf()->snextc();
2334 err |= __ios_base::failbit;
2342 template <typename E, class T, class A, class S>
2344 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2345 typename basic_fbstring<E, T, A, S>::traits_type>&
2347 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2348 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2349 const basic_fbstring<E, T, A, S>& str) {
2351 typename std::basic_ostream<
2352 typename basic_fbstring<E, T, A, S>::value_type,
2353 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2355 typedef std::ostreambuf_iterator<
2356 typename basic_fbstring<E, T, A, S>::value_type,
2357 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2358 size_t __len = str.size();
2360 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2361 if (__pad_and_output(_Ip(os),
2363 __left ? str.data() + __len : str.data(),
2366 os.fill()).failed()) {
2367 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2370 #elif defined(_MSC_VER)
2371 // MSVC doesn't define __ostream_insert
2372 os.write(str.data(), str.size());
2374 std::__ostream_insert(os, str.data(), str.size());
2379 template <typename E1, class T, class A, class S>
2380 const typename basic_fbstring<E1, T, A, S>::size_type
2381 basic_fbstring<E1, T, A, S>::npos =
2382 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2384 #ifndef _LIBSTDCXX_FBSTRING
2385 // basic_string compatibility routines
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.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
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) {
2401 template <typename E, class T, class A, class S>
2403 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2404 const std::string& rhs) {
2405 return !(lhs == rhs);
2408 template <typename E, class T, class A, class S>
2410 bool operator!=(const std::string& lhs,
2411 const basic_fbstring<E, T, A, S>& rhs) {
2412 return !(lhs == rhs);
2415 #if !defined(_LIBSTDCXX_FBSTRING)
2416 typedef basic_fbstring<char> fbstring;
2419 // fbstring is relocatable
2420 template <class T, class R, class A, class S>
2421 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2424 _GLIBCXX_END_NAMESPACE_VERSION
2427 } // namespace folly
2429 #ifndef _LIBSTDCXX_FBSTRING
2431 // Hash functions to make fbstring usable with e.g. hash_map
2433 // Handle interaction with different C++ standard libraries, which
2434 // expect these types to be in different namespaces.
2436 #define FOLLY_FBSTRING_HASH1(T) \
2438 struct hash< ::folly::basic_fbstring<T> > { \
2439 size_t operator()(const ::folly::fbstring& s) const { \
2440 return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2444 // The C++11 standard says that these four are defined
2445 #define FOLLY_FBSTRING_HASH \
2446 FOLLY_FBSTRING_HASH1(char) \
2447 FOLLY_FBSTRING_HASH1(char16_t) \
2448 FOLLY_FBSTRING_HASH1(char32_t) \
2449 FOLLY_FBSTRING_HASH1(wchar_t)
2457 #if FOLLY_HAVE_DEPRECATED_ASSOC
2458 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2459 namespace __gnu_cxx {
2463 } // namespace __gnu_cxx
2464 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2465 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2467 #undef FOLLY_FBSTRING_HASH
2468 #undef FOLLY_FBSTRING_HASH1
2470 #endif // _LIBSTDCXX_FBSTRING
2472 #pragma GCC diagnostic pop
2474 #undef FBSTRING_DISABLE_SSO
2475 #undef FBSTRING_SANITIZE_ADDRESS
2477 #undef FBSTRING_LIKELY
2478 #undef FBSTRING_UNLIKELY
2480 #ifdef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2482 #undef FOLLY_DEFINED_NDEBUG_FOR_FBSTRING
2483 #endif // FOLLY_DEFINED_NDEBUG_FOR_FBSTRING