eta_algorithms/data_structs/
queue.rs

1use crate::utils::{closest_pow2, rotate_inc};
2use std::alloc::{dealloc, realloc, Layout};
3use std::ptr;
4
5pub struct Queue<T>
6where
7    T: Copy + Sized,
8{
9    capacity: usize,
10    len: usize,
11    layout: Layout,
12    data: *mut T,
13    front: usize,
14    end: usize,
15}
16
17impl<T> Queue<T>
18where
19    T: Copy + Sized,
20{
21    pub fn new_pow2_sized(capacity: usize) -> Self {
22        let capacity = closest_pow2(capacity);
23        let layout = Layout::array::<T>(capacity).expect("Failed to create layout");
24        let data = unsafe { std::alloc::alloc(layout) as *mut T };
25        if data.is_null() {
26            panic!("Failed to allocate memory");
27        }
28
29        Queue {
30            capacity,
31            layout,
32            data,
33            len: 0,
34            front: 0,
35            end: 0,
36        }
37    }
38
39    #[inline(always)]
40    pub fn is_empty(&self) -> bool {
41        self.len == 0
42    }
43
44    pub fn extend_pow2_sized(&mut self, capacity_pow: usize) {
45        let new_capacity = closest_pow2(capacity_pow);
46        if new_capacity <= self.capacity {
47            panic!("New capacity is less than or equal to current capacity");
48        }
49
50        let new_layout = Layout::array::<T>(new_capacity).expect("Failed to create layout");
51        // Data can only wrap if data actually exists. We need to do len check.
52        if self.front >= self.end && self.len > 0 {
53            let new_data = unsafe { std::alloc::alloc(new_layout) as *mut T };
54            if new_data.is_null() {
55                panic!("Failed to allocate memory");
56            }
57            let from_front_to_array_end_len = self.capacity() - self.front;
58            let from_start_to_end_len = self.front;
59            unsafe {
60                ptr::copy_nonoverlapping(
61                    self.data.add(self.front),
62                    new_data,
63                    from_front_to_array_end_len,
64                )
65            }; // After Front
66            unsafe {
67                ptr::copy_nonoverlapping(
68                    self.data,
69                    new_data.add(from_front_to_array_end_len),
70                    from_start_to_end_len,
71                )
72            }; // Before Front
73
74            unsafe { dealloc(self.data as *mut u8, self.layout) };
75            self.capacity = new_capacity;
76            self.data = new_data;
77            self.front = 0;
78            self.end = from_front_to_array_end_len + from_start_to_end_len;
79            return;
80        }
81
82        unsafe {
83            self.data = realloc(self.data as *mut u8, new_layout, new_layout.size()) as *mut T;
84            if self.data.is_null() {
85                panic!("Failed to reallocate memory");
86            }
87            self.capacity = new_capacity;
88        }
89    }
90    #[inline(always)]
91    pub fn extend_pow2_sized_by(&mut self, capacity_pow: usize) {
92        if self.capacity < self.capacity + capacity_pow {
93            return;
94        }
95        let new_capacity = closest_pow2(self.capacity + capacity_pow);
96        self.extend_pow2_sized(new_capacity)
97    }
98    #[inline(always)]
99    pub fn capacity(&self) -> usize {
100        self.capacity
101    }
102    #[inline(always)]
103    pub fn len(&self) -> usize {
104        self.len
105    }
106
107    #[inline(always)]
108    pub fn push(&mut self, value: T) {
109        if self.len == self.capacity {
110            panic!("Queue is full");
111        }
112        unsafe {
113            self.data.add(self.end).write(value);
114            self.len += 1;
115            self.end = rotate_inc(self.end, self.capacity - 1);
116        }
117    }
118    #[inline(always)]
119    pub fn front(&self) -> Option<&T> {
120        if self.len == 0 {
121            return None;
122        }
123        unsafe { Some(self.data.add(self.front).as_ref().unwrap()) }
124    }
125    #[inline(always)]
126    pub fn front_mut(&mut self) -> Option<&mut T> {
127        if self.len == 0 {
128            return None;
129        }
130        unsafe { Some(self.data.add(self.front).as_mut().unwrap()) }
131    }
132    #[inline(always)]
133    pub fn dequeue(&mut self) -> Option<T> {
134        if self.len == 0 {
135            return None;
136        }
137        unsafe {
138            let result = Some(self.data.add(self.front).read());
139            self.len -= 1;
140            self.front = rotate_inc(self.front, self.capacity - 1);
141            result
142        }
143    }
144}
145
146impl<T> Drop for Queue<T>
147where
148    T: Copy + Sized,
149{
150    fn drop(&mut self) {
151        unsafe {
152            dealloc(self.data as *mut u8, self.layout);
153        }
154    }
155}
eta_algorithms/data_structs/queue.rs

eta_algorithms/data_structs/
queue.rs
