登录
原文实在是太NOI-istic。小生在此抛砖引玉给出一个人类可读版本的：
// root at one as routine
// inline helper funtion, they can be better to be written in marco or association function
impl SegmentTreeAllocator {
#[inline]
fn left_child(&self, idx : usize) -> usize {idx << 1}
#[inline]
fn right_child(&self, idx : usize) -> usize {(idx << 1) | 1}
#[inline]
fn update(&mut self, idx : usize) {
let mut temp = idx >> 1;
while temp > 0 {
// if left child and right child is full, then nodes[p] is full
self.nodes[temp] = self.nodes[self.left_child(temp)] & self.nodes[self.right_child(temp)];
temp >>= 1;
}
}
}
// consturct a complete binary tree and put all real node into leaves.
// so [l,r) length assignment needs pow(2, log(2,r-l)+1) leaves to store, from lfet most child to right
impl SegmentTreeAllocator {
// init [l,r) interval
pub fn init(&mut self, l : usize, r : usize) {
self.offset = l;
self.total = r - l; // total may be not a power of 2
// compute the first key index
self.leaf_begin = 1;
// why add 2?
// one for root start from one instead of zero
// another one for total number is contained, say we have 10 number,
// naturally, the condition shall be less than 11, you need to take 10 into account
while self.leaf_begin < self.total + 2 {
self.leaf_begin <<= 1;
}
// since [l,r) may not be aligned, we need to let extra element marked as invalid
// on level of leaf, you have pow(2,leaf_begin)'s leaves.
// so total elements of this complete binary tree should be
// 1 + 2 + 4 + ... + pow(2,leaf_begin)
// pow(2,leaf_begin+1) - 1, namely range from [1,pow(2,leaf_begin+1)
for i in (1..(self.leaf_begin << 1)) {self.nodes[i] = 1;}
// avaiable part, please notice it shall start from left child, which is even
// different from origin version,
// so you can see above self.offset is l, not l-1
for i in (0..self.total) {self.nodes[self.leaf_begin + i] = 0;}
// update parents who are available
for i in (1..self.leaf_begin).rev() {
self.nodes[i] = self.nodes[self.left_child(i)] & self.nodes[self.right_child(i)];
}
}
// allocate a physical page, return a physical page number
pub fn alloc(&mut self) -> usize {
// assume that we never run out of physical memory
if self.nodes[1] == 1 {
panic!("physical memory depleted!");
}
// from top, find first available page
let mut p = 1;
while p < self.leaf_begin {
if self.nodes[self.left_child(p)] == 0 {
p = self.left_child(p);
} else{
p = self.right_child(p);
}
}
// since it has offset, we need to compute
let result = (p - self.leaf_begin) + self.offset;
// it has been allocated, we need to mark it as used
self.nodes[p] = 1;
// update its ancestor
self.update(p);
result
}
// recycle the target page
pub fn dealloc(&mut self, idx : usize) {
// notice there is a difference between alloc and de-alloc
// the operation order is inversed.
let pos_in_tree = (idx - self.offset) + self.leaf_begin;
// we recycle a used one
assert!(self.nodes[pos_in_tree] == 1);
self.nodes[pos_in_tree] = 0;
self.update(pos_in_tree);
}
}
// singleton
pub static SEGMENT_TREE_ALLOCATOR: Mutex<SegmentTreeAllocator> = Mutex::new(SegmentTreeAllocator {
nodes: [0; MAX_PHYSICAL_PAGES << 1],
leaf_begin: 0,
total: 0,
offset: 0
});
