Use LFIO queue for allocator

1 files changed, 54 insertions, 52 deletions

diff --git a/src/mem/alloc.rs b/src/mem/alloc.rs
index 1c32a38..307be5c 100644
--- a/src/mem/alloc.rs
+++ b/src/mem/alloc.rs
@@ -7,8 +7,10 @@ use crate::sync::NullLock;
 use crate::sync::interface::Mutex;
 use crate::vprintln;
 use super::types::*;
-use crate::util::{QueueAllocator,QueueItem};
-use crate::init_queue;
+use os_pic::util::node::Node;
+use os_pic::util::lifo_queue::LifoQueue;
+use os_pic::init_lifo_queue;
+use os_pic::util::queue::Queue;
 
 /// # Grand Allocator
 ///
@@ -18,16 +20,16 @@ pub struct GrandAllocator { }
 /// # The number of elements of each size
 const GRAND_ALLOC_SIZE: usize = 64;
 
-init_queue!(U8_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u8);
-init_queue!(U16_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u16);
-init_queue!(U32_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u32);
-init_queue!(U64_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u64);
-init_queue!(U128_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u128);
-init_queue!(U256_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U256::new()}, U256);
-init_queue!(U512_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U512::new()}, U512);
-init_queue!(U1024_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U1024::new()}, U1024);
-init_queue!(U2048_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U2048::new()}, U2048);
-init_queue!(U4096_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U4096::new()}, U4096);
+init_lifo_queue!(U8_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u8);
+init_lifo_queue!(U16_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u16);
+init_lifo_queue!(U32_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u32);
+init_lifo_queue!(U64_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u64);
+init_lifo_queue!(U128_GRAND_ALLOC, GRAND_ALLOC_SIZE, 0, u128);
+init_lifo_queue!(U256_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U256::new()}, U256);
+init_lifo_queue!(U512_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U512::new()}, U512);
+init_lifo_queue!(U1024_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U1024::new()}, U1024);
+init_lifo_queue!(U2048_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U2048::new()}, U2048);
+init_lifo_queue!(U4096_GRAND_ALLOC, GRAND_ALLOC_SIZE, {U4096::new()}, U4096);
 
 impl GrandAllocator {
 	pub fn init(&self) -> Result<(), &'static str> {
@@ -64,7 +66,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 		vprintln!("GA: Allocating chunk of size {}!", layout.size());
 		match layout.size() {
 			1 => {
-				match U8_GRAND_ALLOC.alloc() {
+				match U8_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -74,7 +76,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			2 => {
-				match U16_GRAND_ALLOC.alloc() {
+				match U16_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -84,7 +86,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			3..=4 => {
-				match U32_GRAND_ALLOC.alloc() {
+				match U32_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -94,7 +96,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			5..=8 => {
-				match U64_GRAND_ALLOC.alloc() {
+				match U64_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -104,7 +106,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			9..=16 => {
-				match U128_GRAND_ALLOC.alloc() {
+				match U128_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -114,7 +116,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			17..=32 => {
-				match U256_GRAND_ALLOC.alloc() {
+				match U256_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -124,7 +126,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			33..=64 => {
-				match U512_GRAND_ALLOC.alloc() {
+				match U512_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -134,7 +136,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			65..=128 => {
-				match U1024_GRAND_ALLOC.alloc() {
+				match U1024_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -144,7 +146,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			129..=256 => {
-				match U2048_GRAND_ALLOC.alloc() {
+				match U2048_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -154,7 +156,7 @@ unsafe impl GlobalAlloc for GrandAllocator {
 				}
 			}
 			257..=512 => {
-				match U4096_GRAND_ALLOC.alloc() {
+				match U4096_GRAND_ALLOC.pop() {
 					None => {
 						panic!("No cells to allocate!");
 					}
@@ -177,111 +179,111 @@ unsafe impl GlobalAlloc for GrandAllocator {
 		match layout.size() {
 			1 => {
 				U8_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U8_GRAND_ALLOC.free(&mut pool[index+2]);
+					U8_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			2 => {
 				U16_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U16_GRAND_ALLOC.free(&mut pool[index+2]);
+					U16_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			3..=4 => {
 				U32_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U32_GRAND_ALLOC.free(&mut pool[index+2]);
+					U32_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			5..=8 => {
 				U64_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U64_GRAND_ALLOC.free(&mut pool[index+2]);
+					U64_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			9..=16 => {
 				U128_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U128_GRAND_ALLOC.free(&mut pool[index+2]);
+					U128_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			17..=32 => {
 				U256_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U256_GRAND_ALLOC.free(&mut pool[index+2]);
+					U256_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			33..=64 => {
 				U512_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U512_GRAND_ALLOC.free(&mut pool[index+2]);
+					U512_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			65..=128 => {
 				U1024_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U1024_GRAND_ALLOC.free(&mut pool[index+2]);
+					U1024_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			129..=256 => {
 				U2048_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U2048_GRAND_ALLOC.free(&mut pool[index+2]);
+					U2048_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}
 			257..=512 => {
 				U4096_GRAND_ALLOC.inner.lock(|pool| {
-					let spacing: usize = (pool[3].ptr() as usize) - (pool[2].ptr() as usize);
-					let diff: usize = (ptr as usize) - (pool[2].ptr() as usize);
+					let spacing: usize = (pool[2].ptr() as usize) - (pool[1].ptr() as usize);
+					let diff: usize = (ptr as usize) - (pool[1].ptr() as usize);
 					let index: usize = diff/spacing;
 					assert!(index < GRAND_ALLOC_SIZE, "{} is out of the allocation bounds ({})", index, GRAND_ALLOC_SIZE);
 					assert_eq!(diff % spacing, 0, "{} is not aligned with the spacings and so it must not have been allocated by the Grand Allocator", diff % spacing);
-					U4096_GRAND_ALLOC.free(&mut pool[index+2]);
+					U4096_GRAND_ALLOC.push(&mut pool[index+1]);
 					vprintln!("GA: Freeing ({}, {}, {})", index, diff, spacing);
 				});
 			}