1/*
2 * Copyright 2011-present Facebook, Inc.
3 *
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
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
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.
15 */
16
17// @author: Andrei Alexandrescu (aalexandre)
18// String type.
19
20#pragma once
21
22#include <atomic>
23#include <cstddef>
24#include <iosfwd>
25#include <limits>
26#include <stdexcept>
27#include <type_traits>
28
29// This file appears in two locations: inside fbcode and in the
30// libstdc++ source code (when embedding fbstring as std::string).
31// To aid in this schizophrenic use, _LIBSTDCXX_FBSTRING is defined in
32// libstdc++'s c++config.h, to gate use inside fbcode v. libstdc++.
33#ifdef _LIBSTDCXX_FBSTRING
34
35#pragma GCC system_header
36
37#include <basic_fbstring_malloc.h> // @manual
38
39// When used as std::string replacement always disable assertions.
40#define FBSTRING_ASSERT(expr) /* empty */
41
42#else // !_LIBSTDCXX_FBSTRING
43
44#include <folly/CppAttributes.h>
45#include <folly/Portability.h>
46
47// libc++ doesn't provide this header, nor does msvc
48#if __has_include(<bits/c++config.h>)
49#include <bits/c++config.h>
50#endif
51
52#include <algorithm>
53#include <cassert>
54#include <cstring>
55#include <string>
56#include <utility>
57
58#include <folly/Traits.h>
59#include <folly/hash/Hash.h>
60#include <folly/lang/Exception.h>
61#include <folly/memory/Malloc.h>
62
63// When used in folly, assertions are not disabled.
64#define FBSTRING_ASSERT(expr) assert(expr)
65
66#endif
67
68// We defined these here rather than including Likely.h to avoid
69// redefinition errors when fbstring is imported into libstdc++.
70#if defined(__GNUC__) && __GNUC__ >= 4
71#define FBSTRING_LIKELY(x) (__builtin_expect((x), 1))
72#define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
73#else
74#define FBSTRING_LIKELY(x) (x)
75#define FBSTRING_UNLIKELY(x) (x)
76#endif
77
78FOLLY_PUSH_WARNING
79// Ignore shadowing warnings within this file, so includers can use -Wshadow.
80FOLLY_GNU_DISABLE_WARNING("-Wshadow")
81// GCC 4.9 has a false positive in setSmallSize (probably
82// https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59124), disable
83// compile-time array bound checking.
84FOLLY_GNU_DISABLE_WARNING("-Warray-bounds")
85
86// FBString cannot use throw when replacing std::string, though it may still
87// use folly::throw_exception
88// nolint
89#define throw FOLLY_FBSTRING_MAY_NOT_USE_THROW
90
91#ifdef _LIBSTDCXX_FBSTRING
92#define FOLLY_FBSTRING_BEGIN_NAMESPACE \
93 namespace std _GLIBCXX_VISIBILITY(default) { \
94 _GLIBCXX_BEGIN_NAMESPACE_VERSION
95#define FOLLY_FBSTRING_END_NAMESPACE \
96 _GLIBCXX_END_NAMESPACE_VERSION \
97 } // namespace std
98#else
99#define FOLLY_FBSTRING_BEGIN_NAMESPACE namespace folly {
100#define FOLLY_FBSTRING_END_NAMESPACE } // namespace folly
101#endif
102
103FOLLY_FBSTRING_BEGIN_NAMESPACE
104
105#if defined(__clang__)
106#if __has_feature(address_sanitizer)
107#define FBSTRING_SANITIZE_ADDRESS
108#endif
109#elif defined(__GNUC__) && \
110 (((__GNUC__ == 4) && (__GNUC_MINOR__ >= 8)) || (__GNUC__ >= 5)) && \
111 __SANITIZE_ADDRESS__
112#define FBSTRING_SANITIZE_ADDRESS
113#endif
114
115// When compiling with ASan, always heap-allocate the string even if
116// it would fit in-situ, so that ASan can detect access to the string
117// buffer after it has been invalidated (destroyed, resized, etc.).
118// Note that this flag doesn't remove support for in-situ strings, as
119// that would break ABI-compatibility and wouldn't allow linking code
120// compiled with this flag with code compiled without.
121#ifdef FBSTRING_SANITIZE_ADDRESS
122#define FBSTRING_DISABLE_SSO true
123#else
124#define FBSTRING_DISABLE_SSO false
125#endif
126
127namespace fbstring_detail {
128
129template <class InIt, class OutIt>
130inline std::pair<InIt, OutIt> copy_n(
131 InIt b,
132 typename std::iterator_traits<InIt>::difference_type n,
133 OutIt d) {
134 for (; n != 0; --n, ++b, ++d) {
135 *d = *b;
136 }
137 return std::make_pair(b, d);
138}
139
140template <class Pod, class T>
141inline void podFill(Pod* b, Pod* e, T c) {
142 FBSTRING_ASSERT(b && e && b <= e);
143 constexpr auto kUseMemset = sizeof(T) == 1;
144 if /* constexpr */ (kUseMemset) {
145 memset(b, c, size_t(e - b));
146 } else {
147 auto const ee = b + ((e - b) & ~7u);
148 for (; b != ee; b += 8) {
149 b[0] = c;
150 b[1] = c;
151 b[2] = c;
152 b[3] = c;
153 b[4] = c;
154 b[5] = c;
155 b[6] = c;
156 b[7] = c;
157 }
158 // Leftovers
159 for (; b != e; ++b) {
160 *b = c;
161 }
162 }
163}
164
165/*
166 * Lightly structured memcpy, simplifies copying PODs and introduces
167 * some asserts. Unfortunately using this function may cause
168 * measurable overhead (presumably because it adjusts from a begin/end
169 * convention to a pointer/size convention, so it does some extra
170 * arithmetic even though the caller might have done the inverse
171 * adaptation outside).
172 */
173template <class Pod>
174inline void podCopy(const Pod* b, const Pod* e, Pod* d) {
175 FBSTRING_ASSERT(b != nullptr);
176 FBSTRING_ASSERT(e != nullptr);
177 FBSTRING_ASSERT(d != nullptr);
178 FBSTRING_ASSERT(e >= b);
179 FBSTRING_ASSERT(d >= e || d + (e - b) <= b);
180 memcpy(d, b, (e - b) * sizeof(Pod));
181}
182
183/*
184 * Lightly structured memmove, simplifies copying PODs and introduces
185 * some asserts
186 */
187template <class Pod>
188inline void podMove(const Pod* b, const Pod* e, Pod* d) {
189 FBSTRING_ASSERT(e >= b);
190 memmove(d, b, (e - b) * sizeof(*b));
191}
192
193// always inline
194#if defined(__GNUC__) // Clang also defines __GNUC__
195#define FBSTRING_ALWAYS_INLINE inline __attribute__((__always_inline__))
196#elif defined(_MSC_VER)
197#define FBSTRING_ALWAYS_INLINE __forceinline
198#else
199#define FBSTRING_ALWAYS_INLINE inline
200#endif
201
202[[noreturn]] FBSTRING_ALWAYS_INLINE void assume_unreachable() {
203#if defined(__GNUC__) // Clang also defines __GNUC__
204 __builtin_unreachable();
205#elif defined(_MSC_VER)
206 __assume(0);
207#else
208 // Well, it's better than nothing.
209 std::abort();
210#endif
211}
212
213} // namespace fbstring_detail
214
215/**
216 * Defines a special acquisition method for constructing fbstring
217 * objects. AcquireMallocatedString means that the user passes a
218 * pointer to a malloc-allocated string that the fbstring object will
219 * take into custody.
220 */
221enum class AcquireMallocatedString {};
222
223/*
224 * fbstring_core_model is a mock-up type that defines all required
225 * signatures of a fbstring core. The fbstring class itself uses such
226 * a core object to implement all of the numerous member functions
227 * required by the standard.
228 *
229 * If you want to define a new core, copy the definition below and
230 * implement the primitives. Then plug the core into basic_fbstring as
231 * a template argument.
232
233template <class Char>
234class fbstring_core_model {
235 public:
236 fbstring_core_model();
237 fbstring_core_model(const fbstring_core_model &);
238 ~fbstring_core_model();
239 // Returns a pointer to string's buffer (currently only contiguous
240 // strings are supported). The pointer is guaranteed to be valid
241 // until the next call to a non-const member function.
242 const Char * data() const;
243 // Much like data(), except the string is prepared to support
244 // character-level changes. This call is a signal for
245 // e.g. reference-counted implementation to fork the data. The
246 // pointer is guaranteed to be valid until the next call to a
247 // non-const member function.
248 Char* mutableData();
249 // Returns a pointer to string's buffer and guarantees that a
250 // readable '\0' lies right after the buffer. The pointer is
251 // guaranteed to be valid until the next call to a non-const member
252 // function.
253 const Char * c_str() const;
254 // Shrinks the string by delta characters. Asserts that delta <=
255 // size().
256 void shrink(size_t delta);
257 // Expands the string by delta characters (i.e. after this call
258 // size() will report the old size() plus delta) but without
259 // initializing the expanded region. The expanded region is
260 // zero-terminated. Returns a pointer to the memory to be
261 // initialized (the beginning of the expanded portion). The caller
262 // is expected to fill the expanded area appropriately.
263 // If expGrowth is true, exponential growth is guaranteed.
264 // It is not guaranteed not to reallocate even if size() + delta <
265 // capacity(), so all references to the buffer are invalidated.
266 Char* expandNoinit(size_t delta, bool expGrowth);
267 // Expands the string by one character and sets the last character
268 // to c.
269 void push_back(Char c);
270 // Returns the string's size.
271 size_t size() const;
272 // Returns the string's capacity, i.e. maximum size that the string
273 // can grow to without reallocation. Note that for reference counted
274 // strings that's technically a lie - even assigning characters
275 // within the existing size would cause a reallocation.
276 size_t capacity() const;
277 // Returns true if the data underlying the string is actually shared
278 // across multiple strings (in a refcounted fashion).
279 bool isShared() const;
280 // Makes sure that at least minCapacity characters are available for
281 // the string without reallocation. For reference-counted strings,
282 // it should fork the data even if minCapacity < size().
283 void reserve(size_t minCapacity);
284 private:
285 // Do not implement
286 fbstring_core_model& operator=(const fbstring_core_model &);
287};
288*/
289
290/**
291 * This is the core of the string. The code should work on 32- and
292 * 64-bit and both big- and little-endianan architectures with any
293 * Char size.
294 *
295 * The storage is selected as follows (assuming we store one-byte
296 * characters on a 64-bit machine): (a) "small" strings between 0 and
297 * 23 chars are stored in-situ without allocation (the rightmost byte
298 * stores the size); (b) "medium" strings from 24 through 254 chars
299 * are stored in malloc-allocated memory that is copied eagerly; (c)
300 * "large" strings of 255 chars and above are stored in a similar
301 * structure as medium arrays, except that the string is
302 * reference-counted and copied lazily. the reference count is
303 * allocated right before the character array.
304 *
305 * The discriminator between these three strategies sits in two
306 * bits of the rightmost char of the storage:
307 * - If neither is set, then the string is small. Its length is represented by
308 * the lower-order bits on little-endian or the high-order bits on big-endian
309 * of that rightmost character. The value of these six bits is
310 * `maxSmallSize - size`, so this quantity must be subtracted from
311 * `maxSmallSize` to compute the `size` of the string (see `smallSize()`).
312 * This scheme ensures that when `size == `maxSmallSize`, the last byte in the
313 * storage is \0. This way, storage will be a null-terminated sequence of
314 * bytes, even if all 23 bytes of data are used on a 64-bit architecture.
315 * This enables `c_str()` and `data()` to simply return a pointer to the
316 * storage.
317 *
318 * - If the MSb is set, the string is medium width.
319 *
320 * - If the second MSb is set, then the string is large. On little-endian,
321 * these 2 bits are the 2 MSbs of MediumLarge::capacity_, while on
322 * big-endian, these 2 bits are the 2 LSbs. This keeps both little-endian
323 * and big-endian fbstring_core equivalent with merely different ops used
324 * to extract capacity/category.
325 */
326template <class Char>
327class fbstring_core {
328 protected:
329// It's MSVC, so we just have to guess ... and allow an override
330#ifdef _MSC_VER
331#ifdef FOLLY_ENDIAN_BE
332 static constexpr auto kIsLittleEndian = false;
333#else
334 static constexpr auto kIsLittleEndian = true;
335#endif
336#else
337 static constexpr auto kIsLittleEndian =
338 __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;
339#endif
340 public:
341 fbstring_core() noexcept {
342 reset();
343 }
344
345 fbstring_core(const fbstring_core& rhs) {
346 FBSTRING_ASSERT(&rhs != this);
347 switch (rhs.category()) {
348 case Category::isSmall:
349 copySmall(rhs);
350 break;
351 case Category::isMedium:
352 copyMedium(rhs);
353 break;
354 case Category::isLarge:
355 copyLarge(rhs);
356 break;
357 default:
358 fbstring_detail::assume_unreachable();
359 }
360 FBSTRING_ASSERT(size() == rhs.size());
361 FBSTRING_ASSERT(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
362 }
363
364 fbstring_core(fbstring_core&& goner) noexcept {
365 // Take goner's guts
366 ml_ = goner.ml_;
367 // Clean goner's carcass
368 goner.reset();
369 }
370
371 fbstring_core(
372 const Char* const data,
373 const size_t size,
374 bool disableSSO = FBSTRING_DISABLE_SSO) {
375 if (!disableSSO && size <= maxSmallSize) {
376 initSmall(data, size);
377 } else if (size <= maxMediumSize) {
378 initMedium(data, size);
379 } else {
380 initLarge(data, size);
381 }
382 FBSTRING_ASSERT(this->size() == size);
383 FBSTRING_ASSERT(
384 size == 0 || memcmp(this->data(), data, size * sizeof(Char)) == 0);
385 }
386
387 ~fbstring_core() noexcept {
388 if (category() == Category::isSmall) {
389 return;
390 }
391 destroyMediumLarge();
392 }
393
394 // Snatches a previously mallocated string. The parameter "size"
395 // is the size of the string, and the parameter "allocatedSize"
396 // is the size of the mallocated block. The string must be
397 // \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.
398 //
399 // So if you want a 2-character string, pass malloc(3) as "data",
400 // pass 2 as "size", and pass 3 as "allocatedSize".
401 fbstring_core(
402 Char* const data,
403 const size_t size,
404 const size_t allocatedSize,
405 AcquireMallocatedString) {
406 if (size > 0) {
407 FBSTRING_ASSERT(allocatedSize >= size + 1);
408 FBSTRING_ASSERT(data[size] == '\0');
409 // Use the medium string storage
410 ml_.data_ = data;
411 ml_.size_ = size;
412 // Don't forget about null terminator
413 ml_.setCapacity(allocatedSize - 1, Category::isMedium);
414 } else {
415 // No need for the memory
416 free(data);
417 reset();
418 }
419 }
420
421 // swap below doesn't test whether &rhs == this (and instead
422 // potentially does extra work) on the premise that the rarity of
423 // that situation actually makes the check more expensive than is
424 // worth.
425 void swap(fbstring_core& rhs) {
426 auto const t = ml_;
427 ml_ = rhs.ml_;
428 rhs.ml_ = t;
429 }
430
431 // In C++11 data() and c_str() are 100% equivalent.
432 const Char* data() const {
433 return c_str();
434 }
435
436 Char* mutableData() {
437 switch (category()) {
438 case Category::isSmall:
439 return small_;
440 case Category::isMedium:
441 return ml_.data_;
442 case Category::isLarge:
443 return mutableDataLarge();
444 }
445 fbstring_detail::assume_unreachable();
446 }
447
448 const Char* c_str() const {
449 const Char* ptr = ml_.data_;
450 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
451 ptr = (category() == Category::isSmall) ? small_ : ptr;
452 return ptr;
453 }
454
455 void shrink(const size_t delta) {
456 if (category() == Category::isSmall) {
457 shrinkSmall(delta);
458 } else if (
459 category() == Category::isMedium || RefCounted::refs(ml_.data_) == 1) {
460 shrinkMedium(delta);
461 } else {
462 shrinkLarge(delta);
463 }
464 }
465
466 FOLLY_MALLOC_NOINLINE
467 void reserve(size_t minCapacity, bool disableSSO = FBSTRING_DISABLE_SSO) {
468 switch (category()) {
469 case Category::isSmall:
470 reserveSmall(minCapacity, disableSSO);
471 break;
472 case Category::isMedium:
473 reserveMedium(minCapacity);
474 break;
475 case Category::isLarge:
476 reserveLarge(minCapacity);
477 break;
478 default:
479 fbstring_detail::assume_unreachable();
480 }
481 FBSTRING_ASSERT(capacity() >= minCapacity);
482 }
483
484 Char* expandNoinit(
485 const size_t delta,
486 bool expGrowth = false,
487 bool disableSSO = FBSTRING_DISABLE_SSO);
488
489 void push_back(Char c) {
490 *expandNoinit(1, /* expGrowth = */ true) = c;
491 }
492
493 size_t size() const {
494 size_t ret = ml_.size_;
495 if /* constexpr */ (kIsLittleEndian) {
496 // We can save a couple instructions, because the category is
497 // small iff the last char, as unsigned, is <= maxSmallSize.
498 typedef typename std::make_unsigned<Char>::type UChar;
499 auto maybeSmallSize = size_t(maxSmallSize) -
500 size_t(static_cast<UChar>(small_[maxSmallSize]));
501 // With this syntax, GCC and Clang generate a CMOV instead of a branch.
502 ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;
503 } else {
504 ret = (category() == Category::isSmall) ? smallSize() : ret;
505 }
506 return ret;
507 }
508
509 size_t capacity() const {
510 switch (category()) {
511 case Category::isSmall:
512 return maxSmallSize;
513 case Category::isLarge:
514 // For large-sized strings, a multi-referenced chunk has no
515 // available capacity. This is because any attempt to append
516 // data would trigger a new allocation.
517 if (RefCounted::refs(ml_.data_) > 1) {
518 return ml_.size_;
519 }
520 break;
521 default:
522 break;
523 }
524 return ml_.capacity();
525 }
526
527 bool isShared() const {
528 return category() == Category::isLarge && RefCounted::refs(ml_.data_) > 1;
529 }
530
531 private:
532 // Disabled
533 fbstring_core& operator=(const fbstring_core& rhs);
534
535 void reset() {
536 setSmallSize(0);
537 }
538
539 FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {
540 auto const c = category();
541 FBSTRING_ASSERT(c != Category::isSmall);
542 if (c == Category::isMedium) {
543 free(ml_.data_);
544 } else {
545 RefCounted::decrementRefs(ml_.data_);
546 }
547 }
548
549 struct RefCounted {
550 std::atomic<size_t> refCount_;
551 Char data_[1];
552
553 constexpr static size_t getDataOffset() {
554 return offsetof(RefCounted, data_);
555 }
556
557 static RefCounted* fromData(Char* p) {
558 return static_cast<RefCounted*>(static_cast<void*>(
559 static_cast<unsigned char*>(static_cast<void*>(p)) -
560 getDataOffset()));
561 }
562
563 static size_t refs(Char* p) {
564 return fromData(p)->refCount_.load(std::memory_order_acquire);
565 }
566
567 static void incrementRefs(Char* p) {
568 fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
569 }
570
571 static void decrementRefs(Char* p) {
572 auto const dis = fromData(p);
573 size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
574 FBSTRING_ASSERT(oldcnt > 0);
575 if (oldcnt == 1) {
576 free(dis);
577 }
578 }
579
580 static RefCounted* create(size_t* size) {
581 const size_t allocSize =
582 goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));
583 auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
584 result->refCount_.store(1, std::memory_order_release);
585 *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;
586 return result;
587 }
588
589 static RefCounted* create(const Char* data, size_t* size) {
590 const size_t effectiveSize = *size;
591 auto result = create(size);
592 if (FBSTRING_LIKELY(effectiveSize > 0)) {
593 fbstring_detail::podCopy(data, data + effectiveSize, result->data_);
594 }
595 return result;
596 }
597
598 static RefCounted* reallocate(
599 Char* const data,
600 const size_t currentSize,
601 const size_t currentCapacity,
602 size_t* newCapacity) {
603 FBSTRING_ASSERT(*newCapacity > 0 && *newCapacity > currentSize);
604 const size_t allocNewCapacity =
605 goodMallocSize(getDataOffset() + (*newCapacity + 1) * sizeof(Char));
606 auto const dis = fromData(data);
607 FBSTRING_ASSERT(dis->refCount_.load(std::memory_order_acquire) == 1);
608 auto result = static_cast<RefCounted*>(smartRealloc(
609 dis,
610 getDataOffset() + (currentSize + 1) * sizeof(Char),
611 getDataOffset() + (currentCapacity + 1) * sizeof(Char),
612 allocNewCapacity));
613 FBSTRING_ASSERT(result->refCount_.load(std::memory_order_acquire) == 1);
614 *newCapacity = (allocNewCapacity - getDataOffset()) / sizeof(Char) - 1;
615 return result;
616 }
617 };
618
619 typedef uint8_t category_type;
620
621 enum class Category : category_type {
622 isSmall = 0,
623 isMedium = kIsLittleEndian ? 0x80 : 0x2,
624 isLarge = kIsLittleEndian ? 0x40 : 0x1,
625 };
626
627 Category category() const {
628 // works for both big-endian and little-endian
629 return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);
630 }
631
632 struct MediumLarge {
633 Char* data_;
634 size_t size_;
635 size_t capacity_;
636
637 size_t capacity() const {
638 return kIsLittleEndian ? capacity_ & capacityExtractMask : capacity_ >> 2;
639 }
640
641 void setCapacity(size_t cap, Category cat) {
642 capacity_ = kIsLittleEndian
643 ? cap | (static_cast<size_t>(cat) << kCategoryShift)
644 : (cap << 2) | static_cast<size_t>(cat);
645 }
646 };
647
648 union {
649 uint8_t bytes_[sizeof(MediumLarge)]; // For accessing the last byte.
650 Char small_[sizeof(MediumLarge) / sizeof(Char)];
651 MediumLarge ml_;
652 };
653
654 constexpr static size_t lastChar = sizeof(MediumLarge) - 1;
655 constexpr static size_t maxSmallSize = lastChar / sizeof(Char);
656 constexpr static size_t maxMediumSize = 254 / sizeof(Char);
657 constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;
658 constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;
659 constexpr static size_t capacityExtractMask = kIsLittleEndian
660 ? ~(size_t(categoryExtractMask) << kCategoryShift)
661 : 0x0 /* unused */;
662
663 static_assert(
664 !(sizeof(MediumLarge) % sizeof(Char)),
665 "Corrupt memory layout for fbstring.");
666
667 size_t smallSize() const {
668 FBSTRING_ASSERT(category() == Category::isSmall);
669 constexpr auto shift = kIsLittleEndian ? 0 : 2;
670 auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;
671 FBSTRING_ASSERT(static_cast<size_t>(maxSmallSize) >= smallShifted);
672 return static_cast<size_t>(maxSmallSize) - smallShifted;
673 }
674
675 void setSmallSize(size_t s) {
676 // Warning: this should work with uninitialized strings too,
677 // so don't assume anything about the previous value of
678 // small_[maxSmallSize].
679 FBSTRING_ASSERT(s <= maxSmallSize);
680 constexpr auto shift = kIsLittleEndian ? 0 : 2;
681 small_[maxSmallSize] = char((maxSmallSize - s) << shift);
682 small_[s] = '\0';
683 FBSTRING_ASSERT(category() == Category::isSmall && size() == s);
684 }
685
686 void copySmall(const fbstring_core&);
687 void copyMedium(const fbstring_core&);
688 void copyLarge(const fbstring_core&);
689
690 void initSmall(const Char* data, size_t size);
691 void initMedium(const Char* data, size_t size);
692 void initLarge(const Char* data, size_t size);
693
694 void reserveSmall(size_t minCapacity, bool disableSSO);
695 void reserveMedium(size_t minCapacity);
696 void reserveLarge(size_t minCapacity);
697
698 void shrinkSmall(size_t delta);
699 void shrinkMedium(size_t delta);
700 void shrinkLarge(size_t delta);
701
702 void unshare(size_t minCapacity = 0);
703 Char* mutableDataLarge();
704};
705
706template <class Char>
707inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {
708 static_assert(offsetof(MediumLarge, data_) == 0, "fbstring layout failure");
709 static_assert(
710 offsetof(MediumLarge, size_) == sizeof(ml_.data_),
711 "fbstring layout failure");
712 static_assert(
713 offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_),
714 "fbstring layout failure");
715 // Just write the whole thing, don't look at details. In
716 // particular we need to copy capacity anyway because we want
717 // to set the size (don't forget that the last character,
718 // which stores a short string's length, is shared with the
719 // ml_.capacity field).
720 ml_ = rhs.ml_;
721 FBSTRING_ASSERT(
722 category() == Category::isSmall && this->size() == rhs.size());
723}
724
725template <class Char>
726FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyMedium(
727 const fbstring_core& rhs) {
728 // Medium strings are copied eagerly. Don't forget to allocate
729 // one extra Char for the null terminator.
730 auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
731 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
732 // Also copies terminator.
733 fbstring_detail::podCopy(
734 rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);
735 ml_.size_ = rhs.ml_.size_;
736 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
737 FBSTRING_ASSERT(category() == Category::isMedium);
738}
739
740template <class Char>
741FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::copyLarge(
742 const fbstring_core& rhs) {
743 // Large strings are just refcounted
744 ml_ = rhs.ml_;
745 RefCounted::incrementRefs(ml_.data_);
746 FBSTRING_ASSERT(category() == Category::isLarge && size() == rhs.size());
747}
748
749// Small strings are bitblitted
750template <class Char>
751inline void fbstring_core<Char>::initSmall(
752 const Char* const data,
753 const size_t size) {
754 // Layout is: Char* data_, size_t size_, size_t capacity_
755 static_assert(
756 sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t),
757 "fbstring has unexpected size");
758 static_assert(
759 sizeof(Char*) == sizeof(size_t), "fbstring size assumption violation");
760 // sizeof(size_t) must be a power of 2
761 static_assert(
762 (sizeof(size_t) & (sizeof(size_t) - 1)) == 0,
763 "fbstring size assumption violation");
764
765// If data is aligned, use fast word-wise copying. Otherwise,
766// use conservative memcpy.
767// The word-wise path reads bytes which are outside the range of
768// the string, and makes ASan unhappy, so we disable it when
769// compiling with ASan.
770#ifndef FBSTRING_SANITIZE_ADDRESS
771 if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {
772 const size_t byteSize = size * sizeof(Char);
773 constexpr size_t wordWidth = sizeof(size_t);
774 switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.
775 case 3:
776 ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
777 FOLLY_FALLTHROUGH;
778 case 2:
779 ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
780 FOLLY_FALLTHROUGH;
781 case 1:
782 ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
783 FOLLY_FALLTHROUGH;
784 case 0:
785 break;
786 }
787 } else
788#endif
789 {
790 if (size != 0) {
791 fbstring_detail::podCopy(data, data + size, small_);
792 }
793 }
794 setSmallSize(size);
795}
796
797template <class Char>
798FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initMedium(
799 const Char* const data,
800 const size_t size) {
801 // Medium strings are allocated normally. Don't forget to
802 // allocate one extra Char for the terminating null.
803 auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
804 ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
805 if (FBSTRING_LIKELY(size > 0)) {
806 fbstring_detail::podCopy(data, data + size, ml_.data_);
807 }
808 ml_.size_ = size;
809 ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);
810 ml_.data_[size] = '\0';
811}
812
813template <class Char>
814FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::initLarge(
815 const Char* const data,
816 const size_t size) {
817 // Large strings are allocated differently
818 size_t effectiveCapacity = size;
819 auto const newRC = RefCounted::create(data, &effectiveCapacity);
820 ml_.data_ = newRC->data_;
821 ml_.size_ = size;
822 ml_.setCapacity(effectiveCapacity, Category::isLarge);
823 ml_.data_[size] = '\0';
824}
825
826template <class Char>
827FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(
828 size_t minCapacity) {
829 FBSTRING_ASSERT(category() == Category::isLarge);
830 size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());
831 auto const newRC = RefCounted::create(&effectiveCapacity);
832 // If this fails, someone placed the wrong capacity in an
833 // fbstring.
834 FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());
835 // Also copies terminator.
836 fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);
837 RefCounted::decrementRefs(ml_.data_);
838 ml_.data_ = newRC->data_;
839 ml_.setCapacity(effectiveCapacity, Category::isLarge);
840 // size_ remains unchanged.
841}
842
843template <class Char>
844inline Char* fbstring_core<Char>::mutableDataLarge() {
845 FBSTRING_ASSERT(category() == Category::isLarge);
846 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.
847 unshare();
848 }
849 return ml_.data_;
850}
851
852template <class Char>
853FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveLarge(
854 size_t minCapacity) {
855 FBSTRING_ASSERT(category() == Category::isLarge);
856 if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique
857 // We must make it unique regardless; in-place reallocation is
858 // useless if the string is shared. In order to not surprise
859 // people, reserve the new block at current capacity or
860 // more. That way, a string's capacity never shrinks after a
861 // call to reserve.
862 unshare(minCapacity);
863 } else {
864 // String is not shared, so let's try to realloc (if needed)
865 if (minCapacity > ml_.capacity()) {
866 // Asking for more memory
867 auto const newRC = RefCounted::reallocate(
868 ml_.data_, ml_.size_, ml_.capacity(), &minCapacity);
869 ml_.data_ = newRC->data_;
870 ml_.setCapacity(minCapacity, Category::isLarge);
871 }
872 FBSTRING_ASSERT(capacity() >= minCapacity);
873 }
874}
875
876template <class Char>
877FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveMedium(
878 const size_t minCapacity) {
879 FBSTRING_ASSERT(category() == Category::isMedium);
880 // String is not shared
881 if (minCapacity <= ml_.capacity()) {
882 return; // nothing to do, there's enough room
883 }
884 if (minCapacity <= maxMediumSize) {
885 // Keep the string at medium size. Don't forget to allocate
886 // one extra Char for the terminating null.
887 size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
888 // Also copies terminator.
889 ml_.data_ = static_cast<Char*>(smartRealloc(
890 ml_.data_,
891 (ml_.size_ + 1) * sizeof(Char),
892 (ml_.capacity() + 1) * sizeof(Char),
893 capacityBytes));
894 ml_.setCapacity(capacityBytes / sizeof(Char) - 1, Category::isMedium);
895 } else {
896 // Conversion from medium to large string
897 fbstring_core nascent;
898 // Will recurse to another branch of this function
899 nascent.reserve(minCapacity);
900 nascent.ml_.size_ = ml_.size_;
901 // Also copies terminator.
902 fbstring_detail::podCopy(
903 ml_.data_, ml_.data_ + ml_.size_ + 1, nascent.ml_.data_);
904 nascent.swap(*this);
905 FBSTRING_ASSERT(capacity() >= minCapacity);
906 }
907}
908
909template <class Char>
910FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::reserveSmall(
911 size_t minCapacity,
912 const bool disableSSO) {
913 FBSTRING_ASSERT(category() == Category::isSmall);
914 if (!disableSSO && minCapacity <= maxSmallSize) {
915 // small
916 // Nothing to do, everything stays put
917 } else if (minCapacity <= maxMediumSize) {
918 // medium
919 // Don't forget to allocate one extra Char for the terminating null
920 auto const allocSizeBytes =
921 goodMallocSize((1 + minCapacity) * sizeof(Char));
922 auto const pData = static_cast<Char*>(checkedMalloc(allocSizeBytes));
923 auto const size = smallSize();
924 // Also copies terminator.
925 fbstring_detail::podCopy(small_, small_ + size + 1, pData);
926 ml_.data_ = pData;
927 ml_.size_ = size;
928 ml_.setCapacity(allocSizeBytes / sizeof(Char) - 1, Category::isMedium);
929 } else {
930 // large
931 auto const newRC = RefCounted::create(&minCapacity);
932 auto const size = smallSize();
933 // Also copies terminator.
934 fbstring_detail::podCopy(small_, small_ + size + 1, newRC->data_);
935 ml_.data_ = newRC->data_;
936 ml_.size_ = size;
937 ml_.setCapacity(minCapacity, Category::isLarge);
938 FBSTRING_ASSERT(capacity() >= minCapacity);
939 }
940}
941
942template <class Char>
943inline Char* fbstring_core<Char>::expandNoinit(
944 const size_t delta,
945 bool expGrowth, /* = false */
946 bool disableSSO /* = FBSTRING_DISABLE_SSO */) {
947 // Strategy is simple: make room, then change size
948 FBSTRING_ASSERT(capacity() >= size());
949 size_t sz, newSz;
950 if (category() == Category::isSmall) {
951 sz = smallSize();
952 newSz = sz + delta;
953 if (!disableSSO && FBSTRING_LIKELY(newSz <= maxSmallSize)) {
954 setSmallSize(newSz);
955 return small_ + sz;
956 }
957 reserveSmall(
958 expGrowth ? std::max(newSz, 2 * maxSmallSize) : newSz, disableSSO);
959 } else {
960 sz = ml_.size_;
961 newSz = sz + delta;
962 if (FBSTRING_UNLIKELY(newSz > capacity())) {
963 // ensures not shared
964 reserve(expGrowth ? std::max(newSz, 1 + capacity() * 3 / 2) : newSz);
965 }
966 }
967 FBSTRING_ASSERT(capacity() >= newSz);
968 // Category can't be small - we took care of that above
969 FBSTRING_ASSERT(
970 category() == Category::isMedium || category() == Category::isLarge);
971 ml_.size_ = newSz;
972 ml_.data_[newSz] = '\0';
973 FBSTRING_ASSERT(size() == newSz);
974 return ml_.data_ + sz;
975}
976
977template <class Char>
978inline void fbstring_core<Char>::shrinkSmall(const size_t delta) {
979 // Check for underflow
980 FBSTRING_ASSERT(delta <= smallSize());
981 setSmallSize(smallSize() - delta);
982}
983
984template <class Char>
985inline void fbstring_core<Char>::shrinkMedium(const size_t delta) {
986 // Medium strings and unique large strings need no special
987 // handling.
988 FBSTRING_ASSERT(ml_.size_ >= delta);
989 ml_.size_ -= delta;
990 ml_.data_[ml_.size_] = '\0';
991}
992
993template <class Char>
994inline void fbstring_core<Char>::shrinkLarge(const size_t delta) {
995 FBSTRING_ASSERT(ml_.size_ >= delta);
996 // Shared large string, must make unique. This is because of the
997 // durn terminator must be written, which may trample the shared
998 // data.
999 if (delta) {
1000 fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
1001 }
1002 // No need to write the terminator.
1003}
1004
1005#ifndef _LIBSTDCXX_FBSTRING
1006/**
1007 * Dummy fbstring core that uses an actual std::string. This doesn't
1008 * make any sense - it's just for testing purposes.
1009 */
1010template <class Char>
1011class dummy_fbstring_core {
1012 public:
1013 dummy_fbstring_core() {}
1014 dummy_fbstring_core(const dummy_fbstring_core& another)
1015 : backend_(another.backend_) {}
1016 dummy_fbstring_core(const Char* s, size_t n) : backend_(s, n) {}
1017 void swap(dummy_fbstring_core& rhs) {
1018 backend_.swap(rhs.backend_);
1019 }
1020 const Char* data() const {
1021 return backend_.data();
1022 }
1023 Char* mutableData() {
1024 return const_cast<Char*>(backend_.data());
1025 }
1026 void shrink(size_t delta) {
1027 FBSTRING_ASSERT(delta <= size());
1028 backend_.resize(size() - delta);
1029 }
1030 Char* expandNoinit(size_t delta) {
1031 auto const sz = size();
1032 backend_.resize(size() + delta);
1033 return backend_.data() + sz;
1034 }
1035 void push_back(Char c) {
1036 backend_.push_back(c);
1037 }
1038 size_t size() const {
1039 return backend_.size();
1040 }
1041 size_t capacity() const {
1042 return backend_.capacity();
1043 }
1044 bool isShared() const {
1045 return false;
1046 }
1047 void reserve(size_t minCapacity) {
1048 backend_.reserve(minCapacity);
1049 }
1050
1051 private:
1052 std::basic_string<Char> backend_;
1053};
1054#endif // !_LIBSTDCXX_FBSTRING
1055
1056/**
1057 * This is the basic_string replacement. For conformity,
1058 * basic_fbstring takes the same template parameters, plus the last
1059 * one which is the core.
1060 */
1061#ifdef _LIBSTDCXX_FBSTRING
1062template <typename E, class T, class A, class Storage>
1063#else
1064template <
1065 typename E,
1066 class T = std::char_traits<E>,
1067 class A = std::allocator<E>,
1068 class Storage = fbstring_core<E>>
1069#endif
1070class basic_fbstring {
1071 template <typename Ex, typename... Args>
1072 FOLLY_ALWAYS_INLINE static void enforce(bool condition, Args&&... args) {
1073 if (!condition) {
1074 throw_exception<Ex>(static_cast<Args&&>(args)...);
1075 }
1076 }
1077
1078 bool isSane() const {
1079 return begin() <= end() && empty() == (size() == 0) &&
1080 empty() == (begin() == end()) && size() <= max_size() &&
1081 capacity() <= max_size() && size() <= capacity() &&
1082 begin()[size()] == '\0';
1083 }
1084
1085 struct Invariant {
1086 Invariant& operator=(const Invariant&) = delete;
1087 explicit Invariant(const basic_fbstring& s) noexcept : s_(s) {
1088 FBSTRING_ASSERT(s_.isSane());
1089 }
1090 ~Invariant() noexcept {
1091 FBSTRING_ASSERT(s_.isSane());
1092 }
1093
1094 private:
1095 const basic_fbstring& s_;
1096 };
1097
1098 public:
1099 // types
1100 typedef T traits_type;
1101 typedef typename traits_type::char_type value_type;
1102 typedef A allocator_type;
1103 typedef typename A::size_type size_type;
1104 typedef typename A::difference_type difference_type;
1105
1106 typedef typename A::reference reference;
1107 typedef typename A::const_reference const_reference;
1108 typedef typename A::pointer pointer;
1109 typedef typename A::const_pointer const_pointer;
1110
1111 typedef E* iterator;
1112 typedef const E* const_iterator;
1113 typedef std::reverse_iterator<iterator> reverse_iterator;
1114 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
1115
1116 static constexpr size_type npos = size_type(-1);
1117 typedef std::true_type IsRelocatable;
1118
1119 private:
1120 static void procrustes(size_type& n, size_type nmax) {
1121 if (n > nmax) {
1122 n = nmax;
1123 }
1124 }
1125
1126 static size_type traitsLength(const value_type* s);
1127
1128 public:
1129 // C++11 21.4.2 construct/copy/destroy
1130
1131 // Note: while the following two constructors can be (and previously were)
1132 // collapsed into one constructor written this way:
1133 //
1134 // explicit basic_fbstring(const A& a = A()) noexcept { }
1135 //
1136 // This can cause Clang (at least version 3.7) to fail with the error:
1137 // "chosen constructor is explicit in copy-initialization ...
1138 // in implicit initialization of field '(x)' with omitted initializer"
1139 //
1140 // if used in a struct which is default-initialized. Hence the split into
1141 // these two separate constructors.
1142
1143 basic_fbstring() noexcept : basic_fbstring(A()) {}
1144
1145 explicit basic_fbstring(const A&) noexcept {}
1146
1147 basic_fbstring(const basic_fbstring& str) : store_(str.store_) {}
1148
1149 // Move constructor
1150 basic_fbstring(basic_fbstring&& goner) noexcept
1151 : store_(std::move(goner.store_)) {}
1152
1153#ifndef _LIBSTDCXX_FBSTRING
1154 // This is defined for compatibility with std::string
1155 template <typename A2>
1156 /* implicit */ basic_fbstring(const std::basic_string<E, T, A2>& str)
1157 : store_(str.data(), str.size()) {}
1158#endif
1159
1160 basic_fbstring(
1161 const basic_fbstring& str,
1162 size_type pos,
1163 size_type n = npos,
1164 const A& /* a */ = A()) {
1165 assign(str, pos, n);
1166 }
1167
1168 FOLLY_MALLOC_NOINLINE
1169 /* implicit */ basic_fbstring(const value_type* s, const A& /*a*/ = A())
1170 : store_(s, traitsLength(s)) {}
1171
1172 FOLLY_MALLOC_NOINLINE
1173 basic_fbstring(const value_type* s, size_type n, const A& /*a*/ = A())
1174 : store_(s, n) {}
1175
1176 FOLLY_MALLOC_NOINLINE
1177 basic_fbstring(size_type n, value_type c, const A& /*a*/ = A()) {
1178 auto const pData = store_.expandNoinit(n);
1179 fbstring_detail::podFill(pData, pData + n, c);
1180 }
1181
1182 template <class InIt>
1183 FOLLY_MALLOC_NOINLINE basic_fbstring(
1184 InIt begin,
1185 InIt end,
1186 typename std::enable_if<
1187 !std::is_same<InIt, value_type*>::value,
1188 const A>::type& /*a*/
1189 = A()) {
1190 assign(begin, end);
1191 }
1192
1193 // Specialization for const char*, const char*
1194 FOLLY_MALLOC_NOINLINE
1195 basic_fbstring(const value_type* b, const value_type* e, const A& /*a*/ = A())
1196 : store_(b, size_type(e - b)) {}
1197
1198 // Nonstandard constructor
1199 basic_fbstring(
1200 value_type* s,
1201 size_type n,
1202 size_type c,
1203 AcquireMallocatedString a)
1204 : store_(s, n, c, a) {}
1205
1206 // Construction from initialization list
1207 FOLLY_MALLOC_NOINLINE
1208 basic_fbstring(std::initializer_list<value_type> il) {
1209 assign(il.begin(), il.end());
1210 }
1211
1212 ~basic_fbstring() noexcept {}
1213
1214 basic_fbstring& operator=(const basic_fbstring& lhs);
1215
1216 // Move assignment
1217 basic_fbstring& operator=(basic_fbstring&& goner) noexcept;
1218
1219#ifndef _LIBSTDCXX_FBSTRING
1220 // Compatibility with std::string
1221 template <typename A2>
1222 basic_fbstring& operator=(const std::basic_string<E, T, A2>& rhs) {
1223 return assign(rhs.data(), rhs.size());
1224 }
1225
1226 // Compatibility with std::string
1227 std::basic_string<E, T, A> toStdString() const {
1228 return std::basic_string<E, T, A>(data(), size());
1229 }
1230#else
1231 // A lot of code in fbcode still uses this method, so keep it here for now.
1232 const basic_fbstring& toStdString() const {
1233 return *this;
1234 }
1235#endif
1236
1237 basic_fbstring& operator=(const value_type* s) {
1238 return assign(s);
1239 }
1240
1241 // This actually goes directly against the C++ spec, but the
1242 // value_type overload is dangerous, so we're explicitly deleting
1243 // any overloads of operator= that could implicitly convert to
1244 // value_type.
1245 // Note that we do need to explicitly specify the template types because
1246 // otherwise MSVC 2017 will aggressively pre-resolve value_type to
1247 // traits_type::char_type, which won't compare as equal when determining
1248 // which overload the implementation is referring to.
1249 // Also note that MSVC 2015 Update 3 requires us to explicitly specify the
1250 // namespace in-which to search for basic_fbstring, otherwise it tries to
1251 // look for basic_fbstring::basic_fbstring, which is just plain wrong.
1252 template <typename TP>
1253 typename std::enable_if<
1254 std::is_same<
1255 typename std::decay<TP>::type,
1256 typename folly::basic_fbstring<E, T, A, Storage>::value_type>::value,
1257 basic_fbstring<E, T, A, Storage>&>::type
1258 operator=(TP c);
1259
1260 basic_fbstring& operator=(std::initializer_list<value_type> il) {
1261 return assign(il.begin(), il.end());
1262 }
1263
1264 // C++11 21.4.3 iterators:
1265 iterator begin() {
1266 return store_.mutableData();
1267 }
1268
1269 const_iterator begin() const {
1270 return store_.data();
1271 }
1272
1273 const_iterator cbegin() const {
1274 return begin();
1275 }
1276
1277 iterator end() {
1278 return store_.mutableData() + store_.size();
1279 }
1280
1281 const_iterator end() const {
1282 return store_.data() + store_.size();
1283 }
1284
1285 const_iterator cend() const {
1286 return end();
1287 }
1288
1289 reverse_iterator rbegin() {
1290 return reverse_iterator(end());
1291 }
1292
1293 const_reverse_iterator rbegin() const {
1294 return const_reverse_iterator(end());
1295 }
1296
1297 const_reverse_iterator crbegin() const {
1298 return rbegin();
1299 }
1300
1301 reverse_iterator rend() {
1302 return reverse_iterator(begin());
1303 }
1304
1305 const_reverse_iterator rend() const {
1306 return const_reverse_iterator(begin());
1307 }
1308
1309 const_reverse_iterator crend() const {
1310 return rend();
1311 }
1312
1313 // Added by C++11
1314 // C++11 21.4.5, element access:
1315 const value_type& front() const {
1316 return *begin();
1317 }
1318 const value_type& back() const {
1319 FBSTRING_ASSERT(!empty());
1320 // Should be begin()[size() - 1], but that branches twice
1321 return *(end() - 1);
1322 }
1323 value_type& front() {
1324 return *begin();
1325 }
1326 value_type& back() {
1327 FBSTRING_ASSERT(!empty());
1328 // Should be begin()[size() - 1], but that branches twice
1329 return *(end() - 1);
1330 }
1331 void pop_back() {
1332 FBSTRING_ASSERT(!empty());
1333 store_.shrink(1);
1334 }
1335
1336 // C++11 21.4.4 capacity:
1337 size_type size() const {
1338 return store_.size();
1339 }
1340
1341 size_type length() const {
1342 return size();
1343 }
1344
1345 size_type max_size() const {
1346 return std::numeric_limits<size_type>::max();
1347 }
1348
1349 void resize(size_type n, value_type c = value_type());
1350
1351 size_type capacity() const {
1352 return store_.capacity();
1353 }
1354
1355 void reserve(size_type res_arg = 0) {
1356 enforce<std::length_error>(res_arg <= max_size(), "");
1357 store_.reserve(res_arg);
1358 }
1359
1360 void shrink_to_fit() {
1361 // Shrink only if slack memory is sufficiently large
1362 if (capacity() < size() * 3 / 2) {
1363 return;
1364 }
1365 basic_fbstring(cbegin(), cend()).swap(*this);
1366 }
1367
1368 void clear() {
1369 resize(0);
1370 }
1371
1372 bool empty() const {
1373 return size() == 0;
1374 }
1375
1376 // C++11 21.4.5 element access:
1377 const_reference operator[](size_type pos) const {
1378 return *(begin() + pos);
1379 }
1380
1381 reference operator[](size_type pos) {
1382 return *(begin() + pos);
1383 }
1384
1385 const_reference at(size_type n) const {
1386 enforce<std::out_of_range>(n < size(), "");
1387 return (*this)[n];
1388 }
1389
1390 reference at(size_type n) {
1391 enforce<std::out_of_range>(n < size(), "");
1392 return (*this)[n];
1393 }
1394
1395 // C++11 21.4.6 modifiers:
1396 basic_fbstring& operator+=(const basic_fbstring& str) {
1397 return append(str);
1398 }
1399
1400 basic_fbstring& operator+=(const value_type* s) {
1401 return append(s);
1402 }
1403
1404 basic_fbstring& operator+=(const value_type c) {
1405 push_back(c);
1406 return *this;
1407 }
1408
1409 basic_fbstring& operator+=(std::initializer_list<value_type> il) {
1410 append(il);
1411 return *this;
1412 }
1413
1414 basic_fbstring& append(const basic_fbstring& str);
1415
1416 basic_fbstring&
1417 append(const basic_fbstring& str, const size_type pos, size_type n);
1418
1419 basic_fbstring& append(const value_type* s, size_type n);
1420
1421 basic_fbstring& append(const value_type* s) {
1422 return append(s, traitsLength(s));
1423 }
1424
1425 basic_fbstring& append(size_type n, value_type c);
1426
1427 template <class InputIterator>
1428 basic_fbstring& append(InputIterator first, InputIterator last) {
1429 insert(end(), first, last);
1430 return *this;
1431 }
1432
1433 basic_fbstring& append(std::initializer_list<value_type> il) {
1434 return append(il.begin(), il.end());
1435 }
1436
1437 void push_back(const value_type c) { // primitive
1438 store_.push_back(c);
1439 }
1440
1441 basic_fbstring& assign(const basic_fbstring& str) {
1442 if (&str == this) {
1443 return *this;
1444 }
1445 return assign(str.data(), str.size());
1446 }
1447
1448 basic_fbstring& assign(basic_fbstring&& str) {
1449 return *this = std::move(str);
1450 }
1451
1452 basic_fbstring&
1453 assign(const basic_fbstring& str, const size_type pos, size_type n);
1454
1455 basic_fbstring& assign(const value_type* s, const size_type n);
1456
1457 basic_fbstring& assign(const value_type* s) {
1458 return assign(s, traitsLength(s));
1459 }
1460
1461 basic_fbstring& assign(std::initializer_list<value_type> il) {
1462 return assign(il.begin(), il.end());
1463 }
1464
1465 template <class ItOrLength, class ItOrChar>
1466 basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1467 return replace(begin(), end(), first_or_n, last_or_c);
1468 }
1469
1470 basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1471 return insert(pos1, str.data(), str.size());
1472 }
1473
1474 basic_fbstring& insert(
1475 size_type pos1,
1476 const basic_fbstring& str,
1477 size_type pos2,
1478 size_type n) {
1479 enforce<std::out_of_range>(pos2 <= str.length(), "");
1480 procrustes(n, str.length() - pos2);
1481 return insert(pos1, str.data() + pos2, n);
1482 }
1483
1484 basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1485 enforce<std::out_of_range>(pos <= length(), "");
1486 insert(begin() + pos, s, s + n);
1487 return *this;
1488 }
1489
1490 basic_fbstring& insert(size_type pos, const value_type* s) {
1491 return insert(pos, s, traitsLength(s));
1492 }
1493
1494 basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1495 enforce<std::out_of_range>(pos <= length(), "");
1496 insert(begin() + pos, n, c);
1497 return *this;
1498 }
1499
1500 iterator insert(const_iterator p, const value_type c) {
1501 const size_type pos = p - cbegin();
1502 insert(p, 1, c);
1503 return begin() + pos;
1504 }
1505
1506#ifndef _LIBSTDCXX_FBSTRING
1507 private:
1508 typedef std::basic_istream<value_type, traits_type> istream_type;
1509 istream_type& getlineImpl(istream_type& is, value_type delim);
1510
1511 public:
1512 friend inline istream_type&
1513 getline(istream_type& is, basic_fbstring& str, value_type delim) {
1514 return str.getlineImpl(is, delim);
1515 }
1516
1517 friend inline istream_type& getline(istream_type& is, basic_fbstring& str) {
1518 return getline(is, str, '\n');
1519 }
1520#endif
1521
1522 private:
1523 iterator
1524 insertImplDiscr(const_iterator i, size_type n, value_type c, std::true_type);
1525
1526 template <class InputIter>
1527 iterator
1528 insertImplDiscr(const_iterator i, InputIter b, InputIter e, std::false_type);
1529
1530 template <class FwdIterator>
1531 iterator insertImpl(
1532 const_iterator i,
1533 FwdIterator s1,
1534 FwdIterator s2,
1535 std::forward_iterator_tag);
1536
1537 template <class InputIterator>
1538 iterator insertImpl(
1539 const_iterator i,
1540 InputIterator b,
1541 InputIterator e,
1542 std::input_iterator_tag);
1543
1544 public:
1545 template <class ItOrLength, class ItOrChar>
1546 iterator insert(const_iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1547 using Sel = bool_constant<std::numeric_limits<ItOrLength>::is_specialized>;
1548 return insertImplDiscr(p, first_or_n, last_or_c, Sel());
1549 }
1550
1551 iterator insert(const_iterator p, std::initializer_list<value_type> il) {
1552 return insert(p, il.begin(), il.end());
1553 }
1554
1555 basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1556 Invariant checker(*this);
1557
1558 enforce<std::out_of_range>(pos <= length(), "");
1559 procrustes(n, length() - pos);
1560 std::copy(begin() + pos + n, end(), begin() + pos);
1561 resize(length() - n);
1562 return *this;
1563 }
1564
1565 iterator erase(iterator position) {
1566 const size_type pos(position - begin());
1567 enforce<std::out_of_range>(pos <= size(), "");
1568 erase(pos, 1);
1569 return begin() + pos;
1570 }
1571
1572 iterator erase(iterator first, iterator last) {
1573 const size_type pos(first - begin());
1574 erase(pos, last - first);
1575 return begin() + pos;
1576 }
1577
1578 // Replaces at most n1 chars of *this, starting with pos1 with the
1579 // content of str
1580 basic_fbstring&
1581 replace(size_type pos1, size_type n1, const basic_fbstring& str) {
1582 return replace(pos1, n1, str.data(), str.size());
1583 }
1584
1585 // Replaces at most n1 chars of *this, starting with pos1,
1586 // with at most n2 chars of str starting with pos2
1587 basic_fbstring& replace(
1588 size_type pos1,
1589 size_type n1,
1590 const basic_fbstring& str,
1591 size_type pos2,
1592 size_type n2) {
1593 enforce<std::out_of_range>(pos2 <= str.length(), "");
1594 return replace(
1595 pos1, n1, str.data() + pos2, std::min(n2, str.size() - pos2));
1596 }
1597
1598 // Replaces at most n1 chars of *this, starting with pos, with chars from s
1599 basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1600 return replace(pos, n1, s, traitsLength(s));
1601 }
1602
1603 // Replaces at most n1 chars of *this, starting with pos, with n2
1604 // occurrences of c
1605 //
1606 // consolidated with
1607 //
1608 // Replaces at most n1 chars of *this, starting with pos, with at
1609 // most n2 chars of str. str must have at least n2 chars.
1610 template <class StrOrLength, class NumOrChar>
1611 basic_fbstring&
1612 replace(size_type pos, size_type n1, StrOrLength s_or_n2, NumOrChar n_or_c) {
1613 Invariant checker(*this);
1614
1615 enforce<std::out_of_range>(pos <= size(), "");
1616 procrustes(n1, length() - pos);
1617 const iterator b = begin() + pos;
1618 return replace(b, b + n1, s_or_n2, n_or_c);
1619 }
1620
1621 basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1622 return replace(i1, i2, str.data(), str.length());
1623 }
1624
1625 basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1626 return replace(i1, i2, s, traitsLength(s));
1627 }
1628
1629 private:
1630 basic_fbstring& replaceImplDiscr(
1631 iterator i1,
1632 iterator i2,
1633 const value_type* s,
1634 size_type n,
1635 std::integral_constant<int, 2>);
1636
1637 basic_fbstring& replaceImplDiscr(
1638 iterator i1,
1639 iterator i2,
1640 size_type n2,
1641 value_type c,
1642 std::integral_constant<int, 1>);
1643
1644 template <class InputIter>
1645 basic_fbstring& replaceImplDiscr(
1646 iterator i1,
1647 iterator i2,
1648 InputIter b,
1649 InputIter e,
1650 std::integral_constant<int, 0>);
1651
1652 private:
1653 template <class FwdIterator>
1654 bool replaceAliased(
1655 iterator /* i1 */,
1656 iterator /* i2 */,
1657 FwdIterator /* s1 */,
1658 FwdIterator /* s2 */,
1659 std::false_type) {
1660 return false;
1661 }
1662
1663 template <class FwdIterator>
1664 bool replaceAliased(
1665 iterator i1,
1666 iterator i2,
1667 FwdIterator s1,
1668 FwdIterator s2,
1669 std::true_type);
1670
1671 template <class FwdIterator>
1672 void replaceImpl(
1673 iterator i1,
1674 iterator i2,
1675 FwdIterator s1,
1676 FwdIterator s2,
1677 std::forward_iterator_tag);
1678
1679 template <class InputIterator>
1680 void replaceImpl(
1681 iterator i1,
1682 iterator i2,
1683 InputIterator b,
1684 InputIterator e,
1685 std::input_iterator_tag);
1686
1687 public:
1688 template <class T1, class T2>
1689 basic_fbstring&
1690 replace(iterator i1, iterator i2, T1 first_or_n_or_s, T2 last_or_c_or_n) {
1691 constexpr bool num1 = std::numeric_limits<T1>::is_specialized,
1692 num2 = std::numeric_limits<T2>::is_specialized;
1693 using Sel =
1694 std::integral_constant<int, num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>;
1695 return replaceImplDiscr(i1, i2, first_or_n_or_s, last_or_c_or_n, Sel());
1696 }
1697
1698 size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1699 enforce<std::out_of_range>(pos <= size(), "");
1700 procrustes(n, size() - pos);
1701
1702 if (n != 0) {
1703 fbstring_detail::podCopy(data() + pos, data() + pos + n, s);
1704 }
1705 return n;
1706 }
1707
1708 void swap(basic_fbstring& rhs) {
1709 store_.swap(rhs.store_);
1710 }
1711
1712 const value_type* c_str() const {
1713 return store_.c_str();
1714 }
1715
1716 const value_type* data() const {
1717 return c_str();
1718 }
1719
1720 allocator_type get_allocator() const {
1721 return allocator_type();
1722 }
1723
1724 size_type find(const basic_fbstring& str, size_type pos = 0) const {
1725 return find(str.data(), pos, str.length());
1726 }
1727
1728 size_type find(const value_type* needle, size_type pos, size_type nsize)
1729 const;
1730
1731 size_type find(const value_type* s, size_type pos = 0) const {
1732 return find(s, pos, traitsLength(s));
1733 }
1734
1735 size_type find(value_type c, size_type pos = 0) const {
1736 return find(&c, pos, 1);
1737 }
1738
1739 size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1740 return rfind(str.data(), pos, str.length());
1741 }
1742
1743 size_type rfind(const value_type* s, size_type pos, size_type n) const;
1744
1745 size_type rfind(const value_type* s, size_type pos = npos) const {
1746 return rfind(s, pos, traitsLength(s));
1747 }
1748
1749 size_type rfind(value_type c, size_type pos = npos) const {
1750 return rfind(&c, pos, 1);
1751 }
1752
1753 size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1754 return find_first_of(str.data(), pos, str.length());
1755 }
1756
1757 size_type find_first_of(const value_type* s, size_type pos, size_type n)
1758 const;
1759
1760 size_type find_first_of(const value_type* s, size_type pos = 0) const {
1761 return find_first_of(s, pos, traitsLength(s));
1762 }
1763
1764 size_type find_first_of(value_type c, size_type pos = 0) const {
1765 return find_first_of(&c, pos, 1);
1766 }
1767
1768 size_type find_last_of(const basic_fbstring& str, size_type pos = npos)
1769 const {
1770 return find_last_of(str.data(), pos, str.length());
1771 }
1772
1773 size_type find_last_of(const value_type* s, size_type pos, size_type n) const;
1774
1775 size_type find_last_of(const value_type* s, size_type pos = npos) const {
1776 return find_last_of(s, pos, traitsLength(s));
1777 }
1778
1779 size_type find_last_of(value_type c, size_type pos = npos) const {
1780 return find_last_of(&c, pos, 1);
1781 }
1782
1783 size_type find_first_not_of(const basic_fbstring& str, size_type pos = 0)
1784 const {
1785 return find_first_not_of(str.data(), pos, str.size());
1786 }
1787
1788 size_type find_first_not_of(const value_type* s, size_type pos, size_type n)
1789 const;
1790
1791 size_type find_first_not_of(const value_type* s, size_type pos = 0) const {
1792 return find_first_not_of(s, pos, traitsLength(s));
1793 }
1794
1795 size_type find_first_not_of(value_type c, size_type pos = 0) const {
1796 return find_first_not_of(&c, pos, 1);
1797 }
1798
1799 size_type find_last_not_of(const basic_fbstring& str, size_type pos = npos)
1800 const {
1801 return find_last_not_of(str.data(), pos, str.length());
1802 }
1803
1804 size_type find_last_not_of(const value_type* s, size_type pos, size_type n)
1805 const;
1806
1807 size_type find_last_not_of(const value_type* s, size_type pos = npos) const {
1808 return find_last_not_of(s, pos, traitsLength(s));
1809 }
1810
1811 size_type find_last_not_of(value_type c, size_type pos = npos) const {
1812 return find_last_not_of(&c, pos, 1);
1813 }
1814
1815 basic_fbstring substr(size_type pos = 0, size_type n = npos) const& {
1816 enforce<std::out_of_range>(pos <= size(), "");
1817 return basic_fbstring(data() + pos, std::min(n, size() - pos));
1818 }
1819
1820 basic_fbstring substr(size_type pos = 0, size_type n = npos) && {
1821 enforce<std::out_of_range>(pos <= size(), "");
1822 erase(0, pos);
1823 if (n < size()) {
1824 resize(n);
1825 }
1826 return std::move(*this);
1827 }
1828
1829 int compare(const basic_fbstring& str) const {
1830 // FIX due to Goncalo N M de Carvalho July 18, 2005
1831 return compare(0, size(), str);
1832 }
1833
1834 int compare(size_type pos1, size_type n1, const basic_fbstring& str) const {
1835 return compare(pos1, n1, str.data(), str.size());
1836 }
1837
1838 int compare(size_type pos1, size_type n1, const value_type* s) const {
1839 return compare(pos1, n1, s, traitsLength(s));
1840 }
1841
1842 int compare(size_type pos1, size_type n1, const value_type* s, size_type n2)
1843 const {
1844 enforce<std::out_of_range>(pos1 <= size(), "");
1845 procrustes(n1, size() - pos1);
1846 // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1847 const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1848 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1849 }
1850
1851 int compare(
1852 size_type pos1,
1853 size_type n1,
1854 const basic_fbstring& str,
1855 size_type pos2,
1856 size_type n2) const {
1857 enforce<std::out_of_range>(pos2 <= str.size(), "");
1858 return compare(
1859 pos1, n1, str.data() + pos2, std::min(n2, str.size() - pos2));
1860 }
1861
1862 // Code from Jean-Francois Bastien (03/26/2007)
1863 int compare(const value_type* s) const {
1864 // Could forward to compare(0, size(), s, traitsLength(s))
1865 // but that does two extra checks
1866 const size_type n1(size()), n2(traitsLength(s));
1867 const int r = traits_type::compare(data(), s, std::min(n1, n2));
1868 return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1869 }
1870
1871 private:
1872 // Data
1873 Storage store_;
1874};
1875
1876template <typename E, class T, class A, class S>
1877FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
1878basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
1879 return s ? traits_type::length(s)
1880 : (throw_exception<std::logic_error>(
1881 "basic_fbstring: null pointer initializer not valid"),
1882 0);
1883}
1884
1885template <typename E, class T, class A, class S>
1886inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1887 const basic_fbstring& lhs) {
1888 Invariant checker(*this);
1889
1890 if (FBSTRING_UNLIKELY(&lhs == this)) {
1891 return *this;
1892 }
1893
1894 return assign(lhs.data(), lhs.size());
1895}
1896
1897// Move assignment
1898template <typename E, class T, class A, class S>
1899inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
1900 basic_fbstring&& goner) noexcept {
1901 if (FBSTRING_UNLIKELY(&goner == this)) {
1902 // Compatibility with std::basic_string<>,
1903 // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1904 return *this;
1905 }
1906 // No need of this anymore
1907 this->~basic_fbstring();
1908 // Move the goner into this
1909 new (&store_) S(std::move(goner.store_));
1910 return *this;
1911}
1912
1913template <typename E, class T, class A, class S>
1914template <typename TP>
1915inline typename std::enable_if<
1916 std::is_same<
1917 typename std::decay<TP>::type,
1918 typename folly::basic_fbstring<E, T, A, S>::value_type>::value,
1919 basic_fbstring<E, T, A, S>&>::type
1920basic_fbstring<E, T, A, S>::operator=(TP c) {
1921 Invariant checker(*this);
1922
1923 if (empty()) {
1924 store_.expandNoinit(1);
1925 } else if (store_.isShared()) {
1926 basic_fbstring(1, c).swap(*this);
1927 return *this;
1928 } else {
1929 store_.shrink(size() - 1);
1930 }
1931 front() = c;
1932 return *this;
1933}
1934
1935template <typename E, class T, class A, class S>
1936inline void basic_fbstring<E, T, A, S>::resize(
1937 const size_type n,
1938 const value_type c /*= value_type()*/) {
1939 Invariant checker(*this);
1940
1941 auto size = this->size();
1942 if (n <= size) {
1943 store_.shrink(size - n);
1944 } else {
1945 auto const delta = n - size;
1946 auto pData = store_.expandNoinit(delta);
1947 fbstring_detail::podFill(pData, pData + delta, c);
1948 }
1949 FBSTRING_ASSERT(this->size() == n);
1950}
1951
1952template <typename E, class T, class A, class S>
1953inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1954 const basic_fbstring& str) {
1955#ifndef NDEBUG
1956 auto desiredSize = size() + str.size();
1957#endif
1958 append(str.data(), str.size());
1959 FBSTRING_ASSERT(size() == desiredSize);
1960 return *this;
1961}
1962
1963template <typename E, class T, class A, class S>
1964inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
1965 const basic_fbstring& str,
1966 const size_type pos,
1967 size_type n) {
1968 const size_type sz = str.size();
1969 enforce<std::out_of_range>(pos <= sz, "");
1970 procrustes(n, sz - pos);
1971 return append(str.data() + pos, n);
1972}
1973
1974template <typename E, class T, class A, class S>
1975FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
1976basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
1977 Invariant checker(*this);
1978
1979 if (FBSTRING_UNLIKELY(!n)) {
1980 // Unlikely but must be done
1981 return *this;
1982 }
1983 auto const oldSize = size();
1984 auto const oldData = data();
1985 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
1986
1987 // Check for aliasing (rare). We could use "<=" here but in theory
1988 // those do not work for pointers unless the pointers point to
1989 // elements in the same array. For that reason we use
1990 // std::less_equal, which is guaranteed to offer a total order
1991 // over pointers. See discussion at http://goo.gl/Cy2ya for more
1992 // info.
1993 std::less_equal<const value_type*> le;
1994 if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1995 FBSTRING_ASSERT(le(s + n, oldData + oldSize));
1996 // expandNoinit() could have moved the storage, restore the source.
1997 s = data() + (s - oldData);
1998 fbstring_detail::podMove(s, s + n, pData);
1999 } else {
2000 fbstring_detail::podCopy(s, s + n, pData);
2001 }
2002
2003 FBSTRING_ASSERT(size() == oldSize + n);
2004 return *this;
2005}
2006
2007template <typename E, class T, class A, class S>
2008inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
2009 size_type n,
2010 value_type c) {
2011 Invariant checker(*this);
2012 auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
2013 fbstring_detail::podFill(pData, pData + n, c);
2014 return *this;
2015}
2016
2017template <typename E, class T, class A, class S>
2018inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
2019 const basic_fbstring& str,
2020 const size_type pos,
2021 size_type n) {
2022 const size_type sz = str.size();
2023 enforce<std::out_of_range>(pos <= sz, "");
2024 procrustes(n, sz - pos);
2025 return assign(str.data() + pos, n);
2026}
2027
2028template <typename E, class T, class A, class S>
2029FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
2030basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
2031 Invariant checker(*this);
2032
2033 if (n == 0) {
2034 resize(0);
2035 } else if (size() >= n) {
2036 // s can alias this, we need to use podMove.
2037 fbstring_detail::podMove(s, s + n, store_.mutableData());
2038 store_.shrink(size() - n);
2039 FBSTRING_ASSERT(size() == n);
2040 } else {
2041 // If n is larger than size(), s cannot alias this string's
2042 // storage.
2043 resize(0);
2044 // Do not use exponential growth here: assign() should be tight,
2045 // to mirror the behavior of the equivalent constructor.
2046 fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
2047 }
2048
2049 FBSTRING_ASSERT(size() == n);
2050 return *this;
2051}
2052
2053#ifndef _LIBSTDCXX_FBSTRING
2054template <typename E, class T, class A, class S>
2055inline typename basic_fbstring<E, T, A, S>::istream_type&
2056basic_fbstring<E, T, A, S>::getlineImpl(istream_type& is, value_type delim) {
2057 Invariant checker(*this);
2058
2059 clear();
2060 size_t size = 0;
2061 while (true) {
2062 size_t avail = capacity() - size;
2063 // fbstring has 1 byte extra capacity for the null terminator,
2064 // and getline null-terminates the read string.
2065 is.getline(store_.expandNoinit(avail), avail + 1, delim);
2066 size += is.gcount();
2067
2068 if (is.bad() || is.eof() || !is.fail()) {
2069 // Done by either failure, end of file, or normal read.
2070 if (!is.bad() && !is.eof()) {
2071 --size; // gcount() also accounts for the delimiter.
2072 }
2073 resize(size);
2074 break;
2075 }
2076
2077 FBSTRING_ASSERT(size == this->size());
2078 FBSTRING_ASSERT(size == capacity());
2079 // Start at minimum allocation 63 + terminator = 64.
2080 reserve(std::max<size_t>(63, 3 * size / 2));
2081 // Clear the error so we can continue reading.
2082 is.clear();
2083 }
2084 return is;
2085}
2086#endif
2087
2088template <typename E, class T, class A, class S>
2089inline typename basic_fbstring<E, T, A, S>::size_type
2090basic_fbstring<E, T, A, S>::find(
2091 const value_type* needle,
2092 const size_type pos,
2093 const size_type nsize) const {
2094 auto const size = this->size();
2095 // nsize + pos can overflow (eg pos == npos), guard against that by checking
2096 // that nsize + pos does not wrap around.
2097 if (nsize + pos > size || nsize + pos < pos) {
2098 return npos;
2099 }
2100
2101 if (nsize == 0) {
2102 return pos;
2103 }
2104 // Don't use std::search, use a Boyer-Moore-like trick by comparing
2105 // the last characters first
2106 auto const haystack = data();
2107 auto const nsize_1 = nsize - 1;
2108 auto const lastNeedle = needle[nsize_1];
2109
2110 // Boyer-Moore skip value for the last char in the needle. Zero is
2111 // not a valid value; skip will be computed the first time it's
2112 // needed.
2113 size_type skip = 0;
2114
2115 const E* i = haystack + pos;
2116 auto iEnd = haystack + size - nsize_1;
2117
2118 while (i < iEnd) {
2119 // Boyer-Moore: match the last element in the needle
2120 while (i[nsize_1] != lastNeedle) {
2121 if (++i == iEnd) {
2122 // not found
2123 return npos;
2124 }
2125 }
2126 // Here we know that the last char matches
2127 // Continue in pedestrian mode
2128 for (size_t j = 0;;) {
2129 FBSTRING_ASSERT(j < nsize);
2130 if (i[j] != needle[j]) {
2131 // Not found, we can skip
2132 // Compute the skip value lazily
2133 if (skip == 0) {
2134 skip = 1;
2135 while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
2136 ++skip;
2137 }
2138 }
2139 i += skip;
2140 break;
2141 }
2142 // Check if done searching
2143 if (++j == nsize) {
2144 // Yay
2145 return i - haystack;
2146 }
2147 }
2148 }
2149 return npos;
2150}
2151
2152template <typename E, class T, class A, class S>
2153inline typename basic_fbstring<E, T, A, S>::iterator
2154basic_fbstring<E, T, A, S>::insertImplDiscr(
2155 const_iterator i,
2156 size_type n,
2157 value_type c,
2158 std::true_type) {
2159 Invariant checker(*this);
2160
2161 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2162 const size_type pos = i - cbegin();
2163
2164 auto oldSize = size();
2165 store_.expandNoinit(n, /* expGrowth = */ true);
2166 auto b = begin();
2167 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2168 fbstring_detail::podFill(b + pos, b + pos + n, c);
2169
2170 return b + pos;
2171}
2172
2173template <typename E, class T, class A, class S>
2174template <class InputIter>
2175inline typename basic_fbstring<E, T, A, S>::iterator
2176basic_fbstring<E, T, A, S>::insertImplDiscr(
2177 const_iterator i,
2178 InputIter b,
2179 InputIter e,
2180 std::false_type) {
2181 return insertImpl(
2182 i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
2183}
2184
2185template <typename E, class T, class A, class S>
2186template <class FwdIterator>
2187inline typename basic_fbstring<E, T, A, S>::iterator
2188basic_fbstring<E, T, A, S>::insertImpl(
2189 const_iterator i,
2190 FwdIterator s1,
2191 FwdIterator s2,
2192 std::forward_iterator_tag) {
2193 Invariant checker(*this);
2194
2195 FBSTRING_ASSERT(i >= cbegin() && i <= cend());
2196 const size_type pos = i - cbegin();
2197 auto n = std::distance(s1, s2);
2198 FBSTRING_ASSERT(n >= 0);
2199
2200 auto oldSize = size();
2201 store_.expandNoinit(n, /* expGrowth = */ true);
2202 auto b = begin();
2203 fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
2204 std::copy(s1, s2, b + pos);
2205
2206 return b + pos;
2207}
2208
2209template <typename E, class T, class A, class S>
2210template <class InputIterator>
2211inline typename basic_fbstring<E, T, A, S>::iterator
2212basic_fbstring<E, T, A, S>::insertImpl(
2213 const_iterator i,
2214 InputIterator b,
2215 InputIterator e,
2216 std::input_iterator_tag) {
2217 const auto pos = i - cbegin();
2218 basic_fbstring temp(cbegin(), i);
2219 for (; b != e; ++b) {
2220 temp.push_back(*b);
2221 }
2222 temp.append(i, cend());
2223 swap(temp);
2224 return begin() + pos;
2225}
2226
2227template <typename E, class T, class A, class S>
2228inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2229 iterator i1,
2230 iterator i2,
2231 const value_type* s,
2232 size_type n,
2233 std::integral_constant<int, 2>) {
2234 FBSTRING_ASSERT(i1 <= i2);
2235 FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
2236 FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
2237 return replace(i1, i2, s, s + n);
2238}
2239
2240template <typename E, class T, class A, class S>
2241inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2242 iterator i1,
2243 iterator i2,
2244 size_type n2,
2245 value_type c,
2246 std::integral_constant<int, 1>) {
2247 const size_type n1 = i2 - i1;
2248 if (n1 > n2) {
2249 std::fill(i1, i1 + n2, c);
2250 erase(i1 + n2, i2);
2251 } else {
2252 std::fill(i1, i2, c);
2253 insert(i2, n2 - n1, c);
2254 }
2255 FBSTRING_ASSERT(isSane());
2256 return *this;
2257}
2258
2259template <typename E, class T, class A, class S>
2260template <class InputIter>
2261inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
2262 iterator i1,
2263 iterator i2,
2264 InputIter b,
2265 InputIter e,
2266 std::integral_constant<int, 0>) {
2267 using Cat = typename std::iterator_traits<InputIter>::iterator_category;
2268 replaceImpl(i1, i2, b, e, Cat());
2269 return *this;
2270}
2271
2272template <typename E, class T, class A, class S>
2273template <class FwdIterator>
2274inline bool basic_fbstring<E, T, A, S>::replaceAliased(
2275 iterator i1,
2276 iterator i2,
2277 FwdIterator s1,
2278 FwdIterator s2,
2279 std::true_type) {
2280 std::less_equal<const value_type*> le{};
2281 const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
2282 if (!aliased) {
2283 return false;
2284 }
2285 // Aliased replace, copy to new string
2286 basic_fbstring temp;
2287 temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
2288 temp.append(begin(), i1).append(s1, s2).append(i2, end());
2289 swap(temp);
2290 return true;
2291}
2292
2293template <typename E, class T, class A, class S>
2294template <class FwdIterator>
2295inline void basic_fbstring<E, T, A, S>::replaceImpl(
2296 iterator i1,
2297 iterator i2,
2298 FwdIterator s1,
2299 FwdIterator s2,
2300 std::forward_iterator_tag) {
2301 Invariant checker(*this);
2302
2303 // Handle aliased replace
2304 using Sel = bool_constant<
2305 std::is_same<FwdIterator, iterator>::value ||
2306 std::is_same<FwdIterator, const_iterator>::value>;
2307 if (replaceAliased(i1, i2, s1, s2, Sel())) {
2308 return;
2309 }
2310
2311 auto const n1 = i2 - i1;
2312 FBSTRING_ASSERT(n1 >= 0);
2313 auto const n2 = std::distance(s1, s2);
2314 FBSTRING_ASSERT(n2 >= 0);
2315
2316 if (n1 > n2) {
2317 // shrinks
2318 std::copy(s1, s2, i1);
2319 erase(i1 + n2, i2);
2320 } else {
2321 // grows
2322 s1 = fbstring_detail::copy_n(s1, n1, i1).first;
2323 insert(i2, s1, s2);
2324 }
2325 FBSTRING_ASSERT(isSane());
2326}
2327
2328template <typename E, class T, class A, class S>
2329template <class InputIterator>
2330inline void basic_fbstring<E, T, A, S>::replaceImpl(
2331 iterator i1,
2332 iterator i2,
2333 InputIterator b,
2334 InputIterator e,
2335 std::input_iterator_tag) {
2336 basic_fbstring temp(begin(), i1);
2337 temp.append(b, e).append(i2, end());
2338 swap(temp);
2339}
2340
2341template <typename E, class T, class A, class S>
2342inline typename basic_fbstring<E, T, A, S>::size_type
2343basic_fbstring<E, T, A, S>::rfind(
2344 const value_type* s,
2345 size_type pos,
2346 size_type n) const {
2347 if (n > length()) {
2348 return npos;
2349 }
2350 pos = std::min(pos, length() - n);
2351 if (n == 0) {
2352 return pos;
2353 }
2354
2355 const_iterator i(begin() + pos);
2356 for (;; --i) {
2357 if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
2358 return i - begin();
2359 }
2360 if (i == begin()) {
2361 break;
2362 }
2363 }
2364 return npos;
2365}
2366
2367template <typename E, class T, class A, class S>
2368inline typename basic_fbstring<E, T, A, S>::size_type
2369basic_fbstring<E, T, A, S>::find_first_of(
2370 const value_type* s,
2371 size_type pos,
2372 size_type n) const {
2373 if (pos > length() || n == 0) {
2374 return npos;
2375 }
2376 const_iterator i(begin() + pos), finish(end());
2377 for (; i != finish; ++i) {
2378 if (traits_type::find(s, n, *i) != nullptr) {
2379 return i - begin();
2380 }
2381 }
2382 return npos;
2383}
2384
2385template <typename E, class T, class A, class S>
2386inline typename basic_fbstring<E, T, A, S>::size_type
2387basic_fbstring<E, T, A, S>::find_last_of(
2388 const value_type* s,
2389 size_type pos,
2390 size_type n) const {
2391 if (!empty() && n > 0) {
2392 pos = std::min(pos, length() - 1);
2393 const_iterator i(begin() + pos);
2394 for (;; --i) {
2395 if (traits_type::find(s, n, *i) != nullptr) {
2396 return i - begin();
2397 }
2398 if (i == begin()) {
2399 break;
2400 }
2401 }
2402 }
2403 return npos;
2404}
2405
2406template <typename E, class T, class A, class S>
2407inline typename basic_fbstring<E, T, A, S>::size_type
2408basic_fbstring<E, T, A, S>::find_first_not_of(
2409 const value_type* s,
2410 size_type pos,
2411 size_type n) const {
2412 if (pos < length()) {
2413 const_iterator i(begin() + pos), finish(end());
2414 for (; i != finish; ++i) {
2415 if (traits_type::find(s, n, *i) == nullptr) {
2416 return i - begin();
2417 }
2418 }
2419 }
2420 return npos;
2421}
2422
2423template <typename E, class T, class A, class S>
2424inline typename basic_fbstring<E, T, A, S>::size_type
2425basic_fbstring<E, T, A, S>::find_last_not_of(
2426 const value_type* s,
2427 size_type pos,
2428 size_type n) const {
2429 if (!this->empty()) {
2430 pos = std::min(pos, size() - 1);
2431 const_iterator i(begin() + pos);
2432 for (;; --i) {
2433 if (traits_type::find(s, n, *i) == nullptr) {
2434 return i - begin();
2435 }
2436 if (i == begin()) {
2437 break;
2438 }
2439 }
2440 }
2441 return npos;
2442}
2443
2444// non-member functions
2445// C++11 21.4.8.1/1
2446template <typename E, class T, class A, class S>
2447inline basic_fbstring<E, T, A, S> operator+(
2448 const basic_fbstring<E, T, A, S>& lhs,
2449 const basic_fbstring<E, T, A, S>& rhs) {
2450 basic_fbstring<E, T, A, S> result;
2451 result.reserve(lhs.size() + rhs.size());
2452 result.append(lhs).append(rhs);
2453 return std::move(result);
2454}
2455
2456// C++11 21.4.8.1/2
2457template <typename E, class T, class A, class S>
2458inline basic_fbstring<E, T, A, S> operator+(
2459 basic_fbstring<E, T, A, S>&& lhs,
2460 const basic_fbstring<E, T, A, S>& rhs) {
2461 return std::move(lhs.append(rhs));
2462}
2463
2464// C++11 21.4.8.1/3
2465template <typename E, class T, class A, class S>
2466inline basic_fbstring<E, T, A, S> operator+(
2467 const basic_fbstring<E, T, A, S>& lhs,
2468 basic_fbstring<E, T, A, S>&& rhs) {
2469 if (rhs.capacity() >= lhs.size() + rhs.size()) {
2470 // Good, at least we don't need to reallocate
2471 return std::move(rhs.insert(0, lhs));
2472 }
2473 // Meh, no go. Forward to operator+(const&, const&).
2474 auto const& rhsC = rhs;
2475 return lhs + rhsC;
2476}
2477
2478// C++11 21.4.8.1/4
2479template <typename E, class T, class A, class S>
2480inline basic_fbstring<E, T, A, S> operator+(
2481 basic_fbstring<E, T, A, S>&& lhs,
2482 basic_fbstring<E, T, A, S>&& rhs) {
2483 return std::move(lhs.append(rhs));
2484}
2485
2486// C++11 21.4.8.1/5
2487template <typename E, class T, class A, class S>
2488inline basic_fbstring<E, T, A, S> operator+(
2489 const E* lhs,
2490 const basic_fbstring<E, T, A, S>& rhs) {
2491 //
2492 basic_fbstring<E, T, A, S> result;
2493 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2494 result.reserve(len + rhs.size());
2495 result.append(lhs, len).append(rhs);
2496 return result;
2497}
2498
2499// C++11 21.4.8.1/6
2500template <typename E, class T, class A, class S>
2501inline basic_fbstring<E, T, A, S> operator+(
2502 const E* lhs,
2503 basic_fbstring<E, T, A, S>&& rhs) {
2504 //
2505 const auto len = basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2506 if (rhs.capacity() >= len + rhs.size()) {
2507 // Good, at least we don't need to reallocate
2508 rhs.insert(rhs.begin(), lhs, lhs + len);
2509 return std::move(rhs);
2510 }
2511 // Meh, no go. Do it by hand since we have len already.
2512 basic_fbstring<E, T, A, S> result;
2513 result.reserve(len + rhs.size());
2514 result.append(lhs, len).append(rhs);
2515 return result;
2516}
2517
2518// C++11 21.4.8.1/7
2519template <typename E, class T, class A, class S>
2520inline basic_fbstring<E, T, A, S> operator+(
2521 E lhs,
2522 const basic_fbstring<E, T, A, S>& rhs) {
2523 basic_fbstring<E, T, A, S> result;
2524 result.reserve(1 + rhs.size());
2525 result.push_back(lhs);
2526 result.append(rhs);
2527 return result;
2528}
2529
2530// C++11 21.4.8.1/8
2531template <typename E, class T, class A, class S>
2532inline basic_fbstring<E, T, A, S> operator+(
2533 E lhs,
2534 basic_fbstring<E, T, A, S>&& rhs) {
2535 //
2536 if (rhs.capacity() > rhs.size()) {
2537 // Good, at least we don't need to reallocate
2538 rhs.insert(rhs.begin(), lhs);
2539 return std::move(rhs);
2540 }
2541 // Meh, no go. Forward to operator+(E, const&).
2542 auto const& rhsC = rhs;
2543 return lhs + rhsC;
2544}
2545
2546// C++11 21.4.8.1/9
2547template <typename E, class T, class A, class S>
2548inline basic_fbstring<E, T, A, S> operator+(
2549 const basic_fbstring<E, T, A, S>& lhs,
2550 const E* rhs) {
2551 typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2552 typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2553
2554 basic_fbstring<E, T, A, S> result;
2555 const size_type len = traits_type::length(rhs);
2556 result.reserve(lhs.size() + len);
2557 result.append(lhs).append(rhs, len);
2558 return result;
2559}
2560
2561// C++11 21.4.8.1/10
2562template <typename E, class T, class A, class S>
2563inline basic_fbstring<E, T, A, S> operator+(
2564 basic_fbstring<E, T, A, S>&& lhs,
2565 const E* rhs) {
2566 //
2567 return std::move(lhs += rhs);
2568}
2569
2570// C++11 21.4.8.1/11
2571template <typename E, class T, class A, class S>
2572inline basic_fbstring<E, T, A, S> operator+(
2573 const basic_fbstring<E, T, A, S>& lhs,
2574 E rhs) {
2575 basic_fbstring<E, T, A, S> result;
2576 result.reserve(lhs.size() + 1);
2577 result.append(lhs);
2578 result.push_back(rhs);
2579 return result;
2580}
2581
2582// C++11 21.4.8.1/12
2583template <typename E, class T, class A, class S>
2584inline basic_fbstring<E, T, A, S> operator+(
2585 basic_fbstring<E, T, A, S>&& lhs,
2586 E rhs) {
2587 //
2588 return std::move(lhs += rhs);
2589}
2590
2591template <typename E, class T, class A, class S>
2592inline bool operator==(
2593 const basic_fbstring<E, T, A, S>& lhs,
2594 const basic_fbstring<E, T, A, S>& rhs) {
2595 return lhs.size() == rhs.size() && lhs.compare(rhs) == 0;
2596}
2597
2598template <typename E, class T, class A, class S>
2599inline bool operator==(
2600 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2601 const basic_fbstring<E, T, A, S>& rhs) {
2602 return rhs == lhs;
2603}
2604
2605template <typename E, class T, class A, class S>
2606inline bool operator==(
2607 const basic_fbstring<E, T, A, S>& lhs,
2608 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2609 return lhs.compare(rhs) == 0;
2610}
2611
2612template <typename E, class T, class A, class S>
2613inline bool operator!=(
2614 const basic_fbstring<E, T, A, S>& lhs,
2615 const basic_fbstring<E, T, A, S>& rhs) {
2616 return !(lhs == rhs);
2617}
2618
2619template <typename E, class T, class A, class S>
2620inline bool operator!=(
2621 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2622 const basic_fbstring<E, T, A, S>& rhs) {
2623 return !(lhs == rhs);
2624}
2625
2626template <typename E, class T, class A, class S>
2627inline bool operator!=(
2628 const basic_fbstring<E, T, A, S>& lhs,
2629 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2630 return !(lhs == rhs);
2631}
2632
2633template <typename E, class T, class A, class S>
2634inline bool operator<(
2635 const basic_fbstring<E, T, A, S>& lhs,
2636 const basic_fbstring<E, T, A, S>& rhs) {
2637 return lhs.compare(rhs) < 0;
2638}
2639
2640template <typename E, class T, class A, class S>
2641inline bool operator<(
2642 const basic_fbstring<E, T, A, S>& lhs,
2643 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2644 return lhs.compare(rhs) < 0;
2645}
2646
2647template <typename E, class T, class A, class S>
2648inline bool operator<(
2649 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2650 const basic_fbstring<E, T, A, S>& rhs) {
2651 return rhs.compare(lhs) > 0;
2652}
2653
2654template <typename E, class T, class A, class S>
2655inline bool operator>(
2656 const basic_fbstring<E, T, A, S>& lhs,
2657 const basic_fbstring<E, T, A, S>& rhs) {
2658 return rhs < lhs;
2659}
2660
2661template <typename E, class T, class A, class S>
2662inline bool operator>(
2663 const basic_fbstring<E, T, A, S>& lhs,
2664 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2665 return rhs < lhs;
2666}
2667
2668template <typename E, class T, class A, class S>
2669inline bool operator>(
2670 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2671 const basic_fbstring<E, T, A, S>& rhs) {
2672 return rhs < lhs;
2673}
2674
2675template <typename E, class T, class A, class S>
2676inline bool operator<=(
2677 const basic_fbstring<E, T, A, S>& lhs,
2678 const basic_fbstring<E, T, A, S>& rhs) {
2679 return !(rhs < lhs);
2680}
2681
2682template <typename E, class T, class A, class S>
2683inline bool operator<=(
2684 const basic_fbstring<E, T, A, S>& lhs,
2685 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2686 return !(rhs < lhs);
2687}
2688
2689template <typename E, class T, class A, class S>
2690inline bool operator<=(
2691 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2692 const basic_fbstring<E, T, A, S>& rhs) {
2693 return !(rhs < lhs);
2694}
2695
2696template <typename E, class T, class A, class S>
2697inline bool operator>=(
2698 const basic_fbstring<E, T, A, S>& lhs,
2699 const basic_fbstring<E, T, A, S>& rhs) {
2700 return !(lhs < rhs);
2701}
2702
2703template <typename E, class T, class A, class S>
2704inline bool operator>=(
2705 const basic_fbstring<E, T, A, S>& lhs,
2706 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2707 return !(lhs < rhs);
2708}
2709
2710template <typename E, class T, class A, class S>
2711inline bool operator>=(
2712 const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2713 const basic_fbstring<E, T, A, S>& rhs) {
2714 return !(lhs < rhs);
2715}
2716
2717// C++11 21.4.8.8
2718template <typename E, class T, class A, class S>
2719void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2720 lhs.swap(rhs);
2721}
2722
2723// TODO: make this faster.
2724template <typename E, class T, class A, class S>
2725inline std::basic_istream<
2726 typename basic_fbstring<E, T, A, S>::value_type,
2727 typename basic_fbstring<E, T, A, S>::traits_type>&
2728operator>>(
2729 std::basic_istream<
2730 typename basic_fbstring<E, T, A, S>::value_type,
2731 typename basic_fbstring<E, T, A, S>::traits_type>& is,
2732 basic_fbstring<E, T, A, S>& str) {
2733 typedef std::basic_istream<
2734 typename basic_fbstring<E, T, A, S>::value_type,
2735 typename basic_fbstring<E, T, A, S>::traits_type>
2736 _istream_type;
2737 typename _istream_type::sentry sentry(is);
2738 size_t extracted = 0;
2739 auto err = _istream_type::goodbit;
2740 if (sentry) {
2741 auto n = is.width();
2742 if (n <= 0) {
2743 n = str.max_size();
2744 }
2745 str.erase();
2746 for (auto got = is.rdbuf()->sgetc(); extracted != size_t(n); ++extracted) {
2747 if (got == T::eof()) {
2748 err |= _istream_type::eofbit;
2749 is.width(0);
2750 break;
2751 }
2752 if (isspace(got)) {
2753 break;
2754 }
2755 str.push_back(got);
2756 got = is.rdbuf()->snextc();
2757 }
2758 }
2759 if (!extracted) {
2760 err |= _istream_type::failbit;
2761 }
2762 if (err) {
2763 is.setstate(err);
2764 }
2765 return is;
2766}
2767
2768template <typename E, class T, class A, class S>
2769inline std::basic_ostream<
2770 typename basic_fbstring<E, T, A, S>::value_type,
2771 typename basic_fbstring<E, T, A, S>::traits_type>&
2772operator<<(
2773 std::basic_ostream<
2774 typename basic_fbstring<E, T, A, S>::value_type,
2775 typename basic_fbstring<E, T, A, S>::traits_type>& os,
2776 const basic_fbstring<E, T, A, S>& str) {
2777#if _LIBCPP_VERSION
2778 typedef std::basic_ostream<
2779 typename basic_fbstring<E, T, A, S>::value_type,
2780 typename basic_fbstring<E, T, A, S>::traits_type>
2781 _ostream_type;
2782 typename _ostream_type::sentry _s(os);
2783 if (_s) {
2784 typedef std::ostreambuf_iterator<
2785 typename basic_fbstring<E, T, A, S>::value_type,
2786 typename basic_fbstring<E, T, A, S>::traits_type>
2787 _Ip;
2788 size_t __len = str.size();
2789 bool __left =
2790 (os.flags() & _ostream_type::adjustfield) == _ostream_type::left;
2791 if (__pad_and_output(
2792 _Ip(os),
2793 str.data(),
2794 __left ? str.data() + __len : str.data(),
2795 str.data() + __len,
2796 os,
2797 os.fill())
2798 .failed()) {
2799 os.setstate(_ostream_type::badbit | _ostream_type::failbit);
2800 }
2801 }
2802#elif defined(_MSC_VER)
2803 typedef decltype(os.precision()) streamsize;
2804 // MSVC doesn't define __ostream_insert
2805 os.write(str.data(), static_cast<streamsize>(str.size()));
2806#else
2807 std::__ostream_insert(os, str.data(), str.size());
2808#endif
2809 return os;
2810}
2811
2812template <typename E1, class T, class A, class S>
2813constexpr typename basic_fbstring<E1, T, A, S>::size_type
2814 basic_fbstring<E1, T, A, S>::npos;
2815
2816#ifndef _LIBSTDCXX_FBSTRING
2817// basic_string compatibility routines
2818
2819template <typename E, class T, class A, class S, class A2>
2820inline bool operator==(
2821 const basic_fbstring<E, T, A, S>& lhs,
2822 const std::basic_string<E, T, A2>& rhs) {
2823 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2824}
2825
2826template <typename E, class T, class A, class S, class A2>
2827inline bool operator==(
2828 const std::basic_string<E, T, A2>& lhs,
2829 const basic_fbstring<E, T, A, S>& rhs) {
2830 return rhs == lhs;
2831}
2832
2833template <typename E, class T, class A, class S, class A2>
2834inline bool operator!=(
2835 const basic_fbstring<E, T, A, S>& lhs,
2836 const std::basic_string<E, T, A2>& rhs) {
2837 return !(lhs == rhs);
2838}
2839
2840template <typename E, class T, class A, class S, class A2>
2841inline bool operator!=(
2842 const std::basic_string<E, T, A2>& lhs,
2843 const basic_fbstring<E, T, A, S>& rhs) {
2844 return !(lhs == rhs);
2845}
2846
2847template <typename E, class T, class A, class S, class A2>
2848inline bool operator<(
2849 const basic_fbstring<E, T, A, S>& lhs,
2850 const std::basic_string<E, T, A2>& rhs) {
2851 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) < 0;
2852}
2853
2854template <typename E, class T, class A, class S, class A2>
2855inline bool operator>(
2856 const basic_fbstring<E, T, A, S>& lhs,
2857 const std::basic_string<E, T, A2>& rhs) {
2858 return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) > 0;
2859}
2860
2861template <typename E, class T, class A, class S, class A2>
2862inline bool operator<(
2863 const std::basic_string<E, T, A2>& lhs,
2864 const basic_fbstring<E, T, A, S>& rhs) {
2865 return rhs > lhs;
2866}
2867
2868template <typename E, class T, class A, class S, class A2>
2869inline bool operator>(
2870 const std::basic_string<E, T, A2>& lhs,
2871 const basic_fbstring<E, T, A, S>& rhs) {
2872 return rhs < lhs;
2873}
2874
2875template <typename E, class T, class A, class S, class A2>
2876inline bool operator<=(
2877 const basic_fbstring<E, T, A, S>& lhs,
2878 const std::basic_string<E, T, A2>& rhs) {
2879 return !(lhs > rhs);
2880}
2881
2882template <typename E, class T, class A, class S, class A2>
2883inline bool operator>=(
2884 const basic_fbstring<E, T, A, S>& lhs,
2885 const std::basic_string<E, T, A2>& rhs) {
2886 return !(lhs < rhs);
2887}
2888
2889template <typename E, class T, class A, class S, class A2>
2890inline bool operator<=(
2891 const std::basic_string<E, T, A2>& lhs,
2892 const basic_fbstring<E, T, A, S>& rhs) {
2893 return !(lhs > rhs);
2894}
2895
2896template <typename E, class T, class A, class S, class A2>
2897inline bool operator>=(
2898 const std::basic_string<E, T, A2>& lhs,
2899 const basic_fbstring<E, T, A, S>& rhs) {
2900 return !(lhs < rhs);
2901}
2902
2903#if !defined(_LIBSTDCXX_FBSTRING)
2904typedef basic_fbstring<char> fbstring;
2905#endif
2906
2907// fbstring is relocatable
2908template <class T, class R, class A, class S>
2909FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2910
2911#endif
2912
2913FOLLY_FBSTRING_END_NAMESPACE
2914
2915#ifndef _LIBSTDCXX_FBSTRING
2916
2917// Hash functions to make fbstring usable with e.g. hash_map
2918//
2919// Handle interaction with different C++ standard libraries, which
2920// expect these types to be in different namespaces.
2921
2922#define FOLLY_FBSTRING_HASH1(T) \
2923 template <> \
2924 struct hash<::folly::basic_fbstring<T>> { \
2925 size_t operator()(const ::folly::basic_fbstring<T>& s) const { \
2926 return ::folly::hash::fnv32_buf(s.data(), s.size() * sizeof(T)); \
2927 } \
2928 };
2929
2930// The C++11 standard says that these four are defined
2931#define FOLLY_FBSTRING_HASH \
2932 FOLLY_FBSTRING_HASH1(char) \
2933 FOLLY_FBSTRING_HASH1(char16_t) \
2934 FOLLY_FBSTRING_HASH1(char32_t) \
2935 FOLLY_FBSTRING_HASH1(wchar_t)
2936
2937namespace std {
2938
2939FOLLY_FBSTRING_HASH
2940
2941} // namespace std
2942
2943#undef FOLLY_FBSTRING_HASH
2944#undef FOLLY_FBSTRING_HASH1
2945
2946#endif // _LIBSTDCXX_FBSTRING
2947
2948FOLLY_POP_WARNING
2949
2950#undef FBSTRING_DISABLE_SSO
2951#undef FBSTRING_SANITIZE_ADDRESS
2952#undef throw
2953#undef FBSTRING_LIKELY
2954#undef FBSTRING_UNLIKELY
2955#undef FBSTRING_ASSERT
2956
2957#ifndef _LIBSTDCXX_FBSTRING
2958namespace folly {
2959template <class T>
2960struct IsSomeString;
2961
2962template <>
2963struct IsSomeString<fbstring> : std::true_type {};
2964} // namespace folly
2965#endif
2966