+/*
+ * Copyright 2012 Facebook, Inc.
+ *
+ * Licensed under the Apache License, Version 2.0 (the "License");
+ * you may not use this file except in compliance with the License.
+ * You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+// @author: Andrei Alexandrescu (aalexandre)
+// String type.
+
+#ifndef FOLLY_BASE_FBSTRING_H_
+#define FOLLY_BASE_FBSTRING_H_
+
+/**
+ fbstring's behavior can be configured via two macro definitions, as
+ follows. Normally, fbstring does not write a '\0' at the end of
+ each string whenever it changes the underlying characters. Instead,
+ it lazily writes the '\0' whenever either c_str() or data()
+ called.
+
+ This is standard-compliant behavior and may save costs in some
+ circumstances. However, it may be surprising to some client code
+ because c_str() and data() are const member functions (fbstring
+ uses the "mutable" storage class for its own state).
+
+ In order to appease client code that expects fbstring to be
+ zero-terminated at all times, if the preprocessor symbol
+ FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
+ i.e. it goes the extra mile to guarantee a '\0' is always planted
+ at the end of its data.
+
+ On the contrary, if the desire is to debug faulty client code that
+ unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
+ emphatically NOT a zero) at the end of each string if
+ FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
+ writes the '\0', of course.)
+
+ The preprocessor symbols FBSTRING_PERVERSE and
+ FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
+ enforced during preprocessing.
+*/
+
+//#define FBSTRING_PERVERSE
+//#define FBSTRING_CONSERVATIVE
+
+#ifdef FBSTRING_PERVERSE
+#ifdef FBSTRING_CONSERVATIVE
+#error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
+#endif
+#endif
+
+// This file appears in two locations: inside fbcode and in the
+// libstdc++ source code (when embedding fbstring as std::string).
+// To aid in this schizophrenic use, two macros are defined in
+// c++config.h:
+// _LIBSTDCXX_FBSTRING - Set inside libstdc++. This is useful to
+// gate use inside fbcode v. libstdc++
+#include <bits/c++config.h>
+
+#ifdef _LIBSTDCXX_FBSTRING
+
+#pragma GCC system_header
+
+// Handle the cases where the fbcode version (folly/Malloc.h) is included
+// either before or after this inclusion. */home/engshare/third-party/src/
+// libgcc/libgcc-4.6.2/gcc-4.6.2-20111027/libstdc++-v3/include/bits/
+// basic_string.h* has a more detailed explanation of why this is necessary.
+#ifdef FOLLY_MALLOC_H_
+#undef FOLLY_MALLOC_H_
+#include "basic_fbstring_malloc.h"
+#else
+#include "basic_fbstring_malloc.h"
+#undef FOLLY_MALLOC_H_
+#endif
+
+#else // !_LIBSTDCXX_FBSTRING
+
+#include <string>
+#include <cstring>
+#include <cassert>
+
+#include "folly/Traits.h"
+#include "folly/Malloc.h"
+#include "folly/Hash.h"
+
+#endif
+
+#include <atomic>
+#include <limits>
+#include <type_traits>
+
+#ifdef _LIBSTDCXX_FBSTRING
+namespace std _GLIBCXX_VISIBILITY(default) {
+_GLIBCXX_BEGIN_NAMESPACE_VERSION
+#else
+namespace folly {
+#endif
+
+namespace fbstring_detail {
+
+template <class InIt, class OutIt>
+inline
+OutIt copy_n(InIt b,
+ typename std::iterator_traits<InIt>::difference_type n,
+ OutIt d) {
+ for (; n != 0; --n, ++b, ++d) {
+ assert((const void*)&*d != &*b);
+ *d = *b;
+ }
+ return d;
+}
+
+template <class Pod, class T>
+inline void pod_fill(Pod* b, Pod* e, T c) {
+ assert(b && e && b <= e);
+ /*static*/ if (sizeof(T) == 1) {
+ memset(b, c, e - b);
+ } else {
+ auto const ee = b + ((e - b) & ~7u);
+ for (; b != ee; b += 8) {
+ b[0] = c;
+ b[1] = c;
+ b[2] = c;
+ b[3] = c;
+ b[4] = c;
+ b[5] = c;
+ b[6] = c;
+ b[7] = c;
+ }
+ // Leftovers
+ for (; b != e; ++b) {
+ *b = c;
+ }
+ }
+}
+
+/*
+ * Lightly structured memcpy, simplifies copying PODs and introduces
+ * some asserts
+ */
+template <class Pod>
+inline Pod* pod_copy(const Pod* b, const Pod* e, Pod* d) {
+ assert(e >= b);
+ assert(d >= e || d + (e - b) <= b);
+ const size_t s = e - b;
+ std::memcpy(d, b, s * sizeof(*b));
+ return d + s;
+}
+
+/*
+ * Lightly structured memmove, simplifies copying PODs and introduces
+ * some asserts
+ */
+template <class Pod>
+inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
+ assert(e >= b);
+ memmove(d, b, (e - b) * sizeof(*b));
+}
+
+} // namespace fbstring_detail
+
+/**
+ * Defines a special acquisition method for constructing fbstring
+ * objects. AcquireMallocatedString means that the user passes a
+ * pointer to a malloc-allocated string that the fbstring object will
+ * take into custody.
+ */
+enum class AcquireMallocatedString {};
+
+/*
+ * fbstring_core_model is a mock-up type that defines all required
+ * signatures of a fbstring core. The fbstring class itself uses such
+ * a core object to implement all of the numerous member functions
+ * required by the standard.
+ *
+ * If you want to define a new core, copy the definition below and
+ * implement the primitives. Then plug the core into basic_fbstring as
+ * a template argument.
+
+template <class Char>
+class fbstring_core_model {
+public:
+ fbstring_core_model();
+ fbstring_core_model(const fbstring_core_model &);
+ ~fbstring_core_model();
+ // Returns a pointer to string's buffer (currently only contiguous
+ // strings are supported). The pointer is guaranteed to be valid
+ // until the next call to a non-const member function.
+ const Char * data() const;
+ // Much like data(), except the string is prepared to support
+ // character-level changes. This call is a signal for
+ // e.g. reference-counted implementation to fork the data. The
+ // pointer is guaranteed to be valid until the next call to a
+ // non-const member function.
+ Char * mutable_data();
+ // Returns a pointer to string's buffer and guarantees that a
+ // readable '\0' lies right after the buffer. The pointer is
+ // guaranteed to be valid until the next call to a non-const member
+ // function.
+ const Char * c_str() const;
+ // Shrinks the string by delta characters. Asserts that delta <=
+ // size().
+ void shrink(size_t delta);
+ // Expands the string by delta characters (i.e. after this call
+ // size() will report the old size() plus delta) but without
+ // initializing the expanded region. The caller is expected to fill
+ // the expanded area appropriately.
+ void expand_noinit(size_t delta);
+ // Expands the string by one character and sets the last character
+ // to c.
+ void push_back(Char c);
+ // Returns the string's size.
+ size_t size() const;
+ // Returns the string's capacity, i.e. maximum size that the string
+ // can grow to without reallocation. Note that for reference counted
+ // strings that's technically a lie - even assigning characters
+ // within the existing size would cause a reallocation.
+ size_t capacity() const;
+ // Returns true if the data underlying the string is actually shared
+ // across multiple strings (in a refcounted fashion).
+ bool isShared() const;
+ // Makes sure that at least minCapacity characters are available for
+ // the string without reallocation. For reference-counted strings,
+ // it should fork the data even if minCapacity < size().
+ void reserve(size_t minCapacity);
+private:
+ // Do not implement
+ fbstring_core_model& operator=(const fbstring_core_model &);
+};
+*/
+
+/**
+ * This is the core of the string. The code should work on 32- and
+ * 64-bit architectures and with any Char size. Porting to big endian
+ * architectures would require some changes.
+ *
+ * The storage is selected as follows (assuming we store one-byte
+ * characters on a 64-bit machine): (a) "small" strings between 0 and
+ * 23 chars are stored in-situ without allocation (the rightmost byte
+ * stores the size); (b) "medium" strings from 24 through 254 chars
+ * are stored in malloc-allocated memory that is copied eagerly; (c)
+ * "large" strings of 255 chars and above are stored in a similar
+ * structure as medium arrays, except that the string is
+ * reference-counted and copied lazily. the reference count is
+ * allocated right before the character array.
+ *
+ * The discriminator between these three strategies sits in the two
+ * most significant bits of the rightmost char of the storage. If
+ * neither is set, then the string is small (and its length sits in
+ * the lower-order bits of that rightmost character). If the MSb is
+ * set, the string is medium width. If the second MSb is set, then the
+ * string is large.
+ */
+template <class Char> class fbstring_core {
+public:
+ fbstring_core() {
+ // Only initialize the tag, will set the MSBs (i.e. the small
+ // string size) to zero too
+ ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - 1));
+ // or: setSmallSize(0);
+ writeTerminator();
+ assert(category() == isSmall && size() == 0);
+ }
+
+ fbstring_core(const fbstring_core & rhs) {
+ assert(&rhs != this);
+ // Simplest case first: small strings are bitblitted
+ if (rhs.category() == isSmall) {
+ assert(offsetof(MediumLarge, data_) == 0);
+ assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
+ assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
+ const size_t size = rhs.smallSize();
+ if (size == 0) {
+ ml_.capacity_ = rhs.ml_.capacity_;
+ writeTerminator();
+ } else {
+ // Just write the whole thing, don't look at details. In
+ // particular we need to copy capacity anyway because we want
+ // to set the size (don't forget that the last character,
+ // which stores a short string's length, is shared with the
+ // ml_.capacity field).
+ ml_ = rhs.ml_;
+ }
+ assert(category() == isSmall && this->size() == rhs.size());
+ } else if (rhs.category() == isLarge) {
+ // Large strings are just refcounted
+ ml_ = rhs.ml_;
+ RefCounted::incrementRefs(ml_.data_);
+ assert(category() == isLarge && size() == rhs.size());
+ } else {
+ // Medium strings are copied eagerly. Don't forget to allocate
+ // one extra Char for the null terminator.
+ auto const allocSize =
+ goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
+ ml_.data_ = static_cast<Char*>(malloc(allocSize));
+ fbstring_detail::pod_copy(rhs.ml_.data_,
+ // 1 for terminator
+ rhs.ml_.data_ + rhs.ml_.size_ + 1,
+ ml_.data_);
+ // No need for writeTerminator() here, we copied one extra
+ // element just above.
+ ml_.size_ = rhs.ml_.size_;
+ ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
+ assert(category() == isMedium);
+ }
+ assert(size() == rhs.size());
+ assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
+ }
+
+ fbstring_core(fbstring_core&& goner) {
+ if (goner.category() == isSmall) {
+ // Just copy, leave the goner in peace
+ new(this) fbstring_core(goner.small_, goner.smallSize());
+ } else {
+ // Take goner's guts
+ ml_ = goner.ml_;
+ // Clean goner's carcass
+ goner.setSmallSize(0);
+ }
+ }
+
+ fbstring_core(const Char *const data, const size_t size) {
+ // Simplest case first: small strings are bitblitted
+ if (size <= maxSmallSize) {
+ // Layout is: Char* data_, size_t size_, size_t capacity_
+ /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
+ /*static_*/assert(sizeof(Char*) == sizeof(size_t));
+ // sizeof(size_t) must be a power of 2
+ /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
+
+ // If data is aligned, use fast word-wise copying. Otherwise,
+ // use conservative memcpy.
+ if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
+ fbstring_detail::pod_copy(data, data + size, small_);
+ } else {
+ // Copy one word (64 bits) at a time
+ const size_t byteSize = size * sizeof(Char);
+ if (byteSize > 2 * sizeof(size_t)) {
+ // Copy three words
+ ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
+ copyTwo:
+ ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
+ copyOne:
+ ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
+ } else if (byteSize > sizeof(size_t)) {
+ // Copy two words
+ goto copyTwo;
+ } else if (size > 0) {
+ // Copy one word
+ goto copyOne;
+ }
+ }
+ setSmallSize(size);
+ } else if (size <= maxMediumSize) {
+ // Medium strings are allocated normally. Don't forget to
+ // allocate one extra Char for the terminating null.
+ auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
+ ml_.data_ = static_cast<Char*>(malloc(allocSize));
+ fbstring_detail::pod_copy(data, data + size, ml_.data_);
+ ml_.size_ = size;
+ ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
+ } else {
+ // Large strings are allocated differently
+ size_t effectiveCapacity = size;
+ auto const newRC = RefCounted::create(data, & effectiveCapacity);
+ ml_.data_ = newRC->data_;
+ ml_.size_ = size;
+ ml_.capacity_ = effectiveCapacity | isLarge;
+ }
+ writeTerminator();
+ assert(this->size() == size);
+ assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
+ }
+
+ ~fbstring_core() {
+ auto const c = category();
+ if (c == isSmall) {
+ return;
+ }
+ if (c == isMedium) {
+ free(ml_.data_);
+ return;
+ }
+ RefCounted::decrementRefs(ml_.data_);
+ }
+
+ // Snatches a previously mallocated string. The parameter "size"
+ // is the size of the string, and the parameter "capacity" is the size
+ // of the mallocated block. The string must be \0-terminated, so
+ // data[size] == '\0' and capacity >= size + 1.
+ //
+ // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
+ // "size", and pass 3 as "capacity".
+ fbstring_core(Char *const data, const size_t size,
+ const size_t capacity,
+ AcquireMallocatedString) {
+ if (size > 0) {
+ assert(capacity > size);
+ assert(data[size] == '\0');
+ // Use the medium string storage
+ ml_.data_ = data;
+ ml_.size_ = size;
+ ml_.capacity_ = capacity | isMedium;
+ } else {
+ // No need for the memory
+ free(data);
+ setSmallSize(0);
+ }
+ }
+
+ // swap below doesn't test whether &rhs == this (and instead
+ // potentially does extra work) on the premise that the rarity of
+ // that situation actually makes the check more expensive than is
+ // worth.
+ void swap(fbstring_core & rhs) {
+ auto const t = ml_;
+ ml_ = rhs.ml_;
+ rhs.ml_ = t;
+ }
+
+ // In C++11 data() and c_str() are 100% equivalent.
+ const Char * data() const {
+ return c_str();
+ }
+
+ Char * mutable_data() {
+ auto const c = category();
+ if (c == isSmall) {
+ return small_;
+ }
+ assert(c == isMedium || c == isLarge);
+ if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
+ // Ensure unique.
+ size_t effectiveCapacity = ml_.capacity();
+ auto const newRC = RefCounted::create(& effectiveCapacity);
+ // If this fails, someone placed the wrong capacity in an
+ // fbstring.
+ assert(effectiveCapacity >= ml_.capacity());
+ fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
+ newRC->data_);
+ RefCounted::decrementRefs(ml_.data_);
+ ml_.data_ = newRC->data_;
+ // No need to call writeTerminator(), we have + 1 above.
+ }
+ return ml_.data_;
+ }
+
+ const Char * c_str() const {
+ auto const c = category();
+#ifdef FBSTRING_PERVERSE
+ if (c == isSmall) {
+ assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
+ || small_[smallSize()] == '\0');
+ small_[smallSize()] = '\0';
+ return small_;
+ }
+ assert(c == isMedium || c == isLarge);
+ assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
+ ml_.data_[ml_.size_] = '\0';
+#elif defined(FBSTRING_CONSERVATIVE)
+ if (c == isSmall) {
+ assert(small_[smallSize()] == '\0');
+ return small_;
+ }
+ assert(c == isMedium || c == isLarge);
+ assert(ml_.data_[ml_.size_] == '\0');
+#else
+ if (c == isSmall) {
+ small_[smallSize()] = '\0';
+ return small_;
+ }
+ assert(c == isMedium || c == isLarge);
+ ml_.data_[ml_.size_] = '\0';
+#endif
+ return ml_.data_;
+ }
+
+ void shrink(const size_t delta) {
+ if (category() == isSmall) {
+ // Check for underflow
+ assert(delta <= smallSize());
+ setSmallSize(smallSize() - delta);
+ } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
+ // Medium strings and unique large strings need no special
+ // handling.
+ assert(ml_.size_ >= delta);
+ ml_.size_ -= delta;
+ } else {
+ assert(ml_.size_ >= delta);
+ // Shared large string, must make unique. This is because of the
+ // durn terminator must be written, which may trample the shared
+ // data.
+ if (delta) {
+ fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
+ }
+ // No need to write the terminator.
+ return;
+ }
+ writeTerminator();
+ }
+
+ void reserve(size_t minCapacity) {
+ if (category() == isLarge) {
+ // Ensure unique
+ if (RefCounted::refs(ml_.data_) > 1) {
+ // We must make it unique regardless; in-place reallocation is
+ // useless if the string is shared. In order to not surprise
+ // people, reserve the new block at current capacity or
+ // more. That way, a string's capacity never shrinks after a
+ // call to reserve.
+ minCapacity = std::max(minCapacity, ml_.capacity());
+ auto const newRC = RefCounted::create(& minCapacity);
+ fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
+ newRC->data_);
+ // Done with the old data. No need to call writeTerminator(),
+ // we have + 1 above.
+ RefCounted::decrementRefs(ml_.data_);
+ ml_.data_ = newRC->data_;
+ ml_.capacity_ = minCapacity | isLarge;
+ // size remains unchanged
+ } else {
+ // String is not shared, so let's try to realloc (if needed)
+ if (minCapacity > ml_.capacity()) {
+ // Asking for more memory
+ auto const newRC =
+ RefCounted::reallocate(ml_.data_, ml_.size_,
+ ml_.capacity(), minCapacity);
+ ml_.data_ = newRC->data_;
+ ml_.capacity_ = minCapacity | isLarge;
+ writeTerminator();
+ }
+ assert(capacity() >= minCapacity);
+ }
+ } else if (category() == isMedium) {
+ // String is not shared
+ if (minCapacity <= ml_.capacity()) {
+ return; // nothing to do, there's enough room
+ }
+ if (minCapacity <= maxMediumSize) {
+ // Keep the string at medium size. Don't forget to allocate
+ // one extra Char for the terminating null.
+ size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
+ ml_.data_ = static_cast<Char *>(
+ smartRealloc(
+ ml_.data_,
+ ml_.size_ * sizeof(Char),
+ ml_.capacity() * sizeof(Char),
+ capacityBytes));
+ writeTerminator();
+ ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
+ } else {
+ // Conversion from medium to large string
+ fbstring_core nascent;
+ // Will recurse to another branch of this function
+ nascent.reserve(minCapacity);
+ nascent.ml_.size_ = ml_.size_;
+ fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
+ nascent.ml_.data_);
+ nascent.swap(*this);
+ writeTerminator();
+ assert(capacity() >= minCapacity);
+ }
+ } else {
+ assert(category() == isSmall);
+ if (minCapacity > maxMediumSize) {
+ // large
+ auto const newRC = RefCounted::create(& minCapacity);
+ auto const size = smallSize();
+ fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
+ // No need for writeTerminator(), we wrote it above with + 1.
+ ml_.data_ = newRC->data_;
+ ml_.size_ = size;
+ ml_.capacity_ = minCapacity | isLarge;
+ assert(capacity() >= minCapacity);
+ } else if (minCapacity > maxSmallSize) {
+ // medium
+ // Don't forget to allocate one extra Char for the terminating null
+ auto const allocSizeBytes =
+ goodMallocSize((1 + minCapacity) * sizeof(Char));
+ auto const data = static_cast<Char*>(malloc(allocSizeBytes));
+ auto const size = smallSize();
+ fbstring_detail::pod_copy(small_, small_ + size + 1, data);
+ // No need for writeTerminator(), we wrote it above with + 1.
+ ml_.data_ = data;
+ ml_.size_ = size;
+ ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
+ } else {
+ // small
+ // Nothing to do, everything stays put
+ }
+ }
+ assert(capacity() >= minCapacity);
+ }
+
+ void expand_noinit(const size_t delta) {
+ // Strategy is simple: make room, then change size
+ assert(capacity() >= size());
+ size_t sz, newSz, cp;
+ if (category() == isSmall) {
+ sz = smallSize();
+ newSz = sz + delta;
+ if (newSz <= maxSmallSize) {
+ setSmallSize(newSz);
+ writeTerminator();
+ return;
+ }
+ cp = maxSmallSize;
+ } else {
+ sz = ml_.size_;
+ newSz = sz + delta;
+ cp = capacity();
+ }
+ if (newSz > cp) reserve(newSz);
+ assert(capacity() >= newSz);
+ // Category can't be small - we took care of that above
+ assert(category() == isMedium || category() == isLarge);
+ ml_.size_ = newSz;
+ writeTerminator();
+ assert(size() == newSz);
+ }
+
+ void push_back(Char c) {
+ assert(capacity() >= size());
+ size_t sz, cp;
+ if (category() == isSmall) {
+ sz = smallSize();
+ if (sz < maxSmallSize) {
+ setSmallSize(sz + 1);
+ small_[sz] = c;
+ writeTerminator();
+ return;
+ }
+ reserve(maxSmallSize * 3 / 2);
+ } else {
+ sz = ml_.size_;
+ cp = ml_.capacity();
+ if (sz == cp) reserve(cp * 3 / 2);
+ }
+ assert(capacity() >= sz + 1);
+ // Category can't be small - we took care of that above
+ assert(category() == isMedium || category() == isLarge);
+ ml_.size_ = sz + 1;
+ mutable_data()[sz] = c;
+ writeTerminator();
+ }
+
+ size_t size() const {
+ return category() == isSmall ? smallSize() : ml_.size_;
+ }
+
+ size_t capacity() const {
+ switch (category()) {
+ case isSmall:
+ return maxSmallSize;
+ case isLarge:
+ // For large-sized strings, a multi-referenced chunk has no
+ // available capacity. This is because any attempt to append
+ // data would trigger a new allocation.
+ if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
+ default: {}
+ }
+ return ml_.capacity();
+ }
+
+ bool isShared() const {
+ return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
+ }
+
+#ifdef FBSTRING_PERVERSE
+ enum { TERMINATOR = '^' };
+#else
+ enum { TERMINATOR = '\0' };
+#endif
+
+ void writeTerminator() {
+#if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
+ if (category() == isSmall) {
+ const auto s = smallSize();
+ if (s != maxSmallSize) {
+ small_[s] = TERMINATOR;
+ }
+ } else {
+ ml_.data_[ml_.size_] = TERMINATOR;
+ }
+#endif
+ }
+
+private:
+ // Disabled
+ fbstring_core & operator=(const fbstring_core & rhs);
+
+ struct MediumLarge {
+ Char * data_;
+ size_t size_;
+ size_t capacity_;
+
+ size_t capacity() const {
+ return capacity_ & capacityExtractMask;
+ }
+ };
+
+ struct RefCounted {
+ std::atomic<size_t> refCount_;
+ Char data_[1];
+
+ static RefCounted * fromData(Char * p) {
+ return static_cast<RefCounted*>(
+ static_cast<void*>(
+ static_cast<unsigned char*>(static_cast<void*>(p))
+ - offsetof(RefCounted, data_)));
+ }
+
+ static size_t refs(Char * p) {
+ return fromData(p)->refCount_.load(std::memory_order_acquire);
+ }
+
+ static void incrementRefs(Char * p) {
+ fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
+ }
+
+ static void decrementRefs(Char * p) {
+ auto const dis = fromData(p);
+ size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
+ assert(oldcnt > 0);
+ if (oldcnt == 1) {
+ free(dis);
+ }
+ }
+
+ static RefCounted * create(size_t * size) {
+ // Don't forget to allocate one extra Char for the terminating
+ // null. In this case, however, one Char is already part of the
+ // struct.
+ const size_t allocSize = goodMallocSize(
+ sizeof(RefCounted) + *size * sizeof(Char));
+ auto result = static_cast<RefCounted*>(malloc(allocSize));
+ result->refCount_.store(1, std::memory_order_release);
+ *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
+ return result;
+ }
+
+ static RefCounted * create(const Char * data, size_t * size) {
+ const size_t effectiveSize = *size;
+ auto result = create(size);
+ fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
+ return result;
+ }
+
+ static RefCounted * reallocate(Char *const data,
+ const size_t currentSize,
+ const size_t currentCapacity,
+ const size_t newCapacity) {
+ assert(newCapacity > 0 && newCapacity > currentSize);
+ auto const dis = fromData(data);
+ assert(dis->refCount_.load(std::memory_order_acquire) == 1);
+ // Don't forget to allocate one extra Char for the terminating
+ // null. In this case, however, one Char is already part of the
+ // struct.
+ auto result = static_cast<RefCounted*>(
+ smartRealloc(dis,
+ sizeof(RefCounted) + currentSize * sizeof(Char),
+ sizeof(RefCounted) + currentCapacity * sizeof(Char),
+ sizeof(RefCounted) + newCapacity * sizeof(Char)));
+ assert(result->refCount_.load(std::memory_order_acquire) == 1);
+ return result;
+ }
+ };
+
+ union {
+ mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
+ mutable MediumLarge ml_;
+ };
+
+ enum {
+ lastChar = sizeof(MediumLarge) - 1,
+ maxSmallSize = lastChar / sizeof(Char),
+ maxMediumSize = 254 / sizeof(Char), // coincides with the small
+ // bin size in dlmalloc
+ categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
+ capacityExtractMask = ~categoryExtractMask,
+ };
+ static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
+ "Corrupt memory layout for fbstring.");
+
+ enum Category {
+ isSmall = 0,
+ isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
+ isLarge = sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
+ };
+
+ Category category() const {
+ // Assumes little endian
+ return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
+ }
+
+ size_t smallSize() const {
+ assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
+ return static_cast<size_t>(maxSmallSize)
+ - static_cast<size_t>(small_[maxSmallSize]);
+ }
+
+ void setSmallSize(size_t s) {
+ // Warning: this should work with uninitialized strings too,
+ // so don't assume anything about the previous value of
+ // small_[maxSmallSize].
+ assert(s <= maxSmallSize);
+ small_[maxSmallSize] = maxSmallSize - s;
+ }
+};
+
+#ifndef _LIBSTDCXX_FBSTRING
+/**
+ * Dummy fbstring core that uses an actual std::string. This doesn't
+ * make any sense - it's just for testing purposes.
+ */
+template <class Char>
+class dummy_fbstring_core {
+public:
+ dummy_fbstring_core() {
+ }
+ dummy_fbstring_core(const dummy_fbstring_core& another)
+ : backend_(another.backend_) {
+ }
+ dummy_fbstring_core(const Char * s, size_t n)
+ : backend_(s, n) {
+ }
+ void swap(dummy_fbstring_core & rhs) {
+ backend_.swap(rhs.backend_);
+ }
+ const Char * data() const {
+ return backend_.data();
+ }
+ Char * mutable_data() {
+ //assert(!backend_.empty());
+ return &*backend_.begin();
+ }
+ void shrink(size_t delta) {
+ assert(delta <= size());
+ backend_.resize(size() - delta);
+ }
+ void expand_noinit(size_t delta) {
+ backend_.resize(size() + delta);
+ }
+ void push_back(Char c) {
+ backend_.push_back(c);
+ }
+ size_t size() const {
+ return backend_.size();
+ }
+ size_t capacity() const {
+ return backend_.capacity();
+ }
+ bool isShared() const {
+ return false;
+ }
+ void reserve(size_t minCapacity) {
+ backend_.reserve(minCapacity);
+ }
+
+private:
+ std::basic_string<Char> backend_;
+};
+#endif // !_LIBSTDCXX_FBSTRING
+
+/**
+ * This is the basic_string replacement. For conformity,
+ * basic_fbstring takes the same template parameters, plus the last
+ * one which is the core.
+ */
+#ifdef _LIBSTDCXX_FBSTRING
+template <typename E, class T, class A, class Storage>
+#else
+template <typename E,
+ class T = std::char_traits<E>,
+ class A = std::allocator<E>,
+ class Storage = fbstring_core<E> >
+#endif
+class basic_fbstring {
+
+ static void enforce(
+ bool condition,
+ void (*throw_exc)(const char*),
+ const char* msg) {
+ if (!condition) throw_exc(msg);
+ }
+
+ bool isSane() const {
+ return
+ begin() <= end() &&
+ empty() == (size() == 0) &&
+ empty() == (begin() == end()) &&
+ size() <= max_size() &&
+ capacity() <= max_size() &&
+ size() <= capacity() &&
+ (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
+ }
+
+ struct Invariant;
+ friend struct Invariant;
+ struct Invariant {
+#ifndef NDEBUG
+ explicit Invariant(const basic_fbstring& s) : s_(s) {
+ assert(s_.isSane());
+ }
+ ~Invariant() {
+ assert(s_.isSane());
+ }
+ private:
+ const basic_fbstring& s_;
+#else
+ explicit Invariant(const basic_fbstring&) {}
+#endif
+ Invariant& operator=(const Invariant&);
+ };
+
+public:
+ // types
+ typedef T traits_type;
+ typedef typename traits_type::char_type value_type;
+ typedef A allocator_type;
+ typedef typename A::size_type size_type;
+ typedef typename A::difference_type difference_type;
+
+ typedef typename A::reference reference;
+ typedef typename A::const_reference const_reference;
+ typedef typename A::pointer pointer;
+ typedef typename A::const_pointer const_pointer;
+
+ typedef E* iterator;
+ typedef const E* const_iterator;
+ typedef std::reverse_iterator<iterator
+#ifdef NO_ITERATOR_TRAITS
+ , value_type
+#endif
+ > reverse_iterator;
+ typedef std::reverse_iterator<const_iterator
+#ifdef NO_ITERATOR_TRAITS
+ , const value_type
+#endif
+ > const_reverse_iterator;
+
+ static const size_type npos; // = size_type(-1)
+
+private:
+ static void procrustes(size_type& n, size_type nmax) {
+ if (n > nmax) n = nmax;
+ }
+
+public:
+ // 21.3.1 construct/copy/destroy
+ explicit basic_fbstring(const A& a = A()) {
+ }
+
+ basic_fbstring(const basic_fbstring& str)
+ : store_(str.store_) {
+ }
+
+ // Move constructor
+ basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
+ }
+
+#ifndef _LIBSTDCXX_FBSTRING
+ // This is defined for compatibility with std::string
+ /* implicit */ basic_fbstring(const std::string& str)
+ : store_(str.data(), str.size()) {
+ }
+#endif
+
+ basic_fbstring(const basic_fbstring& str, size_type pos,
+ size_type n = npos, const A& a = A()) {
+ assign(str, pos, n);
+ }
+
+ /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
+ : store_(s, s ? traits_type::length(s) : ({
+ basic_fbstring<char> err = __PRETTY_FUNCTION__;
+ err += ": null pointer initializer not valid";
+ std::__throw_logic_error(err.c_str());
+ 0;
+ })) {
+ }
+
+ basic_fbstring(const value_type* s, size_type n, const A& a = A())
+ : store_(s, n) {
+ }
+
+ basic_fbstring(size_type n, value_type c, const A& a = A()) {
+ store_.expand_noinit(n);
+ auto const data = store_.mutable_data();
+ fbstring_detail::pod_fill(data, data + n, c);
+ store_.writeTerminator();
+ }
+
+ template <class InIt>
+ basic_fbstring(InIt begin, InIt end,
+ typename std::enable_if<
+ !std::is_same<typename std::remove_const<InIt>::type,
+ value_type*>::value, const A>::type & a = A()) {
+ assign(begin, end);
+ }
+
+ // Specialization for const char*, const char*
+ basic_fbstring(const value_type* b, const value_type* e)
+ : store_(b, e - b) {
+ }
+
+ // Nonstandard constructor
+ basic_fbstring(value_type *s, size_type n, size_type c,
+ AcquireMallocatedString a)
+ : store_(s, n, c, a) {
+ }
+
+ ~basic_fbstring() {
+ }
+
+ basic_fbstring& operator=(const basic_fbstring & lhs) {
+ if (&lhs == this) {
+ return *this;
+ }
+ auto const oldSize = size();
+ auto const srcSize = lhs.size();
+ if (capacity() >= srcSize && !store_.isShared()) {
+ // great, just copy the contents
+ if (oldSize < srcSize)
+ store_.expand_noinit(srcSize - oldSize);
+ else
+ store_.shrink(oldSize - srcSize);
+ assert(size() == srcSize);
+ fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
+ store_.writeTerminator();
+ } else {
+ // need to reallocate, so we may as well create a brand new string
+ basic_fbstring(lhs).swap(*this);
+ }
+ return *this;
+ }
+
+ // Move assignment
+ basic_fbstring& operator=(basic_fbstring&& goner) {
+ // No need of this anymore
+ this->~basic_fbstring();
+ // Move the goner into this
+ new(&store_) fbstring_core<E>(std::move(goner.store_));
+ return *this;
+ }
+
+#ifndef _LIBSTDCXX_FBSTRING
+ // Compatibility with std::string
+ basic_fbstring & operator=(const std::string & rhs) {
+ return assign(rhs.data(), rhs.size());
+ }
+
+ // Compatibility with std::string
+ std::string toStdString() const {
+ return std::string(data(), size());
+ }
+#else
+ // A lot of code in fbcode still uses this method, so keep it here for now.
+ const basic_fbstring& toStdString() const {
+ return *this;
+ }
+#endif
+
+ basic_fbstring& operator=(const value_type* s) {
+ return assign(s);
+ }
+
+ basic_fbstring& operator=(value_type c) {
+ if (empty()) {
+ store_.expand_noinit(1);
+ } else if (store_.isShared()) {
+ basic_fbstring(1, c).swap(*this);
+ return *this;
+ } else {
+ store_.shrink(size() - 1);
+ }
+ *store_.mutable_data() = c;
+ store_.writeTerminator();
+ return *this;
+ }
+
+ // 21.3.2 iterators:
+ iterator begin() { return store_.mutable_data(); }
+
+ const_iterator begin() const { return store_.data(); }
+
+ iterator end() {
+ return store_.mutable_data() + store_.size();
+ }
+
+ const_iterator end() const {
+ return store_.data() + store_.size();
+ }
+
+ reverse_iterator rbegin() {
+ return reverse_iterator(end());
+ }
+
+ const_reverse_iterator rbegin() const {
+ return const_reverse_iterator(end());
+ }
+
+ reverse_iterator rend() {
+ return reverse_iterator(begin());
+ }
+
+ const_reverse_iterator rend() const {
+ return const_reverse_iterator(begin());
+ }
+
+ // Non-standard functions. They intentionally return by value to
+ // reduce pressure on the reference counting mechanism.
+ value_type front() const { return *begin(); }
+ value_type back() const {
+ assert(!empty());
+ return begin()[size() - 1];
+ }
+ void pop_back() { assert(!empty()); store_.shrink(1); }
+
+ // 21.3.3 capacity:
+ size_type size() const { return store_.size(); }
+
+ size_type length() const { return size(); }
+
+ size_type max_size() const {
+ return std::numeric_limits<size_type>::max();
+ }
+
+ void resize(const size_type n, const value_type c = value_type()) {
+ auto size = this->size();
+ if (n <= size) {
+ store_.shrink(size - n);
+ } else {
+ // Do this in two steps to minimize slack memory copied (see
+ // smartRealloc).
+ auto const capacity = this->capacity();
+ assert(capacity >= size);
+ if (size < capacity) {
+ auto delta = std::min(n, capacity) - size;
+ store_.expand_noinit(delta);
+ fbstring_detail::pod_fill(begin() + size, end(), c);
+ size += delta;
+ if (size == n) {
+ store_.writeTerminator();
+ return;
+ }
+ assert(size < n);
+ }
+ auto const delta = n - size;
+ store_.expand_noinit(delta);
+ fbstring_detail::pod_fill(end() - delta, end(), c);
+ store_.writeTerminator();
+ }
+ assert(this->size() == n);
+ }
+
+ size_type capacity() const { return store_.capacity(); }
+
+ void reserve(size_type res_arg = 0) {
+ enforce(res_arg <= max_size(), std::__throw_length_error, "");
+ store_.reserve(res_arg);
+ }
+
+ void clear() { resize(0); }
+
+ bool empty() const { return size() == 0; }
+
+ // 21.3.4 element access:
+ const_reference operator[](size_type pos) const {
+ return *(c_str() + pos);
+ }
+
+ reference operator[](size_type pos) {
+ if (pos == size()) {
+ // Just call c_str() to make sure '\0' is present
+ c_str();
+ }
+ return *(begin() + pos);
+ }
+
+ const_reference at(size_type n) const {
+ enforce(n <= size(), std::__throw_out_of_range, "");
+ return (*this)[n];
+ }
+
+ reference at(size_type n) {
+ enforce(n < size(), std::__throw_out_of_range, "");
+ return (*this)[n];
+ }
+
+ // 21.3.5 modifiers:
+ basic_fbstring& operator+=(const basic_fbstring& str) {
+ return append(str);
+ }
+
+ basic_fbstring& operator+=(const value_type* s) {
+ return append(s);
+ }
+
+ basic_fbstring& operator+=(const value_type c) {
+ push_back(c);
+ return *this;
+ }
+
+ basic_fbstring& append(const basic_fbstring& str) {
+#ifndef NDEBUG
+ auto desiredSize = size() + str.size();
+#endif
+ append(str.data(), str.size());
+ assert(size() == desiredSize);
+ return *this;
+ }
+
+ basic_fbstring& 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);
+ }
+
+ basic_fbstring& append(const value_type* s, const size_type n) {
+#ifndef NDEBUG
+ auto oldSize = size();
+#endif
+ Invariant checker(*this);
+ (void) checker;
+ static std::less_equal<const value_type*> le;
+ if (le(data(), s) && !le(data() + size(), s)) {// aliasing
+ assert(le(s + n, data() + size()));
+ const size_type offset = s - data();
+ store_.reserve(size() + n);
+ // Restore the source
+ s = data() + offset;
+ }
+ store_.expand_noinit(n);
+ fbstring_detail::pod_copy(s, s + n, end() - n);
+ store_.writeTerminator();
+ assert(size() == oldSize + n);
+ return *this;
+ }
+
+ basic_fbstring& append(const value_type* s) {
+ return append(s, traits_type::length(s));
+ }
+
+ basic_fbstring& append(size_type n, value_type c) {
+ resize(size() + n, c);
+ return *this;
+ }
+
+ template<class InputIterator>
+ basic_fbstring& append(InputIterator first, InputIterator last) {
+ insert(end(), first, last);
+ return *this;
+ }
+
+ void push_back(const value_type c) { // primitive
+ store_.push_back(c);
+ }
+
+ basic_fbstring& assign(const basic_fbstring& str) {
+ if (&str == this) return *this;
+ return assign(str.data(), str.size());
+ }
+
+ basic_fbstring& 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);
+ }
+
+ basic_fbstring& assign(const value_type* s, const size_type n) {
+ Invariant checker(*this);
+ (void) checker;
+ if (size() >= n) {
+ std::copy(s, s + n, begin());
+ resize(n);
+ assert(size() == n);
+ } else {
+ const value_type *const s2 = s + size();
+ std::copy(s, s2, begin());
+ append(s2, n - size());
+ assert(size() == n);
+ }
+ store_.writeTerminator();
+ assert(size() == n);
+ return *this;
+ }
+
+ basic_fbstring& assign(const value_type* s) {
+ return assign(s, traits_type::length(s));
+ }
+
+ template <class ItOrLength, class ItOrChar>
+ basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
+ return replace(begin(), end(), first_or_n, last_or_c);
+ }
+
+ basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
+ return insert(pos1, str.data(), str.size());
+ }
+
+ basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
+ size_type pos2, size_type n) {
+ enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
+ procrustes(n, str.length() - pos2);
+ return insert(pos1, str.data() + pos2, n);
+ }
+
+ basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
+ enforce(pos <= length(), std::__throw_out_of_range, "");
+ insert(begin() + pos, s, s + n);
+ return *this;
+ }
+
+ basic_fbstring& insert(size_type pos, const value_type* s) {
+ return insert(pos, s, traits_type::length(s));
+ }
+
+ basic_fbstring& insert(size_type pos, size_type n, value_type c) {
+ enforce(pos <= length(), std::__throw_out_of_range, "");
+ insert(begin() + pos, n, c);
+ return *this;
+ }
+
+ iterator insert(const iterator p, const value_type c) {
+ const size_type pos = p - begin();
+ insert(p, 1, c);
+ return begin() + pos;
+ }
+
+private:
+ template <int i> class Selector {};
+
+ basic_fbstring& insertImplDiscr(iterator p,
+ size_type n, value_type c, Selector<1>) {
+ Invariant checker(*this);
+ (void) checker;
+ assert(p >= begin() && p <= end());
+ if (capacity() - size() < n) {
+ const size_type sz = p - begin();
+ reserve(size() + n);
+ p = begin() + sz;
+ }
+ const iterator oldEnd = end();
+ if( n < size_type(oldEnd - p)) {
+ append(oldEnd - n, oldEnd);
+ //std::copy(
+ // reverse_iterator(oldEnd - n),
+ // reverse_iterator(p),
+ // reverse_iterator(oldEnd));
+ fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
+ std::fill(p, p + n, c);
+ } else {
+ append(n - (end() - p), c);
+ append(p, oldEnd);
+ std::fill(p, oldEnd, c);
+ }
+ store_.writeTerminator();
+ return *this;
+ }
+
+ template<class InputIter>
+ basic_fbstring& insertImplDiscr(iterator i,
+ InputIter b, InputIter e, Selector<0>) {
+ insertImpl(i, b, e,
+ typename std::iterator_traits<InputIter>::iterator_category());
+ return *this;
+ }
+
+ template <class FwdIterator>
+ void insertImpl(iterator i,
+ FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
+ Invariant checker(*this);
+ (void) checker;
+ const size_type pos = i - begin();
+ const typename std::iterator_traits<FwdIterator>::difference_type n2 =
+ std::distance(s1, s2);
+ assert(n2 >= 0);
+ using namespace fbstring_detail;
+ assert(pos <= size());
+
+ const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
+ capacity() - size();
+ if (maxn2 < n2) {
+ // realloc the string
+ reserve(size() + n2);
+ i = begin() + pos;
+ }
+ if (pos + n2 <= size()) {
+ const iterator tailBegin = end() - n2;
+ store_.expand_noinit(n2);
+ fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
+ std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
+ reverse_iterator(tailBegin + n2));
+ std::copy(s1, s2, i);
+ } else {
+ FwdIterator t = s1;
+ const size_type old_size = size();
+ std::advance(t, old_size - pos);
+ const size_t newElems = std::distance(t, s2);
+ store_.expand_noinit(n2);
+ std::copy(t, s2, begin() + old_size);
+ fbstring_detail::pod_copy(data() + pos, data() + old_size,
+ begin() + old_size + newElems);
+ std::copy(s1, t, i);
+ }
+ store_.writeTerminator();
+ }
+
+ template <class InputIterator>
+ void insertImpl(iterator i,
+ InputIterator b, InputIterator e, std::input_iterator_tag) {
+ basic_fbstring temp(begin(), i);
+ for (; b != e; ++b) {
+ temp.push_back(*b);
+ }
+ temp.append(i, end());
+ swap(temp);
+ }
+
+public:
+ template <class ItOrLength, class ItOrChar>
+ void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
+ Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
+ insertImplDiscr(p, first_or_n, last_or_c, sel);
+ }
+
+ basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
+ Invariant checker(*this);
+ (void) checker;
+ enforce(pos <= length(), std::__throw_out_of_range, "");
+ procrustes(n, length() - pos);
+ std::copy(begin() + pos + n, end(), begin() + pos);
+ resize(length() - n);
+ return *this;
+ }
+
+ iterator erase(iterator position) {
+ const size_type pos(position - begin());
+ enforce(pos <= size(), std::__throw_out_of_range, "");
+ erase(pos, 1);
+ return begin() + pos;
+ }
+
+ iterator erase(iterator first, iterator last) {
+ const size_type pos(first - begin());
+ erase(pos, last - first);
+ return begin() + pos;
+ }
+
+ // Replaces at most n1 chars of *this, starting with pos1 with the
+ // content of str
+ basic_fbstring& replace(size_type pos1, size_type n1,
+ const basic_fbstring& str) {
+ return replace(pos1, n1, str.data(), str.size());
+ }
+
+ // Replaces at most n1 chars of *this, starting with pos1,
+ // with at most n2 chars of str starting with pos2
+ basic_fbstring& replace(size_type pos1, size_type n1,
+ const basic_fbstring& str,
+ size_type pos2, size_type n2) {
+ enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
+ return replace(pos1, n1, str.data() + pos2,
+ std::min(n2, str.size() - pos2));
+ }
+
+ // Replaces at most n1 chars of *this, starting with pos, with chars from s
+ basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
+ return replace(pos, n1, s, traits_type::length(s));
+ }
+
+ // Replaces at most n1 chars of *this, starting with pos, with n2
+ // occurences of c
+ //
+ // consolidated with
+ //
+ // Replaces at most n1 chars of *this, starting with pos, with at
+ // most n2 chars of str. str must have at least n2 chars.
+ template <class StrOrLength, class NumOrChar>
+ basic_fbstring& replace(size_type pos, size_type n1,
+ StrOrLength s_or_n2, NumOrChar n_or_c) {
+ Invariant checker(*this);
+ (void) checker;
+ enforce(pos <= size(), std::__throw_out_of_range, "");
+ procrustes(n1, length() - pos);
+ const iterator b = begin() + pos;
+ return replace(b, b + n1, s_or_n2, n_or_c);
+ }
+
+ basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
+ return replace(i1, i2, str.data(), str.length());
+ }
+
+ basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
+ return replace(i1, i2, s, traits_type::length(s));
+ }
+
+private:
+ basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
+ const value_type* s, size_type n,
+ Selector<2>) {
+ assert(i1 <= i2);
+ assert(begin() <= i1 && i1 <= end());
+ assert(begin() <= i2 && i2 <= end());
+ return replace(i1, i2, s, s + n);
+ }
+
+ basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
+ size_type n2, value_type c, Selector<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);
+ }
+ assert(isSane());
+ return *this;
+ }
+
+ template <class InputIter>
+ basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
+ InputIter b, InputIter e,
+ Selector<0>) {
+ replaceImpl(i1, i2, b, e,
+ typename std::iterator_traits<InputIter>::iterator_category());
+ return *this;
+ }
+
+private:
+ template <class FwdIterator, class P>
+ bool replaceAliased(iterator i1, iterator i2,
+ FwdIterator s1, FwdIterator s2, P*) {
+ return false;
+ }
+
+ template <class FwdIterator>
+ bool replaceAliased(iterator i1, iterator i2,
+ FwdIterator s1, FwdIterator s2, value_type*) {
+ static const std::less_equal<const value_type*> le =
+ std::less_equal<const value_type*>();
+ 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;
+ }
+
+public:
+ template <class FwdIterator>
+ void replaceImpl(iterator i1, iterator i2,
+ FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
+ Invariant checker(*this);
+ (void) checker;
+
+ // Handle aliased replace
+ if (replaceAliased(i1, i2, s1, s2, &*s1)) {
+ return;
+ }
+
+ auto const n1 = i2 - i1;
+ assert(n1 >= 0);
+ auto const n2 = std::distance(s1, s2);
+ assert(n2 >= 0);
+
+ if (n1 > n2) {
+ // shrinks
+ std::copy(s1, s2, i1);
+ erase(i1 + n2, i2);
+ } else {
+ // grows
+ fbstring_detail::copy_n(s1, n1, i1);
+ std::advance(s1, n1);
+ insert(i2, s1, s2);
+ }
+ assert(isSane());
+ }
+
+ template <class InputIterator>
+ void 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);
+ }
+
+public:
+ template <class T1, class T2>
+ basic_fbstring& replace(iterator i1, iterator i2,
+ T1 first_or_n_or_s, T2 last_or_c_or_n) {
+ const bool
+ num1 = std::numeric_limits<T1>::is_specialized,
+ num2 = std::numeric_limits<T2>::is_specialized;
+ return replaceImplDiscr(
+ i1, i2, first_or_n_or_s, last_or_c_or_n,
+ Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
+ }
+
+ size_type copy(value_type* s, size_type n, size_type pos = 0) const {
+ enforce(pos <= size(), std::__throw_out_of_range, "");
+ procrustes(n, size() - pos);
+
+ fbstring_detail::pod_copy(
+ data() + pos,
+ data() + pos + n,
+ s);
+ return n;
+ }
+
+ void swap(basic_fbstring& rhs) {
+ store_.swap(rhs.store_);
+ }
+
+ // 21.3.6 string operations:
+ const value_type* c_str() const {
+ return store_.c_str();
+ }
+
+ const value_type* data() const { return c_str(); }
+
+ allocator_type get_allocator() const {
+ return allocator_type();
+ }
+
+ size_type find(const basic_fbstring& str, size_type pos = 0) const {
+ return find(str.data(), pos, str.length());
+ }
+
+ size_type find(const value_type* needle, const size_type pos,
+ const size_type nsize) const {
+ if (!nsize) return pos;
+ auto const size = this->size();
+ if (nsize + pos > size) return npos;
+ // 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; ; ) {
+ 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;
+ }
+
+ size_type find(const value_type* s, size_type pos = 0) const {
+ return find(s, pos, traits_type::length(s));
+ }
+
+ size_type find (value_type c, size_type pos = 0) const {
+ return find(&c, pos, 1);
+ }
+
+ size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
+ return rfind(str.data(), pos, str.length());
+ }
+
+ size_type 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;
+ }
+
+ size_type rfind(const value_type* s, size_type pos = npos) const {
+ return rfind(s, pos, traits_type::length(s));
+ }
+
+ size_type rfind(value_type c, size_type pos = npos) const {
+ return rfind(&c, pos, 1);
+ }
+
+ size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
+ return find_first_of(str.data(), pos, str.length());
+ }
+
+ size_type 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) != 0) {
+ return i - begin();
+ }
+ }
+ return npos;
+ }
+
+ size_type find_first_of(const value_type* s, size_type pos = 0) const {
+ return find_first_of(s, pos, traits_type::length(s));
+ }
+
+ size_type find_first_of(value_type c, size_type pos = 0) const {
+ return find_first_of(&c, pos, 1);
+ }
+
+ size_type find_last_of (const basic_fbstring& str,
+ size_type pos = npos) const {
+ return find_last_of(str.data(), pos, str.length());
+ }
+
+ size_type 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) != 0) {
+ return i - begin();
+ }
+ if (i == begin()) break;
+ }
+ }
+ return npos;
+ }
+
+ size_type find_last_of (const value_type* s,
+ size_type pos = npos) const {
+ return find_last_of(s, pos, traits_type::length(s));
+ }
+
+ size_type find_last_of (value_type c, size_type pos = npos) const {
+ return find_last_of(&c, pos, 1);
+ }
+
+ size_type find_first_not_of(const basic_fbstring& str,
+ size_type pos = 0) const {
+ return find_first_not_of(str.data(), pos, str.size());
+ }
+
+ size_type 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) == 0) {
+ return i - begin();
+ }
+ }
+ }
+ return npos;
+ }
+
+ size_type find_first_not_of(const value_type* s,
+ size_type pos = 0) const {
+ return find_first_not_of(s, pos, traits_type::length(s));
+ }
+
+ size_type find_first_not_of(value_type c, size_type pos = 0) const {
+ return find_first_not_of(&c, pos, 1);
+ }
+
+ size_type find_last_not_of(const basic_fbstring& str,
+ size_type pos = npos) const {
+ return find_last_not_of(str.data(), pos, str.length());
+ }
+
+ size_type 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) == 0) {
+ return i - begin();
+ }
+ if (i == begin()) break;
+ }
+ }
+ return npos;
+ }
+
+ size_type find_last_not_of(const value_type* s,
+ size_type pos = npos) const {
+ return find_last_not_of(s, pos, traits_type::length(s));
+ }
+
+ size_type find_last_not_of (value_type c, size_type pos = npos) const {
+ return find_last_not_of(&c, pos, 1);
+ }
+
+ basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
+ enforce(pos <= size(), std::__throw_out_of_range, "");
+ return basic_fbstring(data() + pos, std::min(n, size() - pos));
+ }
+
+ int compare(const basic_fbstring& str) const {
+ // FIX due to Goncalo N M de Carvalho July 18, 2005
+ return compare(0, size(), str);
+ }
+
+ int compare(size_type pos1, size_type n1,
+ const basic_fbstring& str) const {
+ return compare(pos1, n1, str.data(), str.size());
+ }
+
+ int compare(size_type pos1, size_type n1,
+ const value_type* s) const {
+ return compare(pos1, n1, s, traits_type::length(s));
+ }
+
+ int compare(size_type pos1, size_type n1,
+ const value_type* s, size_type n2) const {
+ enforce(pos1 <= size(), std::__throw_out_of_range, "");
+ procrustes(n1, size() - pos1);
+ // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
+ const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
+ return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
+ }
+
+ int compare(size_type pos1, size_type n1,
+ const basic_fbstring& str,
+ size_type pos2, size_type n2) const {
+ enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
+ return compare(pos1, n1, str.data() + pos2,
+ std::min(n2, str.size() - pos2));
+ }
+
+ // Code from Jean-Francois Bastien (03/26/2007)
+ int compare(const value_type* s) const {
+ // Could forward to compare(0, size(), s, traits_type::length(s))
+ // but that does two extra checks
+ const size_type n1(size()), n2(traits_type::length(s));
+ const int r = traits_type::compare(data(), s, std::min(n1, n2));
+ return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
+ }
+
+private:
+ // Data
+ Storage store_;
+};
+
+// non-member functions
+// C++11 21.4.8.1/2
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+
+ basic_fbstring<E, T, A, S> result;
+ result.reserve(lhs.size() + rhs.size());
+ result.append(lhs).append(rhs);
+ return std::move(result);
+}
+
+// C++11 21.4.8.1/2
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return std::move(lhs.append(rhs));
+}
+
+// C++11 21.4.8.1/3
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
+ basic_fbstring<E, T, A, S>&& rhs) {
+ if (rhs.capacity() >= lhs.size() + rhs.size()) {
+ // Good, at least we don't need to reallocate
+ return std::move(rhs.insert(0, lhs));
+ }
+ // Meh, no go. Forward to operator+(const&, const&).
+ auto const& rhsC = rhs;
+ return lhs + rhsC;
+}
+
+// C++11 21.4.8.1/4
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
+ basic_fbstring<E, T, A, S>&& rhs) {
+ return std::move(lhs.append(rhs));
+}
+
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ //
+ basic_fbstring<E, T, A, S> result;
+ const typename basic_fbstring<E, T, A, S>::size_type len =
+ basic_fbstring<E, T, A, S>::traits_type::length(lhs);
+ result.reserve(len + rhs.size());
+ result.append(lhs, len).append(rhs);
+ return result;
+}
+
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ typename basic_fbstring<E, T, A, S>::value_type lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+
+ basic_fbstring<E, T, A, S> result;
+ result.reserve(1 + rhs.size());
+ result.push_back(lhs);
+ result.append(rhs);
+ return result;
+}
+
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+
+ typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
+ typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
+
+ basic_fbstring<E, T, A, S> result;
+ const size_type len = traits_type::length(rhs);
+ result.reserve(lhs.size() + len);
+ result.append(lhs).append(rhs, len);
+ return result;
+}
+
+template <typename E, class T, class A, class S>
+inline
+basic_fbstring<E, T, A, S> operator+(
+ const basic_fbstring<E, T, A, S>& lhs,
+ typename basic_fbstring<E, T, A, S>::value_type rhs) {
+
+ basic_fbstring<E, T, A, S> result;
+ result.reserve(lhs.size() + 1);
+ result.append(lhs);
+ result.push_back(rhs);
+ return result;
+}
+
+template <typename E, class T, class A, class S>
+inline
+bool operator==(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return lhs.compare(rhs) == 0; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return rhs == lhs; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator==(const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+ return lhs.compare(rhs) == 0; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(lhs == rhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(lhs == rhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+ return !(lhs == rhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator<(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return lhs.compare(rhs) < 0; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator<(const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+ return lhs.compare(rhs) < 0; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return rhs.compare(lhs) > 0; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator>(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return rhs < lhs; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator>(const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+ return rhs < lhs; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return rhs < lhs; }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(rhs < lhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+ return !(rhs < lhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(rhs < lhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(lhs < rhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
+ const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
+ return !(lhs < rhs); }
+
+template <typename E, class T, class A, class S>
+inline
+bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(lhs < rhs);
+}
+
+// subclause 21.3.7.8:
+template <typename E, class T, class A, class S>
+void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
+ lhs.swap(rhs);
+}
+
+// TODO: make this faster.
+template <typename E, class T, class A, class S>
+inline
+std::basic_istream<
+ typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>&
+ operator>>(
+ std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>& is,
+ basic_fbstring<E, T, A, S>& str) {
+ typename std::basic_istream<E, T>::sentry sentry(is);
+ typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>
+ __istream_type;
+ typedef typename __istream_type::ios_base __ios_base;
+ size_t extracted = 0;
+ auto err = __ios_base::goodbit;
+ if (sentry) {
+ auto n = is.width();
+ if (n == 0) {
+ n = str.max_size();
+ }
+ str.erase();
+ auto got = is.rdbuf()->sgetc();
+ for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
+ // Whew. We get to store this guy
+ str.push_back(got);
+ got = is.rdbuf()->snextc();
+ }
+ if (got == T::eof()) {
+ err |= __ios_base::eofbit;
+ is.width(0);
+ }
+ }
+ if (!extracted) {
+ err |= __ios_base::failbit;
+ }
+ if (err) {
+ is.setstate(err);
+ }
+ return is;
+}
+
+template <typename E, class T, class A, class S>
+inline
+std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>&
+operator<<(
+ std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>& os,
+ const basic_fbstring<E, T, A, S>& str) {
+ os.write(str.data(), str.size());
+ return os;
+}
+
+#ifndef _LIBSTDCXX_FBSTRING
+
+template <typename E, class T, class A, class S>
+inline
+std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>&
+getline(
+ std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>& is,
+ basic_fbstring<E, T, A, S>& str,
+ typename basic_fbstring<E, T, A, S>::value_type delim) {
+ // Use the nonstandard getdelim()
+ char * buf = NULL;
+ size_t size = 0;
+ for (;;) {
+ // This looks quadratic but it really depends on realloc
+ auto const newSize = size + 128;
+ buf = static_cast<char*>(realloc(buf, newSize));
+ is.getline(buf + size, newSize - size, delim);
+ if (is.bad() || is.eof() || !is.fail()) {
+ // done by either failure, end of file, or normal read
+ size += std::strlen(buf + size);
+ break;
+ }
+ // Here we have failed due to too short a buffer
+ // Minus one to discount the terminating '\0'
+ size = newSize - 1;
+ assert(buf[size] == 0);
+ // Clear the error so we can continue reading
+ is.clear();
+ }
+ basic_fbstring<E, T, A, S> result(buf, size, size + 1,
+ AcquireMallocatedString());
+ result.swap(str);
+ return is;
+}
+
+template <typename E, class T, class A, class S>
+inline
+std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>&
+getline(
+ std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
+ typename basic_fbstring<E, T, A, S>::traits_type>& is,
+ basic_fbstring<E, T, A, S>& str) {
+ // Just forward to the version with a delimiter
+ return getline(is, str, '\n');
+}
+
+#endif
+
+template <typename E1, class T, class A, class S>
+const typename basic_fbstring<E1, T, A, S>::size_type
+basic_fbstring<E1, T, A, S>::npos =
+ static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
+
+#ifndef _LIBSTDCXX_FBSTRING
+// basic_string compatiblity routines
+
+template <typename E, class T, class A, class S>
+inline
+bool operator==(const basic_fbstring<E, T, A, S>& lhs,
+ const std::string& rhs) {
+ return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
+}
+
+template <typename E, class T, class A, class S>
+inline
+bool operator==(const std::string& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return rhs == lhs;
+}
+
+template <typename E, class T, class A, class S>
+inline
+bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
+ const std::string& rhs) {
+ return !(lhs == rhs);
+}
+
+template <typename E, class T, class A, class S>
+inline
+bool operator!=(const std::string& lhs,
+ const basic_fbstring<E, T, A, S>& rhs) {
+ return !(lhs == rhs);
+}
+
+#if !defined(_LIBSTDCXX_FBSTRING)
+typedef basic_fbstring<char> fbstring;
+#endif
+
+// fbstring is relocatable
+template <class T, class R, class A, class S>
+FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
+
+#else
+_GLIBCXX_END_NAMESPACE_VERSION
+#endif
+
+} // namespace folly
+
+#ifndef _LIBSTDCXX_FBSTRING
+
+namespace std {
+template <>
+struct hash< ::folly::fbstring> {
+ size_t operator()(const ::folly::fbstring& s) const {
+ return ::folly::hash::fnv32(s.c_str());
+ }
+};
+}
+
+#endif // _LIBSTDCXX_FBSTRING
+
+#endif // FOLLY_BASE_FBSTRING_H_