Struct Address 

pub struct Address<T> {
    pub node: T,
    pub offset: Offset,
}

Item/entry location in a BTreeMap.

Each item in a B-Tree is addressed by a node identifier and an offset in the node. We write @id:offset the address of the item contained in the node id at offset offset.

                                  ┌────────────────┐
                                  │ node 0      ┌──┼─── this item address is `@0:1`
                                  │┌────────┐ ┌─v─┐│
                       ┌───────── ││ item 0 │ │ 1 ││ ──────────┐
                       │          │└────────┘ └───┘│           │
                       │          └────────────────┘           │
                       │                   │                   │
              ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
              │ node 1          │ │ node 2          │ │ node 3          │
              │┌───┐ ┌───┐ ┌───┐│ │┌───┐ ┌───┐ ┌───┐│ │┌───┐ ┌───┐ ┌───┐│
              ││ 0 │ │ 1 │ │ 2 ││ ││ 0 │ │ 1 │ │ 2 ││ ││ 0 │ │ 1 │ │ 2 ││
              │└─^─┘ └───┘ └───┘│ │└───┘ └───┘ └─^─┘│ │└───┘ └───┘ └───┘│
              └──┼──────────────┘ └──────────────┼──┘ └─────────────────┘
                 └─ this item address is `@1:0`  └─ this item address is `@2:2`

Validity

An item adress addr is valid in a given BTreeMap if it addr.id refers to an existing node and if addr.offset is comprised between -1 and the number of items in the node (included). We say that addr is occupied if it points to an actual item (addr.offset at least 0 and less than the number of items in the node).

The following diagram shows all the valid address in a B-Tree.

                                            ┌───────────┐
                                            │ node 0    │
                                       ┌───┐│┌───┐ ┌───┐│┌───┐
                  ┌────────────────────│-1 │││ 0 │ │ 1 │││ 2 │─────────────────┐
                  │                    └───┘│└───┘ └───┘│└───┘                 │
                  │                         └───────────┘                      │
                  │                               │                            │
         ┌─────────────────┐             ┌─────────────────┐             ┌───────────┐
         │ node 1          │             │ node 2          │             │ node 3    │    
    ┌───┐│┌───┐ ┌───┐ ┌───┐│┌───┐   ┌───┐│┌───┐ ┌───┐ ┌───┐│┌───┐   ┌───┐│┌───┐ ┌───┐│┌───┐
    │-1 │││ 0 │ │ 1 │ │ 2 │││ 3 │   │-1 │││ 0 │ │ 1 │ │ 2 │││ 3 │   │-1 │││ 0 │ │ 1 │││ 2 │
    └───┘│└───┘ └───┘ └───┘│└───┘   └───┘│└───┘ └───┘ └───┘│└───┘   └───┘│└───┘ └───┘│└───┘
         └─────────────────┘             └─────────────────┘             └───────────┘

Note how some valid addresses are outside of nodes bounds. Even is thoses addresses do not refers to any items, they can be useful to operate on the tree.

Back addresses

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 all the back addresses in a node.

                       ┌───────────┄┄┄┄┄───────┐      
                       │ node i                │       
                       │┌───┐ ┌───┐     ┌─────┐│┌───┐  where `n` is
                       ││ 0 │ │ 1 │ ... │ n-1 │││ n │  the number of items in the node.
                       │└───┘ └───┘     └─────┘│└───┘  
                       └───────────┄┄┄┄┄───────┘   

Note that an address with offset -1 is not a back address.

Front addresses

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 all the front addresses in a node.

                            ┌───────────┄┄┄┄┄───────┐      
                            │ node i                │       
                       ┌───┐│┌───┐ ┌───┐     ┌─────┐│  where `n` is
                       │-1 │││ 0 │ │ 1 │ ... │ n-1 ││  the number of items in the node.
                       └───┘│└───┘ └───┘     └─────┘│  
                            └───────────┄┄┄┄┄───────┘   

Note that an address with offset n is not a front address.

Safety

It is not safe to use an address addr in which addr.id is not the identifier of any node currently used by the tree.

Fields

node: T

Identifier of the node.

offset: Offset

Offset in the node.

Implementations

impl<T> Address<T>

pub fn new(id: T, offset: Offset) -> Address<T>

Creates a new address from the identifier of the node and the offset in the node.

Trait Implementations

impl<T: Clone> Clone for Address<T>

fn clone(&self) -> Address<T>

Returns a duplicate of the value.

fn clone_from(&mut self, source: &Self)

Performs copy-assignment from source.

impl<T: Debug> Debug for Address<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: Display> Display for Address<T>

fn fmt(&self, f: &mut Formatter<'_>) -> Result

Formats the value using the given formatter.

impl<T: PartialEq> PartialEq for Address<T>

fn eq(&self, other: &Address<T>) -> bool

Tests for self and other values to be equal, and is used by ==.

fn ne(&self, other: &Rhs) -> bool

Tests for !=. The default implementation is almost always sufficient, and should not be overridden without very good reason.

impl<T: Copy> Copy for Address<T>

impl<T: Eq> Eq for Address<T>

impl<T> StructuralPartialEq for Address<T>