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

//! Root and layer-root creation helpers.

use std::sync::atomic::{AtomicPtr, Ordering as AtomicOrdering};

use crate::TreeAllocator;
use crate::internode::InternodeNode;
use crate::leaf15::LeafNode15;
use crate::policy::LeafPolicy;

/// Unit struct namespace for root creation operations.
pub struct RootCreation;

impl RootCreation {
    // =========================================================================
    // Main Tree Root Creation
    // =========================================================================

    /// Create a new main tree root internode from two leaves.
    ///
    /// Atomically installs a new root via store on `root_ptr`. Parent pointers
    /// are updated after the store to avoid dangling references.
    pub fn create_root_from_leaves<P, A>(
        root_ptr: &AtomicPtr<u8>,
        allocator: &A,
        left_leaf_ptr: *mut LeafNode15<P>,
        right_leaf_ptr: *mut LeafNode15<P>,
        split_ikey: u64,
    ) -> *mut InternodeNode
    where
        P: LeafPolicy,
        A: TreeAllocator<P>,
    {
        let new_root_ptr: *mut u8 = allocator.alloc_internode_direct_root(0);
        let new_root: &InternodeNode = unsafe { &*new_root_ptr.cast::<InternodeNode>() };

        new_root.set_child(0, left_leaf_ptr.cast());
        new_root.set_ikey(0, split_ikey);
        new_root.set_child(1, right_leaf_ptr.cast());
        new_root.set_nkeys(1);

        root_ptr.store(new_root_ptr, AtomicOrdering::Release);

        // SAFETY: Both leaves are valid and locked (left by caller, right split-locked).
        unsafe {
            (*left_leaf_ptr).set_parent(new_root_ptr);
            (*right_leaf_ptr).set_parent(new_root_ptr);
            (*left_leaf_ptr).version().mark_nonroot();
        }

        new_root_ptr.cast()
    }

    /// Create a new main tree root internode from two internodes.
    pub fn create_root_from_internodes<P, A>(
        root_ptr: &AtomicPtr<u8>,
        allocator: &A,
        left_inode_ptr: *mut InternodeNode,
        right_inode_ptr: *mut InternodeNode,
        split_ikey: u64,
    ) -> *mut InternodeNode
    where
        P: LeafPolicy,
        A: TreeAllocator<P>,
    {
        let left: &InternodeNode = unsafe { &*left_inode_ptr };

        let new_root_ptr: *mut u8 = allocator.alloc_internode_direct_root(left.height() + 1);
        let new_root: &InternodeNode = unsafe { &*new_root_ptr.cast::<InternodeNode>() };

        new_root.set_child(0, left_inode_ptr.cast());
        new_root.set_ikey(0, split_ikey);
        new_root.set_child(1, right_inode_ptr.cast());
        new_root.set_nkeys(1);

        root_ptr.store(new_root_ptr, AtomicOrdering::Release);

        // SAFETY: Both internodes are valid and locked (left by caller, right split-locked).
        unsafe {
            (*left_inode_ptr).set_parent(new_root_ptr);
            (*right_inode_ptr).set_parent(new_root_ptr);
            (*left_inode_ptr).version().mark_nonroot();
        }

        new_root_ptr.cast()
    }

    // =========================================================================
    // Layer Root Creation
    // =========================================================================

    /// Promote a layer root leaf to a new layer internode.
    pub fn promote_layer_root_leaves<P, A>(
        allocator: &A,
        left_leaf_ptr: *mut LeafNode15<P>,
        right_leaf_ptr: *mut LeafNode15<P>,
        split_ikey: u64,
    ) -> *mut InternodeNode
    where
        P: LeafPolicy,
        A: TreeAllocator<P>,
    {
        let new_inode_ptr: *mut u8 = allocator.alloc_internode_direct_root(0);
        let new_inode: &InternodeNode = unsafe { &*new_inode_ptr.cast::<InternodeNode>() };

        new_inode.set_child(0, left_leaf_ptr.cast());
        new_inode.set_ikey(0, split_ikey);
        new_inode.set_child(1, right_leaf_ptr.cast());
        new_inode.set_nkeys(1);

        // SAFETY: Both leaves are valid and locked (left by caller, right split-locked).
        // set_parent uses Release ordering internally.
        unsafe {
            (*left_leaf_ptr).set_parent(new_inode_ptr);
            (*right_leaf_ptr).set_parent(new_inode_ptr);
            (*left_leaf_ptr).version().mark_nonroot();
            (*right_leaf_ptr).version().mark_nonroot();
        }

        new_inode_ptr.cast()
    }

    /// Promote a layer root internode to a new layer internode.
    pub fn promote_layer_root_internodes<P, A>(
        allocator: &A,
        left_inode_ptr: *mut InternodeNode,
        right_inode_ptr: *mut InternodeNode,
        split_ikey: u64,
    ) -> *mut InternodeNode
    where
        P: LeafPolicy,
        A: TreeAllocator<P>,
    {
        let left: &InternodeNode = unsafe { &*left_inode_ptr };

        let new_inode_ptr: *mut u8 = allocator.alloc_internode_direct_root(left.height() + 1);
        let new_inode: &InternodeNode = unsafe { &*new_inode_ptr.cast::<InternodeNode>() };

        new_inode.set_child(0, left_inode_ptr.cast());
        new_inode.set_ikey(0, split_ikey);
        new_inode.set_child(1, right_inode_ptr.cast());
        new_inode.set_nkeys(1);

        // SAFETY: Both internodes are valid and locked (left by caller, right split-locked).
        // set_parent uses Release ordering internally.
        unsafe {
            (*left_inode_ptr).set_parent(new_inode_ptr);
            (*right_inode_ptr).set_parent(new_inode_ptr);
            (*left_inode_ptr).version().mark_nonroot();
        }

        new_inode_ptr.cast()
    }
}