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_*
110 #define throw FOLLY_FBSTRING_MAY_NOT_USE_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 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1798 // that nsize + pos does not wrap around.
1799 if (nsize + pos > size || nsize + pos < pos) return npos;
1800 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1801 // the last characters first
1802 auto const haystack = data();
1803 auto const nsize_1 = nsize - 1;
1804 auto const lastNeedle = needle[nsize_1];
1806 // Boyer-Moore skip value for the last char in the needle. Zero is
1807 // not a valid value; skip will be computed the first time it's
1811 const E * i = haystack + pos;
1812 auto iEnd = haystack + size - nsize_1;
1815 // Boyer-Moore: match the last element in the needle
1816 while (i[nsize_1] != lastNeedle) {
1822 // Here we know that the last char matches
1823 // Continue in pedestrian mode
1824 for (size_t j = 0; ; ) {
1826 if (i[j] != needle[j]) {
1827 // Not found, we can skip
1828 // Compute the skip value lazily
1831 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1838 // Check if done searching
1841 return i - haystack;
1848 size_type find(const value_type* s, size_type pos = 0) const {
1849 return find(s, pos, traits_type::length(s));
1852 size_type find (value_type c, size_type pos = 0) const {
1853 return find(&c, pos, 1);
1856 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1857 return rfind(str.data(), pos, str.length());
1860 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1861 if (n > length()) return npos;
1862 pos = std::min(pos, length() - n);
1863 if (n == 0) return pos;
1865 const_iterator i(begin() + pos);
1867 if (traits_type::eq(*i, *s)
1868 && traits_type::compare(&*i, s, n) == 0) {
1871 if (i == begin()) break;
1876 size_type rfind(const value_type* s, size_type pos = npos) const {
1877 return rfind(s, pos, traits_type::length(s));
1880 size_type rfind(value_type c, size_type pos = npos) const {
1881 return rfind(&c, pos, 1);
1884 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1885 return find_first_of(str.data(), pos, str.length());
1888 size_type find_first_of(const value_type* s,
1889 size_type pos, size_type n) const {
1890 if (pos > length() || n == 0) return npos;
1891 const_iterator i(begin() + pos),
1893 for (; i != finish; ++i) {
1894 if (traits_type::find(s, n, *i) != 0) {
1901 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1902 return find_first_of(s, pos, traits_type::length(s));
1905 size_type find_first_of(value_type c, size_type pos = 0) const {
1906 return find_first_of(&c, pos, 1);
1909 size_type find_last_of (const basic_fbstring& str,
1910 size_type pos = npos) const {
1911 return find_last_of(str.data(), pos, str.length());
1914 size_type find_last_of (const value_type* s, size_type pos,
1915 size_type n) const {
1916 if (!empty() && n > 0) {
1917 pos = std::min(pos, length() - 1);
1918 const_iterator i(begin() + pos);
1920 if (traits_type::find(s, n, *i) != 0) {
1923 if (i == begin()) break;
1929 size_type find_last_of (const value_type* s,
1930 size_type pos = npos) const {
1931 return find_last_of(s, pos, traits_type::length(s));
1934 size_type find_last_of (value_type c, size_type pos = npos) const {
1935 return find_last_of(&c, pos, 1);
1938 size_type find_first_not_of(const basic_fbstring& str,
1939 size_type pos = 0) const {
1940 return find_first_not_of(str.data(), pos, str.size());
1943 size_type find_first_not_of(const value_type* s, size_type pos,
1944 size_type n) const {
1945 if (pos < length()) {
1949 for (; i != finish; ++i) {
1950 if (traits_type::find(s, n, *i) == 0) {
1958 size_type find_first_not_of(const value_type* s,
1959 size_type pos = 0) const {
1960 return find_first_not_of(s, pos, traits_type::length(s));
1963 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1964 return find_first_not_of(&c, pos, 1);
1967 size_type find_last_not_of(const basic_fbstring& str,
1968 size_type pos = npos) const {
1969 return find_last_not_of(str.data(), pos, str.length());
1972 size_type find_last_not_of(const value_type* s, size_type pos,
1973 size_type n) const {
1974 if (!this->empty()) {
1975 pos = std::min(pos, size() - 1);
1976 const_iterator i(begin() + pos);
1978 if (traits_type::find(s, n, *i) == 0) {
1981 if (i == begin()) break;
1987 size_type find_last_not_of(const value_type* s,
1988 size_type pos = npos) const {
1989 return find_last_not_of(s, pos, traits_type::length(s));
1992 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1993 return find_last_not_of(&c, pos, 1);
1996 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1997 enforce(pos <= size(), std::__throw_out_of_range, "");
1998 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2001 int compare(const basic_fbstring& str) const {
2002 // FIX due to Goncalo N M de Carvalho July 18, 2005
2003 return compare(0, size(), str);
2006 int compare(size_type pos1, size_type n1,
2007 const basic_fbstring& str) const {
2008 return compare(pos1, n1, str.data(), str.size());
2011 int compare(size_type pos1, size_type n1,
2012 const value_type* s) const {
2013 return compare(pos1, n1, s, traits_type::length(s));
2016 int compare(size_type pos1, size_type n1,
2017 const value_type* s, size_type n2) const {
2018 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2019 procrustes(n1, size() - pos1);
2020 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2021 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2022 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2025 int compare(size_type pos1, size_type n1,
2026 const basic_fbstring& str,
2027 size_type pos2, size_type n2) const {
2028 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2029 return compare(pos1, n1, str.data() + pos2,
2030 std::min(n2, str.size() - pos2));
2033 // Code from Jean-Francois Bastien (03/26/2007)
2034 int compare(const value_type* s) const {
2035 // Could forward to compare(0, size(), s, traits_type::length(s))
2036 // but that does two extra checks
2037 const size_type n1(size()), n2(traits_type::length(s));
2038 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2039 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2047 // non-member functions
2049 template <typename E, class T, class A, class S>
2051 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2052 const basic_fbstring<E, T, A, S>& rhs) {
2054 basic_fbstring<E, T, A, S> result;
2055 result.reserve(lhs.size() + rhs.size());
2056 result.append(lhs).append(rhs);
2057 return std::move(result);
2061 template <typename E, class T, class A, class S>
2063 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2064 const basic_fbstring<E, T, A, S>& rhs) {
2065 return std::move(lhs.append(rhs));
2069 template <typename E, class T, class A, class S>
2071 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2072 basic_fbstring<E, T, A, S>&& rhs) {
2073 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2074 // Good, at least we don't need to reallocate
2075 return std::move(rhs.insert(0, lhs));
2077 // Meh, no go. Forward to operator+(const&, const&).
2078 auto const& rhsC = rhs;
2083 template <typename E, class T, class A, class S>
2085 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2086 basic_fbstring<E, T, A, S>&& rhs) {
2087 return std::move(lhs.append(rhs));
2090 template <typename E, class T, class A, class S>
2092 basic_fbstring<E, T, A, S> operator+(
2093 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2094 const basic_fbstring<E, T, A, S>& rhs) {
2096 basic_fbstring<E, T, A, S> result;
2097 const typename basic_fbstring<E, T, A, S>::size_type len =
2098 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2099 result.reserve(len + rhs.size());
2100 result.append(lhs, len).append(rhs);
2104 template <typename E, class T, class A, class S>
2106 basic_fbstring<E, T, A, S> operator+(
2107 typename basic_fbstring<E, T, A, S>::value_type lhs,
2108 const basic_fbstring<E, T, A, S>& rhs) {
2110 basic_fbstring<E, T, A, S> result;
2111 result.reserve(1 + rhs.size());
2112 result.push_back(lhs);
2117 template <typename E, class T, class A, class S>
2119 basic_fbstring<E, T, A, S> operator+(
2120 const basic_fbstring<E, T, A, S>& lhs,
2121 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2123 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2124 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2126 basic_fbstring<E, T, A, S> result;
2127 const size_type len = traits_type::length(rhs);
2128 result.reserve(lhs.size() + len);
2129 result.append(lhs).append(rhs, len);
2133 template <typename E, class T, class A, class S>
2135 basic_fbstring<E, T, A, S> operator+(
2136 const basic_fbstring<E, T, A, S>& lhs,
2137 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2139 basic_fbstring<E, T, A, S> result;
2140 result.reserve(lhs.size() + 1);
2142 result.push_back(rhs);
2146 template <typename E, class T, class A, class S>
2148 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2149 const basic_fbstring<E, T, A, S>& rhs) {
2150 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2152 template <typename E, class T, class A, class S>
2154 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2155 const basic_fbstring<E, T, A, S>& rhs) {
2156 return rhs == lhs; }
2158 template <typename E, class T, class A, class S>
2160 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2161 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2162 return lhs.compare(rhs) == 0; }
2164 template <typename E, class T, class A, class S>
2166 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2167 const basic_fbstring<E, T, A, S>& rhs) {
2168 return !(lhs == rhs); }
2170 template <typename E, class T, class A, class S>
2172 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2173 const basic_fbstring<E, T, A, S>& rhs) {
2174 return !(lhs == rhs); }
2176 template <typename E, class T, class A, class S>
2178 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2179 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2180 return !(lhs == rhs); }
2182 template <typename E, class T, class A, class S>
2184 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2185 const basic_fbstring<E, T, A, S>& rhs) {
2186 return lhs.compare(rhs) < 0; }
2188 template <typename E, class T, class A, class S>
2190 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2191 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2192 return lhs.compare(rhs) < 0; }
2194 template <typename E, class T, class A, class S>
2196 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2197 const basic_fbstring<E, T, A, S>& rhs) {
2198 return rhs.compare(lhs) > 0; }
2200 template <typename E, class T, class A, class S>
2202 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2203 const basic_fbstring<E, T, A, S>& rhs) {
2206 template <typename E, class T, class A, class S>
2208 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2209 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2212 template <typename E, class T, class A, class S>
2214 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2215 const basic_fbstring<E, T, A, S>& rhs) {
2218 template <typename E, class T, class A, class S>
2220 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2221 const basic_fbstring<E, T, A, S>& rhs) {
2222 return !(rhs < lhs); }
2224 template <typename E, class T, class A, class S>
2226 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2227 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2228 return !(rhs < lhs); }
2230 template <typename E, class T, class A, class S>
2232 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2233 const basic_fbstring<E, T, A, S>& rhs) {
2234 return !(rhs < lhs); }
2236 template <typename E, class T, class A, class S>
2238 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2239 const basic_fbstring<E, T, A, S>& rhs) {
2240 return !(lhs < rhs); }
2242 template <typename E, class T, class A, class S>
2244 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2245 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2246 return !(lhs < rhs); }
2248 template <typename E, class T, class A, class S>
2250 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2251 const basic_fbstring<E, T, A, S>& rhs) {
2252 return !(lhs < rhs);
2256 template <typename E, class T, class A, class S>
2257 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2261 // TODO: make this faster.
2262 template <typename E, class T, class A, class S>
2265 typename basic_fbstring<E, T, A, S>::value_type,
2266 typename basic_fbstring<E, T, A, S>::traits_type>&
2268 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2269 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2270 basic_fbstring<E, T, A, S>& str) {
2271 typename std::basic_istream<E, T>::sentry sentry(is);
2272 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2273 typename basic_fbstring<E, T, A, S>::traits_type>
2275 typedef typename __istream_type::ios_base __ios_base;
2276 size_t extracted = 0;
2277 auto err = __ios_base::goodbit;
2279 auto n = is.width();
2284 auto got = is.rdbuf()->sgetc();
2285 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2286 // Whew. We get to store this guy
2288 got = is.rdbuf()->snextc();
2290 if (got == T::eof()) {
2291 err |= __ios_base::eofbit;
2296 err |= __ios_base::failbit;
2304 template <typename E, class T, class A, class S>
2306 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2307 typename basic_fbstring<E, T, A, S>::traits_type>&
2309 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2310 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2311 const basic_fbstring<E, T, A, S>& str) {
2312 os.write(str.data(), str.size());
2316 #ifndef _LIBSTDCXX_FBSTRING
2318 template <typename E, class T, class A, class S>
2320 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2321 typename basic_fbstring<E, T, A, S>::traits_type>&
2323 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2324 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2325 basic_fbstring<E, T, A, S>& str,
2326 typename basic_fbstring<E, T, A, S>::value_type delim) {
2327 // Use the nonstandard getdelim()
2331 // This looks quadratic but it really depends on realloc
2332 auto const newSize = size + 128;
2333 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2334 is.getline(buf + size, newSize - size, delim);
2335 if (is.bad() || is.eof() || !is.fail()) {
2336 // done by either failure, end of file, or normal read
2337 size += std::strlen(buf + size);
2340 // Here we have failed due to too short a buffer
2341 // Minus one to discount the terminating '\0'
2343 assert(buf[size] == 0);
2344 // Clear the error so we can continue reading
2347 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2348 AcquireMallocatedString());
2353 template <typename E, class T, class A, class S>
2355 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2356 typename basic_fbstring<E, T, A, S>::traits_type>&
2358 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2359 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2360 basic_fbstring<E, T, A, S>& str) {
2361 // Just forward to the version with a delimiter
2362 return getline(is, str, '\n');
2367 template <typename E1, class T, class A, class S>
2368 const typename basic_fbstring<E1, T, A, S>::size_type
2369 basic_fbstring<E1, T, A, S>::npos =
2370 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2372 #ifndef _LIBSTDCXX_FBSTRING
2373 // basic_string compatibility routines
2375 template <typename E, class T, class A, class S>
2377 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2378 const std::string& rhs) {
2379 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2382 template <typename E, class T, class A, class S>
2384 bool operator==(const std::string& lhs,
2385 const basic_fbstring<E, T, A, S>& rhs) {
2389 template <typename E, class T, class A, class S>
2391 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2392 const std::string& rhs) {
2393 return !(lhs == rhs);
2396 template <typename E, class T, class A, class S>
2398 bool operator!=(const std::string& lhs,
2399 const basic_fbstring<E, T, A, S>& rhs) {
2400 return !(lhs == rhs);
2403 #if !defined(_LIBSTDCXX_FBSTRING)
2404 typedef basic_fbstring<char> fbstring;
2407 // fbstring is relocatable
2408 template <class T, class R, class A, class S>
2409 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2412 _GLIBCXX_END_NAMESPACE_VERSION
2415 } // namespace folly
2417 #pragma GCC diagnostic pop
2419 #ifndef _LIBSTDCXX_FBSTRING
2423 struct hash< ::folly::fbstring> {
2424 size_t operator()(const ::folly::fbstring& s) const {
2425 return ::folly::hash::fnv32_buf(s.data(), s.size());
2430 #endif // _LIBSTDCXX_FBSTRING
2432 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2434 #undef FBSTRING_LIKELY
2435 #undef FBSTRING_UNLIKELY
2437 #endif // FOLLY_BASE_FBSTRING_H_