class CordRepBtree

Destruction

Returns the `height` of the tree. The height of a tree is limited to

kMaxHeight. `height` is implemented as an `int` as in some places we

use negative (-1) values for 'data edges'.

Properties: begin, back, end, front/back boundary indexes.

Properties: size and capacity.

`capacity` contains the current capacity of this instance, where

`kMaxCapacity` contains the maximum capacity of a btree node.

For now, `capacity` and `kMaxCapacity` return the same value, but this may

change in the future if we see benefit in dynamically sizing 'small' nodes

to 'large' nodes for large data trees.

Creates a btree from the given input. Adopts a ref of `rep`.

If the input `rep` is itself a btree, i.e., `IsBtree()`, then this

function immediately returns `rep->btree()`. If the input is a valid data

edge (see IsDataEdge()), then a new leaf node is returned containing `rep`

as the sole data edge. Else, the input is assumed to be a (legacy) concat

tree, and the input is consumed and transformed into a btree().

Destroys the provided tree. Should only be called by cord internal API's,

typically after a ref_count.Decrement() on the last reference count.

Unrefs all edges in `edges` which are assumed to be 'likely one'.

Appends / Prepends an existing CordRep instance to this tree.

The below methods accept three types of input:

1) `rep` is a data node (See `IsDataNode` for valid data edges).

`rep` is appended or prepended to this tree 'as is'.

2) `rep` is a BTREE.

`rep` is merged into `tree` respecting the Append/Prepend order.

3) `rep` is some other (legacy) type.

`rep` is converted in place and added to `tree`

Requires `tree` and `rep` to be not null.

Append/Prepend the data in `data` to this tree.

The `extra` parameter defines how much extra capacity should be allocated

for any additional FLAT being allocated. This is an optimization hint from

the caller. For example, a caller may need to add 2 string_views of data

"abc" and "defghi" which are not consecutive. The caller can in this case

invoke `AddData(tree, "abc", 6)`, and any newly added flat is allocated

where possible with at least 6 bytes of extra capacity beyond `length`.

This helps avoiding data getting fragmented over multiple flats.

There is no limit on the size of `data`. If `data` can not be stored inside

a single flat, then the function will iteratively add flats until all data

has been consumed and appended or prepended to the tree.

Returns a new tree, containing `n` bytes of data from this instance

starting at offset `offset`. Where possible, the returned tree shares

(re-uses) data edges and nodes with this instance to minimize the

combined memory footprint of both trees.

Requires `offset + n

<

= length`. Returns `nullptr` if `n` is zero.

Removes `n` trailing bytes from `tree`, and returns the resulting tree

or data edge. Returns `tree` if n is zero, and nullptr if n == length.

This function is logically identical to:

result = tree->SubTree(0, tree->length - n);

Unref(tree);

return result;

However, the actual implementation will as much as possible perform 'in

place' modifications on the tree on all nodes and edges that are mutable.

For example, in a fully privately owned tree with the last edge being a

flat of length 12, RemoveSuffix(1) will simply set the length of that data

edge to 11, and reduce the length of all nodes on the edge path by 1.

Returns the character at the given offset.

Returns true if this node holds a single data edge, and if so, sets

`fragment` to reference the contained data. `fragment` is an optional

output parameter and allowed to be null.

Returns true if the data of `n` bytes starting at offset `offset`

is contained in a single data edge, and if so, sets fragment to reference

the contained data. `fragment` is an optional output parameter and allowed

to be null.

Returns a span (mutable range of bytes) of up to `size` bytes into the

last FLAT data edge inside this tree under the following conditions:

- none of the nodes down into the FLAT node are shared.

- the last data edge in this tree is a non-shared FLAT.

- the referenced FLAT has additional capacity available.

If all these conditions are met, a non-empty span is returned, and the

length of the flat node and involved tree nodes have been increased by

`span.length()`. The caller is responsible for immediately assigning values

to all uninitialized data reference by the returned span.

Requires `this->refcount.IsOne()`: this function forces the caller to do

this fast path check on the top level node, as this is the most commonly

shared node of a cord tree.

Extracts the right-most data edge from this tree iff:

- the tree and all internal edges to the right-most node are not shared.

- the right-most node is a FLAT node and not shared.

- the right-most node has at least the desired extra capacity.

Returns {tree, nullptr} if any of the above conditions are not met.

