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 // FBString cannot use throw when replacing std::string, though it may still
109 // use std::__throw_*
112 #ifdef _LIBSTDCXX_FBSTRING
113 namespace std _GLIBCXX_VISIBILITY(default) {
114 _GLIBCXX_BEGIN_NAMESPACE_VERSION
119 // Different versions of gcc/clang support different versions of
120 // the address sanitizer attribute. Unfortunately, this attribute
121 // has issues when inlining is used, so disable that as well.
122 #if defined(__clang__)
123 # if __has_feature(address_sanitizer)
124 # if __has_attribute(__no_address_safety_analysis__)
125 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
126 __attribute__((__no_address_safety_analysis__, __noinline__))
127 # elif __has_attribute(__no_sanitize_address__)
128 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
129 __attribute__((__no_sanitize_address__, __noinline__))
132 #elif defined (__GNUC__) && \
134 (__GNUC_MINOR__ >= 8) && \
136 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
137 __attribute__((__no_address_safety_analysis__, __noinline__))
139 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
140 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
143 namespace fbstring_detail {
145 template <class InIt, class OutIt>
148 typename std::iterator_traits<InIt>::difference_type n,
150 for (; n != 0; --n, ++b, ++d) {
151 assert((const void*)&*d != &*b);
157 template <class Pod, class T>
158 inline void pod_fill(Pod* b, Pod* e, T c) {
159 assert(b && e && b <= e);
160 /*static*/ if (sizeof(T) == 1) {
163 auto const ee = b + ((e - b) & ~7u);
164 for (; b != ee; b += 8) {
175 for (; b != e; ++b) {
182 * Lightly structured memcpy, simplifies copying PODs and introduces
183 * some asserts. Unfortunately using this function may cause
184 * measurable overhead (presumably because it adjusts from a begin/end
185 * convention to a pointer/size convention, so it does some extra
186 * arithmetic even though the caller might have done the inverse
187 * adaptation outside).
190 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
192 assert(d >= e || d + (e - b) <= b);
193 memcpy(d, b, (e - b) * sizeof(Pod));
197 * Lightly structured memmove, simplifies copying PODs and introduces
201 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
203 memmove(d, b, (e - b) * sizeof(*b));
206 } // namespace fbstring_detail
209 * Defines a special acquisition method for constructing fbstring
210 * objects. AcquireMallocatedString means that the user passes a
211 * pointer to a malloc-allocated string that the fbstring object will
214 enum class AcquireMallocatedString {};
217 * fbstring_core_model is a mock-up type that defines all required
218 * signatures of a fbstring core. The fbstring class itself uses such
219 * a core object to implement all of the numerous member functions
220 * required by the standard.
222 * If you want to define a new core, copy the definition below and
223 * implement the primitives. Then plug the core into basic_fbstring as
224 * a template argument.
226 template <class Char>
227 class fbstring_core_model {
229 fbstring_core_model();
230 fbstring_core_model(const fbstring_core_model &);
231 ~fbstring_core_model();
232 // Returns a pointer to string's buffer (currently only contiguous
233 // strings are supported). The pointer is guaranteed to be valid
234 // until the next call to a non-const member function.
235 const Char * data() const;
236 // Much like data(), except the string is prepared to support
237 // character-level changes. This call is a signal for
238 // e.g. reference-counted implementation to fork the data. The
239 // pointer is guaranteed to be valid until the next call to a
240 // non-const member function.
241 Char * mutable_data();
242 // Returns a pointer to string's buffer and guarantees that a
243 // readable '\0' lies right after the buffer. The pointer is
244 // guaranteed to be valid until the next call to a non-const member
246 const Char * c_str() const;
247 // Shrinks the string by delta characters. Asserts that delta <=
249 void shrink(size_t delta);
250 // Expands the string by delta characters (i.e. after this call
251 // size() will report the old size() plus delta) but without
252 // initializing the expanded region. Returns a pointer to the memory
253 // to be initialized (the beginning of the expanded portion). The
254 // caller is expected to fill the expanded area appropriately.
255 Char* expand_noinit(size_t delta);
256 // Expands the string by one character and sets the last character
258 void push_back(Char c);
259 // Returns the string's size.
261 // Returns the string's capacity, i.e. maximum size that the string
262 // can grow to without reallocation. Note that for reference counted
263 // strings that's technically a lie - even assigning characters
264 // within the existing size would cause a reallocation.
265 size_t capacity() const;
266 // Returns true if the data underlying the string is actually shared
267 // across multiple strings (in a refcounted fashion).
268 bool isShared() const;
269 // Makes sure that at least minCapacity characters are available for
270 // the string without reallocation. For reference-counted strings,
271 // it should fork the data even if minCapacity < size().
272 void reserve(size_t minCapacity);
275 fbstring_core_model& operator=(const fbstring_core_model &);
280 * gcc-4.7 throws what appears to be some false positive uninitialized
281 * warnings for the members of the MediumLarge struct. So, mute them here.
283 #if defined(__GNUC__) && !defined(__clang__)
284 # pragma GCC diagnostic push
285 # pragma GCC diagnostic ignored "-Wuninitialized"
289 * This is the core of the string. The code should work on 32- and
290 * 64-bit architectures and with any Char size. Porting to big endian
291 * architectures would require some changes.
293 * The storage is selected as follows (assuming we store one-byte
294 * characters on a 64-bit machine): (a) "small" strings between 0 and
295 * 23 chars are stored in-situ without allocation (the rightmost byte
296 * stores the size); (b) "medium" strings from 24 through 254 chars
297 * are stored in malloc-allocated memory that is copied eagerly; (c)
298 * "large" strings of 255 chars and above are stored in a similar
299 * structure as medium arrays, except that the string is
300 * reference-counted and copied lazily. the reference count is
301 * allocated right before the character array.
303 * The discriminator between these three strategies sits in the two
304 * most significant bits of the rightmost char of the storage. If
305 * neither is set, then the string is small (and its length sits in
306 * the lower-order bits of that rightmost character). If the MSb is
307 * set, the string is medium width. If the second MSb is set, then the
310 template <class Char> class fbstring_core {
312 fbstring_core() noexcept {
313 // Only initialize the tag, will set the MSBs (i.e. the small
314 // string size) to zero too
315 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
316 // or: setSmallSize(0);
318 assert(category() == isSmall && size() == 0);
321 fbstring_core(const fbstring_core & rhs) {
322 assert(&rhs != this);
323 // Simplest case first: small strings are bitblitted
324 if (rhs.category() == isSmall) {
325 assert(offsetof(MediumLarge, data_) == 0);
326 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
327 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
328 const size_t size = rhs.smallSize();
330 ml_.capacity_ = rhs.ml_.capacity_;
333 // Just write the whole thing, don't look at details. In
334 // particular we need to copy capacity anyway because we want
335 // to set the size (don't forget that the last character,
336 // which stores a short string's length, is shared with the
337 // ml_.capacity field).
340 assert(category() == isSmall && this->size() == rhs.size());
341 } else if (rhs.category() == isLarge) {
342 // Large strings are just refcounted
344 RefCounted::incrementRefs(ml_.data_);
345 assert(category() == isLarge && size() == rhs.size());
347 // Medium strings are copied eagerly. Don't forget to allocate
348 // one extra Char for the null terminator.
349 auto const allocSize =
350 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
351 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
352 fbstring_detail::pod_copy(rhs.ml_.data_,
354 rhs.ml_.data_ + rhs.ml_.size_ + 1,
356 // No need for writeTerminator() here, we copied one extra
357 // element just above.
358 ml_.size_ = rhs.ml_.size_;
359 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
360 assert(category() == isMedium);
362 assert(size() == rhs.size());
363 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
366 fbstring_core(fbstring_core&& goner) noexcept {
367 if (goner.category() == isSmall) {
368 // Just copy, leave the goner in peace
369 new(this) fbstring_core(goner.small_, goner.smallSize());
373 // Clean goner's carcass
374 goner.setSmallSize(0);
378 // NOTE(agallagher): The word-aligned copy path copies bytes which are
379 // outside the range of the string, and makes address sanitizer unhappy,
380 // so just disable it on this function.
381 fbstring_core(const Char *const data, const size_t size)
382 FBSTRING_DISABLE_ADDRESS_SANITIZER {
383 // Simplest case first: small strings are bitblitted
384 if (size <= maxSmallSize) {
385 // Layout is: Char* data_, size_t size_, size_t capacity_
386 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
387 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
388 // sizeof(size_t) must be a power of 2
389 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
391 // If data is aligned, use fast word-wise copying. Otherwise,
392 // use conservative memcpy.
393 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
394 fbstring_detail::pod_copy(data, data + size, small_);
396 // Copy one word (64 bits) at a time
397 const size_t byteSize = size * sizeof(Char);
398 if (byteSize > 2 * sizeof(size_t)) {
400 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
402 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
404 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
405 } else if (byteSize > sizeof(size_t)) {
408 } else if (size > 0) {
414 } else if (size <= maxMediumSize) {
415 // Medium strings are allocated normally. Don't forget to
416 // allocate one extra Char for the terminating null.
417 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
418 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
419 fbstring_detail::pod_copy(data, data + size, ml_.data_);
421 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
423 // Large strings are allocated differently
424 size_t effectiveCapacity = size;
425 auto const newRC = RefCounted::create(data, & effectiveCapacity);
426 ml_.data_ = newRC->data_;
428 ml_.capacity_ = effectiveCapacity | isLarge;
431 assert(this->size() == size);
432 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
435 ~fbstring_core() noexcept {
436 auto const c = category();
444 RefCounted::decrementRefs(ml_.data_);
447 // Snatches a previously mallocated string. The parameter "size"
448 // is the size of the string, and the parameter "allocatedSize"
449 // is the size of the mallocated block. The string must be
450 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
452 // So if you want a 2-character string, pass malloc(3) as "data",
453 // pass 2 as "size", and pass 3 as "allocatedSize".
454 fbstring_core(Char * const data,
456 const size_t allocatedSize,
457 AcquireMallocatedString) {
459 assert(allocatedSize >= size + 1);
460 assert(data[size] == '\0');
461 // Use the medium string storage
464 // Don't forget about null terminator
465 ml_.capacity_ = (allocatedSize - 1) | isMedium;
467 // No need for the memory
473 // swap below doesn't test whether &rhs == this (and instead
474 // potentially does extra work) on the premise that the rarity of
475 // that situation actually makes the check more expensive than is
477 void swap(fbstring_core & rhs) {
483 // In C++11 data() and c_str() are 100% equivalent.
484 const Char * data() const {
488 Char * mutable_data() {
489 auto const c = category();
493 assert(c == isMedium || c == isLarge);
494 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
496 size_t effectiveCapacity = ml_.capacity();
497 auto const newRC = RefCounted::create(& effectiveCapacity);
498 // If this fails, someone placed the wrong capacity in an
500 assert(effectiveCapacity >= ml_.capacity());
501 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
503 RefCounted::decrementRefs(ml_.data_);
504 ml_.data_ = newRC->data_;
505 // No need to call writeTerminator(), we have + 1 above.
510 const Char * c_str() const {
511 auto const c = category();
512 #ifdef FBSTRING_PERVERSE
514 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
515 || small_[smallSize()] == '\0');
516 small_[smallSize()] = '\0';
519 assert(c == isMedium || c == isLarge);
520 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
521 ml_.data_[ml_.size_] = '\0';
522 #elif defined(FBSTRING_CONSERVATIVE)
524 assert(small_[smallSize()] == '\0');
527 assert(c == isMedium || c == isLarge);
528 assert(ml_.data_[ml_.size_] == '\0');
531 small_[smallSize()] = '\0';
534 assert(c == isMedium || c == isLarge);
535 ml_.data_[ml_.size_] = '\0';
540 void shrink(const size_t delta) {
541 if (category() == isSmall) {
542 // Check for underflow
543 assert(delta <= smallSize());
544 setSmallSize(smallSize() - delta);
545 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
546 // Medium strings and unique large strings need no special
548 assert(ml_.size_ >= delta);
551 assert(ml_.size_ >= delta);
552 // Shared large string, must make unique. This is because of the
553 // durn terminator must be written, which may trample the shared
556 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
558 // No need to write the terminator.
564 void reserve(size_t minCapacity) {
565 if (category() == isLarge) {
567 if (RefCounted::refs(ml_.data_) > 1) {
568 // We must make it unique regardless; in-place reallocation is
569 // useless if the string is shared. In order to not surprise
570 // people, reserve the new block at current capacity or
571 // more. That way, a string's capacity never shrinks after a
573 minCapacity = std::max(minCapacity, ml_.capacity());
574 auto const newRC = RefCounted::create(& minCapacity);
575 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
577 // Done with the old data. No need to call writeTerminator(),
578 // we have + 1 above.
579 RefCounted::decrementRefs(ml_.data_);
580 ml_.data_ = newRC->data_;
581 ml_.capacity_ = minCapacity | isLarge;
582 // size remains unchanged
584 // String is not shared, so let's try to realloc (if needed)
585 if (minCapacity > ml_.capacity()) {
586 // Asking for more memory
588 RefCounted::reallocate(ml_.data_, ml_.size_,
589 ml_.capacity(), minCapacity);
590 ml_.data_ = newRC->data_;
591 ml_.capacity_ = minCapacity | isLarge;
594 assert(capacity() >= minCapacity);
596 } else if (category() == isMedium) {
597 // String is not shared
598 if (minCapacity <= ml_.capacity()) {
599 return; // nothing to do, there's enough room
601 if (minCapacity <= maxMediumSize) {
602 // Keep the string at medium size. Don't forget to allocate
603 // one extra Char for the terminating null.
604 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
605 ml_.data_ = static_cast<Char *>(
608 ml_.size_ * sizeof(Char),
609 (ml_.capacity() + 1) * sizeof(Char),
612 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
614 // Conversion from medium to large string
615 fbstring_core nascent;
616 // Will recurse to another branch of this function
617 nascent.reserve(minCapacity);
618 nascent.ml_.size_ = ml_.size_;
619 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
623 assert(capacity() >= minCapacity);
626 assert(category() == isSmall);
627 if (minCapacity > maxMediumSize) {
629 auto const newRC = RefCounted::create(& minCapacity);
630 auto const size = smallSize();
631 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
632 // No need for writeTerminator(), we wrote it above with + 1.
633 ml_.data_ = newRC->data_;
635 ml_.capacity_ = minCapacity | isLarge;
636 assert(capacity() >= minCapacity);
637 } else if (minCapacity > maxSmallSize) {
639 // Don't forget to allocate one extra Char for the terminating null
640 auto const allocSizeBytes =
641 goodMallocSize((1 + minCapacity) * sizeof(Char));
642 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
643 auto const size = smallSize();
644 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
645 // No need for writeTerminator(), we wrote it above with + 1.
648 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
651 // Nothing to do, everything stays put
654 assert(capacity() >= minCapacity);
657 Char * expand_noinit(const size_t delta) {
658 // Strategy is simple: make room, then change size
659 assert(capacity() >= size());
661 if (category() == isSmall) {
664 if (newSz <= maxSmallSize) {
672 newSz = ml_.size_ + delta;
673 if (newSz > capacity()) {
677 assert(capacity() >= newSz);
678 // Category can't be small - we took care of that above
679 assert(category() == isMedium || category() == isLarge);
682 assert(size() == newSz);
683 return ml_.data_ + sz;
686 void push_back(Char c) {
687 assert(capacity() >= size());
689 if (category() == isSmall) {
691 if (sz < maxSmallSize) {
692 setSmallSize(sz + 1);
697 reserve(maxSmallSize * 2);
700 if (sz == capacity()) { // always true for isShared()
701 reserve(1 + sz * 3 / 2); // ensures not shared
705 assert(capacity() >= sz + 1);
706 // Category can't be small - we took care of that above
707 assert(category() == isMedium || category() == isLarge);
713 size_t size() const {
714 return category() == isSmall ? smallSize() : ml_.size_;
717 size_t capacity() const {
718 switch (category()) {
722 // For large-sized strings, a multi-referenced chunk has no
723 // available capacity. This is because any attempt to append
724 // data would trigger a new allocation.
725 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
728 return ml_.capacity();
731 bool isShared() const {
732 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
735 #ifdef FBSTRING_PERVERSE
736 enum { TERMINATOR = '^' };
738 enum { TERMINATOR = '\0' };
741 void writeTerminator() {
742 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
743 if (category() == isSmall) {
744 const auto s = smallSize();
745 if (s != maxSmallSize) {
746 small_[s] = TERMINATOR;
749 ml_.data_[ml_.size_] = TERMINATOR;
756 fbstring_core & operator=(const fbstring_core & rhs);
763 size_t capacity() const {
764 return capacity_ & capacityExtractMask;
769 std::atomic<size_t> refCount_;
772 static RefCounted * fromData(Char * p) {
773 return static_cast<RefCounted*>(
775 static_cast<unsigned char*>(static_cast<void*>(p))
776 - sizeof(refCount_)));
779 static size_t refs(Char * p) {
780 return fromData(p)->refCount_.load(std::memory_order_acquire);
783 static void incrementRefs(Char * p) {
784 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
787 static void decrementRefs(Char * p) {
788 auto const dis = fromData(p);
789 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
796 static RefCounted * create(size_t * size) {
797 // Don't forget to allocate one extra Char for the terminating
798 // null. In this case, however, one Char is already part of the
800 const size_t allocSize = goodMallocSize(
801 sizeof(RefCounted) + *size * sizeof(Char));
802 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
803 result->refCount_.store(1, std::memory_order_release);
804 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
808 static RefCounted * create(const Char * data, size_t * size) {
809 const size_t effectiveSize = *size;
810 auto result = create(size);
811 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
815 static RefCounted * reallocate(Char *const data,
816 const size_t currentSize,
817 const size_t currentCapacity,
818 const size_t newCapacity) {
819 assert(newCapacity > 0 && newCapacity > currentSize);
820 auto const dis = fromData(data);
821 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
822 // Don't forget to allocate one extra Char for the terminating
823 // null. In this case, however, one Char is already part of the
825 auto result = static_cast<RefCounted*>(
827 sizeof(RefCounted) + currentSize * sizeof(Char),
828 sizeof(RefCounted) + currentCapacity * sizeof(Char),
829 sizeof(RefCounted) + newCapacity * sizeof(Char)));
830 assert(result->refCount_.load(std::memory_order_acquire) == 1);
836 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
837 mutable MediumLarge ml_;
841 lastChar = sizeof(MediumLarge) - 1,
842 maxSmallSize = lastChar / sizeof(Char),
843 maxMediumSize = 254 / sizeof(Char), // coincides with the small
844 // bin size in dlmalloc
845 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
846 capacityExtractMask = ~categoryExtractMask,
848 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
849 "Corrupt memory layout for fbstring.");
853 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
854 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
857 Category category() const {
858 // Assumes little endian
859 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
862 size_t smallSize() const {
863 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
864 return static_cast<size_t>(maxSmallSize)
865 - static_cast<size_t>(small_[maxSmallSize]);
868 void setSmallSize(size_t s) {
869 // Warning: this should work with uninitialized strings too,
870 // so don't assume anything about the previous value of
871 // small_[maxSmallSize].
872 assert(s <= maxSmallSize);
873 small_[maxSmallSize] = maxSmallSize - s;
877 #if defined(__GNUC__) && !defined(__clang__)
878 # pragma GCC diagnostic pop
881 #ifndef _LIBSTDCXX_FBSTRING
883 * Dummy fbstring core that uses an actual std::string. This doesn't
884 * make any sense - it's just for testing purposes.
886 template <class Char>
887 class dummy_fbstring_core {
889 dummy_fbstring_core() {
891 dummy_fbstring_core(const dummy_fbstring_core& another)
892 : backend_(another.backend_) {
894 dummy_fbstring_core(const Char * s, size_t n)
897 void swap(dummy_fbstring_core & rhs) {
898 backend_.swap(rhs.backend_);
900 const Char * data() const {
901 return backend_.data();
903 Char * mutable_data() {
904 //assert(!backend_.empty());
905 return &*backend_.begin();
907 void shrink(size_t delta) {
908 assert(delta <= size());
909 backend_.resize(size() - delta);
911 Char * expand_noinit(size_t delta) {
912 auto const sz = size();
913 backend_.resize(size() + delta);
914 return backend_.data() + sz;
916 void push_back(Char c) {
917 backend_.push_back(c);
919 size_t size() const {
920 return backend_.size();
922 size_t capacity() const {
923 return backend_.capacity();
925 bool isShared() const {
928 void reserve(size_t minCapacity) {
929 backend_.reserve(minCapacity);
933 std::basic_string<Char> backend_;
935 #endif // !_LIBSTDCXX_FBSTRING
938 * This is the basic_string replacement. For conformity,
939 * basic_fbstring takes the same template parameters, plus the last
940 * one which is the core.
942 #ifdef _LIBSTDCXX_FBSTRING
943 template <typename E, class T, class A, class Storage>
945 template <typename E,
946 class T = std::char_traits<E>,
947 class A = std::allocator<E>,
948 class Storage = fbstring_core<E> >
950 class basic_fbstring {
954 void (*throw_exc)(const char*),
956 if (!condition) throw_exc(msg);
959 bool isSane() const {
962 empty() == (size() == 0) &&
963 empty() == (begin() == end()) &&
964 size() <= max_size() &&
965 capacity() <= max_size() &&
966 size() <= capacity() &&
967 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
971 friend struct Invariant;
974 explicit Invariant(const basic_fbstring& s) : s_(s) {
981 const basic_fbstring& s_;
983 explicit Invariant(const basic_fbstring&) {}
985 Invariant& operator=(const Invariant&);
990 typedef T traits_type;
991 typedef typename traits_type::char_type value_type;
992 typedef A allocator_type;
993 typedef typename A::size_type size_type;
994 typedef typename A::difference_type difference_type;
996 typedef typename A::reference reference;
997 typedef typename A::const_reference const_reference;
998 typedef typename A::pointer pointer;
999 typedef typename A::const_pointer const_pointer;
1001 typedef E* iterator;
1002 typedef const E* const_iterator;
1003 typedef std::reverse_iterator<iterator
1004 #ifdef NO_ITERATOR_TRAITS
1008 typedef std::reverse_iterator<const_iterator
1009 #ifdef NO_ITERATOR_TRAITS
1012 > const_reverse_iterator;
1014 static const size_type npos; // = size_type(-1)
1017 static void procrustes(size_type& n, size_type nmax) {
1018 if (n > nmax) n = nmax;
1022 // C++11 21.4.2 construct/copy/destroy
1023 explicit basic_fbstring(const A& a = A()) noexcept {
1026 basic_fbstring(const basic_fbstring& str)
1027 : store_(str.store_) {
1031 basic_fbstring(basic_fbstring&& goner) noexcept
1032 : store_(std::move(goner.store_)) {
1035 #ifndef _LIBSTDCXX_FBSTRING
1036 // This is defined for compatibility with std::string
1037 /* implicit */ basic_fbstring(const std::string& str)
1038 : store_(str.data(), str.size()) {
1042 basic_fbstring(const basic_fbstring& str, size_type pos,
1043 size_type n = npos, const A& a = A()) {
1044 assign(str, pos, n);
1047 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1048 : store_(s, s ? traits_type::length(s) : ({
1049 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1050 err += ": null pointer initializer not valid";
1051 std::__throw_logic_error(err.c_str());
1056 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1060 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1061 auto const data = store_.expand_noinit(n);
1062 fbstring_detail::pod_fill(data, data + n, c);
1063 store_.writeTerminator();
1066 template <class InIt>
1067 basic_fbstring(InIt begin, InIt end,
1068 typename std::enable_if<
1069 !std::is_same<typename std::remove_const<InIt>::type,
1070 value_type*>::value, const A>::type & a = A()) {
1074 // Specialization for const char*, const char*
1075 basic_fbstring(const value_type* b, const value_type* e)
1076 : store_(b, e - b) {
1079 // Nonstandard constructor
1080 basic_fbstring(value_type *s, size_type n, size_type c,
1081 AcquireMallocatedString a)
1082 : store_(s, n, c, a) {
1085 // Construction from initialization list
1086 basic_fbstring(std::initializer_list<value_type> il) {
1087 assign(il.begin(), il.end());
1090 ~basic_fbstring() noexcept {
1093 basic_fbstring& operator=(const basic_fbstring& lhs) {
1094 if (FBSTRING_UNLIKELY(&lhs == this)) {
1097 auto const oldSize = size();
1098 auto const srcSize = lhs.size();
1099 if (capacity() >= srcSize && !store_.isShared()) {
1100 // great, just copy the contents
1101 if (oldSize < srcSize)
1102 store_.expand_noinit(srcSize - oldSize);
1104 store_.shrink(oldSize - srcSize);
1105 assert(size() == srcSize);
1106 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1107 store_.writeTerminator();
1109 // need to reallocate, so we may as well create a brand new string
1110 basic_fbstring(lhs).swap(*this);
1116 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1117 if (FBSTRING_UNLIKELY(&goner == this)) {
1118 // Compatibility with std::basic_string<>,
1119 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1122 // No need of this anymore
1123 this->~basic_fbstring();
1124 // Move the goner into this
1125 new(&store_) fbstring_core<E>(std::move(goner.store_));
1129 #ifndef _LIBSTDCXX_FBSTRING
1130 // Compatibility with std::string
1131 basic_fbstring & operator=(const std::string & rhs) {
1132 return assign(rhs.data(), rhs.size());
1135 // Compatibility with std::string
1136 std::string toStdString() const {
1137 return std::string(data(), size());
1140 // A lot of code in fbcode still uses this method, so keep it here for now.
1141 const basic_fbstring& toStdString() const {
1146 basic_fbstring& operator=(const value_type* s) {
1150 basic_fbstring& operator=(value_type c) {
1152 store_.expand_noinit(1);
1153 } else if (store_.isShared()) {
1154 basic_fbstring(1, c).swap(*this);
1157 store_.shrink(size() - 1);
1159 *store_.mutable_data() = c;
1160 store_.writeTerminator();
1164 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1165 return assign(il.begin(), il.end());
1168 // C++11 21.4.3 iterators:
1169 iterator begin() { return store_.mutable_data(); }
1171 const_iterator begin() const { return store_.data(); }
1173 const_iterator cbegin() const { return begin(); }
1176 return store_.mutable_data() + store_.size();
1179 const_iterator end() const {
1180 return store_.data() + store_.size();
1183 const_iterator cend() const { return end(); }
1185 reverse_iterator rbegin() {
1186 return reverse_iterator(end());
1189 const_reverse_iterator rbegin() const {
1190 return const_reverse_iterator(end());
1193 const_reverse_iterator crbegin() const { return rbegin(); }
1195 reverse_iterator rend() {
1196 return reverse_iterator(begin());
1199 const_reverse_iterator rend() const {
1200 return const_reverse_iterator(begin());
1203 const_reverse_iterator crend() const { return rend(); }
1206 // C++11 21.4.5, element access:
1207 const value_type& front() const { return *begin(); }
1208 const value_type& back() const {
1210 // Should be begin()[size() - 1], but that branches twice
1211 return *(end() - 1);
1213 value_type& front() { return *begin(); }
1214 value_type& back() {
1216 // Should be begin()[size() - 1], but that branches twice
1217 return *(end() - 1);
1224 // C++11 21.4.4 capacity:
1225 size_type size() const { return store_.size(); }
1227 size_type length() const { return size(); }
1229 size_type max_size() const {
1230 return std::numeric_limits<size_type>::max();
1233 void resize(const size_type n, const value_type c = value_type()) {
1234 auto size = this->size();
1236 store_.shrink(size - n);
1238 // Do this in two steps to minimize slack memory copied (see
1240 auto const capacity = this->capacity();
1241 assert(capacity >= size);
1242 if (size < capacity) {
1243 auto delta = std::min(n, capacity) - size;
1244 store_.expand_noinit(delta);
1245 fbstring_detail::pod_fill(begin() + size, end(), c);
1248 store_.writeTerminator();
1253 auto const delta = n - size;
1254 store_.expand_noinit(delta);
1255 fbstring_detail::pod_fill(end() - delta, end(), c);
1256 store_.writeTerminator();
1258 assert(this->size() == n);
1261 size_type capacity() const { return store_.capacity(); }
1263 void reserve(size_type res_arg = 0) {
1264 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1265 store_.reserve(res_arg);
1268 void shrink_to_fit() {
1269 // Shrink only if slack memory is sufficiently large
1270 if (capacity() < size() * 3 / 2) {
1273 basic_fbstring(cbegin(), cend()).swap(*this);
1276 void clear() { resize(0); }
1278 bool empty() const { return size() == 0; }
1280 // C++11 21.4.5 element access:
1281 const_reference operator[](size_type pos) const {
1282 return *(c_str() + pos);
1285 reference operator[](size_type pos) {
1286 if (pos == size()) {
1287 // Just call c_str() to make sure '\0' is present
1290 return *(begin() + pos);
1293 const_reference at(size_type n) const {
1294 enforce(n <= size(), std::__throw_out_of_range, "");
1298 reference at(size_type n) {
1299 enforce(n < size(), std::__throw_out_of_range, "");
1303 // C++11 21.4.6 modifiers:
1304 basic_fbstring& operator+=(const basic_fbstring& str) {
1308 basic_fbstring& operator+=(const value_type* s) {
1312 basic_fbstring& operator+=(const value_type c) {
1317 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1322 basic_fbstring& append(const basic_fbstring& str) {
1324 auto desiredSize = size() + str.size();
1326 append(str.data(), str.size());
1327 assert(size() == desiredSize);
1331 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1333 const size_type sz = str.size();
1334 enforce(pos <= sz, std::__throw_out_of_range, "");
1335 procrustes(n, sz - pos);
1336 return append(str.data() + pos, n);
1339 basic_fbstring& append(const value_type* s, size_type n) {
1341 Invariant checker(*this);
1344 if (FBSTRING_UNLIKELY(!n)) {
1345 // Unlikely but must be done
1348 auto const oldSize = size();
1349 auto const oldData = data();
1350 // Check for aliasing (rare). We could use "<=" here but in theory
1351 // those do not work for pointers unless the pointers point to
1352 // elements in the same array. For that reason we use
1353 // std::less_equal, which is guaranteed to offer a total order
1354 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1356 std::less_equal<const value_type*> le;
1357 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1358 assert(le(s + n, oldData + oldSize));
1359 const size_type offset = s - oldData;
1360 store_.reserve(oldSize + n);
1361 // Restore the source
1362 s = data() + offset;
1364 // Warning! Repeated appends with short strings may actually incur
1365 // practically quadratic performance. Avoid that by pushing back
1366 // the first character (which ensures exponential growth) and then
1367 // appending the rest normally. Worst case the append may incur a
1368 // second allocation but that will be rare.
1371 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1372 assert(size() == oldSize + n + 1);
1376 basic_fbstring& append(const value_type* s) {
1377 return append(s, traits_type::length(s));
1380 basic_fbstring& append(size_type n, value_type c) {
1381 resize(size() + n, c);
1385 template<class InputIterator>
1386 basic_fbstring& append(InputIterator first, InputIterator last) {
1387 insert(end(), first, last);
1391 basic_fbstring& append(std::initializer_list<value_type> il) {
1392 return append(il.begin(), il.end());
1395 void push_back(const value_type c) { // primitive
1396 store_.push_back(c);
1399 basic_fbstring& assign(const basic_fbstring& str) {
1400 if (&str == this) return *this;
1401 return assign(str.data(), str.size());
1404 basic_fbstring& assign(basic_fbstring&& str) {
1405 return *this = std::move(str);
1408 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1410 const size_type sz = str.size();
1411 enforce(pos <= sz, std::__throw_out_of_range, "");
1412 procrustes(n, sz - pos);
1413 return assign(str.data() + pos, n);
1416 basic_fbstring& assign(const value_type* s, const size_type n) {
1417 Invariant checker(*this);
1420 std::copy(s, s + n, begin());
1422 assert(size() == n);
1424 const value_type *const s2 = s + size();
1425 std::copy(s, s2, begin());
1426 append(s2, n - size());
1427 assert(size() == n);
1429 store_.writeTerminator();
1430 assert(size() == n);
1434 basic_fbstring& assign(const value_type* s) {
1435 return assign(s, traits_type::length(s));
1438 basic_fbstring& assign(std::initializer_list<value_type> il) {
1439 return assign(il.begin(), il.end());
1442 template <class ItOrLength, class ItOrChar>
1443 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1444 return replace(begin(), end(), first_or_n, last_or_c);
1447 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1448 return insert(pos1, str.data(), str.size());
1451 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1452 size_type pos2, size_type n) {
1453 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1454 procrustes(n, str.length() - pos2);
1455 return insert(pos1, str.data() + pos2, n);
1458 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1459 enforce(pos <= length(), std::__throw_out_of_range, "");
1460 insert(begin() + pos, s, s + n);
1464 basic_fbstring& insert(size_type pos, const value_type* s) {
1465 return insert(pos, s, traits_type::length(s));
1468 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1469 enforce(pos <= length(), std::__throw_out_of_range, "");
1470 insert(begin() + pos, n, c);
1474 iterator insert(const_iterator p, const value_type c) {
1475 const size_type pos = p - begin();
1477 return begin() + pos;
1481 template <int i> class Selector {};
1483 iterator insertImplDiscr(const_iterator p,
1484 size_type n, value_type c, Selector<1>) {
1485 Invariant checker(*this);
1487 auto const pos = p - begin();
1488 assert(p >= begin() && p <= end());
1489 if (capacity() - size() < n) {
1490 const size_type sz = p - begin();
1491 reserve(size() + n);
1494 const iterator oldEnd = end();
1495 if (n < size_type(oldEnd - p)) {
1496 append(oldEnd - n, oldEnd);
1498 // reverse_iterator(oldEnd - n),
1499 // reverse_iterator(p),
1500 // reverse_iterator(oldEnd));
1501 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1503 std::fill(begin() + pos, begin() + pos + n, c);
1505 append(n - (end() - p), c);
1506 append(iterator(p), oldEnd);
1507 std::fill(iterator(p), oldEnd, c);
1509 store_.writeTerminator();
1510 return begin() + pos;
1513 template<class InputIter>
1514 iterator insertImplDiscr(const_iterator i,
1515 InputIter b, InputIter e, Selector<0>) {
1516 return insertImpl(i, b, e,
1517 typename std::iterator_traits<InputIter>::iterator_category());
1520 template <class FwdIterator>
1521 iterator insertImpl(const_iterator i,
1522 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1523 Invariant checker(*this);
1525 const size_type pos = i - begin();
1526 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1527 std::distance(s1, s2);
1529 using namespace fbstring_detail;
1530 assert(pos <= size());
1532 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1533 capacity() - size();
1535 // realloc the string
1536 reserve(size() + n2);
1539 if (pos + n2 <= size()) {
1540 const iterator tailBegin = end() - n2;
1541 store_.expand_noinit(n2);
1542 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1543 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1544 reverse_iterator(tailBegin + n2));
1545 std::copy(s1, s2, begin() + pos);
1548 const size_type old_size = size();
1549 std::advance(t, old_size - pos);
1550 const size_t newElems = std::distance(t, s2);
1551 store_.expand_noinit(n2);
1552 std::copy(t, s2, begin() + old_size);
1553 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1554 begin() + old_size + newElems);
1555 std::copy(s1, t, begin() + pos);
1557 store_.writeTerminator();
1558 return begin() + pos;
1561 template <class InputIterator>
1562 iterator insertImpl(const_iterator i,
1563 InputIterator b, InputIterator e,
1564 std::input_iterator_tag) {
1565 const auto pos = i - begin();
1566 basic_fbstring temp(begin(), i);
1567 for (; b != e; ++b) {
1570 temp.append(i, cend());
1572 return begin() + pos;
1576 template <class ItOrLength, class ItOrChar>
1577 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1578 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1579 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1582 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1583 return insert(p, il.begin(), il.end());
1586 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1587 Invariant checker(*this);
1589 enforce(pos <= length(), std::__throw_out_of_range, "");
1590 procrustes(n, length() - pos);
1591 std::copy(begin() + pos + n, end(), begin() + pos);
1592 resize(length() - n);
1596 iterator erase(iterator position) {
1597 const size_type pos(position - begin());
1598 enforce(pos <= size(), std::__throw_out_of_range, "");
1600 return begin() + pos;
1603 iterator erase(iterator first, iterator last) {
1604 const size_type pos(first - begin());
1605 erase(pos, last - first);
1606 return begin() + pos;
1609 // Replaces at most n1 chars of *this, starting with pos1 with the
1611 basic_fbstring& replace(size_type pos1, size_type n1,
1612 const basic_fbstring& str) {
1613 return replace(pos1, n1, str.data(), str.size());
1616 // Replaces at most n1 chars of *this, starting with pos1,
1617 // with at most n2 chars of str starting with pos2
1618 basic_fbstring& replace(size_type pos1, size_type n1,
1619 const basic_fbstring& str,
1620 size_type pos2, size_type n2) {
1621 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1622 return replace(pos1, n1, str.data() + pos2,
1623 std::min(n2, str.size() - pos2));
1626 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1627 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1628 return replace(pos, n1, s, traits_type::length(s));
1631 // Replaces at most n1 chars of *this, starting with pos, with n2
1634 // consolidated with
1636 // Replaces at most n1 chars of *this, starting with pos, with at
1637 // most n2 chars of str. str must have at least n2 chars.
1638 template <class StrOrLength, class NumOrChar>
1639 basic_fbstring& replace(size_type pos, size_type n1,
1640 StrOrLength s_or_n2, NumOrChar n_or_c) {
1641 Invariant checker(*this);
1643 enforce(pos <= size(), std::__throw_out_of_range, "");
1644 procrustes(n1, length() - pos);
1645 const iterator b = begin() + pos;
1646 return replace(b, b + n1, s_or_n2, n_or_c);
1649 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1650 return replace(i1, i2, str.data(), str.length());
1653 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1654 return replace(i1, i2, s, traits_type::length(s));
1658 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1659 const value_type* s, size_type n,
1662 assert(begin() <= i1 && i1 <= end());
1663 assert(begin() <= i2 && i2 <= end());
1664 return replace(i1, i2, s, s + n);
1667 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1668 size_type n2, value_type c, Selector<1>) {
1669 const size_type n1 = i2 - i1;
1671 std::fill(i1, i1 + n2, c);
1674 std::fill(i1, i2, c);
1675 insert(i2, n2 - n1, c);
1681 template <class InputIter>
1682 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1683 InputIter b, InputIter e,
1685 replaceImpl(i1, i2, b, e,
1686 typename std::iterator_traits<InputIter>::iterator_category());
1691 template <class FwdIterator, class P>
1692 bool replaceAliased(iterator i1, iterator i2,
1693 FwdIterator s1, FwdIterator s2, P*) {
1697 template <class FwdIterator>
1698 bool replaceAliased(iterator i1, iterator i2,
1699 FwdIterator s1, FwdIterator s2, value_type*) {
1700 static const std::less_equal<const value_type*> le =
1701 std::less_equal<const value_type*>();
1702 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1706 // Aliased replace, copy to new string
1707 basic_fbstring temp;
1708 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1709 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1715 template <class FwdIterator>
1716 void replaceImpl(iterator i1, iterator i2,
1717 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1718 Invariant checker(*this);
1721 // Handle aliased replace
1722 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1726 auto const n1 = i2 - i1;
1728 auto const n2 = std::distance(s1, s2);
1733 std::copy(s1, s2, i1);
1737 fbstring_detail::copy_n(s1, n1, i1);
1738 std::advance(s1, n1);
1744 template <class InputIterator>
1745 void replaceImpl(iterator i1, iterator i2,
1746 InputIterator b, InputIterator e, std::input_iterator_tag) {
1747 basic_fbstring temp(begin(), i1);
1748 temp.append(b, e).append(i2, end());
1753 template <class T1, class T2>
1754 basic_fbstring& replace(iterator i1, iterator i2,
1755 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1757 num1 = std::numeric_limits<T1>::is_specialized,
1758 num2 = std::numeric_limits<T2>::is_specialized;
1759 return replaceImplDiscr(
1760 i1, i2, first_or_n_or_s, last_or_c_or_n,
1761 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1764 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1765 enforce(pos <= size(), std::__throw_out_of_range, "");
1766 procrustes(n, size() - pos);
1768 fbstring_detail::pod_copy(
1775 void swap(basic_fbstring& rhs) {
1776 store_.swap(rhs.store_);
1779 const value_type* c_str() const {
1780 return store_.c_str();
1783 const value_type* data() const { return c_str(); }
1785 allocator_type get_allocator() const {
1786 return allocator_type();
1789 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1790 return find(str.data(), pos, str.length());
1793 size_type find(const value_type* needle, const size_type pos,
1794 const size_type nsize) const {
1795 if (!nsize) return pos;
1796 auto const size = this->size();
1797 if (nsize + pos > size) return npos;
1798 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1799 // the last characters first
1800 auto const haystack = data();
1801 auto const nsize_1 = nsize - 1;
1802 auto const lastNeedle = needle[nsize_1];
1804 // Boyer-Moore skip value for the last char in the needle. Zero is
1805 // not a valid value; skip will be computed the first time it's
1809 const E * i = haystack + pos;
1810 auto iEnd = haystack + size - nsize_1;
1813 // Boyer-Moore: match the last element in the needle
1814 while (i[nsize_1] != lastNeedle) {
1820 // Here we know that the last char matches
1821 // Continue in pedestrian mode
1822 for (size_t j = 0; ; ) {
1824 if (i[j] != needle[j]) {
1825 // Not found, we can skip
1826 // Compute the skip value lazily
1829 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1836 // Check if done searching
1839 return i - haystack;
1846 size_type find(const value_type* s, size_type pos = 0) const {
1847 return find(s, pos, traits_type::length(s));
1850 size_type find (value_type c, size_type pos = 0) const {
1851 return find(&c, pos, 1);
1854 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1855 return rfind(str.data(), pos, str.length());
1858 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1859 if (n > length()) return npos;
1860 pos = std::min(pos, length() - n);
1861 if (n == 0) return pos;
1863 const_iterator i(begin() + pos);
1865 if (traits_type::eq(*i, *s)
1866 && traits_type::compare(&*i, s, n) == 0) {
1869 if (i == begin()) break;
1874 size_type rfind(const value_type* s, size_type pos = npos) const {
1875 return rfind(s, pos, traits_type::length(s));
1878 size_type rfind(value_type c, size_type pos = npos) const {
1879 return rfind(&c, pos, 1);
1882 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1883 return find_first_of(str.data(), pos, str.length());
1886 size_type find_first_of(const value_type* s,
1887 size_type pos, size_type n) const {
1888 if (pos > length() || n == 0) return npos;
1889 const_iterator i(begin() + pos),
1891 for (; i != finish; ++i) {
1892 if (traits_type::find(s, n, *i) != 0) {
1899 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1900 return find_first_of(s, pos, traits_type::length(s));
1903 size_type find_first_of(value_type c, size_type pos = 0) const {
1904 return find_first_of(&c, pos, 1);
1907 size_type find_last_of (const basic_fbstring& str,
1908 size_type pos = npos) const {
1909 return find_last_of(str.data(), pos, str.length());
1912 size_type find_last_of (const value_type* s, size_type pos,
1913 size_type n) const {
1914 if (!empty() && n > 0) {
1915 pos = std::min(pos, length() - 1);
1916 const_iterator i(begin() + pos);
1918 if (traits_type::find(s, n, *i) != 0) {
1921 if (i == begin()) break;
1927 size_type find_last_of (const value_type* s,
1928 size_type pos = npos) const {
1929 return find_last_of(s, pos, traits_type::length(s));
1932 size_type find_last_of (value_type c, size_type pos = npos) const {
1933 return find_last_of(&c, pos, 1);
1936 size_type find_first_not_of(const basic_fbstring& str,
1937 size_type pos = 0) const {
1938 return find_first_not_of(str.data(), pos, str.size());
1941 size_type find_first_not_of(const value_type* s, size_type pos,
1942 size_type n) const {
1943 if (pos < length()) {
1947 for (; i != finish; ++i) {
1948 if (traits_type::find(s, n, *i) == 0) {
1956 size_type find_first_not_of(const value_type* s,
1957 size_type pos = 0) const {
1958 return find_first_not_of(s, pos, traits_type::length(s));
1961 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1962 return find_first_not_of(&c, pos, 1);
1965 size_type find_last_not_of(const basic_fbstring& str,
1966 size_type pos = npos) const {
1967 return find_last_not_of(str.data(), pos, str.length());
1970 size_type find_last_not_of(const value_type* s, size_type pos,
1971 size_type n) const {
1972 if (!this->empty()) {
1973 pos = std::min(pos, size() - 1);
1974 const_iterator i(begin() + pos);
1976 if (traits_type::find(s, n, *i) == 0) {
1979 if (i == begin()) break;
1985 size_type find_last_not_of(const value_type* s,
1986 size_type pos = npos) const {
1987 return find_last_not_of(s, pos, traits_type::length(s));
1990 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1991 return find_last_not_of(&c, pos, 1);
1994 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1995 enforce(pos <= size(), std::__throw_out_of_range, "");
1996 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1999 int compare(const basic_fbstring& str) const {
2000 // FIX due to Goncalo N M de Carvalho July 18, 2005
2001 return compare(0, size(), str);
2004 int compare(size_type pos1, size_type n1,
2005 const basic_fbstring& str) const {
2006 return compare(pos1, n1, str.data(), str.size());
2009 int compare(size_type pos1, size_type n1,
2010 const value_type* s) const {
2011 return compare(pos1, n1, s, traits_type::length(s));
2014 int compare(size_type pos1, size_type n1,
2015 const value_type* s, size_type n2) const {
2016 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2017 procrustes(n1, size() - pos1);
2018 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2019 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2020 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2023 int compare(size_type pos1, size_type n1,
2024 const basic_fbstring& str,
2025 size_type pos2, size_type n2) const {
2026 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2027 return compare(pos1, n1, str.data() + pos2,
2028 std::min(n2, str.size() - pos2));
2031 // Code from Jean-Francois Bastien (03/26/2007)
2032 int compare(const value_type* s) const {
2033 // Could forward to compare(0, size(), s, traits_type::length(s))
2034 // but that does two extra checks
2035 const size_type n1(size()), n2(traits_type::length(s));
2036 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2037 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2045 // non-member functions
2047 template <typename E, class T, class A, class S>
2049 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2050 const basic_fbstring<E, T, A, S>& rhs) {
2052 basic_fbstring<E, T, A, S> result;
2053 result.reserve(lhs.size() + rhs.size());
2054 result.append(lhs).append(rhs);
2055 return std::move(result);
2059 template <typename E, class T, class A, class S>
2061 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2062 const basic_fbstring<E, T, A, S>& rhs) {
2063 return std::move(lhs.append(rhs));
2067 template <typename E, class T, class A, class S>
2069 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2070 basic_fbstring<E, T, A, S>&& rhs) {
2071 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2072 // Good, at least we don't need to reallocate
2073 return std::move(rhs.insert(0, lhs));
2075 // Meh, no go. Forward to operator+(const&, const&).
2076 auto const& rhsC = rhs;
2081 template <typename E, class T, class A, class S>
2083 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2084 basic_fbstring<E, T, A, S>&& rhs) {
2085 return std::move(lhs.append(rhs));
2088 template <typename E, class T, class A, class S>
2090 basic_fbstring<E, T, A, S> operator+(
2091 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2092 const basic_fbstring<E, T, A, S>& rhs) {
2094 basic_fbstring<E, T, A, S> result;
2095 const typename basic_fbstring<E, T, A, S>::size_type len =
2096 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2097 result.reserve(len + rhs.size());
2098 result.append(lhs, len).append(rhs);
2102 template <typename E, class T, class A, class S>
2104 basic_fbstring<E, T, A, S> operator+(
2105 typename basic_fbstring<E, T, A, S>::value_type lhs,
2106 const basic_fbstring<E, T, A, S>& rhs) {
2108 basic_fbstring<E, T, A, S> result;
2109 result.reserve(1 + rhs.size());
2110 result.push_back(lhs);
2115 template <typename E, class T, class A, class S>
2117 basic_fbstring<E, T, A, S> operator+(
2118 const basic_fbstring<E, T, A, S>& lhs,
2119 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2121 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2122 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2124 basic_fbstring<E, T, A, S> result;
2125 const size_type len = traits_type::length(rhs);
2126 result.reserve(lhs.size() + len);
2127 result.append(lhs).append(rhs, len);
2131 template <typename E, class T, class A, class S>
2133 basic_fbstring<E, T, A, S> operator+(
2134 const basic_fbstring<E, T, A, S>& lhs,
2135 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2137 basic_fbstring<E, T, A, S> result;
2138 result.reserve(lhs.size() + 1);
2140 result.push_back(rhs);
2144 template <typename E, class T, class A, class S>
2146 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2147 const basic_fbstring<E, T, A, S>& rhs) {
2148 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2150 template <typename E, class T, class A, class S>
2152 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2153 const basic_fbstring<E, T, A, S>& rhs) {
2154 return rhs == lhs; }
2156 template <typename E, class T, class A, class S>
2158 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2159 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2160 return lhs.compare(rhs) == 0; }
2162 template <typename E, class T, class A, class S>
2164 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2165 const basic_fbstring<E, T, A, S>& rhs) {
2166 return !(lhs == rhs); }
2168 template <typename E, class T, class A, class S>
2170 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2171 const basic_fbstring<E, T, A, S>& rhs) {
2172 return !(lhs == rhs); }
2174 template <typename E, class T, class A, class S>
2176 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2177 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2178 return !(lhs == rhs); }
2180 template <typename E, class T, class A, class S>
2182 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2183 const basic_fbstring<E, T, A, S>& rhs) {
2184 return lhs.compare(rhs) < 0; }
2186 template <typename E, class T, class A, class S>
2188 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2189 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2190 return lhs.compare(rhs) < 0; }
2192 template <typename E, class T, class A, class S>
2194 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2195 const basic_fbstring<E, T, A, S>& rhs) {
2196 return rhs.compare(lhs) > 0; }
2198 template <typename E, class T, class A, class S>
2200 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2201 const basic_fbstring<E, T, A, S>& rhs) {
2204 template <typename E, class T, class A, class S>
2206 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2207 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2210 template <typename E, class T, class A, class S>
2212 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2213 const basic_fbstring<E, T, A, S>& rhs) {
2216 template <typename E, class T, class A, class S>
2218 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2219 const basic_fbstring<E, T, A, S>& rhs) {
2220 return !(rhs < lhs); }
2222 template <typename E, class T, class A, class S>
2224 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2225 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2226 return !(rhs < lhs); }
2228 template <typename E, class T, class A, class S>
2230 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2231 const basic_fbstring<E, T, A, S>& rhs) {
2232 return !(rhs < lhs); }
2234 template <typename E, class T, class A, class S>
2236 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2237 const basic_fbstring<E, T, A, S>& rhs) {
2238 return !(lhs < rhs); }
2240 template <typename E, class T, class A, class S>
2242 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2243 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2244 return !(lhs < rhs); }
2246 template <typename E, class T, class A, class S>
2248 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2249 const basic_fbstring<E, T, A, S>& rhs) {
2250 return !(lhs < rhs);
2254 template <typename E, class T, class A, class S>
2255 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2259 // TODO: make this faster.
2260 template <typename E, class T, class A, class S>
2263 typename basic_fbstring<E, T, A, S>::value_type,
2264 typename basic_fbstring<E, T, A, S>::traits_type>&
2266 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2267 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2268 basic_fbstring<E, T, A, S>& str) {
2269 typename std::basic_istream<E, T>::sentry sentry(is);
2270 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2271 typename basic_fbstring<E, T, A, S>::traits_type>
2273 typedef typename __istream_type::ios_base __ios_base;
2274 size_t extracted = 0;
2275 auto err = __ios_base::goodbit;
2277 auto n = is.width();
2282 auto got = is.rdbuf()->sgetc();
2283 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2284 // Whew. We get to store this guy
2286 got = is.rdbuf()->snextc();
2288 if (got == T::eof()) {
2289 err |= __ios_base::eofbit;
2294 err |= __ios_base::failbit;
2302 template <typename E, class T, class A, class S>
2304 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2305 typename basic_fbstring<E, T, A, S>::traits_type>&
2307 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2308 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2309 const basic_fbstring<E, T, A, S>& str) {
2310 os.write(str.data(), str.size());
2314 #ifndef _LIBSTDCXX_FBSTRING
2316 template <typename E, class T, class A, class S>
2318 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2319 typename basic_fbstring<E, T, A, S>::traits_type>&
2321 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2322 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2323 basic_fbstring<E, T, A, S>& str,
2324 typename basic_fbstring<E, T, A, S>::value_type delim) {
2325 // Use the nonstandard getdelim()
2329 // This looks quadratic but it really depends on realloc
2330 auto const newSize = size + 128;
2331 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2332 is.getline(buf + size, newSize - size, delim);
2333 if (is.bad() || is.eof() || !is.fail()) {
2334 // done by either failure, end of file, or normal read
2335 size += std::strlen(buf + size);
2338 // Here we have failed due to too short a buffer
2339 // Minus one to discount the terminating '\0'
2341 assert(buf[size] == 0);
2342 // Clear the error so we can continue reading
2345 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2346 AcquireMallocatedString());
2351 template <typename E, class T, class A, class S>
2353 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2354 typename basic_fbstring<E, T, A, S>::traits_type>&
2356 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2357 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2358 basic_fbstring<E, T, A, S>& str) {
2359 // Just forward to the version with a delimiter
2360 return getline(is, str, '\n');
2365 template <typename E1, class T, class A, class S>
2366 const typename basic_fbstring<E1, T, A, S>::size_type
2367 basic_fbstring<E1, T, A, S>::npos =
2368 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2370 #ifndef _LIBSTDCXX_FBSTRING
2371 // basic_string compatibility routines
2373 template <typename E, class T, class A, class S>
2375 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2376 const std::string& rhs) {
2377 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2380 template <typename E, class T, class A, class S>
2382 bool operator==(const std::string& lhs,
2383 const basic_fbstring<E, T, A, S>& rhs) {
2387 template <typename E, class T, class A, class S>
2389 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2390 const std::string& rhs) {
2391 return !(lhs == rhs);
2394 template <typename E, class T, class A, class S>
2396 bool operator!=(const std::string& lhs,
2397 const basic_fbstring<E, T, A, S>& rhs) {
2398 return !(lhs == rhs);
2401 #if !defined(_LIBSTDCXX_FBSTRING)
2402 typedef basic_fbstring<char> fbstring;
2405 // fbstring is relocatable
2406 template <class T, class R, class A, class S>
2407 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2410 _GLIBCXX_END_NAMESPACE_VERSION
2413 } // namespace folly
2415 #pragma GCC diagnostic pop
2417 #ifndef _LIBSTDCXX_FBSTRING
2421 struct hash< ::folly::fbstring> {
2422 size_t operator()(const ::folly::fbstring& s) const {
2423 return ::folly::hash::fnv32_buf(s.data(), s.size());
2428 #endif // _LIBSTDCXX_FBSTRING
2430 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2432 #undef FBSTRING_LIKELY
2433 #undef FBSTRING_UNLIKELY
2435 #endif // FOLLY_BASE_FBSTRING_H_