folly/FBString.h

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