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