std::string s("str");  
const char* p = s.data();  
{  
    std::string s2(s);  
    (void) s[0];         // 触发COW  
}  
std::cout << *p << '\n';      // p指向的原有空间已经无效

class string {  
  char *start;  
  size_t size;  
  static const int kLocalSize = 15;  
  union{  
    char buffer[kLocalSize+1];      // 满足条件时，用来存放短字符串  
    size_t capacity;  
  }data;  
};

template <  
    typename E,  
    class T = std::char_traits<E>,  
    class A = std::allocator<E>,  
    class Storage = fbstring_core<E>>  
class basic_fbstring;

struct RefCounted {  
    std::atomic<size_t> refCount_;  
    Char data_[1];  
    static RefCounted * create(size_t * size);       // 创建一个RefCounted  
    static RefCounted * create(const Char * data, size_t * size);     // ditto  
    static void incrementRefs(Char * p);     // 增加一个引用  
    static void decrementRefs(Char * p);    // 减少一个引用  
    // 其他函数定义  
}
;  
struct MediumLarge {  
  Char* data_;  
  size_t size_;  
  size_t capacity_;  

  size_t capacity() const {  
    return kIsLittleEndian ? capacity_ & capacityExtractMask : capacity_ >> 2;  
  } 

  void setCapacity(size_t cap, Category cat) {  
    capacity_ = kIsLittleEndian  
        ? cap | (static_cast<size_t>(cat) << kCategoryShift)  
        : (cap << 2) | static_cast<size_t>(cat);  
  }  
};  

union {  
    uint8_t bytes_[sizeof(MediumLarge)];          // For accessing the last byte.  
    Char small_[sizeof(MediumLarge) / sizeof(Char)];  
    MediumLarge ml_;  
};

typedef uint8_t category_type;  
enum class Category : category_type {  
    isSmall = 0,  
    isMedium = kIsLittleEndian ? 0x80 : 0x2,       //  10000000 , 00000010  
    isLarge = kIsLittleEndian ? 0x40 : 0x1,        //  01000000 , 00000001  
};

void setSmallSize(size_t s) {  
  ......  
  constexpr auto shift = kIsLittleEndian ? 0 : 2;  
  small_[maxSmallSize] = char((maxSmallSize - s) << shift);  
  ......  
}

constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8;  
void setCapacity(size_t cap, Category cat) {  
    capacity_ = kIsLittleEndian  
        ? cap | (static_cast<size_t>(cat) << kCategoryShift)  
        : (cap << 2) | static_cast<size_t>(cat);  
}

constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;    // 11000000 , 00000011  
constexpr static size_t lastChar = sizeof(MediumLarge) - 1;  

union {  
    uint8_t bytes_[sizeof(MediumLarge)];          // For accessing the last byte.  
    Char small_[sizeof(MediumLarge) / sizeof(Char)];  
    MediumLarge ml_;  
};  

Category category() const {  
  // works for both big-endian and little-endian  
  return static_cast<Category>(bytes_[lastChar] & categoryExtractMask);  
}

size_t capacity() const {  
  switch (category()) {  
    case Category::isSmall:  
      return maxSmallSize;  
    case Category::isLarge:  
      // For large-sized strings, a multi-referenced chunk has no  
      // available capacity. This is because any attempt to append  
      // data would trigger a new allocation.  
      if (RefCounted::refs(ml_.data_) > 1) {  
        return ml_.size_;  
      }  
      break;  
    case Category::isMedium:  
    default:  
      break;  
  }  
  return ml_.capacity();  
}

constexpr static uint8_t categoryExtractMask = kIsLittleEndian ? 0xC0 : 0x3;  
constexpr static size_t kCategoryShift = (sizeof(size_t) - 1) * 8; 

constexpr static size_t capacityExtractMask = kIsLittleEndian  
      ? ~(size_t(categoryExtractMask) << kCategoryShift)  
      : 0x0 /* unused */;  

