osom_lib_btree/btree/
inspect.rs

1//! This module holds various helpers for inspecting the internal structure of the B-tree.
2
3use crate::btree::node_ptr::BTreeNodePtr;
4
5use super::{BTree, BTreeConfig};
6
7/// Returns the maximum number of key-value pairs that a single node can hold.
8/// This is an odd number.
9#[inline(always)]
10#[must_use]
11pub const fn get_max_kvp_count<TKey, TValue, TConfig>(_: &BTree<TKey, TValue, TConfig>) -> usize
12where
13    TKey: Ord,
14    TConfig: BTreeConfig,
15{
16    TConfig::CHILDREN_COUNT - 1
17}
18
19/// Returns the minimum number of key-value pairs that a single node can hold.
20/// This is typically half of the maximum number of key-value pairs.
21#[inline(always)]
22#[must_use]
23pub const fn get_min_kvp_count<TKey, TValue, TConfig>(_: &BTree<TKey, TValue, TConfig>) -> usize
24where
25    TKey: Ord,
26    TConfig: BTreeConfig,
27{
28    (TConfig::CHILDREN_COUNT - 1) / 2
29}
30
31/// Returns the height of the B-tree.
32///
33/// Note: this function scans the entire tree recursively.
34#[must_use]
35pub fn get_height<TKey, TValue, TConfig>(btree: &BTree<TKey, TValue, TConfig>) -> usize
36where
37    TKey: Ord,
38    TConfig: BTreeConfig,
39{
40    if btree.data.is_null() {
41        return 0;
42    }
43
44    get_height_recursive(btree.data)
45}
46
47fn get_height_recursive<TKey, TValue, TConfig>(node: BTreeNodePtr<TKey, TValue, TConfig>) -> usize
48where
49    TKey: Ord,
50    TConfig: BTreeConfig,
51{
52    unsafe {
53        let mut current_height = 1;
54
55        if node.is_leaf() {
56            return current_height;
57        }
58
59        for index in 0..=node.len() {
60            let child = node.children_ptr().add(index).read();
61            if child.is_null() {
62                continue;
63            }
64            let height = get_height_recursive(child);
65            if height > current_height {
66                current_height = height;
67            }
68        }
69
70        current_height + 1
71    }
72}
73
74/// Calculates the memory usage of the B-tree. Note that it does not inspect keys and values
75/// internally. Meaning that if they store pointers internally, the memory they point to is not included.
76///
77/// The memory usage is calculated by summing the allocated memory size of each internal node.
78///
79/// It also does not include the memory usage of the `btree` struct itself,
80/// i.e. `size_of(btree)` is not included.
81#[must_use]
82pub fn calculate_memory_usage<TKey, TValue, TConfig>(btree: &BTree<TKey, TValue, TConfig>) -> usize
83where
84    TKey: Ord,
85    TConfig: BTreeConfig,
86{
87    if btree.data.is_null() {
88        return 0;
89    }
90
91    calculate_memory_usage_recursive(btree.data)
92}
93
94fn calculate_memory_usage_recursive<TKey, TValue, TConfig>(node: BTreeNodePtr<TKey, TValue, TConfig>) -> usize
95where
96    TKey: Ord,
97    TConfig: BTreeConfig,
98{
99    let mut current_size = node.memory_layout().size();
100    unsafe {
101        if !node.is_leaf() {
102            for index in 0..=node.len() {
103                let child = node.children_ptr().add(index).read();
104                if child.is_null() {
105                    continue;
106                }
107                current_size += calculate_memory_usage_recursive(child);
108            }
109        }
110    }
111
112    current_size
113}
osom_lib_btree/btree/inspect.rs

osom_lib_btree/btree/
inspect.rs
