tether_map/
lib.rs

1#![doc = include_str!("../README.md")]
2#![cfg_attr(not(feature = "std"), no_std)]
3#![deny(missing_docs)]
4
5mod arena;
6pub mod linked_hash_map;
7
8use core::num::NonZeroU32;
9
10pub use linked_hash_map::CursorMut;
11pub use linked_hash_map::Entry;
12pub use linked_hash_map::IntoIter;
13pub use linked_hash_map::Iter;
14pub use linked_hash_map::OccupiedEntry;
15pub use linked_hash_map::VacantEntry;
16
17extern crate alloc;
18
19#[cfg(feature = "std")]
20type RandomState = std::hash::RandomState;
21#[cfg(not(feature = "std"))]
22type RandomState = hashbrown::DefaultHashBuilder;
23
24/// A hash map that maintains the relative order of entries, implemented as a
25/// doubly-linked list backed by a hash table for O(1) lookups.
26///
27/// This is the main type alias using the default hasher. For custom hashers,
28/// use [`linked_hash_map::LinkedHashMap`] directly.
29///
30/// # Examples
31///
32/// ```
33/// use tether_map::LinkedHashMap;
34///
35/// let mut map = LinkedHashMap::new();
36/// map.insert("a", 1);
37/// map.insert("b", 2);
38///
39/// // Maintains relative order
40/// let entries: Vec<_> = map.iter().collect();
41/// assert_eq!(entries, [(&"a", &1), (&"b", &2)]);
42/// ```
43pub type LinkedHashMap<K, V> = crate::linked_hash_map::LinkedHashMap<K, V, RandomState>;
44
45#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
46/// A pointer type used to identify entries in the linked hash map.
47///
48/// This is an opaque handle that can be used to directly access entries
49/// without key lookup. It provides O(1) access to entries.
50///
51/// By default, `Ptr` is **non-generational**, meaning that once an entry is
52/// removed, the pointer may be re-used for a new entry. With the `generational`
53/// feature enabled, `Ptr` includes generation tracking that will panic or
54/// return None when attempting to use a stale pointer after its entry has been
55/// removed.
56///
57/// # Examples
58///
59/// ```
60/// # #[cfg(not(feature = "generational"))] {
61/// use tether_map::Entry;
62/// use tether_map::LinkedHashMap;
63/// use tether_map::Ptr;
64///
65/// let mut map = LinkedHashMap::new();
66/// let ptr = match map.entry("key") {
67///     Entry::Vacant(entry) => entry.insert_tail(42).0,
68///     Entry::Occupied(entry) => entry.ptr(),
69/// };
70///
71/// // Use the pointer for direct access
72/// assert_eq!(map.ptr_get(ptr), Some(&42));
73///
74/// // Remove the entry
75/// map.remove(&"key");
76///
77/// // Using the stale pointer is a logic error but will not panic
78/// assert_eq!(map.ptr_get(ptr), None);
79///
80/// // Insert a new entry, which may reuse the same Ptr value
81/// map.insert("key", 100);
82///
83/// // The old pointer is stale, but may point to the new entry by coincidence
84/// // This may work or not depending on whether the same Ptr value was reused:
85/// // assert_eq!(map.ptr_get(ptr), Some(100));
86///
87/// # }
88/// ```
89///
90/// With the `generational` feature enabled, using a stale pointer will return
91/// None or panic:
92///
93/// ```
94/// # #[cfg(feature = "generational")] {
95/// use tether_map::Entry;
96/// use tether_map::LinkedHashMap;
97/// use tether_map::Ptr;
98///
99/// let mut map = LinkedHashMap::new();
100/// let ptr = match map.entry("key") {
101///     Entry::Vacant(entry) => entry.insert_tail(42).0,
102///     Entry::Occupied(entry) => entry.ptr(),
103/// };
104///
105/// // Remove the entry
106/// map.remove(&"key");
107///
108/// // Using the stale pointer will return None or panic
109/// assert_eq!(map.ptr_get(ptr), None);
110///
111/// // Insert a new entry, which may reuse the same Ptr value
112/// map.insert("key", 100);
113/// // The old pointer is stale, so this will definitely return None
114/// assert_eq!(map.ptr_get(ptr), None);
115///
116/// # }
117/// ```
118pub struct Ptr {
119    inner: NonZeroU32,
120    #[cfg(feature = "generational")]
121    generation: u32,
122}
123
124impl core::fmt::Debug for Ptr {
125    fn fmt(
126        &self,
127        f: &mut core::fmt::Formatter<'_>,
128    ) -> core::fmt::Result {
129        #[cfg(not(feature = "generational"))]
130        {
131            write!(f, "Ptr({})", self.inner.get() - 1)
132        }
133        #[cfg(feature = "generational")]
134        write!(f, "Ptr({}@{})", self.inner.get() - 1, self.generation)
135    }
136}
137
138impl Ptr {
139    pub(crate) fn unchecked_from(
140        index: usize,
141        #[cfg(feature = "generational")] generation: u32,
142    ) -> Self {
143        debug_assert!(
144            index < u32::MAX as usize,
145            "Index too large to fit in Ptr: {index}"
146        );
147        Ptr {
148            inner: NonZeroU32::new((index as u32).saturating_add(1)).unwrap(),
149            #[cfg(feature = "generational")]
150            generation,
151        }
152    }
153
154    pub(crate) fn unchecked_get(self) -> usize {
155        self.inner.get() as usize - 1
156    }
157}
tether_map/lib.rs

tether_map/
lib.rs