size_t capacity() const {  
      return kIsLittleEndian ? capacity_ & capacityExtractMask : capacity_ >> 2;  
}

size_t size() const {  
  size_t ret = ml_.size_;

  if /* constexpr */ (kIsLittleEndian) {  
    // We can save a couple instructions, because the category is  
    // small iff the last char, as unsigned, is <= maxSmallSize.  
    typedef typename std::make_unsigned<Char>::type UChar;  

    auto maybeSmallSize = size_t(maxSmallSize) -  
        size_t(static_cast<UChar>(small_[maxSmallSize]));  

    // With this syntax, GCC and Clang generate a CMOV instead of a branch.  
    ret = (static_cast<ssize_t>(maybeSmallSize) >= 0) ? maybeSmallSize : ret;  
  } else {  
    ret = (category() == Category::isSmall) ? smallSize() : ret;  
  }  

  return ret;  
}

size_t smallSize() const {  
  assert(category() == Category::isSmall);  
  constexpr auto shift = kIsLittleEndian ? 0 : 2;  
  auto smallShifted = static_cast<size_t>(small_[maxSmallSize]) >> shift;  
  assert(static_cast<size_t>(maxSmallSize) >= smallShifted);  
  return static_cast<size_t>(maxSmallSize) - smallShifted;  
}

fbstring_core(  
    const Char* const data,  
    const size_t size,  
    bool disableSSO = FBSTRING_DISABLE_SSO) {  
  if (!disableSSO && size <= maxSmallSize) {  
    initSmall(data, size);  
  } else if (size <= maxMediumSize) {  
    initMedium(data, size);  
  } else {  
    initLarge(data, size);  
  }  
}

template <class Char>  
inline void fbstring_core<Char>::initSmall(  
    const Char* const data,  
    const size_t size) { 

// If data is aligned, use fast word-wise copying. Otherwise,  
// use conservative memcpy.  
// The word-wise path reads bytes which are outside the range of  
// the string, and makes ASan unhappy, so we disable it when  
// compiling with ASan.  
#ifndef FOLLY_SANITIZE_ADDRESS  
  if ((reinterpret_cast<size_t>(data) & (sizeof(size_t) - 1)) == 0) {  
    const size_t byteSize = size * sizeof(Char);  
    constexpr size_t wordWidth = sizeof(size_t);  

    switch ((byteSize + wordWidth - 1) / wordWidth) { // Number of words.  
      case 3:  
        ml_.capacity_ = reinterpret_cast<const size_t*>(data)[2];  
        FOLLY_FALLTHROUGH;  
      case 2:  
        ml_.size_ = reinterpret_cast<const size_t*>(data)[1];  
        FOLLY_FALLTHROUGH;  
      case 1:  
        ml_.data_ = *reinterpret_cast<Char**>(const_cast<Char*>(data));  
        FOLLY_FALLTHROUGH;  
      case 0:  
        break;  
    }  
  } else  
#endif  
  {  
    if (size != 0) {  
      fbstring_detail::podCopy(data, data + size, small_);  
    }  
  }  
  setSmallSize(size);  
}

void setSmallSize(size_t s) {  
  // Warning: this should work with uninitialized strings too,  
  // so don't assume anything about the previous value of  
  // small_[maxSmallSize].  
  assert(s <= maxSmallSize);  
  constexpr auto shift = kIsLittleEndian ? 0 : 2;  
  small_[maxSmallSize] = char((maxSmallSize - s) << shift);  
  small_[s] = '\0';  
  assert(category() == Category::isSmall && size() == s);  
}

