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
//! The B+-tree under the map and the set: a root, internal nodes and leaves
//! (`doc/03-decisions.md` D51, D52), on fixed-size, self-aligned node pages,
//! with keys and values in leaves, and separator keys in internal nodes, or
//! with inline keys, in leaves too (`doc/03-decisions.md` D9, D11, D12, D13,
//! D15, D17, D21, D29, D49).
//!
//! The tree stores each key once (D17): values live only in leaves, and a
//! separator keeps its value in the leaf right of it, as that leaf's head.
//! Its key moves up into an internal node; with inline keys, it stays in the
//! head beside its value, and the internal node keeps only its inline key
//! (D49). Nodes have no parent pointers: whatever goes back up keeps a node
//! stack from the root instead (D11).
//!
//! - [`node`] is the two kinds of node, each its own type: [`node::leaf`]
//! and [`node::internal`], with every operation on one node, and what
//! they are both made of: pages, their layouts, slot arrays, and the
//! inline keys they search (D18).
//! - [`root`] is the root and the tree that owns it ([`root::Tree`]): the root
//! page, with the root node and what the tree keeps for it in place of a
//! parent, its fences, as the bytes every key shares (D50, D52,
//! `node/root_page.rs`, `shared_prefix.rs`), and the last leaf an append
//! went to (D45). Every operation on a whole tree starts there.
//! - [`latched`] is a tree that threads share (`BBTreeMap`): the same
//! nodes with a latch word each (`node/latch.rs`), read optimistically
//! above the leaves (`node/optimistic.rs`) (D54), with the points where
//! Shuttle may switch its threads in tests (`interleaving.rs`).
//! - The rest of this module is the tree's operations, each in its own
//! feature's module. Node stacks from the root and the iterators' walks
//! along them (`node_stack.rs`, `walk.rs`), and searches that need no node
//! stack (`search.rs`). Changes along a node stack: `insert.rs`,
//! `remove.rs`, `cut.rs`, which cuts a tree in two, and `join.rs`, which
//! joins two. Whole trees at once: `build.rs`, from entries in order,
//! `clone.rs` and `teardown.rs`. The prefixes nodes strip, which their
//! fences decide (`prefix.rs`). And checks and views of a tree:
//! `invariants.rs`, `inspect.rs`, and `test_support.rs` for tests.
//!
//! A node handle is a page pointer, which carries no access of its own; the
//! code that holds one keeps the contracts `tree/node/mod.rs` lists. The
//! types keep safety only where the code is stable: the borrow types of
//! node stacks and walks, which hand out each entry once (`node_stack.rs`,
//! `walk.rs`), and the slot arrays and page allocation under the nodes.
//! `unsafe` code is in the node modules that touch pages or erase types
//! (`node/mod.rs`, `page.rs`, `slots.rs`, `leaf.rs`, `internal.rs`,
//! `root_page.rs`, `siblings.rs`, `inline_key_search.rs`, `vector_count.rs`,
//! `type_identity.rs`, `optimistic.rs`), and in `root.rs`, `node_stack.rs`,
//! `search.rs`, `walk.rs`, `batch.rs` and `latched/`, where a contract the
//! type system doesn't check is relied on.
//! Every other module is `#![forbid(unsafe_code)]`. What only the tree
//! uses, such as making a node handle from a pointer, is
//! `pub(in crate::tree)`; the map and the set see the rest.
pub
pub
pub
pub
pub
pub
pub
pub
pub