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