vecmap/
lib.rs

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

vecmap/
lib.rs
