1use crate::*;
2use core::borrow::Borrow;
3use core::fmt;
4use core::hash::{BuildHasher, Hash, Hasher};
5use std::collections::hash_map::{DefaultHasher, HashMap};
6
7#[derive(Clone, Copy)]
8pub struct DetState;
9
10impl BuildHasher for DetState {
11 type Hasher = DefaultHasher;
12
13 #[inline]
14 fn build_hasher(&self) -> DefaultHasher {
15 return DefaultHasher::new();
16 }
17}
18
19#[derive(Clone, Copy)]
20pub enum HashRefSlot<Key, Value>
21where
22 Key: Copy,
23 Value: Copy,
24{
25 Some(Key, Value),
26 None,
27}
28
29#[derive(Clone, Copy)]
30pub struct HashRef<'a, Key, Value, State = DetState>
31where
32 Key: Eq + Hash + Copy + 'a,
33 Value: Copy + 'a,
34 State: BuildHasher,
35{
36 pub slots: &'a [HashRefSlot<Key, Value>],
37 pub size: usize,
38 pub state: State,
39}
40
41impl<'a, K, V> HashRef<'a, K, V, DetState>
42where
43 K: Eq + Hash + Copy + 'a,
44 V: Copy + 'a,
45{
46 pub fn new(frame: impl Allocator, data: &HashMap<K, V>) -> Self {
47 return Self::with_state(frame, data, DetState);
48 }
49
50 pub fn new_iter<I>(frame: impl Allocator, capa: usize, data: I) -> Self
51 where
52 I: Iterator<Item = (K, V)>,
53 {
54 return Self::with_state_iter(frame, capa, data, DetState);
55 }
56
57 pub fn empty() -> Self {
58 Self {
59 slots: &mut [],
60 size: 0,
61 state: DetState,
62 }
63 }
64}
65
66impl<'a, K, V, State> HashRef<'a, K, V, State>
67where
68 K: Eq + Hash + Copy + 'a,
69 V: Copy + 'a,
70 State: BuildHasher,
71{
72 pub fn with_state(frame: impl Allocator, data: &HashMap<K, V>, state: State) -> Self {
73 let capa = data.len() * 3 / 2;
74 return Self::with_state_iter(frame, capa, data.iter().map(|(&k, &v)| (k, v)), state);
75 }
76
77 pub fn with_state_iter<I>(frame: impl Allocator, capa: usize, data: I, state: State) -> Self
78 where
79 I: Iterator<Item = (K, V)>,
80 {
81 let mut slots_array = pod![HashRefSlot::None; capa; &frame];
82 let slots = &mut *slots_array;
83 let mut size = 0;
84
85 for (key, value) in data {
86 if size == capa {
87 panic!(
88 "allocated too little capacity for size (size = capacity = {})",
89 size
90 );
91 }
92
93 let mut hasher = state.build_hasher();
94 key.hash(&mut hasher);
95 let mut slot_idx = hasher.finish() as usize % slots.len();
96
97 loop {
98 match &mut slots[slot_idx] {
99 HashRefSlot::Some(slot_key, slot_value) => {
100 if slot_key == &key {
101 *slot_key = key;
102 *slot_value = value;
103 break;
104 }
105 }
106 slot @ HashRefSlot::None => {
107 *slot = HashRefSlot::Some(key, value);
108 size += 1;
109 break;
110 }
111 }
112
113 slot_idx += 1;
114 slot_idx = slot_idx % slots.len();
115 }
116 }
117
118 let slots: &'a mut [_] = slots_array.leak();
119 Self { slots, size, state }
120 }
121
122 #[inline]
123 pub fn len(&self) -> usize {
124 return self.size;
125 }
126
127 #[inline]
128 pub fn capacity(&self) -> usize {
129 return self.slots.len();
130 }
131
132 fn get_index<Q: ?Sized>(&self, key: &Q) -> Option<usize>
133 where
134 K: Borrow<Q>,
135 Q: Hash + Eq,
136 {
137 let mut hasher = self.state.build_hasher();
138 key.hash(&mut hasher);
139
140 let mut slot_idx = hasher.finish() as usize % self.slots.len();
141 let original_slot_idx = slot_idx;
142 match &self.slots[slot_idx] {
143 HashRefSlot::None => return None,
144 HashRefSlot::Some(slot_key, slot_value) => {
145 if slot_key.borrow() == key {
146 return Some(slot_idx);
147 }
148 }
149 }
150
151 loop {
152 slot_idx += 1;
153 slot_idx = slot_idx % self.slots.len();
154
155 if slot_idx == original_slot_idx {
156 return None;
157 }
158
159 match &self.slots[slot_idx] {
160 HashRefSlot::None => return None,
161 HashRefSlot::Some(slot_key, slot_value) => {
162 if slot_key.borrow() == key {
163 return Some(slot_idx);
164 }
165 }
166 }
167 }
168 }
169
170 pub fn get<Q: ?Sized>(&self, key: &Q) -> Option<&V>
171 where
172 K: Borrow<Q>,
173 Q: Hash + Eq,
174 {
175 let idx = self.get_index(key)?;
176
177 match &self.slots[idx] {
178 HashRefSlot::None => return None,
179 HashRefSlot::Some(slot_key, slot_value) => {
180 if slot_key.borrow() == key {
181 return Some(slot_value);
182 }
183 }
184 };
185
186 return None;
187 }
188}
189
190pub struct HashRefIter<'a, Key, Value>
191where
192 Key: Copy,
193 Value: Copy,
194{
195 pub slots: &'a [HashRefSlot<Key, Value>],
196 pub slot_idx: usize,
197}
198
199impl<'a, Key, Value> Iterator for HashRefIter<'a, Key, Value>
200where
201 Key: Eq + Hash + Copy,
202 Value: Copy,
203{
204 type Item = (&'a Key, &'a Value);
205
206 fn next(&mut self) -> Option<Self::Item> {
207 loop {
208 if self.slot_idx == self.slots.len() {
209 return None;
210 } else if let HashRefSlot::Some(key, value) = &self.slots[self.slot_idx] {
211 self.slot_idx += 1;
212 return Some((key, value));
213 }
214
215 self.slot_idx += 1;
216 }
217 }
218}
219
220impl<'a, K, V, State> IntoIterator for &HashRef<'a, K, V, State>
221where
222 K: Eq + Hash + Copy,
223 V: Copy,
224 State: BuildHasher,
225{
226 type Item = (&'a K, &'a V);
227 type IntoIter = HashRefIter<'a, K, V>;
228
229 fn into_iter(self) -> Self::IntoIter {
230 HashRefIter {
231 slots: self.slots,
232 slot_idx: 0,
233 }
234 }
235}
236
237impl<'a, K, V, State> IntoIterator for HashRef<'a, K, V, State>
238where
239 K: Eq + Hash + Copy,
240 V: Copy,
241 State: BuildHasher,
242{
243 type Item = (&'a K, &'a V);
244 type IntoIter = HashRefIter<'a, K, V>;
245
246 fn into_iter(self) -> Self::IntoIter {
247 HashRefIter {
248 slots: self.slots,
249 slot_idx: 0,
250 }
251 }
252}
253
254impl<'a, Key, Value, State> fmt::Debug for HashRef<'a, Key, Value, State>
255where
256 Key: Eq + Hash + Copy + fmt::Debug,
257 Value: fmt::Debug + Copy,
258 State: BuildHasher,
259{
260 fn fmt(&self, fmt: &mut fmt::Formatter) -> Result<(), fmt::Error> {
261 fmt.debug_map().entries(self.into_iter()).finish()
262 }
263}