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. */home/engshare/third-party/src/
75 // libgcc/libgcc-4.6.2/gcc-4.6.2-20111027/libstdc++-v3/include/bits/
76 // basic_string.h* has a more detailed explanation of why this is necessary.
77 #ifdef FOLLY_MALLOC_H_
78 #undef FOLLY_MALLOC_H_
79 #include "basic_fbstring_malloc.h"
81 #include "basic_fbstring_malloc.h"
82 #undef FOLLY_MALLOC_H_
85 #else // !_LIBSTDCXX_FBSTRING
91 #include "folly/Traits.h"
92 #include "folly/Malloc.h"
93 #include "folly/Hash.h"
99 #include <type_traits>
101 #ifdef _LIBSTDCXX_FBSTRING
102 namespace std _GLIBCXX_VISIBILITY(default) {
103 _GLIBCXX_BEGIN_NAMESPACE_VERSION
108 namespace fbstring_detail {
110 template <class InIt, class OutIt>
113 typename std::iterator_traits<InIt>::difference_type n,
115 for (; n != 0; --n, ++b, ++d) {
116 assert((const void*)&*d != &*b);
122 template <class Pod, class T>
123 inline void pod_fill(Pod* b, Pod* e, T c) {
124 assert(b && e && b <= e);
125 /*static*/ if (sizeof(T) == 1) {
128 auto const ee = b + ((e - b) & ~7u);
129 for (; b != ee; b += 8) {
140 for (; b != e; ++b) {
147 * Lightly structured memcpy, simplifies copying PODs and introduces
151 inline Pod* pod_copy(const Pod* b, const Pod* e, Pod* d) {
153 assert(d >= e || d + (e - b) <= b);
154 const size_t s = e - b;
155 std::memcpy(d, b, s * sizeof(*b));
160 * Lightly structured memmove, simplifies copying PODs and introduces
164 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
166 memmove(d, b, (e - b) * sizeof(*b));
169 } // namespace fbstring_detail
172 * Defines a special acquisition method for constructing fbstring
173 * objects. AcquireMallocatedString means that the user passes a
174 * pointer to a malloc-allocated string that the fbstring object will
177 enum class AcquireMallocatedString {};
180 * fbstring_core_model is a mock-up type that defines all required
181 * signatures of a fbstring core. The fbstring class itself uses such
182 * a core object to implement all of the numerous member functions
183 * required by the standard.
185 * If you want to define a new core, copy the definition below and
186 * implement the primitives. Then plug the core into basic_fbstring as
187 * a template argument.
189 template <class Char>
190 class fbstring_core_model {
192 fbstring_core_model();
193 fbstring_core_model(const fbstring_core_model &);
194 ~fbstring_core_model();
195 // Returns a pointer to string's buffer (currently only contiguous
196 // strings are supported). The pointer is guaranteed to be valid
197 // until the next call to a non-const member function.
198 const Char * data() const;
199 // Much like data(), except the string is prepared to support
200 // character-level changes. This call is a signal for
201 // e.g. reference-counted implementation to fork the data. The
202 // pointer is guaranteed to be valid until the next call to a
203 // non-const member function.
204 Char * mutable_data();
205 // Returns a pointer to string's buffer and guarantees that a
206 // readable '\0' lies right after the buffer. The pointer is
207 // guaranteed to be valid until the next call to a non-const member
209 const Char * c_str() const;
210 // Shrinks the string by delta characters. Asserts that delta <=
212 void shrink(size_t delta);
213 // Expands the string by delta characters (i.e. after this call
214 // size() will report the old size() plus delta) but without
215 // initializing the expanded region. The caller is expected to fill
216 // the expanded area appropriately.
217 void expand_noinit(size_t delta);
218 // Expands the string by one character and sets the last character
220 void push_back(Char c);
221 // Returns the string's size.
223 // Returns the string's capacity, i.e. maximum size that the string
224 // can grow to without reallocation. Note that for reference counted
225 // strings that's technically a lie - even assigning characters
226 // within the existing size would cause a reallocation.
227 size_t capacity() const;
228 // Returns true if the data underlying the string is actually shared
229 // across multiple strings (in a refcounted fashion).
230 bool isShared() const;
231 // Makes sure that at least minCapacity characters are available for
232 // the string without reallocation. For reference-counted strings,
233 // it should fork the data even if minCapacity < size().
234 void reserve(size_t minCapacity);
237 fbstring_core_model& operator=(const fbstring_core_model &);
242 * This is the core of the string. The code should work on 32- and
243 * 64-bit architectures and with any Char size. Porting to big endian
244 * architectures would require some changes.
246 * The storage is selected as follows (assuming we store one-byte
247 * characters on a 64-bit machine): (a) "small" strings between 0 and
248 * 23 chars are stored in-situ without allocation (the rightmost byte
249 * stores the size); (b) "medium" strings from 24 through 254 chars
250 * are stored in malloc-allocated memory that is copied eagerly; (c)
251 * "large" strings of 255 chars and above are stored in a similar
252 * structure as medium arrays, except that the string is
253 * reference-counted and copied lazily. the reference count is
254 * allocated right before the character array.
256 * The discriminator between these three strategies sits in the two
257 * most significant bits of the rightmost char of the storage. If
258 * neither is set, then the string is small (and its length sits in
259 * the lower-order bits of that rightmost character). If the MSb is
260 * set, the string is medium width. If the second MSb is set, then the
263 template <class Char> class fbstring_core {
266 // Only initialize the tag, will set the MSBs (i.e. the small
267 // string size) to zero too
268 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - 1));
269 // or: setSmallSize(0);
271 assert(category() == isSmall && size() == 0);
274 fbstring_core(const fbstring_core & rhs) {
275 assert(&rhs != this);
276 // Simplest case first: small strings are bitblitted
277 if (rhs.category() == isSmall) {
278 assert(offsetof(MediumLarge, data_) == 0);
279 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
280 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
281 const size_t size = rhs.smallSize();
283 ml_.capacity_ = rhs.ml_.capacity_;
286 // Just write the whole thing, don't look at details. In
287 // particular we need to copy capacity anyway because we want
288 // to set the size (don't forget that the last character,
289 // which stores a short string's length, is shared with the
290 // ml_.capacity field).
293 assert(category() == isSmall && this->size() == rhs.size());
294 } else if (rhs.category() == isLarge) {
295 // Large strings are just refcounted
297 RefCounted::incrementRefs(ml_.data_);
298 assert(category() == isLarge && size() == rhs.size());
300 // Medium strings are copied eagerly. Don't forget to allocate
301 // one extra Char for the null terminator.
302 auto const allocSize =
303 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
304 ml_.data_ = static_cast<Char*>(malloc(allocSize));
305 fbstring_detail::pod_copy(rhs.ml_.data_,
307 rhs.ml_.data_ + rhs.ml_.size_ + 1,
309 // No need for writeTerminator() here, we copied one extra
310 // element just above.
311 ml_.size_ = rhs.ml_.size_;
312 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
313 assert(category() == isMedium);
315 assert(size() == rhs.size());
316 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
319 fbstring_core(fbstring_core&& goner) {
320 if (goner.category() == isSmall) {
321 // Just copy, leave the goner in peace
322 new(this) fbstring_core(goner.small_, goner.smallSize());
326 // Clean goner's carcass
327 goner.setSmallSize(0);
331 fbstring_core(const Char *const data, const size_t size) {
332 // Simplest case first: small strings are bitblitted
333 if (size <= maxSmallSize) {
334 // Layout is: Char* data_, size_t size_, size_t capacity_
335 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
336 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
337 // sizeof(size_t) must be a power of 2
338 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
340 // If data is aligned, use fast word-wise copying. Otherwise,
341 // use conservative memcpy.
342 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
343 fbstring_detail::pod_copy(data, data + size, small_);
345 // Copy one word (64 bits) at a time
346 const size_t byteSize = size * sizeof(Char);
347 if (byteSize > 2 * sizeof(size_t)) {
349 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
351 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
353 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
354 } else if (byteSize > sizeof(size_t)) {
357 } else if (size > 0) {
363 } else if (size <= maxMediumSize) {
364 // Medium strings are allocated normally. Don't forget to
365 // allocate one extra Char for the terminating null.
366 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
367 ml_.data_ = static_cast<Char*>(malloc(allocSize));
368 fbstring_detail::pod_copy(data, data + size, ml_.data_);
370 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
372 // Large strings are allocated differently
373 size_t effectiveCapacity = size;
374 auto const newRC = RefCounted::create(data, & effectiveCapacity);
375 ml_.data_ = newRC->data_;
377 ml_.capacity_ = effectiveCapacity | isLarge;
380 assert(this->size() == size);
381 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
385 auto const c = category();
393 RefCounted::decrementRefs(ml_.data_);
396 // Snatches a previously mallocated string. The parameter "size"
397 // is the size of the string, and the parameter "capacity" is the size
398 // of the mallocated block. The string must be \0-terminated, so
399 // data[size] == '\0' and capacity >= size + 1.
401 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
402 // "size", and pass 3 as "capacity".
403 fbstring_core(Char *const data, const size_t size,
404 const size_t capacity,
405 AcquireMallocatedString) {
407 assert(capacity > size);
408 assert(data[size] == '\0');
409 // Use the medium string storage
412 ml_.capacity_ = capacity | isMedium;
414 // No need for the memory
420 // swap below doesn't test whether &rhs == this (and instead
421 // potentially does extra work) on the premise that the rarity of
422 // that situation actually makes the check more expensive than is
424 void swap(fbstring_core & rhs) {
430 // In C++11 data() and c_str() are 100% equivalent.
431 const Char * data() const {
435 Char * mutable_data() {
436 auto const c = category();
440 assert(c == isMedium || c == isLarge);
441 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
443 size_t effectiveCapacity = ml_.capacity();
444 auto const newRC = RefCounted::create(& effectiveCapacity);
445 // If this fails, someone placed the wrong capacity in an
447 assert(effectiveCapacity >= ml_.capacity());
448 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
450 RefCounted::decrementRefs(ml_.data_);
451 ml_.data_ = newRC->data_;
452 // No need to call writeTerminator(), we have + 1 above.
457 const Char * c_str() const {
458 auto const c = category();
459 #ifdef FBSTRING_PERVERSE
461 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
462 || small_[smallSize()] == '\0');
463 small_[smallSize()] = '\0';
466 assert(c == isMedium || c == isLarge);
467 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
468 ml_.data_[ml_.size_] = '\0';
469 #elif defined(FBSTRING_CONSERVATIVE)
471 assert(small_[smallSize()] == '\0');
474 assert(c == isMedium || c == isLarge);
475 assert(ml_.data_[ml_.size_] == '\0');
478 small_[smallSize()] = '\0';
481 assert(c == isMedium || c == isLarge);
482 ml_.data_[ml_.size_] = '\0';
487 void shrink(const size_t delta) {
488 if (category() == isSmall) {
489 // Check for underflow
490 assert(delta <= smallSize());
491 setSmallSize(smallSize() - delta);
492 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
493 // Medium strings and unique large strings need no special
495 assert(ml_.size_ >= delta);
498 assert(ml_.size_ >= delta);
499 // Shared large string, must make unique. This is because of the
500 // durn terminator must be written, which may trample the shared
503 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
505 // No need to write the terminator.
511 void reserve(size_t minCapacity) {
512 if (category() == isLarge) {
514 if (RefCounted::refs(ml_.data_) > 1) {
515 // We must make it unique regardless; in-place reallocation is
516 // useless if the string is shared. In order to not surprise
517 // people, reserve the new block at current capacity or
518 // more. That way, a string's capacity never shrinks after a
520 minCapacity = std::max(minCapacity, ml_.capacity());
521 auto const newRC = RefCounted::create(& minCapacity);
522 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
524 // Done with the old data. No need to call writeTerminator(),
525 // we have + 1 above.
526 RefCounted::decrementRefs(ml_.data_);
527 ml_.data_ = newRC->data_;
528 ml_.capacity_ = minCapacity | isLarge;
529 // size remains unchanged
531 // String is not shared, so let's try to realloc (if needed)
532 if (minCapacity > ml_.capacity()) {
533 // Asking for more memory
535 RefCounted::reallocate(ml_.data_, ml_.size_,
536 ml_.capacity(), minCapacity);
537 ml_.data_ = newRC->data_;
538 ml_.capacity_ = minCapacity | isLarge;
541 assert(capacity() >= minCapacity);
543 } else if (category() == isMedium) {
544 // String is not shared
545 if (minCapacity <= ml_.capacity()) {
546 return; // nothing to do, there's enough room
548 if (minCapacity <= maxMediumSize) {
549 // Keep the string at medium size. Don't forget to allocate
550 // one extra Char for the terminating null.
551 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
552 ml_.data_ = static_cast<Char *>(
555 ml_.size_ * sizeof(Char),
556 ml_.capacity() * sizeof(Char),
559 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
561 // Conversion from medium to large string
562 fbstring_core nascent;
563 // Will recurse to another branch of this function
564 nascent.reserve(minCapacity);
565 nascent.ml_.size_ = ml_.size_;
566 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
570 assert(capacity() >= minCapacity);
573 assert(category() == isSmall);
574 if (minCapacity > maxMediumSize) {
576 auto const newRC = RefCounted::create(& minCapacity);
577 auto const size = smallSize();
578 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
579 // No need for writeTerminator(), we wrote it above with + 1.
580 ml_.data_ = newRC->data_;
582 ml_.capacity_ = minCapacity | isLarge;
583 assert(capacity() >= minCapacity);
584 } else if (minCapacity > maxSmallSize) {
586 // Don't forget to allocate one extra Char for the terminating null
587 auto const allocSizeBytes =
588 goodMallocSize((1 + minCapacity) * sizeof(Char));
589 auto const data = static_cast<Char*>(malloc(allocSizeBytes));
590 auto const size = smallSize();
591 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
592 // No need for writeTerminator(), we wrote it above with + 1.
595 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
598 // Nothing to do, everything stays put
601 assert(capacity() >= minCapacity);
604 void expand_noinit(const size_t delta) {
605 // Strategy is simple: make room, then change size
606 assert(capacity() >= size());
607 size_t sz, newSz, cp;
608 if (category() == isSmall) {
611 if (newSz <= maxSmallSize) {
622 if (newSz > cp) reserve(newSz);
623 assert(capacity() >= newSz);
624 // Category can't be small - we took care of that above
625 assert(category() == isMedium || category() == isLarge);
628 assert(size() == newSz);
631 void push_back(Char c) {
632 assert(capacity() >= size());
634 if (category() == isSmall) {
636 if (sz < maxSmallSize) {
637 setSmallSize(sz + 1);
642 reserve(maxSmallSize * 3 / 2);
646 if (sz == cp) reserve(cp * 3 / 2);
648 assert(capacity() >= sz + 1);
649 // Category can't be small - we took care of that above
650 assert(category() == isMedium || category() == isLarge);
652 mutable_data()[sz] = c;
656 size_t size() const {
657 return category() == isSmall ? smallSize() : ml_.size_;
660 size_t capacity() const {
661 switch (category()) {
665 // For large-sized strings, a multi-referenced chunk has no
666 // available capacity. This is because any attempt to append
667 // data would trigger a new allocation.
668 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
671 return ml_.capacity();
674 bool isShared() const {
675 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
678 #ifdef FBSTRING_PERVERSE
679 enum { TERMINATOR = '^' };
681 enum { TERMINATOR = '\0' };
684 void writeTerminator() {
685 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
686 if (category() == isSmall) {
687 const auto s = smallSize();
688 if (s != maxSmallSize) {
689 small_[s] = TERMINATOR;
692 ml_.data_[ml_.size_] = TERMINATOR;
699 fbstring_core & operator=(const fbstring_core & rhs);
706 size_t capacity() const {
707 return capacity_ & capacityExtractMask;
712 std::atomic<size_t> refCount_;
715 static RefCounted * fromData(Char * p) {
716 return static_cast<RefCounted*>(
718 static_cast<unsigned char*>(static_cast<void*>(p))
719 - offsetof(RefCounted, data_)));
722 static size_t refs(Char * p) {
723 return fromData(p)->refCount_.load(std::memory_order_acquire);
726 static void incrementRefs(Char * p) {
727 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
730 static void decrementRefs(Char * p) {
731 auto const dis = fromData(p);
732 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
739 static RefCounted * create(size_t * size) {
740 // Don't forget to allocate one extra Char for the terminating
741 // null. In this case, however, one Char is already part of the
743 const size_t allocSize = goodMallocSize(
744 sizeof(RefCounted) + *size * sizeof(Char));
745 auto result = static_cast<RefCounted*>(malloc(allocSize));
746 result->refCount_.store(1, std::memory_order_release);
747 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
751 static RefCounted * create(const Char * data, size_t * size) {
752 const size_t effectiveSize = *size;
753 auto result = create(size);
754 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
758 static RefCounted * reallocate(Char *const data,
759 const size_t currentSize,
760 const size_t currentCapacity,
761 const size_t newCapacity) {
762 assert(newCapacity > 0 && newCapacity > currentSize);
763 auto const dis = fromData(data);
764 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
765 // Don't forget to allocate one extra Char for the terminating
766 // null. In this case, however, one Char is already part of the
768 auto result = static_cast<RefCounted*>(
770 sizeof(RefCounted) + currentSize * sizeof(Char),
771 sizeof(RefCounted) + currentCapacity * sizeof(Char),
772 sizeof(RefCounted) + newCapacity * sizeof(Char)));
773 assert(result->refCount_.load(std::memory_order_acquire) == 1);
779 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
780 mutable MediumLarge ml_;
784 lastChar = sizeof(MediumLarge) - 1,
785 maxSmallSize = lastChar / sizeof(Char),
786 maxMediumSize = 254 / sizeof(Char), // coincides with the small
787 // bin size in dlmalloc
788 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
789 capacityExtractMask = ~categoryExtractMask,
791 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
792 "Corrupt memory layout for fbstring.");
796 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
797 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
800 Category category() const {
801 // Assumes little endian
802 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
805 size_t smallSize() const {
806 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
807 return static_cast<size_t>(maxSmallSize)
808 - static_cast<size_t>(small_[maxSmallSize]);
811 void setSmallSize(size_t s) {
812 // Warning: this should work with uninitialized strings too,
813 // so don't assume anything about the previous value of
814 // small_[maxSmallSize].
815 assert(s <= maxSmallSize);
816 small_[maxSmallSize] = maxSmallSize - s;
820 #ifndef _LIBSTDCXX_FBSTRING
822 * Dummy fbstring core that uses an actual std::string. This doesn't
823 * make any sense - it's just for testing purposes.
825 template <class Char>
826 class dummy_fbstring_core {
828 dummy_fbstring_core() {
830 dummy_fbstring_core(const dummy_fbstring_core& another)
831 : backend_(another.backend_) {
833 dummy_fbstring_core(const Char * s, size_t n)
836 void swap(dummy_fbstring_core & rhs) {
837 backend_.swap(rhs.backend_);
839 const Char * data() const {
840 return backend_.data();
842 Char * mutable_data() {
843 //assert(!backend_.empty());
844 return &*backend_.begin();
846 void shrink(size_t delta) {
847 assert(delta <= size());
848 backend_.resize(size() - delta);
850 void expand_noinit(size_t delta) {
851 backend_.resize(size() + delta);
853 void push_back(Char c) {
854 backend_.push_back(c);
856 size_t size() const {
857 return backend_.size();
859 size_t capacity() const {
860 return backend_.capacity();
862 bool isShared() const {
865 void reserve(size_t minCapacity) {
866 backend_.reserve(minCapacity);
870 std::basic_string<Char> backend_;
872 #endif // !_LIBSTDCXX_FBSTRING
875 * This is the basic_string replacement. For conformity,
876 * basic_fbstring takes the same template parameters, plus the last
877 * one which is the core.
879 #ifdef _LIBSTDCXX_FBSTRING
880 template <typename E, class T, class A, class Storage>
882 template <typename E,
883 class T = std::char_traits<E>,
884 class A = std::allocator<E>,
885 class Storage = fbstring_core<E> >
887 class basic_fbstring {
891 void (*throw_exc)(const char*),
893 if (!condition) throw_exc(msg);
896 bool isSane() const {
899 empty() == (size() == 0) &&
900 empty() == (begin() == end()) &&
901 size() <= max_size() &&
902 capacity() <= max_size() &&
903 size() <= capacity() &&
904 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
908 friend struct Invariant;
911 explicit Invariant(const basic_fbstring& s) : s_(s) {
918 const basic_fbstring& s_;
920 explicit Invariant(const basic_fbstring&) {}
922 Invariant& operator=(const Invariant&);
927 typedef T traits_type;
928 typedef typename traits_type::char_type value_type;
929 typedef A allocator_type;
930 typedef typename A::size_type size_type;
931 typedef typename A::difference_type difference_type;
933 typedef typename A::reference reference;
934 typedef typename A::const_reference const_reference;
935 typedef typename A::pointer pointer;
936 typedef typename A::const_pointer const_pointer;
939 typedef const E* const_iterator;
940 typedef std::reverse_iterator<iterator
941 #ifdef NO_ITERATOR_TRAITS
945 typedef std::reverse_iterator<const_iterator
946 #ifdef NO_ITERATOR_TRAITS
949 > const_reverse_iterator;
951 static const size_type npos; // = size_type(-1)
954 static void procrustes(size_type& n, size_type nmax) {
955 if (n > nmax) n = nmax;
959 // 21.3.1 construct/copy/destroy
960 explicit basic_fbstring(const A& a = A()) {
963 basic_fbstring(const basic_fbstring& str)
964 : store_(str.store_) {
968 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
971 #ifndef _LIBSTDCXX_FBSTRING
972 // This is defined for compatibility with std::string
973 /* implicit */ basic_fbstring(const std::string& str)
974 : store_(str.data(), str.size()) {
978 basic_fbstring(const basic_fbstring& str, size_type pos,
979 size_type n = npos, const A& a = A()) {
983 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
984 : store_(s, s ? traits_type::length(s) : ({
985 basic_fbstring<char> err = __PRETTY_FUNCTION__;
986 err += ": null pointer initializer not valid";
987 std::__throw_logic_error(err.c_str());
992 basic_fbstring(const value_type* s, size_type n, const A& a = A())
996 basic_fbstring(size_type n, value_type c, const A& a = A()) {
997 store_.expand_noinit(n);
998 auto const data = store_.mutable_data();
999 fbstring_detail::pod_fill(data, data + n, c);
1000 store_.writeTerminator();
1003 template <class InIt>
1004 basic_fbstring(InIt begin, InIt end,
1005 typename std::enable_if<
1006 !std::is_same<typename std::remove_const<InIt>::type,
1007 value_type*>::value, const A>::type & a = A()) {
1011 // Specialization for const char*, const char*
1012 basic_fbstring(const value_type* b, const value_type* e)
1013 : store_(b, e - b) {
1016 // Nonstandard constructor
1017 basic_fbstring(value_type *s, size_type n, size_type c,
1018 AcquireMallocatedString a)
1019 : store_(s, n, c, a) {
1025 basic_fbstring& operator=(const basic_fbstring & lhs) {
1029 auto const oldSize = size();
1030 auto const srcSize = lhs.size();
1031 if (capacity() >= srcSize && !store_.isShared()) {
1032 // great, just copy the contents
1033 if (oldSize < srcSize)
1034 store_.expand_noinit(srcSize - oldSize);
1036 store_.shrink(oldSize - srcSize);
1037 assert(size() == srcSize);
1038 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1039 store_.writeTerminator();
1041 // need to reallocate, so we may as well create a brand new string
1042 basic_fbstring(lhs).swap(*this);
1048 basic_fbstring& operator=(basic_fbstring&& goner) {
1049 // No need of this anymore
1050 this->~basic_fbstring();
1051 // Move the goner into this
1052 new(&store_) fbstring_core<E>(std::move(goner.store_));
1056 #ifndef _LIBSTDCXX_FBSTRING
1057 // Compatibility with std::string
1058 basic_fbstring & operator=(const std::string & rhs) {
1059 return assign(rhs.data(), rhs.size());
1062 // Compatibility with std::string
1063 std::string toStdString() const {
1064 return std::string(data(), size());
1067 // A lot of code in fbcode still uses this method, so keep it here for now.
1068 const basic_fbstring& toStdString() const {
1073 basic_fbstring& operator=(const value_type* s) {
1077 basic_fbstring& operator=(value_type c) {
1079 store_.expand_noinit(1);
1080 } else if (store_.isShared()) {
1081 basic_fbstring(1, c).swap(*this);
1084 store_.shrink(size() - 1);
1086 *store_.mutable_data() = c;
1087 store_.writeTerminator();
1091 // 21.3.2 iterators:
1092 iterator begin() { return store_.mutable_data(); }
1094 const_iterator begin() const { return store_.data(); }
1097 return store_.mutable_data() + store_.size();
1100 const_iterator end() const {
1101 return store_.data() + store_.size();
1104 reverse_iterator rbegin() {
1105 return reverse_iterator(end());
1108 const_reverse_iterator rbegin() const {
1109 return const_reverse_iterator(end());
1112 reverse_iterator rend() {
1113 return reverse_iterator(begin());
1116 const_reverse_iterator rend() const {
1117 return const_reverse_iterator(begin());
1120 // Non-standard functions. They intentionally return by value to
1121 // reduce pressure on the reference counting mechanism.
1122 value_type front() const { return *begin(); }
1123 value_type back() const {
1125 return begin()[size() - 1];
1127 void pop_back() { assert(!empty()); store_.shrink(1); }
1130 size_type size() const { return store_.size(); }
1132 size_type length() const { return size(); }
1134 size_type max_size() const {
1135 return std::numeric_limits<size_type>::max();
1138 void resize(const size_type n, const value_type c = value_type()) {
1139 auto size = this->size();
1141 store_.shrink(size - n);
1143 // Do this in two steps to minimize slack memory copied (see
1145 auto const capacity = this->capacity();
1146 assert(capacity >= size);
1147 if (size < capacity) {
1148 auto delta = std::min(n, capacity) - size;
1149 store_.expand_noinit(delta);
1150 fbstring_detail::pod_fill(begin() + size, end(), c);
1153 store_.writeTerminator();
1158 auto const delta = n - size;
1159 store_.expand_noinit(delta);
1160 fbstring_detail::pod_fill(end() - delta, end(), c);
1161 store_.writeTerminator();
1163 assert(this->size() == n);
1166 size_type capacity() const { return store_.capacity(); }
1168 void reserve(size_type res_arg = 0) {
1169 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1170 store_.reserve(res_arg);
1173 void clear() { resize(0); }
1175 bool empty() const { return size() == 0; }
1177 // 21.3.4 element access:
1178 const_reference operator[](size_type pos) const {
1179 return *(c_str() + pos);
1182 reference operator[](size_type pos) {
1183 if (pos == size()) {
1184 // Just call c_str() to make sure '\0' is present
1187 return *(begin() + pos);
1190 const_reference at(size_type n) const {
1191 enforce(n <= size(), std::__throw_out_of_range, "");
1195 reference at(size_type n) {
1196 enforce(n < size(), std::__throw_out_of_range, "");
1200 // 21.3.5 modifiers:
1201 basic_fbstring& operator+=(const basic_fbstring& str) {
1205 basic_fbstring& operator+=(const value_type* s) {
1209 basic_fbstring& operator+=(const value_type c) {
1214 basic_fbstring& append(const basic_fbstring& str) {
1216 auto desiredSize = size() + str.size();
1218 append(str.data(), str.size());
1219 assert(size() == desiredSize);
1223 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1225 const size_type sz = str.size();
1226 enforce(pos <= sz, std::__throw_out_of_range, "");
1227 procrustes(n, sz - pos);
1228 return append(str.data() + pos, n);
1231 basic_fbstring& append(const value_type* s, const size_type n) {
1233 auto oldSize = size();
1235 Invariant checker(*this);
1237 static std::less_equal<const value_type*> le;
1238 if (le(data(), s) && !le(data() + size(), s)) {// aliasing
1239 assert(le(s + n, data() + size()));
1240 const size_type offset = s - data();
1241 store_.reserve(size() + n);
1242 // Restore the source
1243 s = data() + offset;
1245 store_.expand_noinit(n);
1246 fbstring_detail::pod_copy(s, s + n, end() - n);
1247 store_.writeTerminator();
1248 assert(size() == oldSize + n);
1252 basic_fbstring& append(const value_type* s) {
1253 return append(s, traits_type::length(s));
1256 basic_fbstring& append(size_type n, value_type c) {
1257 resize(size() + n, c);
1261 template<class InputIterator>
1262 basic_fbstring& append(InputIterator first, InputIterator last) {
1263 insert(end(), first, last);
1267 void push_back(const value_type c) { // primitive
1268 store_.push_back(c);
1271 basic_fbstring& assign(const basic_fbstring& str) {
1272 if (&str == this) return *this;
1273 return assign(str.data(), str.size());
1276 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1278 const size_type sz = str.size();
1279 enforce(pos <= sz, std::__throw_out_of_range, "");
1280 procrustes(n, sz - pos);
1281 return assign(str.data() + pos, n);
1284 basic_fbstring& assign(const value_type* s, const size_type n) {
1285 Invariant checker(*this);
1288 std::copy(s, s + n, begin());
1290 assert(size() == n);
1292 const value_type *const s2 = s + size();
1293 std::copy(s, s2, begin());
1294 append(s2, n - size());
1295 assert(size() == n);
1297 store_.writeTerminator();
1298 assert(size() == n);
1302 basic_fbstring& assign(const value_type* s) {
1303 return assign(s, traits_type::length(s));
1306 template <class ItOrLength, class ItOrChar>
1307 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1308 return replace(begin(), end(), first_or_n, last_or_c);
1311 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1312 return insert(pos1, str.data(), str.size());
1315 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1316 size_type pos2, size_type n) {
1317 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1318 procrustes(n, str.length() - pos2);
1319 return insert(pos1, str.data() + pos2, n);
1322 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1323 enforce(pos <= length(), std::__throw_out_of_range, "");
1324 insert(begin() + pos, s, s + n);
1328 basic_fbstring& insert(size_type pos, const value_type* s) {
1329 return insert(pos, s, traits_type::length(s));
1332 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1333 enforce(pos <= length(), std::__throw_out_of_range, "");
1334 insert(begin() + pos, n, c);
1338 iterator insert(const iterator p, const value_type c) {
1339 const size_type pos = p - begin();
1341 return begin() + pos;
1345 template <int i> class Selector {};
1347 basic_fbstring& insertImplDiscr(iterator p,
1348 size_type n, value_type c, Selector<1>) {
1349 Invariant checker(*this);
1351 assert(p >= begin() && p <= end());
1352 if (capacity() - size() < n) {
1353 const size_type sz = p - begin();
1354 reserve(size() + n);
1357 const iterator oldEnd = end();
1358 if( n < size_type(oldEnd - p)) {
1359 append(oldEnd - n, oldEnd);
1361 // reverse_iterator(oldEnd - n),
1362 // reverse_iterator(p),
1363 // reverse_iterator(oldEnd));
1364 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1365 std::fill(p, p + n, c);
1367 append(n - (end() - p), c);
1369 std::fill(p, oldEnd, c);
1371 store_.writeTerminator();
1375 template<class InputIter>
1376 basic_fbstring& insertImplDiscr(iterator i,
1377 InputIter b, InputIter e, Selector<0>) {
1379 typename std::iterator_traits<InputIter>::iterator_category());
1383 template <class FwdIterator>
1384 void insertImpl(iterator i,
1385 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1386 Invariant checker(*this);
1388 const size_type pos = i - begin();
1389 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1390 std::distance(s1, s2);
1392 using namespace fbstring_detail;
1393 assert(pos <= size());
1395 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1396 capacity() - size();
1398 // realloc the string
1399 reserve(size() + n2);
1402 if (pos + n2 <= size()) {
1403 const iterator tailBegin = end() - n2;
1404 store_.expand_noinit(n2);
1405 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1406 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1407 reverse_iterator(tailBegin + n2));
1408 std::copy(s1, s2, i);
1411 const size_type old_size = size();
1412 std::advance(t, old_size - pos);
1413 const size_t newElems = std::distance(t, s2);
1414 store_.expand_noinit(n2);
1415 std::copy(t, s2, begin() + old_size);
1416 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1417 begin() + old_size + newElems);
1418 std::copy(s1, t, i);
1420 store_.writeTerminator();
1423 template <class InputIterator>
1424 void insertImpl(iterator i,
1425 InputIterator b, InputIterator e, std::input_iterator_tag) {
1426 basic_fbstring temp(begin(), i);
1427 for (; b != e; ++b) {
1430 temp.append(i, end());
1435 template <class ItOrLength, class ItOrChar>
1436 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1437 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1438 insertImplDiscr(p, first_or_n, last_or_c, sel);
1441 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1442 Invariant checker(*this);
1444 enforce(pos <= length(), std::__throw_out_of_range, "");
1445 procrustes(n, length() - pos);
1446 std::copy(begin() + pos + n, end(), begin() + pos);
1447 resize(length() - n);
1451 iterator erase(iterator position) {
1452 const size_type pos(position - begin());
1453 enforce(pos <= size(), std::__throw_out_of_range, "");
1455 return begin() + pos;
1458 iterator erase(iterator first, iterator last) {
1459 const size_type pos(first - begin());
1460 erase(pos, last - first);
1461 return begin() + pos;
1464 // Replaces at most n1 chars of *this, starting with pos1 with the
1466 basic_fbstring& replace(size_type pos1, size_type n1,
1467 const basic_fbstring& str) {
1468 return replace(pos1, n1, str.data(), str.size());
1471 // Replaces at most n1 chars of *this, starting with pos1,
1472 // with at most n2 chars of str starting with pos2
1473 basic_fbstring& replace(size_type pos1, size_type n1,
1474 const basic_fbstring& str,
1475 size_type pos2, size_type n2) {
1476 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1477 return replace(pos1, n1, str.data() + pos2,
1478 std::min(n2, str.size() - pos2));
1481 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1482 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1483 return replace(pos, n1, s, traits_type::length(s));
1486 // Replaces at most n1 chars of *this, starting with pos, with n2
1489 // consolidated with
1491 // Replaces at most n1 chars of *this, starting with pos, with at
1492 // most n2 chars of str. str must have at least n2 chars.
1493 template <class StrOrLength, class NumOrChar>
1494 basic_fbstring& replace(size_type pos, size_type n1,
1495 StrOrLength s_or_n2, NumOrChar n_or_c) {
1496 Invariant checker(*this);
1498 enforce(pos <= size(), std::__throw_out_of_range, "");
1499 procrustes(n1, length() - pos);
1500 const iterator b = begin() + pos;
1501 return replace(b, b + n1, s_or_n2, n_or_c);
1504 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1505 return replace(i1, i2, str.data(), str.length());
1508 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1509 return replace(i1, i2, s, traits_type::length(s));
1513 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1514 const value_type* s, size_type n,
1517 assert(begin() <= i1 && i1 <= end());
1518 assert(begin() <= i2 && i2 <= end());
1519 return replace(i1, i2, s, s + n);
1522 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1523 size_type n2, value_type c, Selector<1>) {
1524 const size_type n1 = i2 - i1;
1526 std::fill(i1, i1 + n2, c);
1529 std::fill(i1, i2, c);
1530 insert(i2, n2 - n1, c);
1536 template <class InputIter>
1537 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1538 InputIter b, InputIter e,
1540 replaceImpl(i1, i2, b, e,
1541 typename std::iterator_traits<InputIter>::iterator_category());
1546 template <class FwdIterator, class P>
1547 bool replaceAliased(iterator i1, iterator i2,
1548 FwdIterator s1, FwdIterator s2, P*) {
1552 template <class FwdIterator>
1553 bool replaceAliased(iterator i1, iterator i2,
1554 FwdIterator s1, FwdIterator s2, value_type*) {
1555 static const std::less_equal<const value_type*> le =
1556 std::less_equal<const value_type*>();
1557 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1561 // Aliased replace, copy to new string
1562 basic_fbstring temp;
1563 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1564 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1570 template <class FwdIterator>
1571 void replaceImpl(iterator i1, iterator i2,
1572 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1573 Invariant checker(*this);
1576 // Handle aliased replace
1577 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1581 auto const n1 = i2 - i1;
1583 auto const n2 = std::distance(s1, s2);
1588 std::copy(s1, s2, i1);
1592 fbstring_detail::copy_n(s1, n1, i1);
1593 std::advance(s1, n1);
1599 template <class InputIterator>
1600 void replaceImpl(iterator i1, iterator i2,
1601 InputIterator b, InputIterator e, std::input_iterator_tag) {
1602 basic_fbstring temp(begin(), i1);
1603 temp.append(b, e).append(i2, end());
1608 template <class T1, class T2>
1609 basic_fbstring& replace(iterator i1, iterator i2,
1610 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1612 num1 = std::numeric_limits<T1>::is_specialized,
1613 num2 = std::numeric_limits<T2>::is_specialized;
1614 return replaceImplDiscr(
1615 i1, i2, first_or_n_or_s, last_or_c_or_n,
1616 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1619 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1620 enforce(pos <= size(), std::__throw_out_of_range, "");
1621 procrustes(n, size() - pos);
1623 fbstring_detail::pod_copy(
1630 void swap(basic_fbstring& rhs) {
1631 store_.swap(rhs.store_);
1634 // 21.3.6 string operations:
1635 const value_type* c_str() const {
1636 return store_.c_str();
1639 const value_type* data() const { return c_str(); }
1641 allocator_type get_allocator() const {
1642 return allocator_type();
1645 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1646 return find(str.data(), pos, str.length());
1649 size_type find(const value_type* needle, const size_type pos,
1650 const size_type nsize) const {
1651 if (!nsize) return pos;
1652 auto const size = this->size();
1653 if (nsize + pos > size) return npos;
1654 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1655 // the last characters first
1656 auto const haystack = data();
1657 auto const nsize_1 = nsize - 1;
1658 auto const lastNeedle = needle[nsize_1];
1660 // Boyer-Moore skip value for the last char in the needle. Zero is
1661 // not a valid value; skip will be computed the first time it's
1665 const E * i = haystack + pos;
1666 auto iEnd = haystack + size - nsize_1;
1669 // Boyer-Moore: match the last element in the needle
1670 while (i[nsize_1] != lastNeedle) {
1676 // Here we know that the last char matches
1677 // Continue in pedestrian mode
1678 for (size_t j = 0; ; ) {
1680 if (i[j] != needle[j]) {
1681 // Not found, we can skip
1682 // Compute the skip value lazily
1685 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1692 // Check if done searching
1695 return i - haystack;
1702 size_type find(const value_type* s, size_type pos = 0) const {
1703 return find(s, pos, traits_type::length(s));
1706 size_type find (value_type c, size_type pos = 0) const {
1707 return find(&c, pos, 1);
1710 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1711 return rfind(str.data(), pos, str.length());
1714 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1715 if (n > length()) return npos;
1716 pos = std::min(pos, length() - n);
1717 if (n == 0) return pos;
1719 const_iterator i(begin() + pos);
1721 if (traits_type::eq(*i, *s)
1722 && traits_type::compare(&*i, s, n) == 0) {
1725 if (i == begin()) break;
1730 size_type rfind(const value_type* s, size_type pos = npos) const {
1731 return rfind(s, pos, traits_type::length(s));
1734 size_type rfind(value_type c, size_type pos = npos) const {
1735 return rfind(&c, pos, 1);
1738 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1739 return find_first_of(str.data(), pos, str.length());
1742 size_type find_first_of(const value_type* s,
1743 size_type pos, size_type n) const {
1744 if (pos > length() || n == 0) return npos;
1745 const_iterator i(begin() + pos),
1747 for (; i != finish; ++i) {
1748 if (traits_type::find(s, n, *i) != 0) {
1755 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1756 return find_first_of(s, pos, traits_type::length(s));
1759 size_type find_first_of(value_type c, size_type pos = 0) const {
1760 return find_first_of(&c, pos, 1);
1763 size_type find_last_of (const basic_fbstring& str,
1764 size_type pos = npos) const {
1765 return find_last_of(str.data(), pos, str.length());
1768 size_type find_last_of (const value_type* s, size_type pos,
1769 size_type n) const {
1770 if (!empty() && n > 0) {
1771 pos = std::min(pos, length() - 1);
1772 const_iterator i(begin() + pos);
1774 if (traits_type::find(s, n, *i) != 0) {
1777 if (i == begin()) break;
1783 size_type find_last_of (const value_type* s,
1784 size_type pos = npos) const {
1785 return find_last_of(s, pos, traits_type::length(s));
1788 size_type find_last_of (value_type c, size_type pos = npos) const {
1789 return find_last_of(&c, pos, 1);
1792 size_type find_first_not_of(const basic_fbstring& str,
1793 size_type pos = 0) const {
1794 return find_first_not_of(str.data(), pos, str.size());
1797 size_type find_first_not_of(const value_type* s, size_type pos,
1798 size_type n) const {
1799 if (pos < length()) {
1803 for (; i != finish; ++i) {
1804 if (traits_type::find(s, n, *i) == 0) {
1812 size_type find_first_not_of(const value_type* s,
1813 size_type pos = 0) const {
1814 return find_first_not_of(s, pos, traits_type::length(s));
1817 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1818 return find_first_not_of(&c, pos, 1);
1821 size_type find_last_not_of(const basic_fbstring& str,
1822 size_type pos = npos) const {
1823 return find_last_not_of(str.data(), pos, str.length());
1826 size_type find_last_not_of(const value_type* s, size_type pos,
1827 size_type n) const {
1828 if (!this->empty()) {
1829 pos = std::min(pos, size() - 1);
1830 const_iterator i(begin() + pos);
1832 if (traits_type::find(s, n, *i) == 0) {
1835 if (i == begin()) break;
1841 size_type find_last_not_of(const value_type* s,
1842 size_type pos = npos) const {
1843 return find_last_not_of(s, pos, traits_type::length(s));
1846 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1847 return find_last_not_of(&c, pos, 1);
1850 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1851 enforce(pos <= size(), std::__throw_out_of_range, "");
1852 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1855 int compare(const basic_fbstring& str) const {
1856 // FIX due to Goncalo N M de Carvalho July 18, 2005
1857 return compare(0, size(), str);
1860 int compare(size_type pos1, size_type n1,
1861 const basic_fbstring& str) const {
1862 return compare(pos1, n1, str.data(), str.size());
1865 int compare(size_type pos1, size_type n1,
1866 const value_type* s) const {
1867 return compare(pos1, n1, s, traits_type::length(s));
1870 int compare(size_type pos1, size_type n1,
1871 const value_type* s, size_type n2) const {
1872 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1873 procrustes(n1, size() - pos1);
1874 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1875 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1876 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1879 int compare(size_type pos1, size_type n1,
1880 const basic_fbstring& str,
1881 size_type pos2, size_type n2) const {
1882 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1883 return compare(pos1, n1, str.data() + pos2,
1884 std::min(n2, str.size() - pos2));
1887 // Code from Jean-Francois Bastien (03/26/2007)
1888 int compare(const value_type* s) const {
1889 // Could forward to compare(0, size(), s, traits_type::length(s))
1890 // but that does two extra checks
1891 const size_type n1(size()), n2(traits_type::length(s));
1892 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1893 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1901 // non-member functions
1903 template <typename E, class T, class A, class S>
1905 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1906 const basic_fbstring<E, T, A, S>& rhs) {
1908 basic_fbstring<E, T, A, S> result;
1909 result.reserve(lhs.size() + rhs.size());
1910 result.append(lhs).append(rhs);
1911 return std::move(result);
1915 template <typename E, class T, class A, class S>
1917 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1918 const basic_fbstring<E, T, A, S>& rhs) {
1919 return std::move(lhs.append(rhs));
1923 template <typename E, class T, class A, class S>
1925 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1926 basic_fbstring<E, T, A, S>&& rhs) {
1927 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1928 // Good, at least we don't need to reallocate
1929 return std::move(rhs.insert(0, lhs));
1931 // Meh, no go. Forward to operator+(const&, const&).
1932 auto const& rhsC = rhs;
1937 template <typename E, class T, class A, class S>
1939 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1940 basic_fbstring<E, T, A, S>&& rhs) {
1941 return std::move(lhs.append(rhs));
1944 template <typename E, class T, class A, class S>
1946 basic_fbstring<E, T, A, S> operator+(
1947 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
1948 const basic_fbstring<E, T, A, S>& rhs) {
1950 basic_fbstring<E, T, A, S> result;
1951 const typename basic_fbstring<E, T, A, S>::size_type len =
1952 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
1953 result.reserve(len + rhs.size());
1954 result.append(lhs, len).append(rhs);
1958 template <typename E, class T, class A, class S>
1960 basic_fbstring<E, T, A, S> operator+(
1961 typename basic_fbstring<E, T, A, S>::value_type lhs,
1962 const basic_fbstring<E, T, A, S>& rhs) {
1964 basic_fbstring<E, T, A, S> result;
1965 result.reserve(1 + rhs.size());
1966 result.push_back(lhs);
1971 template <typename E, class T, class A, class S>
1973 basic_fbstring<E, T, A, S> operator+(
1974 const basic_fbstring<E, T, A, S>& lhs,
1975 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
1977 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
1978 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
1980 basic_fbstring<E, T, A, S> result;
1981 const size_type len = traits_type::length(rhs);
1982 result.reserve(lhs.size() + len);
1983 result.append(lhs).append(rhs, len);
1987 template <typename E, class T, class A, class S>
1989 basic_fbstring<E, T, A, S> operator+(
1990 const basic_fbstring<E, T, A, S>& lhs,
1991 typename basic_fbstring<E, T, A, S>::value_type rhs) {
1993 basic_fbstring<E, T, A, S> result;
1994 result.reserve(lhs.size() + 1);
1996 result.push_back(rhs);
2000 template <typename E, class T, class A, class S>
2002 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2003 const basic_fbstring<E, T, A, S>& rhs) {
2004 return lhs.compare(rhs) == 0; }
2006 template <typename E, class T, class A, class S>
2008 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2009 const basic_fbstring<E, T, A, S>& rhs) {
2010 return rhs == lhs; }
2012 template <typename E, class T, class A, class S>
2014 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2015 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2016 return lhs.compare(rhs) == 0; }
2018 template <typename E, class T, class A, class S>
2020 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2021 const basic_fbstring<E, T, A, S>& rhs) {
2022 return !(lhs == rhs); }
2024 template <typename E, class T, class A, class S>
2026 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2027 const basic_fbstring<E, T, A, S>& rhs) {
2028 return !(lhs == rhs); }
2030 template <typename E, class T, class A, class S>
2032 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2033 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2034 return !(lhs == rhs); }
2036 template <typename E, class T, class A, class S>
2038 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2039 const basic_fbstring<E, T, A, S>& rhs) {
2040 return lhs.compare(rhs) < 0; }
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 typename basic_fbstring<E, T, A, S>::value_type* lhs,
2051 const basic_fbstring<E, T, A, S>& rhs) {
2052 return rhs.compare(lhs) > 0; }
2054 template <typename E, class T, class A, class S>
2056 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2057 const basic_fbstring<E, T, A, S>& 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) {
2066 template <typename E, class T, class A, class S>
2068 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2069 const basic_fbstring<E, T, A, S>& rhs) {
2072 template <typename E, class T, class A, class S>
2074 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2075 const basic_fbstring<E, T, A, S>& rhs) {
2076 return !(rhs < lhs); }
2078 template <typename E, class T, class A, class S>
2080 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2081 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2082 return !(rhs < lhs); }
2084 template <typename E, class T, class A, class S>
2086 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2087 const basic_fbstring<E, T, A, S>& rhs) {
2088 return !(rhs < lhs); }
2090 template <typename E, class T, class A, class S>
2092 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2093 const basic_fbstring<E, T, A, S>& rhs) {
2094 return !(lhs < rhs); }
2096 template <typename E, class T, class A, class S>
2098 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2099 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2100 return !(lhs < rhs); }
2102 template <typename E, class T, class A, class S>
2104 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2105 const basic_fbstring<E, T, A, S>& rhs) {
2106 return !(lhs < rhs);
2109 // subclause 21.3.7.8:
2110 template <typename E, class T, class A, class S>
2111 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2115 // TODO: make this faster.
2116 template <typename E, class T, class A, class S>
2119 typename basic_fbstring<E, T, A, S>::value_type,
2120 typename basic_fbstring<E, T, A, S>::traits_type>&
2122 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2123 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2124 basic_fbstring<E, T, A, S>& str) {
2125 typename std::basic_istream<E, T>::sentry sentry(is);
2126 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2127 typename basic_fbstring<E, T, A, S>::traits_type>
2129 typedef typename __istream_type::ios_base __ios_base;
2130 size_t extracted = 0;
2131 auto err = __ios_base::goodbit;
2133 auto n = is.width();
2138 auto got = is.rdbuf()->sgetc();
2139 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2140 // Whew. We get to store this guy
2142 got = is.rdbuf()->snextc();
2144 if (got == T::eof()) {
2145 err |= __ios_base::eofbit;
2150 err |= __ios_base::failbit;
2158 template <typename E, class T, class A, class S>
2160 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2161 typename basic_fbstring<E, T, A, S>::traits_type>&
2163 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2164 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2165 const basic_fbstring<E, T, A, S>& str) {
2166 os.write(str.data(), str.size());
2170 #ifndef _LIBSTDCXX_FBSTRING
2172 template <typename E, class T, class A, class S>
2174 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2175 typename basic_fbstring<E, T, A, S>::traits_type>&
2177 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2178 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2179 basic_fbstring<E, T, A, S>& str,
2180 typename basic_fbstring<E, T, A, S>::value_type delim) {
2181 // Use the nonstandard getdelim()
2185 // This looks quadratic but it really depends on realloc
2186 auto const newSize = size + 128;
2187 buf = static_cast<char*>(realloc(buf, newSize));
2188 is.getline(buf + size, newSize - size, delim);
2189 if (is.bad() || is.eof() || !is.fail()) {
2190 // done by either failure, end of file, or normal read
2191 size += std::strlen(buf + size);
2194 // Here we have failed due to too short a buffer
2195 // Minus one to discount the terminating '\0'
2197 assert(buf[size] == 0);
2198 // Clear the error so we can continue reading
2201 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2202 AcquireMallocatedString());
2207 template <typename E, class T, class A, class S>
2209 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2210 typename basic_fbstring<E, T, A, S>::traits_type>&
2212 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2213 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2214 basic_fbstring<E, T, A, S>& str) {
2215 // Just forward to the version with a delimiter
2216 return getline(is, str, '\n');
2221 template <typename E1, class T, class A, class S>
2222 const typename basic_fbstring<E1, T, A, S>::size_type
2223 basic_fbstring<E1, T, A, S>::npos =
2224 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2226 #ifndef _LIBSTDCXX_FBSTRING
2227 // basic_string compatiblity routines
2229 template <typename E, class T, class A, class S>
2231 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2232 const std::string& rhs) {
2233 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2236 template <typename E, class T, class A, class S>
2238 bool operator==(const std::string& lhs,
2239 const basic_fbstring<E, T, A, S>& rhs) {
2243 template <typename E, class T, class A, class S>
2245 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2246 const std::string& rhs) {
2247 return !(lhs == rhs);
2250 template <typename E, class T, class A, class S>
2252 bool operator!=(const std::string& lhs,
2253 const basic_fbstring<E, T, A, S>& rhs) {
2254 return !(lhs == rhs);
2257 #if !defined(_LIBSTDCXX_FBSTRING)
2258 typedef basic_fbstring<char> fbstring;
2261 // fbstring is relocatable
2262 template <class T, class R, class A, class S>
2263 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2266 _GLIBCXX_END_NAMESPACE_VERSION
2269 } // namespace folly
2271 #ifndef _LIBSTDCXX_FBSTRING
2275 struct hash< ::folly::fbstring> {
2276 size_t operator()(const ::folly::fbstring& s) const {
2277 return ::folly::hash::fnv32(s.c_str());
2282 #endif // _LIBSTDCXX_FBSTRING
2284 #endif // FOLLY_BASE_FBSTRING_H_