folly/FBString.h

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