3929938005

Build Type

push

github

Committed by GitHub

Commit Message

Merge #713

Run Details

84930 of 96741 relevant lines covered (87.79%)

79640.1 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.06

/operators/src/processing/circle_merging_quadtree/hash_map.rs

use std::{fmt::Debug, hash::Hasher};

use num_traits::AsPrimitive;
use rustc_hash::FxHasher;

/// A hash map implementation that uses separate chaining for collision detection.
/// This allows stable iteration over the keys independent of the order of insertion.
#[derive(Debug, Clone)]
pub struct SeparateChainingHashMap<K, V>
where
    K: Copy + Debug,
    V: Clone + Debug,
{
    table: Vec<Bucket<K, V>>,
    bucket_mask: usize,
    entries_left: usize,
}

/// A bucket in the hash map.
/// A filled bucket is most of the time a single element,
/// but may contain more elements in the case of collisions.
#[derive(Debug, Clone)]
pub enum Bucket<K, V>
where
    K: Copy + Debug,
    V: Clone + Debug,
{
    Empty,
    Single(Entry<K, V>),
    Multi(Vec<Entry<K, V>>),
}

impl<K, V> Default for Bucket<K, V>
where
    K: Copy + Debug,
    V: Clone + Debug,
{
    fn default() -> Self {
        Bucket::Empty
    }
}

impl<K, V> Bucket<K, V>
where
    K: Copy + Debug,
    V: Clone + Debug,
{
    fn insert_entry(&mut self, entry: Entry<K, V>) {
        match self {
            Bucket::Empty => *self = Bucket::Single(entry),
            Bucket::Single(_) => {
                if let Bucket::Single(old_entry) = std::mem::replace(self, Bucket::Empty) {
                    *self = Bucket::Multi(vec![old_entry, entry]);
                }
            }
            Bucket::Multi(entries) => entries.push(entry),
        };
    }
}

/// A hash map entry that stores its key.
#[derive(Debug, Clone)]
pub struct Entry<K, V>
// where
//     K: PartialOrd + PartialEq,
{
    key: K,
    value: V,
}

/// Equality by key
impl<K, V> PartialEq for Entry<K, V>
where
    K: PartialEq,
{
    fn eq(&self, other: &Self) -> bool {
        self.key == other.key
    }
}

impl<K, V> Eq for Entry<K, V> where K: Eq {}

/// Ordering by key
impl<K, V> PartialOrd for Entry<K, V>
where
    K: PartialOrd,
{
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        self.key.partial_cmp(&other.key)
    }
}

/// Ordering by key
impl<K, V> Ord for Entry<K, V>
where
    K: Ord,
{
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.key.cmp(&other.key)
    }
}

#[derive(Debug)]
pub enum ValueRef<'e, K, V> {
    Vacant(VacantEntryPos<K>),
    Occupied(&'e mut V),
}

#[derive(Debug, Clone, Copy)]
pub struct VacantEntryPos<K> {
    hash: usize,
    bucket_index: usize,
    key: K,
}

impl<K, V> SeparateChainingHashMap<K, V>
where
    K: Copy + Debug + AsPrimitive<usize> + Eq + Ord,
    V: Clone + Debug,
{
    pub fn new() -> Self {
        Self {
            table: vec![Bucket::default(); 2],
            bucket_mask: 1,
            entries_left: Self::bucket_mask_to_capacity(1),
        }
    }

    pub fn entry(&mut self, key: K) -> ValueRef<'_, K, V> {
        let hash = Self::hash(key);

        let bucket_index = hash & self.bucket_mask;

        for entry in &mut self.table[bucket_index] {
            if entry.key == key {
                return ValueRef::Occupied(&mut entry.value);
            }
        }

        ValueRef::Vacant(VacantEntryPos {
            hash,
            bucket_index,
            key,
        })
    }

    pub fn insert_unchecked(&mut self, entry_pos: VacantEntryPos<K>, value: V) {
        let VacantEntryPos {
            hash,
            mut bucket_index,
            key,
        } = entry_pos;

        if self.entries_left == 0 {
            // would insert, so resize
            self.resize();

            // update bucket_index due to new hash table size
            bucket_index = hash & self.bucket_mask;
        }

        self.table[bucket_index].insert_entry(Entry { key, value });

        self.entries_left -= 1;
    }

    fn resize(&mut self) {
        let table_size = 2 * self.table.len();

        let old_table = std::mem::replace(&mut self.table, vec![Bucket::default(); table_size]);

        self.bucket_mask = table_size - 1;
        self.entries_left = Self::bucket_mask_to_capacity(self.bucket_mask);

        // re-insert all entries into larger table
        for entry in old_table.into_iter().flat_map(Bucket::into_iter) {
            let bucket_index = Self::hash(entry.key) & self.bucket_mask;
            self.table[bucket_index].insert_entry(entry);
            self.entries_left -= 1;
        }
    }

    #[inline]
    fn hash(key: K) -> usize {
        let mut hasher = FxHasher::default();
        hasher.write_usize(key.as_());
        hasher.finish() as usize
    }

    #[inline]
    fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {
        if bucket_mask < 8 {
            // For tables with 1/2/4/8 buckets, we always reserve one empty slot.
            // Keep in mind that the bucket mask is one less than the bucket count.
            bucket_mask
        } else {
            // For larger tables we reserve 12.5% of the slots as empty.
            ((bucket_mask + 1) / 8) * 7
        }
    }

    #[allow(unused)]
    pub fn capacity(&self) -> usize {
        self.table.len()
    }
}