template <class Char>  
FOLLY_NOINLINE inline void fbstring_core<Char>::initMedium(  
    const Char* const data,  
    const size_t size) {  
  // Medium strings are allocated normally. Don't forget to  
  // allocate one extra Char for the terminating null.  
  auto const allocSize = goodMallocSize((1 + size) * sizeof(Char));  

  ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));  
  if (FOLLY_LIKELY(size > 0)) {  
    fbstring_detail::podCopy(data, data + size, ml_.data_);  
  }  

  ml_.size_ = size;  
  ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);  
  ml_.data_[size] = '\0';  
}

template <class Char>  
FOLLY_NOINLINE inline void fbstring_core<Char>::initLarge(  
    const Char* const data,  
    const size_t size) {  
  // Large strings are allocated differently  
  size_t effectiveCapacity = size;  

  auto const newRC = RefCounted::create(data, &effectiveCapacity);  
  ml_.data_ = newRC->data_;  
  ml_.size_ = size;  
  ml_.setCapacity(effectiveCapacity, Category::isLarge);  
  ml_.data_[size] = '\0';  
}

struct RefCounted {  
    std::atomic<size_t> refCount_;  
    Char data_[1];  

    constexpr static size_t getDataOffset() {  
      return offsetof(RefCounted, data_);  
    }  

    static RefCounted* create(size_t* size) {  
      const size_t allocSize =  
          goodMallocSize(getDataOffset() + (*size + 1) * sizeof(Char));  
      auto result = static_cast<RefCounted*>(checkedMalloc(allocSize));  
      result->refCount_.store(1, std::memory_order_release);  
      *size = (allocSize - getDataOffset()) / sizeof(Char) - 1;  
      return result;  
    } 

    static RefCounted* create(const Char* data, size_t* size) {  
      const size_t effectiveSize = *size;  
      auto result = create(size);  
      if (FOLLY_LIKELY(effectiveSize > 0)) {  
        fbstring_detail::podCopy(data, data + effectiveSize, result->data_);  
      }  
      return result;  
    }  
};

/**  
  * Defines a special acquisition method for constructing fbstring  
  * objects. AcquireMallocatedString means that the user passes a  
  * pointer to a malloc-allocated string that the fbstring object will  
  * take into custody.  
  */  
enum class AcquireMallocatedString {};  

// Nonstandard constructor  
basic_fbstring(value_type *s, size_type n, size_type c,  
                  AcquireMallocatedString a)  
      : store_(s, n, c, a) {  
}

// Snatches a previously mallocated string. The parameter "size"  
// is the size of the string, and the parameter "allocatedSize"  
// is the size of the mallocated block.  The string must be  
// \0-terminated, so allocatedSize >= size + 1 and data[size] == '\0'.  
//  
// So if you want a 2-character string, pass malloc(3) as "data",  
// pass 2 as "size", and pass 3 as "allocatedSize".  
fbstring_core(Char * const data,  
              const size_t size,  
              const size_t allocatedSize,  
              AcquireMallocatedString) {  
  if (size > 0) {  
    FBSTRING_ASSERT(allocatedSize >= size + 1);  
    FBSTRING_ASSERT(data[size] == '\0');  

    // Use the medium string storage  
    ml_.data_ = data;  
    ml_.size_ = size;  

    // Don't forget about null terminator  
    ml_.setCapacity(allocatedSize - 1, Category::isMedium);  
  } else {  
    // No need for the memory  
    free(data);  
    reset();  
  }  
}

// Ensure NUL terminated  
*writableTail() = 0;  
fbstring str(  
      reinterpret_cast<char*>(writableData()),  
      length(),  
      capacity(),  
      AcquireMallocatedString());

fbstring_core(const fbstring_core& rhs) {  
  assert(&rhs != this);  
  switch (rhs.category()) {  
    case Category::isSmall:  
      copySmall(rhs);  
      break;  
    case Category::isMedium:  
      copyMedium(rhs);  
      break;  
    case Category::isLarge:  
      copyLarge(rhs);  
      break;  
    default:  
      folly::assume_unreachable();  
  }  
}

