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::hash_tables::*;
11 use lightning::util::indexed_map::{self, IndexedMap};
12 use std::collections::{btree_map, BTreeMap};
14 use crate::utils::test_logger;
16 use std::ops::{Bound, RangeBounds};
18 struct ExclLowerInclUpper(u8, u8);
19 impl RangeBounds<u8> for ExclLowerInclUpper {
20 fn start_bound(&self) -> Bound<&u8> {
21 Bound::Excluded(&self.0)
23 fn end_bound(&self) -> Bound<&u8> {
24 Bound::Included(&self.1)
27 struct ExclLowerExclUpper(u8, u8);
28 impl RangeBounds<u8> for ExclLowerExclUpper {
29 fn start_bound(&self) -> Bound<&u8> {
30 Bound::Excluded(&self.0)
32 fn end_bound(&self) -> Bound<&u8> {
33 Bound::Excluded(&self.1)
37 fn check_eq(btree: &BTreeMap<u8, u8>, mut indexed: IndexedMap<u8, u8>) {
38 assert_eq!(btree.len(), indexed.len());
39 assert_eq!(btree.is_empty(), indexed.is_empty());
41 let mut btree_clone = btree.clone();
42 assert!(btree_clone == *btree);
43 let mut indexed_clone = indexed.clone();
44 assert!(indexed_clone == indexed);
47 assert_eq!(btree.contains_key(&k), indexed.contains_key(&k));
48 assert_eq!(btree.get(&k), indexed.get(&k));
50 let btree_entry = btree_clone.entry(k);
51 let indexed_entry = indexed_clone.entry(k);
53 btree_map::Entry::Occupied(mut bo) => {
54 if let indexed_map::Entry::Occupied(mut io) = indexed_entry {
55 assert_eq!(bo.get(), io.get());
56 assert_eq!(bo.get_mut(), io.get_mut());
61 btree_map::Entry::Vacant(_) => {
62 if let indexed_map::Entry::Vacant(_) = indexed_entry {
70 const STRIDE: u8 = 16;
71 for range_type in 0..4 {
72 for k in 0..=255 / STRIDE {
73 let lower_bound = k * STRIDE;
74 let upper_bound = lower_bound + (STRIDE - 1);
78 0 => $map.range(lower_bound..upper_bound),
79 1 => $map.range(lower_bound..=upper_bound),
80 2 => $map.range(ExclLowerInclUpper(lower_bound, upper_bound)),
81 3 => $map.range(ExclLowerExclUpper(lower_bound, upper_bound)),
86 let mut btree_iter = range!(btree);
87 let mut indexed_iter = range!(indexed);
89 let b_v = btree_iter.next();
90 let i_v = indexed_iter.next();
99 let mut key_set = hash_map_with_capacity(1024);
100 for k in indexed.unordered_keys() {
101 assert!(key_set.insert(*k, ()).is_none());
102 assert!(btree.contains_key(k));
104 assert_eq!(key_set.len(), btree.len());
107 for (k, v) in indexed.unordered_iter() {
108 assert!(key_set.insert(*k, ()).is_none());
109 assert_eq!(btree.get(k).unwrap(), v);
111 assert_eq!(key_set.len(), btree.len());
114 for (k, v) in indexed_clone.unordered_iter_mut() {
115 assert!(key_set.insert(*k, ()).is_none());
116 assert_eq!(btree.get(k).unwrap(), v);
118 assert_eq!(key_set.len(), btree.len());
122 pub fn do_test(data: &[u8]) {
123 if data.len() % 2 != 0 {
126 let mut btree = BTreeMap::new();
127 let mut indexed = IndexedMap::new();
129 // Read in k-v pairs from the input and insert them into the maps then check that the maps are
130 // equivalent in every way we can read them.
131 for tuple in data.windows(2) {
132 let prev_value_b = btree.insert(tuple[0], tuple[1]);
133 let prev_value_i = indexed.insert(tuple[0], tuple[1]);
134 assert_eq!(prev_value_b, prev_value_i);
136 check_eq(&btree, indexed.clone());
138 // Now, modify the maps in all the ways we have to do so, checking that the maps remain
139 // equivalent as we go.
140 for (k, v) in indexed.unordered_iter_mut() {
142 *btree.get_mut(k).unwrap() = *k;
144 check_eq(&btree, indexed.clone());
147 match btree.entry(k) {
148 btree_map::Entry::Occupied(mut bo) => {
149 if let indexed_map::Entry::Occupied(mut io) = indexed.entry(k) {
151 *io.get_mut() ^= 0xff;
152 *bo.get_mut() ^= 0xff;
154 *io.into_mut() ^= 0xff;
155 *bo.get_mut() ^= 0xff;
157 assert_eq!(bo.remove_entry(), io.remove_entry());
163 btree_map::Entry::Vacant(bv) => {
164 if let indexed_map::Entry::Vacant(iv) = indexed.entry(k) {
173 check_eq(&btree, indexed);
176 pub fn indexedmap_test<Out: test_logger::Output>(data: &[u8], _out: Out) {
181 pub extern "C" fn indexedmap_run(data: *const u8, datalen: usize) {
182 do_test(unsafe { std::slice::from_raw_parts(data, datalen) });