Skip to main content

hash_link/
element.rs

1pub trait Hashable: PartialEq {
2    /// Returns the hash value of the element
3    ///
4    /// This function should provide fast, simple hash computation
5    fn get_hash(&self) -> u32;
6}
7
8pub(crate) struct Element<T: Hashable> {
9    value: T,
10
11    /// bit 31: deleted flag
12    /// bit 0..30: Seq of next element in same hash bucket, equals to element's list_index+1. 0 means end of chain.
13    del_and_next: u32,
14}
15
16impl<T: Hashable + std::fmt::Debug> std::fmt::Debug for Element<T> {
17    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
18        f.debug_struct("Element")
19            .field("value", &self.value)
20            .field("next", &self.next())
21            .field("deleted", &self.is_deleted())
22            .finish()
23    }
24}
25
26impl<T: Hashable> Element<T> {
27    pub const fn new(value: T, next: usize) -> Self {
28        debug_assert!(next <= 0x7FFF_FFFF);
29        Self {
30            value,
31            del_and_next: next as u32,
32        }
33    }
34
35    #[inline(always)]
36    pub const unsafe fn value(&self) -> &T {
37        &self.value
38    }
39
40    #[inline(always)]
41    pub const unsafe fn value_mut(&mut self) -> &mut T {
42        &mut self.value
43    }
44
45    #[inline(always)]
46    pub const fn next(&self) -> usize {
47        (self.del_and_next & 0x7FFF_FFFF) as usize
48    }
49
50    #[inline(always)]
51    pub const fn set_next(&mut self, seq: usize) {
52        debug_assert!(seq <= 0x7FFF_FFFF);
53        self.del_and_next = (self.del_and_next & !0x7FFF_FFFF) | seq as u32;
54    }
55
56    #[inline(always)]
57    pub const fn is_deleted(&self) -> bool {
58        self.del_and_next & 0x8000_0000 != 0
59    }
60
61    #[inline(always)]
62    pub const fn set_deleted(&mut self) {
63        self.del_and_next |= 0x8000_0000;
64    }
65}
66
67//
68// Implement Hashable for common types
69//
70
71impl Hashable for usize {
72    #[inline(always)]
73    fn get_hash(&self) -> u32 {
74        // For usize, return itself as hash value directly
75        *self as u32
76    }
77}
78
79impl Hashable for u32 {
80    #[inline(always)]
81    fn get_hash(&self) -> u32 {
82        *self
83    }
84}
85
86impl Hashable for i32 {
87    #[inline(always)]
88    fn get_hash(&self) -> u32 {
89        *self as u32
90    }
91}
92
93impl Hashable for [u8] {
94    fn get_hash(&self) -> u32 {
95        let mut hash: u32 = 2166136261;
96        for &byte in self {
97            hash ^= byte as u32;
98            hash = hash.wrapping_mul(16777619);
99        }
100        hash
101    }
102}
103
104impl Hashable for str {
105    #[inline]
106    fn get_hash(&self) -> u32 {
107        self.as_bytes().get_hash()
108    }
109}
110
111impl Hashable for String {
112    #[inline]
113    fn get_hash(&self) -> u32 {
114        self.as_bytes().get_hash()
115    }
116}
117
118/// Element guard for safely modifying elements while maintaining hash index synchronization
119pub struct ElementGuard<'a, T: Hashable> {
120    /// Original hash value (captures hash before modification)
121    original_hash: u32,
122    /// Element index position
123    index: usize,
124    /// Mutable reference inside guard
125    value: &'a mut T,
126    /// Hash update callback function
127    update_callback: Option<Box<dyn FnOnce(usize, u32) + 'a>>,
128}
129
130impl<'a, T: Hashable> std::ops::Deref for ElementGuard<'a, T> {
131    type Target = T;
132
133    #[inline(always)]
134    fn deref(&self) -> &Self::Target {
135        self.value
136    }
137}
138
139impl<'a, T: Hashable> std::ops::DerefMut for ElementGuard<'a, T> {
140    #[inline(always)]
141    fn deref_mut(&mut self) -> &mut Self::Target {
142        self.value
143    }
144}
145
146impl<'a, T: Hashable> Drop for ElementGuard<'a, T> {
147    fn drop(&mut self) {
148        // If hash was changed, need to update hash bucket
149        if self.value.get_hash() != self.original_hash
150            && let Some(f) = self.update_callback.take()
151        {
152            f(self.index, self.original_hash);
153        }
154    }
155}
156
157impl<'a, T: Hashable> ElementGuard<'a, T> {
158    pub(super) fn new(
159        index: usize,
160        value: &'a mut T,
161        update_fn: impl FnOnce(usize, u32) + 'a,
162    ) -> Self {
163        ElementGuard {
164            original_hash: value.get_hash(),
165            index,
166            value,
167            update_callback: Some(Box::new(update_fn)),
168        }
169    }
170
171    /// Get original hash value
172    #[inline(always)]
173    pub const fn original_hash(&self) -> u32 {
174        self.original_hash
175    }
176
177    /// Get current hash value
178    #[inline(always)]
179    pub fn current_hash(&self) -> u32 {
180        self.value.get_hash()
181    }
182
183    /// Check if hash value changed
184    pub fn hash_changed(&self) -> bool {
185        self.current_hash() != self.original_hash()
186    }
187}