template <class Char>  
inline void fbstring_core<Char>::copySmall(const fbstring_core& rhs) {  
  // Just write the whole thing, don't look at details. In  
  // particular we need to copy capacity anyway because we want  
  // to set the size (don't forget that the last character,  
  // which stores a short string's length, is shared with the  
  // ml_.capacity field).  
  ml_ = rhs.ml_;  
}

template <class Char>  
FOLLY_NOINLINE inline void fbstring_core<Char>::copyMedium(  
    const fbstring_core& rhs) {  
  // Medium strings are copied eagerly. Don't forget to allocate  
  // one extra Char for the null terminator.  
  auto const allocSize = goodMallocSize((1 + rhs.ml_.size_) * sizeof(Char));  
  ml_.data_ = static_cast<Char*>(checkedMalloc(allocSize));  
  // Also copies terminator.  
  fbstring_detail::podCopy(  
      rhs.ml_.data_, rhs.ml_.data_ + rhs.ml_.size_ + 1, ml_.data_);  
  ml_.size_ = rhs.ml_.size_;  
  ml_.setCapacity(allocSize / sizeof(Char) - 1, Category::isMedium);  
}

template <class Char>  
FOLLY_NOINLINE inline void fbstring_core<Char>::copyLarge(  
    const fbstring_core& rhs) {  
  // Large strings are just refcounted  
  ml_ = rhs.ml_;  
  RefCounted::incrementRefs(ml_.data_);  
}

static RefCounted* fromData(Char* p) {  
      return static_cast<RefCounted*>(static_cast<void*>(  
          static_cast<unsigned char*>(static_cast<void*>(p)) -  
          getDataOffset()));  
}  

static void incrementRefs(Char* p) {  
  fromData(p)->refCount_.fetch_add(1, std::memory_order_acq_rel);  
}

static RefCounted * fromData(Char * p) {  
      // 转换data_[1]的地址  
      void* voidDataAddr = static_cast<void*>(p);  
      unsigned char* unsignedDataAddr = static_cast<unsigned char*>(voidDataAddr);  
      // 获取data_[1]在结构体的偏移量再相减，得到的就是所属RefCounted的地址  
      unsigned char* unsignedRefAddr = unsignedDataAddr - getDataOffset();  
      void* voidRefAddr = static_cast<void*>(unsignedRefAddr);  
      RefCounted* refCountAddr = static_cast<RefCounted*>(voidRefAddr);  
      return refCountAddr;  
}

~fbstring_core() noexcept {  
    if (category() == Category::isSmall) {  
      return;  
    }  
    destroyMediumLarge();  
}

FOLLY_MALLOC_NOINLINE void destroyMediumLarge() noexcept {  
  auto const c = category();  
  FBSTRING_ASSERT(c != Category::isSmall);  
  if (c == Category::isMedium) {  
    free(ml_.data_);  
  } else {  
    RefCounted::decrementRefs(ml_.data_);  
  }  
}

static void decrementRefs(Char * p) {  
  auto const dis = fromData(p);  
  size_t oldcnt = dis->refCount_.fetch_sub(1, std::memory_order_acq_rel);  
  FBSTRING_ASSERT(oldcnt > 0);  
  if (oldcnt == 1) {  
    free(dis);  
  }  
}

reference operator[](size_type pos "") {  
    return *(begin() + pos);  
}  

iterator begin() {  
    return store_.mutableData();  
}

Char* mutableData() {  
  switch (category()) {  
  case Category::isSmall:  
    return small_;  
  case Category::isMedium:  
    return ml_.data_;  
  case Category::isLarge:  
    return mutableDataLarge();  
  }  
  fbstring_detail::assume_unreachable();  
}  

template <class Char>  
inline Char* fbstring_core<Char>::mutableDataLarge() {  
  FBSTRING_ASSERT(category() == Category::isLarge);  
  if (RefCounted::refs(ml_.data_) > 1) { // Ensure unique.  
    unshare();  
  }  
  return ml_.data_;  
}

