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>
28 #include "folly/Portability.h"
30 // libc++ doesn't provide this header, nor does msvc
31 #ifdef FOLLY_HAVE_BITS_CXXCONFIG_H
32 // This file appears in two locations: inside fbcode and in the
33 // libstdc++ source code (when embedding fbstring as std::string).
34 // To aid in this schizophrenic use, two macros are defined in
36 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
37 // gate use inside fbcode v. libstdc++
38 #include <bits/c++config.h>
41 #ifdef _LIBSTDCXX_FBSTRING
43 #pragma GCC system_header
45 // Handle the cases where the fbcode version (folly/Malloc.h) is included
46 // either before or after this inclusion.
47 #ifdef FOLLY_MALLOC_H_
48 #undef FOLLY_MALLOC_H_
49 #include "basic_fbstring_malloc.h"
51 #include "basic_fbstring_malloc.h"
52 #undef FOLLY_MALLOC_H_
55 #else // !_LIBSTDCXX_FBSTRING
61 #include "folly/Traits.h"
62 #include "folly/Malloc.h"
63 #include "folly/Hash.h"
64 #include "folly/ScopeGuard.h"
66 #if FOLLY_HAVE_DEPRECATED_ASSOC
67 #ifdef _GLIBCXX_SYMVER
68 #include <ext/hash_set>
69 #include <ext/hash_map>
75 // We defined these here rather than including Likely.h to avoid
76 // redefinition errors when fbstring is imported into libstdc++.
77 #if defined(__GNUC__) && __GNUC__ >= 4
78 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
79 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
81 #define FBSTRING_LIKELY(x) (x)
82 #define FBSTRING_UNLIKELY(x) (x)
85 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
86 #pragma GCC diagnostic push
87 #pragma GCC diagnostic ignored "-Wshadow"
89 // FBString cannot use throw when replacing std::string, though it may still
91 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
93 #ifdef _LIBSTDCXX_FBSTRING
94 namespace std _GLIBCXX_VISIBILITY(default) {
95 _GLIBCXX_BEGIN_NAMESPACE_VERSION
100 // Different versions of gcc/clang support different versions of
101 // the address sanitizer attribute. Unfortunately, this attribute
102 // has issues when inlining is used, so disable that as well.
103 #if defined(__clang__)
104 # if __has_feature(address_sanitizer)
105 # if __has_attribute(__no_address_safety_analysis__)
106 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
107 __attribute__((__no_address_safety_analysis__, __noinline__))
108 # elif __has_attribute(__no_sanitize_address__)
109 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
110 __attribute__((__no_sanitize_address__, __noinline__))
113 #elif defined (__GNUC__) && \
115 (__GNUC_MINOR__ >= 8) && \
117 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
118 __attribute__((__no_address_safety_analysis__, __noinline__))
120 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
121 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
124 namespace fbstring_detail {
126 template <class InIt, class OutIt>
129 typename std::iterator_traits<InIt>::difference_type n,
131 for (; n != 0; --n, ++b, ++d) {
137 template <class Pod, class T>
138 inline void pod_fill(Pod* b, Pod* e, T c) {
139 assert(b && e && b <= e);
140 /*static*/ if (sizeof(T) == 1) {
143 auto const ee = b + ((e - b) & ~7u);
144 for (; b != ee; b += 8) {
155 for (; b != e; ++b) {
162 * Lightly structured memcpy, simplifies copying PODs and introduces
163 * some asserts. Unfortunately using this function may cause
164 * measurable overhead (presumably because it adjusts from a begin/end
165 * convention to a pointer/size convention, so it does some extra
166 * arithmetic even though the caller might have done the inverse
167 * adaptation outside).
170 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
172 assert(d >= e || d + (e - b) <= b);
173 memcpy(d, b, (e - b) * sizeof(Pod));
177 * Lightly structured memmove, simplifies copying PODs and introduces
181 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
183 memmove(d, b, (e - b) * sizeof(*b));
186 } // namespace fbstring_detail
189 * Defines a special acquisition method for constructing fbstring
190 * objects. AcquireMallocatedString means that the user passes a
191 * pointer to a malloc-allocated string that the fbstring object will
194 enum class AcquireMallocatedString {};
197 * fbstring_core_model is a mock-up type that defines all required
198 * signatures of a fbstring core. The fbstring class itself uses such
199 * a core object to implement all of the numerous member functions
200 * required by the standard.
202 * If you want to define a new core, copy the definition below and
203 * implement the primitives. Then plug the core into basic_fbstring as
204 * a template argument.
206 template <class Char>
207 class fbstring_core_model {
209 fbstring_core_model();
210 fbstring_core_model(const fbstring_core_model &);
211 ~fbstring_core_model();
212 // Returns a pointer to string's buffer (currently only contiguous
213 // strings are supported). The pointer is guaranteed to be valid
214 // until the next call to a non-const member function.
215 const Char * data() const;
216 // Much like data(), except the string is prepared to support
217 // character-level changes. This call is a signal for
218 // e.g. reference-counted implementation to fork the data. The
219 // pointer is guaranteed to be valid until the next call to a
220 // non-const member function.
221 Char * mutable_data();
222 // Returns a pointer to string's buffer and guarantees that a
223 // readable '\0' lies right after the buffer. The pointer is
224 // guaranteed to be valid until the next call to a non-const member
226 const Char * c_str() const;
227 // Shrinks the string by delta characters. Asserts that delta <=
229 void shrink(size_t delta);
230 // Expands the string by delta characters (i.e. after this call
231 // size() will report the old size() plus delta) but without
232 // initializing the expanded region. Returns a pointer to the memory
233 // to be initialized (the beginning of the expanded portion). The
234 // caller is expected to fill the expanded area appropriately.
235 Char* expand_noinit(size_t delta);
236 // Expands the string by one character and sets the last character
238 void push_back(Char c);
239 // Returns the string's size.
241 // Returns the string's capacity, i.e. maximum size that the string
242 // can grow to without reallocation. Note that for reference counted
243 // strings that's technically a lie - even assigning characters
244 // within the existing size would cause a reallocation.
245 size_t capacity() const;
246 // Returns true if the data underlying the string is actually shared
247 // across multiple strings (in a refcounted fashion).
248 bool isShared() const;
249 // Makes sure that at least minCapacity characters are available for
250 // the string without reallocation. For reference-counted strings,
251 // it should fork the data even if minCapacity < size().
252 void reserve(size_t minCapacity);
255 fbstring_core_model& operator=(const fbstring_core_model &);
260 * gcc-4.7 throws what appears to be some false positive uninitialized
261 * warnings for the members of the MediumLarge struct. So, mute them here.
263 #if defined(__GNUC__) && !defined(__clang__)
264 # pragma GCC diagnostic push
265 # pragma GCC diagnostic ignored "-Wuninitialized"
269 * This is the core of the string. The code should work on 32- and
270 * 64-bit architectures and with any Char size. Porting to big endian
271 * architectures would require some changes.
273 * The storage is selected as follows (assuming we store one-byte
274 * characters on a 64-bit machine): (a) "small" strings between 0 and
275 * 23 chars are stored in-situ without allocation (the rightmost byte
276 * stores the size); (b) "medium" strings from 24 through 254 chars
277 * are stored in malloc-allocated memory that is copied eagerly; (c)
278 * "large" strings of 255 chars and above are stored in a similar
279 * structure as medium arrays, except that the string is
280 * reference-counted and copied lazily. the reference count is
281 * allocated right before the character array.
283 * The discriminator between these three strategies sits in the two
284 * most significant bits of the rightmost char of the storage. If
285 * neither is set, then the string is small (and its length sits in
286 * the lower-order bits of that rightmost character). If the MSb is
287 * set, the string is medium width. If the second MSb is set, then the
290 template <class Char> class fbstring_core {
292 fbstring_core() noexcept {
293 // Only initialize the tag, will set the MSBs (i.e. the small
294 // string size) to zero too
295 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
296 // or: setSmallSize(0);
298 assert(category() == isSmall && size() == 0);
301 fbstring_core(const fbstring_core & rhs) {
302 assert(&rhs != this);
303 // Simplest case first: small strings are bitblitted
304 if (rhs.category() == isSmall) {
305 static_assert(offsetof(MediumLarge, data_) == 0,
306 "fbstring layout failure");
307 static_assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_),
308 "fbstring layout failure");
309 static_assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
310 "fbstring layout failure");
311 const size_t size = rhs.smallSize();
313 ml_.capacity_ = rhs.ml_.capacity_;
316 // Just write the whole thing, don't look at details. In
317 // particular we need to copy capacity anyway because we want
318 // to set the size (don't forget that the last character,
319 // which stores a short string's length, is shared with the
320 // ml_.capacity field).
323 assert(category() == isSmall && this->size() == rhs.size());
324 } else if (rhs.category() == isLarge) {
325 // Large strings are just refcounted
327 RefCounted::incrementRefs(ml_.data_);
328 assert(category() == isLarge && size() == rhs.size());
330 // Medium strings are copied eagerly. Don't forget to allocate
331 // one extra Char for the null terminator.
332 auto const allocSize =
333 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
334 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
335 fbstring_detail::pod_copy(rhs.ml_.data_,
337 rhs.ml_.data_ + rhs.ml_.size_ + 1,
339 // No need for writeTerminator() here, we copied one extra
340 // element just above.
341 ml_.size_ = rhs.ml_.size_;
342 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
343 assert(category() == isMedium);
345 assert(size() == rhs.size());
346 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
349 fbstring_core(fbstring_core&& goner) noexcept {
350 if (goner.category() == isSmall) {
351 // Just copy, leave the goner in peace
352 new(this) fbstring_core(goner.small_, goner.smallSize());
356 // Clean goner's carcass
357 goner.setSmallSize(0);
361 // NOTE(agallagher): The word-aligned copy path copies bytes which are
362 // outside the range of the string, and makes address sanitizer unhappy,
363 // so just disable it on this function.
364 fbstring_core(const Char *const data, const size_t size)
365 FBSTRING_DISABLE_ADDRESS_SANITIZER {
367 #ifndef _LIBSTDCXX_FBSTRING
369 assert(this->size() == size);
370 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
375 // Simplest case first: small strings are bitblitted
376 if (size <= maxSmallSize) {
377 // Layout is: Char* data_, size_t size_, size_t capacity_
378 static_assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
379 "fbstring has unexpected size");
380 static_assert(sizeof(Char*) == sizeof(size_t),
381 "fbstring size assumption violation");
382 // sizeof(size_t) must be a power of 2
383 static_assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
384 "fbstring size assumption violation");
386 // If data is aligned, use fast word-wise copying. Otherwise,
387 // use conservative memcpy.
388 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
389 fbstring_detail::pod_copy(data, data + size, small_);
391 // Copy one word (64 bits) at a time
392 const size_t byteSize = size * sizeof(Char);
393 if (byteSize > 2 * sizeof(size_t)) {
395 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
397 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
399 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
400 } else if (byteSize > sizeof(size_t)) {
403 } else if (size > 0) {
410 } else if (size <= maxMediumSize) {
411 // Medium strings are allocated normally. Don't forget to
412 // allocate one extra Char for the terminating null.
413 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
414 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
415 fbstring_detail::pod_copy(data, data + size, ml_.data_);
417 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | 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 | isLarge;
429 ~fbstring_core() noexcept {
430 auto const c = category();
438 RefCounted::decrementRefs(ml_.data_);
441 // Snatches a previously mallocated string. The parameter "size"
442 // is the size of the string, and the parameter "allocatedSize"
443 // is the size of the mallocated block. The string must be
444 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
446 // So if you want a 2-character string, pass malloc(3) as "data",
447 // pass 2 as "size", and pass 3 as "allocatedSize".
448 fbstring_core(Char * const data,
450 const size_t allocatedSize,
451 AcquireMallocatedString) {
453 assert(allocatedSize >= size + 1);
454 assert(data[size] == '\0');
455 // Use the medium string storage
458 // Don't forget about null terminator
459 ml_.capacity_ = (allocatedSize - 1) | isMedium;
461 // No need for the memory
467 // swap below doesn't test whether &rhs == this (and instead
468 // potentially does extra work) on the premise that the rarity of
469 // that situation actually makes the check more expensive than is
471 void swap(fbstring_core & rhs) {
477 // In C++11 data() and c_str() are 100% equivalent.
478 const Char * data() const {
482 Char * mutable_data() {
483 auto const c = category();
487 assert(c == isMedium || c == isLarge);
488 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
490 size_t effectiveCapacity = ml_.capacity();
491 auto const newRC = RefCounted::create(& effectiveCapacity);
492 // If this fails, someone placed the wrong capacity in an
494 assert(effectiveCapacity >= ml_.capacity());
495 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
497 RefCounted::decrementRefs(ml_.data_);
498 ml_.data_ = newRC->data_;
499 // No need to call writeTerminator(), we have + 1 above.
504 const Char * c_str() const {
505 auto const c = category();
507 assert(small_[smallSize()] == '\0');
510 assert(c == isMedium || c == isLarge);
511 assert(ml_.data_[ml_.size_] == '\0');
515 void shrink(const size_t delta) {
516 if (category() == isSmall) {
517 // Check for underflow
518 assert(delta <= smallSize());
519 setSmallSize(smallSize() - delta);
520 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
521 // Medium strings and unique large strings need no special
523 assert(ml_.size_ >= delta);
527 assert(ml_.size_ >= delta);
528 // Shared large string, must make unique. This is because of the
529 // durn terminator must be written, which may trample the shared
532 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
534 // No need to write the terminator.
538 void reserve(size_t minCapacity) {
539 if (category() == isLarge) {
541 if (RefCounted::refs(ml_.data_) > 1) {
542 // We must make it unique regardless; in-place reallocation is
543 // useless if the string is shared. In order to not surprise
544 // people, reserve the new block at current capacity or
545 // more. That way, a string's capacity never shrinks after a
547 minCapacity = std::max(minCapacity, ml_.capacity());
548 auto const newRC = RefCounted::create(& minCapacity);
549 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
551 // Done with the old data. No need to call writeTerminator(),
552 // we have + 1 above.
553 RefCounted::decrementRefs(ml_.data_);
554 ml_.data_ = newRC->data_;
555 ml_.capacity_ = minCapacity | isLarge;
556 // size remains unchanged
558 // String is not shared, so let's try to realloc (if needed)
559 if (minCapacity > ml_.capacity()) {
560 // Asking for more memory
562 RefCounted::reallocate(ml_.data_, ml_.size_,
563 ml_.capacity(), minCapacity);
564 ml_.data_ = newRC->data_;
565 ml_.capacity_ = minCapacity | isLarge;
568 assert(capacity() >= minCapacity);
570 } else if (category() == isMedium) {
571 // String is not shared
572 if (minCapacity <= ml_.capacity()) {
573 return; // nothing to do, there's enough room
575 if (minCapacity <= maxMediumSize) {
576 // Keep the string at medium size. Don't forget to allocate
577 // one extra Char for the terminating null.
578 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
579 ml_.data_ = static_cast<Char *>(
582 ml_.size_ * sizeof(Char),
583 (ml_.capacity() + 1) * sizeof(Char),
586 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
588 // Conversion from medium to large string
589 fbstring_core nascent;
590 // Will recurse to another branch of this function
591 nascent.reserve(minCapacity);
592 nascent.ml_.size_ = ml_.size_;
593 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
597 assert(capacity() >= minCapacity);
600 assert(category() == isSmall);
601 if (minCapacity > maxMediumSize) {
603 auto const newRC = RefCounted::create(& minCapacity);
604 auto const size = smallSize();
605 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
606 // No need for writeTerminator(), we wrote it above with + 1.
607 ml_.data_ = newRC->data_;
609 ml_.capacity_ = minCapacity | isLarge;
610 assert(capacity() >= minCapacity);
611 } else if (minCapacity > maxSmallSize) {
613 // Don't forget to allocate one extra Char for the terminating null
614 auto const allocSizeBytes =
615 goodMallocSize((1 + minCapacity) * sizeof(Char));
616 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
617 auto const size = smallSize();
618 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
619 // No need for writeTerminator(), we wrote it above with + 1.
622 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
625 // Nothing to do, everything stays put
628 assert(capacity() >= minCapacity);
631 Char * expand_noinit(const size_t delta) {
632 // Strategy is simple: make room, then change size
633 assert(capacity() >= size());
635 if (category() == isSmall) {
638 if (newSz <= maxSmallSize) {
645 newSz = ml_.size_ + delta;
646 if (newSz > capacity()) {
650 assert(capacity() >= newSz);
651 // Category can't be small - we took care of that above
652 assert(category() == isMedium || category() == isLarge);
655 assert(size() == newSz);
656 return ml_.data_ + sz;
659 void push_back(Char c) {
660 assert(capacity() >= size());
662 if (category() == isSmall) {
664 if (sz < maxSmallSize) {
666 setSmallSize(sz + 1);
669 reserve(maxSmallSize * 2);
672 if (sz == capacity()) { // always true for isShared()
673 reserve(1 + sz * 3 / 2); // ensures not shared
677 assert(capacity() >= sz + 1);
678 // Category can't be small - we took care of that above
679 assert(category() == isMedium || category() == isLarge);
685 size_t size() const {
686 return category() == isSmall ? smallSize() : ml_.size_;
689 size_t capacity() const {
690 switch (category()) {
694 // For large-sized strings, a multi-referenced chunk has no
695 // available capacity. This is because any attempt to append
696 // data would trigger a new allocation.
697 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
700 return ml_.capacity();
703 bool isShared() const {
704 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
707 void writeTerminator() {
708 if (category() == isSmall) {
709 const auto s = smallSize();
710 if (s != maxSmallSize) {
714 ml_.data_[ml_.size_] = '\0';
720 fbstring_core & operator=(const fbstring_core & rhs);
727 size_t capacity() const {
728 return capacity_ & capacityExtractMask;
733 std::atomic<size_t> refCount_;
736 static RefCounted * fromData(Char * p) {
737 return static_cast<RefCounted*>(
739 static_cast<unsigned char*>(static_cast<void*>(p))
740 - sizeof(refCount_)));
743 static size_t refs(Char * p) {
744 return fromData(p)->refCount_.load(std::memory_order_acquire);
747 static void incrementRefs(Char * p) {
748 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
751 static void decrementRefs(Char * p) {
752 auto const dis = fromData(p);
753 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
760 static RefCounted * create(size_t * size) {
761 // Don't forget to allocate one extra Char for the terminating
762 // null. In this case, however, one Char is already part of the
764 const size_t allocSize = goodMallocSize(
765 sizeof(RefCounted) + *size * sizeof(Char));
766 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
767 result->refCount_.store(1, std::memory_order_release);
768 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
772 static RefCounted * create(const Char * data, size_t * size) {
773 const size_t effectiveSize = *size;
774 auto result = create(size);
775 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
779 static RefCounted * reallocate(Char *const data,
780 const size_t currentSize,
781 const size_t currentCapacity,
782 const size_t newCapacity) {
783 assert(newCapacity > 0 && newCapacity > currentSize);
784 auto const dis = fromData(data);
785 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
786 // Don't forget to allocate one extra Char for the terminating
787 // null. In this case, however, one Char is already part of the
789 auto result = static_cast<RefCounted*>(
791 sizeof(RefCounted) + currentSize * sizeof(Char),
792 sizeof(RefCounted) + currentCapacity * sizeof(Char),
793 sizeof(RefCounted) + newCapacity * sizeof(Char)));
794 assert(result->refCount_.load(std::memory_order_acquire) == 1);
800 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
801 mutable MediumLarge ml_;
805 lastChar = sizeof(MediumLarge) - 1,
806 maxSmallSize = lastChar / sizeof(Char),
807 maxMediumSize = 254 / sizeof(Char), // coincides with the small
808 // bin size in dlmalloc
809 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
810 capacityExtractMask = ~categoryExtractMask,
812 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
813 "Corrupt memory layout for fbstring.");
817 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
818 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
821 Category category() const {
822 // Assumes little endian
823 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
826 size_t smallSize() const {
827 assert(category() == isSmall &&
828 static_cast<size_t>(small_[maxSmallSize])
829 <= static_cast<size_t>(maxSmallSize));
830 return static_cast<size_t>(maxSmallSize)
831 - static_cast<size_t>(small_[maxSmallSize]);
834 void setSmallSize(size_t s) {
835 // Warning: this should work with uninitialized strings too,
836 // so don't assume anything about the previous value of
837 // small_[maxSmallSize].
838 assert(s <= maxSmallSize);
839 small_[maxSmallSize] = maxSmallSize - s;
844 #if defined(__GNUC__) && !defined(__clang__)
845 # pragma GCC diagnostic pop
848 #ifndef _LIBSTDCXX_FBSTRING
850 * Dummy fbstring core that uses an actual std::string. This doesn't
851 * make any sense - it's just for testing purposes.
853 template <class Char>
854 class dummy_fbstring_core {
856 dummy_fbstring_core() {
858 dummy_fbstring_core(const dummy_fbstring_core& another)
859 : backend_(another.backend_) {
861 dummy_fbstring_core(const Char * s, size_t n)
864 void swap(dummy_fbstring_core & rhs) {
865 backend_.swap(rhs.backend_);
867 const Char * data() const {
868 return backend_.data();
870 Char * mutable_data() {
871 //assert(!backend_.empty());
872 return &*backend_.begin();
874 void shrink(size_t delta) {
875 assert(delta <= size());
876 backend_.resize(size() - delta);
878 Char * expand_noinit(size_t delta) {
879 auto const sz = size();
880 backend_.resize(size() + delta);
881 return backend_.data() + sz;
883 void push_back(Char c) {
884 backend_.push_back(c);
886 size_t size() const {
887 return backend_.size();
889 size_t capacity() const {
890 return backend_.capacity();
892 bool isShared() const {
895 void reserve(size_t minCapacity) {
896 backend_.reserve(minCapacity);
900 std::basic_string<Char> backend_;
902 #endif // !_LIBSTDCXX_FBSTRING
905 * This is the basic_string replacement. For conformity,
906 * basic_fbstring takes the same template parameters, plus the last
907 * one which is the core.
909 #ifdef _LIBSTDCXX_FBSTRING
910 template <typename E, class T, class A, class Storage>
912 template <typename E,
913 class T = std::char_traits<E>,
914 class A = std::allocator<E>,
915 class Storage = fbstring_core<E> >
917 class basic_fbstring {
921 void (*throw_exc)(const char*),
923 if (!condition) throw_exc(msg);
926 bool isSane() const {
929 empty() == (size() == 0) &&
930 empty() == (begin() == end()) &&
931 size() <= max_size() &&
932 capacity() <= max_size() &&
933 size() <= capacity() &&
934 begin()[size()] == '\0';
938 friend struct Invariant;
941 explicit Invariant(const basic_fbstring& s) : s_(s) {
948 const basic_fbstring& s_;
950 explicit Invariant(const basic_fbstring&) {}
952 Invariant& operator=(const Invariant&);
957 typedef T traits_type;
958 typedef typename traits_type::char_type value_type;
959 typedef A allocator_type;
960 typedef typename A::size_type size_type;
961 typedef typename A::difference_type difference_type;
963 typedef typename A::reference reference;
964 typedef typename A::const_reference const_reference;
965 typedef typename A::pointer pointer;
966 typedef typename A::const_pointer const_pointer;
969 typedef const E* const_iterator;
970 typedef std::reverse_iterator<iterator
971 #ifdef NO_ITERATOR_TRAITS
975 typedef std::reverse_iterator<const_iterator
976 #ifdef NO_ITERATOR_TRAITS
979 > const_reverse_iterator;
981 static const size_type npos; // = size_type(-1)
984 static void procrustes(size_type& n, size_type nmax) {
985 if (n > nmax) n = nmax;
989 // C++11 21.4.2 construct/copy/destroy
990 explicit basic_fbstring(const A& a = A()) noexcept {
993 basic_fbstring(const basic_fbstring& str)
994 : store_(str.store_) {
998 basic_fbstring(basic_fbstring&& goner) noexcept
999 : store_(std::move(goner.store_)) {
1002 #ifndef _LIBSTDCXX_FBSTRING
1003 // This is defined for compatibility with std::string
1004 /* implicit */ basic_fbstring(const std::string& str)
1005 : store_(str.data(), str.size()) {
1009 basic_fbstring(const basic_fbstring& str, size_type pos,
1010 size_type n = npos, const A& a = A()) {
1011 assign(str, pos, n);
1014 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1016 ? traits_type::length(s)
1018 std::__throw_logic_error(
1019 "basic_fbstring: null pointer initializer not valid");
1024 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1028 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1029 auto const data = store_.expand_noinit(n);
1030 fbstring_detail::pod_fill(data, data + n, c);
1031 store_.writeTerminator();
1034 template <class InIt>
1035 basic_fbstring(InIt begin, InIt end,
1036 typename std::enable_if<
1037 !std::is_same<typename std::remove_const<InIt>::type,
1038 value_type*>::value, const A>::type & a = A()) {
1042 // Specialization for const char*, const char*
1043 basic_fbstring(const value_type* b, const value_type* e)
1044 : store_(b, e - b) {
1047 // Nonstandard constructor
1048 basic_fbstring(value_type *s, size_type n, size_type c,
1049 AcquireMallocatedString a)
1050 : store_(s, n, c, a) {
1053 // Construction from initialization list
1054 basic_fbstring(std::initializer_list<value_type> il) {
1055 assign(il.begin(), il.end());
1058 ~basic_fbstring() noexcept {
1061 basic_fbstring& operator=(const basic_fbstring& lhs) {
1062 if (FBSTRING_UNLIKELY(&lhs == this)) {
1065 auto const oldSize = size();
1066 auto const srcSize = lhs.size();
1067 if (capacity() >= srcSize && !store_.isShared()) {
1068 // great, just copy the contents
1069 if (oldSize < srcSize)
1070 store_.expand_noinit(srcSize - oldSize);
1072 store_.shrink(oldSize - srcSize);
1073 assert(size() == srcSize);
1074 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1075 store_.writeTerminator();
1077 // need to reallocate, so we may as well create a brand new string
1078 basic_fbstring(lhs).swap(*this);
1084 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1085 if (FBSTRING_UNLIKELY(&goner == this)) {
1086 // Compatibility with std::basic_string<>,
1087 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1090 // No need of this anymore
1091 this->~basic_fbstring();
1092 // Move the goner into this
1093 new(&store_) fbstring_core<E>(std::move(goner.store_));
1097 #ifndef _LIBSTDCXX_FBSTRING
1098 // Compatibility with std::string
1099 basic_fbstring & operator=(const std::string & rhs) {
1100 return assign(rhs.data(), rhs.size());
1103 // Compatibility with std::string
1104 std::string toStdString() const {
1105 return std::string(data(), size());
1108 // A lot of code in fbcode still uses this method, so keep it here for now.
1109 const basic_fbstring& toStdString() const {
1114 basic_fbstring& operator=(const value_type* s) {
1118 basic_fbstring& operator=(value_type c) {
1120 store_.expand_noinit(1);
1121 } else if (store_.isShared()) {
1122 basic_fbstring(1, c).swap(*this);
1125 store_.shrink(size() - 1);
1127 *store_.mutable_data() = c;
1128 store_.writeTerminator();
1132 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1133 return assign(il.begin(), il.end());
1136 // C++11 21.4.3 iterators:
1137 iterator begin() { return store_.mutable_data(); }
1139 const_iterator begin() const { return store_.data(); }
1141 const_iterator cbegin() const { return begin(); }
1144 return store_.mutable_data() + store_.size();
1147 const_iterator end() const {
1148 return store_.data() + store_.size();
1151 const_iterator cend() const { return end(); }
1153 reverse_iterator rbegin() {
1154 return reverse_iterator(end());
1157 const_reverse_iterator rbegin() const {
1158 return const_reverse_iterator(end());
1161 const_reverse_iterator crbegin() const { return rbegin(); }
1163 reverse_iterator rend() {
1164 return reverse_iterator(begin());
1167 const_reverse_iterator rend() const {
1168 return const_reverse_iterator(begin());
1171 const_reverse_iterator crend() const { return rend(); }
1174 // C++11 21.4.5, element access:
1175 const value_type& front() const { return *begin(); }
1176 const value_type& back() const {
1178 // Should be begin()[size() - 1], but that branches twice
1179 return *(end() - 1);
1181 value_type& front() { return *begin(); }
1182 value_type& back() {
1184 // Should be begin()[size() - 1], but that branches twice
1185 return *(end() - 1);
1192 // C++11 21.4.4 capacity:
1193 size_type size() const { return store_.size(); }
1195 size_type length() const { return size(); }
1197 size_type max_size() const {
1198 return std::numeric_limits<size_type>::max();
1201 void resize(const size_type n, const value_type c = value_type()) {
1202 auto size = this->size();
1204 store_.shrink(size - n);
1206 // Do this in two steps to minimize slack memory copied (see
1208 auto const capacity = this->capacity();
1209 assert(capacity >= size);
1210 if (size < capacity) {
1211 auto delta = std::min(n, capacity) - size;
1212 store_.expand_noinit(delta);
1213 fbstring_detail::pod_fill(begin() + size, end(), c);
1216 store_.writeTerminator();
1221 auto const delta = n - size;
1222 store_.expand_noinit(delta);
1223 fbstring_detail::pod_fill(end() - delta, end(), c);
1224 store_.writeTerminator();
1226 assert(this->size() == n);
1229 size_type capacity() const { return store_.capacity(); }
1231 void reserve(size_type res_arg = 0) {
1232 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1233 store_.reserve(res_arg);
1236 void shrink_to_fit() {
1237 // Shrink only if slack memory is sufficiently large
1238 if (capacity() < size() * 3 / 2) {
1241 basic_fbstring(cbegin(), cend()).swap(*this);
1244 void clear() { resize(0); }
1246 bool empty() const { return size() == 0; }
1248 // C++11 21.4.5 element access:
1249 const_reference operator[](size_type pos) const {
1250 return *(c_str() + pos);
1253 reference operator[](size_type pos) {
1254 if (pos == size()) {
1255 // Just call c_str() to make sure '\0' is present
1258 return *(begin() + pos);
1261 const_reference at(size_type n) const {
1262 enforce(n <= size(), std::__throw_out_of_range, "");
1266 reference at(size_type n) {
1267 enforce(n < size(), std::__throw_out_of_range, "");
1271 // C++11 21.4.6 modifiers:
1272 basic_fbstring& operator+=(const basic_fbstring& str) {
1276 basic_fbstring& operator+=(const value_type* s) {
1280 basic_fbstring& operator+=(const value_type c) {
1285 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1290 basic_fbstring& append(const basic_fbstring& str) {
1292 auto desiredSize = size() + str.size();
1294 append(str.data(), str.size());
1295 assert(size() == desiredSize);
1299 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1301 const size_type sz = str.size();
1302 enforce(pos <= sz, std::__throw_out_of_range, "");
1303 procrustes(n, sz - pos);
1304 return append(str.data() + pos, n);
1307 basic_fbstring& append(const value_type* s, size_type n) {
1309 Invariant checker(*this);
1312 if (FBSTRING_UNLIKELY(!n)) {
1313 // Unlikely but must be done
1316 auto const oldSize = size();
1317 auto const oldData = data();
1318 // Check for aliasing (rare). We could use "<=" here but in theory
1319 // those do not work for pointers unless the pointers point to
1320 // elements in the same array. For that reason we use
1321 // std::less_equal, which is guaranteed to offer a total order
1322 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1324 std::less_equal<const value_type*> le;
1325 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1326 assert(le(s + n, oldData + oldSize));
1327 const size_type offset = s - oldData;
1328 store_.reserve(oldSize + n);
1329 // Restore the source
1330 s = data() + offset;
1332 // Warning! Repeated appends with short strings may actually incur
1333 // practically quadratic performance. Avoid that by pushing back
1334 // the first character (which ensures exponential growth) and then
1335 // appending the rest normally. Worst case the append may incur a
1336 // second allocation but that will be rare.
1339 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1340 assert(size() == oldSize + n + 1);
1344 basic_fbstring& append(const value_type* s) {
1345 return append(s, traits_type::length(s));
1348 basic_fbstring& append(size_type n, value_type c) {
1349 resize(size() + n, c);
1353 template<class InputIterator>
1354 basic_fbstring& append(InputIterator first, InputIterator last) {
1355 insert(end(), first, last);
1359 basic_fbstring& append(std::initializer_list<value_type> il) {
1360 return append(il.begin(), il.end());
1363 void push_back(const value_type c) { // primitive
1364 store_.push_back(c);
1367 basic_fbstring& assign(const basic_fbstring& str) {
1368 if (&str == this) return *this;
1369 return assign(str.data(), str.size());
1372 basic_fbstring& assign(basic_fbstring&& str) {
1373 return *this = std::move(str);
1376 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1378 const size_type sz = str.size();
1379 enforce(pos <= sz, std::__throw_out_of_range, "");
1380 procrustes(n, sz - pos);
1381 return assign(str.data() + pos, n);
1384 basic_fbstring& assign(const value_type* s, const size_type n) {
1385 Invariant checker(*this);
1388 std::copy(s, s + n, begin());
1390 assert(size() == n);
1392 const value_type *const s2 = s + size();
1393 std::copy(s, s2, begin());
1394 append(s2, n - size());
1395 assert(size() == n);
1397 store_.writeTerminator();
1398 assert(size() == n);
1402 basic_fbstring& assign(const value_type* s) {
1403 return assign(s, traits_type::length(s));
1406 basic_fbstring& assign(std::initializer_list<value_type> il) {
1407 return assign(il.begin(), il.end());
1410 template <class ItOrLength, class ItOrChar>
1411 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1412 return replace(begin(), end(), first_or_n, last_or_c);
1415 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1416 return insert(pos1, str.data(), str.size());
1419 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1420 size_type pos2, size_type n) {
1421 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1422 procrustes(n, str.length() - pos2);
1423 return insert(pos1, str.data() + pos2, n);
1426 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1427 enforce(pos <= length(), std::__throw_out_of_range, "");
1428 insert(begin() + pos, s, s + n);
1432 basic_fbstring& insert(size_type pos, const value_type* s) {
1433 return insert(pos, s, traits_type::length(s));
1436 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1437 enforce(pos <= length(), std::__throw_out_of_range, "");
1438 insert(begin() + pos, n, c);
1442 iterator insert(const_iterator p, const value_type c) {
1443 const size_type pos = p - begin();
1445 return begin() + pos;
1449 template <int i> class Selector {};
1451 iterator insertImplDiscr(const_iterator p,
1452 size_type n, value_type c, Selector<1>) {
1453 Invariant checker(*this);
1455 auto const pos = p - begin();
1456 assert(p >= begin() && p <= end());
1457 if (capacity() - size() < n) {
1458 const size_type sz = p - begin();
1459 reserve(size() + n);
1462 const iterator oldEnd = end();
1463 if (n < size_type(oldEnd - p)) {
1464 append(oldEnd - n, oldEnd);
1466 // reverse_iterator(oldEnd - n),
1467 // reverse_iterator(p),
1468 // reverse_iterator(oldEnd));
1469 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1471 std::fill(begin() + pos, begin() + pos + n, c);
1473 append(n - (end() - p), c);
1474 append(iterator(p), oldEnd);
1475 std::fill(iterator(p), oldEnd, c);
1477 store_.writeTerminator();
1478 return begin() + pos;
1481 template<class InputIter>
1482 iterator insertImplDiscr(const_iterator i,
1483 InputIter b, InputIter e, Selector<0>) {
1484 return insertImpl(i, b, e,
1485 typename std::iterator_traits<InputIter>::iterator_category());
1488 template <class FwdIterator>
1489 iterator insertImpl(const_iterator i,
1490 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1491 Invariant checker(*this);
1493 const size_type pos = i - begin();
1494 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1495 std::distance(s1, s2);
1497 using namespace fbstring_detail;
1498 assert(pos <= size());
1500 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1501 capacity() - size();
1503 // realloc the string
1504 reserve(size() + n2);
1507 if (pos + n2 <= size()) {
1508 const iterator tailBegin = end() - n2;
1509 store_.expand_noinit(n2);
1510 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1511 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1512 reverse_iterator(tailBegin + n2));
1513 std::copy(s1, s2, begin() + pos);
1516 const size_type old_size = size();
1517 std::advance(t, old_size - pos);
1518 const size_t newElems = std::distance(t, s2);
1519 store_.expand_noinit(n2);
1520 std::copy(t, s2, begin() + old_size);
1521 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1522 begin() + old_size + newElems);
1523 std::copy(s1, t, begin() + pos);
1525 store_.writeTerminator();
1526 return begin() + pos;
1529 template <class InputIterator>
1530 iterator insertImpl(const_iterator i,
1531 InputIterator b, InputIterator e,
1532 std::input_iterator_tag) {
1533 const auto pos = i - begin();
1534 basic_fbstring temp(begin(), i);
1535 for (; b != e; ++b) {
1538 temp.append(i, cend());
1540 return begin() + pos;
1544 template <class ItOrLength, class ItOrChar>
1545 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1546 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1547 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1550 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1551 return insert(p, il.begin(), il.end());
1554 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1555 Invariant checker(*this);
1557 enforce(pos <= length(), std::__throw_out_of_range, "");
1558 procrustes(n, length() - pos);
1559 std::copy(begin() + pos + n, end(), begin() + pos);
1560 resize(length() - n);
1564 iterator erase(iterator position) {
1565 const size_type pos(position - begin());
1566 enforce(pos <= size(), std::__throw_out_of_range, "");
1568 return begin() + pos;
1571 iterator erase(iterator first, iterator last) {
1572 const size_type pos(first - begin());
1573 erase(pos, last - first);
1574 return begin() + pos;
1577 // Replaces at most n1 chars of *this, starting with pos1 with the
1579 basic_fbstring& replace(size_type pos1, size_type n1,
1580 const basic_fbstring& str) {
1581 return replace(pos1, n1, str.data(), str.size());
1584 // Replaces at most n1 chars of *this, starting with pos1,
1585 // with at most n2 chars of str starting with pos2
1586 basic_fbstring& replace(size_type pos1, size_type n1,
1587 const basic_fbstring& str,
1588 size_type pos2, size_type n2) {
1589 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1590 return replace(pos1, n1, str.data() + pos2,
1591 std::min(n2, str.size() - pos2));
1594 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1595 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1596 return replace(pos, n1, s, traits_type::length(s));
1599 // Replaces at most n1 chars of *this, starting with pos, with n2
1602 // consolidated with
1604 // Replaces at most n1 chars of *this, starting with pos, with at
1605 // most n2 chars of str. str must have at least n2 chars.
1606 template <class StrOrLength, class NumOrChar>
1607 basic_fbstring& replace(size_type pos, size_type n1,
1608 StrOrLength s_or_n2, NumOrChar n_or_c) {
1609 Invariant checker(*this);
1611 enforce(pos <= size(), std::__throw_out_of_range, "");
1612 procrustes(n1, length() - pos);
1613 const iterator b = begin() + pos;
1614 return replace(b, b + n1, s_or_n2, n_or_c);
1617 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1618 return replace(i1, i2, str.data(), str.length());
1621 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1622 return replace(i1, i2, s, traits_type::length(s));
1626 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1627 const value_type* s, size_type n,
1630 assert(begin() <= i1 && i1 <= end());
1631 assert(begin() <= i2 && i2 <= end());
1632 return replace(i1, i2, s, s + n);
1635 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1636 size_type n2, value_type c, Selector<1>) {
1637 const size_type n1 = i2 - i1;
1639 std::fill(i1, i1 + n2, c);
1642 std::fill(i1, i2, c);
1643 insert(i2, n2 - n1, c);
1649 template <class InputIter>
1650 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1651 InputIter b, InputIter e,
1653 replaceImpl(i1, i2, b, e,
1654 typename std::iterator_traits<InputIter>::iterator_category());
1659 template <class FwdIterator>
1660 bool replaceAliased(iterator i1, iterator i2,
1661 FwdIterator s1, FwdIterator s2, std::false_type) {
1665 template <class FwdIterator>
1666 bool replaceAliased(iterator i1, iterator i2,
1667 FwdIterator s1, FwdIterator s2, std::true_type) {
1668 static const std::less_equal<const value_type*> le =
1669 std::less_equal<const value_type*>();
1670 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1674 // Aliased replace, copy to new string
1675 basic_fbstring temp;
1676 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1677 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1682 template <class FwdIterator>
1683 void replaceImpl(iterator i1, iterator i2,
1684 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1685 Invariant checker(*this);
1688 // Handle aliased replace
1689 if (replaceAliased(i1, i2, s1, s2,
1690 std::integral_constant<bool,
1691 std::is_same<FwdIterator, iterator>::value ||
1692 std::is_same<FwdIterator, const_iterator>::value>())) {
1696 auto const n1 = i2 - i1;
1698 auto const n2 = std::distance(s1, s2);
1703 std::copy(s1, s2, i1);
1707 fbstring_detail::copy_n(s1, n1, i1);
1708 std::advance(s1, n1);
1714 template <class InputIterator>
1715 void replaceImpl(iterator i1, iterator i2,
1716 InputIterator b, InputIterator e, std::input_iterator_tag) {
1717 basic_fbstring temp(begin(), i1);
1718 temp.append(b, e).append(i2, end());
1723 template <class T1, class T2>
1724 basic_fbstring& replace(iterator i1, iterator i2,
1725 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1727 num1 = std::numeric_limits<T1>::is_specialized,
1728 num2 = std::numeric_limits<T2>::is_specialized;
1729 return replaceImplDiscr(
1730 i1, i2, first_or_n_or_s, last_or_c_or_n,
1731 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1734 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1735 enforce(pos <= size(), std::__throw_out_of_range, "");
1736 procrustes(n, size() - pos);
1738 fbstring_detail::pod_copy(
1745 void swap(basic_fbstring& rhs) {
1746 store_.swap(rhs.store_);
1749 const value_type* c_str() const {
1750 return store_.c_str();
1753 const value_type* data() const { return c_str(); }
1755 allocator_type get_allocator() const {
1756 return allocator_type();
1759 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1760 return find(str.data(), pos, str.length());
1763 size_type find(const value_type* needle, const size_type pos,
1764 const size_type nsize) const {
1765 if (!nsize) return pos;
1766 auto const size = this->size();
1767 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1768 // that nsize + pos does not wrap around.
1769 if (nsize + pos > size || nsize + pos < pos) return npos;
1770 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1771 // the last characters first
1772 auto const haystack = data();
1773 auto const nsize_1 = nsize - 1;
1774 auto const lastNeedle = needle[nsize_1];
1776 // Boyer-Moore skip value for the last char in the needle. Zero is
1777 // not a valid value; skip will be computed the first time it's
1781 const E * i = haystack + pos;
1782 auto iEnd = haystack + size - nsize_1;
1785 // Boyer-Moore: match the last element in the needle
1786 while (i[nsize_1] != lastNeedle) {
1792 // Here we know that the last char matches
1793 // Continue in pedestrian mode
1794 for (size_t j = 0; ; ) {
1796 if (i[j] != needle[j]) {
1797 // Not found, we can skip
1798 // Compute the skip value lazily
1801 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1808 // Check if done searching
1811 return i - haystack;
1818 size_type find(const value_type* s, size_type pos = 0) const {
1819 return find(s, pos, traits_type::length(s));
1822 size_type find (value_type c, size_type pos = 0) const {
1823 return find(&c, pos, 1);
1826 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1827 return rfind(str.data(), pos, str.length());
1830 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1831 if (n > length()) return npos;
1832 pos = std::min(pos, length() - n);
1833 if (n == 0) return pos;
1835 const_iterator i(begin() + pos);
1837 if (traits_type::eq(*i, *s)
1838 && traits_type::compare(&*i, s, n) == 0) {
1841 if (i == begin()) break;
1846 size_type rfind(const value_type* s, size_type pos = npos) const {
1847 return rfind(s, pos, traits_type::length(s));
1850 size_type rfind(value_type c, size_type pos = npos) const {
1851 return rfind(&c, pos, 1);
1854 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1855 return find_first_of(str.data(), pos, str.length());
1858 size_type find_first_of(const value_type* s,
1859 size_type pos, size_type n) const {
1860 if (pos > length() || n == 0) return npos;
1861 const_iterator i(begin() + pos),
1863 for (; i != finish; ++i) {
1864 if (traits_type::find(s, n, *i) != 0) {
1871 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1872 return find_first_of(s, pos, traits_type::length(s));
1875 size_type find_first_of(value_type c, size_type pos = 0) const {
1876 return find_first_of(&c, pos, 1);
1879 size_type find_last_of (const basic_fbstring& str,
1880 size_type pos = npos) const {
1881 return find_last_of(str.data(), pos, str.length());
1884 size_type find_last_of (const value_type* s, size_type pos,
1885 size_type n) const {
1886 if (!empty() && n > 0) {
1887 pos = std::min(pos, length() - 1);
1888 const_iterator i(begin() + pos);
1890 if (traits_type::find(s, n, *i) != 0) {
1893 if (i == begin()) break;
1899 size_type find_last_of (const value_type* s,
1900 size_type pos = npos) const {
1901 return find_last_of(s, pos, traits_type::length(s));
1904 size_type find_last_of (value_type c, size_type pos = npos) const {
1905 return find_last_of(&c, pos, 1);
1908 size_type find_first_not_of(const basic_fbstring& str,
1909 size_type pos = 0) const {
1910 return find_first_not_of(str.data(), pos, str.size());
1913 size_type find_first_not_of(const value_type* s, size_type pos,
1914 size_type n) const {
1915 if (pos < length()) {
1919 for (; i != finish; ++i) {
1920 if (traits_type::find(s, n, *i) == 0) {
1928 size_type find_first_not_of(const value_type* s,
1929 size_type pos = 0) const {
1930 return find_first_not_of(s, pos, traits_type::length(s));
1933 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1934 return find_first_not_of(&c, pos, 1);
1937 size_type find_last_not_of(const basic_fbstring& str,
1938 size_type pos = npos) const {
1939 return find_last_not_of(str.data(), pos, str.length());
1942 size_type find_last_not_of(const value_type* s, size_type pos,
1943 size_type n) const {
1944 if (!this->empty()) {
1945 pos = std::min(pos, size() - 1);
1946 const_iterator i(begin() + pos);
1948 if (traits_type::find(s, n, *i) == 0) {
1951 if (i == begin()) break;
1957 size_type find_last_not_of(const value_type* s,
1958 size_type pos = npos) const {
1959 return find_last_not_of(s, pos, traits_type::length(s));
1962 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1963 return find_last_not_of(&c, pos, 1);
1966 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1967 enforce(pos <= size(), std::__throw_out_of_range, "");
1968 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1971 int compare(const basic_fbstring& str) const {
1972 // FIX due to Goncalo N M de Carvalho July 18, 2005
1973 return compare(0, size(), str);
1976 int compare(size_type pos1, size_type n1,
1977 const basic_fbstring& str) const {
1978 return compare(pos1, n1, str.data(), str.size());
1981 int compare(size_type pos1, size_type n1,
1982 const value_type* s) const {
1983 return compare(pos1, n1, s, traits_type::length(s));
1986 int compare(size_type pos1, size_type n1,
1987 const value_type* s, size_type n2) const {
1988 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1989 procrustes(n1, size() - pos1);
1990 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1991 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1992 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1995 int compare(size_type pos1, size_type n1,
1996 const basic_fbstring& str,
1997 size_type pos2, size_type n2) const {
1998 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1999 return compare(pos1, n1, str.data() + pos2,
2000 std::min(n2, str.size() - pos2));
2003 // Code from Jean-Francois Bastien (03/26/2007)
2004 int compare(const value_type* s) const {
2005 // Could forward to compare(0, size(), s, traits_type::length(s))
2006 // but that does two extra checks
2007 const size_type n1(size()), n2(traits_type::length(s));
2008 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2009 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2017 // non-member functions
2019 template <typename E, class T, class A, class S>
2021 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2022 const basic_fbstring<E, T, A, S>& rhs) {
2024 basic_fbstring<E, T, A, S> result;
2025 result.reserve(lhs.size() + rhs.size());
2026 result.append(lhs).append(rhs);
2027 return std::move(result);
2031 template <typename E, class T, class A, class S>
2033 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2034 const basic_fbstring<E, T, A, S>& rhs) {
2035 return std::move(lhs.append(rhs));
2039 template <typename E, class T, class A, class S>
2041 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2042 basic_fbstring<E, T, A, S>&& rhs) {
2043 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2044 // Good, at least we don't need to reallocate
2045 return std::move(rhs.insert(0, lhs));
2047 // Meh, no go. Forward to operator+(const&, const&).
2048 auto const& rhsC = rhs;
2053 template <typename E, class T, class A, class S>
2055 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2056 basic_fbstring<E, T, A, S>&& rhs) {
2057 return std::move(lhs.append(rhs));
2060 template <typename E, class T, class A, class S>
2062 basic_fbstring<E, T, A, S> operator+(
2063 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2064 const basic_fbstring<E, T, A, S>& rhs) {
2066 basic_fbstring<E, T, A, S> result;
2067 const typename basic_fbstring<E, T, A, S>::size_type len =
2068 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2069 result.reserve(len + rhs.size());
2070 result.append(lhs, len).append(rhs);
2074 template <typename E, class T, class A, class S>
2076 basic_fbstring<E, T, A, S> operator+(
2077 typename basic_fbstring<E, T, A, S>::value_type lhs,
2078 const basic_fbstring<E, T, A, S>& rhs) {
2080 basic_fbstring<E, T, A, S> result;
2081 result.reserve(1 + rhs.size());
2082 result.push_back(lhs);
2087 template <typename E, class T, class A, class S>
2089 basic_fbstring<E, T, A, S> operator+(
2090 const basic_fbstring<E, T, A, S>& lhs,
2091 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2093 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2094 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2096 basic_fbstring<E, T, A, S> result;
2097 const size_type len = traits_type::length(rhs);
2098 result.reserve(lhs.size() + len);
2099 result.append(lhs).append(rhs, len);
2103 template <typename E, class T, class A, class S>
2105 basic_fbstring<E, T, A, S> operator+(
2106 const basic_fbstring<E, T, A, S>& lhs,
2107 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2109 basic_fbstring<E, T, A, S> result;
2110 result.reserve(lhs.size() + 1);
2112 result.push_back(rhs);
2116 template <typename E, class T, class A, class S>
2118 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2119 const basic_fbstring<E, T, A, S>& rhs) {
2120 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2122 template <typename E, class T, class A, class S>
2124 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2125 const basic_fbstring<E, T, A, S>& rhs) {
2126 return rhs == lhs; }
2128 template <typename E, class T, class A, class S>
2130 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2131 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2132 return lhs.compare(rhs) == 0; }
2134 template <typename E, class T, class A, class S>
2136 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2137 const basic_fbstring<E, T, A, S>& rhs) {
2138 return !(lhs == rhs); }
2140 template <typename E, class T, class A, class S>
2142 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2143 const basic_fbstring<E, T, A, S>& rhs) {
2144 return !(lhs == rhs); }
2146 template <typename E, class T, class A, class S>
2148 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2149 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2150 return !(lhs == rhs); }
2152 template <typename E, class T, class A, class S>
2154 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2155 const basic_fbstring<E, T, A, S>& rhs) {
2156 return lhs.compare(rhs) < 0; }
2158 template <typename E, class T, class A, class S>
2160 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2161 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2162 return lhs.compare(rhs) < 0; }
2164 template <typename E, class T, class A, class S>
2166 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2167 const basic_fbstring<E, T, A, S>& rhs) {
2168 return rhs.compare(lhs) > 0; }
2170 template <typename E, class T, class A, class S>
2172 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2173 const basic_fbstring<E, T, A, S>& rhs) {
2176 template <typename E, class T, class A, class S>
2178 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2179 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2182 template <typename E, class T, class A, class S>
2184 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2185 const basic_fbstring<E, T, A, S>& rhs) {
2188 template <typename E, class T, class A, class S>
2190 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2191 const basic_fbstring<E, T, A, S>& rhs) {
2192 return !(rhs < lhs); }
2194 template <typename E, class T, class A, class S>
2196 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2197 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2198 return !(rhs < lhs); }
2200 template <typename E, class T, class A, class S>
2202 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2203 const basic_fbstring<E, T, A, S>& rhs) {
2204 return !(rhs < lhs); }
2206 template <typename E, class T, class A, class S>
2208 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2209 const basic_fbstring<E, T, A, S>& rhs) {
2210 return !(lhs < rhs); }
2212 template <typename E, class T, class A, class S>
2214 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2215 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2216 return !(lhs < rhs); }
2218 template <typename E, class T, class A, class S>
2220 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2221 const basic_fbstring<E, T, A, S>& rhs) {
2222 return !(lhs < rhs);
2226 template <typename E, class T, class A, class S>
2227 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2231 // TODO: make this faster.
2232 template <typename E, class T, class A, class S>
2235 typename basic_fbstring<E, T, A, S>::value_type,
2236 typename basic_fbstring<E, T, A, S>::traits_type>&
2238 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2239 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2240 basic_fbstring<E, T, A, S>& str) {
2241 typename std::basic_istream<E, T>::sentry sentry(is);
2242 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2243 typename basic_fbstring<E, T, A, S>::traits_type>
2245 typedef typename __istream_type::ios_base __ios_base;
2246 size_t extracted = 0;
2247 auto err = __ios_base::goodbit;
2249 auto n = is.width();
2254 auto got = is.rdbuf()->sgetc();
2255 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2256 // Whew. We get to store this guy
2258 got = is.rdbuf()->snextc();
2260 if (got == T::eof()) {
2261 err |= __ios_base::eofbit;
2266 err |= __ios_base::failbit;
2274 template <typename E, class T, class A, class S>
2276 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2277 typename basic_fbstring<E, T, A, S>::traits_type>&
2279 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2280 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2281 const basic_fbstring<E, T, A, S>& str) {
2283 typename std::basic_ostream<
2284 typename basic_fbstring<E, T, A, S>::value_type,
2285 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2287 typedef std::ostreambuf_iterator<
2288 typename basic_fbstring<E, T, A, S>::value_type,
2289 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2290 size_t __len = str.size();
2292 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2293 if (__pad_and_output(_Ip(os),
2295 __left ? str.data() + __len : str.data(),
2298 os.fill()).failed()) {
2299 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2303 std::__ostream_insert(os, str.data(), str.size());
2308 #ifndef _LIBSTDCXX_FBSTRING
2310 template <typename E, class T, class A, class S>
2312 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2313 typename basic_fbstring<E, T, A, S>::traits_type>&
2315 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2316 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2317 basic_fbstring<E, T, A, S>& str,
2318 typename basic_fbstring<E, T, A, S>::value_type delim) {
2319 // Use the nonstandard getdelim()
2320 char * buf = nullptr;
2323 // This looks quadratic but it really depends on realloc
2324 auto const newSize = size + 128;
2325 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2326 is.getline(buf + size, newSize - size, delim);
2327 if (is.bad() || is.eof() || !is.fail()) {
2328 // done by either failure, end of file, or normal read
2329 size += std::strlen(buf + size);
2332 // Here we have failed due to too short a buffer
2333 // Minus one to discount the terminating '\0'
2335 assert(buf[size] == 0);
2336 // Clear the error so we can continue reading
2339 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2340 AcquireMallocatedString());
2345 template <typename E, class T, class A, class S>
2347 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2348 typename basic_fbstring<E, T, A, S>::traits_type>&
2350 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2351 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2352 basic_fbstring<E, T, A, S>& str) {
2353 // Just forward to the version with a delimiter
2354 return getline(is, str, '\n');
2359 template <typename E1, class T, class A, class S>
2360 const typename basic_fbstring<E1, T, A, S>::size_type
2361 basic_fbstring<E1, T, A, S>::npos =
2362 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2364 #ifndef _LIBSTDCXX_FBSTRING
2365 // basic_string compatibility routines
2367 template <typename E, class T, class A, class S>
2369 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2370 const std::string& rhs) {
2371 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2374 template <typename E, class T, class A, class S>
2376 bool operator==(const std::string& lhs,
2377 const basic_fbstring<E, T, A, S>& rhs) {
2381 template <typename E, class T, class A, class S>
2383 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2384 const std::string& rhs) {
2385 return !(lhs == rhs);
2388 template <typename E, class T, class A, class S>
2390 bool operator!=(const std::string& lhs,
2391 const basic_fbstring<E, T, A, S>& rhs) {
2392 return !(lhs == rhs);
2395 #if !defined(_LIBSTDCXX_FBSTRING)
2396 typedef basic_fbstring<char> fbstring;
2399 // fbstring is relocatable
2400 template <class T, class R, class A, class S>
2401 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2404 _GLIBCXX_END_NAMESPACE_VERSION
2407 } // namespace folly
2409 #ifndef _LIBSTDCXX_FBSTRING
2411 // Hash functions to make fbstring usable with e.g. hash_map
2413 // Handle interaction with different C++ standard libraries, which
2414 // expect these types to be in different namespaces.
2418 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2419 size_t operator()(const folly::basic_fbstring<C> & s) const {
2420 return hash<const C*>::operator()(s.c_str());
2425 struct hash< ::folly::fbstring> {
2426 size_t operator()(const ::folly::fbstring& s) const {
2427 return ::folly::hash::fnv32_buf(s.data(), s.size());
2433 #if FOLLY_HAVE_DEPRECATED_ASSOC
2434 #if defined(_GLIBCXX_SYMVER) && !defined(__BIONIC__)
2435 namespace __gnu_cxx {
2438 struct hash<folly::basic_fbstring<C> > : private hash<const C*> {
2439 size_t operator()(const folly::basic_fbstring<C> & s) const {
2440 return hash<const C*>::operator()(s.c_str());
2445 struct hash< ::folly::fbstring> {
2446 size_t operator()(const ::folly::fbstring& s) const {
2447 return ::folly::hash::fnv32_buf(s.data(), s.size());
2452 #endif // _GLIBCXX_SYMVER && !__BIONIC__
2453 #endif // FOLLY_HAVE_DEPRECATED_ASSOC
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_