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 /// A very simple BitVector type.
  12 pub struct BitVector {
  13     data: Vec<u64>
  14 }
  15
  16 impl BitVector {
  17     pub fn new(num_bits: usize) -> BitVector {
  18         let num_words = u64s(num_bits);
  19         BitVector { data: vec![0; num_words] }
  20     }
  21
  22     pub fn contains(&self, bit: usize) -> bool {
  23         let (word, mask) = word_mask(bit);
  24         (self.data[word] & mask) != 0
  25     }
  26
  27     /// Returns true if the bit has changed.
  28     pub fn insert(&mut self, bit: usize) -> bool {
  29         let (word, mask) = word_mask(bit);
  30         let data = &mut self.data[word];
  31         let value = *data;
  32         let new_value = value | mask;
  33         *data = new_value;
  34         new_value != value
  35     }
  36
  37     pub fn insert_all(&mut self, all: &BitVector) -> bool {
  38         assert!(self.data.len() == all.data.len());
  39         let mut changed = false;
  40         for (i, j) in self.data.iter_mut().zip(&all.data) {
  41             let value = *i;
  42             *i = value | *j;
  43             if value != *i { changed = true; }
  44         }
  45         changed
  46     }
  47
  48     pub fn grow(&mut self, num_bits: usize) {
  49         let num_words = u64s(num_bits);
  50         let extra_words = self.data.len() - num_words;
  51         self.data.extend((0..extra_words).map(|_| 0));
  52     }
  53 }
  54
  55 /// A "bit matrix" is basically a square matrix of booleans
  56 /// represented as one gigantic bitvector. In other words, it is as if
  57 /// you have N bitvectors, each of length N. Note that `elements` here is `N`/
  58 #[derive(Clone)]
  59 pub struct BitMatrix {
  60     elements: usize,
  61     vector: Vec<u64>,
  62 }
  63
  64 impl BitMatrix {
  65     // Create a new `elements x elements` matrix, initially empty.
  66     pub fn new(elements: usize) -> BitMatrix {
  67         // For every element, we need one bit for every other
  68         // element. Round up to an even number of u64s.
  69         let u64s_per_elem = u64s(elements);
  70         BitMatrix {
  71             elements: elements,
  72             vector: vec![0; elements * u64s_per_elem]
  73         }
  74     }
  75
  76     /// The range of bits for a given element.
  77     fn range(&self, element: usize) -> (usize, usize) {
  78         let u64s_per_elem = u64s(self.elements);
  79         let start = element * u64s_per_elem;
  80         (start, start + u64s_per_elem)
  81     }
  82
  83     pub fn add(&mut self, source: usize, target: usize) -> bool {
  84         let (start, _) = self.range(source);
  85         let (word, mask) = word_mask(target);
  86         let mut vector = &mut self.vector[..];
  87         let v1 = vector[start+word];
  88         let v2 = v1 | mask;
  89         vector[start+word] = v2;
  90         v1 != v2
  91     }
  92
  93     /// Do the bits from `source` contain `target`?
  94     ///
  95     /// Put another way, if the matrix represents (transitive)
  96     /// reachability, can `source` reach `target`?
  97     pub fn contains(&self, source: usize, target: usize) -> bool {
  98         let (start, _) = self.range(source);
  99         let (word, mask) = word_mask(target);
 100         (self.vector[start+word] & mask) != 0
 101     }
 102
 103     /// Returns those indices that are reachable from both `a` and
 104     /// `b`. This is an O(n) operation where `n` is the number of
 105     /// elements (somewhat independent from the actual size of the
 106     /// intersection, in particular).
 107     pub fn intersection(&self, a: usize, b: usize) -> Vec<usize> {
 108         let (a_start, a_end) = self.range(a);
 109         let (b_start, b_end) = self.range(b);
 110         let mut result = Vec::with_capacity(self.elements);
 111         for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
 112             let mut v = self.vector[i] & self.vector[j];
 113             for bit in 0..64 {
 114                 if v == 0 { break; }
 115                 if v & 0x1 != 0 { result.push(base*64 + bit); }
 116                 v >>= 1;
 117             }
 118         }
 119         result
 120     }
 121
 122     /// Add the bits from `read` to the bits from `write`,
 123     /// return true if anything changed.
 124     ///
 125     /// This is used when computing transitive reachability because if
 126     /// you have an edge `write -> read`, because in that case
 127     /// `write` can reach everything that `read` can (and
 128     /// potentially more).
 129     pub fn merge(&mut self, read: usize, write: usize) -> bool {
 130         let (read_start, read_end) = self.range(read);
 131         let (write_start, write_end) = self.range(write);
 132         let vector = &mut self.vector[..];
 133         let mut changed = false;
 134         for (read_index, write_index) in
 135             (read_start..read_end).zip(write_start..write_end)
 136         {
 137             let v1 = vector[write_index];
 138             let v2 = v1 | vector[read_index];
 139             vector[write_index] = v2;
 140             changed = changed | (v1 != v2);
 141         }
 142         changed
 143     }
 144 }
 145
 146 fn u64s(elements: usize) -> usize {
 147     (elements + 63) / 64
 148 }
 149
 150 fn word_mask(index: usize) -> (usize, u64) {
 151     let word = index / 64;
 152     let mask = 1 << (index % 64);
 153     (word, mask)
 154 }
 155
 156 #[test]
 157 fn union_two_vecs() {
 158     let mut vec1 = BitVector::new(65);
 159     let mut vec2 = BitVector::new(65);
 160     assert!(vec1.insert(3));
 161     assert!(!vec1.insert(3));
 162     assert!(vec2.insert(5));
 163     assert!(vec2.insert(64));
 164     assert!(vec1.insert_all(&vec2));
 165     assert!(!vec1.insert_all(&vec2));
 166     assert!(vec1.contains(3));
 167     assert!(!vec1.contains(4));
 168     assert!(vec1.contains(5));
 169     assert!(!vec1.contains(63));
 170     assert!(vec1.contains(64));
 171 }
 172
 173 #[test]
 174 fn grow() {
 175     let mut vec1 = BitVector::new(65);
 176     assert!(vec1.insert(3));
 177     assert!(!vec1.insert(3));
 178     assert!(vec1.insert(5));
 179     assert!(vec1.insert(64));
 180     vec1.grow(128);
 181     assert!(vec1.contains(3));
 182     assert!(vec1.contains(5));
 183     assert!(vec1.contains(64));
 184     assert!(!vec1.contains(126));
 185 }
 186
 187 #[test]
 188 fn matrix_intersection() {
 189     let mut vec1 = BitMatrix::new(200);
 190
 191     // (*) Elements reachable from both 2 and 65.
 192
 193     vec1.add(2, 3);
 194     vec1.add(2, 6);
 195     vec1.add(2, 10); // (*)
 196     vec1.add(2, 64); // (*)
 197     vec1.add(2, 65);
 198     vec1.add(2, 130);
 199     vec1.add(2, 160); // (*)
 200
 201     vec1.add(64, 133);
 202
 203     vec1.add(65, 2);
 204     vec1.add(65, 8);
 205     vec1.add(65, 10); // (*)
 206     vec1.add(65, 64); // (*)
 207     vec1.add(65, 68);
 208     vec1.add(65, 133);
 209     vec1.add(65, 160); // (*)
 210
 211     let intersection = vec1.intersection(2, 64);
 212     assert!(intersection.is_empty());
 213
 214     let intersection = vec1.intersection(2, 65);
 215     assert_eq!(intersection, &[10, 64, 160]);
 216 }