blob: f2f4a69d882b45c671d6538693d2911e7a4d15ce (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
// Copyright 2015 The Rust Project Developers. See the COPYRIGHT
// file at the top-level directory of this distribution and at
// http://rust-lang.org/COPYRIGHT.
//
// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
// option. This file may not be copied, modified, or distributed
// except according to those terms.
/// A very simple BitVector type.
pub struct BitVector {
data: Vec<u64>
}
impl BitVector {
pub fn new(num_bits: usize) -> BitVector {
let num_words = (num_bits + 63) / 64;
BitVector { data: vec![0; num_words] }
}
fn word_mask(&self, bit: usize) -> (usize, u64) {
let word = bit / 64;
let mask = 1 << (bit % 64);
(word, mask)
}
pub fn contains(&self, bit: usize) -> bool {
let (word, mask) = self.word_mask(bit);
(self.data[word] & mask) != 0
}
pub fn insert(&mut self, bit: usize) -> bool {
let (word, mask) = self.word_mask(bit);
let data = &mut self.data[word];
let value = *data;
*data = value | mask;
(value | mask) != value
}
}
|
