O(1) deallocation

2 files changed, 55 insertions, 43 deletions

diff --git a/src/mem.rs b/src/mem.rs
index 920965d..099532b 100644
--- a/src/mem.rs
+++ b/src/mem.rs
@@ -1 +1,4 @@
+//! Memory crate
+//!
+//! Provides the Allocator for the OS.
 pub mod alloc;
diff --git a/src/mem/alloc.rs b/src/mem/alloc.rs
index a361cf4..bb22ba6 100644
--- a/src/mem/alloc.rs
+++ b/src/mem/alloc.rs
@@ -1,4 +1,7 @@
-//! # Allocate
+//! # Allocate crate
+//!
+//! Provides the Global allocator and methods
+//! to create special purpose allocators.
 use alloc::alloc::{GlobalAlloc,Layout};
 use crate::sync::NullLock;
 use crate::sync::interface::Mutex;
@@ -268,68 +271,74 @@ unsafe impl GlobalAlloc for GrandAllocator {
 		match layout.size() {
 			1 => {
 				U8_GRAND_ALLOC.inner.lock(|pool| {
-					for idx in 2..pool.len() {
-						if pool[idx].ptr() == ptr {
-							U8_GRAND_ALLOC.free(&mut pool[idx]);
-							return;
-						}
-					}
-					panic!("Didn't deallocate!");
+					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 index: usize = diff/spacing;
+					assert!(index < GRAND_ALLOC_SIZE);
+					assert_eq!(diff % spacing, 0);
+					U8_GRAND_ALLOC.free(&mut pool[index]);
+					#[cfg(_DEBUG_)]
+					crate::println!("{:?}", diff/spacing);
 				});
 			}
 			2 => {
 				U16_GRAND_ALLOC.inner.lock(|pool| {
-					for idx in 2..pool.len() {
-						if pool[idx].ptr() == ptr {
-							U16_GRAND_ALLOC.free(&mut pool[idx]);
-							return;
-						}
-					}
-					panic!("Didn't deallocate!");
+					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 index: usize = diff/spacing;
+					assert!(index < GRAND_ALLOC_SIZE);
+					assert_eq!(diff % spacing, 0);
+					U16_GRAND_ALLOC.free(&mut pool[index]);
+					#[cfg(_DEBUG_)]
+					crate::println!("{:?}", diff/spacing);
 				});
 			}
 			3..=4 => {
 				U32_GRAND_ALLOC.inner.lock(|pool| {
-					for idx in 2..pool.len() {
-						if pool[idx].ptr() == ptr {
-							U32_GRAND_ALLOC.free(&mut pool[idx]);
-							return;
-						}
-					}
-					panic!("Didn't deallocate!");
+					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 index: usize = diff/spacing;
+					assert!(index < GRAND_ALLOC_SIZE);
+					assert_eq!(diff % spacing, 0);
+					U32_GRAND_ALLOC.free(&mut pool[index]);
+					#[cfg(_DEBUG_)]
+					crate::println!("{:?}", diff/spacing);
 				});
 			}
 			5..=8 => {
 				U64_GRAND_ALLOC.inner.lock(|pool| {
-					for idx in 2..pool.len() {
-						if pool[idx].ptr() == ptr {
-							U64_GRAND_ALLOC.free(&mut pool[idx]);
-							return;
-						}
-					}
-					panic!("Didn't deallocate!");
+					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 index: usize = diff/spacing;
+					assert!(index < GRAND_ALLOC_SIZE);
+					assert_eq!(diff % spacing, 0);
+					U64_GRAND_ALLOC.free(&mut pool[index]);
+					#[cfg(_DEBUG_)]
+					crate::println!("{:?}", diff/spacing);
 				});
 			}
 			9..=16 => {
 				U128_GRAND_ALLOC.inner.lock(|pool| {
-					for idx in 2..pool.len() {
-						if pool[idx].ptr() == ptr {
-							U128_GRAND_ALLOC.free(&mut pool[idx]);
-							return;
-						}
-					}
-					panic!("Didn't deallocate!");
+					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 index: usize = diff/spacing;
+					assert!(index < GRAND_ALLOC_SIZE);
+					assert_eq!(diff % spacing, 0);
+					U128_GRAND_ALLOC.free(&mut pool[index]);
+					#[cfg(_DEBUG_)]
+					crate::println!("{:?}", diff/spacing);
 				});
 			}
 			17..=32 => {
 				U256_GRAND_ALLOC.inner.lock(|pool| {
-					for idx in 2..pool.len() {
-						if pool[idx].ptr() == ptr {
-							U256_GRAND_ALLOC.free(&mut pool[idx]);
-							return;
-						}
-					}
-					panic!("Didn't deallocate!");
+					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 index: usize = diff/spacing;
+					assert!(index < GRAND_ALLOC_SIZE);
+					assert_eq!(diff % spacing, 0);
+					U256_GRAND_ALLOC.free(&mut pool[index]);
+					#[cfg(_DEBUG_)]
+					crate::println!("{:?}", diff/spacing);
 				});
 			}
 			_ => {