Compiler Explorer

Source code

#include <atomic>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <memory>

class RefcountAndFlags {
 public:
  constexpr RefcountAndFlags() : count_{kRefIncrement} {}
  constexpr RefcountAndFlags(const RefcountAndFlags&) : count_{kRefIncrement} {}

struct Immortal {};
  explicit constexpr RefcountAndFlags(Immortal) : count_(kImmortalFlag) {}

inline void Increment() {    count_.fetch_add(kRefIncrement, std::memory_order_relaxed);  }

inline bool Decrement() {
    int32_t refcount = count_.load(std::memory_order_acquire) & kRefcountMask;
    assert(refcount > 0 || refcount & kImmortalFlag);
    return refcount != kRefIncrement &&
           (count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel) &
            kRefcountMask) != kRefIncrement;
  }

inline bool DecrementExpectHighRefcount() {
    int32_t refcount =
        count_.fetch_sub(kRefIncrement, std::memory_order_acq_rel) &
        kRefcountMask;
    assert(refcount > 0 || refcount & kImmortalFlag);
    return refcount != kRefIncrement;
  }

inline size_t Get() const {
    return static_cast<size_t>(count_.load(std::memory_order_acquire) >>
                               kNumFlags);
  }

inline bool IsOne() {
    return (count_.load(std::memory_order_acquire) & kRefcountMask) ==
           kRefIncrement;
  }

bool IsImmortal() const {
    return (count_.load(std::memory_order_relaxed) & kImmortalFlag) != 0;
  }

private:
  enum Flags {
    kNumFlags = 2,
    kImmortalFlag = 0x1,
    kReservedFlag = 0x2,
    kRefIncrement = (1 << kNumFlags),
    kRefcountMask = ~kReservedFlag,
  };

std::atomic<int32_t> count_;
};

// Various representations that we allow
enum CordRepKind {
  UNUSED_0 = 0,
  SUBSTRING = 1,
  CRC = 2,
  BTREE = 3,
  RING = 4,
  EXTERNAL = 5,

// We have different tags for different sized flat arrays,
  // starting with FLAT, and limited to MAX_FLAT_TAG. The below values map to an
  // allocated range of 32 bytes to 256 KB. The current granularity is:
  // - 8 byte granularity for flat sizes in [32 - 512]
  // - 64 byte granularity for flat sizes in (512 - 8KiB]
  // - 4KiB byte granularity for flat sizes in (8KiB, 256 KiB]
  // If a new tag is needed in the future, then 'FLAT' and 'MAX_FLAT_TAG' should
  // be adjusted as well as the Tag <---> Size mapping logic so that FLAT still
  // represents the minimum flat allocation size. (32 bytes as of now).
  FLAT = 6,
  MAX_FLAT_TAG = 248
};

struct CordRep {
  struct ExtractResult {
    CordRep* tree;
    CordRep* extracted;
  };

CordRep() = default;
  constexpr CordRep(RefcountAndFlags::Immortal immortal, size_t l)
      : length(l), refcount(immortal), tag(EXTERNAL), storage{} {}

size_t length;
  RefcountAndFlags refcount;
  uint8_t tag;

uint8_t storage[3];

// Memory management

// Destroys the provided `rep`.
  static void Destroy(CordRep* rep);

// Increments the reference count of `rep`.
  // Requires `rep` to be a non-null pointer value.
  static inline CordRep* Ref(CordRep* rep);

// Decrements the reference count of `rep`. Destroys rep if count reaches
  // zero. Requires `rep` to be a non-null pointer value.
  static inline void Unref(CordRep* rep);
};

class CordRepBtree : public CordRep {
 public:  
  // EdgeType identifies `front` and `back` enum values.
  // Various implementations in CordRepBtree such as `Add` and `Edge` are
  // generic and templated on operating on either of the boundary edges.
  // For more information on the possible edges contained in a CordRepBtree
  // instance see the documentation for `edges_`.
  enum class EdgeType { kFront, kBack };

// Convenience constants into `EdgeType`
  static constexpr EdgeType kFront = EdgeType::kFront;
  static constexpr EdgeType kBack = EdgeType::kBack;

// Maximum number of edges: based on experiments and performance data, we can
  // pick suitable values resulting in optimum cacheline aligned values. The
  // preferred values are based on 64-bit systems where we aim to align this
  // class onto 64 bytes, i.e.:  6 = 64 bytes, 14 = 128 bytes, etc.
  // TODO(b/192061034): experiment with alternative sizes.
  static constexpr size_t kMaxCapacity = 6;

// Reasonable maximum height of the btree. We can expect a fill ratio of at
  // least 50%: trees are always expanded at the front or back. Concatenating
  // trees will then typically fold at the top most node, where the lower nodes
  // are at least at capacity on one side of joined inputs. At a lower fill
  // rate of 4 edges per node, we have capacity for ~16 million leaf nodes.
  // We will fail / abort if an application ever exceeds this height, which
  // should be extremely rare (near impossible) and be an indication of an
  // application error: we do not assume it reasonable for any application to
  // operate correctly with such monster trees.
  // Another compelling reason for the number `12` is that any contextual stack
  // required for navigation or insertion requires 12 words and 12 bytes, which
  // fits inside 2 cache lines with some room to spare, and is reasonable as a
  // local stack variable compared to Cord's current near 400 bytes stack use.
  // The maximum `height` value of a node is then `kMaxDepth - 1` as node height
  // values start with a value of 0 for leaf nodes.
  static constexpr size_t kMaxDepth = 12;
  // See comments on height() for why this is an int and not a size_t.
  static constexpr int kMaxHeight = static_cast<int>(kMaxDepth - 1);

CordRepBtree(const CordRepBtree& rha) = default;

CordRepBtree* CopyRaw(int new_length) const {
    CordRepBtree* tree = new CordRepBtree;
    // `length` and `refcount` are the first members of `CordRepBtree`.
    // We initialize `length` using the given length, have `refcount` be set to
    // ref = 1 through its default constructor, and copy all data beyond
    // 'refcount' which starts with `tag` using a single memcpy: all contents
    // except `refcount` is trivially copyable, and the compiler does not
    // efficiently coalesce member-wise copy of these members.
    tree->length = new_length;
    uint8_t* dst = &tree->tag;
    const uint8_t* src = &tag;
    const ptrdiff_t offset = src - reinterpret_cast<const uint8_t*>(this);
    memcpy(dst, src, sizeof(CordRepBtree) - static_cast<size_t>(offset));
    return tree;  return tree;
  }

private:
  CordRepBtree() = default;
  ~CordRepBtree() = default;

// `edges_` contains all edges starting from this instance.
  // These are explicitly `child` edges only, a cord btree (or any cord tree in
  // that respect) does not store `parent` pointers anywhere: multiple trees /
  // parents can reference the same shared child edge. The type of these edges
  // depends on the height of the node. `Leaf nodes` (height == 0) contain `data
  // edges` (external or flat nodes, or sub-strings thereof). All other nodes
  // (height > 0) contain pointers to BTREE nodes with a height of `height - 1`.
  CordRep* edges_[kMaxCapacity]; 
};

CordRepBtree* CopyRaw(void*mem, const CordRepBtree&rhs, int new_length) {
  return rhs.CopyRaw(new_length);
}