ext4_metadata/
sorted_vec_map.rs

1// Copyright 2025 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
5use std::borrow::Borrow;
6use std::cmp::Ordering;
7use std::fmt::Debug;
8use std::marker::PhantomData;
9use std::{iter, slice};
10
11/// An ordered map built on a `Vec`.
12///
13/// This map is optimized for reducing the memory usage of data that rarely or never changes.
14/// Insertions and removals take linear time while lookups take logarithmic time.
15#[derive(Eq, PartialEq, PartialOrd, Ord, Hash, Clone, Default)]
16pub struct SortedVecMap<K, V> {
17    vec: Vec<(K, V)>,
18}
19
20impl<K, V> SortedVecMap<K, V> {
21    /// Constructs a new, empty `SortedVecMap`.
22    pub fn new() -> Self {
23        Self { vec: Vec::new() }
24    }
25
26    /// Returns true if there are not entries in the map.
27    pub fn is_empty(&self) -> bool {
28        self.vec.is_empty()
29    }
30
31    /// Returns a reference to the value corresponding to the key.
32    pub fn get<Q>(&self, key: &Q) -> Option<&V>
33    where
34        K: Borrow<Q> + Ord,
35        Q: Ord + ?Sized,
36    {
37        if let Ok(index) = self.index_of(key) {
38            Some(&self.vec[index].1)
39        } else {
40            None
41        }
42    }
43
44    /// Returns a mutable reference to the value corresponding to the key.
45    pub fn get_mut<Q>(&mut self, key: &Q) -> Option<&mut V>
46    where
47        K: Borrow<Q> + Ord,
48        Q: Ord + ?Sized,
49    {
50        if let Ok(index) = self.index_of(key) {
51            Some(&mut self.vec[index].1)
52        } else {
53            None
54        }
55    }
56
57    /// Inserts a key-value pair into the map. If the map did not have this key present, `None` is
58    /// returned. If the map did have this key present, the value is updated, and the old value is
59    /// returned. The key is not updated.
60    pub fn insert(&mut self, key: K, value: V) -> Option<V>
61    where
62        K: Ord,
63    {
64        match self.index_of(&key) {
65            Ok(index) => {
66                let old = std::mem::replace(&mut self.vec[index], (key, value));
67                Some(old.1)
68            }
69            Err(index) => {
70                self.vec.insert(index, (key, value));
71                None
72            }
73        }
74    }
75
76    /// Returns an iterator over the entries of the map, sorted by key.
77    pub fn iter(&self) -> Iter<'_, K, V> {
78        self.vec.iter().map(|entry| (&entry.0, &entry.1))
79    }
80
81    /// Returns an iterator over the entries of the map, sorted by key.
82    pub fn iter_mut(&mut self) -> IterMut<'_, K, V> {
83        self.vec.iter_mut().map(|entry| (&entry.0, &mut entry.1))
84    }
85
86    /// Returns an iterator over the keys of the map, in sorted order.
87    pub fn keys(&self) -> Keys<'_, K, V> {
88        self.vec.iter().map(|e| &e.0)
89    }
90
91    /// Returns a mutable iterator over the values of the map, sorted by key.
92    pub fn values_mut(&mut self) -> ValuesMut<'_, K, V> {
93        self.vec.iter_mut().map(|e| &mut e.1)
94    }
95
96    /// Searches for the key in the map.
97    ///
98    /// If the key is found then `Result::Ok` is returned with the index of the entry. If the key is
99    /// not found then `Result::Err` is return, containing the index where an entry with that key
100    /// could be inserted while maintaining sorted order.
101    fn index_of<Q>(&self, key: &Q) -> Result<usize, usize>
102    where
103        K: Borrow<Q> + Ord,
104        Q: Ord + ?Sized,
105    {
106        self.vec.binary_search_by(|probe| probe.0.borrow().cmp(key))
107    }
108}
109
110impl<K: Debug, V: Debug> Debug for SortedVecMap<K, V> {
111    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
112        f.debug_map().entries(self.iter()).finish()
113    }
114}
115
116pub type Iter<'a, K, V> = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> (&K, &V)>;
117pub type IterMut<'a, K, V> = iter::Map<slice::IterMut<'a, (K, V)>, fn(&mut (K, V)) -> (&K, &mut V)>;
118pub type Keys<'a, K, V> = iter::Map<slice::Iter<'a, (K, V)>, fn(&(K, V)) -> &K>;
119pub type ValuesMut<'a, K, V> = iter::Map<slice::IterMut<'a, (K, V)>, fn(&mut (K, V)) -> &mut V>;
120
121impl<K: Ord, V> FromIterator<(K, V)> for SortedVecMap<K, V> {
122    fn from_iter<T: IntoIterator<Item = (K, V)>>(iter: T) -> Self {
123        let mut vec = Vec::from_iter(iter);
124        vec.shrink_to_fit();
125        vec.sort_by(sort_comparator);
126        vec.dedup_by(dedup_comparator);
127        Self { vec }
128    }
129}
130
131impl<'de, K, V> serde::Deserialize<'de> for SortedVecMap<K, V>
132where
133    K: Ord + serde::Deserialize<'de>,
134    V: serde::Deserialize<'de>,
135{
136    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
137    where
138        D: serde::Deserializer<'de>,
139    {
140        struct Visitor<K, V> {
141            _map_type: PhantomData<SortedVecMap<K, V>>,
142        }
143        impl<'de, K, V> serde::de::Visitor<'de> for Visitor<K, V>
144        where
145            K: Ord + serde::Deserialize<'de>,
146            V: serde::Deserialize<'de>,
147        {
148            type Value = SortedVecMap<K, V>;
149            fn expecting(&self, formatter: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
150                formatter.write_str("a map")
151            }
152            fn visit_map<A>(self, mut map: A) -> Result<Self::Value, A::Error>
153            where
154                A: serde::de::MapAccess<'de>,
155            {
156                let mut vec: Vec<(K, V)> = match map.size_hint() {
157                    Some(hint) => Vec::with_capacity(hint),
158                    None => Vec::new(),
159                };
160                let mut is_sorted_and_deduped = true;
161                while let Some(entry) = map.next_entry()? {
162                    if is_sorted_and_deduped {
163                        if let Some(back) = vec.last() {
164                            is_sorted_and_deduped = back.0.cmp(&entry.0) == Ordering::Less;
165                        }
166                    }
167                    vec.push(entry);
168                }
169                if !is_sorted_and_deduped {
170                    vec.sort_by(sort_comparator);
171                    vec.dedup_by(dedup_comparator);
172                }
173                vec.shrink_to_fit();
174                Ok(SortedVecMap { vec })
175            }
176        }
177        deserializer.deserialize_map(Visitor { _map_type: PhantomData })
178    }
179}
180
181impl<K: serde::Serialize, V: serde::Serialize> serde::Serialize for SortedVecMap<K, V> {
182    fn serialize<S>(&self, serializer: S) -> Result<S::Ok, S::Error>
183    where
184        S: serde::Serializer,
185    {
186        serializer.collect_map(self.iter())
187    }
188}
189
190fn sort_comparator<K: Ord, V>(a: &(K, V), b: &(K, V)) -> Ordering {
191    a.0.cmp(&b.0)
192}
193
194fn dedup_comparator<K: Ord, V>(a: &mut (K, V), b: &mut (K, V)) -> bool {
195    a.0 == b.0
196}
197
198#[cfg(test)]
199mod tests {
200    use super::*;
201    use std::collections::BTreeMap;
202
203    #[test]
204    fn test_get() {
205        let mut map = SortedVecMap::new();
206        assert!(map.get(&1).is_none());
207
208        map.insert(1, 21);
209        assert_eq!(map.get(&1), Some(&21));
210
211        map.insert(0, 20);
212        assert_eq!(map.get(&0), Some(&20));
213        assert_eq!(map.get(&1), Some(&21));
214
215        map.insert(2, 22);
216        assert_eq!(map.get(&0), Some(&20));
217        assert_eq!(map.get(&1), Some(&21));
218        assert_eq!(map.get(&2), Some(&22));
219    }
220
221    #[test]
222    fn test_insert() {
223        let mut map = SortedVecMap::new();
224        for (k, v) in [(50, 50), (47, 47), (48, 48), (51, 51), (49, 49)] {
225            assert!(map.insert(k, v).is_none());
226        }
227        assert_eq!(map.insert(48, 88), Some(48));
228        assert_eq!(map.vec.as_slice(), &[(47, 47), (48, 88), (49, 49), (50, 50), (51, 51)])
229    }
230
231    #[test]
232    fn test_serialize_deserialize() {
233        let map: SortedVecMap<i32, i32> =
234            [(56, 56), (47, 47), (53, 53), (51, 51), (49, 49)].into_iter().collect();
235        let serialized = bincode::serialize(&map).unwrap();
236        let deserialized: SortedVecMap<i32, i32> = bincode::deserialize(&serialized).unwrap();
237        assert_eq!(map, deserialized);
238    }
239
240    #[test]
241    fn test_deserialize_from_btree_map() {
242        let map: BTreeMap<i32, i32> = [(56, 56), (47, 47), (53, 53), (51, 51), (49, 49)].into();
243        let serialized = bincode::serialize(&map).unwrap();
244        let deserialized: SortedVecMap<i32, i32> = bincode::deserialize(&serialized).unwrap();
245
246        let map_entries: Vec<(i32, i32)> = map.into_iter().collect();
247        assert_eq!(map_entries, deserialized.vec);
248    }
249}
ext4_metadata/sorted_vec_map.rs

ext4_metadata/
sorted_vec_map.rs
