pagedvector

pagedvector provides PagedVec<T>, a vector whose logical contents are split into lazily allocated fixed-size pages. A page is allocated only after one of its values differs from a configured default value.

The crate has an invariant-safe core, read-only collection ergonomics, and controlled dynamic-length operations. It is useful when page data dominates metadata and most logical values have a common default. It is not a drop-in Vec<T> replacement and does not claim to use constant memory for a very large logical length.

Storage model

Every in-bounds logical index has a value:

• an unallocated page logically contains only the configured default;
• an allocated page owns concrete storage for exactly its logical number of slots;
• the final page is partial when len is not divisible by page_size;
• a page is deallocated as soon as all of its values return to the default.

The current backend has a dense Vec<Option<Page<T>>> page table. Therefore page data is lazy, while page-table metadata remains proportional to ceil(len / page_size). For an extremely large logical length with few writes, that metadata can still be substantial. A sparse page-map backend is a future performance investigation, not a property of this release.

PagedVec is non-contiguous. It intentionally does not implement range slices, Deref<Target = [T]>, AsRef<[T]>, or Borrow<[T]>.

no_std and allocation

The default feature set enables std. The core library also supports no_std + alloc when default features are disabled:

[dependencies]
pagedvector = { version = "0.2", default-features = false }

The final application supplies the global allocator and, where needed, its panic handler. PagedVec cannot work in allocator-free core-only programs: it owns a dense page table and page storage. Disabling std does not make that metadata bounded; the page table remains proportional to ceil(len / page_size).

Serialization also works without std when its corresponding feature is enabled:

[dependencies]
pagedvector = { version = "0.2", default-features = false, features = ["serde"] }
# Or: features = ["bincode"]

The crate's feature graph is intentionally small:

• std (default) enables standard-library integration, including std::error::Error implementations and optional dependency std support;
• serde enables Serde with alloc support;
• bincode enables Serde plus bincode's alloc support.

Safe core API

use pagedvector::PagedVec;

let mut values = PagedVec::new(1_000_000, 0_u32, 1_024);

assert_eq!(values.len(), 1_000_000);
assert_eq!(values.get(42), Some(&0));
assert_eq!(values.allocated_page_count(), 0);

values.set(42, 100)?;
assert_eq!(values[42], 100);
assert_eq!(values.non_default_len(), 1);

values.reset(42)?;
assert_eq!(values.allocated_page_count(), 0);
# Ok::<(), pagedvector::IndexOutOfBounds>(())

get follows normal collection conventions: it returns None for an out-of-bounds index. Index<usize> is also available and panics out of bounds. For in-bounds indices in unallocated pages, both return the configured default.

Mutation is controlled through set, reset, and update:

• set(index, value) and reset(index) return Result<(), IndexOutOfBounds>;
• update(index, f) invokes f on a detached copy and commits only when the closure returns normally, so a panicking closure leaves the vector unchanged;
• no safe API returns &mut T or &mut [T], because such references could bypass the counters required to reclaim pages.

The most relevant inspection methods are page_size, page_count, allocated_page_count, non_default_len, default_value, page_index, page_offset, and allocated_page. allocated_page exposes only concrete physical storage; it does not manufacture a default-filled slice for an unallocated page.

Read-only collection ergonomics

PagedVec exposes three intentionally different read-only views:

1. Logical values exist at every in-bounds index. iter (and IntoIterator for &PagedVec) visits all of them.
2. Non-default values are the logical values unequal to default_value. non_default_iter yields their index and reference.
3. Allocated pages are concrete physical storage. allocated_pages and allocated_page_indices visit only those pages. An allocated page can still contain some default-valued slots.

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()
        .map(|(index, page)| (index, page.to_vec()))
        .collect::<Vec<_>>(),
    vec![(0, vec![0, 5, 0, 7])],
);
assert_eq!(values.to_vec(), vec![0, 5, 0, 7, 0]);
# Ok::<(), pagedvector::PagedVecError>(())

is_page_allocated(page_index) distinguishes an invalid page index from a valid but unallocated page. is_allocated(index) does the same for logical indices, but Some(true) only says the containing page is physical—it does not mean the exact value is non-default.

from_vec accepts explicit default and page-size policies, and to_vec / into_vec materialize the logical sequence. The materialization methods clone values because unallocated slots share one configured default value.

Dynamic length

PagedVec can grow and shrink without compromising its sparse page accounting:

