customizable_buddy/
bitmap.rs

1use crate::{BuddyCollection, BuddyLine, OligarchyCollection};
2use core::fmt;
3
4/// 用一个 usize 作为位图保存占用情况的伙伴行。
5///
6/// - 非侵入式
7/// - 静态分配，容量有限
8pub struct UsizeBuddy {
9    bits: usize,
10    base: usize,
11}
12
13impl UsizeBuddy {
14    const SIZE: usize = usize::BITS as usize;
15
16    #[inline]
17    fn take(&mut self, idx: usize) -> bool {
18        let bit = 1usize << idx;
19        let bits = self.bits;
20        self.bits &= !bit;
21        bits & bit == bit
22    }
23}
24
25impl BuddyLine for UsizeBuddy {
26    const EMPTY: Self = Self { bits: 0, base: 0 };
27
28    #[inline]
29    fn init(&mut self, _order: usize, base: usize) {
30        self.base = base;
31    }
32
33    #[inline]
34    fn take(&mut self, idx: usize) -> bool {
35        self.take(idx - self.base)
36    }
37}
38
39impl OligarchyCollection for UsizeBuddy {
40    #[inline]
41    fn take_any(&mut self, align_order: usize, count: usize) -> Option<usize> {
42        let count = (1 << count) - 1;
43        let align = 1usize << align_order;
44        let mut i = 0;
45        loop {
46            let mask = count << i;
47            if self.bits & mask == mask {
48                self.bits &= !mask;
49                return Some(self.base + i);
50            }
51            i += align;
52            if i >= usize::BITS as usize {
53                return None;
54            }
55        }
56    }
57
58    #[inline]
59    fn put(&mut self, idx: usize) {
60        self.bits |= 1 << (idx - self.base);
61    }
62}
63
64impl BuddyCollection for UsizeBuddy {
65    #[inline]
66    fn take_any(&mut self, align_order: usize) -> Option<usize> {
67        let align = 1usize << align_order;
68        let mut i = 0;
69        loop {
70            let mask = 1 << i;
71            if self.bits & mask == mask {
72                self.bits &= !mask;
73                return Some(self.base + i);
74            }
75            i += align;
76            if i >= usize::BITS as usize {
77                return None;
78            }
79        }
80    }
81
82    #[inline]
83    fn put(&mut self, idx: usize) -> Option<usize> {
84        let idx = idx - self.base;
85        debug_assert!(idx < Self::SIZE, "index out of bound");
86        let buddy = idx ^ 1;
87        if self.take(buddy) {
88            Some(idx << 1)
89        } else {
90            self.bits |= 1 << idx;
91            None
92        }
93    }
94}
95
96impl fmt::Debug for UsizeBuddy {
97    #[inline]
98    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
99        write!(f, "{:b}", self.bits)
100    }
101}
customizable_buddy/bitmap.rs

customizable_buddy/
bitmap.rs
