linked_hash_table/
lib.rs

1//! # LinkedHashMap
2//!
3//! A hash map that maintains **insertion order** and supports efficient
4//! O(1) push/pop from both the **front** and the **back**, similar to `VecDeque`.
5//!
6//! ## Design
7//!
8//! Each key-value pair lives in a heap-allocated node. The nodes form a
9//! doubly-linked list that tracks insertion order. A `HashMap<K, NonNull<Node<K, V>>>`
10//! gives O(1) lookup by key. Because all node pointers are owned by the map and the
11//! `HashMap` only stores raw pointers (never moves the pointed-to memory), pointer
12//! stability is guaranteed as long as the map is alive and the entry is not removed.
13//!
14//! ```text
15//!  head ⟷ node_A ⟷ node_B ⟷ node_C ⟷ tail   (sentinel nodes)
16//!            ↑           ↑           ↑
17//!        HashMap entries (key -> *mut Node)
18//! ```
19//!
20//! The `head` and `tail` fields are **sentinel** nodes that never hold real data.
21//! Their `key` / `value` are never read; they merely anchor the list so that
22//! every "real" node always has both a `prev` and a `next`, eliminating many
23//! `Option` branches in the hot path.
24//!
25//! ## Ordering contract
26//!
27//! [`LinkedHashMap::insert_back`] and [`LinkedHashMap::insert_front`] **preserve
28//! the position** of an existing key: only the value is updated in-place. Use
29//! [`LinkedHashMap::move_to_back`] / [`LinkedHashMap::move_to_front`] to
30//! explicitly reorder an entry.
31
32pub mod iter;
33mod map;
34pub(crate) mod node;
35#[cfg(feature = "serde")]
36mod serde_impl;
37mod set;
38
39pub use iter::{Drain, IntoIter, Iter, IterMut, Keys, Values, ValuesMut};
40pub use map::{Entry, LinkedHashMap, OccupiedEntry, VacantEntry};
41pub use set::{LinkedHashSet, SetDrain, SetIntoIter, SetIter};
42
43#[cfg(test)]
44mod tests;
linked_hash_table/lib.rs

linked_hash_table/
lib.rs
