]>
Commit | Line | Data |
---|---|---|
29967ef6 XL |
1 | use super::Entry::{Occupied, Vacant}; |
2 | use super::*; | |
3dfed10e | 3 | use crate::boxed::Box; |
3dfed10e XL |
4 | use crate::fmt::Debug; |
5 | use crate::rc::Rc; | |
29967ef6 | 6 | use crate::string::{String, ToString}; |
9c376795 FG |
7 | use crate::testing::crash_test::{CrashTestDummy, Panic}; |
8 | use crate::testing::ord_chaos::{Cyclic3, Governed, Governor}; | |
9 | use crate::testing::rng::DeterministicRng; | |
3dfed10e | 10 | use crate::vec::Vec; |
fc512014 | 11 | use std::cmp::Ordering; |
dfeec247 | 12 | use std::convert::TryFrom; |
29967ef6 | 13 | use std::iter::{self, FromIterator}; |
3dfed10e | 14 | use std::mem; |
0531ce1d | 15 | use std::ops::Bound::{self, Excluded, Included, Unbounded}; |
dfeec247 | 16 | use std::ops::RangeBounds; |
ba9703b0 | 17 | use std::panic::{catch_unwind, AssertUnwindSafe}; |
fc512014 XL |
18 | use std::sync::atomic::{AtomicUsize, Ordering::SeqCst}; |
19 | ||
3dfed10e | 20 | // Minimum number of elements to insert, to guarantee a tree with 2 levels, |
29967ef6 | 21 | // i.e., a tree who's root is an internal node at height 1, with edges to leaf nodes. |
ba9703b0 | 22 | // It's not the minimum size: removing an element from such a tree does not always reduce height. |
5e7ed085 | 23 | const MIN_INSERTS_HEIGHT_1: usize = node::CAPACITY + 1; |
ba9703b0 | 24 | |
3dfed10e | 25 | // Minimum number of elements to insert in ascending order, to guarantee a tree with 3 levels, |
29967ef6 | 26 | // i.e., a tree who's root is an internal node at height 2, with edges to more internal nodes. |
ba9703b0 | 27 | // It's not the minimum size: removing an element from such a tree does not always reduce height. |
3dfed10e XL |
28 | const MIN_INSERTS_HEIGHT_2: usize = 89; |
29 | ||
fc512014 | 30 | // Gathers all references from a mutable iterator and makes sure Miri notices if |
3dfed10e XL |
31 | // using them is dangerous. |
32 | fn test_all_refs<'a, T: 'a>(dummy: &mut T, iter: impl Iterator<Item = &'a mut T>) { | |
33 | // Gather all those references. | |
34 | let mut refs: Vec<&mut T> = iter.collect(); | |
35 | // Use them all. Twice, to be sure we got all interleavings. | |
36 | for r in refs.iter_mut() { | |
37 | mem::swap(dummy, r); | |
38 | } | |
39 | for r in refs { | |
40 | mem::swap(dummy, r); | |
41 | } | |
42 | } | |
43 | ||
29967ef6 | 44 | impl<K, V> BTreeMap<K, V> { |
fc512014 XL |
45 | // Panics if the map (or the code navigating it) is corrupted. |
46 | fn check_invariants(&self) { | |
3dfed10e | 47 | if let Some(root) = &self.root { |
fc512014 | 48 | let root_node = root.reborrow(); |
3dfed10e | 49 | |
fc512014 XL |
50 | // Check the back pointers top-down, before we attempt to rely on |
51 | // more serious navigation code. | |
29967ef6 XL |
52 | assert!(root_node.ascend().is_err()); |
53 | root_node.assert_back_pointers(); | |
1b1a35ee | 54 | |
fc512014 | 55 | // Check consistency of `length` with what navigation code encounters. |
29967ef6 | 56 | assert_eq!(self.length, root_node.calc_length()); |
3dfed10e | 57 | |
fc512014 | 58 | // Lastly, check the invariant causing the least harm. |
29967ef6 | 59 | root_node.assert_min_len(if root_node.height() > 0 { 1 } else { 0 }); |
3dfed10e XL |
60 | } else { |
61 | assert_eq!(self.length, 0); | |
62 | } | |
29967ef6 | 63 | |
fc512014 XL |
64 | // Check that `assert_strictly_ascending` will encounter all keys. |
65 | assert_eq!(self.length, self.keys().count()); | |
3dfed10e XL |
66 | } |
67 | ||
fc512014 XL |
68 | // Panics if the map is corrupted or if the keys are not in strictly |
69 | // ascending order, in the current opinion of the `Ord` implementation. | |
70 | // If the `Ord` implementation violates transitivity, this method does not | |
71 | // guarantee that all keys are unique, just that adjacent keys are unique. | |
72 | fn check(&self) | |
73 | where | |
74 | K: Debug + Ord, | |
75 | { | |
76 | self.check_invariants(); | |
77 | self.assert_strictly_ascending(); | |
78 | } | |
79 | ||
80 | // Returns the height of the root, if any. | |
3dfed10e XL |
81 | fn height(&self) -> Option<usize> { |
82 | self.root.as_ref().map(node::Root::height) | |
83 | } | |
84 | ||
85 | fn dump_keys(&self) -> String | |
86 | where | |
87 | K: Debug, | |
88 | { | |
89 | if let Some(root) = self.root.as_ref() { | |
fc512014 | 90 | root.reborrow().dump_keys() |
3dfed10e XL |
91 | } else { |
92 | String::from("not yet allocated") | |
93 | } | |
94 | } | |
29967ef6 | 95 | |
fc512014 XL |
96 | // Panics if the keys are not in strictly ascending order. |
97 | fn assert_strictly_ascending(&self) | |
29967ef6 | 98 | where |
fc512014 | 99 | K: Debug + Ord, |
29967ef6 | 100 | { |
29967ef6 XL |
101 | let mut keys = self.keys(); |
102 | if let Some(mut previous) = keys.next() { | |
29967ef6 XL |
103 | for next in keys { |
104 | assert!(previous < next, "{:?} >= {:?}", previous, next); | |
105 | previous = next; | |
29967ef6 XL |
106 | } |
107 | } | |
29967ef6 | 108 | } |
5869c6ff XL |
109 | |
110 | // Transform the tree to minimize wasted space, obtaining fewer nodes that | |
111 | // are mostly filled up to their capacity. The same compact tree could have | |
112 | // been obtained by inserting keys in a shrewd order. | |
113 | fn compact(&mut self) | |
114 | where | |
115 | K: Ord, | |
116 | { | |
117 | let iter = mem::take(self).into_iter(); | |
5e7ed085 | 118 | if !iter.is_empty() { |
923072b8 | 119 | self.root.insert(Root::new(*self.alloc)).bulk_push(iter, &mut self.length, *self.alloc); |
5e7ed085 | 120 | } |
5869c6ff | 121 | } |
29967ef6 XL |
122 | } |
123 | ||
124 | impl<'a, K: 'a, V: 'a> NodeRef<marker::Immut<'a>, K, V, marker::LeafOrInternal> { | |
125 | fn assert_min_len(self, min_len: usize) { | |
fc512014 | 126 | assert!(self.len() >= min_len, "node len {} < {}", self.len(), min_len); |
29967ef6 XL |
127 | if let node::ForceResult::Internal(node) = self.force() { |
128 | for idx in 0..=node.len() { | |
129 | let edge = unsafe { Handle::new_edge(node, idx) }; | |
130 | edge.descend().assert_min_len(MIN_LEN); | |
131 | } | |
132 | } | |
133 | } | |
3dfed10e XL |
134 | } |
135 | ||
6a06907d XL |
136 | // Tests our value of MIN_INSERTS_HEIGHT_2. Failure may mean you just need to |
137 | // adapt that value to match a change in node::CAPACITY or the choices made | |
138 | // during insertion, otherwise other test cases may fail or be less useful. | |
3dfed10e XL |
139 | #[test] |
140 | fn test_levels() { | |
141 | let mut map = BTreeMap::new(); | |
142 | map.check(); | |
143 | assert_eq!(map.height(), None); | |
144 | assert_eq!(map.len(), 0); | |
145 | ||
146 | map.insert(0, ()); | |
147 | while map.height() == Some(0) { | |
148 | let last_key = *map.last_key_value().unwrap().0; | |
149 | map.insert(last_key + 1, ()); | |
150 | } | |
151 | map.check(); | |
152 | // Structure: | |
153 | // - 1 element in internal root node with 2 children | |
154 | // - 6 elements in left leaf child | |
155 | // - 5 elements in right leaf child | |
156 | assert_eq!(map.height(), Some(1)); | |
157 | assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1, "{}", map.dump_keys()); | |
158 | ||
159 | while map.height() == Some(1) { | |
160 | let last_key = *map.last_key_value().unwrap().0; | |
161 | map.insert(last_key + 1, ()); | |
162 | } | |
3dfed10e XL |
163 | map.check(); |
164 | // Structure: | |
165 | // - 1 element in internal root node with 2 children | |
166 | // - 6 elements in left internal child with 7 grandchildren | |
167 | // - 42 elements in left child's 7 grandchildren with 6 elements each | |
168 | // - 5 elements in right internal child with 6 grandchildren | |
169 | // - 30 elements in right child's 5 first grandchildren with 6 elements each | |
170 | // - 5 elements in right child's last grandchild | |
171 | assert_eq!(map.height(), Some(2)); | |
172 | assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2, "{}", map.dump_keys()); | |
173 | } | |
ba9703b0 | 174 | |
fc512014 XL |
175 | // Ensures the testing infrastructure usually notices order violations. |
176 | #[test] | |
177 | #[should_panic] | |
178 | fn test_check_ord_chaos() { | |
179 | let gov = Governor::new(); | |
5e7ed085 | 180 | let map = BTreeMap::from([(Governed(1, &gov), ()), (Governed(2, &gov), ())]); |
fc512014 XL |
181 | gov.flip(); |
182 | map.check(); | |
183 | } | |
184 | ||
185 | // Ensures the testing infrastructure doesn't always mind order violations. | |
186 | #[test] | |
187 | fn test_check_invariants_ord_chaos() { | |
188 | let gov = Governor::new(); | |
5e7ed085 | 189 | let map = BTreeMap::from([(Governed(1, &gov), ()), (Governed(2, &gov), ())]); |
fc512014 XL |
190 | gov.flip(); |
191 | map.check_invariants(); | |
192 | } | |
193 | ||
c34b1796 AL |
194 | #[test] |
195 | fn test_basic_large() { | |
196 | let mut map = BTreeMap::new(); | |
f9f354fc XL |
197 | // Miri is too slow |
198 | let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 } else { 10000 }; | |
3dfed10e | 199 | let size = size + (size % 2); // round up to even number |
c34b1796 AL |
200 | assert_eq!(map.len(), 0); |
201 | ||
202 | for i in 0..size { | |
3157f602 | 203 | assert_eq!(map.insert(i, 10 * i), None); |
c34b1796 AL |
204 | assert_eq!(map.len(), i + 1); |
205 | } | |
206 | ||
74b04a01 XL |
207 | assert_eq!(map.first_key_value(), Some((&0, &0))); |
208 | assert_eq!(map.last_key_value(), Some((&(size - 1), &(10 * (size - 1))))); | |
209 | assert_eq!(map.first_entry().unwrap().key(), &0); | |
210 | assert_eq!(map.last_entry().unwrap().key(), &(size - 1)); | |
211 | ||
c34b1796 | 212 | for i in 0..size { |
3157f602 | 213 | assert_eq!(map.get(&i).unwrap(), &(i * 10)); |
c34b1796 AL |
214 | } |
215 | ||
3157f602 | 216 | for i in size..size * 2 { |
c34b1796 AL |
217 | assert_eq!(map.get(&i), None); |
218 | } | |
219 | ||
220 | for i in 0..size { | |
3157f602 | 221 | assert_eq!(map.insert(i, 100 * i), Some(10 * i)); |
c34b1796 AL |
222 | assert_eq!(map.len(), size); |
223 | } | |
224 | ||
225 | for i in 0..size { | |
3157f602 | 226 | assert_eq!(map.get(&i).unwrap(), &(i * 100)); |
c34b1796 AL |
227 | } |
228 | ||
3157f602 XL |
229 | for i in 0..size / 2 { |
230 | assert_eq!(map.remove(&(i * 2)), Some(i * 200)); | |
c34b1796 AL |
231 | assert_eq!(map.len(), size - i - 1); |
232 | } | |
233 | ||
3157f602 XL |
234 | for i in 0..size / 2 { |
235 | assert_eq!(map.get(&(2 * i)), None); | |
236 | assert_eq!(map.get(&(2 * i + 1)).unwrap(), &(i * 200 + 100)); | |
c34b1796 AL |
237 | } |
238 | ||
3157f602 XL |
239 | for i in 0..size / 2 { |
240 | assert_eq!(map.remove(&(2 * i)), None); | |
241 | assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100)); | |
242 | assert_eq!(map.len(), size / 2 - i - 1); | |
c34b1796 | 243 | } |
3dfed10e | 244 | map.check(); |
c34b1796 AL |
245 | } |
246 | ||
247 | #[test] | |
248 | fn test_basic_small() { | |
249 | let mut map = BTreeMap::new(); | |
ba9703b0 | 250 | // Empty, root is absent (None): |
c34b1796 | 251 | assert_eq!(map.remove(&1), None); |
60c5eb7d | 252 | assert_eq!(map.len(), 0); |
dfeec247 XL |
253 | assert_eq!(map.get(&1), None); |
254 | assert_eq!(map.get_mut(&1), None); | |
60c5eb7d XL |
255 | assert_eq!(map.first_key_value(), None); |
256 | assert_eq!(map.last_key_value(), None); | |
dfeec247 XL |
257 | assert_eq!(map.keys().count(), 0); |
258 | assert_eq!(map.values().count(), 0); | |
259 | assert_eq!(map.range(..).next(), None); | |
260 | assert_eq!(map.range(..1).next(), None); | |
261 | assert_eq!(map.range(1..).next(), None); | |
262 | assert_eq!(map.range(1..=1).next(), None); | |
263 | assert_eq!(map.range(1..2).next(), None); | |
3dfed10e | 264 | assert_eq!(map.height(), None); |
c34b1796 | 265 | assert_eq!(map.insert(1, 1), None); |
3dfed10e XL |
266 | assert_eq!(map.height(), Some(0)); |
267 | map.check(); | |
dfeec247 XL |
268 | |
269 | // 1 key-value pair: | |
60c5eb7d | 270 | assert_eq!(map.len(), 1); |
c34b1796 | 271 | assert_eq!(map.get(&1), Some(&1)); |
dfeec247 | 272 | assert_eq!(map.get_mut(&1), Some(&mut 1)); |
60c5eb7d XL |
273 | assert_eq!(map.first_key_value(), Some((&1, &1))); |
274 | assert_eq!(map.last_key_value(), Some((&1, &1))); | |
dfeec247 XL |
275 | assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]); |
276 | assert_eq!(map.values().collect::<Vec<_>>(), vec![&1]); | |
c34b1796 | 277 | assert_eq!(map.insert(1, 2), Some(1)); |
60c5eb7d | 278 | assert_eq!(map.len(), 1); |
c34b1796 | 279 | assert_eq!(map.get(&1), Some(&2)); |
dfeec247 | 280 | assert_eq!(map.get_mut(&1), Some(&mut 2)); |
60c5eb7d XL |
281 | assert_eq!(map.first_key_value(), Some((&1, &2))); |
282 | assert_eq!(map.last_key_value(), Some((&1, &2))); | |
dfeec247 XL |
283 | assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1]); |
284 | assert_eq!(map.values().collect::<Vec<_>>(), vec![&2]); | |
c34b1796 | 285 | assert_eq!(map.insert(2, 4), None); |
3dfed10e XL |
286 | assert_eq!(map.height(), Some(0)); |
287 | map.check(); | |
dfeec247 XL |
288 | |
289 | // 2 key-value pairs: | |
60c5eb7d | 290 | assert_eq!(map.len(), 2); |
c34b1796 | 291 | assert_eq!(map.get(&2), Some(&4)); |
dfeec247 | 292 | assert_eq!(map.get_mut(&2), Some(&mut 4)); |
60c5eb7d XL |
293 | assert_eq!(map.first_key_value(), Some((&1, &2))); |
294 | assert_eq!(map.last_key_value(), Some((&2, &4))); | |
dfeec247 XL |
295 | assert_eq!(map.keys().collect::<Vec<_>>(), vec![&1, &2]); |
296 | assert_eq!(map.values().collect::<Vec<_>>(), vec![&2, &4]); | |
c34b1796 | 297 | assert_eq!(map.remove(&1), Some(2)); |
3dfed10e XL |
298 | assert_eq!(map.height(), Some(0)); |
299 | map.check(); | |
dfeec247 XL |
300 | |
301 | // 1 key-value pair: | |
60c5eb7d XL |
302 | assert_eq!(map.len(), 1); |
303 | assert_eq!(map.get(&1), None); | |
dfeec247 | 304 | assert_eq!(map.get_mut(&1), None); |
60c5eb7d | 305 | assert_eq!(map.get(&2), Some(&4)); |
dfeec247 | 306 | assert_eq!(map.get_mut(&2), Some(&mut 4)); |
60c5eb7d XL |
307 | assert_eq!(map.first_key_value(), Some((&2, &4))); |
308 | assert_eq!(map.last_key_value(), Some((&2, &4))); | |
dfeec247 XL |
309 | assert_eq!(map.keys().collect::<Vec<_>>(), vec![&2]); |
310 | assert_eq!(map.values().collect::<Vec<_>>(), vec![&4]); | |
c34b1796 | 311 | assert_eq!(map.remove(&2), Some(4)); |
3dfed10e XL |
312 | assert_eq!(map.height(), Some(0)); |
313 | map.check(); | |
dfeec247 | 314 | |
ba9703b0 | 315 | // Empty but root is owned (Some(...)): |
60c5eb7d | 316 | assert_eq!(map.len(), 0); |
dfeec247 XL |
317 | assert_eq!(map.get(&1), None); |
318 | assert_eq!(map.get_mut(&1), None); | |
60c5eb7d XL |
319 | assert_eq!(map.first_key_value(), None); |
320 | assert_eq!(map.last_key_value(), None); | |
dfeec247 XL |
321 | assert_eq!(map.keys().count(), 0); |
322 | assert_eq!(map.values().count(), 0); | |
323 | assert_eq!(map.range(..).next(), None); | |
324 | assert_eq!(map.range(..1).next(), None); | |
325 | assert_eq!(map.range(1..).next(), None); | |
326 | assert_eq!(map.range(1..=1).next(), None); | |
327 | assert_eq!(map.range(1..2).next(), None); | |
c34b1796 | 328 | assert_eq!(map.remove(&1), None); |
3dfed10e XL |
329 | assert_eq!(map.height(), Some(0)); |
330 | map.check(); | |
c34b1796 AL |
331 | } |
332 | ||
333 | #[test] | |
334 | fn test_iter() { | |
f9f354fc XL |
335 | // Miri is too slow |
336 | let size = if cfg!(miri) { 200 } else { 10000 }; | |
5e7ed085 | 337 | let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i))); |
c34b1796 | 338 | |
3157f602 | 339 | fn test<T>(size: usize, mut iter: T) |
dfeec247 XL |
340 | where |
341 | T: Iterator<Item = (usize, usize)>, | |
3157f602 | 342 | { |
c34b1796 AL |
343 | for i in 0..size { |
344 | assert_eq!(iter.size_hint(), (size - i, Some(size - i))); | |
345 | assert_eq!(iter.next().unwrap(), (i, i)); | |
346 | } | |
347 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
348 | assert_eq!(iter.next(), None); | |
349 | } | |
350 | test(size, map.iter().map(|(&k, &v)| (k, v))); | |
351 | test(size, map.iter_mut().map(|(&k, &mut v)| (k, v))); | |
352 | test(size, map.into_iter()); | |
353 | } | |
354 | ||
355 | #[test] | |
356 | fn test_iter_rev() { | |
f9f354fc XL |
357 | // Miri is too slow |
358 | let size = if cfg!(miri) { 200 } else { 10000 }; | |
5e7ed085 | 359 | let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i))); |
c34b1796 | 360 | |
3157f602 | 361 | fn test<T>(size: usize, mut iter: T) |
dfeec247 XL |
362 | where |
363 | T: Iterator<Item = (usize, usize)>, | |
3157f602 | 364 | { |
c34b1796 AL |
365 | for i in 0..size { |
366 | assert_eq!(iter.size_hint(), (size - i, Some(size - i))); | |
367 | assert_eq!(iter.next().unwrap(), (size - i - 1, size - i - 1)); | |
368 | } | |
369 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
370 | assert_eq!(iter.next(), None); | |
371 | } | |
372 | test(size, map.iter().rev().map(|(&k, &v)| (k, v))); | |
373 | test(size, map.iter_mut().rev().map(|(&k, &mut v)| (k, v))); | |
374 | test(size, map.into_iter().rev()); | |
375 | } | |
376 | ||
fc512014 | 377 | // Specifically tests iter_mut's ability to mutate the value of pairs in-line. |
dfeec247 XL |
378 | fn do_test_iter_mut_mutation<T>(size: usize) |
379 | where | |
380 | T: Copy + Debug + Ord + TryFrom<usize>, | |
29967ef6 | 381 | <T as TryFrom<usize>>::Error: Debug, |
dfeec247 XL |
382 | { |
383 | let zero = T::try_from(0).unwrap(); | |
5e7ed085 | 384 | let mut map = BTreeMap::from_iter((0..size).map(|i| (T::try_from(i).unwrap(), zero))); |
dfeec247 XL |
385 | |
386 | // Forward and backward iteration sees enough pairs (also tested elsewhere) | |
387 | assert_eq!(map.iter_mut().count(), size); | |
388 | assert_eq!(map.iter_mut().rev().count(), size); | |
389 | ||
390 | // Iterate forwards, trying to mutate to unique values | |
391 | for (i, (k, v)) in map.iter_mut().enumerate() { | |
392 | assert_eq!(*k, T::try_from(i).unwrap()); | |
393 | assert_eq!(*v, zero); | |
394 | *v = T::try_from(i + 1).unwrap(); | |
395 | } | |
396 | ||
397 | // Iterate backwards, checking that mutations succeeded and trying to mutate again | |
398 | for (i, (k, v)) in map.iter_mut().rev().enumerate() { | |
399 | assert_eq!(*k, T::try_from(size - i - 1).unwrap()); | |
400 | assert_eq!(*v, T::try_from(size - i).unwrap()); | |
401 | *v = T::try_from(2 * size - i).unwrap(); | |
402 | } | |
403 | ||
404 | // Check that backward mutations succeeded | |
405 | for (i, (k, v)) in map.iter_mut().enumerate() { | |
406 | assert_eq!(*k, T::try_from(i).unwrap()); | |
407 | assert_eq!(*v, T::try_from(size + i + 1).unwrap()); | |
408 | } | |
3dfed10e | 409 | map.check(); |
dfeec247 XL |
410 | } |
411 | ||
412 | #[derive(Clone, Copy, Debug, Eq, PartialEq, PartialOrd, Ord)] | |
413 | #[repr(align(32))] | |
414 | struct Align32(usize); | |
415 | ||
416 | impl TryFrom<usize> for Align32 { | |
417 | type Error = (); | |
418 | ||
419 | fn try_from(s: usize) -> Result<Align32, ()> { | |
420 | Ok(Align32(s)) | |
421 | } | |
422 | } | |
423 | ||
424 | #[test] | |
425 | fn test_iter_mut_mutation() { | |
ba9703b0 | 426 | // Check many alignments and trees with roots at various heights. |
dfeec247 XL |
427 | do_test_iter_mut_mutation::<u8>(0); |
428 | do_test_iter_mut_mutation::<u8>(1); | |
ba9703b0 | 429 | do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_1); |
3dfed10e | 430 | do_test_iter_mut_mutation::<u8>(MIN_INSERTS_HEIGHT_2); |
dfeec247 | 431 | do_test_iter_mut_mutation::<u16>(1); |
ba9703b0 XL |
432 | do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_1); |
433 | do_test_iter_mut_mutation::<u16>(MIN_INSERTS_HEIGHT_2); | |
dfeec247 | 434 | do_test_iter_mut_mutation::<u32>(1); |
ba9703b0 XL |
435 | do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_1); |
436 | do_test_iter_mut_mutation::<u32>(MIN_INSERTS_HEIGHT_2); | |
dfeec247 | 437 | do_test_iter_mut_mutation::<u64>(1); |
ba9703b0 XL |
438 | do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_1); |
439 | do_test_iter_mut_mutation::<u64>(MIN_INSERTS_HEIGHT_2); | |
dfeec247 | 440 | do_test_iter_mut_mutation::<u128>(1); |
ba9703b0 XL |
441 | do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_1); |
442 | do_test_iter_mut_mutation::<u128>(MIN_INSERTS_HEIGHT_2); | |
dfeec247 | 443 | do_test_iter_mut_mutation::<Align32>(1); |
ba9703b0 XL |
444 | do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_1); |
445 | do_test_iter_mut_mutation::<Align32>(MIN_INSERTS_HEIGHT_2); | |
dfeec247 XL |
446 | } |
447 | ||
54a0048b SL |
448 | #[test] |
449 | fn test_values_mut() { | |
5e7ed085 | 450 | let mut a = BTreeMap::from_iter((0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i))); |
3dfed10e XL |
451 | test_all_refs(&mut 13, a.values_mut()); |
452 | a.check(); | |
453 | } | |
454 | ||
455 | #[test] | |
456 | fn test_values_mut_mutation() { | |
54a0048b SL |
457 | let mut a = BTreeMap::new(); |
458 | a.insert(1, String::from("hello")); | |
459 | a.insert(2, String::from("goodbye")); | |
460 | ||
461 | for value in a.values_mut() { | |
462 | value.push_str("!"); | |
463 | } | |
464 | ||
5e7ed085 | 465 | let values = Vec::from_iter(a.values().cloned()); |
3157f602 | 466 | assert_eq!(values, [String::from("hello!"), String::from("goodbye!")]); |
3dfed10e XL |
467 | a.check(); |
468 | } | |
469 | ||
470 | #[test] | |
3dfed10e | 471 | fn test_iter_entering_root_twice() { |
5e7ed085 | 472 | let mut map = BTreeMap::from([(0, 0), (1, 1)]); |
3dfed10e XL |
473 | let mut it = map.iter_mut(); |
474 | let front = it.next().unwrap(); | |
475 | let back = it.next_back().unwrap(); | |
476 | assert_eq!(front, (&0, &mut 0)); | |
477 | assert_eq!(back, (&1, &mut 1)); | |
478 | *front.1 = 24; | |
479 | *back.1 = 42; | |
480 | assert_eq!(front, (&0, &mut 24)); | |
481 | assert_eq!(back, (&1, &mut 42)); | |
fc512014 XL |
482 | assert_eq!(it.next(), None); |
483 | assert_eq!(it.next_back(), None); | |
3dfed10e XL |
484 | map.check(); |
485 | } | |
486 | ||
487 | #[test] | |
3dfed10e | 488 | fn test_iter_descending_to_same_node_twice() { |
5e7ed085 | 489 | let mut map = BTreeMap::from_iter((0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i))); |
3dfed10e XL |
490 | let mut it = map.iter_mut(); |
491 | // Descend into first child. | |
492 | let front = it.next().unwrap(); | |
493 | // Descend into first child again, after running through second child. | |
494 | while it.next_back().is_some() {} | |
495 | // Check immutable access. | |
496 | assert_eq!(front, (&0, &mut 0)); | |
497 | // Perform mutable access. | |
498 | *front.1 = 42; | |
499 | map.check(); | |
54a0048b SL |
500 | } |
501 | ||
c34b1796 AL |
502 | #[test] |
503 | fn test_iter_mixed() { | |
f9f354fc XL |
504 | // Miri is too slow |
505 | let size = if cfg!(miri) { 200 } else { 10000 }; | |
c34b1796 | 506 | |
5e7ed085 | 507 | let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i))); |
c34b1796 AL |
508 | |
509 | fn test<T>(size: usize, mut iter: T) | |
dfeec247 XL |
510 | where |
511 | T: Iterator<Item = (usize, usize)> + DoubleEndedIterator, | |
3157f602 | 512 | { |
c34b1796 AL |
513 | for i in 0..size / 4 { |
514 | assert_eq!(iter.size_hint(), (size - i * 2, Some(size - i * 2))); | |
515 | assert_eq!(iter.next().unwrap(), (i, i)); | |
516 | assert_eq!(iter.next_back().unwrap(), (size - i - 1, size - i - 1)); | |
517 | } | |
518 | for i in size / 4..size * 3 / 4 { | |
519 | assert_eq!(iter.size_hint(), (size * 3 / 4 - i, Some(size * 3 / 4 - i))); | |
520 | assert_eq!(iter.next().unwrap(), (i, i)); | |
521 | } | |
522 | assert_eq!(iter.size_hint(), (0, Some(0))); | |
523 | assert_eq!(iter.next(), None); | |
524 | } | |
525 | test(size, map.iter().map(|(&k, &v)| (k, v))); | |
526 | test(size, map.iter_mut().map(|(&k, &mut v)| (k, v))); | |
527 | test(size, map.into_iter()); | |
528 | } | |
529 | ||
f035d41b | 530 | #[test] |
f035d41b XL |
531 | fn test_iter_min_max() { |
532 | let mut a = BTreeMap::new(); | |
533 | assert_eq!(a.iter().min(), None); | |
534 | assert_eq!(a.iter().max(), None); | |
535 | assert_eq!(a.iter_mut().min(), None); | |
536 | assert_eq!(a.iter_mut().max(), None); | |
537 | assert_eq!(a.range(..).min(), None); | |
538 | assert_eq!(a.range(..).max(), None); | |
539 | assert_eq!(a.range_mut(..).min(), None); | |
540 | assert_eq!(a.range_mut(..).max(), None); | |
541 | assert_eq!(a.keys().min(), None); | |
542 | assert_eq!(a.keys().max(), None); | |
543 | assert_eq!(a.values().min(), None); | |
544 | assert_eq!(a.values().max(), None); | |
545 | assert_eq!(a.values_mut().min(), None); | |
546 | assert_eq!(a.values_mut().max(), None); | |
547 | a.insert(1, 42); | |
548 | a.insert(2, 24); | |
549 | assert_eq!(a.iter().min(), Some((&1, &42))); | |
550 | assert_eq!(a.iter().max(), Some((&2, &24))); | |
551 | assert_eq!(a.iter_mut().min(), Some((&1, &mut 42))); | |
552 | assert_eq!(a.iter_mut().max(), Some((&2, &mut 24))); | |
553 | assert_eq!(a.range(..).min(), Some((&1, &42))); | |
554 | assert_eq!(a.range(..).max(), Some((&2, &24))); | |
555 | assert_eq!(a.range_mut(..).min(), Some((&1, &mut 42))); | |
556 | assert_eq!(a.range_mut(..).max(), Some((&2, &mut 24))); | |
557 | assert_eq!(a.keys().min(), Some(&1)); | |
558 | assert_eq!(a.keys().max(), Some(&2)); | |
559 | assert_eq!(a.values().min(), Some(&24)); | |
560 | assert_eq!(a.values().max(), Some(&42)); | |
561 | assert_eq!(a.values_mut().min(), Some(&mut 24)); | |
562 | assert_eq!(a.values_mut().max(), Some(&mut 42)); | |
3dfed10e | 563 | a.check(); |
f035d41b XL |
564 | } |
565 | ||
dfeec247 | 566 | fn range_keys(map: &BTreeMap<i32, i32>, range: impl RangeBounds<i32>) -> Vec<i32> { |
5e7ed085 FG |
567 | Vec::from_iter(map.range(range).map(|(&k, &v)| { |
568 | assert_eq!(k, v); | |
569 | k | |
570 | })) | |
dfeec247 XL |
571 | } |
572 | ||
c34b1796 AL |
573 | #[test] |
574 | fn test_range_small() { | |
dfeec247 XL |
575 | let size = 4; |
576 | ||
5e7ed085 | 577 | let all = Vec::from_iter(1..=size); |
dfeec247 | 578 | let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]); |
5e7ed085 | 579 | let map = BTreeMap::from_iter(all.iter().copied().map(|i| (i, i))); |
dfeec247 XL |
580 | |
581 | assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all); | |
582 | assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all); | |
583 | assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all); | |
584 | assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all); | |
585 | assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all); | |
586 | assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all); | |
587 | assert_eq!(range_keys(&map, (Included(0), Included(size))), all); | |
588 | assert_eq!(range_keys(&map, (Included(0), Unbounded)), all); | |
589 | assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all); | |
590 | assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all); | |
591 | assert_eq!(range_keys(&map, (Included(1), Included(size))), all); | |
592 | assert_eq!(range_keys(&map, (Included(1), Unbounded)), all); | |
593 | assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all); | |
594 | assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all); | |
595 | assert_eq!(range_keys(&map, (Unbounded, Included(size))), all); | |
596 | assert_eq!(range_keys(&map, ..), all); | |
597 | ||
598 | assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]); | |
599 | assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]); | |
600 | assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]); | |
601 | assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]); | |
602 | assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]); | |
603 | assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]); | |
604 | assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first); | |
605 | assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first); | |
606 | assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first); | |
607 | assert_eq!(range_keys(&map, (Included(0), Included(1))), first); | |
608 | assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first); | |
609 | assert_eq!(range_keys(&map, (Included(1), Included(1))), first); | |
610 | assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first); | |
611 | assert_eq!(range_keys(&map, (Unbounded, Included(1))), first); | |
612 | assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last); | |
613 | assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last); | |
614 | assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last); | |
615 | assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last); | |
616 | assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last); | |
617 | assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last); | |
618 | assert_eq!(range_keys(&map, (Included(size), Included(size))), last); | |
619 | assert_eq!(range_keys(&map, (Included(size), Unbounded)), last); | |
620 | assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]); | |
621 | assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]); | |
622 | assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]); | |
623 | assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]); | |
624 | assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]); | |
625 | assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]); | |
626 | ||
627 | assert_eq!(range_keys(&map, ..3), vec![1, 2]); | |
628 | assert_eq!(range_keys(&map, 3..), vec![3, 4]); | |
629 | assert_eq!(range_keys(&map, 2..=3), vec![2, 3]); | |
630 | } | |
c34b1796 | 631 | |
dfeec247 | 632 | #[test] |
ba9703b0 | 633 | fn test_range_height_1() { |
5e7ed085 FG |
634 | // Tests tree with a root and 2 leaves. We test around the middle of the |
635 | // keys because one of those is the single key in the root node. | |
636 | let map = BTreeMap::from_iter((0..MIN_INSERTS_HEIGHT_1 as i32).map(|i| (i, i))); | |
fc512014 XL |
637 | let middle = MIN_INSERTS_HEIGHT_1 as i32 / 2; |
638 | for root in middle - 2..=middle + 2 { | |
dfeec247 XL |
639 | assert_eq!(range_keys(&map, (Excluded(root), Excluded(root + 1))), vec![]); |
640 | assert_eq!(range_keys(&map, (Excluded(root), Included(root + 1))), vec![root + 1]); | |
641 | assert_eq!(range_keys(&map, (Included(root), Excluded(root + 1))), vec![root]); | |
642 | assert_eq!(range_keys(&map, (Included(root), Included(root + 1))), vec![root, root + 1]); | |
643 | ||
644 | assert_eq!(range_keys(&map, (Excluded(root - 1), Excluded(root))), vec![]); | |
645 | assert_eq!(range_keys(&map, (Included(root - 1), Excluded(root))), vec![root - 1]); | |
646 | assert_eq!(range_keys(&map, (Excluded(root - 1), Included(root))), vec![root]); | |
647 | assert_eq!(range_keys(&map, (Included(root - 1), Included(root))), vec![root - 1, root]); | |
c34b1796 | 648 | } |
c34b1796 AL |
649 | } |
650 | ||
8bb4bdeb | 651 | #[test] |
dfeec247 XL |
652 | fn test_range_large() { |
653 | let size = 200; | |
8bb4bdeb | 654 | |
5e7ed085 | 655 | let all = Vec::from_iter(1..=size); |
dfeec247 | 656 | let (first, last) = (vec![all[0]], vec![all[size as usize - 1]]); |
5e7ed085 | 657 | let map = BTreeMap::from_iter(all.iter().copied().map(|i| (i, i))); |
dfeec247 XL |
658 | |
659 | assert_eq!(range_keys(&map, (Excluded(0), Excluded(size + 1))), all); | |
660 | assert_eq!(range_keys(&map, (Excluded(0), Included(size + 1))), all); | |
661 | assert_eq!(range_keys(&map, (Excluded(0), Included(size))), all); | |
662 | assert_eq!(range_keys(&map, (Excluded(0), Unbounded)), all); | |
663 | assert_eq!(range_keys(&map, (Included(0), Excluded(size + 1))), all); | |
664 | assert_eq!(range_keys(&map, (Included(0), Included(size + 1))), all); | |
665 | assert_eq!(range_keys(&map, (Included(0), Included(size))), all); | |
666 | assert_eq!(range_keys(&map, (Included(0), Unbounded)), all); | |
667 | assert_eq!(range_keys(&map, (Included(1), Excluded(size + 1))), all); | |
668 | assert_eq!(range_keys(&map, (Included(1), Included(size + 1))), all); | |
669 | assert_eq!(range_keys(&map, (Included(1), Included(size))), all); | |
670 | assert_eq!(range_keys(&map, (Included(1), Unbounded)), all); | |
671 | assert_eq!(range_keys(&map, (Unbounded, Excluded(size + 1))), all); | |
672 | assert_eq!(range_keys(&map, (Unbounded, Included(size + 1))), all); | |
673 | assert_eq!(range_keys(&map, (Unbounded, Included(size))), all); | |
674 | assert_eq!(range_keys(&map, ..), all); | |
675 | ||
676 | assert_eq!(range_keys(&map, (Excluded(0), Excluded(1))), vec![]); | |
677 | assert_eq!(range_keys(&map, (Excluded(0), Included(0))), vec![]); | |
678 | assert_eq!(range_keys(&map, (Included(0), Included(0))), vec![]); | |
679 | assert_eq!(range_keys(&map, (Included(0), Excluded(1))), vec![]); | |
680 | assert_eq!(range_keys(&map, (Unbounded, Excluded(1))), vec![]); | |
681 | assert_eq!(range_keys(&map, (Unbounded, Included(0))), vec![]); | |
682 | assert_eq!(range_keys(&map, (Excluded(0), Excluded(2))), first); | |
683 | assert_eq!(range_keys(&map, (Excluded(0), Included(1))), first); | |
684 | assert_eq!(range_keys(&map, (Included(0), Excluded(2))), first); | |
685 | assert_eq!(range_keys(&map, (Included(0), Included(1))), first); | |
686 | assert_eq!(range_keys(&map, (Included(1), Excluded(2))), first); | |
687 | assert_eq!(range_keys(&map, (Included(1), Included(1))), first); | |
688 | assert_eq!(range_keys(&map, (Unbounded, Excluded(2))), first); | |
689 | assert_eq!(range_keys(&map, (Unbounded, Included(1))), first); | |
690 | assert_eq!(range_keys(&map, (Excluded(size - 1), Excluded(size + 1))), last); | |
691 | assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size + 1))), last); | |
692 | assert_eq!(range_keys(&map, (Excluded(size - 1), Included(size))), last); | |
693 | assert_eq!(range_keys(&map, (Excluded(size - 1), Unbounded)), last); | |
694 | assert_eq!(range_keys(&map, (Included(size), Excluded(size + 1))), last); | |
695 | assert_eq!(range_keys(&map, (Included(size), Included(size + 1))), last); | |
696 | assert_eq!(range_keys(&map, (Included(size), Included(size))), last); | |
697 | assert_eq!(range_keys(&map, (Included(size), Unbounded)), last); | |
698 | assert_eq!(range_keys(&map, (Excluded(size), Excluded(size + 1))), vec![]); | |
699 | assert_eq!(range_keys(&map, (Excluded(size), Included(size))), vec![]); | |
700 | assert_eq!(range_keys(&map, (Excluded(size), Unbounded)), vec![]); | |
701 | assert_eq!(range_keys(&map, (Included(size + 1), Excluded(size + 1))), vec![]); | |
702 | assert_eq!(range_keys(&map, (Included(size + 1), Included(size + 1))), vec![]); | |
703 | assert_eq!(range_keys(&map, (Included(size + 1), Unbounded)), vec![]); | |
8bb4bdeb XL |
704 | |
705 | fn check<'a, L, R>(lhs: L, rhs: R) | |
dfeec247 XL |
706 | where |
707 | L: IntoIterator<Item = (&'a i32, &'a i32)>, | |
708 | R: IntoIterator<Item = (&'a i32, &'a i32)>, | |
8bb4bdeb | 709 | { |
5e7ed085 | 710 | assert_eq!(Vec::from_iter(lhs), Vec::from_iter(rhs)); |
8bb4bdeb XL |
711 | } |
712 | ||
dfeec247 | 713 | check(map.range(..=100), map.range(..101)); |
ea8adc8c | 714 | check(map.range(5..=8), vec![(&5, &5), (&6, &6), (&7, &7), (&8, &8)]); |
dfeec247 | 715 | check(map.range(-1..=2), vec![(&1, &1), (&2, &2)]); |
8bb4bdeb XL |
716 | } |
717 | ||
718 | #[test] | |
719 | fn test_range_inclusive_max_value() { | |
ba9703b0 | 720 | let max = usize::MAX; |
5e7ed085 FG |
721 | let map = BTreeMap::from([(max, 0)]); |
722 | assert_eq!(Vec::from_iter(map.range(max..=max)), &[(&max, &0)]); | |
8bb4bdeb XL |
723 | } |
724 | ||
725 | #[test] | |
726 | fn test_range_equal_empty_cases() { | |
5e7ed085 | 727 | let map = BTreeMap::from_iter((0..5).map(|i| (i, i))); |
8bb4bdeb XL |
728 | assert_eq!(map.range((Included(2), Excluded(2))).next(), None); |
729 | assert_eq!(map.range((Excluded(2), Included(2))).next(), None); | |
730 | } | |
731 | ||
732 | #[test] | |
733 | #[should_panic] | |
734 | fn test_range_equal_excluded() { | |
5e7ed085 | 735 | let map = BTreeMap::from_iter((0..5).map(|i| (i, i))); |
3c0e092e | 736 | let _ = map.range((Excluded(2), Excluded(2))); |
8bb4bdeb XL |
737 | } |
738 | ||
739 | #[test] | |
740 | #[should_panic] | |
741 | fn test_range_backwards_1() { | |
5e7ed085 | 742 | let map = BTreeMap::from_iter((0..5).map(|i| (i, i))); |
3c0e092e | 743 | let _ = map.range((Included(3), Included(2))); |
8bb4bdeb XL |
744 | } |
745 | ||
746 | #[test] | |
747 | #[should_panic] | |
748 | fn test_range_backwards_2() { | |
5e7ed085 | 749 | let map = BTreeMap::from_iter((0..5).map(|i| (i, i))); |
3c0e092e | 750 | let _ = map.range((Included(3), Excluded(2))); |
8bb4bdeb XL |
751 | } |
752 | ||
753 | #[test] | |
754 | #[should_panic] | |
755 | fn test_range_backwards_3() { | |
5e7ed085 | 756 | let map = BTreeMap::from_iter((0..5).map(|i| (i, i))); |
3c0e092e | 757 | let _ = map.range((Excluded(3), Included(2))); |
8bb4bdeb XL |
758 | } |
759 | ||
760 | #[test] | |
761 | #[should_panic] | |
762 | fn test_range_backwards_4() { | |
5e7ed085 | 763 | let map = BTreeMap::from_iter((0..5).map(|i| (i, i))); |
3c0e092e | 764 | let _ = map.range((Excluded(3), Excluded(2))); |
8bb4bdeb XL |
765 | } |
766 | ||
fc512014 | 767 | #[test] |
5869c6ff | 768 | fn test_range_finding_ill_order_in_map() { |
fc512014 XL |
769 | let mut map = BTreeMap::new(); |
770 | map.insert(Cyclic3::B, ()); | |
771 | // Lacking static_assert, call `range` conditionally, to emphasise that | |
772 | // we cause a different panic than `test_range_backwards_1` does. | |
773 | // A more refined `should_panic` would be welcome. | |
774 | if Cyclic3::C < Cyclic3::A { | |
3c0e092e | 775 | let _ = map.range(Cyclic3::C..=Cyclic3::A); |
fc512014 XL |
776 | } |
777 | } | |
778 | ||
5869c6ff | 779 | #[test] |
5869c6ff XL |
780 | fn test_range_finding_ill_order_in_range_ord() { |
781 | // Has proper order the first time asked, then flips around. | |
782 | struct EvilTwin(i32); | |
783 | ||
784 | impl PartialOrd for EvilTwin { | |
785 | fn partial_cmp(&self, other: &Self) -> Option<Ordering> { | |
786 | Some(self.cmp(other)) | |
787 | } | |
788 | } | |
789 | ||
790 | static COMPARES: AtomicUsize = AtomicUsize::new(0); | |
791 | impl Ord for EvilTwin { | |
792 | fn cmp(&self, other: &Self) -> Ordering { | |
793 | let ord = self.0.cmp(&other.0); | |
794 | if COMPARES.fetch_add(1, SeqCst) > 0 { ord.reverse() } else { ord } | |
795 | } | |
796 | } | |
797 | ||
798 | impl PartialEq for EvilTwin { | |
799 | fn eq(&self, other: &Self) -> bool { | |
800 | self.0.eq(&other.0) | |
801 | } | |
802 | } | |
803 | ||
804 | impl Eq for EvilTwin {} | |
805 | ||
806 | #[derive(PartialEq, Eq, PartialOrd, Ord)] | |
807 | struct CompositeKey(i32, EvilTwin); | |
808 | ||
809 | impl Borrow<EvilTwin> for CompositeKey { | |
810 | fn borrow(&self) -> &EvilTwin { | |
811 | &self.1 | |
812 | } | |
813 | } | |
814 | ||
5e7ed085 | 815 | let map = BTreeMap::from_iter((0..12).map(|i| (CompositeKey(i, EvilTwin(i)), ()))); |
3c0e092e | 816 | let _ = map.range(EvilTwin(5)..=EvilTwin(7)); |
5869c6ff XL |
817 | } |
818 | ||
c34b1796 AL |
819 | #[test] |
820 | fn test_range_1000() { | |
f9f354fc XL |
821 | // Miri is too slow |
822 | let size = if cfg!(miri) { MIN_INSERTS_HEIGHT_2 as u32 } else { 1000 }; | |
5e7ed085 | 823 | let map = BTreeMap::from_iter((0..size).map(|i| (i, i))); |
c34b1796 AL |
824 | |
825 | fn test(map: &BTreeMap<u32, u32>, size: u32, min: Bound<&u32>, max: Bound<&u32>) { | |
32a655c1 | 826 | let mut kvs = map.range((min, max)).map(|(&k, &v)| (k, v)); |
c34b1796 AL |
827 | let mut pairs = (0..size).map(|i| (i, i)); |
828 | ||
829 | for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { | |
830 | assert_eq!(kv, pair); | |
831 | } | |
832 | assert_eq!(kvs.next(), None); | |
833 | assert_eq!(pairs.next(), None); | |
834 | } | |
835 | test(&map, size, Included(&0), Excluded(&size)); | |
836 | test(&map, size, Unbounded, Excluded(&size)); | |
837 | test(&map, size, Included(&0), Included(&(size - 1))); | |
838 | test(&map, size, Unbounded, Included(&(size - 1))); | |
839 | test(&map, size, Included(&0), Unbounded); | |
840 | test(&map, size, Unbounded, Unbounded); | |
841 | } | |
842 | ||
32a655c1 SL |
843 | #[test] |
844 | fn test_range_borrowed_key() { | |
845 | let mut map = BTreeMap::new(); | |
846 | map.insert("aardvark".to_string(), 1); | |
847 | map.insert("baboon".to_string(), 2); | |
848 | map.insert("coyote".to_string(), 3); | |
849 | map.insert("dingo".to_string(), 4); | |
850 | // NOTE: would like to use simply "b".."d" here... | |
dfeec247 | 851 | let mut iter = map.range::<str, _>((Included("b"), Excluded("d"))); |
32a655c1 SL |
852 | assert_eq!(iter.next(), Some((&"baboon".to_string(), &2))); |
853 | assert_eq!(iter.next(), Some((&"coyote".to_string(), &3))); | |
854 | assert_eq!(iter.next(), None); | |
855 | } | |
856 | ||
c34b1796 AL |
857 | #[test] |
858 | fn test_range() { | |
859 | let size = 200; | |
f9f354fc XL |
860 | // Miri is too slow |
861 | let step = if cfg!(miri) { 66 } else { 1 }; | |
5e7ed085 | 862 | let map = BTreeMap::from_iter((0..size).map(|i| (i, i))); |
c34b1796 | 863 | |
74b04a01 XL |
864 | for i in (0..size).step_by(step) { |
865 | for j in (i..size).step_by(step) { | |
32a655c1 | 866 | let mut kvs = map.range((Included(&i), Included(&j))).map(|(&k, &v)| (k, v)); |
0731742a | 867 | let mut pairs = (i..=j).map(|i| (i, i)); |
32a655c1 SL |
868 | |
869 | for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { | |
870 | assert_eq!(kv, pair); | |
871 | } | |
872 | assert_eq!(kvs.next(), None); | |
873 | assert_eq!(pairs.next(), None); | |
874 | } | |
875 | } | |
876 | } | |
877 | ||
878 | #[test] | |
879 | fn test_range_mut() { | |
880 | let size = 200; | |
f9f354fc XL |
881 | // Miri is too slow |
882 | let step = if cfg!(miri) { 66 } else { 1 }; | |
5e7ed085 | 883 | let mut map = BTreeMap::from_iter((0..size).map(|i| (i, i))); |
32a655c1 | 884 | |
74b04a01 XL |
885 | for i in (0..size).step_by(step) { |
886 | for j in (i..size).step_by(step) { | |
32a655c1 | 887 | let mut kvs = map.range_mut((Included(&i), Included(&j))).map(|(&k, &mut v)| (k, v)); |
0731742a | 888 | let mut pairs = (i..=j).map(|i| (i, i)); |
c34b1796 AL |
889 | |
890 | for (kv, pair) in kvs.by_ref().zip(pairs.by_ref()) { | |
891 | assert_eq!(kv, pair); | |
892 | } | |
893 | assert_eq!(kvs.next(), None); | |
894 | assert_eq!(pairs.next(), None); | |
895 | } | |
896 | } | |
3dfed10e | 897 | map.check(); |
c34b1796 AL |
898 | } |
899 | ||
923072b8 FG |
900 | #[should_panic(expected = "range start is greater than range end in BTreeMap")] |
901 | #[test] | |
902 | fn test_range_panic_1() { | |
903 | let mut map = BTreeMap::new(); | |
904 | map.insert(3, "a"); | |
905 | map.insert(5, "b"); | |
906 | map.insert(8, "c"); | |
907 | ||
908 | let _invalid_range = map.range((Included(&8), Included(&3))); | |
909 | } | |
910 | ||
911 | #[should_panic(expected = "range start and end are equal and excluded in BTreeMap")] | |
912 | #[test] | |
913 | fn test_range_panic_2() { | |
914 | let mut map = BTreeMap::new(); | |
915 | map.insert(3, "a"); | |
916 | map.insert(5, "b"); | |
917 | map.insert(8, "c"); | |
918 | ||
919 | let _invalid_range = map.range((Excluded(&5), Excluded(&5))); | |
920 | } | |
921 | ||
922 | #[should_panic(expected = "range start and end are equal and excluded in BTreeMap")] | |
923 | #[test] | |
924 | fn test_range_panic_3() { | |
925 | let mut map: BTreeMap<i32, ()> = BTreeMap::new(); | |
926 | map.insert(3, ()); | |
927 | map.insert(5, ()); | |
928 | map.insert(8, ()); | |
929 | ||
930 | let _invalid_range = map.range((Excluded(&5), Excluded(&5))); | |
931 | } | |
932 | ||
fc512014 XL |
933 | #[test] |
934 | fn test_retain() { | |
5e7ed085 | 935 | let mut map = BTreeMap::from_iter((0..100).map(|x| (x, x * 10))); |
fc512014 XL |
936 | |
937 | map.retain(|&k, _| k % 2 == 0); | |
938 | assert_eq!(map.len(), 50); | |
939 | assert_eq!(map[&2], 20); | |
940 | assert_eq!(map[&4], 40); | |
941 | assert_eq!(map[&6], 60); | |
942 | } | |
943 | ||
ba9703b0 XL |
944 | mod test_drain_filter { |
945 | use super::*; | |
946 | ||
947 | #[test] | |
948 | fn empty() { | |
949 | let mut map: BTreeMap<i32, i32> = BTreeMap::new(); | |
950 | map.drain_filter(|_, _| unreachable!("there's nothing to decide on")); | |
5e7ed085 | 951 | assert_eq!(map.height(), None); |
3dfed10e | 952 | map.check(); |
ba9703b0 XL |
953 | } |
954 | ||
fc512014 | 955 | // Explicitly consumes the iterator, where most test cases drop it instantly. |
ba9703b0 | 956 | #[test] |
fc512014 | 957 | fn consumed_keeping_all() { |
ba9703b0 | 958 | let pairs = (0..3).map(|i| (i, i)); |
5e7ed085 | 959 | let mut map = BTreeMap::from_iter(pairs); |
29967ef6 | 960 | assert!(map.drain_filter(|_, _| false).eq(iter::empty())); |
3dfed10e | 961 | map.check(); |
ba9703b0 XL |
962 | } |
963 | ||
fc512014 | 964 | // Explicitly consumes the iterator, where most test cases drop it instantly. |
ba9703b0 | 965 | #[test] |
fc512014 | 966 | fn consumed_removing_all() { |
ba9703b0 | 967 | let pairs = (0..3).map(|i| (i, i)); |
5e7ed085 | 968 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 | 969 | assert!(map.drain_filter(|_, _| true).eq(pairs)); |
fc512014 | 970 | assert!(map.is_empty()); |
3dfed10e | 971 | map.check(); |
ba9703b0 XL |
972 | } |
973 | ||
fc512014 | 974 | // Explicitly consumes the iterator and modifies values through it. |
ba9703b0 XL |
975 | #[test] |
976 | fn mutating_and_keeping() { | |
977 | let pairs = (0..3).map(|i| (i, i)); | |
5e7ed085 | 978 | let mut map = BTreeMap::from_iter(pairs); |
ba9703b0 XL |
979 | assert!( |
980 | map.drain_filter(|_, v| { | |
981 | *v += 6; | |
982 | false | |
983 | }) | |
29967ef6 | 984 | .eq(iter::empty()) |
ba9703b0 XL |
985 | ); |
986 | assert!(map.keys().copied().eq(0..3)); | |
987 | assert!(map.values().copied().eq(6..9)); | |
3dfed10e | 988 | map.check(); |
ba9703b0 XL |
989 | } |
990 | ||
fc512014 | 991 | // Explicitly consumes the iterator and modifies values through it. |
ba9703b0 XL |
992 | #[test] |
993 | fn mutating_and_removing() { | |
994 | let pairs = (0..3).map(|i| (i, i)); | |
5e7ed085 | 995 | let mut map = BTreeMap::from_iter(pairs); |
ba9703b0 XL |
996 | assert!( |
997 | map.drain_filter(|_, v| { | |
998 | *v += 6; | |
999 | true | |
1000 | }) | |
1001 | .eq((0..3).map(|i| (i, i + 6))) | |
1002 | ); | |
1003 | assert!(map.is_empty()); | |
3dfed10e | 1004 | map.check(); |
ba9703b0 XL |
1005 | } |
1006 | ||
1007 | #[test] | |
1008 | fn underfull_keeping_all() { | |
1009 | let pairs = (0..3).map(|i| (i, i)); | |
5e7ed085 | 1010 | let mut map = BTreeMap::from_iter(pairs); |
ba9703b0 XL |
1011 | map.drain_filter(|_, _| false); |
1012 | assert!(map.keys().copied().eq(0..3)); | |
3dfed10e | 1013 | map.check(); |
ba9703b0 XL |
1014 | } |
1015 | ||
1016 | #[test] | |
1017 | fn underfull_removing_one() { | |
1018 | let pairs = (0..3).map(|i| (i, i)); | |
1019 | for doomed in 0..3 { | |
5e7ed085 | 1020 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 XL |
1021 | map.drain_filter(|i, _| *i == doomed); |
1022 | assert_eq!(map.len(), 2); | |
3dfed10e | 1023 | map.check(); |
ba9703b0 XL |
1024 | } |
1025 | } | |
1026 | ||
1027 | #[test] | |
1028 | fn underfull_keeping_one() { | |
1029 | let pairs = (0..3).map(|i| (i, i)); | |
1030 | for sacred in 0..3 { | |
5e7ed085 | 1031 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 XL |
1032 | map.drain_filter(|i, _| *i != sacred); |
1033 | assert!(map.keys().copied().eq(sacred..=sacred)); | |
3dfed10e | 1034 | map.check(); |
ba9703b0 XL |
1035 | } |
1036 | } | |
1037 | ||
1038 | #[test] | |
1039 | fn underfull_removing_all() { | |
1040 | let pairs = (0..3).map(|i| (i, i)); | |
5e7ed085 | 1041 | let mut map = BTreeMap::from_iter(pairs); |
ba9703b0 XL |
1042 | map.drain_filter(|_, _| true); |
1043 | assert!(map.is_empty()); | |
3dfed10e | 1044 | map.check(); |
ba9703b0 XL |
1045 | } |
1046 | ||
1047 | #[test] | |
1048 | fn height_0_keeping_all() { | |
5e7ed085 FG |
1049 | let pairs = (0..node::CAPACITY).map(|i| (i, i)); |
1050 | let mut map = BTreeMap::from_iter(pairs); | |
ba9703b0 | 1051 | map.drain_filter(|_, _| false); |
5e7ed085 | 1052 | assert!(map.keys().copied().eq(0..node::CAPACITY)); |
3dfed10e | 1053 | map.check(); |
ba9703b0 XL |
1054 | } |
1055 | ||
1056 | #[test] | |
1057 | fn height_0_removing_one() { | |
5e7ed085 FG |
1058 | let pairs = (0..node::CAPACITY).map(|i| (i, i)); |
1059 | for doomed in 0..node::CAPACITY { | |
1060 | let mut map = BTreeMap::from_iter(pairs.clone()); | |
ba9703b0 | 1061 | map.drain_filter(|i, _| *i == doomed); |
5e7ed085 | 1062 | assert_eq!(map.len(), node::CAPACITY - 1); |
3dfed10e | 1063 | map.check(); |
ba9703b0 XL |
1064 | } |
1065 | } | |
1066 | ||
1067 | #[test] | |
1068 | fn height_0_keeping_one() { | |
5e7ed085 FG |
1069 | let pairs = (0..node::CAPACITY).map(|i| (i, i)); |
1070 | for sacred in 0..node::CAPACITY { | |
1071 | let mut map = BTreeMap::from_iter(pairs.clone()); | |
ba9703b0 XL |
1072 | map.drain_filter(|i, _| *i != sacred); |
1073 | assert!(map.keys().copied().eq(sacred..=sacred)); | |
3dfed10e | 1074 | map.check(); |
ba9703b0 XL |
1075 | } |
1076 | } | |
1077 | ||
1078 | #[test] | |
1079 | fn height_0_removing_all() { | |
5e7ed085 FG |
1080 | let pairs = (0..node::CAPACITY).map(|i| (i, i)); |
1081 | let mut map = BTreeMap::from_iter(pairs); | |
ba9703b0 XL |
1082 | map.drain_filter(|_, _| true); |
1083 | assert!(map.is_empty()); | |
3dfed10e | 1084 | map.check(); |
ba9703b0 XL |
1085 | } |
1086 | ||
1087 | #[test] | |
1088 | fn height_0_keeping_half() { | |
5e7ed085 | 1089 | let mut map = BTreeMap::from_iter((0..16).map(|i| (i, i))); |
ba9703b0 XL |
1090 | assert_eq!(map.drain_filter(|i, _| *i % 2 == 0).count(), 8); |
1091 | assert_eq!(map.len(), 8); | |
3dfed10e | 1092 | map.check(); |
ba9703b0 XL |
1093 | } |
1094 | ||
1095 | #[test] | |
1096 | fn height_1_removing_all() { | |
1097 | let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); | |
5e7ed085 | 1098 | let mut map = BTreeMap::from_iter(pairs); |
ba9703b0 XL |
1099 | map.drain_filter(|_, _| true); |
1100 | assert!(map.is_empty()); | |
3dfed10e | 1101 | map.check(); |
ba9703b0 XL |
1102 | } |
1103 | ||
1104 | #[test] | |
1105 | fn height_1_removing_one() { | |
1106 | let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); | |
1107 | for doomed in 0..MIN_INSERTS_HEIGHT_1 { | |
5e7ed085 | 1108 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 XL |
1109 | map.drain_filter(|i, _| *i == doomed); |
1110 | assert_eq!(map.len(), MIN_INSERTS_HEIGHT_1 - 1); | |
3dfed10e | 1111 | map.check(); |
ba9703b0 XL |
1112 | } |
1113 | } | |
1114 | ||
1115 | #[test] | |
1116 | fn height_1_keeping_one() { | |
1117 | let pairs = (0..MIN_INSERTS_HEIGHT_1).map(|i| (i, i)); | |
1118 | for sacred in 0..MIN_INSERTS_HEIGHT_1 { | |
5e7ed085 | 1119 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 XL |
1120 | map.drain_filter(|i, _| *i != sacred); |
1121 | assert!(map.keys().copied().eq(sacred..=sacred)); | |
3dfed10e | 1122 | map.check(); |
ba9703b0 XL |
1123 | } |
1124 | } | |
1125 | ||
ba9703b0 XL |
1126 | #[test] |
1127 | fn height_2_removing_one() { | |
1128 | let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); | |
1129 | for doomed in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { | |
5e7ed085 | 1130 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 XL |
1131 | map.drain_filter(|i, _| *i == doomed); |
1132 | assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); | |
3dfed10e | 1133 | map.check(); |
ba9703b0 XL |
1134 | } |
1135 | } | |
1136 | ||
ba9703b0 XL |
1137 | #[test] |
1138 | fn height_2_keeping_one() { | |
1139 | let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); | |
1140 | for sacred in (0..MIN_INSERTS_HEIGHT_2).step_by(12) { | |
5e7ed085 | 1141 | let mut map = BTreeMap::from_iter(pairs.clone()); |
ba9703b0 XL |
1142 | map.drain_filter(|i, _| *i != sacred); |
1143 | assert!(map.keys().copied().eq(sacred..=sacred)); | |
3dfed10e | 1144 | map.check(); |
ba9703b0 XL |
1145 | } |
1146 | } | |
1147 | ||
1148 | #[test] | |
1149 | fn height_2_removing_all() { | |
1150 | let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); | |
5e7ed085 | 1151 | let mut map = BTreeMap::from_iter(pairs); |
ba9703b0 XL |
1152 | map.drain_filter(|_, _| true); |
1153 | assert!(map.is_empty()); | |
3dfed10e | 1154 | map.check(); |
ba9703b0 XL |
1155 | } |
1156 | ||
1157 | #[test] | |
1158 | fn drop_panic_leak() { | |
6a06907d XL |
1159 | let a = CrashTestDummy::new(0); |
1160 | let b = CrashTestDummy::new(1); | |
1161 | let c = CrashTestDummy::new(2); | |
1162 | let mut map = BTreeMap::new(); | |
1163 | map.insert(a.spawn(Panic::Never), ()); | |
1164 | map.insert(b.spawn(Panic::InDrop), ()); | |
1165 | map.insert(c.spawn(Panic::Never), ()); | |
ba9703b0 | 1166 | |
6a06907d | 1167 | catch_unwind(move || drop(map.drain_filter(|dummy, _| dummy.query(true)))).unwrap_err(); |
ba9703b0 | 1168 | |
6a06907d XL |
1169 | assert_eq!(a.queried(), 1); |
1170 | assert_eq!(b.queried(), 1); | |
1171 | assert_eq!(c.queried(), 0); | |
1172 | assert_eq!(a.dropped(), 1); | |
1173 | assert_eq!(b.dropped(), 1); | |
1174 | assert_eq!(c.dropped(), 1); | |
ba9703b0 XL |
1175 | } |
1176 | ||
1177 | #[test] | |
1178 | fn pred_panic_leak() { | |
6a06907d XL |
1179 | let a = CrashTestDummy::new(0); |
1180 | let b = CrashTestDummy::new(1); | |
1181 | let c = CrashTestDummy::new(2); | |
1182 | let mut map = BTreeMap::new(); | |
1183 | map.insert(a.spawn(Panic::Never), ()); | |
1184 | map.insert(b.spawn(Panic::InQuery), ()); | |
1185 | map.insert(c.spawn(Panic::InQuery), ()); | |
1186 | ||
1187 | catch_unwind(AssertUnwindSafe(|| drop(map.drain_filter(|dummy, _| dummy.query(true))))) | |
1188 | .unwrap_err(); | |
1189 | ||
1190 | assert_eq!(a.queried(), 1); | |
1191 | assert_eq!(b.queried(), 1); | |
1192 | assert_eq!(c.queried(), 0); | |
1193 | assert_eq!(a.dropped(), 1); | |
1194 | assert_eq!(b.dropped(), 0); | |
1195 | assert_eq!(c.dropped(), 0); | |
ba9703b0 | 1196 | assert_eq!(map.len(), 2); |
6a06907d XL |
1197 | assert_eq!(map.first_entry().unwrap().key().id(), 1); |
1198 | assert_eq!(map.last_entry().unwrap().key().id(), 2); | |
3dfed10e XL |
1199 | map.check(); |
1200 | } | |
1201 | ||
1202 | // Same as above, but attempt to use the iterator again after the panic in the predicate | |
1203 | #[test] | |
1204 | fn pred_panic_reuse() { | |
6a06907d XL |
1205 | let a = CrashTestDummy::new(0); |
1206 | let b = CrashTestDummy::new(1); | |
1207 | let c = CrashTestDummy::new(2); | |
1208 | let mut map = BTreeMap::new(); | |
1209 | map.insert(a.spawn(Panic::Never), ()); | |
1210 | map.insert(b.spawn(Panic::InQuery), ()); | |
1211 | map.insert(c.spawn(Panic::InQuery), ()); | |
3dfed10e XL |
1212 | |
1213 | { | |
6a06907d | 1214 | let mut it = map.drain_filter(|dummy, _| dummy.query(true)); |
3dfed10e XL |
1215 | catch_unwind(AssertUnwindSafe(|| while it.next().is_some() {})).unwrap_err(); |
1216 | // Iterator behaviour after a panic is explicitly unspecified, | |
1217 | // so this is just the current implementation: | |
1218 | let result = catch_unwind(AssertUnwindSafe(|| it.next())); | |
1219 | assert!(matches!(result, Ok(None))); | |
1220 | } | |
1221 | ||
6a06907d XL |
1222 | assert_eq!(a.queried(), 1); |
1223 | assert_eq!(b.queried(), 1); | |
1224 | assert_eq!(c.queried(), 0); | |
1225 | assert_eq!(a.dropped(), 1); | |
1226 | assert_eq!(b.dropped(), 0); | |
1227 | assert_eq!(c.dropped(), 0); | |
3dfed10e | 1228 | assert_eq!(map.len(), 2); |
6a06907d XL |
1229 | assert_eq!(map.first_entry().unwrap().key().id(), 1); |
1230 | assert_eq!(map.last_entry().unwrap().key().id(), 2); | |
3dfed10e | 1231 | map.check(); |
ba9703b0 XL |
1232 | } |
1233 | } | |
1234 | ||
d9579d0f AL |
1235 | #[test] |
1236 | fn test_borrow() { | |
1237 | // make sure these compile -- using the Borrow trait | |
1238 | { | |
1239 | let mut map = BTreeMap::new(); | |
1240 | map.insert("0".to_string(), 1); | |
1241 | assert_eq!(map["0"], 1); | |
1242 | } | |
1243 | ||
1244 | { | |
1245 | let mut map = BTreeMap::new(); | |
1246 | map.insert(Box::new(0), 1); | |
1247 | assert_eq!(map[&0], 1); | |
1248 | } | |
1249 | ||
1250 | { | |
1251 | let mut map = BTreeMap::new(); | |
1252 | map.insert(Box::new([0, 1]) as Box<[i32]>, 1); | |
1253 | assert_eq!(map[&[0, 1][..]], 1); | |
1254 | } | |
1255 | ||
1256 | { | |
1257 | let mut map = BTreeMap::new(); | |
1258 | map.insert(Rc::new(0), 1); | |
1259 | assert_eq!(map[&0], 1); | |
1260 | } | |
5869c6ff XL |
1261 | |
1262 | #[allow(dead_code)] | |
1263 | fn get<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) { | |
3c0e092e | 1264 | let _ = v.get(t); |
5869c6ff XL |
1265 | } |
1266 | ||
1267 | #[allow(dead_code)] | |
1268 | fn get_mut<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) { | |
3c0e092e | 1269 | let _ = v.get_mut(t); |
5869c6ff XL |
1270 | } |
1271 | ||
1272 | #[allow(dead_code)] | |
1273 | fn get_key_value<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) { | |
3c0e092e | 1274 | let _ = v.get_key_value(t); |
5869c6ff XL |
1275 | } |
1276 | ||
1277 | #[allow(dead_code)] | |
1278 | fn contains_key<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: &T) { | |
3c0e092e | 1279 | let _ = v.contains_key(t); |
5869c6ff XL |
1280 | } |
1281 | ||
1282 | #[allow(dead_code)] | |
1283 | fn range<T: Ord>(v: &BTreeMap<Box<T>, ()>, t: T) { | |
3c0e092e | 1284 | let _ = v.range(t..); |
5869c6ff XL |
1285 | } |
1286 | ||
1287 | #[allow(dead_code)] | |
1288 | fn range_mut<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: T) { | |
3c0e092e | 1289 | let _ = v.range_mut(t..); |
5869c6ff XL |
1290 | } |
1291 | ||
1292 | #[allow(dead_code)] | |
1293 | fn remove<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) { | |
1294 | v.remove(t); | |
1295 | } | |
1296 | ||
1297 | #[allow(dead_code)] | |
1298 | fn remove_entry<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) { | |
1299 | v.remove_entry(t); | |
1300 | } | |
1301 | ||
1302 | #[allow(dead_code)] | |
1303 | fn split_off<T: Ord>(v: &mut BTreeMap<Box<T>, ()>, t: &T) { | |
1304 | v.split_off(t); | |
1305 | } | |
d9579d0f AL |
1306 | } |
1307 | ||
c34b1796 | 1308 | #[test] |
3157f602 | 1309 | fn test_entry() { |
c34b1796 AL |
1310 | let xs = [(1, 10), (2, 20), (3, 30), (4, 40), (5, 50), (6, 60)]; |
1311 | ||
5e7ed085 | 1312 | let mut map = BTreeMap::from(xs); |
c34b1796 AL |
1313 | |
1314 | // Existing key (insert) | |
1315 | match map.entry(1) { | |
1316 | Vacant(_) => unreachable!(), | |
1317 | Occupied(mut view) => { | |
1318 | assert_eq!(view.get(), &10); | |
1319 | assert_eq!(view.insert(100), 10); | |
1320 | } | |
1321 | } | |
1322 | assert_eq!(map.get(&1).unwrap(), &100); | |
1323 | assert_eq!(map.len(), 6); | |
1324 | ||
c34b1796 AL |
1325 | // Existing key (update) |
1326 | match map.entry(2) { | |
1327 | Vacant(_) => unreachable!(), | |
1328 | Occupied(mut view) => { | |
1329 | let v = view.get_mut(); | |
1330 | *v *= 10; | |
1331 | } | |
1332 | } | |
1333 | assert_eq!(map.get(&2).unwrap(), &200); | |
1334 | assert_eq!(map.len(), 6); | |
3dfed10e | 1335 | map.check(); |
c34b1796 AL |
1336 | |
1337 | // Existing key (take) | |
1338 | match map.entry(3) { | |
1339 | Vacant(_) => unreachable!(), | |
1340 | Occupied(view) => { | |
1341 | assert_eq!(view.remove(), 30); | |
1342 | } | |
1343 | } | |
1344 | assert_eq!(map.get(&3), None); | |
1345 | assert_eq!(map.len(), 5); | |
3dfed10e | 1346 | map.check(); |
c34b1796 | 1347 | |
c34b1796 AL |
1348 | // Inexistent key (insert) |
1349 | match map.entry(10) { | |
1350 | Occupied(_) => unreachable!(), | |
1351 | Vacant(view) => { | |
1352 | assert_eq!(*view.insert(1000), 1000); | |
1353 | } | |
1354 | } | |
1355 | assert_eq!(map.get(&10).unwrap(), &1000); | |
1356 | assert_eq!(map.len(), 6); | |
3dfed10e | 1357 | map.check(); |
c34b1796 AL |
1358 | } |
1359 | ||
62682a34 SL |
1360 | #[test] |
1361 | fn test_extend_ref() { | |
1362 | let mut a = BTreeMap::new(); | |
1363 | a.insert(1, "one"); | |
1364 | let mut b = BTreeMap::new(); | |
1365 | b.insert(2, "two"); | |
1366 | b.insert(3, "three"); | |
1367 | ||
1368 | a.extend(&b); | |
1369 | ||
1370 | assert_eq!(a.len(), 3); | |
1371 | assert_eq!(a[&1], "one"); | |
1372 | assert_eq!(a[&2], "two"); | |
1373 | assert_eq!(a[&3], "three"); | |
3dfed10e | 1374 | a.check(); |
62682a34 SL |
1375 | } |
1376 | ||
b039eaaf SL |
1377 | #[test] |
1378 | fn test_zst() { | |
1379 | let mut m = BTreeMap::new(); | |
1380 | assert_eq!(m.len(), 0); | |
1381 | ||
1382 | assert_eq!(m.insert((), ()), None); | |
1383 | assert_eq!(m.len(), 1); | |
1384 | ||
1385 | assert_eq!(m.insert((), ()), Some(())); | |
1386 | assert_eq!(m.len(), 1); | |
1387 | assert_eq!(m.iter().count(), 1); | |
1388 | ||
1389 | m.clear(); | |
1390 | assert_eq!(m.len(), 0); | |
1391 | ||
1392 | for _ in 0..100 { | |
1393 | m.insert((), ()); | |
1394 | } | |
1395 | ||
1396 | assert_eq!(m.len(), 1); | |
1397 | assert_eq!(m.iter().count(), 1); | |
3dfed10e | 1398 | m.check(); |
b039eaaf SL |
1399 | } |
1400 | ||
1401 | // This test's only purpose is to ensure that zero-sized keys with nonsensical orderings | |
1402 | // do not cause segfaults when used with zero-sized values. All other map behavior is | |
1403 | // undefined. | |
1404 | #[test] | |
1405 | fn test_bad_zst() { | |
3dfed10e | 1406 | #[derive(Clone, Copy, Debug)] |
b039eaaf SL |
1407 | struct Bad; |
1408 | ||
1409 | impl PartialEq for Bad { | |
3157f602 XL |
1410 | fn eq(&self, _: &Self) -> bool { |
1411 | false | |
1412 | } | |
b039eaaf SL |
1413 | } |
1414 | ||
1415 | impl Eq for Bad {} | |
1416 | ||
1417 | impl PartialOrd for Bad { | |
3157f602 XL |
1418 | fn partial_cmp(&self, _: &Self) -> Option<Ordering> { |
1419 | Some(Ordering::Less) | |
1420 | } | |
b039eaaf SL |
1421 | } |
1422 | ||
1423 | impl Ord for Bad { | |
3157f602 XL |
1424 | fn cmp(&self, _: &Self) -> Ordering { |
1425 | Ordering::Less | |
1426 | } | |
b039eaaf SL |
1427 | } |
1428 | ||
1429 | let mut m = BTreeMap::new(); | |
1430 | ||
1431 | for _ in 0..100 { | |
1432 | m.insert(Bad, Bad); | |
1433 | } | |
3dfed10e | 1434 | m.check(); |
b039eaaf SL |
1435 | } |
1436 | ||
6a06907d XL |
1437 | #[test] |
1438 | fn test_clear() { | |
1439 | let mut map = BTreeMap::new(); | |
5e7ed085 | 1440 | for &len in &[MIN_INSERTS_HEIGHT_1, MIN_INSERTS_HEIGHT_2, 0, node::CAPACITY] { |
6a06907d XL |
1441 | for i in 0..len { |
1442 | map.insert(i, ()); | |
1443 | } | |
1444 | assert_eq!(map.len(), len); | |
1445 | map.clear(); | |
1446 | map.check(); | |
5e7ed085 | 1447 | assert_eq!(map.height(), None); |
6a06907d XL |
1448 | } |
1449 | } | |
1450 | ||
1451 | #[test] | |
1452 | fn test_clear_drop_panic_leak() { | |
1453 | let a = CrashTestDummy::new(0); | |
1454 | let b = CrashTestDummy::new(1); | |
1455 | let c = CrashTestDummy::new(2); | |
1456 | ||
1457 | let mut map = BTreeMap::new(); | |
1458 | map.insert(a.spawn(Panic::Never), ()); | |
1459 | map.insert(b.spawn(Panic::InDrop), ()); | |
1460 | map.insert(c.spawn(Panic::Never), ()); | |
1461 | ||
1462 | catch_unwind(AssertUnwindSafe(|| map.clear())).unwrap_err(); | |
1463 | assert_eq!(a.dropped(), 1); | |
1464 | assert_eq!(b.dropped(), 1); | |
1465 | assert_eq!(c.dropped(), 1); | |
1466 | assert_eq!(map.len(), 0); | |
1467 | ||
1468 | drop(map); | |
1469 | assert_eq!(a.dropped(), 1); | |
1470 | assert_eq!(b.dropped(), 1); | |
1471 | assert_eq!(c.dropped(), 1); | |
1472 | } | |
1473 | ||
9cc50fc6 SL |
1474 | #[test] |
1475 | fn test_clone() { | |
1476 | let mut map = BTreeMap::new(); | |
ba9703b0 | 1477 | let size = MIN_INSERTS_HEIGHT_1; |
9cc50fc6 SL |
1478 | assert_eq!(map.len(), 0); |
1479 | ||
1480 | for i in 0..size { | |
3157f602 | 1481 | assert_eq!(map.insert(i, 10 * i), None); |
9cc50fc6 | 1482 | assert_eq!(map.len(), i + 1); |
3dfed10e | 1483 | map.check(); |
9cc50fc6 SL |
1484 | assert_eq!(map, map.clone()); |
1485 | } | |
1486 | ||
1487 | for i in 0..size { | |
3157f602 | 1488 | assert_eq!(map.insert(i, 100 * i), Some(10 * i)); |
9cc50fc6 | 1489 | assert_eq!(map.len(), size); |
3dfed10e | 1490 | map.check(); |
9cc50fc6 SL |
1491 | assert_eq!(map, map.clone()); |
1492 | } | |
1493 | ||
3157f602 XL |
1494 | for i in 0..size / 2 { |
1495 | assert_eq!(map.remove(&(i * 2)), Some(i * 200)); | |
9cc50fc6 | 1496 | assert_eq!(map.len(), size - i - 1); |
3dfed10e | 1497 | map.check(); |
9cc50fc6 SL |
1498 | assert_eq!(map, map.clone()); |
1499 | } | |
1500 | ||
3157f602 XL |
1501 | for i in 0..size / 2 { |
1502 | assert_eq!(map.remove(&(2 * i)), None); | |
1503 | assert_eq!(map.remove(&(2 * i + 1)), Some(i * 200 + 100)); | |
1504 | assert_eq!(map.len(), size / 2 - i - 1); | |
3dfed10e | 1505 | map.check(); |
9cc50fc6 SL |
1506 | assert_eq!(map, map.clone()); |
1507 | } | |
74b04a01 | 1508 | |
3dfed10e | 1509 | // Test a tree with 2 semi-full levels and a tree with 3 levels. |
5e7ed085 | 1510 | map = BTreeMap::from_iter((1..MIN_INSERTS_HEIGHT_2).map(|i| (i, i))); |
ba9703b0 XL |
1511 | assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2 - 1); |
1512 | assert_eq!(map, map.clone()); | |
1513 | map.insert(0, 0); | |
1514 | assert_eq!(map.len(), MIN_INSERTS_HEIGHT_2); | |
1515 | assert_eq!(map, map.clone()); | |
3dfed10e | 1516 | map.check(); |
74b04a01 XL |
1517 | } |
1518 | ||
c295e0f8 XL |
1519 | fn test_clone_panic_leak(size: usize) { |
1520 | for i in 0..size { | |
5e7ed085 FG |
1521 | let dummies = Vec::from_iter((0..size).map(|id| CrashTestDummy::new(id))); |
1522 | let map = BTreeMap::from_iter(dummies.iter().map(|dummy| { | |
1523 | let panic = if dummy.id == i { Panic::InClone } else { Panic::Never }; | |
1524 | (dummy.spawn(panic), ()) | |
1525 | })); | |
6a06907d | 1526 | |
c295e0f8 XL |
1527 | catch_unwind(|| map.clone()).unwrap_err(); |
1528 | for d in &dummies { | |
1529 | assert_eq!(d.cloned(), if d.id <= i { 1 } else { 0 }, "id={}/{}", d.id, i); | |
1530 | assert_eq!(d.dropped(), if d.id < i { 1 } else { 0 }, "id={}/{}", d.id, i); | |
1531 | } | |
1532 | assert_eq!(map.len(), size); | |
6a06907d | 1533 | |
c295e0f8 XL |
1534 | drop(map); |
1535 | for d in &dummies { | |
1536 | assert_eq!(d.cloned(), if d.id <= i { 1 } else { 0 }, "id={}/{}", d.id, i); | |
1537 | assert_eq!(d.dropped(), if d.id < i { 2 } else { 1 }, "id={}/{}", d.id, i); | |
1538 | } | |
1539 | } | |
1540 | } | |
6a06907d | 1541 | |
c295e0f8 XL |
1542 | #[test] |
1543 | fn test_clone_panic_leak_height_0() { | |
1544 | test_clone_panic_leak(3) | |
1545 | } | |
1546 | ||
1547 | #[test] | |
1548 | fn test_clone_panic_leak_height_1() { | |
1549 | test_clone_panic_leak(MIN_INSERTS_HEIGHT_1) | |
6a06907d XL |
1550 | } |
1551 | ||
74b04a01 XL |
1552 | #[test] |
1553 | fn test_clone_from() { | |
1554 | let mut map1 = BTreeMap::new(); | |
ba9703b0 | 1555 | let max_size = MIN_INSERTS_HEIGHT_1; |
74b04a01 XL |
1556 | |
1557 | // Range to max_size inclusive, because i is the size of map1 being tested. | |
1558 | for i in 0..=max_size { | |
1559 | let mut map2 = BTreeMap::new(); | |
1560 | for j in 0..i { | |
1561 | let mut map1_copy = map2.clone(); | |
1562 | map1_copy.clone_from(&map1); // small cloned from large | |
1563 | assert_eq!(map1_copy, map1); | |
1564 | let mut map2_copy = map1.clone(); | |
1565 | map2_copy.clone_from(&map2); // large cloned from small | |
1566 | assert_eq!(map2_copy, map2); | |
1567 | map2.insert(100 * j + 1, 2 * j + 1); | |
1568 | } | |
1569 | map2.clone_from(&map1); // same length | |
3dfed10e | 1570 | map2.check(); |
74b04a01 XL |
1571 | assert_eq!(map2, map1); |
1572 | map1.insert(i, 10 * i); | |
3dfed10e | 1573 | map1.check(); |
74b04a01 | 1574 | } |
9cc50fc6 SL |
1575 | } |
1576 | ||
7453a54e | 1577 | #[allow(dead_code)] |
a2a8927a | 1578 | fn assert_covariance() { |
3157f602 XL |
1579 | fn map_key<'new>(v: BTreeMap<&'static str, ()>) -> BTreeMap<&'new str, ()> { |
1580 | v | |
1581 | } | |
1582 | fn map_val<'new>(v: BTreeMap<(), &'static str>) -> BTreeMap<(), &'new str> { | |
1583 | v | |
1584 | } | |
29967ef6 | 1585 | |
3157f602 XL |
1586 | fn iter_key<'a, 'new>(v: Iter<'a, &'static str, ()>) -> Iter<'a, &'new str, ()> { |
1587 | v | |
1588 | } | |
1589 | fn iter_val<'a, 'new>(v: Iter<'a, (), &'static str>) -> Iter<'a, (), &'new str> { | |
1590 | v | |
1591 | } | |
29967ef6 | 1592 | |
3157f602 XL |
1593 | fn into_iter_key<'new>(v: IntoIter<&'static str, ()>) -> IntoIter<&'new str, ()> { |
1594 | v | |
1595 | } | |
1596 | fn into_iter_val<'new>(v: IntoIter<(), &'static str>) -> IntoIter<(), &'new str> { | |
1597 | v | |
1598 | } | |
29967ef6 XL |
1599 | |
1600 | fn into_keys_key<'new>(v: IntoKeys<&'static str, ()>) -> IntoKeys<&'new str, ()> { | |
1601 | v | |
1602 | } | |
1603 | fn into_keys_val<'new>(v: IntoKeys<(), &'static str>) -> IntoKeys<(), &'new str> { | |
1604 | v | |
1605 | } | |
1606 | ||
1607 | fn into_values_key<'new>(v: IntoValues<&'static str, ()>) -> IntoValues<&'new str, ()> { | |
1608 | v | |
1609 | } | |
1610 | fn into_values_val<'new>(v: IntoValues<(), &'static str>) -> IntoValues<(), &'new str> { | |
1611 | v | |
1612 | } | |
1613 | ||
3157f602 XL |
1614 | fn range_key<'a, 'new>(v: Range<'a, &'static str, ()>) -> Range<'a, &'new str, ()> { |
1615 | v | |
1616 | } | |
1617 | fn range_val<'a, 'new>(v: Range<'a, (), &'static str>) -> Range<'a, (), &'new str> { | |
1618 | v | |
1619 | } | |
29967ef6 XL |
1620 | |
1621 | fn keys_key<'a, 'new>(v: Keys<'a, &'static str, ()>) -> Keys<'a, &'new str, ()> { | |
1622 | v | |
1623 | } | |
1624 | fn keys_val<'a, 'new>(v: Keys<'a, (), &'static str>) -> Keys<'a, (), &'new str> { | |
1625 | v | |
1626 | } | |
1627 | ||
1628 | fn values_key<'a, 'new>(v: Values<'a, &'static str, ()>) -> Values<'a, &'new str, ()> { | |
3157f602 XL |
1629 | v |
1630 | } | |
29967ef6 | 1631 | fn values_val<'a, 'new>(v: Values<'a, (), &'static str>) -> Values<'a, (), &'new str> { |
3157f602 XL |
1632 | v |
1633 | } | |
9cc50fc6 SL |
1634 | } |
1635 | ||
1b1a35ee | 1636 | #[allow(dead_code)] |
a2a8927a | 1637 | fn assert_sync() { |
1b1a35ee XL |
1638 | fn map<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ { |
1639 | v | |
1640 | } | |
1641 | ||
1642 | fn into_iter<T: Sync>(v: BTreeMap<T, T>) -> impl Sync { | |
1643 | v.into_iter() | |
1644 | } | |
1645 | ||
1646 | fn into_keys<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync { | |
1647 | v.into_keys() | |
1648 | } | |
1649 | ||
1650 | fn into_values<T: Sync + Ord>(v: BTreeMap<T, T>) -> impl Sync { | |
1651 | v.into_values() | |
1652 | } | |
1653 | ||
1654 | fn drain_filter<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1655 | v.drain_filter(|_, _| false) | |
1656 | } | |
1657 | ||
1658 | fn iter<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ { | |
1659 | v.iter() | |
1660 | } | |
1661 | ||
1662 | fn iter_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1663 | v.iter_mut() | |
1664 | } | |
1665 | ||
1666 | fn keys<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ { | |
1667 | v.keys() | |
1668 | } | |
1669 | ||
1670 | fn values<T: Sync>(v: &BTreeMap<T, T>) -> impl Sync + '_ { | |
1671 | v.values() | |
1672 | } | |
1673 | ||
1674 | fn values_mut<T: Sync>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1675 | v.values_mut() | |
1676 | } | |
1677 | ||
1678 | fn range<T: Sync + Ord>(v: &BTreeMap<T, T>) -> impl Sync + '_ { | |
1679 | v.range(..) | |
1680 | } | |
1681 | ||
1682 | fn range_mut<T: Sync + Ord>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1683 | v.range_mut(..) | |
1684 | } | |
1685 | ||
1686 | fn entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1687 | v.entry(Default::default()) | |
1688 | } | |
1689 | ||
1690 | fn occupied_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1691 | match v.entry(Default::default()) { | |
1692 | Occupied(entry) => entry, | |
1693 | _ => unreachable!(), | |
1694 | } | |
1695 | } | |
1696 | ||
1697 | fn vacant_entry<T: Sync + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Sync + '_ { | |
1698 | match v.entry(Default::default()) { | |
1699 | Vacant(entry) => entry, | |
1700 | _ => unreachable!(), | |
1701 | } | |
1702 | } | |
1703 | } | |
1704 | ||
1b1a35ee | 1705 | #[allow(dead_code)] |
a2a8927a | 1706 | fn assert_send() { |
1b1a35ee XL |
1707 | fn map<T: Send>(v: BTreeMap<T, T>) -> impl Send { |
1708 | v | |
1709 | } | |
1710 | ||
1711 | fn into_iter<T: Send>(v: BTreeMap<T, T>) -> impl Send { | |
1712 | v.into_iter() | |
1713 | } | |
1714 | ||
1715 | fn into_keys<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send { | |
1716 | v.into_keys() | |
1717 | } | |
1718 | ||
1719 | fn into_values<T: Send + Ord>(v: BTreeMap<T, T>) -> impl Send { | |
1720 | v.into_values() | |
1721 | } | |
1722 | ||
1723 | fn drain_filter<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { | |
1724 | v.drain_filter(|_, _| false) | |
1725 | } | |
1726 | ||
1727 | fn iter<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ { | |
1728 | v.iter() | |
1729 | } | |
1730 | ||
29967ef6 | 1731 | fn iter_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { |
1b1a35ee XL |
1732 | v.iter_mut() |
1733 | } | |
1734 | ||
1735 | fn keys<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ { | |
1736 | v.keys() | |
1737 | } | |
1738 | ||
1739 | fn values<T: Send + Sync>(v: &BTreeMap<T, T>) -> impl Send + '_ { | |
1740 | v.values() | |
1741 | } | |
1742 | ||
29967ef6 | 1743 | fn values_mut<T: Send>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { |
1b1a35ee XL |
1744 | v.values_mut() |
1745 | } | |
1746 | ||
1747 | fn range<T: Send + Sync + Ord>(v: &BTreeMap<T, T>) -> impl Send + '_ { | |
1748 | v.range(..) | |
1749 | } | |
1750 | ||
29967ef6 | 1751 | fn range_mut<T: Send + Ord>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { |
1b1a35ee XL |
1752 | v.range_mut(..) |
1753 | } | |
1754 | ||
1755 | fn entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { | |
1756 | v.entry(Default::default()) | |
1757 | } | |
1758 | ||
1759 | fn occupied_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { | |
1760 | match v.entry(Default::default()) { | |
1761 | Occupied(entry) => entry, | |
1762 | _ => unreachable!(), | |
1763 | } | |
1764 | } | |
1765 | ||
1766 | fn vacant_entry<T: Send + Ord + Default>(v: &mut BTreeMap<T, T>) -> impl Send + '_ { | |
1767 | match v.entry(Default::default()) { | |
1768 | Vacant(entry) => entry, | |
1769 | _ => unreachable!(), | |
1770 | } | |
1771 | } | |
1772 | } | |
1773 | ||
94222f64 | 1774 | #[test] |
5869c6ff XL |
1775 | fn test_ord_absence() { |
1776 | fn map<K>(mut map: BTreeMap<K, ()>) { | |
c295e0f8 XL |
1777 | let _ = map.is_empty(); |
1778 | let _ = map.len(); | |
6a06907d | 1779 | map.clear(); |
c295e0f8 XL |
1780 | let _ = map.iter(); |
1781 | let _ = map.iter_mut(); | |
1782 | let _ = map.keys(); | |
1783 | let _ = map.values(); | |
1784 | let _ = map.values_mut(); | |
6a06907d | 1785 | if true { |
c295e0f8 | 1786 | let _ = map.into_values(); |
6a06907d | 1787 | } else if true { |
c295e0f8 | 1788 | let _ = map.into_iter(); |
6a06907d | 1789 | } else { |
c295e0f8 | 1790 | let _ = map.into_keys(); |
6a06907d | 1791 | } |
5869c6ff XL |
1792 | } |
1793 | ||
1794 | fn map_debug<K: Debug>(mut map: BTreeMap<K, ()>) { | |
5e7ed085 | 1795 | format!("{map:?}"); |
5869c6ff XL |
1796 | format!("{:?}", map.iter()); |
1797 | format!("{:?}", map.iter_mut()); | |
1798 | format!("{:?}", map.keys()); | |
1799 | format!("{:?}", map.values()); | |
1800 | format!("{:?}", map.values_mut()); | |
6a06907d XL |
1801 | if true { |
1802 | format!("{:?}", map.into_iter()); | |
1803 | } else if true { | |
1804 | format!("{:?}", map.into_keys()); | |
1805 | } else { | |
1806 | format!("{:?}", map.into_values()); | |
1807 | } | |
5869c6ff XL |
1808 | } |
1809 | ||
1810 | fn map_clone<K: Clone>(mut map: BTreeMap<K, ()>) { | |
1811 | map.clone_from(&map.clone()); | |
1812 | } | |
5869c6ff | 1813 | |
94222f64 XL |
1814 | #[derive(Debug, Clone)] |
1815 | struct NonOrd; | |
1816 | map(BTreeMap::<NonOrd, _>::new()); | |
1817 | map_debug(BTreeMap::<NonOrd, _>::new()); | |
1818 | map_clone(BTreeMap::<NonOrd, _>::default()); | |
29967ef6 XL |
1819 | } |
1820 | ||
54a0048b SL |
1821 | #[test] |
1822 | fn test_occupied_entry_key() { | |
1823 | let mut a = BTreeMap::new(); | |
1824 | let key = "hello there"; | |
1825 | let value = "value goes here"; | |
5e7ed085 | 1826 | assert_eq!(a.height(), None); |
6a06907d | 1827 | a.insert(key, value); |
54a0048b SL |
1828 | assert_eq!(a.len(), 1); |
1829 | assert_eq!(a[key], value); | |
1830 | ||
6a06907d | 1831 | match a.entry(key) { |
54a0048b SL |
1832 | Vacant(_) => panic!(), |
1833 | Occupied(e) => assert_eq!(key, *e.key()), | |
1834 | } | |
1835 | assert_eq!(a.len(), 1); | |
1836 | assert_eq!(a[key], value); | |
3dfed10e | 1837 | a.check(); |
54a0048b SL |
1838 | } |
1839 | ||
1840 | #[test] | |
1841 | fn test_vacant_entry_key() { | |
1842 | let mut a = BTreeMap::new(); | |
1843 | let key = "hello there"; | |
1844 | let value = "value goes here"; | |
1845 | ||
5e7ed085 | 1846 | assert_eq!(a.height(), None); |
6a06907d | 1847 | match a.entry(key) { |
5e7ed085 | 1848 | Occupied(_) => unreachable!(), |
54a0048b SL |
1849 | Vacant(e) => { |
1850 | assert_eq!(key, *e.key()); | |
6a06907d | 1851 | e.insert(value); |
3157f602 | 1852 | } |
54a0048b SL |
1853 | } |
1854 | assert_eq!(a.len(), 1); | |
1855 | assert_eq!(a[key], value); | |
3dfed10e | 1856 | a.check(); |
54a0048b SL |
1857 | } |
1858 | ||
5e7ed085 FG |
1859 | #[test] |
1860 | fn test_vacant_entry_no_insert() { | |
1861 | let mut a = BTreeMap::<&str, ()>::new(); | |
1862 | let key = "hello there"; | |
1863 | ||
1864 | // Non-allocated | |
1865 | assert_eq!(a.height(), None); | |
1866 | match a.entry(key) { | |
1867 | Occupied(_) => unreachable!(), | |
1868 | Vacant(e) => assert_eq!(key, *e.key()), | |
1869 | } | |
1870 | // Ensures the tree has no root. | |
1871 | assert_eq!(a.height(), None); | |
1872 | a.check(); | |
1873 | ||
1874 | // Allocated but still empty | |
1875 | a.insert(key, ()); | |
1876 | a.remove(&key); | |
1877 | assert_eq!(a.height(), Some(0)); | |
1878 | assert!(a.is_empty()); | |
1879 | match a.entry(key) { | |
1880 | Occupied(_) => unreachable!(), | |
1881 | Vacant(e) => assert_eq!(key, *e.key()), | |
1882 | } | |
1883 | // Ensures the allocated root is not changed. | |
1884 | assert_eq!(a.height(), Some(0)); | |
1885 | assert!(a.is_empty()); | |
1886 | a.check(); | |
1887 | } | |
1888 | ||
60c5eb7d XL |
1889 | #[test] |
1890 | fn test_first_last_entry() { | |
1891 | let mut a = BTreeMap::new(); | |
1892 | assert!(a.first_entry().is_none()); | |
1893 | assert!(a.last_entry().is_none()); | |
1894 | a.insert(1, 42); | |
1895 | assert_eq!(a.first_entry().unwrap().key(), &1); | |
1896 | assert_eq!(a.last_entry().unwrap().key(), &1); | |
1897 | a.insert(2, 24); | |
1898 | assert_eq!(a.first_entry().unwrap().key(), &1); | |
1899 | assert_eq!(a.last_entry().unwrap().key(), &2); | |
1900 | a.insert(0, 6); | |
1901 | assert_eq!(a.first_entry().unwrap().key(), &0); | |
1902 | assert_eq!(a.last_entry().unwrap().key(), &2); | |
1903 | let (k1, v1) = a.first_entry().unwrap().remove_entry(); | |
1904 | assert_eq!(k1, 0); | |
1905 | assert_eq!(v1, 6); | |
1906 | let (k2, v2) = a.last_entry().unwrap().remove_entry(); | |
1907 | assert_eq!(k2, 2); | |
1908 | assert_eq!(v2, 24); | |
1909 | assert_eq!(a.first_entry().unwrap().key(), &1); | |
1910 | assert_eq!(a.last_entry().unwrap().key(), &1); | |
3dfed10e XL |
1911 | a.check(); |
1912 | } | |
1913 | ||
04454e1e FG |
1914 | #[test] |
1915 | fn test_pop_first_last() { | |
1916 | let mut map = BTreeMap::new(); | |
1917 | assert_eq!(map.pop_first(), None); | |
1918 | assert_eq!(map.pop_last(), None); | |
1919 | ||
1920 | map.insert(1, 10); | |
1921 | map.insert(2, 20); | |
1922 | map.insert(3, 30); | |
1923 | map.insert(4, 40); | |
1924 | ||
1925 | assert_eq!(map.len(), 4); | |
1926 | ||
1927 | let (key, val) = map.pop_first().unwrap(); | |
1928 | assert_eq!(key, 1); | |
1929 | assert_eq!(val, 10); | |
1930 | assert_eq!(map.len(), 3); | |
1931 | ||
1932 | let (key, val) = map.pop_first().unwrap(); | |
1933 | assert_eq!(key, 2); | |
1934 | assert_eq!(val, 20); | |
1935 | assert_eq!(map.len(), 2); | |
1936 | let (key, val) = map.pop_last().unwrap(); | |
1937 | assert_eq!(key, 4); | |
1938 | assert_eq!(val, 40); | |
1939 | assert_eq!(map.len(), 1); | |
1940 | ||
1941 | map.insert(5, 50); | |
1942 | map.insert(6, 60); | |
1943 | assert_eq!(map.len(), 3); | |
1944 | ||
1945 | let (key, val) = map.pop_first().unwrap(); | |
1946 | assert_eq!(key, 3); | |
1947 | assert_eq!(val, 30); | |
1948 | assert_eq!(map.len(), 2); | |
1949 | ||
1950 | let (key, val) = map.pop_last().unwrap(); | |
1951 | assert_eq!(key, 6); | |
1952 | assert_eq!(val, 60); | |
1953 | assert_eq!(map.len(), 1); | |
1954 | ||
1955 | let (key, val) = map.pop_last().unwrap(); | |
1956 | assert_eq!(key, 5); | |
1957 | assert_eq!(val, 50); | |
1958 | assert_eq!(map.len(), 0); | |
1959 | ||
1960 | assert_eq!(map.pop_first(), None); | |
1961 | assert_eq!(map.pop_last(), None); | |
1962 | ||
1963 | map.insert(7, 70); | |
1964 | map.insert(8, 80); | |
1965 | ||
1966 | let (key, val) = map.pop_last().unwrap(); | |
1967 | assert_eq!(key, 8); | |
1968 | assert_eq!(val, 80); | |
1969 | assert_eq!(map.len(), 1); | |
1970 | ||
1971 | let (key, val) = map.pop_last().unwrap(); | |
1972 | assert_eq!(key, 7); | |
1973 | assert_eq!(val, 70); | |
1974 | assert_eq!(map.len(), 0); | |
1975 | ||
1976 | assert_eq!(map.pop_first(), None); | |
1977 | assert_eq!(map.pop_last(), None); | |
1978 | } | |
1979 | ||
1980 | #[test] | |
1981 | fn test_get_key_value() { | |
1982 | let mut map = BTreeMap::new(); | |
1983 | ||
1984 | assert!(map.is_empty()); | |
1985 | assert_eq!(map.get_key_value(&1), None); | |
1986 | assert_eq!(map.get_key_value(&2), None); | |
1987 | ||
1988 | map.insert(1, 10); | |
1989 | map.insert(2, 20); | |
1990 | map.insert(3, 30); | |
1991 | ||
1992 | assert_eq!(map.len(), 3); | |
1993 | assert_eq!(map.get_key_value(&1), Some((&1, &10))); | |
1994 | assert_eq!(map.get_key_value(&3), Some((&3, &30))); | |
1995 | assert_eq!(map.get_key_value(&4), None); | |
1996 | ||
1997 | map.remove(&3); | |
1998 | ||
1999 | assert_eq!(map.len(), 2); | |
2000 | assert_eq!(map.get_key_value(&3), None); | |
2001 | assert_eq!(map.get_key_value(&2), Some((&2, &20))); | |
2002 | } | |
2003 | ||
3dfed10e | 2004 | #[test] |
5869c6ff | 2005 | fn test_insert_into_full_height_0() { |
5e7ed085 | 2006 | let size = node::CAPACITY; |
5869c6ff | 2007 | for pos in 0..=size { |
5e7ed085 | 2008 | let mut map = BTreeMap::from_iter((0..size).map(|i| (i * 2 + 1, ()))); |
5869c6ff XL |
2009 | assert!(map.insert(pos * 2, ()).is_none()); |
2010 | map.check(); | |
2011 | } | |
3dfed10e XL |
2012 | } |
2013 | ||
2014 | #[test] | |
5869c6ff | 2015 | fn test_insert_into_full_height_1() { |
5e7ed085 | 2016 | let size = node::CAPACITY + 1 + node::CAPACITY; |
5869c6ff | 2017 | for pos in 0..=size { |
5e7ed085 | 2018 | let mut map = BTreeMap::from_iter((0..size).map(|i| (i * 2 + 1, ()))); |
5869c6ff XL |
2019 | map.compact(); |
2020 | let root_node = map.root.as_ref().unwrap().reborrow(); | |
2021 | assert_eq!(root_node.len(), 1); | |
5e7ed085 FG |
2022 | assert_eq!(root_node.first_leaf_edge().into_node().len(), node::CAPACITY); |
2023 | assert_eq!(root_node.last_leaf_edge().into_node().len(), node::CAPACITY); | |
5869c6ff XL |
2024 | |
2025 | assert!(map.insert(pos * 2, ()).is_none()); | |
2026 | map.check(); | |
2027 | } | |
60c5eb7d XL |
2028 | } |
2029 | ||
04454e1e FG |
2030 | #[test] |
2031 | fn test_try_insert() { | |
2032 | let mut map = BTreeMap::new(); | |
2033 | ||
2034 | assert!(map.is_empty()); | |
2035 | ||
2036 | assert_eq!(map.try_insert(1, 10).unwrap(), &10); | |
2037 | assert_eq!(map.try_insert(2, 20).unwrap(), &20); | |
2038 | ||
2039 | let err = map.try_insert(2, 200).unwrap_err(); | |
2040 | assert_eq!(err.entry.key(), &2); | |
2041 | assert_eq!(err.entry.get(), &20); | |
2042 | assert_eq!(err.value, 200); | |
2043 | } | |
2044 | ||
a7813a04 XL |
2045 | macro_rules! create_append_test { |
2046 | ($name:ident, $len:expr) => { | |
2047 | #[test] | |
2048 | fn $name() { | |
2049 | let mut a = BTreeMap::new(); | |
2050 | for i in 0..8 { | |
2051 | a.insert(i, i); | |
2052 | } | |
2053 | ||
2054 | let mut b = BTreeMap::new(); | |
2055 | for i in 5..$len { | |
dfeec247 | 2056 | b.insert(i, 2 * i); |
a7813a04 XL |
2057 | } |
2058 | ||
2059 | a.append(&mut b); | |
2060 | ||
2061 | assert_eq!(a.len(), $len); | |
2062 | assert_eq!(b.len(), 0); | |
2063 | ||
2064 | for i in 0..$len { | |
2065 | if i < 5 { | |
2066 | assert_eq!(a[&i], i); | |
2067 | } else { | |
dfeec247 | 2068 | assert_eq!(a[&i], 2 * i); |
a7813a04 XL |
2069 | } |
2070 | } | |
2071 | ||
3dfed10e | 2072 | a.check(); |
dfeec247 XL |
2073 | assert_eq!(a.remove(&($len - 1)), Some(2 * ($len - 1))); |
2074 | assert_eq!(a.insert($len - 1, 20), None); | |
3dfed10e | 2075 | a.check(); |
a7813a04 XL |
2076 | } |
2077 | }; | |
2078 | } | |
2079 | ||
2080 | // These are mostly for testing the algorithm that "fixes" the right edge after insertion. | |
2081 | // Single node. | |
2082 | create_append_test!(test_append_9, 9); | |
2083 | // Two leafs that don't need fixing. | |
2084 | create_append_test!(test_append_17, 17); | |
2085 | // Two leafs where the second one ends up underfull and needs stealing at the end. | |
2086 | create_append_test!(test_append_14, 14); | |
2087 | // Two leafs where the second one ends up empty because the insertion finished at the root. | |
2088 | create_append_test!(test_append_12, 12); | |
2089 | // Three levels; insertion finished at the root. | |
2090 | create_append_test!(test_append_144, 144); | |
2091 | // Three levels; insertion finished at leaf while there is an empty node on the second level. | |
2092 | create_append_test!(test_append_145, 145); | |
2093 | // Tests for several randomly chosen sizes. | |
2094 | create_append_test!(test_append_170, 170); | |
2095 | create_append_test!(test_append_181, 181); | |
74b04a01 | 2096 | #[cfg(not(miri))] // Miri is too slow |
a7813a04 | 2097 | create_append_test!(test_append_239, 239); |
9fa01778 | 2098 | #[cfg(not(miri))] // Miri is too slow |
a7813a04 XL |
2099 | create_append_test!(test_append_1700, 1700); |
2100 | ||
29967ef6 XL |
2101 | #[test] |
2102 | fn test_append_drop_leak() { | |
6a06907d XL |
2103 | let a = CrashTestDummy::new(0); |
2104 | let b = CrashTestDummy::new(1); | |
2105 | let c = CrashTestDummy::new(2); | |
29967ef6 XL |
2106 | let mut left = BTreeMap::new(); |
2107 | let mut right = BTreeMap::new(); | |
6a06907d XL |
2108 | left.insert(a.spawn(Panic::Never), ()); |
2109 | left.insert(b.spawn(Panic::InDrop), ()); // first duplicate key, dropped during append | |
2110 | left.insert(c.spawn(Panic::Never), ()); | |
2111 | right.insert(b.spawn(Panic::Never), ()); | |
2112 | right.insert(c.spawn(Panic::Never), ()); | |
29967ef6 XL |
2113 | |
2114 | catch_unwind(move || left.append(&mut right)).unwrap_err(); | |
6a06907d XL |
2115 | assert_eq!(a.dropped(), 1); |
2116 | assert_eq!(b.dropped(), 1); // should be 2 were it not for Rust issue #47949 | |
2117 | assert_eq!(c.dropped(), 2); | |
fc512014 XL |
2118 | } |
2119 | ||
2120 | #[test] | |
2121 | fn test_append_ord_chaos() { | |
2122 | let mut map1 = BTreeMap::new(); | |
2123 | map1.insert(Cyclic3::A, ()); | |
2124 | map1.insert(Cyclic3::B, ()); | |
2125 | let mut map2 = BTreeMap::new(); | |
2126 | map2.insert(Cyclic3::A, ()); | |
2127 | map2.insert(Cyclic3::B, ()); | |
2128 | map2.insert(Cyclic3::C, ()); // lands first, before A | |
2129 | map2.insert(Cyclic3::B, ()); // lands first, before C | |
2130 | map1.check(); | |
2131 | map2.check(); // keys are not unique but still strictly ascending | |
2132 | assert_eq!(map1.len(), 2); | |
2133 | assert_eq!(map2.len(), 4); | |
2134 | map1.append(&mut map2); | |
2135 | assert_eq!(map1.len(), 5); | |
2136 | assert_eq!(map2.len(), 0); | |
2137 | map1.check(); | |
2138 | map2.check(); | |
29967ef6 XL |
2139 | } |
2140 | ||
3157f602 XL |
2141 | fn rand_data(len: usize) -> Vec<(u32, u32)> { |
2142 | let mut rng = DeterministicRng::new(); | |
c30ab7b3 | 2143 | Vec::from_iter((0..len).map(|_| (rng.next(), rng.next()))) |
3157f602 XL |
2144 | } |
2145 | ||
2146 | #[test] | |
2147 | fn test_split_off_empty_right() { | |
2148 | let mut data = rand_data(173); | |
2149 | ||
2150 | let mut map = BTreeMap::from_iter(data.clone()); | |
2151 | let right = map.split_off(&(data.iter().max().unwrap().0 + 1)); | |
3dfed10e XL |
2152 | map.check(); |
2153 | right.check(); | |
3157f602 XL |
2154 | |
2155 | data.sort(); | |
2156 | assert!(map.into_iter().eq(data)); | |
2157 | assert!(right.into_iter().eq(None)); | |
2158 | } | |
2159 | ||
2160 | #[test] | |
2161 | fn test_split_off_empty_left() { | |
2162 | let mut data = rand_data(314); | |
2163 | ||
2164 | let mut map = BTreeMap::from_iter(data.clone()); | |
2165 | let right = map.split_off(&data.iter().min().unwrap().0); | |
3dfed10e XL |
2166 | map.check(); |
2167 | right.check(); | |
3157f602 XL |
2168 | |
2169 | data.sort(); | |
2170 | assert!(map.into_iter().eq(None)); | |
2171 | assert!(right.into_iter().eq(data)); | |
2172 | } | |
2173 | ||
3dfed10e XL |
2174 | // In a tree with 3 levels, if all but a part of the first leaf node is split off, |
2175 | // make sure fix_top eliminates both top levels. | |
2176 | #[test] | |
2177 | fn test_split_off_tiny_left_height_2() { | |
2178 | let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); | |
5e7ed085 | 2179 | let mut left = BTreeMap::from_iter(pairs.clone()); |
3dfed10e XL |
2180 | let right = left.split_off(&1); |
2181 | left.check(); | |
2182 | right.check(); | |
2183 | assert_eq!(left.len(), 1); | |
2184 | assert_eq!(right.len(), MIN_INSERTS_HEIGHT_2 - 1); | |
2185 | assert_eq!(*left.first_key_value().unwrap().0, 0); | |
2186 | assert_eq!(*right.first_key_value().unwrap().0, 1); | |
2187 | } | |
2188 | ||
2189 | // In a tree with 3 levels, if only part of the last leaf node is split off, | |
2190 | // make sure fix_top eliminates both top levels. | |
2191 | #[test] | |
2192 | fn test_split_off_tiny_right_height_2() { | |
2193 | let pairs = (0..MIN_INSERTS_HEIGHT_2).map(|i| (i, i)); | |
2194 | let last = MIN_INSERTS_HEIGHT_2 - 1; | |
5e7ed085 | 2195 | let mut left = BTreeMap::from_iter(pairs.clone()); |
3dfed10e XL |
2196 | assert_eq!(*left.last_key_value().unwrap().0, last); |
2197 | let right = left.split_off(&last); | |
2198 | left.check(); | |
2199 | right.check(); | |
2200 | assert_eq!(left.len(), MIN_INSERTS_HEIGHT_2 - 1); | |
2201 | assert_eq!(right.len(), 1); | |
2202 | assert_eq!(*left.last_key_value().unwrap().0, last - 1); | |
2203 | assert_eq!(*right.last_key_value().unwrap().0, last); | |
2204 | } | |
2205 | ||
5869c6ff XL |
2206 | #[test] |
2207 | fn test_split_off_halfway() { | |
2208 | let mut rng = DeterministicRng::new(); | |
5e7ed085 | 2209 | for &len in &[node::CAPACITY, 25, 50, 75, 100] { |
5869c6ff XL |
2210 | let mut data = Vec::from_iter((0..len).map(|_| (rng.next(), ()))); |
2211 | // Insertion in non-ascending order creates some variation in node length. | |
2212 | let mut map = BTreeMap::from_iter(data.iter().copied()); | |
2213 | data.sort(); | |
2214 | let small_keys = data.iter().take(len / 2).map(|kv| kv.0); | |
2215 | let large_keys = data.iter().skip(len / 2).map(|kv| kv.0); | |
2216 | let split_key = large_keys.clone().next().unwrap(); | |
2217 | let right = map.split_off(&split_key); | |
2218 | map.check(); | |
2219 | right.check(); | |
2220 | assert!(map.keys().copied().eq(small_keys)); | |
2221 | assert!(right.keys().copied().eq(large_keys)); | |
2222 | } | |
2223 | } | |
2224 | ||
3157f602 XL |
2225 | #[test] |
2226 | fn test_split_off_large_random_sorted() { | |
f9f354fc XL |
2227 | // Miri is too slow |
2228 | let mut data = if cfg!(miri) { rand_data(529) } else { rand_data(1529) }; | |
3157f602 XL |
2229 | // special case with maximum height. |
2230 | data.sort(); | |
2231 | ||
2232 | let mut map = BTreeMap::from_iter(data.clone()); | |
2233 | let key = data[data.len() / 2].0; | |
2234 | let right = map.split_off(&key); | |
3dfed10e XL |
2235 | map.check(); |
2236 | right.check(); | |
3157f602 XL |
2237 | |
2238 | assert!(map.into_iter().eq(data.clone().into_iter().filter(|x| x.0 < key))); | |
2239 | assert!(right.into_iter().eq(data.into_iter().filter(|x| x.0 >= key))); | |
2240 | } | |
74b04a01 XL |
2241 | |
2242 | #[test] | |
ba9703b0 | 2243 | fn test_into_iter_drop_leak_height_0() { |
6a06907d XL |
2244 | let a = CrashTestDummy::new(0); |
2245 | let b = CrashTestDummy::new(1); | |
2246 | let c = CrashTestDummy::new(2); | |
2247 | let d = CrashTestDummy::new(3); | |
2248 | let e = CrashTestDummy::new(4); | |
74b04a01 | 2249 | let mut map = BTreeMap::new(); |
6a06907d XL |
2250 | map.insert("a", a.spawn(Panic::Never)); |
2251 | map.insert("b", b.spawn(Panic::Never)); | |
2252 | map.insert("c", c.spawn(Panic::Never)); | |
2253 | map.insert("d", d.spawn(Panic::InDrop)); | |
2254 | map.insert("e", e.spawn(Panic::Never)); | |
74b04a01 | 2255 | |
3dfed10e | 2256 | catch_unwind(move || drop(map.into_iter())).unwrap_err(); |
74b04a01 | 2257 | |
6a06907d XL |
2258 | assert_eq!(a.dropped(), 1); |
2259 | assert_eq!(b.dropped(), 1); | |
2260 | assert_eq!(c.dropped(), 1); | |
2261 | assert_eq!(d.dropped(), 1); | |
2262 | assert_eq!(e.dropped(), 1); | |
74b04a01 XL |
2263 | } |
2264 | ||
2265 | #[test] | |
ba9703b0 XL |
2266 | fn test_into_iter_drop_leak_height_1() { |
2267 | let size = MIN_INSERTS_HEIGHT_1; | |
74b04a01 | 2268 | for panic_point in vec![0, 1, size - 2, size - 1] { |
5e7ed085 FG |
2269 | let dummies = Vec::from_iter((0..size).map(|i| CrashTestDummy::new(i))); |
2270 | let map = BTreeMap::from_iter((0..size).map(|i| { | |
2271 | let panic = if i == panic_point { Panic::InDrop } else { Panic::Never }; | |
2272 | (dummies[i].spawn(Panic::Never), dummies[i].spawn(panic)) | |
2273 | })); | |
3dfed10e | 2274 | catch_unwind(move || drop(map.into_iter())).unwrap_err(); |
6a06907d XL |
2275 | for i in 0..size { |
2276 | assert_eq!(dummies[i].dropped(), 2); | |
2277 | } | |
74b04a01 XL |
2278 | } |
2279 | } | |
3dfed10e XL |
2280 | |
2281 | #[test] | |
2282 | fn test_into_keys() { | |
5e7ed085 FG |
2283 | let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); |
2284 | let keys = Vec::from_iter(map.into_keys()); | |
3dfed10e XL |
2285 | |
2286 | assert_eq!(keys.len(), 3); | |
2287 | assert!(keys.contains(&1)); | |
2288 | assert!(keys.contains(&2)); | |
2289 | assert!(keys.contains(&3)); | |
2290 | } | |
2291 | ||
2292 | #[test] | |
2293 | fn test_into_values() { | |
5e7ed085 FG |
2294 | let map = BTreeMap::from([(1, 'a'), (2, 'b'), (3, 'c')]); |
2295 | let values = Vec::from_iter(map.into_values()); | |
3dfed10e XL |
2296 | |
2297 | assert_eq!(values.len(), 3); | |
2298 | assert!(values.contains(&'a')); | |
2299 | assert!(values.contains(&'b')); | |
2300 | assert!(values.contains(&'c')); | |
2301 | } | |
1b1a35ee XL |
2302 | |
2303 | #[test] | |
2304 | fn test_insert_remove_intertwined() { | |
2305 | let loops = if cfg!(miri) { 100 } else { 1_000_000 }; | |
2306 | let mut map = BTreeMap::new(); | |
2307 | let mut i = 1; | |
fc512014 | 2308 | let offset = 165; // somewhat arbitrarily chosen to cover some code paths |
1b1a35ee | 2309 | for _ in 0..loops { |
fc512014 | 2310 | i = (i + offset) & 0xFF; |
1b1a35ee XL |
2311 | map.insert(i, i); |
2312 | map.remove(&(0xFF - i)); | |
2313 | } | |
1b1a35ee XL |
2314 | map.check(); |
2315 | } | |
fc512014 XL |
2316 | |
2317 | #[test] | |
2318 | fn test_insert_remove_intertwined_ord_chaos() { | |
2319 | let loops = if cfg!(miri) { 100 } else { 1_000_000 }; | |
2320 | let gov = Governor::new(); | |
2321 | let mut map = BTreeMap::new(); | |
2322 | let mut i = 1; | |
2323 | let offset = 165; // more arbitrarily copied from above | |
2324 | for _ in 0..loops { | |
2325 | i = (i + offset) & 0xFF; | |
2326 | map.insert(Governed(i, &gov), ()); | |
2327 | map.remove(&Governed(0xFF - i, &gov)); | |
2328 | gov.flip(); | |
2329 | } | |
2330 | map.check_invariants(); | |
2331 | } | |
94222f64 XL |
2332 | |
2333 | #[test] | |
2334 | fn from_array() { | |
2335 | let map = BTreeMap::from([(1, 2), (3, 4)]); | |
2336 | let unordered_duplicates = BTreeMap::from([(3, 4), (1, 2), (1, 2)]); | |
2337 | assert_eq!(map, unordered_duplicates); | |
2338 | } |