folly/FBString.h

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