type BucketVecIter<K, V> = std::vec::IntoIter<Bucket<K, V>>;
type BucketEntriesIter<K, V> = std::iter::FlatMap<
    BucketVecIter<K, V>,
    BucketIterator<K, V>,
    fn(Bucket<K, V>) -> BucketIterator<K, V>,
>;
type BucketEntryValuesIter<K, V> = std::iter::Map<BucketEntriesIter<K, V>, fn(Entry<K, V>) -> V>;

impl<K, V> IntoIterator for SeparateChainingHashMap<K, V>
where
    K: Copy + Debug + Ord,
    V: Clone + Debug,
{
    type Item = V;

    type IntoIter = BucketEntryValuesIter<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        let buckets: BucketVecIter<K, V> = self.table.into_iter();
        let entries: BucketEntriesIter<K, V> = buckets.flat_map(Bucket::into_iter);

        entries.map(Entry::value)
    }
}

impl<K, V> Entry<K, V> {
    fn value(self) -> V {
        self.value
    }
}

pub enum BucketIterator<K, V> {
    Empty,
    Single(std::iter::Once<Entry<K, V>>),
    Multi(std::vec::IntoIter<Entry<K, V>>),
}

impl<K, V> Iterator for BucketIterator<K, V> {
    type Item = Entry<K, V>;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            BucketIterator::Empty => None,
            BucketIterator::Single(iter) => iter.next(),
            BucketIterator::Multi(iter) => iter.next(),
        }
    }
}

impl<K, V> IntoIterator for Bucket<K, V>
where
    K: Copy + Debug + Ord,
    V: Clone + Debug,
{
    type Item = Entry<K, V>;

    type IntoIter = BucketIterator<K, V>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Bucket::Empty => BucketIterator::Empty,
            Bucket::Single(e) => BucketIterator::Single(std::iter::once(e)),
            Bucket::Multi(mut es) => {
                es.sort_unstable();
                BucketIterator::Multi(es.into_iter())
            }
        }
    }
}

