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