2 * Copyright 2014 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
25 #include <type_traits>
27 // This file appears in two locations: inside fbcode and in the
28 // libstdc++ source code (when embedding fbstring as std::string).
29 // To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
30 // libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
31 #ifdef _LIBSTDCXX_FBSTRING
33 #pragma GCC system_header
35 // Handle the cases where the fbcode version (folly/Malloc.h) is included
36 // either before or after this inclusion.
37 #ifdef FOLLY_MALLOC_H_
38 #undef FOLLY_MALLOC_H_
39 #include "basic_fbstring_malloc.h"
41 #include "basic_fbstring_malloc.h"
42 #undef FOLLY_MALLOC_H_
45 #else // !_LIBSTDCXX_FBSTRING
47 #include <folly/Portability.h>
49 // libc++ doesn't provide this header, nor does msvc
50 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
51 #include <bits/c++config.h>
59 #include <folly/Traits.h>
60 #include <folly/Malloc.h>
61 #include <folly/Hash.h>
62 #include <folly/ScopeGuard.h>
64 #if FOLLY_HAVE_DEPRECATED_ASSOC
65 #ifdef _GLIBCXX_SYMVER
66 #include <ext/hash_set>
67 #include <ext/hash_map>
73 // We defined these here rather than including Likely.h to avoid
74 // redefinition errors when fbstring is imported into libstdc++.
75 #if defined(__GNUC__) && __GNUC__ >= 4
76 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
77 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
79 #define FBSTRING_LIKELY(x) (x)
80 #define FBSTRING_UNLIKELY(x) (x)
83 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
84 #pragma GCC diagnostic push
85 #pragma GCC diagnostic ignored "-Wshadow"
87 // FBString cannot use throw when replacing std::string, though it may still
89 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
91 #ifdef _LIBSTDCXX_FBSTRING
92 namespace std _GLIBCXX_VISIBILITY(default) {
93 _GLIBCXX_BEGIN_NAMESPACE_VERSION
98 // Different versions of gcc/clang support different versions of
99 // the address sanitizer attribute. Unfortunately, this attribute
100 // has issues when inlining is used, so disable that as well.
101 #if defined(__clang__)
102 # if __has_feature(address_sanitizer)
103 # if __has_attribute(__no_address_safety_analysis__)
104 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
105 __attribute__((__no_address_safety_analysis__, __noinline__))
106 # elif __has_attribute(__no_sanitize_address__)
107 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
108 __attribute__((__no_sanitize_address__, __noinline__))
111 #elif defined (__GNUC__) && \
113 (__GNUC_MINOR__ >= 8) && \
115 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
116 __attribute__((__no_address_safety_analysis__, __noinline__))
118 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
119 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
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. Returns a pointer to the memory
231 // to be initialized (the beginning of the expanded portion). The
232 // caller is expected to fill the expanded area appropriately.
233 Char* expand_noinit(size_t delta);
234 // Expands the string by one character and sets the last character
236 void push_back(Char c);
237 // Returns the string's size.
239 // Returns the string's capacity, i.e. maximum size that the string
240 // can grow to without reallocation. Note that for reference counted
241 // strings that's technically a lie - even assigning characters
242 // within the existing size would cause a reallocation.
243 size_t capacity() const;
244 // Returns true if the data underlying the string is actually shared
245 // across multiple strings (in a refcounted fashion).
246 bool isShared() const;
247 // Makes sure that at least minCapacity characters are available for
248 // the string without reallocation. For reference-counted strings,
249 // it should fork the data even if minCapacity < size().
250 void reserve(size_t minCapacity);
253 fbstring_core_model& operator=(const fbstring_core_model &);
258 * gcc-4.7 throws what appears to be some false positive uninitialized
259 * warnings for the members of the MediumLarge struct. So, mute them here.
261 #if defined(__GNUC__) && !defined(__clang__)
262 # pragma GCC diagnostic push
263 # pragma GCC diagnostic ignored "-Wuninitialized"
267 * This is the core of the string. The code should work on 32- and
268 * 64-bit architectures and with any Char size. Porting to big endian
269 * architectures would require some changes.
271 * The storage is selected as follows (assuming we store one-byte
272 * characters on a 64-bit machine): (a) "small" strings between 0 and
273 * 23 chars are stored in-situ without allocation (the rightmost byte
274 * stores the size); (b) "medium" strings from 24 through 254 chars
275 * are stored in malloc-allocated memory that is copied eagerly; (c)
276 * "large" strings of 255 chars and above are stored in a similar
277 * structure as medium arrays, except that the string is
278 * reference-counted and copied lazily. the reference count is
279 * allocated right before the character array.
281 * The discriminator between these three strategies sits in the two
282 * most significant bits of the rightmost char of the storage. If
283 * neither is set, then the string is small (and its length sits in
284 * the lower-order bits of that rightmost character). If the MSb is
285 * set, the string is medium width. If the second MSb is set, then the
288 template <class Char> class fbstring_core {
290 fbstring_core() noexcept {
291 // Only initialize the tag, will set the MSBs (i.e. the small
292 // string size) to zero too
293 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
294 // or: setSmallSize(0);
296 assert(category() == Category::isSmall && size() == 0);
299 fbstring_core(const fbstring_core & rhs) {
300 assert(&rhs != this);
301 // Simplest case first: small strings are bitblitted
302 if (rhs.category() == Category::isSmall) {
303 static_assert(offsetof(MediumLarge, data_) == 0,
304 "fbstring layout failure");
305 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
306 "fbstring layout failure");
307 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
308 "fbstring layout failure");
309 const size_t size = rhs.smallSize();
311 ml_.capacity_ = rhs.ml_.capacity_;
314 // Just write the whole thing, don't look at details. In
315 // particular we need to copy capacity anyway because we want
316 // to set the size (don't forget that the last character,
317 // which stores a short string's length, is shared with the
318 // ml_.capacity field).
321 assert(category() == Category::isSmall && this->size() == rhs.size());
322 } else if (rhs.category() == Category::isLarge) {
323 // Large strings are just refcounted
325 RefCounted::incrementRefs(ml_.data_);
326 assert(category() == Category::isLarge && size() == rhs.size());
328 // Medium strings are copied eagerly. Don't forget to allocate
329 // one extra Char for the null terminator.
330 auto const allocSize =
331 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
332 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
333 fbstring_detail::pod_copy(rhs.ml_.data_,
335 rhs.ml_.data_ + rhs.ml_.size_ + 1,
337 // No need for writeTerminator() here, we copied one extra
338 // element just above.
339 ml_.size_ = rhs.ml_.size_;
340 ml_.capacity_ = (allocSize / sizeof(Char) - 1)
341 | static_cast<category_type>(Category::isMedium);
342 assert(category() == Category::isMedium);
344 assert(size() == rhs.size());
345 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
348 fbstring_core(fbstring_core&& goner) noexcept {
349 if (goner.category() == Category::isSmall) {
350 // Just copy, leave the goner in peace
351 new(this) fbstring_core(goner.small_, goner.smallSize());
355 // Clean goner's carcass
356 goner.setSmallSize(0);
360 // NOTE(agallagher): The word-aligned copy path copies bytes which are
361 // outside the range of the string, and makes address sanitizer unhappy,
362 // so just disable it on this function.
363 fbstring_core(const Char *const data, const size_t size)
364 FBSTRING_DISABLE_ADDRESS_SANITIZER {
366 #ifndef _LIBSTDCXX_FBSTRING
368 assert(this->size() == size);
369 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
374 // Simplest case first: small strings are bitblitted
375 if (size <= maxSmallSize) {
376 // Layout is: Char* data_, size_t size_, size_t capacity_
377 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
378 "fbstring has unexpected size");
379 static_assert(sizeof(Char*) == sizeof(size_t),
380 "fbstring size assumption violation");
381 // sizeof(size_t) must be a power of 2
382 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
383 "fbstring size assumption violation");
385 // If data is aligned, use fast word-wise copying. Otherwise,
386 // use conservative memcpy.
387 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
388 fbstring_detail::pod_copy(data, data + size, small_);
390 // Copy one word (64 bits) at a time
391 const size_t byteSize = size * sizeof(Char);
392 if (byteSize > 2 * sizeof(size_t)) {
394 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
396 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
398 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
399 } else if (byteSize > sizeof(size_t)) {
402 } else if (size > 0) {
409 } else if (size <= maxMediumSize) {
410 // Medium strings are allocated normally. Don't forget to
411 // allocate one extra Char for the terminating null.
412 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
413 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
414 fbstring_detail::pod_copy(data, data + size, ml_.data_);
416 ml_.capacity_ = (allocSize / sizeof(Char) - 1)
417 | static_cast<category_type>(Category::isMedium);
419 // Large strings are allocated differently
420 size_t effectiveCapacity = size;
421 auto const newRC = RefCounted::create(data, & effectiveCapacity);
422 ml_.data_ = newRC->data_;
424 ml_.capacity_ = effectiveCapacity
425 | static_cast<category_type>(Category::isLarge);
430 ~fbstring_core() noexcept {
431 auto const c = category();
432 if (c == Category::isSmall) {
435 if (c == Category::isMedium) {
439 RefCounted::decrementRefs(ml_.data_);
442 // Snatches a previously mallocated string. The parameter "size"
443 // is the size of the string, and the parameter "allocatedSize"
444 // is the size of the mallocated block. The string must be
445 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
447 // So if you want a 2-character string, pass malloc(3) as "data",
448 // pass 2 as "size", and pass 3 as "allocatedSize".
449 fbstring_core(Char * const data,
451 const size_t allocatedSize,
452 AcquireMallocatedString) {
454 assert(allocatedSize >= size + 1);
455 assert(data[size] == '\0');
456 // Use the medium string storage
459 // Don't forget about null terminator
460 ml_.capacity_ = (allocatedSize - 1)
461 | static_cast<category_type>(Category::isMedium);
463 // No need for the memory
469 // swap below doesn't test whether &rhs == this (and instead
470 // potentially does extra work) on the premise that the rarity of
471 // that situation actually makes the check more expensive than is
473 void swap(fbstring_core & rhs) {
479 // In C++11 data() and c_str() are 100% equivalent.
480 const Char * data() const {
484 Char * mutable_data() {
485 auto const c = category();
486 if (c == Category::isSmall) {
489 assert(c == Category::isMedium || c == Category::isLarge);
490 if (c == Category::isLarge && RefCounted::refs(ml_.data_) > 1) {
492 size_t effectiveCapacity = ml_.capacity();
493 auto const newRC = RefCounted::create(& effectiveCapacity);
494 // If this fails, someone placed the wrong capacity in an
496 assert(effectiveCapacity >= ml_.capacity());
497 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
499 RefCounted::decrementRefs(ml_.data_);
500 ml_.data_ = newRC->data_;
501 // No need to call writeTerminator(), we have + 1 above.
506 const Char * c_str() const {
507 auto const c = category();
508 if (c == Category::isSmall) {
509 assert(small_[smallSize()] == '\0');
512 assert(c == Category::isMedium || c == Category::isLarge);
513 assert(ml_.data_[ml_.size_] == '\0');
517 void shrink(const size_t delta) {
518 if (category() == Category::isSmall) {
519 // Check for underflow
520 assert(delta <= smallSize());
521 setSmallSize(smallSize() - delta);
522 } else if (category() == Category::isMedium ||
523 RefCounted::refs(ml_.data_) == 1) {
524 // Medium strings and unique large strings need no special
526 assert(ml_.size_ >= delta);
530 assert(ml_.size_ >= delta);
531 // Shared large string, must make unique. This is because of the
532 // durn terminator must be written, which may trample the shared
535 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
537 // No need to write the terminator.
541 void reserve(size_t minCapacity) {
542 if (category() == Category::isLarge) {
544 if (RefCounted::refs(ml_.data_) > 1) {
545 // We must make it unique regardless; in-place reallocation is
546 // useless if the string is shared. In order to not surprise
547 // people, reserve the new block at current capacity or
548 // more. That way, a string's capacity never shrinks after a
550 minCapacity = std::max(minCapacity, ml_.capacity());
551 auto const newRC = RefCounted::create(& minCapacity);
552 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
554 // Done with the old data. No need to call writeTerminator(),
555 // we have + 1 above.
556 RefCounted::decrementRefs(ml_.data_);
557 ml_.data_ = newRC->data_;
558 ml_.capacity_ = minCapacity
559 | static_cast<category_type>(Category::isLarge);
560 // size remains unchanged
562 // String is not shared, so let's try to realloc (if needed)
563 if (minCapacity > ml_.capacity()) {
564 // Asking for more memory
566 RefCounted::reallocate(ml_.data_, ml_.size_,
567 ml_.capacity(), minCapacity);
568 ml_.data_ = newRC->data_;
569 ml_.capacity_ = minCapacity
570 | static_cast<category_type>(Category::isLarge);
573 assert(capacity() >= minCapacity);
575 } else if (category() == Category::isMedium) {
576 // String is not shared
577 if (minCapacity <= ml_.capacity()) {
578 return; // nothing to do, there's enough room
580 if (minCapacity <= maxMediumSize) {
581 // Keep the string at medium size. Don't forget to allocate
582 // one extra Char for the terminating null.
583 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
584 ml_.data_ = static_cast<Char *>(
587 ml_.size_ * sizeof(Char),
588 (ml_.capacity() + 1) * sizeof(Char),
591 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1)
592 | static_cast<category_type>(Category::isMedium);
594 // Conversion from medium to large string
595 fbstring_core nascent;
596 // Will recurse to another branch of this function
597 nascent.reserve(minCapacity);
598 nascent.ml_.size_ = ml_.size_;
599 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
603 assert(capacity() >= minCapacity);
606 assert(category() == Category::isSmall);
607 if (minCapacity > maxMediumSize) {
609 auto const newRC = RefCounted::create(& minCapacity);
610 auto const size = smallSize();
611 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
612 // No need for writeTerminator(), we wrote it above with + 1.
613 ml_.data_ = newRC->data_;
615 ml_.capacity_ = minCapacity
616 | static_cast<category_type>(Category::isLarge);
617 assert(capacity() >= minCapacity);
618 } else if (minCapacity > maxSmallSize) {
620 // Don't forget to allocate one extra Char for the terminating null
621 auto const allocSizeBytes =
622 goodMallocSize((1 + minCapacity) * sizeof(Char));
623 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
624 auto const size = smallSize();
625 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
626 // No need for writeTerminator(), we wrote it above with + 1.
629 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1)
630 | static_cast<category_type>(Category::isMedium);
633 // Nothing to do, everything stays put
636 assert(capacity() >= minCapacity);
639 Char * expand_noinit(const size_t delta) {
640 // Strategy is simple: make room, then change size
641 assert(capacity() >= size());
643 if (category() == Category::isSmall) {
646 if (newSz <= maxSmallSize) {
653 newSz = ml_.size_ + delta;
654 if (newSz > capacity()) {
658 assert(capacity() >= newSz);
659 // Category can't be small - we took care of that above
660 assert(category() == Category::isMedium || category() == Category::isLarge);
663 assert(size() == newSz);
664 return ml_.data_ + sz;
667 void push_back(Char c) {
668 assert(capacity() >= size());
670 if (category() == Category::isSmall) {
672 if (sz < maxSmallSize) {
674 setSmallSize(sz + 1);
677 reserve(maxSmallSize * 2);
680 if (sz == capacity()) { // always true for isShared()
681 reserve(1 + sz * 3 / 2); // ensures not shared
685 assert(capacity() >= sz + 1);
686 // Category can't be small - we took care of that above
687 assert(category() == Category::isMedium || category() == Category::isLarge);
693 size_t size() const {
694 return category() == Category::isSmall ? smallSize() : ml_.size_;
697 size_t capacity() const {
698 switch (category()) {
699 case Category::isSmall:
701 case Category::isLarge:
702 // For large-sized strings, a multi-referenced chunk has no
703 // available capacity. This is because any attempt to append
704 // data would trigger a new allocation.
705 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
708 return ml_.capacity();
711 bool isShared() const {
712 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
715 void writeTerminator() {
716 if (category() == Category::isSmall) {
717 const auto s = smallSize();
718 if (s != maxSmallSize) {
722 ml_.data_[ml_.size_] = '\0';
728 fbstring_core & operator=(const fbstring_core & rhs);
735 size_t capacity() const {
736 return capacity_ & capacityExtractMask;
741 std::atomic<size_t> refCount_;
744 static RefCounted * fromData(Char * p) {
745 return static_cast<RefCounted*>(
747 static_cast<unsigned char*>(static_cast<void*>(p))
748 - sizeof(refCount_)));
751 static size_t refs(Char * p) {
752 return fromData(p)->refCount_.load(std::memory_order_acquire);
755 static void incrementRefs(Char * p) {
756 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
759 static void decrementRefs(Char * p) {
760 auto const dis = fromData(p);
761 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
768 static RefCounted * create(size_t * size) {
769 // Don't forget to allocate one extra Char for the terminating
770 // null. In this case, however, one Char is already part of the
772 const size_t allocSize = goodMallocSize(
773 sizeof(RefCounted) + *size * sizeof(Char));
774 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
775 result->refCount_.store(1, std::memory_order_release);
776 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
780 static RefCounted * create(const Char * data, size_t * size) {
781 const size_t effectiveSize = *size;
782 auto result = create(size);
783 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
787 static RefCounted * reallocate(Char *const data,
788 const size_t currentSize,
789 const size_t currentCapacity,
790 const size_t newCapacity) {
791 assert(newCapacity > 0 && newCapacity > currentSize);
792 auto const dis = fromData(data);
793 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
794 // Don't forget to allocate one extra Char for the terminating
795 // null. In this case, however, one Char is already part of the
797 auto result = static_cast<RefCounted*>(
799 sizeof(RefCounted) + currentSize * sizeof(Char),
800 sizeof(RefCounted) + currentCapacity * sizeof(Char),
801 sizeof(RefCounted) + newCapacity * sizeof(Char)));
802 assert(result->refCount_.load(std::memory_order_acquire) == 1);
808 Char small_[sizeof(MediumLarge) / sizeof(Char)];
813 lastChar = sizeof(MediumLarge) - 1,
814 maxSmallSize = lastChar / sizeof(Char),
815 maxMediumSize = 254 / sizeof(Char), // coincides with the small
816 // bin size in dlmalloc
817 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
818 capacityExtractMask = ~categoryExtractMask,
820 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
821 "Corrupt memory layout for fbstring.");
823 typedef std::conditional<sizeof(size_t) == 4, uint32_t, uint64_t>::type
826 enum class Category : category_type {
828 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
829 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
832 Category category() const {
833 // Assumes little endian
834 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
837 size_t smallSize() const {
838 assert(category() == Category::isSmall &&
839 static_cast<size_t>(small_[maxSmallSize])
840 <= static_cast<size_t>(maxSmallSize));
841 return static_cast<size_t>(maxSmallSize)
842 - static_cast<size_t>(small_[maxSmallSize]);
845 void setSmallSize(size_t s) {
846 // Warning: this should work with uninitialized strings too,
847 // so don't assume anything about the previous value of
848 // small_[maxSmallSize].
849 assert(s <= maxSmallSize);
850 small_[maxSmallSize] = maxSmallSize - s;
855 #if defined(__GNUC__) && !defined(__clang__)
856 # pragma GCC diagnostic pop
859 #ifndef _LIBSTDCXX_FBSTRING
861 * Dummy fbstring core that uses an actual std::string. This doesn't
862 * make any sense - it's just for testing purposes.
864 template <class Char>
865 class dummy_fbstring_core {
867 dummy_fbstring_core() {
869 dummy_fbstring_core(const dummy_fbstring_core& another)
870 : backend_(another.backend_) {
872 dummy_fbstring_core(const Char * s, size_t n)
875 void swap(dummy_fbstring_core & rhs) {
876 backend_.swap(rhs.backend_);
878 const Char * data() const {
879 return backend_.data();
881 Char * mutable_data() {
882 //assert(!backend_.empty());
883 return &*backend_.begin();
885 void shrink(size_t delta) {
886 assert(delta <= size());
887 backend_.resize(size() - delta);
889 Char * expand_noinit(size_t delta) {
890 auto const sz = size();
891 backend_.resize(size() + delta);
892 return backend_.data() + sz;
894 void push_back(Char c) {
895 backend_.push_back(c);
897 size_t size() const {
898 return backend_.size();
900 size_t capacity() const {
901 return backend_.capacity();
903 bool isShared() const {
906 void reserve(size_t minCapacity) {
907 backend_.reserve(minCapacity);
911 std::basic_string<Char> backend_;
913 #endif // !_LIBSTDCXX_FBSTRING
916 * This is the basic_string replacement. For conformity,
917 * basic_fbstring takes the same template parameters, plus the last
918 * one which is the core.
920 #ifdef _LIBSTDCXX_FBSTRING
921 template <typename E, class T, class A, class Storage>
923 template <typename E,
924 class T = std::char_traits<E>,
925 class A = std::allocator<E>,
926 class Storage = fbstring_core<E> >
928 class basic_fbstring {
932 void (*throw_exc)(const char*),
934 if (!condition) throw_exc(msg);
937 bool isSane() const {
940 empty() == (size() == 0) &&
941 empty() == (begin() == end()) &&
942 size() <= max_size() &&
943 capacity() <= max_size() &&
944 size() <= capacity() &&
945 begin()[size()] == '\0';
949 friend struct Invariant;
952 explicit Invariant(const basic_fbstring& s) : s_(s) {
959 const basic_fbstring& s_;
961 explicit Invariant(const basic_fbstring&) {}
963 Invariant& operator=(const Invariant&);
968 typedef T traits_type;
969 typedef typename traits_type::char_type value_type;
970 typedef A allocator_type;
971 typedef typename A::size_type size_type;
972 typedef typename A::difference_type difference_type;
974 typedef typename A::reference reference;
975 typedef typename A::const_reference const_reference;
976 typedef typename A::pointer pointer;
977 typedef typename A::const_pointer const_pointer;
980 typedef const E* const_iterator;
981 typedef std::reverse_iterator<iterator
982 #ifdef NO_ITERATOR_TRAITS
986 typedef std::reverse_iterator<const_iterator
987 #ifdef NO_ITERATOR_TRAITS
990 > const_reverse_iterator;
992 static const size_type npos; // = size_type(-1)
995 static void procrustes(size_type& n, size_type nmax) {
996 if (n > nmax) n = nmax;
1000 // C++11 21.4.2 construct/copy/destroy
1001 explicit basic_fbstring(const A& a = 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, size_type pos,
1021 size_type n = npos, const A& a = A()) {
1022 assign(str, pos, n);
1025 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1027 ? traits_type::length(s)
1028 : (std::__throw_logic_error(
1029 "basic_fbstring: null pointer initializer not valid"),
1033 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1037 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1038 auto const data = store_.expand_noinit(n);
1039 fbstring_detail::pod_fill(data, data + n, c);
1040 store_.writeTerminator();
1043 template <class InIt>
1044 basic_fbstring(InIt begin, InIt end,
1045 typename std::enable_if<
1046 !std::is_same<typename std::remove_const<InIt>::type,
1047 value_type*>::value, const A>::type & a = A()) {
1051 // Specialization for const char*, const char*
1052 basic_fbstring(const value_type* b, const value_type* e)
1053 : store_(b, e - b) {
1056 // Nonstandard constructor
1057 basic_fbstring(value_type *s, size_type n, size_type c,
1058 AcquireMallocatedString a)
1059 : store_(s, n, c, a) {
1062 // Construction from initialization list
1063 basic_fbstring(std::initializer_list<value_type> il) {
1064 assign(il.begin(), il.end());
1067 ~basic_fbstring() noexcept {
1070 basic_fbstring& operator=(const basic_fbstring& lhs) {
1071 if (FBSTRING_UNLIKELY(&lhs == this)) {
1074 auto const oldSize = size();
1075 auto const srcSize = lhs.size();
1076 if (capacity() >= srcSize && !store_.isShared()) {
1077 // great, just copy the contents
1078 if (oldSize < srcSize)
1079 store_.expand_noinit(srcSize - oldSize);
1081 store_.shrink(oldSize - srcSize);
1082 assert(size() == srcSize);
1083 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1084 store_.writeTerminator();
1086 // need to reallocate, so we may as well create a brand new string
1087 basic_fbstring(lhs).swap(*this);
1093 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1094 if (FBSTRING_UNLIKELY(&goner == this)) {
1095 // Compatibility with std::basic_string<>,
1096 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1099 // No need of this anymore
1100 this->~basic_fbstring();
1101 // Move the goner into this
1102 new(&store_) fbstring_core<E>(std::move(goner.store_));
1106 #ifndef _LIBSTDCXX_FBSTRING
1107 // Compatibility with std::string
1108 basic_fbstring & operator=(const std::string & rhs) {
1109 return assign(rhs.data(), rhs.size());
1112 // Compatibility with std::string
1113 std::string toStdString() const {
1114 return std::string(data(), size());
1117 // A lot of code in fbcode still uses this method, so keep it here for now.
1118 const basic_fbstring& toStdString() const {
1123 basic_fbstring& operator=(const value_type* s) {
1127 basic_fbstring& operator=(value_type c) {
1129 store_.expand_noinit(1);
1130 } else if (store_.isShared()) {
1131 basic_fbstring(1, c).swap(*this);
1134 store_.shrink(size() - 1);
1136 *store_.mutable_data() = c;
1137 store_.writeTerminator();
1141 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1142 return assign(il.begin(), il.end());
1145 // C++11 21.4.3 iterators:
1146 iterator begin() { return store_.mutable_data(); }
1148 const_iterator begin() const { return store_.data(); }
1150 const_iterator cbegin() const { return begin(); }
1153 return store_.mutable_data() + store_.size();
1156 const_iterator end() const {
1157 return store_.data() + store_.size();
1160 const_iterator cend() const { return end(); }
1162 reverse_iterator rbegin() {
1163 return reverse_iterator(end());
1166 const_reverse_iterator rbegin() const {
1167 return const_reverse_iterator(end());
1170 const_reverse_iterator crbegin() const { return rbegin(); }
1172 reverse_iterator rend() {
1173 return reverse_iterator(begin());
1176 const_reverse_iterator rend() const {
1177 return const_reverse_iterator(begin());
1180 const_reverse_iterator crend() const { return rend(); }
1183 // C++11 21.4.5, element access:
1184 const value_type& front() const { return *begin(); }
1185 const value_type& back() const {
1187 // Should be begin()[size() - 1], but that branches twice
1188 return *(end() - 1);
1190 value_type& front() { return *begin(); }
1191 value_type& back() {
1193 // Should be begin()[size() - 1], but that branches twice
1194 return *(end() - 1);
1201 // C++11 21.4.4 capacity:
1202 size_type size() const { return store_.size(); }
1204 size_type length() const { return size(); }
1206 size_type max_size() const {
1207 return std::numeric_limits<size_type>::max();
1210 void resize(const size_type n, const value_type c = value_type()) {
1211 auto size = this->size();
1213 store_.shrink(size - n);
1215 // Do this in two steps to minimize slack memory copied (see
1217 auto const capacity = this->capacity();
1218 assert(capacity >= size);
1219 if (size < capacity) {
1220 auto delta = std::min(n, capacity) - size;
1221 store_.expand_noinit(delta);
1222 fbstring_detail::pod_fill(begin() + size, end(), c);
1225 store_.writeTerminator();
1230 auto const delta = n - size;
1231 store_.expand_noinit(delta);
1232 fbstring_detail::pod_fill(end() - delta, end(), c);
1233 store_.writeTerminator();
1235 assert(this->size() == n);
1238 size_type capacity() const { return store_.capacity(); }
1240 void reserve(size_type res_arg = 0) {
1241 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1242 store_.reserve(res_arg);
1245 void shrink_to_fit() {
1246 // Shrink only if slack memory is sufficiently large
1247 if (capacity() < size() * 3 / 2) {
1250 basic_fbstring(cbegin(), cend()).swap(*this);
1253 void clear() { resize(0); }
1255 bool empty() const { return size() == 0; }
1257 // C++11 21.4.5 element access:
1258 const_reference operator[](size_type pos) const {
1259 return *(begin() + pos);
1262 reference operator[](size_type pos) {
1263 return *(begin() + pos);
1266 const_reference at(size_type n) const {
1267 enforce(n <= size(), std::__throw_out_of_range, "");
1271 reference at(size_type n) {
1272 enforce(n < size(), std::__throw_out_of_range, "");
1276 // C++11 21.4.6 modifiers:
1277 basic_fbstring& operator+=(const basic_fbstring& str) {
1281 basic_fbstring& operator+=(const value_type* s) {
1285 basic_fbstring& operator+=(const value_type c) {
1290 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1295 basic_fbstring& append(const basic_fbstring& str) {
1297 auto desiredSize = size() + str.size();
1299 append(str.data(), str.size());
1300 assert(size() == desiredSize);
1304 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1306 const size_type sz = str.size();
1307 enforce(pos <= sz, std::__throw_out_of_range, "");
1308 procrustes(n, sz - pos);
1309 return append(str.data() + pos, n);
1312 basic_fbstring& append(const value_type* s, size_type n) {
1314 Invariant checker(*this);
1317 if (FBSTRING_UNLIKELY(!n)) {
1318 // Unlikely but must be done
1321 auto const oldSize = size();
1322 auto const oldData = data();
1323 // Check for aliasing (rare). We could use "<=" here but in theory
1324 // those do not work for pointers unless the pointers point to
1325 // elements in the same array. For that reason we use
1326 // std::less_equal, which is guaranteed to offer a total order
1327 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1329 std::less_equal<const value_type*> le;
1330 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1331 assert(le(s + n, oldData + oldSize));
1332 const size_type offset = s - oldData;
1333 store_.reserve(oldSize + n);
1334 // Restore the source
1335 s = data() + offset;
1337 // Warning! Repeated appends with short strings may actually incur
1338 // practically quadratic performance. Avoid that by pushing back
1339 // the first character (which ensures exponential growth) and then
1340 // appending the rest normally. Worst case the append may incur a
1341 // second allocation but that will be rare.
1344 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1345 assert(size() == oldSize + n + 1);
1349 basic_fbstring& append(const value_type* s) {
1350 return append(s, traits_type::length(s));
1353 basic_fbstring& append(size_type n, value_type c) {
1354 resize(size() + n, c);
1358 template<class InputIterator>
1359 basic_fbstring& append(InputIterator first, InputIterator last) {
1360 insert(end(), first, last);
1364 basic_fbstring& append(std::initializer_list<value_type> il) {
1365 return append(il.begin(), il.end());
1368 void push_back(const value_type c) { // primitive
1369 store_.push_back(c);
1372 basic_fbstring& assign(const basic_fbstring& str) {
1373 if (&str == this) return *this;
1374 return assign(str.data(), str.size());
1377 basic_fbstring& assign(basic_fbstring&& str) {
1378 return *this = std::move(str);
1381 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1383 const size_type sz = str.size();
1384 enforce(pos <= sz, std::__throw_out_of_range, "");
1385 procrustes(n, sz - pos);
1386 return assign(str.data() + pos, n);
1389 basic_fbstring& assign(const value_type* s, const size_type n) {
1390 Invariant checker(*this);
1393 std::copy(s, s + n, begin());
1395 assert(size() == n);
1397 const value_type *const s2 = s + size();
1398 std::copy(s, s2, begin());
1399 append(s2, n - size());
1400 assert(size() == n);
1402 store_.writeTerminator();
1403 assert(size() == n);
1407 basic_fbstring& assign(const value_type* s) {
1408 return assign(s, traits_type::length(s));
1411 basic_fbstring& assign(std::initializer_list<value_type> il) {
1412 return assign(il.begin(), il.end());
1415 template <class ItOrLength, class ItOrChar>
1416 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1417 return replace(begin(), end(), first_or_n, last_or_c);
1420 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1421 return insert(pos1, str.data(), str.size());
1424 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1425 size_type pos2, size_type n) {
1426 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1427 procrustes(n, str.length() - pos2);
1428 return insert(pos1, str.data() + pos2, n);
1431 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1432 enforce(pos <= length(), std::__throw_out_of_range, "");
1433 insert(begin() + pos, s, s + n);
1437 basic_fbstring& insert(size_type pos, const value_type* s) {
1438 return insert(pos, s, traits_type::length(s));
1441 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1442 enforce(pos <= length(), std::__throw_out_of_range, "");
1443 insert(begin() + pos, n, c);
1447 iterator insert(const_iterator p, const value_type c) {
1448 const size_type pos = p - begin();
1450 return begin() + pos;
1454 template <int i> class Selector {};
1456 iterator insertImplDiscr(const_iterator p,
1457 size_type n, value_type c, Selector<1>) {
1458 Invariant checker(*this);
1460 auto const pos = p - begin();
1461 assert(p >= begin() && p <= end());
1462 if (capacity() - size() < n) {
1463 const size_type sz = p - begin();
1464 reserve(size() + n);
1467 const iterator oldEnd = end();
1468 if (n < size_type(oldEnd - p)) {
1469 append(oldEnd - n, oldEnd);
1471 // reverse_iterator(oldEnd - n),
1472 // reverse_iterator(p),
1473 // reverse_iterator(oldEnd));
1474 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1476 std::fill(begin() + pos, begin() + pos + n, c);
1478 append(n - (end() - p), c);
1479 append(iterator(p), oldEnd);
1480 std::fill(iterator(p), oldEnd, c);
1482 store_.writeTerminator();
1483 return begin() + pos;
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,
1495 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1496 Invariant checker(*this);
1498 const size_type pos = i - begin();
1499 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1500 std::distance(s1, s2);
1502 using namespace fbstring_detail;
1503 assert(pos <= size());
1505 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1506 capacity() - size();
1508 // realloc the string
1509 reserve(size() + n2);
1512 if (pos + n2 <= size()) {
1513 const iterator tailBegin = end() - n2;
1514 store_.expand_noinit(n2);
1515 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1516 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1517 reverse_iterator(tailBegin + n2));
1518 std::copy(s1, s2, begin() + pos);
1521 const size_type old_size = size();
1522 std::advance(t, old_size - pos);
1523 const size_t newElems = std::distance(t, s2);
1524 store_.expand_noinit(n2);
1525 std::copy(t, s2, begin() + old_size);
1526 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1527 begin() + old_size + newElems);
1528 std::copy(s1, t, begin() + pos);
1530 store_.writeTerminator();
1531 return begin() + pos;
1534 template <class InputIterator>
1535 iterator insertImpl(const_iterator i,
1536 InputIterator b, InputIterator e,
1537 std::input_iterator_tag) {
1538 const auto pos = i - begin();
1539 basic_fbstring temp(begin(), i);
1540 for (; b != e; ++b) {
1543 temp.append(i, cend());
1545 return begin() + pos;
1549 template <class ItOrLength, class ItOrChar>
1550 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1551 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1552 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1555 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1556 return insert(p, il.begin(), il.end());
1559 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1560 Invariant checker(*this);
1562 enforce(pos <= length(), std::__throw_out_of_range, "");
1563 procrustes(n, length() - pos);
1564 std::copy(begin() + pos + n, end(), begin() + pos);
1565 resize(length() - n);
1569 iterator erase(iterator position) {
1570 const size_type pos(position - begin());
1571 enforce(pos <= size(), std::__throw_out_of_range, "");
1573 return begin() + pos;
1576 iterator erase(iterator first, iterator last) {
1577 const size_type pos(first - begin());
1578 erase(pos, last - first);
1579 return begin() + pos;
1582 // Replaces at most n1 chars of *this, starting with pos1 with the
1584 basic_fbstring& replace(size_type pos1, size_type n1,
1585 const basic_fbstring& str) {
1586 return replace(pos1, n1, str.data(), str.size());
1589 // Replaces at most n1 chars of *this, starting with pos1,
1590 // with at most n2 chars of str starting with pos2
1591 basic_fbstring& replace(size_type pos1, size_type n1,
1592 const basic_fbstring& str,
1593 size_type pos2, size_type n2) {
1594 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1595 return replace(pos1, n1, str.data() + pos2,
1596 std::min(n2, str.size() - pos2));
1599 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1600 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1601 return replace(pos, n1, s, traits_type::length(s));
1604 // Replaces at most n1 chars of *this, starting with pos, with n2
1607 // consolidated with
1609 // Replaces at most n1 chars of *this, starting with pos, with at
1610 // most n2 chars of str. str must have at least n2 chars.
1611 template <class StrOrLength, class NumOrChar>
1612 basic_fbstring& replace(size_type pos, size_type n1,
1613 StrOrLength s_or_n2, NumOrChar n_or_c) {
1614 Invariant checker(*this);
1616 enforce(pos <= size(), std::__throw_out_of_range, "");
1617 procrustes(n1, length() - pos);
1618 const iterator b = begin() + pos;
1619 return replace(b, b + n1, s_or_n2, n_or_c);
1622 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1623 return replace(i1, i2, str.data(), str.length());
1626 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1627 return replace(i1, i2, s, traits_type::length(s));
1631 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1632 const value_type* s, size_type n,
1635 assert(begin() <= i1 && i1 <= end());
1636 assert(begin() <= i2 && i2 <= end());
1637 return replace(i1, i2, s, s + n);
1640 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1641 size_type n2, value_type c, Selector<1>) {
1642 const size_type n1 = i2 - i1;
1644 std::fill(i1, i1 + n2, c);
1647 std::fill(i1, i2, c);
1648 insert(i2, n2 - n1, c);
1654 template <class InputIter>
1655 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1656 InputIter b, InputIter e,
1658 replaceImpl(i1, i2, b, e,
1659 typename std::iterator_traits<InputIter>::iterator_category());
1664 template <class FwdIterator>
1665 bool replaceAliased(iterator i1, iterator i2,
1666 FwdIterator s1, FwdIterator s2, std::false_type) {
1670 template <class FwdIterator>
1671 bool replaceAliased(iterator i1, iterator i2,
1672 FwdIterator s1, FwdIterator s2, std::true_type) {
1673 static const std::less_equal<const value_type*> le =
1674 std::less_equal<const value_type*>();
1675 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1679 // Aliased replace, copy to new string
1680 basic_fbstring temp;
1681 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1682 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1687 template <class FwdIterator>
1688 void replaceImpl(iterator i1, iterator i2,
1689 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1690 Invariant checker(*this);
1693 // Handle aliased replace
1694 if (replaceAliased(i1, i2, s1, s2,
1695 std::integral_constant<bool,
1696 std::is_same<FwdIterator, iterator>::value ||
1697 std::is_same<FwdIterator, const_iterator>::value>())) {
1701 auto const n1 = i2 - i1;
1703 auto const n2 = std::distance(s1, s2);
1708 std::copy(s1, s2, i1);
1712 fbstring_detail::copy_n(s1, n1, i1);
1713 std::advance(s1, n1);
1719 template <class InputIterator>
1720 void replaceImpl(iterator i1, iterator i2,
1721 InputIterator b, InputIterator e, std::input_iterator_tag) {
1722 basic_fbstring temp(begin(), i1);
1723 temp.append(b, e).append(i2, end());
1728 template <class T1, class T2>
1729 basic_fbstring& replace(iterator i1, iterator i2,
1730 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1732 num1 = std::numeric_limits<T1>::is_specialized,
1733 num2 = std::numeric_limits<T2>::is_specialized;
1734 return replaceImplDiscr(
1735 i1, i2, first_or_n_or_s, last_or_c_or_n,
1736 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1739 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1740 enforce(pos <= size(), std::__throw_out_of_range, "");
1741 procrustes(n, size() - pos);
1743 fbstring_detail::pod_copy(
1750 void swap(basic_fbstring& rhs) {
1751 store_.swap(rhs.store_);
1754 const value_type* c_str() const {
1755 return store_.c_str();
1758 const value_type* data() const { return c_str(); }
1760 allocator_type get_allocator() const {
1761 return allocator_type();
1764 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1765 return find(str.data(), pos, str.length());
1768 size_type find(const value_type* needle, const size_type pos,
1769 const size_type nsize) const {
1770 if (!nsize) return pos;
1771 auto const size = this->size();
1772 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1773 // that nsize + pos does not wrap around.
1774 if (nsize + pos > size || nsize + pos < pos) return npos;
1775 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1776 // the last characters first
1777 auto const haystack = data();
1778 auto const nsize_1 = nsize - 1;
1779 auto const lastNeedle = needle[nsize_1];
1781 // Boyer-Moore skip value for the last char in the needle. Zero is
1782 // not a valid value; skip will be computed the first time it's
1786 const E * i = haystack + pos;
1787 auto iEnd = haystack + size - nsize_1;
1790 // Boyer-Moore: match the last element in the needle
1791 while (i[nsize_1] != lastNeedle) {
1797 // Here we know that the last char matches
1798 // Continue in pedestrian mode
1799 for (size_t j = 0; ; ) {
1801 if (i[j] != needle[j]) {
1802 // Not found, we can skip
1803 // Compute the skip value lazily
1806 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1813 // Check if done searching
1816 return i - haystack;
1823 size_type find(const value_type* s, size_type pos = 0) const {
1824 return find(s, pos, traits_type::length(s));
1827 size_type find (value_type c, size_type pos = 0) const {
1828 return find(&c, pos, 1);
1831 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1832 return rfind(str.data(), pos, str.length());
1835 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1836 if (n > length()) return npos;
1837 pos = std::min(pos, length() - n);
1838 if (n == 0) return pos;
1840 const_iterator i(begin() + pos);
1842 if (traits_type::eq(*i, *s)
1843 && traits_type::compare(&*i, s, n) == 0) {
1846 if (i == begin()) break;
1851 size_type rfind(const value_type* s, size_type pos = npos) const {
1852 return rfind(s, pos, traits_type::length(s));
1855 size_type rfind(value_type c, size_type pos = npos) const {
1856 return rfind(&c, pos, 1);
1859 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1860 return find_first_of(str.data(), pos, str.length());
1863 size_type find_first_of(const value_type* s,
1864 size_type pos, size_type n) const {
1865 if (pos > length() || n == 0) return npos;
1866 const_iterator i(begin() + pos),
1868 for (; i != finish; ++i) {
1869 if (traits_type::find(s, n, *i) != 0) {
1876 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1877 return find_first_of(s, pos, traits_type::length(s));
1880 size_type find_first_of(value_type c, size_type pos = 0) const {
1881 return find_first_of(&c, pos, 1);
1884 size_type find_last_of (const basic_fbstring& str,
1885 size_type pos = npos) const {
1886 return find_last_of(str.data(), pos, str.length());
1889 size_type find_last_of (const value_type* s, size_type pos,
1890 size_type n) const {
1891 if (!empty() && n > 0) {
1892 pos = std::min(pos, length() - 1);
1893 const_iterator i(begin() + pos);
1895 if (traits_type::find(s, n, *i) != 0) {
1898 if (i == begin()) break;
1904 size_type find_last_of (const value_type* s,
1905 size_type pos = npos) const {
1906 return find_last_of(s, pos, traits_type::length(s));
1909 size_type find_last_of (value_type c, size_type pos = npos) const {
1910 return find_last_of(&c, pos, 1);
1913 size_type find_first_not_of(const basic_fbstring& str,
1914 size_type pos = 0) const {
1915 return find_first_not_of(str.data(), pos, str.size());
1918 size_type find_first_not_of(const value_type* s, size_type pos,
1919 size_type n) const {
1920 if (pos < length()) {
1924 for (; i != finish; ++i) {
1925 if (traits_type::find(s, n, *i) == 0) {
1933 size_type find_first_not_of(const value_type* s,
1934 size_type pos = 0) const {
1935 return find_first_not_of(s, pos, traits_type::length(s));
1938 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1939 return find_first_not_of(&c, pos, 1);
1942 size_type find_last_not_of(const basic_fbstring& str,
1943 size_type pos = npos) const {
1944 return find_last_not_of(str.data(), pos, str.length());
1947 size_type find_last_not_of(const value_type* s, size_type pos,
1948 size_type n) const {
1949 if (!this->empty()) {
1950 pos = std::min(pos, size() - 1);
1951 const_iterator i(begin() + pos);
1953 if (traits_type::find(s, n, *i) == 0) {
1956 if (i == begin()) break;
1962 size_type find_last_not_of(const value_type* s,
1963 size_type pos = npos) const {
1964 return find_last_not_of(s, pos, traits_type::length(s));
1967 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1968 return find_last_not_of(&c, pos, 1);
1971 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1972 enforce(pos <= size(), std::__throw_out_of_range, "");
1973 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1976 int compare(const basic_fbstring& str) const {
1977 // FIX due to Goncalo N M de Carvalho July 18, 2005
1978 return compare(0, size(), str);
1981 int compare(size_type pos1, size_type n1,
1982 const basic_fbstring& str) const {
1983 return compare(pos1, n1, str.data(), str.size());
1986 int compare(size_type pos1, size_type n1,
1987 const value_type* s) const {
1988 return compare(pos1, n1, s, traits_type::length(s));
1991 int compare(size_type pos1, size_type n1,
1992 const value_type* s, size_type n2) const {
1993 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1994 procrustes(n1, size() - pos1);
1995 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1996 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1997 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2000 int compare(size_type pos1, size_type n1,
2001 const basic_fbstring& str,
2002 size_type pos2, size_type n2) const {
2003 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2004 return compare(pos1, n1, str.data() + pos2,
2005 std::min(n2, str.size() - pos2));
2008 // Code from Jean-Francois Bastien (03/26/2007)
2009 int compare(const value_type* s) const {
2010 // Could forward to compare(0, size(), s, traits_type::length(s))
2011 // but that does two extra checks
2012 const size_type n1(size()), n2(traits_type::length(s));
2013 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2014 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2022 // non-member functions
2024 template <typename E, class T, class A, class S>
2026 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2027 const basic_fbstring<E, T, A, S>& rhs) {
2029 basic_fbstring<E, T, A, S> result;
2030 result.reserve(lhs.size() + rhs.size());
2031 result.append(lhs).append(rhs);
2032 return std::move(result);
2036 template <typename E, class T, class A, class S>
2038 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2039 const basic_fbstring<E, T, A, S>& rhs) {
2040 return std::move(lhs.append(rhs));
2044 template <typename E, class T, class A, class S>
2046 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2047 basic_fbstring<E, T, A, S>&& rhs) {
2048 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2049 // Good, at least we don't need to reallocate
2050 return std::move(rhs.insert(0, lhs));
2052 // Meh, no go. Forward to operator+(const&, const&).
2053 auto const& rhsC = rhs;
2058 template <typename E, class T, class A, class S>
2060 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2061 basic_fbstring<E, T, A, S>&& rhs) {
2062 return std::move(lhs.append(rhs));
2065 template <typename E, class T, class A, class S>
2067 basic_fbstring<E, T, A, S> operator+(
2068 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2069 const basic_fbstring<E, T, A, S>& rhs) {
2071 basic_fbstring<E, T, A, S> result;
2072 const typename basic_fbstring<E, T, A, S>::size_type len =
2073 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2074 result.reserve(len + rhs.size());
2075 result.append(lhs, len).append(rhs);
2079 template <typename E, class T, class A, class S>
2081 basic_fbstring<E, T, A, S> operator+(
2082 typename basic_fbstring<E, T, A, S>::value_type lhs,
2083 const basic_fbstring<E, T, A, S>& rhs) {
2085 basic_fbstring<E, T, A, S> result;
2086 result.reserve(1 + rhs.size());
2087 result.push_back(lhs);
2092 template <typename E, class T, class A, class S>
2094 basic_fbstring<E, T, A, S> operator+(
2095 const basic_fbstring<E, T, A, S>& lhs,
2096 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2098 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2099 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2101 basic_fbstring<E, T, A, S> result;
2102 const size_type len = traits_type::length(rhs);
2103 result.reserve(lhs.size() + len);
2104 result.append(lhs).append(rhs, len);
2108 template <typename E, class T, class A, class S>
2110 basic_fbstring<E, T, A, S> operator+(
2111 const basic_fbstring<E, T, A, S>& lhs,
2112 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2114 basic_fbstring<E, T, A, S> result;
2115 result.reserve(lhs.size() + 1);
2117 result.push_back(rhs);
2121 template <typename E, class T, class A, class S>
2123 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2124 const basic_fbstring<E, T, A, S>& rhs) {
2125 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2127 template <typename E, class T, class A, class S>
2129 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2130 const basic_fbstring<E, T, A, S>& rhs) {
2131 return rhs == lhs; }
2133 template <typename E, class T, class A, class S>
2135 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2136 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2137 return lhs.compare(rhs) == 0; }
2139 template <typename E, class T, class A, class S>
2141 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2142 const basic_fbstring<E, T, A, S>& rhs) {
2143 return !(lhs == rhs); }
2145 template <typename E, class T, class A, class S>
2147 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2148 const basic_fbstring<E, T, A, S>& rhs) {
2149 return !(lhs == rhs); }
2151 template <typename E, class T, class A, class S>
2153 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2154 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2155 return !(lhs == rhs); }
2157 template <typename E, class T, class A, class S>
2159 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2160 const basic_fbstring<E, T, A, S>& rhs) {
2161 return lhs.compare(rhs) < 0; }
2163 template <typename E, class T, class A, class S>
2165 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2166 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2167 return lhs.compare(rhs) < 0; }
2169 template <typename E, class T, class A, class S>
2171 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2172 const basic_fbstring<E, T, A, S>& rhs) {
2173 return rhs.compare(lhs) > 0; }
2175 template <typename E, class T, class A, class S>
2177 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2178 const basic_fbstring<E, T, A, S>& rhs) {
2181 template <typename E, class T, class A, class S>
2183 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2184 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2187 template <typename E, class T, class A, class S>
2189 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2190 const basic_fbstring<E, T, A, S>& rhs) {
2193 template <typename E, class T, class A, class S>
2195 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2196 const basic_fbstring<E, T, A, S>& rhs) {
2197 return !(rhs < lhs); }
2199 template <typename E, class T, class A, class S>
2201 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2202 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2203 return !(rhs < lhs); }
2205 template <typename E, class T, class A, class S>
2207 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2208 const basic_fbstring<E, T, A, S>& rhs) {
2209 return !(rhs < lhs); }
2211 template <typename E, class T, class A, class S>
2213 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2214 const basic_fbstring<E, T, A, S>& rhs) {
2215 return !(lhs < rhs); }
2217 template <typename E, class T, class A, class S>
2219 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2220 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2221 return !(lhs < rhs); }
2223 template <typename E, class T, class A, class S>
2225 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2226 const basic_fbstring<E, T, A, S>& rhs) {
2227 return !(lhs < rhs);
2231 template <typename E, class T, class A, class S>
2232 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2236 // TODO: make this faster.
2237 template <typename E, class T, class A, class S>
2240 typename basic_fbstring<E, T, A, S>::value_type,
2241 typename basic_fbstring<E, T, A, S>::traits_type>&
2243 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2244 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2245 basic_fbstring<E, T, A, S>& str) {
2246 typename std::basic_istream<E, T>::sentry sentry(is);
2247 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2248 typename basic_fbstring<E, T, A, S>::traits_type>
2250 typedef typename __istream_type::ios_base __ios_base;
2251 size_t extracted = 0;
2252 auto err = __ios_base::goodbit;
2254 auto n = is.width();
2259 auto got = is.rdbuf()->sgetc();
2260 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2261 // Whew. We get to store this guy
2263 got = is.rdbuf()->snextc();
2265 if (got == T::eof()) {
2266 err |= __ios_base::eofbit;
2271 err |= __ios_base::failbit;
2279 template <typename E, class T, class A, class S>
2281 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2282 typename basic_fbstring<E, T, A, S>::traits_type>&
2284 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2285 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2286 const basic_fbstring<E, T, A, S>& str) {
2288 typename std::basic_ostream<
2289 typename basic_fbstring<E, T, A, S>::value_type,
2290 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2292 typedef std::ostreambuf_iterator<
2293 typename basic_fbstring<E, T, A, S>::value_type,
2294 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2295 size_t __len = str.size();
2297 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2298 if (__pad_and_output(_Ip(os),
2300 __left ? str.data() + __len : str.data(),
2303 os.fill()).failed()) {
2304 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2308 std::__ostream_insert(os, str.data(), str.size());
2313 #ifndef _LIBSTDCXX_FBSTRING
2315 template <typename E, class T, class A, class S>
2317 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2318 typename basic_fbstring<E, T, A, S>::traits_type>&
2320 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2321 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2322 basic_fbstring<E, T, A, S>& str,
2323 typename basic_fbstring<E, T, A, S>::value_type delim) {
2324 // Use the nonstandard getdelim()
2325 char * buf = nullptr;
2328 // This looks quadratic but it really depends on realloc
2329 auto const newSize = size + 128;
2330 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2331 is.getline(buf + size, newSize - size, delim);
2332 if (is.bad() || is.eof() || !is.fail()) {
2333 // done by either failure, end of file, or normal read
2334 size += std::strlen(buf + size);
2337 // Here we have failed due to too short a buffer
2338 // Minus one to discount the terminating '\0'
2340 assert(buf[size] == 0);
2341 // Clear the error so we can continue reading
2344 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2345 AcquireMallocatedString());
2350 template <typename E, class T, class A, class S>
2352 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2353 typename basic_fbstring<E, T, A, S>::traits_type>&
2355 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2356 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2357 basic_fbstring<E, T, A, S>& str) {
2358 // Just forward to the version with a delimiter
2359 return getline(is, str, '\n');
2364 template <typename E1, class T, class A, class S>
2365 const typename basic_fbstring<E1, T, A, S>::size_type
2366 basic_fbstring<E1, T, A, S>::npos =
2367 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2369 #ifndef _LIBSTDCXX_FBSTRING
2370 // basic_string compatibility routines
2372 template <typename E, class T, class A, class S>
2374 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2375 const std::string& rhs) {
2376 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2379 template <typename E, class T, class A, class S>
2381 bool operator==(const std::string& lhs,
2382 const basic_fbstring<E, T, A, S>& rhs) {
2386 template <typename E, class T, class A, class S>
2388 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2389 const std::string& rhs) {
2390 return !(lhs == rhs);
2393 template <typename E, class T, class A, class S>
2395 bool operator!=(const std::string& lhs,
2396 const basic_fbstring<E, T, A, S>& rhs) {
2397 return !(lhs == rhs);
2400 #if !defined(_LIBSTDCXX_FBSTRING)
2401 typedef basic_fbstring<char> fbstring;
2404 // fbstring is relocatable
2405 template <class T, class R, class A, class S>
2406 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2409 _GLIBCXX_END_NAMESPACE_VERSION
2412 } // namespace folly
2414 #ifndef _LIBSTDCXX_FBSTRING
2416 // Hash functions to make fbstring usable with e.g. hash_map
2418 // Handle interaction with different C++ standard libraries, which
2419 // expect these types to be in different namespaces.
2421 #define FOLLY_FBSTRING_HASH1(T) \
2423 struct hash< ::folly::basic_fbstring<T> > { \
2424 size_t operator()(const ::folly::fbstring& s) const { \
2425 return ::folly::hash::fnv32_buf(s.data(), s.size()); \
2429 // The C++11 standard says that these four are defined
2430 #define FOLLY_FBSTRING_HASH \
2431 FOLLY_FBSTRING_HASH1(char) \
2432 FOLLY_FBSTRING_HASH1(char16_t) \
2433 FOLLY_FBSTRING_HASH1(char32_t) \
2434 FOLLY_FBSTRING_HASH1(wchar_t)
2442 #if FOLLY_HAVE_DEPRECATED_ASSOC
2443 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2444 namespace __gnu_cxx {
2448 } // namespace __gnu_cxx
2449 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2450 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
2452 #undef FOLLY_FBSTRING_HASH
2453 #undef FOLLY_FBSTRING_HASH1
2455 #endif // _LIBSTDCXX_FBSTRING
2457 #pragma GCC diagnostic pop
2459 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2461 #undef FBSTRING_LIKELY
2462 #undef FBSTRING_UNLIKELY
2464 #endif // FOLLY_BASE_FBSTRING_H_