dary/
bit_cache.rs

1/// 空いているindexをbitで管理する
2/// 0: 空, 1: 空でない
3pub struct BitCache {
4    cache: Vec<i64>,
5    start: usize,
6}
7
8impl BitCache {
9    const BIT_MASK: usize = 0b111111; // 63
10    const BIT_LEN: usize = 64;
11    const BIT_CNT: usize = 6;
12
13    pub fn new() -> BitCache {
14        BitCache {
15            cache: vec![0; 65535],
16            start: 4, // utf8想定なので256 / 64
17        }
18    }
19
20    /*
21    pub fn debug_print(&self) {
22        println!("start = {}", self.start);
23    }
24    */
25
26    /// 配列の空き状態を見て探索開始indexを進める
27    pub fn update_start(&mut self) {
28        for &bits in &self.cache[self.start..] {
29            if bits.count_ones() >= 60 {
30                // 95%以上埋まっていたらstart位置を進める
31                self.start += 1;
32            } else {
33                break;
34            }
35        }
36    }
37
38    /// 指定されたインデックスを取得する
39    /// 空なら0, 空でないなら0以外
40    ///
41    /// # Arguments
42    ///
43    /// * `idx`- 調べたいindex
44    pub fn get(&self, idx: usize) -> usize {
45        let arr_idx: usize = idx >> Self::BIT_CNT; // idx / Self::BIT_LEN
46        let bit_idx: usize = idx & Self::BIT_MASK; // idx % Self::BIT_LEN
47        if arr_idx < self.cache.len() {
48            (self.cache[arr_idx] as usize) & (1 << bit_idx)
49        } else {
50            0
51        }
52    }
53
54    /// 指定されたインデックスのビットを立てる
55    ///
56    /// # Arguments
57    ///
58    /// * `idx`- ビットを立てたいindex
59    pub fn set(&mut self, idx: usize) {
60        let arr_idx: usize = idx >> Self::BIT_CNT; // idx / Self::BIT_LEN
61        let bit_idx: usize = idx & Self::BIT_MASK; // idx % Self::BIT_LEN
62        if arr_idx >= self.cache.len() {
63            self.cache.resize(arr_idx * 2, 0);
64        }
65        self.cache[arr_idx] |= 1 << bit_idx;
66    }
67
68    /// offset以降の最初の空いているインデックスを返す
69    ///
70    /// # Arguments
71    ///
72    /// * `offset`- 探索開始インデックス
73    pub fn find_empty_idx(&self, offset: usize) -> usize {
74        let arr_idx: usize = self.start + (offset >> Self::BIT_CNT); // idx / Self::BIT_LEN
75        let bit_idx: usize = offset & Self::BIT_MASK; // idx % Self::BIT_LEN
76        if arr_idx >= self.cache.len() {
77            return offset + self.start * 64;
78        }
79        // offset よりも前のビットを0埋めするためのマスク
80        let mut mask: i64 = -1 << bit_idx;
81        let mut cnt = arr_idx;
82        for &e in &self.cache[arr_idx..] {
83            // bit反転しているので、0が要素あり、1が空
84            let bits = (e ^ -1) & mask;
85            if bits != 0 {
86                // 右から連続した0の個数を数える。0の個数が空のindexとなる
87                let zeros = bits.trailing_zeros() as usize;
88                return cnt * Self::BIT_LEN + zeros;
89            }
90            mask = -1;
91            cnt += 1;
92        }
93        self.cache.len() * Self::BIT_LEN
94    }
95
96    /// cacheの中で一番最後に現れる1のindexを返す
97    pub fn last_index_of_one(&self) -> Option<usize> {
98        for (i, &bits) in self.cache.iter().enumerate().rev() {
99            if bits != 0 {
100                // 左から連続した0の個数を数える。
101                // (Self::BIT_LEN - (0の個数 + 1)) はビット内での1のindex
102                let zeros = bits.leading_zeros() as usize;
103                return Some((i * Self::BIT_LEN) + (Self::BIT_LEN - (zeros + 1)));
104            }
105        }
106        None
107    }
108}
109
110#[cfg(test)]
111mod tests {
112    use super::*;
113
114    #[test]
115    fn test_set_get() {
116        let mut bit_cache = BitCache::new();
117        bit_cache.set(0);
118        bit_cache.set(100);
119        bit_cache.set(100000000);
120        // セットしたindexが登録されている
121        assert_eq!(false, bit_cache.get(0) == 0);
122        assert_eq!(false, bit_cache.get(100) == 0);
123        assert_eq!(false, bit_cache.get(100000000) == 0);
124        // セットしていないindexは登録されていない
125        assert_eq!(true, bit_cache.get(1000000) == 0);
126    }
127
128    #[test]
129    fn test_find_empty_idx() {
130        let mut bit_cache = BitCache::new();
131        // 探索開始位置=256。最初に見つかる空きノードは256
132        assert_eq!(256, bit_cache.find_empty_idx(0));
133
134        for i in 0..1000 {
135            if i % 100 != 0 {
136                bit_cache.set(i);
137            }
138        }
139        // 探索開始位置=256。最初に見つかる空きノードは300
140        assert_eq!(300, bit_cache.find_empty_idx(0));
141
142        // 探索開始位置=960。最初に見つかる空きノードは1000
143        bit_cache.update_start();
144        assert_eq!(1000, bit_cache.find_empty_idx(0));
145
146        // 探索開始位置=960、オフセット=50なので最初に見つかる空きノードは1010になる
147        // 探索開始位置=960。オフセット=50。最初に見つかる空きノードは1010
148        assert_eq!(1010, bit_cache.find_empty_idx(50));
149
150        // 探索開始位置=960。オフセット=1000000。最初に見つかる空きノードは1000960
151        assert_eq!(1000960, bit_cache.find_empty_idx(1000000));
152
153        // 探索開始位置=960。オフセット=10000000。配列の範囲外なので空きノードは1000960
154        assert_eq!(10000960, bit_cache.find_empty_idx(10000000));
155    }
156
157    #[test]
158    fn test_last_index_of_one() {
159        let mut bit_cache = BitCache::new();
160        assert_eq!(None, bit_cache.last_index_of_one());
161        bit_cache.set(0);
162        assert_eq!(Some(0), bit_cache.last_index_of_one());
163        bit_cache.set(63);
164        assert_eq!(Some(63), bit_cache.last_index_of_one());
165        bit_cache.set(300);
166        assert_eq!(Some(300), bit_cache.last_index_of_one());
167    }
168}
dary/bit_cache.rs

dary/
bit_cache.rs
