1use std::collections::TryReserveError;
2
3use crate::{
4 element::{Element, ElementGuard, Hashable},
5 mem::MemChunk,
6};
7
8#[derive(Debug)]
9pub struct HashList<T: Hashable> {
10 chunk: MemChunk<T>,
11}
12
13impl<T: Hashable> HashList<T> {
14 pub fn new() -> Self {
15 Self::with_capacity(4, 2)
16 }
17
18 pub fn with_capacity(hash_size: usize, list_capacity: usize) -> Self {
20 let chunk = MemChunk::<T>::new(hash_size, list_capacity);
21 Self { chunk }
22 }
23
24 pub fn from_vec(vec: Vec<T>) -> Self {
25 let n = vec.len();
26 let mut list = Self::with_capacity(n.max(1).next_power_of_two(), n);
27 for value in vec {
28 list.push(value);
29 }
30 list
31 }
32
33 fn update_hash_index(&mut self, index: usize, old_hash: u32) {
35 debug_assert!(index < self.chunk.list_count);
36
37 let old_hash_index = (old_hash as usize) & self.chunk.hash_mask();
39 let hash_buckets_ptr = self.chunk.hash_buckets_base_mut_ptr();
40 let list_ptr = self.chunk.list_base_mut_ptr();
41
42 unsafe {
43 let mut seq = *hash_buckets_ptr.add(old_hash_index);
44 let mut prev_seq = 0;
45
46 while seq != 0 {
47 let idx = seq - 1;
48 if idx == index {
49 let next = (&*list_ptr.add(index)).next();
51 if prev_seq == 0 {
52 *hash_buckets_ptr.add(old_hash_index) = next; } else {
54 (&mut *list_ptr.add(prev_seq - 1)).set_next(next);
55 }
56 break;
57 }
58
59 prev_seq = seq;
60 seq = (&*list_ptr.add(idx)).next();
61 }
62 }
63
64 unsafe {
65 let element = &*self.chunk.list_base_ptr().add(index);
67 let hash = (element.value().get_hash() as usize) & self.chunk.hash_mask();
68
69 let next =
71 std::ptr::replace(self.chunk.hash_buckets_base_mut_ptr().add(hash), index + 1);
72
73 (&mut *self.chunk.list_base_mut_ptr().add(index)).set_next(next);
74 };
75 }
76
77 #[inline(always)]
79 pub fn push(&mut self, value: T) -> usize {
80 self.chunk.append(value).unwrap()
81 }
82
83 #[inline(always)]
85 pub fn index_of(&self, value: &T) -> Option<usize> {
86 self.chunk.index_of(value)
87 }
88
89 pub const fn remove_index(&mut self, index: usize) -> bool {
91 if index < self.chunk.list_count && !self.chunk.is_deleted(index) {
92 self.chunk.mark_deleted(index);
93 true
94 } else {
95 false
96 }
97 }
98
99 #[inline]
101 pub fn remove(&mut self, value: &T) -> bool {
102 self.index_of(value).is_some_and(|i| self.remove_index(i))
103 }
104
105 #[inline(always)]
107 pub fn compact(&mut self) {
108 self.chunk.compact();
109 }
110
111 #[inline(always)]
113 pub const fn count(&self) -> usize {
114 self.chunk.list_count - self.chunk.count_deleted
115 }
116
117 #[inline(always)]
119 pub const fn len(&self) -> usize {
120 self.chunk.list_count
121 }
122
123 pub const fn is_empty(&self) -> bool {
125 self.count() == 0
126 }
127
128 #[inline(always)]
130 pub const fn capacity(&self) -> usize {
131 self.chunk.list_capacity
132 }
133
134 #[inline(always)]
136 pub const fn hash_bucket_count(&self) -> usize {
137 self.chunk.hash_count
138 }
139
140 #[inline(always)]
142 pub const fn count_deleted(&self) -> usize {
143 self.chunk.count_deleted
144 }
145
146 #[inline(always)]
147 pub(super) const unsafe fn get_mut_unchecked(&mut self, index: usize) -> &mut Element<T> {
148 unsafe { self.chunk.element_mut(index) }
149 }
150
151 pub const fn get(&self, index: usize) -> Option<&T> {
153 if index < self.chunk.list_count {
154 unsafe {
155 let el = self.chunk.element(index);
156 if !el.is_deleted() {
157 return Some(el.value());
158 }
159 }
160 }
161 None
162 }
163
164 pub fn get_mut(&mut self, index: usize) -> Option<ElementGuard<'_, T>> {
166 if index < self.chunk.list_count && !self.chunk.is_deleted(index) {
167 let this_ptr = self as *mut Self;
168
169 unsafe {
170 let el = self.get_mut_unchecked(index);
171 Some(ElementGuard::new(
172 index,
173 el.value_mut(),
174 move |idx: usize, old_hash: u32| {
175 let this = &mut *this_ptr;
176 this.update_hash_index(idx, old_hash);
177 },
178 ))
179 }
180 } else {
181 None
182 }
183 }
184
185 pub fn first(&self) -> Option<&T> {
187 for i in 0..self.chunk.list_count {
189 if !self.chunk.is_deleted(i) {
190 return self.get(i);
191 }
192 }
193 None
194 }
195
196 pub fn last(&self) -> Option<&T> {
198 for i in (0..self.chunk.list_count).rev() {
199 if !self.chunk.is_deleted(i) {
200 return self.get(i);
201 }
202 }
203 None
204 }
205
206 #[inline(always)]
207 pub fn clear(&mut self) {
208 self.chunk.clear();
209 }
210
211 pub fn contains(&self, value: &T) -> bool {
213 self.index_of(value).is_some()
214 }
215
216 pub fn try_reserve(&mut self, additional: usize) -> Result<(), TryReserveError> {
218 let cap = self.chunk.list_count + additional;
219 if cap > self.chunk.list_capacity {
220 self.chunk.resize(self.chunk.hash_count, cap)
221 } else {
222 Ok(())
223 }
224 }
225
226 #[inline(always)]
228 pub fn reserve(&mut self, additional: usize) {
229 self.try_reserve(additional).unwrap()
230 }
231
232 #[inline(always)]
234 pub fn shrink_to_fit(&mut self) {
235 self.chunk.shrink_to_fit().unwrap();
236 }
237
238 pub const fn iter(&self) -> HashLinkIter<'_, T> {
240 HashLinkIter {
241 container: self,
242 index: 0,
243 }
244 }
245
246 pub const fn find_hash(&self, hash: u32) -> HashLinkFindIter<'_, T> {
249 HashLinkFindIter {
250 container: self,
251 seq: unsafe {
252 *self
253 .chunk
254 .hash_buckets_base_ptr()
255 .add(hash as usize & self.chunk.hash_mask())
256 },
257 expected_hash: hash,
258 }
259 }
260}
261
262pub struct HashLinkIter<'a, T: Hashable> {
264 container: &'a HashList<T>,
265 index: usize,
266}
267
268impl<'a, T: Hashable> Iterator for HashLinkIter<'a, T> {
269 type Item = (usize, &'a T);
270
271 fn next(&mut self) -> Option<Self::Item> {
272 while self.index < self.container.chunk.list_count {
273 let i = self.index;
274 self.index += 1;
275
276 unsafe {
277 let el = self.container.chunk.element(i);
278 if !el.is_deleted() {
279 return Some((i, el.value()));
280 }
281 }
282 }
283
284 None
285 }
286}
287
288pub struct HashLinkFindIter<'a, T: Hashable> {
290 container: &'a HashList<T>,
291 seq: usize,
292 expected_hash: u32,
293}
294
295impl<'a, T: Hashable> Iterator for HashLinkFindIter<'a, T> {
296 type Item = (usize, &'a T);
297
298 fn next(&mut self) -> Option<Self::Item> {
299 while self.seq != 0 {
300 let index = self.seq - 1;
301
302 if index < self.container.chunk.list_count {
303 unsafe {
304 let el = self.container.chunk.element(index);
305 self.seq = el.next();
306 if el.value().get_hash() == self.expected_hash && !el.is_deleted() {
309 return Some((index, el.value()));
310 }
311 }
312 } else {
313 self.seq = 0; }
315 }
316
317 None
318 }
319}