Trait Storage

pub unsafe trait Storage<T>: Default {
    type Node: Copy + PartialEq + Debug;
    type Dropper: Dropper<T, Self>;

    // Required methods
    fn allocate_node(&mut self, node: Node<T, Self>) -> Self::Node;
    unsafe fn release_node(&mut self, id: Self::Node) -> Node<T, Self>;
    fn start_dropping(&self) -> Option<Self::Dropper>;
    unsafe fn get(&self, id: Self::Node) -> &Node<T, Self>;
    unsafe fn get_mut(&mut self, id: Self::Node) -> &mut Node<T, Self>;

    // Provided methods
    unsafe fn insert_node(&mut self, node: Node<T, Self>) -> Self::Node { ... }
    unsafe fn normalize(
        &self,
        addr: Address<Self::Node>,
    ) -> Option<Address<Self::Node>> { ... }
    unsafe fn leaf_address(
        &self,
        addr: Address<Self::Node>,
    ) -> Address<Self::Node> { ... }
    unsafe fn previous_item_address(
        &self,
        addr: Address<Self::Node>,
    ) -> Option<Address<Self::Node>> { ... }
    unsafe fn previous_front_address(
        &self,
        addr: Address<Self::Node>,
    ) -> Option<Address<Self::Node>> { ... }
    unsafe fn next_item_address(
        &self,
        addr: Address<Self::Node>,
    ) -> Option<Address<Self::Node>> { ... }
    unsafe fn next_back_address(
        &self,
        addr: Address<Self::Node>,
    ) -> Option<Address<Self::Node>> { ... }
    unsafe fn next_item_or_back_address(
        &self,
        addr: Address<Self::Node>,
    ) -> Option<Address<Self::Node>> { ... }
    unsafe fn address_in<Q: ?Sized>(
        &self,
        id: Self::Node,
        cmp: impl Fn(&T, &Q) -> Ordering,
        key: &Q,
    ) -> Result<Address<Self::Node>, Address<Self::Node>> { ... }
    unsafe fn insert_at(
        &mut self,
        root: Option<Self::Node>,
        addr: Option<Address<Self::Node>>,
        item: T,
    ) -> (Option<Self::Node>, Option<Address<Self::Node>>) { ... }
    unsafe fn insert_exactly_at(
        &mut self,
        root: Option<Self::Node>,
        addr: Option<Address<Self::Node>>,
        item: T,
        opt_right_id: Option<Self::Node>,
    ) -> (Option<Self::Node>, Option<Address<Self::Node>>) { ... }
    unsafe fn replace_at(&mut self, addr: Address<Self::Node>, item: T) -> T { ... }
    unsafe fn remove_at(
        &mut self,
        root: Option<Self::Node>,
        addr: Address<Self::Node>,
    ) -> Option<RemovedItem<T, Self>> { ... }
    unsafe fn remove_rightmost_leaf_of(
        &mut self,
        id: Self::Node,
    ) -> (T, Self::Node) { ... }
}

BTree node storage.

Safety

An active identifier is a node identifier (Self::Node) that has been created using allocate_node (or insert_node) but not yet released using release_node or a Dropper (created with start_dropping).

• Default method implementations must not be overridden by the implementor.
• allocate_node must not return an active identifier. Once returned and until released using release_node, this identifier must always map to the same node through get and get_mut. We say that the identifier and node are “bound” together by the storage. The created node must live at least as long as its identifier is active and the storage is not dropped.
• release_node may only drop the node bound to the given identifier.
• start_dropping creates a dropper for this storage.
• get must return the node bound to the given identifier.
• get_mut must return the node bound to the given identifier.

Required Associated Types

type Node: Copy + PartialEq + Debug

Node.

type Dropper: Dropper<T, Self>

Nodes dropper.

Required Methods

fn allocate_node(&mut self, node: Node<T, Self>) -> Self::Node

Allocates the given node.

unsafe fn release_node(&mut self, id: Self::Node) -> Node<T, Self>

Safety

Input node must not have been deallocated.

fn start_dropping(&self) -> Option<Self::Dropper>

Creates a new dropper.

Returns None if no dropper is required to eventually drop all the nodes.

unsafe fn get(&self, id: Self::Node) -> &Node<T, Self>

Safety

Input node must not have been deallocated.

unsafe fn get_mut(&mut self, id: Self::Node) -> &mut Node<T, Self>

Safety

• Input node must not have been deallocated.
• Different id must map to non-aliased nodes.
• Must not be used to create more than one concurrent mutable reference to the same node.

Provided Methods

unsafe fn insert_node(&mut self, node: Node<T, Self>) -> Self::Node

Inserts the given node into the storage, setting the children parent.

Safety

The input node’s children must not have been deallocated.

unsafe fn normalize( &self, addr: Address<Self::Node>, ) -> Option<Address<Self::Node>>

Normalizes the given address.

Safety

Input address’s node must not have been deallocated.

unsafe fn leaf_address(&self, addr: Address<Self::Node>) -> Address<Self::Node>

Converts this arbitrary address into a leaf address.

Safety

Input address’s node must not have been deallocated.

unsafe fn previous_item_address( &self, addr: Address<Self::Node>, ) -> Option<Address<Self::Node>>

Get the address of the item located before this address.

Safety

Input address’s node must not have been deallocated.

unsafe fn previous_front_address( &self, addr: Address<Self::Node>, ) -> Option<Address<Self::Node>>

Returns the front address directly preceding the given address.

Safety

Input address’s node must not have been deallocated.

unsafe fn next_item_address( &self, addr: Address<Self::Node>, ) -> Option<Address<Self::Node>>

Get the address of the item located after this address if any.

Safety

Input address’s node must not have been deallocated.

unsafe fn next_back_address( &self, addr: Address<Self::Node>, ) -> Option<Address<Self::Node>>

Safety

Input address’s node must not have been deallocated.

unsafe fn next_item_or_back_address( &self, addr: Address<Self::Node>, ) -> Option<Address<Self::Node>>

Returns the item address or back address directly following the given address.

Safety

Input address’s node must not have been deallocated.

unsafe fn address_in<Q: ?Sized>( &self, id: Self::Node, cmp: impl Fn(&T, &Q) -> Ordering, key: &Q, ) -> Result<Address<Self::Node>, Address<Self::Node>>

Safety

Input node must not have been deallocated.

unsafe fn insert_at( &mut self, root: Option<Self::Node>, addr: Option<Address<Self::Node>>, item: T, ) -> (Option<Self::Node>, Option<Address<Self::Node>>)

Inserts the item at the given address.

Safety

Input nodes must not have been deallocated.

unsafe fn insert_exactly_at( &mut self, root: Option<Self::Node>, addr: Option<Address<Self::Node>>, item: T, opt_right_id: Option<Self::Node>, ) -> (Option<Self::Node>, Option<Address<Self::Node>>)

Inserts the given item exactly at the provided leaf address.

Safety

Input nodes must not have been deallocated.

unsafe fn replace_at(&mut self, addr: Address<Self::Node>, item: T) -> T

Replaces the item located at the given address.

Safety

Input address’s node must not have been deallocated.

unsafe fn remove_at( &mut self, root: Option<Self::Node>, addr: Address<Self::Node>, ) -> Option<RemovedItem<T, Self>>

Safety

Input nodes must not have been deallocated.

unsafe fn remove_rightmost_leaf_of(&mut self, id: Self::Node) -> (T, Self::Node)

Remove the rightmost leaf node under the given node.

Safety

Input node must not have been deallocated.

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.

Implementors

impl<T> Storage<T> for BoxStorage

type Node = BoxPtr<T>

type Dropper = BoxDrop