osom_lib_hash_tables/bytell/hash_table/
bytell_immutable.rs

1use core::{borrow::Borrow, hash::Hash, marker::PhantomData};
2
3use osom_lib_primitives::{length::Length, power_of_two::PowerOfTwo32};
4
5use crate::{
6    bytell::{
7        configuration::BytellConfig,
8        hash_table::{BytellHashTable, block_layout::BlockLayoutHolder, entry::Entry},
9    },
10    helpers::ptr_to_ref,
11    traits::ImmutableHashTable,
12};
13
14struct BytellImmutableIter<'a, TKey: 'a, TValue: 'a, TConfig> {
15    data: *mut u8,
16    last_element_index: u32,
17    blocks_count: PowerOfTwo32,
18    _marker: PhantomData<(&'a TKey, &'a TValue, TConfig)>,
19}
20
21impl<'a, TKey: 'a, TValue: 'a, TConfig> BytellImmutableIter<'a, TKey, TValue, TConfig>
22where
23    TKey: Eq + Hash,
24    TConfig: BytellConfig,
25{
26    #[inline(always)]
27    pub const fn from_hash_table(
28        table: &'a BytellHashTable<TKey, TValue, TConfig>,
29    ) -> BytellImmutableIter<'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 BytellImmutableIter<'a, TKey, TValue, TConfig> {
40    type Item = (&'a TKey, &'a 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_ref!(entry.kvp());
62                self.last_element_index = el_idx;
63                return Some((&kvp.key, &kvp.value));
64            }
65        }
66    }
67}
68
69impl<TKey, TValue, TConfig> ImmutableHashTable<TKey, TValue> for BytellHashTable<TKey, TValue, TConfig>
70where
71    TKey: Eq + Hash,
72    TConfig: BytellConfig,
73{
74    #[inline(always)]
75    fn length(&self) -> Length {
76        self.elements_count
77    }
78
79    #[inline(always)]
80    fn contains<Q>(&self, key: &Q) -> bool
81    where
82        TKey: Borrow<Q>,
83        Q: Eq + Hash + ?Sized,
84    {
85        self.get(key).is_some()
86    }
87
88    #[inline(always)]
89    fn get<Q>(&self, key: &Q) -> Option<&TValue>
90    where
91        TKey: Borrow<Q>,
92        Q: Eq + Hash + ?Sized,
93    {
94        match self.get_key_value(key) {
95            Some(pair) => Some(pair.1),
96            None => None,
97        }
98    }
99
100    #[inline(never)]
101    fn get_key_value<Q>(&self, key: &Q) -> Option<(&TKey, &TValue)>
102    where
103        TKey: Borrow<Q>,
104        Q: Eq + Hash + ?Sized,
105    {
106        if self.blocks_count.value() == 0 {
107            return None;
108        }
109
110        unsafe {
111            let mut entry = self.get_entry_by_key(key);
112            let control_byte = ptr_to_ref!(entry.control_byte());
113            if !control_byte.is_direct_hit() {
114                return None;
115            }
116
117            loop {
118                let kvp = ptr_to_ref!(entry.kvp());
119                if kvp.key.borrow() == key {
120                    return Some((&kvp.key, &kvp.value));
121                }
122                if let Some(next) = entry.next_link() {
123                    entry = next;
124                } else {
125                    return None;
126                }
127            }
128        }
129    }
130
131    #[inline(always)]
132    fn iter<'a>(&'a self) -> impl Iterator<Item = (&'a TKey, &'a TValue)>
133    where
134        TKey: 'a,
135        TValue: 'a,
136        Self: 'a,
137    {
138        BytellImmutableIter::from_hash_table(self)
139    }
140}
osom_lib_hash_tables/bytell/hash_table/bytell_immutable.rs

osom_lib_hash_tables/bytell/hash_table/
bytell_immutable.rs
