2 * Copyright 2012 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/Likely.h"
91 #include "folly/Malloc.h"
92 #include "folly/Hash.h"
98 #include <type_traits>
100 #ifdef _LIBSTDCXX_FBSTRING
101 namespace std _GLIBCXX_VISIBILITY(default) {
102 _GLIBCXX_BEGIN_NAMESPACE_VERSION
107 namespace fbstring_detail {
109 template <class InIt, class OutIt>
112 typename std::iterator_traits<InIt>::difference_type n,
114 for (; n != 0; --n, ++b, ++d) {
115 assert((const void*)&*d != &*b);
121 template <class Pod, class T>
122 inline void pod_fill(Pod* b, Pod* e, T c) {
123 assert(b && e && b <= e);
124 /*static*/ if (sizeof(T) == 1) {
127 auto const ee = b + ((e - b) & ~7u);
128 for (; b != ee; b += 8) {
139 for (; b != e; ++b) {
146 * Lightly structured memcpy, simplifies copying PODs and introduces
147 * some asserts. Unfortunately using this function may cause
148 * measurable overhead (presumably because it adjusts from a begin/end
149 * convention to a pointer/size convention, so it does some extra
150 * arithmetic even though the caller might have done the inverse
151 * adaptation outside).
154 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
156 assert(d >= e || d + (e - b) <= b);
157 memcpy(d, b, (e - b) * sizeof(Pod));
161 * Lightly structured memmove, simplifies copying PODs and introduces
165 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
167 memmove(d, b, (e - b) * sizeof(*b));
170 } // namespace fbstring_detail
173 * Defines a special acquisition method for constructing fbstring
174 * objects. AcquireMallocatedString means that the user passes a
175 * pointer to a malloc-allocated string that the fbstring object will
178 enum class AcquireMallocatedString {};
181 * fbstring_core_model is a mock-up type that defines all required
182 * signatures of a fbstring core. The fbstring class itself uses such
183 * a core object to implement all of the numerous member functions
184 * required by the standard.
186 * If you want to define a new core, copy the definition below and
187 * implement the primitives. Then plug the core into basic_fbstring as
188 * a template argument.
190 template <class Char>
191 class fbstring_core_model {
193 fbstring_core_model();
194 fbstring_core_model(const fbstring_core_model &);
195 ~fbstring_core_model();
196 // Returns a pointer to string's buffer (currently only contiguous
197 // strings are supported). The pointer is guaranteed to be valid
198 // until the next call to a non-const member function.
199 const Char * data() const;
200 // Much like data(), except the string is prepared to support
201 // character-level changes. This call is a signal for
202 // e.g. reference-counted implementation to fork the data. The
203 // pointer is guaranteed to be valid until the next call to a
204 // non-const member function.
205 Char * mutable_data();
206 // Returns a pointer to string's buffer and guarantees that a
207 // readable '\0' lies right after the buffer. The pointer is
208 // guaranteed to be valid until the next call to a non-const member
210 const Char * c_str() const;
211 // Shrinks the string by delta characters. Asserts that delta <=
213 void shrink(size_t delta);
214 // Expands the string by delta characters (i.e. after this call
215 // size() will report the old size() plus delta) but without
216 // initializing the expanded region. Returns a pointer to the memory
217 // to be initialized (the beginning of the expanded portion). The
218 // caller is expected to fill the expanded area appropriately.
219 Char* expand_noinit(size_t delta);
220 // Expands the string by one character and sets the last character
222 void push_back(Char c);
223 // Returns the string's size.
225 // Returns the string's capacity, i.e. maximum size that the string
226 // can grow to without reallocation. Note that for reference counted
227 // strings that's technically a lie - even assigning characters
228 // within the existing size would cause a reallocation.
229 size_t capacity() const;
230 // Returns true if the data underlying the string is actually shared
231 // across multiple strings (in a refcounted fashion).
232 bool isShared() const;
233 // Makes sure that at least minCapacity characters are available for
234 // the string without reallocation. For reference-counted strings,
235 // it should fork the data even if minCapacity < size().
236 void reserve(size_t minCapacity);
239 fbstring_core_model& operator=(const fbstring_core_model &);
244 * gcc-4.7 throws what appears to be some false positive uninitialized
245 * warnings for the members of the MediumLarge struct. So, mute them here.
247 # pragma GCC diagnostic push
248 # pragma GCC diagnostic ignored "-Wuninitialized"
251 * This is the core of the string. The code should work on 32- and
252 * 64-bit architectures and with any Char size. Porting to big endian
253 * architectures would require some changes.
255 * The storage is selected as follows (assuming we store one-byte
256 * characters on a 64-bit machine): (a) "small" strings between 0 and
257 * 23 chars are stored in-situ without allocation (the rightmost byte
258 * stores the size); (b) "medium" strings from 24 through 254 chars
259 * are stored in malloc-allocated memory that is copied eagerly; (c)
260 * "large" strings of 255 chars and above are stored in a similar
261 * structure as medium arrays, except that the string is
262 * reference-counted and copied lazily. the reference count is
263 * allocated right before the character array.
265 * The discriminator between these three strategies sits in the two
266 * most significant bits of the rightmost char of the storage. If
267 * neither is set, then the string is small (and its length sits in
268 * the lower-order bits of that rightmost character). If the MSb is
269 * set, the string is medium width. If the second MSb is set, then the
272 template <class Char> class fbstring_core {
275 // Only initialize the tag, will set the MSBs (i.e. the small
276 // string size) to zero too
277 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - 1));
278 // or: setSmallSize(0);
280 assert(category() == isSmall && size() == 0);
283 fbstring_core(const fbstring_core & rhs) {
284 assert(&rhs != this);
285 // Simplest case first: small strings are bitblitted
286 if (rhs.category() == isSmall) {
287 assert(offsetof(MediumLarge, data_) == 0);
288 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
289 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
290 const size_t size = rhs.smallSize();
292 ml_.capacity_ = rhs.ml_.capacity_;
295 // Just write the whole thing, don't look at details. In
296 // particular we need to copy capacity anyway because we want
297 // to set the size (don't forget that the last character,
298 // which stores a short string's length, is shared with the
299 // ml_.capacity field).
302 assert(category() == isSmall && this->size() == rhs.size());
303 } else if (rhs.category() == isLarge) {
304 // Large strings are just refcounted
306 RefCounted::incrementRefs(ml_.data_);
307 assert(category() == isLarge && size() == rhs.size());
309 // Medium strings are copied eagerly. Don't forget to allocate
310 // one extra Char for the null terminator.
311 auto const allocSize =
312 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
313 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
314 fbstring_detail::pod_copy(rhs.ml_.data_,
316 rhs.ml_.data_ + rhs.ml_.size_ + 1,
318 // No need for writeTerminator() here, we copied one extra
319 // element just above.
320 ml_.size_ = rhs.ml_.size_;
321 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
322 assert(category() == isMedium);
324 assert(size() == rhs.size());
325 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
328 fbstring_core(fbstring_core&& goner) {
329 if (goner.category() == isSmall) {
330 // Just copy, leave the goner in peace
331 new(this) fbstring_core(goner.small_, goner.smallSize());
335 // Clean goner's carcass
336 goner.setSmallSize(0);
340 fbstring_core(const Char *const data, const size_t size) {
341 // Simplest case first: small strings are bitblitted
342 if (size <= maxSmallSize) {
343 // Layout is: Char* data_, size_t size_, size_t capacity_
344 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
345 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
346 // sizeof(size_t) must be a power of 2
347 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
349 // If data is aligned, use fast word-wise copying. Otherwise,
350 // use conservative memcpy.
351 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
352 fbstring_detail::pod_copy(data, data + size, small_);
354 // Copy one word (64 bits) at a time
355 const size_t byteSize = size * sizeof(Char);
356 if (byteSize > 2 * sizeof(size_t)) {
358 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
360 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
362 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
363 } else if (byteSize > sizeof(size_t)) {
366 } else if (size > 0) {
372 } else if (size <= maxMediumSize) {
373 // Medium strings are allocated normally. Don't forget to
374 // allocate one extra Char for the terminating null.
375 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
376 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
377 fbstring_detail::pod_copy(data, data + size, ml_.data_);
379 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
381 // Large strings are allocated differently
382 size_t effectiveCapacity = size;
383 auto const newRC = RefCounted::create(data, & effectiveCapacity);
384 ml_.data_ = newRC->data_;
386 ml_.capacity_ = effectiveCapacity | isLarge;
389 assert(this->size() == size);
390 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
394 auto const c = category();
402 RefCounted::decrementRefs(ml_.data_);
405 // Snatches a previously mallocated string. The parameter "size"
406 // is the size of the string, and the parameter "capacity" is the size
407 // of the mallocated block. The string must be \0-terminated, so
408 // data[size] == '\0' and capacity >= size + 1.
410 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
411 // "size", and pass 3 as "capacity".
412 fbstring_core(Char *const data, const size_t size,
413 const size_t capacity,
414 AcquireMallocatedString) {
416 assert(capacity > size);
417 assert(data[size] == '\0');
418 // Use the medium string storage
421 ml_.capacity_ = capacity | isMedium;
423 // No need for the memory
429 // swap below doesn't test whether &rhs == this (and instead
430 // potentially does extra work) on the premise that the rarity of
431 // that situation actually makes the check more expensive than is
433 void swap(fbstring_core & rhs) {
439 // In C++11 data() and c_str() are 100% equivalent.
440 const Char * data() const {
444 Char * mutable_data() {
445 auto const c = category();
449 assert(c == isMedium || c == isLarge);
450 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
452 size_t effectiveCapacity = ml_.capacity();
453 auto const newRC = RefCounted::create(& effectiveCapacity);
454 // If this fails, someone placed the wrong capacity in an
456 assert(effectiveCapacity >= ml_.capacity());
457 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
459 RefCounted::decrementRefs(ml_.data_);
460 ml_.data_ = newRC->data_;
461 // No need to call writeTerminator(), we have + 1 above.
466 const Char * c_str() const {
467 auto const c = category();
468 #ifdef FBSTRING_PERVERSE
470 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
471 || small_[smallSize()] == '\0');
472 small_[smallSize()] = '\0';
475 assert(c == isMedium || c == isLarge);
476 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
477 ml_.data_[ml_.size_] = '\0';
478 #elif defined(FBSTRING_CONSERVATIVE)
480 assert(small_[smallSize()] == '\0');
483 assert(c == isMedium || c == isLarge);
484 assert(ml_.data_[ml_.size_] == '\0');
487 small_[smallSize()] = '\0';
490 assert(c == isMedium || c == isLarge);
491 ml_.data_[ml_.size_] = '\0';
496 void shrink(const size_t delta) {
497 if (category() == isSmall) {
498 // Check for underflow
499 assert(delta <= smallSize());
500 setSmallSize(smallSize() - delta);
501 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
502 // Medium strings and unique large strings need no special
504 assert(ml_.size_ >= delta);
507 assert(ml_.size_ >= delta);
508 // Shared large string, must make unique. This is because of the
509 // durn terminator must be written, which may trample the shared
512 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
514 // No need to write the terminator.
520 void reserve(size_t minCapacity) {
521 if (category() == isLarge) {
523 if (RefCounted::refs(ml_.data_) > 1) {
524 // We must make it unique regardless; in-place reallocation is
525 // useless if the string is shared. In order to not surprise
526 // people, reserve the new block at current capacity or
527 // more. That way, a string's capacity never shrinks after a
529 minCapacity = std::max(minCapacity, ml_.capacity());
530 auto const newRC = RefCounted::create(& minCapacity);
531 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
533 // Done with the old data. No need to call writeTerminator(),
534 // we have + 1 above.
535 RefCounted::decrementRefs(ml_.data_);
536 ml_.data_ = newRC->data_;
537 ml_.capacity_ = minCapacity | isLarge;
538 // size remains unchanged
540 // String is not shared, so let's try to realloc (if needed)
541 if (minCapacity > ml_.capacity()) {
542 // Asking for more memory
544 RefCounted::reallocate(ml_.data_, ml_.size_,
545 ml_.capacity(), minCapacity);
546 ml_.data_ = newRC->data_;
547 ml_.capacity_ = minCapacity | isLarge;
550 assert(capacity() >= minCapacity);
552 } else if (category() == isMedium) {
553 // String is not shared
554 if (minCapacity <= ml_.capacity()) {
555 return; // nothing to do, there's enough room
557 if (minCapacity <= maxMediumSize) {
558 // Keep the string at medium size. Don't forget to allocate
559 // one extra Char for the terminating null.
560 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
561 ml_.data_ = static_cast<Char *>(
564 ml_.size_ * sizeof(Char),
565 ml_.capacity() * sizeof(Char),
568 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
570 // Conversion from medium to large string
571 fbstring_core nascent;
572 // Will recurse to another branch of this function
573 nascent.reserve(minCapacity);
574 nascent.ml_.size_ = ml_.size_;
575 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
579 assert(capacity() >= minCapacity);
582 assert(category() == isSmall);
583 if (minCapacity > maxMediumSize) {
585 auto const newRC = RefCounted::create(& minCapacity);
586 auto const size = smallSize();
587 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
588 // No need for writeTerminator(), we wrote it above with + 1.
589 ml_.data_ = newRC->data_;
591 ml_.capacity_ = minCapacity | isLarge;
592 assert(capacity() >= minCapacity);
593 } else if (minCapacity > maxSmallSize) {
595 // Don't forget to allocate one extra Char for the terminating null
596 auto const allocSizeBytes =
597 goodMallocSize((1 + minCapacity) * sizeof(Char));
598 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
599 auto const size = smallSize();
600 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
601 // No need for writeTerminator(), we wrote it above with + 1.
604 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
607 // Nothing to do, everything stays put
610 assert(capacity() >= minCapacity);
613 Char * expand_noinit(const size_t delta) {
614 // Strategy is simple: make room, then change size
615 assert(capacity() >= size());
617 if (category() == isSmall) {
620 if (newSz <= maxSmallSize) {
628 newSz = ml_.size_ + delta;
629 if (newSz > ml_.capacity()) {
633 assert(capacity() >= newSz);
634 // Category can't be small - we took care of that above
635 assert(category() == isMedium || category() == isLarge);
638 assert(size() == newSz);
639 return ml_.data_ + sz;
642 void push_back(Char c) {
643 assert(capacity() >= size());
645 if (category() == isSmall) {
647 if (sz < maxSmallSize) {
648 setSmallSize(sz + 1);
653 reserve(maxSmallSize * 2);
657 if (sz == cp) reserve(cp * 3 / 2);
659 assert(capacity() >= sz + 1);
660 // Category can't be small - we took care of that above
661 assert(category() == isMedium || category() == isLarge);
663 mutable_data()[sz] = c;
667 size_t size() const {
668 return category() == isSmall ? smallSize() : ml_.size_;
671 size_t capacity() const {
672 switch (category()) {
676 // For large-sized strings, a multi-referenced chunk has no
677 // available capacity. This is because any attempt to append
678 // data would trigger a new allocation.
679 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
682 return ml_.capacity();
685 bool isShared() const {
686 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
689 #ifdef FBSTRING_PERVERSE
690 enum { TERMINATOR = '^' };
692 enum { TERMINATOR = '\0' };
695 void writeTerminator() {
696 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
697 if (category() == isSmall) {
698 const auto s = smallSize();
699 if (s != maxSmallSize) {
700 small_[s] = TERMINATOR;
703 ml_.data_[ml_.size_] = TERMINATOR;
710 fbstring_core & operator=(const fbstring_core & rhs);
717 size_t capacity() const {
718 return capacity_ & capacityExtractMask;
723 std::atomic<size_t> refCount_;
726 static RefCounted * fromData(Char * p) {
727 return static_cast<RefCounted*>(
729 static_cast<unsigned char*>(static_cast<void*>(p))
730 - offsetof(RefCounted, data_)));
733 static size_t refs(Char * p) {
734 return fromData(p)->refCount_.load(std::memory_order_acquire);
737 static void incrementRefs(Char * p) {
738 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
741 static void decrementRefs(Char * p) {
742 auto const dis = fromData(p);
743 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
750 static RefCounted * create(size_t * size) {
751 // Don't forget to allocate one extra Char for the terminating
752 // null. In this case, however, one Char is already part of the
754 const size_t allocSize = goodMallocSize(
755 sizeof(RefCounted) + *size * sizeof(Char));
756 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
757 result->refCount_.store(1, std::memory_order_release);
758 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
762 static RefCounted * create(const Char * data, size_t * size) {
763 const size_t effectiveSize = *size;
764 auto result = create(size);
765 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
769 static RefCounted * reallocate(Char *const data,
770 const size_t currentSize,
771 const size_t currentCapacity,
772 const size_t newCapacity) {
773 assert(newCapacity > 0 && newCapacity > currentSize);
774 auto const dis = fromData(data);
775 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
776 // Don't forget to allocate one extra Char for the terminating
777 // null. In this case, however, one Char is already part of the
779 auto result = static_cast<RefCounted*>(
781 sizeof(RefCounted) + currentSize * sizeof(Char),
782 sizeof(RefCounted) + currentCapacity * sizeof(Char),
783 sizeof(RefCounted) + newCapacity * sizeof(Char)));
784 assert(result->refCount_.load(std::memory_order_acquire) == 1);
790 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
791 mutable MediumLarge ml_;
795 lastChar = sizeof(MediumLarge) - 1,
796 maxSmallSize = lastChar / sizeof(Char),
797 maxMediumSize = 254 / sizeof(Char), // coincides with the small
798 // bin size in dlmalloc
799 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
800 capacityExtractMask = ~categoryExtractMask,
802 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
803 "Corrupt memory layout for fbstring.");
807 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
808 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
811 Category category() const {
812 // Assumes little endian
813 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
816 size_t smallSize() const {
817 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
818 return static_cast<size_t>(maxSmallSize)
819 - static_cast<size_t>(small_[maxSmallSize]);
822 void setSmallSize(size_t s) {
823 // Warning: this should work with uninitialized strings too,
824 // so don't assume anything about the previous value of
825 // small_[maxSmallSize].
826 assert(s <= maxSmallSize);
827 small_[maxSmallSize] = maxSmallSize - s;
831 # pragma GCC diagnostic pop
833 #ifndef _LIBSTDCXX_FBSTRING
835 * Dummy fbstring core that uses an actual std::string. This doesn't
836 * make any sense - it's just for testing purposes.
838 template <class Char>
839 class dummy_fbstring_core {
841 dummy_fbstring_core() {
843 dummy_fbstring_core(const dummy_fbstring_core& another)
844 : backend_(another.backend_) {
846 dummy_fbstring_core(const Char * s, size_t n)
849 void swap(dummy_fbstring_core & rhs) {
850 backend_.swap(rhs.backend_);
852 const Char * data() const {
853 return backend_.data();
855 Char * mutable_data() {
856 //assert(!backend_.empty());
857 return &*backend_.begin();
859 void shrink(size_t delta) {
860 assert(delta <= size());
861 backend_.resize(size() - delta);
863 Char * expand_noinit(size_t delta) {
864 auto const sz = size();
865 backend_.resize(size() + delta);
866 return backend_.data() + sz;
868 void push_back(Char c) {
869 backend_.push_back(c);
871 size_t size() const {
872 return backend_.size();
874 size_t capacity() const {
875 return backend_.capacity();
877 bool isShared() const {
880 void reserve(size_t minCapacity) {
881 backend_.reserve(minCapacity);
885 std::basic_string<Char> backend_;
887 #endif // !_LIBSTDCXX_FBSTRING
890 * This is the basic_string replacement. For conformity,
891 * basic_fbstring takes the same template parameters, plus the last
892 * one which is the core.
894 #ifdef _LIBSTDCXX_FBSTRING
895 template <typename E, class T, class A, class Storage>
897 template <typename E,
898 class T = std::char_traits<E>,
899 class A = std::allocator<E>,
900 class Storage = fbstring_core<E> >
902 class basic_fbstring {
906 void (*throw_exc)(const char*),
908 if (!condition) throw_exc(msg);
911 bool isSane() const {
914 empty() == (size() == 0) &&
915 empty() == (begin() == end()) &&
916 size() <= max_size() &&
917 capacity() <= max_size() &&
918 size() <= capacity() &&
919 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
923 friend struct Invariant;
926 explicit Invariant(const basic_fbstring& s) : s_(s) {
933 const basic_fbstring& s_;
935 explicit Invariant(const basic_fbstring&) {}
937 Invariant& operator=(const Invariant&);
942 typedef T traits_type;
943 typedef typename traits_type::char_type value_type;
944 typedef A allocator_type;
945 typedef typename A::size_type size_type;
946 typedef typename A::difference_type difference_type;
948 typedef typename A::reference reference;
949 typedef typename A::const_reference const_reference;
950 typedef typename A::pointer pointer;
951 typedef typename A::const_pointer const_pointer;
954 typedef const E* const_iterator;
955 typedef std::reverse_iterator<iterator
956 #ifdef NO_ITERATOR_TRAITS
960 typedef std::reverse_iterator<const_iterator
961 #ifdef NO_ITERATOR_TRAITS
964 > const_reverse_iterator;
966 static const size_type npos; // = size_type(-1)
969 static void procrustes(size_type& n, size_type nmax) {
970 if (n > nmax) n = nmax;
974 // 21.3.1 construct/copy/destroy
975 explicit basic_fbstring(const A& a = A()) {
978 basic_fbstring(const basic_fbstring& str)
979 : store_(str.store_) {
983 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
986 #ifndef _LIBSTDCXX_FBSTRING
987 // This is defined for compatibility with std::string
988 /* implicit */ basic_fbstring(const std::string& str)
989 : store_(str.data(), str.size()) {
993 basic_fbstring(const basic_fbstring& str, size_type pos,
994 size_type n = npos, const A& a = A()) {
998 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
999 : store_(s, s ? traits_type::length(s) : ({
1000 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1001 err += ": null pointer initializer not valid";
1002 std::__throw_logic_error(err.c_str());
1007 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1011 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1012 auto const data = store_.expand_noinit(n);
1013 fbstring_detail::pod_fill(data, data + n, c);
1014 store_.writeTerminator();
1017 template <class InIt>
1018 basic_fbstring(InIt begin, InIt end,
1019 typename std::enable_if<
1020 !std::is_same<typename std::remove_const<InIt>::type,
1021 value_type*>::value, const A>::type & a = A()) {
1025 // Specialization for const char*, const char*
1026 basic_fbstring(const value_type* b, const value_type* e)
1027 : store_(b, e - b) {
1030 // Nonstandard constructor
1031 basic_fbstring(value_type *s, size_type n, size_type c,
1032 AcquireMallocatedString a)
1033 : store_(s, n, c, a) {
1039 basic_fbstring& operator=(const basic_fbstring & lhs) {
1043 auto const oldSize = size();
1044 auto const srcSize = lhs.size();
1045 if (capacity() >= srcSize && !store_.isShared()) {
1046 // great, just copy the contents
1047 if (oldSize < srcSize)
1048 store_.expand_noinit(srcSize - oldSize);
1050 store_.shrink(oldSize - srcSize);
1051 assert(size() == srcSize);
1052 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1053 store_.writeTerminator();
1055 // need to reallocate, so we may as well create a brand new string
1056 basic_fbstring(lhs).swap(*this);
1062 basic_fbstring& operator=(basic_fbstring&& goner) {
1063 // No need of this anymore
1064 this->~basic_fbstring();
1065 // Move the goner into this
1066 new(&store_) fbstring_core<E>(std::move(goner.store_));
1070 #ifndef _LIBSTDCXX_FBSTRING
1071 // Compatibility with std::string
1072 basic_fbstring & operator=(const std::string & rhs) {
1073 return assign(rhs.data(), rhs.size());
1076 // Compatibility with std::string
1077 std::string toStdString() const {
1078 return std::string(data(), size());
1081 // A lot of code in fbcode still uses this method, so keep it here for now.
1082 const basic_fbstring& toStdString() const {
1087 basic_fbstring& operator=(const value_type* s) {
1091 basic_fbstring& operator=(value_type c) {
1093 store_.expand_noinit(1);
1094 } else if (store_.isShared()) {
1095 basic_fbstring(1, c).swap(*this);
1098 store_.shrink(size() - 1);
1100 *store_.mutable_data() = c;
1101 store_.writeTerminator();
1105 // 21.3.2 iterators:
1106 iterator begin() { return store_.mutable_data(); }
1108 const_iterator begin() const { return store_.data(); }
1111 return store_.mutable_data() + store_.size();
1114 const_iterator end() const {
1115 return store_.data() + store_.size();
1118 reverse_iterator rbegin() {
1119 return reverse_iterator(end());
1122 const_reverse_iterator rbegin() const {
1123 return const_reverse_iterator(end());
1126 reverse_iterator rend() {
1127 return reverse_iterator(begin());
1130 const_reverse_iterator rend() const {
1131 return const_reverse_iterator(begin());
1134 // Non-standard functions. They intentionally return by value to
1135 // reduce pressure on the reference counting mechanism.
1136 value_type front() const { return *begin(); }
1137 value_type back() const {
1139 return begin()[size() - 1];
1141 void pop_back() { assert(!empty()); store_.shrink(1); }
1144 size_type size() const { return store_.size(); }
1146 size_type length() const { return size(); }
1148 size_type max_size() const {
1149 return std::numeric_limits<size_type>::max();
1152 void resize(const size_type n, const value_type c = value_type()) {
1153 auto size = this->size();
1155 store_.shrink(size - n);
1157 // Do this in two steps to minimize slack memory copied (see
1159 auto const capacity = this->capacity();
1160 assert(capacity >= size);
1161 if (size < capacity) {
1162 auto delta = std::min(n, capacity) - size;
1163 store_.expand_noinit(delta);
1164 fbstring_detail::pod_fill(begin() + size, end(), c);
1167 store_.writeTerminator();
1172 auto const delta = n - size;
1173 store_.expand_noinit(delta);
1174 fbstring_detail::pod_fill(end() - delta, end(), c);
1175 store_.writeTerminator();
1177 assert(this->size() == n);
1180 size_type capacity() const { return store_.capacity(); }
1182 void reserve(size_type res_arg = 0) {
1183 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1184 store_.reserve(res_arg);
1187 void clear() { resize(0); }
1189 bool empty() const { return size() == 0; }
1191 // 21.3.4 element access:
1192 const_reference operator[](size_type pos) const {
1193 return *(c_str() + pos);
1196 reference operator[](size_type pos) {
1197 if (pos == size()) {
1198 // Just call c_str() to make sure '\0' is present
1201 return *(begin() + pos);
1204 const_reference at(size_type n) const {
1205 enforce(n <= size(), std::__throw_out_of_range, "");
1209 reference at(size_type n) {
1210 enforce(n < size(), std::__throw_out_of_range, "");
1214 // 21.3.5 modifiers:
1215 basic_fbstring& operator+=(const basic_fbstring& str) {
1219 basic_fbstring& operator+=(const value_type* s) {
1223 basic_fbstring& operator+=(const value_type c) {
1228 basic_fbstring& append(const basic_fbstring& str) {
1230 auto desiredSize = size() + str.size();
1232 append(str.data(), str.size());
1233 assert(size() == desiredSize);
1237 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1239 const size_type sz = str.size();
1240 enforce(pos <= sz, std::__throw_out_of_range, "");
1241 procrustes(n, sz - pos);
1242 return append(str.data() + pos, n);
1245 basic_fbstring& append(const value_type* s, size_type n) {
1247 Invariant checker(*this);
1251 // Unlikely but must be done
1254 auto const oldSize = size();
1255 auto const oldData = data();
1256 // Check for aliasing (rare). We could use "<=" here but in theory
1257 // those do not work for pointers unless the pointers point to
1258 // elements in the same array. For that reason we use
1259 // std::less_equal, which is guaranteed to offer a total order
1260 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1262 static const std::less_equal<const value_type*> le;
1263 if (UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1264 assert(le(s + n, oldData + oldSize));
1265 const size_type offset = s - oldData;
1266 store_.reserve(oldSize + n);
1267 // Restore the source
1268 s = data() + offset;
1270 // Warning! Repeated appends with short strings may actually incur
1271 // practically quadratic performance. Avoid that by pushing back
1272 // the first character (which ensures exponential growth) and then
1273 // appending the rest normally. Worst case the append may incur a
1274 // second allocation but that will be rare.
1277 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1278 assert(size() == oldSize + n + 1);
1282 basic_fbstring& append(const value_type* s) {
1283 return append(s, traits_type::length(s));
1286 basic_fbstring& append(size_type n, value_type c) {
1287 resize(size() + n, c);
1291 template<class InputIterator>
1292 basic_fbstring& append(InputIterator first, InputIterator last) {
1293 insert(end(), first, last);
1297 void push_back(const value_type c) { // primitive
1298 store_.push_back(c);
1301 basic_fbstring& assign(const basic_fbstring& str) {
1302 if (&str == this) return *this;
1303 return assign(str.data(), str.size());
1306 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1308 const size_type sz = str.size();
1309 enforce(pos <= sz, std::__throw_out_of_range, "");
1310 procrustes(n, sz - pos);
1311 return assign(str.data() + pos, n);
1314 basic_fbstring& assign(const value_type* s, const size_type n) {
1315 Invariant checker(*this);
1318 std::copy(s, s + n, begin());
1320 assert(size() == n);
1322 const value_type *const s2 = s + size();
1323 std::copy(s, s2, begin());
1324 append(s2, n - size());
1325 assert(size() == n);
1327 store_.writeTerminator();
1328 assert(size() == n);
1332 basic_fbstring& assign(const value_type* s) {
1333 return assign(s, traits_type::length(s));
1336 template <class ItOrLength, class ItOrChar>
1337 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1338 return replace(begin(), end(), first_or_n, last_or_c);
1341 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1342 return insert(pos1, str.data(), str.size());
1345 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1346 size_type pos2, size_type n) {
1347 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1348 procrustes(n, str.length() - pos2);
1349 return insert(pos1, str.data() + pos2, n);
1352 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1353 enforce(pos <= length(), std::__throw_out_of_range, "");
1354 insert(begin() + pos, s, s + n);
1358 basic_fbstring& insert(size_type pos, const value_type* s) {
1359 return insert(pos, s, traits_type::length(s));
1362 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1363 enforce(pos <= length(), std::__throw_out_of_range, "");
1364 insert(begin() + pos, n, c);
1368 iterator insert(const iterator p, const value_type c) {
1369 const size_type pos = p - begin();
1371 return begin() + pos;
1375 template <int i> class Selector {};
1377 basic_fbstring& insertImplDiscr(iterator p,
1378 size_type n, value_type c, Selector<1>) {
1379 Invariant checker(*this);
1381 assert(p >= begin() && p <= end());
1382 if (capacity() - size() < n) {
1383 const size_type sz = p - begin();
1384 reserve(size() + n);
1387 const iterator oldEnd = end();
1388 if( n < size_type(oldEnd - p)) {
1389 append(oldEnd - n, oldEnd);
1391 // reverse_iterator(oldEnd - n),
1392 // reverse_iterator(p),
1393 // reverse_iterator(oldEnd));
1394 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1395 std::fill(p, p + n, c);
1397 append(n - (end() - p), c);
1399 std::fill(p, oldEnd, c);
1401 store_.writeTerminator();
1405 template<class InputIter>
1406 basic_fbstring& insertImplDiscr(iterator i,
1407 InputIter b, InputIter e, Selector<0>) {
1409 typename std::iterator_traits<InputIter>::iterator_category());
1413 template <class FwdIterator>
1414 void insertImpl(iterator i,
1415 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1416 Invariant checker(*this);
1418 const size_type pos = i - begin();
1419 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1420 std::distance(s1, s2);
1422 using namespace fbstring_detail;
1423 assert(pos <= size());
1425 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1426 capacity() - size();
1428 // realloc the string
1429 reserve(size() + n2);
1432 if (pos + n2 <= size()) {
1433 const iterator tailBegin = end() - n2;
1434 store_.expand_noinit(n2);
1435 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1436 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1437 reverse_iterator(tailBegin + n2));
1438 std::copy(s1, s2, i);
1441 const size_type old_size = size();
1442 std::advance(t, old_size - pos);
1443 const size_t newElems = std::distance(t, s2);
1444 store_.expand_noinit(n2);
1445 std::copy(t, s2, begin() + old_size);
1446 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1447 begin() + old_size + newElems);
1448 std::copy(s1, t, i);
1450 store_.writeTerminator();
1453 template <class InputIterator>
1454 void insertImpl(iterator i,
1455 InputIterator b, InputIterator e, std::input_iterator_tag) {
1456 basic_fbstring temp(begin(), i);
1457 for (; b != e; ++b) {
1460 temp.append(i, end());
1465 template <class ItOrLength, class ItOrChar>
1466 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1467 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1468 insertImplDiscr(p, first_or_n, last_or_c, sel);
1471 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1472 Invariant checker(*this);
1474 enforce(pos <= length(), std::__throw_out_of_range, "");
1475 procrustes(n, length() - pos);
1476 std::copy(begin() + pos + n, end(), begin() + pos);
1477 resize(length() - n);
1481 iterator erase(iterator position) {
1482 const size_type pos(position - begin());
1483 enforce(pos <= size(), std::__throw_out_of_range, "");
1485 return begin() + pos;
1488 iterator erase(iterator first, iterator last) {
1489 const size_type pos(first - begin());
1490 erase(pos, last - first);
1491 return begin() + pos;
1494 // Replaces at most n1 chars of *this, starting with pos1 with the
1496 basic_fbstring& replace(size_type pos1, size_type n1,
1497 const basic_fbstring& str) {
1498 return replace(pos1, n1, str.data(), str.size());
1501 // Replaces at most n1 chars of *this, starting with pos1,
1502 // with at most n2 chars of str starting with pos2
1503 basic_fbstring& replace(size_type pos1, size_type n1,
1504 const basic_fbstring& str,
1505 size_type pos2, size_type n2) {
1506 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1507 return replace(pos1, n1, str.data() + pos2,
1508 std::min(n2, str.size() - pos2));
1511 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1512 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1513 return replace(pos, n1, s, traits_type::length(s));
1516 // Replaces at most n1 chars of *this, starting with pos, with n2
1519 // consolidated with
1521 // Replaces at most n1 chars of *this, starting with pos, with at
1522 // most n2 chars of str. str must have at least n2 chars.
1523 template <class StrOrLength, class NumOrChar>
1524 basic_fbstring& replace(size_type pos, size_type n1,
1525 StrOrLength s_or_n2, NumOrChar n_or_c) {
1526 Invariant checker(*this);
1528 enforce(pos <= size(), std::__throw_out_of_range, "");
1529 procrustes(n1, length() - pos);
1530 const iterator b = begin() + pos;
1531 return replace(b, b + n1, s_or_n2, n_or_c);
1534 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1535 return replace(i1, i2, str.data(), str.length());
1538 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1539 return replace(i1, i2, s, traits_type::length(s));
1543 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1544 const value_type* s, size_type n,
1547 assert(begin() <= i1 && i1 <= end());
1548 assert(begin() <= i2 && i2 <= end());
1549 return replace(i1, i2, s, s + n);
1552 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1553 size_type n2, value_type c, Selector<1>) {
1554 const size_type n1 = i2 - i1;
1556 std::fill(i1, i1 + n2, c);
1559 std::fill(i1, i2, c);
1560 insert(i2, n2 - n1, c);
1566 template <class InputIter>
1567 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1568 InputIter b, InputIter e,
1570 replaceImpl(i1, i2, b, e,
1571 typename std::iterator_traits<InputIter>::iterator_category());
1576 template <class FwdIterator, class P>
1577 bool replaceAliased(iterator i1, iterator i2,
1578 FwdIterator s1, FwdIterator s2, P*) {
1582 template <class FwdIterator>
1583 bool replaceAliased(iterator i1, iterator i2,
1584 FwdIterator s1, FwdIterator s2, value_type*) {
1585 static const std::less_equal<const value_type*> le =
1586 std::less_equal<const value_type*>();
1587 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1591 // Aliased replace, copy to new string
1592 basic_fbstring temp;
1593 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1594 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1600 template <class FwdIterator>
1601 void replaceImpl(iterator i1, iterator i2,
1602 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1603 Invariant checker(*this);
1606 // Handle aliased replace
1607 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1611 auto const n1 = i2 - i1;
1613 auto const n2 = std::distance(s1, s2);
1618 std::copy(s1, s2, i1);
1622 fbstring_detail::copy_n(s1, n1, i1);
1623 std::advance(s1, n1);
1629 template <class InputIterator>
1630 void replaceImpl(iterator i1, iterator i2,
1631 InputIterator b, InputIterator e, std::input_iterator_tag) {
1632 basic_fbstring temp(begin(), i1);
1633 temp.append(b, e).append(i2, end());
1638 template <class T1, class T2>
1639 basic_fbstring& replace(iterator i1, iterator i2,
1640 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1642 num1 = std::numeric_limits<T1>::is_specialized,
1643 num2 = std::numeric_limits<T2>::is_specialized;
1644 return replaceImplDiscr(
1645 i1, i2, first_or_n_or_s, last_or_c_or_n,
1646 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1649 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1650 enforce(pos <= size(), std::__throw_out_of_range, "");
1651 procrustes(n, size() - pos);
1653 fbstring_detail::pod_copy(
1660 void swap(basic_fbstring& rhs) {
1661 store_.swap(rhs.store_);
1664 // 21.3.6 string operations:
1665 const value_type* c_str() const {
1666 return store_.c_str();
1669 const value_type* data() const { return c_str(); }
1671 allocator_type get_allocator() const {
1672 return allocator_type();
1675 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1676 return find(str.data(), pos, str.length());
1679 size_type find(const value_type* needle, const size_type pos,
1680 const size_type nsize) const {
1681 if (!nsize) return pos;
1682 auto const size = this->size();
1683 if (nsize + pos > size) return npos;
1684 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1685 // the last characters first
1686 auto const haystack = data();
1687 auto const nsize_1 = nsize - 1;
1688 auto const lastNeedle = needle[nsize_1];
1690 // Boyer-Moore skip value for the last char in the needle. Zero is
1691 // not a valid value; skip will be computed the first time it's
1695 const E * i = haystack + pos;
1696 auto iEnd = haystack + size - nsize_1;
1699 // Boyer-Moore: match the last element in the needle
1700 while (i[nsize_1] != lastNeedle) {
1706 // Here we know that the last char matches
1707 // Continue in pedestrian mode
1708 for (size_t j = 0; ; ) {
1710 if (i[j] != needle[j]) {
1711 // Not found, we can skip
1712 // Compute the skip value lazily
1715 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1722 // Check if done searching
1725 return i - haystack;
1732 size_type find(const value_type* s, size_type pos = 0) const {
1733 return find(s, pos, traits_type::length(s));
1736 size_type find (value_type c, size_type pos = 0) const {
1737 return find(&c, pos, 1);
1740 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1741 return rfind(str.data(), pos, str.length());
1744 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1745 if (n > length()) return npos;
1746 pos = std::min(pos, length() - n);
1747 if (n == 0) return pos;
1749 const_iterator i(begin() + pos);
1751 if (traits_type::eq(*i, *s)
1752 && traits_type::compare(&*i, s, n) == 0) {
1755 if (i == begin()) break;
1760 size_type rfind(const value_type* s, size_type pos = npos) const {
1761 return rfind(s, pos, traits_type::length(s));
1764 size_type rfind(value_type c, size_type pos = npos) const {
1765 return rfind(&c, pos, 1);
1768 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1769 return find_first_of(str.data(), pos, str.length());
1772 size_type find_first_of(const value_type* s,
1773 size_type pos, size_type n) const {
1774 if (pos > length() || n == 0) return npos;
1775 const_iterator i(begin() + pos),
1777 for (; i != finish; ++i) {
1778 if (traits_type::find(s, n, *i) != 0) {
1785 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1786 return find_first_of(s, pos, traits_type::length(s));
1789 size_type find_first_of(value_type c, size_type pos = 0) const {
1790 return find_first_of(&c, pos, 1);
1793 size_type find_last_of (const basic_fbstring& str,
1794 size_type pos = npos) const {
1795 return find_last_of(str.data(), pos, str.length());
1798 size_type find_last_of (const value_type* s, size_type pos,
1799 size_type n) const {
1800 if (!empty() && n > 0) {
1801 pos = std::min(pos, length() - 1);
1802 const_iterator i(begin() + pos);
1804 if (traits_type::find(s, n, *i) != 0) {
1807 if (i == begin()) break;
1813 size_type find_last_of (const value_type* s,
1814 size_type pos = npos) const {
1815 return find_last_of(s, pos, traits_type::length(s));
1818 size_type find_last_of (value_type c, size_type pos = npos) const {
1819 return find_last_of(&c, pos, 1);
1822 size_type find_first_not_of(const basic_fbstring& str,
1823 size_type pos = 0) const {
1824 return find_first_not_of(str.data(), pos, str.size());
1827 size_type find_first_not_of(const value_type* s, size_type pos,
1828 size_type n) const {
1829 if (pos < length()) {
1833 for (; i != finish; ++i) {
1834 if (traits_type::find(s, n, *i) == 0) {
1842 size_type find_first_not_of(const value_type* s,
1843 size_type pos = 0) const {
1844 return find_first_not_of(s, pos, traits_type::length(s));
1847 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1848 return find_first_not_of(&c, pos, 1);
1851 size_type find_last_not_of(const basic_fbstring& str,
1852 size_type pos = npos) const {
1853 return find_last_not_of(str.data(), pos, str.length());
1856 size_type find_last_not_of(const value_type* s, size_type pos,
1857 size_type n) const {
1858 if (!this->empty()) {
1859 pos = std::min(pos, size() - 1);
1860 const_iterator i(begin() + pos);
1862 if (traits_type::find(s, n, *i) == 0) {
1865 if (i == begin()) break;
1871 size_type find_last_not_of(const value_type* s,
1872 size_type pos = npos) const {
1873 return find_last_not_of(s, pos, traits_type::length(s));
1876 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1877 return find_last_not_of(&c, pos, 1);
1880 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1881 enforce(pos <= size(), std::__throw_out_of_range, "");
1882 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1885 int compare(const basic_fbstring& str) const {
1886 // FIX due to Goncalo N M de Carvalho July 18, 2005
1887 return compare(0, size(), str);
1890 int compare(size_type pos1, size_type n1,
1891 const basic_fbstring& str) const {
1892 return compare(pos1, n1, str.data(), str.size());
1895 int compare(size_type pos1, size_type n1,
1896 const value_type* s) const {
1897 return compare(pos1, n1, s, traits_type::length(s));
1900 int compare(size_type pos1, size_type n1,
1901 const value_type* s, size_type n2) const {
1902 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1903 procrustes(n1, size() - pos1);
1904 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1905 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1906 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1909 int compare(size_type pos1, size_type n1,
1910 const basic_fbstring& str,
1911 size_type pos2, size_type n2) const {
1912 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1913 return compare(pos1, n1, str.data() + pos2,
1914 std::min(n2, str.size() - pos2));
1917 // Code from Jean-Francois Bastien (03/26/2007)
1918 int compare(const value_type* s) const {
1919 // Could forward to compare(0, size(), s, traits_type::length(s))
1920 // but that does two extra checks
1921 const size_type n1(size()), n2(traits_type::length(s));
1922 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1923 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1931 // non-member functions
1933 template <typename E, class T, class A, class S>
1935 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1936 const basic_fbstring<E, T, A, S>& rhs) {
1938 basic_fbstring<E, T, A, S> result;
1939 result.reserve(lhs.size() + rhs.size());
1940 result.append(lhs).append(rhs);
1941 return std::move(result);
1945 template <typename E, class T, class A, class S>
1947 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1948 const basic_fbstring<E, T, A, S>& rhs) {
1949 return std::move(lhs.append(rhs));
1953 template <typename E, class T, class A, class S>
1955 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1956 basic_fbstring<E, T, A, S>&& rhs) {
1957 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1958 // Good, at least we don't need to reallocate
1959 return std::move(rhs.insert(0, lhs));
1961 // Meh, no go. Forward to operator+(const&, const&).
1962 auto const& rhsC = rhs;
1967 template <typename E, class T, class A, class S>
1969 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1970 basic_fbstring<E, T, A, S>&& rhs) {
1971 return std::move(lhs.append(rhs));
1974 template <typename E, class T, class A, class S>
1976 basic_fbstring<E, T, A, S> operator+(
1977 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
1978 const basic_fbstring<E, T, A, S>& rhs) {
1980 basic_fbstring<E, T, A, S> result;
1981 const typename basic_fbstring<E, T, A, S>::size_type len =
1982 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
1983 result.reserve(len + rhs.size());
1984 result.append(lhs, len).append(rhs);
1988 template <typename E, class T, class A, class S>
1990 basic_fbstring<E, T, A, S> operator+(
1991 typename basic_fbstring<E, T, A, S>::value_type lhs,
1992 const basic_fbstring<E, T, A, S>& rhs) {
1994 basic_fbstring<E, T, A, S> result;
1995 result.reserve(1 + rhs.size());
1996 result.push_back(lhs);
2001 template <typename E, class T, class A, class S>
2003 basic_fbstring<E, T, A, S> operator+(
2004 const basic_fbstring<E, T, A, S>& lhs,
2005 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2007 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2008 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2010 basic_fbstring<E, T, A, S> result;
2011 const size_type len = traits_type::length(rhs);
2012 result.reserve(lhs.size() + len);
2013 result.append(lhs).append(rhs, len);
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 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2023 basic_fbstring<E, T, A, S> result;
2024 result.reserve(lhs.size() + 1);
2026 result.push_back(rhs);
2030 template <typename E, class T, class A, class S>
2032 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2033 const basic_fbstring<E, T, A, S>& rhs) {
2034 return lhs.compare(rhs) == 0; }
2036 template <typename E, class T, class A, class S>
2038 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2039 const basic_fbstring<E, T, A, S>& rhs) {
2040 return rhs == lhs; }
2042 template <typename E, class T, class A, class S>
2044 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2045 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2046 return lhs.compare(rhs) == 0; }
2048 template <typename E, class T, class A, class S>
2050 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2051 const basic_fbstring<E, T, A, S>& rhs) {
2052 return !(lhs == rhs); }
2054 template <typename E, class T, class A, class S>
2056 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2057 const basic_fbstring<E, T, A, S>& rhs) {
2058 return !(lhs == rhs); }
2060 template <typename E, class T, class A, class S>
2062 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2063 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2064 return !(lhs == rhs); }
2066 template <typename E, class T, class A, class S>
2068 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2069 const basic_fbstring<E, T, A, S>& rhs) {
2070 return lhs.compare(rhs) < 0; }
2072 template <typename E, class T, class A, class S>
2074 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2075 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2076 return lhs.compare(rhs) < 0; }
2078 template <typename E, class T, class A, class S>
2080 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2081 const basic_fbstring<E, T, A, S>& rhs) {
2082 return rhs.compare(lhs) > 0; }
2084 template <typename E, class T, class A, class S>
2086 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2087 const basic_fbstring<E, T, A, S>& rhs) {
2090 template <typename E, class T, class A, class S>
2092 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2093 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2096 template <typename E, class T, class A, class S>
2098 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2099 const basic_fbstring<E, T, A, S>& rhs) {
2102 template <typename E, class T, class A, class S>
2104 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2105 const basic_fbstring<E, T, A, S>& rhs) {
2106 return !(rhs < lhs); }
2108 template <typename E, class T, class A, class S>
2110 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2111 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2112 return !(rhs < lhs); }
2114 template <typename E, class T, class A, class S>
2116 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2117 const basic_fbstring<E, T, A, S>& rhs) {
2118 return !(rhs < lhs); }
2120 template <typename E, class T, class A, class S>
2122 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2123 const basic_fbstring<E, T, A, S>& rhs) {
2124 return !(lhs < rhs); }
2126 template <typename E, class T, class A, class S>
2128 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2129 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2130 return !(lhs < rhs); }
2132 template <typename E, class T, class A, class S>
2134 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2135 const basic_fbstring<E, T, A, S>& rhs) {
2136 return !(lhs < rhs);
2139 // subclause 21.3.7.8:
2140 template <typename E, class T, class A, class S>
2141 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2145 // TODO: make this faster.
2146 template <typename E, class T, class A, class S>
2149 typename basic_fbstring<E, T, A, S>::value_type,
2150 typename basic_fbstring<E, T, A, S>::traits_type>&
2152 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2153 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2154 basic_fbstring<E, T, A, S>& str) {
2155 typename std::basic_istream<E, T>::sentry sentry(is);
2156 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2157 typename basic_fbstring<E, T, A, S>::traits_type>
2159 typedef typename __istream_type::ios_base __ios_base;
2160 size_t extracted = 0;
2161 auto err = __ios_base::goodbit;
2163 auto n = is.width();
2168 auto got = is.rdbuf()->sgetc();
2169 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2170 // Whew. We get to store this guy
2172 got = is.rdbuf()->snextc();
2174 if (got == T::eof()) {
2175 err |= __ios_base::eofbit;
2180 err |= __ios_base::failbit;
2188 template <typename E, class T, class A, class S>
2190 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2191 typename basic_fbstring<E, T, A, S>::traits_type>&
2193 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2194 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2195 const basic_fbstring<E, T, A, S>& str) {
2196 os.write(str.data(), str.size());
2200 #ifndef _LIBSTDCXX_FBSTRING
2202 template <typename E, class T, class A, class S>
2204 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2205 typename basic_fbstring<E, T, A, S>::traits_type>&
2207 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2208 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2209 basic_fbstring<E, T, A, S>& str,
2210 typename basic_fbstring<E, T, A, S>::value_type delim) {
2211 // Use the nonstandard getdelim()
2215 // This looks quadratic but it really depends on realloc
2216 auto const newSize = size + 128;
2217 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2218 is.getline(buf + size, newSize - size, delim);
2219 if (is.bad() || is.eof() || !is.fail()) {
2220 // done by either failure, end of file, or normal read
2221 size += std::strlen(buf + size);
2224 // Here we have failed due to too short a buffer
2225 // Minus one to discount the terminating '\0'
2227 assert(buf[size] == 0);
2228 // Clear the error so we can continue reading
2231 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2232 AcquireMallocatedString());
2237 template <typename E, class T, class A, class S>
2239 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2240 typename basic_fbstring<E, T, A, S>::traits_type>&
2242 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2243 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2244 basic_fbstring<E, T, A, S>& str) {
2245 // Just forward to the version with a delimiter
2246 return getline(is, str, '\n');
2251 template <typename E1, class T, class A, class S>
2252 const typename basic_fbstring<E1, T, A, S>::size_type
2253 basic_fbstring<E1, T, A, S>::npos =
2254 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2256 #ifndef _LIBSTDCXX_FBSTRING
2257 // basic_string compatibility routines
2259 template <typename E, class T, class A, class S>
2261 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2262 const std::string& rhs) {
2263 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2266 template <typename E, class T, class A, class S>
2268 bool operator==(const std::string& lhs,
2269 const basic_fbstring<E, T, A, S>& rhs) {
2273 template <typename E, class T, class A, class S>
2275 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2276 const std::string& rhs) {
2277 return !(lhs == rhs);
2280 template <typename E, class T, class A, class S>
2282 bool operator!=(const std::string& lhs,
2283 const basic_fbstring<E, T, A, S>& rhs) {
2284 return !(lhs == rhs);
2287 #if !defined(_LIBSTDCXX_FBSTRING)
2288 typedef basic_fbstring<char> fbstring;
2291 // fbstring is relocatable
2292 template <class T, class R, class A, class S>
2293 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2296 _GLIBCXX_END_NAMESPACE_VERSION
2299 } // namespace folly
2301 #ifndef _LIBSTDCXX_FBSTRING
2305 struct hash< ::folly::fbstring> {
2306 size_t operator()(const ::folly::fbstring& s) const {
2307 return ::folly::hash::fnv32(s.c_str());
2312 #endif // _LIBSTDCXX_FBSTRING
2314 #endif // FOLLY_BASE_FBSTRING_H_