void unshare(size_t minCapacity = 0);  

template <class Char>  
FOLLY_MALLOC_NOINLINE inline void fbstring_core<Char>::unshare(  
    size_t minCapacity) {  
  FBSTRING_ASSERT(category() == Category::isLarge);  
  size_t effectiveCapacity = std::max(minCapacity, ml_.capacity());  
  auto const newRC = RefCounted::create(&effectiveCapacity);  

  // If this fails, someone placed the wrong capacity in an  
  // fbstring.  
  FBSTRING_ASSERT(effectiveCapacity >= ml_.capacity());  

  // Also copies terminator.  
  fbstring_detail::podCopy(ml_.data_, ml_.data_ + ml_.size_ + 1, newRC->data_);  

  RefCounted::decrementRefs(ml_.data_);  
  ml_.data_ = newRC->data_;  
  ml_.setCapacity(effectiveCapacity, Category::isLarge);  
  // size_ remains unchanged.  
}

// C++11 21.4.5 element access:  
const_reference operator[](size_type pos "") const {  
    return *(begin() + pos);  
}  

const_iterator begin() const {  
    return store_.data();  
}  

// In C++11 data() and c_str() are 100% equivalent.  
const Char* data() const { return c_str(); }  

const Char* c_str() const {  
    const Char* ptr = ml_.data_;  
    // With this syntax, GCC and Clang generate a CMOV instead of a branch.  
    ptr = (category() == Category::isSmall) ? small_ : ptr;  
    return ptr;  
}

#include "folly/Benchmark.h"  
#include "folly/FBString.h"  
#include "folly/container/Foreach.h"  

using namespace std;  
using namespace folly;  

BENCHMARK(nonConstFbstringAt, n) {  
  ::folly::fbstring str(  
      "fbstring is a drop-in replacement for std::string. The main benefit of fbstring is significantly increased "  
      "performance on virtually all important primitives. This is achieved by using a three-tiered storage strategy "  
      "and by cooperating with the memory allocator. In particular, fbstring is designed to detect use of jemalloc and "  
      "cooperate with it to achieve significant improvements in speed and memory usage.");  
  FOR_EACH_RANGE(i, 0, n) {  
    char &s = str[2];  
    doNotOptimizeAway(s);  
  }  
}  

BENCHMARK_DRAW_LINE();  

BENCHMARK_RELATIVE(constFbstringAt, n) {  
  const ::folly::fbstring str(  
      "fbstring is a drop-in replacement for std::string. The main benefit of fbstring is significantly increased "  
      "performance on virtually all important primitives. This is achieved by using a three-tiered storage strategy "  
      "and by cooperating with the memory allocator. In particular, fbstring is designed to detect use of jemalloc and "  
      "cooperate with it to achieve significant improvements in speed and memory usage.");  
  FOR_EACH_RANGE(i, 0, n) {  
    const char &s = str[2];  
    doNotOptimizeAway(s);  
  }  
}  

int main() { runBenchmarks(); }

============================================================================  
delve_folly/main.cc                             relative  time/iter  iters/s  
============================================================================  
nonConstFbstringAt                                          39.85ns   25.10M  
----------------------------------------------------------------------------  
constFbstringAt                                  175.57%    22.70ns   44.06M  
============================================================================

inline void* checkedRealloc(void* ptr, size_t size) {  
  void* p = realloc(ptr, size);  
  if (!p) {  
    throw_exception<std::bad_alloc>();  
  }  
  return p;  
}  

/**  
  * This function tries to reallocate a buffer of which only the first  
  * currentSize bytes are used. The problem with using realloc is that  
  * if currentSize is relatively small _and_ if realloc decides it  
  * needs to move the memory chunk to a new buffer, then realloc ends  
  * up copying data that is not used. It's generally not a win to try  
  * to hook in to realloc() behavior to avoid copies - at least in  
  * jemalloc, realloc() almost always ends up doing a copy, because  
  * there is little fragmentation / slack space to take advantage of.  
  */  
