n_key_list.rs
1 //! Declaration for an n-keyed list type, allowing access to each of its members by each of N 2 //! different keys. 3 4 // Re-export dependencies that we use to make this macro work. 5 #[doc(hidden)] 6 pub mod deps { 7 pub use paste::paste; 8 pub use slab::Slab; 9 pub use smallvec::SmallVec; 10 } 11 12 /// Declare a structure that can hold elements with multiple unique keys. 13 /// 14 /// Each element can be looked up by any of its keys. The keys themselves can be any type that 15 /// supports `Hash`, `Eq`, and `Clone`. Elements can have multiple keys of the same type: for 16 /// example, a person can have a username `String` and an irc_handle `String`. 17 /// 18 /// Multiple values can be stored for a given key: a lookup of one key returns all elements with 19 /// that key. 20 /// 21 /// Keys may be accessed from elements either by field access or by an accessor function. 22 /// 23 /// Keys may be optional. If all keys are optional, then we require additionally that every element 24 /// must have at least one key. 25 /// 26 /// # Examples 27 /// 28 /// ``` 29 /// use tor_basic_utils::n_key_list; 30 /// 31 /// // We declare a person struct with several different fields. 32 /// pub struct Person { 33 /// username: String, 34 /// irc_handle: String, 35 /// student_id: Option<u64>, 36 /// favorite_joke: Option<String>, 37 /// } 38 /// 39 /// n_key_list! { 40 /// pub struct PersonList for Person { 41 /// // See note on "Key syntax" below. The ".foo" syntax 42 /// // here means that the value for the key is returned 43 /// // by accessing a given field. 44 /// username: String { .username }, 45 /// irc_handle: String { .irc_handle }, 46 /// (Option) student_id: u64 { .student_id } 47 /// } 48 /// } 49 /// 50 /// let mut people = PersonList::new(); 51 /// people.insert(Person { 52 /// username: "mina".into(), 53 /// irc_handle: "pashMina".into(), 54 /// student_id: None, 55 /// favorite_joke: None, 56 /// }); 57 /// assert_eq!(people.by_username("mina").len(), 1); 58 /// assert_eq!(people.by_irc_handle("pashMina").len(), 1); 59 /// ``` 60 /// 61 /// # Key syntax 62 /// 63 /// You can tell the map to access the keys of an element in any of several ways. 64 /// 65 /// * `name : type { func() }` - A key whose name is `name` and type is `type`, that can be accessed 66 /// from a given element by calling `element.func()`. 67 /// * `name : type { .field }` - A key whose name is `name` and type is `type`, that can be accessed 68 /// from a given element by calling `&element.field`. 69 /// * `name : type` - Short for as `name : type { name() }`. 70 /// 71 /// If a key declaration is preceded with `(Option)`, then the key is treated as optional, and 72 /// accessor functions are expected to return `Option<&Type>`. 73 /// 74 /// # Additional features 75 /// 76 /// You can put generic parameters and `where` constraints on your structure. The `where` clause (if 77 /// present) must be wrapped in square brackets. 78 /// 79 /// If you need to use const generics or lifetimes in your structure, you need to use square 80 /// brackets instead of angle brackets, and specify both the generic parameters *and* the type that 81 /// you are implementing. (This is due to limitations in the Rust macro system.) For example: 82 /// 83 /// ``` 84 /// # use tor_basic_utils::n_key_list; 85 /// n_key_list!{ 86 /// struct['a, T, const N: usize] ArrayMap2['a, T, N] for (String, [&'a T;N]) 87 /// [ where T: Clone + 'a ] 88 /// { 89 /// name: String { .0 } 90 /// } 91 /// } 92 /// ``` 93 #[macro_export] 94 macro_rules! n_key_list { 95 { 96 $(#[$meta:meta])* 97 $vis:vis struct $mapname:ident $(<$($P:ident),*>)? for $V:ty 98 $( where [ $($constr:tt)+ ] )? 99 { 100 $($body:tt)+ 101 } 102 } => { 103 n_key_list!{ 104 $(#[$meta])* 105 $vis struct [$($($P),*)?] $mapname [$($($P),*)?] for $V 106 $( [ where $($constr)+ ] )? 107 { 108 $( $body )+ 109 } 110 } 111 }; 112 { 113 $(#[$meta:meta])* 114 $vis:vis struct [$($($G:tt)+)?] $mapname:ident [$($($P:tt)+)?] for $V:ty 115 $( [ where $($constr:tt)+ ])? 116 { 117 $( $(( $($flag:ident)+ ))? $key:ident : $KEY:ty $({ $($source:tt)+ })? ),+ 118 $(,)? 119 } 120 } => { 121 $crate::n_key_list::deps::paste!{ 122 $( #[$meta] )* 123 /// # General information 124 /// 125 #[doc = concat!( 126 "A list of elements of type `", stringify!($V), "` whose members can be accessed by multiple keys." 127 )] 128 /// 129 /// The keys are: 130 /// 131 #[doc = $( "- `" $key "` (`" $KEY "`)" $(" (" $($flag)+ ")\n" )? )+] 132 /// 133 /// Each element has a value for *each* required key, and up to one value for *each* optional 134 /// key. There can be many elements for a given key value. 135 /// 136 /// ## Requirements 137 /// 138 /// Key types must have consistent `Hash` and `Eq` implementations, as they will be used as keys 139 /// in a `HashMap`. 140 /// 141 /// If all keys are optional, then every element inserted must have at least one non-`None` key. 142 /// 143 /// An element must not change its keys over time through interior mutability. 144 /// 145 /// <div class='warning'> 146 /// 147 /// If *any* of these rules is violated, the consequences are unspecified, and could include 148 /// panics or wrong answers (but not memory-unsafety). 149 /// 150 /// </div> 151 $vis struct $mapname $(<$($G)*>)? 152 where 153 $( $KEY : std::hash::Hash + Eq + Clone , )+ 154 $($($constr)+, )? 155 { 156 /// The $key fields here are a set of maps from each of the key values to the lists of the 157 /// positions of values with the same key within the Slab. 158 /// 159 /// Invariants: 160 /// - There is an entry K=>idx in the map `$key` if and only if values[idx].$accessor() == 161 /// K. 162 /// - Every value in `values` has at least one key. 163 /// - A list should never be empty. 164 /// 165 /// The map values (the lists) are effectively a set, but using an inline vec should have 166 /// better cache performance than something like HashSet. 167 /// 168 /// The SmallVec size of 4 was chosen arbitrarily under the assumption that a given key will 169 /// have a small number of values on average. The exact constant probably won't matter, but 170 /// inlining most of the lists should be good even if some spill into separate memory 171 /// allocations. It's not worth exposing this level of internal detail to the macro caller 172 /// unless there's a reason we need to. 173 $([<$key _map>]: std::collections::HashMap<$KEY, $crate::n_key_list::deps::SmallVec<[usize; 4]>> , )+ 174 175 /// A map from the indices to the values. 176 values: $crate::n_key_list::deps::Slab<$V>, 177 } 178 179 #[allow(dead_code)] // may be needed if this is not public 180 impl $(<$($G)*>)? $mapname $(<$($P)*>)? 181 where 182 $( $KEY : std::hash::Hash + Eq + Clone , )+ 183 $($($constr)+)? 184 { 185 #[doc = "Construct a new [`" $mapname "`](Self)."] 186 $vis fn new() -> Self { 187 Self::with_capacity(0) 188 } 189 190 #[doc = "Construct a new [`" $mapname "`](Self) with a given capacity."] 191 $vis fn with_capacity(n: usize) -> Self { 192 Self { 193 $([<$key _map>]: std::collections::HashMap::with_capacity(n),)* 194 values: $crate::n_key_list::deps::Slab::with_capacity(n), 195 } 196 } 197 198 // for each key type 199 $( 200 #[doc = "Return an iterator of the elements whose `" $key "` is `key`."] 201 /// 202 /// The iteration order is arbitrary. 203 $vis fn [<by_ $key>] <BorrowAsKey_>(&self, key: &BorrowAsKey_) -> [<$mapname Iter>] <'_, $V> 204 where 205 $KEY : std::borrow::Borrow<BorrowAsKey_>, 206 BorrowAsKey_: std::hash::Hash + Eq + ?Sized, 207 { 208 [<$mapname Iter>] { 209 iter: self.[<$key _map>].get(key).map(|set| set.iter()).unwrap_or([].iter()), 210 values: &self.values, 211 } 212 } 213 214 #[doc = "Return `true` if this list contains an element whose `" $key "` is `key`."] 215 $vis fn [<contains_ $key>] <BorrowAsKey_>(&mut self, key: &BorrowAsKey_) -> bool 216 where 217 $KEY : std::borrow::Borrow<BorrowAsKey_>, 218 BorrowAsKey_: std::hash::Hash + Eq + ?Sized, 219 { 220 let Some(list) = self.[<$key _map>].get(key) else { 221 return false; 222 }; 223 224 if list.is_empty() { 225 // we're not supposed to let this happen, so panic in debug builds 226 #[cfg(debug_assertions)] 227 panic!("Should not have an empty list"); 228 #[cfg(not(debug_assertions))] 229 return false; 230 } 231 232 true 233 } 234 235 #[doc = "Remove and return the elements whose `" $key "` is `key`"] 236 /// and where `filter` returns `true`. 237 $vis fn [<remove_by_ $key>] <BorrowAsKey_>( 238 &mut self, 239 key: &BorrowAsKey_, 240 mut filter: impl FnMut(&$V) -> bool, 241 ) -> Vec<$V> 242 where 243 $KEY : std::borrow::Borrow<BorrowAsKey_>, 244 BorrowAsKey_: std::hash::Hash + Eq + ?Sized, 245 { 246 let idx_list: Vec<usize> = { 247 let Some(set) = self.[<$key _map>].get(key) else { 248 return Vec::new(); 249 }; 250 251 set 252 .iter() 253 .filter(|&&idx| filter(self.values.get(idx).expect("inconsistent state"))) 254 .copied() 255 .collect() 256 }; 257 258 let mut removed = Vec::with_capacity(idx_list.len()); 259 for idx in idx_list { 260 removed.push(self.remove_at(idx).expect("inconsistent state")); 261 } 262 263 removed 264 } 265 )+ 266 267 fn remove_at(&mut self, idx: usize) -> Option<$V> { 268 if let Some(removed) = self.values.try_remove(idx) { 269 $( 270 let $key = $crate::n_key_list!( @access(removed, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ); 271 if let Some($key) = $key { 272 let set = self.[<$key _map>].get_mut($key).expect("inconsistent state"); 273 274 #[cfg(debug_assertions)] 275 let size_before_remove = set.len(); 276 277 // a `swap_retain` if it existed might be nice here, but the set should be small 278 // so shifting all later elements should be fine 279 set.retain(|x| *x != idx); 280 281 #[cfg(debug_assertions)] 282 assert_ne!(set.len(), size_before_remove, "should have removed at least one element"); 283 284 // don't leave entries around with empty lists 285 if set.is_empty() { 286 self.[<$key _map>].remove($key); 287 } 288 } 289 )* 290 Some(removed) 291 } else { 292 None 293 } 294 } 295 296 /// Return an iterator over the elements in this container. 297 $vis fn values(&self) -> impl Iterator<Item=&$V> + '_ { 298 self.values.iter().map(|(_, v)| v) 299 } 300 301 /// Consume this container and return an iterator of its values. 302 $vis fn into_values(self) -> impl Iterator<Item=$V> { 303 self.values.into_iter().map(|(_, v)| v) 304 } 305 306 /// Try to insert `value`. 307 /// 308 /// Return `Error::NoKeys` if all the keys are optional, and `value` has no keys at all. 309 $vis fn try_insert(&mut self, value: $V) -> Result<(), $crate::n_key_list::Error> { 310 if self.capacity() > 32 && self.len() < self.capacity() / 4 { 311 // we have the opportunity to free up a fair amount of space; let's take it 312 self.compact() 313 } 314 315 let mut some_key_found = false; 316 317 $( 318 let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ); 319 some_key_found |= $key.is_some(); 320 )* 321 322 if !some_key_found { 323 // exit early before we add it to `values` 324 return Err($crate::n_key_list::Error::NoKeys); 325 } 326 327 let idx = self.values.insert(value); 328 let value = self.values.get(idx).expect("inconsistent state"); 329 330 $( 331 let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ); 332 if let Some($key) = $key { 333 let set = self.[<$key _map>].entry($key.to_owned()).or_default(); 334 set.push(idx); 335 336 // we don't want the list's capacity to grow unbounded, so in the (hopefully) rare 337 // case that the list grows large and then small again, try to free some of the 338 // memory 339 if set.capacity() > 64 && set.len() < set.capacity() / 4 { 340 set.shrink_to_fit(); 341 } 342 343 // TODO: would it be beneficial to aggressively shrink the list if `len()` is 344 // smaller than `inline_size()`? 345 } 346 )* 347 348 Ok(()) 349 } 350 351 /// See [`try_insert`](Self::try_insert). Panicks on errors. 352 $vis fn insert(&mut self, value: $V) { 353 self.try_insert(value) 354 .expect("tried to add a value with no key") 355 } 356 357 /// Return the number of elements in this container. 358 $vis fn len(&self) -> usize { 359 self.values.len() 360 } 361 362 /// Return `true` if there are no elements in this container. 363 $vis fn is_empty(&self) -> bool { 364 let is_empty = self.len() == 0; 365 366 #[cfg(debug_assertions)] 367 if is_empty { 368 $(assert!(self.[<$key _map>].is_empty());)* 369 } 370 371 is_empty 372 } 373 374 /// Return the number of elements for which this container has allocated storage. 375 $vis fn capacity(&self) -> usize { 376 self.values.capacity() 377 } 378 379 /// Remove every element that does not satisfy the predicate `pred`. 380 $vis fn retain<F>(&mut self, mut pred: F) 381 where 382 F: FnMut(&$V) -> bool, 383 { 384 for idx in 0..self.values.capacity() { 385 if self.values.get(idx).map(&mut pred) == Some(false) { 386 self.remove_at(idx); 387 } 388 } 389 } 390 391 /// An empty iterator. 392 /// 393 /// **NOTE:** This function is weird and will be removed in the future. We can fix this once 394 /// we support a minimum rust version of 1.79. 395 // TODO: The problem is that we need to assign `values` some value. In rust 1.79 we can just 396 // use a constant expression, but without constant expressions, there's no way to get a 397 // reference to a `Slab` with the generic types of `$V`. Once we support a minimum rust 398 // version of 1.79, remove this function and uncomment the `Default` impl for the iterator 399 // below. 400 #[deprecated] 401 $vis fn empty_iterator(&self) -> [<$mapname Iter>] <'_, $V> { 402 [<$mapname Iter>] { 403 iter: [].iter(), 404 values: &self.values, 405 } 406 } 407 408 /// Re-index all the values in this map, so that the map can use a more compact 409 /// representation. 410 /// 411 /// This should be done infrequently; it's expensive. 412 fn compact(&mut self) { 413 let old_value = std::mem::replace(self, Self::with_capacity(self.len())); 414 for item in old_value.into_values() { 415 self.insert(item); 416 } 417 } 418 419 /// Assert that this list appears to be in an internally consistent state. 420 /// 421 /// This method can be very expensive, and it should never fail unless your code has a bug. 422 /// 423 /// # Panics 424 /// 425 /// Panics if it finds bugs in this object, or constraint violations in its elements. See 426 /// the (type documentation)[Self#Requirements] for a list of constraints. 427 // it would be nice to run this after every operation that mutates internal state in debug 428 // builds, but this function is way too slow for that 429 fn check_consistency(&self) { 430 // ensure each value is in exactly the correct maps 431 for (idx, value) in &self.values { 432 $( 433 let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ); 434 if let Some($key) = $key { 435 // check that it exists in the set that it should be in 436 let set = self.[<$key _map>].get($key).expect("inconsistent state"); 437 assert!(set.contains(&idx)); 438 // check that it does not exist in any set that it should not be in 439 for (_key, set) in self.[<$key _map>].iter().filter(|(key, _)| *key != $key) { 440 assert!(!set.contains(&idx)); 441 } 442 } else { 443 // check that it does not exist in any set 444 for set in self.[<$key _map>].values() { 445 assert!(!set.contains(&idx)); 446 } 447 } 448 )* 449 } 450 451 $( 452 for set in self.[<$key _map>].values() { 453 // ensure no sets have dangling idxs 454 for idx in set { 455 assert!(self.values.contains(*idx)); 456 } 457 458 // ensure no sets have duplicate idxs 459 let mut set_iter = set.iter(); 460 while let Some(idx) = set_iter.next() { 461 assert!(!set_iter.clone().any(|x| x == idx)); 462 } 463 464 // ensure no sets are empty 465 assert!(!set.is_empty()); 466 } 467 )* 468 469 // ensure that if a value is in a key's map, then the value really has that key 470 $( 471 for (key, set) in &self.[<$key _map>] { 472 for idx in set { 473 let value = self.values.get(*idx).expect("inconsistent state"); 474 let $key = $crate::n_key_list!( @access(value, ($($($flag)+)?) $key : $KEY $({$($source)+})?) ); 475 let $key = $key.expect("inconsistent state"); 476 assert!(key == $key); 477 } 478 } 479 )* 480 } 481 } 482 483 impl $(<$($G)*>)? Default for $mapname $(<$($P)*>)? 484 where 485 $( $KEY : std::hash::Hash + Eq + Clone , )+ 486 $($($constr)+)? 487 { 488 fn default() -> Self { 489 $mapname::new() 490 } 491 } 492 493 impl $(<$($G)*>)? std::iter::FromIterator<$V> for $mapname $(<$($P)*>)? 494 where 495 $( $KEY : std::hash::Hash + Eq + Clone , )* 496 $($($constr)+)? 497 { 498 fn from_iter<IntoIter_>(iter: IntoIter_) -> Self 499 where 500 IntoIter_: std::iter::IntoIterator<Item = $V>, 501 { 502 let iter = iter.into_iter(); 503 let mut list = Self::with_capacity(iter.size_hint().0); 504 for value in iter { 505 list.insert(value); 506 } 507 list 508 } 509 } 510 511 #[doc = "An iterator for [`" $mapname "`](" $mapname ")."] 512 $vis struct [<$mapname Iter>] <'a, T> { 513 iter: std::slice::Iter<'a, usize>, 514 values: &'a $crate::n_key_list::deps::Slab<T>, 515 } 516 517 impl<'a, T> std::iter::Iterator for [<$mapname Iter>] <'a, T> { 518 type Item = &'a T; 519 520 fn next(&mut self) -> std::option::Option<Self::Item> { 521 self.iter.next().map(|idx| self.values.get(*idx).expect("inconsistent state")) 522 } 523 524 #[inline] 525 fn size_hint(&self) -> (usize, std::option::Option<usize>) { 526 self.iter.size_hint() 527 } 528 } 529 530 impl<'a, T> std::iter::ExactSizeIterator for [<$mapname Iter>] <'a, T> 531 where 532 // no harm in specifying it here, even though it should always be true 533 std::slice::Iter<'a, usize>: std::iter::ExactSizeIterator, 534 { 535 #[inline] 536 fn len(&self) -> usize { 537 self.iter.len() 538 } 539 } 540 541 // TODO: see comments on 'empty_iterator' above 542 /* 543 impl<'a, T> std::default::Default for [<$mapname Iter>] <'a, T> { 544 fn default() -> Self { 545 [<$mapname Iter>] { 546 iter: [].iter(), 547 values: const { &$crate::n_key_list::deps::Slab::new() }, 548 } 549 } 550 } 551 */ 552 } 553 }; 554 555 // Helper: Generate an expression to access a specific key and return an `Option<&TYPE>` for that 556 // key. This is the part of the macro that parses key descriptions. 557 558 { @access($ex:expr, (Option) $key:ident : $t:ty ) } => { 559 $ex.key() 560 }; 561 { @access($ex:expr, () $key:ident : $t:ty) } => { 562 Some($ex.key()) 563 }; 564 { @access($ex:expr, (Option) $key:ident : $t:ty { . $field:tt } ) } => { 565 $ex.$field.as_ref() 566 }; 567 { @access($ex:expr, () $key:ident : $t:ty { . $field:tt } ) } => { 568 Some(&$ex.$field) 569 }; 570 { @access($ex:expr, (Option) $key:ident : $t:ty { $func:ident () } ) } => { 571 $ex.$func() 572 }; 573 { @access($ex:expr, () $key:ident : $t:ty { $func:ident () } ) } => { 574 Some($ex.$func()) 575 }; 576 } 577 578 /// An error returned from an operation on an [`n_key_list`]. 579 #[derive(Clone, Debug, thiserror::Error)] 580 #[non_exhaustive] 581 pub enum Error { 582 /// We tried to insert a value into a set where all keys were optional, but every key on that 583 /// value was `None`. 584 #[error("Tried to insert a value with no keys")] 585 NoKeys, 586 } 587 588 #[cfg(test)] 589 mod test { 590 // @@ begin test lint list maintained by maint/add_warning @@ 591 #![allow(clippy::bool_assert_comparison)] 592 #![allow(clippy::clone_on_copy)] 593 #![allow(clippy::dbg_macro)] 594 #![allow(clippy::mixed_attributes_style)] 595 #![allow(clippy::print_stderr)] 596 #![allow(clippy::print_stdout)] 597 #![allow(clippy::single_char_pattern)] 598 #![allow(clippy::unwrap_used)] 599 #![allow(clippy::unchecked_duration_subtraction)] 600 #![allow(clippy::useless_vec)] 601 #![allow(clippy::needless_pass_by_value)] 602 //! <!-- @@ end test lint list maintained by maint/add_warning @@ --> 603 604 fn sort<T: std::cmp::Ord>(i: impl Iterator<Item = T>) -> Vec<T> { 605 let mut v: Vec<_> = i.collect(); 606 v.sort(); 607 v 608 } 609 610 n_key_list! { 611 #[derive(Clone, Debug)] 612 struct Tuple2List<A,B> for (A,B) { 613 first: A { .0 }, 614 second: B { .1 }, 615 } 616 } 617 618 #[test] 619 #[allow(clippy::cognitive_complexity)] 620 fn basic() { 621 let mut list = Tuple2List::new(); 622 assert!(list.is_empty()); 623 624 // add a single element and do some sanity checks 625 list.insert((0_u32, 99_u16)); 626 assert_eq!(list.len(), 1); 627 assert_eq!(list.contains_first(&0), true); 628 assert_eq!(list.contains_second(&99), true); 629 assert_eq!(list.contains_first(&99), false); 630 assert_eq!(list.contains_second(&0), false); 631 assert_eq!(sort(list.by_first(&0)), [&(0, 99)]); 632 assert_eq!(sort(list.by_second(&99)), [&(0, 99)]); 633 assert_eq!(list.by_first(&99).len(), 0); 634 assert_eq!(list.by_second(&0).len(), 0); 635 list.check_consistency(); 636 637 // lookup by a key that has never existed in the map 638 assert_eq!(list.by_first(&1000000).len(), 0); 639 640 // inserting the same element again should add it to the list 641 assert_eq!(list.len(), 1); 642 list.insert((0_u32, 99_u16)); 643 assert_eq!(list.len(), 2); 644 list.check_consistency(); 645 646 // add two new entries 647 list.insert((12, 34)); 648 list.insert((0, 34)); 649 assert_eq!(list.len(), 4); 650 assert!(list.capacity() >= 4); 651 assert_eq!(sort(list.by_first(&0)), [&(0, 34), &(0, 99), &(0, 99)]); 652 assert_eq!(sort(list.by_first(&12)), [&(12, 34)]); 653 list.check_consistency(); 654 655 // remove some elements 656 assert_eq!( 657 list.remove_by_first(&0, |(_, b)| *b == 99), 658 vec![(0, 99), (0, 99)] 659 ); 660 assert_eq!(list.remove_by_first(&0, |_| true), vec![(0, 34)]); 661 assert_eq!(list.len(), 1); 662 list.check_consistency(); 663 664 // test adding an element again 665 assert_eq!(sort(list.by_first(&12)), [&(12, 34)]); 666 list.insert((12, 123)); 667 assert_eq!(list.len(), 2); 668 assert_eq!(sort(list.by_first(&12)), [&(12, 34), &(12, 123)]); 669 assert_eq!(sort(list.by_second(&34)), [&(12, 34)]); 670 assert_eq!(sort(list.by_second(&123)), [&(12, 123)]); 671 list.check_consistency(); 672 673 // test iterators 674 list.insert((56, 78)); 675 assert_eq!(sort(list.values()), [&(12, 34), &(12, 123), &(56, 78)]); 676 assert_eq!(sort(list.into_values()), [(12, 34), (12, 123), (56, 78)]); 677 } 678 679 #[test] 680 fn retain_and_compact() { 681 let mut list: Tuple2List<String, String> = (1..=1000) 682 .map(|idx| (format!("A={}", idx), format!("B={}", idx))) 683 .collect(); 684 685 assert_eq!(list.len(), 1000); 686 let cap_orig = list.capacity(); 687 assert!(cap_orig >= list.len()); 688 list.check_consistency(); 689 690 // retain only the values whose first key is 3 characters long; that's 9 values out of 1000 691 list.retain(|(a, _)| a.len() <= 3); 692 assert_eq!(list.len(), 9); 693 // we don't shrink till we next insert 694 assert_eq!(list.capacity(), cap_orig); 695 list.check_consistency(); 696 697 // insert should cause the list to shrink 698 list.insert(("A=0".to_string(), "B=0".to_string())); 699 assert!(list.capacity() < cap_orig); 700 assert_eq!(list.len(), 10); 701 for idx in 0..=9 { 702 assert!(list.contains_first(&format!("A={}", idx))); 703 } 704 list.check_consistency(); 705 } 706 707 n_key_list! { 708 #[derive(Clone, Debug)] 709 struct AllOptional<A,B> for (Option<A>,Option<B>) { 710 (Option) first: A { .0 }, 711 (Option) second: B { .1 }, 712 } 713 } 714 715 #[test] 716 fn optional() { 717 let mut list = AllOptional::<u8, u8>::new(); 718 719 // should be able to insert values with at least one key 720 list.insert((Some(1), Some(2))); 721 list.insert((None, Some(2))); 722 list.insert((Some(1), None)); 723 list.check_consistency(); 724 725 assert_eq!( 726 sort(list.by_first(&1)), 727 [&(Some(1), None), &(Some(1), Some(2))], 728 ); 729 730 // check that inserting a value with no keys results in an error 731 assert!(matches!( 732 list.try_insert((None, None)), 733 Err(super::Error::NoKeys), 734 )); 735 } 736 737 #[allow(dead_code)] 738 struct Weekday { 739 dow: u8, 740 name: &'static str, 741 lucky_number: Option<u16>, 742 } 743 #[allow(dead_code)] 744 impl Weekday { 745 fn dow(&self) -> &u8 { 746 &self.dow 747 } 748 fn name(&self) -> &str { 749 self.name 750 } 751 fn lucky_number(&self) -> Option<&u16> { 752 self.lucky_number.as_ref() 753 } 754 } 755 n_key_list! { 756 struct WeekdaySet for Weekday { 757 idx: u8 { dow() }, 758 (Option) lucky: u16 { lucky_number() }, 759 name: String { name() } 760 } 761 } 762 763 n_key_list! { 764 struct['a] ArrayMap['a] for (String, [&'a u32;10]) { 765 name: String { .0 } 766 } 767 } 768 769 n_key_list! { 770 struct['a, const N:usize] ArrayMap2['a, N] for (String, [&'a u32;N]) { 771 name: String { .0 } 772 } 773 } 774 }