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 namespace fbstring_detail {
117 template <class InIt, class OutIt>
120 typename std::iterator_traits<InIt>::difference_type n,
122 for (; n != 0; --n, ++b, ++d) {
123 assert((const void*)&*d != &*b);
129 template <class Pod, class T>
130 inline void pod_fill(Pod* b, Pod* e, T c) {
131 assert(b && e && b <= e);
132 /*static*/ if (sizeof(T) == 1) {
135 auto const ee = b + ((e - b) & ~7u);
136 for (; b != ee; b += 8) {
147 for (; b != e; ++b) {
154 * Lightly structured memcpy, simplifies copying PODs and introduces
155 * some asserts. Unfortunately using this function may cause
156 * measurable overhead (presumably because it adjusts from a begin/end
157 * convention to a pointer/size convention, so it does some extra
158 * arithmetic even though the caller might have done the inverse
159 * adaptation outside).
162 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
164 assert(d >= e || d + (e - b) <= b);
165 memcpy(d, b, (e - b) * sizeof(Pod));
169 * Lightly structured memmove, simplifies copying PODs and introduces
173 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
175 memmove(d, b, (e - b) * sizeof(*b));
178 } // namespace fbstring_detail
181 * Defines a special acquisition method for constructing fbstring
182 * objects. AcquireMallocatedString means that the user passes a
183 * pointer to a malloc-allocated string that the fbstring object will
186 enum class AcquireMallocatedString {};
189 * fbstring_core_model is a mock-up type that defines all required
190 * signatures of a fbstring core. The fbstring class itself uses such
191 * a core object to implement all of the numerous member functions
192 * required by the standard.
194 * If you want to define a new core, copy the definition below and
195 * implement the primitives. Then plug the core into basic_fbstring as
196 * a template argument.
198 template <class Char>
199 class fbstring_core_model {
201 fbstring_core_model();
202 fbstring_core_model(const fbstring_core_model &);
203 ~fbstring_core_model();
204 // Returns a pointer to string's buffer (currently only contiguous
205 // strings are supported). The pointer is guaranteed to be valid
206 // until the next call to a non-const member function.
207 const Char * data() const;
208 // Much like data(), except the string is prepared to support
209 // character-level changes. This call is a signal for
210 // e.g. reference-counted implementation to fork the data. The
211 // pointer is guaranteed to be valid until the next call to a
212 // non-const member function.
213 Char * mutable_data();
214 // Returns a pointer to string's buffer and guarantees that a
215 // readable '\0' lies right after the buffer. The pointer is
216 // guaranteed to be valid until the next call to a non-const member
218 const Char * c_str() const;
219 // Shrinks the string by delta characters. Asserts that delta <=
221 void shrink(size_t delta);
222 // Expands the string by delta characters (i.e. after this call
223 // size() will report the old size() plus delta) but without
224 // initializing the expanded region. Returns a pointer to the memory
225 // to be initialized (the beginning of the expanded portion). The
226 // caller is expected to fill the expanded area appropriately.
227 Char* expand_noinit(size_t delta);
228 // Expands the string by one character and sets the last character
230 void push_back(Char c);
231 // Returns the string's size.
233 // Returns the string's capacity, i.e. maximum size that the string
234 // can grow to without reallocation. Note that for reference counted
235 // strings that's technically a lie - even assigning characters
236 // within the existing size would cause a reallocation.
237 size_t capacity() const;
238 // Returns true if the data underlying the string is actually shared
239 // across multiple strings (in a refcounted fashion).
240 bool isShared() const;
241 // Makes sure that at least minCapacity characters are available for
242 // the string without reallocation. For reference-counted strings,
243 // it should fork the data even if minCapacity < size().
244 void reserve(size_t minCapacity);
247 fbstring_core_model& operator=(const fbstring_core_model &);
252 * gcc-4.7 throws what appears to be some false positive uninitialized
253 * warnings for the members of the MediumLarge struct. So, mute them here.
255 #if defined(__GNUC__) && !defined(__clang__)
256 # pragma GCC diagnostic push
257 # pragma GCC diagnostic ignored "-Wuninitialized"
261 * This is the core of the string. The code should work on 32- and
262 * 64-bit architectures and with any Char size. Porting to big endian
263 * architectures would require some changes.
265 * The storage is selected as follows (assuming we store one-byte
266 * characters on a 64-bit machine): (a) "small" strings between 0 and
267 * 23 chars are stored in-situ without allocation (the rightmost byte
268 * stores the size); (b) "medium" strings from 24 through 254 chars
269 * are stored in malloc-allocated memory that is copied eagerly; (c)
270 * "large" strings of 255 chars and above are stored in a similar
271 * structure as medium arrays, except that the string is
272 * reference-counted and copied lazily. the reference count is
273 * allocated right before the character array.
275 * The discriminator between these three strategies sits in the two
276 * most significant bits of the rightmost char of the storage. If
277 * neither is set, then the string is small (and its length sits in
278 * the lower-order bits of that rightmost character). If the MSb is
279 * set, the string is medium width. If the second MSb is set, then the
282 template <class Char> class fbstring_core {
285 // Only initialize the tag, will set the MSBs (i.e. the small
286 // string size) to zero too
287 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
288 // or: setSmallSize(0);
290 assert(category() == isSmall && size() == 0);
293 fbstring_core(const fbstring_core & rhs) {
294 assert(&rhs != this);
295 // Simplest case first: small strings are bitblitted
296 if (rhs.category() == isSmall) {
297 assert(offsetof(MediumLarge, data_) == 0);
298 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
299 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
300 const size_t size = rhs.smallSize();
302 ml_.capacity_ = rhs.ml_.capacity_;
305 // Just write the whole thing, don't look at details. In
306 // particular we need to copy capacity anyway because we want
307 // to set the size (don't forget that the last character,
308 // which stores a short string's length, is shared with the
309 // ml_.capacity field).
312 assert(category() == isSmall && this->size() == rhs.size());
313 } else if (rhs.category() == isLarge) {
314 // Large strings are just refcounted
316 RefCounted::incrementRefs(ml_.data_);
317 assert(category() == isLarge && size() == rhs.size());
319 // Medium strings are copied eagerly. Don't forget to allocate
320 // one extra Char for the null terminator.
321 auto const allocSize =
322 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
323 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
324 fbstring_detail::pod_copy(rhs.ml_.data_,
326 rhs.ml_.data_ + rhs.ml_.size_ + 1,
328 // No need for writeTerminator() here, we copied one extra
329 // element just above.
330 ml_.size_ = rhs.ml_.size_;
331 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
332 assert(category() == isMedium);
334 assert(size() == rhs.size());
335 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
338 fbstring_core(fbstring_core&& goner) {
339 if (goner.category() == isSmall) {
340 // Just copy, leave the goner in peace
341 new(this) fbstring_core(goner.small_, goner.smallSize());
345 // Clean goner's carcass
346 goner.setSmallSize(0);
350 fbstring_core(const Char *const data, const size_t size) {
351 // Simplest case first: small strings are bitblitted
352 if (size <= maxSmallSize) {
353 // Layout is: Char* data_, size_t size_, size_t capacity_
354 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
355 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
356 // sizeof(size_t) must be a power of 2
357 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
359 // If data is aligned, use fast word-wise copying. Otherwise,
360 // use conservative memcpy.
361 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
362 fbstring_detail::pod_copy(data, data + size, small_);
364 // Copy one word (64 bits) at a time
365 const size_t byteSize = size * sizeof(Char);
366 if (byteSize > 2 * sizeof(size_t)) {
368 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
370 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
372 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
373 } else if (byteSize > sizeof(size_t)) {
376 } else if (size > 0) {
382 } else if (size <= maxMediumSize) {
383 // Medium strings are allocated normally. Don't forget to
384 // allocate one extra Char for the terminating null.
385 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
386 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
387 fbstring_detail::pod_copy(data, data + size, ml_.data_);
389 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
391 // Large strings are allocated differently
392 size_t effectiveCapacity = size;
393 auto const newRC = RefCounted::create(data, & effectiveCapacity);
394 ml_.data_ = newRC->data_;
396 ml_.capacity_ = effectiveCapacity | isLarge;
399 assert(this->size() == size);
400 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
404 auto const c = category();
412 RefCounted::decrementRefs(ml_.data_);
415 // Snatches a previously mallocated string. The parameter "size"
416 // is the size of the string, and the parameter "capacity" is the size
417 // of the mallocated block. The string must be \0-terminated, so
418 // data[size] == '\0' and capacity >= size + 1.
420 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
421 // "size", and pass 3 as "capacity".
422 fbstring_core(Char *const data, const size_t size,
423 const size_t capacity,
424 AcquireMallocatedString) {
426 assert(capacity > size);
427 assert(data[size] == '\0');
428 // Use the medium string storage
431 ml_.capacity_ = capacity | isMedium;
433 // No need for the memory
439 // swap below doesn't test whether &rhs == this (and instead
440 // potentially does extra work) on the premise that the rarity of
441 // that situation actually makes the check more expensive than is
443 void swap(fbstring_core & rhs) {
449 // In C++11 data() and c_str() are 100% equivalent.
450 const Char * data() const {
454 Char * mutable_data() {
455 auto const c = category();
459 assert(c == isMedium || c == isLarge);
460 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
462 size_t effectiveCapacity = ml_.capacity();
463 auto const newRC = RefCounted::create(& effectiveCapacity);
464 // If this fails, someone placed the wrong capacity in an
466 assert(effectiveCapacity >= ml_.capacity());
467 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
469 RefCounted::decrementRefs(ml_.data_);
470 ml_.data_ = newRC->data_;
471 // No need to call writeTerminator(), we have + 1 above.
476 const Char * c_str() const {
477 auto const c = category();
478 #ifdef FBSTRING_PERVERSE
480 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
481 || small_[smallSize()] == '\0');
482 small_[smallSize()] = '\0';
485 assert(c == isMedium || c == isLarge);
486 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
487 ml_.data_[ml_.size_] = '\0';
488 #elif defined(FBSTRING_CONSERVATIVE)
490 assert(small_[smallSize()] == '\0');
493 assert(c == isMedium || c == isLarge);
494 assert(ml_.data_[ml_.size_] == '\0');
497 small_[smallSize()] = '\0';
500 assert(c == isMedium || c == isLarge);
501 ml_.data_[ml_.size_] = '\0';
506 void shrink(const size_t delta) {
507 if (category() == isSmall) {
508 // Check for underflow
509 assert(delta <= smallSize());
510 setSmallSize(smallSize() - delta);
511 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
512 // Medium strings and unique large strings need no special
514 assert(ml_.size_ >= delta);
517 assert(ml_.size_ >= delta);
518 // Shared large string, must make unique. This is because of the
519 // durn terminator must be written, which may trample the shared
522 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
524 // No need to write the terminator.
530 void reserve(size_t minCapacity) {
531 if (category() == isLarge) {
533 if (RefCounted::refs(ml_.data_) > 1) {
534 // We must make it unique regardless; in-place reallocation is
535 // useless if the string is shared. In order to not surprise
536 // people, reserve the new block at current capacity or
537 // more. That way, a string's capacity never shrinks after a
539 minCapacity = std::max(minCapacity, ml_.capacity());
540 auto const newRC = RefCounted::create(& minCapacity);
541 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
543 // Done with the old data. No need to call writeTerminator(),
544 // we have + 1 above.
545 RefCounted::decrementRefs(ml_.data_);
546 ml_.data_ = newRC->data_;
547 ml_.capacity_ = minCapacity | isLarge;
548 // size remains unchanged
550 // String is not shared, so let's try to realloc (if needed)
551 if (minCapacity > ml_.capacity()) {
552 // Asking for more memory
554 RefCounted::reallocate(ml_.data_, ml_.size_,
555 ml_.capacity(), minCapacity);
556 ml_.data_ = newRC->data_;
557 ml_.capacity_ = minCapacity | isLarge;
560 assert(capacity() >= minCapacity);
562 } else if (category() == isMedium) {
563 // String is not shared
564 if (minCapacity <= ml_.capacity()) {
565 return; // nothing to do, there's enough room
567 if (minCapacity <= maxMediumSize) {
568 // Keep the string at medium size. Don't forget to allocate
569 // one extra Char for the terminating null.
570 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
571 ml_.data_ = static_cast<Char *>(
574 ml_.size_ * sizeof(Char),
575 ml_.capacity() * sizeof(Char),
578 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
580 // Conversion from medium to large string
581 fbstring_core nascent;
582 // Will recurse to another branch of this function
583 nascent.reserve(minCapacity);
584 nascent.ml_.size_ = ml_.size_;
585 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
589 assert(capacity() >= minCapacity);
592 assert(category() == isSmall);
593 if (minCapacity > maxMediumSize) {
595 auto const newRC = RefCounted::create(& minCapacity);
596 auto const size = smallSize();
597 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
598 // No need for writeTerminator(), we wrote it above with + 1.
599 ml_.data_ = newRC->data_;
601 ml_.capacity_ = minCapacity | isLarge;
602 assert(capacity() >= minCapacity);
603 } else if (minCapacity > maxSmallSize) {
605 // Don't forget to allocate one extra Char for the terminating null
606 auto const allocSizeBytes =
607 goodMallocSize((1 + minCapacity) * sizeof(Char));
608 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
609 auto const size = smallSize();
610 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
611 // No need for writeTerminator(), we wrote it above with + 1.
614 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
617 // Nothing to do, everything stays put
620 assert(capacity() >= minCapacity);
623 Char * expand_noinit(const size_t delta) {
624 // Strategy is simple: make room, then change size
625 assert(capacity() >= size());
627 if (category() == isSmall) {
630 if (newSz <= maxSmallSize) {
638 newSz = ml_.size_ + delta;
639 if (newSz > capacity()) {
643 assert(capacity() >= newSz);
644 // Category can't be small - we took care of that above
645 assert(category() == isMedium || category() == isLarge);
648 assert(size() == newSz);
649 return ml_.data_ + sz;
652 void push_back(Char c) {
653 assert(capacity() >= size());
655 if (category() == isSmall) {
657 if (sz < maxSmallSize) {
658 setSmallSize(sz + 1);
663 reserve(maxSmallSize * 2);
666 if (sz == capacity()) { // always true for isShared()
667 reserve(sz * 3 / 2); // ensures not shared
671 assert(capacity() >= sz + 1);
672 // Category can't be small - we took care of that above
673 assert(category() == isMedium || category() == isLarge);
679 size_t size() const {
680 return category() == isSmall ? smallSize() : ml_.size_;
683 size_t capacity() const {
684 switch (category()) {
688 // For large-sized strings, a multi-referenced chunk has no
689 // available capacity. This is because any attempt to append
690 // data would trigger a new allocation.
691 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
694 return ml_.capacity();
697 bool isShared() const {
698 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
701 #ifdef FBSTRING_PERVERSE
702 enum { TERMINATOR = '^' };
704 enum { TERMINATOR = '\0' };
707 void writeTerminator() {
708 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
709 if (category() == isSmall) {
710 const auto s = smallSize();
711 if (s != maxSmallSize) {
712 small_[s] = TERMINATOR;
715 ml_.data_[ml_.size_] = TERMINATOR;
722 fbstring_core & operator=(const fbstring_core & rhs);
729 size_t capacity() const {
730 return capacity_ & capacityExtractMask;
735 std::atomic<size_t> refCount_;
738 static RefCounted * fromData(Char * p) {
739 return static_cast<RefCounted*>(
741 static_cast<unsigned char*>(static_cast<void*>(p))
742 - sizeof(refCount_)));
745 static size_t refs(Char * p) {
746 return fromData(p)->refCount_.load(std::memory_order_acquire);
749 static void incrementRefs(Char * p) {
750 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
753 static void decrementRefs(Char * p) {
754 auto const dis = fromData(p);
755 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
762 static RefCounted * create(size_t * size) {
763 // Don't forget to allocate one extra Char for the terminating
764 // null. In this case, however, one Char is already part of the
766 const size_t allocSize = goodMallocSize(
767 sizeof(RefCounted) + *size * sizeof(Char));
768 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
769 result->refCount_.store(1, std::memory_order_release);
770 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
774 static RefCounted * create(const Char * data, size_t * size) {
775 const size_t effectiveSize = *size;
776 auto result = create(size);
777 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
781 static RefCounted * reallocate(Char *const data,
782 const size_t currentSize,
783 const size_t currentCapacity,
784 const size_t newCapacity) {
785 assert(newCapacity > 0 && newCapacity > currentSize);
786 auto const dis = fromData(data);
787 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
788 // Don't forget to allocate one extra Char for the terminating
789 // null. In this case, however, one Char is already part of the
791 auto result = static_cast<RefCounted*>(
793 sizeof(RefCounted) + currentSize * sizeof(Char),
794 sizeof(RefCounted) + currentCapacity * sizeof(Char),
795 sizeof(RefCounted) + newCapacity * sizeof(Char)));
796 assert(result->refCount_.load(std::memory_order_acquire) == 1);
802 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
803 mutable MediumLarge ml_;
807 lastChar = sizeof(MediumLarge) - 1,
808 maxSmallSize = lastChar / sizeof(Char),
809 maxMediumSize = 254 / sizeof(Char), // coincides with the small
810 // bin size in dlmalloc
811 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
812 capacityExtractMask = ~categoryExtractMask,
814 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
815 "Corrupt memory layout for fbstring.");
819 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
820 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
823 Category category() const {
824 // Assumes little endian
825 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
828 size_t smallSize() const {
829 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
830 return static_cast<size_t>(maxSmallSize)
831 - static_cast<size_t>(small_[maxSmallSize]);
834 void setSmallSize(size_t s) {
835 // Warning: this should work with uninitialized strings too,
836 // so don't assume anything about the previous value of
837 // small_[maxSmallSize].
838 assert(s <= maxSmallSize);
839 small_[maxSmallSize] = maxSmallSize - s;
843 #if defined(__GNUC__) && !defined(__clang__)
844 # pragma GCC diagnostic pop
847 #ifndef _LIBSTDCXX_FBSTRING
849 * Dummy fbstring core that uses an actual std::string. This doesn't
850 * make any sense - it's just for testing purposes.
852 template <class Char>
853 class dummy_fbstring_core {
855 dummy_fbstring_core() {
857 dummy_fbstring_core(const dummy_fbstring_core& another)
858 : backend_(another.backend_) {
860 dummy_fbstring_core(const Char * s, size_t n)
863 void swap(dummy_fbstring_core & rhs) {
864 backend_.swap(rhs.backend_);
866 const Char * data() const {
867 return backend_.data();
869 Char * mutable_data() {
870 //assert(!backend_.empty());
871 return &*backend_.begin();
873 void shrink(size_t delta) {
874 assert(delta <= size());
875 backend_.resize(size() - delta);
877 Char * expand_noinit(size_t delta) {
878 auto const sz = size();
879 backend_.resize(size() + delta);
880 return backend_.data() + sz;
882 void push_back(Char c) {
883 backend_.push_back(c);
885 size_t size() const {
886 return backend_.size();
888 size_t capacity() const {
889 return backend_.capacity();
891 bool isShared() const {
894 void reserve(size_t minCapacity) {
895 backend_.reserve(minCapacity);
899 std::basic_string<Char> backend_;
901 #endif // !_LIBSTDCXX_FBSTRING
904 * This is the basic_string replacement. For conformity,
905 * basic_fbstring takes the same template parameters, plus the last
906 * one which is the core.
908 #ifdef _LIBSTDCXX_FBSTRING
909 template <typename E, class T, class A, class Storage>
911 template <typename E,
912 class T = std::char_traits<E>,
913 class A = std::allocator<E>,
914 class Storage = fbstring_core<E> >
916 class basic_fbstring {
920 void (*throw_exc)(const char*),
922 if (!condition) throw_exc(msg);
925 bool isSane() const {
928 empty() == (size() == 0) &&
929 empty() == (begin() == end()) &&
930 size() <= max_size() &&
931 capacity() <= max_size() &&
932 size() <= capacity() &&
933 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
937 friend struct Invariant;
940 explicit Invariant(const basic_fbstring& s) : s_(s) {
947 const basic_fbstring& s_;
949 explicit Invariant(const basic_fbstring&) {}
951 Invariant& operator=(const Invariant&);
956 typedef T traits_type;
957 typedef typename traits_type::char_type value_type;
958 typedef A allocator_type;
959 typedef typename A::size_type size_type;
960 typedef typename A::difference_type difference_type;
962 typedef typename A::reference reference;
963 typedef typename A::const_reference const_reference;
964 typedef typename A::pointer pointer;
965 typedef typename A::const_pointer const_pointer;
968 typedef const E* const_iterator;
969 typedef std::reverse_iterator<iterator
970 #ifdef NO_ITERATOR_TRAITS
974 typedef std::reverse_iterator<const_iterator
975 #ifdef NO_ITERATOR_TRAITS
978 > const_reverse_iterator;
980 static const size_type npos; // = size_type(-1)
983 static void procrustes(size_type& n, size_type nmax) {
984 if (n > nmax) n = nmax;
988 // C++11 21.4.2 construct/copy/destroy
989 explicit basic_fbstring(const A& a = A()) {
992 basic_fbstring(const basic_fbstring& str)
993 : store_(str.store_) {
997 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
1000 #ifndef _LIBSTDCXX_FBSTRING
1001 // This is defined for compatibility with std::string
1002 /* implicit */ basic_fbstring(const std::string& str)
1003 : store_(str.data(), str.size()) {
1007 basic_fbstring(const basic_fbstring& str, size_type pos,
1008 size_type n = npos, const A& a = A()) {
1009 assign(str, pos, n);
1012 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1013 : store_(s, s ? traits_type::length(s) : ({
1014 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1015 err += ": null pointer initializer not valid";
1016 std::__throw_logic_error(err.c_str());
1021 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1025 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1026 auto const data = store_.expand_noinit(n);
1027 fbstring_detail::pod_fill(data, data + n, c);
1028 store_.writeTerminator();
1031 template <class InIt>
1032 basic_fbstring(InIt begin, InIt end,
1033 typename std::enable_if<
1034 !std::is_same<typename std::remove_const<InIt>::type,
1035 value_type*>::value, const A>::type & a = A()) {
1039 // Specialization for const char*, const char*
1040 basic_fbstring(const value_type* b, const value_type* e)
1041 : store_(b, e - b) {
1044 // Nonstandard constructor
1045 basic_fbstring(value_type *s, size_type n, size_type c,
1046 AcquireMallocatedString a)
1047 : store_(s, n, c, a) {
1050 // Construction from initialization list
1051 basic_fbstring(std::initializer_list<value_type> il) {
1052 assign(il.begin(), il.end());
1058 basic_fbstring& operator=(const basic_fbstring& lhs) {
1059 if (FBSTRING_UNLIKELY(&lhs == this)) {
1062 auto const oldSize = size();
1063 auto const srcSize = lhs.size();
1064 if (capacity() >= srcSize && !store_.isShared()) {
1065 // great, just copy the contents
1066 if (oldSize < srcSize)
1067 store_.expand_noinit(srcSize - oldSize);
1069 store_.shrink(oldSize - srcSize);
1070 assert(size() == srcSize);
1071 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1072 store_.writeTerminator();
1074 // need to reallocate, so we may as well create a brand new string
1075 basic_fbstring(lhs).swap(*this);
1081 basic_fbstring& operator=(basic_fbstring&& goner) {
1082 if (FBSTRING_UNLIKELY(&goner == this)) {
1083 // Compatibility with std::basic_string<>,
1084 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1087 // No need of this anymore
1088 this->~basic_fbstring();
1089 // Move the goner into this
1090 new(&store_) fbstring_core<E>(std::move(goner.store_));
1094 #ifndef _LIBSTDCXX_FBSTRING
1095 // Compatibility with std::string
1096 basic_fbstring & operator=(const std::string & rhs) {
1097 return assign(rhs.data(), rhs.size());
1100 // Compatibility with std::string
1101 std::string toStdString() const {
1102 return std::string(data(), size());
1105 // A lot of code in fbcode still uses this method, so keep it here for now.
1106 const basic_fbstring& toStdString() const {
1111 basic_fbstring& operator=(const value_type* s) {
1115 basic_fbstring& operator=(value_type c) {
1117 store_.expand_noinit(1);
1118 } else if (store_.isShared()) {
1119 basic_fbstring(1, c).swap(*this);
1122 store_.shrink(size() - 1);
1124 *store_.mutable_data() = c;
1125 store_.writeTerminator();
1129 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1130 return assign(il.begin(), il.end());
1133 // C++11 21.4.3 iterators:
1134 iterator begin() { return store_.mutable_data(); }
1136 const_iterator begin() const { return store_.data(); }
1138 const_iterator cbegin() const { return begin(); }
1141 return store_.mutable_data() + store_.size();
1144 const_iterator end() const {
1145 return store_.data() + store_.size();
1148 const_iterator cend() const { return end(); }
1150 reverse_iterator rbegin() {
1151 return reverse_iterator(end());
1154 const_reverse_iterator rbegin() const {
1155 return const_reverse_iterator(end());
1158 const_reverse_iterator crbegin() const { return rbegin(); }
1160 reverse_iterator rend() {
1161 return reverse_iterator(begin());
1164 const_reverse_iterator rend() const {
1165 return const_reverse_iterator(begin());
1168 const_reverse_iterator crend() const { return rend(); }
1171 // C++11 21.4.5, element access:
1172 const value_type& front() const { return *begin(); }
1173 const value_type& back() const {
1175 // Should be begin()[size() - 1], but that branches twice
1176 return *(end() - 1);
1178 value_type& front() { return *begin(); }
1179 value_type& back() {
1181 // Should be begin()[size() - 1], but that branches twice
1182 return *(end() - 1);
1189 // C++11 21.4.4 capacity:
1190 size_type size() const { return store_.size(); }
1192 size_type length() const { return size(); }
1194 size_type max_size() const {
1195 return std::numeric_limits<size_type>::max();
1198 void resize(const size_type n, const value_type c = value_type()) {
1199 auto size = this->size();
1201 store_.shrink(size - n);
1203 // Do this in two steps to minimize slack memory copied (see
1205 auto const capacity = this->capacity();
1206 assert(capacity >= size);
1207 if (size < capacity) {
1208 auto delta = std::min(n, capacity) - size;
1209 store_.expand_noinit(delta);
1210 fbstring_detail::pod_fill(begin() + size, end(), c);
1213 store_.writeTerminator();
1218 auto const delta = n - size;
1219 store_.expand_noinit(delta);
1220 fbstring_detail::pod_fill(end() - delta, end(), c);
1221 store_.writeTerminator();
1223 assert(this->size() == n);
1226 size_type capacity() const { return store_.capacity(); }
1228 void reserve(size_type res_arg = 0) {
1229 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1230 store_.reserve(res_arg);
1233 void shrink_to_fit() {
1234 // Shrink only if slack memory is sufficiently large
1235 if (capacity() < size() * 3 / 2) {
1238 basic_fbstring(cbegin(), cend()).swap(*this);
1241 void clear() { resize(0); }
1243 bool empty() const { return size() == 0; }
1245 // C++11 21.4.5 element access:
1246 const_reference operator[](size_type pos) const {
1247 return *(c_str() + pos);
1250 reference operator[](size_type pos) {
1251 if (pos == size()) {
1252 // Just call c_str() to make sure '\0' is present
1255 return *(begin() + pos);
1258 const_reference at(size_type n) const {
1259 enforce(n <= size(), std::__throw_out_of_range, "");
1263 reference at(size_type n) {
1264 enforce(n < size(), std::__throw_out_of_range, "");
1268 // C++11 21.4.6 modifiers:
1269 basic_fbstring& operator+=(const basic_fbstring& str) {
1273 basic_fbstring& operator+=(const value_type* s) {
1277 basic_fbstring& operator+=(const value_type c) {
1282 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1287 basic_fbstring& append(const basic_fbstring& str) {
1289 auto desiredSize = size() + str.size();
1291 append(str.data(), str.size());
1292 assert(size() == desiredSize);
1296 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1298 const size_type sz = str.size();
1299 enforce(pos <= sz, std::__throw_out_of_range, "");
1300 procrustes(n, sz - pos);
1301 return append(str.data() + pos, n);
1304 basic_fbstring& append(const value_type* s, size_type n) {
1306 Invariant checker(*this);
1309 if (FBSTRING_UNLIKELY(!n)) {
1310 // Unlikely but must be done
1313 auto const oldSize = size();
1314 auto const oldData = data();
1315 // Check for aliasing (rare). We could use "<=" here but in theory
1316 // those do not work for pointers unless the pointers point to
1317 // elements in the same array. For that reason we use
1318 // std::less_equal, which is guaranteed to offer a total order
1319 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1321 std::less_equal<const value_type*> le;
1322 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1323 assert(le(s + n, oldData + oldSize));
1324 const size_type offset = s - oldData;
1325 store_.reserve(oldSize + n);
1326 // Restore the source
1327 s = data() + offset;
1329 // Warning! Repeated appends with short strings may actually incur
1330 // practically quadratic performance. Avoid that by pushing back
1331 // the first character (which ensures exponential growth) and then
1332 // appending the rest normally. Worst case the append may incur a
1333 // second allocation but that will be rare.
1336 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1337 assert(size() == oldSize + n + 1);
1341 basic_fbstring& append(const value_type* s) {
1342 return append(s, traits_type::length(s));
1345 basic_fbstring& append(size_type n, value_type c) {
1346 resize(size() + n, c);
1350 template<class InputIterator>
1351 basic_fbstring& append(InputIterator first, InputIterator last) {
1352 insert(end(), first, last);
1356 basic_fbstring& append(std::initializer_list<value_type> il) {
1357 return append(il.begin(), il.end());
1360 void push_back(const value_type c) { // primitive
1361 store_.push_back(c);
1364 basic_fbstring& assign(const basic_fbstring& str) {
1365 if (&str == this) return *this;
1366 return assign(str.data(), str.size());
1369 basic_fbstring& assign(basic_fbstring&& str) {
1370 return *this = std::move(str);
1373 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1375 const size_type sz = str.size();
1376 enforce(pos <= sz, std::__throw_out_of_range, "");
1377 procrustes(n, sz - pos);
1378 return assign(str.data() + pos, n);
1381 basic_fbstring& assign(const value_type* s, const size_type n) {
1382 Invariant checker(*this);
1385 std::copy(s, s + n, begin());
1387 assert(size() == n);
1389 const value_type *const s2 = s + size();
1390 std::copy(s, s2, begin());
1391 append(s2, n - size());
1392 assert(size() == n);
1394 store_.writeTerminator();
1395 assert(size() == n);
1399 basic_fbstring& assign(const value_type* s) {
1400 return assign(s, traits_type::length(s));
1403 basic_fbstring& assign(std::initializer_list<value_type> il) {
1404 return assign(il.begin(), il.end());
1407 template <class ItOrLength, class ItOrChar>
1408 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1409 return replace(begin(), end(), first_or_n, last_or_c);
1412 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1413 return insert(pos1, str.data(), str.size());
1416 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1417 size_type pos2, size_type n) {
1418 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1419 procrustes(n, str.length() - pos2);
1420 return insert(pos1, str.data() + pos2, n);
1423 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1424 enforce(pos <= length(), std::__throw_out_of_range, "");
1425 insert(begin() + pos, s, s + n);
1429 basic_fbstring& insert(size_type pos, const value_type* s) {
1430 return insert(pos, s, traits_type::length(s));
1433 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1434 enforce(pos <= length(), std::__throw_out_of_range, "");
1435 insert(begin() + pos, n, c);
1439 iterator insert(const_iterator p, const value_type c) {
1440 const size_type pos = p - begin();
1442 return begin() + pos;
1446 template <int i> class Selector {};
1448 iterator insertImplDiscr(const_iterator p,
1449 size_type n, value_type c, Selector<1>) {
1450 Invariant checker(*this);
1452 auto const pos = p - begin();
1453 assert(p >= begin() && p <= end());
1454 if (capacity() - size() < n) {
1455 const size_type sz = p - begin();
1456 reserve(size() + n);
1459 const iterator oldEnd = end();
1460 if (n < size_type(oldEnd - p)) {
1461 append(oldEnd - n, oldEnd);
1463 // reverse_iterator(oldEnd - n),
1464 // reverse_iterator(p),
1465 // reverse_iterator(oldEnd));
1466 fbstring_detail::pod_move(&*p, &*oldEnd - n,
1468 std::fill(begin() + pos, begin() + pos + n, c);
1470 append(n - (end() - p), c);
1471 append(iterator(p), oldEnd);
1472 std::fill(iterator(p), oldEnd, c);
1474 store_.writeTerminator();
1475 return begin() + pos;
1478 template<class InputIter>
1479 iterator insertImplDiscr(const_iterator i,
1480 InputIter b, InputIter e, Selector<0>) {
1481 return insertImpl(i, b, e,
1482 typename std::iterator_traits<InputIter>::iterator_category());
1485 template <class FwdIterator>
1486 iterator insertImpl(const_iterator i,
1487 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1488 Invariant checker(*this);
1490 const size_type pos = i - begin();
1491 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1492 std::distance(s1, s2);
1494 using namespace fbstring_detail;
1495 assert(pos <= size());
1497 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1498 capacity() - size();
1500 // realloc the string
1501 reserve(size() + n2);
1504 if (pos + n2 <= size()) {
1505 const iterator tailBegin = end() - n2;
1506 store_.expand_noinit(n2);
1507 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1508 std::copy(const_reverse_iterator(tailBegin), const_reverse_iterator(i),
1509 reverse_iterator(tailBegin + n2));
1510 std::copy(s1, s2, begin() + pos);
1513 const size_type old_size = size();
1514 std::advance(t, old_size - pos);
1515 const size_t newElems = std::distance(t, s2);
1516 store_.expand_noinit(n2);
1517 std::copy(t, s2, begin() + old_size);
1518 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1519 begin() + old_size + newElems);
1520 std::copy(s1, t, begin() + pos);
1522 store_.writeTerminator();
1523 return begin() + pos;
1526 template <class InputIterator>
1527 iterator insertImpl(const_iterator i,
1528 InputIterator b, InputIterator e,
1529 std::input_iterator_tag) {
1530 const auto pos = i - begin();
1531 basic_fbstring temp(begin(), i);
1532 for (; b != e; ++b) {
1535 temp.append(i, end());
1537 return begin() + pos;
1541 template <class ItOrLength, class ItOrChar>
1542 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1543 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1544 return insertImplDiscr(p, first_or_n, last_or_c, sel);
1547 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1548 return insert(p, il.begin(), il.end());
1551 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1552 Invariant checker(*this);
1554 enforce(pos <= length(), std::__throw_out_of_range, "");
1555 procrustes(n, length() - pos);
1556 std::copy(begin() + pos + n, end(), begin() + pos);
1557 resize(length() - n);
1561 iterator erase(iterator position) {
1562 const size_type pos(position - begin());
1563 enforce(pos <= size(), std::__throw_out_of_range, "");
1565 return begin() + pos;
1568 iterator erase(iterator first, iterator last) {
1569 const size_type pos(first - begin());
1570 erase(pos, last - first);
1571 return begin() + pos;
1574 // Replaces at most n1 chars of *this, starting with pos1 with the
1576 basic_fbstring& replace(size_type pos1, size_type n1,
1577 const basic_fbstring& str) {
1578 return replace(pos1, n1, str.data(), str.size());
1581 // Replaces at most n1 chars of *this, starting with pos1,
1582 // with at most n2 chars of str starting with pos2
1583 basic_fbstring& replace(size_type pos1, size_type n1,
1584 const basic_fbstring& str,
1585 size_type pos2, size_type n2) {
1586 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1587 return replace(pos1, n1, str.data() + pos2,
1588 std::min(n2, str.size() - pos2));
1591 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1592 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1593 return replace(pos, n1, s, traits_type::length(s));
1596 // Replaces at most n1 chars of *this, starting with pos, with n2
1599 // consolidated with
1601 // Replaces at most n1 chars of *this, starting with pos, with at
1602 // most n2 chars of str. str must have at least n2 chars.
1603 template <class StrOrLength, class NumOrChar>
1604 basic_fbstring& replace(size_type pos, size_type n1,
1605 StrOrLength s_or_n2, NumOrChar n_or_c) {
1606 Invariant checker(*this);
1608 enforce(pos <= size(), std::__throw_out_of_range, "");
1609 procrustes(n1, length() - pos);
1610 const iterator b = begin() + pos;
1611 return replace(b, b + n1, s_or_n2, n_or_c);
1614 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1615 return replace(i1, i2, str.data(), str.length());
1618 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1619 return replace(i1, i2, s, traits_type::length(s));
1623 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1624 const value_type* s, size_type n,
1627 assert(begin() <= i1 && i1 <= end());
1628 assert(begin() <= i2 && i2 <= end());
1629 return replace(i1, i2, s, s + n);
1632 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1633 size_type n2, value_type c, Selector<1>) {
1634 const size_type n1 = i2 - i1;
1636 std::fill(i1, i1 + n2, c);
1639 std::fill(i1, i2, c);
1640 insert(i2, n2 - n1, c);
1646 template <class InputIter>
1647 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1648 InputIter b, InputIter e,
1650 replaceImpl(i1, i2, b, e,
1651 typename std::iterator_traits<InputIter>::iterator_category());
1656 template <class FwdIterator, class P>
1657 bool replaceAliased(iterator i1, iterator i2,
1658 FwdIterator s1, FwdIterator s2, P*) {
1662 template <class FwdIterator>
1663 bool replaceAliased(iterator i1, iterator i2,
1664 FwdIterator s1, FwdIterator s2, value_type*) {
1665 static const std::less_equal<const value_type*> le =
1666 std::less_equal<const value_type*>();
1667 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1671 // Aliased replace, copy to new string
1672 basic_fbstring temp;
1673 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1674 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1680 template <class FwdIterator>
1681 void replaceImpl(iterator i1, iterator i2,
1682 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1683 Invariant checker(*this);
1686 // Handle aliased replace
1687 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1691 auto const n1 = i2 - i1;
1693 auto const n2 = std::distance(s1, s2);
1698 std::copy(s1, s2, i1);
1702 fbstring_detail::copy_n(s1, n1, i1);
1703 std::advance(s1, n1);
1709 template <class InputIterator>
1710 void replaceImpl(iterator i1, iterator i2,
1711 InputIterator b, InputIterator e, std::input_iterator_tag) {
1712 basic_fbstring temp(begin(), i1);
1713 temp.append(b, e).append(i2, end());
1718 template <class T1, class T2>
1719 basic_fbstring& replace(iterator i1, iterator i2,
1720 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1722 num1 = std::numeric_limits<T1>::is_specialized,
1723 num2 = std::numeric_limits<T2>::is_specialized;
1724 return replaceImplDiscr(
1725 i1, i2, first_or_n_or_s, last_or_c_or_n,
1726 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1729 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1730 enforce(pos <= size(), std::__throw_out_of_range, "");
1731 procrustes(n, size() - pos);
1733 fbstring_detail::pod_copy(
1740 void swap(basic_fbstring& rhs) {
1741 store_.swap(rhs.store_);
1744 const value_type* c_str() const {
1745 return store_.c_str();
1748 const value_type* data() const { return c_str(); }
1750 allocator_type get_allocator() const {
1751 return allocator_type();
1754 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1755 return find(str.data(), pos, str.length());
1758 size_type find(const value_type* needle, const size_type pos,
1759 const size_type nsize) const {
1760 if (!nsize) return pos;
1761 auto const size = this->size();
1762 if (nsize + pos > size) return npos;
1763 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1764 // the last characters first
1765 auto const haystack = data();
1766 auto const nsize_1 = nsize - 1;
1767 auto const lastNeedle = needle[nsize_1];
1769 // Boyer-Moore skip value for the last char in the needle. Zero is
1770 // not a valid value; skip will be computed the first time it's
1774 const E * i = haystack + pos;
1775 auto iEnd = haystack + size - nsize_1;
1778 // Boyer-Moore: match the last element in the needle
1779 while (i[nsize_1] != lastNeedle) {
1785 // Here we know that the last char matches
1786 // Continue in pedestrian mode
1787 for (size_t j = 0; ; ) {
1789 if (i[j] != needle[j]) {
1790 // Not found, we can skip
1791 // Compute the skip value lazily
1794 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1801 // Check if done searching
1804 return i - haystack;
1811 size_type find(const value_type* s, size_type pos = 0) const {
1812 return find(s, pos, traits_type::length(s));
1815 size_type find (value_type c, size_type pos = 0) const {
1816 return find(&c, pos, 1);
1819 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1820 return rfind(str.data(), pos, str.length());
1823 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1824 if (n > length()) return npos;
1825 pos = std::min(pos, length() - n);
1826 if (n == 0) return pos;
1828 const_iterator i(begin() + pos);
1830 if (traits_type::eq(*i, *s)
1831 && traits_type::compare(&*i, s, n) == 0) {
1834 if (i == begin()) break;
1839 size_type rfind(const value_type* s, size_type pos = npos) const {
1840 return rfind(s, pos, traits_type::length(s));
1843 size_type rfind(value_type c, size_type pos = npos) const {
1844 return rfind(&c, pos, 1);
1847 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1848 return find_first_of(str.data(), pos, str.length());
1851 size_type find_first_of(const value_type* s,
1852 size_type pos, size_type n) const {
1853 if (pos > length() || n == 0) return npos;
1854 const_iterator i(begin() + pos),
1856 for (; i != finish; ++i) {
1857 if (traits_type::find(s, n, *i) != 0) {
1864 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1865 return find_first_of(s, pos, traits_type::length(s));
1868 size_type find_first_of(value_type c, size_type pos = 0) const {
1869 return find_first_of(&c, pos, 1);
1872 size_type find_last_of (const basic_fbstring& str,
1873 size_type pos = npos) const {
1874 return find_last_of(str.data(), pos, str.length());
1877 size_type find_last_of (const value_type* s, size_type pos,
1878 size_type n) const {
1879 if (!empty() && n > 0) {
1880 pos = std::min(pos, length() - 1);
1881 const_iterator i(begin() + pos);
1883 if (traits_type::find(s, n, *i) != 0) {
1886 if (i == begin()) break;
1892 size_type find_last_of (const value_type* s,
1893 size_type pos = npos) const {
1894 return find_last_of(s, pos, traits_type::length(s));
1897 size_type find_last_of (value_type c, size_type pos = npos) const {
1898 return find_last_of(&c, pos, 1);
1901 size_type find_first_not_of(const basic_fbstring& str,
1902 size_type pos = 0) const {
1903 return find_first_not_of(str.data(), pos, str.size());
1906 size_type find_first_not_of(const value_type* s, size_type pos,
1907 size_type n) const {
1908 if (pos < length()) {
1912 for (; i != finish; ++i) {
1913 if (traits_type::find(s, n, *i) == 0) {
1921 size_type find_first_not_of(const value_type* s,
1922 size_type pos = 0) const {
1923 return find_first_not_of(s, pos, traits_type::length(s));
1926 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1927 return find_first_not_of(&c, pos, 1);
1930 size_type find_last_not_of(const basic_fbstring& str,
1931 size_type pos = npos) const {
1932 return find_last_not_of(str.data(), pos, str.length());
1935 size_type find_last_not_of(const value_type* s, size_type pos,
1936 size_type n) const {
1937 if (!this->empty()) {
1938 pos = std::min(pos, size() - 1);
1939 const_iterator i(begin() + pos);
1941 if (traits_type::find(s, n, *i) == 0) {
1944 if (i == begin()) break;
1950 size_type find_last_not_of(const value_type* s,
1951 size_type pos = npos) const {
1952 return find_last_not_of(s, pos, traits_type::length(s));
1955 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1956 return find_last_not_of(&c, pos, 1);
1959 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1960 enforce(pos <= size(), std::__throw_out_of_range, "");
1961 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1964 int compare(const basic_fbstring& str) const {
1965 // FIX due to Goncalo N M de Carvalho July 18, 2005
1966 return compare(0, size(), str);
1969 int compare(size_type pos1, size_type n1,
1970 const basic_fbstring& str) const {
1971 return compare(pos1, n1, str.data(), str.size());
1974 int compare(size_type pos1, size_type n1,
1975 const value_type* s) const {
1976 return compare(pos1, n1, s, traits_type::length(s));
1979 int compare(size_type pos1, size_type n1,
1980 const value_type* s, size_type n2) const {
1981 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1982 procrustes(n1, size() - pos1);
1983 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1984 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1985 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1988 int compare(size_type pos1, size_type n1,
1989 const basic_fbstring& str,
1990 size_type pos2, size_type n2) const {
1991 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1992 return compare(pos1, n1, str.data() + pos2,
1993 std::min(n2, str.size() - pos2));
1996 // Code from Jean-Francois Bastien (03/26/2007)
1997 int compare(const value_type* s) const {
1998 // Could forward to compare(0, size(), s, traits_type::length(s))
1999 // but that does two extra checks
2000 const size_type n1(size()), n2(traits_type::length(s));
2001 const int r = traits_type::compare(data(), s, std::min(n1, n2));
2002 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
2010 // non-member functions
2012 template <typename E, class T, class A, class S>
2014 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2015 const basic_fbstring<E, T, A, S>& rhs) {
2017 basic_fbstring<E, T, A, S> result;
2018 result.reserve(lhs.size() + rhs.size());
2019 result.append(lhs).append(rhs);
2020 return std::move(result);
2024 template <typename E, class T, class A, class S>
2026 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2027 const basic_fbstring<E, T, A, S>& rhs) {
2028 return std::move(lhs.append(rhs));
2032 template <typename E, class T, class A, class S>
2034 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
2035 basic_fbstring<E, T, A, S>&& rhs) {
2036 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2037 // Good, at least we don't need to reallocate
2038 return std::move(rhs.insert(0, lhs));
2040 // Meh, no go. Forward to operator+(const&, const&).
2041 auto const& rhsC = rhs;
2046 template <typename E, class T, class A, class S>
2048 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
2049 basic_fbstring<E, T, A, S>&& rhs) {
2050 return std::move(lhs.append(rhs));
2053 template <typename E, class T, class A, class S>
2055 basic_fbstring<E, T, A, S> operator+(
2056 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2057 const basic_fbstring<E, T, A, S>& rhs) {
2059 basic_fbstring<E, T, A, S> result;
2060 const typename basic_fbstring<E, T, A, S>::size_type len =
2061 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2062 result.reserve(len + rhs.size());
2063 result.append(lhs, len).append(rhs);
2067 template <typename E, class T, class A, class S>
2069 basic_fbstring<E, T, A, S> operator+(
2070 typename basic_fbstring<E, T, A, S>::value_type lhs,
2071 const basic_fbstring<E, T, A, S>& rhs) {
2073 basic_fbstring<E, T, A, S> result;
2074 result.reserve(1 + rhs.size());
2075 result.push_back(lhs);
2080 template <typename E, class T, class A, class S>
2082 basic_fbstring<E, T, A, S> operator+(
2083 const basic_fbstring<E, T, A, S>& lhs,
2084 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2086 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2087 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2089 basic_fbstring<E, T, A, S> result;
2090 const size_type len = traits_type::length(rhs);
2091 result.reserve(lhs.size() + len);
2092 result.append(lhs).append(rhs, len);
2096 template <typename E, class T, class A, class S>
2098 basic_fbstring<E, T, A, S> operator+(
2099 const basic_fbstring<E, T, A, S>& lhs,
2100 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2102 basic_fbstring<E, T, A, S> result;
2103 result.reserve(lhs.size() + 1);
2105 result.push_back(rhs);
2109 template <typename E, class T, class A, class S>
2111 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2112 const basic_fbstring<E, T, A, S>& rhs) {
2113 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2115 template <typename E, class T, class A, class S>
2117 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2118 const basic_fbstring<E, T, A, S>& rhs) {
2119 return rhs == lhs; }
2121 template <typename E, class T, class A, class S>
2123 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2124 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2125 return lhs.compare(rhs) == 0; }
2127 template <typename E, class T, class A, class S>
2129 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2130 const basic_fbstring<E, T, A, S>& rhs) {
2131 return !(lhs == rhs); }
2133 template <typename E, class T, class A, class S>
2135 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2136 const basic_fbstring<E, T, A, S>& rhs) {
2137 return !(lhs == rhs); }
2139 template <typename E, class T, class A, class S>
2141 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2142 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2143 return !(lhs == rhs); }
2145 template <typename E, class T, class A, class S>
2147 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2148 const basic_fbstring<E, T, A, S>& rhs) {
2149 return lhs.compare(rhs) < 0; }
2151 template <typename E, class T, class A, class S>
2153 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2154 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2155 return lhs.compare(rhs) < 0; }
2157 template <typename E, class T, class A, class S>
2159 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2160 const basic_fbstring<E, T, A, S>& rhs) {
2161 return rhs.compare(lhs) > 0; }
2163 template <typename E, class T, class A, class S>
2165 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2166 const basic_fbstring<E, T, A, S>& rhs) {
2169 template <typename E, class T, class A, class S>
2171 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2172 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2175 template <typename E, class T, class A, class S>
2177 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2178 const basic_fbstring<E, T, A, S>& rhs) {
2181 template <typename E, class T, class A, class S>
2183 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2184 const basic_fbstring<E, T, A, S>& rhs) {
2185 return !(rhs < lhs); }
2187 template <typename E, class T, class A, class S>
2189 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2190 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2191 return !(rhs < lhs); }
2193 template <typename E, class T, class A, class S>
2195 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2196 const basic_fbstring<E, T, A, S>& rhs) {
2197 return !(rhs < lhs); }
2199 template <typename E, class T, class A, class S>
2201 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2202 const basic_fbstring<E, T, A, S>& rhs) {
2203 return !(lhs < rhs); }
2205 template <typename E, class T, class A, class S>
2207 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2208 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2209 return !(lhs < rhs); }
2211 template <typename E, class T, class A, class S>
2213 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2214 const basic_fbstring<E, T, A, S>& rhs) {
2215 return !(lhs < rhs);
2219 template <typename E, class T, class A, class S>
2220 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2224 // TODO: make this faster.
2225 template <typename E, class T, class A, class S>
2228 typename basic_fbstring<E, T, A, S>::value_type,
2229 typename basic_fbstring<E, T, A, S>::traits_type>&
2231 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2232 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2233 basic_fbstring<E, T, A, S>& str) {
2234 typename std::basic_istream<E, T>::sentry sentry(is);
2235 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2236 typename basic_fbstring<E, T, A, S>::traits_type>
2238 typedef typename __istream_type::ios_base __ios_base;
2239 size_t extracted = 0;
2240 auto err = __ios_base::goodbit;
2242 auto n = is.width();
2247 auto got = is.rdbuf()->sgetc();
2248 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2249 // Whew. We get to store this guy
2251 got = is.rdbuf()->snextc();
2253 if (got == T::eof()) {
2254 err |= __ios_base::eofbit;
2259 err |= __ios_base::failbit;
2267 template <typename E, class T, class A, class S>
2269 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2270 typename basic_fbstring<E, T, A, S>::traits_type>&
2272 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2273 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2274 const basic_fbstring<E, T, A, S>& str) {
2275 os.write(str.data(), str.size());
2279 #ifndef _LIBSTDCXX_FBSTRING
2281 template <typename E, class T, class A, class S>
2283 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2284 typename basic_fbstring<E, T, A, S>::traits_type>&
2286 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2287 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2288 basic_fbstring<E, T, A, S>& str,
2289 typename basic_fbstring<E, T, A, S>::value_type delim) {
2290 // Use the nonstandard getdelim()
2294 // This looks quadratic but it really depends on realloc
2295 auto const newSize = size + 128;
2296 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2297 is.getline(buf + size, newSize - size, delim);
2298 if (is.bad() || is.eof() || !is.fail()) {
2299 // done by either failure, end of file, or normal read
2300 size += std::strlen(buf + size);
2303 // Here we have failed due to too short a buffer
2304 // Minus one to discount the terminating '\0'
2306 assert(buf[size] == 0);
2307 // Clear the error so we can continue reading
2310 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2311 AcquireMallocatedString());
2316 template <typename E, class T, class A, class S>
2318 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2319 typename basic_fbstring<E, T, A, S>::traits_type>&
2321 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2322 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2323 basic_fbstring<E, T, A, S>& str) {
2324 // Just forward to the version with a delimiter
2325 return getline(is, str, '\n');
2330 template <typename E1, class T, class A, class S>
2331 const typename basic_fbstring<E1, T, A, S>::size_type
2332 basic_fbstring<E1, T, A, S>::npos =
2333 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2335 #ifndef _LIBSTDCXX_FBSTRING
2336 // basic_string compatibility routines
2338 template <typename E, class T, class A, class S>
2340 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2341 const std::string& rhs) {
2342 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2345 template <typename E, class T, class A, class S>
2347 bool operator==(const std::string& lhs,
2348 const basic_fbstring<E, T, A, S>& rhs) {
2352 template <typename E, class T, class A, class S>
2354 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2355 const std::string& rhs) {
2356 return !(lhs == rhs);
2359 template <typename E, class T, class A, class S>
2361 bool operator!=(const std::string& lhs,
2362 const basic_fbstring<E, T, A, S>& rhs) {
2363 return !(lhs == rhs);
2366 #if !defined(_LIBSTDCXX_FBSTRING)
2367 typedef basic_fbstring<char> fbstring;
2370 // fbstring is relocatable
2371 template <class T, class R, class A, class S>
2372 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2375 _GLIBCXX_END_NAMESPACE_VERSION
2378 } // namespace folly
2380 #pragma GCC diagnostic pop
2382 #ifndef _LIBSTDCXX_FBSTRING
2386 struct hash< ::folly::fbstring> {
2387 size_t operator()(const ::folly::fbstring& s) const {
2388 return ::folly::hash::fnv32_buf(s.data(), s.size());
2393 #endif // _LIBSTDCXX_FBSTRING
2395 #undef FBSTRING_LIKELY
2396 #undef FBSTRING_UNLIKELY
2398 #endif // FOLLY_BASE_FBSTRING_H_