From a36c3e86e2030ec91900dcab9b0ebc770960b31b Mon Sep 17 00:00:00 2001
From: Christian Cunningham <cc@localhost>
Date: Sat, 20 Aug 2022 12:49:33 -0700
Subject: O(1) deallocation

---
 src/mem/alloc.rs | 95 +++++++++++++++++++++++++++++++-------------------------
 1 file changed, 52 insertions(+), 43 deletions(-)

(limited to 'src/mem/alloc.rs')

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);
 				});
 			}
 			_ => {
-- 
cgit v1.2.1