src/vector_clock.rs

   1 use rustc_data_structures::fx::FxHashMap;
   2 use rustc_index::vec::Idx;
   3 use smallvec::SmallVec;
   4 use std::{
   5     cmp::Ordering,
   6     convert::TryFrom,
   7     fmt::{self, Debug},
   8     mem,
   9     ops::Index,
  10 };
  11
  12 /// A vector clock index, this is associated with a thread id
  13 /// but in some cases one vector index may be shared with
  14 /// multiple thread ids id it safe to do so.
  15 #[derive(Clone, Copy, Debug, PartialOrd, Ord, PartialEq, Eq, Hash)]
  16 pub struct VectorIdx(u32);
  17
  18 impl VectorIdx {
  19     #[inline(always)]
  20     pub fn to_u32(self) -> u32 {
  21         self.0
  22     }
  23
  24     pub const MAX_INDEX: VectorIdx = VectorIdx(u32::MAX);
  25 }
  26
  27 impl Idx for VectorIdx {
  28     #[inline]
  29     fn new(idx: usize) -> Self {
  30         VectorIdx(u32::try_from(idx).unwrap())
  31     }
  32
  33     #[inline]
  34     fn index(self) -> usize {
  35         usize::try_from(self.0).unwrap()
  36     }
  37 }
  38
  39 impl From<u32> for VectorIdx {
  40     #[inline]
  41     fn from(id: u32) -> Self {
  42         Self(id)
  43     }
  44 }
  45
  46 /// A sparse mapping of vector index values to vector clocks, this
  47 /// is optimized for the common case with only one element stored
  48 /// inside the map.
  49 /// This is used to store the set of currently active release
  50 /// sequences at a given memory location, since RMW operations
  51 /// allow for multiple release sequences to be active at once
  52 /// and to be collapsed back to one active release sequence
  53 /// once a non RMW atomic store operation occurs.
  54 /// An all zero vector is considered to be equal to no
  55 /// element stored internally since it will never be
  56 /// stored and has no meaning as a release sequence
  57 /// vector clock.
  58 #[derive(Clone)]
  59 pub struct VSmallClockMap(VSmallClockMapInner);
  60
  61 #[derive(Clone)]
  62 enum VSmallClockMapInner {
  63     /// Zero or 1 vector elements, common
  64     /// case for the sparse set.
  65     /// The all zero vector clock is treated
  66     /// as equal to the empty element.
  67     Small(VectorIdx, VClock),
  68
  69     /// Hash-map of vector clocks.
  70     Large(FxHashMap<VectorIdx, VClock>),
  71 }
  72
  73 impl VSmallClockMap {
  74     /// Remove all clock vectors from the map, setting them
  75     /// to the zero vector.
  76     pub fn clear(&mut self) {
  77         match &mut self.0 {
  78             VSmallClockMapInner::Small(_, clock) => clock.set_zero_vector(),
  79             VSmallClockMapInner::Large(hash_map) => {
  80                 hash_map.clear();
  81             }
  82         }
  83     }
  84
  85     /// Remove all clock vectors except for the clock vector
  86     /// stored at the given index, which is retained.
  87     pub fn retain_index(&mut self, index: VectorIdx) {
  88         match &mut self.0 {
  89             VSmallClockMapInner::Small(small_idx, clock) => {
  90                 if index != *small_idx {
  91                     // The zero-vector is considered to equal
  92                     // the empty element.
  93                     clock.set_zero_vector()
  94                 }
  95             }
  96             VSmallClockMapInner::Large(hash_map) => {
  97                 let value = hash_map.remove(&index).unwrap_or_default();
  98                 self.0 = VSmallClockMapInner::Small(index, value);
  99             }
 100         }
 101     }
 102
 103     /// Insert the vector clock into the associated vector
 104     /// index.
 105     pub fn insert(&mut self, index: VectorIdx, clock: &VClock) {
 106         match &mut self.0 {
 107             VSmallClockMapInner::Small(small_idx, small_clock) => {
 108                 if small_clock.is_zero_vector() {
 109                     *small_idx = index;
 110                     small_clock.clone_from(clock);
 111                 } else if !clock.is_zero_vector() {
 112                     // Convert to using the hash-map representation.
 113                     let mut hash_map = FxHashMap::default();
 114                     hash_map.insert(*small_idx, mem::take(small_clock));
 115                     hash_map.insert(index, clock.clone());
 116                     self.0 = VSmallClockMapInner::Large(hash_map);
 117                 }
 118             }
 119             VSmallClockMapInner::Large(hash_map) =>
 120                 if !clock.is_zero_vector() {
 121                     hash_map.insert(index, clock.clone());
 122                 },
 123         }
 124     }
 125
 126     /// Try to load the vector clock associated with the current
 127     ///  vector index.
 128     pub fn get(&self, index: VectorIdx) -> Option<&VClock> {
 129         match &self.0 {
 130             VSmallClockMapInner::Small(small_idx, small_clock) => {
 131                 if *small_idx == index && !small_clock.is_zero_vector() {
 132                     Some(small_clock)
 133                 } else {
 134                     None
 135                 }
 136             }
 137             VSmallClockMapInner::Large(hash_map) => hash_map.get(&index),
 138         }
 139     }
 140 }
 141
 142 impl Default for VSmallClockMap {
 143     #[inline]
 144     fn default() -> Self {
 145         VSmallClockMap(VSmallClockMapInner::Small(VectorIdx::new(0), VClock::default()))
 146     }
 147 }
 148
 149 impl Debug for VSmallClockMap {
 150     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
 151         // Print the contents of the small vector clock set as the map
 152         // of vector index to vector clock that they represent.
 153         let mut map = f.debug_map();
 154         match &self.0 {
 155             VSmallClockMapInner::Small(small_idx, small_clock) =>
 156                 if !small_clock.is_zero_vector() {
 157                     map.entry(&small_idx, &small_clock);
 158                 },
 159             VSmallClockMapInner::Large(hash_map) =>
 160                 for (idx, elem) in hash_map.iter() {
 161                     map.entry(idx, elem);
 162                 },
 163         }
 164         map.finish()
 165     }
 166 }
 167
 168 impl PartialEq for VSmallClockMap {
 169     fn eq(&self, other: &Self) -> bool {
 170         use VSmallClockMapInner::*;
 171         match (&self.0, &other.0) {
 172             (Small(i1, c1), Small(i2, c2)) => {
 173                 if c1.is_zero_vector() {
 174                     // Either they are both zero or they are non-equal
 175                     c2.is_zero_vector()
 176                 } else {
 177                     // At least one is non-zero, so the full comparison is correct
 178                     i1 == i2 && c1 == c2
 179                 }
 180             }
 181             (Small(idx, clock), Large(hash_map)) | (Large(hash_map), Small(idx, clock)) => {
 182                 if hash_map.len() == 0 {
 183                     // Equal to the empty hash-map
 184                     clock.is_zero_vector()
 185                 } else if hash_map.len() == 1 {
 186                     // Equal to the hash-map with one element
 187                     let (hash_idx, hash_clock) = hash_map.iter().next().unwrap();
 188                     hash_idx == idx && hash_clock == clock
 189                 } else {
 190                     false
 191                 }
 192             }
 193             (Large(map1), Large(map2)) => map1 == map2,
 194         }
 195     }
 196 }
 197
 198 impl Eq for VSmallClockMap {}
 199
 200 /// The size of the vector-clock to store inline
 201 /// clock vectors larger than this will be stored on the heap
 202 const SMALL_VECTOR: usize = 4;
 203
 204 /// The type of the time-stamps recorded in the data-race detector
 205 /// set to a type of unsigned integer
 206 pub type VTimestamp = u32;
 207
 208 /// A vector clock for detecting data-races, this is conceptually
 209 /// a map from a vector index (and thus a thread id) to a timestamp.
 210 /// The compare operations require that the invariant that the last
 211 /// element in the internal timestamp slice must not be a 0, hence
 212 /// all zero vector clocks are always represented by the empty slice;
 213 /// and allows for the implementation of compare operations to short
 214 /// circuit the calculation and return the correct result faster,
 215 /// also this means that there is only one unique valid length
 216 /// for each set of vector clock values and hence the PartialEq
 217 //  and Eq derivations are correct.
 218 #[derive(PartialEq, Eq, Default, Debug)]
 219 pub struct VClock(SmallVec<[VTimestamp; SMALL_VECTOR]>);
 220
 221 impl VClock {
 222     /// Create a new vector-clock containing all zeros except
 223     /// for a value at the given index
 224     pub fn new_with_index(index: VectorIdx, timestamp: VTimestamp) -> VClock {
 225         let len = index.index() + 1;
 226         let mut vec = smallvec::smallvec![0; len];
 227         vec[index.index()] = timestamp;
 228         VClock(vec)
 229     }
 230
 231     /// Load the internal timestamp slice in the vector clock
 232     #[inline]
 233     pub fn as_slice(&self) -> &[VTimestamp] {
 234         self.0.as_slice()
 235     }
 236
 237     /// Get a mutable slice to the internal vector with minimum `min_len`
 238     /// elements, to preserve invariants this vector must modify
 239     /// the `min_len`-1 nth element to a non-zero value
 240     #[inline]
 241     fn get_mut_with_min_len(&mut self, min_len: usize) -> &mut [VTimestamp] {
 242         if self.0.len() < min_len {
 243             self.0.resize(min_len, 0);
 244         }
 245         assert!(self.0.len() >= min_len);
 246         self.0.as_mut_slice()
 247     }
 248
 249     /// Increment the vector clock at a known index
 250     /// this will panic if the vector index overflows
 251     #[inline]
 252     pub fn increment_index(&mut self, idx: VectorIdx) {
 253         let idx = idx.index();
 254         let mut_slice = self.get_mut_with_min_len(idx + 1);
 255         let idx_ref = &mut mut_slice[idx];
 256         *idx_ref = idx_ref.checked_add(1).expect("Vector clock overflow")
 257     }
 258
 259     // Join the two vector-clocks together, this
 260     // sets each vector-element to the maximum value
 261     // of that element in either of the two source elements.
 262     pub fn join(&mut self, other: &Self) {
 263         let rhs_slice = other.as_slice();
 264         let lhs_slice = self.get_mut_with_min_len(rhs_slice.len());
 265         for (l, &r) in lhs_slice.iter_mut().zip(rhs_slice.iter()) {
 266             *l = r.max(*l);
 267         }
 268     }
 269
 270     /// Set the element at the current index of the vector
 271     pub fn set_at_index(&mut self, other: &Self, idx: VectorIdx) {
 272         let idx = idx.index();
 273         let mut_slice = self.get_mut_with_min_len(idx + 1);
 274         let slice = other.as_slice();
 275         mut_slice[idx] = slice[idx];
 276     }
 277
 278     /// Set the vector to the all-zero vector
 279     #[inline]
 280     pub fn set_zero_vector(&mut self) {
 281         self.0.clear();
 282     }
 283
 284     /// Return if this vector is the all-zero vector
 285     pub fn is_zero_vector(&self) -> bool {
 286         self.0.is_empty()
 287     }
 288 }
 289
 290 impl Clone for VClock {
 291     fn clone(&self) -> Self {
 292         VClock(self.0.clone())
 293     }
 294
 295     // Optimized clone-from, can be removed
 296     // and replaced with a derive once a similar
 297     // optimization is inserted into SmallVec's
 298     // clone implementation.
 299     fn clone_from(&mut self, source: &Self) {
 300         let source_slice = source.as_slice();
 301         self.0.clear();
 302         self.0.extend_from_slice(source_slice);
 303     }
 304 }
 305
 306 impl PartialOrd for VClock {
 307     fn partial_cmp(&self, other: &VClock) -> Option<Ordering> {
 308         // Load the values as slices
 309         let lhs_slice = self.as_slice();
 310         let rhs_slice = other.as_slice();
 311
 312         // Iterate through the combined vector slice continuously updating
 313         // the value of `order` to the current comparison of the vector from
 314         // index 0 to the currently checked index.
 315         // An Equal ordering can be converted into Less or Greater ordering
 316         // on finding an element that is less than or greater than the other
 317         // but if one Greater and one Less element-wise comparison is found
 318         // then no ordering is possible and so directly return an ordering
 319         // of None.
 320         let mut iter = lhs_slice.iter().zip(rhs_slice.iter());
 321         let mut order = match iter.next() {
 322             Some((lhs, rhs)) => lhs.cmp(rhs),
 323             None => Ordering::Equal,
 324         };
 325         for (l, r) in iter {
 326             match order {
 327                 Ordering::Equal => order = l.cmp(r),
 328                 Ordering::Less =>
 329                     if l > r {
 330                         return None;
 331                     },
 332                 Ordering::Greater =>
 333                     if l < r {
 334                         return None;
 335                     },
 336             }
 337         }
 338
 339         // Now test if either left or right have trailing elements,
 340         // by the invariant the trailing elements have at least 1
 341         // non zero value, so no additional calculation is required
 342         // to determine the result of the PartialOrder.
 343         let l_len = lhs_slice.len();
 344         let r_len = rhs_slice.len();
 345         match l_len.cmp(&r_len) {
 346             // Equal means no additional elements: return current order
 347             Ordering::Equal => Some(order),
 348             // Right has at least 1 element > than the implicit 0,
 349             // so the only valid values are Ordering::Less or None.
 350             Ordering::Less => match order {
 351                 Ordering::Less | Ordering::Equal => Some(Ordering::Less),
 352                 Ordering::Greater => None,
 353             },
 354             // Left has at least 1 element > than the implicit 0,
 355             // so the only valid values are Ordering::Greater or None.
 356             Ordering::Greater => match order {
 357                 Ordering::Greater | Ordering::Equal => Some(Ordering::Greater),
 358                 Ordering::Less => None,
 359             },
 360         }
 361     }
 362
 363     fn lt(&self, other: &VClock) -> bool {
 364         // Load the values as slices
 365         let lhs_slice = self.as_slice();
 366         let rhs_slice = other.as_slice();
 367
 368         // If l_len > r_len then at least one element
 369         // in l_len is > than r_len, therefore the result
 370         // is either Some(Greater) or None, so return false
 371         // early.
 372         let l_len = lhs_slice.len();
 373         let r_len = rhs_slice.len();
 374         if l_len <= r_len {
 375             // If any elements on the left are greater than the right
 376             // then the result is None or Some(Greater), both of which
 377             // return false, the earlier test asserts that no elements in the
 378             // extended tail violate this assumption. Otherwise l <= r, finally
 379             // the case where the values are potentially equal needs to be considered
 380             // and false returned as well
 381             let mut equal = l_len == r_len;
 382             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 383                 if l > r {
 384                     return false;
 385                 } else if l < r {
 386                     equal = false;
 387                 }
 388             }
 389             !equal
 390         } else {
 391             false
 392         }
 393     }
 394
 395     fn le(&self, other: &VClock) -> bool {
 396         // Load the values as slices
 397         let lhs_slice = self.as_slice();
 398         let rhs_slice = other.as_slice();
 399
 400         // If l_len > r_len then at least one element
 401         // in l_len is > than r_len, therefore the result
 402         // is either Some(Greater) or None, so return false
 403         // early.
 404         let l_len = lhs_slice.len();
 405         let r_len = rhs_slice.len();
 406         if l_len <= r_len {
 407             // If any elements on the left are greater than the right
 408             // then the result is None or Some(Greater), both of which
 409             // return false, the earlier test asserts that no elements in the
 410             // extended tail violate this assumption. Otherwise l <= r
 411             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l > r)
 412         } else {
 413             false
 414         }
 415     }
 416
 417     fn gt(&self, other: &VClock) -> bool {
 418         // Load the values as slices
 419         let lhs_slice = self.as_slice();
 420         let rhs_slice = other.as_slice();
 421
 422         // If r_len > l_len then at least one element
 423         // in r_len is > than l_len, therefore the result
 424         // is either Some(Less) or None, so return false
 425         // early.
 426         let l_len = lhs_slice.len();
 427         let r_len = rhs_slice.len();
 428         if l_len >= r_len {
 429             // If any elements on the left are less than the right
 430             // then the result is None or Some(Less), both of which
 431             // return false, the earlier test asserts that no elements in the
 432             // extended tail violate this assumption. Otherwise l >=, finally
 433             // the case where the values are potentially equal needs to be considered
 434             // and false returned as well
 435             let mut equal = l_len == r_len;
 436             for (&l, &r) in lhs_slice.iter().zip(rhs_slice.iter()) {
 437                 if l < r {
 438                     return false;
 439                 } else if l > r {
 440                     equal = false;
 441                 }
 442             }
 443             !equal
 444         } else {
 445             false
 446         }
 447     }
 448
 449     fn ge(&self, other: &VClock) -> bool {
 450         // Load the values as slices
 451         let lhs_slice = self.as_slice();
 452         let rhs_slice = other.as_slice();
 453
 454         // If r_len > l_len then at least one element
 455         // in r_len is > than l_len, therefore the result
 456         // is either Some(Less) or None, so return false
 457         // early.
 458         let l_len = lhs_slice.len();
 459         let r_len = rhs_slice.len();
 460         if l_len >= r_len {
 461             // If any elements on the left are less than the right
 462             // then the result is None or Some(Less), both of which
 463             // return false, the earlier test asserts that no elements in the
 464             // extended tail violate this assumption. Otherwise l >= r
 465             !lhs_slice.iter().zip(rhs_slice.iter()).any(|(&l, &r)| l < r)
 466         } else {
 467             false
 468         }
 469     }
 470 }
 471
 472 impl Index<VectorIdx> for VClock {
 473     type Output = VTimestamp;
 474
 475     #[inline]
 476     fn index(&self, index: VectorIdx) -> &VTimestamp {
 477         self.as_slice().get(index.to_u32() as usize).unwrap_or(&0)
 478     }
 479 }
 480
 481 /// Test vector clock ordering operations
 482 ///  data-race detection is tested in the external
 483 ///  test suite
 484 #[cfg(test)]
 485 mod tests {
 486
 487     use super::{VClock, VSmallClockMap, VTimestamp, VectorIdx};
 488     use std::cmp::Ordering;
 489
 490     #[test]
 491     fn test_equal() {
 492         let mut c1 = VClock::default();
 493         let mut c2 = VClock::default();
 494         assert_eq!(c1, c2);
 495         c1.increment_index(VectorIdx(5));
 496         assert_ne!(c1, c2);
 497         c2.increment_index(VectorIdx(53));
 498         assert_ne!(c1, c2);
 499         c1.increment_index(VectorIdx(53));
 500         assert_ne!(c1, c2);
 501         c2.increment_index(VectorIdx(5));
 502         assert_eq!(c1, c2);
 503     }
 504
 505     #[test]
 506     fn test_partial_order() {
 507         // Small test
 508         assert_order(&[1], &[1], Some(Ordering::Equal));
 509         assert_order(&[1], &[2], Some(Ordering::Less));
 510         assert_order(&[2], &[1], Some(Ordering::Greater));
 511         assert_order(&[1], &[1, 2], Some(Ordering::Less));
 512         assert_order(&[2], &[1, 2], None);
 513
 514         // Misc tests
 515         assert_order(&[400], &[0, 1], None);
 516
 517         // Large test
 518         assert_order(
 519             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 520             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 521             Some(Ordering::Equal),
 522         );
 523         assert_order(
 524             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
 525             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 526             Some(Ordering::Less),
 527         );
 528         assert_order(
 529             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 530             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 531             Some(Ordering::Greater),
 532         );
 533         assert_order(
 534             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 11],
 535             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 536             None,
 537         );
 538         assert_order(
 539             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 540             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 0, 0],
 541             Some(Ordering::Less),
 542         );
 543         assert_order(
 544             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 9],
 545             &[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 1, 0],
 546             Some(Ordering::Less),
 547         );
 548     }
 549
 550     fn from_slice(mut slice: &[VTimestamp]) -> VClock {
 551         while let Some(0) = slice.last() {
 552             slice = &slice[..slice.len() - 1]
 553         }
 554         VClock(smallvec::SmallVec::from_slice(slice))
 555     }
 556
 557     fn assert_order(l: &[VTimestamp], r: &[VTimestamp], o: Option<Ordering>) {
 558         let l = from_slice(l);
 559         let r = from_slice(r);
 560
 561         //Test partial_cmp
 562         let compare = l.partial_cmp(&r);
 563         assert_eq!(compare, o, "Invalid comparison\n l: {:?}\n r: {:?}", l, r);
 564         let alt_compare = r.partial_cmp(&l);
 565         assert_eq!(
 566             alt_compare,
 567             o.map(Ordering::reverse),
 568             "Invalid alt comparison\n l: {:?}\n r: {:?}",
 569             l,
 570             r
 571         );
 572
 573         //Test operators with faster implementations
 574         assert_eq!(
 575             matches!(compare, Some(Ordering::Less)),
 576             l < r,
 577             "Invalid (<):\n l: {:?}\n r: {:?}",
 578             l,
 579             r
 580         );
 581         assert_eq!(
 582             matches!(compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 583             l <= r,
 584             "Invalid (<=):\n l: {:?}\n r: {:?}",
 585             l,
 586             r
 587         );
 588         assert_eq!(
 589             matches!(compare, Some(Ordering::Greater)),
 590             l > r,
 591             "Invalid (>):\n l: {:?}\n r: {:?}",
 592             l,
 593             r
 594         );
 595         assert_eq!(
 596             matches!(compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 597             l >= r,
 598             "Invalid (>=):\n l: {:?}\n r: {:?}",
 599             l,
 600             r
 601         );
 602         assert_eq!(
 603             matches!(alt_compare, Some(Ordering::Less)),
 604             r < l,
 605             "Invalid alt (<):\n l: {:?}\n r: {:?}",
 606             l,
 607             r
 608         );
 609         assert_eq!(
 610             matches!(alt_compare, Some(Ordering::Less) | Some(Ordering::Equal)),
 611             r <= l,
 612             "Invalid alt (<=):\n l: {:?}\n r: {:?}",
 613             l,
 614             r
 615         );
 616         assert_eq!(
 617             matches!(alt_compare, Some(Ordering::Greater)),
 618             r > l,
 619             "Invalid alt (>):\n l: {:?}\n r: {:?}",
 620             l,
 621             r
 622         );
 623         assert_eq!(
 624             matches!(alt_compare, Some(Ordering::Greater) | Some(Ordering::Equal)),
 625             r >= l,
 626             "Invalid alt (>=):\n l: {:?}\n r: {:?}",
 627             l,
 628             r
 629         );
 630     }
 631
 632     #[test]
 633     pub fn test_vclock_set() {
 634         let mut map = VSmallClockMap::default();
 635         let v1 = from_slice(&[3, 0, 1]);
 636         let v2 = from_slice(&[4, 2, 3]);
 637         let v3 = from_slice(&[4, 8, 3]);
 638         map.insert(VectorIdx(0), &v1);
 639         assert_eq!(map.get(VectorIdx(0)), Some(&v1));
 640         map.insert(VectorIdx(5), &v2);
 641         assert_eq!(map.get(VectorIdx(0)), Some(&v1));
 642         assert_eq!(map.get(VectorIdx(5)), Some(&v2));
 643         map.insert(VectorIdx(53), &v3);
 644         assert_eq!(map.get(VectorIdx(0)), Some(&v1));
 645         assert_eq!(map.get(VectorIdx(5)), Some(&v2));
 646         assert_eq!(map.get(VectorIdx(53)), Some(&v3));
 647         map.retain_index(VectorIdx(53));
 648         assert_eq!(map.get(VectorIdx(0)), None);
 649         assert_eq!(map.get(VectorIdx(5)), None);
 650         assert_eq!(map.get(VectorIdx(53)), Some(&v3));
 651         map.clear();
 652         assert_eq!(map.get(VectorIdx(0)), None);
 653         assert_eq!(map.get(VectorIdx(5)), None);
 654         assert_eq!(map.get(VectorIdx(53)), None);
 655         map.insert(VectorIdx(53), &v3);
 656         assert_eq!(map.get(VectorIdx(0)), None);
 657         assert_eq!(map.get(VectorIdx(5)), None);
 658         assert_eq!(map.get(VectorIdx(53)), Some(&v3));
 659     }
 660 }