folly/FBString.h

   1 /*
   2  * Copyright 2013 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // @author: Andrei Alexandrescu (aalexandre)
  18 // String type.
  19
  20 #ifndef FOLLY_BASE_FBSTRING_H_
  21 #define FOLLY_BASE_FBSTRING_H_
  22
  23 /**
  24    fbstring's behavior can be configured via two macro definitions, as
  25    follows. Normally, fbstring does not write a '\0' at the end of
  26    each string whenever it changes the underlying characters. Instead,
  27    it lazily writes the '\0' whenever either c_str() or data()
  28    called.
  29
  30    This is standard-compliant behavior and may save costs in some
  31    circumstances. However, it may be surprising to some client code
  32    because c_str() and data() are const member functions (fbstring
  33    uses the "mutable" storage class for its own state).
  34
  35    In order to appease client code that expects fbstring to be
  36    zero-terminated at all times, if the preprocessor symbol
  37    FBSTRING_CONSERVATIVE is defined, fbstring does exactly that,
  38    i.e. it goes the extra mile to guarantee a '\0' is always planted
  39    at the end of its data.
  40
  41    On the contrary, if the desire is to debug faulty client code that
  42    unduly assumes the '\0' is present, fbstring plants a '^' (i.e.,
  43    emphatically NOT a zero) at the end of each string if
  44    FBSTRING_PERVERSE is defined. (Calling c_str() or data() still
  45    writes the '\0', of course.)
  46
  47    The preprocessor symbols FBSTRING_PERVERSE and
  48    FBSTRING_CONSERVATIVE cannot be defined simultaneously. This is
  49    enforced during preprocessing.
  50 */
  51
  52 //#define FBSTRING_PERVERSE
  53 //#define FBSTRING_CONSERVATIVE
  54
  55 #ifdef FBSTRING_PERVERSE
  56 #ifdef FBSTRING_CONSERVATIVE
  57 #error Cannot define both FBSTRING_PERVERSE and FBSTRING_CONSERVATIVE.
  58 #endif
  59 #endif
  60
  61 // This file appears in two locations: inside fbcode and in the
  62 // libstdc++ source code (when embedding fbstring as std::string).
  63 // To aid in this schizophrenic use, two macros are defined in
  64 // c++config.h:
  65 //   _LIBSTDCXX_FBSTRING - Set inside libstdc++.  This is useful to
  66 //      gate use inside fbcode v. libstdc++
  67 #include <bits/c++config.h>
  68
  69 #ifdef _LIBSTDCXX_FBSTRING
  70
  71 #pragma GCC system_header
  72
  73 // Handle the cases where the fbcode version (folly/Malloc.h) is included
  74 // either before or after this inclusion.
  75 #ifdef FOLLY_MALLOC_H_
  76 #undef FOLLY_MALLOC_H_
  77 #include "basic_fbstring_malloc.h"
  78 #else
  79 #include "basic_fbstring_malloc.h"
  80 #undef FOLLY_MALLOC_H_
  81 #endif
  82
  83 #else // !_LIBSTDCXX_FBSTRING
  84
  85 #include <string>
  86 #include <cstring>
  87 #include <cassert>
  88
  89 #include "folly/Traits.h"
  90 #include "folly/Malloc.h"
  91 #include "folly/Hash.h"
  92
  93 #endif
  94
  95 // We defined these here rather than including Likely.h to avoid
  96 // redefinition errors when fbstring is imported into libstdc++.
  97 #define FBSTRING_LIKELY(x)   (__builtin_expect((x), 1))
  98 #define FBSTRING_UNLIKELY(x) (__builtin_expect((x), 0))
  99
 100 #include <atomic>
 101 #include <limits>
 102 #include <type_traits>
 103
 104 #ifdef _LIBSTDCXX_FBSTRING
 105 namespace std _GLIBCXX_VISIBILITY(default) {
 106 _GLIBCXX_BEGIN_NAMESPACE_VERSION
 107 #else
 108 namespace folly {
 109 #endif
 110
 111 namespace fbstring_detail {
 112
 113 template <class InIt, class OutIt>
 114 inline
 115 OutIt copy_n(InIt b,
 116              typename std::iterator_traits<InIt>::difference_type n,
 117              OutIt d) {
 118   for (; n != 0; --n, ++b, ++d) {
 119     assert((const void*)&*d != &*b);
 120     *d = *b;
 121   }
 122   return d;
 123 }
 124
 125 template <class Pod, class T>
 126 inline void pod_fill(Pod* b, Pod* e, T c) {
 127   assert(b && e && b <= e);
 128   /*static*/ if (sizeof(T) == 1) {
 129     memset(b, c, e - b);
 130   } else {
 131     auto const ee = b + ((e - b) & ~7u);
 132     for (; b != ee; b += 8) {
 133       b[0] = c;
 134       b[1] = c;
 135       b[2] = c;
 136       b[3] = c;
 137       b[4] = c;
 138       b[5] = c;
 139       b[6] = c;
 140       b[7] = c;
 141     }
 142     // Leftovers
 143     for (; b != e; ++b) {
 144       *b = c;
 145     }
 146   }
 147 }
 148
 149 /*
 150  * Lightly structured memcpy, simplifies copying PODs and introduces
 151  * some asserts. Unfortunately using this function may cause
 152  * measurable overhead (presumably because it adjusts from a begin/end
 153  * convention to a pointer/size convention, so it does some extra
 154  * arithmetic even though the caller might have done the inverse
 155  * adaptation outside).
 156  */
 157 template <class Pod>
 158 inline void pod_copy(const Pod* b, const Pod* e, Pod* d) {
 159   assert(e >= b);
 160   assert(d >= e || d + (e - b) <= b);
 161   memcpy(d, b, (e - b) * sizeof(Pod));
 162 }
 163
 164 /*
 165  * Lightly structured memmove, simplifies copying PODs and introduces
 166  * some asserts
 167  */
 168 template <class Pod>
 169 inline void pod_move(const Pod* b, const Pod* e, Pod* d) {
 170   assert(e >= b);
 171   memmove(d, b, (e - b) * sizeof(*b));
 172 }
 173
 174 } // namespace fbstring_detail
 175
 176 /**
 177  * Defines a special acquisition method for constructing fbstring
 178  * objects. AcquireMallocatedString means that the user passes a
 179  * pointer to a malloc-allocated string that the fbstring object will
 180  * take into custody.
 181  */
 182 enum class AcquireMallocatedString {};
 183
 184 /*
 185  * fbstring_core_model is a mock-up type that defines all required
 186  * signatures of a fbstring core. The fbstring class itself uses such
 187  * a core object to implement all of the numerous member functions
 188  * required by the standard.
 189  *
 190  * If you want to define a new core, copy the definition below and
 191  * implement the primitives. Then plug the core into basic_fbstring as
 192  * a template argument.
 193
 194 template <class Char>
 195 class fbstring_core_model {
 196 public:
 197   fbstring_core_model();
 198   fbstring_core_model(const fbstring_core_model &);
 199   ~fbstring_core_model();
 200   // Returns a pointer to string's buffer (currently only contiguous
 201   // strings are supported). The pointer is guaranteed to be valid
 202   // until the next call to a non-const member function.
 203   const Char * data() const;
 204   // Much like data(), except the string is prepared to support
 205   // character-level changes. This call is a signal for
 206   // e.g. reference-counted implementation to fork the data. The
 207   // pointer is guaranteed to be valid until the next call to a
 208   // non-const member function.
 209   Char * mutable_data();
 210   // Returns a pointer to string's buffer and guarantees that a
 211   // readable '\0' lies right after the buffer. The pointer is
 212   // guaranteed to be valid until the next call to a non-const member
 213   // function.
 214   const Char * c_str() const;
 215   // Shrinks the string by delta characters. Asserts that delta <=
 216   // size().
 217   void shrink(size_t delta);
 218   // Expands the string by delta characters (i.e. after this call
 219   // size() will report the old size() plus delta) but without
 220   // initializing the expanded region. Returns a pointer to the memory
 221   // to be initialized (the beginning of the expanded portion). The
 222   // caller is expected to fill the expanded area appropriately.
 223   Char* expand_noinit(size_t delta);
 224   // Expands the string by one character and sets the last character
 225   // to c.
 226   void push_back(Char c);
 227   // Returns the string's size.
 228   size_t size() const;
 229   // Returns the string's capacity, i.e. maximum size that the string
 230   // can grow to without reallocation. Note that for reference counted
 231   // strings that's technically a lie - even assigning characters
 232   // within the existing size would cause a reallocation.
 233   size_t capacity() const;
 234   // Returns true if the data underlying the string is actually shared
 235   // across multiple strings (in a refcounted fashion).
 236   bool isShared() const;
 237   // Makes sure that at least minCapacity characters are available for
 238   // the string without reallocation. For reference-counted strings,
 239   // it should fork the data even if minCapacity < size().
 240   void reserve(size_t minCapacity);
 241 private:
 242   // Do not implement
 243   fbstring_core_model& operator=(const fbstring_core_model &);
 244 };
 245 */
 246
 247 /**
 248  * gcc-4.7 throws what appears to be some false positive uninitialized
 249  * warnings for the members of the MediumLarge struct.  So, mute them here.
 250  */
 251 #if defined(__GNUC__) && !defined(__clang__)
 252 # pragma GCC diagnostic push
 253 # pragma GCC diagnostic ignored "-Wuninitialized"
 254 #endif
 255
 256 /**
 257  * This is the core of the string. The code should work on 32- and
 258  * 64-bit architectures and with any Char size. Porting to big endian
 259  * architectures would require some changes.
 260  *
 261  * The storage is selected as follows (assuming we store one-byte
 262  * characters on a 64-bit machine): (a) "small" strings between 0 and
 263  * 23 chars are stored in-situ without allocation (the rightmost byte
 264  * stores the size); (b) "medium" strings from 24 through 254 chars
 265  * are stored in malloc-allocated memory that is copied eagerly; (c)
 266  * "large" strings of 255 chars and above are stored in a similar
 267  * structure as medium arrays, except that the string is
 268  * reference-counted and copied lazily. the reference count is
 269  * allocated right before the character array.
 270  *
 271  * The discriminator between these three strategies sits in the two
 272  * most significant bits of the rightmost char of the storage. If
 273  * neither is set, then the string is small (and its length sits in
 274  * the lower-order bits of that rightmost character). If the MSb is
 275  * set, the string is medium width. If the second MSb is set, then the
 276  * string is large.
 277  */
 278 template <class Char> class fbstring_core {
 279 public:
 280   fbstring_core() {
 281     // Only initialize the tag, will set the MSBs (i.e. the small
 282     // string size) to zero too
 283     ml_.capacity_ = maxSmallSize << (8 * (sizeof(size_t) - sizeof(Char)));
 284     // or: setSmallSize(0);
 285     writeTerminator();
 286     assert(category() == isSmall && size() == 0);
 287   }
 288
 289   fbstring_core(const fbstring_core & rhs) {
 290     assert(&rhs != this);
 291     // Simplest case first: small strings are bitblitted
 292     if (rhs.category() == isSmall) {
 293       assert(offsetof(MediumLarge, data_) == 0);
 294       assert(offsetof(MediumLarge, size_) == sizeof(ml_.data_));
 295       assert(offsetof(MediumLarge, capacity_) == 2 * sizeof(ml_.data_));
 296       const size_t size = rhs.smallSize();
 297       if (size == 0) {
 298         ml_.capacity_ = rhs.ml_.capacity_;
 299         writeTerminator();
 300       } else {
 301         // Just write the whole thing, don't look at details. In
 302         // particular we need to copy capacity anyway because we want
 303         // to set the size (don't forget that the last character,
 304         // which stores a short string's length, is shared with the
 305         // ml_.capacity field).
 306         ml_ = rhs.ml_;
 307       }
 308       assert(category() == isSmall && this->size() == rhs.size());
 309     } else if (rhs.category() == isLarge) {
 310       // Large strings are just refcounted
 311       ml_ = rhs.ml_;
 312       RefCounted::incrementRefs(ml_.data_);
 313       assert(category() == isLarge && size() == rhs.size());
 314     } else {
 315       // Medium strings are copied eagerly. Don't forget to allocate
 316       // one extra Char for the null terminator.
 317       auto const allocSize =
 318            goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));
 319       ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
 320       fbstring_detail::pod_copy(rhs.ml_.data_,
 321                                 // 1 for terminator
 322                                 rhs.ml_.data_ + rhs.ml_.size_ + 1,
 323                                 ml_.data_);
 324       // No need for writeTerminator() here, we copied one extra
 325       // element just above.
 326       ml_.size_ = rhs.ml_.size_;
 327       ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
 328       assert(category() == isMedium);
 329     }
 330     assert(size() == rhs.size());
 331     assert(memcmp(data(), rhs.data(), size() * sizeof(Char)) == 0);
 332   }
 333
 334   fbstring_core(fbstring_core&& goner) {
 335     if (goner.category() == isSmall) {
 336       // Just copy, leave the goner in peace
 337       new(this) fbstring_core(goner.small_, goner.smallSize());
 338     } else {
 339       // Take goner's guts
 340       ml_ = goner.ml_;
 341       // Clean goner's carcass
 342       goner.setSmallSize(0);
 343     }
 344   }
 345
 346   fbstring_core(const Char *const data, const size_t size) {
 347     // Simplest case first: small strings are bitblitted
 348     if (size <= maxSmallSize) {
 349       // Layout is: Char* data_, size_t size_, size_t capacity_
 350       /*static_*/assert(sizeof(*this) == sizeof(Char*) + 2 * sizeof(size_t));
 351       /*static_*/assert(sizeof(Char*) == sizeof(size_t));
 352       // sizeof(size_t) must be a power of 2
 353       /*static_*/assert((sizeof(size_t) & (sizeof(size_t) - 1)) == 0);
 354
 355       // If data is aligned, use fast word-wise copying. Otherwise,
 356       // use conservative memcpy.
 357       if (reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) {
 358         fbstring_detail::pod_copy(data, data + size, small_);
 359       } else {
 360         // Copy one word (64 bits) at a time
 361         const size_t byteSize = size * sizeof(Char);
 362         if (byteSize > 2 * sizeof(size_t)) {
 363           // Copy three words
 364           ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];
 365           copyTwo:
 366           ml_.size_ = reinterpret_cast<const size_t*>(data)[1];
 367           copyOne:
 368           ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));
 369         } else if (byteSize > sizeof(size_t)) {
 370           // Copy two words
 371           goto copyTwo;
 372         } else if (size > 0) {
 373           // Copy one word
 374           goto copyOne;
 375         }
 376       }
 377       setSmallSize(size);
 378     } else if (size <= maxMediumSize) {
 379       // Medium strings are allocated normally. Don't forget to
 380       // allocate one extra Char for the terminating null.
 381       auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));
 382       ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));
 383       fbstring_detail::pod_copy(data, data + size, ml_.data_);
 384       ml_.size_ = size;
 385       ml_.capacity_ = (allocSize / sizeof(Char) - 1) | isMedium;
 386     } else {
 387       // Large strings are allocated differently
 388       size_t effectiveCapacity = size;
 389       auto const newRC = RefCounted::create(data, & effectiveCapacity);
 390       ml_.data_ = newRC->data_;
 391       ml_.size_ = size;
 392       ml_.capacity_ = effectiveCapacity | isLarge;
 393     }
 394     writeTerminator();
 395     assert(this->size() == size);
 396     assert(memcmp(this->data(), data, size * sizeof(Char)) == 0);
 397   }
 398
 399   ~fbstring_core() {
 400     auto const c = category();
 401     if (c == isSmall) {
 402       return;
 403     }
 404     if (c == isMedium) {
 405       free(ml_.data_);
 406       return;
 407     }
 408     RefCounted::decrementRefs(ml_.data_);
 409   }
 410
 411   // Snatches a previously mallocated string. The parameter "size"
 412   // is the size of the string, and the parameter "capacity" is the size
 413   // of the mallocated block.  The string must be \0-terminated, so
 414   // data[size] == '\0' and capacity >= size + 1.
 415   //
 416   // So if you want a 2-character string, pass malloc(3) as "data", pass 2 as
 417   // "size", and pass 3 as "capacity".
 418   fbstring_core(Char *const data, const size_t size,
 419                 const size_t capacity,
 420                 AcquireMallocatedString) {
 421     if (size > 0) {
 422       assert(capacity > size);
 423       assert(data[size] == '\0');
 424       // Use the medium string storage
 425       ml_.data_ = data;
 426       ml_.size_ = size;
 427       ml_.capacity_ = capacity | isMedium;
 428     } else {
 429       // No need for the memory
 430       free(data);
 431       setSmallSize(0);
 432     }
 433   }
 434
 435   // swap below doesn't test whether &rhs == this (and instead
 436   // potentially does extra work) on the premise that the rarity of
 437   // that situation actually makes the check more expensive than is
 438   // worth.
 439   void swap(fbstring_core & rhs) {
 440     auto const t = ml_;
 441     ml_ = rhs.ml_;
 442     rhs.ml_ = t;
 443   }
 444
 445   // In C++11 data() and c_str() are 100% equivalent.
 446   const Char * data() const {
 447     return c_str();
 448   }
 449
 450   Char * mutable_data() {
 451     auto const c = category();
 452     if (c == isSmall) {
 453       return small_;
 454     }
 455     assert(c == isMedium || c == isLarge);
 456     if (c == isLarge && RefCounted::refs(ml_.data_) > 1) {
 457       // Ensure unique.
 458       size_t effectiveCapacity = ml_.capacity();
 459       auto const newRC = RefCounted::create(& effectiveCapacity);
 460       // If this fails, someone placed the wrong capacity in an
 461       // fbstring.
 462       assert(effectiveCapacity >= ml_.capacity());
 463       fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
 464                                 newRC->data_);
 465       RefCounted::decrementRefs(ml_.data_);
 466       ml_.data_ = newRC->data_;
 467       // No need to call writeTerminator(), we have + 1 above.
 468     }
 469     return ml_.data_;
 470   }
 471
 472   const Char * c_str() const {
 473     auto const c = category();
 474 #ifdef FBSTRING_PERVERSE
 475     if (c == isSmall) {
 476       assert(small_[smallSize()] == TERMINATOR || smallSize() == maxSmallSize
 477              || small_[smallSize()] == '\0');
 478       small_[smallSize()] = '\0';
 479       return small_;
 480     }
 481     assert(c == isMedium || c == isLarge);
 482     assert(ml_.data_[ml_.size_] == TERMINATOR || ml_.data_[ml_.size_] == '\0');
 483     ml_.data_[ml_.size_] = '\0';
 484 #elif defined(FBSTRING_CONSERVATIVE)
 485     if (c == isSmall) {
 486       assert(small_[smallSize()] == '\0');
 487       return small_;
 488     }
 489     assert(c == isMedium || c == isLarge);
 490     assert(ml_.data_[ml_.size_] == '\0');
 491 #else
 492     if (c == isSmall) {
 493       small_[smallSize()] = '\0';
 494       return small_;
 495     }
 496     assert(c == isMedium || c == isLarge);
 497     ml_.data_[ml_.size_] = '\0';
 498 #endif
 499     return ml_.data_;
 500   }
 501
 502   void shrink(const size_t delta) {
 503     if (category() == isSmall) {
 504       // Check for underflow
 505       assert(delta <= smallSize());
 506       setSmallSize(smallSize() - delta);
 507     } else if (category() == isMedium || RefCounted::refs(ml_.data_) == 1) {
 508       // Medium strings and unique large strings need no special
 509       // handling.
 510       assert(ml_.size_ >= delta);
 511       ml_.size_ -= delta;
 512     } else {
 513       assert(ml_.size_ >= delta);
 514       // Shared large string, must make unique. This is because of the
 515       // durn terminator must be written, which may trample the shared
 516       // data.
 517       if (delta) {
 518         fbstring_core(ml_.data_, ml_.size_ - delta).swap(*this);
 519       }
 520       // No need to write the terminator.
 521       return;
 522     }
 523     writeTerminator();
 524   }
 525
 526   void reserve(size_t minCapacity) {
 527     if (category() == isLarge) {
 528       // Ensure unique
 529       if (RefCounted::refs(ml_.data_) > 1) {
 530         // We must make it unique regardless; in-place reallocation is
 531         // useless if the string is shared. In order to not surprise
 532         // people, reserve the new block at current capacity or
 533         // more. That way, a string's capacity never shrinks after a
 534         // call to reserve.
 535         minCapacity = std::max(minCapacity, ml_.capacity());
 536         auto const newRC = RefCounted::create(& minCapacity);
 537         fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_ + 1,
 538                                    newRC->data_);
 539         // Done with the old data. No need to call writeTerminator(),
 540         // we have + 1 above.
 541         RefCounted::decrementRefs(ml_.data_);
 542         ml_.data_ = newRC->data_;
 543         ml_.capacity_ = minCapacity | isLarge;
 544         // size remains unchanged
 545       } else {
 546         // String is not shared, so let's try to realloc (if needed)
 547         if (minCapacity > ml_.capacity()) {
 548           // Asking for more memory
 549           auto const newRC =
 550                RefCounted::reallocate(ml_.data_, ml_.size_,
 551                                       ml_.capacity(), minCapacity);
 552           ml_.data_ = newRC->data_;
 553           ml_.capacity_ = minCapacity | isLarge;
 554           writeTerminator();
 555         }
 556         assert(capacity() >= minCapacity);
 557       }
 558     } else if (category() == isMedium) {
 559       // String is not shared
 560       if (minCapacity <= ml_.capacity()) {
 561         return; // nothing to do, there's enough room
 562       }
 563       if (minCapacity <= maxMediumSize) {
 564         // Keep the string at medium size. Don't forget to allocate
 565         // one extra Char for the terminating null.
 566         size_t capacityBytes = goodMallocSize((1 + minCapacity) * sizeof(Char));
 567         ml_.data_ = static_cast<Char *>(
 568           smartRealloc(
 569             ml_.data_,
 570             ml_.size_ * sizeof(Char),
 571             ml_.capacity() * sizeof(Char),
 572             capacityBytes));
 573         writeTerminator();
 574         ml_.capacity_ = (capacityBytes / sizeof(Char) - 1) | isMedium;
 575       } else {
 576         // Conversion from medium to large string
 577         fbstring_core nascent;
 578         // Will recurse to another branch of this function
 579         nascent.reserve(minCapacity);
 580         nascent.ml_.size_ = ml_.size_;
 581         fbstring_detail::pod_copy(ml_.data_, ml_.data_ + ml_.size_,
 582                                   nascent.ml_.data_);
 583         nascent.swap(*this);
 584         writeTerminator();
 585         assert(capacity() >= minCapacity);
 586       }
 587     } else {
 588       assert(category() == isSmall);
 589       if (minCapacity > maxMediumSize) {
 590         // large
 591         auto const newRC = RefCounted::create(& minCapacity);
 592         auto const size = smallSize();
 593         fbstring_detail::pod_copy(small_, small_ + size + 1, newRC->data_);
 594         // No need for writeTerminator(), we wrote it above with + 1.
 595         ml_.data_ = newRC->data_;
 596         ml_.size_ = size;
 597         ml_.capacity_ = minCapacity | isLarge;
 598         assert(capacity() >= minCapacity);
 599       } else if (minCapacity > maxSmallSize) {
 600         // medium
 601         // Don't forget to allocate one extra Char for the terminating null
 602         auto const allocSizeBytes =
 603           goodMallocSize((1 + minCapacity) * sizeof(Char));
 604         auto const data = static_cast<Char*>(checkedMalloc(allocSizeBytes));
 605         auto const size = smallSize();
 606         fbstring_detail::pod_copy(small_, small_ + size + 1, data);
 607         // No need for writeTerminator(), we wrote it above with + 1.
 608         ml_.data_ = data;
 609         ml_.size_ = size;
 610         ml_.capacity_ = (allocSizeBytes / sizeof(Char) - 1) | isMedium;
 611       } else {
 612         // small
 613         // Nothing to do, everything stays put
 614       }
 615     }
 616     assert(capacity() >= minCapacity);
 617   }
 618
 619   Char * expand_noinit(const size_t delta) {
 620     // Strategy is simple: make room, then change size
 621     assert(capacity() >= size());
 622     size_t sz, newSz;
 623     if (category() == isSmall) {
 624       sz = smallSize();
 625       newSz = sz + delta;
 626       if (newSz <= maxSmallSize) {
 627         setSmallSize(newSz);
 628         writeTerminator();
 629         return small_ + sz;
 630       }
 631       reserve(newSz);
 632     } else {
 633       sz = ml_.size_;
 634       newSz = ml_.size_ + delta;
 635       if (newSz > capacity()) {
 636         reserve(newSz);
 637       }
 638     }
 639     assert(capacity() >= newSz);
 640     // Category can't be small - we took care of that above
 641     assert(category() == isMedium || category() == isLarge);
 642     ml_.size_ = newSz;
 643     writeTerminator();
 644     assert(size() == newSz);
 645     return ml_.data_ + sz;
 646   }
 647
 648   void push_back(Char c) {
 649     assert(capacity() >= size());
 650     size_t sz;
 651     if (category() == isSmall) {
 652       sz = smallSize();
 653       if (sz < maxSmallSize) {
 654         setSmallSize(sz + 1);
 655         small_[sz] = c;
 656         writeTerminator();
 657         return;
 658       }
 659       reserve(maxSmallSize * 2);
 660     } else {
 661       sz = ml_.size_;
 662       if (sz == capacity()) {  // always true for isShared()
 663         reserve(sz * 3 / 2);  // ensures not shared
 664       }
 665     }
 666     assert(!isShared());
 667     assert(capacity() >= sz + 1);
 668     // Category can't be small - we took care of that above
 669     assert(category() == isMedium || category() == isLarge);
 670     ml_.size_ = sz + 1;
 671     ml_.data_[sz] = c;
 672     writeTerminator();
 673   }
 674
 675   size_t size() const {
 676     return category() == isSmall ? smallSize() : ml_.size_;
 677   }
 678
 679   size_t capacity() const {
 680     switch (category()) {
 681       case isSmall:
 682         return maxSmallSize;
 683       case isLarge:
 684         // For large-sized strings, a multi-referenced chunk has no
 685         // available capacity. This is because any attempt to append
 686         // data would trigger a new allocation.
 687         if (RefCounted::refs(ml_.data_) > 1) return ml_.size_;
 688       default: {}
 689     }
 690     return ml_.capacity();
 691   }
 692
 693   bool isShared() const {
 694     return category() == isLarge && RefCounted::refs(ml_.data_) > 1;
 695   }
 696
 697 #ifdef FBSTRING_PERVERSE
 698   enum { TERMINATOR = '^' };
 699 #else
 700   enum { TERMINATOR = '\0' };
 701 #endif
 702
 703   void writeTerminator() {
 704 #if defined(FBSTRING_PERVERSE) || defined(FBSTRING_CONSERVATIVE)
 705     if (category() == isSmall) {
 706       const auto s = smallSize();
 707       if (s != maxSmallSize) {
 708         small_[s] = TERMINATOR;
 709       }
 710     } else {
 711       ml_.data_[ml_.size_] = TERMINATOR;
 712     }
 713 #endif
 714   }
 715
 716 private:
 717   // Disabled
 718   fbstring_core & operator=(const fbstring_core & rhs);
 719
 720   struct MediumLarge {
 721     Char * data_;
 722     size_t size_;
 723     size_t capacity_;
 724
 725     size_t capacity() const {
 726       return capacity_ & capacityExtractMask;
 727     }
 728   };
 729
 730   struct RefCounted {
 731     std::atomic<size_t> refCount_;
 732     Char data_[1];
 733
 734     static RefCounted * fromData(Char * p) {
 735       return static_cast<RefCounted*>(
 736         static_cast<void*>(
 737           static_cast<unsigned char*>(static_cast<void*>(p))
 738           - sizeof(refCount_)));
 739     }
 740
 741     static size_t refs(Char * p) {
 742       return fromData(p)->refCount_.load(std::memory_order_acquire);
 743     }
 744
 745     static void incrementRefs(Char * p) {
 746       fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);
 747     }
 748
 749     static void decrementRefs(Char * p) {
 750       auto const dis = fromData(p);
 751       size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);
 752       assert(oldcnt > 0);
 753       if (oldcnt == 1) {
 754         free(dis);
 755       }
 756     }
 757
 758     static RefCounted * create(size_t * size) {
 759       // Don't forget to allocate one extra Char for the terminating
 760       // null. In this case, however, one Char is already part of the
 761       // struct.
 762       const size_t allocSize = goodMallocSize(
 763         sizeof(RefCounted) + *size * sizeof(Char));
 764       auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));
 765       result->refCount_.store(1, std::memory_order_release);
 766       *size = (allocSize - sizeof(RefCounted)) / sizeof(Char);
 767       return result;
 768     }
 769
 770     static RefCounted * create(const Char * data, size_t * size) {
 771       const size_t effectiveSize = *size;
 772       auto result = create(size);
 773       fbstring_detail::pod_copy(data, data + effectiveSize, result->data_);
 774       return result;
 775     }
 776
 777     static RefCounted * reallocate(Char *const data,
 778                                    const size_t currentSize,
 779                                    const size_t currentCapacity,
 780                                    const size_t newCapacity) {
 781       assert(newCapacity > 0 && newCapacity > currentSize);
 782       auto const dis = fromData(data);
 783       assert(dis->refCount_.load(std::memory_order_acquire) == 1);
 784       // Don't forget to allocate one extra Char for the terminating
 785       // null. In this case, however, one Char is already part of the
 786       // struct.
 787       auto result = static_cast<RefCounted*>(
 788              smartRealloc(dis,
 789                           sizeof(RefCounted) + currentSize * sizeof(Char),
 790                           sizeof(RefCounted) + currentCapacity * sizeof(Char),
 791                           sizeof(RefCounted) + newCapacity * sizeof(Char)));
 792       assert(result->refCount_.load(std::memory_order_acquire) == 1);
 793       return result;
 794     }
 795   };
 796
 797   union {
 798     mutable Char small_[sizeof(MediumLarge) / sizeof(Char)];
 799     mutable MediumLarge ml_;
 800   };
 801
 802   enum {
 803     lastChar = sizeof(MediumLarge) - 1,
 804     maxSmallSize = lastChar / sizeof(Char),
 805     maxMediumSize = 254 / sizeof(Char),            // coincides with the small
 806                                                    // bin size in dlmalloc
 807     categoryExtractMask = sizeof(size_t) == 4 ? 0xC0000000 : 0xC000000000000000,
 808     capacityExtractMask = ~categoryExtractMask,
 809   };
 810   static_assert(!(sizeof(MediumLarge) % sizeof(Char)),
 811                 "Corrupt memory layout for fbstring.");
 812
 813   enum Category {
 814     isSmall = 0,
 815     isMedium = sizeof(size_t) == 4 ? 0x80000000 : 0x8000000000000000,
 816     isLarge =  sizeof(size_t) == 4 ? 0x40000000 : 0x4000000000000000,
 817   };
 818
 819   Category category() const {
 820     // Assumes little endian
 821     return static_cast<Category>(ml_.capacity_ & categoryExtractMask);
 822   }
 823
 824   size_t smallSize() const {
 825     assert(category() == isSmall && small_[maxSmallSize] <= maxSmallSize);
 826     return static_cast<size_t>(maxSmallSize)
 827       - static_cast<size_t>(small_[maxSmallSize]);
 828   }
 829
 830   void setSmallSize(size_t s) {
 831     // Warning: this should work with uninitialized strings too,
 832     // so don't assume anything about the previous value of
 833     // small_[maxSmallSize].
 834     assert(s <= maxSmallSize);
 835     small_[maxSmallSize] = maxSmallSize - s;
 836   }
 837 };
 838
 839 #if defined(__GNUC__) && !defined(__clang__)
 840 # pragma GCC diagnostic pop
 841 #endif
 842
 843 #ifndef _LIBSTDCXX_FBSTRING
 844 /**
 845  * Dummy fbstring core that uses an actual std::string. This doesn't
 846  * make any sense - it's just for testing purposes.
 847  */
 848 template <class Char>
 849 class dummy_fbstring_core {
 850 public:
 851   dummy_fbstring_core() {
 852   }
 853   dummy_fbstring_core(const dummy_fbstring_core& another)
 854       : backend_(another.backend_) {
 855   }
 856   dummy_fbstring_core(const Char * s, size_t n)
 857       : backend_(s, n) {
 858   }
 859   void swap(dummy_fbstring_core & rhs) {
 860     backend_.swap(rhs.backend_);
 861   }
 862   const Char * data() const {
 863     return backend_.data();
 864   }
 865   Char * mutable_data() {
 866     //assert(!backend_.empty());
 867     return &*backend_.begin();
 868   }
 869   void shrink(size_t delta) {
 870     assert(delta <= size());
 871     backend_.resize(size() - delta);
 872   }
 873   Char * expand_noinit(size_t delta) {
 874     auto const sz = size();
 875     backend_.resize(size() + delta);
 876     return backend_.data() + sz;
 877   }
 878   void push_back(Char c) {
 879     backend_.push_back(c);
 880   }
 881   size_t size() const {
 882     return backend_.size();
 883   }
 884   size_t capacity() const {
 885     return backend_.capacity();
 886   }
 887   bool isShared() const {
 888     return false;
 889   }
 890   void reserve(size_t minCapacity) {
 891     backend_.reserve(minCapacity);
 892   }
 893
 894 private:
 895   std::basic_string<Char> backend_;
 896 };
 897 #endif // !_LIBSTDCXX_FBSTRING
 898
 899 /**
 900  * This is the basic_string replacement. For conformity,
 901  * basic_fbstring takes the same template parameters, plus the last
 902  * one which is the core.
 903  */
 904 #ifdef _LIBSTDCXX_FBSTRING
 905 template <typename E, class T, class A, class Storage>
 906 #else
 907 template <typename E,
 908           class T = std::char_traits<E>,
 909           class A = std::allocator<E>,
 910           class Storage = fbstring_core<E> >
 911 #endif
 912 class basic_fbstring {
 913
 914   static void enforce(
 915       bool condition,
 916       void (*throw_exc)(const char*),
 917       const char* msg) {
 918     if (!condition) throw_exc(msg);
 919   }
 920
 921   bool isSane() const {
 922     return
 923       begin() <= end() &&
 924       empty() == (size() == 0) &&
 925       empty() == (begin() == end()) &&
 926       size() <= max_size() &&
 927       capacity() <= max_size() &&
 928       size() <= capacity() &&
 929       (begin()[size()] == Storage::TERMINATOR || begin()[size()] == '\0');
 930   }
 931
 932   struct Invariant;
 933   friend struct Invariant;
 934   struct Invariant {
 935 #ifndef NDEBUG
 936     explicit Invariant(const basic_fbstring& s) : s_(s) {
 937       assert(s_.isSane());
 938     }
 939     ~Invariant() {
 940       assert(s_.isSane());
 941     }
 942   private:
 943     const basic_fbstring& s_;
 944 #else
 945     explicit Invariant(const basic_fbstring&) {}
 946 #endif
 947     Invariant& operator=(const Invariant&);
 948   };
 949
 950 public:
 951   // types
 952   typedef T traits_type;
 953   typedef typename traits_type::char_type value_type;
 954   typedef A allocator_type;
 955   typedef typename A::size_type size_type;
 956   typedef typename A::difference_type difference_type;
 957
 958   typedef typename A::reference reference;
 959   typedef typename A::const_reference const_reference;
 960   typedef typename A::pointer pointer;
 961   typedef typename A::const_pointer const_pointer;
 962
 963   typedef E* iterator;
 964   typedef const E* const_iterator;
 965   typedef std::reverse_iterator<iterator
 966 #ifdef NO_ITERATOR_TRAITS
 967                                 , value_type
 968 #endif
 969                                 > reverse_iterator;
 970   typedef std::reverse_iterator<const_iterator
 971 #ifdef NO_ITERATOR_TRAITS
 972                                 , const value_type
 973 #endif
 974                                 > const_reverse_iterator;
 975
 976   static const size_type npos;                     // = size_type(-1)
 977
 978 private:
 979   static void procrustes(size_type& n, size_type nmax) {
 980     if (n > nmax) n = nmax;
 981   }
 982
 983 public:
 984   // 21.3.1 construct/copy/destroy
 985   explicit basic_fbstring(const A& a = A()) {
 986   }
 987
 988   basic_fbstring(const basic_fbstring& str)
 989       : store_(str.store_) {
 990   }
 991
 992   // Move constructor
 993   basic_fbstring(basic_fbstring&& goner) : store_(std::move(goner.store_)) {
 994   }
 995
 996 #ifndef _LIBSTDCXX_FBSTRING
 997   // This is defined for compatibility with std::string
 998   /* implicit */ basic_fbstring(const std::string& str)
 999       : store_(str.data(), str.size()) {
1000   }
1001 #endif
1002
1003   basic_fbstring(const basic_fbstring& str, size_type pos,
1004                  size_type n = npos, const A& a = A()) {
1005     assign(str, pos, n);
1006   }
1007
1008   /* implicit */ basic_fbstring(const value_type* s, const A& a = A())
1009       : store_(s, s ? traits_type::length(s) : ({
1010           basic_fbstring<char> err = __PRETTY_FUNCTION__;
1011           err += ": null pointer initializer not valid";
1012           std::__throw_logic_error(err.c_str());
1013           0;
1014       })) {
1015   }
1016
1017   basic_fbstring(const value_type* s, size_type n, const A& a = A())
1018       : store_(s, n) {
1019   }
1020
1021   basic_fbstring(size_type n, value_type c, const A& a = A()) {
1022     auto const data = store_.expand_noinit(n);
1023     fbstring_detail::pod_fill(data, data + n, c);
1024     store_.writeTerminator();
1025   }
1026
1027   template <class InIt>
1028   basic_fbstring(InIt begin, InIt end,
1029                  typename std::enable_if<
1030                  !std::is_same<typename std::remove_const<InIt>::type,
1031                  value_type*>::value, const A>::type & a = A()) {
1032     assign(begin, end);
1033   }
1034
1035   // Specialization for const char*, const char*
1036   basic_fbstring(const value_type* b, const value_type* e)
1037       : store_(b, e - b) {
1038   }
1039
1040   // Nonstandard constructor
1041   basic_fbstring(value_type *s, size_type n, size_type c,
1042                  AcquireMallocatedString a)
1043       : store_(s, n, c, a) {
1044   }
1045
1046   ~basic_fbstring() {
1047   }
1048
1049   basic_fbstring& operator=(const basic_fbstring& lhs) {
1050     if (FBSTRING_UNLIKELY(&lhs == this)) {
1051       return *this;
1052     }
1053     auto const oldSize = size();
1054     auto const srcSize = lhs.size();
1055     if (capacity() >= srcSize && !store_.isShared()) {
1056       // great, just copy the contents
1057       if (oldSize < srcSize)
1058         store_.expand_noinit(srcSize - oldSize);
1059       else
1060         store_.shrink(oldSize - srcSize);
1061       assert(size() == srcSize);
1062       fbstring_detail::pod_copy(lhs.begin(), lhs.end(), begin());
1063       store_.writeTerminator();
1064     } else {
1065       // need to reallocate, so we may as well create a brand new string
1066       basic_fbstring(lhs).swap(*this);
1067     }
1068     return *this;
1069   }
1070
1071   // Move assignment
1072   basic_fbstring& operator=(basic_fbstring&& goner) {
1073     // Self move assignment is illegal, see 17.6.4.9 for the explanation
1074     assert(&goner != this);
1075     // No need of this anymore
1076     this->~basic_fbstring();
1077     // Move the goner into this
1078     new(&store_) fbstring_core<E>(std::move(goner.store_));
1079     return *this;
1080   }
1081
1082 #ifndef _LIBSTDCXX_FBSTRING
1083   // Compatibility with std::string
1084   basic_fbstring & operator=(const std::string & rhs) {
1085     return assign(rhs.data(), rhs.size());
1086   }
1087
1088   // Compatibility with std::string
1089   std::string toStdString() const {
1090     return std::string(data(), size());
1091   }
1092 #else
1093   // A lot of code in fbcode still uses this method, so keep it here for now.
1094   const basic_fbstring& toStdString() const {
1095     return *this;
1096   }
1097 #endif
1098
1099   basic_fbstring& operator=(const value_type* s) {
1100     return assign(s);
1101   }
1102
1103   basic_fbstring& operator=(value_type c) {
1104     if (empty()) {
1105       store_.expand_noinit(1);
1106     } else if (store_.isShared()) {
1107       basic_fbstring(1, c).swap(*this);
1108       return *this;
1109     } else {
1110       store_.shrink(size() - 1);
1111     }
1112     *store_.mutable_data() = c;
1113     store_.writeTerminator();
1114     return *this;
1115   }
1116
1117   // 21.3.2 iterators:
1118   iterator begin() { return store_.mutable_data(); }
1119
1120   const_iterator begin() const { return store_.data(); }
1121
1122   iterator end() {
1123     return store_.mutable_data() + store_.size();
1124   }
1125
1126   const_iterator end() const {
1127     return store_.data() + store_.size();
1128   }
1129
1130   reverse_iterator rbegin() {
1131     return reverse_iterator(end());
1132   }
1133
1134   const_reverse_iterator rbegin() const {
1135     return const_reverse_iterator(end());
1136   }
1137
1138   reverse_iterator rend() {
1139     return reverse_iterator(begin());
1140   }
1141
1142   const_reverse_iterator rend() const {
1143     return const_reverse_iterator(begin());
1144   }
1145
1146   // Added by C++11
1147   // C++11 21.4.5, element access:
1148   const value_type& front() const { return *begin(); }
1149   const value_type& back() const {
1150     assert(!empty());
1151     // Should be begin()[size() - 1], but that branches twice
1152     return *(end() - 1);
1153   }
1154   value_type& front() { return *begin(); }
1155   value_type& back() {
1156     assert(!empty());
1157     // Should be begin()[size() - 1], but that branches twice
1158     return *(end() - 1);
1159   }
1160   void pop_back() {
1161     assert(!empty());
1162     store_.shrink(1);
1163   }
1164
1165   // 21.3.3 capacity:
1166   size_type size() const { return store_.size(); }
1167
1168   size_type length() const { return size(); }
1169
1170   size_type max_size() const {
1171     return std::numeric_limits<size_type>::max();
1172   }
1173
1174   void resize(const size_type n, const value_type c = value_type()) {
1175     auto size = this->size();
1176     if (n <= size) {
1177       store_.shrink(size - n);
1178     } else {
1179       // Do this in two steps to minimize slack memory copied (see
1180       // smartRealloc).
1181       auto const capacity = this->capacity();
1182       assert(capacity >= size);
1183       if (size < capacity) {
1184         auto delta = std::min(n, capacity) - size;
1185         store_.expand_noinit(delta);
1186         fbstring_detail::pod_fill(begin() + size, end(), c);
1187         size += delta;
1188         if (size == n) {
1189           store_.writeTerminator();
1190           return;
1191         }
1192         assert(size < n);
1193       }
1194       auto const delta = n - size;
1195       store_.expand_noinit(delta);
1196       fbstring_detail::pod_fill(end() - delta, end(), c);
1197       store_.writeTerminator();
1198     }
1199     assert(this->size() == n);
1200   }
1201
1202   size_type capacity() const { return store_.capacity(); }
1203
1204   void reserve(size_type res_arg = 0) {
1205     enforce(res_arg <= max_size(), std::__throw_length_error, "");
1206     store_.reserve(res_arg);
1207   }
1208
1209   void clear() { resize(0); }
1210
1211   bool empty() const { return size() == 0; }
1212
1213   // 21.3.4 element access:
1214   const_reference operator[](size_type pos) const {
1215     return *(c_str() + pos);
1216   }
1217
1218   reference operator[](size_type pos) {
1219     if (pos == size()) {
1220       // Just call c_str() to make sure '\0' is present
1221       c_str();
1222     }
1223     return *(begin() + pos);
1224   }
1225
1226   const_reference at(size_type n) const {
1227     enforce(n <= size(), std::__throw_out_of_range, "");
1228     return (*this)[n];
1229   }
1230
1231   reference at(size_type n) {
1232     enforce(n < size(), std::__throw_out_of_range, "");
1233     return (*this)[n];
1234   }
1235
1236   // 21.3.5 modifiers:
1237   basic_fbstring& operator+=(const basic_fbstring& str) {
1238     return append(str);
1239   }
1240
1241   basic_fbstring& operator+=(const value_type* s) {
1242     return append(s);
1243   }
1244
1245   basic_fbstring& operator+=(const value_type c) {
1246     push_back(c);
1247     return *this;
1248   }
1249
1250   basic_fbstring& append(const basic_fbstring& str) {
1251 #ifndef NDEBUG
1252     auto desiredSize = size() + str.size();
1253 #endif
1254     append(str.data(), str.size());
1255     assert(size() == desiredSize);
1256     return *this;
1257   }
1258
1259   basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1260                          size_type n) {
1261     const size_type sz = str.size();
1262     enforce(pos <= sz, std::__throw_out_of_range, "");
1263     procrustes(n, sz - pos);
1264     return append(str.data() + pos, n);
1265   }
1266
1267   basic_fbstring& append(const value_type* s, size_type n) {
1268 #ifndef NDEBUG
1269     Invariant checker(*this);
1270     (void) checker;
1271 #endif
1272     if (FBSTRING_UNLIKELY(!n)) {
1273       // Unlikely but must be done
1274       return *this;
1275     }
1276     auto const oldSize = size();
1277     auto const oldData = data();
1278     // Check for aliasing (rare). We could use "<=" here but in theory
1279     // those do not work for pointers unless the pointers point to
1280     // elements in the same array. For that reason we use
1281     // std::less_equal, which is guaranteed to offer a total order
1282     // over pointers. See discussion at http://goo.gl/Cy2ya for more
1283     // info.
1284     std::less_equal<const value_type*> le;
1285     if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1286       assert(le(s + n, oldData + oldSize));
1287       const size_type offset = s - oldData;
1288       store_.reserve(oldSize + n);
1289       // Restore the source
1290       s = data() + offset;
1291     }
1292     // Warning! Repeated appends with short strings may actually incur
1293     // practically quadratic performance. Avoid that by pushing back
1294     // the first character (which ensures exponential growth) and then
1295     // appending the rest normally. Worst case the append may incur a
1296     // second allocation but that will be rare.
1297     push_back(*s++);
1298     --n;
1299     memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1300     assert(size() == oldSize + n + 1);
1301     return *this;
1302   }
1303
1304   basic_fbstring& append(const value_type* s) {
1305     return append(s, traits_type::length(s));
1306   }
1307
1308   basic_fbstring& append(size_type n, value_type c) {
1309     resize(size() + n, c);
1310     return *this;
1311   }
1312
1313   template<class InputIterator>
1314   basic_fbstring& append(InputIterator first, InputIterator last) {
1315     insert(end(), first, last);
1316     return *this;
1317   }
1318
1319   void push_back(const value_type c) {             // primitive
1320     store_.push_back(c);
1321   }
1322
1323   basic_fbstring& assign(const basic_fbstring& str) {
1324     if (&str == this) return *this;
1325     return assign(str.data(), str.size());
1326   }
1327
1328   basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1329                          size_type n) {
1330     const size_type sz = str.size();
1331     enforce(pos <= sz, std::__throw_out_of_range, "");
1332     procrustes(n, sz - pos);
1333     return assign(str.data() + pos, n);
1334   }
1335
1336   basic_fbstring& assign(const value_type* s, const size_type n) {
1337     Invariant checker(*this);
1338     (void) checker;
1339     if (size() >= n) {
1340       std::copy(s, s + n, begin());
1341       resize(n);
1342       assert(size() == n);
1343     } else {
1344       const value_type *const s2 = s + size();
1345       std::copy(s, s2, begin());
1346       append(s2, n - size());
1347       assert(size() == n);
1348     }
1349     store_.writeTerminator();
1350     assert(size() == n);
1351     return *this;
1352   }
1353
1354   basic_fbstring& assign(const value_type* s) {
1355     return assign(s, traits_type::length(s));
1356   }
1357
1358   template <class ItOrLength, class ItOrChar>
1359   basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1360     return replace(begin(), end(), first_or_n, last_or_c);
1361   }
1362
1363   basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1364     return insert(pos1, str.data(), str.size());
1365   }
1366
1367   basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1368                          size_type pos2, size_type n) {
1369     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1370     procrustes(n, str.length() - pos2);
1371     return insert(pos1, str.data() + pos2, n);
1372   }
1373
1374   basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1375     enforce(pos <= length(), std::__throw_out_of_range, "");
1376     insert(begin() + pos, s, s + n);
1377     return *this;
1378   }
1379
1380   basic_fbstring& insert(size_type pos, const value_type* s) {
1381     return insert(pos, s, traits_type::length(s));
1382   }
1383
1384   basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1385     enforce(pos <= length(), std::__throw_out_of_range, "");
1386     insert(begin() + pos, n, c);
1387     return *this;
1388   }
1389
1390   iterator insert(const iterator p, const value_type c) {
1391     const size_type pos = p - begin();
1392     insert(p, 1, c);
1393     return begin() + pos;
1394   }
1395
1396 private:
1397   template <int i> class Selector {};
1398
1399   basic_fbstring& insertImplDiscr(iterator p,
1400                                   size_type n, value_type c, Selector<1>) {
1401     Invariant checker(*this);
1402     (void) checker;
1403     assert(p >= begin() && p <= end());
1404     if (capacity() - size() < n) {
1405       const size_type sz = p - begin();
1406       reserve(size() + n);
1407       p = begin() + sz;
1408     }
1409     const iterator oldEnd = end();
1410     if( n < size_type(oldEnd - p)) {
1411       append(oldEnd - n, oldEnd);
1412       //std::copy(
1413       //    reverse_iterator(oldEnd - n),
1414       //    reverse_iterator(p),
1415       //    reverse_iterator(oldEnd));
1416       fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1417       std::fill(p, p + n, c);
1418     } else {
1419       append(n - (end() - p), c);
1420       append(p, oldEnd);
1421       std::fill(p, oldEnd, c);
1422     }
1423     store_.writeTerminator();
1424     return *this;
1425   }
1426
1427   template<class InputIter>
1428   basic_fbstring& insertImplDiscr(iterator i,
1429                                   InputIter b, InputIter e, Selector<0>) {
1430     insertImpl(i, b, e,
1431                typename std::iterator_traits<InputIter>::iterator_category());
1432     return *this;
1433   }
1434
1435   template <class FwdIterator>
1436   void insertImpl(iterator i,
1437                   FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1438     Invariant checker(*this);
1439     (void) checker;
1440     const size_type pos = i - begin();
1441     const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1442       std::distance(s1, s2);
1443     assert(n2 >= 0);
1444     using namespace fbstring_detail;
1445     assert(pos <= size());
1446
1447     const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1448       capacity() - size();
1449     if (maxn2 < n2) {
1450       // realloc the string
1451       reserve(size() + n2);
1452       i = begin() + pos;
1453     }
1454     if (pos + n2 <= size()) {
1455       const iterator tailBegin = end() - n2;
1456       store_.expand_noinit(n2);
1457       fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1458       std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1459                 reverse_iterator(tailBegin + n2));
1460       std::copy(s1, s2, i);
1461     } else {
1462       FwdIterator t = s1;
1463       const size_type old_size = size();
1464       std::advance(t, old_size - pos);
1465       const size_t newElems = std::distance(t, s2);
1466       store_.expand_noinit(n2);
1467       std::copy(t, s2, begin() + old_size);
1468       fbstring_detail::pod_copy(data() + pos, data() + old_size,
1469                                  begin() + old_size + newElems);
1470       std::copy(s1, t, i);
1471     }
1472     store_.writeTerminator();
1473   }
1474
1475   template <class InputIterator>
1476   void insertImpl(iterator i,
1477                   InputIterator b, InputIterator e, std::input_iterator_tag) {
1478     basic_fbstring temp(begin(), i);
1479     for (; b != e; ++b) {
1480       temp.push_back(*b);
1481     }
1482     temp.append(i, end());
1483     swap(temp);
1484   }
1485
1486 public:
1487   template <class ItOrLength, class ItOrChar>
1488   void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1489     Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1490     insertImplDiscr(p, first_or_n, last_or_c, sel);
1491   }
1492
1493   basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1494     Invariant checker(*this);
1495     (void) checker;
1496     enforce(pos <= length(), std::__throw_out_of_range, "");
1497     procrustes(n, length() - pos);
1498     std::copy(begin() + pos + n, end(), begin() + pos);
1499     resize(length() - n);
1500     return *this;
1501   }
1502
1503   iterator erase(iterator position) {
1504     const size_type pos(position - begin());
1505     enforce(pos <= size(), std::__throw_out_of_range, "");
1506     erase(pos, 1);
1507     return begin() + pos;
1508   }
1509
1510   iterator erase(iterator first, iterator last) {
1511     const size_type pos(first - begin());
1512     erase(pos, last - first);
1513     return begin() + pos;
1514   }
1515
1516   // Replaces at most n1 chars of *this, starting with pos1 with the
1517   // content of str
1518   basic_fbstring& replace(size_type pos1, size_type n1,
1519                           const basic_fbstring& str) {
1520     return replace(pos1, n1, str.data(), str.size());
1521   }
1522
1523   // Replaces at most n1 chars of *this, starting with pos1,
1524   // with at most n2 chars of str starting with pos2
1525   basic_fbstring& replace(size_type pos1, size_type n1,
1526                           const basic_fbstring& str,
1527                           size_type pos2, size_type n2) {
1528     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1529     return replace(pos1, n1, str.data() + pos2,
1530                    std::min(n2, str.size() - pos2));
1531   }
1532
1533   // Replaces at most n1 chars of *this, starting with pos, with chars from s
1534   basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1535     return replace(pos, n1, s, traits_type::length(s));
1536   }
1537
1538   // Replaces at most n1 chars of *this, starting with pos, with n2
1539   // occurrences of c
1540   //
1541   // consolidated with
1542   //
1543   // Replaces at most n1 chars of *this, starting with pos, with at
1544   // most n2 chars of str.  str must have at least n2 chars.
1545   template <class StrOrLength, class NumOrChar>
1546   basic_fbstring& replace(size_type pos, size_type n1,
1547                           StrOrLength s_or_n2, NumOrChar n_or_c) {
1548     Invariant checker(*this);
1549     (void) checker;
1550     enforce(pos <= size(), std::__throw_out_of_range, "");
1551     procrustes(n1, length() - pos);
1552     const iterator b = begin() + pos;
1553     return replace(b, b + n1, s_or_n2, n_or_c);
1554   }
1555
1556   basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1557     return replace(i1, i2, str.data(), str.length());
1558   }
1559
1560   basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1561     return replace(i1, i2, s, traits_type::length(s));
1562   }
1563
1564 private:
1565   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1566                                    const value_type* s, size_type n,
1567                                    Selector<2>) {
1568     assert(i1 <= i2);
1569     assert(begin() <= i1 && i1 <= end());
1570     assert(begin() <= i2 && i2 <= end());
1571     return replace(i1, i2, s, s + n);
1572   }
1573
1574   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1575                                    size_type n2, value_type c, Selector<1>) {
1576     const size_type n1 = i2 - i1;
1577     if (n1 > n2) {
1578       std::fill(i1, i1 + n2, c);
1579       erase(i1 + n2, i2);
1580     } else {
1581       std::fill(i1, i2, c);
1582       insert(i2, n2 - n1, c);
1583     }
1584     assert(isSane());
1585     return *this;
1586   }
1587
1588   template <class InputIter>
1589   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1590                                    InputIter b, InputIter e,
1591                                    Selector<0>) {
1592     replaceImpl(i1, i2, b, e,
1593                 typename std::iterator_traits<InputIter>::iterator_category());
1594     return *this;
1595   }
1596
1597 private:
1598   template <class FwdIterator, class P>
1599   bool replaceAliased(iterator i1, iterator i2,
1600                       FwdIterator s1, FwdIterator s2, P*) {
1601     return false;
1602   }
1603
1604   template <class FwdIterator>
1605   bool replaceAliased(iterator i1, iterator i2,
1606                       FwdIterator s1, FwdIterator s2, value_type*) {
1607     static const std::less_equal<const value_type*> le =
1608       std::less_equal<const value_type*>();
1609     const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1610     if (!aliased) {
1611       return false;
1612     }
1613     // Aliased replace, copy to new string
1614     basic_fbstring temp;
1615     temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1616     temp.append(begin(), i1).append(s1, s2).append(i2, end());
1617     swap(temp);
1618     return true;
1619   }
1620
1621 public:
1622   template <class FwdIterator>
1623   void replaceImpl(iterator i1, iterator i2,
1624                    FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1625     Invariant checker(*this);
1626     (void) checker;
1627
1628     // Handle aliased replace
1629     if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1630       return;
1631     }
1632
1633     auto const n1 = i2 - i1;
1634     assert(n1 >= 0);
1635     auto const n2 = std::distance(s1, s2);
1636     assert(n2 >= 0);
1637
1638     if (n1 > n2) {
1639       // shrinks
1640       std::copy(s1, s2, i1);
1641       erase(i1 + n2, i2);
1642     } else {
1643       // grows
1644       fbstring_detail::copy_n(s1, n1, i1);
1645       std::advance(s1, n1);
1646       insert(i2, s1, s2);
1647     }
1648     assert(isSane());
1649   }
1650
1651   template <class InputIterator>
1652   void replaceImpl(iterator i1, iterator i2,
1653                    InputIterator b, InputIterator e, std::input_iterator_tag) {
1654     basic_fbstring temp(begin(), i1);
1655     temp.append(b, e).append(i2, end());
1656     swap(temp);
1657   }
1658
1659 public:
1660   template <class T1, class T2>
1661   basic_fbstring& replace(iterator i1, iterator i2,
1662                           T1 first_or_n_or_s, T2 last_or_c_or_n) {
1663     const bool
1664       num1 = std::numeric_limits<T1>::is_specialized,
1665       num2 = std::numeric_limits<T2>::is_specialized;
1666     return replaceImplDiscr(
1667       i1, i2, first_or_n_or_s, last_or_c_or_n,
1668       Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1669   }
1670
1671   size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1672     enforce(pos <= size(), std::__throw_out_of_range, "");
1673     procrustes(n, size() - pos);
1674
1675     fbstring_detail::pod_copy(
1676       data() + pos,
1677       data() + pos + n,
1678       s);
1679     return n;
1680   }
1681
1682   void swap(basic_fbstring& rhs) {
1683     store_.swap(rhs.store_);
1684   }
1685
1686   // 21.3.6 string operations:
1687   const value_type* c_str() const {
1688     return store_.c_str();
1689   }
1690
1691   const value_type* data() const { return c_str(); }
1692
1693   allocator_type get_allocator() const {
1694     return allocator_type();
1695   }
1696
1697   size_type find(const basic_fbstring& str, size_type pos = 0) const {
1698     return find(str.data(), pos, str.length());
1699   }
1700
1701   size_type find(const value_type* needle, const size_type pos,
1702                  const size_type nsize) const {
1703     if (!nsize) return pos;
1704     auto const size = this->size();
1705     if (nsize + pos > size) return npos;
1706     // Don't use std::search, use a Boyer-Moore-like trick by comparing
1707     // the last characters first
1708     auto const haystack = data();
1709     auto const nsize_1 = nsize - 1;
1710     auto const lastNeedle = needle[nsize_1];
1711
1712     // Boyer-Moore skip value for the last char in the needle. Zero is
1713     // not a valid value; skip will be computed the first time it's
1714     // needed.
1715     size_type skip = 0;
1716
1717     const E * i = haystack + pos;
1718     auto iEnd = haystack + size - nsize_1;
1719
1720     while (i < iEnd) {
1721       // Boyer-Moore: match the last element in the needle
1722       while (i[nsize_1] != lastNeedle) {
1723         if (++i == iEnd) {
1724           // not found
1725           return npos;
1726         }
1727       }
1728       // Here we know that the last char matches
1729       // Continue in pedestrian mode
1730       for (size_t j = 0; ; ) {
1731         assert(j < nsize);
1732         if (i[j] != needle[j]) {
1733           // Not found, we can skip
1734           // Compute the skip value lazily
1735           if (skip == 0) {
1736             skip = 1;
1737             while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1738               ++skip;
1739             }
1740           }
1741           i += skip;
1742           break;
1743         }
1744         // Check if done searching
1745         if (++j == nsize) {
1746           // Yay
1747           return i - haystack;
1748         }
1749       }
1750     }
1751     return npos;
1752   }
1753
1754   size_type find(const value_type* s, size_type pos = 0) const {
1755     return find(s, pos, traits_type::length(s));
1756   }
1757
1758   size_type find (value_type c, size_type pos = 0) const {
1759     return find(&c, pos, 1);
1760   }
1761
1762   size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1763     return rfind(str.data(), pos, str.length());
1764   }
1765
1766   size_type rfind(const value_type* s, size_type pos, size_type n) const {
1767     if (n > length()) return npos;
1768     pos = std::min(pos, length() - n);
1769     if (n == 0) return pos;
1770
1771     const_iterator i(begin() + pos);
1772     for (; ; --i) {
1773       if (traits_type::eq(*i, *s)
1774           && traits_type::compare(&*i, s, n) == 0) {
1775         return i - begin();
1776       }
1777       if (i == begin()) break;
1778     }
1779     return npos;
1780   }
1781
1782   size_type rfind(const value_type* s, size_type pos = npos) const {
1783     return rfind(s, pos, traits_type::length(s));
1784   }
1785
1786   size_type rfind(value_type c, size_type pos = npos) const {
1787     return rfind(&c, pos, 1);
1788   }
1789
1790   size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1791     return find_first_of(str.data(), pos, str.length());
1792   }
1793
1794   size_type find_first_of(const value_type* s,
1795                           size_type pos, size_type n) const {
1796     if (pos > length() || n == 0) return npos;
1797     const_iterator i(begin() + pos),
1798       finish(end());
1799     for (; i != finish; ++i) {
1800       if (traits_type::find(s, n, *i) != 0) {
1801         return i - begin();
1802       }
1803     }
1804     return npos;
1805   }
1806
1807   size_type find_first_of(const value_type* s, size_type pos = 0) const {
1808     return find_first_of(s, pos, traits_type::length(s));
1809   }
1810
1811   size_type find_first_of(value_type c, size_type pos = 0) const {
1812     return find_first_of(&c, pos, 1);
1813   }
1814
1815   size_type find_last_of (const basic_fbstring& str,
1816                           size_type pos = npos) const {
1817     return find_last_of(str.data(), pos, str.length());
1818   }
1819
1820   size_type find_last_of (const value_type* s, size_type pos,
1821                           size_type n) const {
1822     if (!empty() && n > 0) {
1823       pos = std::min(pos, length() - 1);
1824       const_iterator i(begin() + pos);
1825       for (;; --i) {
1826         if (traits_type::find(s, n, *i) != 0) {
1827           return i - begin();
1828         }
1829         if (i == begin()) break;
1830       }
1831     }
1832     return npos;
1833   }
1834
1835   size_type find_last_of (const value_type* s,
1836                           size_type pos = npos) const {
1837     return find_last_of(s, pos, traits_type::length(s));
1838   }
1839
1840   size_type find_last_of (value_type c, size_type pos = npos) const {
1841     return find_last_of(&c, pos, 1);
1842   }
1843
1844   size_type find_first_not_of(const basic_fbstring& str,
1845                               size_type pos = 0) const {
1846     return find_first_not_of(str.data(), pos, str.size());
1847   }
1848
1849   size_type find_first_not_of(const value_type* s, size_type pos,
1850                               size_type n) const {
1851     if (pos < length()) {
1852       const_iterator
1853         i(begin() + pos),
1854         finish(end());
1855       for (; i != finish; ++i) {
1856         if (traits_type::find(s, n, *i) == 0) {
1857           return i - begin();
1858         }
1859       }
1860     }
1861     return npos;
1862   }
1863
1864   size_type find_first_not_of(const value_type* s,
1865                               size_type pos = 0) const {
1866     return find_first_not_of(s, pos, traits_type::length(s));
1867   }
1868
1869   size_type find_first_not_of(value_type c, size_type pos = 0) const {
1870     return find_first_not_of(&c, pos, 1);
1871   }
1872
1873   size_type find_last_not_of(const basic_fbstring& str,
1874                              size_type pos = npos) const {
1875     return find_last_not_of(str.data(), pos, str.length());
1876   }
1877
1878   size_type find_last_not_of(const value_type* s, size_type pos,
1879                              size_type n) const {
1880     if (!this->empty()) {
1881       pos = std::min(pos, size() - 1);
1882       const_iterator i(begin() + pos);
1883       for (;; --i) {
1884         if (traits_type::find(s, n, *i) == 0) {
1885           return i - begin();
1886         }
1887         if (i == begin()) break;
1888       }
1889     }
1890     return npos;
1891   }
1892
1893   size_type find_last_not_of(const value_type* s,
1894                              size_type pos = npos) const {
1895     return find_last_not_of(s, pos, traits_type::length(s));
1896   }
1897
1898   size_type find_last_not_of (value_type c, size_type pos = npos) const {
1899     return find_last_not_of(&c, pos, 1);
1900   }
1901
1902   basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1903     enforce(pos <= size(), std::__throw_out_of_range, "");
1904     return basic_fbstring(data() + pos, std::min(n, size() - pos));
1905   }
1906
1907   int compare(const basic_fbstring& str) const {
1908     // FIX due to Goncalo N M de Carvalho July 18, 2005
1909     return compare(0, size(), str);
1910   }
1911
1912   int compare(size_type pos1, size_type n1,
1913               const basic_fbstring& str) const {
1914     return compare(pos1, n1, str.data(), str.size());
1915   }
1916
1917   int compare(size_type pos1, size_type n1,
1918               const value_type* s) const {
1919     return compare(pos1, n1, s, traits_type::length(s));
1920   }
1921
1922   int compare(size_type pos1, size_type n1,
1923               const value_type* s, size_type n2) const {
1924     enforce(pos1 <= size(), std::__throw_out_of_range, "");
1925     procrustes(n1, size() - pos1);
1926     // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1927     const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1928     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1929   }
1930
1931   int compare(size_type pos1, size_type n1,
1932               const basic_fbstring& str,
1933               size_type pos2, size_type n2) const {
1934     enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1935     return compare(pos1, n1, str.data() + pos2,
1936                    std::min(n2, str.size() - pos2));
1937   }
1938
1939   // Code from Jean-Francois Bastien (03/26/2007)
1940   int compare(const value_type* s) const {
1941     // Could forward to compare(0, size(), s, traits_type::length(s))
1942     // but that does two extra checks
1943     const size_type n1(size()), n2(traits_type::length(s));
1944     const int r = traits_type::compare(data(), s, std::min(n1, n2));
1945     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1946   }
1947
1948 private:
1949   // Data
1950   Storage store_;
1951 };
1952
1953 // non-member functions
1954 // C++11 21.4.8.1/2
1955 template <typename E, class T, class A, class S>
1956 inline
1957 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1958                                      const basic_fbstring<E, T, A, S>& rhs) {
1959
1960   basic_fbstring<E, T, A, S> result;
1961   result.reserve(lhs.size() + rhs.size());
1962   result.append(lhs).append(rhs);
1963   return std::move(result);
1964 }
1965
1966 // C++11 21.4.8.1/2
1967 template <typename E, class T, class A, class S>
1968 inline
1969 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1970                                      const basic_fbstring<E, T, A, S>& rhs) {
1971   return std::move(lhs.append(rhs));
1972 }
1973
1974 // C++11 21.4.8.1/3
1975 template <typename E, class T, class A, class S>
1976 inline
1977 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1978                                      basic_fbstring<E, T, A, S>&& rhs) {
1979   if (rhs.capacity() >= lhs.size() + rhs.size()) {
1980     // Good, at least we don't need to reallocate
1981     return std::move(rhs.insert(0, lhs));
1982   }
1983   // Meh, no go. Forward to operator+(const&, const&).
1984   auto const& rhsC = rhs;
1985   return lhs + rhsC;
1986 }
1987
1988 // C++11 21.4.8.1/4
1989 template <typename E, class T, class A, class S>
1990 inline
1991 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1992                                      basic_fbstring<E, T, A, S>&& rhs) {
1993   return std::move(lhs.append(rhs));
1994 }
1995
1996 template <typename E, class T, class A, class S>
1997 inline
1998 basic_fbstring<E, T, A, S> operator+(
1999   const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2000   const basic_fbstring<E, T, A, S>& rhs) {
2001   //
2002   basic_fbstring<E, T, A, S> result;
2003   const typename basic_fbstring<E, T, A, S>::size_type len =
2004     basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2005   result.reserve(len + rhs.size());
2006   result.append(lhs, len).append(rhs);
2007   return result;
2008 }
2009
2010 template <typename E, class T, class A, class S>
2011 inline
2012 basic_fbstring<E, T, A, S> operator+(
2013   typename basic_fbstring<E, T, A, S>::value_type lhs,
2014   const basic_fbstring<E, T, A, S>& rhs) {
2015
2016   basic_fbstring<E, T, A, S> result;
2017   result.reserve(1 + rhs.size());
2018   result.push_back(lhs);
2019   result.append(rhs);
2020   return result;
2021 }
2022
2023 template <typename E, class T, class A, class S>
2024 inline
2025 basic_fbstring<E, T, A, S> operator+(
2026   const basic_fbstring<E, T, A, S>& lhs,
2027   const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2028
2029   typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2030   typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2031
2032   basic_fbstring<E, T, A, S> result;
2033   const size_type len = traits_type::length(rhs);
2034   result.reserve(lhs.size() + len);
2035   result.append(lhs).append(rhs, len);
2036   return result;
2037 }
2038
2039 template <typename E, class T, class A, class S>
2040 inline
2041 basic_fbstring<E, T, A, S> operator+(
2042   const basic_fbstring<E, T, A, S>& lhs,
2043   typename basic_fbstring<E, T, A, S>::value_type rhs) {
2044
2045   basic_fbstring<E, T, A, S> result;
2046   result.reserve(lhs.size() + 1);
2047   result.append(lhs);
2048   result.push_back(rhs);
2049   return result;
2050 }
2051
2052 template <typename E, class T, class A, class S>
2053 inline
2054 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2055                 const basic_fbstring<E, T, A, S>& rhs) {
2056   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2057
2058 template <typename E, class T, class A, class S>
2059 inline
2060 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2061                 const basic_fbstring<E, T, A, S>& rhs) {
2062   return rhs == lhs; }
2063
2064 template <typename E, class T, class A, class S>
2065 inline
2066 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2067                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2068   return lhs.compare(rhs) == 0; }
2069
2070 template <typename E, class T, class A, class S>
2071 inline
2072 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2073                 const basic_fbstring<E, T, A, S>& rhs) {
2074   return !(lhs == rhs); }
2075
2076 template <typename E, class T, class A, class S>
2077 inline
2078 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2079                 const basic_fbstring<E, T, A, S>& rhs) {
2080   return !(lhs == rhs); }
2081
2082 template <typename E, class T, class A, class S>
2083 inline
2084 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2085                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2086   return !(lhs == rhs); }
2087
2088 template <typename E, class T, class A, class S>
2089 inline
2090 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2091                const basic_fbstring<E, T, A, S>& rhs) {
2092   return lhs.compare(rhs) < 0; }
2093
2094 template <typename E, class T, class A, class S>
2095 inline
2096 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2097                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2098   return lhs.compare(rhs) < 0; }
2099
2100 template <typename E, class T, class A, class S>
2101 inline
2102 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2103                const basic_fbstring<E, T, A, S>& rhs) {
2104   return rhs.compare(lhs) > 0; }
2105
2106 template <typename E, class T, class A, class S>
2107 inline
2108 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2109                const basic_fbstring<E, T, A, S>& rhs) {
2110   return rhs < lhs; }
2111
2112 template <typename E, class T, class A, class S>
2113 inline
2114 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2115                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2116   return rhs < lhs; }
2117
2118 template <typename E, class T, class A, class S>
2119 inline
2120 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2121                const basic_fbstring<E, T, A, S>& rhs) {
2122   return rhs < lhs; }
2123
2124 template <typename E, class T, class A, class S>
2125 inline
2126 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2127                 const basic_fbstring<E, T, A, S>& rhs) {
2128   return !(rhs < lhs); }
2129
2130 template <typename E, class T, class A, class S>
2131 inline
2132 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2133                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2134   return !(rhs < lhs); }
2135
2136 template <typename E, class T, class A, class S>
2137 inline
2138 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2139                 const basic_fbstring<E, T, A, S>& rhs) {
2140   return !(rhs < lhs); }
2141
2142 template <typename E, class T, class A, class S>
2143 inline
2144 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2145                 const basic_fbstring<E, T, A, S>& rhs) {
2146   return !(lhs < rhs); }
2147
2148 template <typename E, class T, class A, class S>
2149 inline
2150 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2151                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2152   return !(lhs < rhs); }
2153
2154 template <typename E, class T, class A, class S>
2155 inline
2156 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2157                 const basic_fbstring<E, T, A, S>& rhs) {
2158  return !(lhs < rhs);
2159 }
2160
2161 // subclause 21.3.7.8:
2162 template <typename E, class T, class A, class S>
2163 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2164   lhs.swap(rhs);
2165 }
2166
2167 // TODO: make this faster.
2168 template <typename E, class T, class A, class S>
2169 inline
2170 std::basic_istream<
2171   typename basic_fbstring<E, T, A, S>::value_type,
2172   typename basic_fbstring<E, T, A, S>::traits_type>&
2173   operator>>(
2174     std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2175     typename basic_fbstring<E, T, A, S>::traits_type>& is,
2176     basic_fbstring<E, T, A, S>& str) {
2177   typename std::basic_istream<E, T>::sentry sentry(is);
2178   typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2179                              typename basic_fbstring<E, T, A, S>::traits_type>
2180                         __istream_type;
2181   typedef typename __istream_type::ios_base __ios_base;
2182   size_t extracted = 0;
2183   auto err = __ios_base::goodbit;
2184   if (sentry) {
2185     auto n = is.width();
2186     if (n == 0) {
2187       n = str.max_size();
2188     }
2189     str.erase();
2190     auto got = is.rdbuf()->sgetc();
2191     for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2192       // Whew. We get to store this guy
2193       str.push_back(got);
2194       got = is.rdbuf()->snextc();
2195     }
2196     if (got == T::eof()) {
2197       err |= __ios_base::eofbit;
2198       is.width(0);
2199     }
2200   }
2201   if (!extracted) {
2202     err |= __ios_base::failbit;
2203   }
2204   if (err) {
2205     is.setstate(err);
2206   }
2207   return is;
2208 }
2209
2210 template <typename E, class T, class A, class S>
2211 inline
2212 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2213                    typename basic_fbstring<E, T, A, S>::traits_type>&
2214 operator<<(
2215   std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2216   typename basic_fbstring<E, T, A, S>::traits_type>& os,
2217     const basic_fbstring<E, T, A, S>& str) {
2218   os.write(str.data(), str.size());
2219   return os;
2220 }
2221
2222 #ifndef _LIBSTDCXX_FBSTRING
2223
2224 template <typename E, class T, class A, class S>
2225 inline
2226 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2227                    typename basic_fbstring<E, T, A, S>::traits_type>&
2228 getline(
2229   std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2230   typename basic_fbstring<E, T, A, S>::traits_type>& is,
2231     basic_fbstring<E, T, A, S>& str,
2232   typename basic_fbstring<E, T, A, S>::value_type delim) {
2233   // Use the nonstandard getdelim()
2234   char * buf = NULL;
2235   size_t size = 0;
2236   for (;;) {
2237     // This looks quadratic but it really depends on realloc
2238     auto const newSize = size + 128;
2239     buf = static_cast<char*>(checkedRealloc(buf, newSize));
2240     is.getline(buf + size, newSize - size, delim);
2241     if (is.bad() || is.eof() || !is.fail()) {
2242       // done by either failure, end of file, or normal read
2243       size += std::strlen(buf + size);
2244       break;
2245     }
2246     // Here we have failed due to too short a buffer
2247     // Minus one to discount the terminating '\0'
2248     size = newSize - 1;
2249     assert(buf[size] == 0);
2250     // Clear the error so we can continue reading
2251     is.clear();
2252   }
2253   basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2254                                     AcquireMallocatedString());
2255   result.swap(str);
2256   return is;
2257 }
2258
2259 template <typename E, class T, class A, class S>
2260 inline
2261 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2262                    typename basic_fbstring<E, T, A, S>::traits_type>&
2263 getline(
2264   std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2265   typename basic_fbstring<E, T, A, S>::traits_type>& is,
2266   basic_fbstring<E, T, A, S>& str) {
2267   // Just forward to the version with a delimiter
2268   return getline(is, str, '\n');
2269 }
2270
2271 #endif
2272
2273 template <typename E1, class T, class A, class S>
2274 const typename basic_fbstring<E1, T, A, S>::size_type
2275 basic_fbstring<E1, T, A, S>::npos =
2276               static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2277
2278 #ifndef _LIBSTDCXX_FBSTRING
2279 // basic_string compatibility routines
2280
2281 template <typename E, class T, class A, class S>
2282 inline
2283 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2284                 const std::string& rhs) {
2285   return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2286 }
2287
2288 template <typename E, class T, class A, class S>
2289 inline
2290 bool operator==(const std::string& lhs,
2291                 const basic_fbstring<E, T, A, S>& rhs) {
2292   return rhs == lhs;
2293 }
2294
2295 template <typename E, class T, class A, class S>
2296 inline
2297 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2298                 const std::string& rhs) {
2299   return !(lhs == rhs);
2300 }
2301
2302 template <typename E, class T, class A, class S>
2303 inline
2304 bool operator!=(const std::string& lhs,
2305                 const basic_fbstring<E, T, A, S>& rhs) {
2306   return !(lhs == rhs);
2307 }
2308
2309 #if !defined(_LIBSTDCXX_FBSTRING)
2310 typedef basic_fbstring<char> fbstring;
2311 #endif
2312
2313 // fbstring is relocatable
2314 template <class T, class R, class A, class S>
2315 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2316
2317 #else
2318 _GLIBCXX_END_NAMESPACE_VERSION
2319 #endif
2320
2321 } // namespace folly
2322
2323 #ifndef _LIBSTDCXX_FBSTRING
2324
2325 namespace std {
2326 template <>
2327 struct hash< ::folly::fbstring> {
2328   size_t operator()(const ::folly::fbstring& s) const {
2329     return ::folly::hash::fnv32_buf(s.data(), s.size());
2330   }
2331 };
2332 }
2333
2334 #endif // _LIBSTDCXX_FBSTRING
2335
2336 #undef FBSTRING_LIKELY
2337 #undef FBSTRING_UNLIKELY
2338
2339 #endif // FOLLY_BASE_FBSTRING_H_