btree_plus_store/copyable/
map.rs

1use crate::BTreeStore;
2use std::borrow::Borrow;
3use std::cmp::Ordering;
4use std::fmt::{Debug, Formatter};
5use std::hash::{Hash, Hasher};
6use std::marker::PhantomData;
7use std::mem::{size_of, transmute, MaybeUninit};
8use std::ops::{Deref, RangeBounds};
9
10/// A copyable, immutable b-tree map, which doesn't drop its contents.
11pub struct BTreeMap<'store, K, V> {
12    inner: RawBTreeMap<'store, K, V>,
13}
14
15pub type Iter<'a, K, V> = crate::map::Iter<'a, K, V>;
16pub type Keys<'a, K, V> = crate::map::Keys<'a, K, V>;
17pub type Values<'a, K, V> = crate::map::Values<'a, K, V>;
18pub type Range<'a, K, V> = crate::map::Range<'a, K, V>;
19
20impl<'store, K, V> From<crate::BTreeMap<'store, K, V>> for BTreeMap<'store, K, V> {
21    /// Creates a copyable map from a non-copyable map. Afterwards, the map is no longer mutable and
22    /// will no longer drop its contents.
23    #[inline]
24    fn from(inner: crate::BTreeMap<'store, K, V>) -> Self {
25        Self {
26            inner: RawBTreeMap::from(inner),
27        }
28    }
29}
30
31impl<'store, K, V> BTreeMap<'store, K, V> {
32    // region length
33    /// Returns the number of elements in the map.
34    #[inline]
35    pub fn len(&self) -> usize {
36        self.inner.len()
37    }
38
39    /// Returns `true` if the map contains no elements.
40    #[inline]
41    pub fn is_empty(&self) -> bool {
42        self.inner.is_empty()
43    }
44    // endregion
45
46    // region retrieval
47    /// Whether the map contains the key
48    #[inline]
49    pub fn contains_key<Q: Ord>(&self, key: &Q) -> bool
50    where
51        K: Borrow<Q>,
52    {
53        self.inner.contains_key(key)
54    }
55
56    /// Returns a reference to the value corresponding to the key.
57    #[inline]
58    pub fn get<Q: Ord>(&self, key: &Q) -> Option<&V>
59    where
60        K: Borrow<Q>,
61    {
62        self.inner.get(key)
63    }
64
65    /// Returns a reference to the equivalent key
66    ///
67    /// This is (only) useful when `Q` is a different type than `K`.
68    #[inline]
69    pub fn get_key<Q: Ord>(&self, key: &Q) -> Option<&K>
70    where
71        K: Borrow<Q>,
72    {
73        self.inner.get_key(key)
74    }
75
76    /// Returns a reference to the equivalent key and associated value
77    ///
78    /// This is (only) useful when `Q` is a different type than `K`.
79    #[inline]
80    pub fn get_key_value<Q: Ord>(&self, key: &Q) -> Option<(&K, &V)>
81    where
82        K: Borrow<Q>,
83    {
84        self.inner.get_key_value(key)
85    }
86
87    /// Returns the first key and value
88    #[inline]
89    pub fn first_key_value(&self) -> Option<(&K, &V)> {
90        self.inner.first_key_value()
91    }
92
93    /// Returns the last key and value
94    #[inline]
95    pub fn last_key_value(&self) -> Option<(&K, &V)> {
96        self.inner.last_key_value()
97    }
98    // endregion
99
100    // region advanced
101    /// Validates the map, *panic*ing if it is invalid. Specifically, we check that the number of
102    /// entries in each node is within the b-tree invariant bounds, and that the keys are in order.
103    ///
104    /// Ideally, this should always be a no-op.
105    #[inline]
106    pub fn validate(&self)
107    where
108        K: Debug + Ord,
109        V: Debug,
110    {
111        self.inner.validate()
112    }
113
114    /// Prints the b-tree in ascii
115    #[inline]
116    pub fn print(&self, f: &mut Formatter<'_>) -> std::fmt::Result
117    where
118        K: Debug,
119        V: Debug,
120    {
121        self.inner.print(f)
122    }
123    // endregion
124
125    // region iteration
126    /// Iterates over the map's key-value pairs in order.
127    #[inline]
128    pub fn iter(&self) -> Iter<'_, K, V> {
129        self.inner.iter()
130    }
131
132    /// Iterates over the map's keys in order.
133    #[inline]
134    pub fn keys(&self) -> Keys<'_, K, V> {
135        self.inner.keys()
136    }
137
138    /// Iterates over the map's values in order.
139    #[inline]
140    pub fn values(&self) -> Values<'_, K, V> {
141        self.inner.values()
142    }
143
144    /// Iterates over the map's key-value pairs in order, within the given range.
145    #[inline]
146    pub fn range<Q: Ord>(&self, bounds: impl RangeBounds<Q>) -> Range<'_, K, V>
147    where
148        K: Borrow<Q>,
149    {
150        self.inner.range(bounds)
151    }
152
153    /// Iterates over the map's keys in order, within the given range.
154    #[inline]
155    pub fn range_keys<Q: Ord>(&self, bounds: impl RangeBounds<Q>) -> impl Iterator<Item = &K> + '_
156    where
157        K: Borrow<Q>,
158    {
159        self.inner.range_keys(bounds)
160    }
161
162    /// Iterates over the map's values in order, within the given range.
163    #[inline]
164    pub fn range_values<Q: Ord>(&self, bounds: impl RangeBounds<Q>) -> impl Iterator<Item = &V> + '_
165    where
166        K: Borrow<Q>,
167    {
168        self.inner.range_values(bounds)
169    }
170}
171
172// region common trait impls
173impl<'store, K: Debug, V: Debug> Debug for BTreeMap<'store, K, V> {
174    #[inline]
175    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
176        self.inner.fmt(f)
177    }
178}
179
180impl<'store, K, V> Clone for BTreeMap<'store, K, V> {
181    #[inline]
182    fn clone(&self) -> Self {
183        // SAFETY: This is copy-able because:
184        // - All of the fields (all of `inner`'s fields) are copy-able
185        // - `inner` implements [Drop], but we wrapped it in [ManuallyDrop]
186        // - Most importantly, we only allow access to functions which access inner's indirect data
187        //   via shared references, which means we can safely create multiple copies which point to
188        //   the same indirect data.
189        *self
190    }
191}
192
193impl<'store, K, V> Copy for BTreeMap<'store, K, V> {}
194
195impl<'store, K: PartialEq, V: PartialEq> PartialEq for BTreeMap<'store, K, V> {
196    #[inline]
197    fn eq(&self, other: &Self) -> bool {
198        &*self.inner == &*other.inner
199    }
200
201    #[inline]
202    fn ne(&self, other: &Self) -> bool {
203        &*self.inner != &*other.inner
204    }
205}
206
207impl<'store, K: Eq, V: Eq> Eq for BTreeMap<'store, K, V> {}
208
209impl<'store, K: PartialOrd, V: PartialOrd> PartialOrd for BTreeMap<'store, K, V> {
210    #[inline]
211    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
212        self.inner.partial_cmp(&other.inner)
213    }
214}
215
216impl<'store, K: Ord, V: Ord> Ord for BTreeMap<'store, K, V> {
217    #[inline]
218    fn cmp(&self, other: &Self) -> Ordering {
219        self.inner.cmp(&other.inner)
220    }
221}
222
223impl<'store, K: Hash, V: Hash> Hash for BTreeMap<'store, K, V> {
224    #[inline]
225    fn hash<H: Hasher>(&self, state: &mut H) {
226        self.inner.hash(state)
227    }
228}
229// endregion
230
231// region RawBTreeMap
232/// [crate::BTreeMap] but as raw data so it can be [Copy]'d. Also doesn't run drop code.
233struct RawBTreeMap<'store, K, V> {
234    // generic parameters may not be used in const operations
235    // But fortunately [crate::BTreeMap]'s size doesn't depend on its generics, because everything
236    // is under an indirect pointer, and `K` and `V` are [Sized]
237    data: [MaybeUninit<u8>; size_of::<crate::BTreeMap<'static, (), ()>>()],
238    _p: PhantomData<(&'store K, &'store V)>,
239}
240
241impl<'store, K, V> From<crate::BTreeMap<'store, K, V>> for RawBTreeMap<'store, K, V> {
242    #[inline]
243    fn from(inner: crate::BTreeMap<'store, K, V>) -> Self {
244        Self {
245            data: unsafe { transmute(inner) },
246            _p: PhantomData,
247        }
248    }
249}
250
251impl<'store, K, V> Deref for RawBTreeMap<'store, K, V> {
252    type Target = crate::BTreeMap<'store, K, V>;
253
254    #[inline]
255    fn deref(&self) -> &Self::Target {
256        unsafe { &*(self.data.as_ptr() as *const crate::BTreeMap<'store, K, V>) }
257    }
258}
259
260impl<'store, K, V> Clone for RawBTreeMap<'store, K, V> {
261    #[inline]
262    fn clone(&self) -> Self {
263        Self {
264            data: self.data,
265            _p: PhantomData,
266        }
267    }
268}
269
270impl<'store, K, V> Copy for RawBTreeMap<'store, K, V> {}
271// endregion
272
273//noinspection DuplicatedCode
274// region iterator impls
275impl<'store: 'a, 'a, K, V> IntoIterator for &'a BTreeMap<'store, K, V> {
276    type Item = (&'a K, &'a V);
277    type IntoIter = Iter<'a, K, V>;
278
279    #[inline]
280    fn into_iter(self) -> Self::IntoIter {
281        self.iter()
282    }
283}
284// endregion
285
286impl<'store, K, V> crate::copyable::sealed::BTree<'store, K, V> for BTreeMap<'store, K, V> {
287    #[inline]
288    fn assert_store(&self, store: &BTreeStore<K, V>) {
289        self.inner.assert_store(store)
290    }
291
292    #[inline]
293    fn nodes(&self) -> crate::copyable::sealed::NodeIter<'store, K, V> {
294        self.inner.nodes()
295    }
296}
btree_plus_store/copyable/map.rs

btree_plus_store/copyable/
map.rs