• push(value) appends one value, allocating physical storage only if the resulting page contains a non-default value;
• pop() removes and returns the final value, cloning the configured default when that final slot was unallocated;
• resize(new_len) shrinks or grows using the configured default, unlike Vec::resize, which accepts an explicit fill value;
• truncate(new_len) only shrinks and is a no-op when new_len >= len();
• clear() drops all logical values and changes the length to zero;
• reset_all() keeps the length but restores every logical slot to the default and releases every physical page;
• Extend<T> appends an iterator by applying push to each item.

Growing with default-valued slots does not allocate data pages, although it can grow the dense page table. If an allocated partial final page is extended, resize clones the existing values and configured default into replacement storage before committing the new length. This gives resize a strong guarantee for clone panics: the vector is unchanged. push first grows the logical extent and then stores the new value, so a later panic while storing that value can leave a canonical, newly appended default-valued slot.

clear, reset_all, and truncate commit their new canonical metadata before dropping detached page storage. A panic from T::Drop can therefore propagate, but does not restore stale pages or counters. Extend<T> is repeated push, so iteration or element panics can leave the already appended prefix present.

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.extend([0, 3, 0, 4, 0]);
values.push(5);
assert_eq!(values.to_vec(), vec![0, 3, 0, 4, 0, 5]);
assert_eq!(values.pop(), Some(5));

values.truncate(3);
values.reset_all();
assert_eq!(values.to_vec(), vec![0, 0, 0]);
values.clear();
assert!(values.is_empty());

Invariants

The implementation maintains these canonical rules after every safe mutation:

1. page size is non-zero;
2. logical indices are valid only below len;
3. unallocated pages logically contain only the default;
4. every allocated page has at least one non-default value;
5. each page counter exactly equals its number of non-default values;
6. a page with a zero counter is immediately deallocated;
7. page-table length is ceil(len / page_size);
8. allocated page storage has exactly its logical length, including a partial final page;
9. the global non-default counter equals the sum of page counters.

Debug builds check these invariants after every mutation. The test suite also checks them after every operation in a randomized model test.

Construction and serialization

PagedVec::new panics when page_size is zero. Use try_new with fallible input; it returns PagedVecError::ZeroPageSize.

Serialization is opt-in:

[dependencies]
pagedvector = { version = "0.2", features = ["serde"] }

The bincode feature enables the optional bincode dependency in addition to serde. Serialization uses a private, versioned representation of logical fields and page values, never trusted page or global counters. Deserialization validates page sizes, page count, and page lengths; it recounts values and normalizes default-only pages. The representation is not yet a stable wire format.

Equality compares logical length, the configured default, and every logical value. It ignores page size and physical allocation layout; therefore vectors with matching logical contents can compare equal with different page sizes. Vectors with different configured defaults compare unequal even if all current logical values match.

0.2 breaking changes

This release removes get_mut, get_page_slice_mut, IndexMut, and all page-slice/range-slice APIs. It also replaces the panicking get with Option<&T>, renames page-count methods, makes set fallible, and makes serde dependencies optional. See CHANGELOG.md for the complete list.

Roadmap

The roadmap is staged deliberately; none of these items are promises of a specific release date.

1. Invariant-safe core — safe access, set/reset, canonical counters, correct final-page sizing, tests, CI. Implemented.
2. Read-only ergonomics — iteration, non-default iteration, allocated-page iteration, contains, materialization, and logical equality documentation. Implemented.
3. Dynamic length — push, pop, resize, truncate, clear, reset_all, and extend. Implemented.
4. Controlled mutation — richer closure updates, an entry API, mutation guards, and transformations, only where bookkeeping remains reliable.
5. Serialization stability — compatibility policy, versioned format tests, and documented support guarantees.
6. Performance and backends — benchmarks and comparison of the dense page table with sparse page-map backends.

iter_mut, IndexMut, arbitrary range slices, and slice-deref conversions are not roadmap goals because they conflict with the accounting or layout model.

Development checks

CI runs on stable Rust and executes:

cargo fmt --all -- --check
cargo clippy --all-targets --all-features -- -D warnings
cargo check
cargo check --all-features
cargo check --no-default-features
cargo check --no-default-features --features serde
cargo check --no-default-features --features bincode
cargo check --features serde
cargo check --features bincode
cargo check --examples --all-features
cargo test --all-features
cargo test --no-default-features
cargo test --features serde
cargo test --features bincode
cargo test --doc --all-features
cargo doc --no-deps --all-features
cargo package

The MSRV is Rust 1.85. CI checks the no-default-feature library and test suite on that toolchain, while stable CI additionally checks no_std + alloc on the host and thumbv7em-none-eabi target.

License

Licensed under either of MIT or Apache-2.0, at your option.