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