2 * Copyright 2013 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
24 fbstring's behavior can be configured via two macro definitions, as
25 follows. Normally, fbstring does not write a '\0' at the end of
26 each string whenever it changes the underlying characters. Instead,
27 it lazily writes the '\0' whenever either c_str() or data()
30 This is standard-compliant behavior and may save costs in some
31 circumstances. However, it may be surprising to some client code
32 because c_str() and data() are const member functions (fbstring
33 uses the "mutable" storage class for its own state).
35 In order to appease client code that expects fbstring to be
36 zero-terminated at all times, if the preprocessor symbol
37 FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
38 i.e. it goes the extra mile to guarantee a '\0' is always planted
39 at the end of its data.
41 On the contrary, if the desire is to debug faulty client code that
42 unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
43 emphatically NOT a zero) at the end of each string if
44 FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
45 writes the '\0', of course.)
47 The preprocessor symbols FBSTRING_PERVERSE and
48 FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
49 enforced during preprocessing.
52 //#define FBSTRING_PERVERSE
53 //#define FBSTRING_CONSERVATIVE
55 #ifdef FBSTRING_PERVERSE
56 #ifdef FBSTRING_CONSERVATIVE
57 #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
61 // This file appears in two locations: inside fbcode and in the
62 // libstdc++ source code (when embedding fbstring as std::string).
63 // To aid in this schizophrenic use, two macros are defined in
65 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
66 // gate use inside fbcode v. libstdc++
67 #include <bits/c++config.h>
69 #ifdef _LIBSTDCXX_FBSTRING
71 #pragma GCC system_header
73 // Handle the cases where the fbcode version (folly/Malloc.h) is included
74 // either before or after this inclusion.
75 #ifdef FOLLY_MALLOC_H_
76 #undef FOLLY_MALLOC_H_
77 #include "basic_fbstring_malloc.h"
79 #include "basic_fbstring_malloc.h"
80 #undef FOLLY_MALLOC_H_
83 #else // !_LIBSTDCXX_FBSTRING
89 #include "folly/Traits.h"
90 #include "folly/Malloc.h"
91 #include "folly/Hash.h"
95 // We defined these here rather than including Likely.h to avoid
96 // redefinition errors when fbstring is imported into libstdc++.
97 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
98 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
102 #include <type_traits>
104 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
105 #pragma GCC diagnostic push
106 #pragma GCC diagnostic ignored "-Wshadow"
108 #ifdef _LIBSTDCXX_FBSTRING
109 namespace std _GLIBCXX_VISIBILITY(default) {
110 _GLIBCXX_BEGIN_NAMESPACE_VERSION
115 // Different versions of gcc/clang support different versions of
116 // the address sanitizer attribute. Unfortunately, this attribute
117 // has issues when inlining is used, so disable that as well.
118 #if defined(__clang__)
119 # if __has_feature(address_sanitizer)
120 # if __has_attribute(__no_address_safety_analysis__)
121 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
122 __attribute__((__no_address_safety_analysis__, __noinline__))
123 # elif __has_attribute(__no_sanitize_address__)
124 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
125 __attribute__((__no_sanitize_address__, __noinline__))
128 #elif defined (__GNUC__) && \
130 (__GNUC_MINOR__ >= 8) && \
132 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
133 __attribute__((__no_address_safety_analysis__, __noinline__))
135 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
136 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
139 namespace fbstring_detail {
141 template <class InIt, class OutIt>
144 typename std::iterator_traits<InIt>::difference_type n,
146 for (; n != 0; --n, ++b, ++d) {
147 assert((const void*)&*d != &*b);
153 template <class Pod, class T>
154 inline void pod_fill(Pod* b, Pod* e, T c) {
155 assert(b && e && b <= e);
156 /*static*/ if (sizeof(T) == 1) {
159 auto const ee = b + ((e - b) & ~7u);
160 for (; b != ee; b += 8) {
171 for (; b != e; ++b) {
178 * Lightly structured memcpy, simplifies copying PODs and introduces
179 * some asserts. Unfortunately using this function may cause
180 * measurable overhead (presumably because it adjusts from a begin/end
181 * convention to a pointer/size convention, so it does some extra
182 * arithmetic even though the caller might have done the inverse
183 * adaptation outside).
186 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
188 assert(d >= e || d + (e - b) <= b);
189 memcpy(d, b, (e - b) * sizeof(Pod));
193 * Lightly structured memmove, simplifies copying PODs and introduces
197 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
199 memmove(d, b, (e - b) * sizeof(*b));
202 } // namespace fbstring_detail
205 * Defines a special acquisition method for constructing fbstring
206 * objects. AcquireMallocatedString means that the user passes a
207 * pointer to a malloc-allocated string that the fbstring object will
210 enum class AcquireMallocatedString {};
213 * fbstring_core_model is a mock-up type that defines all required
214 * signatures of a fbstring core. The fbstring class itself uses such
215 * a core object to implement all of the numerous member functions
216 * required by the standard.
218 * If you want to define a new core, copy the definition below and
219 * implement the primitives. Then plug the core into basic_fbstring as
220 * a template argument.
222 template <class Char>
223 class fbstring_core_model {
225 fbstring_core_model();
226 fbstring_core_model(const fbstring_core_model &);
227 ~fbstring_core_model();
228 // Returns a pointer to string's buffer (currently only contiguous
229 // strings are supported). The pointer is guaranteed to be valid
230 // until the next call to a non-const member function.
231 const Char * data() const;
232 // Much like data(), except the string is prepared to support
233 // character-level changes. This call is a signal for
234 // e.g. reference-counted implementation to fork the data. The
235 // pointer is guaranteed to be valid until the next call to a
236 // non-const member function.
237 Char * mutable_data();
238 // Returns a pointer to string's buffer and guarantees that a
239 // readable '\0' lies right after the buffer. The pointer is
240 // guaranteed to be valid until the next call to a non-const member
242 const Char * c_str() const;
243 // Shrinks the string by delta characters. Asserts that delta <=
245 void shrink(size_t delta);
246 // Expands the string by delta characters (i.e. after this call
247 // size() will report the old size() plus delta) but without
248 // initializing the expanded region. Returns a pointer to the memory
249 // to be initialized (the beginning of the expanded portion). The
250 // caller is expected to fill the expanded area appropriately.
251 Char* expand_noinit(size_t delta);
252 // Expands the string by one character and sets the last character
254 void push_back(Char c);
255 // Returns the string's size.
257 // Returns the string's capacity, i.e. maximum size that the string
258 // can grow to without reallocation. Note that for reference counted
259 // strings that's technically a lie - even assigning characters
260 // within the existing size would cause a reallocation.
261 size_t capacity() const;
262 // Returns true if the data underlying the string is actually shared
263 // across multiple strings (in a refcounted fashion).
264 bool isShared() const;
265 // Makes sure that at least minCapacity characters are available for
266 // the string without reallocation. For reference-counted strings,
267 // it should fork the data even if minCapacity < size().
268 void reserve(size_t minCapacity);
271 fbstring_core_model& operator=(const fbstring_core_model &);
276 * gcc-4.7 throws what appears to be some false positive uninitialized
277 * warnings for the members of the MediumLarge struct. So, mute them here.
279 #if defined(__GNUC__) && !defined(__clang__)
280 # pragma GCC diagnostic push
281 # pragma GCC diagnostic ignored "-Wuninitialized"
285 * This is the core of the string. The code should work on 32- and
286 * 64-bit architectures and with any Char size. Porting to big endian
287 * architectures would require some changes.
289 * The storage is selected as follows (assuming we store one-byte
290 * characters on a 64-bit machine): (a) "small" strings between 0 and
291 * 23 chars are stored in-situ without allocation (the rightmost byte
292 * stores the size); (b) "medium" strings from 24 through 254 chars
293 * are stored in malloc-allocated memory that is copied eagerly; (c)
294 * "large" strings of 255 chars and above are stored in a similar
295 * structure as medium arrays, except that the string is
296 * reference-counted and copied lazily. the reference count is
297 * allocated right before the character array.
299 * The discriminator between these three strategies sits in the two
300 * most significant bits of the rightmost char of the storage. If
301 * neither is set, then the string is small (and its length sits in
302 * the lower-order bits of that rightmost character). If the MSb is
303 * set, the string is medium width. If the second MSb is set, then the
306 template <class Char> class fbstring_core {
308 fbstring_core() noexcept {
309 // Only initialize the tag, will set the MSBs (i.e. the small
310 // string size) to zero too
311 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
312 // or: setSmallSize(0);
314 assert(category() == isSmall && size() == 0);
317 fbstring_core(const fbstring_core & rhs) {
318 assert(&rhs != this);
319 // Simplest case first: small strings are bitblitted
320 if (rhs.category() == isSmall) {
321 assert(offsetof(MediumLarge, data_) == 0);
322 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
323 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
324 const size_t size = rhs.smallSize();
326 ml_.capacity_ = rhs.ml_.capacity_;
329 // Just write the whole thing, don't look at details. In
330 // particular we need to copy capacity anyway because we want
331 // to set the size (don't forget that the last character,
332 // which stores a short string's length, is shared with the
333 // ml_.capacity field).
336 assert(category() == isSmall && this->size() == rhs.size());
337 } else if (rhs.category() == isLarge) {
338 // Large strings are just refcounted
340 RefCounted::incrementRefs(ml_.data_);
341 assert(category() == isLarge && size() == rhs.size());
343 // Medium strings are copied eagerly. Don't forget to allocate
344 // one extra Char for the null terminator.
345 auto const allocSize =
346 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
347 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
348 fbstring_detail::pod_copy(rhs.ml_.data_,
350 rhs.ml_.data_ + rhs.ml_.size_ + 1,
352 // No need for writeTerminator() here, we copied one extra
353 // element just above.
354 ml_.size_ = rhs.ml_.size_;
355 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
356 assert(category() == isMedium);
358 assert(size() == rhs.size());
359 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
362 fbstring_core(fbstring_core&& goner) noexcept {
363 if (goner.category() == isSmall) {
364 // Just copy, leave the goner in peace
365 new(this) fbstring_core(goner.small_, goner.smallSize());
369 // Clean goner's carcass
370 goner.setSmallSize(0);
374 // NOTE(agallagher): The word-aligned copy path copies bytes which are
375 // outside the range of the string, and makes address sanitizer unhappy,
376 // so just disable it on this function.
377 fbstring_core(const Char *const data, const size_t size)
378 FBSTRING_DISABLE_ADDRESS_SANITIZER {
379 // Simplest case first: small strings are bitblitted
380 if (size <= maxSmallSize) {
381 // Layout is: Char* data_, size_t size_, size_t capacity_
382 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
383 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
384 // sizeof(size_t) must be a power of 2
385 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
387 // If data is aligned, use fast word-wise copying. Otherwise,
388 // use conservative memcpy.
389 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
390 fbstring_detail::pod_copy(data, data + size, small_);
392 // Copy one word (64 bits) at a time
393 const size_t byteSize = size * sizeof(Char);
394 if (byteSize > 2 * sizeof(size_t)) {
396 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
398 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
400 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
401 } else if (byteSize > sizeof(size_t)) {
404 } else if (size > 0) {
410 } else if (size <= maxMediumSize) {
411 // Medium strings are allocated normally. Don't forget to
412 // allocate one extra Char for the terminating null.
413 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
414 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
415 fbstring_detail::pod_copy(data, data + size, ml_.data_);
417 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
419 // Large strings are allocated differently
420 size_t effectiveCapacity = size;
421 auto const newRC = RefCounted::create(data, & effectiveCapacity);
422 ml_.data_ = newRC->data_;
424 ml_.capacity_ = effectiveCapacity | isLarge;
427 assert(this->size() == size);
428 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
431 ~fbstring_core() noexcept {
432 auto const c = category();
440 RefCounted::decrementRefs(ml_.data_);
443 // Snatches a previously mallocated string. The parameter "size"
444 // is the size of the string, and the parameter "capacity" is the size
445 // of the mallocated block. The string must be \0-terminated, so
446 // data[size] == '\0' and capacity >= size + 1.
448 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
449 // "size", and pass 3 as "capacity".
450 fbstring_core(Char *const data, const size_t size,
451 const size_t capacity,
452 AcquireMallocatedString) {
454 assert(capacity > size);
455 assert(data[size] == '\0');
456 // Use the medium string storage
459 ml_.capacity_ = capacity | isMedium;
461 // No need for the memory
467 // swap below doesn't test whether &rhs == this (and instead
468 // potentially does extra work) on the premise that the rarity of
469 // that situation actually makes the check more expensive than is
471 void swap(fbstring_core & rhs) {
477 // In C++11 data() and c_str() are 100% equivalent.
478 const Char * data() const {
482 Char * mutable_data() {
483 auto const c = category();
487 assert(c == isMedium || c == isLarge);
488 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
490 size_t effectiveCapacity = ml_.capacity();
491 auto const newRC = RefCounted::create(& effectiveCapacity);
492 // If this fails, someone placed the wrong capacity in an
494 assert(effectiveCapacity >= ml_.capacity());
495 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
497 RefCounted::decrementRefs(ml_.data_);
498 ml_.data_ = newRC->data_;
499 // No need to call writeTerminator(), we have + 1 above.
504 const Char * c_str() const {
505 auto const c = category();
506 #ifdef FBSTRING_PERVERSE
508 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
509 || small_[smallSize()] == '\0');
510 small_[smallSize()] = '\0';
513 assert(c == isMedium || c == isLarge);
514 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
515 ml_.data_[ml_.size_] = '\0';
516 #elif defined(FBSTRING_CONSERVATIVE)
518 assert(small_[smallSize()] == '\0');
521 assert(c == isMedium || c == isLarge);
522 assert(ml_.data_[ml_.size_] == '\0');
525 small_[smallSize()] = '\0';
528 assert(c == isMedium || c == isLarge);
529 ml_.data_[ml_.size_] = '\0';
534 void shrink(const size_t delta) {
535 if (category() == isSmall) {
536 // Check for underflow
537 assert(delta <= smallSize());
538 setSmallSize(smallSize() - delta);
539 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
540 // Medium strings and unique large strings need no special
542 assert(ml_.size_ >= delta);
545 assert(ml_.size_ >= delta);
546 // Shared large string, must make unique. This is because of the
547 // durn terminator must be written, which may trample the shared
550 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
552 // No need to write the terminator.
558 void reserve(size_t minCapacity) {
559 if (category() == isLarge) {
561 if (RefCounted::refs(ml_.data_) > 1) {
562 // We must make it unique regardless; in-place reallocation is
563 // useless if the string is shared. In order to not surprise
564 // people, reserve the new block at current capacity or
565 // more. That way, a string's capacity never shrinks after a
567 minCapacity = std::max(minCapacity, ml_.capacity());
568 auto const newRC = RefCounted::create(& minCapacity);
569 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
571 // Done with the old data. No need to call writeTerminator(),
572 // we have + 1 above.
573 RefCounted::decrementRefs(ml_.data_);
574 ml_.data_ = newRC->data_;
575 ml_.capacity_ = minCapacity | isLarge;
576 // size remains unchanged
578 // String is not shared, so let's try to realloc (if needed)
579 if (minCapacity > ml_.capacity()) {
580 // Asking for more memory
582 RefCounted::reallocate(ml_.data_, ml_.size_,
583 ml_.capacity(), minCapacity);
584 ml_.data_ = newRC->data_;
585 ml_.capacity_ = minCapacity | isLarge;
588 assert(capacity() >= minCapacity);
590 } else if (category() == isMedium) {
591 // String is not shared
592 if (minCapacity <= ml_.capacity()) {
593 return; // nothing to do, there's enough room
595 if (minCapacity <= maxMediumSize) {
596 // Keep the string at medium size. Don't forget to allocate
597 // one extra Char for the terminating null.
598 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
599 ml_.data_ = static_cast<Char *>(
602 ml_.size_ * sizeof(Char),
603 ml_.capacity() * sizeof(Char),
606 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
608 // Conversion from medium to large string
609 fbstring_core nascent;
610 // Will recurse to another branch of this function
611 nascent.reserve(minCapacity);
612 nascent.ml_.size_ = ml_.size_;
613 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
617 assert(capacity() >= minCapacity);
620 assert(category() == isSmall);
621 if (minCapacity > maxMediumSize) {
623 auto const newRC = RefCounted::create(& minCapacity);
624 auto const size = smallSize();
625 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
626 // No need for writeTerminator(), we wrote it above with + 1.
627 ml_.data_ = newRC->data_;
629 ml_.capacity_ = minCapacity | isLarge;
630 assert(capacity() >= minCapacity);
631 } else if (minCapacity > maxSmallSize) {
633 // Don't forget to allocate one extra Char for the terminating null
634 auto const allocSizeBytes =
635 goodMallocSize((1 + minCapacity) * sizeof(Char));
636 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
637 auto const size = smallSize();
638 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
639 // No need for writeTerminator(), we wrote it above with + 1.
642 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
645 // Nothing to do, everything stays put
648 assert(capacity() >= minCapacity);
651 Char * expand_noinit(const size_t delta) {
652 // Strategy is simple: make room, then change size
653 assert(capacity() >= size());
655 if (category() == isSmall) {
658 if (newSz <= maxSmallSize) {
666 newSz = ml_.size_ + delta;
667 if (newSz > capacity()) {
671 assert(capacity() >= newSz);
672 // Category can't be small - we took care of that above
673 assert(category() == isMedium || category() == isLarge);
676 assert(size() == newSz);
677 return ml_.data_ + sz;
680 void push_back(Char c) {
681 assert(capacity() >= size());
683 if (category() == isSmall) {
685 if (sz < maxSmallSize) {
686 setSmallSize(sz + 1);
691 reserve(maxSmallSize * 2);
694 if (sz == capacity()) { // always true for isShared()
695 reserve(sz * 3 / 2); // ensures not shared
699 assert(capacity() >= sz + 1);
700 // Category can't be small - we took care of that above
701 assert(category() == isMedium || category() == isLarge);
707 size_t size() const {
708 return category() == isSmall ? smallSize() : ml_.size_;
711 size_t capacity() const {
712 switch (category()) {
716 // For large-sized strings, a multi-referenced chunk has no
717 // available capacity. This is because any attempt to append
718 // data would trigger a new allocation.
719 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
722 return ml_.capacity();
725 bool isShared() const {
726 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
729 #ifdef FBSTRING_PERVERSE
730 enum { TERMINATOR = '^' };
732 enum { TERMINATOR = '\0' };
735 void writeTerminator() {
736 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
737 if (category() == isSmall) {
738 const auto s = smallSize();
739 if (s != maxSmallSize) {
740 small_[s] = TERMINATOR;
743 ml_.data_[ml_.size_] = TERMINATOR;
750 fbstring_core & operator=(const fbstring_core & rhs);
757 size_t capacity() const {
758 return capacity_ & capacityExtractMask;
763 std::atomic<size_t> refCount_;
766 static RefCounted * fromData(Char * p) {
767 return static_cast<RefCounted*>(
769 static_cast<unsigned char*>(static_cast<void*>(p))
770 - sizeof(refCount_)));
773 static size_t refs(Char * p) {
774 return fromData(p)->refCount_.load(std::memory_order_acquire);
777 static void incrementRefs(Char * p) {
778 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
781 static void decrementRefs(Char * p) {
782 auto const dis = fromData(p);
783 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
790 static RefCounted * create(size_t * size) {
791 // Don't forget to allocate one extra Char for the terminating
792 // null. In this case, however, one Char is already part of the
794 const size_t allocSize = goodMallocSize(
795 sizeof(RefCounted) + *size * sizeof(Char));
796 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
797 result->refCount_.store(1, std::memory_order_release);
798 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
802 static RefCounted * create(const Char * data, size_t * size) {
803 const size_t effectiveSize = *size;
804 auto result = create(size);
805 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
809 static RefCounted * reallocate(Char *const data,
810 const size_t currentSize,
811 const size_t currentCapacity,
812 const size_t newCapacity) {
813 assert(newCapacity > 0 && newCapacity > currentSize);
814 auto const dis = fromData(data);
815 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
816 // Don't forget to allocate one extra Char for the terminating
817 // null. In this case, however, one Char is already part of the
819 auto result = static_cast<RefCounted*>(
821 sizeof(RefCounted) + currentSize * sizeof(Char),
822 sizeof(RefCounted) + currentCapacity * sizeof(Char),
823 sizeof(RefCounted) + newCapacity * sizeof(Char)));
824 assert(result->refCount_.load(std::memory_order_acquire) == 1);
830 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
831 mutable MediumLarge ml_;
835 lastChar = sizeof(MediumLarge) - 1,
836 maxSmallSize = lastChar / sizeof(Char),
837 maxMediumSize = 254 / sizeof(Char), // coincides with the small
838 // bin size in dlmalloc
839 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
840 capacityExtractMask = ~categoryExtractMask,
842 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
843 "Corrupt memory layout for fbstring.");
847 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
848 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
851 Category category() const {
852 // Assumes little endian
853 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
856 size_t smallSize() const {
857 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
858 return static_cast<size_t>(maxSmallSize)
859 - static_cast<size_t>(small_[maxSmallSize]);
862 void setSmallSize(size_t s) {
863 // Warning: this should work with uninitialized strings too,
864 // so don't assume anything about the previous value of
865 // small_[maxSmallSize].
866 assert(s <= maxSmallSize);
867 small_[maxSmallSize] = maxSmallSize - s;
871 #if defined(__GNUC__) && !defined(__clang__)
872 # pragma GCC diagnostic pop
875 #ifndef _LIBSTDCXX_FBSTRING
877 * Dummy fbstring core that uses an actual std::string. This doesn't
878 * make any sense - it's just for testing purposes.
880 template <class Char>
881 class dummy_fbstring_core {
883 dummy_fbstring_core() {
885 dummy_fbstring_core(const dummy_fbstring_core& another)
886 : backend_(another.backend_) {
888 dummy_fbstring_core(const Char * s, size_t n)
891 void swap(dummy_fbstring_core & rhs) {
892 backend_.swap(rhs.backend_);
894 const Char * data() const {
895 return backend_.data();
897 Char * mutable_data() {
898 //assert(!backend_.empty());
899 return &*backend_.begin();
901 void shrink(size_t delta) {
902 assert(delta <= size());
903 backend_.resize(size() - delta);
905 Char * expand_noinit(size_t delta) {
906 auto const sz = size();
907 backend_.resize(size() + delta);
908 return backend_.data() + sz;
910 void push_back(Char c) {
911 backend_.push_back(c);
913 size_t size() const {
914 return backend_.size();
916 size_t capacity() const {
917 return backend_.capacity();
919 bool isShared() const {
922 void reserve(size_t minCapacity) {
923 backend_.reserve(minCapacity);
927 std::basic_string<Char> backend_;
929 #endif // !_LIBSTDCXX_FBSTRING
932 * This is the basic_string replacement. For conformity,
933 * basic_fbstring takes the same template parameters, plus the last
934 * one which is the core.
936 #ifdef _LIBSTDCXX_FBSTRING
937 template <typename E, class T, class A, class Storage>
939 template <typename E,
940 class T = std::char_traits<E>,
941 class A = std::allocator<E>,
942 class Storage = fbstring_core<E> >
944 class basic_fbstring {
948 void (*throw_exc)(const char*),
950 if (!condition) throw_exc(msg);
953 bool isSane() const {
956 empty() == (size() == 0) &&
957 empty() == (begin() == end()) &&
958 size() <= max_size() &&
959 capacity() <= max_size() &&
960 size() <= capacity() &&
961 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
965 friend struct Invariant;
968 explicit Invariant(const basic_fbstring& s) : s_(s) {
975 const basic_fbstring& s_;
977 explicit Invariant(const basic_fbstring&) {}
979 Invariant& operator=(const Invariant&);
984 typedef T traits_type;
985 typedef typename traits_type::char_type value_type;
986 typedef A allocator_type;
987 typedef typename A::size_type size_type;
988 typedef typename A::difference_type difference_type;
990 typedef typename A::reference reference;
991 typedef typename A::const_reference const_reference;
992 typedef typename A::pointer pointer;
993 typedef typename A::const_pointer const_pointer;
996 typedef const E* const_iterator;
997 typedef std::reverse_iterator<iterator
998 #ifdef NO_ITERATOR_TRAITS
1002 typedef std::reverse_iterator<const_iterator
1003 #ifdef NO_ITERATOR_TRAITS
1006 > const_reverse_iterator;
1008 static const size_type npos; // = size_type(-1)
1011 static void procrustes(size_type& n, size_type nmax) {
1012 if (n > nmax) n = nmax;
1016 // C++11 21.4.2 construct/copy/destroy
1017 explicit basic_fbstring(const A& a = A()) noexcept {
1020 basic_fbstring(const basic_fbstring& str)
1021 : store_(str.store_) {
1025 basic_fbstring(basic_fbstring&& goner) noexcept
1026 : store_(std::move(goner.store_)) {
1029 #ifndef _LIBSTDCXX_FBSTRING
1030 // This is defined for compatibility with std::string
1031 /* implicit */ basic_fbstring(const std::string& str)
1032 : store_(str.data(), str.size()) {
1036 basic_fbstring(const basic_fbstring& str, size_type pos,
1037 size_type n = npos, const A& a = A()) {
1038 assign(str, pos, n);
1041 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1042 : store_(s, s ? traits_type::length(s) : ({
1043 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1044 err += ": null pointer initializer not valid";
1045 std::__throw_logic_error(err.c_str());
1050 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1054 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1055 auto const data = store_.expand_noinit(n);
1056 fbstring_detail::pod_fill(data, data + n, c);
1057 store_.writeTerminator();
1060 template <class InIt>
1061 basic_fbstring(InIt begin, InIt end,
1062 typename std::enable_if<
1063 !std::is_same<typename std::remove_const<InIt>::type,
1064 value_type*>::value, const A>::type & a = A()) {
1068 // Specialization for const char*, const char*
1069 basic_fbstring(const value_type* b, const value_type* e)
1070 : store_(b, e - b) {
1073 // Nonstandard constructor
1074 basic_fbstring(value_type *s, size_type n, size_type c,
1075 AcquireMallocatedString a)
1076 : store_(s, n, c, a) {
1079 // Construction from initialization list
1080 basic_fbstring(std::initializer_list<value_type> il) {
1081 assign(il.begin(), il.end());
1084 ~basic_fbstring() noexcept {
1087 basic_fbstring& operator=(const basic_fbstring& lhs) {
1088 if (FBSTRING_UNLIKELY(&lhs == this)) {
1091 auto const oldSize = size();
1092 auto const srcSize = lhs.size();
1093 if (capacity() >= srcSize && !store_.isShared()) {
1094 // great, just copy the contents
1095 if (oldSize < srcSize)
1096 store_.expand_noinit(srcSize - oldSize);
1098 store_.shrink(oldSize - srcSize);
1099 assert(size() == srcSize);
1100 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1101 store_.writeTerminator();
1103 // need to reallocate, so we may as well create a brand new string
1104 basic_fbstring(lhs).swap(*this);
1110 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1111 if (FBSTRING_UNLIKELY(&goner == this)) {
1112 // Compatibility with std::basic_string<>,
1113 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1116 // No need of this anymore
1117 this->~basic_fbstring();
1118 // Move the goner into this
1119 new(&store_) fbstring_core<E>(std::move(goner.store_));
1123 #ifndef _LIBSTDCXX_FBSTRING
1124 // Compatibility with std::string
1125 basic_fbstring & operator=(const std::string & rhs) {
1126 return assign(rhs.data(), rhs.size());
1129 // Compatibility with std::string
1130 std::string toStdString() const {
1131 return std::string(data(), size());
1134 // A lot of code in fbcode still uses this method, so keep it here for now.
1135 const basic_fbstring& toStdString() const {
1140 basic_fbstring& operator=(const value_type* s) {
1144 basic_fbstring& operator=(value_type c) {
1146 store_.expand_noinit(1);
1147 } else if (store_.isShared()) {
1148 basic_fbstring(1, c).swap(*this);
1151 store_.shrink(size() - 1);
1153 *store_.mutable_data() = c;
1154 store_.writeTerminator();
1158 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1159 return assign(il.begin(), il.end());
1162 // C++11 21.4.3 iterators:
1163 iterator begin() { return store_.mutable_data(); }
1165 const_iterator begin() const { return store_.data(); }
1167 const_iterator cbegin() const { return begin(); }
1170 return store_.mutable_data() + store_.size();
1173 const_iterator end() const {
1174 return store_.data() + store_.size();
1177 const_iterator cend() const { return end(); }
1179 reverse_iterator rbegin() {
1180 return reverse_iterator(end());
1183 const_reverse_iterator rbegin() const {
1184 return const_reverse_iterator(end());
1187 const_reverse_iterator crbegin() const { return rbegin(); }
1189 reverse_iterator rend() {
1190 return reverse_iterator(begin());
1193 const_reverse_iterator rend() const {
1194 return const_reverse_iterator(begin());
1197 const_reverse_iterator crend() const { return rend(); }
1200 // C++11 21.4.5, element access:
1201 const value_type& front() const { return *begin(); }
1202 const value_type& back() const {
1204 // Should be begin()[size() - 1], but that branches twice
1205 return *(end() - 1);
1207 value_type& front() { return *begin(); }
1208 value_type& back() {
1210 // Should be begin()[size() - 1], but that branches twice
1211 return *(end() - 1);
1218 // C++11 21.4.4 capacity:
1219 size_type size() const { return store_.size(); }
1221 size_type length() const { return size(); }
1223 size_type max_size() const {
1224 return std::numeric_limits<size_type>::max();
1227 void resize(const size_type n, const value_type c = value_type()) {
1228 auto size = this->size();
1230 store_.shrink(size - n);
1232 // Do this in two steps to minimize slack memory copied (see
1234 auto const capacity = this->capacity();
1235 assert(capacity >= size);
1236 if (size < capacity) {
1237 auto delta = std::min(n, capacity) - size;
1238 store_.expand_noinit(delta);
1239 fbstring_detail::pod_fill(begin() + size, end(), c);
1242 store_.writeTerminator();
1247 auto const delta = n - size;
1248 store_.expand_noinit(delta);
1249 fbstring_detail::pod_fill(end() - delta, end(), c);
1250 store_.writeTerminator();
1252 assert(this->size() == n);
1255 size_type capacity() const { return store_.capacity(); }
1257 void reserve(size_type res_arg = 0) {
1258 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1259 store_.reserve(res_arg);
1262 void shrink_to_fit() {
1263 // Shrink only if slack memory is sufficiently large
1264 if (capacity() < size() * 3 / 2) {
1267 basic_fbstring(cbegin(), cend()).swap(*this);
1270 void clear() { resize(0); }
1272 bool empty() const { return size() == 0; }
1274 // C++11 21.4.5 element access:
1275 const_reference operator[](size_type pos) const {
1276 return *(c_str() + pos);
1279 reference operator[](size_type pos) {
1280 if (pos == size()) {
1281 // Just call c_str() to make sure '\0' is present
1284 return *(begin() + pos);
1287 const_reference at(size_type n) const {
1288 enforce(n <= size(), std::__throw_out_of_range, "");
1292 reference at(size_type n) {
1293 enforce(n < size(), std::__throw_out_of_range, "");
1297 // C++11 21.4.6 modifiers:
1298 basic_fbstring& operator+=(const basic_fbstring& str) {
1302 basic_fbstring& operator+=(const value_type* s) {
1306 basic_fbstring& operator+=(const value_type c) {
1311 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1316 basic_fbstring& append(const basic_fbstring& str) {
1318 auto desiredSize = size() + str.size();
1320 append(str.data(), str.size());
1321 assert(size() == desiredSize);
1325 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1327 const size_type sz = str.size();
1328 enforce(pos <= sz, std::__throw_out_of_range, "");
1329 procrustes(n, sz - pos);
1330 return append(str.data() + pos, n);
1333 basic_fbstring& append(const value_type* s, size_type n) {
1335 Invariant checker(*this);
1338 if (FBSTRING_UNLIKELY(!n)) {
1339 // Unlikely but must be done
1342 auto const oldSize = size();
1343 auto const oldData = data();
1344 // Check for aliasing (rare). We could use "<=" here but in theory
1345 // those do not work for pointers unless the pointers point to
1346 // elements in the same array. For that reason we use
1347 // std::less_equal, which is guaranteed to offer a total order
1348 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1350 std::less_equal<const value_type*> le;
1351 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1352 assert(le(s + n, oldData + oldSize));
1353 const size_type offset = s - oldData;
1354 store_.reserve(oldSize + n);
1355 // Restore the source
1356 s = data() + offset;
1358 // Warning! Repeated appends with short strings may actually incur
1359 // practically quadratic performance. Avoid that by pushing back
1360 // the first character (which ensures exponential growth) and then
1361 // appending the rest normally. Worst case the append may incur a
1362 // second allocation but that will be rare.
1365 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1366 assert(size() == oldSize + n + 1);
1370 basic_fbstring& append(const value_type* s) {
1371 return append(s, traits_type::length(s));
1374 basic_fbstring& append(size_type n, value_type c) {
1375 resize(size() + n, c);
1379 template<class InputIterator>
1380 basic_fbstring& append(InputIterator first, InputIterator last) {
1381 insert(end(), first, last);
1385 basic_fbstring& append(std::initializer_list<value_type> il) {
1386 return append(il.begin(), il.end());
1389 void push_back(const value_type c) { // primitive
1390 store_.push_back(c);
1393 basic_fbstring& assign(const basic_fbstring& str) {
1394 if (&str == this) return *this;
1395 return assign(str.data(), str.size());
1398 basic_fbstring& assign(basic_fbstring&& str) {
1399 return *this = std::move(str);
1402 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1404 const size_type sz = str.size();
1405 enforce(pos <= sz, std::__throw_out_of_range, "");
1406 procrustes(n, sz - pos);
1407 return assign(str.data() + pos, n);
1410 basic_fbstring& assign(const value_type* s, const size_type n) {
1411 Invariant checker(*this);
1414 std::copy(s, s + n, begin());
1416 assert(size() == n);
1418 const value_type *const s2 = s + size();
1419 std::copy(s, s2, begin());
1420 append(s2, n - size());
1421 assert(size() == n);
1423 store_.writeTerminator();
1424 assert(size() == n);
1428 basic_fbstring& assign(const value_type* s) {
1429 return assign(s, traits_type::length(s));
1432 basic_fbstring& assign(std::initializer_list<value_type> il) {
1433 return assign(il.begin(), il.end());
1436 template <class ItOrLength, class ItOrChar>
1437 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1438 return replace(begin(), end(), first_or_n, last_or_c);
1441 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1442 return insert(pos1, str.data(), str.size());
1445 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1446 size_type pos2, size_type n) {
1447 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1448 procrustes(n, str.length() - pos2);
1449 return insert(pos1, str.data() + pos2, n);
1452 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1453 enforce(pos <= length(), std::__throw_out_of_range, "");
1454 insert(begin() + pos, s, s + n);
1458 basic_fbstring& insert(size_type pos, const value_type* s) {
1459 return insert(pos, s, traits_type::length(s));
1462 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1463 enforce(pos <= length(), std::__throw_out_of_range, "");
1464 insert(begin() + pos, n, c);
1468 iterator insert(const_iterator p, const value_type c) {
1469 const size_type pos = p - begin();
1471 return begin() + pos;
1475 template <int i> class Selector {};
1477 iterator insertImplDiscr(const_iterator p,
1478 size_type n, value_type c, Selector<1>) {
1479 Invariant checker(*this);
1481 auto const pos = p - begin();
1482 assert(p >= begin() && p <= end());
1483 if (capacity() - size() < n) {
1484 const size_type sz = p - begin();
1485 reserve(size() + n);
1488 const iterator oldEnd = end();
1489 if (n < size_type(oldEnd - p)) {
1490 append(oldEnd - n, oldEnd);
1492 // reverse_iterator(oldEnd - n),
1493 // reverse_iterator(p),
1494 // reverse_iterator(oldEnd));
1495 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1497 std::fill(begin() + pos, begin() + pos + n, c);
1499 append(n - (end() - p), c);
1500 append(iterator(p), oldEnd);
1501 std::fill(iterator(p), oldEnd, c);
1503 store_.writeTerminator();
1504 return begin() + pos;
1507 template<class InputIter>
1508 iterator insertImplDiscr(const_iterator i,
1509 InputIter b, InputIter e, Selector<0>) {
1510 return insertImpl(i, b, e,
1511 typename std::iterator_traits<InputIter>::iterator_category());
1514 template <class FwdIterator>
1515 iterator insertImpl(const_iterator i,
1516 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1517 Invariant checker(*this);
1519 const size_type pos = i - begin();
1520 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1521 std::distance(s1, s2);
1523 using namespace fbstring_detail;
1524 assert(pos <= size());
1526 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1527 capacity() - size();
1529 // realloc the string
1530 reserve(size() + n2);
1533 if (pos + n2 <= size()) {
1534 const iterator tailBegin = end() - n2;
1535 store_.expand_noinit(n2);
1536 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1537 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1538 reverse_iterator(tailBegin + n2));
1539 std::copy(s1, s2, begin() + pos);
1542 const size_type old_size = size();
1543 std::advance(t, old_size - pos);
1544 const size_t newElems = std::distance(t, s2);
1545 store_.expand_noinit(n2);
1546 std::copy(t, s2, begin() + old_size);
1547 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1548 begin() + old_size + newElems);
1549 std::copy(s1, t, begin() + pos);
1551 store_.writeTerminator();
1552 return begin() + pos;
1555 template <class InputIterator>
1556 iterator insertImpl(const_iterator i,
1557 InputIterator b, InputIterator e,
1558 std::input_iterator_tag) {
1559 const auto pos = i - begin();
1560 basic_fbstring temp(begin(), i);
1561 for (; b != e; ++b) {
1564 temp.append(i, cend());
1566 return begin() + pos;
1570 template <class ItOrLength, class ItOrChar>
1571 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1572 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1573 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1576 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1577 return insert(p, il.begin(), il.end());
1580 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1581 Invariant checker(*this);
1583 enforce(pos <= length(), std::__throw_out_of_range, "");
1584 procrustes(n, length() - pos);
1585 std::copy(begin() + pos + n, end(), begin() + pos);
1586 resize(length() - n);
1590 iterator erase(iterator position) {
1591 const size_type pos(position - begin());
1592 enforce(pos <= size(), std::__throw_out_of_range, "");
1594 return begin() + pos;
1597 iterator erase(iterator first, iterator last) {
1598 const size_type pos(first - begin());
1599 erase(pos, last - first);
1600 return begin() + pos;
1603 // Replaces at most n1 chars of *this, starting with pos1 with the
1605 basic_fbstring& replace(size_type pos1, size_type n1,
1606 const basic_fbstring& str) {
1607 return replace(pos1, n1, str.data(), str.size());
1610 // Replaces at most n1 chars of *this, starting with pos1,
1611 // with at most n2 chars of str starting with pos2
1612 basic_fbstring& replace(size_type pos1, size_type n1,
1613 const basic_fbstring& str,
1614 size_type pos2, size_type n2) {
1615 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1616 return replace(pos1, n1, str.data() + pos2,
1617 std::min(n2, str.size() - pos2));
1620 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1621 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1622 return replace(pos, n1, s, traits_type::length(s));
1625 // Replaces at most n1 chars of *this, starting with pos, with n2
1628 // consolidated with
1630 // Replaces at most n1 chars of *this, starting with pos, with at
1631 // most n2 chars of str. str must have at least n2 chars.
1632 template <class StrOrLength, class NumOrChar>
1633 basic_fbstring& replace(size_type pos, size_type n1,
1634 StrOrLength s_or_n2, NumOrChar n_or_c) {
1635 Invariant checker(*this);
1637 enforce(pos <= size(), std::__throw_out_of_range, "");
1638 procrustes(n1, length() - pos);
1639 const iterator b = begin() + pos;
1640 return replace(b, b + n1, s_or_n2, n_or_c);
1643 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1644 return replace(i1, i2, str.data(), str.length());
1647 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1648 return replace(i1, i2, s, traits_type::length(s));
1652 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1653 const value_type* s, size_type n,
1656 assert(begin() <= i1 && i1 <= end());
1657 assert(begin() <= i2 && i2 <= end());
1658 return replace(i1, i2, s, s + n);
1661 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1662 size_type n2, value_type c, Selector<1>) {
1663 const size_type n1 = i2 - i1;
1665 std::fill(i1, i1 + n2, c);
1668 std::fill(i1, i2, c);
1669 insert(i2, n2 - n1, c);
1675 template <class InputIter>
1676 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1677 InputIter b, InputIter e,
1679 replaceImpl(i1, i2, b, e,
1680 typename std::iterator_traits<InputIter>::iterator_category());
1685 template <class FwdIterator, class P>
1686 bool replaceAliased(iterator i1, iterator i2,
1687 FwdIterator s1, FwdIterator s2, P*) {
1691 template <class FwdIterator>
1692 bool replaceAliased(iterator i1, iterator i2,
1693 FwdIterator s1, FwdIterator s2, value_type*) {
1694 static const std::less_equal<const value_type*> le =
1695 std::less_equal<const value_type*>();
1696 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1700 // Aliased replace, copy to new string
1701 basic_fbstring temp;
1702 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1703 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1709 template <class FwdIterator>
1710 void replaceImpl(iterator i1, iterator i2,
1711 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1712 Invariant checker(*this);
1715 // Handle aliased replace
1716 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1720 auto const n1 = i2 - i1;
1722 auto const n2 = std::distance(s1, s2);
1727 std::copy(s1, s2, i1);
1731 fbstring_detail::copy_n(s1, n1, i1);
1732 std::advance(s1, n1);
1738 template <class InputIterator>
1739 void replaceImpl(iterator i1, iterator i2,
1740 InputIterator b, InputIterator e, std::input_iterator_tag) {
1741 basic_fbstring temp(begin(), i1);
1742 temp.append(b, e).append(i2, end());
1747 template <class T1, class T2>
1748 basic_fbstring& replace(iterator i1, iterator i2,
1749 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1751 num1 = std::numeric_limits<T1>::is_specialized,
1752 num2 = std::numeric_limits<T2>::is_specialized;
1753 return replaceImplDiscr(
1754 i1, i2, first_or_n_or_s, last_or_c_or_n,
1755 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1758 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1759 enforce(pos <= size(), std::__throw_out_of_range, "");
1760 procrustes(n, size() - pos);
1762 fbstring_detail::pod_copy(
1769 void swap(basic_fbstring& rhs) {
1770 store_.swap(rhs.store_);
1773 const value_type* c_str() const {
1774 return store_.c_str();
1777 const value_type* data() const { return c_str(); }
1779 allocator_type get_allocator() const {
1780 return allocator_type();
1783 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1784 return find(str.data(), pos, str.length());
1787 size_type find(const value_type* needle, const size_type pos,
1788 const size_type nsize) const {
1789 if (!nsize) return pos;
1790 auto const size = this->size();
1791 if (nsize + pos > size) return npos;
1792 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1793 // the last characters first
1794 auto const haystack = data();
1795 auto const nsize_1 = nsize - 1;
1796 auto const lastNeedle = needle[nsize_1];
1798 // Boyer-Moore skip value for the last char in the needle. Zero is
1799 // not a valid value; skip will be computed the first time it's
1803 const E * i = haystack + pos;
1804 auto iEnd = haystack + size - nsize_1;
1807 // Boyer-Moore: match the last element in the needle
1808 while (i[nsize_1] != lastNeedle) {
1814 // Here we know that the last char matches
1815 // Continue in pedestrian mode
1816 for (size_t j = 0; ; ) {
1818 if (i[j] != needle[j]) {
1819 // Not found, we can skip
1820 // Compute the skip value lazily
1823 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1830 // Check if done searching
1833 return i - haystack;
1840 size_type find(const value_type* s, size_type pos = 0) const {
1841 return find(s, pos, traits_type::length(s));
1844 size_type find (value_type c, size_type pos = 0) const {
1845 return find(&c, pos, 1);
1848 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1849 return rfind(str.data(), pos, str.length());
1852 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1853 if (n > length()) return npos;
1854 pos = std::min(pos, length() - n);
1855 if (n == 0) return pos;
1857 const_iterator i(begin() + pos);
1859 if (traits_type::eq(*i, *s)
1860 && traits_type::compare(&*i, s, n) == 0) {
1863 if (i == begin()) break;
1868 size_type rfind(const value_type* s, size_type pos = npos) const {
1869 return rfind(s, pos, traits_type::length(s));
1872 size_type rfind(value_type c, size_type pos = npos) const {
1873 return rfind(&c, pos, 1);
1876 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1877 return find_first_of(str.data(), pos, str.length());
1880 size_type find_first_of(const value_type* s,
1881 size_type pos, size_type n) const {
1882 if (pos > length() || n == 0) return npos;
1883 const_iterator i(begin() + pos),
1885 for (; i != finish; ++i) {
1886 if (traits_type::find(s, n, *i) != 0) {
1893 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1894 return find_first_of(s, pos, traits_type::length(s));
1897 size_type find_first_of(value_type c, size_type pos = 0) const {
1898 return find_first_of(&c, pos, 1);
1901 size_type find_last_of (const basic_fbstring& str,
1902 size_type pos = npos) const {
1903 return find_last_of(str.data(), pos, str.length());
1906 size_type find_last_of (const value_type* s, size_type pos,
1907 size_type n) const {
1908 if (!empty() && n > 0) {
1909 pos = std::min(pos, length() - 1);
1910 const_iterator i(begin() + pos);
1912 if (traits_type::find(s, n, *i) != 0) {
1915 if (i == begin()) break;
1921 size_type find_last_of (const value_type* s,
1922 size_type pos = npos) const {
1923 return find_last_of(s, pos, traits_type::length(s));
1926 size_type find_last_of (value_type c, size_type pos = npos) const {
1927 return find_last_of(&c, pos, 1);
1930 size_type find_first_not_of(const basic_fbstring& str,
1931 size_type pos = 0) const {
1932 return find_first_not_of(str.data(), pos, str.size());
1935 size_type find_first_not_of(const value_type* s, size_type pos,
1936 size_type n) const {
1937 if (pos < length()) {
1941 for (; i != finish; ++i) {
1942 if (traits_type::find(s, n, *i) == 0) {
1950 size_type find_first_not_of(const value_type* s,
1951 size_type pos = 0) const {
1952 return find_first_not_of(s, pos, traits_type::length(s));
1955 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1956 return find_first_not_of(&c, pos, 1);
1959 size_type find_last_not_of(const basic_fbstring& str,
1960 size_type pos = npos) const {
1961 return find_last_not_of(str.data(), pos, str.length());
1964 size_type find_last_not_of(const value_type* s, size_type pos,
1965 size_type n) const {
1966 if (!this->empty()) {
1967 pos = std::min(pos, size() - 1);
1968 const_iterator i(begin() + pos);
1970 if (traits_type::find(s, n, *i) == 0) {
1973 if (i == begin()) break;
1979 size_type find_last_not_of(const value_type* s,
1980 size_type pos = npos) const {
1981 return find_last_not_of(s, pos, traits_type::length(s));
1984 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1985 return find_last_not_of(&c, pos, 1);
1988 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1989 enforce(pos <= size(), std::__throw_out_of_range, "");
1990 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1993 int compare(const basic_fbstring& str) const {
1994 // FIX due to Goncalo N M de Carvalho July 18, 2005
1995 return compare(0, size(), str);
1998 int compare(size_type pos1, size_type n1,
1999 const basic_fbstring& str) const {
2000 return compare(pos1, n1, str.data(), str.size());
2003 int compare(size_type pos1, size_type n1,
2004 const value_type* s) const {
2005 return compare(pos1, n1, s, traits_type::length(s));
2008 int compare(size_type pos1, size_type n1,
2009 const value_type* s, size_type n2) const {
2010 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2011 procrustes(n1, size() - pos1);
2012 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2013 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2014 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2017 int compare(size_type pos1, size_type n1,
2018 const basic_fbstring& str,
2019 size_type pos2, size_type n2) const {
2020 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2021 return compare(pos1, n1, str.data() + pos2,
2022 std::min(n2, str.size() - pos2));
2025 // Code from Jean-Francois Bastien (03/26/2007)
2026 int compare(const value_type* s) const {
2027 // Could forward to compare(0, size(), s, traits_type::length(s))
2028 // but that does two extra checks
2029 const size_type n1(size()), n2(traits_type::length(s));
2030 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2031 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2039 // non-member functions
2041 template <typename E, class T, class A, class S>
2043 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2044 const basic_fbstring<E, T, A, S>& rhs) {
2046 basic_fbstring<E, T, A, S> result;
2047 result.reserve(lhs.size() + rhs.size());
2048 result.append(lhs).append(rhs);
2049 return std::move(result);
2053 template <typename E, class T, class A, class S>
2055 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2056 const basic_fbstring<E, T, A, S>& rhs) {
2057 return std::move(lhs.append(rhs));
2061 template <typename E, class T, class A, class S>
2063 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2064 basic_fbstring<E, T, A, S>&& rhs) {
2065 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2066 // Good, at least we don't need to reallocate
2067 return std::move(rhs.insert(0, lhs));
2069 // Meh, no go. Forward to operator+(const&, const&).
2070 auto const& rhsC = rhs;
2075 template <typename E, class T, class A, class S>
2077 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2078 basic_fbstring<E, T, A, S>&& rhs) {
2079 return std::move(lhs.append(rhs));
2082 template <typename E, class T, class A, class S>
2084 basic_fbstring<E, T, A, S> operator+(
2085 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2086 const basic_fbstring<E, T, A, S>& rhs) {
2088 basic_fbstring<E, T, A, S> result;
2089 const typename basic_fbstring<E, T, A, S>::size_type len =
2090 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2091 result.reserve(len + rhs.size());
2092 result.append(lhs, len).append(rhs);
2096 template <typename E, class T, class A, class S>
2098 basic_fbstring<E, T, A, S> operator+(
2099 typename basic_fbstring<E, T, A, S>::value_type lhs,
2100 const basic_fbstring<E, T, A, S>& rhs) {
2102 basic_fbstring<E, T, A, S> result;
2103 result.reserve(1 + rhs.size());
2104 result.push_back(lhs);
2109 template <typename E, class T, class A, class S>
2111 basic_fbstring<E, T, A, S> operator+(
2112 const basic_fbstring<E, T, A, S>& lhs,
2113 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2115 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2116 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2118 basic_fbstring<E, T, A, S> result;
2119 const size_type len = traits_type::length(rhs);
2120 result.reserve(lhs.size() + len);
2121 result.append(lhs).append(rhs, len);
2125 template <typename E, class T, class A, class S>
2127 basic_fbstring<E, T, A, S> operator+(
2128 const basic_fbstring<E, T, A, S>& lhs,
2129 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2131 basic_fbstring<E, T, A, S> result;
2132 result.reserve(lhs.size() + 1);
2134 result.push_back(rhs);
2138 template <typename E, class T, class A, class S>
2140 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2141 const basic_fbstring<E, T, A, S>& rhs) {
2142 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2144 template <typename E, class T, class A, class S>
2146 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2147 const basic_fbstring<E, T, A, S>& rhs) {
2148 return rhs == lhs; }
2150 template <typename E, class T, class A, class S>
2152 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2153 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2154 return lhs.compare(rhs) == 0; }
2156 template <typename E, class T, class A, class S>
2158 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2159 const basic_fbstring<E, T, A, S>& rhs) {
2160 return !(lhs == rhs); }
2162 template <typename E, class T, class A, class S>
2164 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* 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 basic_fbstring<E, T, A, S>& lhs,
2171 const typename basic_fbstring<E, T, A, S>::value_type* 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 basic_fbstring<E, T, A, S>& rhs) {
2178 return lhs.compare(rhs) < 0; }
2180 template <typename E, class T, class A, class S>
2182 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2183 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2184 return lhs.compare(rhs) < 0; }
2186 template <typename E, class T, class A, class S>
2188 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2189 const basic_fbstring<E, T, A, S>& rhs) {
2190 return rhs.compare(lhs) > 0; }
2192 template <typename E, class T, class A, class S>
2194 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2195 const basic_fbstring<E, T, A, S>& rhs) {
2198 template <typename E, class T, class A, class S>
2200 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2201 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2204 template <typename E, class T, class A, class S>
2206 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2207 const basic_fbstring<E, T, A, S>& rhs) {
2210 template <typename E, class T, class A, class S>
2212 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2213 const basic_fbstring<E, T, A, S>& rhs) {
2214 return !(rhs < lhs); }
2216 template <typename E, class T, class A, class S>
2218 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2219 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2220 return !(rhs < lhs); }
2222 template <typename E, class T, class A, class S>
2224 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2225 const basic_fbstring<E, T, A, S>& rhs) {
2226 return !(rhs < lhs); }
2228 template <typename E, class T, class A, class S>
2230 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2231 const basic_fbstring<E, T, A, S>& rhs) {
2232 return !(lhs < rhs); }
2234 template <typename E, class T, class A, class S>
2236 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2237 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2238 return !(lhs < rhs); }
2240 template <typename E, class T, class A, class S>
2242 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2243 const basic_fbstring<E, T, A, S>& rhs) {
2244 return !(lhs < rhs);
2248 template <typename E, class T, class A, class S>
2249 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2253 // TODO: make this faster.
2254 template <typename E, class T, class A, class S>
2257 typename basic_fbstring<E, T, A, S>::value_type,
2258 typename basic_fbstring<E, T, A, S>::traits_type>&
2260 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2261 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2262 basic_fbstring<E, T, A, S>& str) {
2263 typename std::basic_istream<E, T>::sentry sentry(is);
2264 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2265 typename basic_fbstring<E, T, A, S>::traits_type>
2267 typedef typename __istream_type::ios_base __ios_base;
2268 size_t extracted = 0;
2269 auto err = __ios_base::goodbit;
2271 auto n = is.width();
2276 auto got = is.rdbuf()->sgetc();
2277 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2278 // Whew. We get to store this guy
2280 got = is.rdbuf()->snextc();
2282 if (got == T::eof()) {
2283 err |= __ios_base::eofbit;
2288 err |= __ios_base::failbit;
2296 template <typename E, class T, class A, class S>
2298 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2299 typename basic_fbstring<E, T, A, S>::traits_type>&
2301 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2302 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2303 const basic_fbstring<E, T, A, S>& str) {
2304 os.write(str.data(), str.size());
2308 #ifndef _LIBSTDCXX_FBSTRING
2310 template <typename E, class T, class A, class S>
2312 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2313 typename basic_fbstring<E, T, A, S>::traits_type>&
2315 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2316 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2317 basic_fbstring<E, T, A, S>& str,
2318 typename basic_fbstring<E, T, A, S>::value_type delim) {
2319 // Use the nonstandard getdelim()
2323 // This looks quadratic but it really depends on realloc
2324 auto const newSize = size + 128;
2325 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2326 is.getline(buf + size, newSize - size, delim);
2327 if (is.bad() || is.eof() || !is.fail()) {
2328 // done by either failure, end of file, or normal read
2329 size += std::strlen(buf + size);
2332 // Here we have failed due to too short a buffer
2333 // Minus one to discount the terminating '\0'
2335 assert(buf[size] == 0);
2336 // Clear the error so we can continue reading
2339 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2340 AcquireMallocatedString());
2345 template <typename E, class T, class A, class S>
2347 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2348 typename basic_fbstring<E, T, A, S>::traits_type>&
2350 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2351 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2352 basic_fbstring<E, T, A, S>& str) {
2353 // Just forward to the version with a delimiter
2354 return getline(is, str, '\n');
2359 template <typename E1, class T, class A, class S>
2360 const typename basic_fbstring<E1, T, A, S>::size_type
2361 basic_fbstring<E1, T, A, S>::npos =
2362 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2364 #ifndef _LIBSTDCXX_FBSTRING
2365 // basic_string compatibility routines
2367 template <typename E, class T, class A, class S>
2369 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2370 const std::string& rhs) {
2371 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2374 template <typename E, class T, class A, class S>
2376 bool operator==(const std::string& lhs,
2377 const basic_fbstring<E, T, A, S>& rhs) {
2381 template <typename E, class T, class A, class S>
2383 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2384 const std::string& rhs) {
2385 return !(lhs == rhs);
2388 template <typename E, class T, class A, class S>
2390 bool operator!=(const std::string& lhs,
2391 const basic_fbstring<E, T, A, S>& rhs) {
2392 return !(lhs == rhs);
2395 #if !defined(_LIBSTDCXX_FBSTRING)
2396 typedef basic_fbstring<char> fbstring;
2399 // fbstring is relocatable
2400 template <class T, class R, class A, class S>
2401 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2404 _GLIBCXX_END_NAMESPACE_VERSION
2407 } // namespace folly
2409 #pragma GCC diagnostic pop
2411 #ifndef _LIBSTDCXX_FBSTRING
2415 struct hash< ::folly::fbstring> {
2416 size_t operator()(const ::folly::fbstring& s) const {
2417 return ::folly::hash::fnv32_buf(s.data(), s.size());
2422 #endif // _LIBSTDCXX_FBSTRING
2424 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2425 #undef FBSTRING_LIKELY
2426 #undef FBSTRING_UNLIKELY
2428 #endif // FOLLY_BASE_FBSTRING_H_