haz-alloc-core 0.4.0

A general-purpose allocator written in Rust, without system symbols
Documentation 
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
84
85
86
87
88
89
90
91
92
93
94

use core::{iter, mem};

#[cfg(test)]
mod tests;

const USIZE_BITS: usize = 8 * mem::size_of::<usize>();

#[inline]
pub fn find_zero(set: &[usize]) -> Option<usize> {
    set.iter()
        .copied()
        .enumerate()
        .find(|(_, v)| *v != !0)
        .map(|(i, v)| i * USIZE_BITS + v.trailing_ones() as usize)
}

pub fn find_zero_run(set: &[usize], len: usize) -> Option<usize> {
    let mut run_start = None;
    for (i, x) in set.iter().enumerate() {
        for j in 0..USIZE_BITS {
            if x & (1 << j) != 0 {
                run_start = None;
                continue;
            }

            let (i0, j0) = *run_start.get_or_insert((i, j));
            if (i - i0) * USIZE_BITS + j - j0 + 1 >= len {
                return Some(i0 * USIZE_BITS + j0);
            }
        }
    }

    None
}

pub fn is_zero_range(set: &[usize], index: usize, len: usize) -> bool {
    set.iter()
        .copied()
        .zip(mask(index, len))
        .skip(index / USIZE_BITS)
        .take((index + len) / USIZE_BITS + 1)
        .all(|(x, y)| x & y == 0)
}

#[inline]
pub fn set(set: &mut [usize], index: usize) {
    set[index / USIZE_BITS] |= 1 << (index % USIZE_BITS);
}

#[inline]
pub fn clear(set: &mut [usize], index: usize) {
    set[index / USIZE_BITS] &= !(1 << (index % USIZE_BITS));
}

pub fn set_range(set: &mut [usize], index: usize, len: usize) {
    for (x, mask) in set
        .iter_mut()
        .zip(mask(index, len))
        .skip(index / USIZE_BITS)
        .take((index + len) / USIZE_BITS + 1)
    {
        *x |= mask;
    }
}

pub fn clear_range(set: &mut [usize], index: usize, len: usize) {
    for (x, mask) in set
        .iter_mut()
        .zip(mask(index, len))
        .skip(index / USIZE_BITS)
        .take((index + len) / USIZE_BITS + 1)
    {
        *x &= !mask;
    }
}

#[inline]
fn mask(index: usize, len: usize) -> impl Iterator<Item = usize> {
    iter::repeat(0)
        .take(index / USIZE_BITS)
        .chain(
            ((index / USIZE_BITS)..=((index + len) / USIZE_BITS)).map(move |i| {
                let mut mask: usize = !0;
                if i == index / USIZE_BITS {
                    mask &= !0 << (index % USIZE_BITS);
                }
                if i == (index + len) / USIZE_BITS {
                    mask &= !(!0 << ((index + len) % USIZE_BITS));
                }
                mask
            }),
        )
        .chain(iter::repeat(0))
}