apfs::BTree¶

template<typename KeyType, typename Compare = std::less<KeyType>>
class BTree¶

NOTE: If you’re using the public API, you will never actually have to use this directly yourself! This is actually a B+ tree.

Each non-leaf node stores keys of type KeyType. No keys smaller than the first KeyType present in the node will ever be present in the subtree of that node, however, the same doesn’t apply for the last entry. The nodes form half-open intervals, with the very last node extending to ‘positive infinity’.

KeyType can have operator< and should have numeric_limits<KeyType>::max() defined.

Public Functions¶

bool is_leaf() const¶

Returns true if the current node is a leaf node and false otherwise.

std::vector<child_t> children() const¶

Returns a typecasted version of the key_values vector.

Throws:¶

If – the current node is not a leaf node.

BTree(const btree_node_phys_t &node, const BlockReader &reader, Compare lt = {})¶

Constructs a BTree using a raw btree_node_phys_t, a BlockReader, and a custom comparator function.

The comparator is optional, and will be ignored if operator< is defined for KeyType, however, it is needed when the keys you are comparing have variable sizes, and it is necessary to use bytes_t to store them to prevent truncation if stored with a general parent struct.

template<typename Convert>
key_value_t lower_bound(const bytes_t &k, const Convert &convert) const¶

Finds the first key-value pair greater than or equal to k.

Parameters:¶

const Convert &convert¶

should convert virtual addresses (where applicable) to physical addresses.

template<typename Convert>
key_value_t upper_bound(const bytes_t &k, const Convert &convert) const¶

Finds the first key-value pair greater than k.

Parameters:¶

const Convert &convert¶

should convert virtual addresses (where applicable) to physical addresses.

template<typename Convert>
key_value_t prev(const bytes_t &k, const Convert &convert) const¶

Finds the key-value pair that comes before k in the in-order traversal of the tree.

Parameters:¶

const Convert &convert¶

should convert virtual addresses (where applicable) to physical addresses.

Public Members¶

std::vector<key_value_t> key_values¶

For a non-leaf, we’ll have children.

For a leaf node, we’ll have key-value pairs.

Public Static Attributes¶

static key_value_t SENTINEL¶

Empty key_value_t to return for when lower_bound/upper_bound does not find anything.