]> git.proxmox.com Git - rustc.git/blob - src/librustc_borrowck/bitslice.rs
Imported Upstream version 1.9.0+dfsg1
[rustc.git] / src / librustc_borrowck / bitslice.rs
1 // Copyright 2012-2016 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::mem;
12
13 /// `BitSlice` provides helper methods for treating a `[usize]`
14 /// as a bitvector.
15 pub trait BitSlice {
16 fn clear_bit(&mut self, idx: usize) -> bool;
17 fn set_bit(&mut self, idx: usize) -> bool;
18 fn get_bit(&self, idx: usize) -> bool;
19 }
20
21 impl BitSlice for [usize] {
22 /// Clears bit at `idx` to 0; returns true iff this changed `self.`
23 fn clear_bit(&mut self, idx: usize) -> bool {
24 let words = self;
25 debug!("clear_bit: words={} idx={}",
26 bits_to_string(words, words.len() * mem::size_of::<usize>()), bit_str(idx));
27 let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
28 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
29 let oldv = words[word];
30 let newv = oldv & !bit_mask;
31 words[word] = newv;
32 oldv != newv
33 }
34
35 /// Sets bit at `idx` to 1; returns true iff this changed `self.`
36 fn set_bit(&mut self, idx: usize) -> bool {
37 let words = self;
38 debug!("set_bit: words={} idx={}",
39 bits_to_string(words, words.len() * mem::size_of::<usize>()), bit_str(idx));
40 let BitLookup { word, bit_in_word, bit_mask } = bit_lookup(idx);
41 debug!("word={} bit_in_word={} bit_mask={}", word, bit_in_word, bit_mask);
42 let oldv = words[word];
43 let newv = oldv | bit_mask;
44 words[word] = newv;
45 oldv != newv
46 }
47
48 /// Extracts value of bit at `idx` in `self`.
49 fn get_bit(&self, idx: usize) -> bool {
50 let words = self;
51 let BitLookup { word, bit_mask, .. } = bit_lookup(idx);
52 (words[word] & bit_mask) != 0
53 }
54 }
55
56 struct BitLookup {
57 /// An index of the word holding the bit in original `[usize]` of query.
58 word: usize,
59 /// Index of the particular bit within the word holding the bit.
60 bit_in_word: usize,
61 /// Word with single 1-bit set corresponding to where the bit is located.
62 bit_mask: usize,
63 }
64
65 #[inline]
66 fn bit_lookup(bit: usize) -> BitLookup {
67 let usize_bits = mem::size_of::<usize>() * 8;
68 let word = bit / usize_bits;
69 let bit_in_word = bit % usize_bits;
70 let bit_mask = 1 << bit_in_word;
71 BitLookup { word: word, bit_in_word: bit_in_word, bit_mask: bit_mask }
72 }
73
74
75 fn bit_str(bit: usize) -> String {
76 let byte = bit >> 8;
77 let lobits = 1 << (bit & 0xFF);
78 format!("[{}:{}-{:02x}]", bit, byte, lobits)
79 }
80
81 pub fn bits_to_string(words: &[usize], bytes: usize) -> String {
82 let mut result = String::new();
83 let mut sep = '[';
84
85 // Note: this is a little endian printout of bytes.
86
87 let mut i = 0;
88 for &word in words.iter() {
89 let mut v = word;
90 for _ in 0..mem::size_of::<usize>() {
91 let byte = v & 0xFF;
92 if i >= bytes {
93 assert!(byte == 0);
94 } else {
95 result.push(sep);
96 result.push_str(&format!("{:02x}", byte));
97 }
98 v >>= 8;
99 i += 1;
100 sep = '-';
101 }
102 }
103 result.push(']');
104 return result
105 }