zigzag_alloc/collections/
mod.rs

1//! High-performance collections backed by explicit allocators.
2//!
3//! Unlike [`std::collections`], every type in this module:
4//!
5//! 1. **Never uses a global allocator.**  Each collection accepts an
6//!    [`Allocator`] reference at construction time and routes all allocations
7//!    through it.
8//! 2. **Provides SIMD-accelerated operations** (fill, search, copy) where
9//!    applicable via the internal `simd` module.
10//! 3. **Decouples data from logic** via *context traits*: hashing and ordering
11//!    are provided through [`HashContext`] and [`OrdContext`] rather than via
12//!    `Hash` / `Ord` bounds.  This allows domain-specific algorithms without
13//!    wrapper types.
14//!
15//! ## Collection Overview
16//!
17//! | Type | Description |
18//! |------|-------------|
19//! | [`ExVec<T>`] | Growable contiguous array |
20//! | [`ExBox<T>`] | Single heap-allocated value |
21//! | [`ExString`] | Growable UTF-8 string |
22//! | [`ExHashMap<K, V, C>`] | Swiss-table open-addressing hash map |
23//! | [`ExPriorityQueue<T, C>`] | Binary-heap priority queue |
24//! | [`ExBoundedArray<T, N>`] | Fixed-capacity stack-allocated array |
25//!
26//! [`Allocator`]: crate::alloc::allocator::Allocator
27
28pub mod vec;
29pub mod boxed;
30pub mod string;
31pub mod hash_map;
32pub mod priority_queue;
33pub mod bounded_array;
34
35pub use vec::ExVec;
36pub use boxed::ExBox;
37pub use string::ExString;
38pub use hash_map::ExHashMap;
39pub use priority_queue::ExPriorityQueue;
40pub use bounded_array::ExBoundedArray;
41
42/// Provides hashing and equality for keys of type `K`.
43///
44/// Implementors replace the standard `Hash` + `Eq` trait combination, allowing
45/// custom hash functions without needing newtype wrappers.
46///
47/// # Contract
48///
49/// * If `eq(a, b)` returns `true`, then `hash(a) == hash(b)` must also hold.
50/// * `eq` must be an equivalence relation (reflexive, symmetric, transitive).
51pub trait HashContext<K> {
52    /// Returns the 64-bit hash of `key`.
53    fn hash(&self, key: &K) -> u64;
54    /// Returns `true` if `a` and `b` should be considered equal keys.
55    fn eq(&self, a: &K, b: &K) -> bool;
56}
57
58/// Provides a total ordering for elements of type `T`.
59///
60/// Implementors replace the standard `Ord` / `PartialOrd` traits, enabling
61/// context-dependent orderings (e.g. reverse order, key-extracted order)
62/// without newtype wrappers.
63///
64/// # Contract
65///
66/// `less` must define a strict weak ordering:
67/// * Irreflexivity: `less(a, a)` is `false`.
68/// * Asymmetry: if `less(a, b)` then `!less(b, a)`.
69/// * Transitivity: if `less(a, b)` and `less(b, c)` then `less(a, c)`.
70pub trait OrdContext<T> {
71    /// Returns `true` if `a` should be ordered *before* `b`.
72    fn less(&self, a: &T, b: &T) -> bool;
73}
74
75/// [`HashContext<u64>`] using FNV-1a hashing.
76pub struct U64HashCtx;
77
78impl HashContext<u64> for U64HashCtx {
79    /// Hashes `k` using the FNV-1a algorithm over its little-endian bytes.
80    #[inline]
81    fn hash(&self, k: &u64) -> u64 {
82        let mut h: u64 = 0xcbf2_9ce4_8422_2325; // FNV offset basis
83        for b in k.to_le_bytes() {
84            h ^= b as u64;
85            h = h.wrapping_mul(0x0100_0000_01b3); // FNV prime
86        }
87        h
88    }
89    #[inline]
90    fn eq(&self, a: &u64, b: &u64) -> bool { a == b }
91}
92
93/// [`HashContext<usize>`] that delegates to [`U64HashCtx`].
94pub struct UsizeHashCtx;
95
96impl HashContext<usize> for UsizeHashCtx {
97    /// Hashes `k` by widening it to `u64` and delegating to [`U64HashCtx`].
98    #[inline]
99    fn hash(&self, k: &usize) -> u64 {
100        U64HashCtx.hash(&(*k as u64))
101    }
102    #[inline]
103    fn eq(&self, a: &usize, b: &usize) -> bool { a == b }
104}
105
106/// [`OrdContext<usize>`] that orders elements from smallest to largest
107/// (min-heap).
108pub struct UsizeMinCtx;
109
110impl OrdContext<usize> for UsizeMinCtx {
111    /// Returns `true` if `a < b`.
112    #[inline]
113    fn less(&self, a: &usize, b: &usize) -> bool { a < b }
114}
zigzag_alloc/collections/mod.rs

zigzag_alloc/collections/
mod.rs
