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 > 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);
656 cp = capacity(); // != ml_.capacity() for isShared()
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());
1135 // C++11 21.4.5, element access:
1136 const value_type& front() const { return *begin(); }
1137 const value_type& back() const {
1139 // Should be begin()[size() - 1], but that branches twice
1140 return *(end() - 1);
1142 value_type& front() { return *begin(); }
1143 value_type& back() {
1145 // Should be begin()[size() - 1], but that branches twice
1146 return *(end() - 1);
1154 size_type size() const { return store_.size(); }
1156 size_type length() const { return size(); }
1158 size_type max_size() const {
1159 return std::numeric_limits<size_type>::max();
1162 void resize(const size_type n, const value_type c = value_type()) {
1163 auto size = this->size();
1165 store_.shrink(size - n);
1167 // Do this in two steps to minimize slack memory copied (see
1169 auto const capacity = this->capacity();
1170 assert(capacity >= size);
1171 if (size < capacity) {
1172 auto delta = std::min(n, capacity) - size;
1173 store_.expand_noinit(delta);
1174 fbstring_detail::pod_fill(begin() + size, end(), c);
1177 store_.writeTerminator();
1182 auto const delta = n - size;
1183 store_.expand_noinit(delta);
1184 fbstring_detail::pod_fill(end() - delta, end(), c);
1185 store_.writeTerminator();
1187 assert(this->size() == n);
1190 size_type capacity() const { return store_.capacity(); }
1192 void reserve(size_type res_arg = 0) {
1193 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1194 store_.reserve(res_arg);
1197 void clear() { resize(0); }
1199 bool empty() const { return size() == 0; }
1201 // 21.3.4 element access:
1202 const_reference operator[](size_type pos) const {
1203 return *(c_str() + pos);
1206 reference operator[](size_type pos) {
1207 if (pos == size()) {
1208 // Just call c_str() to make sure '\0' is present
1211 return *(begin() + pos);
1214 const_reference at(size_type n) const {
1215 enforce(n <= size(), std::__throw_out_of_range, "");
1219 reference at(size_type n) {
1220 enforce(n < size(), std::__throw_out_of_range, "");
1224 // 21.3.5 modifiers:
1225 basic_fbstring& operator+=(const basic_fbstring& str) {
1229 basic_fbstring& operator+=(const value_type* s) {
1233 basic_fbstring& operator+=(const value_type c) {
1238 basic_fbstring& append(const basic_fbstring& str) {
1240 auto desiredSize = size() + str.size();
1242 append(str.data(), str.size());
1243 assert(size() == desiredSize);
1247 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1249 const size_type sz = str.size();
1250 enforce(pos <= sz, std::__throw_out_of_range, "");
1251 procrustes(n, sz - pos);
1252 return append(str.data() + pos, n);
1255 basic_fbstring& append(const value_type* s, size_type n) {
1257 Invariant checker(*this);
1261 // Unlikely but must be done
1264 auto const oldSize = size();
1265 auto const oldData = data();
1266 // Check for aliasing (rare). We could use "<=" here but in theory
1267 // those do not work for pointers unless the pointers point to
1268 // elements in the same array. For that reason we use
1269 // std::less_equal, which is guaranteed to offer a total order
1270 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1272 static const std::less_equal<const value_type*> le;
1273 if (UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1274 assert(le(s + n, oldData + oldSize));
1275 const size_type offset = s - oldData;
1276 store_.reserve(oldSize + n);
1277 // Restore the source
1278 s = data() + offset;
1280 // Warning! Repeated appends with short strings may actually incur
1281 // practically quadratic performance. Avoid that by pushing back
1282 // the first character (which ensures exponential growth) and then
1283 // appending the rest normally. Worst case the append may incur a
1284 // second allocation but that will be rare.
1287 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1288 assert(size() == oldSize + n + 1);
1292 basic_fbstring& append(const value_type* s) {
1293 return append(s, traits_type::length(s));
1296 basic_fbstring& append(size_type n, value_type c) {
1297 resize(size() + n, c);
1301 template<class InputIterator>
1302 basic_fbstring& append(InputIterator first, InputIterator last) {
1303 insert(end(), first, last);
1307 void push_back(const value_type c) { // primitive
1308 store_.push_back(c);
1311 basic_fbstring& assign(const basic_fbstring& str) {
1312 if (&str == this) return *this;
1313 return assign(str.data(), str.size());
1316 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1318 const size_type sz = str.size();
1319 enforce(pos <= sz, std::__throw_out_of_range, "");
1320 procrustes(n, sz - pos);
1321 return assign(str.data() + pos, n);
1324 basic_fbstring& assign(const value_type* s, const size_type n) {
1325 Invariant checker(*this);
1328 std::copy(s, s + n, begin());
1330 assert(size() == n);
1332 const value_type *const s2 = s + size();
1333 std::copy(s, s2, begin());
1334 append(s2, n - size());
1335 assert(size() == n);
1337 store_.writeTerminator();
1338 assert(size() == n);
1342 basic_fbstring& assign(const value_type* s) {
1343 return assign(s, traits_type::length(s));
1346 template <class ItOrLength, class ItOrChar>
1347 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1348 return replace(begin(), end(), first_or_n, last_or_c);
1351 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1352 return insert(pos1, str.data(), str.size());
1355 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1356 size_type pos2, size_type n) {
1357 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1358 procrustes(n, str.length() - pos2);
1359 return insert(pos1, str.data() + pos2, n);
1362 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1363 enforce(pos <= length(), std::__throw_out_of_range, "");
1364 insert(begin() + pos, s, s + n);
1368 basic_fbstring& insert(size_type pos, const value_type* s) {
1369 return insert(pos, s, traits_type::length(s));
1372 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1373 enforce(pos <= length(), std::__throw_out_of_range, "");
1374 insert(begin() + pos, n, c);
1378 iterator insert(const iterator p, const value_type c) {
1379 const size_type pos = p - begin();
1381 return begin() + pos;
1385 template <int i> class Selector {};
1387 basic_fbstring& insertImplDiscr(iterator p,
1388 size_type n, value_type c, Selector<1>) {
1389 Invariant checker(*this);
1391 assert(p >= begin() && p <= end());
1392 if (capacity() - size() < n) {
1393 const size_type sz = p - begin();
1394 reserve(size() + n);
1397 const iterator oldEnd = end();
1398 if( n < size_type(oldEnd - p)) {
1399 append(oldEnd - n, oldEnd);
1401 // reverse_iterator(oldEnd - n),
1402 // reverse_iterator(p),
1403 // reverse_iterator(oldEnd));
1404 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1405 std::fill(p, p + n, c);
1407 append(n - (end() - p), c);
1409 std::fill(p, oldEnd, c);
1411 store_.writeTerminator();
1415 template<class InputIter>
1416 basic_fbstring& insertImplDiscr(iterator i,
1417 InputIter b, InputIter e, Selector<0>) {
1419 typename std::iterator_traits<InputIter>::iterator_category());
1423 template <class FwdIterator>
1424 void insertImpl(iterator i,
1425 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1426 Invariant checker(*this);
1428 const size_type pos = i - begin();
1429 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1430 std::distance(s1, s2);
1432 using namespace fbstring_detail;
1433 assert(pos <= size());
1435 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1436 capacity() - size();
1438 // realloc the string
1439 reserve(size() + n2);
1442 if (pos + n2 <= size()) {
1443 const iterator tailBegin = end() - n2;
1444 store_.expand_noinit(n2);
1445 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1446 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1447 reverse_iterator(tailBegin + n2));
1448 std::copy(s1, s2, i);
1451 const size_type old_size = size();
1452 std::advance(t, old_size - pos);
1453 const size_t newElems = std::distance(t, s2);
1454 store_.expand_noinit(n2);
1455 std::copy(t, s2, begin() + old_size);
1456 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1457 begin() + old_size + newElems);
1458 std::copy(s1, t, i);
1460 store_.writeTerminator();
1463 template <class InputIterator>
1464 void insertImpl(iterator i,
1465 InputIterator b, InputIterator e, std::input_iterator_tag) {
1466 basic_fbstring temp(begin(), i);
1467 for (; b != e; ++b) {
1470 temp.append(i, end());
1475 template <class ItOrLength, class ItOrChar>
1476 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1477 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1478 insertImplDiscr(p, first_or_n, last_or_c, sel);
1481 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1482 Invariant checker(*this);
1484 enforce(pos <= length(), std::__throw_out_of_range, "");
1485 procrustes(n, length() - pos);
1486 std::copy(begin() + pos + n, end(), begin() + pos);
1487 resize(length() - n);
1491 iterator erase(iterator position) {
1492 const size_type pos(position - begin());
1493 enforce(pos <= size(), std::__throw_out_of_range, "");
1495 return begin() + pos;
1498 iterator erase(iterator first, iterator last) {
1499 const size_type pos(first - begin());
1500 erase(pos, last - first);
1501 return begin() + pos;
1504 // Replaces at most n1 chars of *this, starting with pos1 with the
1506 basic_fbstring& replace(size_type pos1, size_type n1,
1507 const basic_fbstring& str) {
1508 return replace(pos1, n1, str.data(), str.size());
1511 // Replaces at most n1 chars of *this, starting with pos1,
1512 // with at most n2 chars of str starting with pos2
1513 basic_fbstring& replace(size_type pos1, size_type n1,
1514 const basic_fbstring& str,
1515 size_type pos2, size_type n2) {
1516 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1517 return replace(pos1, n1, str.data() + pos2,
1518 std::min(n2, str.size() - pos2));
1521 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1522 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1523 return replace(pos, n1, s, traits_type::length(s));
1526 // Replaces at most n1 chars of *this, starting with pos, with n2
1529 // consolidated with
1531 // Replaces at most n1 chars of *this, starting with pos, with at
1532 // most n2 chars of str. str must have at least n2 chars.
1533 template <class StrOrLength, class NumOrChar>
1534 basic_fbstring& replace(size_type pos, size_type n1,
1535 StrOrLength s_or_n2, NumOrChar n_or_c) {
1536 Invariant checker(*this);
1538 enforce(pos <= size(), std::__throw_out_of_range, "");
1539 procrustes(n1, length() - pos);
1540 const iterator b = begin() + pos;
1541 return replace(b, b + n1, s_or_n2, n_or_c);
1544 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1545 return replace(i1, i2, str.data(), str.length());
1548 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1549 return replace(i1, i2, s, traits_type::length(s));
1553 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1554 const value_type* s, size_type n,
1557 assert(begin() <= i1 && i1 <= end());
1558 assert(begin() <= i2 && i2 <= end());
1559 return replace(i1, i2, s, s + n);
1562 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1563 size_type n2, value_type c, Selector<1>) {
1564 const size_type n1 = i2 - i1;
1566 std::fill(i1, i1 + n2, c);
1569 std::fill(i1, i2, c);
1570 insert(i2, n2 - n1, c);
1576 template <class InputIter>
1577 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1578 InputIter b, InputIter e,
1580 replaceImpl(i1, i2, b, e,
1581 typename std::iterator_traits<InputIter>::iterator_category());
1586 template <class FwdIterator, class P>
1587 bool replaceAliased(iterator i1, iterator i2,
1588 FwdIterator s1, FwdIterator s2, P*) {
1592 template <class FwdIterator>
1593 bool replaceAliased(iterator i1, iterator i2,
1594 FwdIterator s1, FwdIterator s2, value_type*) {
1595 static const std::less_equal<const value_type*> le =
1596 std::less_equal<const value_type*>();
1597 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1601 // Aliased replace, copy to new string
1602 basic_fbstring temp;
1603 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1604 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1610 template <class FwdIterator>
1611 void replaceImpl(iterator i1, iterator i2,
1612 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1613 Invariant checker(*this);
1616 // Handle aliased replace
1617 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1621 auto const n1 = i2 - i1;
1623 auto const n2 = std::distance(s1, s2);
1628 std::copy(s1, s2, i1);
1632 fbstring_detail::copy_n(s1, n1, i1);
1633 std::advance(s1, n1);
1639 template <class InputIterator>
1640 void replaceImpl(iterator i1, iterator i2,
1641 InputIterator b, InputIterator e, std::input_iterator_tag) {
1642 basic_fbstring temp(begin(), i1);
1643 temp.append(b, e).append(i2, end());
1648 template <class T1, class T2>
1649 basic_fbstring& replace(iterator i1, iterator i2,
1650 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1652 num1 = std::numeric_limits<T1>::is_specialized,
1653 num2 = std::numeric_limits<T2>::is_specialized;
1654 return replaceImplDiscr(
1655 i1, i2, first_or_n_or_s, last_or_c_or_n,
1656 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1659 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1660 enforce(pos <= size(), std::__throw_out_of_range, "");
1661 procrustes(n, size() - pos);
1663 fbstring_detail::pod_copy(
1670 void swap(basic_fbstring& rhs) {
1671 store_.swap(rhs.store_);
1674 // 21.3.6 string operations:
1675 const value_type* c_str() const {
1676 return store_.c_str();
1679 const value_type* data() const { return c_str(); }
1681 allocator_type get_allocator() const {
1682 return allocator_type();
1685 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1686 return find(str.data(), pos, str.length());
1689 size_type find(const value_type* needle, const size_type pos,
1690 const size_type nsize) const {
1691 if (!nsize) return pos;
1692 auto const size = this->size();
1693 if (nsize + pos > size) return npos;
1694 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1695 // the last characters first
1696 auto const haystack = data();
1697 auto const nsize_1 = nsize - 1;
1698 auto const lastNeedle = needle[nsize_1];
1700 // Boyer-Moore skip value for the last char in the needle. Zero is
1701 // not a valid value; skip will be computed the first time it's
1705 const E * i = haystack + pos;
1706 auto iEnd = haystack + size - nsize_1;
1709 // Boyer-Moore: match the last element in the needle
1710 while (i[nsize_1] != lastNeedle) {
1716 // Here we know that the last char matches
1717 // Continue in pedestrian mode
1718 for (size_t j = 0; ; ) {
1720 if (i[j] != needle[j]) {
1721 // Not found, we can skip
1722 // Compute the skip value lazily
1725 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1732 // Check if done searching
1735 return i - haystack;
1742 size_type find(const value_type* s, size_type pos = 0) const {
1743 return find(s, pos, traits_type::length(s));
1746 size_type find (value_type c, size_type pos = 0) const {
1747 return find(&c, pos, 1);
1750 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1751 return rfind(str.data(), pos, str.length());
1754 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1755 if (n > length()) return npos;
1756 pos = std::min(pos, length() - n);
1757 if (n == 0) return pos;
1759 const_iterator i(begin() + pos);
1761 if (traits_type::eq(*i, *s)
1762 && traits_type::compare(&*i, s, n) == 0) {
1765 if (i == begin()) break;
1770 size_type rfind(const value_type* s, size_type pos = npos) const {
1771 return rfind(s, pos, traits_type::length(s));
1774 size_type rfind(value_type c, size_type pos = npos) const {
1775 return rfind(&c, pos, 1);
1778 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1779 return find_first_of(str.data(), pos, str.length());
1782 size_type find_first_of(const value_type* s,
1783 size_type pos, size_type n) const {
1784 if (pos > length() || n == 0) return npos;
1785 const_iterator i(begin() + pos),
1787 for (; i != finish; ++i) {
1788 if (traits_type::find(s, n, *i) != 0) {
1795 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1796 return find_first_of(s, pos, traits_type::length(s));
1799 size_type find_first_of(value_type c, size_type pos = 0) const {
1800 return find_first_of(&c, pos, 1);
1803 size_type find_last_of (const basic_fbstring& str,
1804 size_type pos = npos) const {
1805 return find_last_of(str.data(), pos, str.length());
1808 size_type find_last_of (const value_type* s, size_type pos,
1809 size_type n) const {
1810 if (!empty() && n > 0) {
1811 pos = std::min(pos, length() - 1);
1812 const_iterator i(begin() + pos);
1814 if (traits_type::find(s, n, *i) != 0) {
1817 if (i == begin()) break;
1823 size_type find_last_of (const value_type* s,
1824 size_type pos = npos) const {
1825 return find_last_of(s, pos, traits_type::length(s));
1828 size_type find_last_of (value_type c, size_type pos = npos) const {
1829 return find_last_of(&c, pos, 1);
1832 size_type find_first_not_of(const basic_fbstring& str,
1833 size_type pos = 0) const {
1834 return find_first_not_of(str.data(), pos, str.size());
1837 size_type find_first_not_of(const value_type* s, size_type pos,
1838 size_type n) const {
1839 if (pos < length()) {
1843 for (; i != finish; ++i) {
1844 if (traits_type::find(s, n, *i) == 0) {
1852 size_type find_first_not_of(const value_type* s,
1853 size_type pos = 0) const {
1854 return find_first_not_of(s, pos, traits_type::length(s));
1857 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1858 return find_first_not_of(&c, pos, 1);
1861 size_type find_last_not_of(const basic_fbstring& str,
1862 size_type pos = npos) const {
1863 return find_last_not_of(str.data(), pos, str.length());
1866 size_type find_last_not_of(const value_type* s, size_type pos,
1867 size_type n) const {
1868 if (!this->empty()) {
1869 pos = std::min(pos, size() - 1);
1870 const_iterator i(begin() + pos);
1872 if (traits_type::find(s, n, *i) == 0) {
1875 if (i == begin()) break;
1881 size_type find_last_not_of(const value_type* s,
1882 size_type pos = npos) const {
1883 return find_last_not_of(s, pos, traits_type::length(s));
1886 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1887 return find_last_not_of(&c, pos, 1);
1890 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1891 enforce(pos <= size(), std::__throw_out_of_range, "");
1892 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1895 int compare(const basic_fbstring& str) const {
1896 // FIX due to Goncalo N M de Carvalho July 18, 2005
1897 return compare(0, size(), str);
1900 int compare(size_type pos1, size_type n1,
1901 const basic_fbstring& str) const {
1902 return compare(pos1, n1, str.data(), str.size());
1905 int compare(size_type pos1, size_type n1,
1906 const value_type* s) const {
1907 return compare(pos1, n1, s, traits_type::length(s));
1910 int compare(size_type pos1, size_type n1,
1911 const value_type* s, size_type n2) const {
1912 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1913 procrustes(n1, size() - pos1);
1914 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1915 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1916 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1919 int compare(size_type pos1, size_type n1,
1920 const basic_fbstring& str,
1921 size_type pos2, size_type n2) const {
1922 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1923 return compare(pos1, n1, str.data() + pos2,
1924 std::min(n2, str.size() - pos2));
1927 // Code from Jean-Francois Bastien (03/26/2007)
1928 int compare(const value_type* s) const {
1929 // Could forward to compare(0, size(), s, traits_type::length(s))
1930 // but that does two extra checks
1931 const size_type n1(size()), n2(traits_type::length(s));
1932 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1933 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1941 // non-member functions
1943 template <typename E, class T, class A, class S>
1945 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1946 const basic_fbstring<E, T, A, S>& rhs) {
1948 basic_fbstring<E, T, A, S> result;
1949 result.reserve(lhs.size() + rhs.size());
1950 result.append(lhs).append(rhs);
1951 return std::move(result);
1955 template <typename E, class T, class A, class S>
1957 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1958 const basic_fbstring<E, T, A, S>& rhs) {
1959 return std::move(lhs.append(rhs));
1963 template <typename E, class T, class A, class S>
1965 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1966 basic_fbstring<E, T, A, S>&& rhs) {
1967 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1968 // Good, at least we don't need to reallocate
1969 return std::move(rhs.insert(0, lhs));
1971 // Meh, no go. Forward to operator+(const&, const&).
1972 auto const& rhsC = rhs;
1977 template <typename E, class T, class A, class S>
1979 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1980 basic_fbstring<E, T, A, S>&& rhs) {
1981 return std::move(lhs.append(rhs));
1984 template <typename E, class T, class A, class S>
1986 basic_fbstring<E, T, A, S> operator+(
1987 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
1988 const basic_fbstring<E, T, A, S>& rhs) {
1990 basic_fbstring<E, T, A, S> result;
1991 const typename basic_fbstring<E, T, A, S>::size_type len =
1992 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
1993 result.reserve(len + rhs.size());
1994 result.append(lhs, len).append(rhs);
1998 template <typename E, class T, class A, class S>
2000 basic_fbstring<E, T, A, S> operator+(
2001 typename basic_fbstring<E, T, A, S>::value_type lhs,
2002 const basic_fbstring<E, T, A, S>& rhs) {
2004 basic_fbstring<E, T, A, S> result;
2005 result.reserve(1 + rhs.size());
2006 result.push_back(lhs);
2011 template <typename E, class T, class A, class S>
2013 basic_fbstring<E, T, A, S> operator+(
2014 const basic_fbstring<E, T, A, S>& lhs,
2015 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2017 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2018 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2020 basic_fbstring<E, T, A, S> result;
2021 const size_type len = traits_type::length(rhs);
2022 result.reserve(lhs.size() + len);
2023 result.append(lhs).append(rhs, len);
2027 template <typename E, class T, class A, class S>
2029 basic_fbstring<E, T, A, S> operator+(
2030 const basic_fbstring<E, T, A, S>& lhs,
2031 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2033 basic_fbstring<E, T, A, S> result;
2034 result.reserve(lhs.size() + 1);
2036 result.push_back(rhs);
2040 template <typename E, class T, class A, class S>
2042 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2043 const basic_fbstring<E, T, A, S>& rhs) {
2044 return lhs.compare(rhs) == 0; }
2046 template <typename E, class T, class A, class S>
2048 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2049 const basic_fbstring<E, T, A, S>& rhs) {
2050 return rhs == lhs; }
2052 template <typename E, class T, class A, class S>
2054 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2055 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2056 return lhs.compare(rhs) == 0; }
2058 template <typename E, class T, class A, class S>
2060 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2061 const basic_fbstring<E, T, A, S>& rhs) {
2062 return !(lhs == rhs); }
2064 template <typename E, class T, class A, class S>
2066 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2067 const basic_fbstring<E, T, A, S>& rhs) {
2068 return !(lhs == rhs); }
2070 template <typename E, class T, class A, class S>
2072 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2073 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2074 return !(lhs == rhs); }
2076 template <typename E, class T, class A, class S>
2078 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2079 const basic_fbstring<E, T, A, S>& rhs) {
2080 return lhs.compare(rhs) < 0; }
2082 template <typename E, class T, class A, class S>
2084 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2085 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2086 return lhs.compare(rhs) < 0; }
2088 template <typename E, class T, class A, class S>
2090 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2091 const basic_fbstring<E, T, A, S>& rhs) {
2092 return rhs.compare(lhs) > 0; }
2094 template <typename E, class T, class A, class S>
2096 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2097 const basic_fbstring<E, T, A, S>& rhs) {
2100 template <typename E, class T, class A, class S>
2102 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2103 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2106 template <typename E, class T, class A, class S>
2108 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2109 const basic_fbstring<E, T, A, S>& rhs) {
2112 template <typename E, class T, class A, class S>
2114 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2115 const basic_fbstring<E, T, A, S>& rhs) {
2116 return !(rhs < lhs); }
2118 template <typename E, class T, class A, class S>
2120 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2121 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2122 return !(rhs < lhs); }
2124 template <typename E, class T, class A, class S>
2126 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2127 const basic_fbstring<E, T, A, S>& rhs) {
2128 return !(rhs < lhs); }
2130 template <typename E, class T, class A, class S>
2132 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2133 const basic_fbstring<E, T, A, S>& rhs) {
2134 return !(lhs < rhs); }
2136 template <typename E, class T, class A, class S>
2138 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2139 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2140 return !(lhs < rhs); }
2142 template <typename E, class T, class A, class S>
2144 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2145 const basic_fbstring<E, T, A, S>& rhs) {
2146 return !(lhs < rhs);
2149 // subclause 21.3.7.8:
2150 template <typename E, class T, class A, class S>
2151 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2155 // TODO: make this faster.
2156 template <typename E, class T, class A, class S>
2159 typename basic_fbstring<E, T, A, S>::value_type,
2160 typename basic_fbstring<E, T, A, S>::traits_type>&
2162 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2163 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2164 basic_fbstring<E, T, A, S>& str) {
2165 typename std::basic_istream<E, T>::sentry sentry(is);
2166 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2167 typename basic_fbstring<E, T, A, S>::traits_type>
2169 typedef typename __istream_type::ios_base __ios_base;
2170 size_t extracted = 0;
2171 auto err = __ios_base::goodbit;
2173 auto n = is.width();
2178 auto got = is.rdbuf()->sgetc();
2179 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2180 // Whew. We get to store this guy
2182 got = is.rdbuf()->snextc();
2184 if (got == T::eof()) {
2185 err |= __ios_base::eofbit;
2190 err |= __ios_base::failbit;
2198 template <typename E, class T, class A, class S>
2200 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2201 typename basic_fbstring<E, T, A, S>::traits_type>&
2203 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2204 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2205 const basic_fbstring<E, T, A, S>& str) {
2206 os.write(str.data(), str.size());
2210 #ifndef _LIBSTDCXX_FBSTRING
2212 template <typename E, class T, class A, class S>
2214 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2215 typename basic_fbstring<E, T, A, S>::traits_type>&
2217 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2218 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2219 basic_fbstring<E, T, A, S>& str,
2220 typename basic_fbstring<E, T, A, S>::value_type delim) {
2221 // Use the nonstandard getdelim()
2225 // This looks quadratic but it really depends on realloc
2226 auto const newSize = size + 128;
2227 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2228 is.getline(buf + size, newSize - size, delim);
2229 if (is.bad() || is.eof() || !is.fail()) {
2230 // done by either failure, end of file, or normal read
2231 size += std::strlen(buf + size);
2234 // Here we have failed due to too short a buffer
2235 // Minus one to discount the terminating '\0'
2237 assert(buf[size] == 0);
2238 // Clear the error so we can continue reading
2241 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2242 AcquireMallocatedString());
2247 template <typename E, class T, class A, class S>
2249 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2250 typename basic_fbstring<E, T, A, S>::traits_type>&
2252 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2253 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2254 basic_fbstring<E, T, A, S>& str) {
2255 // Just forward to the version with a delimiter
2256 return getline(is, str, '\n');
2261 template <typename E1, class T, class A, class S>
2262 const typename basic_fbstring<E1, T, A, S>::size_type
2263 basic_fbstring<E1, T, A, S>::npos =
2264 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2266 #ifndef _LIBSTDCXX_FBSTRING
2267 // basic_string compatibility routines
2269 template <typename E, class T, class A, class S>
2271 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2272 const std::string& rhs) {
2273 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2276 template <typename E, class T, class A, class S>
2278 bool operator==(const std::string& lhs,
2279 const basic_fbstring<E, T, A, S>& rhs) {
2283 template <typename E, class T, class A, class S>
2285 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2286 const std::string& rhs) {
2287 return !(lhs == rhs);
2290 template <typename E, class T, class A, class S>
2292 bool operator!=(const std::string& lhs,
2293 const basic_fbstring<E, T, A, S>& rhs) {
2294 return !(lhs == rhs);
2297 #if !defined(_LIBSTDCXX_FBSTRING)
2298 typedef basic_fbstring<char> fbstring;
2301 // fbstring is relocatable
2302 template <class T, class R, class A, class S>
2303 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2306 _GLIBCXX_END_NAMESPACE_VERSION
2309 } // namespace folly
2311 #ifndef _LIBSTDCXX_FBSTRING
2315 struct hash< ::folly::fbstring> {
2316 size_t operator()(const ::folly::fbstring& s) const {
2317 return ::folly::hash::fnv32_buf(s.data(), s.size());
2322 #endif // _LIBSTDCXX_FBSTRING
2324 #endif // FOLLY_BASE_FBSTRING_H_