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

ext4_metadata/
sorted_vec_map.rs
