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 {
  44                 changed = true;
  45             }
  46         }
  47         changed
  48     }
  49
  50     pub fn grow(&mut self, num_bits: usize) {
  51         let num_words = u64s(num_bits);
  52         let extra_words = self.data.len() - num_words;
  53         self.data.extend((0..extra_words).map(|_| 0));
  54     }
  55
  56     /// Iterates over indexes of set bits in a sorted order
  57     pub fn iter<'a>(&'a self) -> BitVectorIter<'a> {
  58         BitVectorIter {
  59             iter: self.data.iter(),
  60             current: 0,
  61             idx: 0,
  62         }
  63     }
  64 }
  65
  66 pub struct BitVectorIter<'a> {
  67     iter: ::std::slice::Iter<'a, u64>,
  68     current: u64,
  69     idx: usize,
  70 }
  71
  72 impl<'a> Iterator for BitVectorIter<'a> {
  73     type Item = usize;
  74     fn next(&mut self) -> Option<usize> {
  75         while self.current == 0 {
  76             self.current = if let Some(&i) = self.iter.next() {
  77                 if i == 0 {
  78                     self.idx += 64;
  79                     continue;
  80                 } else {
  81                     self.idx = u64s(self.idx) * 64;
  82                     i
  83                 }
  84             } else {
  85                 return None;
  86             }
  87         }
  88         let offset = self.current.trailing_zeros() as usize;
  89         self.current >>= offset;
  90         self.current >>= 1; // shift otherwise overflows for 0b1000_0000_…_0000
  91         self.idx += offset + 1;
  92         return Some(self.idx - 1);
  93     }
  94 }
  95
  96 /// A "bit matrix" is basically a square matrix of booleans
  97 /// represented as one gigantic bitvector. In other words, it is as if
  98 /// you have N bitvectors, each of length N. Note that `elements` here is `N`/
  99 #[derive(Clone)]
 100 pub struct BitMatrix {
 101     elements: usize,
 102     vector: Vec<u64>,
 103 }
 104
 105 impl BitMatrix {
 106     // Create a new `elements x elements` matrix, initially empty.
 107     pub fn new(elements: usize) -> BitMatrix {
 108         // For every element, we need one bit for every other
 109         // element. Round up to an even number of u64s.
 110         let u64s_per_elem = u64s(elements);
 111         BitMatrix {
 112             elements: elements,
 113             vector: vec![0; elements * u64s_per_elem],
 114         }
 115     }
 116
 117     /// The range of bits for a given element.
 118     fn range(&self, element: usize) -> (usize, usize) {
 119         let u64s_per_elem = u64s(self.elements);
 120         let start = element * u64s_per_elem;
 121         (start, start + u64s_per_elem)
 122     }
 123
 124     pub fn add(&mut self, source: usize, target: usize) -> bool {
 125         let (start, _) = self.range(source);
 126         let (word, mask) = word_mask(target);
 127         let mut vector = &mut self.vector[..];
 128         let v1 = vector[start + word];
 129         let v2 = v1 | mask;
 130         vector[start + word] = v2;
 131         v1 != v2
 132     }
 133
 134     /// Do the bits from `source` contain `target`?
 135     ///
 136     /// Put another way, if the matrix represents (transitive)
 137     /// reachability, can `source` reach `target`?
 138     pub fn contains(&self, source: usize, target: usize) -> bool {
 139         let (start, _) = self.range(source);
 140         let (word, mask) = word_mask(target);
 141         (self.vector[start + word] & mask) != 0
 142     }
 143
 144     /// Returns those indices that are reachable from both `a` and
 145     /// `b`. This is an O(n) operation where `n` is the number of
 146     /// elements (somewhat independent from the actual size of the
 147     /// intersection, in particular).
 148     pub fn intersection(&self, a: usize, b: usize) -> Vec<usize> {
 149         let (a_start, a_end) = self.range(a);
 150         let (b_start, b_end) = self.range(b);
 151         let mut result = Vec::with_capacity(self.elements);
 152         for (base, (i, j)) in (a_start..a_end).zip(b_start..b_end).enumerate() {
 153             let mut v = self.vector[i] & self.vector[j];
 154             for bit in 0..64 {
 155                 if v == 0 {
 156                     break;
 157                 }
 158                 if v & 0x1 != 0 {
 159                     result.push(base * 64 + bit);
 160                 }
 161                 v >>= 1;
 162             }
 163         }
 164         result
 165     }
 166
 167     /// Add the bits from `read` to the bits from `write`,
 168     /// return true if anything changed.
 169     ///
 170     /// This is used when computing transitive reachability because if
 171     /// you have an edge `write -> read`, because in that case
 172     /// `write` can reach everything that `read` can (and
 173     /// potentially more).
 174     pub fn merge(&mut self, read: usize, write: usize) -> bool {
 175         let (read_start, read_end) = self.range(read);
 176         let (write_start, write_end) = self.range(write);
 177         let vector = &mut self.vector[..];
 178         let mut changed = false;
 179         for (read_index, write_index) in (read_start..read_end).zip(write_start..write_end) {
 180             let v1 = vector[write_index];
 181             let v2 = v1 | vector[read_index];
 182             vector[write_index] = v2;
 183             changed = changed | (v1 != v2);
 184         }
 185         changed
 186     }
 187 }
 188
 189 fn u64s(elements: usize) -> usize {
 190     (elements + 63) / 64
 191 }
 192
 193 fn word_mask(index: usize) -> (usize, u64) {
 194     let word = index / 64;
 195     let mask = 1 << (index % 64);
 196     (word, mask)
 197 }
 198
 199 #[test]
 200 fn bitvec_iter_works() {
 201     let mut bitvec = BitVector::new(100);
 202     bitvec.insert(1);
 203     bitvec.insert(10);
 204     bitvec.insert(19);
 205     bitvec.insert(62);
 206     bitvec.insert(63);
 207     bitvec.insert(64);
 208     bitvec.insert(65);
 209     bitvec.insert(66);
 210     bitvec.insert(99);
 211     assert_eq!(bitvec.iter().collect::<Vec<_>>(),
 212                [1, 10, 19, 62, 63, 64, 65, 66, 99]);
 213 }
 214
 215 #[test]
 216 fn bitvec_iter_works_2() {
 217     let mut bitvec = BitVector::new(300);
 218     bitvec.insert(1);
 219     bitvec.insert(10);
 220     bitvec.insert(19);
 221     bitvec.insert(62);
 222     bitvec.insert(66);
 223     bitvec.insert(99);
 224     bitvec.insert(299);
 225     assert_eq!(bitvec.iter().collect::<Vec<_>>(),
 226                [1, 10, 19, 62, 66, 99, 299]);
 227
 228 }
 229
 230 #[test]
 231 fn bitvec_iter_works_3() {
 232     let mut bitvec = BitVector::new(319);
 233     bitvec.insert(0);
 234     bitvec.insert(127);
 235     bitvec.insert(191);
 236     bitvec.insert(255);
 237     bitvec.insert(319);
 238     assert_eq!(bitvec.iter().collect::<Vec<_>>(), [0, 127, 191, 255, 319]);
 239 }
 240
 241 #[test]
 242 fn union_two_vecs() {
 243     let mut vec1 = BitVector::new(65);
 244     let mut vec2 = BitVector::new(65);
 245     assert!(vec1.insert(3));
 246     assert!(!vec1.insert(3));
 247     assert!(vec2.insert(5));
 248     assert!(vec2.insert(64));
 249     assert!(vec1.insert_all(&vec2));
 250     assert!(!vec1.insert_all(&vec2));
 251     assert!(vec1.contains(3));
 252     assert!(!vec1.contains(4));
 253     assert!(vec1.contains(5));
 254     assert!(!vec1.contains(63));
 255     assert!(vec1.contains(64));
 256 }
 257
 258 #[test]
 259 fn grow() {
 260     let mut vec1 = BitVector::new(65);
 261     assert!(vec1.insert(3));
 262     assert!(!vec1.insert(3));
 263     assert!(vec1.insert(5));
 264     assert!(vec1.insert(64));
 265     vec1.grow(128);
 266     assert!(vec1.contains(3));
 267     assert!(vec1.contains(5));
 268     assert!(vec1.contains(64));
 269     assert!(!vec1.contains(126));
 270 }
 271
 272 #[test]
 273 fn matrix_intersection() {
 274     let mut vec1 = BitMatrix::new(200);
 275
 276     // (*) Elements reachable from both 2 and 65.
 277
 278     vec1.add(2, 3);
 279     vec1.add(2, 6);
 280     vec1.add(2, 10); // (*)
 281     vec1.add(2, 64); // (*)
 282     vec1.add(2, 65);
 283     vec1.add(2, 130);
 284     vec1.add(2, 160); // (*)
 285
 286     vec1.add(64, 133);
 287
 288     vec1.add(65, 2);
 289     vec1.add(65, 8);
 290     vec1.add(65, 10); // (*)
 291     vec1.add(65, 64); // (*)
 292     vec1.add(65, 68);
 293     vec1.add(65, 133);
 294     vec1.add(65, 160); // (*)
 295
 296     let intersection = vec1.intersection(2, 64);
 297     assert!(intersection.is_empty());
 298
 299     let intersection = vec1.intersection(2, 65);
 300     assert_eq!(intersection, &[10, 64, 160]);
 301 }