avl/
avl.rs

1//！just using for avl tree test, trying to allocate and deallocate node by a different ways to make more node in one line at the same times
2use customizable_buddy::{AvlBuddy, BuddyAllocator, BuddyError, UsizeBuddy};
3use std::{
4    alloc::Layout,
5    ptr::{NonNull, addr_of, addr_of_mut, null_mut},
6    time::Instant,
7};
8
9type Allocator<const N: usize> = BuddyAllocator<N, UsizeBuddy, AvlBuddy>;
10
11#[repr(C, align(4096))]
12struct Page([u8; 4096]);
13
14impl Page {
15    const ZERO: Self = Self([0; 4096]);
16}
17
18const DIVICE_PIECE: usize = 2;
19/// 256 MiB
20static mut MEMORY: [Page; 65536] = [Page::ZERO; 65536];
21
22fn main() -> Result<(), BuddyError> {
23    // 创建全局分配器
24    let mut allocator = Allocator::<12>::new();
25    // 从本机操作系统获取一块内存给程序
26    let ptr = NonNull::new(addr_of_mut!(MEMORY).cast::<u8>()).unwrap();
27    let len = size_of_val(unsafe { &*addr_of!(MEMORY) });
28    // 使用最小阶数和初始地址初始化程序
29    allocator.init(12, ptr);
30    println!(
31        "MEMORY: {:#x}..{:#x}",
32        ptr.as_ptr() as usize,
33        ptr.as_ptr() as usize + len
34    );
35    // 计时
36    let t = Instant::now();
37    // 将地址空间放入分配器进行分配【此时生成的结果应该是默认分配情况下的】
38    unsafe { allocator.transfer(ptr, len) };
39    println!("transfer {:?}", t.elapsed());
40
41    assert_eq!(len, allocator.capacity());
42    assert_eq!(len, allocator.free());
43
44    println!(
45        "
46BEFORE
47{allocator:#x?}"
48    );
49
50    // 创建页面大小的指针？
51    let mut blocks = [null_mut::<Page>(); 65536];
52    let layout = Layout::new::<Page>();
53    let t = Instant::now();
54    for block in blocks.iter_mut() {
55        // 将指向对应page大小的地址指定给对应指针(将地址从buddyLine内删除)
56        let (ptr, size) = allocator.allocate_type::<Page>()?;
57        debug_assert_eq!(layout.size(), size);
58        *block = ptr.as_ptr();
59    }
60    // let (ptr, size) = allocator.allocate_type::<Page>()?;
61    // debug_assert_eq!(layout.size(), size);
62    // blocks[i] = ptr.as_ptr();
63    // for i in 0..DIVICE_PIECE {
64    //     // 对于所有的blocks我们便利四次，但是由于LinkedList 和 AVL 都在同等情况下进行测试，因此不会因为循环过多的次数影响到输出的结果
65    //     let mut cnt = 0;
66    //     for j in 0..50 {
67    //         if cnt == i {
68    //             let (ptr, size) = allocator.allocate_type::<Page>()?;
69    //             debug_assert_eq!(layout.size(), size);
70    //             blocks[j] = ptr.as_ptr();
71    //         }
72    //         cnt += 1;
73    //         if cnt == DIVICE_PIECE {
74    //             cnt = 0;
75    //         }
76    //     }
77    // }
78    let ta = t.elapsed();
79
80    // 呈现出全部都被收回的结果
81    println!(
82        "
83EMPTY
84{allocator:#x?}"
85    );
86
87    assert_eq!(len, allocator.capacity());
88    assert_eq!(len - blocks.len() * layout.size(), allocator.free());
89
90    println!("here");
91    let t = Instant::now();
92    // for block in blocks.iter_mut() {
93    //     // 释放指针所指向的空间给分配器进行调配
94    //     allocator.deallocate(NonNull::new(*block).unwrap(), layout.size());
95    //     *block = null_mut();
96    //     // println!("{allocator:#x?}");
97    // }
98    for i in 0..DIVICE_PIECE {
99        let mut cnt = 0;
100        for j in 0..blocks.len() {
101            if cnt == i {
102                allocator.deallocate(NonNull::new(blocks[j]).unwrap(), layout.size());
103                blocks[i] = null_mut();
104            }
105            // println!("{:#x?} , cnt: {cnt:?}, i: {i:?}", blocks[j]);
106            cnt += 1;
107            if cnt == DIVICE_PIECE {
108                cnt = 0;
109            }
110        }
111        println!("{allocator:#x?}");
112    }
113    let td = t.elapsed();
114
115    assert_eq!(len, allocator.capacity());
116    assert_eq!(len, allocator.free());
117
118    println!(
119        "
120AFTER
121{allocator:#x?}"
122    );
123
124    println!(
125        "allocate   {:?} ({} times)",
126        ta / blocks.len() as u32,
127        blocks.len()
128    );
129    println!(
130        "deallocate {:?} ({} times)",
131        td / blocks.len() as u32,
132        blocks.len()
133    );
134
135    Ok(())
136}
avl/avl.rs

avl/
avl.rs
