packed/
packed_map.rs

1// Copyright 2026 The Fuchsia Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5//! A memory-efficient map optimized for dynamically sized keys.
6//!
7//! `PackedMap` manages its keys sequentially in a contiguous region of memory through
8//! `PackedVec`, mapping them to values stored in a conventional `Vec`. Because it
9//! stores keys as a single allocation, it cannot be modified after construction.
10
11use crate::packed_map_builder::PackedMapBuilder;
12use crate::{PackedItem, PackedVec};
13use std::borrow::Borrow;
14use std::fmt::Debug;
15use std::iter::FromIterator;
16
17/// A map with keys stored in a sorted `PackedVec<K>` and values in a `Vec<V>`.
18///
19/// This map is optimized for reducing memory usage by using a packed representation
20/// for keys. It does not support modification after creation.
21pub struct PackedMap<K: ?Sized + Ord + PackedItem, V> {
22    pub(crate) keys: PackedVec<K>,
23    pub(crate) values: Vec<V>,
24}
25
26impl<K, V> PackedMap<K, V>
27where
28    K: ?Sized + Ord + PackedItem,
29{
30    /// Creates a new `PackedMapBuilder`.
31    pub fn builder() -> PackedMapBuilder<K, V>
32    where
33        K: ToOwned,
34        K::Owned: Ord,
35    {
36        PackedMapBuilder::new()
37    }
38
39    /// Creates a new `PackedMapBuilder` with the specified capacities.
40    ///
41    /// The `element_capacity` argument specifies the number of slices that can be
42    /// stored without reallocating the offsets vector. The `buffer_capacity`
43    /// argument specifies the cumulative length of slices that can be stored
44    /// without reallocating the data vector.
45    pub fn builder_with_capacity(
46        element_capacity: usize,
47        buffer_capacity: usize,
48    ) -> PackedMapBuilder<K, V>
49    where
50        K: ToOwned,
51        K::Owned: Ord,
52    {
53        PackedMapBuilder::with_capacity(element_capacity, buffer_capacity)
54    }
55
56    /// Creates a new empty `PackedMap`.
57    pub fn new() -> Self {
58        Self { keys: PackedVec::new(), values: vec![] }
59    }
60
61    /// Creates a new `PackedMap` with the specified capacities.
62    ///
63    /// The `element_capacity` argument specifies the number of slices that can be
64    /// stored without reallocating the offsets vector. The `buffer_capacity`
65    /// argument specifies the cumulative length of slices that can be stored
66    /// without reallocating the data vector.
67    pub fn with_capacity(element_capacity: usize, buffer_capacity: usize) -> Self {
68        Self {
69            keys: PackedVec::with_capacity(element_capacity, buffer_capacity),
70            values: Vec::with_capacity(element_capacity),
71        }
72    }
73
74    pub(crate) fn from_parts(keys: PackedVec<K>, values: Vec<V>) -> Self {
75        Self { keys, values }
76    }
77
78    /// Returns true if the map contains no elements.
79    pub fn is_empty(&self) -> bool {
80        self.keys.is_empty()
81    }
82
83    /// Returns the number of elements in the map.
84    pub fn element_len(&self) -> usize {
85        self.keys.len()
86    }
87
88    /// Returns the cumulative length of all keys in the map in bytes.
89    pub fn buffer_len(&self) -> usize {
90        self.keys.buffer_len()
91    }
92
93    /// Returns a reference to the value corresponding to the key.
94    pub fn get<Q>(&self, key: &Q) -> Option<&V>
95    where
96        K: Borrow<Q>,
97        Q: Ord + ?Sized,
98    {
99        if let Ok(index) = self.index_of(key) { Some(&self.values[index]) } else { None }
100    }
101
102    /// Returns a mutable reference to the value corresponding to the key.
103    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
104    where
105        K: Borrow<Q>,
106        Q: Ord + ?Sized,
107    {
108        if let Ok(index) = self.index_of(key) { Some(&mut self.values[index]) } else { None }
109    }
110
111    /// Returns true if the map contains a value for the specified key.
112    pub fn contains_key<Q>(&self, key: &Q) -> bool
113    where
114        K: Borrow<Q>,
115        Q: Ord + ?Sized,
116    {
117        self.index_of(key).is_ok()
118    }
119
120    /// Inserts a key-value pair into the map.
121    ///
122    /// If the key is already present, updates the value and returns `Ok(Some(old_value))`.
123    /// If the key is greater than the last key, appends it and returns `Ok(None)`.
124    /// Otherwise, returns `Err(value)`.
125    ///
126    /// # Complexity
127    ///
128    /// - `O(1)` if the key is greater than or equal to the last key in the map.
129    /// - `O(log N)` otherwise, where `N` is the number of elements in the map.
130    pub fn append_or_update(&mut self, key: &K, value: V) -> Result<Option<V>, V> {
131        // Fast path for appends and updates to the last element. This avoids a
132        // binary search when elements are inserted in sorted order.
133        if let Some(last) = self.keys.last() {
134            match key.cmp(last) {
135                std::cmp::Ordering::Greater => {
136                    self.keys.push(key);
137                    self.values.push(value);
138                    return Ok(None);
139                }
140                std::cmp::Ordering::Equal => {
141                    let old_value = std::mem::replace(self.values.last_mut().unwrap(), value);
142                    return Ok(Some(old_value));
143                }
144                std::cmp::Ordering::Less => {}
145            }
146        } else {
147            self.keys.push(key);
148            self.values.push(value);
149            return Ok(None);
150        }
151
152        match self.keys.binary_search(key) {
153            Ok(idx) => {
154                let old_value = std::mem::replace(&mut self.values[idx], value);
155                Ok(Some(old_value))
156            }
157            Err(_) => Err(value),
158        }
159    }
160
161    /// Shrinks the capacity of the map as much as possible.
162    pub fn shrink_to_fit(&mut self) {
163        self.keys.shrink_to_fit();
164        self.values.shrink_to_fit();
165    }
166
167    /// Returns an iterator over the entries of the map, sorted by key.
168    pub fn iter(&self) -> Iter<'_, K, V> {
169        Iter { keys: self.keys.iter(), values: self.values.iter() }
170    }
171
172    /// Returns an iterator over the entries of the map, sorted by key, with mutable values.
173    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
174        IterMut { keys: self.keys.iter(), values: self.values.iter_mut() }
175    }
176
177    /// Drains all elements from the map, returning a lending iterator that yields them.
178    ///
179    /// The elements are yielded in sorted order by key.
180    /// After the iterator is dropped, the map is left empty.
181    ///
182    /// # Leaked
183    ///
184    /// If the returned `Drain` iterator is leaked (e.g. via `std::mem::forget`),
185    /// any elements that have not been yielded yet will be leaked (their destructors
186    /// will not run). However, memory safety is still preserved as the map will be left empty.
187    pub fn drain(&mut self) -> Drain<'_, K, V> {
188        let keys = self.keys.drain();
189        let values = self.values.drain(..);
190        Drain { keys, values }
191    }
192
193    /// Constructs a double-ended iterator over a sub-range of elements in the map.
194    pub fn range<'a, Q, R>(&'a self, range: R) -> Range<'a, K, V>
195    where
196        K: Borrow<Q>,
197        Q: Ord + ?Sized + 'a,
198        R: std::ops::RangeBounds<&'a Q>,
199    {
200        let indices =
201            crate::compute_range_indices(self.element_len(), range, |&key| self.index_of(key));
202        Range { keys: self.keys.range(indices.clone()), values: self.values[indices].iter() }
203    }
204
205    /// Constructs a mutable double-ended iterator over a sub-range of elements in the map.
206    pub fn range_mut<'a, Q, R>(&'a mut self, range: R) -> RangeMut<'a, K, V>
207    where
208        K: Borrow<Q>,
209        Q: Ord + ?Sized + 'a,
210        R: std::ops::RangeBounds<&'a Q>,
211    {
212        let indices =
213            crate::compute_range_indices(self.element_len(), range, |&key| self.index_of(key));
214        RangeMut { keys: self.keys.range(indices.clone()), values: self.values[indices].iter_mut() }
215    }
216
217    /// Returns an iterator over the keys of the map, in sorted order.
218    pub fn keys(&self) -> Keys<'_, K> {
219        Keys { inner: self.keys.iter() }
220    }
221
222    /// Returns an iterator over the values of the map, sorted by key.
223    pub fn values(&self) -> Values<'_, V> {
224        Values { inner: self.values.iter() }
225    }
226
227    /// Returns a mutable iterator over the values of the map, sorted by key.
228    pub fn values_mut(&mut self) -> ValuesMut<'_, V> {
229        ValuesMut { inner: self.values.iter_mut() }
230    }
231
232    /// Returns an iterator that takes ownership of the map's values, sorted by key.
233    pub fn into_values(self) -> IntoValues<V> {
234        IntoValues { inner: self.values.into_iter() }
235    }
236
237    fn index_of<Q>(&self, key: &Q) -> Result<usize, usize>
238    where
239        K: Borrow<Q>,
240        Q: Ord + ?Sized,
241    {
242        self.keys.binary_search_by(|probe| probe.borrow().cmp(key))
243    }
244}
245
246impl<K, V, Q> std::ops::Index<&Q> for PackedMap<K, V>
247where
248    K: ?Sized + Ord + PackedItem + Borrow<Q>,
249    Q: Ord + ?Sized,
250{
251    type Output = V;
252
253    fn index(&self, key: &Q) -> &Self::Output {
254        self.get(key).expect("no entry found for key")
255    }
256}
257
258// This manual implementation avoids an extra constraint of `K: Default` since we've
259// encoded the keys into a byte string.
260impl<K: ?Sized + Ord + PackedItem, V> Default for PackedMap<K, V> {
261    fn default() -> Self {
262        Self::new()
263    }
264}
265
266// This manual implementation avoids an extra constraint of `K: Clone` since
267// we've encoded the keys into a byte string.
268impl<K: ?Sized + Ord + PackedItem, V: Clone> Clone for PackedMap<K, V> {
269    fn clone(&self) -> Self {
270        Self { keys: self.keys.clone(), values: self.values.clone() }
271    }
272}
273
274// This manual implementation avoids an extra constraint of `K: PartialEq` since
275// we've encoded the keys into a byte string.
276impl<K: ?Sized + Ord + PackedItem, V: PartialEq> PartialEq for PackedMap<K, V> {
277    fn eq(&self, other: &Self) -> bool {
278        self.keys == other.keys && self.values == other.values
279    }
280}
281
282// This manual implementation avoids an extra constraint of `K: Eq` since we've
283// encoded the keys into a byte string.
284impl<K: ?Sized + Ord + PackedItem, V: Eq> Eq for PackedMap<K, V> {}
285
286// This manual implementation avoids an extra constraint of `K: Hash` since we've
287// encoded the keys into a byte string.
288impl<K: ?Sized + Ord + PackedItem, V: std::hash::Hash> std::hash::Hash for PackedMap<K, V> {
289    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
290        self.keys.hash(state);
291        self.values.hash(state);
292    }
293}
294
295impl<K: ?Sized + Ord + PackedItem, V: Debug> Debug for PackedMap<K, V>
296where
297    K: Debug,
298{
299    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
300        f.debug_map().entries(self.iter()).finish()
301    }
302}
303
304pub struct Iter<'a, K: ?Sized + Ord + PackedItem, V> {
305    keys: crate::packed_vec::Iter<'a, K>,
306    values: std::slice::Iter<'a, V>,
307}
308
309impl<'a, K: ?Sized + Ord + PackedItem, V> Iterator for Iter<'a, K, V> {
310    type Item = (&'a K, &'a V);
311
312    fn next(&mut self) -> Option<Self::Item> {
313        let key = self.keys.next()?;
314        let value = self.values.next()?;
315        Some((key, value))
316    }
317
318    fn size_hint(&self) -> (usize, Option<usize>) {
319        self.keys.size_hint()
320    }
321}
322
323impl<'a, K: ?Sized + Ord + PackedItem, V> DoubleEndedIterator for Iter<'a, K, V> {
324    fn next_back(&mut self) -> Option<Self::Item> {
325        let key = self.keys.next_back()?;
326        let value = self.values.next_back()?;
327        Some((key, value))
328    }
329}
330
331impl<'a, K: ?Sized + Ord + PackedItem, V> ExactSizeIterator for Iter<'a, K, V> {}
332
333pub struct IterMut<'a, K: ?Sized + Ord + PackedItem, V> {
334    keys: crate::packed_vec::Iter<'a, K>,
335    values: std::slice::IterMut<'a, V>,
336}
337
338impl<'a, K: ?Sized + Ord + PackedItem, V> Iterator for IterMut<'a, K, V> {
339    type Item = (&'a K, &'a mut V);
340
341    fn next(&mut self) -> Option<Self::Item> {
342        let key = self.keys.next()?;
343        let value = self.values.next()?;
344        Some((key, value))
345    }
346
347    fn size_hint(&self) -> (usize, Option<usize>) {
348        self.keys.size_hint()
349    }
350}
351
352impl<'a, K: ?Sized + Ord + PackedItem, V> DoubleEndedIterator for IterMut<'a, K, V> {
353    fn next_back(&mut self) -> Option<Self::Item> {
354        let key = self.keys.next_back()?;
355        let value = self.values.next_back()?;
356        Some((key, value))
357    }
358}
359
360impl<'a, K: ?Sized + Ord + PackedItem, V> ExactSizeIterator for IterMut<'a, K, V> {}
361
362pub struct Range<'a, K: ?Sized + Ord + PackedItem, V> {
363    keys: crate::packed_vec::Iter<'a, K>,
364    values: std::slice::Iter<'a, V>,
365}
366
367impl<'a, K: ?Sized + Ord + PackedItem, V> Iterator for Range<'a, K, V> {
368    type Item = (&'a K, &'a V);
369
370    fn next(&mut self) -> Option<Self::Item> {
371        let key = self.keys.next()?;
372        let value = self.values.next()?;
373        Some((key, value))
374    }
375
376    fn size_hint(&self) -> (usize, Option<usize>) {
377        self.keys.size_hint()
378    }
379}
380
381impl<'a, K: ?Sized + Ord + PackedItem, V> DoubleEndedIterator for Range<'a, K, V> {
382    fn next_back(&mut self) -> Option<Self::Item> {
383        let key = self.keys.next_back()?;
384        let value = self.values.next_back()?;
385        Some((key, value))
386    }
387}
388
389impl<'a, K: ?Sized + Ord + PackedItem, V> ExactSizeIterator for Range<'a, K, V> {}
390
391pub struct RangeMut<'a, K: ?Sized + Ord + PackedItem, V> {
392    keys: crate::packed_vec::Iter<'a, K>,
393    values: std::slice::IterMut<'a, V>,
394}
395
396impl<'a, K: ?Sized + Ord + PackedItem, V> Iterator for RangeMut<'a, K, V> {
397    type Item = (&'a K, &'a mut V);
398
399    fn next(&mut self) -> Option<Self::Item> {
400        let key = self.keys.next()?;
401        let value = self.values.next()?;
402        Some((key, value))
403    }
404
405    fn size_hint(&self) -> (usize, Option<usize>) {
406        self.keys.size_hint()
407    }
408}
409
410impl<'a, K: ?Sized + Ord + PackedItem, V> DoubleEndedIterator for RangeMut<'a, K, V> {
411    fn next_back(&mut self) -> Option<Self::Item> {
412        let key = self.keys.next_back()?;
413        let value = self.values.next_back()?;
414        Some((key, value))
415    }
416}
417
418impl<'a, K: ?Sized + Ord + PackedItem, V> ExactSizeIterator for RangeMut<'a, K, V> {}
419
420/// An iterator over the keys of a `PackedMap`.
421pub struct Keys<'a, K: ?Sized + PackedItem> {
422    inner: crate::packed_vec::Iter<'a, K>,
423}
424
425impl<'a, K: ?Sized + PackedItem> Iterator for Keys<'a, K> {
426    type Item = &'a K;
427
428    fn next(&mut self) -> Option<&'a K> {
429        self.inner.next()
430    }
431
432    fn size_hint(&self) -> (usize, Option<usize>) {
433        self.inner.size_hint()
434    }
435}
436
437impl<'a, K: ?Sized + PackedItem> DoubleEndedIterator for Keys<'a, K> {
438    fn next_back(&mut self) -> Option<&'a K> {
439        self.inner.next_back()
440    }
441}
442
443impl<'a, K: ?Sized + PackedItem> ExactSizeIterator for Keys<'a, K> {}
444
445/// An iterator over the values of a `PackedMap`.
446pub struct Values<'a, V> {
447    inner: std::slice::Iter<'a, V>,
448}
449
450impl<'a, V> Iterator for Values<'a, V> {
451    type Item = &'a V;
452
453    fn next(&mut self) -> Option<&'a V> {
454        self.inner.next()
455    }
456
457    fn size_hint(&self) -> (usize, Option<usize>) {
458        self.inner.size_hint()
459    }
460}
461
462impl<'a, V> DoubleEndedIterator for Values<'a, V> {
463    fn next_back(&mut self) -> Option<&'a V> {
464        self.inner.next_back()
465    }
466}
467
468impl<'a, V> ExactSizeIterator for Values<'a, V> {}
469
470/// A mutable iterator over the values of a `PackedMap`.
471pub struct ValuesMut<'a, V> {
472    inner: std::slice::IterMut<'a, V>,
473}
474
475impl<'a, V> Iterator for ValuesMut<'a, V> {
476    type Item = &'a mut V;
477
478    fn next(&mut self) -> Option<&'a mut V> {
479        self.inner.next()
480    }
481
482    fn size_hint(&self) -> (usize, Option<usize>) {
483        self.inner.size_hint()
484    }
485}
486
487impl<'a, V> DoubleEndedIterator for ValuesMut<'a, V> {
488    fn next_back(&mut self) -> Option<&'a mut V> {
489        self.inner.next_back()
490    }
491}
492
493impl<'a, V> ExactSizeIterator for ValuesMut<'a, V> {}
494
495/// An iterator that takes ownership of a `PackedMap`'s values.
496pub struct IntoValues<V> {
497    inner: std::vec::IntoIter<V>,
498}
499
500impl<V> Iterator for IntoValues<V> {
501    type Item = V;
502
503    fn next(&mut self) -> Option<V> {
504        self.inner.next()
505    }
506
507    fn size_hint(&self) -> (usize, Option<usize>) {
508        self.inner.size_hint()
509    }
510}
511
512impl<V> DoubleEndedIterator for IntoValues<V> {
513    fn next_back(&mut self) -> Option<V> {
514        self.inner.next_back()
515    }
516}
517
518impl<V> ExactSizeIterator for IntoValues<V> {}
519
520impl<'a, K: ?Sized + Ord + PackedItem, V> IntoIterator for &'a PackedMap<K, V> {
521    type Item = (&'a K, &'a V);
522    type IntoIter = Iter<'a, K, V>;
523
524    fn into_iter(self) -> Self::IntoIter {
525        self.iter()
526    }
527}
528
529impl<'a, K: ?Sized + Ord + PackedItem, V> IntoIterator for &'a mut PackedMap<K, V> {
530    type Item = (&'a K, &'a mut V);
531    type IntoIter = IterMut<'a, K, V>;
532
533    fn into_iter(self) -> Self::IntoIter {
534        self.iter_mut()
535    }
536}
537
538/// A draining lending iterator for `PackedMap<K, V>`.
539///
540/// This `struct` is created by `PackedMap::drain`. See its documentation for more.
541pub struct Drain<'a, K: ?Sized + Ord + PackedItem, V> {
542    keys: crate::packed_vec::Drain<'a, K>,
543    values: std::vec::Drain<'a, V>,
544}
545
546impl<'a, K: ?Sized + Ord + PackedItem, V> Drain<'a, K, V> {
547    /// Returns the next element in the draining iterator.
548    pub fn next(&mut self) -> Option<(&K, V)> {
549        let key = self.keys.next()?;
550        let value = self.values.next()?;
551        Some((key, value))
552    }
553
554    /// Returns the next element from the back in the draining iterator.
555    pub fn next_back(&mut self) -> Option<(&K, V)> {
556        let key = self.keys.next_back()?;
557        let value = self.values.next_back()?;
558        Some((key, value))
559    }
560
561    /// Returns the number of elements remaining in the draining iterator.
562    pub fn len(&self) -> usize {
563        self.keys.len()
564    }
565}
566
567impl<K, V, U> FromIterator<(U, V)> for PackedMap<K, V>
568where
569    K: ?Sized + Ord + PackedItem + ToOwned,
570    U: AsRef<K>,
571    K::Owned: Ord,
572{
573    fn from_iter<T: IntoIterator<Item = (U, V)>>(iter: T) -> Self {
574        let iter = iter.into_iter();
575        let (lower, _) = iter.size_hint();
576        let mut builder = PackedMapBuilder::with_capacity(lower, 0);
577        for (k, v) in iter {
578            builder.insert(k.as_ref(), v);
579        }
580        builder.build()
581    }
582}
583
584impl<K, V, U, const N: usize> From<[(U, V); N]> for PackedMap<K, V>
585where
586    K: ?Sized + Ord + PackedItem + ToOwned,
587    U: AsRef<K>,
588    K::Owned: Ord,
589{
590    fn from(arr: [(U, V); N]) -> Self {
591        Self::from_iter(arr)
592    }
593}
594
595impl<K: ?Sized + Ord + PackedItem, V> serde::Serialize for PackedMap<K, V>
596where
597    K: serde::Serialize,
598    V: serde::Serialize,
599{
600    fn serialize<S: serde::Serializer>(&self, serializer: S) -> Result<S::Ok, S::Error> {
601        use serde::ser::SerializeMap;
602        let mut map = serializer.serialize_map(Some(self.element_len()))?;
603        for (k, v) in self.iter() {
604            map.serialize_entry(k, v)?;
605        }
606        map.end()
607    }
608}
609
610impl<'de, K, V> serde::Deserialize<'de> for PackedMap<K, V>
611where
612    K: ?Sized + PackedItem + Ord + ToOwned,
613    Box<K>: serde::Deserialize<'de> + Ord + AsRef<K>,
614    V: serde::Deserialize<'de>,
615    K::Owned: Ord,
616{
617    fn deserialize<D: serde::Deserializer<'de>>(deserializer: D) -> Result<Self, D::Error> {
618        struct MapVisitor<K: ?Sized + Ord + PackedItem, V>(
619            std::marker::PhantomData<fn() -> (*const K, V)>,
620        );
621
622        impl<'de, K, V> serde::de::Visitor<'de> for MapVisitor<K, V>
623        where
624            K: ?Sized + PackedItem + Ord + ToOwned,
625            Box<K>: serde::Deserialize<'de> + Ord + AsRef<K>,
626            V: serde::Deserialize<'de>,
627            K::Owned: Ord,
628        {
629            type Value = PackedMap<K, V>;
630
631            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
632                formatter.write_str("a map of items")
633            }
634
635            fn visit_map<A: serde::de::MapAccess<'de>>(
636                self,
637                mut map: A,
638            ) -> Result<Self::Value, A::Error> {
639                let size = map.size_hint().unwrap_or(0);
640                let mut builder = PackedMapBuilder::with_capacity(size, 0);
641                while let Some((k, v)) = map.next_entry::<Box<K>, V>()? {
642                    builder.insert(k.as_ref(), v);
643                }
644                Ok(builder.build())
645            }
646        }
647
648        deserializer.deserialize_map(MapVisitor(std::marker::PhantomData))
649    }
650}
651
652#[cfg(test)]
653mod tests {
654    use super::*;
655    use std::cmp::Ordering;
656    use std::ops::Bound;
657
658    #[test]
659    fn test_from_iter_and_get() {
660        let entries = vec![("c", 3), ("a", 1), ("b", 2), ("a", 100)];
661        let map: PackedMap<str, i32> = entries.into_iter().collect();
662
663        assert_eq!(map.element_len(), 3);
664        assert_eq!(map.get("a"), Some(&100)); // Last one kept
665        assert_eq!(map.get("b"), Some(&2));
666        assert_eq!(map.get("c"), Some(&3));
667        assert_eq!(map.get("d"), None);
668    }
669
670    #[test]
671    fn test_append_or_update() {
672        let mut map: PackedMap<str, i32> = PackedMap::new();
673        assert_eq!(map.append_or_update("a", 1), Ok(None));
674        assert_eq!(map.append_or_update("b", 2), Ok(None));
675        assert_eq!(map.append_or_update("b", 20), Ok(Some(2))); // Update
676        assert_eq!(map.append_or_update("a", 10), Ok(Some(1))); // Update existing key
677        assert_eq!(map.append_or_update("aa", 5), Err(5)); // Out of order
678
679        assert_eq!(map.get("a"), Some(&10));
680        assert_eq!(map.get("b"), Some(&20));
681    }
682
683    #[derive(
684        Debug, Clone, Copy, Eq, zerocopy::IntoBytes, zerocopy::Immutable, zerocopy::Unaligned,
685    )]
686    #[repr(C)]
687    struct TestKey {
688        id: u8,
689        metadata: u8,
690    }
691
692    impl PartialEq for TestKey {
693        fn eq(&self, other: &Self) -> bool {
694            self.id == other.id
695        }
696    }
697
698    impl Ord for TestKey {
699        fn cmp(&self, other: &Self) -> Ordering {
700            self.id.cmp(&other.id)
701        }
702    }
703
704    impl PartialOrd for TestKey {
705        fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
706            Some(self.cmp(other))
707        }
708    }
709
710    impl PackedItem for TestKey {
711        unsafe fn from_bytes(bytes: &[u8]) -> &Self {
712            unsafe { &*(bytes.as_ptr() as *const TestKey) }
713        }
714    }
715
716    #[test]
717    fn test_append_or_update_keeps_old_key() {
718        let mut map = PackedMap::new();
719        let key1 = TestKey { id: 1, metadata: 10 };
720        let key2 = TestKey { id: 1, metadata: 20 };
721
722        map.append_or_update(&key1, 1).unwrap();
723        map.append_or_update(&key2, 2).unwrap(); // Equal, should go to packed
724
725        let items = map.iter().collect::<Vec<_>>();
726        assert_eq!(items.len(), 1);
727
728        let (k, v) = &items[0];
729        assert_eq!(k.metadata, 10);
730        assert_eq!(**v, 2);
731    }
732
733    #[test]
734    fn test_iter() {
735        let entries = vec![("b", 2), ("a", 1)];
736        let map: PackedMap<str, i32> = entries.into_iter().collect();
737        let collected: Vec<_> = map.iter().collect();
738        assert_eq!(collected, vec![("a", &1), ("b", &2)]);
739    }
740
741    #[test]
742    fn test_duplicate_keys() {
743        let entries = vec![("a", 1), ("b", 2), ("a", 3), ("c", 4), ("b", 5)];
744        let map: PackedMap<str, i32> = entries.into_iter().collect();
745
746        assert_eq!(map.element_len(), 3);
747        // Should keep the last value encountered for each key due to reverse then stable sort
748        assert_eq!(map.get("a"), Some(&3));
749        assert_eq!(map.get("b"), Some(&5));
750        assert_eq!(map.get("c"), Some(&4));
751
752        let collected: Vec<_> = map.iter().collect();
753        assert_eq!(collected, vec![("a", &3), ("b", &5), ("c", &4)]);
754    }
755
756    #[test]
757    fn test_drain() {
758        let entries = vec![("a", 1), ("b", 2), ("c", 3)];
759        let mut map: PackedMap<str, i32> = entries.into_iter().collect();
760
761        let mut drain = map.drain();
762        assert_eq!(drain.len(), 3);
763
764        // Test next()
765        assert_eq!(drain.next(), Some(("a", 1)));
766        assert_eq!(drain.len(), 2);
767
768        // Test next_back()
769        assert_eq!(drain.next_back(), Some(("c", 3)));
770        assert_eq!(drain.len(), 1);
771
772        // Test next() again
773        assert_eq!(drain.next(), Some(("b", 2)));
774        assert_eq!(drain.len(), 0);
775
776        // Test None
777        assert_eq!(drain.next(), None);
778        assert_eq!(drain.next_back(), None);
779    }
780
781    #[test]
782    fn test_drain_drop_clears() {
783        let entries = vec![("a", 1), ("b", 2)];
784        let mut map: PackedMap<str, i32> = entries.into_iter().collect();
785
786        {
787            let mut drain = map.drain();
788            assert_eq!(drain.next(), Some(("a", 1)));
789            // Drop happens here
790        }
791
792        assert!(map.is_empty());
793        assert_eq!(map.element_len(), 0);
794
795        // Make sure both vectors were cleared, not just one.
796        assert!(map.keys.is_empty());
797        assert!(map.values.is_empty());
798    }
799
800    #[test]
801    fn test_range() {
802        let entries = vec![("a", "A"), ("b", "B"), ("c", "C"), ("d", "D")];
803        let map: PackedMap<str, &str> = entries.into_iter().collect();
804
805        let items: Vec<_> = map.range("b"..).map(|(k, v)| (k, *v)).collect();
806        assert_eq!(items, vec![("b", "B"), ("c", "C"), ("d", "D")]);
807
808        let items: Vec<_> = map.range(.."c").map(|(k, v)| (k, *v)).collect();
809        assert_eq!(items, vec![("a", "A"), ("b", "B")]);
810
811        let items: Vec<_> = map.range(..="c").map(|(k, v)| (k, *v)).collect();
812        assert_eq!(items, vec![("a", "A"), ("b", "B"), ("c", "C")]);
813
814        let items: Vec<_> = map.range("b"..="c").map(|(k, v)| (k, *v)).collect();
815        assert_eq!(items, vec![("b", "B"), ("c", "C")]);
816
817        let items: Vec<_> = map.range("e"..).map(|(k, v)| (k, *v)).collect();
818        assert_eq!(items, vec![]);
819
820        let items: Vec<_> = map.range("a1".."c1").map(|(k, v)| (k, *v)).collect();
821        assert_eq!(items, vec![("b", "B"), ("c", "C")]);
822
823        let prefix_entries = vec![("dir/a", "A"), ("dir/b", "B"), ("file", "F")];
824        let prefix_map: PackedMap<str, &str> = prefix_entries.into_iter().collect();
825        let items: Vec<_> = prefix_map.range("dir/".."dir0").map(|(k, v)| (k, *v)).collect();
826        assert_eq!(items, vec![("dir/a", "A"), ("dir/b", "B")]);
827    }
828
829    #[test]
830    fn test_range_mut() {
831        let entries = vec![("a", "a".to_string()), ("b", "b".to_string()), ("c", "c".to_string())];
832        let mut map: PackedMap<str, String> = entries.into_iter().collect();
833
834        for (_, v) in map.range_mut("b"..) {
835            v.push('x');
836        }
837
838        for (_, v) in map.range_mut("a1".."c1") {
839            v.push('y');
840        }
841
842        let items: Vec<_> = map.iter().map(|(k, v)| (k, v.clone())).collect();
843        assert_eq!(
844            items,
845            vec![("a", "a".to_string()), ("b", "bxy".to_string()), ("c", "cxy".to_string())]
846        );
847
848        let mut prefix_map: PackedMap<str, String> =
849            vec![("dir/a", "A".to_string()), ("dir/b", "B".to_string()), ("file", "F".to_string())]
850                .into_iter()
851                .collect();
852
853        for (_, v) in prefix_map.range_mut("dir/".."dir0") {
854            v.push('x');
855        }
856        let items: Vec<_> = prefix_map.iter().map(|(k, v)| (k, v.clone())).collect();
857        assert_eq!(
858            items,
859            vec![
860                ("dir/a", "Ax".to_string()),
861                ("dir/b", "Bx".to_string()),
862                ("file", "F".to_string()),
863            ]
864        );
865    }
866
867    #[test]
868    fn test_string_prefixes() {
869        let entries = [
870            ("meta/", 1),
871            ("meta/a", 2),
872            ("meta/b", 3),
873            ("meta/c", 4),
874            ("meta/dir/a", 5),
875            ("meta/dir/b", 6),
876            ("meta/dir/c", 7),
877            ("meta/e", 8),
878            ("metb/", 9),
879        ];
880        let map: PackedMap<str, i32> = entries.into_iter().collect();
881
882        let mut it = map.range("meta/"..);
883        assert_eq!(it.next(), Some(("meta/", &1)));
884        assert_eq!(it.next(), Some(("meta/a", &2)));
885        assert_eq!(it.next(), Some(("meta/b", &3)));
886        assert_eq!(it.next(), Some(("meta/c", &4)));
887        assert_eq!(it.next(), Some(("meta/dir/a", &5)));
888        assert_eq!(it.next(), Some(("meta/dir/b", &6)));
889        assert_eq!(it.next(), Some(("meta/dir/c", &7)));
890        assert_eq!(it.next(), Some(("meta/e", &8)));
891        assert_eq!(it.next(), Some(("metb/", &9)));
892        assert_eq!(it.next(), None);
893
894        let mut it = map.range((Bound::Excluded("meta/"), Bound::Unbounded));
895        assert_eq!(it.next(), Some(("meta/a", &2)));
896
897        let mut it = map.range("meta/"..);
898        assert_eq!(it.next(), Some(("meta/", &1)));
899
900        let mut it = map.range("meta/dir/"..);
901        assert_eq!(it.next(), Some(("meta/dir/a", &5)));
902
903        let mut it = map.range((Bound::Excluded("meta/dir/"), Bound::Unbounded));
904        assert_eq!(it.next(), Some(("meta/dir/a", &5)));
905    }
906
907    #[test]
908    fn test_serde() {
909        let entries = vec![("a", 1), ("b", 2), ("c", 3)];
910        let map: PackedMap<str, i32> = entries.into_iter().collect();
911        let serialized = serde_json::to_string(&map).unwrap();
912        let deserialized: PackedMap<str, i32> = serde_json::from_str(&serialized).unwrap();
913        assert_eq!(map, deserialized);
914    }
915}
packed/packed_map.rs

packed/
packed_map.rs
