folly/FBString.h

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