btree_slab/generic/node/addr.rs
1use super::Offset;
2use std::fmt;
3
4/// Item/entry location in a BTreeMap.
5///
6/// Each item in a B-Tree is addressed by a node identifier and an offset in the node.
7/// We write `@id:offset` the address of the item contained in the node `id` at offset `offset`.
8///
9/// ```text
10/// ┌────────────────┐
11/// │ node 0 ┌──┼─── this item address is `@0:1`
12/// │┌────────┐ ┌─v─┐│
13/// ┌───────── ││ item 0 │ │ 1 ││ ──────────┐
14/// │ │└────────┘ └───┘│ │
15/// │ └────────────────┘ │
16/// │ │ │
17/// ┌─────────────────┐ ┌─────────────────┐ ┌─────────────────┐
18/// │ node 1 │ │ node 2 │ │ node 3 │
19/// │┌───┐ ┌───┐ ┌───┐│ │┌───┐ ┌───┐ ┌───┐│ │┌───┐ ┌───┐ ┌───┐│
20/// ││ 0 │ │ 1 │ │ 2 ││ ││ 0 │ │ 1 │ │ 2 ││ ││ 0 │ │ 1 │ │ 2 ││
21/// │└─^─┘ └───┘ └───┘│ │└───┘ └───┘ └─^─┘│ │└───┘ └───┘ └───┘│
22/// └──┼──────────────┘ └──────────────┼──┘ └─────────────────┘
23/// └─ this item address is `@1:0` └─ this item address is `@2:2`
24/// ```
25///
26/// ## Validity
27/// An item adress `addr` is *valid* in a given BTreeMap if it `addr.id` refers to an existing
28/// node and if `addr.offset` is comprised between `-1` and the number of items in the node (included).
29/// We say that `addr` is *occupied* if it points to an actual item
30/// (`addr.offset` at least 0 and less than the number of items in the node).
31///
32/// The following diagram shows all the valid address in a B-Tree.
33/// ```text
34/// ┌───────────┐
35/// │ node 0 │
36/// ┌───┐│┌───┐ ┌───┐│┌───┐
37/// ┌────────────────────│-1 │││ 0 │ │ 1 │││ 2 │─────────────────┐
38/// │ └───┘│└───┘ └───┘│└───┘ │
39/// │ └───────────┘ │
40/// │ │ │
41/// ┌─────────────────┐ ┌─────────────────┐ ┌───────────┐
42/// │ node 1 │ │ node 2 │ │ node 3 │
43/// ┌───┐│┌───┐ ┌───┐ ┌───┐│┌───┐ ┌───┐│┌───┐ ┌───┐ ┌───┐│┌───┐ ┌───┐│┌───┐ ┌───┐│┌───┐
44/// │-1 │││ 0 │ │ 1 │ │ 2 │││ 3 │ │-1 │││ 0 │ │ 1 │ │ 2 │││ 3 │ │-1 │││ 0 │ │ 1 │││ 2 │
45/// └───┘│└───┘ └───┘ └───┘│└───┘ └───┘│└───┘ └───┘ └───┘│└───┘ └───┘│└───┘ └───┘│└───┘
46/// └─────────────────┘ └─────────────────┘ └───────────┘
47/// ```
48/// Note how some valid addresses are outside of nodes bounds.
49/// Even is thoses addresses do not refers to any items,
50/// they can be useful to operate on the tree.
51///
52/// ### Back addresses
53///
54/// A "back address" is a valid address whose offset is at least `0`.
55/// If `addr.offset` is equal to the number of items in the node then it doesn't actually refer
56/// to an existing item in the node,
57/// but it can be used to insert a new item with `BTreeExt::insert_at`.
58///
59/// The following diagram shows all the back addresses in a node.
60/// ```text
61/// ┌───────────┄┄┄┄┄───────┐
62/// │ node i │
63/// │┌───┐ ┌───┐ ┌─────┐│┌───┐ where `n` is
64/// ││ 0 │ │ 1 │ ... │ n-1 │││ n │ the number of items in the node.
65/// │└───┘ └───┘ └─────┘│└───┘
66/// └───────────┄┄┄┄┄───────┘
67/// ```
68/// Note that an address with offset `-1` is *not* a back address.
69///
70/// ### Front addresses
71///
72/// A "front address" is a valid address whose offset is less that the number of items in the node.
73/// If `addr.offset` is equal to `-1`, then it doesn't actually refer to an existing item in the node.
74///
75/// The following diagram shows all the front addresses in a node.
76/// ```text
77/// ┌───────────┄┄┄┄┄───────┐
78/// │ node i │
79/// ┌───┐│┌───┐ ┌───┐ ┌─────┐│ where `n` is
80/// │-1 │││ 0 │ │ 1 │ ... │ n-1 ││ the number of items in the node.
81/// └───┘│└───┘ └───┘ └─────┘│
82/// └───────────┄┄┄┄┄───────┘
83/// ```
84/// Note that an address with offset `n` is *not* a front address.
85///
86/// ## Safety
87/// It is not safe to use an address `addr` in which `addr.id` is not the identifier of any node
88/// currently used by the tree.
89#[derive(Clone, Copy, PartialEq, Eq)]
90pub struct Address {
91 /// Identifier of the node.
92 pub id: usize,
93
94 /// Offset in the node.
95 pub offset: Offset,
96}
97
98impl Address {
99 /// Creates a new address from the identifier of the node and the offset in the node.
100 #[inline]
101 pub fn new(id: usize, offset: Offset) -> Address {
102 Address { id, offset }
103 }
104
105 /// Address in the empty tree.
106 ///
107 /// This is the unique valid address address in an ampty tree.
108 /// It is only valid in the empty tree.
109 #[inline]
110 pub fn nowhere() -> Address {
111 Address {
112 id: std::usize::MAX,
113 offset: 0.into(),
114 }
115 }
116
117 /// Checks if the address is nowhere.
118 #[inline]
119 pub fn is_nowhere(&self) -> bool {
120 self.id == std::usize::MAX
121 }
122}
123
124impl fmt::Display for Address {
125 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
126 write!(f, "@{}:{}", self.id, self.offset)
127 }
128}
129
130impl fmt::Debug for Address {
131 fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
132 write!(f, "@{}:{}", self.id, self.offset)
133 }
134}