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