FOLLY_MALLOC_CHECKED_MALLOC FOLLY_NOINLINE inline void* smartRealloc(  
    void* p,  
    const size_t currentSize,  
    const size_t currentCapacity,  
    const size_t newCapacity) {  
  assert(p);  
  assert(currentSize <= currentCapacity &&  
          currentCapacity < newCapacity);  

  auto const slack = currentCapacity - currentSize; 

  if (slack * 2 > currentSize) {  
    // Too much slack, malloc-copy-free cycle:  
    auto const result = checkedMalloc(newCapacity);  
    std::memcpy(result, p, currentSize);  
    free(p);  

    return result;  
  }  

  // If there's not too much slack, we realloc in hope of coalescing  
  return checkedRealloc(p, newCapacity);  
}

long __builtin_expect (long exp, long c)

if (__builtin_expect (x, 0))  
  foo ();

if (__builtin_expect (ptr != NULL, 1))  
  foo (*ptr);

#if __GNUC__  
#define FOLLY_DETAIL_BUILTIN_EXPECT(b, t) (__builtin_expect(b, t))  
#else  
#define FOLLY_DETAIL_BUILTIN_EXPECT(b, t) b  
#endif  

//  Likeliness annotations  
//  
//  Useful when the author has better knowledge than the compiler of whether  
//  the branch condition is overwhelmingly likely to take a specific value.  
//  
//  Useful when the author has better knowledge than the compiler of which code  
//  paths are designed as the fast path and which are designed as the slow path,  
//  and to force the compiler to optimize for the fast path, even when it is not  
//  overwhelmingly likely.  
#define FOLLY_LIKELY(x) FOLLY_DETAIL_BUILTIN_EXPECT((x), 1)  
#define FOLLY_UNLIKELY(x) FOLLY_DETAIL_BUILTIN_EXPECT((x), 0)  

static RefCounted* create(const Char* data, size_t* size) {  
  const size_t effectiveSize = *size;  
  auto result = create(size);  
  if (FOLLY_LIKELY(effectiveSize > 0)) {       // __builtin_expect  
    fbstring_detail::podCopy(data, data + effectiveSize, result->data_);  
  }  
  return result;  
}

const Char* c_str() const {  
  const Char* ptr = ml_.data_;  
  // With this syntax, GCC and Clang generate a CMOV instead of a branch.  
  ptr = (category() == Category::isSmall) ? small_ : ptr;  
  return ptr;  
}

void function_that_never_returns (void);  
int g (int c)  
{  
  if (c)  
    {  
      return 1;  
    }  
  else  
    {  
      function_that_never_returns ();  
      __builtin_unreachable ();  
    }  
}

[[noreturn]] FOLLY_ALWAYS_INLINE void assume_unreachable() {  
  assume(false);  
  // Do a bit more to get the compiler to understand  
  // that this function really will never return.  
#if defined(__GNUC__)  
  __builtin_unreachable();  
#elif defined(_MSC_VER)  
  __assume(0);  
#else  
  // Well, it's better than nothing.  
  std::abort();  
#endif  
}

Char* mutableData() {  
  switch (category()) {  
    case Category::isSmall:  
      return small_;  
    case Category::isMedium:  
      return ml_.data_;  
    case Category::isLarge:  
      return mutableDataLarge();  
  }  
  folly::assume_unreachable();  
}

// It's MSVC, so we just have to guess ... and allow an override  
#ifdef _MSC_VER  
# ifdef FOLLY_ENDIAN_BE  
  static constexpr auto kIsLittleEndian = false;  
# else  
  static constexpr auto kIsLittleEndian = true;  
# endif  
#else  
  static constexpr auto kIsLittleEndian =  
  __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__;  
#endif

/* Test for a little-endian machine */  
#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__