+template <typename E, class T, class A, class S>
+FOLLY_MALLOC_NOINLINE inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::traitsLength(const value_type* s) {
+ return s ? traits_type::length(s)
+ : (std::__throw_logic_error(
+ "basic_fbstring: null pointer initializer not valid"),
+ 0);
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
+ const basic_fbstring& lhs) {
+ Invariant checker(*this);
+
+ if (FBSTRING_UNLIKELY(&lhs == this)) {
+ return *this;
+ }
+
+ return assign(lhs.data(), lhs.size());
+}
+
+// Move assignment
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::operator=(
+ basic_fbstring&& goner) noexcept {
+ if (FBSTRING_UNLIKELY(&goner == this)) {
+ // Compatibility with std::basic_string<>,
+ // C++11 21.4.2 [string.cons] / 23 requires self-move-assignment support.
+ return *this;
+ }
+ // No need of this anymore
+ this->~basic_fbstring();
+ // Move the goner into this
+ new (&store_) S(std::move(goner.store_));
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+template <typename TP>
+inline typename std::enable_if<
+ std::is_same<
+ typename std::decay<TP>::type,
+ typename basic_fbstring<E, T, A, S>::value_type>::value,
+ basic_fbstring<E, T, A, S>&>::type
+basic_fbstring<E, T, A, S>::operator=(TP c) {
+ Invariant checker(*this);
+
+ if (empty()) {
+ store_.expandNoinit(1);
+ } else if (store_.isShared()) {
+ basic_fbstring(1, c).swap(*this);
+ return *this;
+ } else {
+ store_.shrink(size() - 1);
+ }
+ front() = c;
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+inline void basic_fbstring<E, T, A, S>::resize(
+ const size_type n, const value_type c /*= value_type()*/) {
+ Invariant checker(*this);
+
+ auto size = this->size();
+ if (n <= size) {
+ store_.shrink(size - n);
+ } else {
+ auto const delta = n - size;
+ auto pData = store_.expandNoinit(delta);
+ fbstring_detail::podFill(pData, pData + delta, c);
+ }
+ FBSTRING_ASSERT(this->size() == n);
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
+ const basic_fbstring& str) {
+#ifndef NDEBUG
+ auto desiredSize = size() + str.size();
+#endif
+ append(str.data(), str.size());
+ FBSTRING_ASSERT(size() == desiredSize);
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
+ const basic_fbstring& str, const size_type pos, size_type n) {
+ const size_type sz = str.size();
+ enforce(pos <= sz, std::__throw_out_of_range, "");
+ procrustes(n, sz - pos);
+ return append(str.data() + pos, n);
+}
+
+template <typename E, class T, class A, class S>
+FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
+basic_fbstring<E, T, A, S>::append(const value_type* s, size_type n) {
+ Invariant checker(*this);
+
+ if (FBSTRING_UNLIKELY(!n)) {
+ // Unlikely but must be done
+ return *this;
+ }
+ auto const oldSize = size();
+ auto const oldData = data();
+ auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
+
+ // Check for aliasing (rare). We could use "<=" here but in theory
+ // those do not work for pointers unless the pointers point to
+ // elements in the same array. For that reason we use
+ // std::less_equal, which is guaranteed to offer a total order
+ // over pointers. See discussion at http://goo.gl/Cy2ya for more
+ // info.
+ std::less_equal<const value_type*> le;
+ if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
+ FBSTRING_ASSERT(le(s + n, oldData + oldSize));
+ // expandNoinit() could have moved the storage, restore the source.
+ s = data() + (s - oldData);
+ fbstring_detail::podMove(s, s + n, pData);
+ } else {
+ fbstring_detail::podCopy(s, s + n, pData);
+ }
+
+ FBSTRING_ASSERT(size() == oldSize + n);
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::append(
+ size_type n, value_type c) {
+ Invariant checker(*this);
+ auto pData = store_.expandNoinit(n, /* expGrowth = */ true);
+ fbstring_detail::podFill(pData, pData + n, c);
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::assign(
+ const basic_fbstring& str, const size_type pos, size_type n) {
+ const size_type sz = str.size();
+ enforce(pos <= sz, std::__throw_out_of_range, "");
+ procrustes(n, sz - pos);
+ return assign(str.data() + pos, n);
+}
+
+template <typename E, class T, class A, class S>
+FOLLY_MALLOC_NOINLINE inline basic_fbstring<E, T, A, S>&
+basic_fbstring<E, T, A, S>::assign(const value_type* s, const size_type n) {
+ Invariant checker(*this);
+
+ if (n == 0) {
+ resize(0);
+ } else if (size() >= n) {
+ // s can alias this, we need to use podMove.
+ fbstring_detail::podMove(s, s + n, store_.mutableData());
+ store_.shrink(size() - n);
+ FBSTRING_ASSERT(size() == n);
+ } else {
+ // If n is larger than size(), s cannot alias this string's
+ // storage.
+ resize(0);
+ // Do not use exponential growth here: assign() should be tight,
+ // to mirror the behavior of the equivalent constructor.
+ fbstring_detail::podCopy(s, s + n, store_.expandNoinit(n));
+ }
+
+ FBSTRING_ASSERT(size() == n);
+ return *this;
+}
+
+#ifndef _LIBSTDCXX_FBSTRING
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::istream_type&
+basic_fbstring<E, T, A, S>::getlineImpl(istream_type & is, value_type delim) {
+ Invariant checker(*this);
+
+ clear();
+ size_t size = 0;
+ while (true) {
+ size_t avail = capacity() - size;
+ // fbstring has 1 byte extra capacity for the null terminator,
+ // and getline null-terminates the read string.
+ is.getline(store_.expandNoinit(avail), avail + 1, delim);
+ size += is.gcount();
+
+ if (is.bad() || is.eof() || !is.fail()) {
+ // Done by either failure, end of file, or normal read.
+ if (!is.bad() && !is.eof()) {
+ --size; // gcount() also accounts for the delimiter.
+ }
+ resize(size);
+ break;
+ }
+
+ FBSTRING_ASSERT(size == this->size());
+ FBSTRING_ASSERT(size == capacity());
+ // Start at minimum allocation 63 + terminator = 64.
+ reserve(std::max<size_t>(63, 3 * size / 2));
+ // Clear the error so we can continue reading.
+ is.clear();
+ }
+ return is;
+}
+#endif
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::find(
+ const value_type* needle, const size_type pos, const size_type nsize)
+ const {
+ auto const size = this->size();
+ // nsize + pos can overflow (eg pos == npos), guard against that by checking
+ // that nsize + pos does not wrap around.
+ if (nsize + pos > size || nsize + pos < pos) {
+ return npos;
+ }
+
+ if (nsize == 0) {
+ return pos;
+ }
+ // Don't use std::search, use a Boyer-Moore-like trick by comparing
+ // the last characters first
+ auto const haystack = data();
+ auto const nsize_1 = nsize - 1;
+ auto const lastNeedle = needle[nsize_1];
+
+ // Boyer-Moore skip value for the last char in the needle. Zero is
+ // not a valid value; skip will be computed the first time it's
+ // needed.
+ size_type skip = 0;
+
+ const E* i = haystack + pos;
+ auto iEnd = haystack + size - nsize_1;
+
+ while (i < iEnd) {
+ // Boyer-Moore: match the last element in the needle
+ while (i[nsize_1] != lastNeedle) {
+ if (++i == iEnd) {
+ // not found
+ return npos;
+ }
+ }
+ // Here we know that the last char matches
+ // Continue in pedestrian mode
+ for (size_t j = 0;;) {
+ FBSTRING_ASSERT(j < nsize);
+ if (i[j] != needle[j]) {
+ // Not found, we can skip
+ // Compute the skip value lazily
+ if (skip == 0) {
+ skip = 1;
+ while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
+ ++skip;
+ }
+ }
+ i += skip;
+ break;
+ }
+ // Check if done searching
+ if (++j == nsize) {
+ // Yay
+ return i - haystack;
+ }
+ }
+ }
+ return npos;
+}
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::iterator
+basic_fbstring<E, T, A, S>::insertImplDiscr(
+ const_iterator i, size_type n, value_type c, std::true_type) {
+ Invariant checker(*this);
+
+ FBSTRING_ASSERT(i >= cbegin() && i <= cend());
+ const size_type pos = i - cbegin();
+
+ auto oldSize = size();
+ store_.expandNoinit(n, /* expGrowth = */ true);
+ auto b = begin();
+ fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
+ fbstring_detail::podFill(b + pos, b + pos + n, c);
+
+ return b + pos;
+}
+
+template <typename E, class T, class A, class S>
+template <class InputIter>
+inline typename basic_fbstring<E, T, A, S>::iterator
+basic_fbstring<E, T, A, S>::insertImplDiscr(
+ const_iterator i, InputIter b, InputIter e, std::false_type) {
+ return insertImpl(
+ i, b, e, typename std::iterator_traits<InputIter>::iterator_category());
+}
+
+template <typename E, class T, class A, class S>
+template <class FwdIterator>
+inline typename basic_fbstring<E, T, A, S>::iterator
+basic_fbstring<E, T, A, S>::insertImpl(
+ const_iterator i,
+ FwdIterator s1,
+ FwdIterator s2,
+ std::forward_iterator_tag) {
+ Invariant checker(*this);
+
+ FBSTRING_ASSERT(i >= cbegin() && i <= cend());
+ const size_type pos = i - cbegin();
+ auto n = std::distance(s1, s2);
+ FBSTRING_ASSERT(n >= 0);
+
+ auto oldSize = size();
+ store_.expandNoinit(n, /* expGrowth = */ true);
+ auto b = begin();
+ fbstring_detail::podMove(b + pos, b + oldSize, b + pos + n);
+ std::copy(s1, s2, b + pos);
+
+ return b + pos;
+}
+
+template <typename E, class T, class A, class S>
+template <class InputIterator>
+inline typename basic_fbstring<E, T, A, S>::iterator
+basic_fbstring<E, T, A, S>::insertImpl(
+ const_iterator i,
+ InputIterator b,
+ InputIterator e,
+ std::input_iterator_tag) {
+ const auto pos = i - cbegin();
+ basic_fbstring temp(cbegin(), i);
+ for (; b != e; ++b) {
+ temp.push_back(*b);
+ }
+ temp.append(i, cend());
+ swap(temp);
+ return begin() + pos;
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
+ iterator i1,
+ iterator i2,
+ const value_type* s,
+ size_type n,
+ std::integral_constant<int, 2>) {
+ FBSTRING_ASSERT(i1 <= i2);
+ FBSTRING_ASSERT(begin() <= i1 && i1 <= end());
+ FBSTRING_ASSERT(begin() <= i2 && i2 <= end());
+ return replace(i1, i2, s, s + n);
+}
+
+template <typename E, class T, class A, class S>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
+ iterator i1,
+ iterator i2,
+ size_type n2,
+ value_type c,
+ std::integral_constant<int, 1>) {
+ const size_type n1 = i2 - i1;
+ if (n1 > n2) {
+ std::fill(i1, i1 + n2, c);
+ erase(i1 + n2, i2);
+ } else {
+ std::fill(i1, i2, c);
+ insert(i2, n2 - n1, c);
+ }
+ FBSTRING_ASSERT(isSane());
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+template <class InputIter>
+inline basic_fbstring<E, T, A, S>& basic_fbstring<E, T, A, S>::replaceImplDiscr(
+ iterator i1,
+ iterator i2,
+ InputIter b,
+ InputIter e,
+ std::integral_constant<int, 0>) {
+ using Cat = typename std::iterator_traits<InputIter>::iterator_category;
+ replaceImpl(i1, i2, b, e, Cat());
+ return *this;
+}
+
+template <typename E, class T, class A, class S>
+template <class FwdIterator>
+inline bool basic_fbstring<E, T, A, S>::replaceAliased(
+ iterator i1, iterator i2, FwdIterator s1, FwdIterator s2, std::true_type) {
+ std::less_equal<const value_type*> le{};
+ const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
+ if (!aliased) {
+ return false;
+ }
+ // Aliased replace, copy to new string
+ basic_fbstring temp;
+ temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
+ temp.append(begin(), i1).append(s1, s2).append(i2, end());
+ swap(temp);
+ return true;
+}
+
+template <typename E, class T, class A, class S>
+template <class FwdIterator>
+inline void basic_fbstring<E, T, A, S>::replaceImpl(
+ iterator i1,
+ iterator i2,
+ FwdIterator s1,
+ FwdIterator s2,
+ std::forward_iterator_tag) {
+ Invariant checker(*this);
+
+ // Handle aliased replace
+ using Sel = std::integral_constant<
+ bool,
+ std::is_same<FwdIterator, iterator>::value ||
+ std::is_same<FwdIterator, const_iterator>::value>;
+ if (replaceAliased(i1, i2, s1, s2, Sel())) {
+ return;
+ }
+
+ auto const n1 = i2 - i1;
+ FBSTRING_ASSERT(n1 >= 0);
+ auto const n2 = std::distance(s1, s2);
+ FBSTRING_ASSERT(n2 >= 0);
+
+ if (n1 > n2) {
+ // shrinks
+ std::copy(s1, s2, i1);
+ erase(i1 + n2, i2);
+ } else {
+ // grows
+ s1 = fbstring_detail::copy_n(s1, n1, i1).first;
+ insert(i2, s1, s2);
+ }
+ FBSTRING_ASSERT(isSane());
+}
+
+template <typename E, class T, class A, class S>
+template <class InputIterator>
+inline void basic_fbstring<E, T, A, S>::replaceImpl(
+ iterator i1,
+ iterator i2,
+ InputIterator b,
+ InputIterator e,
+ std::input_iterator_tag) {
+ basic_fbstring temp(begin(), i1);
+ temp.append(b, e).append(i2, end());
+ swap(temp);
+}
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::rfind(
+ const value_type* s, size_type pos, size_type n) const {
+ if (n > length()) {
+ return npos;
+ }
+ pos = std::min(pos, length() - n);
+ if (n == 0) {
+ return pos;
+ }
+
+ const_iterator i(begin() + pos);
+ for (;; --i) {
+ if (traits_type::eq(*i, *s) && traits_type::compare(&*i, s, n) == 0) {
+ return i - begin();
+ }
+ if (i == begin()) {
+ break;
+ }
+ }
+ return npos;
+}
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::find_first_of(
+ const value_type* s, size_type pos, size_type n) const {
+ if (pos > length() || n == 0) {
+ return npos;
+ }
+ const_iterator i(begin() + pos), finish(end());
+ for (; i != finish; ++i) {
+ if (traits_type::find(s, n, *i) != nullptr) {
+ return i - begin();
+ }
+ }
+ return npos;
+}
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::find_last_of(
+ const value_type* s, size_type pos, size_type n) const {
+ if (!empty() && n > 0) {
+ pos = std::min(pos, length() - 1);
+ const_iterator i(begin() + pos);
+ for (;; --i) {
+ if (traits_type::find(s, n, *i) != nullptr) {
+ return i - begin();
+ }
+ if (i == begin()) {
+ break;
+ }
+ }
+ }
+ return npos;
+}
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::find_first_not_of(
+ const value_type* s, size_type pos, size_type n) const {
+ if (pos < length()) {
+ const_iterator i(begin() + pos), finish(end());
+ for (; i != finish; ++i) {
+ if (traits_type::find(s, n, *i) == nullptr) {
+ return i - begin();
+ }
+ }
+ }
+ return npos;
+}
+
+template <typename E, class T, class A, class S>
+inline typename basic_fbstring<E, T, A, S>::size_type
+basic_fbstring<E, T, A, S>::find_last_not_of(
+ const value_type* s, size_type pos, size_type n) const {
+ if (!this->empty()) {
+ pos = std::min(pos, size() - 1);
+ const_iterator i(begin() + pos);
+ for (;; --i) {
+ if (traits_type::find(s, n, *i) == nullptr) {
+ return i - begin();
+ }
+ if (i == begin()) {
+ break;
+ }
+ }
+ }
+ return npos;
+}
+