jonaskruckenberg.de
this repo has no description
1//! Stack used for mutable tree operations that records a path through the tree.
2
3use core::marker::PhantomData;
4use core::ops::{Index, IndexMut};
5
6use crate::node::{MAX_POOL_SIZE, NodePos, node_layout};
7use crate::{NodeRef, RangeTreeInteger};
8
9/// Returns the worst case maximum height for a tree with pivot `I`.
10#[inline]
11pub(crate) const fn max_height<I: RangeTreeInteger>() -> usize {
12 // Get the maximum possible number of leaf nodes, assuming an empty `V`.
13 //
14 // `NodePool` stores offsets in a u32 and therefore the total pool size
15 // cannot exceed `u32::MAX`.
16 let mut nodes = MAX_POOL_SIZE / node_layout::<I, ()>().0.size();
17 let mut height = 0;
18
19 // If there are multiple nodes at this height then we need another level
20 // above it.
21 while nodes > 1 {
22 height += 1;
23
24 // If there are less than B nodes then we just need a single root node
25 // above it which will never get split.
26 if nodes < I::B {
27 break;
28 }
29
30 // Otherwise assume a worst case with all internal nodes being half-full.
31 nodes = nodes.div_ceil(I::B / 2);
32 }
33
34 height
35}
36
37/// A height in the tree.
38///
39/// This has the invariant of always being less than `max_height::<I>()`, which
40/// allows safe unchecked indexing in a stack.
41#[derive(Clone, Copy, Debug, Default)]
42pub(crate) struct Height<I: RangeTreeInteger> {
43 height: usize,
44 marker: PhantomData<fn() -> I>,
45}
46
47impl<I: RangeTreeInteger> PartialEq for Height<I> {
48 fn eq(&self, other: &Self) -> bool {
49 self.height == other.height
50 }
51}
52
53impl<I: RangeTreeInteger> Eq for Height<I> {}
54
55impl<I: RangeTreeInteger> Height<I> {
56 /// Returns the height for leaf nodes.
57 pub(crate) const LEAF: Self = Self {
58 height: 0,
59 marker: PhantomData,
60 };
61
62 /// Returns the maximum possible height for a tree.
63 pub(crate) const MAX: Self = Self {
64 height: max_height::<I>(),
65 marker: PhantomData,
66 };
67
68 /// Returns one level down (towards the leaves).
69 #[inline]
70 pub(crate) const fn down(self) -> Option<Self> {
71 if self.height == 0 {
72 None
73 } else {
74 Some(Self {
75 height: self.height - 1,
76 marker: PhantomData,
77 })
78 }
79 }
80
81 /// Returns one level up (towards the root) up to the given maximum height.
82 #[inline]
83 pub(crate) const fn up(self, max: Height<I>) -> Option<Self> {
84 if self.height >= max.height {
85 None
86 } else {
87 Some(Self {
88 height: self.height + 1,
89 marker: PhantomData,
90 })
91 }
92 }
93}
94
95/// Stack which holds the path to a leaf node from the root of the tree.
96///
97/// The is large enough to hold `max_height::<I>()`, which depends on the branching
98/// factor and the node size.
99///
100/// The stack is indexed with `Height` which allows unchecked indexing since
101/// all heights must be less than `max_height::<I>()`.
102#[derive(Clone)]
103pub(crate) struct Stack<I: RangeTreeInteger, const H: usize> {
104 entries: [(NodeRef, NodePos<I>); H],
105}
106
107impl<I: RangeTreeInteger, const H: usize> Default for Stack<I, H> {
108 #[inline]
109 fn default() -> Self {
110 Self {
111 // The values here don't matter and zero initialization is slightly
112 // faster.
113 entries: [(NodeRef::ZERO, NodePos::ZERO); H],
114 }
115 }
116}
117
118impl<I: RangeTreeInteger, const H: usize> Index<Height<I>> for Stack<I, H> {
119 type Output = (NodeRef, NodePos<I>);
120
121 #[inline]
122 fn index(&self, index: Height<I>) -> &Self::Output {
123 const { assert!(H == max_height::<I>()) };
124 // Safety: `Height` is always `< max_height::<I>()`
125 unsafe { self.entries.get_unchecked(index.height) }
126 }
127}
128
129impl<I: RangeTreeInteger, const H: usize> IndexMut<Height<I>> for Stack<I, H> {
130 #[inline]
131 fn index_mut(&mut self, index: Height<I>) -> &mut Self::Output {
132 const { assert!(H == max_height::<I>()) };
133 // Safety: `Height` is always `< max_height::<I>()`
134 unsafe { self.entries.get_unchecked_mut(index.height) }
135 }
136}