meowalloc 0.1.0

Toy allocator written in pure rust, with concurrency in mind
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
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

use core::{alloc::AllocError, cmp::Ordering, marker::PhantomData, num::NonZero, ptr::NonNull};

#[derive(Debug, PartialEq)]
pub enum BlockError {
    Overflow,
    NotAdjacent,
    InvalidIndex,
    TooSmall,
}


#[derive(Debug, PartialEq)]
pub struct Block {
    pub ptr: NonNull<u8>,
    pub size: NonZero<usize>,
}

impl Block {
    pub fn new(ptr: NonNull<u8>, size: NonZero<usize>) -> Self {
        Self { ptr, size }
    }
    
    #[inline(always)]
    pub fn is_adjacent(&self, other: &Self) -> bool {
        self.is_lesser_adjacent(other) || self.is_greater_adjacent(other)
    }
    
    #[inline(always)]
    pub fn is_lesser_adjacent(&self, other: &Self) -> bool {
        unsafe { self.ptr.add(self.size.get()) == other.ptr }
    }
    
    #[inline(always)]
    pub fn is_greater_adjacent(&self, other: &Self) -> bool {
        unsafe { other.ptr.add(other.size.get()) == self.ptr }
    }

    #[inline(always)]
    pub fn merge_ordered<'a>(&'a self, other: &'a Self) -> Option<(&'a Self, &'a Self)> {
        if self.is_lesser_adjacent(other) {
            Some((self, other))
        } else if self.is_greater_adjacent(other) {
            Some((other, self))
        } else {
            None
        }
    }

    #[inline(always)]
    pub fn cmp_adjacent(&self, other: &Self) -> Option<Ordering> {
        if self.is_greater_adjacent(other) {
            Some(Ordering::Greater)
        } else if self.is_lesser_adjacent(other) {
            Some(Ordering::Less)
        } else {
            None
        }
    }
}

#[derive(Debug)]
pub struct BlockIdxGuard<'a>(usize, PhantomData<&'a ()>);

impl<'a> BlockIdxGuard<'a> {
    pub fn new(idx: usize) -> Self { Self(idx, PhantomData) }
}

pub unsafe trait ExtractIdx<T> {
    unsafe fn extract(&self) -> T;
}

unsafe impl<'a> ExtractIdx<usize> for BlockIdxGuard<'a> {
    /// ExtractIdxs the block index from the guard
    ///
    /// # Safety:
    /// The caller must ensure the block list is not mutated in a way
    /// that invalidates the returned index, for the duration of the index's lifetime
    unsafe fn extract(&self) -> usize { self.0 }
}

unsafe impl<'a> ExtractIdx<(usize, usize)> for (BlockIdxGuard<'a>, BlockIdxGuard<'a>) {
    unsafe fn extract(&self) -> (usize, usize) {
        unsafe { (self.0.extract(), self.1.extract()) }
    }
}

impl From<BlockError> for AllocError {
    fn from(_: BlockError) -> Self { AllocError }
}

#[test]
fn cmp_adjacent() {
    let (p1, p2, p3, p4) = (
        NonNull::new(1 as *mut u8).unwrap(),
        NonNull::new(2 as *mut u8).unwrap(),
        NonNull::new(5 as *mut u8).unwrap(),
        NonNull::new(12 as *mut u8).unwrap()
    );
    let (b1, b2, b3, b4) = (
        Block { ptr: p1, size: NonZero::new(1).unwrap() },
        Block { ptr: p2, size: NonZero::new(3).unwrap() },
        Block { ptr: p3, size: NonZero::new(1).unwrap() },
        Block { ptr: p4, size: NonZero::new(1).unwrap() },
    );

    assert_eq!(b1.cmp_adjacent(&b4), None);
    assert_eq!(b2.cmp_adjacent(&b4), None);
    assert_eq!(b3.cmp_adjacent(&b4), None);
    assert_eq!(b4.cmp_adjacent(&b1), None);
    assert_eq!(b4.cmp_adjacent(&b1), None);
    assert_eq!(b4.cmp_adjacent(&b1), None);
    
    assert_eq!(b1.cmp_adjacent(&b2), Some(Ordering::Less));
    assert_eq!(b1.cmp_adjacent(&b3), None);
    assert_eq!(b2.cmp_adjacent(&b1), Some(Ordering::Greater));
    assert_eq!(b2.cmp_adjacent(&b3), Some(Ordering::Less));
    assert_eq!(b3.cmp_adjacent(&b2), Some(Ordering::Greater));
    assert_eq!(b3.cmp_adjacent(&b1), None);

}