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