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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83

// Licensed under the Apache License, Version 2.0 or the MIT License.
// SPDX-License-Identifier: Apache-2.0 OR MIT
// Copyright Tock Contributors 2022.

const BITMAP_SIZE: usize = 20;

pub struct Bitmap {
    map: [u8; BITMAP_SIZE],
}

impl Bitmap {
    pub fn new() -> Bitmap {
        Bitmap {
            map: [0; BITMAP_SIZE],
        }
    }

    pub fn clear(&mut self) {
        for i in 0..self.map.len() {
            self.map[i] = 0;
        }
    }

    pub fn clear_bit(&mut self, idx: usize) {
        let map_idx = idx / 8;
        self.map[map_idx] &= !(1 << (idx % 8));
    }

    pub fn set_bit(&mut self, idx: usize) {
        let map_idx = idx / 8;
        self.map[map_idx] |= 1 << (idx % 8);
    }

    // Sets bits from start_idx (inclusive) to end_idx (exclusive).
    // Returns false if any bits set overlap with already set bits,
    // true otherwise.

    // Returns true if successfully set bits, returns false if the bits
    // overlapped with already set bits
    // Note that each bit represents a multiple of 8 bytes (as everything
    // must be in 8-byte groups), and thus we can store 8*8 = 64 "bytes" per
    // byte in the bitmap.
    pub fn set_bits(&mut self, start_idx: usize, end_idx: usize) -> bool {
        if start_idx > end_idx {
            return false;
        }
        let start_byte_idx = start_idx / 8;
        let end_byte_idx = end_idx / 8;
        let first = 0xff << (start_idx % 8);
        let second = if end_idx % 8 == 0 {
            0x00
        } else {
            0xff >> (8 - (end_idx % 8))
        };
        if start_byte_idx == end_byte_idx {
            let result = (self.map[start_byte_idx] & (first & second)) == 0;
            self.map[start_byte_idx] |= first & second;
            result
        } else {
            let mut result = (self.map[start_byte_idx] & first) == 0;
            result = result && ((self.map[end_byte_idx] & second) == 0);
            self.map[start_byte_idx] |= first;
            self.map[end_byte_idx] |= second;
            // Set all bytes between start and end bytes.
            for i in start_byte_idx + 1..end_byte_idx {
                result = result && (self.map[i] == 0);
                self.map[i] = 0xff;
            }
            result
        }
    }

    pub fn is_complete(&self, total_length: usize) -> bool {
        let mut result = true;
        for i in 0..total_length / 8 {
            result = result && (self.map[i] == 0xff);
        }
        // Check last byte.
        let mask = 0xff >> (8 - (total_length % 8));
        result = result && (self.map[total_length / 8] == mask);
        result
    }
}