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.
114fn dedup<T>(vec: &mut Vec<T>, eq_fn: impl Fn(&T, &T) -> bool) {
115    let mut out = 1;
116    let len = vec.len();
117    for i in 1..len {
118        if (0..i).all(|j| !eq_fn(&vec[i], &vec[j])) {
119            vec.swap(out, i);
120            out += 1;
121        }
122    }
123    vec.truncate(out);
124}
125
126/// Cast a `Vec<T>` into a `Vec<U>`.
127///
128/// # Safety
129///
130/// Callers must ensure that `T` and `U` have the same memory layout.
131unsafe fn transmute_vec<T, U>(mut vec: Vec<T>) -> Vec<U> {
132    let (ptr, len, cap) = (vec.as_mut_ptr(), vec.len(), vec.capacity());
133    core::mem::forget(vec);
134    // SAFETY: callers must uphold the invariants of `T` and `U` mentioned in the function doc.
135    unsafe { Vec::from_raw_parts(ptr.cast(), len, cap) }
136}
137
138#[test]
139fn test_dedup() {
140    fn test(want: &[u32], arr: &[u32]) {
141        let mut vec = arr.to_vec();
142        dedup(&mut vec, |i, j| i == j);
143        assert_eq!(want, vec.as_slice());
144    }
145
146    test(&[], &[]);
147    test(&[1], &[1]);
148    test(&[1], &[1, 1]);
149    test(&[1], &[1, 1, 1]);
150    test(&[3, 1, 2], &[3, 1, 2]);
151    test(&[3, 1, 2], &[3, 1, 2, 1, 2, 3]);
152}
153
154// https://github.com/martinohmann/vecmap-rs/issues/18
155//
156// If `Slot<K, V>` does not have the same memory layout as `(K, V)`, e.g. due to possible field
157// reordering, this test will:
158//
159// - Segfault with "SIGSEGV: invalid memory reference" in the `unsafe` block in `VecMap::as_slice`
160//   when run via `cargo test`.
161// - Trigger a miri error when run via `cargo +nightly miri test`.
162#[test]
163fn issue_18() {
164    use alloc::string::String;
165    use core::{fmt, mem};
166
167    fn test<K, V>(slice: &[(K, V)])
168    where
169        K: Clone + Eq + fmt::Debug,
170        V: Clone + PartialEq + fmt::Debug,
171    {
172        assert_eq!(mem::size_of::<Slot<K, V>>(), mem::size_of::<(K, V)>());
173        assert_eq!(mem::align_of::<Slot<K, V>>(), mem::align_of::<(K, V)>());
174
175        let map = VecMap::from(slice);
176        assert_eq!(map.as_slice(), slice);
177    }
178
179    test(&[(1i64, String::from("foo")), (2, String::from("bar"))]);
180    test(&[(String::from("foo"), 1i64), (String::from("bar"), 2)]);
181    test(&[(true, 1i64), (false, 2)]);
182    test(&[(1i64, true), (2, false)]);
183}
vecmap/lib.rs

vecmap/
lib.rs
