_ Git - rust-lightning/blob - fuzz/src/indexedmap.rs

   1 // This file is Copyright its original authors, visible in version control
   2 // history.
   3 //
   4 // This file is licensed under the Apache License, Version 2.0 <LICENSE-APACHE
   5 // or http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   6 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your option.
   7 // You may not use this file except in accordance with one or both of these
   8 // licenses.
   9
  10 use lightning::util::indexed_map::{IndexedMap, self};
  11 use std::collections::{BTreeMap, btree_map};
  12 use hashbrown::HashSet;
  13
  14 use crate::utils::test_logger;
  15
  16 fn check_eq(btree: &BTreeMap<u8, u8>, indexed: &IndexedMap<u8, u8>) {
  17         assert_eq!(btree.len(), indexed.len());
  18         assert_eq!(btree.is_empty(), indexed.is_empty());
  19
  20         let mut btree_clone = btree.clone();
  21         assert!(btree_clone == *btree);
  22         let mut indexed_clone = indexed.clone();
  23         assert!(indexed_clone == *indexed);
  24
  25         for k in 0..=255 {
  26                 assert_eq!(btree.contains_key(&k), indexed.contains_key(&k));
  27                 assert_eq!(btree.get(&k), indexed.get(&k));
  28
  29                 let btree_entry = btree_clone.entry(k);
  30                 let indexed_entry = indexed_clone.entry(k);
  31                 match btree_entry {
  32                         btree_map::Entry::Occupied(mut bo) => {
  33                                 if let indexed_map::Entry::Occupied(mut io) = indexed_entry {
  34                                         assert_eq!(bo.get(), io.get());
  35                                         assert_eq!(bo.get_mut(), io.get_mut());
  36                                 } else { panic!(); }
  37                         },
  38                         btree_map::Entry::Vacant(_) => {
  39                                 if let indexed_map::Entry::Vacant(_) = indexed_entry {
  40                                 } else { panic!(); }
  41                         }
  42                 }
  43         }
  44
  45         const STRIDE: u8 = 16;
  46         for k in 0..=255/STRIDE {
  47                 let lower_bound = k * STRIDE;
  48                 let upper_bound = lower_bound + (STRIDE - 1);
  49                 let mut btree_iter = btree.range(lower_bound..=upper_bound);
  50                 let mut indexed_iter = indexed.range(lower_bound..=upper_bound);
  51                 loop {
  52                         let b_v = btree_iter.next();
  53                         let i_v = indexed_iter.next();
  54                         assert_eq!(b_v, i_v);
  55                         if b_v.is_none() { break; }
  56                 }
  57         }
  58
  59         let mut key_set = HashSet::with_capacity(256);
  60         for k in indexed.unordered_keys() {
  61                 assert!(key_set.insert(*k));
  62                 assert!(btree.contains_key(k));
  63         }
  64         assert_eq!(key_set.len(), btree.len());
  65
  66         key_set.clear();
  67         for (k, v) in indexed.unordered_iter() {
  68                 assert!(key_set.insert(*k));
  69                 assert_eq!(btree.get(k).unwrap(), v);
  70         }
  71         assert_eq!(key_set.len(), btree.len());
  72
  73         key_set.clear();
  74         for (k, v) in indexed_clone.unordered_iter_mut() {
  75                 assert!(key_set.insert(*k));
  76                 assert_eq!(btree.get(k).unwrap(), v);
  77         }
  78         assert_eq!(key_set.len(), btree.len());
  79 }
  80
  81 #[inline]
  82 pub fn do_test(data: &[u8]) {
  83         if data.len() % 2 != 0 { return; }
  84         let mut btree = BTreeMap::new();
  85         let mut indexed = IndexedMap::new();
  86
  87         // Read in k-v pairs from the input and insert them into the maps then check that the maps are
  88         // equivalent in every way we can read them.
  89         for tuple in data.windows(2) {
  90                 let prev_value_b = btree.insert(tuple[0], tuple[1]);
  91                 let prev_value_i = indexed.insert(tuple[0], tuple[1]);
  92                 assert_eq!(prev_value_b, prev_value_i);
  93         }
  94         check_eq(&btree, &indexed);
  95
  96         // Now, modify the maps in all the ways we have to do so, checking that the maps remain
  97         // equivalent as we go.
  98         for (k, v) in indexed.unordered_iter_mut() {
  99                 *v = *k;
 100                 *btree.get_mut(k).unwrap() = *k;
 101         }
 102         check_eq(&btree, &indexed);
 103
 104         for k in 0..=255 {
 105                 match btree.entry(k) {
 106                         btree_map::Entry::Occupied(mut bo) => {
 107                                 if let indexed_map::Entry::Occupied(mut io) = indexed.entry(k) {
 108                                         if k < 64 {
 109                                                 *io.get_mut() ^= 0xff;
 110                                                 *bo.get_mut() ^= 0xff;
 111                                         } else if k < 128 {
 112                                                 *io.into_mut() ^= 0xff;
 113                                                 *bo.get_mut() ^= 0xff;
 114                                         } else {
 115                                                 assert_eq!(bo.remove_entry(), io.remove_entry());
 116                                         }
 117                                 } else { panic!(); }
 118                         },
 119                         btree_map::Entry::Vacant(bv) => {
 120                                 if let indexed_map::Entry::Vacant(iv) = indexed.entry(k) {
 121                                         bv.insert(k);
 122                                         iv.insert(k);
 123                                 } else { panic!(); }
 124                         },
 125                 }
 126         }
 127         check_eq(&btree, &indexed);
 128 }
 129
 130 pub fn indexedmap_test<Out: test_logger::Output>(data: &[u8], _out: Out) {
 131         do_test(data);
 132 }
 133
 134 #[no_mangle]
 135 pub extern "C" fn indexedmap_run(data: *const u8, datalen: usize) {
 136         do_test(unsafe { std::slice::from_raw_parts(data, datalen) });
 137 }