customizable_buddy/avl.rs
1//! 没有实现线程安全
2//!
3//! ## 总体运算逻辑：
4//! 在进行存储的时候存在如下空间
5//!
6//! 空间序号：1,2,3,4,5,6,7,8
7//! 是否分配：0,1,1,1,0,0,0,0
8//!
9//! 此时对应的层级以及逐步删除划分为：
10//! 1:1 |1:x |1: |1:5,6|1:x,6|1:x|1:7,8|1:x,8 |1:x
11//! 2: |2: |2:5,7 |2:x,7|2:7 |2:7|2:x |2: |2:
12//! 3:5 |3:5 |3:x |3: |3: |3: |3: |3: |3:
13//!
14//! 因此，在进行插入的时候，如果发现存在两个类似的idx，比如7,8，则代表可能出现重复的情况
15//! 此时的想法在于添加一个新的函数，其主要作用在于删除一个制定ptr的节点（已经确定存在）通过这种方式来实现对于兄弟节点的回收
16//! 同时，在完成回收之后，将两个兄弟节点中的最小的节点返回给上一级（并且插入到上一级的avl树中）
17//!
18//! 同时，从总体上来说：在某一层删除一个节点其实相当于从avl树中获取一个节点
19//! 在如果在某一层没有找到对应元素，则向其上一层进行借用，在借用完成的时候再将其中的一部分插入到下一层的位置（这个地方按照lib是可以递归的）
20//! **层级代表着size**
21//!
22//! ## 算法设计：
23//! 整体的算法逻辑如下 [开启了删除伙伴节点方案]
24//! 插入：
25//! IF 插入节点为空：
26//! 直接插入
27//! ELSE:
28//! 判断当前节点以及插入节点的伙伴节点之间的关系以获取下一步的前进方向:
29//! 分成三种情况进行讨论，比当前节点小，大，以及相等
30//! IF 前进方向的下一个节点就是伙伴节点
31//! 按照四种不同删除方式对于伙伴节点进行删除
32//! （其中对于要删除的节点同时存在左右子树的情况下，引入了别的函数，主要目的在于找到当前子树中最大或者最小的节点，clone并返回）
33//! ELSE
34//! 递归到下一个节点处继续进行插入
35//! ENDIF
36//! ENDIF
37//! 删除：
38//! IF 当前节点为空：
39//! 返回None
40//! ELSE:
41//! 根据高度以及当前节点是否存在左右子树的情况，分成四种情况
42//! 找到距离根节点最近的叶子节点进行删除[根据节点的高度信息]
43
44// AVL 算法
45// # 静止的 AVL 树左右子树的高度差的绝对值最大为 1
46//
47// 如果如下的树是 AVL 树：
48//
49// A
50// / \
51// B γ
52// / \
53// α β
54//
55// 则 | α - β | <= 1, | max(α, β) + 1 - γ | <= 1。
56//
57// 如果这是一个需要右单旋的情况（α - β = 1, B - γ = 2），设 x = β，显然：
58//
59// - α = x + 1
60// - β = x
61// - γ = x
62// - A = x + 3
63// - B = x + 2
64//
65// 经过一次右单旋：
66//
67// B | - α = x + 1
68// / \ | - β = x
69// α A | - γ = x
70// / \ | - A = x + 1
71// β γ | - B = x + 2
72//
73// B 的高度不变但整棵树的高度降低 1。
74
75use crate::{BuddyCollection, BuddyLine, OligarchyCollection, Order};
76use core::{fmt, ptr::NonNull};
77/// 基于平衡二叉查找树的侵入式伙伴行。
78pub struct AvlBuddy {
79 tree: Tree,
80 order: Order,
81}
82
83/// 必须实现 [`Send`] 才能加锁。
84unsafe impl Send for AvlBuddy {}
85
86impl BuddyLine for AvlBuddy {
87 const INTRUSIVE_META_SIZE: usize = core::mem::size_of::<Node>();
88
89 const EMPTY: Self = Self {
90 tree: Tree(None),
91 order: Order::new(0),
92 };
93
94 #[inline]
95 fn init(&mut self, order: usize, _base: usize) {
96 self.order = Order::new(order);
97 }
98
99 fn take(&mut self, _idx: usize) -> bool {
100 todo!()
101 }
102}
103
104impl OligarchyCollection for AvlBuddy {
105 fn take_any(&mut self, _align_order: usize, _count: usize) -> Option<usize> {
106 // 个人感觉基于寡头行的数量而言，实现这个地方没有什么效率
107 todo!()
108 }
109
110 #[inline]
111 fn put(&mut self, _idx: usize) {
112 // 个人感觉基于寡头行的数量而言，实现这个没有效率
113 todo!()
114 }
115}
116
117impl BuddyCollection for AvlBuddy {
118 // 从 avl_buddy 行内分配器中获取获取一个节点
119 fn take_any(&mut self, _align_order: usize) -> Option<usize> {
120 // 默认以相同大小进行分配我感觉是比较好的，但是不排除后面修改了想法
121 // TODO 需要考虑是否进行边界判断
122 if _align_order != 0 {
123 None
124 } else {
125 self.tree.delete(&self.order)
126 }
127 }
128
129 /// insert node into avl_buddy
130 fn put(&mut self, idx: usize) -> Option<usize> {
131 // 需要额外考虑一个事情，就是在进行分配的时候，最小分配单元必须大于Node，因为这个Node实际上是存放在分配的空间中的，因此需要加入判定以确保空间不会出现重叠的情况
132 // buddy序号为 0 时地址为空指针，跳过合并。
133 if idx ^ 1 == 0 {
134 self.tree.insert_no_merge(idx, &self.order);
135 return None;
136 }
137 if self.tree.insert(idx, &self.order) {
138 None
139 } else {
140 // find it's buddy
141 /* DEBUG */
142 // println!("facing it's buddy");
143 // Some(idx & (!(1)))
144 Some(idx >> 1)
145 }
146 }
147}
148
149impl fmt::Debug for AvlBuddy {
150 /// 以序列化前序遍历的方式输出
151 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
152 // 这个地方我认为相对来说较难复现前面的算法,即使用层序便利对于结果进行呈现,可能需要采用标准搜索方案来对于结果进行呈现
153 // 同时由于在trait外部实现dfs算法相对比较困难(感觉会造成割裂感),因此采用内部函数递归来实现这个操作
154 write!(f, "[")?;
155
156 fn dfs(root: &Tree, order: &Order, f: &mut fmt::Formatter<'_>) -> fmt::Result {
157 // if it's leaf node
158 match root.0 {
159 // if it's leaf node
160 None => write!(f, "#,"),
161 Some(root_node) => {
162 // let a = root_node.as_ref().l;
163 write!(f, "{:#x}[{:?}],", order.ptr_to_idx(root_node), unsafe {
164 root_node.as_ref().h
165 })?;
166 // write!(f, "{:#x}[{:?}],", root_node.as_ptr() as usize, unsafe { root_node.as_ref().h })?;
167 // write!(f, "{:#x},", root_node.as_ptr() as usize)?;
168 dfs(unsafe { &root_node.as_ref().l }, order, f)?;
169 // write!(f, "{:#x},", root_node.as_ptr() as usize)?;
170 dfs(unsafe { &root_node.as_ref().r }, order, f)
171 }
172 }
173 // if let None = root.0 {
174 // write!(f, "#")
175 // }
176 // else {
177 // write!(f, "{:X}", root.0.)
178 // }
179 }
180
181 dfs(&self.tree, &self.order, f)?;
182 write!(f, "]")
183 }
184}
185
186impl fmt::Debug for Node {
187 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
188 if let Some(left) = self.l.0 {
189 write!(f, "l:{:#x?}", left.as_ptr() as usize)?;
190 write!(f, "[{:?}] ", unsafe { left.as_ref().h })?;
191 } else {
192 write!(f, "l:null ")?;
193 }
194 if let Some(right) = self.r.0 {
195 write!(f, "r:{:#x?}", right.as_ptr() as usize)?;
196 write!(f, "[{:?}] ", unsafe { right.as_ref().h })?;
197 } else {
198 write!(f, "r:null ")?;
199 }
200 write!(f, "h:{}", self.h)
201 }
202}
203
204impl fmt::Debug for Tree {
205 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
206 if let Some(root) = self.0 {
207 write!(f, "{:?}", root)
208 } else {
209 write!(f, "null")
210 }
211 }
212}
213
214#[repr(transparent)]
215#[derive(Clone, Copy)]
216struct Tree(Option<NonNull<Node>>);
217
218#[repr(C)]
219#[derive(Clone, Copy)]
220struct Node {
221 l: Tree,
222 r: Tree,
223 h: usize,
224}
225
226/// 以递归方式找到距离传入子树最大节点最近的子树节点
227///
228/// 注意：调用者需要考虑到传出节点可能存在反向子树的情况
229/// 这个地方没有考虑到开始递归节点处可能在一开始就没有右子树的情况
230fn find_max(node: &NonNull<Node>) -> NonNull<Node> {
231 // 需要考虑到有左子树的情况
232 // [A]
233 // \
234 // [B] (node.r)
235 // /
236 // [?]
237 let right = unsafe { node.as_ref().r.0 };
238 if let Some(right_node) = right {
239 if unsafe { right_node.as_ref().r.0.is_some() } {
240 // if have right and it's right
241 find_max(&right_node)
242 } else {
243 *node
244 }
245 } else {
246 *node
247 // NonNull::new(node.as_ptr()).unwrap()
248 }
249}
250
251/// 以递归方式找到并返回距离最小子树最近的子树
252///
253/// 注意：调用者需要考虑到可能传出节点存在反向子树的情况
254/// 在这个地方没有考虑到开始递归节点可能一开始就没有左子树的情况
255fn find_min(node: &NonNull<Node>) -> NonNull<Node> {
256 // 需要考虑有右子树的情况
257 // [a]
258 // /
259 // [b] (min point)
260 // \
261 // [c]
262 let left = unsafe { node.as_ref().l.0 };
263 if let Some(left_node) = left {
264 if unsafe { left_node.as_ref().l.0.is_some() } {
265 find_min(&left_node)
266 } else {
267 *node
268 }
269 } else {
270 *node
271 // NonNull::new(node.as_ptr()).unwrap()
272 }
273}
274
275impl Tree {
276 /// 向当前节点处插入一个节点
277 ///
278 /// 在碰到节点与伙伴节点同时存在的情况下，会删除伙伴节点并且返回false [插入失败]
279 fn insert(&mut self, idx: usize, order: &Order) -> bool {
280 // 这个地方我认为目前的速度瓶颈主要出现在大量使用递归所带来的影响，但是考虑到本lab主要完成的是分配器，因此可能没有办法实现动态的内存分配，进而使用栈或者队列来实现对应操作
281
282 // 版本二：在进行插入的时候直接完成对应伙伴节点的删除工作
283 let ptr: NonNull<Node> = order.idx_to_ptr(idx).expect("block address is null");
284 match self.0 {
285 // if this node is not empty
286 Some(mut root_ptr) => {
287 let root = unsafe { root_ptr.as_mut() };
288 let buddy = order
289 .idx_to_ptr::<Node>(idx ^ 1)
290 .expect("buddy address is null");
291 use core::cmp::Ordering::*;
292 // use core::mem::replace;
293
294 // 找到我们需要去的方向
295 let ret = match root_ptr.cmp(&buddy) {
296 Less => {
297 // 向右前方前进， 并且右边子树节点为伙伴节点 => 此时做可能出现的所有删除情形的判断
298 if root.r.0.is_some() && order.ptr_to_idx(root.r.0.unwrap()) == idx ^ 1 {
299 // 要删除的节点
300 let node = unsafe { root.r.0.unwrap().as_mut() };
301 // 测试两个子树的状态
302 match (node.l.0.is_some(), node.r.0.is_some()) {
303 (true, true) => {
304 // have both left and right subtree
305 if node.l.height() < node.r.height() {
306 // right tree higher than left tree
307 // root: the point you using the function
308 // node: the point you want to delete
309 // byond: the point byond the leaf
310 // [A] (root) | [A]
311 // / \ | / \
312 // .. [B] (node) | .. [E]
313 // / \ | / \
314 // [C](byond)[D] | [C] [D]
315 // \ | \
316 // [E] (leaf) | [F]
317 // \
318 // [F]
319 if node.r.height() == 1 {
320 // right subtree is leaf => delete node
321 let leaf = unsafe { node.r.0.unwrap().as_mut() };
322 leaf.l = Tree(node.l.0);
323 root.r = Tree(NonNull::new(leaf));
324 leaf.update();
325 root.update();
326 } else {
327 // right subtree has subtree => delete link and relink this link to it's parent then delete node
328 let beyond =
329 unsafe { find_min(&node.r.0.unwrap()).as_mut() };
330
331 if let Some(mut leaf) = beyond.l.0 {
332 // 如果 beyond 存在左节点
333 let leaf = unsafe { leaf.as_mut() };
334
335 // 如果 leaf 存在反方向节点
336 if leaf.r.0.is_some() {
337 beyond.l = Tree(leaf.l.0);
338 leaf.l = Tree(None);
339 } else {
340 beyond.l = Tree(None);
341 }
342 leaf.l = Tree(node.l.0);
343 leaf.r = Tree(node.r.0);
344 root.r = Tree(NonNull::new(leaf));
345 leaf.update();
346 root.update();
347 } else {
348 // 将 beyond 作为 leaf 替换 node 的位置
349 beyond.l = Tree(node.l.0);
350 root.r = Tree(NonNull::new(beyond));
351 beyond.update();
352 root.update();
353 }
354 }
355 } else {
356 // left tree higher than right subtree
357 // root: the point you using the function
358 // node: the point you want to delete
359 // byond: the point byond the leaf
360 // [A] (root) | [A]
361 // \ | \
362 // [B] (node) | [E]
363 // / \ | / \
364 // [C] [D](byond) | [C] [D]
365 // / | \
366 // (E:leaf) | [F]
367 // \
368 // [F]
369 if node.l.height() == 1 {
370 // left subtree is leaf => delete node
371 let leaf = unsafe { node.l.0.unwrap().as_mut() };
372 leaf.r = Tree(node.r.0);
373 root.r = Tree(NonNull::new(leaf));
374 leaf.update();
375 root.update();
376 } else {
377 #[allow(unused_variables, unused_mut, dead_code)]
378 // left subtree has subtree => delete link and relink this link to it's parent then delete node
379 let mut beyond =
380 unsafe { find_max(&node.l.0.unwrap()).as_mut() };
381
382 if let Some(mut leaf) = beyond.r.0 {
383 // 如果 beyond 存在右子树【这个实际上是为了弥补 find_max 中无法获取这种情况下距离最大节点最近的节点设计的】
384 let leaf = unsafe { leaf.as_mut() };
385
386 // 如果 leaf 存在反方向子树
387 if leaf.l.0.is_some() {
388 beyond.r = Tree(leaf.l.0);
389 leaf.l = Tree(None);
390 } else {
391 beyond.r = Tree(None);
392 }
393 leaf.l = Tree(node.l.0);
394 leaf.r = Tree(node.r.0);
395 root.r = Tree(NonNull::new(leaf));
396 leaf.update();
397 root.update();
398 } else {
399 // 将 beyond 作为 leaf 替换 node 的位置
400 beyond.r = Tree(node.r.0);
401 root.r = Tree(NonNull::new(beyond));
402 beyond.update();
403 root.update();
404 }
405 }
406 }
407 node.update();
408 root.r.rotate();
409 }
410 (true, false) => {
411 // have left but not right
412 // [A] <- root | [A]
413 // \ | \
414 // [B] <- node| [C]
415 // / |
416 // [C] |
417 root.r = Tree(Some(node.l.0.unwrap()));
418 node.l = Tree(None); // 可有可无？
419 root.update();
420 }
421 (false, true) => {
422 // have left but not right
423 // [A] <- root | [A]
424 // \ | \
425 // [B] <- node| [C]
426 // \ |
427 // [C] | 这个地方不能直接上旋转，将节点转到叶子的原因是太麻烦了
428 root.r = Tree(Some(node.r.0.unwrap()));
429 node.r = Tree(None);
430 root.update();
431 }
432 (false, false) => {
433 root.r = Tree(None);
434 root.update();
435 }
436 }
437 return false;
438 } else {
439 // 如果前进的方向不是 buddy 节点，则以递归方式继续进行插入，一直到达对应的位置(插入于空节点)
440 root.r.insert(idx, order)
441 }
442 }
443 Equal => {
444 // 个人感觉这个地方只可能出现在根节点处
445 match (root.l.0.is_some(), root.r.0.is_some()) {
446 (true, true) => {
447 match (
448 root.l.height() < root.r.height(),
449 core::cmp::max(root.l.height(), root.r.height()),
450 ) {
451 (_, 1) => {
452 // if both of left and right is leaf => choice left as root
453 let left = unsafe { root.l.0.unwrap().as_mut() };
454 // left.l = Tree(None);
455 left.r = Tree(root.r.0);
456 self.0 = NonNull::new(left);
457 left.update();
458 }
459 (true, _) => {
460 // right higher that left
461 let beyond =
462 unsafe { find_min(&root.r.0.unwrap()).as_mut() };
463
464 if let Some(mut leaf) = beyond.l.0 {
465 let leaf = unsafe { leaf.as_mut() };
466
467 if leaf.r.0.is_some() {
468 beyond.l = Tree(leaf.r.0);
469 leaf.r = Tree(None);
470 } else {
471 beyond.l = Tree(None);
472 }
473 leaf.l = Tree(root.l.0);
474 leaf.r = Tree(root.r.0);
475 self.0 = NonNull::new(leaf);
476 leaf.update();
477 } else {
478 // 取右边最高节点出来作为root
479 let right = unsafe { root.r.0.unwrap().as_mut() };
480 right.l = Tree(root.l.0);
481 self.0 = NonNull::new(right);
482 right.update();
483 }
484 }
485 (false, _) => {
486 // left higher than right
487 let beyond =
488 unsafe { find_max(&root.l.0.unwrap()).as_mut() };
489 if let Some(mut leaf) = beyond.r.0 {
490 let leaf = unsafe { leaf.as_mut() };
491
492 if leaf.l.0.is_some() {
493 beyond.r = Tree(leaf.l.0);
494 leaf.l = Tree(None);
495 } else {
496 beyond.r = Tree(None);
497 }
498 leaf.l = Tree(root.l.0);
499 leaf.r = Tree(root.r.0);
500 self.0 = NonNull::new(leaf);
501 leaf.update();
502 } else {
503 let left = unsafe { root.l.0.unwrap().as_mut() };
504 left.r = Tree(root.r.0);
505 self.0 = NonNull::new(left);
506 left.update()
507 }
508 }
509 }
510 }
511 (true, false) => {
512 self.0 = Some(root.l.0.unwrap());
513 }
514 (false, true) => {
515 self.0 = Some(root.r.0.unwrap());
516 }
517 (false, false) => {
518 self.0 = None;
519 return false;
520 }
521 };
522 false
523 }
524 Greater => {
525 // 向左方前进，前进前确认对应节点是否存在，以及节点是否是buddy
526 if root.l.0.is_some() && order.ptr_to_idx(root.l.0.unwrap()) == idx ^ 1 {
527 // if delete node is not leaf => delete link
528 let node = unsafe { root.l.0.unwrap().as_mut() };
529 match (node.l.0.is_some(), node.r.0.is_some()) {
530 (true, true) => {
531 // have both left and right subtree
532 if node.l.height() < node.r.height() {
533 // right tree higher than left tree
534 // node: the point you want to delete
535 // byond: the point byond the leaf
536 // [A] (root) | [A]
537 // / | /
538 // . [B] (node) | [E]
539 // / \ | / \
540 // [C](byond)[D] | [C] [D]
541 // \ | \
542 // [E] (leaf) | [F]
543 // \
544 // [F]// 找到距离左子树最大节点最近的节点
545 if node.r.height() == 1 {
546 let leaf = unsafe { node.r.0.unwrap().as_mut() };
547 leaf.l = Tree(node.l.0);
548 root.l = Tree(NonNull::new(leaf));
549 leaf.update();
550 root.update();
551 } else {
552 let beyond =
553 unsafe { find_min(&node.r.0.unwrap()).as_mut() };
554 if let Some(mut leaf) = beyond.l.0 {
555 // 如果 beyond 存在左子树
556 let leaf = unsafe { leaf.as_mut() };
557
558 // 如果存在反方向子树
559 if leaf.r.0.is_some() {
560 beyond.l = Tree(leaf.r.0);
561 leaf.r = Tree(None);
562 } else {
563 beyond.l = Tree(None);
564 }
565
566 leaf.l = Tree(node.l.0);
567 leaf.r = Tree(node.r.0);
568 root.l = Tree(NonNull::new(leaf));
569
570 leaf.update();
571 root.update();
572 } else {
573 // 将 beyond 作为 leaf 替换 node
574 beyond.l = Tree(node.l.0);
575 root.l = Tree(NonNull::new(beyond));
576 beyond.update();
577 root.update();
578 }
579 }
580 } else {
581 // left tree higher than right subtree
582 // node: the point you want to delete
583 // byond: the point byond the leaf
584 // [A] (root) | [A]
585 // / | /
586 // [B] (node) | [E]
587 // / \ | / \
588 // [C] [D](byond) | [C] [D]
589 // / | \
590 // (E:leaf) | [F]
591 // \
592 // [F]
593 if node.l.height() == 1 {
594 // left subtree is leaf => delete node
595 let leaf = unsafe { node.l.0.unwrap().as_mut() };
596 leaf.r = Tree(node.r.0);
597 root.l = Tree(NonNull::new(leaf));
598 leaf.update();
599 root.update();
600 } else {
601 // left subtree has subtree => delete link and relink this link to it's parent then delete node
602 let beyond =
603 unsafe { find_max(&node.l.0.unwrap()).as_mut() };
604 if let Some(mut leaf) = beyond.r.0 {
605 let leaf = unsafe { leaf.as_mut() };
606
607 if leaf.l.0.is_some() {
608 beyond.r = Tree(leaf.l.0);
609 leaf.l = Tree(None);
610 } else {
611 beyond.r = Tree(None);
612 }
613 leaf.l = Tree(node.l.0);
614 leaf.r = Tree(node.r.0);
615 root.l = Tree(NonNull::new(leaf));
616 leaf.update();
617 root.update();
618 } else {
619 beyond.r = Tree(node.r.0);
620 root.l = Tree(NonNull::new(beyond));
621 beyond.update();
622 root.update();
623 }
624 }
625 }
626 }
627 (true, false) => {
628 // have left but not right
629 // [A] <- root | [A]
630 // / | /
631 // [B] <- node | [C]
632 // / |
633 // [C] |
634 root.l = Tree(Some(node.l.0.unwrap()));
635 node.l = Tree(None);
636 node.update();
637 }
638 (false, true) => {
639 // have left but not right
640 // [A] <- root | [A]
641 // / | /
642 // [B] <- node | [C]
643 // \ |
644 // [C] |
645 root.l = Tree(Some(node.r.0.unwrap()));
646 node.l = Tree(None);
647 node.update();
648 }
649 (false, false) => {
650 // is leaf node
651 root.l = Tree(None);
652 root.update();
653 }
654 }
655 return false;
656 } else {
657 // 如果前进的方向不是 buddy 节点，则以递归方式继续进行插入，一直到达对应的位置(插入于空节点)
658 root.l.insert(idx, order)
659 }
660 }
661 };
662 root.update();
663 unsafe { self.0.unwrap().as_mut() }.update();
664 self.rotate();
665 ret
666 }
667 // if this node is empty => insert in this point
668 None => {
669 self.0 = Some(ptr);
670 *unsafe { order.idx_to_ptr(idx).unwrap().as_mut() } = Node {
671 l: Tree(None),
672 r: Tree(None),
673 h: 1,
674 };
675 true
676 }
677 }
678 }
679
680 /// 插入结点（不合并buddy）。buddy地址为空时使用。
681 fn insert_no_merge(&mut self, idx: usize, order: &Order) {
682 let ptr: NonNull<Node> = order.idx_to_ptr(idx).expect("block address is null");
683 match self.0 {
684 Some(mut root_ptr) => {
685 let root = unsafe { root_ptr.as_mut() };
686 if ptr < root_ptr {
687 root.l.insert_no_merge(idx, order);
688 } else {
689 root.r.insert_no_merge(idx, order);
690 }
691 root.update();
692 self.rotate();
693 }
694 None => {
695 self.0 = Some(ptr);
696 unsafe {
697 ptr.as_ptr().write(Node {
698 l: Tree(None),
699 r: Tree(None),
700 h: 1,
701 });
702 }
703 }
704 }
705 }
706
707 /// 从地址池中获取一个单位的地址, 并且返回这个地址
708 fn delete(&mut self, order: &Order) -> Option<usize> {
709 /*
710 根据需求，此处需要实现的子模块包括，通过 左右子树中的最小高度导航到 到最近的叶子结点，然后再进行 删除节点操作
711 删除节点操作的时候，由于当前操作在叶子节点处产生，因此不需要考虑额外信息，直接将其删除即可
712 */
713 match self.0 {
714 None => None,
715 Some(mut root_ptr) => {
716 let root = unsafe { root_ptr.as_mut() };
717 let ret = match (root.l.0.is_some(), root.r.0.is_some()) {
718 (true, true) => {
719 // have both left and right subtree
720 // 如果某个方向只剩下一个节点，则直接删除这个节点，并且返回对应信息
721 // 否则以递归方式继续进行
722 // 这个地方实际上主要目的在于减少代码量...但是反而带来了可读性的降低
723 match (
724 root.l.height() < root.r.height(),
725 core::cmp::min(root.l.height(), root.r.height()),
726 ) {
727 (true, 1) => {
728 let node = order.ptr_to_idx(root.l.0.unwrap());
729 root.l = Tree(None);
730 root.update();
731 return Some(node);
732 }
733 (true, _) => root.l.delete(order),
734 (false, 1) => {
735 let node = order.ptr_to_idx(root.r.0.unwrap());
736 root.r = Tree(None);
737 root.update();
738 return Some(node);
739 }
740 (false, _) => root.r.delete(order),
741 }
742 }
743 (true, false) => {
744 // only have left subtree
745 match root.l.height() {
746 1 => {
747 let node = order.ptr_to_idx(root.l.0.unwrap());
748 root.l = Tree(None);
749 root.update();
750 return Some(node);
751 }
752 _ => root.l.delete(order),
753 }
754 }
755 (false, true) => {
756 // only have right subtree
757 match root.r.height() {
758 1 => {
759 let node = order.ptr_to_idx(root.r.0.unwrap());
760 root.r = Tree(None);
761 root.update();
762 return Some(node);
763 }
764 _ => root.r.delete(order),
765 }
766 }
767 (false, false) => {
768 // this is the root node (and it's leaf) => clean itself
769 // let node = self.0.unwrap().as_ptr() as usize;
770 let node = order.ptr_to_idx(self.0.unwrap());
771 self.0 = None;
772 return Some(node);
773 }
774 };
775 root.update();
776 self.rotate();
777 ret
778 }
779 }
780 }
781
782 /// 树高。
783 ///
784 /// 空树高度为 0；单独的结点高度为 1。
785 #[inline]
786 fn height(&self) -> usize {
787 self.0.map_or(0, |node| unsafe { node.as_ref() }.h)
788 }
789
790 /// 旋转
791 fn rotate(&mut self) {
792 let root = unsafe { self.0.unwrap().as_mut() };
793 let bf = root.bf();
794 if bf > 1 {
795 if unsafe { root.l.0.unwrap().as_mut() }.bf() >= 0 {
796 self.rotate_r();
797 } else {
798 root.l.rotate_l();
799 self.rotate_r();
800 }
801 } else if bf < -1 {
802 if unsafe { root.r.0.unwrap().as_mut() }.bf() <= 0 {
803 self.rotate_l();
804 } else {
805 root.r.rotate_r();
806 self.rotate_l();
807 }
808 }
809 }
810
811 #[inline]
812 /// 右旋
813 fn rotate_r(&mut self) {
814 use core::mem::replace;
815 let a = unsafe { self.0.unwrap().as_mut() };
816 let b = unsafe { a.l.0.unwrap().as_mut() };
817 // A -> B | -->
818 // / \ -> / \ | _[A]
819 // B γ -> α A | /| \
820 // / \ -> / \ | / _\|
821 // α β -> β γ | [B]<----[β]
822 self.0 = replace(&mut a.l.0, replace(&mut b.r.0, self.0));
823 a.update();
824 b.update();
825 }
826
827 #[inline]
828 /// 左旋
829 fn rotate_l(&mut self) {
830 use core::mem::replace;
831 let a = unsafe { self.0.unwrap().as_mut() };
832 let b = unsafe { a.r.0.unwrap().as_mut() };
833 // A -> B | <--
834 // / \ -> / \ | [A]_
835 // α B -> A γ | / |\
836 // / \ -> / \ | |/_ \
837 // β γ -> α β | [β]---->[B]
838 self.0 = replace(&mut a.r.0, replace(&mut b.l.0, self.0));
839 a.update();
840 b.update();
841 }
842}
843
844impl Node {
845 /// 更新结点。
846 #[inline]
847 fn update(&mut self) {
848 // 结点高度比左右子树中高的高 1
849 self.h = core::cmp::max(self.l.height(), self.r.height()) + 1;
850 }
851
852 /// 平衡因子。
853 #[inline]
854 fn bf(&self) -> isize {
855 self.l.height() as isize - self.r.height() as isize
856 }
857}
858
859#[cfg(test)]
860#[allow(unused_variables, dead_code)]
861mod test {
862 // 这个地方主要是基于白盒测试点需要实现的，但是随之出现的问题在于其依赖项(pirnt（删除不方便测试），vec[非——必要]）
863 // 没有办法在no_std的情况下运行，也因 rust pub use only for tests 相对比较复杂，同时可能有隔离的问题，因而没有使用这个方法
864 // 也不太能转换成为 write 宏进行实现
865 use super::*;
866
867 #[repr(C, align(4096))]
868 struct Page([u8; 4096]);
869
870 impl Page {
871 const ZERO: Self = Self([0; 4096]);
872 }
873
874 impl Node {
875 const EMPTY: Node = Self {
876 l: Tree(None),
877 r: Tree(None),
878 h: 1,
879 };
880 }
881
882 /// 256 MiB
883 static mut MEMORY: [Page; 1024] = [Page::ZERO; 1024];
884
885 // 彼此之间要间隔开至少24个数字以防止某种程度上的冲突
886 // NonNull<Node>: 8; Node: 24; u8:1
887 // 0 64 128 192 256 320 384 448 512 576 640 704 768 832 896 960
888 fn create_nonnull_list() -> [NonNull<Node>; 1024 / 64] {
889 // let mut list = Vec::new();
890 let mut list = [NonNull::<Node>::dangling(); 1024 / 64];
891 for i in 0..1024 / 64 {
892 list[i] = unsafe { NonNull::new_unchecked(MEMORY[i * 64].0.as_mut_ptr() as *mut Node) };
893 }
894 /* DEBUG
895 println!("num\tidx\t\tptr");
896 for i in 0..list.len() {
897 print!("> {i}:\t");
898 println!("{:#x?}\t", (list[i].as_ptr() as usize) >> ORDER_LEVEL);
899 // println!("{:#x?}", (list[i].as_ptr() as usize));
900 }
901 */
902 list
903 }
904
905 use crate::{AvlBuddy, BuddyCollection};
906 const ORDER_LEVEL: usize = 12;
907 /* TEST FOR BASAL INSERT OPERATION */
908 #[test]
909 fn test_for_insert_l() {
910 let vec = create_nonnull_list();
911 // println!("{}", vec.len());
912 let mut avl_buddy = AvlBuddy::EMPTY;
913 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
914
915 <AvlBuddy as BuddyCollection>::put(
916 &mut avl_buddy,
917 (vec[7].as_ptr() as usize) >> ORDER_LEVEL,
918 );
919 <AvlBuddy as BuddyCollection>::put(
920 &mut avl_buddy,
921 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
922 );
923 <AvlBuddy as BuddyCollection>::put(
924 &mut avl_buddy,
925 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
926 );
927 // <avlbuddy as buddycollection>::put(&mut avl_buddy, (vec[6].as_ptr() as usize) >> order_level);
928
929 // let a = unsafe { &avl_buddy.tree.0.unwrap().as_ref().l};
930 // println!("{avl_buddy:#x?}");
931 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
932 assert_eq!(
933 unsafe { avl_buddy.tree.0.unwrap().as_ref().l.0.unwrap() },
934 vec[7]
935 );
936 assert_eq!(
937 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
938 vec[9]
939 );
940 }
941 #[test]
942 fn test_for_insert_r() {
943 let vec = create_nonnull_list();
944 // println!("{}", vec.len());
945 let mut avl_buddy = AvlBuddy::EMPTY;
946 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
947
948 <AvlBuddy as BuddyCollection>::put(
949 &mut avl_buddy,
950 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
951 );
952 <AvlBuddy as BuddyCollection>::put(
953 &mut avl_buddy,
954 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
955 );
956 <AvlBuddy as BuddyCollection>::put(
957 &mut avl_buddy,
958 (vec[7].as_ptr() as usize) >> ORDER_LEVEL,
959 );
960 // <avlbuddy as buddycollection>::put(&mut avl_buddy, (vec[6].as_ptr() as usize) >> order_level);
961
962 // let a = unsafe { &avl_buddy.tree.0.unwrap().as_ref().l};
963 // println!("{avl_buddy:#x?}");
964 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
965 assert_eq!(
966 unsafe { avl_buddy.tree.0.unwrap().as_ref().l.0.unwrap() },
967 vec[7]
968 );
969 assert_eq!(
970 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
971 vec[9]
972 );
973 }
974 #[test]
975 fn test_for_insert_lr() {
976 let vec = create_nonnull_list();
977 // println!("{}", vec.len());
978 let mut avl_buddy = AvlBuddy::EMPTY;
979 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
980
981 <AvlBuddy as BuddyCollection>::put(
982 &mut avl_buddy,
983 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
984 );
985 <AvlBuddy as BuddyCollection>::put(
986 &mut avl_buddy,
987 (vec[7].as_ptr() as usize) >> ORDER_LEVEL,
988 );
989 <AvlBuddy as BuddyCollection>::put(
990 &mut avl_buddy,
991 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
992 );
993 // <avlbuddy as buddycollection>::put(&mut avl_buddy, (vec[6].as_ptr() as usize) >> order_level);
994
995 // let a = unsafe { &avl_buddy.tree.0.unwrap().as_ref().l};
996 // println!("{avl_buddy:#x?}");
997 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
998 assert_eq!(
999 unsafe { avl_buddy.tree.0.unwrap().as_ref().l.0.unwrap() },
1000 vec[7]
1001 );
1002 assert_eq!(
1003 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1004 vec[9]
1005 );
1006 }
1007 #[test]
1008 fn test_for_insert_rl() {
1009 let vec = create_nonnull_list();
1010 // println!("{}", vec.len());
1011 let mut avl_buddy = AvlBuddy::EMPTY;
1012 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1013
1014 <AvlBuddy as BuddyCollection>::put(
1015 &mut avl_buddy,
1016 (vec[7].as_ptr() as usize) >> ORDER_LEVEL,
1017 );
1018 <AvlBuddy as BuddyCollection>::put(
1019 &mut avl_buddy,
1020 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1021 );
1022 <AvlBuddy as BuddyCollection>::put(
1023 &mut avl_buddy,
1024 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1025 );
1026
1027 // println!("{avl_buddy:#x?}");
1028 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1029 assert_eq!(
1030 unsafe { avl_buddy.tree.0.unwrap().as_ref().l.0.unwrap() },
1031 vec[7]
1032 );
1033 assert_eq!(
1034 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1035 vec[9]
1036 );
1037 }
1038 /* TEST FOR BUDDY OPERATION: DELETE BUDDY NODE AND NOT INSERT */
1039 #[test]
1040 fn test_for_insert_buddy_root() {
1041 let vec = create_nonnull_list();
1042 // println!("{}", vec.len());
1043 let mut avl_buddy = AvlBuddy::EMPTY;
1044 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1045
1046 let root_idx = (vec[7].as_ptr() as usize) >> ORDER_LEVEL;
1047 let buddy_idx = ((vec[7].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1048 // println!("{root_idx:#x?}\t{buddy_idx:#x?}");
1049 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, root_idx);
1050 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1051
1052 // println!("{avl_buddy:#x?}");
1053 assert_eq!(avl_buddy.tree.0, None);
1054 }
1055 #[test]
1056 fn test_for_insert_buddy_left_leaf() {
1057 let vec = create_nonnull_list();
1058 // println!("{}", vec.len());
1059 let mut avl_buddy = AvlBuddy::EMPTY;
1060 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1061
1062 let buddy_idx = ((vec[7].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1063 // println!("{buddy_idx:#x?}");
1064 <AvlBuddy as BuddyCollection>::put(
1065 &mut avl_buddy,
1066 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1067 );
1068 <AvlBuddy as BuddyCollection>::put(
1069 &mut avl_buddy,
1070 (vec[7].as_ptr() as usize) >> ORDER_LEVEL,
1071 );
1072 <AvlBuddy as BuddyCollection>::put(
1073 &mut avl_buddy,
1074 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1075 );
1076 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1077
1078 // println!("{avl_buddy:#x?}");
1079 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1080 assert_eq!(unsafe { avl_buddy.tree.0.unwrap().as_ref().l.0 }, None);
1081 assert_eq!(
1082 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1083 vec[9]
1084 );
1085 }
1086 #[test]
1087 fn test_for_insert_buddy_right_leaf() {
1088 let vec = create_nonnull_list();
1089 // println!("{}", vec.len());
1090 let mut avl_buddy = AvlBuddy::EMPTY;
1091 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1092
1093 let buddy_idx = ((vec[9].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1094 // println!("{buddy_idx:#x?}");
1095 <AvlBuddy as BuddyCollection>::put(
1096 &mut avl_buddy,
1097 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1098 );
1099 <AvlBuddy as BuddyCollection>::put(
1100 &mut avl_buddy,
1101 (vec[7].as_ptr() as usize) >> ORDER_LEVEL,
1102 );
1103 <AvlBuddy as BuddyCollection>::put(
1104 &mut avl_buddy,
1105 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1106 );
1107 // println!("{avl_buddy:#x?}");
1108 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1109 // println!("{avl_buddy:#x?}");
1110 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1111 assert_eq!(
1112 unsafe { avl_buddy.tree.0.unwrap().as_ref().l.0.unwrap() },
1113 vec[7]
1114 );
1115 assert_eq!(unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0 }, None);
1116 }
1117 #[test]
1118 fn test_for_insert_buddy_right_not_leaf_right_only() {
1119 let vec = create_nonnull_list();
1120 // println!("{}", vec.len());
1121 let mut avl_buddy = AvlBuddy::EMPTY;
1122 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1123
1124 let buddy_idx = ((vec[9].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1125 // println!("{buddy_idx:#x?}");
1126 <AvlBuddy as BuddyCollection>::put(
1127 &mut avl_buddy,
1128 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1129 );
1130 <AvlBuddy as BuddyCollection>::put(
1131 &mut avl_buddy,
1132 (vec[6].as_ptr() as usize) >> ORDER_LEVEL,
1133 );
1134 <AvlBuddy as BuddyCollection>::put(
1135 &mut avl_buddy,
1136 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1137 );
1138 <AvlBuddy as BuddyCollection>::put(
1139 &mut avl_buddy,
1140 (vec[4].as_ptr() as usize) >> ORDER_LEVEL,
1141 );
1142 <AvlBuddy as BuddyCollection>::put(
1143 &mut avl_buddy,
1144 (vec[10].as_ptr() as usize) >> ORDER_LEVEL,
1145 );
1146 // println!("{avl_buddy:#x?}");
1147 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1148 // println!("{avl_buddy:#x?}");
1149 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1150 assert_eq!(
1151 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1152 vec[10]
1153 );
1154 }
1155 #[test]
1156 fn test_for_insert_buddy_right_not_leaf_left_only() {
1157 let vec = create_nonnull_list();
1158 // println!("{}", vec.len());
1159 let mut avl_buddy = AvlBuddy::EMPTY;
1160 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1161
1162 let buddy_idx = ((vec[10].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1163 // println!("{buddy_idx:#x?}");
1164 <AvlBuddy as BuddyCollection>::put(
1165 &mut avl_buddy,
1166 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1167 );
1168 <AvlBuddy as BuddyCollection>::put(
1169 &mut avl_buddy,
1170 (vec[6].as_ptr() as usize) >> ORDER_LEVEL,
1171 );
1172 <AvlBuddy as BuddyCollection>::put(
1173 &mut avl_buddy,
1174 (vec[10].as_ptr() as usize) >> ORDER_LEVEL,
1175 );
1176 <AvlBuddy as BuddyCollection>::put(
1177 &mut avl_buddy,
1178 (vec[4].as_ptr() as usize) >> ORDER_LEVEL,
1179 );
1180 <AvlBuddy as BuddyCollection>::put(
1181 &mut avl_buddy,
1182 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1183 );
1184 // println!("{avl_buddy:#x?}");
1185 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1186
1187 // println!("{avl_buddy:#x?}");
1188 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1189 assert_eq!(
1190 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1191 vec[9]
1192 );
1193 }
1194 #[test]
1195 fn test_for_insert_buddy_right_not_leaf_both_no_subleaf() {
1196 let vec = create_nonnull_list();
1197 // println!("{}", vec.len());
1198 let mut avl_buddy = AvlBuddy::EMPTY;
1199 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1200
1201 let buddy_idx = ((vec[10].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1202 // println!("{buddy_idx:#x?}");
1203 <AvlBuddy as BuddyCollection>::put(
1204 &mut avl_buddy,
1205 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1206 );
1207 <AvlBuddy as BuddyCollection>::put(
1208 &mut avl_buddy,
1209 (vec[6].as_ptr() as usize) >> ORDER_LEVEL,
1210 );
1211 <AvlBuddy as BuddyCollection>::put(
1212 &mut avl_buddy,
1213 (vec[10].as_ptr() as usize) >> ORDER_LEVEL,
1214 );
1215 <AvlBuddy as BuddyCollection>::put(
1216 &mut avl_buddy,
1217 (vec[4].as_ptr() as usize) >> ORDER_LEVEL,
1218 );
1219 <AvlBuddy as BuddyCollection>::put(
1220 &mut avl_buddy,
1221 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1222 );
1223 <AvlBuddy as BuddyCollection>::put(
1224 &mut avl_buddy,
1225 (vec[11].as_ptr() as usize) >> ORDER_LEVEL,
1226 );
1227 // println!("{avl_buddy:#x?}");
1228 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1229 // println!("{avl_buddy:#x?}");
1230 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1231 assert_eq!(
1232 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1233 vec[9]
1234 );
1235 }
1236 #[test]
1237 fn test_for_insert_buddy_right_not_leaf_both_with_subleaf() {
1238 let vec = create_nonnull_list();
1239 // println!("{}", vec.len());
1240 let mut avl_buddy = AvlBuddy::EMPTY;
1241 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1242
1243 let buddy_idx = ((vec[10].as_ptr() as usize) >> ORDER_LEVEL) ^ 1;
1244 // println!("{buddy_idx:#x?}");
1245 <AvlBuddy as BuddyCollection>::put(
1246 &mut avl_buddy,
1247 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1248 );
1249 <AvlBuddy as BuddyCollection>::put(
1250 &mut avl_buddy,
1251 (vec[6].as_ptr() as usize) >> ORDER_LEVEL,
1252 );
1253 <AvlBuddy as BuddyCollection>::put(
1254 &mut avl_buddy,
1255 (vec[10].as_ptr() as usize) >> ORDER_LEVEL,
1256 );
1257 <AvlBuddy as BuddyCollection>::put(
1258 &mut avl_buddy,
1259 (vec[4].as_ptr() as usize) >> ORDER_LEVEL,
1260 );
1261 <AvlBuddy as BuddyCollection>::put(
1262 &mut avl_buddy,
1263 (vec[9].as_ptr() as usize) >> ORDER_LEVEL,
1264 );
1265 <AvlBuddy as BuddyCollection>::put(
1266 &mut avl_buddy,
1267 (vec[12].as_ptr() as usize) >> ORDER_LEVEL,
1268 );
1269 <AvlBuddy as BuddyCollection>::put(
1270 &mut avl_buddy,
1271 (vec[2].as_ptr() as usize) >> ORDER_LEVEL,
1272 );
1273 <AvlBuddy as BuddyCollection>::put(
1274 &mut avl_buddy,
1275 (vec[11].as_ptr() as usize) >> ORDER_LEVEL,
1276 );
1277 // println!("{avl_buddy:#x?}");
1278 <AvlBuddy as BuddyCollection>::put(&mut avl_buddy, buddy_idx);
1279 // println!("{avl_buddy:#x?}");
1280 assert_eq!(avl_buddy.tree.0.unwrap(), vec[8]);
1281 assert_eq!(
1282 unsafe { avl_buddy.tree.0.unwrap().as_ref().r.0.unwrap() },
1283 vec[11]
1284 );
1285 }
1286 #[test]
1287 fn test_for_delete_root() {
1288 let vec = create_nonnull_list();
1289 // println!("{}", vec.len());
1290 let mut avl_buddy = AvlBuddy::EMPTY;
1291 avl_buddy.init(ORDER_LEVEL, vec[0].as_ptr() as usize);
1292
1293 <AvlBuddy as BuddyCollection>::put(
1294 &mut avl_buddy,
1295 (vec[8].as_ptr() as usize) >> ORDER_LEVEL,
1296 );
1297 let a = <AvlBuddy as BuddyCollection>::take_any(&mut avl_buddy, 0);
1298
1299 assert_eq!(avl_buddy.tree.0, None);
1300 }
1301}