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