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 // 21.3.1 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) {
1053 basic_fbstring& operator=(const basic_fbstring& lhs) {
1054 if (FBSTRING_UNLIKELY(&lhs == this)) {
1057 auto const oldSize = size();
1058 auto const srcSize = lhs.size();
1059 if (capacity() >= srcSize && !store_.isShared()) {
1060 // great, just copy the contents
1061 if (oldSize < srcSize)
1062 store_.expand_noinit(srcSize - oldSize);
1064 store_.shrink(oldSize - srcSize);
1065 assert(size() == srcSize);
1066 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1067 store_.writeTerminator();
1069 // need to reallocate, so we may as well create a brand new string
1070 basic_fbstring(lhs).swap(*this);
1076 basic_fbstring& operator=(basic_fbstring&& goner) {
1077 if (FBSTRING_UNLIKELY(&goner == this)) {
1078 // Compatibility with std::basic_string<>,
1079 // 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1082 // No need of this anymore
1083 this->~basic_fbstring();
1084 // Move the goner into this
1085 new(&store_) fbstring_core<E>(std::move(goner.store_));
1089 #ifndef _LIBSTDCXX_FBSTRING
1090 // Compatibility with std::string
1091 basic_fbstring & operator=(const std::string & rhs) {
1092 return assign(rhs.data(), rhs.size());
1095 // Compatibility with std::string
1096 std::string toStdString() const {
1097 return std::string(data(), size());
1100 // A lot of code in fbcode still uses this method, so keep it here for now.
1101 const basic_fbstring& toStdString() const {
1106 basic_fbstring& operator=(const value_type* s) {
1110 basic_fbstring& operator=(value_type c) {
1112 store_.expand_noinit(1);
1113 } else if (store_.isShared()) {
1114 basic_fbstring(1, c).swap(*this);
1117 store_.shrink(size() - 1);
1119 *store_.mutable_data() = c;
1120 store_.writeTerminator();
1124 // 21.3.2 iterators:
1125 iterator begin() { return store_.mutable_data(); }
1127 const_iterator begin() const { return store_.data(); }
1130 return store_.mutable_data() + store_.size();
1133 const_iterator end() const {
1134 return store_.data() + store_.size();
1137 reverse_iterator rbegin() {
1138 return reverse_iterator(end());
1141 const_reverse_iterator rbegin() const {
1142 return const_reverse_iterator(end());
1145 reverse_iterator rend() {
1146 return reverse_iterator(begin());
1149 const_reverse_iterator rend() const {
1150 return const_reverse_iterator(begin());
1154 // C++11 21.4.5, element access:
1155 const value_type& front() const { return *begin(); }
1156 const value_type& back() const {
1158 // Should be begin()[size() - 1], but that branches twice
1159 return *(end() - 1);
1161 value_type& front() { return *begin(); }
1162 value_type& back() {
1164 // Should be begin()[size() - 1], but that branches twice
1165 return *(end() - 1);
1173 size_type size() const { return store_.size(); }
1175 size_type length() const { return size(); }
1177 size_type max_size() const {
1178 return std::numeric_limits<size_type>::max();
1181 void resize(const size_type n, const value_type c = value_type()) {
1182 auto size = this->size();
1184 store_.shrink(size - n);
1186 // Do this in two steps to minimize slack memory copied (see
1188 auto const capacity = this->capacity();
1189 assert(capacity >= size);
1190 if (size < capacity) {
1191 auto delta = std::min(n, capacity) - size;
1192 store_.expand_noinit(delta);
1193 fbstring_detail::pod_fill(begin() + size, end(), c);
1196 store_.writeTerminator();
1201 auto const delta = n - size;
1202 store_.expand_noinit(delta);
1203 fbstring_detail::pod_fill(end() - delta, end(), c);
1204 store_.writeTerminator();
1206 assert(this->size() == n);
1209 size_type capacity() const { return store_.capacity(); }
1211 void reserve(size_type res_arg = 0) {
1212 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1213 store_.reserve(res_arg);
1216 void clear() { resize(0); }
1218 bool empty() const { return size() == 0; }
1220 // 21.3.4 element access:
1221 const_reference operator[](size_type pos) const {
1222 return *(c_str() + pos);
1225 reference operator[](size_type pos) {
1226 if (pos == size()) {
1227 // Just call c_str() to make sure '\0' is present
1230 return *(begin() + pos);
1233 const_reference at(size_type n) const {
1234 enforce(n <= size(), std::__throw_out_of_range, "");
1238 reference at(size_type n) {
1239 enforce(n < size(), std::__throw_out_of_range, "");
1243 // 21.3.5 modifiers:
1244 basic_fbstring& operator+=(const basic_fbstring& str) {
1248 basic_fbstring& operator+=(const value_type* s) {
1252 basic_fbstring& operator+=(const value_type c) {
1257 basic_fbstring& append(const basic_fbstring& str) {
1259 auto desiredSize = size() + str.size();
1261 append(str.data(), str.size());
1262 assert(size() == desiredSize);
1266 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1268 const size_type sz = str.size();
1269 enforce(pos <= sz, std::__throw_out_of_range, "");
1270 procrustes(n, sz - pos);
1271 return append(str.data() + pos, n);
1274 basic_fbstring& append(const value_type* s, size_type n) {
1276 Invariant checker(*this);
1279 if (FBSTRING_UNLIKELY(!n)) {
1280 // Unlikely but must be done
1283 auto const oldSize = size();
1284 auto const oldData = data();
1285 // Check for aliasing (rare). We could use "<=" here but in theory
1286 // those do not work for pointers unless the pointers point to
1287 // elements in the same array. For that reason we use
1288 // std::less_equal, which is guaranteed to offer a total order
1289 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1291 std::less_equal<const value_type*> le;
1292 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1293 assert(le(s + n, oldData + oldSize));
1294 const size_type offset = s - oldData;
1295 store_.reserve(oldSize + n);
1296 // Restore the source
1297 s = data() + offset;
1299 // Warning! Repeated appends with short strings may actually incur
1300 // practically quadratic performance. Avoid that by pushing back
1301 // the first character (which ensures exponential growth) and then
1302 // appending the rest normally. Worst case the append may incur a
1303 // second allocation but that will be rare.
1306 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1307 assert(size() == oldSize + n + 1);
1311 basic_fbstring& append(const value_type* s) {
1312 return append(s, traits_type::length(s));
1315 basic_fbstring& append(size_type n, value_type c) {
1316 resize(size() + n, c);
1320 template<class InputIterator>
1321 basic_fbstring& append(InputIterator first, InputIterator last) {
1322 insert(end(), first, last);
1326 void push_back(const value_type c) { // primitive
1327 store_.push_back(c);
1330 basic_fbstring& assign(const basic_fbstring& str) {
1331 if (&str == this) return *this;
1332 return assign(str.data(), str.size());
1335 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1337 const size_type sz = str.size();
1338 enforce(pos <= sz, std::__throw_out_of_range, "");
1339 procrustes(n, sz - pos);
1340 return assign(str.data() + pos, n);
1343 basic_fbstring& assign(const value_type* s, const size_type n) {
1344 Invariant checker(*this);
1347 std::copy(s, s + n, begin());
1349 assert(size() == n);
1351 const value_type *const s2 = s + size();
1352 std::copy(s, s2, begin());
1353 append(s2, n - size());
1354 assert(size() == n);
1356 store_.writeTerminator();
1357 assert(size() == n);
1361 basic_fbstring& assign(const value_type* s) {
1362 return assign(s, traits_type::length(s));
1365 template <class ItOrLength, class ItOrChar>
1366 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1367 return replace(begin(), end(), first_or_n, last_or_c);
1370 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1371 return insert(pos1, str.data(), str.size());
1374 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1375 size_type pos2, size_type n) {
1376 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1377 procrustes(n, str.length() - pos2);
1378 return insert(pos1, str.data() + pos2, n);
1381 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1382 enforce(pos <= length(), std::__throw_out_of_range, "");
1383 insert(begin() + pos, s, s + n);
1387 basic_fbstring& insert(size_type pos, const value_type* s) {
1388 return insert(pos, s, traits_type::length(s));
1391 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1392 enforce(pos <= length(), std::__throw_out_of_range, "");
1393 insert(begin() + pos, n, c);
1397 iterator insert(const iterator p, const value_type c) {
1398 const size_type pos = p - begin();
1400 return begin() + pos;
1404 template <int i> class Selector {};
1406 basic_fbstring& insertImplDiscr(iterator p,
1407 size_type n, value_type c, Selector<1>) {
1408 Invariant checker(*this);
1410 assert(p >= begin() && p <= end());
1411 if (capacity() - size() < n) {
1412 const size_type sz = p - begin();
1413 reserve(size() + n);
1416 const iterator oldEnd = end();
1417 if( n < size_type(oldEnd - p)) {
1418 append(oldEnd - n, oldEnd);
1420 // reverse_iterator(oldEnd - n),
1421 // reverse_iterator(p),
1422 // reverse_iterator(oldEnd));
1423 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1424 std::fill(p, p + n, c);
1426 append(n - (end() - p), c);
1428 std::fill(p, oldEnd, c);
1430 store_.writeTerminator();
1434 template<class InputIter>
1435 basic_fbstring& insertImplDiscr(iterator i,
1436 InputIter b, InputIter e, Selector<0>) {
1438 typename std::iterator_traits<InputIter>::iterator_category());
1442 template <class FwdIterator>
1443 void insertImpl(iterator i,
1444 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1445 Invariant checker(*this);
1447 const size_type pos = i - begin();
1448 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1449 std::distance(s1, s2);
1451 using namespace fbstring_detail;
1452 assert(pos <= size());
1454 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1455 capacity() - size();
1457 // realloc the string
1458 reserve(size() + n2);
1461 if (pos + n2 <= size()) {
1462 const iterator tailBegin = end() - n2;
1463 store_.expand_noinit(n2);
1464 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1465 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1466 reverse_iterator(tailBegin + n2));
1467 std::copy(s1, s2, i);
1470 const size_type old_size = size();
1471 std::advance(t, old_size - pos);
1472 const size_t newElems = std::distance(t, s2);
1473 store_.expand_noinit(n2);
1474 std::copy(t, s2, begin() + old_size);
1475 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1476 begin() + old_size + newElems);
1477 std::copy(s1, t, i);
1479 store_.writeTerminator();
1482 template <class InputIterator>
1483 void insertImpl(iterator i,
1484 InputIterator b, InputIterator e, std::input_iterator_tag) {
1485 basic_fbstring temp(begin(), i);
1486 for (; b != e; ++b) {
1489 temp.append(i, end());
1494 template <class ItOrLength, class ItOrChar>
1495 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1496 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1497 insertImplDiscr(p, first_or_n, last_or_c, sel);
1500 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1501 Invariant checker(*this);
1503 enforce(pos <= length(), std::__throw_out_of_range, "");
1504 procrustes(n, length() - pos);
1505 std::copy(begin() + pos + n, end(), begin() + pos);
1506 resize(length() - n);
1510 iterator erase(iterator position) {
1511 const size_type pos(position - begin());
1512 enforce(pos <= size(), std::__throw_out_of_range, "");
1514 return begin() + pos;
1517 iterator erase(iterator first, iterator last) {
1518 const size_type pos(first - begin());
1519 erase(pos, last - first);
1520 return begin() + pos;
1523 // Replaces at most n1 chars of *this, starting with pos1 with the
1525 basic_fbstring& replace(size_type pos1, size_type n1,
1526 const basic_fbstring& str) {
1527 return replace(pos1, n1, str.data(), str.size());
1530 // Replaces at most n1 chars of *this, starting with pos1,
1531 // with at most n2 chars of str starting with pos2
1532 basic_fbstring& replace(size_type pos1, size_type n1,
1533 const basic_fbstring& str,
1534 size_type pos2, size_type n2) {
1535 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1536 return replace(pos1, n1, str.data() + pos2,
1537 std::min(n2, str.size() - pos2));
1540 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1541 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1542 return replace(pos, n1, s, traits_type::length(s));
1545 // Replaces at most n1 chars of *this, starting with pos, with n2
1548 // consolidated with
1550 // Replaces at most n1 chars of *this, starting with pos, with at
1551 // most n2 chars of str. str must have at least n2 chars.
1552 template <class StrOrLength, class NumOrChar>
1553 basic_fbstring& replace(size_type pos, size_type n1,
1554 StrOrLength s_or_n2, NumOrChar n_or_c) {
1555 Invariant checker(*this);
1557 enforce(pos <= size(), std::__throw_out_of_range, "");
1558 procrustes(n1, length() - pos);
1559 const iterator b = begin() + pos;
1560 return replace(b, b + n1, s_or_n2, n_or_c);
1563 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1564 return replace(i1, i2, str.data(), str.length());
1567 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1568 return replace(i1, i2, s, traits_type::length(s));
1572 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1573 const value_type* s, size_type n,
1576 assert(begin() <= i1 && i1 <= end());
1577 assert(begin() <= i2 && i2 <= end());
1578 return replace(i1, i2, s, s + n);
1581 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1582 size_type n2, value_type c, Selector<1>) {
1583 const size_type n1 = i2 - i1;
1585 std::fill(i1, i1 + n2, c);
1588 std::fill(i1, i2, c);
1589 insert(i2, n2 - n1, c);
1595 template <class InputIter>
1596 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1597 InputIter b, InputIter e,
1599 replaceImpl(i1, i2, b, e,
1600 typename std::iterator_traits<InputIter>::iterator_category());
1605 template <class FwdIterator, class P>
1606 bool replaceAliased(iterator i1, iterator i2,
1607 FwdIterator s1, FwdIterator s2, P*) {
1611 template <class FwdIterator>
1612 bool replaceAliased(iterator i1, iterator i2,
1613 FwdIterator s1, FwdIterator s2, value_type*) {
1614 static const std::less_equal<const value_type*> le =
1615 std::less_equal<const value_type*>();
1616 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1620 // Aliased replace, copy to new string
1621 basic_fbstring temp;
1622 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1623 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1629 template <class FwdIterator>
1630 void replaceImpl(iterator i1, iterator i2,
1631 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1632 Invariant checker(*this);
1635 // Handle aliased replace
1636 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1640 auto const n1 = i2 - i1;
1642 auto const n2 = std::distance(s1, s2);
1647 std::copy(s1, s2, i1);
1651 fbstring_detail::copy_n(s1, n1, i1);
1652 std::advance(s1, n1);
1658 template <class InputIterator>
1659 void replaceImpl(iterator i1, iterator i2,
1660 InputIterator b, InputIterator e, std::input_iterator_tag) {
1661 basic_fbstring temp(begin(), i1);
1662 temp.append(b, e).append(i2, end());
1667 template <class T1, class T2>
1668 basic_fbstring& replace(iterator i1, iterator i2,
1669 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1671 num1 = std::numeric_limits<T1>::is_specialized,
1672 num2 = std::numeric_limits<T2>::is_specialized;
1673 return replaceImplDiscr(
1674 i1, i2, first_or_n_or_s, last_or_c_or_n,
1675 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1678 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1679 enforce(pos <= size(), std::__throw_out_of_range, "");
1680 procrustes(n, size() - pos);
1682 fbstring_detail::pod_copy(
1689 void swap(basic_fbstring& rhs) {
1690 store_.swap(rhs.store_);
1693 // 21.3.6 string operations:
1694 const value_type* c_str() const {
1695 return store_.c_str();
1698 const value_type* data() const { return c_str(); }
1700 allocator_type get_allocator() const {
1701 return allocator_type();
1704 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1705 return find(str.data(), pos, str.length());
1708 size_type find(const value_type* needle, const size_type pos,
1709 const size_type nsize) const {
1710 if (!nsize) return pos;
1711 auto const size = this->size();
1712 if (nsize + pos > size) return npos;
1713 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1714 // the last characters first
1715 auto const haystack = data();
1716 auto const nsize_1 = nsize - 1;
1717 auto const lastNeedle = needle[nsize_1];
1719 // Boyer-Moore skip value for the last char in the needle. Zero is
1720 // not a valid value; skip will be computed the first time it's
1724 const E * i = haystack + pos;
1725 auto iEnd = haystack + size - nsize_1;
1728 // Boyer-Moore: match the last element in the needle
1729 while (i[nsize_1] != lastNeedle) {
1735 // Here we know that the last char matches
1736 // Continue in pedestrian mode
1737 for (size_t j = 0; ; ) {
1739 if (i[j] != needle[j]) {
1740 // Not found, we can skip
1741 // Compute the skip value lazily
1744 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1751 // Check if done searching
1754 return i - haystack;
1761 size_type find(const value_type* s, size_type pos = 0) const {
1762 return find(s, pos, traits_type::length(s));
1765 size_type find (value_type c, size_type pos = 0) const {
1766 return find(&c, pos, 1);
1769 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1770 return rfind(str.data(), pos, str.length());
1773 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1774 if (n > length()) return npos;
1775 pos = std::min(pos, length() - n);
1776 if (n == 0) return pos;
1778 const_iterator i(begin() + pos);
1780 if (traits_type::eq(*i, *s)
1781 && traits_type::compare(&*i, s, n) == 0) {
1784 if (i == begin()) break;
1789 size_type rfind(const value_type* s, size_type pos = npos) const {
1790 return rfind(s, pos, traits_type::length(s));
1793 size_type rfind(value_type c, size_type pos = npos) const {
1794 return rfind(&c, pos, 1);
1797 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1798 return find_first_of(str.data(), pos, str.length());
1801 size_type find_first_of(const value_type* s,
1802 size_type pos, size_type n) const {
1803 if (pos > length() || n == 0) return npos;
1804 const_iterator i(begin() + pos),
1806 for (; i != finish; ++i) {
1807 if (traits_type::find(s, n, *i) != 0) {
1814 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1815 return find_first_of(s, pos, traits_type::length(s));
1818 size_type find_first_of(value_type c, size_type pos = 0) const {
1819 return find_first_of(&c, pos, 1);
1822 size_type find_last_of (const basic_fbstring& str,
1823 size_type pos = npos) const {
1824 return find_last_of(str.data(), pos, str.length());
1827 size_type find_last_of (const value_type* s, size_type pos,
1828 size_type n) const {
1829 if (!empty() && n > 0) {
1830 pos = std::min(pos, length() - 1);
1831 const_iterator i(begin() + pos);
1833 if (traits_type::find(s, n, *i) != 0) {
1836 if (i == begin()) break;
1842 size_type find_last_of (const value_type* s,
1843 size_type pos = npos) const {
1844 return find_last_of(s, pos, traits_type::length(s));
1847 size_type find_last_of (value_type c, size_type pos = npos) const {
1848 return find_last_of(&c, pos, 1);
1851 size_type find_first_not_of(const basic_fbstring& str,
1852 size_type pos = 0) const {
1853 return find_first_not_of(str.data(), pos, str.size());
1856 size_type find_first_not_of(const value_type* s, size_type pos,
1857 size_type n) const {
1858 if (pos < length()) {
1862 for (; i != finish; ++i) {
1863 if (traits_type::find(s, n, *i) == 0) {
1871 size_type find_first_not_of(const value_type* s,
1872 size_type pos = 0) const {
1873 return find_first_not_of(s, pos, traits_type::length(s));
1876 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1877 return find_first_not_of(&c, pos, 1);
1880 size_type find_last_not_of(const basic_fbstring& str,
1881 size_type pos = npos) const {
1882 return find_last_not_of(str.data(), pos, str.length());
1885 size_type find_last_not_of(const value_type* s, size_type pos,
1886 size_type n) const {
1887 if (!this->empty()) {
1888 pos = std::min(pos, size() - 1);
1889 const_iterator i(begin() + pos);
1891 if (traits_type::find(s, n, *i) == 0) {
1894 if (i == begin()) break;
1900 size_type find_last_not_of(const value_type* s,
1901 size_type pos = npos) const {
1902 return find_last_not_of(s, pos, traits_type::length(s));
1905 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1906 return find_last_not_of(&c, pos, 1);
1909 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1910 enforce(pos <= size(), std::__throw_out_of_range, "");
1911 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1914 int compare(const basic_fbstring& str) const {
1915 // FIX due to Goncalo N M de Carvalho July 18, 2005
1916 return compare(0, size(), str);
1919 int compare(size_type pos1, size_type n1,
1920 const basic_fbstring& str) const {
1921 return compare(pos1, n1, str.data(), str.size());
1924 int compare(size_type pos1, size_type n1,
1925 const value_type* s) const {
1926 return compare(pos1, n1, s, traits_type::length(s));
1929 int compare(size_type pos1, size_type n1,
1930 const value_type* s, size_type n2) const {
1931 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1932 procrustes(n1, size() - pos1);
1933 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1934 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1935 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1938 int compare(size_type pos1, size_type n1,
1939 const basic_fbstring& str,
1940 size_type pos2, size_type n2) const {
1941 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1942 return compare(pos1, n1, str.data() + pos2,
1943 std::min(n2, str.size() - pos2));
1946 // Code from Jean-Francois Bastien (03/26/2007)
1947 int compare(const value_type* s) const {
1948 // Could forward to compare(0, size(), s, traits_type::length(s))
1949 // but that does two extra checks
1950 const size_type n1(size()), n2(traits_type::length(s));
1951 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1952 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1960 // non-member functions
1962 template <typename E, class T, class A, class S>
1964 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1965 const basic_fbstring<E, T, A, S>& rhs) {
1967 basic_fbstring<E, T, A, S> result;
1968 result.reserve(lhs.size() + rhs.size());
1969 result.append(lhs).append(rhs);
1970 return std::move(result);
1974 template <typename E, class T, class A, class S>
1976 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1977 const basic_fbstring<E, T, A, S>& rhs) {
1978 return std::move(lhs.append(rhs));
1982 template <typename E, class T, class A, class S>
1984 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1985 basic_fbstring<E, T, A, S>&& rhs) {
1986 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1987 // Good, at least we don't need to reallocate
1988 return std::move(rhs.insert(0, lhs));
1990 // Meh, no go. Forward to operator+(const&, const&).
1991 auto const& rhsC = rhs;
1996 template <typename E, class T, class A, class S>
1998 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1999 basic_fbstring<E, T, A, S>&& rhs) {
2000 return std::move(lhs.append(rhs));
2003 template <typename E, class T, class A, class S>
2005 basic_fbstring<E, T, A, S> operator+(
2006 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2007 const basic_fbstring<E, T, A, S>& rhs) {
2009 basic_fbstring<E, T, A, S> result;
2010 const typename basic_fbstring<E, T, A, S>::size_type len =
2011 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2012 result.reserve(len + rhs.size());
2013 result.append(lhs, len).append(rhs);
2017 template <typename E, class T, class A, class S>
2019 basic_fbstring<E, T, A, S> operator+(
2020 typename basic_fbstring<E, T, A, S>::value_type lhs,
2021 const basic_fbstring<E, T, A, S>& rhs) {
2023 basic_fbstring<E, T, A, S> result;
2024 result.reserve(1 + rhs.size());
2025 result.push_back(lhs);
2030 template <typename E, class T, class A, class S>
2032 basic_fbstring<E, T, A, S> operator+(
2033 const basic_fbstring<E, T, A, S>& lhs,
2034 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2036 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2037 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2039 basic_fbstring<E, T, A, S> result;
2040 const size_type len = traits_type::length(rhs);
2041 result.reserve(lhs.size() + len);
2042 result.append(lhs).append(rhs, len);
2046 template <typename E, class T, class A, class S>
2048 basic_fbstring<E, T, A, S> operator+(
2049 const basic_fbstring<E, T, A, S>& lhs,
2050 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2052 basic_fbstring<E, T, A, S> result;
2053 result.reserve(lhs.size() + 1);
2055 result.push_back(rhs);
2059 template <typename E, class T, class A, class S>
2061 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2062 const basic_fbstring<E, T, A, S>& rhs) {
2063 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2065 template <typename E, class T, class A, class S>
2067 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2068 const basic_fbstring<E, T, A, S>& rhs) {
2069 return rhs == lhs; }
2071 template <typename E, class T, class A, class S>
2073 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2074 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2075 return lhs.compare(rhs) == 0; }
2077 template <typename E, class T, class A, class S>
2079 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2080 const basic_fbstring<E, T, A, S>& rhs) {
2081 return !(lhs == rhs); }
2083 template <typename E, class T, class A, class S>
2085 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2086 const basic_fbstring<E, T, A, S>& rhs) {
2087 return !(lhs == rhs); }
2089 template <typename E, class T, class A, class S>
2091 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2092 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2093 return !(lhs == rhs); }
2095 template <typename E, class T, class A, class S>
2097 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2098 const basic_fbstring<E, T, A, S>& rhs) {
2099 return lhs.compare(rhs) < 0; }
2101 template <typename E, class T, class A, class S>
2103 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2104 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2105 return lhs.compare(rhs) < 0; }
2107 template <typename E, class T, class A, class S>
2109 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2110 const basic_fbstring<E, T, A, S>& rhs) {
2111 return rhs.compare(lhs) > 0; }
2113 template <typename E, class T, class A, class S>
2115 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2116 const basic_fbstring<E, T, A, S>& rhs) {
2119 template <typename E, class T, class A, class S>
2121 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2122 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2125 template <typename E, class T, class A, class S>
2127 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2128 const basic_fbstring<E, T, A, S>& rhs) {
2131 template <typename E, class T, class A, class S>
2133 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2134 const basic_fbstring<E, T, A, S>& rhs) {
2135 return !(rhs < lhs); }
2137 template <typename E, class T, class A, class S>
2139 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2140 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2141 return !(rhs < lhs); }
2143 template <typename E, class T, class A, class S>
2145 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2146 const basic_fbstring<E, T, A, S>& rhs) {
2147 return !(rhs < lhs); }
2149 template <typename E, class T, class A, class S>
2151 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2152 const basic_fbstring<E, T, A, S>& rhs) {
2153 return !(lhs < rhs); }
2155 template <typename E, class T, class A, class S>
2157 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2158 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2159 return !(lhs < rhs); }
2161 template <typename E, class T, class A, class S>
2163 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2164 const basic_fbstring<E, T, A, S>& rhs) {
2165 return !(lhs < rhs);
2168 // subclause 21.3.7.8:
2169 template <typename E, class T, class A, class S>
2170 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2174 // TODO: make this faster.
2175 template <typename E, class T, class A, class S>
2178 typename basic_fbstring<E, T, A, S>::value_type,
2179 typename basic_fbstring<E, T, A, S>::traits_type>&
2181 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2182 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2183 basic_fbstring<E, T, A, S>& str) {
2184 typename std::basic_istream<E, T>::sentry sentry(is);
2185 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2186 typename basic_fbstring<E, T, A, S>::traits_type>
2188 typedef typename __istream_type::ios_base __ios_base;
2189 size_t extracted = 0;
2190 auto err = __ios_base::goodbit;
2192 auto n = is.width();
2197 auto got = is.rdbuf()->sgetc();
2198 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2199 // Whew. We get to store this guy
2201 got = is.rdbuf()->snextc();
2203 if (got == T::eof()) {
2204 err |= __ios_base::eofbit;
2209 err |= __ios_base::failbit;
2217 template <typename E, class T, class A, class S>
2219 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2220 typename basic_fbstring<E, T, A, S>::traits_type>&
2222 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2223 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2224 const basic_fbstring<E, T, A, S>& str) {
2225 os.write(str.data(), str.size());
2229 #ifndef _LIBSTDCXX_FBSTRING
2231 template <typename E, class T, class A, class S>
2233 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2234 typename basic_fbstring<E, T, A, S>::traits_type>&
2236 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2237 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2238 basic_fbstring<E, T, A, S>& str,
2239 typename basic_fbstring<E, T, A, S>::value_type delim) {
2240 // Use the nonstandard getdelim()
2244 // This looks quadratic but it really depends on realloc
2245 auto const newSize = size + 128;
2246 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2247 is.getline(buf + size, newSize - size, delim);
2248 if (is.bad() || is.eof() || !is.fail()) {
2249 // done by either failure, end of file, or normal read
2250 size += std::strlen(buf + size);
2253 // Here we have failed due to too short a buffer
2254 // Minus one to discount the terminating '\0'
2256 assert(buf[size] == 0);
2257 // Clear the error so we can continue reading
2260 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2261 AcquireMallocatedString());
2266 template <typename E, class T, class A, class S>
2268 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2269 typename basic_fbstring<E, T, A, S>::traits_type>&
2271 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2272 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2273 basic_fbstring<E, T, A, S>& str) {
2274 // Just forward to the version with a delimiter
2275 return getline(is, str, '\n');
2280 template <typename E1, class T, class A, class S>
2281 const typename basic_fbstring<E1, T, A, S>::size_type
2282 basic_fbstring<E1, T, A, S>::npos =
2283 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2285 #ifndef _LIBSTDCXX_FBSTRING
2286 // basic_string compatibility routines
2288 template <typename E, class T, class A, class S>
2290 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2291 const std::string& rhs) {
2292 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2295 template <typename E, class T, class A, class S>
2297 bool operator==(const std::string& lhs,
2298 const basic_fbstring<E, T, A, S>& rhs) {
2302 template <typename E, class T, class A, class S>
2304 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2305 const std::string& rhs) {
2306 return !(lhs == rhs);
2309 template <typename E, class T, class A, class S>
2311 bool operator!=(const std::string& lhs,
2312 const basic_fbstring<E, T, A, S>& rhs) {
2313 return !(lhs == rhs);
2316 #if !defined(_LIBSTDCXX_FBSTRING)
2317 typedef basic_fbstring<char> fbstring;
2320 // fbstring is relocatable
2321 template <class T, class R, class A, class S>
2322 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2325 _GLIBCXX_END_NAMESPACE_VERSION
2328 } // namespace folly
2330 #pragma GCC diagnostic pop
2332 #ifndef _LIBSTDCXX_FBSTRING
2336 struct hash< ::folly::fbstring> {
2337 size_t operator()(const ::folly::fbstring& s) const {
2338 return ::folly::hash::fnv32_buf(s.data(), s.size());
2343 #endif // _LIBSTDCXX_FBSTRING
2345 #undef FBSTRING_LIKELY
2346 #undef FBSTRING_UNLIKELY
2348 #endif // FOLLY_BASE_FBSTRING_H_