2 * Copyright 2014 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
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.
63 #include <type_traits>
65 // libc++ doesn't provide this header
66 #ifndef _LIBCPP_VERSION
67 // This file appears in two locations: inside fbcode and in the
68 // libstdc++ source code (when embedding fbstring as std::string).
69 // To aid in this schizophrenic use, two macros are defined in
71 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
72 // gate use inside fbcode v. libstdc++
73 #include <bits/c++config.h>
76 #ifdef _LIBSTDCXX_FBSTRING
78 #pragma GCC system_header
80 // Handle the cases where the fbcode version (folly/Malloc.h) is included
81 // either before or after this inclusion.
82 #ifdef FOLLY_MALLOC_H_
83 #undef FOLLY_MALLOC_H_
84 #include "basic_fbstring_malloc.h"
86 #include "basic_fbstring_malloc.h"
87 #undef FOLLY_MALLOC_H_
90 #else // !_LIBSTDCXX_FBSTRING
96 #include "folly/Traits.h"
97 #include "folly/Malloc.h"
98 #include "folly/Hash.h"
102 // We defined these here rather than including Likely.h to avoid
103 // redefinition errors when fbstring is imported into libstdc++.
104 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
105 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
107 // Ignore shadowing warnings within this file, so includers can use -Wshadow.
108 #pragma GCC diagnostic push
109 #pragma GCC diagnostic ignored "-Wshadow"
111 // FBString cannot use throw when replacing std::string, though it may still
112 // use std::__throw_*
113 #define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
115 #ifdef _LIBSTDCXX_FBSTRING
116 namespace std _GLIBCXX_VISIBILITY(default) {
117 _GLIBCXX_BEGIN_NAMESPACE_VERSION
122 // Different versions of gcc/clang support different versions of
123 // the address sanitizer attribute. Unfortunately, this attribute
124 // has issues when inlining is used, so disable that as well.
125 #if defined(__clang__)
126 # if __has_feature(address_sanitizer)
127 # if __has_attribute(__no_address_safety_analysis__)
128 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
129 __attribute__((__no_address_safety_analysis__, __noinline__))
130 # elif __has_attribute(__no_sanitize_address__)
131 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
132 __attribute__((__no_sanitize_address__, __noinline__))
135 #elif defined (__GNUC__) && \
137 (__GNUC_MINOR__ >= 8) && \
139 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
140 __attribute__((__no_address_safety_analysis__, __noinline__))
142 #ifndef FBSTRING_DISABLE_ADDRESS_SANITIZER
143 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
146 namespace fbstring_detail {
148 template <class InIt, class OutIt>
151 typename std::iterator_traits<InIt>::difference_type n,
153 for (; n != 0; --n, ++b, ++d) {
154 assert((const void*)&*d != &*b);
160 template <class Pod, class T>
161 inline void pod_fill(Pod* b, Pod* e, T c) {
162 assert(b && e && b <= e);
163 /*static*/ if (sizeof(T) == 1) {
166 auto const ee = b + ((e - b) & ~7u);
167 for (; b != ee; b += 8) {
178 for (; b != e; ++b) {
185 * Lightly structured memcpy, simplifies copying PODs and introduces
186 * some asserts. Unfortunately using this function may cause
187 * measurable overhead (presumably because it adjusts from a begin/end
188 * convention to a pointer/size convention, so it does some extra
189 * arithmetic even though the caller might have done the inverse
190 * adaptation outside).
193 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
195 assert(d >= e || d + (e - b) <= b);
196 memcpy(d, b, (e - b) * sizeof(Pod));
200 * Lightly structured memmove, simplifies copying PODs and introduces
204 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
206 memmove(d, b, (e - b) * sizeof(*b));
209 } // namespace fbstring_detail
212 * Defines a special acquisition method for constructing fbstring
213 * objects. AcquireMallocatedString means that the user passes a
214 * pointer to a malloc-allocated string that the fbstring object will
217 enum class AcquireMallocatedString {};
220 * fbstring_core_model is a mock-up type that defines all required
221 * signatures of a fbstring core. The fbstring class itself uses such
222 * a core object to implement all of the numerous member functions
223 * required by the standard.
225 * If you want to define a new core, copy the definition below and
226 * implement the primitives. Then plug the core into basic_fbstring as
227 * a template argument.
229 template <class Char>
230 class fbstring_core_model {
232 fbstring_core_model();
233 fbstring_core_model(const fbstring_core_model &);
234 ~fbstring_core_model();
235 // Returns a pointer to string's buffer (currently only contiguous
236 // strings are supported). The pointer is guaranteed to be valid
237 // until the next call to a non-const member function.
238 const Char * data() const;
239 // Much like data(), except the string is prepared to support
240 // character-level changes. This call is a signal for
241 // e.g. reference-counted implementation to fork the data. The
242 // pointer is guaranteed to be valid until the next call to a
243 // non-const member function.
244 Char * mutable_data();
245 // Returns a pointer to string's buffer and guarantees that a
246 // readable '\0' lies right after the buffer. The pointer is
247 // guaranteed to be valid until the next call to a non-const member
249 const Char * c_str() const;
250 // Shrinks the string by delta characters. Asserts that delta <=
252 void shrink(size_t delta);
253 // Expands the string by delta characters (i.e. after this call
254 // size() will report the old size() plus delta) but without
255 // initializing the expanded region. Returns a pointer to the memory
256 // to be initialized (the beginning of the expanded portion). The
257 // caller is expected to fill the expanded area appropriately.
258 Char* expand_noinit(size_t delta);
259 // Expands the string by one character and sets the last character
261 void push_back(Char c);
262 // Returns the string's size.
264 // Returns the string's capacity, i.e. maximum size that the string
265 // can grow to without reallocation. Note that for reference counted
266 // strings that's technically a lie - even assigning characters
267 // within the existing size would cause a reallocation.
268 size_t capacity() const;
269 // Returns true if the data underlying the string is actually shared
270 // across multiple strings (in a refcounted fashion).
271 bool isShared() const;
272 // Makes sure that at least minCapacity characters are available for
273 // the string without reallocation. For reference-counted strings,
274 // it should fork the data even if minCapacity < size().
275 void reserve(size_t minCapacity);
278 fbstring_core_model& operator=(const fbstring_core_model &);
283 * gcc-4.7 throws what appears to be some false positive uninitialized
284 * warnings for the members of the MediumLarge struct. So, mute them here.
286 #if defined(__GNUC__) && !defined(__clang__)
287 # pragma GCC diagnostic push
288 # pragma GCC diagnostic ignored "-Wuninitialized"
292 * This is the core of the string. The code should work on 32- and
293 * 64-bit architectures and with any Char size. Porting to big endian
294 * architectures would require some changes.
296 * The storage is selected as follows (assuming we store one-byte
297 * characters on a 64-bit machine): (a) "small" strings between 0 and
298 * 23 chars are stored in-situ without allocation (the rightmost byte
299 * stores the size); (b) "medium" strings from 24 through 254 chars
300 * are stored in malloc-allocated memory that is copied eagerly; (c)
301 * "large" strings of 255 chars and above are stored in a similar
302 * structure as medium arrays, except that the string is
303 * reference-counted and copied lazily. the reference count is
304 * allocated right before the character array.
306 * The discriminator between these three strategies sits in the two
307 * most significant bits of the rightmost char of the storage. If
308 * neither is set, then the string is small (and its length sits in
309 * the lower-order bits of that rightmost character). If the MSb is
310 * set, the string is medium width. If the second MSb is set, then the
313 template <class Char> class fbstring_core {
315 fbstring_core() noexcept {
316 // Only initialize the tag, will set the MSBs (i.e. the small
317 // string size) to zero too
318 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
319 // or: setSmallSize(0);
321 assert(category() == isSmall && size() == 0);
324 fbstring_core(const fbstring_core & rhs) {
325 assert(&rhs != this);
326 // Simplest case first: small strings are bitblitted
327 if (rhs.category() == isSmall) {
328 assert(offsetof(MediumLarge, data_) == 0);
329 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
330 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
331 const size_t size = rhs.smallSize();
333 ml_.capacity_ = rhs.ml_.capacity_;
336 // Just write the whole thing, don't look at details. In
337 // particular we need to copy capacity anyway because we want
338 // to set the size (don't forget that the last character,
339 // which stores a short string's length, is shared with the
340 // ml_.capacity field).
343 assert(category() == isSmall && this->size() == rhs.size());
344 } else if (rhs.category() == isLarge) {
345 // Large strings are just refcounted
347 RefCounted::incrementRefs(ml_.data_);
348 assert(category() == isLarge && size() == rhs.size());
350 // Medium strings are copied eagerly. Don't forget to allocate
351 // one extra Char for the null terminator.
352 auto const allocSize =
353 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
354 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
355 fbstring_detail::pod_copy(rhs.ml_.data_,
357 rhs.ml_.data_ + rhs.ml_.size_ + 1,
359 // No need for writeTerminator() here, we copied one extra
360 // element just above.
361 ml_.size_ = rhs.ml_.size_;
362 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
363 assert(category() == isMedium);
365 assert(size() == rhs.size());
366 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
369 fbstring_core(fbstring_core&& goner) noexcept {
370 if (goner.category() == isSmall) {
371 // Just copy, leave the goner in peace
372 new(this) fbstring_core(goner.small_, goner.smallSize());
376 // Clean goner's carcass
377 goner.setSmallSize(0);
381 // NOTE(agallagher): The word-aligned copy path copies bytes which are
382 // outside the range of the string, and makes address sanitizer unhappy,
383 // so just disable it on this function.
384 fbstring_core(const Char *const data, const size_t size)
385 FBSTRING_DISABLE_ADDRESS_SANITIZER {
386 // Simplest case first: small strings are bitblitted
387 if (size <= maxSmallSize) {
388 // Layout is: Char* data_, size_t size_, size_t capacity_
389 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
390 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
391 // sizeof(size_t) must be a power of 2
392 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
394 // If data is aligned, use fast word-wise copying. Otherwise,
395 // use conservative memcpy.
396 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
397 fbstring_detail::pod_copy(data, data + size, small_);
399 // Copy one word (64 bits) at a time
400 const size_t byteSize = size * sizeof(Char);
401 if (byteSize > 2 * sizeof(size_t)) {
403 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
405 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
407 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
408 } else if (byteSize > sizeof(size_t)) {
411 } else if (size > 0) {
417 } else if (size <= maxMediumSize) {
418 // Medium strings are allocated normally. Don't forget to
419 // allocate one extra Char for the terminating null.
420 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
421 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
422 fbstring_detail::pod_copy(data, data + size, ml_.data_);
424 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
426 // Large strings are allocated differently
427 size_t effectiveCapacity = size;
428 auto const newRC = RefCounted::create(data, & effectiveCapacity);
429 ml_.data_ = newRC->data_;
431 ml_.capacity_ = effectiveCapacity | isLarge;
434 assert(this->size() == size);
435 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
438 ~fbstring_core() noexcept {
439 auto const c = category();
447 RefCounted::decrementRefs(ml_.data_);
450 // Snatches a previously mallocated string. The parameter "size"
451 // is the size of the string, and the parameter "allocatedSize"
452 // is the size of the mallocated block. The string must be
453 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
455 // So if you want a 2-character string, pass malloc(3) as "data",
456 // pass 2 as "size", and pass 3 as "allocatedSize".
457 fbstring_core(Char * const data,
459 const size_t allocatedSize,
460 AcquireMallocatedString) {
462 assert(allocatedSize >= size + 1);
463 assert(data[size] == '\0');
464 // Use the medium string storage
467 // Don't forget about null terminator
468 ml_.capacity_ = (allocatedSize - 1) | isMedium;
470 // No need for the memory
476 // swap below doesn't test whether &rhs == this (and instead
477 // potentially does extra work) on the premise that the rarity of
478 // that situation actually makes the check more expensive than is
480 void swap(fbstring_core & rhs) {
486 // In C++11 data() and c_str() are 100% equivalent.
487 const Char * data() const {
491 Char * mutable_data() {
492 auto const c = category();
496 assert(c == isMedium || c == isLarge);
497 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
499 size_t effectiveCapacity = ml_.capacity();
500 auto const newRC = RefCounted::create(& effectiveCapacity);
501 // If this fails, someone placed the wrong capacity in an
503 assert(effectiveCapacity >= ml_.capacity());
504 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
506 RefCounted::decrementRefs(ml_.data_);
507 ml_.data_ = newRC->data_;
508 // No need to call writeTerminator(), we have + 1 above.
513 const Char * c_str() const {
514 auto const c = category();
515 #ifdef FBSTRING_PERVERSE
517 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
518 || small_[smallSize()] == '\0');
519 small_[smallSize()] = '\0';
522 assert(c == isMedium || c == isLarge);
523 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
524 ml_.data_[ml_.size_] = '\0';
525 #elif defined(FBSTRING_CONSERVATIVE)
527 assert(small_[smallSize()] == '\0');
530 assert(c == isMedium || c == isLarge);
531 assert(ml_.data_[ml_.size_] == '\0');
534 small_[smallSize()] = '\0';
537 assert(c == isMedium || c == isLarge);
538 ml_.data_[ml_.size_] = '\0';
543 void shrink(const size_t delta) {
544 if (category() == isSmall) {
545 // Check for underflow
546 assert(delta <= smallSize());
547 setSmallSize(smallSize() - delta);
548 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
549 // Medium strings and unique large strings need no special
551 assert(ml_.size_ >= delta);
554 assert(ml_.size_ >= delta);
555 // Shared large string, must make unique. This is because of the
556 // durn terminator must be written, which may trample the shared
559 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
561 // No need to write the terminator.
567 void reserve(size_t minCapacity) {
568 if (category() == isLarge) {
570 if (RefCounted::refs(ml_.data_) > 1) {
571 // We must make it unique regardless; in-place reallocation is
572 // useless if the string is shared. In order to not surprise
573 // people, reserve the new block at current capacity or
574 // more. That way, a string's capacity never shrinks after a
576 minCapacity = std::max(minCapacity, ml_.capacity());
577 auto const newRC = RefCounted::create(& minCapacity);
578 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
580 // Done with the old data. No need to call writeTerminator(),
581 // we have + 1 above.
582 RefCounted::decrementRefs(ml_.data_);
583 ml_.data_ = newRC->data_;
584 ml_.capacity_ = minCapacity | isLarge;
585 // size remains unchanged
587 // String is not shared, so let's try to realloc (if needed)
588 if (minCapacity > ml_.capacity()) {
589 // Asking for more memory
591 RefCounted::reallocate(ml_.data_, ml_.size_,
592 ml_.capacity(), minCapacity);
593 ml_.data_ = newRC->data_;
594 ml_.capacity_ = minCapacity | isLarge;
597 assert(capacity() >= minCapacity);
599 } else if (category() == isMedium) {
600 // String is not shared
601 if (minCapacity <= ml_.capacity()) {
602 return; // nothing to do, there's enough room
604 if (minCapacity <= maxMediumSize) {
605 // Keep the string at medium size. Don't forget to allocate
606 // one extra Char for the terminating null.
607 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
608 ml_.data_ = static_cast<Char *>(
611 ml_.size_ * sizeof(Char),
612 (ml_.capacity() + 1) * sizeof(Char),
615 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
617 // Conversion from medium to large string
618 fbstring_core nascent;
619 // Will recurse to another branch of this function
620 nascent.reserve(minCapacity);
621 nascent.ml_.size_ = ml_.size_;
622 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
626 assert(capacity() >= minCapacity);
629 assert(category() == isSmall);
630 if (minCapacity > maxMediumSize) {
632 auto const newRC = RefCounted::create(& minCapacity);
633 auto const size = smallSize();
634 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
635 // No need for writeTerminator(), we wrote it above with + 1.
636 ml_.data_ = newRC->data_;
638 ml_.capacity_ = minCapacity | isLarge;
639 assert(capacity() >= minCapacity);
640 } else if (minCapacity > maxSmallSize) {
642 // Don't forget to allocate one extra Char for the terminating null
643 auto const allocSizeBytes =
644 goodMallocSize((1 + minCapacity) * sizeof(Char));
645 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
646 auto const size = smallSize();
647 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
648 // No need for writeTerminator(), we wrote it above with + 1.
651 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
654 // Nothing to do, everything stays put
657 assert(capacity() >= minCapacity);
660 Char * expand_noinit(const size_t delta) {
661 // Strategy is simple: make room, then change size
662 assert(capacity() >= size());
664 if (category() == isSmall) {
667 if (newSz <= maxSmallSize) {
675 newSz = ml_.size_ + delta;
676 if (newSz > capacity()) {
680 assert(capacity() >= newSz);
681 // Category can't be small - we took care of that above
682 assert(category() == isMedium || category() == isLarge);
685 assert(size() == newSz);
686 return ml_.data_ + sz;
689 void push_back(Char c) {
690 assert(capacity() >= size());
692 if (category() == isSmall) {
694 if (sz < maxSmallSize) {
695 setSmallSize(sz + 1);
700 reserve(maxSmallSize * 2);
703 if (sz == capacity()) { // always true for isShared()
704 reserve(1 + sz * 3 / 2); // ensures not shared
708 assert(capacity() >= sz + 1);
709 // Category can't be small - we took care of that above
710 assert(category() == isMedium || category() == isLarge);
716 size_t size() const {
717 return category() == isSmall ? smallSize() : ml_.size_;
720 size_t capacity() const {
721 switch (category()) {
725 // For large-sized strings, a multi-referenced chunk has no
726 // available capacity. This is because any attempt to append
727 // data would trigger a new allocation.
728 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
731 return ml_.capacity();
734 bool isShared() const {
735 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
738 #ifdef FBSTRING_PERVERSE
739 enum { TERMINATOR = '^' };
741 enum { TERMINATOR = '\0' };
744 void writeTerminator() {
745 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
746 if (category() == isSmall) {
747 const auto s = smallSize();
748 if (s != maxSmallSize) {
749 small_[s] = TERMINATOR;
752 ml_.data_[ml_.size_] = TERMINATOR;
759 fbstring_core & operator=(const fbstring_core & rhs);
766 size_t capacity() const {
767 return capacity_ & capacityExtractMask;
772 std::atomic<size_t> refCount_;
775 static RefCounted * fromData(Char * p) {
776 return static_cast<RefCounted*>(
778 static_cast<unsigned char*>(static_cast<void*>(p))
779 - sizeof(refCount_)));
782 static size_t refs(Char * p) {
783 return fromData(p)->refCount_.load(std::memory_order_acquire);
786 static void incrementRefs(Char * p) {
787 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
790 static void decrementRefs(Char * p) {
791 auto const dis = fromData(p);
792 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
799 static RefCounted * create(size_t * size) {
800 // Don't forget to allocate one extra Char for the terminating
801 // null. In this case, however, one Char is already part of the
803 const size_t allocSize = goodMallocSize(
804 sizeof(RefCounted) + *size * sizeof(Char));
805 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
806 result->refCount_.store(1, std::memory_order_release);
807 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
811 static RefCounted * create(const Char * data, size_t * size) {
812 const size_t effectiveSize = *size;
813 auto result = create(size);
814 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
818 static RefCounted * reallocate(Char *const data,
819 const size_t currentSize,
820 const size_t currentCapacity,
821 const size_t newCapacity) {
822 assert(newCapacity > 0 && newCapacity > currentSize);
823 auto const dis = fromData(data);
824 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
825 // Don't forget to allocate one extra Char for the terminating
826 // null. In this case, however, one Char is already part of the
828 auto result = static_cast<RefCounted*>(
830 sizeof(RefCounted) + currentSize * sizeof(Char),
831 sizeof(RefCounted) + currentCapacity * sizeof(Char),
832 sizeof(RefCounted) + newCapacity * sizeof(Char)));
833 assert(result->refCount_.load(std::memory_order_acquire) == 1);
839 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
840 mutable MediumLarge ml_;
844 lastChar = sizeof(MediumLarge) - 1,
845 maxSmallSize = lastChar / sizeof(Char),
846 maxMediumSize = 254 / sizeof(Char), // coincides with the small
847 // bin size in dlmalloc
848 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
849 capacityExtractMask = ~categoryExtractMask,
851 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
852 "Corrupt memory layout for fbstring.");
856 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
857 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
860 Category category() const {
861 // Assumes little endian
862 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
865 size_t smallSize() const {
866 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
867 return static_cast<size_t>(maxSmallSize)
868 - static_cast<size_t>(small_[maxSmallSize]);
871 void setSmallSize(size_t s) {
872 // Warning: this should work with uninitialized strings too,
873 // so don't assume anything about the previous value of
874 // small_[maxSmallSize].
875 assert(s <= maxSmallSize);
876 small_[maxSmallSize] = maxSmallSize - s;
880 #if defined(__GNUC__) && !defined(__clang__)
881 # pragma GCC diagnostic pop
884 #ifndef _LIBSTDCXX_FBSTRING
886 * Dummy fbstring core that uses an actual std::string. This doesn't
887 * make any sense - it's just for testing purposes.
889 template <class Char>
890 class dummy_fbstring_core {
892 dummy_fbstring_core() {
894 dummy_fbstring_core(const dummy_fbstring_core& another)
895 : backend_(another.backend_) {
897 dummy_fbstring_core(const Char * s, size_t n)
900 void swap(dummy_fbstring_core & rhs) {
901 backend_.swap(rhs.backend_);
903 const Char * data() const {
904 return backend_.data();
906 Char * mutable_data() {
907 //assert(!backend_.empty());
908 return &*backend_.begin();
910 void shrink(size_t delta) {
911 assert(delta <= size());
912 backend_.resize(size() - delta);
914 Char * expand_noinit(size_t delta) {
915 auto const sz = size();
916 backend_.resize(size() + delta);
917 return backend_.data() + sz;
919 void push_back(Char c) {
920 backend_.push_back(c);
922 size_t size() const {
923 return backend_.size();
925 size_t capacity() const {
926 return backend_.capacity();
928 bool isShared() const {
931 void reserve(size_t minCapacity) {
932 backend_.reserve(minCapacity);
936 std::basic_string<Char> backend_;
938 #endif // !_LIBSTDCXX_FBSTRING
941 * This is the basic_string replacement. For conformity,
942 * basic_fbstring takes the same template parameters, plus the last
943 * one which is the core.
945 #ifdef _LIBSTDCXX_FBSTRING
946 template <typename E, class T, class A, class Storage>
948 template <typename E,
949 class T = std::char_traits<E>,
950 class A = std::allocator<E>,
951 class Storage = fbstring_core<E> >
953 class basic_fbstring {
957 void (*throw_exc)(const char*),
959 if (!condition) throw_exc(msg);
962 bool isSane() const {
965 empty() == (size() == 0) &&
966 empty() == (begin() == end()) &&
967 size() <= max_size() &&
968 capacity() <= max_size() &&
969 size() <= capacity() &&
970 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
974 friend struct Invariant;
977 explicit Invariant(const basic_fbstring& s) : s_(s) {
984 const basic_fbstring& s_;
986 explicit Invariant(const basic_fbstring&) {}
988 Invariant& operator=(const Invariant&);
993 typedef T traits_type;
994 typedef typename traits_type::char_type value_type;
995 typedef A allocator_type;
996 typedef typename A::size_type size_type;
997 typedef typename A::difference_type difference_type;
999 typedef typename A::reference reference;
1000 typedef typename A::const_reference const_reference;
1001 typedef typename A::pointer pointer;
1002 typedef typename A::const_pointer const_pointer;
1004 typedef E* iterator;
1005 typedef const E* const_iterator;
1006 typedef std::reverse_iterator<iterator
1007 #ifdef NO_ITERATOR_TRAITS
1011 typedef std::reverse_iterator<const_iterator
1012 #ifdef NO_ITERATOR_TRAITS
1015 > const_reverse_iterator;
1017 static const size_type npos; // = size_type(-1)
1020 static void procrustes(size_type& n, size_type nmax) {
1021 if (n > nmax) n = nmax;
1025 // C++11 21.4.2 construct/copy/destroy
1026 explicit basic_fbstring(const A& a = A()) noexcept {
1029 basic_fbstring(const basic_fbstring& str)
1030 : store_(str.store_) {
1034 basic_fbstring(basic_fbstring&& goner) noexcept
1035 : store_(std::move(goner.store_)) {
1038 #ifndef _LIBSTDCXX_FBSTRING
1039 // This is defined for compatibility with std::string
1040 /* implicit */ basic_fbstring(const std::string& str)
1041 : store_(str.data(), str.size()) {
1045 basic_fbstring(const basic_fbstring& str, size_type pos,
1046 size_type n = npos, const A& a = A()) {
1047 assign(str, pos, n);
1050 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1051 : store_(s, s ? traits_type::length(s) : ({
1052 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1053 err += ": null pointer initializer not valid";
1054 std::__throw_logic_error(err.c_str());
1059 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1063 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1064 auto const data = store_.expand_noinit(n);
1065 fbstring_detail::pod_fill(data, data + n, c);
1066 store_.writeTerminator();
1069 template <class InIt>
1070 basic_fbstring(InIt begin, InIt end,
1071 typename std::enable_if<
1072 !std::is_same<typename std::remove_const<InIt>::type,
1073 value_type*>::value, const A>::type & a = A()) {
1077 // Specialization for const char*, const char*
1078 basic_fbstring(const value_type* b, const value_type* e)
1079 : store_(b, e - b) {
1082 // Nonstandard constructor
1083 basic_fbstring(value_type *s, size_type n, size_type c,
1084 AcquireMallocatedString a)
1085 : store_(s, n, c, a) {
1088 // Construction from initialization list
1089 basic_fbstring(std::initializer_list<value_type> il) {
1090 assign(il.begin(), il.end());
1093 ~basic_fbstring() noexcept {
1096 basic_fbstring& operator=(const basic_fbstring& lhs) {
1097 if (FBSTRING_UNLIKELY(&lhs == this)) {
1100 auto const oldSize = size();
1101 auto const srcSize = lhs.size();
1102 if (capacity() >= srcSize && !store_.isShared()) {
1103 // great, just copy the contents
1104 if (oldSize < srcSize)
1105 store_.expand_noinit(srcSize - oldSize);
1107 store_.shrink(oldSize - srcSize);
1108 assert(size() == srcSize);
1109 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1110 store_.writeTerminator();
1112 // need to reallocate, so we may as well create a brand new string
1113 basic_fbstring(lhs).swap(*this);
1119 basic_fbstring& operator=(basic_fbstring&& goner) noexcept {
1120 if (FBSTRING_UNLIKELY(&goner == this)) {
1121 // Compatibility with std::basic_string<>,
1122 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1125 // No need of this anymore
1126 this->~basic_fbstring();
1127 // Move the goner into this
1128 new(&store_) fbstring_core<E>(std::move(goner.store_));
1132 #ifndef _LIBSTDCXX_FBSTRING
1133 // Compatibility with std::string
1134 basic_fbstring & operator=(const std::string & rhs) {
1135 return assign(rhs.data(), rhs.size());
1138 // Compatibility with std::string
1139 std::string toStdString() const {
1140 return std::string(data(), size());
1143 // A lot of code in fbcode still uses this method, so keep it here for now.
1144 const basic_fbstring& toStdString() const {
1149 basic_fbstring& operator=(const value_type* s) {
1153 basic_fbstring& operator=(value_type c) {
1155 store_.expand_noinit(1);
1156 } else if (store_.isShared()) {
1157 basic_fbstring(1, c).swap(*this);
1160 store_.shrink(size() - 1);
1162 *store_.mutable_data() = c;
1163 store_.writeTerminator();
1167 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1168 return assign(il.begin(), il.end());
1171 // C++11 21.4.3 iterators:
1172 iterator begin() { return store_.mutable_data(); }
1174 const_iterator begin() const { return store_.data(); }
1176 const_iterator cbegin() const { return begin(); }
1179 return store_.mutable_data() + store_.size();
1182 const_iterator end() const {
1183 return store_.data() + store_.size();
1186 const_iterator cend() const { return end(); }
1188 reverse_iterator rbegin() {
1189 return reverse_iterator(end());
1192 const_reverse_iterator rbegin() const {
1193 return const_reverse_iterator(end());
1196 const_reverse_iterator crbegin() const { return rbegin(); }
1198 reverse_iterator rend() {
1199 return reverse_iterator(begin());
1202 const_reverse_iterator rend() const {
1203 return const_reverse_iterator(begin());
1206 const_reverse_iterator crend() const { return rend(); }
1209 // C++11 21.4.5, element access:
1210 const value_type& front() const { return *begin(); }
1211 const value_type& back() const {
1213 // Should be begin()[size() - 1], but that branches twice
1214 return *(end() - 1);
1216 value_type& front() { return *begin(); }
1217 value_type& back() {
1219 // Should be begin()[size() - 1], but that branches twice
1220 return *(end() - 1);
1227 // C++11 21.4.4 capacity:
1228 size_type size() const { return store_.size(); }
1230 size_type length() const { return size(); }
1232 size_type max_size() const {
1233 return std::numeric_limits<size_type>::max();
1236 void resize(const size_type n, const value_type c = value_type()) {
1237 auto size = this->size();
1239 store_.shrink(size - n);
1241 // Do this in two steps to minimize slack memory copied (see
1243 auto const capacity = this->capacity();
1244 assert(capacity >= size);
1245 if (size < capacity) {
1246 auto delta = std::min(n, capacity) - size;
1247 store_.expand_noinit(delta);
1248 fbstring_detail::pod_fill(begin() + size, end(), c);
1251 store_.writeTerminator();
1256 auto const delta = n - size;
1257 store_.expand_noinit(delta);
1258 fbstring_detail::pod_fill(end() - delta, end(), c);
1259 store_.writeTerminator();
1261 assert(this->size() == n);
1264 size_type capacity() const { return store_.capacity(); }
1266 void reserve(size_type res_arg = 0) {
1267 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1268 store_.reserve(res_arg);
1271 void shrink_to_fit() {
1272 // Shrink only if slack memory is sufficiently large
1273 if (capacity() < size() * 3 / 2) {
1276 basic_fbstring(cbegin(), cend()).swap(*this);
1279 void clear() { resize(0); }
1281 bool empty() const { return size() == 0; }
1283 // C++11 21.4.5 element access:
1284 const_reference operator[](size_type pos) const {
1285 return *(c_str() + pos);
1288 reference operator[](size_type pos) {
1289 if (pos == size()) {
1290 // Just call c_str() to make sure '\0' is present
1293 return *(begin() + pos);
1296 const_reference at(size_type n) const {
1297 enforce(n <= size(), std::__throw_out_of_range, "");
1301 reference at(size_type n) {
1302 enforce(n < size(), std::__throw_out_of_range, "");
1306 // C++11 21.4.6 modifiers:
1307 basic_fbstring& operator+=(const basic_fbstring& str) {
1311 basic_fbstring& operator+=(const value_type* s) {
1315 basic_fbstring& operator+=(const value_type c) {
1320 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1325 basic_fbstring& append(const basic_fbstring& str) {
1327 auto desiredSize = size() + str.size();
1329 append(str.data(), str.size());
1330 assert(size() == desiredSize);
1334 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1336 const size_type sz = str.size();
1337 enforce(pos <= sz, std::__throw_out_of_range, "");
1338 procrustes(n, sz - pos);
1339 return append(str.data() + pos, n);
1342 basic_fbstring& append(const value_type* s, size_type n) {
1344 Invariant checker(*this);
1347 if (FBSTRING_UNLIKELY(!n)) {
1348 // Unlikely but must be done
1351 auto const oldSize = size();
1352 auto const oldData = data();
1353 // Check for aliasing (rare). We could use "<=" here but in theory
1354 // those do not work for pointers unless the pointers point to
1355 // elements in the same array. For that reason we use
1356 // std::less_equal, which is guaranteed to offer a total order
1357 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1359 std::less_equal<const value_type*> le;
1360 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1361 assert(le(s + n, oldData + oldSize));
1362 const size_type offset = s - oldData;
1363 store_.reserve(oldSize + n);
1364 // Restore the source
1365 s = data() + offset;
1367 // Warning! Repeated appends with short strings may actually incur
1368 // practically quadratic performance. Avoid that by pushing back
1369 // the first character (which ensures exponential growth) and then
1370 // appending the rest normally. Worst case the append may incur a
1371 // second allocation but that will be rare.
1374 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1375 assert(size() == oldSize + n + 1);
1379 basic_fbstring& append(const value_type* s) {
1380 return append(s, traits_type::length(s));
1383 basic_fbstring& append(size_type n, value_type c) {
1384 resize(size() + n, c);
1388 template<class InputIterator>
1389 basic_fbstring& append(InputIterator first, InputIterator last) {
1390 insert(end(), first, last);
1394 basic_fbstring& append(std::initializer_list<value_type> il) {
1395 return append(il.begin(), il.end());
1398 void push_back(const value_type c) { // primitive
1399 store_.push_back(c);
1402 basic_fbstring& assign(const basic_fbstring& str) {
1403 if (&str == this) return *this;
1404 return assign(str.data(), str.size());
1407 basic_fbstring& assign(basic_fbstring&& str) {
1408 return *this = std::move(str);
1411 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1413 const size_type sz = str.size();
1414 enforce(pos <= sz, std::__throw_out_of_range, "");
1415 procrustes(n, sz - pos);
1416 return assign(str.data() + pos, n);
1419 basic_fbstring& assign(const value_type* s, const size_type n) {
1420 Invariant checker(*this);
1423 std::copy(s, s + n, begin());
1425 assert(size() == n);
1427 const value_type *const s2 = s + size();
1428 std::copy(s, s2, begin());
1429 append(s2, n - size());
1430 assert(size() == n);
1432 store_.writeTerminator();
1433 assert(size() == n);
1437 basic_fbstring& assign(const value_type* s) {
1438 return assign(s, traits_type::length(s));
1441 basic_fbstring& assign(std::initializer_list<value_type> il) {
1442 return assign(il.begin(), il.end());
1445 template <class ItOrLength, class ItOrChar>
1446 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1447 return replace(begin(), end(), first_or_n, last_or_c);
1450 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1451 return insert(pos1, str.data(), str.size());
1454 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1455 size_type pos2, size_type n) {
1456 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1457 procrustes(n, str.length() - pos2);
1458 return insert(pos1, str.data() + pos2, n);
1461 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1462 enforce(pos <= length(), std::__throw_out_of_range, "");
1463 insert(begin() + pos, s, s + n);
1467 basic_fbstring& insert(size_type pos, const value_type* s) {
1468 return insert(pos, s, traits_type::length(s));
1471 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1472 enforce(pos <= length(), std::__throw_out_of_range, "");
1473 insert(begin() + pos, n, c);
1477 iterator insert(const_iterator p, const value_type c) {
1478 const size_type pos = p - begin();
1480 return begin() + pos;
1484 template <int i> class Selector {};
1486 iterator insertImplDiscr(const_iterator p,
1487 size_type n, value_type c, Selector<1>) {
1488 Invariant checker(*this);
1490 auto const pos = p - begin();
1491 assert(p >= begin() && p <= end());
1492 if (capacity() - size() < n) {
1493 const size_type sz = p - begin();
1494 reserve(size() + n);
1497 const iterator oldEnd = end();
1498 if (n < size_type(oldEnd - p)) {
1499 append(oldEnd - n, oldEnd);
1501 // reverse_iterator(oldEnd - n),
1502 // reverse_iterator(p),
1503 // reverse_iterator(oldEnd));
1504 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1506 std::fill(begin() + pos, begin() + pos + n, c);
1508 append(n - (end() - p), c);
1509 append(iterator(p), oldEnd);
1510 std::fill(iterator(p), oldEnd, c);
1512 store_.writeTerminator();
1513 return begin() + pos;
1516 template<class InputIter>
1517 iterator insertImplDiscr(const_iterator i,
1518 InputIter b, InputIter e, Selector<0>) {
1519 return insertImpl(i, b, e,
1520 typename std::iterator_traits<InputIter>::iterator_category());
1523 template <class FwdIterator>
1524 iterator insertImpl(const_iterator i,
1525 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1526 Invariant checker(*this);
1528 const size_type pos = i - begin();
1529 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1530 std::distance(s1, s2);
1532 using namespace fbstring_detail;
1533 assert(pos <= size());
1535 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1536 capacity() - size();
1538 // realloc the string
1539 reserve(size() + n2);
1542 if (pos + n2 <= size()) {
1543 const iterator tailBegin = end() - n2;
1544 store_.expand_noinit(n2);
1545 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1546 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1547 reverse_iterator(tailBegin + n2));
1548 std::copy(s1, s2, begin() + pos);
1551 const size_type old_size = size();
1552 std::advance(t, old_size - pos);
1553 const size_t newElems = std::distance(t, s2);
1554 store_.expand_noinit(n2);
1555 std::copy(t, s2, begin() + old_size);
1556 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1557 begin() + old_size + newElems);
1558 std::copy(s1, t, begin() + pos);
1560 store_.writeTerminator();
1561 return begin() + pos;
1564 template <class InputIterator>
1565 iterator insertImpl(const_iterator i,
1566 InputIterator b, InputIterator e,
1567 std::input_iterator_tag) {
1568 const auto pos = i - begin();
1569 basic_fbstring temp(begin(), i);
1570 for (; b != e; ++b) {
1573 temp.append(i, cend());
1575 return begin() + pos;
1579 template <class ItOrLength, class ItOrChar>
1580 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1581 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1582 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1585 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1586 return insert(p, il.begin(), il.end());
1589 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1590 Invariant checker(*this);
1592 enforce(pos <= length(), std::__throw_out_of_range, "");
1593 procrustes(n, length() - pos);
1594 std::copy(begin() + pos + n, end(), begin() + pos);
1595 resize(length() - n);
1599 iterator erase(iterator position) {
1600 const size_type pos(position - begin());
1601 enforce(pos <= size(), std::__throw_out_of_range, "");
1603 return begin() + pos;
1606 iterator erase(iterator first, iterator last) {
1607 const size_type pos(first - begin());
1608 erase(pos, last - first);
1609 return begin() + pos;
1612 // Replaces at most n1 chars of *this, starting with pos1 with the
1614 basic_fbstring& replace(size_type pos1, size_type n1,
1615 const basic_fbstring& str) {
1616 return replace(pos1, n1, str.data(), str.size());
1619 // Replaces at most n1 chars of *this, starting with pos1,
1620 // with at most n2 chars of str starting with pos2
1621 basic_fbstring& replace(size_type pos1, size_type n1,
1622 const basic_fbstring& str,
1623 size_type pos2, size_type n2) {
1624 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1625 return replace(pos1, n1, str.data() + pos2,
1626 std::min(n2, str.size() - pos2));
1629 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1630 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1631 return replace(pos, n1, s, traits_type::length(s));
1634 // Replaces at most n1 chars of *this, starting with pos, with n2
1637 // consolidated with
1639 // Replaces at most n1 chars of *this, starting with pos, with at
1640 // most n2 chars of str. str must have at least n2 chars.
1641 template <class StrOrLength, class NumOrChar>
1642 basic_fbstring& replace(size_type pos, size_type n1,
1643 StrOrLength s_or_n2, NumOrChar n_or_c) {
1644 Invariant checker(*this);
1646 enforce(pos <= size(), std::__throw_out_of_range, "");
1647 procrustes(n1, length() - pos);
1648 const iterator b = begin() + pos;
1649 return replace(b, b + n1, s_or_n2, n_or_c);
1652 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1653 return replace(i1, i2, str.data(), str.length());
1656 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1657 return replace(i1, i2, s, traits_type::length(s));
1661 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1662 const value_type* s, size_type n,
1665 assert(begin() <= i1 && i1 <= end());
1666 assert(begin() <= i2 && i2 <= end());
1667 return replace(i1, i2, s, s + n);
1670 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1671 size_type n2, value_type c, Selector<1>) {
1672 const size_type n1 = i2 - i1;
1674 std::fill(i1, i1 + n2, c);
1677 std::fill(i1, i2, c);
1678 insert(i2, n2 - n1, c);
1684 template <class InputIter>
1685 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1686 InputIter b, InputIter e,
1688 replaceImpl(i1, i2, b, e,
1689 typename std::iterator_traits<InputIter>::iterator_category());
1694 template <class FwdIterator, class P>
1695 bool replaceAliased(iterator i1, iterator i2,
1696 FwdIterator s1, FwdIterator s2, P*) {
1700 template <class FwdIterator>
1701 bool replaceAliased(iterator i1, iterator i2,
1702 FwdIterator s1, FwdIterator s2, value_type*) {
1703 static const std::less_equal<const value_type*> le =
1704 std::less_equal<const value_type*>();
1705 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1709 // Aliased replace, copy to new string
1710 basic_fbstring temp;
1711 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1712 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1718 template <class FwdIterator>
1719 void replaceImpl(iterator i1, iterator i2,
1720 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1721 Invariant checker(*this);
1724 // Handle aliased replace
1725 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1729 auto const n1 = i2 - i1;
1731 auto const n2 = std::distance(s1, s2);
1736 std::copy(s1, s2, i1);
1740 fbstring_detail::copy_n(s1, n1, i1);
1741 std::advance(s1, n1);
1747 template <class InputIterator>
1748 void replaceImpl(iterator i1, iterator i2,
1749 InputIterator b, InputIterator e, std::input_iterator_tag) {
1750 basic_fbstring temp(begin(), i1);
1751 temp.append(b, e).append(i2, end());
1756 template <class T1, class T2>
1757 basic_fbstring& replace(iterator i1, iterator i2,
1758 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1760 num1 = std::numeric_limits<T1>::is_specialized,
1761 num2 = std::numeric_limits<T2>::is_specialized;
1762 return replaceImplDiscr(
1763 i1, i2, first_or_n_or_s, last_or_c_or_n,
1764 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1767 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1768 enforce(pos <= size(), std::__throw_out_of_range, "");
1769 procrustes(n, size() - pos);
1771 fbstring_detail::pod_copy(
1778 void swap(basic_fbstring& rhs) {
1779 store_.swap(rhs.store_);
1782 const value_type* c_str() const {
1783 return store_.c_str();
1786 const value_type* data() const { return c_str(); }
1788 allocator_type get_allocator() const {
1789 return allocator_type();
1792 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1793 return find(str.data(), pos, str.length());
1796 size_type find(const value_type* needle, const size_type pos,
1797 const size_type nsize) const {
1798 if (!nsize) return pos;
1799 auto const size = this->size();
1800 // nsize + pos can overflow (eg pos == npos), guard against that by checking
1801 // that nsize + pos does not wrap around.
1802 if (nsize + pos > size || nsize + pos < pos) return npos;
1803 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1804 // the last characters first
1805 auto const haystack = data();
1806 auto const nsize_1 = nsize - 1;
1807 auto const lastNeedle = needle[nsize_1];
1809 // Boyer-Moore skip value for the last char in the needle. Zero is
1810 // not a valid value; skip will be computed the first time it's
1814 const E * i = haystack + pos;
1815 auto iEnd = haystack + size - nsize_1;
1818 // Boyer-Moore: match the last element in the needle
1819 while (i[nsize_1] != lastNeedle) {
1825 // Here we know that the last char matches
1826 // Continue in pedestrian mode
1827 for (size_t j = 0; ; ) {
1829 if (i[j] != needle[j]) {
1830 // Not found, we can skip
1831 // Compute the skip value lazily
1834 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1841 // Check if done searching
1844 return i - haystack;
1851 size_type find(const value_type* s, size_type pos = 0) const {
1852 return find(s, pos, traits_type::length(s));
1855 size_type find (value_type c, size_type pos = 0) const {
1856 return find(&c, pos, 1);
1859 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1860 return rfind(str.data(), pos, str.length());
1863 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1864 if (n > length()) return npos;
1865 pos = std::min(pos, length() - n);
1866 if (n == 0) return pos;
1868 const_iterator i(begin() + pos);
1870 if (traits_type::eq(*i, *s)
1871 && traits_type::compare(&*i, s, n) == 0) {
1874 if (i == begin()) break;
1879 size_type rfind(const value_type* s, size_type pos = npos) const {
1880 return rfind(s, pos, traits_type::length(s));
1883 size_type rfind(value_type c, size_type pos = npos) const {
1884 return rfind(&c, pos, 1);
1887 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1888 return find_first_of(str.data(), pos, str.length());
1891 size_type find_first_of(const value_type* s,
1892 size_type pos, size_type n) const {
1893 if (pos > length() || n == 0) return npos;
1894 const_iterator i(begin() + pos),
1896 for (; i != finish; ++i) {
1897 if (traits_type::find(s, n, *i) != 0) {
1904 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1905 return find_first_of(s, pos, traits_type::length(s));
1908 size_type find_first_of(value_type c, size_type pos = 0) const {
1909 return find_first_of(&c, pos, 1);
1912 size_type find_last_of (const basic_fbstring& str,
1913 size_type pos = npos) const {
1914 return find_last_of(str.data(), pos, str.length());
1917 size_type find_last_of (const value_type* s, size_type pos,
1918 size_type n) const {
1919 if (!empty() && n > 0) {
1920 pos = std::min(pos, length() - 1);
1921 const_iterator i(begin() + pos);
1923 if (traits_type::find(s, n, *i) != 0) {
1926 if (i == begin()) break;
1932 size_type find_last_of (const value_type* s,
1933 size_type pos = npos) const {
1934 return find_last_of(s, pos, traits_type::length(s));
1937 size_type find_last_of (value_type c, size_type pos = npos) const {
1938 return find_last_of(&c, pos, 1);
1941 size_type find_first_not_of(const basic_fbstring& str,
1942 size_type pos = 0) const {
1943 return find_first_not_of(str.data(), pos, str.size());
1946 size_type find_first_not_of(const value_type* s, size_type pos,
1947 size_type n) const {
1948 if (pos < length()) {
1952 for (; i != finish; ++i) {
1953 if (traits_type::find(s, n, *i) == 0) {
1961 size_type find_first_not_of(const value_type* s,
1962 size_type pos = 0) const {
1963 return find_first_not_of(s, pos, traits_type::length(s));
1966 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1967 return find_first_not_of(&c, pos, 1);
1970 size_type find_last_not_of(const basic_fbstring& str,
1971 size_type pos = npos) const {
1972 return find_last_not_of(str.data(), pos, str.length());
1975 size_type find_last_not_of(const value_type* s, size_type pos,
1976 size_type n) const {
1977 if (!this->empty()) {
1978 pos = std::min(pos, size() - 1);
1979 const_iterator i(begin() + pos);
1981 if (traits_type::find(s, n, *i) == 0) {
1984 if (i == begin()) break;
1990 size_type find_last_not_of(const value_type* s,
1991 size_type pos = npos) const {
1992 return find_last_not_of(s, pos, traits_type::length(s));
1995 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1996 return find_last_not_of(&c, pos, 1);
1999 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
2000 enforce(pos <= size(), std::__throw_out_of_range, "");
2001 return basic_fbstring(data() + pos, std::min(n, size() - pos));
2004 int compare(const basic_fbstring& str) const {
2005 // FIX due to Goncalo N M de Carvalho July 18, 2005
2006 return compare(0, size(), str);
2009 int compare(size_type pos1, size_type n1,
2010 const basic_fbstring& str) const {
2011 return compare(pos1, n1, str.data(), str.size());
2014 int compare(size_type pos1, size_type n1,
2015 const value_type* s) const {
2016 return compare(pos1, n1, s, traits_type::length(s));
2019 int compare(size_type pos1, size_type n1,
2020 const value_type* s, size_type n2) const {
2021 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2022 procrustes(n1, size() - pos1);
2023 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2024 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2025 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2028 int compare(size_type pos1, size_type n1,
2029 const basic_fbstring& str,
2030 size_type pos2, size_type n2) const {
2031 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2032 return compare(pos1, n1, str.data() + pos2,
2033 std::min(n2, str.size() - pos2));
2036 // Code from Jean-Francois Bastien (03/26/2007)
2037 int compare(const value_type* s) const {
2038 // Could forward to compare(0, size(), s, traits_type::length(s))
2039 // but that does two extra checks
2040 const size_type n1(size()), n2(traits_type::length(s));
2041 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2042 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2050 // non-member functions
2052 template <typename E, class T, class A, class S>
2054 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2055 const basic_fbstring<E, T, A, S>& rhs) {
2057 basic_fbstring<E, T, A, S> result;
2058 result.reserve(lhs.size() + rhs.size());
2059 result.append(lhs).append(rhs);
2060 return std::move(result);
2064 template <typename E, class T, class A, class S>
2066 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2067 const basic_fbstring<E, T, A, S>& rhs) {
2068 return std::move(lhs.append(rhs));
2072 template <typename E, class T, class A, class S>
2074 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2075 basic_fbstring<E, T, A, S>&& rhs) {
2076 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2077 // Good, at least we don't need to reallocate
2078 return std::move(rhs.insert(0, lhs));
2080 // Meh, no go. Forward to operator+(const&, const&).
2081 auto const& rhsC = rhs;
2086 template <typename E, class T, class A, class S>
2088 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2089 basic_fbstring<E, T, A, S>&& rhs) {
2090 return std::move(lhs.append(rhs));
2093 template <typename E, class T, class A, class S>
2095 basic_fbstring<E, T, A, S> operator+(
2096 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2097 const basic_fbstring<E, T, A, S>& rhs) {
2099 basic_fbstring<E, T, A, S> result;
2100 const typename basic_fbstring<E, T, A, S>::size_type len =
2101 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2102 result.reserve(len + rhs.size());
2103 result.append(lhs, len).append(rhs);
2107 template <typename E, class T, class A, class S>
2109 basic_fbstring<E, T, A, S> operator+(
2110 typename basic_fbstring<E, T, A, S>::value_type lhs,
2111 const basic_fbstring<E, T, A, S>& rhs) {
2113 basic_fbstring<E, T, A, S> result;
2114 result.reserve(1 + rhs.size());
2115 result.push_back(lhs);
2120 template <typename E, class T, class A, class S>
2122 basic_fbstring<E, T, A, S> operator+(
2123 const basic_fbstring<E, T, A, S>& lhs,
2124 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2126 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2127 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2129 basic_fbstring<E, T, A, S> result;
2130 const size_type len = traits_type::length(rhs);
2131 result.reserve(lhs.size() + len);
2132 result.append(lhs).append(rhs, len);
2136 template <typename E, class T, class A, class S>
2138 basic_fbstring<E, T, A, S> operator+(
2139 const basic_fbstring<E, T, A, S>& lhs,
2140 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2142 basic_fbstring<E, T, A, S> result;
2143 result.reserve(lhs.size() + 1);
2145 result.push_back(rhs);
2149 template <typename E, class T, class A, class S>
2151 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2152 const basic_fbstring<E, T, A, S>& rhs) {
2153 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2155 template <typename E, class T, class A, class S>
2157 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2158 const basic_fbstring<E, T, A, S>& rhs) {
2159 return rhs == lhs; }
2161 template <typename E, class T, class A, class S>
2163 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2164 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2165 return lhs.compare(rhs) == 0; }
2167 template <typename E, class T, class A, class S>
2169 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2170 const basic_fbstring<E, T, A, S>& rhs) {
2171 return !(lhs == rhs); }
2173 template <typename E, class T, class A, class S>
2175 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2176 const basic_fbstring<E, T, A, S>& rhs) {
2177 return !(lhs == rhs); }
2179 template <typename E, class T, class A, class S>
2181 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2182 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2183 return !(lhs == rhs); }
2185 template <typename E, class T, class A, class S>
2187 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2188 const basic_fbstring<E, T, A, S>& rhs) {
2189 return lhs.compare(rhs) < 0; }
2191 template <typename E, class T, class A, class S>
2193 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2194 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2195 return lhs.compare(rhs) < 0; }
2197 template <typename E, class T, class A, class S>
2199 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2200 const basic_fbstring<E, T, A, S>& rhs) {
2201 return rhs.compare(lhs) > 0; }
2203 template <typename E, class T, class A, class S>
2205 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2206 const basic_fbstring<E, T, A, S>& rhs) {
2209 template <typename E, class T, class A, class S>
2211 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2212 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2215 template <typename E, class T, class A, class S>
2217 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2218 const basic_fbstring<E, T, A, S>& rhs) {
2221 template <typename E, class T, class A, class S>
2223 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2224 const basic_fbstring<E, T, A, S>& rhs) {
2225 return !(rhs < lhs); }
2227 template <typename E, class T, class A, class S>
2229 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2230 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2231 return !(rhs < lhs); }
2233 template <typename E, class T, class A, class S>
2235 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2236 const basic_fbstring<E, T, A, S>& rhs) {
2237 return !(rhs < lhs); }
2239 template <typename E, class T, class A, class S>
2241 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2242 const basic_fbstring<E, T, A, S>& rhs) {
2243 return !(lhs < rhs); }
2245 template <typename E, class T, class A, class S>
2247 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2248 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2249 return !(lhs < rhs); }
2251 template <typename E, class T, class A, class S>
2253 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2254 const basic_fbstring<E, T, A, S>& rhs) {
2255 return !(lhs < rhs);
2259 template <typename E, class T, class A, class S>
2260 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2264 // TODO: make this faster.
2265 template <typename E, class T, class A, class S>
2268 typename basic_fbstring<E, T, A, S>::value_type,
2269 typename basic_fbstring<E, T, A, S>::traits_type>&
2271 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2272 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2273 basic_fbstring<E, T, A, S>& str) {
2274 typename std::basic_istream<E, T>::sentry sentry(is);
2275 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2276 typename basic_fbstring<E, T, A, S>::traits_type>
2278 typedef typename __istream_type::ios_base __ios_base;
2279 size_t extracted = 0;
2280 auto err = __ios_base::goodbit;
2282 auto n = is.width();
2287 auto got = is.rdbuf()->sgetc();
2288 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2289 // Whew. We get to store this guy
2291 got = is.rdbuf()->snextc();
2293 if (got == T::eof()) {
2294 err |= __ios_base::eofbit;
2299 err |= __ios_base::failbit;
2307 template <typename E, class T, class A, class S>
2309 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2310 typename basic_fbstring<E, T, A, S>::traits_type>&
2312 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2313 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2314 const basic_fbstring<E, T, A, S>& str) {
2316 typename std::basic_ostream<
2317 typename basic_fbstring<E, T, A, S>::value_type,
2318 typename basic_fbstring<E, T, A, S>::traits_type>::sentry __s(os);
2320 typedef std::ostreambuf_iterator<
2321 typename basic_fbstring<E, T, A, S>::value_type,
2322 typename basic_fbstring<E, T, A, S>::traits_type> _Ip;
2323 size_t __len = str.size();
2325 (os.flags() & std::ios_base::adjustfield) == std::ios_base::left;
2326 if (__pad_and_output(_Ip(os),
2328 __left ? str.data() + __len : str.data(),
2331 os.fill()).failed()) {
2332 os.setstate(std::ios_base::badbit | std::ios_base::failbit);
2336 std::__ostream_insert(os, str.data(), str.size());
2341 #ifndef _LIBSTDCXX_FBSTRING
2343 template <typename E, class T, class A, class S>
2345 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2346 typename basic_fbstring<E, T, A, S>::traits_type>&
2348 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2349 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2350 basic_fbstring<E, T, A, S>& str,
2351 typename basic_fbstring<E, T, A, S>::value_type delim) {
2352 // Use the nonstandard getdelim()
2356 // This looks quadratic but it really depends on realloc
2357 auto const newSize = size + 128;
2358 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2359 is.getline(buf + size, newSize - size, delim);
2360 if (is.bad() || is.eof() || !is.fail()) {
2361 // done by either failure, end of file, or normal read
2362 size += std::strlen(buf + size);
2365 // Here we have failed due to too short a buffer
2366 // Minus one to discount the terminating '\0'
2368 assert(buf[size] == 0);
2369 // Clear the error so we can continue reading
2372 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2373 AcquireMallocatedString());
2378 template <typename E, class T, class A, class S>
2380 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2381 typename basic_fbstring<E, T, A, S>::traits_type>&
2383 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2384 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2385 basic_fbstring<E, T, A, S>& str) {
2386 // Just forward to the version with a delimiter
2387 return getline(is, str, '\n');
2392 template <typename E1, class T, class A, class S>
2393 const typename basic_fbstring<E1, T, A, S>::size_type
2394 basic_fbstring<E1, T, A, S>::npos =
2395 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2397 #ifndef _LIBSTDCXX_FBSTRING
2398 // basic_string compatibility routines
2400 template <typename E, class T, class A, class S>
2402 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2403 const std::string& rhs) {
2404 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2407 template <typename E, class T, class A, class S>
2409 bool operator==(const std::string& lhs,
2410 const basic_fbstring<E, T, A, S>& rhs) {
2414 template <typename E, class T, class A, class S>
2416 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2417 const std::string& rhs) {
2418 return !(lhs == rhs);
2421 template <typename E, class T, class A, class S>
2423 bool operator!=(const std::string& lhs,
2424 const basic_fbstring<E, T, A, S>& rhs) {
2425 return !(lhs == rhs);
2428 #if !defined(_LIBSTDCXX_FBSTRING)
2429 typedef basic_fbstring<char> fbstring;
2432 // fbstring is relocatable
2433 template <class T, class R, class A, class S>
2434 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2437 _GLIBCXX_END_NAMESPACE_VERSION
2440 } // namespace folly
2442 #pragma GCC diagnostic pop
2444 #ifndef _LIBSTDCXX_FBSTRING
2448 struct hash< ::folly::fbstring> {
2449 size_t operator()(const ::folly::fbstring& s) const {
2450 return ::folly::hash::fnv32_buf(s.data(), s.size());
2455 #endif // _LIBSTDCXX_FBSTRING
2457 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2459 #undef FBSTRING_LIKELY
2460 #undef FBSTRING_UNLIKELY
2462 #endif // FOLLY_BASE_FBSTRING_H_