Skip to main content

hash_link/
list.rs

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    /// Constructor with specified initial capacity
19    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    /// Update element's hash index (internal method, called by ElementGuard)
34    fn update_hash_index(&mut self, index: usize, old_hash: u32) {
35        debug_assert!(index < self.chunk.list_count);
36
37        // Remove element from old hash bucket
38        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                    // Find element to remove
50                    let next = (&*list_ptr.add(index)).next();
51                    if prev_seq == 0 {
52                        *hash_buckets_ptr.add(old_hash_index) = next; // Is list head
53                    } 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            // Add element to new hash bucket
66            let element = &*self.chunk.list_base_ptr().add(index);
67            let hash = (element.value().get_hash() as usize) & self.chunk.hash_mask();
68
69            // Head insertion: insert element at head of new hash bucket
70            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    /// Append a new element, returns element index
78    #[inline(always)]
79    pub fn push(&mut self, value: T) -> usize {
80        self.chunk.append(value).unwrap()
81    }
82
83    /// Find index of given `value`.
84    #[inline(always)]
85    pub fn index_of(&self, value: &T) -> Option<usize> {
86        self.chunk.index_of(value)
87    }
88
89    /// Remove by index
90    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    /// Remove by value
100    #[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    /// Compact list, purge deleted elements
106    #[inline(always)]
107    pub fn compact(&mut self) {
108        self.chunk.compact();
109    }
110
111    /// Get count of valid elements
112    #[inline(always)]
113    pub const fn count(&self) -> usize {
114        self.chunk.list_count - self.chunk.count_deleted
115    }
116
117    /// Get count of list valid + deleted elements
118    #[inline(always)]
119    pub const fn len(&self) -> usize {
120        self.chunk.list_count
121    }
122
123    /// Check if empty
124    pub const fn is_empty(&self) -> bool {
125        self.count() == 0
126    }
127
128    /// Get list capacity
129    #[inline(always)]
130    pub const fn capacity(&self) -> usize {
131        self.chunk.list_capacity
132    }
133
134    /// Get hash bucket count
135    #[inline(always)]
136    pub const fn hash_bucket_count(&self) -> usize {
137        self.chunk.hash_count
138    }
139
140    /// Get number of deleted elements
141    #[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    /// Get value by index (if exists and not deleted)
152    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    /// Get value mutable by index (if exists and not deleted)
165    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    /// Get reference to first valid element
186    pub fn first(&self) -> Option<&T> {
187        // Find first non-deleted element from front to back
188        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    /// Get reference to last valid element
197    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    /// Check if contains specified element
212    pub fn contains(&self, value: &T) -> bool {
213        self.index_of(value).is_some()
214    }
215
216    /// Try to reserve capacity for at least additional more elements
217    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    /// List capacity reservation
227    #[inline(always)]
228    pub fn reserve(&mut self, additional: usize) {
229        self.try_reserve(additional).unwrap()
230    }
231
232    /// List capacity shrink
233    #[inline(always)]
234    pub fn shrink_to_fit(&mut self) {
235        self.chunk.shrink_to_fit().unwrap();
236    }
237
238    /// Iterate valid values with its index, in insertion order
239    pub const fn iter(&self) -> HashLinkIter<'_, T> {
240        HashLinkIter {
241            container: self,
242            index: 0,
243        }
244    }
245
246    /// Iterate values matching given hash.
247    /// Note: will actually iterator in reversed order of insertion, if many elements match the same hash.
248    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
262/// HashList indexed iterator, traverses valid elements and their indices in insertion order
263pub 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
288/// Iterator for finding elements by hash value
289pub 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                    // Buckets are selected by masked hash bits only, so the chain can
307                    // still contain entries whose full hash differs from expected_hash.
308                    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; // iter is end
314            }
315        }
316
317        None
318    }
319}