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 if (FBSTRING_UNLIKELY(&goner == this)) {
1074 // Compatibility with std::basic_string<>,
1075 // 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1078 // No need of this anymore
1079 this->~basic_fbstring();
1080 // Move the goner into this
1081 new(&store_) fbstring_core<E>(std::move(goner.store_));
1085 #ifndef _LIBSTDCXX_FBSTRING
1086 // Compatibility with std::string
1087 basic_fbstring & operator=(const std::string & rhs) {
1088 return assign(rhs.data(), rhs.size());
1091 // Compatibility with std::string
1092 std::string toStdString() const {
1093 return std::string(data(), size());
1096 // A lot of code in fbcode still uses this method, so keep it here for now.
1097 const basic_fbstring& toStdString() const {
1102 basic_fbstring& operator=(const value_type* s) {
1106 basic_fbstring& operator=(value_type c) {
1108 store_.expand_noinit(1);
1109 } else if (store_.isShared()) {
1110 basic_fbstring(1, c).swap(*this);
1113 store_.shrink(size() - 1);
1115 *store_.mutable_data() = c;
1116 store_.writeTerminator();
1120 // 21.3.2 iterators:
1121 iterator begin() { return store_.mutable_data(); }
1123 const_iterator begin() const { return store_.data(); }
1126 return store_.mutable_data() + store_.size();
1129 const_iterator end() const {
1130 return store_.data() + store_.size();
1133 reverse_iterator rbegin() {
1134 return reverse_iterator(end());
1137 const_reverse_iterator rbegin() const {
1138 return const_reverse_iterator(end());
1141 reverse_iterator rend() {
1142 return reverse_iterator(begin());
1145 const_reverse_iterator rend() const {
1146 return const_reverse_iterator(begin());
1150 // C++11 21.4.5, element access:
1151 const value_type& front() const { return *begin(); }
1152 const value_type& back() const {
1154 // Should be begin()[size() - 1], but that branches twice
1155 return *(end() - 1);
1157 value_type& front() { return *begin(); }
1158 value_type& back() {
1160 // Should be begin()[size() - 1], but that branches twice
1161 return *(end() - 1);
1169 size_type size() const { return store_.size(); }
1171 size_type length() const { return size(); }
1173 size_type max_size() const {
1174 return std::numeric_limits<size_type>::max();
1177 void resize(const size_type n, const value_type c = value_type()) {
1178 auto size = this->size();
1180 store_.shrink(size - n);
1182 // Do this in two steps to minimize slack memory copied (see
1184 auto const capacity = this->capacity();
1185 assert(capacity >= size);
1186 if (size < capacity) {
1187 auto delta = std::min(n, capacity) - size;
1188 store_.expand_noinit(delta);
1189 fbstring_detail::pod_fill(begin() + size, end(), c);
1192 store_.writeTerminator();
1197 auto const delta = n - size;
1198 store_.expand_noinit(delta);
1199 fbstring_detail::pod_fill(end() - delta, end(), c);
1200 store_.writeTerminator();
1202 assert(this->size() == n);
1205 size_type capacity() const { return store_.capacity(); }
1207 void reserve(size_type res_arg = 0) {
1208 enforce(res_arg <= max_size(), std::__throw_length_error, "");
1209 store_.reserve(res_arg);
1212 void clear() { resize(0); }
1214 bool empty() const { return size() == 0; }
1216 // 21.3.4 element access:
1217 const_reference operator[](size_type pos) const {
1218 return *(c_str() + pos);
1221 reference operator[](size_type pos) {
1222 if (pos == size()) {
1223 // Just call c_str() to make sure '\0' is present
1226 return *(begin() + pos);
1229 const_reference at(size_type n) const {
1230 enforce(n <= size(), std::__throw_out_of_range, "");
1234 reference at(size_type n) {
1235 enforce(n < size(), std::__throw_out_of_range, "");
1239 // 21.3.5 modifiers:
1240 basic_fbstring& operator+=(const basic_fbstring& str) {
1244 basic_fbstring& operator+=(const value_type* s) {
1248 basic_fbstring& operator+=(const value_type c) {
1253 basic_fbstring& append(const basic_fbstring& str) {
1255 auto desiredSize = size() + str.size();
1257 append(str.data(), str.size());
1258 assert(size() == desiredSize);
1262 basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1264 const size_type sz = str.size();
1265 enforce(pos <= sz, std::__throw_out_of_range, "");
1266 procrustes(n, sz - pos);
1267 return append(str.data() + pos, n);
1270 basic_fbstring& append(const value_type* s, size_type n) {
1272 Invariant checker(*this);
1275 if (FBSTRING_UNLIKELY(!n)) {
1276 // Unlikely but must be done
1279 auto const oldSize = size();
1280 auto const oldData = data();
1281 // Check for aliasing (rare). We could use "<=" here but in theory
1282 // those do not work for pointers unless the pointers point to
1283 // elements in the same array. For that reason we use
1284 // std::less_equal, which is guaranteed to offer a total order
1285 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1287 std::less_equal<const value_type*> le;
1288 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1289 assert(le(s + n, oldData + oldSize));
1290 const size_type offset = s - oldData;
1291 store_.reserve(oldSize + n);
1292 // Restore the source
1293 s = data() + offset;
1295 // Warning! Repeated appends with short strings may actually incur
1296 // practically quadratic performance. Avoid that by pushing back
1297 // the first character (which ensures exponential growth) and then
1298 // appending the rest normally. Worst case the append may incur a
1299 // second allocation but that will be rare.
1302 memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1303 assert(size() == oldSize + n + 1);
1307 basic_fbstring& append(const value_type* s) {
1308 return append(s, traits_type::length(s));
1311 basic_fbstring& append(size_type n, value_type c) {
1312 resize(size() + n, c);
1316 template<class InputIterator>
1317 basic_fbstring& append(InputIterator first, InputIterator last) {
1318 insert(end(), first, last);
1322 void push_back(const value_type c) { // primitive
1323 store_.push_back(c);
1326 basic_fbstring& assign(const basic_fbstring& str) {
1327 if (&str == this) return *this;
1328 return assign(str.data(), str.size());
1331 basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1333 const size_type sz = str.size();
1334 enforce(pos <= sz, std::__throw_out_of_range, "");
1335 procrustes(n, sz - pos);
1336 return assign(str.data() + pos, n);
1339 basic_fbstring& assign(const value_type* s, const size_type n) {
1340 Invariant checker(*this);
1343 std::copy(s, s + n, begin());
1345 assert(size() == n);
1347 const value_type *const s2 = s + size();
1348 std::copy(s, s2, begin());
1349 append(s2, n - size());
1350 assert(size() == n);
1352 store_.writeTerminator();
1353 assert(size() == n);
1357 basic_fbstring& assign(const value_type* s) {
1358 return assign(s, traits_type::length(s));
1361 template <class ItOrLength, class ItOrChar>
1362 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1363 return replace(begin(), end(), first_or_n, last_or_c);
1366 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1367 return insert(pos1, str.data(), str.size());
1370 basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1371 size_type pos2, size_type n) {
1372 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1373 procrustes(n, str.length() - pos2);
1374 return insert(pos1, str.data() + pos2, n);
1377 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1378 enforce(pos <= length(), std::__throw_out_of_range, "");
1379 insert(begin() + pos, s, s + n);
1383 basic_fbstring& insert(size_type pos, const value_type* s) {
1384 return insert(pos, s, traits_type::length(s));
1387 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1388 enforce(pos <= length(), std::__throw_out_of_range, "");
1389 insert(begin() + pos, n, c);
1393 iterator insert(const iterator p, const value_type c) {
1394 const size_type pos = p - begin();
1396 return begin() + pos;
1400 template <int i> class Selector {};
1402 basic_fbstring& insertImplDiscr(iterator p,
1403 size_type n, value_type c, Selector<1>) {
1404 Invariant checker(*this);
1406 assert(p >= begin() && p <= end());
1407 if (capacity() - size() < n) {
1408 const size_type sz = p - begin();
1409 reserve(size() + n);
1412 const iterator oldEnd = end();
1413 if( n < size_type(oldEnd - p)) {
1414 append(oldEnd - n, oldEnd);
1416 // reverse_iterator(oldEnd - n),
1417 // reverse_iterator(p),
1418 // reverse_iterator(oldEnd));
1419 fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1420 std::fill(p, p + n, c);
1422 append(n - (end() - p), c);
1424 std::fill(p, oldEnd, c);
1426 store_.writeTerminator();
1430 template<class InputIter>
1431 basic_fbstring& insertImplDiscr(iterator i,
1432 InputIter b, InputIter e, Selector<0>) {
1434 typename std::iterator_traits<InputIter>::iterator_category());
1438 template <class FwdIterator>
1439 void insertImpl(iterator i,
1440 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1441 Invariant checker(*this);
1443 const size_type pos = i - begin();
1444 const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1445 std::distance(s1, s2);
1447 using namespace fbstring_detail;
1448 assert(pos <= size());
1450 const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1451 capacity() - size();
1453 // realloc the string
1454 reserve(size() + n2);
1457 if (pos + n2 <= size()) {
1458 const iterator tailBegin = end() - n2;
1459 store_.expand_noinit(n2);
1460 fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1461 std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1462 reverse_iterator(tailBegin + n2));
1463 std::copy(s1, s2, i);
1466 const size_type old_size = size();
1467 std::advance(t, old_size - pos);
1468 const size_t newElems = std::distance(t, s2);
1469 store_.expand_noinit(n2);
1470 std::copy(t, s2, begin() + old_size);
1471 fbstring_detail::pod_copy(data() + pos, data() + old_size,
1472 begin() + old_size + newElems);
1473 std::copy(s1, t, i);
1475 store_.writeTerminator();
1478 template <class InputIterator>
1479 void insertImpl(iterator i,
1480 InputIterator b, InputIterator e, std::input_iterator_tag) {
1481 basic_fbstring temp(begin(), i);
1482 for (; b != e; ++b) {
1485 temp.append(i, end());
1490 template <class ItOrLength, class ItOrChar>
1491 void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1492 Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1493 insertImplDiscr(p, first_or_n, last_or_c, sel);
1496 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1497 Invariant checker(*this);
1499 enforce(pos <= length(), std::__throw_out_of_range, "");
1500 procrustes(n, length() - pos);
1501 std::copy(begin() + pos + n, end(), begin() + pos);
1502 resize(length() - n);
1506 iterator erase(iterator position) {
1507 const size_type pos(position - begin());
1508 enforce(pos <= size(), std::__throw_out_of_range, "");
1510 return begin() + pos;
1513 iterator erase(iterator first, iterator last) {
1514 const size_type pos(first - begin());
1515 erase(pos, last - first);
1516 return begin() + pos;
1519 // Replaces at most n1 chars of *this, starting with pos1 with the
1521 basic_fbstring& replace(size_type pos1, size_type n1,
1522 const basic_fbstring& str) {
1523 return replace(pos1, n1, str.data(), str.size());
1526 // Replaces at most n1 chars of *this, starting with pos1,
1527 // with at most n2 chars of str starting with pos2
1528 basic_fbstring& replace(size_type pos1, size_type n1,
1529 const basic_fbstring& str,
1530 size_type pos2, size_type n2) {
1531 enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1532 return replace(pos1, n1, str.data() + pos2,
1533 std::min(n2, str.size() - pos2));
1536 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1537 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1538 return replace(pos, n1, s, traits_type::length(s));
1541 // Replaces at most n1 chars of *this, starting with pos, with n2
1544 // consolidated with
1546 // Replaces at most n1 chars of *this, starting with pos, with at
1547 // most n2 chars of str. str must have at least n2 chars.
1548 template <class StrOrLength, class NumOrChar>
1549 basic_fbstring& replace(size_type pos, size_type n1,
1550 StrOrLength s_or_n2, NumOrChar n_or_c) {
1551 Invariant checker(*this);
1553 enforce(pos <= size(), std::__throw_out_of_range, "");
1554 procrustes(n1, length() - pos);
1555 const iterator b = begin() + pos;
1556 return replace(b, b + n1, s_or_n2, n_or_c);
1559 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1560 return replace(i1, i2, str.data(), str.length());
1563 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1564 return replace(i1, i2, s, traits_type::length(s));
1568 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1569 const value_type* s, size_type n,
1572 assert(begin() <= i1 && i1 <= end());
1573 assert(begin() <= i2 && i2 <= end());
1574 return replace(i1, i2, s, s + n);
1577 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1578 size_type n2, value_type c, Selector<1>) {
1579 const size_type n1 = i2 - i1;
1581 std::fill(i1, i1 + n2, c);
1584 std::fill(i1, i2, c);
1585 insert(i2, n2 - n1, c);
1591 template <class InputIter>
1592 basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1593 InputIter b, InputIter e,
1595 replaceImpl(i1, i2, b, e,
1596 typename std::iterator_traits<InputIter>::iterator_category());
1601 template <class FwdIterator, class P>
1602 bool replaceAliased(iterator i1, iterator i2,
1603 FwdIterator s1, FwdIterator s2, P*) {
1607 template <class FwdIterator>
1608 bool replaceAliased(iterator i1, iterator i2,
1609 FwdIterator s1, FwdIterator s2, value_type*) {
1610 static const std::less_equal<const value_type*> le =
1611 std::less_equal<const value_type*>();
1612 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1616 // Aliased replace, copy to new string
1617 basic_fbstring temp;
1618 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1619 temp.append(begin(), i1).append(s1, s2).append(i2, end());
1625 template <class FwdIterator>
1626 void replaceImpl(iterator i1, iterator i2,
1627 FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1628 Invariant checker(*this);
1631 // Handle aliased replace
1632 if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1636 auto const n1 = i2 - i1;
1638 auto const n2 = std::distance(s1, s2);
1643 std::copy(s1, s2, i1);
1647 fbstring_detail::copy_n(s1, n1, i1);
1648 std::advance(s1, n1);
1654 template <class InputIterator>
1655 void replaceImpl(iterator i1, iterator i2,
1656 InputIterator b, InputIterator e, std::input_iterator_tag) {
1657 basic_fbstring temp(begin(), i1);
1658 temp.append(b, e).append(i2, end());
1663 template <class T1, class T2>
1664 basic_fbstring& replace(iterator i1, iterator i2,
1665 T1 first_or_n_or_s, T2 last_or_c_or_n) {
1667 num1 = std::numeric_limits<T1>::is_specialized,
1668 num2 = std::numeric_limits<T2>::is_specialized;
1669 return replaceImplDiscr(
1670 i1, i2, first_or_n_or_s, last_or_c_or_n,
1671 Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1674 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1675 enforce(pos <= size(), std::__throw_out_of_range, "");
1676 procrustes(n, size() - pos);
1678 fbstring_detail::pod_copy(
1685 void swap(basic_fbstring& rhs) {
1686 store_.swap(rhs.store_);
1689 // 21.3.6 string operations:
1690 const value_type* c_str() const {
1691 return store_.c_str();
1694 const value_type* data() const { return c_str(); }
1696 allocator_type get_allocator() const {
1697 return allocator_type();
1700 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1701 return find(str.data(), pos, str.length());
1704 size_type find(const value_type* needle, const size_type pos,
1705 const size_type nsize) const {
1706 if (!nsize) return pos;
1707 auto const size = this->size();
1708 if (nsize + pos > size) return npos;
1709 // Don't use std::search, use a Boyer-Moore-like trick by comparing
1710 // the last characters first
1711 auto const haystack = data();
1712 auto const nsize_1 = nsize - 1;
1713 auto const lastNeedle = needle[nsize_1];
1715 // Boyer-Moore skip value for the last char in the needle. Zero is
1716 // not a valid value; skip will be computed the first time it's
1720 const E * i = haystack + pos;
1721 auto iEnd = haystack + size - nsize_1;
1724 // Boyer-Moore: match the last element in the needle
1725 while (i[nsize_1] != lastNeedle) {
1731 // Here we know that the last char matches
1732 // Continue in pedestrian mode
1733 for (size_t j = 0; ; ) {
1735 if (i[j] != needle[j]) {
1736 // Not found, we can skip
1737 // Compute the skip value lazily
1740 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1747 // Check if done searching
1750 return i - haystack;
1757 size_type find(const value_type* s, size_type pos = 0) const {
1758 return find(s, pos, traits_type::length(s));
1761 size_type find (value_type c, size_type pos = 0) const {
1762 return find(&c, pos, 1);
1765 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1766 return rfind(str.data(), pos, str.length());
1769 size_type rfind(const value_type* s, size_type pos, size_type n) const {
1770 if (n > length()) return npos;
1771 pos = std::min(pos, length() - n);
1772 if (n == 0) return pos;
1774 const_iterator i(begin() + pos);
1776 if (traits_type::eq(*i, *s)
1777 && traits_type::compare(&*i, s, n) == 0) {
1780 if (i == begin()) break;
1785 size_type rfind(const value_type* s, size_type pos = npos) const {
1786 return rfind(s, pos, traits_type::length(s));
1789 size_type rfind(value_type c, size_type pos = npos) const {
1790 return rfind(&c, pos, 1);
1793 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1794 return find_first_of(str.data(), pos, str.length());
1797 size_type find_first_of(const value_type* s,
1798 size_type pos, size_type n) const {
1799 if (pos > length() || n == 0) return npos;
1800 const_iterator i(begin() + pos),
1802 for (; i != finish; ++i) {
1803 if (traits_type::find(s, n, *i) != 0) {
1810 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1811 return find_first_of(s, pos, traits_type::length(s));
1814 size_type find_first_of(value_type c, size_type pos = 0) const {
1815 return find_first_of(&c, pos, 1);
1818 size_type find_last_of (const basic_fbstring& str,
1819 size_type pos = npos) const {
1820 return find_last_of(str.data(), pos, str.length());
1823 size_type find_last_of (const value_type* s, size_type pos,
1824 size_type n) const {
1825 if (!empty() && n > 0) {
1826 pos = std::min(pos, length() - 1);
1827 const_iterator i(begin() + pos);
1829 if (traits_type::find(s, n, *i) != 0) {
1832 if (i == begin()) break;
1838 size_type find_last_of (const value_type* s,
1839 size_type pos = npos) const {
1840 return find_last_of(s, pos, traits_type::length(s));
1843 size_type find_last_of (value_type c, size_type pos = npos) const {
1844 return find_last_of(&c, pos, 1);
1847 size_type find_first_not_of(const basic_fbstring& str,
1848 size_type pos = 0) const {
1849 return find_first_not_of(str.data(), pos, str.size());
1852 size_type find_first_not_of(const value_type* s, size_type pos,
1853 size_type n) const {
1854 if (pos < length()) {
1858 for (; i != finish; ++i) {
1859 if (traits_type::find(s, n, *i) == 0) {
1867 size_type find_first_not_of(const value_type* s,
1868 size_type pos = 0) const {
1869 return find_first_not_of(s, pos, traits_type::length(s));
1872 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1873 return find_first_not_of(&c, pos, 1);
1876 size_type find_last_not_of(const basic_fbstring& str,
1877 size_type pos = npos) const {
1878 return find_last_not_of(str.data(), pos, str.length());
1881 size_type find_last_not_of(const value_type* s, size_type pos,
1882 size_type n) const {
1883 if (!this->empty()) {
1884 pos = std::min(pos, size() - 1);
1885 const_iterator i(begin() + pos);
1887 if (traits_type::find(s, n, *i) == 0) {
1890 if (i == begin()) break;
1896 size_type find_last_not_of(const value_type* s,
1897 size_type pos = npos) const {
1898 return find_last_not_of(s, pos, traits_type::length(s));
1901 size_type find_last_not_of (value_type c, size_type pos = npos) const {
1902 return find_last_not_of(&c, pos, 1);
1905 basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1906 enforce(pos <= size(), std::__throw_out_of_range, "");
1907 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1910 int compare(const basic_fbstring& str) const {
1911 // FIX due to Goncalo N M de Carvalho July 18, 2005
1912 return compare(0, size(), str);
1915 int compare(size_type pos1, size_type n1,
1916 const basic_fbstring& str) const {
1917 return compare(pos1, n1, str.data(), str.size());
1920 int compare(size_type pos1, size_type n1,
1921 const value_type* s) const {
1922 return compare(pos1, n1, s, traits_type::length(s));
1925 int compare(size_type pos1, size_type n1,
1926 const value_type* s, size_type n2) const {
1927 enforce(pos1 <= size(), std::__throw_out_of_range, "");
1928 procrustes(n1, size() - pos1);
1929 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1930 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1931 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1934 int compare(size_type pos1, size_type n1,
1935 const basic_fbstring& str,
1936 size_type pos2, size_type n2) const {
1937 enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1938 return compare(pos1, n1, str.data() + pos2,
1939 std::min(n2, str.size() - pos2));
1942 // Code from Jean-Francois Bastien (03/26/2007)
1943 int compare(const value_type* s) const {
1944 // Could forward to compare(0, size(), s, traits_type::length(s))
1945 // but that does two extra checks
1946 const size_type n1(size()), n2(traits_type::length(s));
1947 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1948 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1956 // non-member functions
1958 template <typename E, class T, class A, class S>
1960 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1961 const basic_fbstring<E, T, A, S>& rhs) {
1963 basic_fbstring<E, T, A, S> result;
1964 result.reserve(lhs.size() + rhs.size());
1965 result.append(lhs).append(rhs);
1966 return std::move(result);
1970 template <typename E, class T, class A, class S>
1972 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1973 const basic_fbstring<E, T, A, S>& rhs) {
1974 return std::move(lhs.append(rhs));
1978 template <typename E, class T, class A, class S>
1980 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1981 basic_fbstring<E, T, A, S>&& rhs) {
1982 if (rhs.capacity() >= lhs.size() + rhs.size()) {
1983 // Good, at least we don't need to reallocate
1984 return std::move(rhs.insert(0, lhs));
1986 // Meh, no go. Forward to operator+(const&, const&).
1987 auto const& rhsC = rhs;
1992 template <typename E, class T, class A, class S>
1994 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1995 basic_fbstring<E, T, A, S>&& rhs) {
1996 return std::move(lhs.append(rhs));
1999 template <typename E, class T, class A, class S>
2001 basic_fbstring<E, T, A, S> operator+(
2002 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2003 const basic_fbstring<E, T, A, S>& rhs) {
2005 basic_fbstring<E, T, A, S> result;
2006 const typename basic_fbstring<E, T, A, S>::size_type len =
2007 basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2008 result.reserve(len + rhs.size());
2009 result.append(lhs, len).append(rhs);
2013 template <typename E, class T, class A, class S>
2015 basic_fbstring<E, T, A, S> operator+(
2016 typename basic_fbstring<E, T, A, S>::value_type lhs,
2017 const basic_fbstring<E, T, A, S>& rhs) {
2019 basic_fbstring<E, T, A, S> result;
2020 result.reserve(1 + rhs.size());
2021 result.push_back(lhs);
2026 template <typename E, class T, class A, class S>
2028 basic_fbstring<E, T, A, S> operator+(
2029 const basic_fbstring<E, T, A, S>& lhs,
2030 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2032 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2033 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2035 basic_fbstring<E, T, A, S> result;
2036 const size_type len = traits_type::length(rhs);
2037 result.reserve(lhs.size() + len);
2038 result.append(lhs).append(rhs, len);
2042 template <typename E, class T, class A, class S>
2044 basic_fbstring<E, T, A, S> operator+(
2045 const basic_fbstring<E, T, A, S>& lhs,
2046 typename basic_fbstring<E, T, A, S>::value_type rhs) {
2048 basic_fbstring<E, T, A, S> result;
2049 result.reserve(lhs.size() + 1);
2051 result.push_back(rhs);
2055 template <typename E, class T, class A, class S>
2057 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2058 const basic_fbstring<E, T, A, S>& rhs) {
2059 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2061 template <typename E, class T, class A, class S>
2063 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2064 const basic_fbstring<E, T, A, S>& rhs) {
2065 return rhs == lhs; }
2067 template <typename E, class T, class A, class S>
2069 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2070 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2071 return lhs.compare(rhs) == 0; }
2073 template <typename E, class T, class A, class S>
2075 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2076 const basic_fbstring<E, T, A, S>& rhs) {
2077 return !(lhs == rhs); }
2079 template <typename E, class T, class A, class S>
2081 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2082 const basic_fbstring<E, T, A, S>& rhs) {
2083 return !(lhs == rhs); }
2085 template <typename E, class T, class A, class S>
2087 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2088 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2089 return !(lhs == rhs); }
2091 template <typename E, class T, class A, class S>
2093 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2094 const basic_fbstring<E, T, A, S>& rhs) {
2095 return lhs.compare(rhs) < 0; }
2097 template <typename E, class T, class A, class S>
2099 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2100 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2101 return lhs.compare(rhs) < 0; }
2103 template <typename E, class T, class A, class S>
2105 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2106 const basic_fbstring<E, T, A, S>& rhs) {
2107 return rhs.compare(lhs) > 0; }
2109 template <typename E, class T, class A, class S>
2111 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2112 const basic_fbstring<E, T, A, S>& rhs) {
2115 template <typename E, class T, class A, class S>
2117 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2118 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2121 template <typename E, class T, class A, class S>
2123 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2124 const basic_fbstring<E, T, A, S>& rhs) {
2127 template <typename E, class T, class A, class S>
2129 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2130 const basic_fbstring<E, T, A, S>& rhs) {
2131 return !(rhs < lhs); }
2133 template <typename E, class T, class A, class S>
2135 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2136 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2137 return !(rhs < lhs); }
2139 template <typename E, class T, class A, class S>
2141 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2142 const basic_fbstring<E, T, A, S>& rhs) {
2143 return !(rhs < lhs); }
2145 template <typename E, class T, class A, class S>
2147 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2148 const basic_fbstring<E, T, A, S>& rhs) {
2149 return !(lhs < rhs); }
2151 template <typename E, class T, class A, class S>
2153 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2154 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2155 return !(lhs < rhs); }
2157 template <typename E, class T, class A, class S>
2159 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2160 const basic_fbstring<E, T, A, S>& rhs) {
2161 return !(lhs < rhs);
2164 // subclause 21.3.7.8:
2165 template <typename E, class T, class A, class S>
2166 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2170 // TODO: make this faster.
2171 template <typename E, class T, class A, class S>
2174 typename basic_fbstring<E, T, A, S>::value_type,
2175 typename basic_fbstring<E, T, A, S>::traits_type>&
2177 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2178 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2179 basic_fbstring<E, T, A, S>& str) {
2180 typename std::basic_istream<E, T>::sentry sentry(is);
2181 typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2182 typename basic_fbstring<E, T, A, S>::traits_type>
2184 typedef typename __istream_type::ios_base __ios_base;
2185 size_t extracted = 0;
2186 auto err = __ios_base::goodbit;
2188 auto n = is.width();
2193 auto got = is.rdbuf()->sgetc();
2194 for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2195 // Whew. We get to store this guy
2197 got = is.rdbuf()->snextc();
2199 if (got == T::eof()) {
2200 err |= __ios_base::eofbit;
2205 err |= __ios_base::failbit;
2213 template <typename E, class T, class A, class S>
2215 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2216 typename basic_fbstring<E, T, A, S>::traits_type>&
2218 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2219 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2220 const basic_fbstring<E, T, A, S>& str) {
2221 os.write(str.data(), str.size());
2225 #ifndef _LIBSTDCXX_FBSTRING
2227 template <typename E, class T, class A, class S>
2229 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2230 typename basic_fbstring<E, T, A, S>::traits_type>&
2232 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2233 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2234 basic_fbstring<E, T, A, S>& str,
2235 typename basic_fbstring<E, T, A, S>::value_type delim) {
2236 // Use the nonstandard getdelim()
2240 // This looks quadratic but it really depends on realloc
2241 auto const newSize = size + 128;
2242 buf = static_cast<char*>(checkedRealloc(buf, newSize));
2243 is.getline(buf + size, newSize - size, delim);
2244 if (is.bad() || is.eof() || !is.fail()) {
2245 // done by either failure, end of file, or normal read
2246 size += std::strlen(buf + size);
2249 // Here we have failed due to too short a buffer
2250 // Minus one to discount the terminating '\0'
2252 assert(buf[size] == 0);
2253 // Clear the error so we can continue reading
2256 basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2257 AcquireMallocatedString());
2262 template <typename E, class T, class A, class S>
2264 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2265 typename basic_fbstring<E, T, A, S>::traits_type>&
2267 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2268 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2269 basic_fbstring<E, T, A, S>& str) {
2270 // Just forward to the version with a delimiter
2271 return getline(is, str, '\n');
2276 template <typename E1, class T, class A, class S>
2277 const typename basic_fbstring<E1, T, A, S>::size_type
2278 basic_fbstring<E1, T, A, S>::npos =
2279 static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2281 #ifndef _LIBSTDCXX_FBSTRING
2282 // basic_string compatibility routines
2284 template <typename E, class T, class A, class S>
2286 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2287 const std::string& rhs) {
2288 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2291 template <typename E, class T, class A, class S>
2293 bool operator==(const std::string& lhs,
2294 const basic_fbstring<E, T, A, S>& rhs) {
2298 template <typename E, class T, class A, class S>
2300 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2301 const std::string& rhs) {
2302 return !(lhs == rhs);
2305 template <typename E, class T, class A, class S>
2307 bool operator!=(const std::string& lhs,
2308 const basic_fbstring<E, T, A, S>& rhs) {
2309 return !(lhs == rhs);
2312 #if !defined(_LIBSTDCXX_FBSTRING)
2313 typedef basic_fbstring<char> fbstring;
2316 // fbstring is relocatable
2317 template <class T, class R, class A, class S>
2318 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2321 _GLIBCXX_END_NAMESPACE_VERSION
2324 } // namespace folly
2326 #ifndef _LIBSTDCXX_FBSTRING
2330 struct hash< ::folly::fbstring> {
2331 size_t operator()(const ::folly::fbstring& s) const {
2332 return ::folly::hash::fnv32_buf(s.data(), s.size());
2337 #endif // _LIBSTDCXX_FBSTRING
2339 #undef FBSTRING_LIKELY
2340 #undef FBSTRING_UNLIKELY
2342 #endif // FOLLY_BASE_FBSTRING_H_