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     if (FBSTRING_UNLIKELY(&goner == this)) {
1074       // Compatibility with std::basic_string<>,
1075       // 21.4.2 [string.cons] / 23 requires self-move-assignment support.
1076       return *this;
1077     }
1078     // No need of this anymore
1079     this->~basic_fbstring();
1080     // Move the goner into this
1081     new(&store_) fbstring_core<E>(std::move(goner.store_));
1082     return *this;
1083   }
1084
1085 #ifndef _LIBSTDCXX_FBSTRING
1086   // Compatibility with std::string
1087   basic_fbstring & operator=(const std::string & rhs) {
1088     return assign(rhs.data(), rhs.size());
1089   }
1090
1091   // Compatibility with std::string
1092   std::string toStdString() const {
1093     return std::string(data(), size());
1094   }
1095 #else
1096   // A lot of code in fbcode still uses this method, so keep it here for now.
1097   const basic_fbstring& toStdString() const {
1098     return *this;
1099   }
1100 #endif
1101
1102   basic_fbstring& operator=(const value_type* s) {
1103     return assign(s);
1104   }
1105
1106   basic_fbstring& operator=(value_type c) {
1107     if (empty()) {
1108       store_.expand_noinit(1);
1109     } else if (store_.isShared()) {
1110       basic_fbstring(1, c).swap(*this);
1111       return *this;
1112     } else {
1113       store_.shrink(size() - 1);
1114     }
1115     *store_.mutable_data() = c;
1116     store_.writeTerminator();
1117     return *this;
1118   }
1119
1120   // 21.3.2 iterators:
1121   iterator begin() { return store_.mutable_data(); }
1122
1123   const_iterator begin() const { return store_.data(); }
1124
1125   iterator end() {
1126     return store_.mutable_data() + store_.size();
1127   }
1128
1129   const_iterator end() const {
1130     return store_.data() + store_.size();
1131   }
1132
1133   reverse_iterator rbegin() {
1134     return reverse_iterator(end());
1135   }
1136
1137   const_reverse_iterator rbegin() const {
1138     return const_reverse_iterator(end());
1139   }
1140
1141   reverse_iterator rend() {
1142     return reverse_iterator(begin());
1143   }
1144
1145   const_reverse_iterator rend() const {
1146     return const_reverse_iterator(begin());
1147   }
1148
1149   // Added by C++11
1150   // C++11 21.4.5, element access:
1151   const value_type& front() const { return *begin(); }
1152   const value_type& back() const {
1153     assert(!empty());
1154     // Should be begin()[size() - 1], but that branches twice
1155     return *(end() - 1);
1156   }
1157   value_type& front() { return *begin(); }
1158   value_type& back() {
1159     assert(!empty());
1160     // Should be begin()[size() - 1], but that branches twice
1161     return *(end() - 1);
1162   }
1163   void pop_back() {
1164     assert(!empty());
1165     store_.shrink(1);
1166   }
1167
1168   // 21.3.3 capacity:
1169   size_type size() const { return store_.size(); }
1170
1171   size_type length() const { return size(); }
1172
1173   size_type max_size() const {
1174     return std::numeric_limits<size_type>::max();
1175   }
1176
1177   void resize(const size_type n, const value_type c = value_type()) {
1178     auto size = this->size();
1179     if (n <= size) {
1180       store_.shrink(size - n);
1181     } else {
1182       // Do this in two steps to minimize slack memory copied (see
1183       // smartRealloc).
1184       auto const capacity = this->capacity();
1185       assert(capacity >= size);
1186       if (size < capacity) {
1187         auto delta = std::min(n, capacity) - size;
1188         store_.expand_noinit(delta);
1189         fbstring_detail::pod_fill(begin() + size, end(), c);
1190         size += delta;
1191         if (size == n) {
1192           store_.writeTerminator();
1193           return;
1194         }
1195         assert(size < n);
1196       }
1197       auto const delta = n - size;
1198       store_.expand_noinit(delta);
1199       fbstring_detail::pod_fill(end() - delta, end(), c);
1200       store_.writeTerminator();
1201     }
1202     assert(this->size() == n);
1203   }
1204
1205   size_type capacity() const { return store_.capacity(); }
1206
1207   void reserve(size_type res_arg = 0) {
1208     enforce(res_arg <= max_size(), std::__throw_length_error, "");
1209     store_.reserve(res_arg);
1210   }
1211
1212   void clear() { resize(0); }
1213
1214   bool empty() const { return size() == 0; }
1215
1216   // 21.3.4 element access:
1217   const_reference operator[](size_type pos) const {
1218     return *(c_str() + pos);
1219   }
1220
1221   reference operator[](size_type pos) {
1222     if (pos == size()) {
1223       // Just call c_str() to make sure '\0' is present
1224       c_str();
1225     }
1226     return *(begin() + pos);
1227   }
1228
1229   const_reference at(size_type n) const {
1230     enforce(n <= size(), std::__throw_out_of_range, "");
1231     return (*this)[n];
1232   }
1233
1234   reference at(size_type n) {
1235     enforce(n < size(), std::__throw_out_of_range, "");
1236     return (*this)[n];
1237   }
1238
1239   // 21.3.5 modifiers:
1240   basic_fbstring& operator+=(const basic_fbstring& str) {
1241     return append(str);
1242   }
1243
1244   basic_fbstring& operator+=(const value_type* s) {
1245     return append(s);
1246   }
1247
1248   basic_fbstring& operator+=(const value_type c) {
1249     push_back(c);
1250     return *this;
1251   }
1252
1253   basic_fbstring& append(const basic_fbstring& str) {
1254 #ifndef NDEBUG
1255     auto desiredSize = size() + str.size();
1256 #endif
1257     append(str.data(), str.size());
1258     assert(size() == desiredSize);
1259     return *this;
1260   }
1261
1262   basic_fbstring& append(const basic_fbstring& str, const size_type pos,
1263                          size_type n) {
1264     const size_type sz = str.size();
1265     enforce(pos <= sz, std::__throw_out_of_range, "");
1266     procrustes(n, sz - pos);
1267     return append(str.data() + pos, n);
1268   }
1269
1270   basic_fbstring& append(const value_type* s, size_type n) {
1271 #ifndef NDEBUG
1272     Invariant checker(*this);
1273     (void) checker;
1274 #endif
1275     if (FBSTRING_UNLIKELY(!n)) {
1276       // Unlikely but must be done
1277       return *this;
1278     }
1279     auto const oldSize = size();
1280     auto const oldData = data();
1281     // Check for aliasing (rare). We could use "<=" here but in theory
1282     // those do not work for pointers unless the pointers point to
1283     // elements in the same array. For that reason we use
1284     // std::less_equal, which is guaranteed to offer a total order
1285     // over pointers. See discussion at http://goo.gl/Cy2ya for more
1286     // info.
1287     std::less_equal<const value_type*> le;
1288     if (FBSTRING_UNLIKELY(le(oldData, s) && !le(oldData + oldSize, s))) {
1289       assert(le(s + n, oldData + oldSize));
1290       const size_type offset = s - oldData;
1291       store_.reserve(oldSize + n);
1292       // Restore the source
1293       s = data() + offset;
1294     }
1295     // Warning! Repeated appends with short strings may actually incur
1296     // practically quadratic performance. Avoid that by pushing back
1297     // the first character (which ensures exponential growth) and then
1298     // appending the rest normally. Worst case the append may incur a
1299     // second allocation but that will be rare.
1300     push_back(*s++);
1301     --n;
1302     memcpy(store_.expand_noinit(n), s, n * sizeof(value_type));
1303     assert(size() == oldSize + n + 1);
1304     return *this;
1305   }
1306
1307   basic_fbstring& append(const value_type* s) {
1308     return append(s, traits_type::length(s));
1309   }
1310
1311   basic_fbstring& append(size_type n, value_type c) {
1312     resize(size() + n, c);
1313     return *this;
1314   }
1315
1316   template<class InputIterator>
1317   basic_fbstring& append(InputIterator first, InputIterator last) {
1318     insert(end(), first, last);
1319     return *this;
1320   }
1321
1322   void push_back(const value_type c) {             // primitive
1323     store_.push_back(c);
1324   }
1325
1326   basic_fbstring& assign(const basic_fbstring& str) {
1327     if (&str == this) return *this;
1328     return assign(str.data(), str.size());
1329   }
1330
1331   basic_fbstring& assign(const basic_fbstring& str, const size_type pos,
1332                          size_type n) {
1333     const size_type sz = str.size();
1334     enforce(pos <= sz, std::__throw_out_of_range, "");
1335     procrustes(n, sz - pos);
1336     return assign(str.data() + pos, n);
1337   }
1338
1339   basic_fbstring& assign(const value_type* s, const size_type n) {
1340     Invariant checker(*this);
1341     (void) checker;
1342     if (size() >= n) {
1343       std::copy(s, s + n, begin());
1344       resize(n);
1345       assert(size() == n);
1346     } else {
1347       const value_type *const s2 = s + size();
1348       std::copy(s, s2, begin());
1349       append(s2, n - size());
1350       assert(size() == n);
1351     }
1352     store_.writeTerminator();
1353     assert(size() == n);
1354     return *this;
1355   }
1356
1357   basic_fbstring& assign(const value_type* s) {
1358     return assign(s, traits_type::length(s));
1359   }
1360
1361   template <class ItOrLength, class ItOrChar>
1362   basic_fbstring& assign(ItOrLength first_or_n, ItOrChar last_or_c) {
1363     return replace(begin(), end(), first_or_n, last_or_c);
1364   }
1365
1366   basic_fbstring& insert(size_type pos1, const basic_fbstring& str) {
1367     return insert(pos1, str.data(), str.size());
1368   }
1369
1370   basic_fbstring& insert(size_type pos1, const basic_fbstring& str,
1371                          size_type pos2, size_type n) {
1372     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1373     procrustes(n, str.length() - pos2);
1374     return insert(pos1, str.data() + pos2, n);
1375   }
1376
1377   basic_fbstring& insert(size_type pos, const value_type* s, size_type n) {
1378     enforce(pos <= length(), std::__throw_out_of_range, "");
1379     insert(begin() + pos, s, s + n);
1380     return *this;
1381   }
1382
1383   basic_fbstring& insert(size_type pos, const value_type* s) {
1384     return insert(pos, s, traits_type::length(s));
1385   }
1386
1387   basic_fbstring& insert(size_type pos, size_type n, value_type c) {
1388     enforce(pos <= length(), std::__throw_out_of_range, "");
1389     insert(begin() + pos, n, c);
1390     return *this;
1391   }
1392
1393   iterator insert(const iterator p, const value_type c) {
1394     const size_type pos = p - begin();
1395     insert(p, 1, c);
1396     return begin() + pos;
1397   }
1398
1399 private:
1400   template <int i> class Selector {};
1401
1402   basic_fbstring& insertImplDiscr(iterator p,
1403                                   size_type n, value_type c, Selector<1>) {
1404     Invariant checker(*this);
1405     (void) checker;
1406     assert(p >= begin() && p <= end());
1407     if (capacity() - size() < n) {
1408       const size_type sz = p - begin();
1409       reserve(size() + n);
1410       p = begin() + sz;
1411     }
1412     const iterator oldEnd = end();
1413     if( n < size_type(oldEnd - p)) {
1414       append(oldEnd - n, oldEnd);
1415       //std::copy(
1416       //    reverse_iterator(oldEnd - n),
1417       //    reverse_iterator(p),
1418       //    reverse_iterator(oldEnd));
1419       fbstring_detail::pod_move(&*p, &*oldEnd - n, &*p + n);
1420       std::fill(p, p + n, c);
1421     } else {
1422       append(n - (end() - p), c);
1423       append(p, oldEnd);
1424       std::fill(p, oldEnd, c);
1425     }
1426     store_.writeTerminator();
1427     return *this;
1428   }
1429
1430   template<class InputIter>
1431   basic_fbstring& insertImplDiscr(iterator i,
1432                                   InputIter b, InputIter e, Selector<0>) {
1433     insertImpl(i, b, e,
1434                typename std::iterator_traits<InputIter>::iterator_category());
1435     return *this;
1436   }
1437
1438   template <class FwdIterator>
1439   void insertImpl(iterator i,
1440                   FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1441     Invariant checker(*this);
1442     (void) checker;
1443     const size_type pos = i - begin();
1444     const typename std::iterator_traits<FwdIterator>::difference_type n2 =
1445       std::distance(s1, s2);
1446     assert(n2 >= 0);
1447     using namespace fbstring_detail;
1448     assert(pos <= size());
1449
1450     const typename std::iterator_traits<FwdIterator>::difference_type maxn2 =
1451       capacity() - size();
1452     if (maxn2 < n2) {
1453       // realloc the string
1454       reserve(size() + n2);
1455       i = begin() + pos;
1456     }
1457     if (pos + n2 <= size()) {
1458       const iterator tailBegin = end() - n2;
1459       store_.expand_noinit(n2);
1460       fbstring_detail::pod_copy(tailBegin, tailBegin + n2, end() - n2);
1461       std::copy(reverse_iterator(tailBegin), reverse_iterator(i),
1462                 reverse_iterator(tailBegin + n2));
1463       std::copy(s1, s2, i);
1464     } else {
1465       FwdIterator t = s1;
1466       const size_type old_size = size();
1467       std::advance(t, old_size - pos);
1468       const size_t newElems = std::distance(t, s2);
1469       store_.expand_noinit(n2);
1470       std::copy(t, s2, begin() + old_size);
1471       fbstring_detail::pod_copy(data() + pos, data() + old_size,
1472                                  begin() + old_size + newElems);
1473       std::copy(s1, t, i);
1474     }
1475     store_.writeTerminator();
1476   }
1477
1478   template <class InputIterator>
1479   void insertImpl(iterator i,
1480                   InputIterator b, InputIterator e, std::input_iterator_tag) {
1481     basic_fbstring temp(begin(), i);
1482     for (; b != e; ++b) {
1483       temp.push_back(*b);
1484     }
1485     temp.append(i, end());
1486     swap(temp);
1487   }
1488
1489 public:
1490   template <class ItOrLength, class ItOrChar>
1491   void insert(iterator p, ItOrLength first_or_n, ItOrChar last_or_c) {
1492     Selector<std::numeric_limits<ItOrLength>::is_specialized> sel;
1493     insertImplDiscr(p, first_or_n, last_or_c, sel);
1494   }
1495
1496   basic_fbstring& erase(size_type pos = 0, size_type n = npos) {
1497     Invariant checker(*this);
1498     (void) checker;
1499     enforce(pos <= length(), std::__throw_out_of_range, "");
1500     procrustes(n, length() - pos);
1501     std::copy(begin() + pos + n, end(), begin() + pos);
1502     resize(length() - n);
1503     return *this;
1504   }
1505
1506   iterator erase(iterator position) {
1507     const size_type pos(position - begin());
1508     enforce(pos <= size(), std::__throw_out_of_range, "");
1509     erase(pos, 1);
1510     return begin() + pos;
1511   }
1512
1513   iterator erase(iterator first, iterator last) {
1514     const size_type pos(first - begin());
1515     erase(pos, last - first);
1516     return begin() + pos;
1517   }
1518
1519   // Replaces at most n1 chars of *this, starting with pos1 with the
1520   // content of str
1521   basic_fbstring& replace(size_type pos1, size_type n1,
1522                           const basic_fbstring& str) {
1523     return replace(pos1, n1, str.data(), str.size());
1524   }
1525
1526   // Replaces at most n1 chars of *this, starting with pos1,
1527   // with at most n2 chars of str starting with pos2
1528   basic_fbstring& replace(size_type pos1, size_type n1,
1529                           const basic_fbstring& str,
1530                           size_type pos2, size_type n2) {
1531     enforce(pos2 <= str.length(), std::__throw_out_of_range, "");
1532     return replace(pos1, n1, str.data() + pos2,
1533                    std::min(n2, str.size() - pos2));
1534   }
1535
1536   // Replaces at most n1 chars of *this, starting with pos, with chars from s
1537   basic_fbstring& replace(size_type pos, size_type n1, const value_type* s) {
1538     return replace(pos, n1, s, traits_type::length(s));
1539   }
1540
1541   // Replaces at most n1 chars of *this, starting with pos, with n2
1542   // occurrences of c
1543   //
1544   // consolidated with
1545   //
1546   // Replaces at most n1 chars of *this, starting with pos, with at
1547   // most n2 chars of str.  str must have at least n2 chars.
1548   template <class StrOrLength, class NumOrChar>
1549   basic_fbstring& replace(size_type pos, size_type n1,
1550                           StrOrLength s_or_n2, NumOrChar n_or_c) {
1551     Invariant checker(*this);
1552     (void) checker;
1553     enforce(pos <= size(), std::__throw_out_of_range, "");
1554     procrustes(n1, length() - pos);
1555     const iterator b = begin() + pos;
1556     return replace(b, b + n1, s_or_n2, n_or_c);
1557   }
1558
1559   basic_fbstring& replace(iterator i1, iterator i2, const basic_fbstring& str) {
1560     return replace(i1, i2, str.data(), str.length());
1561   }
1562
1563   basic_fbstring& replace(iterator i1, iterator i2, const value_type* s) {
1564     return replace(i1, i2, s, traits_type::length(s));
1565   }
1566
1567 private:
1568   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1569                                    const value_type* s, size_type n,
1570                                    Selector<2>) {
1571     assert(i1 <= i2);
1572     assert(begin() <= i1 && i1 <= end());
1573     assert(begin() <= i2 && i2 <= end());
1574     return replace(i1, i2, s, s + n);
1575   }
1576
1577   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1578                                    size_type n2, value_type c, Selector<1>) {
1579     const size_type n1 = i2 - i1;
1580     if (n1 > n2) {
1581       std::fill(i1, i1 + n2, c);
1582       erase(i1 + n2, i2);
1583     } else {
1584       std::fill(i1, i2, c);
1585       insert(i2, n2 - n1, c);
1586     }
1587     assert(isSane());
1588     return *this;
1589   }
1590
1591   template <class InputIter>
1592   basic_fbstring& replaceImplDiscr(iterator i1, iterator i2,
1593                                    InputIter b, InputIter e,
1594                                    Selector<0>) {
1595     replaceImpl(i1, i2, b, e,
1596                 typename std::iterator_traits<InputIter>::iterator_category());
1597     return *this;
1598   }
1599
1600 private:
1601   template <class FwdIterator, class P>
1602   bool replaceAliased(iterator i1, iterator i2,
1603                       FwdIterator s1, FwdIterator s2, P*) {
1604     return false;
1605   }
1606
1607   template <class FwdIterator>
1608   bool replaceAliased(iterator i1, iterator i2,
1609                       FwdIterator s1, FwdIterator s2, value_type*) {
1610     static const std::less_equal<const value_type*> le =
1611       std::less_equal<const value_type*>();
1612     const bool aliased = le(&*begin(), &*s1) && le(&*s1, &*end());
1613     if (!aliased) {
1614       return false;
1615     }
1616     // Aliased replace, copy to new string
1617     basic_fbstring temp;
1618     temp.reserve(size() - (i2 - i1) + std::distance(s1, s2));
1619     temp.append(begin(), i1).append(s1, s2).append(i2, end());
1620     swap(temp);
1621     return true;
1622   }
1623
1624 public:
1625   template <class FwdIterator>
1626   void replaceImpl(iterator i1, iterator i2,
1627                    FwdIterator s1, FwdIterator s2, std::forward_iterator_tag) {
1628     Invariant checker(*this);
1629     (void) checker;
1630
1631     // Handle aliased replace
1632     if (replaceAliased(i1, i2, s1, s2, &*s1)) {
1633       return;
1634     }
1635
1636     auto const n1 = i2 - i1;
1637     assert(n1 >= 0);
1638     auto const n2 = std::distance(s1, s2);
1639     assert(n2 >= 0);
1640
1641     if (n1 > n2) {
1642       // shrinks
1643       std::copy(s1, s2, i1);
1644       erase(i1 + n2, i2);
1645     } else {
1646       // grows
1647       fbstring_detail::copy_n(s1, n1, i1);
1648       std::advance(s1, n1);
1649       insert(i2, s1, s2);
1650     }
1651     assert(isSane());
1652   }
1653
1654   template <class InputIterator>
1655   void replaceImpl(iterator i1, iterator i2,
1656                    InputIterator b, InputIterator e, std::input_iterator_tag) {
1657     basic_fbstring temp(begin(), i1);
1658     temp.append(b, e).append(i2, end());
1659     swap(temp);
1660   }
1661
1662 public:
1663   template <class T1, class T2>
1664   basic_fbstring& replace(iterator i1, iterator i2,
1665                           T1 first_or_n_or_s, T2 last_or_c_or_n) {
1666     const bool
1667       num1 = std::numeric_limits<T1>::is_specialized,
1668       num2 = std::numeric_limits<T2>::is_specialized;
1669     return replaceImplDiscr(
1670       i1, i2, first_or_n_or_s, last_or_c_or_n,
1671       Selector<num1 ? (num2 ? 1 : -1) : (num2 ? 2 : 0)>());
1672   }
1673
1674   size_type copy(value_type* s, size_type n, size_type pos = 0) const {
1675     enforce(pos <= size(), std::__throw_out_of_range, "");
1676     procrustes(n, size() - pos);
1677
1678     fbstring_detail::pod_copy(
1679       data() + pos,
1680       data() + pos + n,
1681       s);
1682     return n;
1683   }
1684
1685   void swap(basic_fbstring& rhs) {
1686     store_.swap(rhs.store_);
1687   }
1688
1689   // 21.3.6 string operations:
1690   const value_type* c_str() const {
1691     return store_.c_str();
1692   }
1693
1694   const value_type* data() const { return c_str(); }
1695
1696   allocator_type get_allocator() const {
1697     return allocator_type();
1698   }
1699
1700   size_type find(const basic_fbstring& str, size_type pos = 0) const {
1701     return find(str.data(), pos, str.length());
1702   }
1703
1704   size_type find(const value_type* needle, const size_type pos,
1705                  const size_type nsize) const {
1706     if (!nsize) return pos;
1707     auto const size = this->size();
1708     if (nsize + pos > size) return npos;
1709     // Don't use std::search, use a Boyer-Moore-like trick by comparing
1710     // the last characters first
1711     auto const haystack = data();
1712     auto const nsize_1 = nsize - 1;
1713     auto const lastNeedle = needle[nsize_1];
1714
1715     // Boyer-Moore skip value for the last char in the needle. Zero is
1716     // not a valid value; skip will be computed the first time it's
1717     // needed.
1718     size_type skip = 0;
1719
1720     const E * i = haystack + pos;
1721     auto iEnd = haystack + size - nsize_1;
1722
1723     while (i < iEnd) {
1724       // Boyer-Moore: match the last element in the needle
1725       while (i[nsize_1] != lastNeedle) {
1726         if (++i == iEnd) {
1727           // not found
1728           return npos;
1729         }
1730       }
1731       // Here we know that the last char matches
1732       // Continue in pedestrian mode
1733       for (size_t j = 0; ; ) {
1734         assert(j < nsize);
1735         if (i[j] != needle[j]) {
1736           // Not found, we can skip
1737           // Compute the skip value lazily
1738           if (skip == 0) {
1739             skip = 1;
1740             while (skip <= nsize_1 && needle[nsize_1 - skip] != lastNeedle) {
1741               ++skip;
1742             }
1743           }
1744           i += skip;
1745           break;
1746         }
1747         // Check if done searching
1748         if (++j == nsize) {
1749           // Yay
1750           return i - haystack;
1751         }
1752       }
1753     }
1754     return npos;
1755   }
1756
1757   size_type find(const value_type* s, size_type pos = 0) const {
1758     return find(s, pos, traits_type::length(s));
1759   }
1760
1761   size_type find (value_type c, size_type pos = 0) const {
1762     return find(&c, pos, 1);
1763   }
1764
1765   size_type rfind(const basic_fbstring& str, size_type pos = npos) const {
1766     return rfind(str.data(), pos, str.length());
1767   }
1768
1769   size_type rfind(const value_type* s, size_type pos, size_type n) const {
1770     if (n > length()) return npos;
1771     pos = std::min(pos, length() - n);
1772     if (n == 0) return pos;
1773
1774     const_iterator i(begin() + pos);
1775     for (; ; --i) {
1776       if (traits_type::eq(*i, *s)
1777           && traits_type::compare(&*i, s, n) == 0) {
1778         return i - begin();
1779       }
1780       if (i == begin()) break;
1781     }
1782     return npos;
1783   }
1784
1785   size_type rfind(const value_type* s, size_type pos = npos) const {
1786     return rfind(s, pos, traits_type::length(s));
1787   }
1788
1789   size_type rfind(value_type c, size_type pos = npos) const {
1790     return rfind(&c, pos, 1);
1791   }
1792
1793   size_type find_first_of(const basic_fbstring& str, size_type pos = 0) const {
1794     return find_first_of(str.data(), pos, str.length());
1795   }
1796
1797   size_type find_first_of(const value_type* s,
1798                           size_type pos, size_type n) const {
1799     if (pos > length() || n == 0) return npos;
1800     const_iterator i(begin() + pos),
1801       finish(end());
1802     for (; i != finish; ++i) {
1803       if (traits_type::find(s, n, *i) != 0) {
1804         return i - begin();
1805       }
1806     }
1807     return npos;
1808   }
1809
1810   size_type find_first_of(const value_type* s, size_type pos = 0) const {
1811     return find_first_of(s, pos, traits_type::length(s));
1812   }
1813
1814   size_type find_first_of(value_type c, size_type pos = 0) const {
1815     return find_first_of(&c, pos, 1);
1816   }
1817
1818   size_type find_last_of (const basic_fbstring& str,
1819                           size_type pos = npos) const {
1820     return find_last_of(str.data(), pos, str.length());
1821   }
1822
1823   size_type find_last_of (const value_type* s, size_type pos,
1824                           size_type n) const {
1825     if (!empty() && n > 0) {
1826       pos = std::min(pos, length() - 1);
1827       const_iterator i(begin() + pos);
1828       for (;; --i) {
1829         if (traits_type::find(s, n, *i) != 0) {
1830           return i - begin();
1831         }
1832         if (i == begin()) break;
1833       }
1834     }
1835     return npos;
1836   }
1837
1838   size_type find_last_of (const value_type* s,
1839                           size_type pos = npos) const {
1840     return find_last_of(s, pos, traits_type::length(s));
1841   }
1842
1843   size_type find_last_of (value_type c, size_type pos = npos) const {
1844     return find_last_of(&c, pos, 1);
1845   }
1846
1847   size_type find_first_not_of(const basic_fbstring& str,
1848                               size_type pos = 0) const {
1849     return find_first_not_of(str.data(), pos, str.size());
1850   }
1851
1852   size_type find_first_not_of(const value_type* s, size_type pos,
1853                               size_type n) const {
1854     if (pos < length()) {
1855       const_iterator
1856         i(begin() + pos),
1857         finish(end());
1858       for (; i != finish; ++i) {
1859         if (traits_type::find(s, n, *i) == 0) {
1860           return i - begin();
1861         }
1862       }
1863     }
1864     return npos;
1865   }
1866
1867   size_type find_first_not_of(const value_type* s,
1868                               size_type pos = 0) const {
1869     return find_first_not_of(s, pos, traits_type::length(s));
1870   }
1871
1872   size_type find_first_not_of(value_type c, size_type pos = 0) const {
1873     return find_first_not_of(&c, pos, 1);
1874   }
1875
1876   size_type find_last_not_of(const basic_fbstring& str,
1877                              size_type pos = npos) const {
1878     return find_last_not_of(str.data(), pos, str.length());
1879   }
1880
1881   size_type find_last_not_of(const value_type* s, size_type pos,
1882                              size_type n) const {
1883     if (!this->empty()) {
1884       pos = std::min(pos, size() - 1);
1885       const_iterator i(begin() + pos);
1886       for (;; --i) {
1887         if (traits_type::find(s, n, *i) == 0) {
1888           return i - begin();
1889         }
1890         if (i == begin()) break;
1891       }
1892     }
1893     return npos;
1894   }
1895
1896   size_type find_last_not_of(const value_type* s,
1897                              size_type pos = npos) const {
1898     return find_last_not_of(s, pos, traits_type::length(s));
1899   }
1900
1901   size_type find_last_not_of (value_type c, size_type pos = npos) const {
1902     return find_last_not_of(&c, pos, 1);
1903   }
1904
1905   basic_fbstring substr(size_type pos = 0, size_type n = npos) const {
1906     enforce(pos <= size(), std::__throw_out_of_range, "");
1907     return basic_fbstring(data() + pos, std::min(n, size() - pos));
1908   }
1909
1910   int compare(const basic_fbstring& str) const {
1911     // FIX due to Goncalo N M de Carvalho July 18, 2005
1912     return compare(0, size(), str);
1913   }
1914
1915   int compare(size_type pos1, size_type n1,
1916               const basic_fbstring& str) const {
1917     return compare(pos1, n1, str.data(), str.size());
1918   }
1919
1920   int compare(size_type pos1, size_type n1,
1921               const value_type* s) const {
1922     return compare(pos1, n1, s, traits_type::length(s));
1923   }
1924
1925   int compare(size_type pos1, size_type n1,
1926               const value_type* s, size_type n2) const {
1927     enforce(pos1 <= size(), std::__throw_out_of_range, "");
1928     procrustes(n1, size() - pos1);
1929     // The line below fixed by Jean-Francois Bastien, 04-23-2007. Thanks!
1930     const int r = traits_type::compare(pos1 + data(), s, std::min(n1, n2));
1931     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1932   }
1933
1934   int compare(size_type pos1, size_type n1,
1935               const basic_fbstring& str,
1936               size_type pos2, size_type n2) const {
1937     enforce(pos2 <= str.size(), std::__throw_out_of_range, "");
1938     return compare(pos1, n1, str.data() + pos2,
1939                    std::min(n2, str.size() - pos2));
1940   }
1941
1942   // Code from Jean-Francois Bastien (03/26/2007)
1943   int compare(const value_type* s) const {
1944     // Could forward to compare(0, size(), s, traits_type::length(s))
1945     // but that does two extra checks
1946     const size_type n1(size()), n2(traits_type::length(s));
1947     const int r = traits_type::compare(data(), s, std::min(n1, n2));
1948     return r != 0 ? r : n1 > n2 ? 1 : n1 < n2 ? -1 : 0;
1949   }
1950
1951 private:
1952   // Data
1953   Storage store_;
1954 };
1955
1956 // non-member functions
1957 // C++11 21.4.8.1/2
1958 template <typename E, class T, class A, class S>
1959 inline
1960 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1961                                      const basic_fbstring<E, T, A, S>& rhs) {
1962
1963   basic_fbstring<E, T, A, S> result;
1964   result.reserve(lhs.size() + rhs.size());
1965   result.append(lhs).append(rhs);
1966   return std::move(result);
1967 }
1968
1969 // C++11 21.4.8.1/2
1970 template <typename E, class T, class A, class S>
1971 inline
1972 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1973                                      const basic_fbstring<E, T, A, S>& rhs) {
1974   return std::move(lhs.append(rhs));
1975 }
1976
1977 // C++11 21.4.8.1/3
1978 template <typename E, class T, class A, class S>
1979 inline
1980 basic_fbstring<E, T, A, S> operator+(const basic_fbstring<E, T, A, S>& lhs,
1981                                      basic_fbstring<E, T, A, S>&& rhs) {
1982   if (rhs.capacity() >= lhs.size() + rhs.size()) {
1983     // Good, at least we don't need to reallocate
1984     return std::move(rhs.insert(0, lhs));
1985   }
1986   // Meh, no go. Forward to operator+(const&, const&).
1987   auto const& rhsC = rhs;
1988   return lhs + rhsC;
1989 }
1990
1991 // C++11 21.4.8.1/4
1992 template <typename E, class T, class A, class S>
1993 inline
1994 basic_fbstring<E, T, A, S> operator+(basic_fbstring<E, T, A, S>&& lhs,
1995                                      basic_fbstring<E, T, A, S>&& rhs) {
1996   return std::move(lhs.append(rhs));
1997 }
1998
1999 template <typename E, class T, class A, class S>
2000 inline
2001 basic_fbstring<E, T, A, S> operator+(
2002   const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2003   const basic_fbstring<E, T, A, S>& rhs) {
2004   //
2005   basic_fbstring<E, T, A, S> result;
2006   const typename basic_fbstring<E, T, A, S>::size_type len =
2007     basic_fbstring<E, T, A, S>::traits_type::length(lhs);
2008   result.reserve(len + rhs.size());
2009   result.append(lhs, len).append(rhs);
2010   return result;
2011 }
2012
2013 template <typename E, class T, class A, class S>
2014 inline
2015 basic_fbstring<E, T, A, S> operator+(
2016   typename basic_fbstring<E, T, A, S>::value_type lhs,
2017   const basic_fbstring<E, T, A, S>& rhs) {
2018
2019   basic_fbstring<E, T, A, S> result;
2020   result.reserve(1 + rhs.size());
2021   result.push_back(lhs);
2022   result.append(rhs);
2023   return result;
2024 }
2025
2026 template <typename E, class T, class A, class S>
2027 inline
2028 basic_fbstring<E, T, A, S> operator+(
2029   const basic_fbstring<E, T, A, S>& lhs,
2030   const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2031
2032   typedef typename basic_fbstring<E, T, A, S>::size_type size_type;
2033   typedef typename basic_fbstring<E, T, A, S>::traits_type traits_type;
2034
2035   basic_fbstring<E, T, A, S> result;
2036   const size_type len = traits_type::length(rhs);
2037   result.reserve(lhs.size() + len);
2038   result.append(lhs).append(rhs, len);
2039   return result;
2040 }
2041
2042 template <typename E, class T, class A, class S>
2043 inline
2044 basic_fbstring<E, T, A, S> operator+(
2045   const basic_fbstring<E, T, A, S>& lhs,
2046   typename basic_fbstring<E, T, A, S>::value_type rhs) {
2047
2048   basic_fbstring<E, T, A, S> result;
2049   result.reserve(lhs.size() + 1);
2050   result.append(lhs);
2051   result.push_back(rhs);
2052   return result;
2053 }
2054
2055 template <typename E, class T, class A, class S>
2056 inline
2057 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2058                 const basic_fbstring<E, T, A, S>& rhs) {
2059   return lhs.size() == rhs.size() && lhs.compare(rhs) == 0; }
2060
2061 template <typename E, class T, class A, class S>
2062 inline
2063 bool operator==(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2064                 const basic_fbstring<E, T, A, S>& rhs) {
2065   return rhs == lhs; }
2066
2067 template <typename E, class T, class A, class S>
2068 inline
2069 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2070                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2071   return lhs.compare(rhs) == 0; }
2072
2073 template <typename E, class T, class A, class S>
2074 inline
2075 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2076                 const basic_fbstring<E, T, A, S>& rhs) {
2077   return !(lhs == rhs); }
2078
2079 template <typename E, class T, class A, class S>
2080 inline
2081 bool operator!=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2082                 const basic_fbstring<E, T, A, S>& rhs) {
2083   return !(lhs == rhs); }
2084
2085 template <typename E, class T, class A, class S>
2086 inline
2087 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2088                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2089   return !(lhs == rhs); }
2090
2091 template <typename E, class T, class A, class S>
2092 inline
2093 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2094                const basic_fbstring<E, T, A, S>& rhs) {
2095   return lhs.compare(rhs) < 0; }
2096
2097 template <typename E, class T, class A, class S>
2098 inline
2099 bool operator<(const basic_fbstring<E, T, A, S>& lhs,
2100                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2101   return lhs.compare(rhs) < 0; }
2102
2103 template <typename E, class T, class A, class S>
2104 inline
2105 bool operator<(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2106                const basic_fbstring<E, T, A, S>& rhs) {
2107   return rhs.compare(lhs) > 0; }
2108
2109 template <typename E, class T, class A, class S>
2110 inline
2111 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2112                const basic_fbstring<E, T, A, S>& rhs) {
2113   return rhs < lhs; }
2114
2115 template <typename E, class T, class A, class S>
2116 inline
2117 bool operator>(const basic_fbstring<E, T, A, S>& lhs,
2118                const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2119   return rhs < lhs; }
2120
2121 template <typename E, class T, class A, class S>
2122 inline
2123 bool operator>(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2124                const basic_fbstring<E, T, A, S>& rhs) {
2125   return rhs < lhs; }
2126
2127 template <typename E, class T, class A, class S>
2128 inline
2129 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2130                 const basic_fbstring<E, T, A, S>& rhs) {
2131   return !(rhs < lhs); }
2132
2133 template <typename E, class T, class A, class S>
2134 inline
2135 bool operator<=(const basic_fbstring<E, T, A, S>& lhs,
2136                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2137   return !(rhs < lhs); }
2138
2139 template <typename E, class T, class A, class S>
2140 inline
2141 bool operator<=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2142                 const basic_fbstring<E, T, A, S>& rhs) {
2143   return !(rhs < lhs); }
2144
2145 template <typename E, class T, class A, class S>
2146 inline
2147 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2148                 const basic_fbstring<E, T, A, S>& rhs) {
2149   return !(lhs < rhs); }
2150
2151 template <typename E, class T, class A, class S>
2152 inline
2153 bool operator>=(const basic_fbstring<E, T, A, S>& lhs,
2154                 const typename basic_fbstring<E, T, A, S>::value_type* rhs) {
2155   return !(lhs < rhs); }
2156
2157 template <typename E, class T, class A, class S>
2158 inline
2159 bool operator>=(const typename basic_fbstring<E, T, A, S>::value_type* lhs,
2160                 const basic_fbstring<E, T, A, S>& rhs) {
2161  return !(lhs < rhs);
2162 }
2163
2164 // subclause 21.3.7.8:
2165 template <typename E, class T, class A, class S>
2166 void swap(basic_fbstring<E, T, A, S>& lhs, basic_fbstring<E, T, A, S>& rhs) {
2167   lhs.swap(rhs);
2168 }
2169
2170 // TODO: make this faster.
2171 template <typename E, class T, class A, class S>
2172 inline
2173 std::basic_istream<
2174   typename basic_fbstring<E, T, A, S>::value_type,
2175   typename basic_fbstring<E, T, A, S>::traits_type>&
2176   operator>>(
2177     std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2178     typename basic_fbstring<E, T, A, S>::traits_type>& is,
2179     basic_fbstring<E, T, A, S>& str) {
2180   typename std::basic_istream<E, T>::sentry sentry(is);
2181   typedef std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2182                              typename basic_fbstring<E, T, A, S>::traits_type>
2183                         __istream_type;
2184   typedef typename __istream_type::ios_base __ios_base;
2185   size_t extracted = 0;
2186   auto err = __ios_base::goodbit;
2187   if (sentry) {
2188     auto n = is.width();
2189     if (n == 0) {
2190       n = str.max_size();
2191     }
2192     str.erase();
2193     auto got = is.rdbuf()->sgetc();
2194     for (; extracted != n && got != T::eof() && !isspace(got); ++extracted) {
2195       // Whew. We get to store this guy
2196       str.push_back(got);
2197       got = is.rdbuf()->snextc();
2198     }
2199     if (got == T::eof()) {
2200       err |= __ios_base::eofbit;
2201       is.width(0);
2202     }
2203   }
2204   if (!extracted) {
2205     err |= __ios_base::failbit;
2206   }
2207   if (err) {
2208     is.setstate(err);
2209   }
2210   return is;
2211 }
2212
2213 template <typename E, class T, class A, class S>
2214 inline
2215 std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2216                    typename basic_fbstring<E, T, A, S>::traits_type>&
2217 operator<<(
2218   std::basic_ostream<typename basic_fbstring<E, T, A, S>::value_type,
2219   typename basic_fbstring<E, T, A, S>::traits_type>& os,
2220     const basic_fbstring<E, T, A, S>& str) {
2221   os.write(str.data(), str.size());
2222   return os;
2223 }
2224
2225 #ifndef _LIBSTDCXX_FBSTRING
2226
2227 template <typename E, class T, class A, class S>
2228 inline
2229 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2230                    typename basic_fbstring<E, T, A, S>::traits_type>&
2231 getline(
2232   std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2233   typename basic_fbstring<E, T, A, S>::traits_type>& is,
2234     basic_fbstring<E, T, A, S>& str,
2235   typename basic_fbstring<E, T, A, S>::value_type delim) {
2236   // Use the nonstandard getdelim()
2237   char * buf = NULL;
2238   size_t size = 0;
2239   for (;;) {
2240     // This looks quadratic but it really depends on realloc
2241     auto const newSize = size + 128;
2242     buf = static_cast<char*>(checkedRealloc(buf, newSize));
2243     is.getline(buf + size, newSize - size, delim);
2244     if (is.bad() || is.eof() || !is.fail()) {
2245       // done by either failure, end of file, or normal read
2246       size += std::strlen(buf + size);
2247       break;
2248     }
2249     // Here we have failed due to too short a buffer
2250     // Minus one to discount the terminating '\0'
2251     size = newSize - 1;
2252     assert(buf[size] == 0);
2253     // Clear the error so we can continue reading
2254     is.clear();
2255   }
2256   basic_fbstring<E, T, A, S> result(buf, size, size + 1,
2257                                     AcquireMallocatedString());
2258   result.swap(str);
2259   return is;
2260 }
2261
2262 template <typename E, class T, class A, class S>
2263 inline
2264 std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2265                    typename basic_fbstring<E, T, A, S>::traits_type>&
2266 getline(
2267   std::basic_istream<typename basic_fbstring<E, T, A, S>::value_type,
2268   typename basic_fbstring<E, T, A, S>::traits_type>& is,
2269   basic_fbstring<E, T, A, S>& str) {
2270   // Just forward to the version with a delimiter
2271   return getline(is, str, '\n');
2272 }
2273
2274 #endif
2275
2276 template <typename E1, class T, class A, class S>
2277 const typename basic_fbstring<E1, T, A, S>::size_type
2278 basic_fbstring<E1, T, A, S>::npos =
2279               static_cast<typename basic_fbstring<E1, T, A, S>::size_type>(-1);
2280
2281 #ifndef _LIBSTDCXX_FBSTRING
2282 // basic_string compatibility routines
2283
2284 template <typename E, class T, class A, class S>
2285 inline
2286 bool operator==(const basic_fbstring<E, T, A, S>& lhs,
2287                 const std::string& rhs) {
2288   return lhs.compare(0, lhs.size(), rhs.data(), rhs.size()) == 0;
2289 }
2290
2291 template <typename E, class T, class A, class S>
2292 inline
2293 bool operator==(const std::string& lhs,
2294                 const basic_fbstring<E, T, A, S>& rhs) {
2295   return rhs == lhs;
2296 }
2297
2298 template <typename E, class T, class A, class S>
2299 inline
2300 bool operator!=(const basic_fbstring<E, T, A, S>& lhs,
2301                 const std::string& rhs) {
2302   return !(lhs == rhs);
2303 }
2304
2305 template <typename E, class T, class A, class S>
2306 inline
2307 bool operator!=(const std::string& lhs,
2308                 const basic_fbstring<E, T, A, S>& rhs) {
2309   return !(lhs == rhs);
2310 }
2311
2312 #if !defined(_LIBSTDCXX_FBSTRING)
2313 typedef basic_fbstring<char> fbstring;
2314 #endif
2315
2316 // fbstring is relocatable
2317 template <class T, class R, class A, class S>
2318 FOLLY_ASSUME_RELOCATABLE(basic_fbstring<T, R, A, S>);
2319
2320 #else
2321 _GLIBCXX_END_NAMESPACE_VERSION
2322 #endif
2323
2324 } // namespace folly
2325
2326 #ifndef _LIBSTDCXX_FBSTRING
2327
2328 namespace std {
2329 template <>
2330 struct hash< ::folly::fbstring> {
2331   size_t operator()(const ::folly::fbstring& s) const {
2332     return ::folly::hash::fnv32_buf(s.data(), s.size());
2333   }
2334 };
2335 }
2336
2337 #endif // _LIBSTDCXX_FBSTRING
2338
2339 #undef FBSTRING_LIKELY
2340 #undef FBSTRING_UNLIKELY
2341
2342 #endif // FOLLY_BASE_FBSTRING_H_