src/librustc_data_structures/bitvec.rs

   1 // Copyright 2015 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use indexed_vec::{Idx, IndexVec};
  12 use std::iter::FromIterator;
  13 use std::marker::PhantomData;
  14
  15 type Word = u128;
  16 const WORD_BITS: usize = 128;
  17
  18 /// A very simple BitVector type.
  19 #[derive(Clone, Debug, PartialEq)]
  20 pub struct BitVector<C: Idx> {
  21     data: Vec<Word>,
  22     marker: PhantomData<C>,
  23 }
  24
  25 impl<C: Idx> BitVector<C> {
  26     #[inline]
  27     pub fn new(num_bits: usize) -> BitVector<C> {
  28         let num_words = words(num_bits);
  29         BitVector {
  30             data: vec![0; num_words],
  31             marker: PhantomData,
  32         }
  33     }
  34
  35     #[inline]
  36     pub fn clear(&mut self) {
  37         for p in &mut self.data {
  38             *p = 0;
  39         }
  40     }
  41
  42     pub fn count(&self) -> usize {
  43         self.data.iter().map(|e| e.count_ones() as usize).sum()
  44     }
  45
  46     /// True if `self` contains the bit `bit`.
  47     #[inline]
  48     pub fn contains(&self, bit: C) -> bool {
  49         let (word, mask) = word_mask(bit);
  50         (self.data[word] & mask) != 0
  51     }
  52
  53     /// True if `self` contains all the bits in `other`.
  54     ///
  55     /// The two vectors must have the same length.
  56     #[inline]
  57     pub fn contains_all(&self, other: &BitVector<C>) -> bool {
  58         assert_eq!(self.data.len(), other.data.len());
  59         self.data.iter().zip(&other.data).all(|(a, b)| (a & b) == *b)
  60     }
  61
  62     #[inline]
  63     pub fn is_empty(&self) -> bool {
  64         self.data.iter().all(|a| *a == 0)
  65     }
  66
  67     /// Returns true if the bit has changed.
  68     #[inline]
  69     pub fn insert(&mut self, bit: C) -> bool {
  70         let (word, mask) = word_mask(bit);
  71         let data = &mut self.data[word];
  72         let value = *data;
  73         let new_value = value | mask;
  74         *data = new_value;
  75         new_value != value
  76     }
  77
  78     /// Sets all bits to true.
  79     pub fn insert_all(&mut self) {
  80         for data in &mut self.data {
  81             *data = u128::max_value();
  82         }
  83     }
  84
  85     /// Returns true if the bit has changed.
  86     #[inline]
  87     pub fn remove(&mut self, bit: C) -> bool {
  88         let (word, mask) = word_mask(bit);
  89         let data = &mut self.data[word];
  90         let value = *data;
  91         let new_value = value & !mask;
  92         *data = new_value;
  93         new_value != value
  94     }
  95
  96     #[inline]
  97     pub fn merge(&mut self, all: &BitVector<C>) -> bool {
  98         assert!(self.data.len() == all.data.len());
  99         let mut changed = false;
 100         for (i, j) in self.data.iter_mut().zip(&all.data) {
 101             let value = *i;
 102             *i = value | *j;
 103             if value != *i {
 104                 changed = true;
 105             }
 106         }
 107         changed
 108     }
 109
 110     #[inline]
 111     pub fn grow(&mut self, num_bits: C) {
 112         let num_words = words(num_bits);
 113         if self.data.len() < num_words {
 114             self.data.resize(num_words, 0)
 115         }
 116     }
 117
 118     /// Iterates over indexes of set bits in a sorted order
 119     #[inline]
 120     pub fn iter<'a>(&'a self) -> BitVectorIter<'a, C> {
 121         BitVectorIter {
 122             iter: self.data.iter(),
 123             current: 0,
 124             idx: 0,
 125             marker: PhantomData,
 126         }
 127     }
 128 }
 129
 130 pub struct BitVectorIter<'a, C: Idx> {
 131     iter: ::std::slice::Iter<'a, Word>,
 132     current: Word,
 133     idx: usize,
 134     marker: PhantomData<C>
 135 }
 136
 137 impl<'a, C: Idx> Iterator for BitVectorIter<'a, C> {
 138     type Item = C;
 139     fn next(&mut self) -> Option<C> {
 140         while self.current == 0 {
 141             self.current = if let Some(&i) = self.iter.next() {
 142                 if i == 0 {
 143                     self.idx += WORD_BITS;
 144                     continue;
 145                 } else {
 146                     self.idx = words(self.idx) * WORD_BITS;
 147                     i
 148                 }
 149             } else {
 150                 return None;
 151             }
 152         }
 153         let offset = self.current.trailing_zeros() as usize;
 154         self.current >>= offset;
 155         self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
 156         self.idx += offset + 1;
 157         return Some(C::new(self.idx - 1));
 158     }
 159
 160     fn size_hint(&self) -> (usize, Option<usize>) {
 161         let (_, upper) = self.iter.size_hint();
 162         (0, upper)
 163     }
 164 }
 165
 166 impl<C: Idx> FromIterator<bool> for BitVector<C> {
 167     fn from_iter<I>(iter: I) -> BitVector<C>
 168     where
 169         I: IntoIterator<Item = bool>,
 170     {
 171         let iter = iter.into_iter();
 172         let (len, _) = iter.size_hint();
 173         // Make the minimum length for the bitvector WORD_BITS bits since that's
 174         // the smallest non-zero size anyway.
 175         let len = if len < WORD_BITS { WORD_BITS } else { len };
 176         let mut bv = BitVector::new(len);
 177         for (idx, val) in iter.enumerate() {
 178             if idx > len {
 179                 bv.grow(C::new(idx));
 180             }
 181             if val {
 182                 bv.insert(C::new(idx));
 183             }
 184         }
 185
 186         bv
 187     }
 188 }
 189
 190 /// A "bit matrix" is basically a matrix of booleans represented as
 191 /// one gigantic bitvector. In other words, it is as if you have
 192 /// `rows` bitvectors, each of length `columns`.
 193 #[derive(Clone, Debug)]
 194 pub struct BitMatrix<R: Idx, C: Idx> {
 195     columns: usize,
 196     vector: Vec<Word>,
 197     phantom: PhantomData<(R, C)>,
 198 }
 199
 200 impl<R: Idx, C: Idx> BitMatrix<R, C> {
 201     /// Create a new `rows x columns` matrix, initially empty.
 202     pub fn new(rows: usize, columns: usize) -> BitMatrix<R, C> {
 203         // For every element, we need one bit for every other
 204         // element. Round up to an even number of words.
 205         let words_per_row = words(columns);
 206         BitMatrix {
 207             columns,
 208             vector: vec![0; rows * words_per_row],
 209             phantom: PhantomData,
 210         }
 211     }
 212
 213     /// The range of bits for a given row.
 214     fn range(&self, row: R) -> (usize, usize) {
 215         let row = row.index();
 216         let words_per_row = words(self.columns);
 217         let start = row * words_per_row;
 218         (start, start + words_per_row)
 219     }
 220
 221     /// Sets the cell at `(row, column)` to true. Put another way, add
 222     /// `column` to the bitset for `row`.
 223     ///
 224     /// Returns true if this changed the matrix, and false otherwise.
 225     pub fn add(&mut self, row: R, column: R) -> bool {
 226         let (start, _) = self.range(row);
 227         let (word, mask) = word_mask(column);
 228         let vector = &mut self.vector[..];
 229         let v1 = vector[start + word];
 230         let v2 = v1 | mask;
 231         vector[start + word] = v2;
 232         v1 != v2
 233     }
 234
 235     /// Do the bits from `row` contain `column`? Put another way, is
 236     /// the matrix cell at `(row, column)` true?  Put yet another way,
 237     /// if the matrix represents (transitive) reachability, can
 238     /// `row` reach `column`?
 239     pub fn contains(&self, row: R, column: R) -> bool {
 240         let (start, _) = self.range(row);
 241         let (word, mask) = word_mask(column);
 242         (self.vector[start + word] & mask) != 0
 243     }
 244
 245     /// Returns those indices that are true in rows `a` and `b`.  This
 246     /// is an O(n) operation where `n` is the number of elements
 247     /// (somewhat independent from the actual size of the
 248     /// intersection, in particular).
 249     pub fn intersection(&self, a: R, b: R) -> Vec<C> {
 250         let (a_start, a_end) = self.range(a);
 251         let (b_start, b_end) = self.range(b);
 252         let mut result = Vec::with_capacity(self.columns);
 253         for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
 254             let mut v = self.vector[i] & self.vector[j];
 255             for bit in 0..WORD_BITS {
 256                 if v == 0 {
 257                     break;
 258                 }
 259                 if v & 0x1 != 0 {
 260                     result.push(C::new(base * WORD_BITS + bit));
 261                 }
 262                 v >>= 1;
 263             }
 264         }
 265         result
 266     }
 267
 268     /// Add the bits from row `read` to the bits from row `write`,
 269     /// return true if anything changed.
 270     ///
 271     /// This is used when computing transitive reachability because if
 272     /// you have an edge `write -> read`, because in that case
 273     /// `write` can reach everything that `read` can (and
 274     /// potentially more).
 275     pub fn merge(&mut self, read: R, write: R) -> bool {
 276         let (read_start, read_end) = self.range(read);
 277         let (write_start, write_end) = self.range(write);
 278         let vector = &mut self.vector[..];
 279         let mut changed = false;
 280         for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
 281             let v1 = vector[write_index];
 282             let v2 = v1 | vector[read_index];
 283             vector[write_index] = v2;
 284             changed = changed | (v1 != v2);
 285         }
 286         changed
 287     }
 288
 289     /// Iterates through all the columns set to true in a given row of
 290     /// the matrix.
 291     pub fn iter<'a>(&'a self, row: R) -> BitVectorIter<'a, C> {
 292         let (start, end) = self.range(row);
 293         BitVectorIter {
 294             iter: self.vector[start..end].iter(),
 295             current: 0,
 296             idx: 0,
 297             marker: PhantomData,
 298         }
 299     }
 300 }
 301
 302 /// A moderately sparse bit matrix: rows are appended lazily, but columns
 303 /// within appended rows are instantiated fully upon creation.
 304 #[derive(Clone, Debug)]
 305 pub struct SparseBitMatrix<R, C>
 306 where
 307     R: Idx,
 308     C: Idx,
 309 {
 310     columns: usize,
 311     vector: IndexVec<R, BitVector<C>>,
 312 }
 313
 314 impl<R: Idx, C: Idx> SparseBitMatrix<R, C> {
 315     /// Create a new empty sparse bit matrix with no rows or columns.
 316     pub fn new(columns: usize) -> Self {
 317         Self {
 318             columns,
 319             vector: IndexVec::new(),
 320         }
 321     }
 322
 323     fn ensure_row(&mut self, row: R) {
 324         let columns = self.columns;
 325         self.vector
 326             .ensure_contains_elem(row, || BitVector::new(columns));
 327     }
 328
 329     /// Sets the cell at `(row, column)` to true. Put another way, insert
 330     /// `column` to the bitset for `row`.
 331     ///
 332     /// Returns true if this changed the matrix, and false otherwise.
 333     pub fn add(&mut self, row: R, column: C) -> bool {
 334         self.ensure_row(row);
 335         self.vector[row].insert(column)
 336     }
 337
 338     /// Do the bits from `row` contain `column`? Put another way, is
 339     /// the matrix cell at `(row, column)` true?  Put yet another way,
 340     /// if the matrix represents (transitive) reachability, can
 341     /// `row` reach `column`?
 342     pub fn contains(&self, row: R, column: C) -> bool {
 343         self.vector.get(row).map_or(false, |r| r.contains(column))
 344     }
 345
 346     /// Add the bits from row `read` to the bits from row `write`,
 347     /// return true if anything changed.
 348     ///
 349     /// This is used when computing transitive reachability because if
 350     /// you have an edge `write -> read`, because in that case
 351     /// `write` can reach everything that `read` can (and
 352     /// potentially more).
 353     pub fn merge(&mut self, read: R, write: R) -> bool {
 354         if read == write || self.vector.get(read).is_none() {
 355             return false;
 356         }
 357
 358         self.ensure_row(write);
 359         let (bitvec_read, bitvec_write) = self.vector.pick2_mut(read, write);
 360         bitvec_write.merge(bitvec_read)
 361     }
 362
 363     /// Merge a row, `from`, into the `into` row.
 364     pub fn merge_into(&mut self, into: R, from: &BitVector<C>) -> bool {
 365         self.ensure_row(into);
 366         self.vector[into].merge(from)
 367     }
 368
 369     /// Add all bits to the given row.
 370     pub fn add_all(&mut self, row: R) {
 371         self.ensure_row(row);
 372         self.vector[row].insert_all();
 373     }
 374
 375     /// Number of elements in the matrix.
 376     pub fn len(&self) -> usize {
 377         self.vector.len()
 378     }
 379
 380     pub fn rows(&self) -> impl Iterator<Item = R> {
 381         self.vector.indices()
 382     }
 383
 384     /// Iterates through all the columns set to true in a given row of
 385     /// the matrix.
 386     pub fn iter<'a>(&'a self, row: R) -> impl Iterator<Item = C> + 'a {
 387         self.vector.get(row).into_iter().flat_map(|r| r.iter())
 388     }
 389
 390     /// Iterates through each row and the accompanying bit set.
 391     pub fn iter_enumerated<'a>(&'a self) -> impl Iterator<Item = (R, &'a BitVector<C>)> + 'a {
 392         self.vector.iter_enumerated()
 393     }
 394
 395     pub fn row(&self, row: R) -> Option<&BitVector<C>> {
 396         self.vector.get(row)
 397     }
 398 }
 399
 400 #[inline]
 401 fn words<C: Idx>(elements: C) -> usize {
 402     (elements.index() + WORD_BITS - 1) / WORD_BITS
 403 }
 404
 405 #[inline]
 406 fn word_mask<C: Idx>(index: C) -> (usize, Word) {
 407     let index = index.index();
 408     let word = index / WORD_BITS;
 409     let mask = 1 << (index % WORD_BITS);
 410     (word, mask)
 411 }
 412
 413 #[test]
 414 fn bitvec_iter_works() {
 415     let mut bitvec: BitVector<usize> = BitVector::new(100);
 416     bitvec.insert(1);
 417     bitvec.insert(10);
 418     bitvec.insert(19);
 419     bitvec.insert(62);
 420     bitvec.insert(63);
 421     bitvec.insert(64);
 422     bitvec.insert(65);
 423     bitvec.insert(66);
 424     bitvec.insert(99);
 425     assert_eq!(
 426         bitvec.iter().collect::<Vec<_>>(),
 427         [1, 10, 19, 62, 63, 64, 65, 66, 99]
 428     );
 429 }
 430
 431 #[test]
 432 fn bitvec_iter_works_2() {
 433     let mut bitvec: BitVector<usize> = BitVector::new(319);
 434     bitvec.insert(0);
 435     bitvec.insert(127);
 436     bitvec.insert(191);
 437     bitvec.insert(255);
 438     bitvec.insert(319);
 439     assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
 440 }
 441
 442 #[test]
 443 fn union_two_vecs() {
 444     let mut vec1: BitVector<usize> = BitVector::new(65);
 445     let mut vec2: BitVector<usize> = BitVector::new(65);
 446     assert!(vec1.insert(3));
 447     assert!(!vec1.insert(3));
 448     assert!(vec2.insert(5));
 449     assert!(vec2.insert(64));
 450     assert!(vec1.merge(&vec2));
 451     assert!(!vec1.merge(&vec2));
 452     assert!(vec1.contains(3));
 453     assert!(!vec1.contains(4));
 454     assert!(vec1.contains(5));
 455     assert!(!vec1.contains(63));
 456     assert!(vec1.contains(64));
 457 }
 458
 459 #[test]
 460 fn grow() {
 461     let mut vec1: BitVector<usize> = BitVector::new(65);
 462     for index in 0..65 {
 463         assert!(vec1.insert(index));
 464         assert!(!vec1.insert(index));
 465     }
 466     vec1.grow(128);
 467
 468     // Check if the bits set before growing are still set
 469     for index in 0..65 {
 470         assert!(vec1.contains(index));
 471     }
 472
 473     // Check if the new bits are all un-set
 474     for index in 65..128 {
 475         assert!(!vec1.contains(index));
 476     }
 477
 478     // Check that we can set all new bits without running out of bounds
 479     for index in 65..128 {
 480         assert!(vec1.insert(index));
 481         assert!(!vec1.insert(index));
 482     }
 483 }
 484
 485 #[test]
 486 fn matrix_intersection() {
 487     let mut vec1: BitMatrix<usize, usize> = BitMatrix::new(200, 200);
 488
 489     // (*) Elements reachable from both 2 and 65.
 490
 491     vec1.add(2, 3);
 492     vec1.add(2, 6);
 493     vec1.add(2, 10); // (*)
 494     vec1.add(2, 64); // (*)
 495     vec1.add(2, 65);
 496     vec1.add(2, 130);
 497     vec1.add(2, 160); // (*)
 498
 499     vec1.add(64, 133);
 500
 501     vec1.add(65, 2);
 502     vec1.add(65, 8);
 503     vec1.add(65, 10); // (*)
 504     vec1.add(65, 64); // (*)
 505     vec1.add(65, 68);
 506     vec1.add(65, 133);
 507     vec1.add(65, 160); // (*)
 508
 509     let intersection = vec1.intersection(2, 64);
 510     assert!(intersection.is_empty());
 511
 512     let intersection = vec1.intersection(2, 65);
 513     assert_eq!(intersection, &[10, 64, 160]);
 514 }
 515
 516 #[test]
 517 fn matrix_iter() {
 518     let mut matrix: BitMatrix<usize, usize> = BitMatrix::new(64, 100);
 519     matrix.add(3, 22);
 520     matrix.add(3, 75);
 521     matrix.add(2, 99);
 522     matrix.add(4, 0);
 523     matrix.merge(3, 5);
 524
 525     let expected = [99];
 526     let mut iter = expected.iter();
 527     for i in matrix.iter(2) {
 528         let j = *iter.next().unwrap();
 529         assert_eq!(i, j);
 530     }
 531     assert!(iter.next().is_none());
 532
 533     let expected = [22, 75];
 534     let mut iter = expected.iter();
 535     for i in matrix.iter(3) {
 536         let j = *iter.next().unwrap();
 537         assert_eq!(i, j);
 538     }
 539     assert!(iter.next().is_none());
 540
 541     let expected = [0];
 542     let mut iter = expected.iter();
 543     for i in matrix.iter(4) {
 544         let j = *iter.next().unwrap();
 545         assert_eq!(i, j);
 546     }
 547     assert!(iter.next().is_none());
 548
 549     let expected = [22, 75];
 550     let mut iter = expected.iter();
 551     for i in matrix.iter(5) {
 552         let j = *iter.next().unwrap();
 553         assert_eq!(i, j);
 554     }
 555     assert!(iter.next().is_none());
 556 }
 557
 558 #[test]
 559 fn sparse_matrix_iter() {
 560     let mut matrix: SparseBitMatrix<usize, usize> = SparseBitMatrix::new(100);
 561     matrix.add(3, 22);
 562     matrix.add(3, 75);
 563     matrix.add(2, 99);
 564     matrix.add(4, 0);
 565     matrix.merge(3, 5);
 566
 567     let expected = [99];
 568     let mut iter = expected.iter();
 569     for i in matrix.iter(2) {
 570         let j = *iter.next().unwrap();
 571         assert_eq!(i, j);
 572     }
 573     assert!(iter.next().is_none());
 574
 575     let expected = [22, 75];
 576     let mut iter = expected.iter();
 577     for i in matrix.iter(3) {
 578         let j = *iter.next().unwrap();
 579         assert_eq!(i, j);
 580     }
 581     assert!(iter.next().is_none());
 582
 583     let expected = [0];
 584     let mut iter = expected.iter();
 585     for i in matrix.iter(4) {
 586         let j = *iter.next().unwrap();
 587         assert_eq!(i, j);
 588     }
 589     assert!(iter.next().is_none());
 590
 591     let expected = [22, 75];
 592     let mut iter = expected.iter();
 593     for i in matrix.iter(5) {
 594         let j = *iter.next().unwrap();
 595         assert_eq!(i, j);
 596     }
 597     assert!(iter.next().is_none());
 598 }