ropey/tree/
mod.rs

1mod node;
2mod node_children;
3mod node_text;
4mod text_info;
5
6pub(crate) use self::node::Node;
7pub(crate) use self::node_children::NodeChildren;
8pub(crate) use self::node_text::NodeText;
9pub(crate) use self::text_info::TextInfo;
10
11// Type used for storing tree metadata, such as byte and char length.
12pub(crate) type Count = u64;
13
14// Real constants used in release builds.
15#[cfg(not(any(test, feature = "small_chunks")))]
16mod constants {
17    use super::{Node, TextInfo};
18    use smallvec::SmallVec;
19    use std::{
20        mem::{align_of, size_of},
21        sync::Arc,
22    };
23
24    // Because stdlib's max is not const for some reason.
25    // TODO: replace with stdlib max once it's const.
26    const fn cmax(a: usize, b: usize) -> usize {
27        if a > b {
28            a
29        } else {
30            b
31        }
32    }
33
34    // Aim for Node + Arc counters to be 1024 bytes.  Keeping the nodes
35    // multiples of large powers of two makes it easier for the memory
36    // allocator to avoid fragmentation.
37    const TARGET_TOTAL_SIZE: usize = 1024;
38
39    // Space that the strong and weak Arc counters take up in `ArcInner`.
40    const ARC_COUNTERS_SIZE: usize = size_of::<std::sync::atomic::AtomicUsize>() * 2;
41
42    // Misc useful info that we need below.
43    const NODE_CHILDREN_ALIGN: usize = cmax(align_of::<Arc<u8>>(), align_of::<TextInfo>());
44    const NODE_TEXT_ALIGN: usize = align_of::<SmallVec<[u8; 16]>>();
45    const START_OFFSET: usize = {
46        const NODE_INNER_ALIGN: usize = cmax(NODE_CHILDREN_ALIGN, NODE_TEXT_ALIGN);
47        // The +NODE_INNER_ALIGN is because of Node's enum discriminant.
48        ARC_COUNTERS_SIZE + NODE_INNER_ALIGN
49    };
50
51    // Node maximums.
52    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
53    pub const MAX_CHILDREN: usize = {
54        let node_list_align = align_of::<Arc<u8>>();
55        let info_list_align = align_of::<TextInfo>();
56        let field_gap = if node_list_align >= info_list_align {
57            0
58        } else {
59            // This is over-conservative, because in reality it depends
60            // on the number of elements.  But handling that is probably
61            // more complexity than it's worth.
62            info_list_align - node_list_align
63        };
64
65        // The -NODE_CHILDREN_ALIGN is for the `len` field in `NodeChildrenInternal`.
66        let target_size = TARGET_TOTAL_SIZE - START_OFFSET - NODE_CHILDREN_ALIGN - field_gap;
67
68        target_size / (size_of::<Arc<u8>>() + size_of::<TextInfo>())
69    };
70    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
71    pub const MAX_BYTES: usize = {
72        let smallvec_overhead = size_of::<SmallVec<[u8; 16]>>() - 16;
73        TARGET_TOTAL_SIZE - START_OFFSET - smallvec_overhead
74    };
75
76    // Node minimums.
77    // Note: MIN_BYTES is intentionally a little smaller than half
78    // MAX_BYTES, to give a little wiggle room when on the edge of
79    // merging/splitting.
80    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
81    pub const MIN_CHILDREN: usize = MAX_CHILDREN / 2;
82    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
83    pub const MIN_BYTES: usize = (MAX_BYTES / 2) - (MAX_BYTES / 32);
84
85    // Compile-time assertion.
86    const _: () = {
87        assert!(
88            (ARC_COUNTERS_SIZE + size_of::<Node>()) == TARGET_TOTAL_SIZE,
89            "`Node` is not the target size in memory.",
90        );
91    };
92}
93
94// Smaller constants used in debug builds.  These are different from release
95// in order to trigger deeper trees without having to use huge text data in
96// the tests.
97#[cfg(any(test, feature = "small_chunks"))]
98mod test_constants {
99    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
100    pub const MAX_CHILDREN: usize = 5;
101    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
102    pub const MIN_CHILDREN: usize = MAX_CHILDREN / 2;
103
104    // MAX_BYTES must be >= 4 to allow for 4-byte utf8 characters.
105    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
106    pub const MAX_BYTES: usize = 9; // Note: can't be 8, because 3-byte characters.
107    #[doc(hidden)] // NOT PART OF THE PUBLIC API!
108    pub const MIN_BYTES: usize = (MAX_BYTES / 2) - (MAX_BYTES / 32);
109}
110
111#[cfg(not(any(test, feature = "small_chunks")))]
112pub use self::constants::{MAX_BYTES, MAX_CHILDREN, MIN_BYTES, MIN_CHILDREN};
113
114#[cfg(any(test, feature = "small_chunks"))]
115pub use self::test_constants::{MAX_BYTES, MAX_CHILDREN, MIN_BYTES, MIN_CHILDREN};
ropey/tree/mod.rs

ropey/tree/
mod.rs
