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 std::iter;
  12
  13 /// A very simple BitVector type.
  14 pub struct BitVector {
  15     data: Vec<u64>
  16 }
  17
  18 impl BitVector {
  19     pub fn new(num_bits: usize) -> BitVector {
  20         let num_words = (num_bits + 63) / 64;
  21         BitVector { data: iter::repeat(0).take(num_words).collect() }
  22     }
  23
  24     fn word_mask(&self, bit: usize) -> (usize, u64) {
  25         let word = bit / 64;
  26         let mask = 1 << (bit % 64);
  27         (word, mask)
  28     }
  29
  30     pub fn contains(&self, bit: usize) -> bool {
  31         let (word, mask) = self.word_mask(bit);
  32         (self.data[word] & mask) != 0
  33     }
  34
  35     pub fn insert(&mut self, bit: usize) -> bool {
  36         let (word, mask) = self.word_mask(bit);
  37         let data = &mut self.data[word];
  38         let value = *data;
  39         *data = value | mask;
  40         (value | mask) != value
  41     }
  42 }