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.
117 #if defined(__clang__)
118 # if __has_attribute(__no_address_safety_analysis__)
119 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
120 __attribute__((__no_address_safety_analysis__))
121 # elif __has_attribute(__no_sanitize_address__)
122 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
123 __attribute__((__no_sanitize_address__))
125 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
127 #elif defined (__GNUC__) && (__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)
128 # define FBSTRING_DISABLE_ADDRESS_SANITIZER \
129 __attribute__((__no_address_safety_analysis__))
131 # define FBSTRING_DISABLE_ADDRESS_SANITIZER
134 namespace fbstring_detail {
136 template <class InIt, class OutIt>
139 typename std::iterator_traits<InIt>::difference_type n,
141 for (; n != 0; --n, ++b, ++d) {
142 assert((const void*)&*d != &*b);
148 template <class Pod, class T>
149 inline void pod_fill(Pod* b, Pod* e, T c) {
150 assert(b && e && b <= e);
151 /*static*/ if (sizeof(T) == 1) {
154 auto const ee = b + ((e - b) & ~7u);
155 for (; b != ee; b += 8) {
166 for (; b != e; ++b) {
173 * Lightly structured memcpy, simplifies copying PODs and introduces
174 * some asserts. Unfortunately using this function may cause
175 * measurable overhead (presumably because it adjusts from a begin/end
176 * convention to a pointer/size convention, so it does some extra
177 * arithmetic even though the caller might have done the inverse
178 * adaptation outside).
181 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
183 assert(d >= e || d + (e - b) <= b);
184 memcpy(d, b, (e - b) * sizeof(Pod));
188 * Lightly structured memmove, simplifies copying PODs and introduces
192 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
194 memmove(d, b, (e - b) * sizeof(*b));
197 } // namespace fbstring_detail
200 * Defines a special acquisition method for constructing fbstring
201 * objects. AcquireMallocatedString means that the user passes a
202 * pointer to a malloc-allocated string that the fbstring object will
205 enum class AcquireMallocatedString {};
208 * fbstring_core_model is a mock-up type that defines all required
209 * signatures of a fbstring core. The fbstring class itself uses such
210 * a core object to implement all of the numerous member functions
211 * required by the standard.
213 * If you want to define a new core, copy the definition below and
214 * implement the primitives. Then plug the core into basic_fbstring as
215 * a template argument.
217 template <class Char>
218 class fbstring_core_model {
220 fbstring_core_model();
221 fbstring_core_model(const fbstring_core_model &);
222 ~fbstring_core_model();
223 // Returns a pointer to string's buffer (currently only contiguous
224 // strings are supported). The pointer is guaranteed to be valid
225 // until the next call to a non-const member function.
226 const Char * data() const;
227 // Much like data(), except the string is prepared to support
228 // character-level changes. This call is a signal for
229 // e.g. reference-counted implementation to fork the data. The
230 // pointer is guaranteed to be valid until the next call to a
231 // non-const member function.
232 Char * mutable_data();
233 // Returns a pointer to string's buffer and guarantees that a
234 // readable '\0' lies right after the buffer. The pointer is
235 // guaranteed to be valid until the next call to a non-const member
237 const Char * c_str() const;
238 // Shrinks the string by delta characters. Asserts that delta <=
240 void shrink(size_t delta);
241 // Expands the string by delta characters (i.e. after this call
242 // size() will report the old size() plus delta) but without
243 // initializing the expanded region. Returns a pointer to the memory
244 // to be initialized (the beginning of the expanded portion). The
245 // caller is expected to fill the expanded area appropriately.
246 Char* expand_noinit(size_t delta);
247 // Expands the string by one character and sets the last character
249 void push_back(Char c);
250 // Returns the string's size.
252 // Returns the string's capacity, i.e. maximum size that the string
253 // can grow to without reallocation. Note that for reference counted
254 // strings that's technically a lie - even assigning characters
255 // within the existing size would cause a reallocation.
256 size_t capacity() const;
257 // Returns true if the data underlying the string is actually shared
258 // across multiple strings (in a refcounted fashion).
259 bool isShared() const;
260 // Makes sure that at least minCapacity characters are available for
261 // the string without reallocation. For reference-counted strings,
262 // it should fork the data even if minCapacity < size().
263 void reserve(size_t minCapacity);
266 fbstring_core_model& operator=(const fbstring_core_model &);
271 * gcc-4.7 throws what appears to be some false positive uninitialized
272 * warnings for the members of the MediumLarge struct. So, mute them here.
274 #if defined(__GNUC__) && !defined(__clang__)
275 # pragma GCC diagnostic push
276 # pragma GCC diagnostic ignored "-Wuninitialized"
280 * This is the core of the string. The code should work on 32- and
281 * 64-bit architectures and with any Char size. Porting to big endian
282 * architectures would require some changes.
284 * The storage is selected as follows (assuming we store one-byte
285 * characters on a 64-bit machine): (a) "small" strings between 0 and
286 * 23 chars are stored in-situ without allocation (the rightmost byte
287 * stores the size); (b) "medium" strings from 24 through 254 chars
288 * are stored in malloc-allocated memory that is copied eagerly; (c)
289 * "large" strings of 255 chars and above are stored in a similar
290 * structure as medium arrays, except that the string is
291 * reference-counted and copied lazily. the reference count is
292 * allocated right before the character array.
294 * The discriminator between these three strategies sits in the two
295 * most significant bits of the rightmost char of the storage. If
296 * neither is set, then the string is small (and its length sits in
297 * the lower-order bits of that rightmost character). If the MSb is
298 * set, the string is medium width. If the second MSb is set, then the
301 template <class Char> class fbstring_core {
304 // Only initialize the tag, will set the MSBs (i.e. the small
305 // string size) to zero too
306 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
307 // or: setSmallSize(0);
309 assert(category() == isSmall && size() == 0);
312 fbstring_core(const fbstring_core & rhs) {
313 assert(&rhs != this);
314 // Simplest case first: small strings are bitblitted
315 if (rhs.category() == isSmall) {
316 assert(offsetof(MediumLarge, data_) == 0);
317 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
318 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
319 const size_t size = rhs.smallSize();
321 ml_.capacity_ = rhs.ml_.capacity_;
324 // Just write the whole thing, don't look at details. In
325 // particular we need to copy capacity anyway because we want
326 // to set the size (don't forget that the last character,
327 // which stores a short string's length, is shared with the
328 // ml_.capacity field).
331 assert(category() == isSmall && this->size() == rhs.size());
332 } else if (rhs.category() == isLarge) {
333 // Large strings are just refcounted
335 RefCounted::incrementRefs(ml_.data_);
336 assert(category() == isLarge && size() == rhs.size());
338 // Medium strings are copied eagerly. Don't forget to allocate
339 // one extra Char for the null terminator.
340 auto const allocSize =
341 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
342 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
343 fbstring_detail::pod_copy(rhs.ml_.data_,
345 rhs.ml_.data_ + rhs.ml_.size_ + 1,
347 // No need for writeTerminator() here, we copied one extra
348 // element just above.
349 ml_.size_ = rhs.ml_.size_;
350 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
351 assert(category() == isMedium);
353 assert(size() == rhs.size());
354 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
357 fbstring_core(fbstring_core&& goner) {
358 if (goner.category() == isSmall) {
359 // Just copy, leave the goner in peace
360 new(this) fbstring_core(goner.small_, goner.smallSize());
364 // Clean goner's carcass
365 goner.setSmallSize(0);
369 // NOTE(agallagher): The word-aligned copy path copies bytes which are
370 // outside the range of the string, and makes address sanitizer unhappy,
371 // so just disable it on this function.
372 fbstring_core(const Char *const data, const size_t size)
373 FBSTRING_DISABLE_ADDRESS_SANITIZER {
374 // Simplest case first: small strings are bitblitted
375 if (size <= maxSmallSize) {
376 // Layout is: Char* data_, size_t size_, size_t capacity_
377 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
378 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
379 // sizeof(size_t) must be a power of 2
380 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
382 // If data is aligned, use fast word-wise copying. Otherwise,
383 // use conservative memcpy.
384 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
385 fbstring_detail::pod_copy(data, data + size, small_);
387 // Copy one word (64 bits) at a time
388 const size_t byteSize = size * sizeof(Char);
389 if (byteSize > 2 * sizeof(size_t)) {
391 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
393 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
395 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
396 } else if (byteSize > sizeof(size_t)) {
399 } else if (size > 0) {
405 } else if (size <= maxMediumSize) {
406 // Medium strings are allocated normally. Don't forget to
407 // allocate one extra Char for the terminating null.
408 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
409 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
410 fbstring_detail::pod_copy(data, data + size, ml_.data_);
412 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
414 // Large strings are allocated differently
415 size_t effectiveCapacity = size;
416 auto const newRC = RefCounted::create(data, & effectiveCapacity);
417 ml_.data_ = newRC->data_;
419 ml_.capacity_ = effectiveCapacity | isLarge;
422 assert(this->size() == size);
423 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
427 auto const c = category();
435 RefCounted::decrementRefs(ml_.data_);
438 // Snatches a previously mallocated string. The parameter "size"
439 // is the size of the string, and the parameter "capacity" is the size
440 // of the mallocated block. The string must be \0-terminated, so
441 // data[size] == '\0' and capacity >= size + 1.
443 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
444 // "size", and pass 3 as "capacity".
445 fbstring_core(Char *const data, const size_t size,
446 const size_t capacity,
447 AcquireMallocatedString) {
449 assert(capacity > size);
450 assert(data[size] == '\0');
451 // Use the medium string storage
454 ml_.capacity_ = capacity | isMedium;
456 // No need for the memory
462 // swap below doesn't test whether &rhs == this (and instead
463 // potentially does extra work) on the premise that the rarity of
464 // that situation actually makes the check more expensive than is
466 void swap(fbstring_core & rhs) {
472 // In C++11 data() and c_str() are 100% equivalent.
473 const Char * data() const {
477 Char * mutable_data() {
478 auto const c = category();
482 assert(c == isMedium || c == isLarge);
483 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
485 size_t effectiveCapacity = ml_.capacity();
486 auto const newRC = RefCounted::create(& effectiveCapacity);
487 // If this fails, someone placed the wrong capacity in an
489 assert(effectiveCapacity >= ml_.capacity());
490 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
492 RefCounted::decrementRefs(ml_.data_);
493 ml_.data_ = newRC->data_;
494 // No need to call writeTerminator(), we have + 1 above.
499 const Char * c_str() const {
500 auto const c = category();
501 #ifdef FBSTRING_PERVERSE
503 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
504 || small_[smallSize()] == '\0');
505 small_[smallSize()] = '\0';
508 assert(c == isMedium || c == isLarge);
509 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
510 ml_.data_[ml_.size_] = '\0';
511 #elif defined(FBSTRING_CONSERVATIVE)
513 assert(small_[smallSize()] == '\0');
516 assert(c == isMedium || c == isLarge);
517 assert(ml_.data_[ml_.size_] == '\0');
520 small_[smallSize()] = '\0';
523 assert(c == isMedium || c == isLarge);
524 ml_.data_[ml_.size_] = '\0';
529 void shrink(const size_t delta) {
530 if (category() == isSmall) {
531 // Check for underflow
532 assert(delta <= smallSize());
533 setSmallSize(smallSize() - delta);
534 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
535 // Medium strings and unique large strings need no special
537 assert(ml_.size_ >= delta);
540 assert(ml_.size_ >= delta);
541 // Shared large string, must make unique. This is because of the
542 // durn terminator must be written, which may trample the shared
545 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
547 // No need to write the terminator.
553 void reserve(size_t minCapacity) {
554 if (category() == isLarge) {
556 if (RefCounted::refs(ml_.data_) > 1) {
557 // We must make it unique regardless; in-place reallocation is
558 // useless if the string is shared. In order to not surprise
559 // people, reserve the new block at current capacity or
560 // more. That way, a string's capacity never shrinks after a
562 minCapacity = std::max(minCapacity, ml_.capacity());
563 auto const newRC = RefCounted::create(& minCapacity);
564 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
566 // Done with the old data. No need to call writeTerminator(),
567 // we have + 1 above.
568 RefCounted::decrementRefs(ml_.data_);
569 ml_.data_ = newRC->data_;
570 ml_.capacity_ = minCapacity | isLarge;
571 // size remains unchanged
573 // String is not shared, so let's try to realloc (if needed)
574 if (minCapacity > ml_.capacity()) {
575 // Asking for more memory
577 RefCounted::reallocate(ml_.data_, ml_.size_,
578 ml_.capacity(), minCapacity);
579 ml_.data_ = newRC->data_;
580 ml_.capacity_ = minCapacity | isLarge;
583 assert(capacity() >= minCapacity);
585 } else if (category() == isMedium) {
586 // String is not shared
587 if (minCapacity <= ml_.capacity()) {
588 return; // nothing to do, there's enough room
590 if (minCapacity <= maxMediumSize) {
591 // Keep the string at medium size. Don't forget to allocate
592 // one extra Char for the terminating null.
593 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
594 ml_.data_ = static_cast<Char *>(
597 ml_.size_ * sizeof(Char),
598 ml_.capacity() * sizeof(Char),
601 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
603 // Conversion from medium to large string
604 fbstring_core nascent;
605 // Will recurse to another branch of this function
606 nascent.reserve(minCapacity);
607 nascent.ml_.size_ = ml_.size_;
608 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
612 assert(capacity() >= minCapacity);
615 assert(category() == isSmall);
616 if (minCapacity > maxMediumSize) {
618 auto const newRC = RefCounted::create(& minCapacity);
619 auto const size = smallSize();
620 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
621 // No need for writeTerminator(), we wrote it above with + 1.
622 ml_.data_ = newRC->data_;
624 ml_.capacity_ = minCapacity | isLarge;
625 assert(capacity() >= minCapacity);
626 } else if (minCapacity > maxSmallSize) {
628 // Don't forget to allocate one extra Char for the terminating null
629 auto const allocSizeBytes =
630 goodMallocSize((1 + minCapacity) * sizeof(Char));
631 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
632 auto const size = smallSize();
633 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
634 // No need for writeTerminator(), we wrote it above with + 1.
637 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
640 // Nothing to do, everything stays put
643 assert(capacity() >= minCapacity);
646 Char * expand_noinit(const size_t delta) {
647 // Strategy is simple: make room, then change size
648 assert(capacity() >= size());
650 if (category() == isSmall) {
653 if (newSz <= maxSmallSize) {
661 newSz = ml_.size_ + delta;
662 if (newSz > capacity()) {
666 assert(capacity() >= newSz);
667 // Category can't be small - we took care of that above
668 assert(category() == isMedium || category() == isLarge);
671 assert(size() == newSz);
672 return ml_.data_ + sz;
675 void push_back(Char c) {
676 assert(capacity() >= size());
678 if (category() == isSmall) {
680 if (sz < maxSmallSize) {
681 setSmallSize(sz + 1);
686 reserve(maxSmallSize * 2);
689 if (sz == capacity()) { // always true for isShared()
690 reserve(sz * 3 / 2); // ensures not shared
694 assert(capacity() >= sz + 1);
695 // Category can't be small - we took care of that above
696 assert(category() == isMedium || category() == isLarge);
702 size_t size() const {
703 return category() == isSmall ? smallSize() : ml_.size_;
706 size_t capacity() const {
707 switch (category()) {
711 // For large-sized strings, a multi-referenced chunk has no
712 // available capacity. This is because any attempt to append
713 // data would trigger a new allocation.
714 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
717 return ml_.capacity();
720 bool isShared() const {
721 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
724 #ifdef FBSTRING_PERVERSE
725 enum { TERMINATOR = '^' };
727 enum { TERMINATOR = '\0' };
730 void writeTerminator() {
731 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
732 if (category() == isSmall) {
733 const auto s = smallSize();
734 if (s != maxSmallSize) {
735 small_[s] = TERMINATOR;
738 ml_.data_[ml_.size_] = TERMINATOR;
745 fbstring_core & operator=(const fbstring_core & rhs);
752 size_t capacity() const {
753 return capacity_ & capacityExtractMask;
758 std::atomic<size_t> refCount_;
761 static RefCounted * fromData(Char * p) {
762 return static_cast<RefCounted*>(
764 static_cast<unsigned char*>(static_cast<void*>(p))
765 - sizeof(refCount_)));
768 static size_t refs(Char * p) {
769 return fromData(p)->refCount_.load(std::memory_order_acquire);
772 static void incrementRefs(Char * p) {
773 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
776 static void decrementRefs(Char * p) {
777 auto const dis = fromData(p);
778 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
785 static RefCounted * create(size_t * size) {
786 // Don't forget to allocate one extra Char for the terminating
787 // null. In this case, however, one Char is already part of the
789 const size_t allocSize = goodMallocSize(
790 sizeof(RefCounted) + *size * sizeof(Char));
791 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
792 result->refCount_.store(1, std::memory_order_release);
793 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
797 static RefCounted * create(const Char * data, size_t * size) {
798 const size_t effectiveSize = *size;
799 auto result = create(size);
800 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
804 static RefCounted * reallocate(Char *const data,
805 const size_t currentSize,
806 const size_t currentCapacity,
807 const size_t newCapacity) {
808 assert(newCapacity > 0 && newCapacity > currentSize);
809 auto const dis = fromData(data);
810 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
811 // Don't forget to allocate one extra Char for the terminating
812 // null. In this case, however, one Char is already part of the
814 auto result = static_cast<RefCounted*>(
816 sizeof(RefCounted) + currentSize * sizeof(Char),
817 sizeof(RefCounted) + currentCapacity * sizeof(Char),
818 sizeof(RefCounted) + newCapacity * sizeof(Char)));
819 assert(result->refCount_.load(std::memory_order_acquire) == 1);
825 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
826 mutable MediumLarge ml_;
830 lastChar = sizeof(MediumLarge) - 1,
831 maxSmallSize = lastChar / sizeof(Char),
832 maxMediumSize = 254 / sizeof(Char), // coincides with the small
833 // bin size in dlmalloc
834 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
835 capacityExtractMask = ~categoryExtractMask,
837 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
838 "Corrupt memory layout for fbstring.");
842 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
843 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
846 Category category() const {
847 // Assumes little endian
848 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
851 size_t smallSize() const {
852 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
853 return static_cast<size_t>(maxSmallSize)
854 - static_cast<size_t>(small_[maxSmallSize]);
857 void setSmallSize(size_t s) {
858 // Warning: this should work with uninitialized strings too,
859 // so don't assume anything about the previous value of
860 // small_[maxSmallSize].
861 assert(s <= maxSmallSize);
862 small_[maxSmallSize] = maxSmallSize - s;
866 #if defined(__GNUC__) && !defined(__clang__)
867 # pragma GCC diagnostic pop
870 #ifndef _LIBSTDCXX_FBSTRING
872 * Dummy fbstring core that uses an actual std::string. This doesn't
873 * make any sense - it's just for testing purposes.
875 template <class Char>
876 class dummy_fbstring_core {
878 dummy_fbstring_core() {
880 dummy_fbstring_core(const dummy_fbstring_core& another)
881 : backend_(another.backend_) {
883 dummy_fbstring_core(const Char * s, size_t n)
886 void swap(dummy_fbstring_core & rhs) {
887 backend_.swap(rhs.backend_);
889 const Char * data() const {
890 return backend_.data();
892 Char * mutable_data() {
893 //assert(!backend_.empty());
894 return &*backend_.begin();
896 void shrink(size_t delta) {
897 assert(delta <= size());
898 backend_.resize(size() - delta);
900 Char * expand_noinit(size_t delta) {
901 auto const sz = size();
902 backend_.resize(size() + delta);
903 return backend_.data() + sz;
905 void push_back(Char c) {
906 backend_.push_back(c);
908 size_t size() const {
909 return backend_.size();
911 size_t capacity() const {
912 return backend_.capacity();
914 bool isShared() const {
917 void reserve(size_t minCapacity) {
918 backend_.reserve(minCapacity);
922 std::basic_string<Char> backend_;
924 #endif // !_LIBSTDCXX_FBSTRING
927 * This is the basic_string replacement. For conformity,
928 * basic_fbstring takes the same template parameters, plus the last
929 * one which is the core.
931 #ifdef _LIBSTDCXX_FBSTRING
932 template <typename E, class T, class A, class Storage>
934 template <typename E,
935 class T = std::char_traits<E>,
936 class A = std::allocator<E>,
937 class Storage = fbstring_core<E> >
939 class basic_fbstring {
943 void (*throw_exc)(const char*),
945 if (!condition) throw_exc(msg);
948 bool isSane() const {
951 empty() == (size() == 0) &&
952 empty() == (begin() == end()) &&
953 size() <= max_size() &&
954 capacity() <= max_size() &&
955 size() <= capacity() &&
956 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
960 friend struct Invariant;
963 explicit Invariant(const basic_fbstring& s) : s_(s) {
970 const basic_fbstring& s_;
972 explicit Invariant(const basic_fbstring&) {}
974 Invariant& operator=(const Invariant&);
979 typedef T traits_type;
980 typedef typename traits_type::char_type value_type;
981 typedef A allocator_type;
982 typedef typename A::size_type size_type;
983 typedef typename A::difference_type difference_type;
985 typedef typename A::reference reference;
986 typedef typename A::const_reference const_reference;
987 typedef typename A::pointer pointer;
988 typedef typename A::const_pointer const_pointer;
991 typedef const E* const_iterator;
992 typedef std::reverse_iterator<iterator
993 #ifdef NO_ITERATOR_TRAITS
997 typedef std::reverse_iterator<const_iterator
998 #ifdef NO_ITERATOR_TRAITS
1001 > const_reverse_iterator;
1003 static const size_type npos; // = size_type(-1)
1006 static void procrustes(size_type& n, size_type nmax) {
1007 if (n > nmax) n = nmax;
1011 // C++11 21.4.2 construct/copy/destroy
1012 explicit basic_fbstring(const A& a = A()) {
1015 basic_fbstring(const basic_fbstring& str)
1016 : store_(str.store_) {
1020 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
1023 #ifndef _LIBSTDCXX_FBSTRING
1024 // This is defined for compatibility with std::string
1025 /* implicit */ basic_fbstring(const std::string& str)
1026 : store_(str.data(), str.size()) {
1030 basic_fbstring(const basic_fbstring& str, size_type pos,
1031 size_type n = npos, const A& a = A()) {
1032 assign(str, pos, n);
1035 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1036 : store_(s, s ? traits_type::length(s) : ({
1037 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1038 err += ": null pointer initializer not valid";
1039 std::__throw_logic_error(err.c_str());
1044 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1048 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1049 auto const data = store_.expand_noinit(n);
1050 fbstring_detail::pod_fill(data, data + n, c);
1051 store_.writeTerminator();
1054 template <class InIt>
1055 basic_fbstring(InIt begin, InIt end,
1056 typename std::enable_if<
1057 !std::is_same<typename std::remove_const<InIt>::type,
1058 value_type*>::value, const A>::type & a = A()) {
1062 // Specialization for const char*, const char*
1063 basic_fbstring(const value_type* b, const value_type* e)
1064 : store_(b, e - b) {
1067 // Nonstandard constructor
1068 basic_fbstring(value_type *s, size_type n, size_type c,
1069 AcquireMallocatedString a)
1070 : store_(s, n, c, a) {
1073 // Construction from initialization list
1074 basic_fbstring(std::initializer_list<value_type> il) {
1075 assign(il.begin(), il.end());
1081 basic_fbstring& operator=(const basic_fbstring& lhs) {
1082 if (FBSTRING_UNLIKELY(&lhs == this)) {
1085 auto const oldSize = size();
1086 auto const srcSize = lhs.size();
1087 if (capacity() >= srcSize && !store_.isShared()) {
1088 // great, just copy the contents
1089 if (oldSize < srcSize)
1090 store_.expand_noinit(srcSize - oldSize);
1092 store_.shrink(oldSize - srcSize);
1093 assert(size() == srcSize);
1094 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1095 store_.writeTerminator();
1097 // need to reallocate, so we may as well create a brand new string
1098 basic_fbstring(lhs).swap(*this);
1104 basic_fbstring& operator=(basic_fbstring&& goner) {
1105 if (FBSTRING_UNLIKELY(&goner == this)) {
1106 // Compatibility with std::basic_string<>,
1107 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1110 // No need of this anymore
1111 this->~basic_fbstring();
1112 // Move the goner into this
1113 new(&store_) fbstring_core<E>(std::move(goner.store_));
1117 #ifndef _LIBSTDCXX_FBSTRING
1118 // Compatibility with std::string
1119 basic_fbstring & operator=(const std::string & rhs) {
1120 return assign(rhs.data(), rhs.size());
1123 // Compatibility with std::string
1124 std::string toStdString() const {
1125 return std::string(data(), size());
1128 // A lot of code in fbcode still uses this method, so keep it here for now.
1129 const basic_fbstring& toStdString() const {
1134 basic_fbstring& operator=(const value_type* s) {
1138 basic_fbstring& operator=(value_type c) {
1140 store_.expand_noinit(1);
1141 } else if (store_.isShared()) {
1142 basic_fbstring(1, c).swap(*this);
1145 store_.shrink(size() - 1);
1147 *store_.mutable_data() = c;
1148 store_.writeTerminator();
1152 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1153 return assign(il.begin(), il.end());
1156 // C++11 21.4.3 iterators:
1157 iterator begin() { return store_.mutable_data(); }
1159 const_iterator begin() const { return store_.data(); }
1161 const_iterator cbegin() const { return begin(); }
1164 return store_.mutable_data() + store_.size();
1167 const_iterator end() const {
1168 return store_.data() + store_.size();
1171 const_iterator cend() const { return end(); }
1173 reverse_iterator rbegin() {
1174 return reverse_iterator(end());
1177 const_reverse_iterator rbegin() const {
1178 return const_reverse_iterator(end());
1181 const_reverse_iterator crbegin() const { return rbegin(); }
1183 reverse_iterator rend() {
1184 return reverse_iterator(begin());
1187 const_reverse_iterator rend() const {
1188 return const_reverse_iterator(begin());
1191 const_reverse_iterator crend() const { return rend(); }
1194 // C++11 21.4.5, element access:
1195 const value_type& front() const { return *begin(); }
1196 const value_type& back() const {
1198 // Should be begin()[size() - 1], but that branches twice
1199 return *(end() - 1);
1201 value_type& front() { return *begin(); }
1202 value_type& back() {
1204 // Should be begin()[size() - 1], but that branches twice
1205 return *(end() - 1);
1212 // C++11 21.4.4 capacity:
1213 size_type size() const { return store_.size(); }
1215 size_type length() const { return size(); }
1217 size_type max_size() const {
1218 return std::numeric_limits<size_type>::max();
1221 void resize(const size_type n, const value_type c = value_type()) {
1222 auto size = this->size();
1224 store_.shrink(size - n);
1226 // Do this in two steps to minimize slack memory copied (see
1228 auto const capacity = this->capacity();
1229 assert(capacity >= size);
1230 if (size < capacity) {
1231 auto delta = std::min(n, capacity) - size;
1232 store_.expand_noinit(delta);
1233 fbstring_detail::pod_fill(begin() + size, end(), c);
1236 store_.writeTerminator();
1241 auto const delta = n - size;
1242 store_.expand_noinit(delta);
1243 fbstring_detail::pod_fill(end() - delta, end(), c);
1244 store_.writeTerminator();
1246 assert(this->size() == n);
1249 size_type capacity() const { return store_.capacity(); }
1251 void reserve(size_type res_arg = 0) {
1252 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1253 store_.reserve(res_arg);
1256 void shrink_to_fit() {
1257 // Shrink only if slack memory is sufficiently large
1258 if (capacity() < size() * 3 / 2) {
1261 basic_fbstring(cbegin(), cend()).swap(*this);
1264 void clear() { resize(0); }
1266 bool empty() const { return size() == 0; }
1268 // C++11 21.4.5 element access:
1269 const_reference operator[](size_type pos) const {
1270 return *(c_str() + pos);
1273 reference operator[](size_type pos) {
1274 if (pos == size()) {
1275 // Just call c_str() to make sure '\0' is present
1278 return *(begin() + pos);
1281 const_reference at(size_type n) const {
1282 enforce(n <= size(), std::__throw_out_of_range, "");
1286 reference at(size_type n) {
1287 enforce(n < size(), std::__throw_out_of_range, "");
1291 // C++11 21.4.6 modifiers:
1292 basic_fbstring& operator+=(const basic_fbstring& str) {
1296 basic_fbstring& operator+=(const value_type* s) {
1300 basic_fbstring& operator+=(const value_type c) {
1305 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1310 basic_fbstring& append(const basic_fbstring& str) {
1312 auto desiredSize = size() + str.size();
1314 append(str.data(), str.size());
1315 assert(size() == desiredSize);
1319 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1321 const size_type sz = str.size();
1322 enforce(pos <= sz, std::__throw_out_of_range, "");
1323 procrustes(n, sz - pos);
1324 return append(str.data() + pos, n);
1327 basic_fbstring& append(const value_type* s, size_type n) {
1329 Invariant checker(*this);
1332 if (FBSTRING_UNLIKELY(!n)) {
1333 // Unlikely but must be done
1336 auto const oldSize = size();
1337 auto const oldData = data();
1338 // Check for aliasing (rare). We could use "<=" here but in theory
1339 // those do not work for pointers unless the pointers point to
1340 // elements in the same array. For that reason we use
1341 // std::less_equal, which is guaranteed to offer a total order
1342 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1344 std::less_equal<const value_type*> le;
1345 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1346 assert(le(s + n, oldData + oldSize));
1347 const size_type offset = s - oldData;
1348 store_.reserve(oldSize + n);
1349 // Restore the source
1350 s = data() + offset;
1352 // Warning! Repeated appends with short strings may actually incur
1353 // practically quadratic performance. Avoid that by pushing back
1354 // the first character (which ensures exponential growth) and then
1355 // appending the rest normally. Worst case the append may incur a
1356 // second allocation but that will be rare.
1359 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1360 assert(size() == oldSize + n + 1);
1364 basic_fbstring& append(const value_type* s) {
1365 return append(s, traits_type::length(s));
1368 basic_fbstring& append(size_type n, value_type c) {
1369 resize(size() + n, c);
1373 template<class InputIterator>
1374 basic_fbstring& append(InputIterator first, InputIterator last) {
1375 insert(end(), first, last);
1379 basic_fbstring& append(std::initializer_list<value_type> il) {
1380 return append(il.begin(), il.end());
1383 void push_back(const value_type c) { // primitive
1384 store_.push_back(c);
1387 basic_fbstring& assign(const basic_fbstring& str) {
1388 if (&str == this) return *this;
1389 return assign(str.data(), str.size());
1392 basic_fbstring& assign(basic_fbstring&& str) {
1393 return *this = std::move(str);
1396 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1398 const size_type sz = str.size();
1399 enforce(pos <= sz, std::__throw_out_of_range, "");
1400 procrustes(n, sz - pos);
1401 return assign(str.data() + pos, n);
1404 basic_fbstring& assign(const value_type* s, const size_type n) {
1405 Invariant checker(*this);
1408 std::copy(s, s + n, begin());
1410 assert(size() == n);
1412 const value_type *const s2 = s + size();
1413 std::copy(s, s2, begin());
1414 append(s2, n - size());
1415 assert(size() == n);
1417 store_.writeTerminator();
1418 assert(size() == n);
1422 basic_fbstring& assign(const value_type* s) {
1423 return assign(s, traits_type::length(s));
1426 basic_fbstring& assign(std::initializer_list<value_type> il) {
1427 return assign(il.begin(), il.end());
1430 template <class ItOrLength, class ItOrChar>
1431 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1432 return replace(begin(), end(), first_or_n, last_or_c);
1435 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1436 return insert(pos1, str.data(), str.size());
1439 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1440 size_type pos2, size_type n) {
1441 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1442 procrustes(n, str.length() - pos2);
1443 return insert(pos1, str.data() + pos2, n);
1446 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1447 enforce(pos <= length(), std::__throw_out_of_range, "");
1448 insert(begin() + pos, s, s + n);
1452 basic_fbstring& insert(size_type pos, const value_type* s) {
1453 return insert(pos, s, traits_type::length(s));
1456 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1457 enforce(pos <= length(), std::__throw_out_of_range, "");
1458 insert(begin() + pos, n, c);
1462 iterator insert(const_iterator p, const value_type c) {
1463 const size_type pos = p - begin();
1465 return begin() + pos;
1469 template <int i> class Selector {};
1471 iterator insertImplDiscr(const_iterator p,
1472 size_type n, value_type c, Selector<1>) {
1473 Invariant checker(*this);
1475 auto const pos = p - begin();
1476 assert(p >= begin() && p <= end());
1477 if (capacity() - size() < n) {
1478 const size_type sz = p - begin();
1479 reserve(size() + n);
1482 const iterator oldEnd = end();
1483 if (n < size_type(oldEnd - p)) {
1484 append(oldEnd - n, oldEnd);
1486 // reverse_iterator(oldEnd - n),
1487 // reverse_iterator(p),
1488 // reverse_iterator(oldEnd));
1489 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1491 std::fill(begin() + pos, begin() + pos + n, c);
1493 append(n - (end() - p), c);
1494 append(iterator(p), oldEnd);
1495 std::fill(iterator(p), oldEnd, c);
1497 store_.writeTerminator();
1498 return begin() + pos;
1501 template<class InputIter>
1502 iterator insertImplDiscr(const_iterator i,
1503 InputIter b, InputIter e, Selector<0>) {
1504 return insertImpl(i, b, e,
1505 typename std::iterator_traits<InputIter>::iterator_category());
1508 template <class FwdIterator>
1509 iterator insertImpl(const_iterator i,
1510 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1511 Invariant checker(*this);
1513 const size_type pos = i - begin();
1514 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1515 std::distance(s1, s2);
1517 using namespace fbstring_detail;
1518 assert(pos <= size());
1520 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1521 capacity() - size();
1523 // realloc the string
1524 reserve(size() + n2);
1527 if (pos + n2 <= size()) {
1528 const iterator tailBegin = end() - n2;
1529 store_.expand_noinit(n2);
1530 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1531 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1532 reverse_iterator(tailBegin + n2));
1533 std::copy(s1, s2, begin() + pos);
1536 const size_type old_size = size();
1537 std::advance(t, old_size - pos);
1538 const size_t newElems = std::distance(t, s2);
1539 store_.expand_noinit(n2);
1540 std::copy(t, s2, begin() + old_size);
1541 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1542 begin() + old_size + newElems);
1543 std::copy(s1, t, begin() + pos);
1545 store_.writeTerminator();
1546 return begin() + pos;
1549 template <class InputIterator>
1550 iterator insertImpl(const_iterator i,
1551 InputIterator b, InputIterator e,
1552 std::input_iterator_tag) {
1553 const auto pos = i - begin();
1554 basic_fbstring temp(begin(), i);
1555 for (; b != e; ++b) {
1558 temp.append(i, cend());
1560 return begin() + pos;
1564 template <class ItOrLength, class ItOrChar>
1565 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1566 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1567 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1570 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1571 return insert(p, il.begin(), il.end());
1574 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1575 Invariant checker(*this);
1577 enforce(pos <= length(), std::__throw_out_of_range, "");
1578 procrustes(n, length() - pos);
1579 std::copy(begin() + pos + n, end(), begin() + pos);
1580 resize(length() - n);
1584 iterator erase(iterator position) {
1585 const size_type pos(position - begin());
1586 enforce(pos <= size(), std::__throw_out_of_range, "");
1588 return begin() + pos;
1591 iterator erase(iterator first, iterator last) {
1592 const size_type pos(first - begin());
1593 erase(pos, last - first);
1594 return begin() + pos;
1597 // Replaces at most n1 chars of *this, starting with pos1 with the
1599 basic_fbstring& replace(size_type pos1, size_type n1,
1600 const basic_fbstring& str) {
1601 return replace(pos1, n1, str.data(), str.size());
1604 // Replaces at most n1 chars of *this, starting with pos1,
1605 // with at most n2 chars of str starting with pos2
1606 basic_fbstring& replace(size_type pos1, size_type n1,
1607 const basic_fbstring& str,
1608 size_type pos2, size_type n2) {
1609 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1610 return replace(pos1, n1, str.data() + pos2,
1611 std::min(n2, str.size() - pos2));
1614 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1615 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1616 return replace(pos, n1, s, traits_type::length(s));
1619 // Replaces at most n1 chars of *this, starting with pos, with n2
1622 // consolidated with
1624 // Replaces at most n1 chars of *this, starting with pos, with at
1625 // most n2 chars of str. str must have at least n2 chars.
1626 template <class StrOrLength, class NumOrChar>
1627 basic_fbstring& replace(size_type pos, size_type n1,
1628 StrOrLength s_or_n2, NumOrChar n_or_c) {
1629 Invariant checker(*this);
1631 enforce(pos <= size(), std::__throw_out_of_range, "");
1632 procrustes(n1, length() - pos);
1633 const iterator b = begin() + pos;
1634 return replace(b, b + n1, s_or_n2, n_or_c);
1637 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1638 return replace(i1, i2, str.data(), str.length());
1641 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1642 return replace(i1, i2, s, traits_type::length(s));
1646 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1647 const value_type* s, size_type n,
1650 assert(begin() <= i1 && i1 <= end());
1651 assert(begin() <= i2 && i2 <= end());
1652 return replace(i1, i2, s, s + n);
1655 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1656 size_type n2, value_type c, Selector<1>) {
1657 const size_type n1 = i2 - i1;
1659 std::fill(i1, i1 + n2, c);
1662 std::fill(i1, i2, c);
1663 insert(i2, n2 - n1, c);
1669 template <class InputIter>
1670 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1671 InputIter b, InputIter e,
1673 replaceImpl(i1, i2, b, e,
1674 typename std::iterator_traits<InputIter>::iterator_category());
1679 template <class FwdIterator, class P>
1680 bool replaceAliased(iterator i1, iterator i2,
1681 FwdIterator s1, FwdIterator s2, P*) {
1685 template <class FwdIterator>
1686 bool replaceAliased(iterator i1, iterator i2,
1687 FwdIterator s1, FwdIterator s2, value_type*) {
1688 static const std::less_equal<const value_type*> le =
1689 std::less_equal<const value_type*>();
1690 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1694 // Aliased replace, copy to new string
1695 basic_fbstring temp;
1696 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1697 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1703 template <class FwdIterator>
1704 void replaceImpl(iterator i1, iterator i2,
1705 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1706 Invariant checker(*this);
1709 // Handle aliased replace
1710 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1714 auto const n1 = i2 - i1;
1716 auto const n2 = std::distance(s1, s2);
1721 std::copy(s1, s2, i1);
1725 fbstring_detail::copy_n(s1, n1, i1);
1726 std::advance(s1, n1);
1732 template <class InputIterator>
1733 void replaceImpl(iterator i1, iterator i2,
1734 InputIterator b, InputIterator e, std::input_iterator_tag) {
1735 basic_fbstring temp(begin(), i1);
1736 temp.append(b, e).append(i2, end());
1741 template <class T1, class T2>
1742 basic_fbstring& replace(iterator i1, iterator i2,
1743 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1745 num1 = std::numeric_limits<T1>::is_specialized,
1746 num2 = std::numeric_limits<T2>::is_specialized;
1747 return replaceImplDiscr(
1748 i1, i2, first_or_n_or_s, last_or_c_or_n,
1749 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1752 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1753 enforce(pos <= size(), std::__throw_out_of_range, "");
1754 procrustes(n, size() - pos);
1756 fbstring_detail::pod_copy(
1763 void swap(basic_fbstring& rhs) {
1764 store_.swap(rhs.store_);
1767 const value_type* c_str() const {
1768 return store_.c_str();
1771 const value_type* data() const { return c_str(); }
1773 allocator_type get_allocator() const {
1774 return allocator_type();
1777 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1778 return find(str.data(), pos, str.length());
1781 size_type find(const value_type* needle, const size_type pos,
1782 const size_type nsize) const {
1783 if (!nsize) return pos;
1784 auto const size = this->size();
1785 if (nsize + pos > size) return npos;
1786 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1787 // the last characters first
1788 auto const haystack = data();
1789 auto const nsize_1 = nsize - 1;
1790 auto const lastNeedle = needle[nsize_1];
1792 // Boyer-Moore skip value for the last char in the needle. Zero is
1793 // not a valid value; skip will be computed the first time it's
1797 const E * i = haystack + pos;
1798 auto iEnd = haystack + size - nsize_1;
1801 // Boyer-Moore: match the last element in the needle
1802 while (i[nsize_1] != lastNeedle) {
1808 // Here we know that the last char matches
1809 // Continue in pedestrian mode
1810 for (size_t j = 0; ; ) {
1812 if (i[j] != needle[j]) {
1813 // Not found, we can skip
1814 // Compute the skip value lazily
1817 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1824 // Check if done searching
1827 return i - haystack;
1834 size_type find(const value_type* s, size_type pos = 0) const {
1835 return find(s, pos, traits_type::length(s));
1838 size_type find (value_type c, size_type pos = 0) const {
1839 return find(&c, pos, 1);
1842 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1843 return rfind(str.data(), pos, str.length());
1846 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1847 if (n > length()) return npos;
1848 pos = std::min(pos, length() - n);
1849 if (n == 0) return pos;
1851 const_iterator i(begin() + pos);
1853 if (traits_type::eq(*i, *s)
1854 && traits_type::compare(&*i, s, n) == 0) {
1857 if (i == begin()) break;
1862 size_type rfind(const value_type* s, size_type pos = npos) const {
1863 return rfind(s, pos, traits_type::length(s));
1866 size_type rfind(value_type c, size_type pos = npos) const {
1867 return rfind(&c, pos, 1);
1870 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1871 return find_first_of(str.data(), pos, str.length());
1874 size_type find_first_of(const value_type* s,
1875 size_type pos, size_type n) const {
1876 if (pos > length() || n == 0) return npos;
1877 const_iterator i(begin() + pos),
1879 for (; i != finish; ++i) {
1880 if (traits_type::find(s, n, *i) != 0) {
1887 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1888 return find_first_of(s, pos, traits_type::length(s));
1891 size_type find_first_of(value_type c, size_type pos = 0) const {
1892 return find_first_of(&c, pos, 1);
1895 size_type find_last_of (const basic_fbstring& str,
1896 size_type pos = npos) const {
1897 return find_last_of(str.data(), pos, str.length());
1900 size_type find_last_of (const value_type* s, size_type pos,
1901 size_type n) const {
1902 if (!empty() && n > 0) {
1903 pos = std::min(pos, length() - 1);
1904 const_iterator i(begin() + pos);
1906 if (traits_type::find(s, n, *i) != 0) {
1909 if (i == begin()) break;
1915 size_type find_last_of (const value_type* s,
1916 size_type pos = npos) const {
1917 return find_last_of(s, pos, traits_type::length(s));
1920 size_type find_last_of (value_type c, size_type pos = npos) const {
1921 return find_last_of(&c, pos, 1);
1924 size_type find_first_not_of(const basic_fbstring& str,
1925 size_type pos = 0) const {
1926 return find_first_not_of(str.data(), pos, str.size());
1929 size_type find_first_not_of(const value_type* s, size_type pos,
1930 size_type n) const {
1931 if (pos < length()) {
1935 for (; i != finish; ++i) {
1936 if (traits_type::find(s, n, *i) == 0) {
1944 size_type find_first_not_of(const value_type* s,
1945 size_type pos = 0) const {
1946 return find_first_not_of(s, pos, traits_type::length(s));
1949 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1950 return find_first_not_of(&c, pos, 1);
1953 size_type find_last_not_of(const basic_fbstring& str,
1954 size_type pos = npos) const {
1955 return find_last_not_of(str.data(), pos, str.length());
1958 size_type find_last_not_of(const value_type* s, size_type pos,
1959 size_type n) const {
1960 if (!this->empty()) {
1961 pos = std::min(pos, size() - 1);
1962 const_iterator i(begin() + pos);
1964 if (traits_type::find(s, n, *i) == 0) {
1967 if (i == begin()) break;
1973 size_type find_last_not_of(const value_type* s,
1974 size_type pos = npos) const {
1975 return find_last_not_of(s, pos, traits_type::length(s));
1978 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1979 return find_last_not_of(&c, pos, 1);
1982 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1983 enforce(pos <= size(), std::__throw_out_of_range, "");
1984 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1987 int compare(const basic_fbstring& str) const {
1988 // FIX due to Goncalo N M de Carvalho July 18, 2005
1989 return compare(0, size(), str);
1992 int compare(size_type pos1, size_type n1,
1993 const basic_fbstring& str) const {
1994 return compare(pos1, n1, str.data(), str.size());
1997 int compare(size_type pos1, size_type n1,
1998 const value_type* s) const {
1999 return compare(pos1, n1, s, traits_type::length(s));
2002 int compare(size_type pos1, size_type n1,
2003 const value_type* s, size_type n2) const {
2004 enforce(pos1 <= size(), std::__throw_out_of_range, "");
2005 procrustes(n1, size() - pos1);
2006 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
2007 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
2008 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2011 int compare(size_type pos1, size_type n1,
2012 const basic_fbstring& str,
2013 size_type pos2, size_type n2) const {
2014 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
2015 return compare(pos1, n1, str.data() + pos2,
2016 std::min(n2, str.size() - pos2));
2019 // Code from Jean-Francois Bastien (03/26/2007)
2020 int compare(const value_type* s) const {
2021 // Could forward to compare(0, size(), s, traits_type::length(s))
2022 // but that does two extra checks
2023 const size_type n1(size()), n2(traits_type::length(s));
2024 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2025 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2033 // non-member functions
2035 template <typename E, class T, class A, class S>
2037 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2038 const basic_fbstring<E, T, A, S>& rhs) {
2040 basic_fbstring<E, T, A, S> result;
2041 result.reserve(lhs.size() + rhs.size());
2042 result.append(lhs).append(rhs);
2043 return std::move(result);
2047 template <typename E, class T, class A, class S>
2049 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2050 const basic_fbstring<E, T, A, S>& rhs) {
2051 return std::move(lhs.append(rhs));
2055 template <typename E, class T, class A, class S>
2057 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2058 basic_fbstring<E, T, A, S>&& rhs) {
2059 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2060 // Good, at least we don't need to reallocate
2061 return std::move(rhs.insert(0, lhs));
2063 // Meh, no go. Forward to operator+(const&, const&).
2064 auto const& rhsC = rhs;
2069 template <typename E, class T, class A, class S>
2071 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2072 basic_fbstring<E, T, A, S>&& rhs) {
2073 return std::move(lhs.append(rhs));
2076 template <typename E, class T, class A, class S>
2078 basic_fbstring<E, T, A, S> operator+(
2079 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2080 const basic_fbstring<E, T, A, S>& rhs) {
2082 basic_fbstring<E, T, A, S> result;
2083 const typename basic_fbstring<E, T, A, S>::size_type len =
2084 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2085 result.reserve(len + rhs.size());
2086 result.append(lhs, len).append(rhs);
2090 template <typename E, class T, class A, class S>
2092 basic_fbstring<E, T, A, S> operator+(
2093 typename basic_fbstring<E, T, A, S>::value_type lhs,
2094 const basic_fbstring<E, T, A, S>& rhs) {
2096 basic_fbstring<E, T, A, S> result;
2097 result.reserve(1 + rhs.size());
2098 result.push_back(lhs);
2103 template <typename E, class T, class A, class S>
2105 basic_fbstring<E, T, A, S> operator+(
2106 const basic_fbstring<E, T, A, S>& lhs,
2107 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2109 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2110 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2112 basic_fbstring<E, T, A, S> result;
2113 const size_type len = traits_type::length(rhs);
2114 result.reserve(lhs.size() + len);
2115 result.append(lhs).append(rhs, len);
2119 template <typename E, class T, class A, class S>
2121 basic_fbstring<E, T, A, S> operator+(
2122 const basic_fbstring<E, T, A, S>& lhs,
2123 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2125 basic_fbstring<E, T, A, S> result;
2126 result.reserve(lhs.size() + 1);
2128 result.push_back(rhs);
2132 template <typename E, class T, class A, class S>
2134 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2135 const basic_fbstring<E, T, A, S>& rhs) {
2136 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2138 template <typename E, class T, class A, class S>
2140 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2141 const basic_fbstring<E, T, A, S>& rhs) {
2142 return rhs == lhs; }
2144 template <typename E, class T, class A, class S>
2146 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2147 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2148 return lhs.compare(rhs) == 0; }
2150 template <typename E, class T, class A, class S>
2152 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2153 const basic_fbstring<E, T, A, S>& rhs) {
2154 return !(lhs == rhs); }
2156 template <typename E, class T, class A, class S>
2158 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* 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 basic_fbstring<E, T, A, S>& lhs,
2165 const typename basic_fbstring<E, T, A, S>::value_type* 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 basic_fbstring<E, T, A, S>& rhs) {
2172 return lhs.compare(rhs) < 0; }
2174 template <typename E, class T, class A, class S>
2176 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2177 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2178 return lhs.compare(rhs) < 0; }
2180 template <typename E, class T, class A, class S>
2182 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2183 const basic_fbstring<E, T, A, S>& rhs) {
2184 return rhs.compare(lhs) > 0; }
2186 template <typename E, class T, class A, class S>
2188 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2189 const basic_fbstring<E, T, A, S>& rhs) {
2192 template <typename E, class T, class A, class S>
2194 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2195 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2198 template <typename E, class T, class A, class S>
2200 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2201 const basic_fbstring<E, T, A, S>& rhs) {
2204 template <typename E, class T, class A, class S>
2206 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2207 const basic_fbstring<E, T, A, S>& rhs) {
2208 return !(rhs < lhs); }
2210 template <typename E, class T, class A, class S>
2212 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2213 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2214 return !(rhs < lhs); }
2216 template <typename E, class T, class A, class S>
2218 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2219 const basic_fbstring<E, T, A, S>& rhs) {
2220 return !(rhs < lhs); }
2222 template <typename E, class T, class A, class S>
2224 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2225 const basic_fbstring<E, T, A, S>& rhs) {
2226 return !(lhs < rhs); }
2228 template <typename E, class T, class A, class S>
2230 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2231 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2232 return !(lhs < rhs); }
2234 template <typename E, class T, class A, class S>
2236 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2237 const basic_fbstring<E, T, A, S>& rhs) {
2238 return !(lhs < rhs);
2242 template <typename E, class T, class A, class S>
2243 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2247 // TODO: make this faster.
2248 template <typename E, class T, class A, class S>
2251 typename basic_fbstring<E, T, A, S>::value_type,
2252 typename basic_fbstring<E, T, A, S>::traits_type>&
2254 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2255 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2256 basic_fbstring<E, T, A, S>& str) {
2257 typename std::basic_istream<E, T>::sentry sentry(is);
2258 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2259 typename basic_fbstring<E, T, A, S>::traits_type>
2261 typedef typename __istream_type::ios_base __ios_base;
2262 size_t extracted = 0;
2263 auto err = __ios_base::goodbit;
2265 auto n = is.width();
2270 auto got = is.rdbuf()->sgetc();
2271 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2272 // Whew. We get to store this guy
2274 got = is.rdbuf()->snextc();
2276 if (got == T::eof()) {
2277 err |= __ios_base::eofbit;
2282 err |= __ios_base::failbit;
2290 template <typename E, class T, class A, class S>
2292 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2293 typename basic_fbstring<E, T, A, S>::traits_type>&
2295 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2296 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2297 const basic_fbstring<E, T, A, S>& str) {
2298 os.write(str.data(), str.size());
2302 #ifndef _LIBSTDCXX_FBSTRING
2304 template <typename E, class T, class A, class S>
2306 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2307 typename basic_fbstring<E, T, A, S>::traits_type>&
2309 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2310 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2311 basic_fbstring<E, T, A, S>& str,
2312 typename basic_fbstring<E, T, A, S>::value_type delim) {
2313 // Use the nonstandard getdelim()
2317 // This looks quadratic but it really depends on realloc
2318 auto const newSize = size + 128;
2319 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2320 is.getline(buf + size, newSize - size, delim);
2321 if (is.bad() || is.eof() || !is.fail()) {
2322 // done by either failure, end of file, or normal read
2323 size += std::strlen(buf + size);
2326 // Here we have failed due to too short a buffer
2327 // Minus one to discount the terminating '\0'
2329 assert(buf[size] == 0);
2330 // Clear the error so we can continue reading
2333 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2334 AcquireMallocatedString());
2339 template <typename E, class T, class A, class S>
2341 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2342 typename basic_fbstring<E, T, A, S>::traits_type>&
2344 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2345 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2346 basic_fbstring<E, T, A, S>& str) {
2347 // Just forward to the version with a delimiter
2348 return getline(is, str, '\n');
2353 template <typename E1, class T, class A, class S>
2354 const typename basic_fbstring<E1, T, A, S>::size_type
2355 basic_fbstring<E1, T, A, S>::npos =
2356 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2358 #ifndef _LIBSTDCXX_FBSTRING
2359 // basic_string compatibility routines
2361 template <typename E, class T, class A, class S>
2363 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2364 const std::string& rhs) {
2365 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2368 template <typename E, class T, class A, class S>
2370 bool operator==(const std::string& lhs,
2371 const basic_fbstring<E, T, A, S>& rhs) {
2375 template <typename E, class T, class A, class S>
2377 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2378 const std::string& rhs) {
2379 return !(lhs == rhs);
2382 template <typename E, class T, class A, class S>
2384 bool operator!=(const std::string& lhs,
2385 const basic_fbstring<E, T, A, S>& rhs) {
2386 return !(lhs == rhs);
2389 #if !defined(_LIBSTDCXX_FBSTRING)
2390 typedef basic_fbstring<char> fbstring;
2393 // fbstring is relocatable
2394 template <class T, class R, class A, class S>
2395 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2398 _GLIBCXX_END_NAMESPACE_VERSION
2401 } // namespace folly
2403 #pragma GCC diagnostic pop
2405 #ifndef _LIBSTDCXX_FBSTRING
2409 struct hash< ::folly::fbstring> {
2410 size_t operator()(const ::folly::fbstring& s) const {
2411 return ::folly::hash::fnv32_buf(s.data(), s.size());
2416 #endif // _LIBSTDCXX_FBSTRING
2418 #undef FBSTRING_DISABLE_ADDRESS_SANITIZER
2419 #undef FBSTRING_LIKELY
2420 #undef FBSTRING_UNLIKELY
2422 #endif // FOLLY_BASE_FBSTRING_H_