pub trait BTreeExt<K, V> {
Show 19 methods
// Required methods
fn root_id(&self) -> Option<usize>;
fn node(&self, id: usize) -> &Node<K, V>;
fn get_in<Q>(&self, key: &Q, id: usize) -> Option<&V>
where K: Borrow<Q>,
Q: Ord + ?Sized;
fn item(&self, addr: Address) -> Option<&Item<K, V>>;
fn first_item_address(&self) -> Option<Address>;
fn first_back_address(&self) -> Address;
fn last_item_address(&self) -> Option<Address>;
fn last_valid_address(&self) -> Address;
fn normalize(&self, addr: Address) -> Option<Address>;
fn leaf_address(&self, addr: Address) -> Address;
fn previous_item_address(&self, addr: Address) -> Option<Address>;
fn previous_front_address(&self, addr: Address) -> Option<Address>;
fn next_item_address(&self, addr: Address) -> Option<Address>;
fn next_back_address(&self, addr: Address) -> Option<Address>;
fn next_item_or_back_address(&self, addr: Address) -> Option<Address>;
fn address_of<Q>(&self, key: &Q) -> Result<Address, Address>
where K: Borrow<Q>,
Q: Ord + ?Sized;
fn address_in<Q>(&self, id: usize, key: &Q) -> Result<Address, Address>
where K: Borrow<Q>,
Q: Ord + ?Sized;
fn validate(&self)
where K: Ord;
fn validate_node(
&self,
id: usize,
parent: Option<usize>,
min: Option<&K>,
max: Option<&K>,
) -> usize
where K: Ord;
}Expand description
Extended API.
This trait can be imported to access the internal functions of the B-Tree. These functions are not intended to be directly called by the users, but can be used to extends the data structure with new functionalities.
§Addressing
In this implementation of B-Trees, each node of a tree is addressed
by the Address type.
Each node is identified by a usize, and each item/entry in the node by an Offset.
This extended API allows the caller to explore, access and modify the
internal structure of the tree using this addressing system.
Note that a valid address does not always refer to an actual item in the tree.
See the Address type documentation for more details.
Required Methods§
Sourcefn node(&self, id: usize) -> &Node<K, V>
fn node(&self, id: usize) -> &Node<K, V>
Get the node associated to the given id.
Panics if id is out of bounds.
Sourcefn get_in<Q>(&self, key: &Q, id: usize) -> Option<&V>
fn get_in<Q>(&self, key: &Q, id: usize) -> Option<&V>
Get a reference to the value associated to the given key in the node id, if any.
Sourcefn item(&self, addr: Address) -> Option<&Item<K, V>>
fn item(&self, addr: Address) -> Option<&Item<K, V>>
Get a reference to the item located at the given address.
Sourcefn first_item_address(&self) -> Option<Address>
fn first_item_address(&self) -> Option<Address>
Get the first item address, if any.
Returns the first occupied valid address, or None if the tree is empty.
Sourcefn first_back_address(&self) -> Address
fn first_back_address(&self) -> Address
Get the first back address.
The returned address may not be occupied if the tree is empty.
Sourcefn last_item_address(&self) -> Option<Address>
fn last_item_address(&self) -> Option<Address>
Get the last item address, if any.
Returns the last occupied valid address, or None if the tree is empty.
Sourcefn last_valid_address(&self) -> Address
fn last_valid_address(&self) -> Address
Get the last valid address in the tree.
Sourcefn normalize(&self, addr: Address) -> Option<Address>
fn normalize(&self, addr: Address) -> Option<Address>
Normalizes the given item address so that an out-of-node-bounds address points to the next item.
Sourcefn leaf_address(&self, addr: Address) -> Address
fn leaf_address(&self, addr: Address) -> Address
Returns the greatest valid leaf address that directly precedes the given address.
A “leaf address” is an address located in a leaf node.
Sourcefn previous_item_address(&self, addr: Address) -> Option<Address>
fn previous_item_address(&self, addr: Address) -> Option<Address>
Get the previous item address.
Returns the previous valid occupied address.
The following diagram shows the order between addresses defined by this function.
┌───────────┐
╔═════════════╪══╗ ╔══╗ │
║ │┌─v─┐║┌─v─┐│
┌───────────╫─────────────││ 0 │║│ 1 ││──────────────────────┐
│ ║ │└─v─┘║└─v─┘│ │
│ ║ └──╫──╫──╫──┘ │
start v │ ║ ║ ║│ ╚══════════════════════╗ │ ^ end
║ │ ║ ╔══╝ ╚╪══════════╗ ║ │ ║
┌──╫──────────────┐ ║ ┌──╫──────────────┐ ║ ┌──╫─────╫──┐
│ ║ ╔═════╗ │ ║ │ ║ ╔═════╗ │ ║ │ ║ ║ │
│┌─v─┐ ┌─^─┐ ┌─v─┐│ ║ │┌─v─┐ ┌─^─┐ ┌─v─┐│ ║ │┌─v─┐ ┌─^─┐│
││ 0 │ │ 1 │ │ 2 ││ ║ ││ 0 │ │ 1 │ │ 2 ││ ║ ││ 0 │ │ 1 ││
│└─v─┘ └─^─┘ └─v─┘│ ║ │└─v─┘ └─^─┘ └─v─┘│ ║ │└─v─┘ └─^─┘│
│ ╚═════╝ ╚══╪══╝ │ ╚═════╝ ╚══╪══╝ │ ╚═════╝ │
└─────────────────┘ └─────────────────┘ └───────────┘Sourcefn previous_front_address(&self, addr: Address) -> Option<Address>
fn previous_front_address(&self, addr: Address) -> Option<Address>
Get the previous front address.
A “front address” is a valid address whose offset is less that the number of items in the node.
If addr.offset is equal to -1, then it doesn’t actually refer to an existing item in the node.
The following diagram shows the order between addresses defined by this function.
^ end
┌─────────║──┐
╔═══════════════╗ │╔══╗ ║ │
║ ┌─v─┐│║┌─v─┐ ┌─^─┐│
┌─────╫─────────────│-1 ││║│ 0 │ │ 1 ││ ─────────────────────┐
│ ║ └─v─┘│║└─v─┘ └─^─┘│ │
│ ║ ║ └╫──╫─────╫──┘ │
│ ║ ║ ║ ║ │ ╚═════════════════════════╪═══════╗
start v │ ║ ║ ║ ╚══╪═══════════════════╗ │ ║
║ │ ║ ╔═╝ ╚═════╪═════╗ ║ │ ║
║ ┌──────────────╫──┐ ║ ┌──────────────╫──┐ ║ ┌───────────┐ ║
║ │ ╔═════╗ ║ │ ║ │ ╔═════╗ ║ │ ║ │ ╔═════╗ │ ║
┌─v─┐│┌─^─┐ ┌─v─┐ ┌─^─┐│ ┌─v─┐│┌─^─┐ ┌─v─┐ ┌─^─┐│ ┌─v─┐│┌─^─┐ ┌─v─┐│ ║
│-1 │││ 0 │ │ 1 │ │ 2 ││ │-1 │││ 0 │ │ 1 │ │ 2 ││ │-1 │││ 0 │ │ 1 ││ ║
└─v─┘│└─^─┘ └─v─┘ └─^─┘│ └─v─┘│└─^─┘ └─v─┘ └─^─┘│ └─v─┘│└─^─┘ └─v─┘│ ║
╚══╪══╝ ╚═════╝ │ ╚══╪══╝ ╚═════╝ │ ╚══╪══╝ ╚══╪═╝
└─────────────────┘ └─────────────────┘ └───────────┘Sourcefn next_item_address(&self, addr: Address) -> Option<Address>
fn next_item_address(&self, addr: Address) -> Option<Address>
Get the next item address.
Returns the next valid occupied address.
The following diagram shows the order between addresses defined by this function.
┌───────────┐
╔═════════════╪══╗ ╔══╗ │
║ │┌─v─┐║┌─v─┐│
┌───────────╫─────────────││ 0 │║│ 1 ││──────────────────────┐
│ ║ │└─v─┘║└─v─┘│ │
│ ║ └──╫──╫──╫──┘ │
start v │ ║ ║ ║│ ╚══════════════════════╗ │ ^ end
║ │ ║ ╔══╝ ╚╪══════════╗ ║ │ ║
┌──╫──────────────┐ ║ ┌──╫──────────────┐ ║ ┌──╫─────╫──┐
│ ║ ╔═════╗ │ ║ │ ║ ╔═════╗ │ ║ │ ║ ║ │
│┌─v─┐ ┌─^─┐ ┌─v─┐│ ║ │┌─v─┐ ┌─^─┐ ┌─v─┐│ ║ │┌─v─┐ ┌─^─┐│
││ 0 │ │ 1 │ │ 2 ││ ║ ││ 0 │ │ 1 │ │ 2 ││ ║ ││ 0 │ │ 1 ││
│└─v─┘ └─^─┘ └─v─┘│ ║ │└─v─┘ └─^─┘ └─v─┘│ ║ │└─v─┘ └─^─┘│
│ ╚═════╝ ╚══╪══╝ │ ╚═════╝ ╚══╪══╝ │ ╚═════╝ │
└─────────────────┘ └─────────────────┘ └───────────┘Sourcefn next_back_address(&self, addr: Address) -> Option<Address>
fn next_back_address(&self, addr: Address) -> Option<Address>
Get the next back address.
A “back address” is a valid address whose offset is at least 0.
If addr.offset is equal to the number of items in the node then it doesn’t actually refer
to an existing item in the node,
but it can be used to insert a new item with BTreeExt::insert_at.
The following diagram shows the order between addresses defined by this function.
┌───────────┐ ^ end
╔═════════════╪══╗ ╔══╗ │ ║
║ │┌─v─┐║┌─v─┐│┌─^─┐
┌───────────╫─────────────││ 0 │║│ 1 │││ 2 │─────────────────┐
│ ║ │└─v─┘║└─v─┘│└─^─┘ │
│ ║ └──╫──╫──╫──┘ ╚═══════════════════╪════════════╗
start v │ ║ ║ ║│ ╚══════════════════════╗ │ ║
║ │ ║ ╔══╝ ╚╪══════════╗ ║ │ ║
┌──╫──────────────┐ ║ ┌──╫──────────────┐ ║ ┌──╫────────┐ ║
│ ║ ╔═════╗ │ ║ │ ║ ╔═════╗ │ ║ │ ║ ╔══╪══╗ ║
│┌─v─┐ ┌─^─┐ ┌─v─┐│┌─^─┐ │┌─v─┐ ┌─^─┐ ┌─v─┐│┌─^─┐ │┌─v─┐ ┌─^─┐│┌─v─┐ ║
││ 0 │ │ 1 │ │ 2 │││ 3 │ ││ 0 │ │ 1 │ │ 2 │││ 3 │ ││ 0 │ │ 1 │││ 2 >═╝
│└─v─┘ └─^─┘ └─v─┘│└─^─┘ │└─v─┘ └─^─┘ └─v─┘│└─^─┘ │└─v─┘ └─^─┘│└───┘
│ ╚═════╝ ╚══╪══╝ │ ╚═════╝ ╚══╪══╝ │ ╚═════╝ │
└─────────────────┘ └─────────────────┘ └───────────┘Sourcefn next_item_or_back_address(&self, addr: Address) -> Option<Address>
fn next_item_or_back_address(&self, addr: Address) -> Option<Address>
Get the next item address if any, or the next back address otherwise.
Sourcefn address_of<Q>(&self, key: &Q) -> Result<Address, Address>
fn address_of<Q>(&self, key: &Q) -> Result<Address, Address>
Get the address of the given key.
Returns Ok(addr) if the key is used in the tree.
If the key is not used in the tree then Err(addr) is returned,
where addr can be used to insert the missing key.
Sourcefn address_in<Q>(&self, id: usize, key: &Q) -> Result<Address, Address>
fn address_in<Q>(&self, id: usize, key: &Q) -> Result<Address, Address>
Search for the address of the given key from the given node id.
Users should directly use BTreeExt::address_of.
Dyn Compatibility§
This trait is not dyn compatible.
In older versions of Rust, dyn compatibility was called "object safety", so this trait is not object safe.