2 * Copyright 2013 Facebook, Inc.
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
8 * http://www.apache.org/licenses/LICENSE-2.0
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
17 // @author: Andrei Alexandrescu (aalexandre)
20 #ifndef FOLLY_BASE_FBSTRING_H_
21 #define FOLLY_BASE_FBSTRING_H_
24 fbstring's behavior can be configured via two macro definitions, as
25 follows. Normally, fbstring does not write a '\0' at the end of
26 each string whenever it changes the underlying characters. Instead,
27 it lazily writes the '\0' whenever either c_str() or data()
30 This is standard-compliant behavior and may save costs in some
31 circumstances. However, it may be surprising to some client code
32 because c_str() and data() are const member functions (fbstring
33 uses the "mutable" storage class for its own state).
35 In order to appease client code that expects fbstring to be
36 zero-terminated at all times, if the preprocessor symbol
37 FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
38 i.e. it goes the extra mile to guarantee a '\0' is always planted
39 at the end of its data.
41 On the contrary, if the desire is to debug faulty client code that
42 unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
43 emphatically NOT a zero) at the end of each string if
44 FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
45 writes the '\0', of course.)
47 The preprocessor symbols FBSTRING_PERVERSE and
48 FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
49 enforced during preprocessing.
52 //#define FBSTRING_PERVERSE
53 //#define FBSTRING_CONSERVATIVE
55 #ifdef FBSTRING_PERVERSE
56 #ifdef FBSTRING_CONSERVATIVE
57 #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
61 // This file appears in two locations: inside fbcode and in the
62 // libstdc++ source code (when embedding fbstring as std::string).
63 // To aid in this schizophrenic use, two macros are defined in
65 // _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
66 // gate use inside fbcode v. libstdc++
67 #include <bits/c++config.h>
69 #ifdef _LIBSTDCXX_FBSTRING
71 #pragma GCC system_header
73 // Handle the cases where the fbcode version (folly/Malloc.h) is included
74 // either before or after this inclusion.
75 #ifdef FOLLY_MALLOC_H_
76 #undef FOLLY_MALLOC_H_
77 #include "basic_fbstring_malloc.h"
79 #include "basic_fbstring_malloc.h"
80 #undef FOLLY_MALLOC_H_
83 #else // !_LIBSTDCXX_FBSTRING
89 #include "folly/Traits.h"
90 #include "folly/Malloc.h"
91 #include "folly/Hash.h"
95 // We defined these here rather than including Likely.h to avoid
96 // redefinition errors when fbstring is imported into libstdc++.
97 #define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
98 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
102 #include <type_traits>
104 #ifdef _LIBSTDCXX_FBSTRING
105 namespace std _GLIBCXX_VISIBILITY(default) {
106 _GLIBCXX_BEGIN_NAMESPACE_VERSION
111 namespace fbstring_detail {
113 template <class InIt, class OutIt>
116 typename std::iterator_traits<InIt>::difference_type n,
118 for (; n != 0; --n, ++b, ++d) {
119 assert((const void*)&*d != &*b);
125 template <class Pod, class T>
126 inline void pod_fill(Pod* b, Pod* e, T c) {
127 assert(b && e && b <= e);
128 /*static*/ if (sizeof(T) == 1) {
131 auto const ee = b + ((e - b) & ~7u);
132 for (; b != ee; b += 8) {
143 for (; b != e; ++b) {
150 * Lightly structured memcpy, simplifies copying PODs and introduces
151 * some asserts. Unfortunately using this function may cause
152 * measurable overhead (presumably because it adjusts from a begin/end
153 * convention to a pointer/size convention, so it does some extra
154 * arithmetic even though the caller might have done the inverse
155 * adaptation outside).
158 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
160 assert(d >= e || d + (e - b) <= b);
161 memcpy(d, b, (e - b) * sizeof(Pod));
165 * Lightly structured memmove, simplifies copying PODs and introduces
169 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
171 memmove(d, b, (e - b) * sizeof(*b));
174 } // namespace fbstring_detail
177 * Defines a special acquisition method for constructing fbstring
178 * objects. AcquireMallocatedString means that the user passes a
179 * pointer to a malloc-allocated string that the fbstring object will
182 enum class AcquireMallocatedString {};
185 * fbstring_core_model is a mock-up type that defines all required
186 * signatures of a fbstring core. The fbstring class itself uses such
187 * a core object to implement all of the numerous member functions
188 * required by the standard.
190 * If you want to define a new core, copy the definition below and
191 * implement the primitives. Then plug the core into basic_fbstring as
192 * a template argument.
194 template <class Char>
195 class fbstring_core_model {
197 fbstring_core_model();
198 fbstring_core_model(const fbstring_core_model &);
199 ~fbstring_core_model();
200 // Returns a pointer to string's buffer (currently only contiguous
201 // strings are supported). The pointer is guaranteed to be valid
202 // until the next call to a non-const member function.
203 const Char * data() const;
204 // Much like data(), except the string is prepared to support
205 // character-level changes. This call is a signal for
206 // e.g. reference-counted implementation to fork the data. The
207 // pointer is guaranteed to be valid until the next call to a
208 // non-const member function.
209 Char * mutable_data();
210 // Returns a pointer to string's buffer and guarantees that a
211 // readable '\0' lies right after the buffer. The pointer is
212 // guaranteed to be valid until the next call to a non-const member
214 const Char * c_str() const;
215 // Shrinks the string by delta characters. Asserts that delta <=
217 void shrink(size_t delta);
218 // Expands the string by delta characters (i.e. after this call
219 // size() will report the old size() plus delta) but without
220 // initializing the expanded region. Returns a pointer to the memory
221 // to be initialized (the beginning of the expanded portion). The
222 // caller is expected to fill the expanded area appropriately.
223 Char* expand_noinit(size_t delta);
224 // Expands the string by one character and sets the last character
226 void push_back(Char c);
227 // Returns the string's size.
229 // Returns the string's capacity, i.e. maximum size that the string
230 // can grow to without reallocation. Note that for reference counted
231 // strings that's technically a lie - even assigning characters
232 // within the existing size would cause a reallocation.
233 size_t capacity() const;
234 // Returns true if the data underlying the string is actually shared
235 // across multiple strings (in a refcounted fashion).
236 bool isShared() const;
237 // Makes sure that at least minCapacity characters are available for
238 // the string without reallocation. For reference-counted strings,
239 // it should fork the data even if minCapacity < size().
240 void reserve(size_t minCapacity);
243 fbstring_core_model& operator=(const fbstring_core_model &);
248 * gcc-4.7 throws what appears to be some false positive uninitialized
249 * warnings for the members of the MediumLarge struct. So, mute them here.
251 #if defined(__GNUC__) && !defined(__clang__)
252 # pragma GCC diagnostic push
253 # pragma GCC diagnostic ignored "-Wuninitialized"
257 * This is the core of the string. The code should work on 32- and
258 * 64-bit architectures and with any Char size. Porting to big endian
259 * architectures would require some changes.
261 * The storage is selected as follows (assuming we store one-byte
262 * characters on a 64-bit machine): (a) "small" strings between 0 and
263 * 23 chars are stored in-situ without allocation (the rightmost byte
264 * stores the size); (b) "medium" strings from 24 through 254 chars
265 * are stored in malloc-allocated memory that is copied eagerly; (c)
266 * "large" strings of 255 chars and above are stored in a similar
267 * structure as medium arrays, except that the string is
268 * reference-counted and copied lazily. the reference count is
269 * allocated right before the character array.
271 * The discriminator between these three strategies sits in the two
272 * most significant bits of the rightmost char of the storage. If
273 * neither is set, then the string is small (and its length sits in
274 * the lower-order bits of that rightmost character). If the MSb is
275 * set, the string is medium width. If the second MSb is set, then the
278 template <class Char> class fbstring_core {
281 // Only initialize the tag, will set the MSBs (i.e. the small
282 // string size) to zero too
283 ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
284 // or: setSmallSize(0);
286 assert(category() == isSmall && size() == 0);
289 fbstring_core(const fbstring_core & rhs) {
290 assert(&rhs != this);
291 // Simplest case first: small strings are bitblitted
292 if (rhs.category() == isSmall) {
293 assert(offsetof(MediumLarge, data_) == 0);
294 assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
295 assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
296 const size_t size = rhs.smallSize();
298 ml_.capacity_ = rhs.ml_.capacity_;
301 // Just write the whole thing, don't look at details. In
302 // particular we need to copy capacity anyway because we want
303 // to set the size (don't forget that the last character,
304 // which stores a short string's length, is shared with the
305 // ml_.capacity field).
308 assert(category() == isSmall && this->size() == rhs.size());
309 } else if (rhs.category() == isLarge) {
310 // Large strings are just refcounted
312 RefCounted::incrementRefs(ml_.data_);
313 assert(category() == isLarge && size() == rhs.size());
315 // Medium strings are copied eagerly. Don't forget to allocate
316 // one extra Char for the null terminator.
317 auto const allocSize =
318 goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
319 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
320 fbstring_detail::pod_copy(rhs.ml_.data_,
322 rhs.ml_.data_ + rhs.ml_.size_ + 1,
324 // No need for writeTerminator() here, we copied one extra
325 // element just above.
326 ml_.size_ = rhs.ml_.size_;
327 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
328 assert(category() == isMedium);
330 assert(size() == rhs.size());
331 assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
334 fbstring_core(fbstring_core&& goner) {
335 if (goner.category() == isSmall) {
336 // Just copy, leave the goner in peace
337 new(this) fbstring_core(goner.small_, goner.smallSize());
341 // Clean goner's carcass
342 goner.setSmallSize(0);
346 fbstring_core(const Char *const data, const size_t size) {
347 // Simplest case first: small strings are bitblitted
348 if (size <= maxSmallSize) {
349 // Layout is: Char* data_, size_t size_, size_t capacity_
350 /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
351 /*static_*/assert(sizeof(Char*) == sizeof(size_t));
352 // sizeof(size_t) must be a power of 2
353 /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
355 // If data is aligned, use fast word-wise copying. Otherwise,
356 // use conservative memcpy.
357 if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
358 fbstring_detail::pod_copy(data, data + size, small_);
360 // Copy one word (64 bits) at a time
361 const size_t byteSize = size * sizeof(Char);
362 if (byteSize > 2 * sizeof(size_t)) {
364 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
366 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
368 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
369 } else if (byteSize > sizeof(size_t)) {
372 } else if (size > 0) {
378 } else if (size <= maxMediumSize) {
379 // Medium strings are allocated normally. Don't forget to
380 // allocate one extra Char for the terminating null.
381 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
382 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
383 fbstring_detail::pod_copy(data, data + size, ml_.data_);
385 ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
387 // Large strings are allocated differently
388 size_t effectiveCapacity = size;
389 auto const newRC = RefCounted::create(data, & effectiveCapacity);
390 ml_.data_ = newRC->data_;
392 ml_.capacity_ = effectiveCapacity | isLarge;
395 assert(this->size() == size);
396 assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
400 auto const c = category();
408 RefCounted::decrementRefs(ml_.data_);
411 // Snatches a previously mallocated string. The parameter "size"
412 // is the size of the string, and the parameter "capacity" is the size
413 // of the mallocated block. The string must be \0-terminated, so
414 // data[size] == '\0' and capacity >= size + 1.
416 // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
417 // "size", and pass 3 as "capacity".
418 fbstring_core(Char *const data, const size_t size,
419 const size_t capacity,
420 AcquireMallocatedString) {
422 assert(capacity > size);
423 assert(data[size] == '\0');
424 // Use the medium string storage
427 ml_.capacity_ = capacity | isMedium;
429 // No need for the memory
435 // swap below doesn't test whether &rhs == this (and instead
436 // potentially does extra work) on the premise that the rarity of
437 // that situation actually makes the check more expensive than is
439 void swap(fbstring_core & rhs) {
445 // In C++11 data() and c_str() are 100% equivalent.
446 const Char * data() const {
450 Char * mutable_data() {
451 auto const c = category();
455 assert(c == isMedium || c == isLarge);
456 if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
458 size_t effectiveCapacity = ml_.capacity();
459 auto const newRC = RefCounted::create(& effectiveCapacity);
460 // If this fails, someone placed the wrong capacity in an
462 assert(effectiveCapacity >= ml_.capacity());
463 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
465 RefCounted::decrementRefs(ml_.data_);
466 ml_.data_ = newRC->data_;
467 // No need to call writeTerminator(), we have + 1 above.
472 const Char * c_str() const {
473 auto const c = category();
474 #ifdef FBSTRING_PERVERSE
476 assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
477 || small_[smallSize()] == '\0');
478 small_[smallSize()] = '\0';
481 assert(c == isMedium || c == isLarge);
482 assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
483 ml_.data_[ml_.size_] = '\0';
484 #elif defined(FBSTRING_CONSERVATIVE)
486 assert(small_[smallSize()] == '\0');
489 assert(c == isMedium || c == isLarge);
490 assert(ml_.data_[ml_.size_] == '\0');
493 small_[smallSize()] = '\0';
496 assert(c == isMedium || c == isLarge);
497 ml_.data_[ml_.size_] = '\0';
502 void shrink(const size_t delta) {
503 if (category() == isSmall) {
504 // Check for underflow
505 assert(delta <= smallSize());
506 setSmallSize(smallSize() - delta);
507 } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
508 // Medium strings and unique large strings need no special
510 assert(ml_.size_ >= delta);
513 assert(ml_.size_ >= delta);
514 // Shared large string, must make unique. This is because of the
515 // durn terminator must be written, which may trample the shared
518 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
520 // No need to write the terminator.
526 void reserve(size_t minCapacity) {
527 if (category() == isLarge) {
529 if (RefCounted::refs(ml_.data_) > 1) {
530 // We must make it unique regardless; in-place reallocation is
531 // useless if the string is shared. In order to not surprise
532 // people, reserve the new block at current capacity or
533 // more. That way, a string's capacity never shrinks after a
535 minCapacity = std::max(minCapacity, ml_.capacity());
536 auto const newRC = RefCounted::create(& minCapacity);
537 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
539 // Done with the old data. No need to call writeTerminator(),
540 // we have + 1 above.
541 RefCounted::decrementRefs(ml_.data_);
542 ml_.data_ = newRC->data_;
543 ml_.capacity_ = minCapacity | isLarge;
544 // size remains unchanged
546 // String is not shared, so let's try to realloc (if needed)
547 if (minCapacity > ml_.capacity()) {
548 // Asking for more memory
550 RefCounted::reallocate(ml_.data_, ml_.size_,
551 ml_.capacity(), minCapacity);
552 ml_.data_ = newRC->data_;
553 ml_.capacity_ = minCapacity | isLarge;
556 assert(capacity() >= minCapacity);
558 } else if (category() == isMedium) {
559 // String is not shared
560 if (minCapacity <= ml_.capacity()) {
561 return; // nothing to do, there's enough room
563 if (minCapacity <= maxMediumSize) {
564 // Keep the string at medium size. Don't forget to allocate
565 // one extra Char for the terminating null.
566 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
567 ml_.data_ = static_cast<Char *>(
570 ml_.size_ * sizeof(Char),
571 ml_.capacity() * sizeof(Char),
574 ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
576 // Conversion from medium to large string
577 fbstring_core nascent;
578 // Will recurse to another branch of this function
579 nascent.reserve(minCapacity);
580 nascent.ml_.size_ = ml_.size_;
581 fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
585 assert(capacity() >= minCapacity);
588 assert(category() == isSmall);
589 if (minCapacity > maxMediumSize) {
591 auto const newRC = RefCounted::create(& minCapacity);
592 auto const size = smallSize();
593 fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
594 // No need for writeTerminator(), we wrote it above with + 1.
595 ml_.data_ = newRC->data_;
597 ml_.capacity_ = minCapacity | isLarge;
598 assert(capacity() >= minCapacity);
599 } else if (minCapacity > maxSmallSize) {
601 // Don't forget to allocate one extra Char for the terminating null
602 auto const allocSizeBytes =
603 goodMallocSize((1 + minCapacity) * sizeof(Char));
604 auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
605 auto const size = smallSize();
606 fbstring_detail::pod_copy(small_, small_ + size + 1, data);
607 // No need for writeTerminator(), we wrote it above with + 1.
610 ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
613 // Nothing to do, everything stays put
616 assert(capacity() >= minCapacity);
619 Char * expand_noinit(const size_t delta) {
620 // Strategy is simple: make room, then change size
621 assert(capacity() >= size());
623 if (category() == isSmall) {
626 if (newSz <= maxSmallSize) {
634 newSz = ml_.size_ + delta;
635 if (newSz > capacity()) {
639 assert(capacity() >= newSz);
640 // Category can't be small - we took care of that above
641 assert(category() == isMedium || category() == isLarge);
644 assert(size() == newSz);
645 return ml_.data_ + sz;
648 void push_back(Char c) {
649 assert(capacity() >= size());
651 if (category() == isSmall) {
653 if (sz < maxSmallSize) {
654 setSmallSize(sz + 1);
659 reserve(maxSmallSize * 2);
662 if (sz == capacity()) { // always true for isShared()
663 reserve(sz * 3 / 2); // ensures not shared
667 assert(capacity() >= sz + 1);
668 // Category can't be small - we took care of that above
669 assert(category() == isMedium || category() == isLarge);
675 size_t size() const {
676 return category() == isSmall ? smallSize() : ml_.size_;
679 size_t capacity() const {
680 switch (category()) {
684 // For large-sized strings, a multi-referenced chunk has no
685 // available capacity. This is because any attempt to append
686 // data would trigger a new allocation.
687 if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
690 return ml_.capacity();
693 bool isShared() const {
694 return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
697 #ifdef FBSTRING_PERVERSE
698 enum { TERMINATOR = '^' };
700 enum { TERMINATOR = '\0' };
703 void writeTerminator() {
704 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
705 if (category() == isSmall) {
706 const auto s = smallSize();
707 if (s != maxSmallSize) {
708 small_[s] = TERMINATOR;
711 ml_.data_[ml_.size_] = TERMINATOR;
718 fbstring_core & operator=(const fbstring_core & rhs);
725 size_t capacity() const {
726 return capacity_ & capacityExtractMask;
731 std::atomic<size_t> refCount_;
734 static RefCounted * fromData(Char * p) {
735 return static_cast<RefCounted*>(
737 static_cast<unsigned char*>(static_cast<void*>(p))
738 - sizeof(refCount_)));
741 static size_t refs(Char * p) {
742 return fromData(p)->refCount_.load(std::memory_order_acquire);
745 static void incrementRefs(Char * p) {
746 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
749 static void decrementRefs(Char * p) {
750 auto const dis = fromData(p);
751 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
758 static RefCounted * create(size_t * size) {
759 // Don't forget to allocate one extra Char for the terminating
760 // null. In this case, however, one Char is already part of the
762 const size_t allocSize = goodMallocSize(
763 sizeof(RefCounted) + *size * sizeof(Char));
764 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
765 result->refCount_.store(1, std::memory_order_release);
766 *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
770 static RefCounted * create(const Char * data, size_t * size) {
771 const size_t effectiveSize = *size;
772 auto result = create(size);
773 fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
777 static RefCounted * reallocate(Char *const data,
778 const size_t currentSize,
779 const size_t currentCapacity,
780 const size_t newCapacity) {
781 assert(newCapacity > 0 && newCapacity > currentSize);
782 auto const dis = fromData(data);
783 assert(dis->refCount_.load(std::memory_order_acquire) == 1);
784 // Don't forget to allocate one extra Char for the terminating
785 // null. In this case, however, one Char is already part of the
787 auto result = static_cast<RefCounted*>(
789 sizeof(RefCounted) + currentSize * sizeof(Char),
790 sizeof(RefCounted) + currentCapacity * sizeof(Char),
791 sizeof(RefCounted) + newCapacity * sizeof(Char)));
792 assert(result->refCount_.load(std::memory_order_acquire) == 1);
798 mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
799 mutable MediumLarge ml_;
803 lastChar = sizeof(MediumLarge) - 1,
804 maxSmallSize = lastChar / sizeof(Char),
805 maxMediumSize = 254 / sizeof(Char), // coincides with the small
806 // bin size in dlmalloc
807 categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
808 capacityExtractMask = ~categoryExtractMask,
810 static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
811 "Corrupt memory layout for fbstring.");
815 isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
816 isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
819 Category category() const {
820 // Assumes little endian
821 return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
824 size_t smallSize() const {
825 assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
826 return static_cast<size_t>(maxSmallSize)
827 - static_cast<size_t>(small_[maxSmallSize]);
830 void setSmallSize(size_t s) {
831 // Warning: this should work with uninitialized strings too,
832 // so don't assume anything about the previous value of
833 // small_[maxSmallSize].
834 assert(s <= maxSmallSize);
835 small_[maxSmallSize] = maxSmallSize - s;
839 #if defined(__GNUC__) && !defined(__clang__)
840 # pragma GCC diagnostic pop
843 #ifndef _LIBSTDCXX_FBSTRING
845 * Dummy fbstring core that uses an actual std::string. This doesn't
846 * make any sense - it's just for testing purposes.
848 template <class Char>
849 class dummy_fbstring_core {
851 dummy_fbstring_core() {
853 dummy_fbstring_core(const dummy_fbstring_core& another)
854 : backend_(another.backend_) {
856 dummy_fbstring_core(const Char * s, size_t n)
859 void swap(dummy_fbstring_core & rhs) {
860 backend_.swap(rhs.backend_);
862 const Char * data() const {
863 return backend_.data();
865 Char * mutable_data() {
866 //assert(!backend_.empty());
867 return &*backend_.begin();
869 void shrink(size_t delta) {
870 assert(delta <= size());
871 backend_.resize(size() - delta);
873 Char * expand_noinit(size_t delta) {
874 auto const sz = size();
875 backend_.resize(size() + delta);
876 return backend_.data() + sz;
878 void push_back(Char c) {
879 backend_.push_back(c);
881 size_t size() const {
882 return backend_.size();
884 size_t capacity() const {
885 return backend_.capacity();
887 bool isShared() const {
890 void reserve(size_t minCapacity) {
891 backend_.reserve(minCapacity);
895 std::basic_string<Char> backend_;
897 #endif // !_LIBSTDCXX_FBSTRING
900 * This is the basic_string replacement. For conformity,
901 * basic_fbstring takes the same template parameters, plus the last
902 * one which is the core.
904 #ifdef _LIBSTDCXX_FBSTRING
905 template <typename E, class T, class A, class Storage>
907 template <typename E,
908 class T = std::char_traits<E>,
909 class A = std::allocator<E>,
910 class Storage = fbstring_core<E> >
912 class basic_fbstring {
916 void (*throw_exc)(const char*),
918 if (!condition) throw_exc(msg);
921 bool isSane() const {
924 empty() == (size() == 0) &&
925 empty() == (begin() == end()) &&
926 size() <= max_size() &&
927 capacity() <= max_size() &&
928 size() <= capacity() &&
929 (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
933 friend struct Invariant;
936 explicit Invariant(const basic_fbstring& s) : s_(s) {
943 const basic_fbstring& s_;
945 explicit Invariant(const basic_fbstring&) {}
947 Invariant& operator=(const Invariant&);
952 typedef T traits_type;
953 typedef typename traits_type::char_type value_type;
954 typedef A allocator_type;
955 typedef typename A::size_type size_type;
956 typedef typename A::difference_type difference_type;
958 typedef typename A::reference reference;
959 typedef typename A::const_reference const_reference;
960 typedef typename A::pointer pointer;
961 typedef typename A::const_pointer const_pointer;
964 typedef const E* const_iterator;
965 typedef std::reverse_iterator<iterator
966 #ifdef NO_ITERATOR_TRAITS
970 typedef std::reverse_iterator<const_iterator
971 #ifdef NO_ITERATOR_TRAITS
974 > const_reverse_iterator;
976 static const size_type npos; // = size_type(-1)
979 static void procrustes(size_type& n, size_type nmax) {
980 if (n > nmax) n = nmax;
984 // 21.3.1 construct/copy/destroy
985 explicit basic_fbstring(const A& a = A()) {
988 basic_fbstring(const basic_fbstring& str)
989 : store_(str.store_) {
993 basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
996 #ifndef _LIBSTDCXX_FBSTRING
997 // This is defined for compatibility with std::string
998 /* implicit */ basic_fbstring(const std::string& str)
999 : store_(str.data(), str.size()) {
1003 basic_fbstring(const basic_fbstring& str, size_type pos,
1004 size_type n = npos, const A& a = A()) {
1005 assign(str, pos, n);
1008 /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1009 : store_(s, s ? traits_type::length(s) : ({
1010 basic_fbstring<char> err = __PRETTY_FUNCTION__;
1011 err += ": null pointer initializer not valid";
1012 std::__throw_logic_error(err.c_str());
1017 basic_fbstring(const value_type* s, size_type n, const A& a = A())
1021 basic_fbstring(size_type n, value_type c, const A& a = A()) {
1022 auto const data = store_.expand_noinit(n);
1023 fbstring_detail::pod_fill(data, data + n, c);
1024 store_.writeTerminator();
1027 template <class InIt>
1028 basic_fbstring(InIt begin, InIt end,
1029 typename std::enable_if<
1030 !std::is_same<typename std::remove_const<InIt>::type,
1031 value_type*>::value, const A>::type & a = A()) {
1035 // Specialization for const char*, const char*
1036 basic_fbstring(const value_type* b, const value_type* e)
1037 : store_(b, e - b) {
1040 // Nonstandard constructor
1041 basic_fbstring(value_type *s, size_type n, size_type c,
1042 AcquireMallocatedString a)
1043 : store_(s, n, c, a) {
1049 basic_fbstring& operator=(const basic_fbstring& lhs) {
1050 if (FBSTRING_UNLIKELY(&lhs == this)) {
1053 auto const oldSize = size();
1054 auto const srcSize = lhs.size();
1055 if (capacity() >= srcSize && !store_.isShared()) {
1056 // great, just copy the contents
1057 if (oldSize < srcSize)
1058 store_.expand_noinit(srcSize - oldSize);
1060 store_.shrink(oldSize - srcSize);
1061 assert(size() == srcSize);
1062 fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1063 store_.writeTerminator();
1065 // need to reallocate, so we may as well create a brand new string
1066 basic_fbstring(lhs).swap(*this);
1072 basic_fbstring& operator=(basic_fbstring&& goner) {
1073 // Self move assignment is illegal, see 17.6.4.9 for the explanation
1074 assert(&goner != this);
1075 // No need of this anymore
1076 this->~basic_fbstring();
1077 // Move the goner into this
1078 new(&store_) fbstring_core<E>(std::move(goner.store_));
1082 #ifndef _LIBSTDCXX_FBSTRING
1083 // Compatibility with std::string
1084 basic_fbstring & operator=(const std::string & rhs) {
1085 return assign(rhs.data(), rhs.size());
1088 // Compatibility with std::string
1089 std::string toStdString() const {
1090 return std::string(data(), size());
1093 // A lot of code in fbcode still uses this method, so keep it here for now.
1094 const basic_fbstring& toStdString() const {
1099 basic_fbstring& operator=(const value_type* s) {
1103 basic_fbstring& operator=(value_type c) {
1105 store_.expand_noinit(1);
1106 } else if (store_.isShared()) {
1107 basic_fbstring(1, c).swap(*this);
1110 store_.shrink(size() - 1);
1112 *store_.mutable_data() = c;
1113 store_.writeTerminator();
1117 // 21.3.2 iterators:
1118 iterator begin() { return store_.mutable_data(); }
1120 const_iterator begin() const { return store_.data(); }
1123 return store_.mutable_data() + store_.size();
1126 const_iterator end() const {
1127 return store_.data() + store_.size();
1130 reverse_iterator rbegin() {
1131 return reverse_iterator(end());
1134 const_reverse_iterator rbegin() const {
1135 return const_reverse_iterator(end());
1138 reverse_iterator rend() {
1139 return reverse_iterator(begin());
1142 const_reverse_iterator rend() const {
1143 return const_reverse_iterator(begin());
1147 // C++11 21.4.5, element access:
1148 const value_type& front() const { return *begin(); }
1149 const value_type& back() const {
1151 // Should be begin()[size() - 1], but that branches twice
1152 return *(end() - 1);
1154 value_type& front() { return *begin(); }
1155 value_type& back() {
1157 // Should be begin()[size() - 1], but that branches twice
1158 return *(end() - 1);
1166 size_type size() const { return store_.size(); }
1168 size_type length() const { return size(); }
1170 size_type max_size() const {
1171 return std::numeric_limits<size_type>::max();
1174 void resize(const size_type n, const value_type c = value_type()) {
1175 auto size = this->size();
1177 store_.shrink(size - n);
1179 // Do this in two steps to minimize slack memory copied (see
1181 auto const capacity = this->capacity();
1182 assert(capacity >= size);
1183 if (size < capacity) {
1184 auto delta = std::min(n, capacity) - size;
1185 store_.expand_noinit(delta);
1186 fbstring_detail::pod_fill(begin() + size, end(), c);
1189 store_.writeTerminator();
1194 auto const delta = n - size;
1195 store_.expand_noinit(delta);
1196 fbstring_detail::pod_fill(end() - delta, end(), c);
1197 store_.writeTerminator();
1199 assert(this->size() == n);
1202 size_type capacity() const { return store_.capacity(); }
1204 void reserve(size_type res_arg = 0) {
1205 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1206 store_.reserve(res_arg);
1209 void clear() { resize(0); }
1211 bool empty() const { return size() == 0; }
1213 // 21.3.4 element access:
1214 const_reference operator[](size_type pos) const {
1215 return *(c_str() + pos);
1218 reference operator[](size_type pos) {
1219 if (pos == size()) {
1220 // Just call c_str() to make sure '\0' is present
1223 return *(begin() + pos);
1226 const_reference at(size_type n) const {
1227 enforce(n <= size(), std::__throw_out_of_range, "");
1231 reference at(size_type n) {
1232 enforce(n < size(), std::__throw_out_of_range, "");
1236 // 21.3.5 modifiers:
1237 basic_fbstring& operator+=(const basic_fbstring& str) {
1241 basic_fbstring& operator+=(const value_type* s) {
1245 basic_fbstring& operator+=(const value_type c) {
1250 basic_fbstring& append(const basic_fbstring& str) {
1252 auto desiredSize = size() + str.size();
1254 append(str.data(), str.size());
1255 assert(size() == desiredSize);
1259 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1261 const size_type sz = str.size();
1262 enforce(pos <= sz, std::__throw_out_of_range, "");
1263 procrustes(n, sz - pos);
1264 return append(str.data() + pos, n);
1267 basic_fbstring& append(const value_type* s, size_type n) {
1269 Invariant checker(*this);
1272 if (FBSTRING_UNLIKELY(!n)) {
1273 // Unlikely but must be done
1276 auto const oldSize = size();
1277 auto const oldData = data();
1278 // Check for aliasing (rare). We could use "<=" here but in theory
1279 // those do not work for pointers unless the pointers point to
1280 // elements in the same array. For that reason we use
1281 // std::less_equal, which is guaranteed to offer a total order
1282 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1284 std::less_equal<const value_type*> le;
1285 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1286 assert(le(s + n, oldData + oldSize));
1287 const size_type offset = s - oldData;
1288 store_.reserve(oldSize + n);
1289 // Restore the source
1290 s = data() + offset;
1292 // Warning! Repeated appends with short strings may actually incur
1293 // practically quadratic performance. Avoid that by pushing back
1294 // the first character (which ensures exponential growth) and then
1295 // appending the rest normally. Worst case the append may incur a
1296 // second allocation but that will be rare.
1299 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1300 assert(size() == oldSize + n + 1);
1304 basic_fbstring& append(const value_type* s) {
1305 return append(s, traits_type::length(s));
1308 basic_fbstring& append(size_type n, value_type c) {
1309 resize(size() + n, c);
1313 template<class InputIterator>
1314 basic_fbstring& append(InputIterator first, InputIterator last) {
1315 insert(end(), first, last);
1319 void push_back(const value_type c) { // primitive
1320 store_.push_back(c);
1323 basic_fbstring& assign(const basic_fbstring& str) {
1324 if (&str == this) return *this;
1325 return assign(str.data(), str.size());
1328 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1330 const size_type sz = str.size();
1331 enforce(pos <= sz, std::__throw_out_of_range, "");
1332 procrustes(n, sz - pos);
1333 return assign(str.data() + pos, n);
1336 basic_fbstring& assign(const value_type* s, const size_type n) {
1337 Invariant checker(*this);
1340 std::copy(s, s + n, begin());
1342 assert(size() == n);
1344 const value_type *const s2 = s + size();
1345 std::copy(s, s2, begin());
1346 append(s2, n - size());
1347 assert(size() == n);
1349 store_.writeTerminator();
1350 assert(size() == n);
1354 basic_fbstring& assign(const value_type* s) {
1355 return assign(s, traits_type::length(s));
1358 template <class ItOrLength, class ItOrChar>
1359 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1360 return replace(begin(), end(), first_or_n, last_or_c);
1363 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1364 return insert(pos1, str.data(), str.size());
1367 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1368 size_type pos2, size_type n) {
1369 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1370 procrustes(n, str.length() - pos2);
1371 return insert(pos1, str.data() + pos2, n);
1374 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1375 enforce(pos <= length(), std::__throw_out_of_range, "");
1376 insert(begin() + pos, s, s + n);
1380 basic_fbstring& insert(size_type pos, const value_type* s) {
1381 return insert(pos, s, traits_type::length(s));
1384 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1385 enforce(pos <= length(), std::__throw_out_of_range, "");
1386 insert(begin() + pos, n, c);
1390 iterator insert(const iterator p, const value_type c) {
1391 const size_type pos = p - begin();
1393 return begin() + pos;
1397 template <int i> class Selector {};
1399 basic_fbstring& insertImplDiscr(iterator p,
1400 size_type n, value_type c, Selector<1>) {
1401 Invariant checker(*this);
1403 assert(p >= begin() && p <= end());
1404 if (capacity() - size() < n) {
1405 const size_type sz = p - begin();
1406 reserve(size() + n);
1409 const iterator oldEnd = end();
1410 if( n < size_type(oldEnd - p)) {
1411 append(oldEnd - n, oldEnd);
1413 // reverse_iterator(oldEnd - n),
1414 // reverse_iterator(p),
1415 // reverse_iterator(oldEnd));
1416 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1417 std::fill(p, p + n, c);
1419 append(n - (end() - p), c);
1421 std::fill(p, oldEnd, c);
1423 store_.writeTerminator();
1427 template<class InputIter>
1428 basic_fbstring& insertImplDiscr(iterator i,
1429 InputIter b, InputIter e, Selector<0>) {
1431 typename std::iterator_traits<InputIter>::iterator_category());
1435 template <class FwdIterator>
1436 void insertImpl(iterator i,
1437 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1438 Invariant checker(*this);
1440 const size_type pos = i - begin();
1441 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1442 std::distance(s1, s2);
1444 using namespace fbstring_detail;
1445 assert(pos <= size());
1447 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1448 capacity() - size();
1450 // realloc the string
1451 reserve(size() + n2);
1454 if (pos + n2 <= size()) {
1455 const iterator tailBegin = end() - n2;
1456 store_.expand_noinit(n2);
1457 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1458 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1459 reverse_iterator(tailBegin + n2));
1460 std::copy(s1, s2, i);
1463 const size_type old_size = size();
1464 std::advance(t, old_size - pos);
1465 const size_t newElems = std::distance(t, s2);
1466 store_.expand_noinit(n2);
1467 std::copy(t, s2, begin() + old_size);
1468 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1469 begin() + old_size + newElems);
1470 std::copy(s1, t, i);
1472 store_.writeTerminator();
1475 template <class InputIterator>
1476 void insertImpl(iterator i,
1477 InputIterator b, InputIterator e, std::input_iterator_tag) {
1478 basic_fbstring temp(begin(), i);
1479 for (; b != e; ++b) {
1482 temp.append(i, end());
1487 template <class ItOrLength, class ItOrChar>
1488 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1489 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1490 insertImplDiscr(p, first_or_n, last_or_c, sel);
1493 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1494 Invariant checker(*this);
1496 enforce(pos <= length(), std::__throw_out_of_range, "");
1497 procrustes(n, length() - pos);
1498 std::copy(begin() + pos + n, end(), begin() + pos);
1499 resize(length() - n);
1503 iterator erase(iterator position) {
1504 const size_type pos(position - begin());
1505 enforce(pos <= size(), std::__throw_out_of_range, "");
1507 return begin() + pos;
1510 iterator erase(iterator first, iterator last) {
1511 const size_type pos(first - begin());
1512 erase(pos, last - first);
1513 return begin() + pos;
1516 // Replaces at most n1 chars of *this, starting with pos1 with the
1518 basic_fbstring& replace(size_type pos1, size_type n1,
1519 const basic_fbstring& str) {
1520 return replace(pos1, n1, str.data(), str.size());
1523 // Replaces at most n1 chars of *this, starting with pos1,
1524 // with at most n2 chars of str starting with pos2
1525 basic_fbstring& replace(size_type pos1, size_type n1,
1526 const basic_fbstring& str,
1527 size_type pos2, size_type n2) {
1528 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1529 return replace(pos1, n1, str.data() + pos2,
1530 std::min(n2, str.size() - pos2));
1533 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1534 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1535 return replace(pos, n1, s, traits_type::length(s));
1538 // Replaces at most n1 chars of *this, starting with pos, with n2
1541 // consolidated with
1543 // Replaces at most n1 chars of *this, starting with pos, with at
1544 // most n2 chars of str. str must have at least n2 chars.
1545 template <class StrOrLength, class NumOrChar>
1546 basic_fbstring& replace(size_type pos, size_type n1,
1547 StrOrLength s_or_n2, NumOrChar n_or_c) {
1548 Invariant checker(*this);
1550 enforce(pos <= size(), std::__throw_out_of_range, "");
1551 procrustes(n1, length() - pos);
1552 const iterator b = begin() + pos;
1553 return replace(b, b + n1, s_or_n2, n_or_c);
1556 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1557 return replace(i1, i2, str.data(), str.length());
1560 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1561 return replace(i1, i2, s, traits_type::length(s));
1565 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1566 const value_type* s, size_type n,
1569 assert(begin() <= i1 && i1 <= end());
1570 assert(begin() <= i2 && i2 <= end());
1571 return replace(i1, i2, s, s + n);
1574 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1575 size_type n2, value_type c, Selector<1>) {
1576 const size_type n1 = i2 - i1;
1578 std::fill(i1, i1 + n2, c);
1581 std::fill(i1, i2, c);
1582 insert(i2, n2 - n1, c);
1588 template <class InputIter>
1589 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1590 InputIter b, InputIter e,
1592 replaceImpl(i1, i2, b, e,
1593 typename std::iterator_traits<InputIter>::iterator_category());
1598 template <class FwdIterator, class P>
1599 bool replaceAliased(iterator i1, iterator i2,
1600 FwdIterator s1, FwdIterator s2, P*) {
1604 template <class FwdIterator>
1605 bool replaceAliased(iterator i1, iterator i2,
1606 FwdIterator s1, FwdIterator s2, value_type*) {
1607 static const std::less_equal<const value_type*> le =
1608 std::less_equal<const value_type*>();
1609 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1613 // Aliased replace, copy to new string
1614 basic_fbstring temp;
1615 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1616 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1622 template <class FwdIterator>
1623 void replaceImpl(iterator i1, iterator i2,
1624 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1625 Invariant checker(*this);
1628 // Handle aliased replace
1629 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1633 auto const n1 = i2 - i1;
1635 auto const n2 = std::distance(s1, s2);
1640 std::copy(s1, s2, i1);
1644 fbstring_detail::copy_n(s1, n1, i1);
1645 std::advance(s1, n1);
1651 template <class InputIterator>
1652 void replaceImpl(iterator i1, iterator i2,
1653 InputIterator b, InputIterator e, std::input_iterator_tag) {
1654 basic_fbstring temp(begin(), i1);
1655 temp.append(b, e).append(i2, end());
1660 template <class T1, class T2>
1661 basic_fbstring& replace(iterator i1, iterator i2,
1662 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1664 num1 = std::numeric_limits<T1>::is_specialized,
1665 num2 = std::numeric_limits<T2>::is_specialized;
1666 return replaceImplDiscr(
1667 i1, i2, first_or_n_or_s, last_or_c_or_n,
1668 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1671 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1672 enforce(pos <= size(), std::__throw_out_of_range, "");
1673 procrustes(n, size() - pos);
1675 fbstring_detail::pod_copy(
1682 void swap(basic_fbstring& rhs) {
1683 store_.swap(rhs.store_);
1686 // 21.3.6 string operations:
1687 const value_type* c_str() const {
1688 return store_.c_str();
1691 const value_type* data() const { return c_str(); }
1693 allocator_type get_allocator() const {
1694 return allocator_type();
1697 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1698 return find(str.data(), pos, str.length());
1701 size_type find(const value_type* needle, const size_type pos,
1702 const size_type nsize) const {
1703 if (!nsize) return pos;
1704 auto const size = this->size();
1705 if (nsize + pos > size) return npos;
1706 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1707 // the last characters first
1708 auto const haystack = data();
1709 auto const nsize_1 = nsize - 1;
1710 auto const lastNeedle = needle[nsize_1];
1712 // Boyer-Moore skip value for the last char in the needle. Zero is
1713 // not a valid value; skip will be computed the first time it's
1717 const E * i = haystack + pos;
1718 auto iEnd = haystack + size - nsize_1;
1721 // Boyer-Moore: match the last element in the needle
1722 while (i[nsize_1] != lastNeedle) {
1728 // Here we know that the last char matches
1729 // Continue in pedestrian mode
1730 for (size_t j = 0; ; ) {
1732 if (i[j] != needle[j]) {
1733 // Not found, we can skip
1734 // Compute the skip value lazily
1737 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1744 // Check if done searching
1747 return i - haystack;
1754 size_type find(const value_type* s, size_type pos = 0) const {
1755 return find(s, pos, traits_type::length(s));
1758 size_type find (value_type c, size_type pos = 0) const {
1759 return find(&c, pos, 1);
1762 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1763 return rfind(str.data(), pos, str.length());
1766 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1767 if (n > length()) return npos;
1768 pos = std::min(pos, length() - n);
1769 if (n == 0) return pos;
1771 const_iterator i(begin() + pos);
1773 if (traits_type::eq(*i, *s)
1774 && traits_type::compare(&*i, s, n) == 0) {
1777 if (i == begin()) break;
1782 size_type rfind(const value_type* s, size_type pos = npos) const {
1783 return rfind(s, pos, traits_type::length(s));
1786 size_type rfind(value_type c, size_type pos = npos) const {
1787 return rfind(&c, pos, 1);
1790 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1791 return find_first_of(str.data(), pos, str.length());
1794 size_type find_first_of(const value_type* s,
1795 size_type pos, size_type n) const {
1796 if (pos > length() || n == 0) return npos;
1797 const_iterator i(begin() + pos),
1799 for (; i != finish; ++i) {
1800 if (traits_type::find(s, n, *i) != 0) {
1807 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1808 return find_first_of(s, pos, traits_type::length(s));
1811 size_type find_first_of(value_type c, size_type pos = 0) const {
1812 return find_first_of(&c, pos, 1);
1815 size_type find_last_of (const basic_fbstring& str,
1816 size_type pos = npos) const {
1817 return find_last_of(str.data(), pos, str.length());
1820 size_type find_last_of (const value_type* s, size_type pos,
1821 size_type n) const {
1822 if (!empty() && n > 0) {
1823 pos = std::min(pos, length() - 1);
1824 const_iterator i(begin() + pos);
1826 if (traits_type::find(s, n, *i) != 0) {
1829 if (i == begin()) break;
1835 size_type find_last_of (const value_type* s,
1836 size_type pos = npos) const {
1837 return find_last_of(s, pos, traits_type::length(s));
1840 size_type find_last_of (value_type c, size_type pos = npos) const {
1841 return find_last_of(&c, pos, 1);
1844 size_type find_first_not_of(const basic_fbstring& str,
1845 size_type pos = 0) const {
1846 return find_first_not_of(str.data(), pos, str.size());
1849 size_type find_first_not_of(const value_type* s, size_type pos,
1850 size_type n) const {
1851 if (pos < length()) {
1855 for (; i != finish; ++i) {
1856 if (traits_type::find(s, n, *i) == 0) {
1864 size_type find_first_not_of(const value_type* s,
1865 size_type pos = 0) const {
1866 return find_first_not_of(s, pos, traits_type::length(s));
1869 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1870 return find_first_not_of(&c, pos, 1);
1873 size_type find_last_not_of(const basic_fbstring& str,
1874 size_type pos = npos) const {
1875 return find_last_not_of(str.data(), pos, str.length());
1878 size_type find_last_not_of(const value_type* s, size_type pos,
1879 size_type n) const {
1880 if (!this->empty()) {
1881 pos = std::min(pos, size() - 1);
1882 const_iterator i(begin() + pos);
1884 if (traits_type::find(s, n, *i) == 0) {
1887 if (i == begin()) break;
1893 size_type find_last_not_of(const value_type* s,
1894 size_type pos = npos) const {
1895 return find_last_not_of(s, pos, traits_type::length(s));
1898 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1899 return find_last_not_of(&c, pos, 1);
1902 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1903 enforce(pos <= size(), std::__throw_out_of_range, "");
1904 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1907 int compare(const basic_fbstring& str) const {
1908 // FIX due to Goncalo N M de Carvalho July 18, 2005
1909 return compare(0, size(), str);
1912 int compare(size_type pos1, size_type n1,
1913 const basic_fbstring& str) const {
1914 return compare(pos1, n1, str.data(), str.size());
1917 int compare(size_type pos1, size_type n1,
1918 const value_type* s) const {
1919 return compare(pos1, n1, s, traits_type::length(s));
1922 int compare(size_type pos1, size_type n1,
1923 const value_type* s, size_type n2) const {
1924 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1925 procrustes(n1, size() - pos1);
1926 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1927 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1928 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1931 int compare(size_type pos1, size_type n1,
1932 const basic_fbstring& str,
1933 size_type pos2, size_type n2) const {
1934 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1935 return compare(pos1, n1, str.data() + pos2,
1936 std::min(n2, str.size() - pos2));
1939 // Code from Jean-Francois Bastien (03/26/2007)
1940 int compare(const value_type* s) const {
1941 // Could forward to compare(0, size(), s, traits_type::length(s))
1942 // but that does two extra checks
1943 const size_type n1(size()), n2(traits_type::length(s));
1944 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1945 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1953 // non-member functions
1955 template <typename E, class T, class A, class S>
1957 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1958 const basic_fbstring<E, T, A, S>& rhs) {
1960 basic_fbstring<E, T, A, S> result;
1961 result.reserve(lhs.size() + rhs.size());
1962 result.append(lhs).append(rhs);
1963 return std::move(result);
1967 template <typename E, class T, class A, class S>
1969 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1970 const basic_fbstring<E, T, A, S>& rhs) {
1971 return std::move(lhs.append(rhs));
1975 template <typename E, class T, class A, class S>
1977 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1978 basic_fbstring<E, T, A, S>&& rhs) {
1979 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1980 // Good, at least we don't need to reallocate
1981 return std::move(rhs.insert(0, lhs));
1983 // Meh, no go. Forward to operator+(const&, const&).
1984 auto const& rhsC = rhs;
1989 template <typename E, class T, class A, class S>
1991 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1992 basic_fbstring<E, T, A, S>&& rhs) {
1993 return std::move(lhs.append(rhs));
1996 template <typename E, class T, class A, class S>
1998 basic_fbstring<E, T, A, S> operator+(
1999 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2000 const basic_fbstring<E, T, A, S>& rhs) {
2002 basic_fbstring<E, T, A, S> result;
2003 const typename basic_fbstring<E, T, A, S>::size_type len =
2004 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2005 result.reserve(len + rhs.size());
2006 result.append(lhs, len).append(rhs);
2010 template <typename E, class T, class A, class S>
2012 basic_fbstring<E, T, A, S> operator+(
2013 typename basic_fbstring<E, T, A, S>::value_type lhs,
2014 const basic_fbstring<E, T, A, S>& rhs) {
2016 basic_fbstring<E, T, A, S> result;
2017 result.reserve(1 + rhs.size());
2018 result.push_back(lhs);
2023 template <typename E, class T, class A, class S>
2025 basic_fbstring<E, T, A, S> operator+(
2026 const basic_fbstring<E, T, A, S>& lhs,
2027 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2029 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2030 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2032 basic_fbstring<E, T, A, S> result;
2033 const size_type len = traits_type::length(rhs);
2034 result.reserve(lhs.size() + len);
2035 result.append(lhs).append(rhs, len);
2039 template <typename E, class T, class A, class S>
2041 basic_fbstring<E, T, A, S> operator+(
2042 const basic_fbstring<E, T, A, S>& lhs,
2043 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2045 basic_fbstring<E, T, A, S> result;
2046 result.reserve(lhs.size() + 1);
2048 result.push_back(rhs);
2052 template <typename E, class T, class A, class S>
2054 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2055 const basic_fbstring<E, T, A, S>& rhs) {
2056 return lhs.compare(rhs) == 0; }
2058 template <typename E, class T, class A, class S>
2060 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2061 const basic_fbstring<E, T, A, S>& rhs) {
2062 return rhs == lhs; }
2064 template <typename E, class T, class A, class S>
2066 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2067 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2068 return lhs.compare(rhs) == 0; }
2070 template <typename E, class T, class A, class S>
2072 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2073 const basic_fbstring<E, T, A, S>& rhs) {
2074 return !(lhs == rhs); }
2076 template <typename E, class T, class A, class S>
2078 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2079 const basic_fbstring<E, T, A, S>& rhs) {
2080 return !(lhs == rhs); }
2082 template <typename E, class T, class A, class S>
2084 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2085 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2086 return !(lhs == rhs); }
2088 template <typename E, class T, class A, class S>
2090 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2091 const basic_fbstring<E, T, A, S>& rhs) {
2092 return lhs.compare(rhs) < 0; }
2094 template <typename E, class T, class A, class S>
2096 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2097 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2098 return lhs.compare(rhs) < 0; }
2100 template <typename E, class T, class A, class S>
2102 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2103 const basic_fbstring<E, T, A, S>& rhs) {
2104 return rhs.compare(lhs) > 0; }
2106 template <typename E, class T, class A, class S>
2108 bool operator>(const basic_fbstring<E, T, A, S>& 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 typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2118 template <typename E, class T, class A, class S>
2120 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2121 const basic_fbstring<E, T, A, S>& rhs) {
2124 template <typename E, class T, class A, class S>
2126 bool operator<=(const basic_fbstring<E, T, A, S>& 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 typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2134 return !(rhs < lhs); }
2136 template <typename E, class T, class A, class S>
2138 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2139 const basic_fbstring<E, T, A, S>& rhs) {
2140 return !(rhs < lhs); }
2142 template <typename E, class T, class A, class S>
2144 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2145 const basic_fbstring<E, T, A, S>& rhs) {
2146 return !(lhs < rhs); }
2148 template <typename E, class T, class A, class S>
2150 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2151 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2152 return !(lhs < rhs); }
2154 template <typename E, class T, class A, class S>
2156 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2157 const basic_fbstring<E, T, A, S>& rhs) {
2158 return !(lhs < rhs);
2161 // subclause 21.3.7.8:
2162 template <typename E, class T, class A, class S>
2163 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2167 // TODO: make this faster.
2168 template <typename E, class T, class A, class S>
2171 typename basic_fbstring<E, T, A, S>::value_type,
2172 typename basic_fbstring<E, T, A, S>::traits_type>&
2174 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2175 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2176 basic_fbstring<E, T, A, S>& str) {
2177 typename std::basic_istream<E, T>::sentry sentry(is);
2178 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2179 typename basic_fbstring<E, T, A, S>::traits_type>
2181 typedef typename __istream_type::ios_base __ios_base;
2182 size_t extracted = 0;
2183 auto err = __ios_base::goodbit;
2185 auto n = is.width();
2190 auto got = is.rdbuf()->sgetc();
2191 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2192 // Whew. We get to store this guy
2194 got = is.rdbuf()->snextc();
2196 if (got == T::eof()) {
2197 err |= __ios_base::eofbit;
2202 err |= __ios_base::failbit;
2210 template <typename E, class T, class A, class S>
2212 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2213 typename basic_fbstring<E, T, A, S>::traits_type>&
2215 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2216 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2217 const basic_fbstring<E, T, A, S>& str) {
2218 os.write(str.data(), str.size());
2222 #ifndef _LIBSTDCXX_FBSTRING
2224 template <typename E, class T, class A, class S>
2226 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2227 typename basic_fbstring<E, T, A, S>::traits_type>&
2229 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2230 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2231 basic_fbstring<E, T, A, S>& str,
2232 typename basic_fbstring<E, T, A, S>::value_type delim) {
2233 // Use the nonstandard getdelim()
2237 // This looks quadratic but it really depends on realloc
2238 auto const newSize = size + 128;
2239 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2240 is.getline(buf + size, newSize - size, delim);
2241 if (is.bad() || is.eof() || !is.fail()) {
2242 // done by either failure, end of file, or normal read
2243 size += std::strlen(buf + size);
2246 // Here we have failed due to too short a buffer
2247 // Minus one to discount the terminating '\0'
2249 assert(buf[size] == 0);
2250 // Clear the error so we can continue reading
2253 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2254 AcquireMallocatedString());
2259 template <typename E, class T, class A, class S>
2261 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2262 typename basic_fbstring<E, T, A, S>::traits_type>&
2264 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2265 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2266 basic_fbstring<E, T, A, S>& str) {
2267 // Just forward to the version with a delimiter
2268 return getline(is, str, '\n');
2273 template <typename E1, class T, class A, class S>
2274 const typename basic_fbstring<E1, T, A, S>::size_type
2275 basic_fbstring<E1, T, A, S>::npos =
2276 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2278 #ifndef _LIBSTDCXX_FBSTRING
2279 // basic_string compatibility routines
2281 template <typename E, class T, class A, class S>
2283 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2284 const std::string& rhs) {
2285 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2288 template <typename E, class T, class A, class S>
2290 bool operator==(const std::string& lhs,
2291 const basic_fbstring<E, T, A, S>& rhs) {
2295 template <typename E, class T, class A, class S>
2297 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2298 const std::string& rhs) {
2299 return !(lhs == rhs);
2302 template <typename E, class T, class A, class S>
2304 bool operator!=(const std::string& lhs,
2305 const basic_fbstring<E, T, A, S>& rhs) {
2306 return !(lhs == rhs);
2309 #if !defined(_LIBSTDCXX_FBSTRING)
2310 typedef basic_fbstring<char> fbstring;
2313 // fbstring is relocatable
2314 template <class T, class R, class A, class S>
2315 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2318 _GLIBCXX_END_NAMESPACE_VERSION
2321 } // namespace folly
2323 #ifndef _LIBSTDCXX_FBSTRING
2327 struct hash< ::folly::fbstring> {
2328 size_t operator()(const ::folly::fbstring& s) const {
2329 return ::folly::hash::fnv32_buf(s.data(), s.size());
2334 #endif // _LIBSTDCXX_FBSTRING
2336 #undef FBSTRING_LIKELY
2337 #undef FBSTRING_UNLIKELY
2339 #endif // FOLLY_BASE_FBSTRING_H_