pub enum BucketRefMutIterator<'e, K, V> {
    Empty,
    Single(std::iter::Once<&'e mut Entry<K, V>>),
    Multi(std::slice::IterMut<'e, Entry<K, V>>),
}

impl<'e, K, V> Iterator for BucketRefMutIterator<'e, K, V> {
    type Item = &'e mut Entry<K, V>;

    fn next(&mut self) -> Option<Self::Item> {
        match self {
            BucketRefMutIterator::Empty => None,
            BucketRefMutIterator::Single(iter) => iter.next(),
            BucketRefMutIterator::Multi(iter) => iter.next(),
        }
    }
}

impl<'e, K, V> IntoIterator for &'e mut Bucket<K, V>
where
    K: Copy + Debug,
    V: Clone + Debug,
{
    type Item = &'e mut Entry<K, V>;

    type IntoIter = BucketRefMutIterator<'e, K, V>;

    fn into_iter(self) -> Self::IntoIter {
        match self {
            Bucket::Empty => BucketRefMutIterator::Empty,
            Bucket::Single(e) => BucketRefMutIterator::Single(std::iter::once(e)),
            Bucket::Multi(es) => BucketRefMutIterator::Multi(es.iter_mut()),
        }
    }
}

#[cfg(test)]
mod tests {
    use rand::prelude::SliceRandom;
    use rand::SeedableRng;

    use super::*;

    fn insert<K, V>(map: &mut SeparateChainingHashMap<K, V>, key: K, value: V)
    where
        K: Copy + Debug + Ord + AsPrimitive<usize>,
        V: Clone + Debug,
    {
        match map.entry(key) {
            ValueRef::Occupied(_) => panic!("key already exists: {key:?}"),
            ValueRef::Vacant(entry_pos) => {
                map.insert_unchecked(entry_pos, value);
            }
        }
    }

    #[test]
    fn capacity() {
        let mut map = SeparateChainingHashMap::<u32, u32>::new();

        let mut capacities = Vec::new();
        for i in 0..5 {
            insert(&mut map, i, i);
            capacities.push(map.capacity());
        }

        assert_eq!(capacities, vec![2, 4, 4, 8, 8]);

        for i in 5..113 {
            insert(&mut map, i, i);
        }

        assert_eq!(map.capacity(), 256);

        for i in 113..128 {
            insert(&mut map, i, i);
        }

        assert_eq!(map.capacity(), 256);
    }

    #[test]
    fn insert_and_retrieve() {
        let mut map = SeparateChainingHashMap::<u32, u32>::new();

        let mut result = Vec::new();
        for i in 0..128 {
            insert(&mut map, i, i);
            result.push(i);
        }

        let mut all_values = map.into_iter().collect::<Vec<_>>();
        all_values.sort_unstable();
        assert_eq!(all_values, result);
    }

    #[test]
    fn insert_and_lookup() {
        let mut map = SeparateChainingHashMap::<u32, u32>::new();

        for i in 0..128 {
            insert(&mut map, i, i);

            match map.entry(i) {
                ValueRef::Vacant(_) => panic!("key not found: {i}"),
                ValueRef::Occupied(_) => (), // okay
            };
        }
    }

    #[test]
    fn insertion_order() {
        let values: Vec<u16> = (0..256).collect();
        let shuffled_values = {
            let mut values = values.clone();
            let mut rng = rand::rngs::StdRng::seed_from_u64(42);
            values.shuffle(&mut rng);
            values
        };

        let mut map1 = SeparateChainingHashMap::<u16, u16>::new();
        for v in values {
            insert(&mut map1, v, v);
        }

        let mut map2 = SeparateChainingHashMap::<u16, u16>::new();
        for v in shuffled_values {
            insert(&mut map2, v, v);
        }

        assert_eq!(
            map1.into_iter().collect::<Vec<_>>(),
            map2.into_iter().collect::<Vec<_>>()
        );
    }
}

1	use std::{fmt::Debug, hash::Hasher};
2
3	use num_traits::AsPrimitive;
4	use rustc_hash::FxHasher;
5
6	/// A hash map implementation that uses separate chaining for collision detection.
7	/// This allows stable iteration over the keys independent of the order of insertion.
8	#[derive(Debug, Clone)]	×
9	pub struct SeparateChainingHashMap<K, V>
10	where
11	K: Copy + Debug,
12	V: Clone + Debug,
13	{
14	table: Vec<Bucket<K, V>>,
15	bucket_mask: usize,
16	entries_left: usize,
17	}
18
19	/// A bucket in the hash map.
20	/// A filled bucket is most of the time a single element,
21	/// but may contain more elements in the case of collisions.
22	#[derive(Debug, Clone)]	3,552✔
23	pub enum Bucket<K, V>
24	where
25	K: Copy + Debug,
26	V: Clone + Debug,
27	{
28	Empty,
29	Single(Entry<K, V>),
30	Multi(Vec<Entry<K, V>>),
31	}
32
33	impl<K, V> Default for Bucket<K, V>
34	where
35	K: Copy + Debug,
36	V: Clone + Debug,
37	{
38	fn default() -> Self {	52✔
39	Bucket::Empty	52✔
40	}	52✔
41	}
42
43	impl<K, V> Bucket<K, V>
44	where
45	K: Copy + Debug,
46	V: Clone + Debug,
47	{
48	fn insert_entry(&mut self, entry: Entry<K, V>) {	2,465✔
49	match self {	2,465✔
50	Bucket::Empty => *self = Bucket::Single(entry),	2,409✔
51	Bucket::Single(_) => {
52	if let Bucket::Single(old_entry) = std::mem::replace(self, Bucket::Empty) {	53✔
53	*self = Bucket::Multi(vec![old_entry, entry]);	53✔
54	}	53✔
55	}
56	Bucket::Multi(entries) => entries.push(entry),	3✔
57	};
58	}	2,465✔
59	}
60
61	/// A hash map entry that stores its key.
62	#[derive(Debug, Clone)]	×
63	pub struct Entry<K, V>
64	// where
65	// K: PartialOrd + PartialEq,
66	{
67	key: K,
68	value: V,
69	}
70
71	/// Equality by key
72	impl<K, V> PartialEq for Entry<K, V>
73	where
74	K: PartialEq,
75	{
76	fn eq(&self, other: &Self) -> bool {	×
77	self.key == other.key	×
78	}	×
79	}
80
81	impl<K, V> Eq for Entry<K, V> where K: Eq {}
82
83	/// Ordering by key
84	impl<K, V> PartialOrd for Entry<K, V>
85	where
86	K: PartialOrd,
87	{
88	fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {	59✔
89	self.key.partial_cmp(&other.key)	59✔
90	}	59✔
91	}
92
93	/// Ordering by key
94	impl<K, V> Ord for Entry<K, V>
95	where
96	K: Ord,
97	{
98	fn cmp(&self, other: &Self) -> std::cmp::Ordering {	×
99	self.key.cmp(&other.key)	×
100	}	×
101	}
102
103	#[derive(Debug)]	×
104	pub enum ValueRef<'e, K, V> {
105	Vacant(VacantEntryPos<K>),
106	Occupied(&'e mut V),
107	}
108
109	#[derive(Debug, Clone, Copy)]	×
110	pub struct VacantEntryPos<K> {
111	hash: usize,
112	bucket_index: usize,
113	key: K,
114	}
115
116	impl<K, V> SeparateChainingHashMap<K, V>
117	where
118	K: Copy + Debug + AsPrimitive<usize> + Eq + Ord,
119	V: Clone + Debug,
120	{
121	pub fn new() -> Self {	10✔
122	Self {	10✔
123	table: vec![Bucket::default(); 2],	10✔
124	bucket_mask: 1,	10✔
125	entries_left: Self::bucket_mask_to_capacity(1),	10✔
126	}	10✔
127	}	10✔
128
129	pub fn entry(&mut self, key: K) -> ValueRef<'_, K, V> {	1,057✔
130	let hash = Self::hash(key);	1,057✔
131		1,057✔
132	let bucket_index = hash & self.bucket_mask;	1,057✔
133
134	for entry in &mut self.table[bucket_index] {	1,057✔
135	if entry.key == key {	202✔
136	return ValueRef::Occupied(&mut entry.value);	150✔
137	}	52✔
138	}
139
140	ValueRef::Vacant(VacantEntryPos {	907✔
141	hash,	907✔
142	bucket_index,	907✔
143	key,	907✔
144	})	907✔
145	}	1,057✔
146
147	pub fn insert_unchecked(&mut self, entry_pos: VacantEntryPos<K>, value: V) {	907✔
148	let VacantEntryPos {	907✔
149	hash,	907✔
150	mut bucket_index,	907✔
151	key,	907✔
152	} = entry_pos;	907✔
153		907✔
154	if self.entries_left == 0 {	907✔
155	// would insert, so resize	42✔
156	self.resize();	42✔
157		42✔
158	// update bucket_index due to new hash table size	42✔
159	bucket_index = hash & self.bucket_mask;	42✔
160	}	865✔
161
162	self.table[bucket_index].insert_entry(Entry { key, value });	907✔
163		907✔
164	self.entries_left -= 1;	907✔
165	}	907✔
166
167	fn resize(&mut self) {	42✔
168	let table_size = 2 * self.table.len();	42✔
169		42✔
170	let old_table = std::mem::replace(&mut self.table, vec![Bucket::default(); table_size]);	42✔
171		42✔
172	self.bucket_mask = table_size - 1;	42✔
173	self.entries_left = Self::bucket_mask_to_capacity(self.bucket_mask);	42✔
174
175	// re-insert all entries into larger table
176	for entry in old_table.into_iter().flat_map(Bucket::into_iter) {	1,558✔
177	let bucket_index = Self::hash(entry.key) & self.bucket_mask;	1,558✔
178	self.table[bucket_index].insert_entry(entry);	1,558✔
179	self.entries_left -= 1;	1,558✔
180	}	1,558✔
181	}	42✔
182
183	#[inline]
184	fn hash(key: K) -> usize {	2,615✔
185	let mut hasher = FxHasher::default();	2,615✔
186	hasher.write_usize(key.as_());	2,615✔
187	hasher.finish() as usize	2,615✔
188	}	2,615✔
189
190	#[inline]
191	fn bucket_mask_to_capacity(bucket_mask: usize) -> usize {	52✔
192	if bucket_mask < 8 {	52✔
193	// For tables with 1/2/4/8 buckets, we always reserve one empty slot.
194	// Keep in mind that the bucket mask is one less than the bucket count.
195	bucket_mask	25✔
196	} else {
197	// For larger tables we reserve 12.5% of the slots as empty.
198	((bucket_mask + 1) / 8) * 7	27✔
199	}
200	}	52✔
201
202	#[allow(unused)]
203	pub fn capacity(&self) -> usize {	7✔
204	self.table.len()	7✔
205	}	7✔
206	}
207
208	type BucketVecIter<K, V> = std::vec::IntoIter<Bucket<K, V>>;
209	type BucketEntriesIter<K, V> = std::iter::FlatMap<
210	BucketVecIter<K, V>,
211	BucketIterator<K, V>,
212	fn(Bucket<K, V>) -> BucketIterator<K, V>,
213	>;
214	type BucketEntryValuesIter<K, V> = std::iter::Map<BucketEntriesIter<K, V>, fn(Entry<K, V>) -> V>;
215
216	impl<K, V> IntoIterator for SeparateChainingHashMap<K, V>
217	where
218	K: Copy + Debug + Ord,
219	V: Clone + Debug,
220	{
221	type Item = V;
222
223	type IntoIter = BucketEntryValuesIter<K, V>;
224
225	fn into_iter(self) -> Self::IntoIter {	8✔
226	let buckets: BucketVecIter<K, V> = self.table.into_iter();	8✔
227	let entries: BucketEntriesIter<K, V> = buckets.flat_map(Bucket::into_iter);	8✔
228		8✔
229	entries.map(Entry::value)	8✔
230	}	8✔
231	}
232
233	impl<K, V> Entry<K, V> {
234	fn value(self) -> V {	651✔
235	self.value	651✔
236	}	651✔
237	}
238
239	pub enum BucketIterator<K, V> {
240	Empty,
241	Single(std::iter::Once<Entry<K, V>>),
242	Multi(std::vec::IntoIter<Entry<K, V>>),
243	}
244
245	impl<K, V> Iterator for BucketIterator<K, V> {
246	type Item = Entry<K, V>;
247
248	fn next(&mut self) -> Option<Self::Item> {	5,301✔
249	match self {	5,301✔
250	BucketIterator::Empty => None,	939✔
251	BucketIterator::Single(iter) => iter.next(),	4,200✔
252	BucketIterator::Multi(iter) => iter.next(),	162✔
253	}
254	}	5,301✔
255	}
256
257	impl<K, V> IntoIterator for Bucket<K, V>
258	where
259	K: Copy + Debug + Ord,
260	V: Clone + Debug,
261	{
262	type Item = Entry<K, V>;
263
264	type IntoIter = BucketIterator<K, V>;
265
266	fn into_iter(self) -> Self::IntoIter {	3,092✔
267	match self {	3,092✔
268	Bucket::Empty => BucketIterator::Empty,	939✔
269	Bucket::Single(e) => BucketIterator::Single(std::iter::once(e)),	2,100✔
270	Bucket::Multi(mut es) => {	53✔
271	es.sort_unstable();	53✔
272	BucketIterator::Multi(es.into_iter())	53✔
273	}
274	}
275	}	3,092✔
276	}
277
278	pub enum BucketRefMutIterator<'e, K, V> {
279	Empty,
280	Single(std::iter::Once<&'e mut Entry<K, V>>),
281	Multi(std::slice::IterMut<'e, Entry<K, V>>),
282	}
283
284	impl<'e, K, V> Iterator for BucketRefMutIterator<'e, K, V> {
285	type Item = &'e mut Entry<K, V>;
286
287	fn next(&mut self) -> Option<Self::Item> {	1,109✔
288	match self {	1,109✔
289	BucketRefMutIterator::Empty => None,	860✔
290	BucketRefMutIterator::Single(iter) => iter.next(),	235✔
291	BucketRefMutIterator::Multi(iter) => iter.next(),	14✔
292	}
293	}	1,109✔
294	}
295
296	impl<'e, K, V> IntoIterator for &'e mut Bucket<K, V>
297	where
298	K: Copy + Debug,
299	V: Clone + Debug,
300	{
301	type Item = &'e mut Entry<K, V>;
302
303	type IntoIter = BucketRefMutIterator<'e, K, V>;
304
305	fn into_iter(self) -> Self::IntoIter {	1,057✔
306	match self {	1,057✔
307	Bucket::Empty => BucketRefMutIterator::Empty,	860✔
308	Bucket::Single(e) => BucketRefMutIterator::Single(std::iter::once(e)),	192✔
309	Bucket::Multi(es) => BucketRefMutIterator::Multi(es.iter_mut()),	5✔
310	}
311	}	1,057✔
312	}
313
314	#[cfg(test)]
315	mod tests {
316	use rand::prelude::SliceRandom;
317	use rand::SeedableRng;
318
319	use super::*;
320
321	fn insert<K, V>(map: &mut SeparateChainingHashMap<K, V>, key: K, value: V)	896✔
322	where	896✔
323	K: Copy + Debug + Ord + AsPrimitive<usize>,	896✔
324	V: Clone + Debug,	896✔
325	{	896✔
326	match map.entry(key) {	896✔
327	ValueRef::Occupied(_) => panic!("key already exists: {key:?}"),	×
328	ValueRef::Vacant(entry_pos) => {	896✔
329	map.insert_unchecked(entry_pos, value);	896✔
330	}	896✔
331	}	896✔
332	}	896✔
333
334	#[test]	1✔
335	fn capacity() {	1✔
336	let mut map = SeparateChainingHashMap::<u32, u32>::new();	1✔
337		1✔
338	let mut capacities = Vec::new();	1✔
339	for i in 0..5 {	6✔
340	insert(&mut map, i, i);	5✔
341	capacities.push(map.capacity());	5✔
342	}	5✔
343
344	assert_eq!(capacities, vec![2, 4, 4, 8, 8]);	1✔
345
346	for i in 5..113 {	109✔
347	insert(&mut map, i, i);	108✔
348	}	108✔
349
350	assert_eq!(map.capacity(), 256);	1✔
351
352	for i in 113..128 {	16✔
353	insert(&mut map, i, i);	15✔
354	}	15✔
355
356	assert_eq!(map.capacity(), 256);	1✔
357	}	1✔
358
359	#[test]	1✔
360	fn insert_and_retrieve() {	1✔
361	let mut map = SeparateChainingHashMap::<u32, u32>::new();	1✔
362		1✔
363	let mut result = Vec::new();	1✔
364	for i in 0..128 {	129✔
365	insert(&mut map, i, i);	128✔
366	result.push(i);	128✔
367	}	128✔
368
369	let mut all_values = map.into_iter().collect::<Vec<_>>();	1✔
370	all_values.sort_unstable();	1✔
371	assert_eq!(all_values, result);	1✔
372	}	1✔
373
374	#[test]	1✔
375	fn insert_and_lookup() {	1✔
376	let mut map = SeparateChainingHashMap::<u32, u32>::new();	1✔
377
378	for i in 0..128 {	129✔
379	insert(&mut map, i, i);	128✔
380		128✔
381	match map.entry(i) {	128✔
382	ValueRef::Vacant(_) => panic!("key not found: {i}"),	×
383	ValueRef::Occupied(_) => (), // okay	128✔
384	};
385	}
386	}	1✔
387
388	#[test]	1✔
389	fn insertion_order() {	1✔
390	let values: Vec<u16> = (0..256).collect();	1✔
391	let shuffled_values = {	1✔
392	let mut values = values.clone();	1✔
393	let mut rng = rand::rngs::StdRng::seed_from_u64(42);	1✔
394	values.shuffle(&mut rng);	1✔
395	values	1✔
396	};	1✔
397		1✔
398	let mut map1 = SeparateChainingHashMap::<u16, u16>::new();	1✔
399	for v in values {	257✔
400	insert(&mut map1, v, v);	256✔
401	}	256✔
402
403	let mut map2 = SeparateChainingHashMap::<u16, u16>::new();	1✔
404	for v in shuffled_values {	257✔
405	insert(&mut map2, v, v);	256✔
406	}	256✔
407
408	assert_eq!(	1✔
409	map1.into_iter().collect::<Vec<_>>(),	1✔
410	map2.into_iter().collect::<Vec<_>>()	1✔
411	);	1✔
412	}	1✔
413	}

geo-engine / geoengine / 3929938005

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous