osom_lib_hash_tables/bytell/hash_table/
bytell_mutable.rs

1use core::{borrow::Borrow, hash::Hash, marker::PhantomData};
2
3use osom_lib_macros::debug_check_or_release_hint;
4use osom_lib_primitives::power_of_two::PowerOfTwo32;
5
6use crate::{
7    bytell::{
8        configuration::BytellConfig,
9        hash_table::{BytellHashTable, block_layout::BlockLayoutHolder, control_byte::ControlByte, entry::Entry},
10    },
11    helpers::{KVP, ptr_to_mut, ptr_to_ref},
12    traits::MutableHashTable,
13};
14
15struct BytellMutableIter<'a, TKey: 'a, TValue: 'a, TConfig> {
16    data: *mut u8,
17    last_element_index: u32,
18    blocks_count: PowerOfTwo32,
19    _marker: PhantomData<(&'a TKey, &'a mut TValue, TConfig)>,
20}
21
22impl<'a, TKey: 'a, TValue: 'a, TConfig> BytellMutableIter<'a, TKey, TValue, TConfig>
23where
24    TKey: Eq + Hash,
25    TConfig: BytellConfig,
26{
27    pub const fn from_hash_table(
28        table: &'a BytellHashTable<TKey, TValue, TConfig>,
29    ) -> BytellMutableIter<'a, TKey, TValue, TConfig> {
30        Self {
31            data: table.data,
32            last_element_index: 0,
33            blocks_count: table.blocks_count,
34            _marker: PhantomData,
35        }
36    }
37}
38
39impl<'a, TKey: 'a, TValue: 'a, TConfig> Iterator for BytellMutableIter<'a, TKey, TValue, TConfig> {
40    type Item = (&'a TKey, &'a mut TValue);
41
42    fn next(&mut self) -> Option<Self::Item> {
43        let elements_count = BlockLayoutHolder::<TKey, TValue>::LAYOUT.block_capacity().value();
44        let capacity = self.blocks_count.value() * elements_count;
45        let mut el_idx = self.last_element_index;
46
47        loop {
48            unsafe {
49                if el_idx == capacity {
50                    self.last_element_index = el_idx;
51                    return None;
52                }
53
54                let entry = Entry::<TKey, TValue>::new(self.data, self.blocks_count, el_idx as usize);
55                el_idx += 1;
56
57                if !(*entry.control_byte()).contains_data() {
58                    continue;
59                }
60
61                let kvp = ptr_to_mut!(entry.kvp());
62                self.last_element_index = el_idx;
63                return Some((&kvp.key, &mut kvp.value));
64            }
65        }
66    }
67}
68
69impl<TKey, TValue, TConfig> MutableHashTable<TKey, TValue> for BytellHashTable<TKey, TValue, TConfig>
70where
71    TKey: Eq + Hash,
72    TConfig: BytellConfig,
73{
74    #[inline]
75    fn insert(&mut self, key: TKey, value: TValue) -> Option<TValue> {
76        let value_ptr = &raw const value;
77        let adder = || unsafe { value_ptr.read() };
78
79        let mut result: Option<TValue> = None;
80        let updater = |current: &mut TValue| {
81            let value = unsafe { value_ptr.read() };
82            let old_value = core::mem::replace(current, value);
83            result = Some(old_value);
84        };
85
86        let _ = self.insert_or_update_with(key, adder, updater);
87        core::mem::forget(value);
88        result
89    }
90
91    #[inline(never)]
92    fn remove_entry<Q>(&mut self, key: &Q) -> Option<(TKey, TValue)>
93    where
94        TKey: Borrow<Q>,
95        Q: Eq + Hash + ?Sized,
96    {
97        if self.blocks_count.value() == 0 {
98            return None;
99        }
100
101        unsafe {
102            let mut entry = self.get_entry_by_key(key);
103            let control_byte = ptr_to_ref!(entry.control_byte());
104            if !control_byte.is_direct_hit() {
105                return None;
106            }
107            let mut entry_parent = None;
108
109            loop {
110                if ptr_to_ref!(entry.kvp()).key.borrow() == key {
111                    break;
112                }
113
114                if let Some(next) = entry.next_link() {
115                    entry_parent = Some(entry);
116                    entry = next;
117                    continue;
118                }
119
120                return None;
121            }
122
123            // Swap found entry with the tail
124            {
125                let mut tail_parent = None;
126                let tail = {
127                    let mut current_entry = entry.clone();
128                    loop {
129                        if let Some(next) = current_entry.next_link() {
130                            tail_parent = Some(current_entry);
131                            current_entry = next;
132                        } else {
133                            break current_entry;
134                        }
135                    }
136                };
137
138                if tail != entry {
139                    let tail_kvp = ptr_to_mut!(tail.kvp());
140                    let entry_kvp = ptr_to_mut!(entry.kvp());
141                    core::mem::swap(tail_kvp, entry_kvp);
142                    entry_parent = tail_parent;
143                    entry = tail;
144                }
145            }
146
147            if let Some(acutal_entry_parent) = entry_parent {
148                ptr_to_mut!(acutal_entry_parent.control_byte()).set_distance_index(0);
149            }
150
151            let kvp = entry.kvp().read();
152            *ptr_to_mut!(entry.control_byte()) = ControlByte::EMPTY;
153            self.elements_count -= 1;
154            Some((kvp.key, kvp.value))
155        }
156    }
157
158    #[inline(never)]
159    fn insert_or_update_with<FAdd, FUpdate>(&mut self, key: TKey, adder: FAdd, updater: FUpdate) -> &mut TValue
160    where
161        FAdd: FnOnce() -> TValue,
162        FUpdate: FnOnce(&mut TValue),
163    {
164        if self.blocks_count.value() == 0 {
165            self.grow();
166        }
167
168        let mut counter = 0;
169
170        #[allow(clippy::redundant_else)]
171        'start: loop {
172            counter += 1;
173            assert!(counter < 30, "Tried to insert over 30 times. Giving up.");
174
175            unsafe {
176                let entry = self.get_entry_by_key(&key);
177                let control_byte = *entry.control_byte();
178
179                debug_check_or_release_hint!(
180                    control_byte != ControlByte::RESERVED,
181                    "Got reserved here? Should not happen."
182                );
183
184                if control_byte.is_direct_hit() {
185                    let mut entry = entry;
186                    loop {
187                        let kvp = ptr_to_mut!(entry.kvp());
188                        if kvp.key == key {
189                            updater(&mut kvp.value);
190                            return &mut kvp.value;
191                        }
192
193                        if let Some(next) = entry.next_link() {
194                            entry = next;
195                            continue;
196                        }
197
198                        break;
199                    }
200
201                    if self.should_grow() {
202                        self.grow();
203                        continue 'start;
204                    }
205
206                    let Some((free_entry, free_distance_index)) = self.search_for_free_entry(&entry) else {
207                        self.grow();
208                        continue 'start;
209                    };
210
211                    *free_entry.control_byte() = ControlByte::NEW_TAIL;
212                    ptr_to_mut!(entry.control_byte()).set_distance_index(free_distance_index);
213                    let new_kvp = KVP {
214                        key: key,
215                        value: adder(),
216                    };
217                    free_entry.kvp().write(new_kvp);
218                    self.elements_count += 1;
219                    return &mut ptr_to_mut!(free_entry.kvp()).value;
220                } else {
221                    if self.should_grow() {
222                        self.grow();
223                        continue 'start;
224                    }
225
226                    if control_byte != ControlByte::EMPTY {
227                        // It is neither direct hit nor empty. Which means we hit storage entry.
228                        // We need to move around the linked list this entry belongs to.
229
230                        let mut current_parent = self.find_parent_for_storage_entry(&entry);
231                        let mut current_entry = entry.clone();
232
233                        let mut first_iteration = true;
234                        loop {
235                            let Some((free_entry, free_distance_index)) = self.search_for_free_entry(&current_parent)
236                            else {
237                                self.grow();
238                                continue 'start;
239                            };
240
241                            *ptr_to_mut!(free_entry.control_byte()) = ControlByte::NEW_TAIL;
242                            free_entry.kvp().write(current_entry.kvp().read());
243                            ptr_to_mut!(current_parent.control_byte()).set_distance_index(free_distance_index);
244
245                            let new_control = if first_iteration {
246                                first_iteration = false;
247                                ControlByte::RESERVED
248                            } else {
249                                ControlByte::EMPTY
250                            };
251
252                            let next_link = current_entry.next_link();
253                            *current_entry.control_byte() = new_control;
254
255                            let Some(next) = next_link else {
256                                break;
257                            };
258
259                            current_parent = free_entry;
260                            current_entry = next;
261                        }
262                    }
263
264                    self.elements_count += 1;
265                    *entry.control_byte() = ControlByte::NEW_DIRECT_HIT;
266                    let kvp = KVP {
267                        key: key,
268                        value: adder(),
269                    };
270                    entry.kvp().write(kvp);
271                    return &mut ptr_to_mut!(entry.kvp()).value;
272                }
273            }
274        }
275    }
276
277    #[inline(always)]
278    fn iter_mut<'a>(&'a mut self) -> impl Iterator<Item = (&'a TKey, &'a mut TValue)>
279    where
280        TKey: 'a,
281        TValue: 'a,
282        Self: 'a,
283    {
284        BytellMutableIter::from_hash_table(self)
285    }
286}
osom_lib_hash_tables/bytell/hash_table/bytell_mutable.rs

osom_lib_hash_tables/bytell/hash_table/
bytell_mutable.rs
