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
//! A vector whose logical contents use lazily allocated fixed-size pages.
//!
//! [`PagedVec`] has a logical value at every index below [`PagedVec::len`], but
//! only allocates physical storage for a page after that page receives a value
//! different from the configured [`PagedVec::default_value`]. Unallocated pages
//! logically contain the default value.
//!
//! The collection is **not contiguous**. It deliberately does not implement
//! slice conversion, range indexing, or mutable indexing. Those APIs would
//! either misrepresent its layout or allow callers to bypass the bookkeeping
//! required to reclaim default-only pages. Use [`PagedVec::set`],
//! [`PagedVec::reset`], or [`PagedVec::update`] for mutation.
//!
//! [`PagedVec::iter`] visits every logical value, including defaults supplied
//! by unallocated pages. [`PagedVec::non_default_iter`] visits only logical
//! values that differ from the default, while [`PagedVec::allocated_pages`]
//! visits only physical page storage. These are deliberately different views:
//! an allocated page can contain default-valued slots.
//!
//! The logical length can change through [`PagedVec::push`], [`PagedVec::pop`],
//! [`PagedVec::resize`], [`PagedVec::truncate`], and [`PagedVec::clear`].
//! Growing uses the configured default value, so it usually adds only dense
//! page-table metadata rather than physical data pages. [`PagedVec::reset_all`]
//! instead preserves the length while restoring every slot to that default.
//!
//! The current backend uses a dense `Vec<Option<Page<T>>>` page table. Page
//! data is allocated lazily, but page-table metadata is proportional to
//! `ceil(len / page_size)`. It is therefore best suited to workloads where
//! page data dominates page-table overhead; it does not use constant memory
//! for an enormous logical length.
//!
//! # `no_std` support
//!
//! The ordinary build enables `std`:
//!
//! ```toml
//! [dependencies]
//! pagedvector = "0.2"
//! ```
//!
//! `PagedVec` also supports `no_std` environments with the [`alloc`] crate:
//!
//! ```toml
//! [dependencies]
//! pagedvector = { version = "0.2", default-features = false }
//! ```
//!
//! Enable `serde` without `std` with:
//!
//! ```toml
//! [dependencies]
//! pagedvector = { version = "0.2", default-features = false, features = ["serde"] }
//! ```
//!
//! The `bincode` feature is also available without `std`. The final application
//! must provide a compatible global allocator and, where applicable, a panic
//! handler. `PagedVec` cannot support allocator-free `core`-only targets
//! because it owns a page table and page storage. `no_std + alloc` does not
//! change the dense page table's proportional metadata cost.
//!
//! # Example
//!
//! ```
//! use pagedvector::PagedVec;
//!
//! let mut values = PagedVec::new(1_000, 0_u32, 64);
//! assert_eq!(values.get(42), Some(&0));
//! assert_eq!(values.allocated_page_count(), 0);
//!
//! values.set(42, 100).unwrap();
//! assert_eq!(values[42], 100);
//! assert_eq!(values.non_default_len(), 1);
//!
//! values.reset(42).unwrap();
//! assert_eq!(values.allocated_page_count(), 0);
//! ```
//!
//! # Read-only views
//!
//! ```
//! use pagedvector::PagedVec;
//!
//! let values = PagedVec::from_vec(vec![0, 5, 0, 7, 0], 0, 4)?;
//!
//! assert_eq!(values.iter().copied().collect::<Vec<_>>(), vec![0, 5, 0, 7, 0]);
//! assert_eq!(
//! values
//! .non_default_iter()
//! .map(|(index, value)| (index, *value))
//! .collect::<Vec<_>>(),
//! vec![(1, 5), (3, 7)],
//! );
//! assert_eq!(values.allocated_pages().count(), 1);
//! assert_eq!(values.to_vec(), vec![0, 5, 0, 7, 0]);
//! # Ok::<(), pagedvector::PagedVecError>(())
//! ```
//!
//! # Changing length
//!
//! ```
//! use pagedvector::PagedVec;
//!
//! let mut values = PagedVec::new(0, 0_i32, 4);
//! values.resize(1_000_000);
//! assert_eq!(values.allocated_page_count(), 0);
//!
//! values.push(7);
//! assert_eq!(values.pop(), Some(7));
//! values.truncate(4);
//! values.reset_all(); // keeps four logical default-valued slots
//! values.clear(); // removes every logical slot
//! ```
extern crate alloc;
extern crate std;
pub use crate;
pub use crate;
pub use cratePagedVec;