allocated_btree/
lib.rs

1//! B-Tree implementations using the _allocated_ pattern for explicit allocator control.
2//!
3//! This crate provides two B-Tree map implementations designed to demonstrate
4//! and compare memory usage patterns:
5//!
6//! - [`NaiveBTreeMap`] - A traditional B-Tree with uniform node structure
7//! - [`CompressedBTreeMap`] - An optimized B-Tree using ~30% less memory
8//!
9//! # Quick Start
10//!
11//! ```
12//! use allocated_btree::CompressedBTreeMap;
13//!
14//! let mut map = CompressedBTreeMap::new();
15//! map.insert(1, "one")?;
16//! map.insert(2, "two")?;
17//! map.insert(3, "three")?;
18//!
19//! assert_eq!(map.get(&2), Some(&"two"));
20//! assert_eq!(map.len(), 3);
21//! # Ok::<(), allocated::AllocErrorWithLayout>(())
22//! ```
23//!
24//! # Which Implementation to Use?
25//!
26//! **Use [`CompressedBTreeMap`]** (recommended) for:
27//! - Production use where memory efficiency matters
28//! - Large datasets where the ~30% memory savings are significant
29//! - General-purpose ordered map needs
30//!
31//! **Use [`NaiveBTreeMap`]** for:
32//! - Learning about B-Tree internals (simpler implementation)
33//! - Comparing memory usage patterns
34//! - Debugging and testing
35//!
36//! # The Allocated Pattern
37//!
38//! This crate follows the _allocated_ pattern, providing two types per implementation:
39//!
40//! ## Wrapper Types (Recommended)
41//!
42//! - [`NaiveBTreeMap<K, V, B, A>`] - Owns allocator, safe API
43//! - [`CompressedBTreeMap<K, V, B, A>`] - Owns allocator, safe API
44//!
45//! These are ergonomic wrappers that own their allocator and provide safe methods:
46//!
47//! ```
48//! use allocated_btree::NaiveBTreeMap;
49//!
50//! let mut map = NaiveBTreeMap::new();
51//! map.insert(42, "answer")?;  // No unsafe blocks needed!
52//! # Ok::<(), allocated::AllocErrorWithLayout>(())
53//! ```
54//!
55//! ## Allocated Types (Advanced)
56//!
57//! - [`AllocatedNaiveBTreeMap<K, V, B>`] - Low-level, requires manual allocator passing
58//! - [`AllocatedCompressedBTreeMap<K, V, B>`] - Low-level, requires manual allocator passing
59//!
60//! These are for building composite data structures or when you need fine control:
61//!
62//! ```
63//! use allocated_btree::AllocatedNaiveBTreeMap;
64//! use allocated::CountingAllocator;
65//!
66//! let alloc = CountingAllocator::default();
67//! let mut map = AllocatedNaiveBTreeMap::<u32, String>::new_in(&alloc)?;
68//!
69//! unsafe {
70//!     map.insert_in(&alloc, 1, "one".to_string())?;
71//! }
72//!
73//! // Track memory usage
74//! println!("Allocations: {}", alloc.n_allocations());
75//! # Ok::<(), allocated::AllocErrorWithLayout>(())
76//! ```
77//!
78//! # Memory Comparison
79//!
80//! The compressed implementation achieves ~30% memory savings by using specialized
81//! node types:
82//!
83//! - **Leaf nodes**: Store only keys and values (no child pointers)
84//! - **Interior nodes**: Store keys, values, and child pointers
85//!
86//! The naive implementation uses a single node type with child pointers always
87//! allocated, even for leaf nodes.
88//!
89//! See `examples/memory-comparison.rs` for a detailed comparison across different
90//! dataset sizes.
91
92#![no_std]
93#![deny(unsafe_op_in_unsafe_fn)]
94
95#[cfg(any(feature = "std", test))]
96extern crate std;
97
98extern crate alloc;
99
100/// Naive B-Tree implementation using a uniform node structure.
101///
102/// This module provides [`btree::AllocatedBTreeMap`] and its wrapper
103/// [`btree::NaiveBTreeMap`]. All nodes in this implementation use the same
104/// structure regardless of whether they are leaf or interior nodes.
105pub mod btree;
106mod common;
107/// Compressed B-Tree implementation using specialized node types.
108///
109/// This module provides [`compressed::AllocatedBTreeMap`] and its wrapper
110/// [`compressed::CompressedBTreeMap`]. This implementation uses ~30% less
111/// memory than the naive variant by using different structures for leaf and interior nodes.
112pub mod compressed;
113
114// Re-export allocated types for advanced use cases
115pub use btree::AllocatedBTreeMap as AllocatedNaiveBTreeMap;
116pub use compressed::AllocatedBTreeMap as AllocatedCompressedBTreeMap;
117
118// Re-export wrapper types (recommended for most use cases)
119pub use btree::NaiveBTreeMap;
120pub use compressed::CompressedBTreeMap;
allocated_btree/lib.rs

allocated_btree/
lib.rs
