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;
17pub mod map;
18pub mod set;
19
20#[doc(inline)]
21pub use self::map::VecMap;
22#[doc(inline)]
23pub use self::set::VecSet;
24pub use alloc::collections::TryReserveError;
25use alloc::vec::Vec;
26
27// The type used to store entries in a `VecMap`.
28//
29// It is just a transparent wrapper around `(K, V)` with accessor methods for use in `map`
30// functions.
31#[repr(transparent)]
32#[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord)]
33struct Slot<K, V> {
34    data: (K, V),
35}
36
37impl<K, V> Slot<K, V> {
38    #[inline]
39    fn new(key: K, value: V) -> Self {
40        Slot { data: (key, value) }
41    }
42
43    #[inline]
44    fn key(&self) -> &K {
45        &self.data.0
46    }
47
48    #[inline]
49    fn key_mut(&mut self) -> &mut K {
50        &mut self.data.0
51    }
52
53    #[inline]
54    fn into_key(self) -> K {
55        self.data.0
56    }
57
58    #[inline]
59    fn value(&self) -> &V {
60        &self.data.1
61    }
62
63    #[inline]
64    fn value_mut(&mut self) -> &mut V {
65        &mut self.data.1
66    }
67
68    #[inline]
69    fn into_value(self) -> V {
70        self.data.1
71    }
72
73    #[inline]
74    fn refs(&self) -> (&K, &V) {
75        (&self.data.0, &self.data.1)
76    }
77
78    #[inline]
79    fn ref_mut(&mut self) -> (&K, &mut V) {
80        (&self.data.0, &mut self.data.1)
81    }
82
83    #[inline]
84    fn muts(&mut self) -> (&mut K, &mut V) {
85        (&mut self.data.0, &mut self.data.1)
86    }
87
88    #[inline]
89    fn into_key_value(self) -> (K, V) {
90        self.data
91    }
92}
93
94// Trait for obtaining access to the entries in a collection.
95trait Entries {
96    type Entry;
97
98    fn as_entries(&self) -> &[Self::Entry];
99
100    fn as_entries_mut(&mut self) -> &mut [Self::Entry];
101
102    fn into_entries(self) -> Vec<Self::Entry>;
103}
104
105/// Deduplicate elements in an unsorted vector.
106fn dedup<T>(vec: &mut Vec<T>, eq_fn: impl Fn(&T, &T) -> bool) {
107    let mut out = 1;
108    let len = vec.len();
109    for i in 1..len {
110        if (0..i).all(|j| !eq_fn(&vec[i], &vec[j])) {
111            vec.swap(out, i);
112            out += 1;
113        }
114    }
115    vec.truncate(out);
116}
117
118/// Cast a `Vec<T>` into a `Vec<U>`.
119///
120/// # Safety
121///
122/// Callers must ensure that `T` and `U` have the same memory layout.
123unsafe fn transmute_vec<T, U>(mut vec: Vec<T>) -> Vec<U> {
124    let (ptr, len, cap) = (vec.as_mut_ptr(), vec.len(), vec.capacity());
125    core::mem::forget(vec);
126    // SAFETY: callers must uphold the invariants of `T` and `U` mentioned in the function doc.
127    unsafe { Vec::from_raw_parts(ptr.cast(), len, cap) }
128}
129
130#[test]
131fn test_dedup() {
132    fn test(want: &[u32], arr: &[u32]) {
133        let mut vec = arr.to_vec();
134        dedup(&mut vec, |i, j| i == j);
135        assert_eq!(want, vec.as_slice());
136    }
137
138    test(&[], &[]);
139    test(&[1], &[1]);
140    test(&[1], &[1, 1]);
141    test(&[1], &[1, 1, 1]);
142    test(&[3, 1, 2], &[3, 1, 2]);
143    test(&[3, 1, 2], &[3, 1, 2, 1, 2, 3]);
144}
145
146// https://github.com/martinohmann/vecmap-rs/issues/18
147//
148// If `Slot<K, V>` does not have the same memory layout as `(K, V)`, e.g. due to possible field
149// reordering, this test will:
150//
151// - Segfault with "SIGSEGV: invalid memory reference" in the `unsafe` block in `VecMap::as_slice`
152//   when run via `cargo test`.
153// - Trigger a miri error when run via `cargo +nightly miri test`.
154#[test]
155fn issue_18() {
156    use alloc::string::String;
157    use core::{fmt, mem};
158
159    fn test<K, V>(slice: &[(K, V)])
160    where
161        K: Clone + Eq + fmt::Debug,
162        V: Clone + PartialEq + fmt::Debug,
163    {
164        assert_eq!(mem::size_of::<Slot<K, V>>(), mem::size_of::<(K, V)>());
165        assert_eq!(mem::align_of::<Slot<K, V>>(), mem::align_of::<(K, V)>());
166
167        let map = VecMap::from(slice);
168        assert_eq!(map.as_slice(), slice);
169    }
170
171    test(&[(1i64, String::from("foo")), (2, String::from("bar"))]);
172    test(&[(String::from("foo"), 1i64), (String::from("bar"), 2)]);
173    test(&[(true, 1i64), (false, 2)]);
174    test(&[(1i64, true), (2, false)]);
175}
vecmap/lib.rs

vecmap/
lib.rs
