masstree 0.9.5

A high-performance concurrent ordered map (trie of B+trees)
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160

//! Unit tests for [`LeafNode15`] methods.

use super::LeafNode15;
use crate::leaf15::{MODSTATE_DELETED_LAYER, MODSTATE_EMPTY, MODSTATE_INSERT, MODSTATE_REMOVE};
use crate::policy::BoxPolicy;

// ========================================================================
//  Adaptive Prefetch Tests
// ========================================================================

#[test]
fn test_prefetch_adaptive() {
    let leaf: Box<LeafNode15<BoxPolicy<u64>>> = LeafNode15::new_boxed();

    // Test all size ranges - these should not panic or crash
    leaf.prefetch_for_search_adaptive(0);
    leaf.prefetch_for_search_adaptive(4);
    leaf.prefetch_for_search_adaptive(8);
    leaf.prefetch_for_search_adaptive(12);
    leaf.prefetch_for_search_adaptive(15);
}

#[test]
fn test_prefetch_for_search() {
    let leaf: Box<LeafNode15<BoxPolicy<u64>>> = LeafNode15::new_boxed();

    // Should not panic or crash
    leaf.prefetch_for_search();
}

#[test]
fn test_prefetch_adaptive_empty_node() {
    let leaf: Box<LeafNode15<BoxPolicy<u64>>> = LeafNode15::new_boxed();

    // For empty nodes, adaptive prefetch should skip CL 2-3
    // This is purely a "doesn't crash" test - we can't verify
    // that the CPU honored the prefetch hint
    assert_eq!(leaf.size(), 0);
    leaf.prefetch_for_search_adaptive(0);
}

#[test]
fn test_prefetch_adaptive_small_node() {
    let leaf: Box<LeafNode15<BoxPolicy<u64>>> = LeafNode15::new_boxed();

    // For size <= 8, adaptive prefetch should skip CL 3
    // Test boundary conditions
    leaf.prefetch_for_search_adaptive(1);
    leaf.prefetch_for_search_adaptive(7);
    leaf.prefetch_for_search_adaptive(8);
}

#[test]
fn test_prefetch_adaptive_large_node() {
    let leaf: Box<LeafNode15<BoxPolicy<u64>>> = LeafNode15::new_boxed();

    // For size > 8, adaptive prefetch should include CL 3
    leaf.prefetch_for_search_adaptive(9);
    leaf.prefetch_for_search_adaptive(14);
    leaf.prefetch_for_search_adaptive(15);
}

// ========================================================================
//  Modstate Queued Bit Masking Tests
// ========================================================================

type TestLeaf = LeafNode15<BoxPolicy<u64>>;

#[test]
fn test_modstate_queued_bit_lifecycle() {
    let leaf: Box<TestLeaf> = LeafNode15::new_boxed();

    // Initial state: INSERT, not queued.
    assert!(!leaf.is_queued());
    assert!(!leaf.is_empty_state());
    assert!(!leaf.is_removing());
    assert!(!leaf.deleted_layer());

    // Mark queued. First call returns true (was not queued).
    assert!(leaf.try_mark_queued());
    assert!(leaf.is_queued());
    // Second call returns false (already queued).
    assert!(!leaf.try_mark_queued());
    assert!(leaf.is_queued());

    // Lifecycle checks still work with queued bit set.
    assert!(!leaf.is_empty_state());
    assert!(!leaf.is_removing());
    assert!(!leaf.deleted_layer());
}

#[test]
fn test_modstate_transitions_preserve_queued_bit() {
    let leaf: Box<TestLeaf> = LeafNode15::new_boxed();

    // Set queued bit first.
    assert!(leaf.try_mark_queued());

    // REMOVE transition preserves queued.
    leaf.mark_remove();
    assert!(leaf.is_removing());
    assert!(leaf.is_queued());

    // EMPTY transition preserves queued.
    leaf.mark_empty();
    assert!(leaf.is_empty_state());
    assert!(leaf.is_queued());
    assert!(!leaf.is_removing());

    // DELETED_LAYER transition preserves queued.
    leaf.mark_deleted_layer();
    assert!(leaf.deleted_layer());
    assert!(leaf.is_queued());
    assert!(!leaf.is_empty_state());
}

#[test]
fn test_modstate_clear_empty_clears_queued() {
    let leaf: Box<TestLeaf> = LeafNode15::new_boxed();

    leaf.mark_empty();
    assert!(leaf.try_mark_queued());
    assert!(leaf.is_queued());
    assert!(leaf.is_empty_state());

    // clear_empty_state stores MODSTATE_INSERT (0), clearing queued bit.
    leaf.clear_empty_state();
    assert!(!leaf.is_queued());
    assert!(!leaf.is_empty_state());
}

#[test]
fn test_modstate_clear_queued_preserves_value() {
    let leaf: Box<TestLeaf> = LeafNode15::new_boxed();

    leaf.mark_empty();
    assert!(leaf.try_mark_queued());
    assert!(leaf.is_empty_state());
    assert!(leaf.is_queued());

    // clear_queued only strips the bit, value unchanged.
    leaf.clear_queued();
    assert!(!leaf.is_queued());
    assert!(leaf.is_empty_state());
}

#[test]
fn test_modstate_value_constants() {
    // Verify constants don't overlap with queued bit.
    assert_eq!(MODSTATE_INSERT & 0x04, 0);
    assert_eq!(MODSTATE_REMOVE & 0x04, 0);
    assert_eq!(MODSTATE_DELETED_LAYER & 0x04, 0);
    assert_eq!(MODSTATE_EMPTY & 0x04, 0);

    // Verify all values fit in 2 bits.
    const { assert!(MODSTATE_INSERT < 4) };
    const { assert!(MODSTATE_REMOVE < 4) };
    const { assert!(MODSTATE_DELETED_LAYER < 4) };
    const { assert!(MODSTATE_EMPTY < 4) };
}