vecmap/
lib.rs

1#![doc = include_str!("../README.md")]
2#![warn(missing_docs)]
3#![warn(clippy::pedantic)]
4#![allow(
5    clippy::match_wildcard_for_single_variants,
6    clippy::missing_errors_doc,
7    clippy::module_name_repetitions,
8    clippy::must_use_candidate,
9    clippy::return_self_not_must_use
10)]
11#![no_std]
12
13extern crate alloc;
14
15#[macro_use]
16mod macros;
17mod keyed;
18pub mod map;
19pub mod set;
20
21#[doc(inline)]
22pub use self::map::VecMap;
23#[doc(inline)]
24pub use self::set::VecSet;
25pub use alloc::collections::TryReserveError;
26use alloc::vec::Vec;
27
28// The type used to store entries in a `VecMap`.
29//
30// It is just a transparent wrapper around `(K, V)` with accessor methods for use in `map`
31// functions.
32#[repr(transparent)]
33#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
34struct Slot<K, V> {
35    data: (K, V),
36}
37
38impl<K, V> keyed::Keyed<K> for Slot<K, V> {
39    #[inline]
40    fn key(&self) -> &K {
41        &self.data.0
42    }
43}
44
45impl<K, V> Slot<K, V> {
46    #[inline]
47    fn new(key: K, value: V) -> Self {
48        Slot { data: (key, value) }
49    }
50
51    #[inline]
52    fn key(&self) -> &K {
53        &self.data.0
54    }
55
56    #[inline]
57    fn key_mut(&mut self) -> &mut K {
58        &mut self.data.0
59    }
60
61    #[inline]
62    fn into_key(self) -> K {
63        self.data.0
64    }
65
66    #[inline]
67    fn value(&self) -> &V {
68        &self.data.1
69    }
70
71    #[inline]
72    fn value_mut(&mut self) -> &mut V {
73        &mut self.data.1
74    }
75
76    #[inline]
77    fn into_value(self) -> V {
78        self.data.1
79    }
80
81    #[inline]
82    fn refs(&self) -> (&K, &V) {
83        (&self.data.0, &self.data.1)
84    }
85
86    #[inline]
87    fn ref_mut(&mut self) -> (&K, &mut V) {
88        (&self.data.0, &mut self.data.1)
89    }
90
91    #[inline]
92    fn muts(&mut self) -> (&mut K, &mut V) {
93        (&mut self.data.0, &mut self.data.1)
94    }
95
96    #[inline]
97    fn into_key_value(self) -> (K, V) {
98        self.data
99    }
100}
101
102// Trait for obtaining access to the entries in a collection.
103trait Entries {
104    type Entry;
105
106    fn as_entries(&self) -> &[Self::Entry];
107
108    fn as_entries_mut(&mut self) -> &mut [Self::Entry];
109
110    fn into_entries(self) -> Vec<Self::Entry>;
111}
112
113/// Deduplicate elements in an unsorted vector, keeping the first occurrence of
114/// each equivalence class.
115fn dedup_keep_first<T>(vec: &mut Vec<T>, eq_fn: impl Fn(&T, &T) -> bool) {
116    let mut out = 1;
117    let len = vec.len();
118    for i in 1..len {
119        if (0..i).all(|j| !eq_fn(&vec[i], &vec[j])) {
120            vec.swap(out, i);
121            out += 1;
122        }
123    }
124    vec.truncate(out);
125}
126
127/// Deduplicate by equivalence, keeping the first occurrence's position but the
128/// last occurrence's value.
129fn dedup_keep_last_value<T>(vec: &mut Vec<T>, eq_fn: impl Fn(&T, &T) -> bool) {
130    if vec.len() <= 1 {
131        return;
132    }
133    let mut out = 1;
134    let len = vec.len();
135    for i in 1..len {
136        if let Some(j) = (0..out).find(|&j| eq_fn(&vec[i], &vec[j])) {
137            vec.swap(i, j);
138        } else {
139            vec.swap(out, i);
140            out += 1;
141        }
142    }
143    vec.truncate(out);
144}
145
146/// Cast a `Vec<T>` into a `Vec<U>`.
147///
148/// # Safety
149///
150/// Callers must ensure that `T` and `U` have the same memory layout.
151unsafe fn transmute_vec<T, U>(mut vec: Vec<T>) -> Vec<U> {
152    let (ptr, len, cap) = (vec.as_mut_ptr(), vec.len(), vec.capacity());
153    core::mem::forget(vec);
154    // SAFETY: callers must uphold the invariants of `T` and `U` mentioned in the function doc.
155    unsafe { Vec::from_raw_parts(ptr.cast(), len, cap) }
156}
157
158#[test]
159fn test_dedup_keep_first() {
160    fn test(want: &[u32], arr: &[u32]) {
161        let mut vec = arr.to_vec();
162        dedup_keep_first(&mut vec, |i, j| i == j);
163        assert_eq!(want, vec.as_slice());
164    }
165
166    test(&[], &[]);
167    test(&[1], &[1]);
168    test(&[1], &[1, 1]);
169    test(&[1], &[1, 1, 1]);
170    test(&[3, 1, 2], &[3, 1, 2]);
171    test(&[3, 1, 2], &[3, 1, 2, 1, 2, 3]);
172}
173
174#[test]
175fn test_dedup_keep_first_preserves_first_payload() {
176    #[derive(Clone, Debug)]
177    #[allow(dead_code)]
178    struct Item(i32, &'static str);
179
180    impl Eq for Item {}
181
182    impl PartialEq for Item {
183        fn eq(&self, other: &Self) -> bool {
184            self.0 == other.0
185        }
186    }
187
188    let mut vec = Vec::from([Item(1, "first"), Item(2, "b"), Item(1, "second")]);
189    dedup_keep_first(&mut vec, |a, b| a == b);
190    assert_eq!(vec, [Item(1, "first"), Item(2, "b")]);
191}
192
193#[test]
194fn test_dedup_keep_last_value() {
195    fn test(want: &[(char, i32)], arr: &[(char, i32)]) {
196        let mut vec = arr.to_vec();
197        dedup_keep_last_value(&mut vec, |lhs, rhs| lhs.0 == rhs.0);
198        assert_eq!(want, vec.as_slice());
199    }
200
201    test(&[], &[]);
202    test(&[('a', 1)], &[('a', 1)]);
203    test(&[('a', 3)], &[('a', 1), ('a', 2), ('a', 3)]);
204    test(&[('a', 3), ('b', 2)], &[('a', 1), ('b', 2), ('a', 3)]);
205    test(&[('b', 2), ('a', 1)], &[('b', 2), ('a', 1)]);
206}
207
208#[test]
209fn test_dedup_keep_last_value_preserves_last_payload() {
210    #[derive(Clone, Debug)]
211    #[allow(dead_code)]
212    struct Entry(i32, &'static str);
213
214    impl Eq for Entry {}
215
216    impl PartialEq for Entry {
217        fn eq(&self, other: &Self) -> bool {
218            self.0 == other.0
219        }
220    }
221
222    let mut vec = Vec::from([Entry(1, "a"), Entry(2, "b"), Entry(1, "c")]);
223    dedup_keep_last_value(&mut vec, |lhs, rhs| lhs.0 == rhs.0);
224    assert_eq!(vec, [Entry(1, "c"), Entry(2, "b")]);
225}
226
227// https://github.com/martinohmann/vecmap-rs/issues/18
228//
229// If `Slot<K, V>` does not have the same memory layout as `(K, V)`, e.g. due to possible field
230// reordering, this test will:
231//
232// - Segfault with "SIGSEGV: invalid memory reference" in the `unsafe` block in `VecMap::as_slice`
233//   when run via `cargo test`.
234// - Trigger a miri error when run via `cargo +nightly miri test`.
235#[test]
236fn issue_18() {
237    use alloc::string::String;
238    use core::{fmt, mem};
239
240    fn test<K, V>(slice: &[(K, V)])
241    where
242        K: Clone + Eq + fmt::Debug,
243        V: Clone + PartialEq + fmt::Debug,
244    {
245        assert_eq!(mem::size_of::<Slot<K, V>>(), mem::size_of::<(K, V)>());
246        assert_eq!(mem::align_of::<Slot<K, V>>(), mem::align_of::<(K, V)>());
247
248        let map = VecMap::from(slice);
249        assert_eq!(map.as_slice(), slice);
250    }
251
252    test(&[(1i64, String::from("foo")), (2, String::from("bar"))]);
253    test(&[(String::from("foo"), 1i64), (String::from("bar"), 2)]);
254    test(&[(true, 1i64), (false, 2)]);
255    test(&[(1i64, true), (2, false)]);
256}
vecmap/lib.rs

vecmap/
lib.rs