This method effectively removes data from the tree. The intent of this

method is to allow applications appending small string data to use

pre-existing capacity, and add the modified rep back to the tree.

Simplified such code would look similar to this:

void MyTreeBuilder::Append(string_view data) {

ExtractResult result = CordRepBtree::ExtractAppendBuffer(tree_, 1);

if (CordRep* rep = result.extracted) {

size_t available = rep->Capacity() - rep->length;

size_t n = std::min(data.size(), n);

memcpy(rep->Data(), data.data(), n);

rep->length += n;

data.remove_prefix(n);

if (!result.tree->IsBtree()) {

tree_ = CordRepBtree::Create(result.tree);

}

tree_ = CordRepBtree::Append(tree_, rep);

}

...

// Remaining edge in `result.tree`.

}

Edge access

Returns reference to the data edge at `index`.

Requires this instance to be a leaf node, and `index` to be valid index.

Diagnostics: returns true if `tree` is valid and internally consistent.

If `shallow` is false, then the provided top level node and all child nodes

below it are recursively checked. If `shallow` is true, only the provided

node in `tree` and the cumulative length, type and height of the direct

child nodes of `tree` are checked. The value of `shallow` is ignored if the

internal `cord_btree_exhaustive_validation` diagnostics variable is true,

in which case the performed validations works as if `shallow` were false.

This function is intended for debugging and testing purposes only.

Diagnostics: asserts that the provided tree is valid.

`AssertValid()` performs a shallow validation by default. `shallow` can be

set to false in which case an exhaustive validation is performed. This

function is implemented in terms of calling `IsValid()` and asserting the

return value to be true. See `IsValid()` for more information.

This function is intended for debugging and testing purposes only.

Diagnostics: dump the contents of this tree to `stream`.

This function is intended for debugging and testing purposes only.

Adds the edge `edge` to this node if possible. `owned` indicates if the

current node is potentially shared or not with other threads. Returns:

- {kSelf,

<this

>}

The edge was directly added to this node.

- {kCopied,

<node

>}

The edge was added to a copy of this node.

- {kPopped, New(edge, height())}

A new leg with the edge was created as this node has no extra capacity.

Replaces the front or back edge with the provided new edge. Returns:

- {kSelf,

<this

>}

The edge was directly set in this node. The old edge is unreffed.

- {kCopied,

<node

>}

A copy of this node was created with the new edge value.

In both cases, the function adopts a reference on `edge`.

Creates a new empty node at the specified height.

Creates a new node containing `rep`, with the height being computed

automatically based on the type of `rep`.

Creates a new node containing both `front` and `back` at height

`front.height() + 1`. Requires `back.height() == front.height()`.

Creates a fully balanced tree from the provided tree by rebuilding a new

tree from all data edges in the input. This function is automatically

invoked internally when the tree exceeds the maximum height.

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_`.

`Action` defines the action for unwinding changes done at the btree's leaf

level that need to be propagated up to the parent node(s). Each operation

on a node has an effect / action defined as follows:

- kSelf

The operation (add / update, etc) was performed directly on the node as

the node is private to the current thread (i.e.: not shared directly or

indirectly through a refcount > 1). Changes can be propagated directly to

all parent nodes as all parent nodes are also then private to the current

thread.

- kCopied

The operation (add / update, etc) was performed on a copy of the original

node, as the node is (potentially) directly or indirectly shared with

other threads. Changes need to be propagated into the parent nodes where

the old down pointer must be unreffed and replaced with this new copy.

Such changes to parent nodes may themselves require a copy if the parent

node is also shared. A kCopied action can propagate all the way to the

top node where we then must unref the `tree` input provided by the

caller, and return the new copy.

- kPopped

The operation (typically add) could not be satisfied due to insufficient

capacity in the targeted node, and a new 'leg' was created that needs to

be added into the parent node. For example, adding a FLAT inside a leaf

node that is at capacity will create a new leaf node containing that

FLAT, that needs to be 'popped' up the btree. Such 'pop' actions can

cascade up the tree if parent nodes are also at capacity. A 'Popped'

action propagating all the way to the top of the tree will result in

the tree becoming one level higher than the current tree through a final

`CordRepBtree::New(tree, popped)` call, resulting in a new top node

referencing the old tree and the new (fully popped upwards) 'leg'.