eta_algorithms/data_structs/
stack.rs

1use std::alloc::{realloc, Layout};
2use std::fmt::Debug;
3use std::ops::{Index, IndexMut};
4use std::ptr;
5
6pub struct Stack<T>
7where
8    T: Copy + Sized,
9{
10    capacity: usize,
11    len: usize,
12    layout: Layout,
13    data: *mut T,
14    top: *mut T,
15    end: *mut T,
16}
17
18impl<T> Stack<T>
19where
20    T: Copy + Sized,
21{
22    #[inline(always)]
23    pub fn capacity(&self) -> usize {
24        self.capacity
25    }
26    #[inline(always)]
27    pub fn len(&self) -> usize {
28        self.len
29    }
30    pub fn new(capacity: usize) -> Self {
31        let layout = Layout::array::<T>(capacity).expect("Failed to create layout");
32        let data = unsafe { std::alloc::alloc(layout) as *mut T };
33        if data.is_null() {
34            panic!("Failed to allocate memory");
35        }
36
37        Stack {
38            capacity,
39            layout,
40            data,
41            len: 0,
42            top: unsafe { data.offset(-1) },
43            end: unsafe { data.add(capacity) },
44        }
45    }
46
47    #[inline(always)]
48    pub fn is_empty(&self) -> bool {
49        self.len == 0
50    }
51
52    pub fn extend(&mut self, new_capacity: usize) {
53        let new_layout = Layout::array::<T>(new_capacity).expect("Failed to create layout");
54        unsafe {
55            self.data = realloc(self.data as *mut u8, new_layout, new_layout.size()) as *mut T;
56            if self.data.is_null() {
57                panic!("Failed to reallocate memory");
58            }
59            self.end = self.data.add(new_capacity);
60            self.top = self.data.offset((self.len as isize) - 1);
61        }
62        self.capacity = new_capacity;
63        self.layout = new_layout;
64    }
65    #[inline(always)]
66    pub fn extend_by(&mut self, additional_capacity: usize) {
67        self.extend(self.capacity + additional_capacity);
68    }
69    #[inline(always)]
70    pub fn top(&self) -> Option<&T> {
71        if self.len == 0 {
72            return None;
73        }
74        unsafe { Some(self.top.as_ref().unwrap()) }
75    }
76    #[inline(always)]
77    pub fn top_mut(&mut self) -> Option<&mut T> {
78        if self.len == 0 {
79            return None;
80        }
81        unsafe { Some(self.top.as_mut().unwrap()) }
82    }
83    #[inline(always)]
84    pub fn push(&mut self, value: T) {
85        let new_top = unsafe { self.top.offset(1) };
86        if new_top == self.end {
87            panic!("Stack over capacity!");
88        }
89
90        self.top = new_top;
91        unsafe { self.top.write(value) };
92        self.len += 1;
93    }
94    #[inline(always)]
95    pub fn pop(&mut self) -> Option<T> {
96        if self.len == 0 {
97            return None;
98        }
99
100        unsafe {
101            let result = Some(ptr::read(self.top));
102            self.top = self.top.offset(-1);
103            self.len -= 1;
104            result
105        }
106    }
107}
108
109impl<T> Debug for Stack<T>
110where
111    T: Copy + Sized + Debug,
112{
113    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
114        write!(f, "Stack [len={}, cap={}] [", self.len, self.capacity)?;
115        unsafe {
116            let mut pivot = self.data;
117            let end = self.top.add(1);
118            while pivot != end {
119                let value = pivot.read();
120                write!(f, " {:?}", value)?;
121                pivot = pivot.add(1);
122            }
123        }
124        write!(f, " ]")?;
125        Ok(())
126    }
127}
128
129impl<T> Index<isize> for Stack<T>
130where
131    T: Copy + Sized,
132{
133    type Output = T;
134    #[inline(always)]
135    fn index(&self, index: isize) -> &Self::Output {
136        if index > 0 {
137            panic!("Index out of bounds");
138        }
139
140        if index <= -(self.len as isize) {
141            panic!("Index out of bounds");
142        }
143
144        let indexed_data = unsafe { self.top.offset(index) };
145        unsafe { indexed_data.as_ref().unwrap() }
146    }
147}
148
149impl<T> IndexMut<isize> for Stack<T>
150where
151    T: Copy + Sized,
152{
153    #[inline(always)]
154    fn index_mut(&mut self, index: isize) -> &mut Self::Output {
155        if index > 0 {
156            panic!("Index out of bounds");
157        }
158
159        if index < -(self.len as isize) {
160            panic!("Index out of bounds");
161        }
162
163        let indexed_data = unsafe { self.top.offset(index) };
164        unsafe { indexed_data.as_mut().unwrap() }
165    }
166}
167
168impl<T> Drop for Stack<T>
169where
170    T: Copy + Sized,
171{
172    fn drop(&mut self) {
173        unsafe {
174            std::alloc::dealloc(self.data as *mut u8, self.layout);
175        }
176    }
177}
eta_algorithms/data_structs/stack.rs

eta_algorithms/data_structs/
stack.rs
