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 #ifdef _LIBSTDCXX_FBSTRING
105 namespace std _GLIBCXX_VISIBILITY(default) {
106 _GLIBCXX_BEGIN_NAMESPACE_VERSION
111 namespace fbstring_detail {
113 template <class InIt, class OutIt>
116 typename std::iterator_traits<InIt>::difference_type n,
118 for (; n != 0; --n, ++b, ++d) {
119 assert((const void*)&*d != &*b);
125 template <class Pod, class T>
126 inline void pod_fill(Pod* b, Pod* e, T c) {
127 assert(b && e && b <= e);
128 /*static*/ if (sizeof(T) == 1) {
131 auto const ee = b + ((e - b) & ~7u);
132 for (; b != ee; b += 8) {
143 for (; b != e; ++b) {
150 * Lightly structured memcpy, simplifies copying PODs and introduces
151 * some asserts. Unfortunately using this function may cause
152 * measurable overhead (presumably because it adjusts from a begin/end
153 * convention to a pointer/size convention, so it does some extra
154 * arithmetic even though the caller might have done the inverse
155 * adaptation outside).
158 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
160 assert(d >= e || d + (e - b) <= b);
161 memcpy(d, b, (e - b) * sizeof(Pod));
165 * Lightly structured memmove, simplifies copying PODs and introduces
169 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
171 memmove(d, b, (e - b) * sizeof(*b));
174 } // namespace fbstring_detail
177 * Defines a special acquisition method for constructing fbstring
178 * objects. AcquireMallocatedString means that the user passes a
179 * pointer to a malloc-allocated string that the fbstring object will
182 enum class AcquireMallocatedString {};
185 * fbstring_core_model is a mock-up type that defines all required
186 * signatures of a fbstring core. The fbstring class itself uses such
187 * a core object to implement all of the numerous member functions
188 * required by the standard.
190 * If you want to define a new core, copy the definition below and
191 * implement the primitives. Then plug the core into basic_fbstring as
192 * a template argument.
194 template <class Char>
195 class fbstring_core_model {
197 fbstring_core_model();
198 fbstring_core_model(const fbstring_core_model &);
199 ~fbstring_core_model();
200 // Returns a pointer to string's buffer (currently only contiguous
201 // strings are supported). The pointer is guaranteed to be valid
202 // until the next call to a non-const member function.
203 const Char * data() const;
204 // Much like data(), except the string is prepared to support
205 // character-level changes. This call is a signal for
206 // e.g. reference-counted implementation to fork the data. The
207 // pointer is guaranteed to be valid until the next call to a
208 // non-const member function.
209 Char * mutable_data();
210 // Returns a pointer to string's buffer and guarantees that a
211 // readable '\0' lies right after the buffer. The pointer is
212 // guaranteed to be valid until the next call to a non-const member
214 const Char * c_str() const;
215 // Shrinks the string by delta characters. Asserts that delta <=
217 void shrink(size_t delta);
218 // Expands the string by delta characters (i.e. after this call
219 // size() will report the old size() plus delta) but without
220 // initializing the expanded region. Returns a pointer to the memory
221 // to be initialized (the beginning of the expanded portion). The
222 // caller is expected to fill the expanded area appropriately.
223 Char* expand_noinit(size_t delta);
224 // Expands the string by one character and sets the last character
226 void push_back(Char c);
227 // Returns the string's size.
229 // Returns the string's capacity, i.e. maximum size that the string
230 // can grow to without reallocation. Note that for reference counted
231 // strings that's technically a lie - even assigning characters
232 // within the existing size would cause a reallocation.
233 size_t capacity() const;
234 // Returns true if the data underlying the string is actually shared
235 // across multiple strings (in a refcounted fashion).
236 bool isShared() const;
237 // Makes sure that at least minCapacity characters are available for
238 // the string without reallocation. For reference-counted strings,
239 // it should fork the data even if minCapacity < size().
240 void reserve(size_t minCapacity);
243 fbstring_core_model& operator=(const fbstring_core_model &);
248 * gcc-4.7 throws what appears to be some false positive uninitialized
249 * warnings for the members of the MediumLarge struct. So, mute them here.
251 # pragma GCC diagnostic push
252 # pragma GCC diagnostic ignored "-Wuninitialized"
255 * This is the core of the string. The code should work on 32- and
256 * 64-bit architectures and with any Char size. Porting to big endian
257 * architectures would require some changes.
259 * The storage is selected as follows (assuming we store one-byte
260 * characters on a 64-bit machine): (a) "small" strings between 0 and
261 * 23 chars are stored in-situ without allocation (the rightmost byte
262 * stores the size); (b) "medium" strings from 24 through 254 chars
263 * are stored in malloc-allocated memory that is copied eagerly; (c)
264 * "large" strings of 255 chars and above are stored in a similar
265 * structure as medium arrays, except that the string is
266 * reference-counted and copied lazily. the reference count is
267 * allocated right before the character array.
269 * The discriminator between these three strategies sits in the two
270 * most significant bits of the rightmost char of the storage. If
271 * neither is set, then the string is small (and its length sits in
272 * the lower-order bits of that rightmost character). If the MSb is
273 * set, the string is medium width. If the second MSb is set, then the
276 template <class Char> class fbstring_core {
279 // Only initialize the tag, will set the MSBs (i.e. the small
280 // string size) to zero too
281 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
282 // or: setSmallSize(0);
284 assert(category() == isSmall && size() == 0);
287 fbstring_core(const fbstring_core & rhs) {
288 assert(&rhs != this);
289 // Simplest case first: small strings are bitblitted
290 if (rhs.category() == isSmall) {
291 assert(offsetof(MediumLarge, data_) == 0);
292 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
293 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
294 const size_t size = rhs.smallSize();
296 ml_.capacity_ = rhs.ml_.capacity_;
299 // Just write the whole thing, don't look at details. In
300 // particular we need to copy capacity anyway because we want
301 // to set the size (don't forget that the last character,
302 // which stores a short string's length, is shared with the
303 // ml_.capacity field).
306 assert(category() == isSmall && this->size() == rhs.size());
307 } else if (rhs.category() == isLarge) {
308 // Large strings are just refcounted
310 RefCounted::incrementRefs(ml_.data_);
311 assert(category() == isLarge && size() == rhs.size());
313 // Medium strings are copied eagerly. Don't forget to allocate
314 // one extra Char for the null terminator.
315 auto const allocSize =
316 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
317 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
318 fbstring_detail::pod_copy(rhs.ml_.data_,
320 rhs.ml_.data_ + rhs.ml_.size_ + 1,
322 // No need for writeTerminator() here, we copied one extra
323 // element just above.
324 ml_.size_ = rhs.ml_.size_;
325 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
326 assert(category() == isMedium);
328 assert(size() == rhs.size());
329 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
332 fbstring_core(fbstring_core&& goner) {
333 if (goner.category() == isSmall) {
334 // Just copy, leave the goner in peace
335 new(this) fbstring_core(goner.small_, goner.smallSize());
339 // Clean goner's carcass
340 goner.setSmallSize(0);
344 fbstring_core(const Char *const data, const size_t size) {
345 // Simplest case first: small strings are bitblitted
346 if (size <= maxSmallSize) {
347 // Layout is: Char* data_, size_t size_, size_t capacity_
348 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
349 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
350 // sizeof(size_t) must be a power of 2
351 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
353 // If data is aligned, use fast word-wise copying. Otherwise,
354 // use conservative memcpy.
355 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
356 fbstring_detail::pod_copy(data, data + size, small_);
358 // Copy one word (64 bits) at a time
359 const size_t byteSize = size * sizeof(Char);
360 if (byteSize > 2 * sizeof(size_t)) {
362 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
364 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
366 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
367 } else if (byteSize > sizeof(size_t)) {
370 } else if (size > 0) {
376 } else if (size <= maxMediumSize) {
377 // Medium strings are allocated normally. Don't forget to
378 // allocate one extra Char for the terminating null.
379 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
380 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
381 fbstring_detail::pod_copy(data, data + size, ml_.data_);
383 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
385 // Large strings are allocated differently
386 size_t effectiveCapacity = size;
387 auto const newRC = RefCounted::create(data, & effectiveCapacity);
388 ml_.data_ = newRC->data_;
390 ml_.capacity_ = effectiveCapacity | isLarge;
393 assert(this->size() == size);
394 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
398 auto const c = category();
406 RefCounted::decrementRefs(ml_.data_);
409 // Snatches a previously mallocated string. The parameter "size"
410 // is the size of the string, and the parameter "capacity" is the size
411 // of the mallocated block. The string must be \0-terminated, so
412 // data[size] == '\0' and capacity >= size + 1.
414 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
415 // "size", and pass 3 as "capacity".
416 fbstring_core(Char *const data, const size_t size,
417 const size_t capacity,
418 AcquireMallocatedString) {
420 assert(capacity > size);
421 assert(data[size] == '\0');
422 // Use the medium string storage
425 ml_.capacity_ = capacity | isMedium;
427 // No need for the memory
433 // swap below doesn't test whether &rhs == this (and instead
434 // potentially does extra work) on the premise that the rarity of
435 // that situation actually makes the check more expensive than is
437 void swap(fbstring_core & rhs) {
443 // In C++11 data() and c_str() are 100% equivalent.
444 const Char * data() const {
448 Char * mutable_data() {
449 auto const c = category();
453 assert(c == isMedium || c == isLarge);
454 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
456 size_t effectiveCapacity = ml_.capacity();
457 auto const newRC = RefCounted::create(& effectiveCapacity);
458 // If this fails, someone placed the wrong capacity in an
460 assert(effectiveCapacity >= ml_.capacity());
461 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
463 RefCounted::decrementRefs(ml_.data_);
464 ml_.data_ = newRC->data_;
465 // No need to call writeTerminator(), we have + 1 above.
470 const Char * c_str() const {
471 auto const c = category();
472 #ifdef FBSTRING_PERVERSE
474 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
475 || small_[smallSize()] == '\0');
476 small_[smallSize()] = '\0';
479 assert(c == isMedium || c == isLarge);
480 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
481 ml_.data_[ml_.size_] = '\0';
482 #elif defined(FBSTRING_CONSERVATIVE)
484 assert(small_[smallSize()] == '\0');
487 assert(c == isMedium || c == isLarge);
488 assert(ml_.data_[ml_.size_] == '\0');
491 small_[smallSize()] = '\0';
494 assert(c == isMedium || c == isLarge);
495 ml_.data_[ml_.size_] = '\0';
500 void shrink(const size_t delta) {
501 if (category() == isSmall) {
502 // Check for underflow
503 assert(delta <= smallSize());
504 setSmallSize(smallSize() - delta);
505 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
506 // Medium strings and unique large strings need no special
508 assert(ml_.size_ >= delta);
511 assert(ml_.size_ >= delta);
512 // Shared large string, must make unique. This is because of the
513 // durn terminator must be written, which may trample the shared
516 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
518 // No need to write the terminator.
524 void reserve(size_t minCapacity) {
525 if (category() == isLarge) {
527 if (RefCounted::refs(ml_.data_) > 1) {
528 // We must make it unique regardless; in-place reallocation is
529 // useless if the string is shared. In order to not surprise
530 // people, reserve the new block at current capacity or
531 // more. That way, a string's capacity never shrinks after a
533 minCapacity = std::max(minCapacity, ml_.capacity());
534 auto const newRC = RefCounted::create(& minCapacity);
535 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
537 // Done with the old data. No need to call writeTerminator(),
538 // we have + 1 above.
539 RefCounted::decrementRefs(ml_.data_);
540 ml_.data_ = newRC->data_;
541 ml_.capacity_ = minCapacity | isLarge;
542 // size remains unchanged
544 // String is not shared, so let's try to realloc (if needed)
545 if (minCapacity > ml_.capacity()) {
546 // Asking for more memory
548 RefCounted::reallocate(ml_.data_, ml_.size_,
549 ml_.capacity(), minCapacity);
550 ml_.data_ = newRC->data_;
551 ml_.capacity_ = minCapacity | isLarge;
554 assert(capacity() >= minCapacity);
556 } else if (category() == isMedium) {
557 // String is not shared
558 if (minCapacity <= ml_.capacity()) {
559 return; // nothing to do, there's enough room
561 if (minCapacity <= maxMediumSize) {
562 // Keep the string at medium size. Don't forget to allocate
563 // one extra Char for the terminating null.
564 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
565 ml_.data_ = static_cast<Char *>(
568 ml_.size_ * sizeof(Char),
569 ml_.capacity() * sizeof(Char),
572 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
574 // Conversion from medium to large string
575 fbstring_core nascent;
576 // Will recurse to another branch of this function
577 nascent.reserve(minCapacity);
578 nascent.ml_.size_ = ml_.size_;
579 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
583 assert(capacity() >= minCapacity);
586 assert(category() == isSmall);
587 if (minCapacity > maxMediumSize) {
589 auto const newRC = RefCounted::create(& minCapacity);
590 auto const size = smallSize();
591 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
592 // No need for writeTerminator(), we wrote it above with + 1.
593 ml_.data_ = newRC->data_;
595 ml_.capacity_ = minCapacity | isLarge;
596 assert(capacity() >= minCapacity);
597 } else if (minCapacity > maxSmallSize) {
599 // Don't forget to allocate one extra Char for the terminating null
600 auto const allocSizeBytes =
601 goodMallocSize((1 + minCapacity) * sizeof(Char));
602 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
603 auto const size = smallSize();
604 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
605 // No need for writeTerminator(), we wrote it above with + 1.
608 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
611 // Nothing to do, everything stays put
614 assert(capacity() >= minCapacity);
617 Char * expand_noinit(const size_t delta) {
618 // Strategy is simple: make room, then change size
619 assert(capacity() >= size());
621 if (category() == isSmall) {
624 if (newSz <= maxSmallSize) {
632 newSz = ml_.size_ + delta;
633 if (newSz > capacity()) {
637 assert(capacity() >= newSz);
638 // Category can't be small - we took care of that above
639 assert(category() == isMedium || category() == isLarge);
642 assert(size() == newSz);
643 return ml_.data_ + sz;
646 void push_back(Char c) {
647 assert(capacity() >= size());
649 if (category() == isSmall) {
651 if (sz < maxSmallSize) {
652 setSmallSize(sz + 1);
657 reserve(maxSmallSize * 2);
660 if (sz == capacity()) { // always true for isShared()
661 reserve(sz * 3 / 2); // ensures not shared
665 assert(capacity() >= sz + 1);
666 // Category can't be small - we took care of that above
667 assert(category() == isMedium || category() == isLarge);
673 size_t size() const {
674 return category() == isSmall ? smallSize() : ml_.size_;
677 size_t capacity() const {
678 switch (category()) {
682 // For large-sized strings, a multi-referenced chunk has no
683 // available capacity. This is because any attempt to append
684 // data would trigger a new allocation.
685 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
688 return ml_.capacity();
691 bool isShared() const {
692 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
695 #ifdef FBSTRING_PERVERSE
696 enum { TERMINATOR = '^' };
698 enum { TERMINATOR = '\0' };
701 void writeTerminator() {
702 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
703 if (category() == isSmall) {
704 const auto s = smallSize();
705 if (s != maxSmallSize) {
706 small_[s] = TERMINATOR;
709 ml_.data_[ml_.size_] = TERMINATOR;
716 fbstring_core & operator=(const fbstring_core & rhs);
723 size_t capacity() const {
724 return capacity_ & capacityExtractMask;
729 std::atomic<size_t> refCount_;
732 static RefCounted * fromData(Char * p) {
733 return static_cast<RefCounted*>(
735 static_cast<unsigned char*>(static_cast<void*>(p))
736 - sizeof(refCount_)));
739 static size_t refs(Char * p) {
740 return fromData(p)->refCount_.load(std::memory_order_acquire);
743 static void incrementRefs(Char * p) {
744 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
747 static void decrementRefs(Char * p) {
748 auto const dis = fromData(p);
749 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
756 static RefCounted * create(size_t * size) {
757 // Don't forget to allocate one extra Char for the terminating
758 // null. In this case, however, one Char is already part of the
760 const size_t allocSize = goodMallocSize(
761 sizeof(RefCounted) + *size * sizeof(Char));
762 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
763 result->refCount_.store(1, std::memory_order_release);
764 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
768 static RefCounted * create(const Char * data, size_t * size) {
769 const size_t effectiveSize = *size;
770 auto result = create(size);
771 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
775 static RefCounted * reallocate(Char *const data,
776 const size_t currentSize,
777 const size_t currentCapacity,
778 const size_t newCapacity) {
779 assert(newCapacity > 0 && newCapacity > currentSize);
780 auto const dis = fromData(data);
781 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
782 // Don't forget to allocate one extra Char for the terminating
783 // null. In this case, however, one Char is already part of the
785 auto result = static_cast<RefCounted*>(
787 sizeof(RefCounted) + currentSize * sizeof(Char),
788 sizeof(RefCounted) + currentCapacity * sizeof(Char),
789 sizeof(RefCounted) + newCapacity * sizeof(Char)));
790 assert(result->refCount_.load(std::memory_order_acquire) == 1);
796 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
797 mutable MediumLarge ml_;
801 lastChar = sizeof(MediumLarge) - 1,
802 maxSmallSize = lastChar / sizeof(Char),
803 maxMediumSize = 254 / sizeof(Char), // coincides with the small
804 // bin size in dlmalloc
805 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
806 capacityExtractMask = ~categoryExtractMask,
808 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
809 "Corrupt memory layout for fbstring.");
813 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
814 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
817 Category category() const {
818 // Assumes little endian
819 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
822 size_t smallSize() const {
823 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
824 return static_cast<size_t>(maxSmallSize)
825 - static_cast<size_t>(small_[maxSmallSize]);
828 void setSmallSize(size_t s) {
829 // Warning: this should work with uninitialized strings too,
830 // so don't assume anything about the previous value of
831 // small_[maxSmallSize].
832 assert(s <= maxSmallSize);
833 small_[maxSmallSize] = maxSmallSize - s;
837 # pragma GCC diagnostic pop
839 #ifndef _LIBSTDCXX_FBSTRING
841 * Dummy fbstring core that uses an actual std::string. This doesn't
842 * make any sense - it's just for testing purposes.
844 template <class Char>
845 class dummy_fbstring_core {
847 dummy_fbstring_core() {
849 dummy_fbstring_core(const dummy_fbstring_core& another)
850 : backend_(another.backend_) {
852 dummy_fbstring_core(const Char * s, size_t n)
855 void swap(dummy_fbstring_core & rhs) {
856 backend_.swap(rhs.backend_);
858 const Char * data() const {
859 return backend_.data();
861 Char * mutable_data() {
862 //assert(!backend_.empty());
863 return &*backend_.begin();
865 void shrink(size_t delta) {
866 assert(delta <= size());
867 backend_.resize(size() - delta);
869 Char * expand_noinit(size_t delta) {
870 auto const sz = size();
871 backend_.resize(size() + delta);
872 return backend_.data() + sz;
874 void push_back(Char c) {
875 backend_.push_back(c);
877 size_t size() const {
878 return backend_.size();
880 size_t capacity() const {
881 return backend_.capacity();
883 bool isShared() const {
886 void reserve(size_t minCapacity) {
887 backend_.reserve(minCapacity);
891 std::basic_string<Char> backend_;
893 #endif // !_LIBSTDCXX_FBSTRING
896 * This is the basic_string replacement. For conformity,
897 * basic_fbstring takes the same template parameters, plus the last
898 * one which is the core.
900 #ifdef _LIBSTDCXX_FBSTRING
901 template <typename E, class T, class A, class Storage>
903 template <typename E,
904 class T = std::char_traits<E>,
905 class A = std::allocator<E>,
906 class Storage = fbstring_core<E> >
908 class basic_fbstring {
912 void (*throw_exc)(const char*),
914 if (!condition) throw_exc(msg);
917 bool isSane() const {
920 empty() == (size() == 0) &&
921 empty() == (begin() == end()) &&
922 size() <= max_size() &&
923 capacity() <= max_size() &&
924 size() <= capacity() &&
925 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
929 friend struct Invariant;
932 explicit Invariant(const basic_fbstring& s) : s_(s) {
939 const basic_fbstring& s_;
941 explicit Invariant(const basic_fbstring&) {}
943 Invariant& operator=(const Invariant&);
948 typedef T traits_type;
949 typedef typename traits_type::char_type value_type;
950 typedef A allocator_type;
951 typedef typename A::size_type size_type;
952 typedef typename A::difference_type difference_type;
954 typedef typename A::reference reference;
955 typedef typename A::const_reference const_reference;
956 typedef typename A::pointer pointer;
957 typedef typename A::const_pointer const_pointer;
960 typedef const E* const_iterator;
961 typedef std::reverse_iterator<iterator
962 #ifdef NO_ITERATOR_TRAITS
966 typedef std::reverse_iterator<const_iterator
967 #ifdef NO_ITERATOR_TRAITS
970 > const_reverse_iterator;
972 static const size_type npos; // = size_type(-1)
975 static void procrustes(size_type& n, size_type nmax) {
976 if (n > nmax) n = nmax;
980 // 21.3.1 construct/copy/destroy
981 explicit basic_fbstring(const A& a = A()) {
984 basic_fbstring(const basic_fbstring& str)
985 : store_(str.store_) {
989 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
992 #ifndef _LIBSTDCXX_FBSTRING
993 // This is defined for compatibility with std::string
994 /* implicit */ basic_fbstring(const std::string& str)
995 : store_(str.data(), str.size()) {
999 basic_fbstring(const basic_fbstring& str, size_type pos,
1000 size_type n = npos, const A& a = A()) {
1001 assign(str, pos, n);
1004 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1005 : store_(s, s ? traits_type::length(s) : ({
1006 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1007 err += ": null pointer initializer not valid";
1008 std::__throw_logic_error(err.c_str());
1013 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1017 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1018 auto const data = store_.expand_noinit(n);
1019 fbstring_detail::pod_fill(data, data + n, c);
1020 store_.writeTerminator();
1023 template <class InIt>
1024 basic_fbstring(InIt begin, InIt end,
1025 typename std::enable_if<
1026 !std::is_same<typename std::remove_const<InIt>::type,
1027 value_type*>::value, const A>::type & a = A()) {
1031 // Specialization for const char*, const char*
1032 basic_fbstring(const value_type* b, const value_type* e)
1033 : store_(b, e - b) {
1036 // Nonstandard constructor
1037 basic_fbstring(value_type *s, size_type n, size_type c,
1038 AcquireMallocatedString a)
1039 : store_(s, n, c, a) {
1045 basic_fbstring& operator=(const basic_fbstring & lhs) {
1049 auto const oldSize = size();
1050 auto const srcSize = lhs.size();
1051 if (capacity() >= srcSize && !store_.isShared()) {
1052 // great, just copy the contents
1053 if (oldSize < srcSize)
1054 store_.expand_noinit(srcSize - oldSize);
1056 store_.shrink(oldSize - srcSize);
1057 assert(size() == srcSize);
1058 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1059 store_.writeTerminator();
1061 // need to reallocate, so we may as well create a brand new string
1062 basic_fbstring(lhs).swap(*this);
1068 basic_fbstring& operator=(basic_fbstring&& goner) {
1069 // No need of this anymore
1070 this->~basic_fbstring();
1071 // Move the goner into this
1072 new(&store_) fbstring_core<E>(std::move(goner.store_));
1076 #ifndef _LIBSTDCXX_FBSTRING
1077 // Compatibility with std::string
1078 basic_fbstring & operator=(const std::string & rhs) {
1079 return assign(rhs.data(), rhs.size());
1082 // Compatibility with std::string
1083 std::string toStdString() const {
1084 return std::string(data(), size());
1087 // A lot of code in fbcode still uses this method, so keep it here for now.
1088 const basic_fbstring& toStdString() const {
1093 basic_fbstring& operator=(const value_type* s) {
1097 basic_fbstring& operator=(value_type c) {
1099 store_.expand_noinit(1);
1100 } else if (store_.isShared()) {
1101 basic_fbstring(1, c).swap(*this);
1104 store_.shrink(size() - 1);
1106 *store_.mutable_data() = c;
1107 store_.writeTerminator();
1111 // 21.3.2 iterators:
1112 iterator begin() { return store_.mutable_data(); }
1114 const_iterator begin() const { return store_.data(); }
1117 return store_.mutable_data() + store_.size();
1120 const_iterator end() const {
1121 return store_.data() + store_.size();
1124 reverse_iterator rbegin() {
1125 return reverse_iterator(end());
1128 const_reverse_iterator rbegin() const {
1129 return const_reverse_iterator(end());
1132 reverse_iterator rend() {
1133 return reverse_iterator(begin());
1136 const_reverse_iterator rend() const {
1137 return const_reverse_iterator(begin());
1141 // C++11 21.4.5, element access:
1142 const value_type& front() const { return *begin(); }
1143 const value_type& back() const {
1145 // Should be begin()[size() - 1], but that branches twice
1146 return *(end() - 1);
1148 value_type& front() { return *begin(); }
1149 value_type& back() {
1151 // Should be begin()[size() - 1], but that branches twice
1152 return *(end() - 1);
1160 size_type size() const { return store_.size(); }
1162 size_type length() const { return size(); }
1164 size_type max_size() const {
1165 return std::numeric_limits<size_type>::max();
1168 void resize(const size_type n, const value_type c = value_type()) {
1169 auto size = this->size();
1171 store_.shrink(size - n);
1173 // Do this in two steps to minimize slack memory copied (see
1175 auto const capacity = this->capacity();
1176 assert(capacity >= size);
1177 if (size < capacity) {
1178 auto delta = std::min(n, capacity) - size;
1179 store_.expand_noinit(delta);
1180 fbstring_detail::pod_fill(begin() + size, end(), c);
1183 store_.writeTerminator();
1188 auto const delta = n - size;
1189 store_.expand_noinit(delta);
1190 fbstring_detail::pod_fill(end() - delta, end(), c);
1191 store_.writeTerminator();
1193 assert(this->size() == n);
1196 size_type capacity() const { return store_.capacity(); }
1198 void reserve(size_type res_arg = 0) {
1199 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1200 store_.reserve(res_arg);
1203 void clear() { resize(0); }
1205 bool empty() const { return size() == 0; }
1207 // 21.3.4 element access:
1208 const_reference operator[](size_type pos) const {
1209 return *(c_str() + pos);
1212 reference operator[](size_type pos) {
1213 if (pos == size()) {
1214 // Just call c_str() to make sure '\0' is present
1217 return *(begin() + pos);
1220 const_reference at(size_type n) const {
1221 enforce(n <= size(), std::__throw_out_of_range, "");
1225 reference at(size_type n) {
1226 enforce(n < size(), std::__throw_out_of_range, "");
1230 // 21.3.5 modifiers:
1231 basic_fbstring& operator+=(const basic_fbstring& str) {
1235 basic_fbstring& operator+=(const value_type* s) {
1239 basic_fbstring& operator+=(const value_type c) {
1244 basic_fbstring& append(const basic_fbstring& str) {
1246 auto desiredSize = size() + str.size();
1248 append(str.data(), str.size());
1249 assert(size() == desiredSize);
1253 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1255 const size_type sz = str.size();
1256 enforce(pos <= sz, std::__throw_out_of_range, "");
1257 procrustes(n, sz - pos);
1258 return append(str.data() + pos, n);
1261 basic_fbstring& append(const value_type* s, size_type n) {
1263 Invariant checker(*this);
1266 if (FBSTRING_UNLIKELY(!n)) {
1267 // Unlikely but must be done
1270 auto const oldSize = size();
1271 auto const oldData = data();
1272 // Check for aliasing (rare). We could use "<=" here but in theory
1273 // those do not work for pointers unless the pointers point to
1274 // elements in the same array. For that reason we use
1275 // std::less_equal, which is guaranteed to offer a total order
1276 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1278 std::less_equal<const value_type*> le;
1279 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1280 assert(le(s + n, oldData + oldSize));
1281 const size_type offset = s - oldData;
1282 store_.reserve(oldSize + n);
1283 // Restore the source
1284 s = data() + offset;
1286 // Warning! Repeated appends with short strings may actually incur
1287 // practically quadratic performance. Avoid that by pushing back
1288 // the first character (which ensures exponential growth) and then
1289 // appending the rest normally. Worst case the append may incur a
1290 // second allocation but that will be rare.
1293 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1294 assert(size() == oldSize + n + 1);
1298 basic_fbstring& append(const value_type* s) {
1299 return append(s, traits_type::length(s));
1302 basic_fbstring& append(size_type n, value_type c) {
1303 resize(size() + n, c);
1307 template<class InputIterator>
1308 basic_fbstring& append(InputIterator first, InputIterator last) {
1309 insert(end(), first, last);
1313 void push_back(const value_type c) { // primitive
1314 store_.push_back(c);
1317 basic_fbstring& assign(const basic_fbstring& str) {
1318 if (&str == this) return *this;
1319 return assign(str.data(), str.size());
1322 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1324 const size_type sz = str.size();
1325 enforce(pos <= sz, std::__throw_out_of_range, "");
1326 procrustes(n, sz - pos);
1327 return assign(str.data() + pos, n);
1330 basic_fbstring& assign(const value_type* s, const size_type n) {
1331 Invariant checker(*this);
1334 std::copy(s, s + n, begin());
1336 assert(size() == n);
1338 const value_type *const s2 = s + size();
1339 std::copy(s, s2, begin());
1340 append(s2, n - size());
1341 assert(size() == n);
1343 store_.writeTerminator();
1344 assert(size() == n);
1348 basic_fbstring& assign(const value_type* s) {
1349 return assign(s, traits_type::length(s));
1352 template <class ItOrLength, class ItOrChar>
1353 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1354 return replace(begin(), end(), first_or_n, last_or_c);
1357 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1358 return insert(pos1, str.data(), str.size());
1361 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1362 size_type pos2, size_type n) {
1363 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1364 procrustes(n, str.length() - pos2);
1365 return insert(pos1, str.data() + pos2, n);
1368 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1369 enforce(pos <= length(), std::__throw_out_of_range, "");
1370 insert(begin() + pos, s, s + n);
1374 basic_fbstring& insert(size_type pos, const value_type* s) {
1375 return insert(pos, s, traits_type::length(s));
1378 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1379 enforce(pos <= length(), std::__throw_out_of_range, "");
1380 insert(begin() + pos, n, c);
1384 iterator insert(const iterator p, const value_type c) {
1385 const size_type pos = p - begin();
1387 return begin() + pos;
1391 template <int i> class Selector {};
1393 basic_fbstring& insertImplDiscr(iterator p,
1394 size_type n, value_type c, Selector<1>) {
1395 Invariant checker(*this);
1397 assert(p >= begin() && p <= end());
1398 if (capacity() - size() < n) {
1399 const size_type sz = p - begin();
1400 reserve(size() + n);
1403 const iterator oldEnd = end();
1404 if( n < size_type(oldEnd - p)) {
1405 append(oldEnd - n, oldEnd);
1407 // reverse_iterator(oldEnd - n),
1408 // reverse_iterator(p),
1409 // reverse_iterator(oldEnd));
1410 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1411 std::fill(p, p + n, c);
1413 append(n - (end() - p), c);
1415 std::fill(p, oldEnd, c);
1417 store_.writeTerminator();
1421 template<class InputIter>
1422 basic_fbstring& insertImplDiscr(iterator i,
1423 InputIter b, InputIter e, Selector<0>) {
1425 typename std::iterator_traits<InputIter>::iterator_category());
1429 template <class FwdIterator>
1430 void insertImpl(iterator i,
1431 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1432 Invariant checker(*this);
1434 const size_type pos = i - begin();
1435 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1436 std::distance(s1, s2);
1438 using namespace fbstring_detail;
1439 assert(pos <= size());
1441 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1442 capacity() - size();
1444 // realloc the string
1445 reserve(size() + n2);
1448 if (pos + n2 <= size()) {
1449 const iterator tailBegin = end() - n2;
1450 store_.expand_noinit(n2);
1451 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1452 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1453 reverse_iterator(tailBegin + n2));
1454 std::copy(s1, s2, i);
1457 const size_type old_size = size();
1458 std::advance(t, old_size - pos);
1459 const size_t newElems = std::distance(t, s2);
1460 store_.expand_noinit(n2);
1461 std::copy(t, s2, begin() + old_size);
1462 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1463 begin() + old_size + newElems);
1464 std::copy(s1, t, i);
1466 store_.writeTerminator();
1469 template <class InputIterator>
1470 void insertImpl(iterator i,
1471 InputIterator b, InputIterator e, std::input_iterator_tag) {
1472 basic_fbstring temp(begin(), i);
1473 for (; b != e; ++b) {
1476 temp.append(i, end());
1481 template <class ItOrLength, class ItOrChar>
1482 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1483 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1484 insertImplDiscr(p, first_or_n, last_or_c, sel);
1487 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1488 Invariant checker(*this);
1490 enforce(pos <= length(), std::__throw_out_of_range, "");
1491 procrustes(n, length() - pos);
1492 std::copy(begin() + pos + n, end(), begin() + pos);
1493 resize(length() - n);
1497 iterator erase(iterator position) {
1498 const size_type pos(position - begin());
1499 enforce(pos <= size(), std::__throw_out_of_range, "");
1501 return begin() + pos;
1504 iterator erase(iterator first, iterator last) {
1505 const size_type pos(first - begin());
1506 erase(pos, last - first);
1507 return begin() + pos;
1510 // Replaces at most n1 chars of *this, starting with pos1 with the
1512 basic_fbstring& replace(size_type pos1, size_type n1,
1513 const basic_fbstring& str) {
1514 return replace(pos1, n1, str.data(), str.size());
1517 // Replaces at most n1 chars of *this, starting with pos1,
1518 // with at most n2 chars of str starting with pos2
1519 basic_fbstring& replace(size_type pos1, size_type n1,
1520 const basic_fbstring& str,
1521 size_type pos2, size_type n2) {
1522 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1523 return replace(pos1, n1, str.data() + pos2,
1524 std::min(n2, str.size() - pos2));
1527 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1528 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1529 return replace(pos, n1, s, traits_type::length(s));
1532 // Replaces at most n1 chars of *this, starting with pos, with n2
1535 // consolidated with
1537 // Replaces at most n1 chars of *this, starting with pos, with at
1538 // most n2 chars of str. str must have at least n2 chars.
1539 template <class StrOrLength, class NumOrChar>
1540 basic_fbstring& replace(size_type pos, size_type n1,
1541 StrOrLength s_or_n2, NumOrChar n_or_c) {
1542 Invariant checker(*this);
1544 enforce(pos <= size(), std::__throw_out_of_range, "");
1545 procrustes(n1, length() - pos);
1546 const iterator b = begin() + pos;
1547 return replace(b, b + n1, s_or_n2, n_or_c);
1550 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1551 return replace(i1, i2, str.data(), str.length());
1554 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1555 return replace(i1, i2, s, traits_type::length(s));
1559 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1560 const value_type* s, size_type n,
1563 assert(begin() <= i1 && i1 <= end());
1564 assert(begin() <= i2 && i2 <= end());
1565 return replace(i1, i2, s, s + n);
1568 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1569 size_type n2, value_type c, Selector<1>) {
1570 const size_type n1 = i2 - i1;
1572 std::fill(i1, i1 + n2, c);
1575 std::fill(i1, i2, c);
1576 insert(i2, n2 - n1, c);
1582 template <class InputIter>
1583 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1584 InputIter b, InputIter e,
1586 replaceImpl(i1, i2, b, e,
1587 typename std::iterator_traits<InputIter>::iterator_category());
1592 template <class FwdIterator, class P>
1593 bool replaceAliased(iterator i1, iterator i2,
1594 FwdIterator s1, FwdIterator s2, P*) {
1598 template <class FwdIterator>
1599 bool replaceAliased(iterator i1, iterator i2,
1600 FwdIterator s1, FwdIterator s2, value_type*) {
1601 static const std::less_equal<const value_type*> le =
1602 std::less_equal<const value_type*>();
1603 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1607 // Aliased replace, copy to new string
1608 basic_fbstring temp;
1609 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1610 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1616 template <class FwdIterator>
1617 void replaceImpl(iterator i1, iterator i2,
1618 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1619 Invariant checker(*this);
1622 // Handle aliased replace
1623 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1627 auto const n1 = i2 - i1;
1629 auto const n2 = std::distance(s1, s2);
1634 std::copy(s1, s2, i1);
1638 fbstring_detail::copy_n(s1, n1, i1);
1639 std::advance(s1, n1);
1645 template <class InputIterator>
1646 void replaceImpl(iterator i1, iterator i2,
1647 InputIterator b, InputIterator e, std::input_iterator_tag) {
1648 basic_fbstring temp(begin(), i1);
1649 temp.append(b, e).append(i2, end());
1654 template <class T1, class T2>
1655 basic_fbstring& replace(iterator i1, iterator i2,
1656 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1658 num1 = std::numeric_limits<T1>::is_specialized,
1659 num2 = std::numeric_limits<T2>::is_specialized;
1660 return replaceImplDiscr(
1661 i1, i2, first_or_n_or_s, last_or_c_or_n,
1662 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1665 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1666 enforce(pos <= size(), std::__throw_out_of_range, "");
1667 procrustes(n, size() - pos);
1669 fbstring_detail::pod_copy(
1676 void swap(basic_fbstring& rhs) {
1677 store_.swap(rhs.store_);
1680 // 21.3.6 string operations:
1681 const value_type* c_str() const {
1682 return store_.c_str();
1685 const value_type* data() const { return c_str(); }
1687 allocator_type get_allocator() const {
1688 return allocator_type();
1691 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1692 return find(str.data(), pos, str.length());
1695 size_type find(const value_type* needle, const size_type pos,
1696 const size_type nsize) const {
1697 if (!nsize) return pos;
1698 auto const size = this->size();
1699 if (nsize + pos > size) return npos;
1700 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1701 // the last characters first
1702 auto const haystack = data();
1703 auto const nsize_1 = nsize - 1;
1704 auto const lastNeedle = needle[nsize_1];
1706 // Boyer-Moore skip value for the last char in the needle. Zero is
1707 // not a valid value; skip will be computed the first time it's
1711 const E * i = haystack + pos;
1712 auto iEnd = haystack + size - nsize_1;
1715 // Boyer-Moore: match the last element in the needle
1716 while (i[nsize_1] != lastNeedle) {
1722 // Here we know that the last char matches
1723 // Continue in pedestrian mode
1724 for (size_t j = 0; ; ) {
1726 if (i[j] != needle[j]) {
1727 // Not found, we can skip
1728 // Compute the skip value lazily
1731 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1738 // Check if done searching
1741 return i - haystack;
1748 size_type find(const value_type* s, size_type pos = 0) const {
1749 return find(s, pos, traits_type::length(s));
1752 size_type find (value_type c, size_type pos = 0) const {
1753 return find(&c, pos, 1);
1756 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1757 return rfind(str.data(), pos, str.length());
1760 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1761 if (n > length()) return npos;
1762 pos = std::min(pos, length() - n);
1763 if (n == 0) return pos;
1765 const_iterator i(begin() + pos);
1767 if (traits_type::eq(*i, *s)
1768 && traits_type::compare(&*i, s, n) == 0) {
1771 if (i == begin()) break;
1776 size_type rfind(const value_type* s, size_type pos = npos) const {
1777 return rfind(s, pos, traits_type::length(s));
1780 size_type rfind(value_type c, size_type pos = npos) const {
1781 return rfind(&c, pos, 1);
1784 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1785 return find_first_of(str.data(), pos, str.length());
1788 size_type find_first_of(const value_type* s,
1789 size_type pos, size_type n) const {
1790 if (pos > length() || n == 0) return npos;
1791 const_iterator i(begin() + pos),
1793 for (; i != finish; ++i) {
1794 if (traits_type::find(s, n, *i) != 0) {
1801 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1802 return find_first_of(s, pos, traits_type::length(s));
1805 size_type find_first_of(value_type c, size_type pos = 0) const {
1806 return find_first_of(&c, pos, 1);
1809 size_type find_last_of (const basic_fbstring& str,
1810 size_type pos = npos) const {
1811 return find_last_of(str.data(), pos, str.length());
1814 size_type find_last_of (const value_type* s, size_type pos,
1815 size_type n) const {
1816 if (!empty() && n > 0) {
1817 pos = std::min(pos, length() - 1);
1818 const_iterator i(begin() + pos);
1820 if (traits_type::find(s, n, *i) != 0) {
1823 if (i == begin()) break;
1829 size_type find_last_of (const value_type* s,
1830 size_type pos = npos) const {
1831 return find_last_of(s, pos, traits_type::length(s));
1834 size_type find_last_of (value_type c, size_type pos = npos) const {
1835 return find_last_of(&c, pos, 1);
1838 size_type find_first_not_of(const basic_fbstring& str,
1839 size_type pos = 0) const {
1840 return find_first_not_of(str.data(), pos, str.size());
1843 size_type find_first_not_of(const value_type* s, size_type pos,
1844 size_type n) const {
1845 if (pos < length()) {
1849 for (; i != finish; ++i) {
1850 if (traits_type::find(s, n, *i) == 0) {
1858 size_type find_first_not_of(const value_type* s,
1859 size_type pos = 0) const {
1860 return find_first_not_of(s, pos, traits_type::length(s));
1863 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1864 return find_first_not_of(&c, pos, 1);
1867 size_type find_last_not_of(const basic_fbstring& str,
1868 size_type pos = npos) const {
1869 return find_last_not_of(str.data(), pos, str.length());
1872 size_type find_last_not_of(const value_type* s, size_type pos,
1873 size_type n) const {
1874 if (!this->empty()) {
1875 pos = std::min(pos, size() - 1);
1876 const_iterator i(begin() + pos);
1878 if (traits_type::find(s, n, *i) == 0) {
1881 if (i == begin()) break;
1887 size_type find_last_not_of(const value_type* s,
1888 size_type pos = npos) const {
1889 return find_last_not_of(s, pos, traits_type::length(s));
1892 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1893 return find_last_not_of(&c, pos, 1);
1896 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1897 enforce(pos <= size(), std::__throw_out_of_range, "");
1898 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1901 int compare(const basic_fbstring& str) const {
1902 // FIX due to Goncalo N M de Carvalho July 18, 2005
1903 return compare(0, size(), str);
1906 int compare(size_type pos1, size_type n1,
1907 const basic_fbstring& str) const {
1908 return compare(pos1, n1, str.data(), str.size());
1911 int compare(size_type pos1, size_type n1,
1912 const value_type* s) const {
1913 return compare(pos1, n1, s, traits_type::length(s));
1916 int compare(size_type pos1, size_type n1,
1917 const value_type* s, size_type n2) const {
1918 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1919 procrustes(n1, size() - pos1);
1920 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1921 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1922 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1925 int compare(size_type pos1, size_type n1,
1926 const basic_fbstring& str,
1927 size_type pos2, size_type n2) const {
1928 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1929 return compare(pos1, n1, str.data() + pos2,
1930 std::min(n2, str.size() - pos2));
1933 // Code from Jean-Francois Bastien (03/26/2007)
1934 int compare(const value_type* s) const {
1935 // Could forward to compare(0, size(), s, traits_type::length(s))
1936 // but that does two extra checks
1937 const size_type n1(size()), n2(traits_type::length(s));
1938 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1939 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1947 // non-member functions
1949 template <typename E, class T, class A, class S>
1951 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1952 const basic_fbstring<E, T, A, S>& rhs) {
1954 basic_fbstring<E, T, A, S> result;
1955 result.reserve(lhs.size() + rhs.size());
1956 result.append(lhs).append(rhs);
1957 return std::move(result);
1961 template <typename E, class T, class A, class S>
1963 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1964 const basic_fbstring<E, T, A, S>& rhs) {
1965 return std::move(lhs.append(rhs));
1969 template <typename E, class T, class A, class S>
1971 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1972 basic_fbstring<E, T, A, S>&& rhs) {
1973 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1974 // Good, at least we don't need to reallocate
1975 return std::move(rhs.insert(0, lhs));
1977 // Meh, no go. Forward to operator+(const&, const&).
1978 auto const& rhsC = rhs;
1983 template <typename E, class T, class A, class S>
1985 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1986 basic_fbstring<E, T, A, S>&& rhs) {
1987 return std::move(lhs.append(rhs));
1990 template <typename E, class T, class A, class S>
1992 basic_fbstring<E, T, A, S> operator+(
1993 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
1994 const basic_fbstring<E, T, A, S>& rhs) {
1996 basic_fbstring<E, T, A, S> result;
1997 const typename basic_fbstring<E, T, A, S>::size_type len =
1998 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
1999 result.reserve(len + rhs.size());
2000 result.append(lhs, len).append(rhs);
2004 template <typename E, class T, class A, class S>
2006 basic_fbstring<E, T, A, S> operator+(
2007 typename basic_fbstring<E, T, A, S>::value_type lhs,
2008 const basic_fbstring<E, T, A, S>& rhs) {
2010 basic_fbstring<E, T, A, S> result;
2011 result.reserve(1 + rhs.size());
2012 result.push_back(lhs);
2017 template <typename E, class T, class A, class S>
2019 basic_fbstring<E, T, A, S> operator+(
2020 const basic_fbstring<E, T, A, S>& lhs,
2021 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2023 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2024 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2026 basic_fbstring<E, T, A, S> result;
2027 const size_type len = traits_type::length(rhs);
2028 result.reserve(lhs.size() + len);
2029 result.append(lhs).append(rhs, len);
2033 template <typename E, class T, class A, class S>
2035 basic_fbstring<E, T, A, S> operator+(
2036 const basic_fbstring<E, T, A, S>& lhs,
2037 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2039 basic_fbstring<E, T, A, S> result;
2040 result.reserve(lhs.size() + 1);
2042 result.push_back(rhs);
2046 template <typename E, class T, class A, class S>
2048 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2049 const basic_fbstring<E, T, A, S>& rhs) {
2050 return lhs.compare(rhs) == 0; }
2052 template <typename E, class T, class A, class S>
2054 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2055 const basic_fbstring<E, T, A, S>& rhs) {
2056 return rhs == lhs; }
2058 template <typename E, class T, class A, class S>
2060 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2061 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2062 return lhs.compare(rhs) == 0; }
2064 template <typename E, class T, class A, class S>
2066 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2067 const basic_fbstring<E, T, A, S>& rhs) {
2068 return !(lhs == rhs); }
2070 template <typename E, class T, class A, class S>
2072 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2073 const basic_fbstring<E, T, A, S>& rhs) {
2074 return !(lhs == rhs); }
2076 template <typename E, class T, class A, class S>
2078 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2079 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2080 return !(lhs == rhs); }
2082 template <typename E, class T, class A, class S>
2084 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2085 const basic_fbstring<E, T, A, S>& rhs) {
2086 return lhs.compare(rhs) < 0; }
2088 template <typename E, class T, class A, class S>
2090 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2091 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2092 return lhs.compare(rhs) < 0; }
2094 template <typename E, class T, class A, class S>
2096 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2097 const basic_fbstring<E, T, A, S>& rhs) {
2098 return rhs.compare(lhs) > 0; }
2100 template <typename E, class T, class A, class S>
2102 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2103 const basic_fbstring<E, T, A, S>& rhs) {
2106 template <typename E, class T, class A, class S>
2108 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2109 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2112 template <typename E, class T, class A, class S>
2114 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2115 const basic_fbstring<E, T, A, S>& rhs) {
2118 template <typename E, class T, class A, class S>
2120 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2121 const basic_fbstring<E, T, A, S>& rhs) {
2122 return !(rhs < lhs); }
2124 template <typename E, class T, class A, class S>
2126 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2127 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2128 return !(rhs < lhs); }
2130 template <typename E, class T, class A, class S>
2132 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2133 const basic_fbstring<E, T, A, S>& rhs) {
2134 return !(rhs < lhs); }
2136 template <typename E, class T, class A, class S>
2138 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2139 const basic_fbstring<E, T, A, S>& rhs) {
2140 return !(lhs < rhs); }
2142 template <typename E, class T, class A, class S>
2144 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2145 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2146 return !(lhs < rhs); }
2148 template <typename E, class T, class A, class S>
2150 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2151 const basic_fbstring<E, T, A, S>& rhs) {
2152 return !(lhs < rhs);
2155 // subclause 21.3.7.8:
2156 template <typename E, class T, class A, class S>
2157 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2161 // TODO: make this faster.
2162 template <typename E, class T, class A, class S>
2165 typename basic_fbstring<E, T, A, S>::value_type,
2166 typename basic_fbstring<E, T, A, S>::traits_type>&
2168 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2169 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2170 basic_fbstring<E, T, A, S>& str) {
2171 typename std::basic_istream<E, T>::sentry sentry(is);
2172 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2173 typename basic_fbstring<E, T, A, S>::traits_type>
2175 typedef typename __istream_type::ios_base __ios_base;
2176 size_t extracted = 0;
2177 auto err = __ios_base::goodbit;
2179 auto n = is.width();
2184 auto got = is.rdbuf()->sgetc();
2185 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2186 // Whew. We get to store this guy
2188 got = is.rdbuf()->snextc();
2190 if (got == T::eof()) {
2191 err |= __ios_base::eofbit;
2196 err |= __ios_base::failbit;
2204 template <typename E, class T, class A, class S>
2206 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2207 typename basic_fbstring<E, T, A, S>::traits_type>&
2209 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2210 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2211 const basic_fbstring<E, T, A, S>& str) {
2212 os.write(str.data(), str.size());
2216 #ifndef _LIBSTDCXX_FBSTRING
2218 template <typename E, class T, class A, class S>
2220 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2221 typename basic_fbstring<E, T, A, S>::traits_type>&
2223 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2224 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2225 basic_fbstring<E, T, A, S>& str,
2226 typename basic_fbstring<E, T, A, S>::value_type delim) {
2227 // Use the nonstandard getdelim()
2231 // This looks quadratic but it really depends on realloc
2232 auto const newSize = size + 128;
2233 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2234 is.getline(buf + size, newSize - size, delim);
2235 if (is.bad() || is.eof() || !is.fail()) {
2236 // done by either failure, end of file, or normal read
2237 size += std::strlen(buf + size);
2240 // Here we have failed due to too short a buffer
2241 // Minus one to discount the terminating '\0'
2243 assert(buf[size] == 0);
2244 // Clear the error so we can continue reading
2247 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2248 AcquireMallocatedString());
2253 template <typename E, class T, class A, class S>
2255 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2256 typename basic_fbstring<E, T, A, S>::traits_type>&
2258 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2259 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2260 basic_fbstring<E, T, A, S>& str) {
2261 // Just forward to the version with a delimiter
2262 return getline(is, str, '\n');
2267 template <typename E1, class T, class A, class S>
2268 const typename basic_fbstring<E1, T, A, S>::size_type
2269 basic_fbstring<E1, T, A, S>::npos =
2270 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2272 #ifndef _LIBSTDCXX_FBSTRING
2273 // basic_string compatibility routines
2275 template <typename E, class T, class A, class S>
2277 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2278 const std::string& rhs) {
2279 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2282 template <typename E, class T, class A, class S>
2284 bool operator==(const std::string& lhs,
2285 const basic_fbstring<E, T, A, S>& rhs) {
2289 template <typename E, class T, class A, class S>
2291 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2292 const std::string& rhs) {
2293 return !(lhs == rhs);
2296 template <typename E, class T, class A, class S>
2298 bool operator!=(const std::string& lhs,
2299 const basic_fbstring<E, T, A, S>& rhs) {
2300 return !(lhs == rhs);
2303 #if !defined(_LIBSTDCXX_FBSTRING)
2304 typedef basic_fbstring<char> fbstring;
2307 // fbstring is relocatable
2308 template <class T, class R, class A, class S>
2309 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2312 _GLIBCXX_END_NAMESPACE_VERSION
2315 } // namespace folly
2317 #ifndef _LIBSTDCXX_FBSTRING
2321 struct hash< ::folly::fbstring> {
2322 size_t operator()(const ::folly::fbstring& s) const {
2323 return ::folly::hash::fnv32_buf(s.data(), s.size());
2328 #endif // _LIBSTDCXX_FBSTRING
2330 #undef FBSTRING_LIKELY
2331 #undef FBSTRING_UNLIKELY
2333 #endif // FOLLY_BASE_FBSTRING_H_