2 * Copyright 2013 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_
24 fbstring's behavior can be configured via two macro definitions, as
25 follows. Normally, fbstring does not write a '\0' at the end of
26 each string whenever it changes the underlying characters. Instead,
27 it lazily writes the '\0' whenever either c_str() or data()
30 This is standard-compliant behavior and may save costs in some
31 circumstances. However, it may be surprising to some client code
32 because c_str() and data() are const member functions (fbstring
33 uses the "mutable" storage class for its own state).
35 In order to appease client code that expects fbstring to be
36 zero-terminated at all times, if the preprocessor symbol
37 FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
38 i.e. it goes the extra mile to guarantee a '\0' is always planted
39 at the end of its data.
41 On the contrary, if the desire is to debug faulty client code that
42 unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
43 emphatically NOT a zero) at the end of each string if
44 FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
45 writes the '\0', of course.)
47 The preprocessor symbols FBSTRING_PERVERSE and
48 FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
49 enforced during preprocessing.
52 //#define FBSTRING_PERVERSE
53 //#define FBSTRING_CONSERVATIVE
55 #ifdef FBSTRING_PERVERSE
56 #ifdef FBSTRING_CONSERVATIVE
57 #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
61 // This file appears in two locations: inside fbcode and in the
62 // libstdc++ source code (when embedding fbstring as std::string).
63 // To aid in this schizophrenic use, two macros are defined in
65 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
66 // gate use inside fbcode v. libstdc++
67 #include <bits/c++config.h>
69 #ifdef _LIBSTDCXX_FBSTRING
71 #pragma GCC system_header
73 // Handle the cases where the fbcode version (folly/Malloc.h) is included
74 // either before or after this inclusion.
75 #ifdef FOLLY_MALLOC_H_
76 #undef FOLLY_MALLOC_H_
77 #include "basic_fbstring_malloc.h"
79 #include "basic_fbstring_malloc.h"
80 #undef FOLLY_MALLOC_H_
83 #else // !_LIBSTDCXX_FBSTRING
89 #include "folly/Traits.h"
90 #include "folly/Malloc.h"
91 #include "folly/Hash.h"
95 // We defined these here rather than including Likely.h to avoid
96 // redefinition errors when fbstring is imported into libstdc++.
97 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
98 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
102 #include <type_traits>
104 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
105 #pragma GCC diagnostic push
106 #pragma GCC diagnostic ignored "-Wshadow"
108 #ifdef _LIBSTDCXX_FBSTRING
109 namespace std _GLIBCXX_VISIBILITY(default) {
110 _GLIBCXX_BEGIN_NAMESPACE_VERSION
115 // Different versions of gcc/clang support different versions of
116 // the address sanitizer attribute. Unfortunately, this attribute
117 // has issues when inlining is used, so disable that as well.
118 #if defined(__clang__)
119 # if __has_feature(address_sanitizer)
120 # if __has_attribute(__no_address_safety_analysis__)
121 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
122 __attribute__((__no_address_safety_analysis__, __noinline__))
123 # elif __has_attribute(__no_sanitize_address__)
124 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
125 __attribute__((__no_sanitize_address__, __noinline__))
128 #elif defined (__GNUC__) && \
130 (__GNUC_MINOR__ >= 8) && \
132 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
133 __attribute__((__no_address_safety_analysis__, __noinline__))
135 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
136 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
139 namespace fbstring_detail {
141 template <class InIt, class OutIt>
144 typename std::iterator_traits<InIt>::difference_type n,
146 for (; n != 0; --n, ++b, ++d) {
147 assert((const void*)&*d != &*b);
153 template <class Pod, class T>
154 inline void pod_fill(Pod* b, Pod* e, T c) {
155 assert(b && e && b <= e);
156 /*static*/ if (sizeof(T) == 1) {
159 auto const ee = b + ((e - b) & ~7u);
160 for (; b != ee; b += 8) {
171 for (; b != e; ++b) {
178 * Lightly structured memcpy, simplifies copying PODs and introduces
179 * some asserts. Unfortunately using this function may cause
180 * measurable overhead (presumably because it adjusts from a begin/end
181 * convention to a pointer/size convention, so it does some extra
182 * arithmetic even though the caller might have done the inverse
183 * adaptation outside).
186 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
188 assert(d >= e || d + (e - b) <= b);
189 memcpy(d, b, (e - b) * sizeof(Pod));
193 * Lightly structured memmove, simplifies copying PODs and introduces
197 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
199 memmove(d, b, (e - b) * sizeof(*b));
202 } // namespace fbstring_detail
205 * Defines a special acquisition method for constructing fbstring
206 * objects. AcquireMallocatedString means that the user passes a
207 * pointer to a malloc-allocated string that the fbstring object will
210 enum class AcquireMallocatedString {};
213 * fbstring_core_model is a mock-up type that defines all required
214 * signatures of a fbstring core. The fbstring class itself uses such
215 * a core object to implement all of the numerous member functions
216 * required by the standard.
218 * If you want to define a new core, copy the definition below and
219 * implement the primitives. Then plug the core into basic_fbstring as
220 * a template argument.
222 template <class Char>
223 class fbstring_core_model {
225 fbstring_core_model();
226 fbstring_core_model(const fbstring_core_model &);
227 ~fbstring_core_model();
228 // Returns a pointer to string's buffer (currently only contiguous
229 // strings are supported). The pointer is guaranteed to be valid
230 // until the next call to a non-const member function.
231 const Char * data() const;
232 // Much like data(), except the string is prepared to support
233 // character-level changes. This call is a signal for
234 // e.g. reference-counted implementation to fork the data. The
235 // pointer is guaranteed to be valid until the next call to a
236 // non-const member function.
237 Char * mutable_data();
238 // Returns a pointer to string's buffer and guarantees that a
239 // readable '\0' lies right after the buffer. The pointer is
240 // guaranteed to be valid until the next call to a non-const member
242 const Char * c_str() const;
243 // Shrinks the string by delta characters. Asserts that delta <=
245 void shrink(size_t delta);
246 // Expands the string by delta characters (i.e. after this call
247 // size() will report the old size() plus delta) but without
248 // initializing the expanded region. Returns a pointer to the memory
249 // to be initialized (the beginning of the expanded portion). The
250 // caller is expected to fill the expanded area appropriately.
251 Char* expand_noinit(size_t delta);
252 // Expands the string by one character and sets the last character
254 void push_back(Char c);
255 // Returns the string's size.
257 // Returns the string's capacity, i.e. maximum size that the string
258 // can grow to without reallocation. Note that for reference counted
259 // strings that's technically a lie - even assigning characters
260 // within the existing size would cause a reallocation.
261 size_t capacity() const;
262 // Returns true if the data underlying the string is actually shared
263 // across multiple strings (in a refcounted fashion).
264 bool isShared() const;
265 // Makes sure that at least minCapacity characters are available for
266 // the string without reallocation. For reference-counted strings,
267 // it should fork the data even if minCapacity < size().
268 void reserve(size_t minCapacity);
271 fbstring_core_model& operator=(const fbstring_core_model &);
276 * gcc-4.7 throws what appears to be some false positive uninitialized
277 * warnings for the members of the MediumLarge struct. So, mute them here.
279 #if defined(__GNUC__) && !defined(__clang__)
280 # pragma GCC diagnostic push
281 # pragma GCC diagnostic ignored "-Wuninitialized"
285 * This is the core of the string. The code should work on 32- and
286 * 64-bit architectures and with any Char size. Porting to big endian
287 * architectures would require some changes.
289 * The storage is selected as follows (assuming we store one-byte
290 * characters on a 64-bit machine): (a) "small" strings between 0 and
291 * 23 chars are stored in-situ without allocation (the rightmost byte
292 * stores the size); (b) "medium" strings from 24 through 254 chars
293 * are stored in malloc-allocated memory that is copied eagerly; (c)
294 * "large" strings of 255 chars and above are stored in a similar
295 * structure as medium arrays, except that the string is
296 * reference-counted and copied lazily. the reference count is
297 * allocated right before the character array.
299 * The discriminator between these three strategies sits in the two
300 * most significant bits of the rightmost char of the storage. If
301 * neither is set, then the string is small (and its length sits in
302 * the lower-order bits of that rightmost character). If the MSb is
303 * set, the string is medium width. If the second MSb is set, then the
306 template <class Char> class fbstring_core {
309 // Only initialize the tag, will set the MSBs (i.e. the small
310 // string size) to zero too
311 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
312 // or: setSmallSize(0);
314 assert(category() == isSmall && size() == 0);
317 fbstring_core(const fbstring_core & rhs) {
318 assert(&rhs != this);
319 // Simplest case first: small strings are bitblitted
320 if (rhs.category() == isSmall) {
321 assert(offsetof(MediumLarge, data_) == 0);
322 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
323 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
324 const size_t size = rhs.smallSize();
326 ml_.capacity_ = rhs.ml_.capacity_;
329 // Just write the whole thing, don't look at details. In
330 // particular we need to copy capacity anyway because we want
331 // to set the size (don't forget that the last character,
332 // which stores a short string's length, is shared with the
333 // ml_.capacity field).
336 assert(category() == isSmall && this->size() == rhs.size());
337 } else if (rhs.category() == isLarge) {
338 // Large strings are just refcounted
340 RefCounted::incrementRefs(ml_.data_);
341 assert(category() == isLarge && size() == rhs.size());
343 // Medium strings are copied eagerly. Don't forget to allocate
344 // one extra Char for the null terminator.
345 auto const allocSize =
346 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
347 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
348 fbstring_detail::pod_copy(rhs.ml_.data_,
350 rhs.ml_.data_ + rhs.ml_.size_ + 1,
352 // No need for writeTerminator() here, we copied one extra
353 // element just above.
354 ml_.size_ = rhs.ml_.size_;
355 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
356 assert(category() == isMedium);
358 assert(size() == rhs.size());
359 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
362 fbstring_core(fbstring_core&& goner) {
363 if (goner.category() == isSmall) {
364 // Just copy, leave the goner in peace
365 new(this) fbstring_core(goner.small_, goner.smallSize());
369 // Clean goner's carcass
370 goner.setSmallSize(0);
374 // NOTE(agallagher): The word-aligned copy path copies bytes which are
375 // outside the range of the string, and makes address sanitizer unhappy,
376 // so just disable it on this function.
377 fbstring_core(const Char *const data, const size_t size)
378 FBSTRING_DISABLE_ADDRESS_SANITIZER {
379 // Simplest case first: small strings are bitblitted
380 if (size <= maxSmallSize) {
381 // Layout is: Char* data_, size_t size_, size_t capacity_
382 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
383 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
384 // sizeof(size_t) must be a power of 2
385 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
387 // If data is aligned, use fast word-wise copying. Otherwise,
388 // use conservative memcpy.
389 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
390 fbstring_detail::pod_copy(data, data + size, small_);
392 // Copy one word (64 bits) at a time
393 const size_t byteSize = size * sizeof(Char);
394 if (byteSize > 2 * sizeof(size_t)) {
396 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
398 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
400 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
401 } else if (byteSize > sizeof(size_t)) {
404 } 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;
427 assert(this->size() == size);
428 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
432 auto const c = category();
440 RefCounted::decrementRefs(ml_.data_);
443 // Snatches a previously mallocated string. The parameter "size"
444 // is the size of the string, and the parameter "capacity" is the size
445 // of the mallocated block. The string must be \0-terminated, so
446 // data[size] == '\0' and capacity >= size + 1.
448 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
449 // "size", and pass 3 as "capacity".
450 fbstring_core(Char *const data, const size_t size,
451 const size_t capacity,
452 AcquireMallocatedString) {
454 assert(capacity > size);
455 assert(data[size] == '\0');
456 // Use the medium string storage
459 ml_.capacity_ = capacity | 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();
506 #ifdef FBSTRING_PERVERSE
508 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
509 || small_[smallSize()] == '\0');
510 small_[smallSize()] = '\0';
513 assert(c == isMedium || c == isLarge);
514 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
515 ml_.data_[ml_.size_] = '\0';
516 #elif defined(FBSTRING_CONSERVATIVE)
518 assert(small_[smallSize()] == '\0');
521 assert(c == isMedium || c == isLarge);
522 assert(ml_.data_[ml_.size_] == '\0');
525 small_[smallSize()] = '\0';
528 assert(c == isMedium || c == isLarge);
529 ml_.data_[ml_.size_] = '\0';
534 void shrink(const size_t delta) {
535 if (category() == isSmall) {
536 // Check for underflow
537 assert(delta <= smallSize());
538 setSmallSize(smallSize() - delta);
539 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
540 // Medium strings and unique large strings need no special
542 assert(ml_.size_ >= delta);
545 assert(ml_.size_ >= delta);
546 // Shared large string, must make unique. This is because of the
547 // durn terminator must be written, which may trample the shared
550 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
552 // No need to write the terminator.
558 void reserve(size_t minCapacity) {
559 if (category() == isLarge) {
561 if (RefCounted::refs(ml_.data_) > 1) {
562 // We must make it unique regardless; in-place reallocation is
563 // useless if the string is shared. In order to not surprise
564 // people, reserve the new block at current capacity or
565 // more. That way, a string's capacity never shrinks after a
567 minCapacity = std::max(minCapacity, ml_.capacity());
568 auto const newRC = RefCounted::create(& minCapacity);
569 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
571 // Done with the old data. No need to call writeTerminator(),
572 // we have + 1 above.
573 RefCounted::decrementRefs(ml_.data_);
574 ml_.data_ = newRC->data_;
575 ml_.capacity_ = minCapacity | isLarge;
576 // size remains unchanged
578 // String is not shared, so let's try to realloc (if needed)
579 if (minCapacity > ml_.capacity()) {
580 // Asking for more memory
582 RefCounted::reallocate(ml_.data_, ml_.size_,
583 ml_.capacity(), minCapacity);
584 ml_.data_ = newRC->data_;
585 ml_.capacity_ = minCapacity | isLarge;
588 assert(capacity() >= minCapacity);
590 } else if (category() == isMedium) {
591 // String is not shared
592 if (minCapacity <= ml_.capacity()) {
593 return; // nothing to do, there's enough room
595 if (minCapacity <= maxMediumSize) {
596 // Keep the string at medium size. Don't forget to allocate
597 // one extra Char for the terminating null.
598 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
599 ml_.data_ = static_cast<Char *>(
602 ml_.size_ * sizeof(Char),
603 ml_.capacity() * sizeof(Char),
606 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
608 // Conversion from medium to large string
609 fbstring_core nascent;
610 // Will recurse to another branch of this function
611 nascent.reserve(minCapacity);
612 nascent.ml_.size_ = ml_.size_;
613 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
617 assert(capacity() >= minCapacity);
620 assert(category() == isSmall);
621 if (minCapacity > maxMediumSize) {
623 auto const newRC = RefCounted::create(& minCapacity);
624 auto const size = smallSize();
625 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
626 // No need for writeTerminator(), we wrote it above with + 1.
627 ml_.data_ = newRC->data_;
629 ml_.capacity_ = minCapacity | isLarge;
630 assert(capacity() >= minCapacity);
631 } else if (minCapacity > maxSmallSize) {
633 // Don't forget to allocate one extra Char for the terminating null
634 auto const allocSizeBytes =
635 goodMallocSize((1 + minCapacity) * sizeof(Char));
636 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
637 auto const size = smallSize();
638 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
639 // No need for writeTerminator(), we wrote it above with + 1.
642 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
645 // Nothing to do, everything stays put
648 assert(capacity() >= minCapacity);
651 Char * expand_noinit(const size_t delta) {
652 // Strategy is simple: make room, then change size
653 assert(capacity() >= size());
655 if (category() == isSmall) {
658 if (newSz <= maxSmallSize) {
666 newSz = ml_.size_ + delta;
667 if (newSz > capacity()) {
671 assert(capacity() >= newSz);
672 // Category can't be small - we took care of that above
673 assert(category() == isMedium || category() == isLarge);
676 assert(size() == newSz);
677 return ml_.data_ + sz;
680 void push_back(Char c) {
681 assert(capacity() >= size());
683 if (category() == isSmall) {
685 if (sz < maxSmallSize) {
686 setSmallSize(sz + 1);
691 reserve(maxSmallSize * 2);
694 if (sz == capacity()) { // always true for isShared()
695 reserve(sz * 3 / 2); // ensures not shared
699 assert(capacity() >= sz + 1);
700 // Category can't be small - we took care of that above
701 assert(category() == isMedium || category() == isLarge);
707 size_t size() const {
708 return category() == isSmall ? smallSize() : ml_.size_;
711 size_t capacity() const {
712 switch (category()) {
716 // For large-sized strings, a multi-referenced chunk has no
717 // available capacity. This is because any attempt to append
718 // data would trigger a new allocation.
719 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
722 return ml_.capacity();
725 bool isShared() const {
726 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
729 #ifdef FBSTRING_PERVERSE
730 enum { TERMINATOR = '^' };
732 enum { TERMINATOR = '\0' };
735 void writeTerminator() {
736 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
737 if (category() == isSmall) {
738 const auto s = smallSize();
739 if (s != maxSmallSize) {
740 small_[s] = TERMINATOR;
743 ml_.data_[ml_.size_] = TERMINATOR;
750 fbstring_core & operator=(const fbstring_core & rhs);
757 size_t capacity() const {
758 return capacity_ & capacityExtractMask;
763 std::atomic<size_t> refCount_;
766 static RefCounted * fromData(Char * p) {
767 return static_cast<RefCounted*>(
769 static_cast<unsigned char*>(static_cast<void*>(p))
770 - sizeof(refCount_)));
773 static size_t refs(Char * p) {
774 return fromData(p)->refCount_.load(std::memory_order_acquire);
777 static void incrementRefs(Char * p) {
778 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
781 static void decrementRefs(Char * p) {
782 auto const dis = fromData(p);
783 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
790 static RefCounted * create(size_t * size) {
791 // Don't forget to allocate one extra Char for the terminating
792 // null. In this case, however, one Char is already part of the
794 const size_t allocSize = goodMallocSize(
795 sizeof(RefCounted) + *size * sizeof(Char));
796 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
797 result->refCount_.store(1, std::memory_order_release);
798 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
802 static RefCounted * create(const Char * data, size_t * size) {
803 const size_t effectiveSize = *size;
804 auto result = create(size);
805 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
809 static RefCounted * reallocate(Char *const data,
810 const size_t currentSize,
811 const size_t currentCapacity,
812 const size_t newCapacity) {
813 assert(newCapacity > 0 && newCapacity > currentSize);
814 auto const dis = fromData(data);
815 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
816 // Don't forget to allocate one extra Char for the terminating
817 // null. In this case, however, one Char is already part of the
819 auto result = static_cast<RefCounted*>(
821 sizeof(RefCounted) + currentSize * sizeof(Char),
822 sizeof(RefCounted) + currentCapacity * sizeof(Char),
823 sizeof(RefCounted) + newCapacity * sizeof(Char)));
824 assert(result->refCount_.load(std::memory_order_acquire) == 1);
830 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
831 mutable MediumLarge ml_;
835 lastChar = sizeof(MediumLarge) - 1,
836 maxSmallSize = lastChar / sizeof(Char),
837 maxMediumSize = 254 / sizeof(Char), // coincides with the small
838 // bin size in dlmalloc
839 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
840 capacityExtractMask = ~categoryExtractMask,
842 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
843 "Corrupt memory layout for fbstring.");
847 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
848 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
851 Category category() const {
852 // Assumes little endian
853 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
856 size_t smallSize() const {
857 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
858 return static_cast<size_t>(maxSmallSize)
859 - static_cast<size_t>(small_[maxSmallSize]);
862 void setSmallSize(size_t s) {
863 // Warning: this should work with uninitialized strings too,
864 // so don't assume anything about the previous value of
865 // small_[maxSmallSize].
866 assert(s <= maxSmallSize);
867 small_[maxSmallSize] = maxSmallSize - s;
871 #if defined(__GNUC__) && !defined(__clang__)
872 # pragma GCC diagnostic pop
875 #ifndef _LIBSTDCXX_FBSTRING
877 * Dummy fbstring core that uses an actual std::string. This doesn't
878 * make any sense - it's just for testing purposes.
880 template <class Char>
881 class dummy_fbstring_core {
883 dummy_fbstring_core() {
885 dummy_fbstring_core(const dummy_fbstring_core& another)
886 : backend_(another.backend_) {
888 dummy_fbstring_core(const Char * s, size_t n)
891 void swap(dummy_fbstring_core & rhs) {
892 backend_.swap(rhs.backend_);
894 const Char * data() const {
895 return backend_.data();
897 Char * mutable_data() {
898 //assert(!backend_.empty());
899 return &*backend_.begin();
901 void shrink(size_t delta) {
902 assert(delta <= size());
903 backend_.resize(size() - delta);
905 Char * expand_noinit(size_t delta) {
906 auto const sz = size();
907 backend_.resize(size() + delta);
908 return backend_.data() + sz;
910 void push_back(Char c) {
911 backend_.push_back(c);
913 size_t size() const {
914 return backend_.size();
916 size_t capacity() const {
917 return backend_.capacity();
919 bool isShared() const {
922 void reserve(size_t minCapacity) {
923 backend_.reserve(minCapacity);
927 std::basic_string<Char> backend_;
929 #endif // !_LIBSTDCXX_FBSTRING
932 * This is the basic_string replacement. For conformity,
933 * basic_fbstring takes the same template parameters, plus the last
934 * one which is the core.
936 #ifdef _LIBSTDCXX_FBSTRING
937 template <typename E, class T, class A, class Storage>
939 template <typename E,
940 class T = std::char_traits<E>,
941 class A = std::allocator<E>,
942 class Storage = fbstring_core<E> >
944 class basic_fbstring {
948 void (*throw_exc)(const char*),
950 if (!condition) throw_exc(msg);
953 bool isSane() const {
956 empty() == (size() == 0) &&
957 empty() == (begin() == end()) &&
958 size() <= max_size() &&
959 capacity() <= max_size() &&
960 size() <= capacity() &&
961 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
965 friend struct Invariant;
968 explicit Invariant(const basic_fbstring& s) : s_(s) {
975 const basic_fbstring& s_;
977 explicit Invariant(const basic_fbstring&) {}
979 Invariant& operator=(const Invariant&);
984 typedef T traits_type;
985 typedef typename traits_type::char_type value_type;
986 typedef A allocator_type;
987 typedef typename A::size_type size_type;
988 typedef typename A::difference_type difference_type;
990 typedef typename A::reference reference;
991 typedef typename A::const_reference const_reference;
992 typedef typename A::pointer pointer;
993 typedef typename A::const_pointer const_pointer;
996 typedef const E* const_iterator;
997 typedef std::reverse_iterator<iterator
998 #ifdef NO_ITERATOR_TRAITS
1002 typedef std::reverse_iterator<const_iterator
1003 #ifdef NO_ITERATOR_TRAITS
1006 > const_reverse_iterator;
1008 static const size_type npos; // = size_type(-1)
1011 static void procrustes(size_type& n, size_type nmax) {
1012 if (n > nmax) n = nmax;
1016 // C++11 21.4.2 construct/copy/destroy
1017 explicit basic_fbstring(const A& a = A()) {
1020 basic_fbstring(const basic_fbstring& str)
1021 : store_(str.store_) {
1025 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
1028 #ifndef _LIBSTDCXX_FBSTRING
1029 // This is defined for compatibility with std::string
1030 /* implicit */ basic_fbstring(const std::string& str)
1031 : store_(str.data(), str.size()) {
1035 basic_fbstring(const basic_fbstring& str, size_type pos,
1036 size_type n = npos, const A& a = A()) {
1037 assign(str, pos, n);
1040 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1041 : store_(s, s ? traits_type::length(s) : ({
1042 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1043 err += ": null pointer initializer not valid";
1044 std::__throw_logic_error(err.c_str());
1049 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1053 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1054 auto const data = store_.expand_noinit(n);
1055 fbstring_detail::pod_fill(data, data + n, c);
1056 store_.writeTerminator();
1059 template <class InIt>
1060 basic_fbstring(InIt begin, InIt end,
1061 typename std::enable_if<
1062 !std::is_same<typename std::remove_const<InIt>::type,
1063 value_type*>::value, const A>::type & a = A()) {
1067 // Specialization for const char*, const char*
1068 basic_fbstring(const value_type* b, const value_type* e)
1069 : store_(b, e - b) {
1072 // Nonstandard constructor
1073 basic_fbstring(value_type *s, size_type n, size_type c,
1074 AcquireMallocatedString a)
1075 : store_(s, n, c, a) {
1078 // Construction from initialization list
1079 basic_fbstring(std::initializer_list<value_type> il) {
1080 assign(il.begin(), il.end());
1086 basic_fbstring& operator=(const basic_fbstring& lhs) {
1087 if (FBSTRING_UNLIKELY(&lhs == this)) {
1090 auto const oldSize = size();
1091 auto const srcSize = lhs.size();
1092 if (capacity() >= srcSize && !store_.isShared()) {
1093 // great, just copy the contents
1094 if (oldSize < srcSize)
1095 store_.expand_noinit(srcSize - oldSize);
1097 store_.shrink(oldSize - srcSize);
1098 assert(size() == srcSize);
1099 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1100 store_.writeTerminator();
1102 // need to reallocate, so we may as well create a brand new string
1103 basic_fbstring(lhs).swap(*this);
1109 basic_fbstring& operator=(basic_fbstring&& goner) {
1110 if (FBSTRING_UNLIKELY(&goner == this)) {
1111 // Compatibility with std::basic_string<>,
1112 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1115 // No need of this anymore
1116 this->~basic_fbstring();
1117 // Move the goner into this
1118 new(&store_) fbstring_core<E>(std::move(goner.store_));
1122 #ifndef _LIBSTDCXX_FBSTRING
1123 // Compatibility with std::string
1124 basic_fbstring & operator=(const std::string & rhs) {
1125 return assign(rhs.data(), rhs.size());
1128 // Compatibility with std::string
1129 std::string toStdString() const {
1130 return std::string(data(), size());
1133 // A lot of code in fbcode still uses this method, so keep it here for now.
1134 const basic_fbstring& toStdString() const {
1139 basic_fbstring& operator=(const value_type* s) {
1143 basic_fbstring& operator=(value_type c) {
1145 store_.expand_noinit(1);
1146 } else if (store_.isShared()) {
1147 basic_fbstring(1, c).swap(*this);
1150 store_.shrink(size() - 1);
1152 *store_.mutable_data() = c;
1153 store_.writeTerminator();
1157 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1158 return assign(il.begin(), il.end());
1161 // C++11 21.4.3 iterators:
1162 iterator begin() { return store_.mutable_data(); }
1164 const_iterator begin() const { return store_.data(); }
1166 const_iterator cbegin() const { return begin(); }
1169 return store_.mutable_data() + store_.size();
1172 const_iterator end() const {
1173 return store_.data() + store_.size();
1176 const_iterator cend() const { return end(); }
1178 reverse_iterator rbegin() {
1179 return reverse_iterator(end());
1182 const_reverse_iterator rbegin() const {
1183 return const_reverse_iterator(end());
1186 const_reverse_iterator crbegin() const { return rbegin(); }
1188 reverse_iterator rend() {
1189 return reverse_iterator(begin());
1192 const_reverse_iterator rend() const {
1193 return const_reverse_iterator(begin());
1196 const_reverse_iterator crend() const { return rend(); }
1199 // C++11 21.4.5, element access:
1200 const value_type& front() const { return *begin(); }
1201 const value_type& back() const {
1203 // Should be begin()[size() - 1], but that branches twice
1204 return *(end() - 1);
1206 value_type& front() { return *begin(); }
1207 value_type& back() {
1209 // Should be begin()[size() - 1], but that branches twice
1210 return *(end() - 1);
1217 // C++11 21.4.4 capacity:
1218 size_type size() const { return store_.size(); }
1220 size_type length() const { return size(); }
1222 size_type max_size() const {
1223 return std::numeric_limits<size_type>::max();
1226 void resize(const size_type n, const value_type c = value_type()) {
1227 auto size = this->size();
1229 store_.shrink(size - n);
1231 // Do this in two steps to minimize slack memory copied (see
1233 auto const capacity = this->capacity();
1234 assert(capacity >= size);
1235 if (size < capacity) {
1236 auto delta = std::min(n, capacity) - size;
1237 store_.expand_noinit(delta);
1238 fbstring_detail::pod_fill(begin() + size, end(), c);
1241 store_.writeTerminator();
1246 auto const delta = n - size;
1247 store_.expand_noinit(delta);
1248 fbstring_detail::pod_fill(end() - delta, end(), c);
1249 store_.writeTerminator();
1251 assert(this->size() == n);
1254 size_type capacity() const { return store_.capacity(); }
1256 void reserve(size_type res_arg = 0) {
1257 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1258 store_.reserve(res_arg);
1261 void shrink_to_fit() {
1262 // Shrink only if slack memory is sufficiently large
1263 if (capacity() < size() * 3 / 2) {
1266 basic_fbstring(cbegin(), cend()).swap(*this);
1269 void clear() { resize(0); }
1271 bool empty() const { return size() == 0; }
1273 // C++11 21.4.5 element access:
1274 const_reference operator[](size_type pos) const {
1275 return *(c_str() + pos);
1278 reference operator[](size_type pos) {
1279 if (pos == size()) {
1280 // Just call c_str() to make sure '\0' is present
1283 return *(begin() + pos);
1286 const_reference at(size_type n) const {
1287 enforce(n <= size(), std::__throw_out_of_range, "");
1291 reference at(size_type n) {
1292 enforce(n < size(), std::__throw_out_of_range, "");
1296 // C++11 21.4.6 modifiers:
1297 basic_fbstring& operator+=(const basic_fbstring& str) {
1301 basic_fbstring& operator+=(const value_type* s) {
1305 basic_fbstring& operator+=(const value_type c) {
1310 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1315 basic_fbstring& append(const basic_fbstring& str) {
1317 auto desiredSize = size() + str.size();
1319 append(str.data(), str.size());
1320 assert(size() == desiredSize);
1324 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1326 const size_type sz = str.size();
1327 enforce(pos <= sz, std::__throw_out_of_range, "");
1328 procrustes(n, sz - pos);
1329 return append(str.data() + pos, n);
1332 basic_fbstring& append(const value_type* s, size_type n) {
1334 Invariant checker(*this);
1337 if (FBSTRING_UNLIKELY(!n)) {
1338 // Unlikely but must be done
1341 auto const oldSize = size();
1342 auto const oldData = data();
1343 // Check for aliasing (rare). We could use "<=" here but in theory
1344 // those do not work for pointers unless the pointers point to
1345 // elements in the same array. For that reason we use
1346 // std::less_equal, which is guaranteed to offer a total order
1347 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1349 std::less_equal<const value_type*> le;
1350 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1351 assert(le(s + n, oldData + oldSize));
1352 const size_type offset = s - oldData;
1353 store_.reserve(oldSize + n);
1354 // Restore the source
1355 s = data() + offset;
1357 // Warning! Repeated appends with short strings may actually incur
1358 // practically quadratic performance. Avoid that by pushing back
1359 // the first character (which ensures exponential growth) and then
1360 // appending the rest normally. Worst case the append may incur a
1361 // second allocation but that will be rare.
1364 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1365 assert(size() == oldSize + n + 1);
1369 basic_fbstring& append(const value_type* s) {
1370 return append(s, traits_type::length(s));
1373 basic_fbstring& append(size_type n, value_type c) {
1374 resize(size() + n, c);
1378 template<class InputIterator>
1379 basic_fbstring& append(InputIterator first, InputIterator last) {
1380 insert(end(), first, last);
1384 basic_fbstring& append(std::initializer_list<value_type> il) {
1385 return append(il.begin(), il.end());
1388 void push_back(const value_type c) { // primitive
1389 store_.push_back(c);
1392 basic_fbstring& assign(const basic_fbstring& str) {
1393 if (&str == this) return *this;
1394 return assign(str.data(), str.size());
1397 basic_fbstring& assign(basic_fbstring&& str) {
1398 return *this = std::move(str);
1401 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1403 const size_type sz = str.size();
1404 enforce(pos <= sz, std::__throw_out_of_range, "");
1405 procrustes(n, sz - pos);
1406 return assign(str.data() + pos, n);
1409 basic_fbstring& assign(const value_type* s, const size_type n) {
1410 Invariant checker(*this);
1413 std::copy(s, s + n, begin());
1415 assert(size() == n);
1417 const value_type *const s2 = s + size();
1418 std::copy(s, s2, begin());
1419 append(s2, n - size());
1420 assert(size() == n);
1422 store_.writeTerminator();
1423 assert(size() == n);
1427 basic_fbstring& assign(const value_type* s) {
1428 return assign(s, traits_type::length(s));
1431 basic_fbstring& assign(std::initializer_list<value_type> il) {
1432 return assign(il.begin(), il.end());
1435 template <class ItOrLength, class ItOrChar>
1436 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1437 return replace(begin(), end(), first_or_n, last_or_c);
1440 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1441 return insert(pos1, str.data(), str.size());
1444 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1445 size_type pos2, size_type n) {
1446 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1447 procrustes(n, str.length() - pos2);
1448 return insert(pos1, str.data() + pos2, n);
1451 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1452 enforce(pos <= length(), std::__throw_out_of_range, "");
1453 insert(begin() + pos, s, s + n);
1457 basic_fbstring& insert(size_type pos, const value_type* s) {
1458 return insert(pos, s, traits_type::length(s));
1461 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1462 enforce(pos <= length(), std::__throw_out_of_range, "");
1463 insert(begin() + pos, n, c);
1467 iterator insert(const_iterator p, const value_type c) {
1468 const size_type pos = p - begin();
1470 return begin() + pos;
1474 template <int i> class Selector {};
1476 iterator insertImplDiscr(const_iterator p,
1477 size_type n, value_type c, Selector<1>) {
1478 Invariant checker(*this);
1480 auto const pos = p - begin();
1481 assert(p >= begin() && p <= end());
1482 if (capacity() - size() < n) {
1483 const size_type sz = p - begin();
1484 reserve(size() + n);
1487 const iterator oldEnd = end();
1488 if (n < size_type(oldEnd - p)) {
1489 append(oldEnd - n, oldEnd);
1491 // reverse_iterator(oldEnd - n),
1492 // reverse_iterator(p),
1493 // reverse_iterator(oldEnd));
1494 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1496 std::fill(begin() + pos, begin() + pos + n, c);
1498 append(n - (end() - p), c);
1499 append(iterator(p), oldEnd);
1500 std::fill(iterator(p), oldEnd, c);
1502 store_.writeTerminator();
1503 return begin() + pos;
1506 template<class InputIter>
1507 iterator insertImplDiscr(const_iterator i,
1508 InputIter b, InputIter e, Selector<0>) {
1509 return insertImpl(i, b, e,
1510 typename std::iterator_traits<InputIter>::iterator_category());
1513 template <class FwdIterator>
1514 iterator insertImpl(const_iterator i,
1515 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1516 Invariant checker(*this);
1518 const size_type pos = i - begin();
1519 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1520 std::distance(s1, s2);
1522 using namespace fbstring_detail;
1523 assert(pos <= size());
1525 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1526 capacity() - size();
1528 // realloc the string
1529 reserve(size() + n2);
1532 if (pos + n2 <= size()) {
1533 const iterator tailBegin = end() - n2;
1534 store_.expand_noinit(n2);
1535 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1536 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1537 reverse_iterator(tailBegin + n2));
1538 std::copy(s1, s2, begin() + pos);
1541 const size_type old_size = size();
1542 std::advance(t, old_size - pos);
1543 const size_t newElems = std::distance(t, s2);
1544 store_.expand_noinit(n2);
1545 std::copy(t, s2, begin() + old_size);
1546 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1547 begin() + old_size + newElems);
1548 std::copy(s1, t, begin() + pos);
1550 store_.writeTerminator();
1551 return begin() + pos;
1554 template <class InputIterator>
1555 iterator insertImpl(const_iterator i,
1556 InputIterator b, InputIterator e,
1557 std::input_iterator_tag) {
1558 const auto pos = i - begin();
1559 basic_fbstring temp(begin(), i);
1560 for (; b != e; ++b) {
1563 temp.append(i, cend());
1565 return begin() + pos;
1569 template <class ItOrLength, class ItOrChar>
1570 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1571 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1572 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1575 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1576 return insert(p, il.begin(), il.end());
1579 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1580 Invariant checker(*this);
1582 enforce(pos <= length(), std::__throw_out_of_range, "");
1583 procrustes(n, length() - pos);
1584 std::copy(begin() + pos + n, end(), begin() + pos);
1585 resize(length() - n);
1589 iterator erase(iterator position) {
1590 const size_type pos(position - begin());
1591 enforce(pos <= size(), std::__throw_out_of_range, "");
1593 return begin() + pos;
1596 iterator erase(iterator first, iterator last) {
1597 const size_type pos(first - begin());
1598 erase(pos, last - first);
1599 return begin() + pos;
1602 // Replaces at most n1 chars of *this, starting with pos1 with the
1604 basic_fbstring& replace(size_type pos1, size_type n1,
1605 const basic_fbstring& str) {
1606 return replace(pos1, n1, str.data(), str.size());
1609 // Replaces at most n1 chars of *this, starting with pos1,
1610 // with at most n2 chars of str starting with pos2
1611 basic_fbstring& replace(size_type pos1, size_type n1,
1612 const basic_fbstring& str,
1613 size_type pos2, size_type n2) {
1614 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1615 return replace(pos1, n1, str.data() + pos2,
1616 std::min(n2, str.size() - pos2));
1619 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1620 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1621 return replace(pos, n1, s, traits_type::length(s));
1624 // Replaces at most n1 chars of *this, starting with pos, with n2
1627 // consolidated with
1629 // Replaces at most n1 chars of *this, starting with pos, with at
1630 // most n2 chars of str. str must have at least n2 chars.
1631 template <class StrOrLength, class NumOrChar>
1632 basic_fbstring& replace(size_type pos, size_type n1,
1633 StrOrLength s_or_n2, NumOrChar n_or_c) {
1634 Invariant checker(*this);
1636 enforce(pos <= size(), std::__throw_out_of_range, "");
1637 procrustes(n1, length() - pos);
1638 const iterator b = begin() + pos;
1639 return replace(b, b + n1, s_or_n2, n_or_c);
1642 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1643 return replace(i1, i2, str.data(), str.length());
1646 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1647 return replace(i1, i2, s, traits_type::length(s));
1651 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1652 const value_type* s, size_type n,
1655 assert(begin() <= i1 && i1 <= end());
1656 assert(begin() <= i2 && i2 <= end());
1657 return replace(i1, i2, s, s + n);
1660 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1661 size_type n2, value_type c, Selector<1>) {
1662 const size_type n1 = i2 - i1;
1664 std::fill(i1, i1 + n2, c);
1667 std::fill(i1, i2, c);
1668 insert(i2, n2 - n1, c);
1674 template <class InputIter>
1675 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1676 InputIter b, InputIter e,
1678 replaceImpl(i1, i2, b, e,
1679 typename std::iterator_traits<InputIter>::iterator_category());
1684 template <class FwdIterator, class P>
1685 bool replaceAliased(iterator i1, iterator i2,
1686 FwdIterator s1, FwdIterator s2, P*) {
1690 template <class FwdIterator>
1691 bool replaceAliased(iterator i1, iterator i2,
1692 FwdIterator s1, FwdIterator s2, value_type*) {
1693 static const std::less_equal<const value_type*> le =
1694 std::less_equal<const value_type*>();
1695 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1699 // Aliased replace, copy to new string
1700 basic_fbstring temp;
1701 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1702 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1708 template <class FwdIterator>
1709 void replaceImpl(iterator i1, iterator i2,
1710 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1711 Invariant checker(*this);
1714 // Handle aliased replace
1715 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1719 auto const n1 = i2 - i1;
1721 auto const n2 = std::distance(s1, s2);
1726 std::copy(s1, s2, i1);
1730 fbstring_detail::copy_n(s1, n1, i1);
1731 std::advance(s1, n1);
1737 template <class InputIterator>
1738 void replaceImpl(iterator i1, iterator i2,
1739 InputIterator b, InputIterator e, std::input_iterator_tag) {
1740 basic_fbstring temp(begin(), i1);
1741 temp.append(b, e).append(i2, end());
1746 template <class T1, class T2>
1747 basic_fbstring& replace(iterator i1, iterator i2,
1748 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1750 num1 = std::numeric_limits<T1>::is_specialized,
1751 num2 = std::numeric_limits<T2>::is_specialized;
1752 return replaceImplDiscr(
1753 i1, i2, first_or_n_or_s, last_or_c_or_n,
1754 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1757 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1758 enforce(pos <= size(), std::__throw_out_of_range, "");
1759 procrustes(n, size() - pos);
1761 fbstring_detail::pod_copy(
1768 void swap(basic_fbstring& rhs) {
1769 store_.swap(rhs.store_);
1772 const value_type* c_str() const {
1773 return store_.c_str();
1776 const value_type* data() const { return c_str(); }
1778 allocator_type get_allocator() const {
1779 return allocator_type();
1782 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1783 return find(str.data(), pos, str.length());
1786 size_type find(const value_type* needle, const size_type pos,
1787 const size_type nsize) const {
1788 if (!nsize) return pos;
1789 auto const size = this->size();
1790 if (nsize + pos > size) return npos;
1791 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1792 // the last characters first
1793 auto const haystack = data();
1794 auto const nsize_1 = nsize - 1;
1795 auto const lastNeedle = needle[nsize_1];
1797 // Boyer-Moore skip value for the last char in the needle. Zero is
1798 // not a valid value; skip will be computed the first time it's
1802 const E * i = haystack + pos;
1803 auto iEnd = haystack + size - nsize_1;
1806 // Boyer-Moore: match the last element in the needle
1807 while (i[nsize_1] != lastNeedle) {
1813 // Here we know that the last char matches
1814 // Continue in pedestrian mode
1815 for (size_t j = 0; ; ) {
1817 if (i[j] != needle[j]) {
1818 // Not found, we can skip
1819 // Compute the skip value lazily
1822 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1829 // Check if done searching
1832 return i - haystack;
1839 size_type find(const value_type* s, size_type pos = 0) const {
1840 return find(s, pos, traits_type::length(s));
1843 size_type find (value_type c, size_type pos = 0) const {
1844 return find(&c, pos, 1);
1847 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1848 return rfind(str.data(), pos, str.length());
1851 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1852 if (n > length()) return npos;
1853 pos = std::min(pos, length() - n);
1854 if (n == 0) return pos;
1856 const_iterator i(begin() + pos);
1858 if (traits_type::eq(*i, *s)
1859 && traits_type::compare(&*i, s, n) == 0) {
1862 if (i == begin()) break;
1867 size_type rfind(const value_type* s, size_type pos = npos) const {
1868 return rfind(s, pos, traits_type::length(s));
1871 size_type rfind(value_type c, size_type pos = npos) const {
1872 return rfind(&c, pos, 1);
1875 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1876 return find_first_of(str.data(), pos, str.length());
1879 size_type find_first_of(const value_type* s,
1880 size_type pos, size_type n) const {
1881 if (pos > length() || n == 0) return npos;
1882 const_iterator i(begin() + pos),
1884 for (; i != finish; ++i) {
1885 if (traits_type::find(s, n, *i) != 0) {
1892 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1893 return find_first_of(s, pos, traits_type::length(s));
1896 size_type find_first_of(value_type c, size_type pos = 0) const {
1897 return find_first_of(&c, pos, 1);
1900 size_type find_last_of (const basic_fbstring& str,
1901 size_type pos = npos) const {
1902 return find_last_of(str.data(), pos, str.length());
1905 size_type find_last_of (const value_type* s, size_type pos,
1906 size_type n) const {
1907 if (!empty() && n > 0) {
1908 pos = std::min(pos, length() - 1);
1909 const_iterator i(begin() + pos);
1911 if (traits_type::find(s, n, *i) != 0) {
1914 if (i == begin()) break;
1920 size_type find_last_of (const value_type* s,
1921 size_type pos = npos) const {
1922 return find_last_of(s, pos, traits_type::length(s));
1925 size_type find_last_of (value_type c, size_type pos = npos) const {
1926 return find_last_of(&c, pos, 1);
1929 size_type find_first_not_of(const basic_fbstring& str,
1930 size_type pos = 0) const {
1931 return find_first_not_of(str.data(), pos, str.size());
1934 size_type find_first_not_of(const value_type* s, size_type pos,
1935 size_type n) const {
1936 if (pos < length()) {
1940 for (; i != finish; ++i) {
1941 if (traits_type::find(s, n, *i) == 0) {
1949 size_type find_first_not_of(const value_type* s,
1950 size_type pos = 0) const {
1951 return find_first_not_of(s, pos, traits_type::length(s));
1954 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1955 return find_first_not_of(&c, pos, 1);
1958 size_type find_last_not_of(const basic_fbstring& str,
1959 size_type pos = npos) const {
1960 return find_last_not_of(str.data(), pos, str.length());
1963 size_type find_last_not_of(const value_type* s, size_type pos,
1964 size_type n) const {
1965 if (!this->empty()) {
1966 pos = std::min(pos, size() - 1);
1967 const_iterator i(begin() + pos);
1969 if (traits_type::find(s, n, *i) == 0) {
1972 if (i == begin()) break;
1978 size_type find_last_not_of(const value_type* s,
1979 size_type pos = npos) const {
1980 return find_last_not_of(s, pos, traits_type::length(s));
1983 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1984 return find_last_not_of(&c, pos, 1);
1987 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1988 enforce(pos <= size(), std::__throw_out_of_range, "");
1989 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1992 int compare(const basic_fbstring& str) const {
1993 // FIX due to Goncalo N M de Carvalho July 18, 2005
1994 return compare(0, size(), str);
1997 int compare(size_type pos1, size_type n1,
1998 const basic_fbstring& str) const {
1999 return compare(pos1, n1, str.data(), str.size());
2002 int compare(size_type pos1, size_type n1,
2003 const value_type* s) const {
2004 return compare(pos1, n1, s, traits_type::length(s));
2007 int compare(size_type pos1, size_type n1,
2008 const value_type* s, size_type n2) const {
2009 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2010 procrustes(n1, size() - pos1);
2011 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2012 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2013 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2016 int compare(size_type pos1, size_type n1,
2017 const basic_fbstring& str,
2018 size_type pos2, size_type n2) const {
2019 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2020 return compare(pos1, n1, str.data() + pos2,
2021 std::min(n2, str.size() - pos2));
2024 // Code from Jean-Francois Bastien (03/26/2007)
2025 int compare(const value_type* s) const {
2026 // Could forward to compare(0, size(), s, traits_type::length(s))
2027 // but that does two extra checks
2028 const size_type n1(size()), n2(traits_type::length(s));
2029 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2030 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2038 // non-member functions
2040 template <typename E, class T, class A, class S>
2042 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2043 const basic_fbstring<E, T, A, S>& rhs) {
2045 basic_fbstring<E, T, A, S> result;
2046 result.reserve(lhs.size() + rhs.size());
2047 result.append(lhs).append(rhs);
2048 return std::move(result);
2052 template <typename E, class T, class A, class S>
2054 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2055 const basic_fbstring<E, T, A, S>& rhs) {
2056 return std::move(lhs.append(rhs));
2060 template <typename E, class T, class A, class S>
2062 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2063 basic_fbstring<E, T, A, S>&& rhs) {
2064 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2065 // Good, at least we don't need to reallocate
2066 return std::move(rhs.insert(0, lhs));
2068 // Meh, no go. Forward to operator+(const&, const&).
2069 auto const& rhsC = rhs;
2074 template <typename E, class T, class A, class S>
2076 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2077 basic_fbstring<E, T, A, S>&& rhs) {
2078 return std::move(lhs.append(rhs));
2081 template <typename E, class T, class A, class S>
2083 basic_fbstring<E, T, A, S> operator+(
2084 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2085 const basic_fbstring<E, T, A, S>& rhs) {
2087 basic_fbstring<E, T, A, S> result;
2088 const typename basic_fbstring<E, T, A, S>::size_type len =
2089 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2090 result.reserve(len + rhs.size());
2091 result.append(lhs, len).append(rhs);
2095 template <typename E, class T, class A, class S>
2097 basic_fbstring<E, T, A, S> operator+(
2098 typename basic_fbstring<E, T, A, S>::value_type lhs,
2099 const basic_fbstring<E, T, A, S>& rhs) {
2101 basic_fbstring<E, T, A, S> result;
2102 result.reserve(1 + rhs.size());
2103 result.push_back(lhs);
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 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2114 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2115 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2117 basic_fbstring<E, T, A, S> result;
2118 const size_type len = traits_type::length(rhs);
2119 result.reserve(lhs.size() + len);
2120 result.append(lhs).append(rhs, len);
2124 template <typename E, class T, class A, class S>
2126 basic_fbstring<E, T, A, S> operator+(
2127 const basic_fbstring<E, T, A, S>& lhs,
2128 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2130 basic_fbstring<E, T, A, S> result;
2131 result.reserve(lhs.size() + 1);
2133 result.push_back(rhs);
2137 template <typename E, class T, class A, class S>
2139 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2140 const basic_fbstring<E, T, A, S>& rhs) {
2141 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2143 template <typename E, class T, class A, class S>
2145 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2146 const basic_fbstring<E, T, A, S>& rhs) {
2147 return rhs == lhs; }
2149 template <typename E, class T, class A, class S>
2151 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2152 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2153 return lhs.compare(rhs) == 0; }
2155 template <typename E, class T, class A, class S>
2157 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2158 const basic_fbstring<E, T, A, S>& rhs) {
2159 return !(lhs == rhs); }
2161 template <typename E, class T, class A, class S>
2163 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2164 const basic_fbstring<E, T, A, S>& rhs) {
2165 return !(lhs == rhs); }
2167 template <typename E, class T, class A, class S>
2169 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2170 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2171 return !(lhs == rhs); }
2173 template <typename E, class T, class A, class S>
2175 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2176 const basic_fbstring<E, T, A, S>& rhs) {
2177 return lhs.compare(rhs) < 0; }
2179 template <typename E, class T, class A, class S>
2181 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2182 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2183 return lhs.compare(rhs) < 0; }
2185 template <typename E, class T, class A, class S>
2187 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2188 const basic_fbstring<E, T, A, S>& rhs) {
2189 return rhs.compare(lhs) > 0; }
2191 template <typename E, class T, class A, class S>
2193 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2194 const basic_fbstring<E, T, A, S>& rhs) {
2197 template <typename E, class T, class A, class S>
2199 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2200 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2203 template <typename E, class T, class A, class S>
2205 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2206 const basic_fbstring<E, T, A, S>& rhs) {
2209 template <typename E, class T, class A, class S>
2211 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2212 const basic_fbstring<E, T, A, S>& rhs) {
2213 return !(rhs < lhs); }
2215 template <typename E, class T, class A, class S>
2217 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2218 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2219 return !(rhs < lhs); }
2221 template <typename E, class T, class A, class S>
2223 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2224 const basic_fbstring<E, T, A, S>& rhs) {
2225 return !(rhs < lhs); }
2227 template <typename E, class T, class A, class S>
2229 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2230 const basic_fbstring<E, T, A, S>& rhs) {
2231 return !(lhs < rhs); }
2233 template <typename E, class T, class A, class S>
2235 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2236 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2237 return !(lhs < rhs); }
2239 template <typename E, class T, class A, class S>
2241 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2242 const basic_fbstring<E, T, A, S>& rhs) {
2243 return !(lhs < rhs);
2247 template <typename E, class T, class A, class S>
2248 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2252 // TODO: make this faster.
2253 template <typename E, class T, class A, class S>
2256 typename basic_fbstring<E, T, A, S>::value_type,
2257 typename basic_fbstring<E, T, A, S>::traits_type>&
2259 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2260 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2261 basic_fbstring<E, T, A, S>& str) {
2262 typename std::basic_istream<E, T>::sentry sentry(is);
2263 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2264 typename basic_fbstring<E, T, A, S>::traits_type>
2266 typedef typename __istream_type::ios_base __ios_base;
2267 size_t extracted = 0;
2268 auto err = __ios_base::goodbit;
2270 auto n = is.width();
2275 auto got = is.rdbuf()->sgetc();
2276 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2277 // Whew. We get to store this guy
2279 got = is.rdbuf()->snextc();
2281 if (got == T::eof()) {
2282 err |= __ios_base::eofbit;
2287 err |= __ios_base::failbit;
2295 template <typename E, class T, class A, class S>
2297 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2298 typename basic_fbstring<E, T, A, S>::traits_type>&
2300 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2301 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2302 const basic_fbstring<E, T, A, S>& str) {
2303 os.write(str.data(), str.size());
2307 #ifndef _LIBSTDCXX_FBSTRING
2309 template <typename E, class T, class A, class S>
2311 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2312 typename basic_fbstring<E, T, A, S>::traits_type>&
2314 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2315 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2316 basic_fbstring<E, T, A, S>& str,
2317 typename basic_fbstring<E, T, A, S>::value_type delim) {
2318 // Use the nonstandard getdelim()
2322 // This looks quadratic but it really depends on realloc
2323 auto const newSize = size + 128;
2324 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2325 is.getline(buf + size, newSize - size, delim);
2326 if (is.bad() || is.eof() || !is.fail()) {
2327 // done by either failure, end of file, or normal read
2328 size += std::strlen(buf + size);
2331 // Here we have failed due to too short a buffer
2332 // Minus one to discount the terminating '\0'
2334 assert(buf[size] == 0);
2335 // Clear the error so we can continue reading
2338 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2339 AcquireMallocatedString());
2344 template <typename E, class T, class A, class S>
2346 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2347 typename basic_fbstring<E, T, A, S>::traits_type>&
2349 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2350 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2351 basic_fbstring<E, T, A, S>& str) {
2352 // Just forward to the version with a delimiter
2353 return getline(is, str, '\n');
2358 template <typename E1, class T, class A, class S>
2359 const typename basic_fbstring<E1, T, A, S>::size_type
2360 basic_fbstring<E1, T, A, S>::npos =
2361 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2363 #ifndef _LIBSTDCXX_FBSTRING
2364 // basic_string compatibility routines
2366 template <typename E, class T, class A, class S>
2368 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2369 const std::string& rhs) {
2370 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2373 template <typename E, class T, class A, class S>
2375 bool operator==(const std::string& lhs,
2376 const basic_fbstring<E, T, A, S>& rhs) {
2380 template <typename E, class T, class A, class S>
2382 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2383 const std::string& rhs) {
2384 return !(lhs == rhs);
2387 template <typename E, class T, class A, class S>
2389 bool operator!=(const std::string& lhs,
2390 const basic_fbstring<E, T, A, S>& rhs) {
2391 return !(lhs == rhs);
2394 #if !defined(_LIBSTDCXX_FBSTRING)
2395 typedef basic_fbstring<char> fbstring;
2398 // fbstring is relocatable
2399 template <class T, class R, class A, class S>
2400 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2403 _GLIBCXX_END_NAMESPACE_VERSION
2406 } // namespace folly
2408 #pragma GCC diagnostic pop
2410 #ifndef _LIBSTDCXX_FBSTRING
2414 struct hash< ::folly::fbstring> {
2415 size_t operator()(const ::folly::fbstring& s) const {
2416 return ::folly::hash::fnv32_buf(s.data(), s.size());
2421 #endif // _LIBSTDCXX_FBSTRING
2423 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2424 #undef FBSTRING_LIKELY
2425 #undef FBSTRING_UNLIKELY
2427 #endif // FOLLY_BASE_FBSTRING_H_