1 // This file is Copyright its original authors, visible in version control
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
10 use lightning::util::indexed_map::{IndexedMap, self};
11 use std::collections::{BTreeMap, btree_map};
12 use hashbrown::HashSet;
14 use crate::utils::test_logger;
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());
20 let mut btree_clone = btree.clone();
21 assert!(btree_clone == *btree);
22 let mut indexed_clone = indexed.clone();
23 assert!(indexed_clone == *indexed);
26 assert_eq!(btree.contains_key(&k), indexed.contains_key(&k));
27 assert_eq!(btree.get(&k), indexed.get(&k));
29 let btree_entry = btree_clone.entry(k);
30 let indexed_entry = indexed_clone.entry(k);
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());
38 btree_map::Entry::Vacant(_) => {
39 if let indexed_map::Entry::Vacant(_) = indexed_entry {
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);
52 let b_v = btree_iter.next();
53 let i_v = indexed_iter.next();
55 if b_v.is_none() { break; }
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));
64 assert_eq!(key_set.len(), btree.len());
67 for (k, v) in indexed.unordered_iter() {
68 assert!(key_set.insert(*k));
69 assert_eq!(btree.get(k).unwrap(), v);
71 assert_eq!(key_set.len(), btree.len());
74 for (k, v) in indexed_clone.unordered_iter_mut() {
75 assert!(key_set.insert(*k));
76 assert_eq!(btree.get(k).unwrap(), v);
78 assert_eq!(key_set.len(), btree.len());
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();
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);
94 check_eq(&btree, &indexed);
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() {
100 *btree.get_mut(k).unwrap() = *k;
102 check_eq(&btree, &indexed);
105 match btree.entry(k) {
106 btree_map::Entry::Occupied(mut bo) => {
107 if let indexed_map::Entry::Occupied(mut io) = indexed.entry(k) {
109 *io.get_mut() ^= 0xff;
110 *bo.get_mut() ^= 0xff;
112 *io.into_mut() ^= 0xff;
113 *bo.get_mut() ^= 0xff;
115 assert_eq!(bo.remove_entry(), io.remove_entry());
119 btree_map::Entry::Vacant(bv) => {
120 if let indexed_map::Entry::Vacant(iv) = indexed.entry(k) {
127 check_eq(&btree, &indexed);
130 pub fn indexedmap_test<Out: test_logger::Output>(data: &[u8], _out: Out) {
135 pub extern "C" fn indexedmap_run(data: *const u8, datalen: usize) {
136 do_test(unsafe { std::slice::from_raw_parts(data, datalen) });