summaryrefslogtreecommitdiffstats
path: root/compiler/rustc_index/src/bit_set/tests.rs
diff options
context:
space:
mode:
Diffstat (limited to 'compiler/rustc_index/src/bit_set/tests.rs')
-rw-r--r--compiler/rustc_index/src/bit_set/tests.rs873
1 files changed, 873 insertions, 0 deletions
diff --git a/compiler/rustc_index/src/bit_set/tests.rs b/compiler/rustc_index/src/bit_set/tests.rs
new file mode 100644
index 000000000..351d62fee
--- /dev/null
+++ b/compiler/rustc_index/src/bit_set/tests.rs
@@ -0,0 +1,873 @@
+use super::*;
+
+extern crate test;
+use std::hint::black_box;
+use test::Bencher;
+
+#[test]
+fn test_new_filled() {
+ for i in 0..128 {
+ let idx_buf = BitSet::new_filled(i);
+ let elems: Vec<usize> = idx_buf.iter().collect();
+ let expected: Vec<usize> = (0..i).collect();
+ assert_eq!(elems, expected);
+ }
+}
+
+#[test]
+fn bitset_iter_works() {
+ let mut bitset: BitSet<usize> = BitSet::new_empty(100);
+ bitset.insert(1);
+ bitset.insert(10);
+ bitset.insert(19);
+ bitset.insert(62);
+ bitset.insert(63);
+ bitset.insert(64);
+ bitset.insert(65);
+ bitset.insert(66);
+ bitset.insert(99);
+ assert_eq!(bitset.iter().collect::<Vec<_>>(), [1, 10, 19, 62, 63, 64, 65, 66, 99]);
+}
+
+#[test]
+fn bitset_iter_works_2() {
+ let mut bitset: BitSet<usize> = BitSet::new_empty(320);
+ bitset.insert(0);
+ bitset.insert(127);
+ bitset.insert(191);
+ bitset.insert(255);
+ bitset.insert(319);
+ assert_eq!(bitset.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
+}
+
+#[test]
+fn bitset_clone_from() {
+ let mut a: BitSet<usize> = BitSet::new_empty(10);
+ a.insert(4);
+ a.insert(7);
+ a.insert(9);
+
+ let mut b = BitSet::new_empty(2);
+ b.clone_from(&a);
+ assert_eq!(b.domain_size(), 10);
+ assert_eq!(b.iter().collect::<Vec<_>>(), [4, 7, 9]);
+
+ b.clone_from(&BitSet::new_empty(40));
+ assert_eq!(b.domain_size(), 40);
+ assert_eq!(b.iter().collect::<Vec<_>>(), []);
+}
+
+#[test]
+fn union_two_sets() {
+ let mut set1: BitSet<usize> = BitSet::new_empty(65);
+ let mut set2: BitSet<usize> = BitSet::new_empty(65);
+ assert!(set1.insert(3));
+ assert!(!set1.insert(3));
+ assert!(set2.insert(5));
+ assert!(set2.insert(64));
+ assert!(set1.union(&set2));
+ assert!(!set1.union(&set2));
+ assert!(set1.contains(3));
+ assert!(!set1.contains(4));
+ assert!(set1.contains(5));
+ assert!(!set1.contains(63));
+ assert!(set1.contains(64));
+}
+
+#[test]
+fn hybrid_bitset() {
+ let mut sparse038: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+ assert!(sparse038.is_empty());
+ assert!(sparse038.insert(0));
+ assert!(sparse038.insert(1));
+ assert!(sparse038.insert(8));
+ assert!(sparse038.insert(3));
+ assert!(!sparse038.insert(3));
+ assert!(sparse038.remove(1));
+ assert!(!sparse038.is_empty());
+ assert_eq!(sparse038.iter().collect::<Vec<_>>(), [0, 3, 8]);
+
+ for i in 0..256 {
+ if i == 0 || i == 3 || i == 8 {
+ assert!(sparse038.contains(i));
+ } else {
+ assert!(!sparse038.contains(i));
+ }
+ }
+
+ let mut sparse01358 = sparse038.clone();
+ assert!(sparse01358.insert(1));
+ assert!(sparse01358.insert(5));
+ assert_eq!(sparse01358.iter().collect::<Vec<_>>(), [0, 1, 3, 5, 8]);
+
+ let mut dense10 = HybridBitSet::new_empty(256);
+ for i in 0..10 {
+ assert!(dense10.insert(i));
+ }
+ assert!(!dense10.is_empty());
+ assert_eq!(dense10.iter().collect::<Vec<_>>(), [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]);
+
+ let mut dense256 = HybridBitSet::new_empty(256);
+ assert!(dense256.is_empty());
+ dense256.insert_all();
+ assert!(!dense256.is_empty());
+ for i in 0..256 {
+ assert!(dense256.contains(i));
+ }
+
+ assert!(sparse038.superset(&sparse038)); // sparse + sparse (self)
+ assert!(sparse01358.superset(&sparse038)); // sparse + sparse
+ assert!(dense10.superset(&sparse038)); // dense + sparse
+ assert!(dense10.superset(&dense10)); // dense + dense (self)
+ assert!(dense256.superset(&dense10)); // dense + dense
+
+ let mut hybrid = sparse038.clone();
+ assert!(!sparse01358.union(&hybrid)); // no change
+ assert!(hybrid.union(&sparse01358));
+ assert!(hybrid.superset(&sparse01358) && sparse01358.superset(&hybrid));
+ assert!(!dense256.union(&dense10));
+
+ // dense / sparse where dense superset sparse
+ assert!(!dense10.clone().union(&sparse01358));
+ assert!(sparse01358.clone().union(&dense10));
+ assert!(dense10.clone().intersect(&sparse01358));
+ assert!(!sparse01358.clone().intersect(&dense10));
+ assert!(dense10.clone().subtract(&sparse01358));
+ assert!(sparse01358.clone().subtract(&dense10));
+
+ // dense / sparse where sparse superset dense
+ let dense038 = sparse038.to_dense();
+ assert!(!sparse01358.clone().union(&dense038));
+ assert!(dense038.clone().union(&sparse01358));
+ assert!(sparse01358.clone().intersect(&dense038));
+ assert!(!dense038.clone().intersect(&sparse01358));
+ assert!(sparse01358.clone().subtract(&dense038));
+ assert!(dense038.clone().subtract(&sparse01358));
+
+ let mut dense = dense10.clone();
+ assert!(dense.union(&dense256));
+ assert!(dense.superset(&dense256) && dense256.superset(&dense));
+ assert!(hybrid.union(&dense256));
+ assert!(hybrid.superset(&dense256) && dense256.superset(&hybrid));
+
+ assert!(!dense10.clone().intersect(&dense256));
+ assert!(dense256.clone().intersect(&dense10));
+ assert!(dense10.clone().subtract(&dense256));
+ assert!(dense256.clone().subtract(&dense10));
+
+ assert_eq!(dense256.iter().count(), 256);
+ let mut dense0 = dense256;
+ for i in 0..256 {
+ assert!(dense0.remove(i));
+ }
+ assert!(!dense0.remove(0));
+ assert!(dense0.is_empty());
+}
+
+#[test]
+fn chunked_bitset() {
+ let mut b0 = ChunkedBitSet::<usize>::new_empty(0);
+ let b0b = b0.clone();
+ assert_eq!(b0, ChunkedBitSet { domain_size: 0, chunks: Box::new([]), marker: PhantomData });
+
+ // There are no valid insert/remove/contains operations on a 0-domain
+ // bitset, but we can test `union`.
+ b0.assert_valid();
+ assert!(!b0.union(&b0b));
+ assert_eq!(b0.chunks(), vec![]);
+ assert_eq!(b0.count(), 0);
+ b0.assert_valid();
+
+ //-----------------------------------------------------------------------
+
+ let mut b1 = ChunkedBitSet::<usize>::new_empty(1);
+ assert_eq!(
+ b1,
+ ChunkedBitSet { domain_size: 1, chunks: Box::new([Zeros(1)]), marker: PhantomData }
+ );
+
+ b1.assert_valid();
+ assert!(!b1.contains(0));
+ assert_eq!(b1.count(), 0);
+ assert!(b1.insert(0));
+ assert!(b1.contains(0));
+ assert_eq!(b1.count(), 1);
+ assert_eq!(b1.chunks(), [Ones(1)]);
+ assert!(!b1.insert(0));
+ assert!(b1.remove(0));
+ assert!(!b1.contains(0));
+ assert_eq!(b1.count(), 0);
+ assert_eq!(b1.chunks(), [Zeros(1)]);
+ b1.assert_valid();
+
+ //-----------------------------------------------------------------------
+
+ let mut b100 = ChunkedBitSet::<usize>::new_filled(100);
+ assert_eq!(
+ b100,
+ ChunkedBitSet { domain_size: 100, chunks: Box::new([Ones(100)]), marker: PhantomData }
+ );
+
+ b100.assert_valid();
+ for i in 0..100 {
+ assert!(b100.contains(i));
+ }
+ assert_eq!(b100.count(), 100);
+ assert!(b100.remove(3));
+ assert!(b100.insert(3));
+ assert_eq!(b100.chunks(), vec![Ones(100)]);
+ assert!(
+ b100.remove(20) && b100.remove(30) && b100.remove(40) && b100.remove(99) && b100.insert(30)
+ );
+ assert_eq!(b100.count(), 97);
+ assert!(!b100.contains(20) && b100.contains(30) && !b100.contains(99) && b100.contains(50));
+ assert_eq!(
+ b100.chunks(),
+ vec![Mixed(
+ 100,
+ 97,
+ #[rustfmt::skip]
+ Rc::new([
+ 0b11111111_11111111_11111110_11111111_11111111_11101111_11111111_11111111,
+ 0b00000000_00000000_00000000_00000111_11111111_11111111_11111111_11111111,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0,
+ ])
+ )],
+ );
+ b100.assert_valid();
+ let mut num_removed = 0;
+ for i in 0..100 {
+ if b100.remove(i) {
+ num_removed += 1;
+ }
+ }
+ assert_eq!(num_removed, 97);
+ assert_eq!(b100.chunks(), vec![Zeros(100)]);
+ b100.assert_valid();
+
+ //-----------------------------------------------------------------------
+
+ let mut b2548 = ChunkedBitSet::<usize>::new_empty(2548);
+ assert_eq!(
+ b2548,
+ ChunkedBitSet {
+ domain_size: 2548,
+ chunks: Box::new([Zeros(2048), Zeros(500)]),
+ marker: PhantomData,
+ }
+ );
+
+ b2548.assert_valid();
+ b2548.insert(14);
+ b2548.remove(14);
+ assert_eq!(b2548.chunks(), vec![Zeros(2048), Zeros(500)]);
+ b2548.insert_all();
+ for i in 0..2548 {
+ assert!(b2548.contains(i));
+ }
+ assert_eq!(b2548.count(), 2548);
+ assert_eq!(b2548.chunks(), vec![Ones(2048), Ones(500)]);
+ b2548.assert_valid();
+
+ //-----------------------------------------------------------------------
+
+ let mut b4096 = ChunkedBitSet::<usize>::new_empty(4096);
+ assert_eq!(
+ b4096,
+ ChunkedBitSet {
+ domain_size: 4096,
+ chunks: Box::new([Zeros(2048), Zeros(2048)]),
+ marker: PhantomData,
+ }
+ );
+
+ b4096.assert_valid();
+ for i in 0..4096 {
+ assert!(!b4096.contains(i));
+ }
+ assert!(b4096.insert(0) && b4096.insert(4095) && !b4096.insert(4095));
+ assert!(
+ b4096.contains(0) && !b4096.contains(2047) && !b4096.contains(2048) && b4096.contains(4095)
+ );
+ assert_eq!(
+ b4096.chunks(),
+ #[rustfmt::skip]
+ vec![
+ Mixed(2048, 1, Rc::new([
+ 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
+ ])),
+ Mixed(2048, 1, Rc::new([
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x8000_0000_0000_0000
+ ])),
+ ],
+ );
+ assert_eq!(b4096.count(), 2);
+ b4096.assert_valid();
+
+ //-----------------------------------------------------------------------
+
+ let mut b10000 = ChunkedBitSet::<usize>::new_empty(10000);
+ assert_eq!(
+ b10000,
+ ChunkedBitSet {
+ domain_size: 10000,
+ chunks: Box::new([Zeros(2048), Zeros(2048), Zeros(2048), Zeros(2048), Zeros(1808),]),
+ marker: PhantomData,
+ }
+ );
+
+ b10000.assert_valid();
+ assert!(b10000.insert(3000) && b10000.insert(5000));
+ assert_eq!(
+ b10000.chunks(),
+ #[rustfmt::skip]
+ vec![
+ Zeros(2048),
+ Mixed(2048, 1, Rc::new([
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100_0000_0000_0000, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ ])),
+ Mixed(2048, 1, Rc::new([
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0x0100, 0,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ ])),
+ Zeros(2048),
+ Zeros(1808),
+ ],
+ );
+ let mut b10000b = ChunkedBitSet::<usize>::new_empty(10000);
+ b10000b.clone_from(&b10000);
+ assert_eq!(b10000, b10000b);
+ for i in 6000..7000 {
+ b10000b.insert(i);
+ }
+ assert_eq!(b10000b.count(), 1002);
+ b10000b.assert_valid();
+ b10000b.clone_from(&b10000);
+ assert_eq!(b10000b.count(), 2);
+ for i in 2000..8000 {
+ b10000b.insert(i);
+ }
+ b10000.union(&b10000b);
+ assert_eq!(b10000.count(), 6000);
+ b10000.union(&b10000b);
+ assert_eq!(b10000.count(), 6000);
+ b10000.assert_valid();
+ b10000b.assert_valid();
+}
+
+fn with_elements_chunked(elements: &[usize], domain_size: usize) -> ChunkedBitSet<usize> {
+ let mut s = ChunkedBitSet::new_empty(domain_size);
+ for &e in elements {
+ assert!(s.insert(e));
+ }
+ s
+}
+
+fn with_elements_standard(elements: &[usize], domain_size: usize) -> BitSet<usize> {
+ let mut s = BitSet::new_empty(domain_size);
+ for &e in elements {
+ assert!(s.insert(e));
+ }
+ s
+}
+
+#[test]
+fn chunked_bitset_into_bitset_operations() {
+ let a = vec![1, 5, 7, 11, 15, 2000, 3000];
+ let b = vec![3, 4, 11, 3000, 4000];
+ let aub = vec![1, 3, 4, 5, 7, 11, 15, 2000, 3000, 4000];
+ let aib = vec![11, 3000];
+
+ let b = with_elements_chunked(&b, 9876);
+
+ let mut union = with_elements_standard(&a, 9876);
+ assert!(union.union(&b));
+ assert!(!union.union(&b));
+ assert!(union.iter().eq(aub.iter().copied()));
+
+ let mut intersection = with_elements_standard(&a, 9876);
+ assert!(intersection.intersect(&b));
+ assert!(!intersection.intersect(&b));
+ assert!(intersection.iter().eq(aib.iter().copied()));
+}
+
+#[test]
+fn chunked_bitset_iter() {
+ fn check_iter(bit: &ChunkedBitSet<usize>, vec: &Vec<usize>) {
+ // Test collecting via both `.next()` and `.fold()` calls, to make sure both are correct
+ let mut collect_next = Vec::new();
+ let mut bit_iter = bit.iter();
+ while let Some(item) = bit_iter.next() {
+ collect_next.push(item);
+ }
+ assert_eq!(vec, &collect_next);
+
+ let collect_fold = bit.iter().fold(Vec::new(), |mut v, item| {
+ v.push(item);
+ v
+ });
+ assert_eq!(vec, &collect_fold);
+ }
+
+ // Empty
+ let vec: Vec<usize> = Vec::new();
+ let bit = with_elements_chunked(&vec, 9000);
+ check_iter(&bit, &vec);
+
+ // Filled
+ let n = 10000;
+ let vec: Vec<usize> = (0..n).collect();
+ let bit = with_elements_chunked(&vec, n);
+ check_iter(&bit, &vec);
+
+ // Filled with trailing zeros
+ let n = 10000;
+ let vec: Vec<usize> = (0..n).collect();
+ let bit = with_elements_chunked(&vec, 2 * n);
+ check_iter(&bit, &vec);
+
+ // Mixed
+ let n = 12345;
+ let vec: Vec<usize> = vec![0, 1, 2, 2010, 2047, 2099, 6000, 6002, 6004];
+ let bit = with_elements_chunked(&vec, n);
+ check_iter(&bit, &vec);
+}
+
+#[test]
+fn grow() {
+ let mut set: GrowableBitSet<usize> = GrowableBitSet::with_capacity(65);
+ for index in 0..65 {
+ assert!(set.insert(index));
+ assert!(!set.insert(index));
+ }
+ set.ensure(128);
+
+ // Check if the bits set before growing are still set
+ for index in 0..65 {
+ assert!(set.contains(index));
+ }
+
+ // Check if the new bits are all un-set
+ for index in 65..128 {
+ assert!(!set.contains(index));
+ }
+
+ // Check that we can set all new bits without running out of bounds
+ for index in 65..128 {
+ assert!(set.insert(index));
+ assert!(!set.insert(index));
+ }
+}
+
+#[test]
+fn matrix_intersection() {
+ let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
+
+ // (*) Elements reachable from both 2 and 65.
+
+ matrix.insert(2, 3);
+ matrix.insert(2, 6);
+ matrix.insert(2, 10); // (*)
+ matrix.insert(2, 64); // (*)
+ matrix.insert(2, 65);
+ matrix.insert(2, 130);
+ matrix.insert(2, 160); // (*)
+
+ matrix.insert(64, 133);
+
+ matrix.insert(65, 2);
+ matrix.insert(65, 8);
+ matrix.insert(65, 10); // (*)
+ matrix.insert(65, 64); // (*)
+ matrix.insert(65, 68);
+ matrix.insert(65, 133);
+ matrix.insert(65, 160); // (*)
+
+ let intersection = matrix.intersect_rows(2, 64);
+ assert!(intersection.is_empty());
+
+ let intersection = matrix.intersect_rows(2, 65);
+ assert_eq!(intersection, &[10, 64, 160]);
+}
+
+#[test]
+fn matrix_iter() {
+ let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
+ matrix.insert(3, 22);
+ matrix.insert(3, 75);
+ matrix.insert(2, 99);
+ matrix.insert(4, 0);
+ matrix.union_rows(3, 5);
+ matrix.insert_all_into_row(6);
+
+ let expected = [99];
+ let mut iter = expected.iter();
+ for i in matrix.iter(2) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ let expected = [22, 75];
+ let mut iter = expected.iter();
+ assert_eq!(matrix.count(3), expected.len());
+ for i in matrix.iter(3) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ let expected = [0];
+ let mut iter = expected.iter();
+ assert_eq!(matrix.count(4), expected.len());
+ for i in matrix.iter(4) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ let expected = [22, 75];
+ let mut iter = expected.iter();
+ assert_eq!(matrix.count(5), expected.len());
+ for i in matrix.iter(5) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ assert_eq!(matrix.count(6), 100);
+ let mut count = 0;
+ for (idx, i) in matrix.iter(6).enumerate() {
+ assert_eq!(idx, i);
+ count += 1;
+ }
+ assert_eq!(count, 100);
+
+ if let Some(i) = matrix.iter(7).next() {
+ panic!("expected no elements in row, but contains element {:?}", i);
+ }
+}
+
+#[test]
+fn sparse_matrix_iter() {
+ let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
+ matrix.insert(3, 22);
+ matrix.insert(3, 75);
+ matrix.insert(2, 99);
+ matrix.insert(4, 0);
+ matrix.union_rows(3, 5);
+
+ let expected = [99];
+ let mut iter = expected.iter();
+ for i in matrix.iter(2) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ let expected = [22, 75];
+ let mut iter = expected.iter();
+ for i in matrix.iter(3) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ let expected = [0];
+ let mut iter = expected.iter();
+ for i in matrix.iter(4) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+
+ let expected = [22, 75];
+ let mut iter = expected.iter();
+ for i in matrix.iter(5) {
+ let j = *iter.next().unwrap();
+ assert_eq!(i, j);
+ }
+ assert!(iter.next().is_none());
+}
+
+#[test]
+fn sparse_matrix_operations() {
+ let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
+ matrix.insert(3, 22);
+ matrix.insert(3, 75);
+ matrix.insert(2, 99);
+ matrix.insert(4, 0);
+
+ let mut disjoint: HybridBitSet<usize> = HybridBitSet::new_empty(100);
+ disjoint.insert(33);
+
+ let mut superset = HybridBitSet::new_empty(100);
+ superset.insert(22);
+ superset.insert(75);
+ superset.insert(33);
+
+ let mut subset = HybridBitSet::new_empty(100);
+ subset.insert(22);
+
+ // SparseBitMatrix::remove
+ {
+ let mut matrix = matrix.clone();
+ matrix.remove(3, 22);
+ assert!(!matrix.row(3).unwrap().contains(22));
+ matrix.remove(0, 0);
+ assert!(matrix.row(0).is_none());
+ }
+
+ // SparseBitMatrix::clear
+ {
+ let mut matrix = matrix.clone();
+ matrix.clear(3);
+ assert!(!matrix.row(3).unwrap().contains(75));
+ matrix.clear(0);
+ assert!(matrix.row(0).is_none());
+ }
+
+ // SparseBitMatrix::intersect_row
+ {
+ let mut matrix = matrix.clone();
+ assert!(!matrix.intersect_row(3, &superset));
+ assert!(matrix.intersect_row(3, &subset));
+ matrix.intersect_row(0, &disjoint);
+ assert!(matrix.row(0).is_none());
+ }
+
+ // SparseBitMatrix::subtract_row
+ {
+ let mut matrix = matrix.clone();
+ assert!(!matrix.subtract_row(3, &disjoint));
+ assert!(matrix.subtract_row(3, &subset));
+ assert!(matrix.subtract_row(3, &superset));
+ matrix.intersect_row(0, &disjoint);
+ assert!(matrix.row(0).is_none());
+ }
+
+ // SparseBitMatrix::union_row
+ {
+ let mut matrix = matrix.clone();
+ assert!(!matrix.union_row(3, &subset));
+ assert!(matrix.union_row(3, &disjoint));
+ matrix.union_row(0, &disjoint);
+ assert!(matrix.row(0).is_some());
+ }
+}
+
+#[test]
+fn dense_insert_range() {
+ #[track_caller]
+ fn check<R>(domain: usize, range: R)
+ where
+ R: RangeBounds<usize> + Clone + IntoIterator<Item = usize> + std::fmt::Debug,
+ {
+ let mut set = BitSet::new_empty(domain);
+ set.insert_range(range.clone());
+ for i in set.iter() {
+ assert!(range.contains(&i));
+ }
+ for i in range.clone() {
+ assert!(set.contains(i), "{} in {:?}, inserted {:?}", i, set, range);
+ }
+ }
+ check(300, 10..10);
+ check(300, WORD_BITS..WORD_BITS * 2);
+ check(300, WORD_BITS - 1..WORD_BITS * 2);
+ check(300, WORD_BITS - 1..WORD_BITS);
+ check(300, 10..100);
+ check(300, 10..30);
+ check(300, 0..5);
+ check(300, 0..250);
+ check(300, 200..250);
+
+ check(300, 10..=10);
+ check(300, WORD_BITS..=WORD_BITS * 2);
+ check(300, WORD_BITS - 1..=WORD_BITS * 2);
+ check(300, WORD_BITS - 1..=WORD_BITS);
+ check(300, 10..=100);
+ check(300, 10..=30);
+ check(300, 0..=5);
+ check(300, 0..=250);
+ check(300, 200..=250);
+
+ for i in 0..WORD_BITS * 2 {
+ for j in i..WORD_BITS * 2 {
+ check(WORD_BITS * 2, i..j);
+ check(WORD_BITS * 2, i..=j);
+ check(300, i..j);
+ check(300, i..=j);
+ }
+ }
+}
+
+#[test]
+fn dense_last_set_before() {
+ fn easy(set: &BitSet<usize>, needle: impl RangeBounds<usize>) -> Option<usize> {
+ let mut last_leq = None;
+ for e in set.iter() {
+ if needle.contains(&e) {
+ last_leq = Some(e);
+ }
+ }
+ last_leq
+ }
+
+ #[track_caller]
+ fn cmp(set: &BitSet<usize>, needle: impl RangeBounds<usize> + Clone + std::fmt::Debug) {
+ assert_eq!(
+ set.last_set_in(needle.clone()),
+ easy(set, needle.clone()),
+ "{:?} in {:?}",
+ needle,
+ set
+ );
+ }
+ let mut set = BitSet::new_empty(300);
+ cmp(&set, 50..=50);
+ set.insert(WORD_BITS);
+ cmp(&set, WORD_BITS..=WORD_BITS);
+ set.insert(WORD_BITS - 1);
+ cmp(&set, 0..=WORD_BITS - 1);
+ cmp(&set, 0..=5);
+ cmp(&set, 10..100);
+ set.insert(100);
+ cmp(&set, 100..110);
+ cmp(&set, 99..100);
+ cmp(&set, 99..=100);
+
+ for i in 0..=WORD_BITS * 2 {
+ for j in i..=WORD_BITS * 2 {
+ for k in 0..WORD_BITS * 2 {
+ let mut set = BitSet::new_empty(300);
+ cmp(&set, i..j);
+ cmp(&set, i..=j);
+ set.insert(k);
+ cmp(&set, i..j);
+ cmp(&set, i..=j);
+ }
+ }
+ }
+}
+
+/// Merge dense hybrid set into empty sparse hybrid set.
+#[bench]
+fn union_hybrid_sparse_empty_to_dense(b: &mut Bencher) {
+ let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+ for i in 0..10 {
+ assert!(pre_dense.insert(i));
+ }
+ let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+ b.iter(|| {
+ let dense = pre_dense.clone();
+ let mut sparse = pre_sparse.clone();
+ sparse.union(&dense);
+ })
+}
+
+/// Merge dense hybrid set into full hybrid set with same indices.
+#[bench]
+fn union_hybrid_sparse_full_to_dense(b: &mut Bencher) {
+ let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+ for i in 0..10 {
+ assert!(pre_dense.insert(i));
+ }
+ let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(256);
+ for i in 0..SPARSE_MAX {
+ assert!(pre_sparse.insert(i));
+ }
+ b.iter(|| {
+ let dense = pre_dense.clone();
+ let mut sparse = pre_sparse.clone();
+ sparse.union(&dense);
+ })
+}
+
+/// Merge dense hybrid set into full hybrid set with indices over the whole domain.
+#[bench]
+fn union_hybrid_sparse_domain_to_dense(b: &mut Bencher) {
+ let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
+ for i in 0..10 {
+ assert!(pre_dense.insert(i));
+ }
+ let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX * 64);
+ for i in 0..SPARSE_MAX {
+ assert!(pre_sparse.insert(i * 64));
+ }
+ b.iter(|| {
+ let dense = pre_dense.clone();
+ let mut sparse = pre_sparse.clone();
+ sparse.union(&dense);
+ })
+}
+
+/// Merge dense hybrid set into empty hybrid set where the domain is very small.
+#[bench]
+fn union_hybrid_sparse_empty_small_domain(b: &mut Bencher) {
+ let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+ for i in 0..SPARSE_MAX {
+ assert!(pre_dense.insert(i));
+ }
+ let pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+ b.iter(|| {
+ let dense = pre_dense.clone();
+ let mut sparse = pre_sparse.clone();
+ sparse.union(&dense);
+ })
+}
+
+/// Merge dense hybrid set into full hybrid set where the domain is very small.
+#[bench]
+fn union_hybrid_sparse_full_small_domain(b: &mut Bencher) {
+ let mut pre_dense: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+ for i in 0..SPARSE_MAX {
+ assert!(pre_dense.insert(i));
+ }
+ let mut pre_sparse: HybridBitSet<usize> = HybridBitSet::new_empty(SPARSE_MAX);
+ for i in 0..SPARSE_MAX {
+ assert!(pre_sparse.insert(i));
+ }
+ b.iter(|| {
+ let dense = pre_dense.clone();
+ let mut sparse = pre_sparse.clone();
+ sparse.union(&dense);
+ })
+}
+
+#[bench]
+fn bench_insert(b: &mut Bencher) {
+ let mut bs = BitSet::new_filled(99999usize);
+ b.iter(|| {
+ black_box(bs.insert(black_box(100u32)));
+ });
+}
+
+#[bench]
+fn bench_remove(b: &mut Bencher) {
+ let mut bs = BitSet::new_filled(99999usize);
+ b.iter(|| {
+ black_box(bs.remove(black_box(100u32)));
+ });
+}
+
+#[bench]
+fn bench_iter(b: &mut Bencher) {
+ let bs = BitSet::new_filled(99999usize);
+ b.iter(|| {
+ bs.iter().map(|b: usize| black_box(b)).for_each(drop);
+ });
+}
+
+#[bench]
+fn bench_intersect(b: &mut Bencher) {
+ let mut ba: BitSet<u32> = BitSet::new_filled(99999usize);
+ let bb = BitSet::new_filled(99999usize);
+ b.iter(|| {
+ ba.intersect(black_box(&bb));
+ });
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-11 21:14:53 +0000