devela/data/key/static_map/define.rs
1// devela::data::key::static_map::define
2//
3//! Defines the [`define_static_map!`] macro.
4//
5// TOC
6// - define_static_map
7// - const arm
8// - non-const arm
9// - @shared arm
10//
11//
12// IMPROVE:
13// - Generalize further for non-numeric keys? (&str, [u8; N], etc.)
14// - maybe use a separate arm with a tombstone array, in a different arm…
15// think of macro arm prefix for:
16// - primitive keys: nothing(default), prim...
17// - non-primitive keys: (?)
18//
19// - insert automatically-generated benchmark results.
20// - now it uses criterion, but use my own solution.
21//
22// - use macro to avoid repeating inner bodies?
23//
24// - Optimize probing strategy?
25// - linear DONE
26// - quadratic
27// - robin hood
28//
29// TODO
30// - can you make a custom Debug impl so that the pretty print shows in the
31// header a summary with of our instrospection metrics?
32//
33// - FIX
34// - custom hasher on non-const definition FAILS, TODO:DEBUG
35
36#[cfg(doc)]
37define_static_map![ExampleStaticMapU16, KEY: u16];
38
39/// Build a custom static hashmap.
40///
41/// # Arguments
42/// - `$NAME`: the name of the new hashmap.
43/// - `$KEY`: the integer primitive type for the keys.
44///
45/// optional:
46/// - `$EMPTY`: the `$KEY` value for empty entries.
47/// - `$TOMB`: the `$KEY` value for deleted entries.
48/// - `$HASH_ARG`: the argument representing the byte slice.
49/// - `$HASH_EXPR`: the const hasher expression using `$HASH_ARG`.
50///
51// FIXME:
52/// # Notes
53/// - values `V` have to be `Copy` + `ConstDefault`.
54/// - keys `$KEY` can be any primitive integers, floats or `char`.
55/// - Two specific `$KEY` values are reserved to indicate empty deleted keys.
56/// They default to `MIN` and `MAX`, respectively, but can be customized.
57/// - The default hasher is [`HasherFx`][crate::HasherFx].
58///
59// IMPROVE:
60/// There are two variants, one prefixed with const that supports const methods,
61/// but the empty and tomb values have to be known at compile time.
62/// The other variant has not const methods,
63///
64/// # Examples
65/// See the example type: [`ExampleStaticMapU16`].
66///
67/// Basic usage
68/// ```
69/// # use devela::define_static_map;
70/// // Define a static hashmap with `u16` keys and default hasher
71/// define_static_map![const ExampleMap, KEY: u16];
72///
73/// let mut map = ExampleMap::<u16, u32, 8>::new();
74///
75/// // Insert key-value pairs
76/// map.insert(1, 100).unwrap();
77/// map.insert(2, 200).unwrap();
78///
79/// // Retrieve values
80/// assert_eq!(map.get(1), Some(100));
81/// assert_eq!(map.get(2), Some(200));
82/// assert_eq!(map.get(3), None); // Key not found
83///
84/// // Delete a key
85/// assert!(map.remove(1));
86/// assert_eq!(map.get(1), None);
87///
88/// // Check introspection methods
89/// assert_eq!(map.len(), 1);
90/// assert!(!map.is_empty());
91/// assert!(!map.is_full());
92///
93/// // Rebuild after deletions to optimize probing
94/// if map.should_rebuild() {
95/// map.rebuild();
96/// }
97/// ```
98///
99/// Custom hashers
100/// ```
101/// # use devela::{define_static_map, HasherFx};
102/// // Define a static hashmap using `HasherFx` with a custom seed
103/// define_static_map![const ExampleMapFxSeeded, KEY: u16,
104/// HASHER: |b| HasherFx::<usize>::hash_bytes_with_seed(123, b)
105/// ];
106/// let mut map = ExampleMapFxSeeded::<u16, u32, 8>::new();
107/// map.insert(1, 100).unwrap();
108/// assert_eq!(map.get(1), Some(100));
109///
110/// # #[cfg(feature = "hash")] {
111/// # use devela::HasherPengy;
112/// // Define a static hashmap using a stateful pengy hasher
113/// # #[cfg(feature = "hash")]
114/// define_static_map![const ExampleMapPengy, KEY: u16,
115/// HASHER: |b| {
116/// let mut p = HasherPengy::new();
117/// p.process(b);
118/// p.digest() as usize
119/// }
120/// ];
121/// let mut map = ExampleMapPengy::<u16, u32, 8>::new();
122/// map.insert(1, 100).unwrap();
123/// assert_eq!(map.get(1), Some(100));
124/// # }
125/// ```
126#[cfg_attr(cargo_primary_package, doc(hidden))]
127#[macro_export]
128macro_rules! define_static_map {
129 // --------------------------------------------------------------------------------------------
130 (const // Default constructor
131 $NAME:ident, KEY:$KEY:ty $(,)?
132 ) => {
133 $crate::define_static_map![const $NAME, KEY:$KEY,
134 EMPTY:<$KEY>::MIN, TOMB:<$KEY>::MAX,
135 HASHER:|bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
136 ];
137 };
138 (const // Custom Empty/Tomb, Default Hasher
139 $NAME:ident, KEY:$KEY:ty, EMPTY:$EMPTY:expr, TOMB:$TOMB:expr $(,)?
140 ) => {
141 $crate::define_static_map![const $NAME, KEY:$KEY,
142 EMPTY:$EMPTY, TOMB:$TOMB,
143 HASHER:|bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
144 ];
145 };
146 (const // Custom Hasher, Default Empty/Tomb
147 $NAME:ident, KEY:$KEY:ty, HASHER: | $HASH_ARG:ident | $HASH_EXPR:expr $(,)?
148 ) => {
149 $crate::define_static_map![const $NAME, KEY:$KEY, EMPTY:<$KEY>::MIN, TOMB:<$KEY>::MAX,
150 HASHER: | $HASH_ARG | $HASH_EXPR
151 ];
152 };
153 (const // Fully customizable
154 $NAME:ident, KEY:$KEY:ty, EMPTY:$EMPTY:expr, TOMB:$TOMB:expr,
155 HASHER: | $HASH_ARG:ident | $HASH_EXPR:expr $(,)?
156 ) => {
157 #[doc = concat!("A custom static hashmap with `", stringify!($KEY), "` keys.")]
158 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
159 pub struct $NAME<K: Copy, V, const N: usize> {
160 keys: [K; N],
161 values: [V; N],
162 }
163
164 $crate::define_static_map![@shared $NAME, KEY:$KEY,
165 HASHER:|bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
166 ];
167
168 #[allow(unused)]
169 impl<V, const N: usize> $NAME<$KEY, V, N> {
170 /// Compile-time key value used to mark empty slots.
171 pub const EMPTY: $KEY = $EMPTY as $KEY;
172 /// Compile-time key value used to mark deleted slots.
173 pub const TOMB: $KEY = $TOMB as $KEY;
174
175 /// Returns the key value used to mark empty slots.
176 pub const fn empty(&self) -> $KEY { $EMPTY }
177 /// Returns the key value used to mark deleted slots.
178 pub const fn tomb(&self) -> $KEY { $TOMB }
179 }
180
181 impl<V: Copy + $crate::ConstDefault, const N: usize>
182 $crate::ConstDefault for $NAME<$KEY, V, N> {
183 const DEFAULT: Self = Self::new();
184 }
185 impl<V: Default, const N: usize> Default for $NAME<$KEY, V, N> {
186 /// Creates an empty hashmap.
187 ///
188 /// # Panics
189 /// Panics in debug if `EMPTY` and `TOMB` are equal,
190 /// or if any of them are out of range for `$KEY`.
191 #[allow(unexpected_cfgs, reason = "array_init")]
192 fn default() -> Self {
193 Self:: debug_assert_invariants();
194 Self {
195 keys: [$EMPTY; N],
196 values: $crate::array_init![default [V; N], "safe_data", "unsafe_array"],
197 }
198 }
199 }
200
201 #[allow(unused)]
202 impl<V: Copy + $crate::ConstDefault, const N: usize> $NAME<$KEY, V, N> {
203 /// Creates an empty hashmap.
204 ///
205 /// # Panics
206 /// Panics in debug if `EMPTY` and `TOMB` are equal,
207 /// or if any of them are out of range for `$KEY`.
208 #[allow(clippy::float_cmp_const)]
209 pub const fn new() -> Self {
210 Self:: debug_assert_invariants();
211 Self {
212 keys: [$EMPTY; N],
213 values: [V::DEFAULT; N],
214 }
215 }
216 }
217
218 #[allow(unused)]
219 impl<V, const N: usize> $NAME<$KEY, V, N> {
220 /// Retrieves some shared reference to the value associated with the given key.
221 pub const fn get_ref(&self, key: $KEY) -> Option<&V> {
222 Self::debug_assert_valid_key(key);
223 let mut index = self.hash_index(key);
224 let mut i = 0;
225 while i < N {
226 if self.keys[index] == key { return Some(&self.values[index]); }
227 if self.keys[index] == self.empty() { return None; }
228 index = (index + 1) % N;
229 i += 1;
230 }
231 None
232 }
233
234 /// Retrieves some exclusive reference to the value associated with the given key.
235 pub const fn get_mut(&mut self, key: $KEY) -> Option<&mut V> {
236 Self::debug_assert_valid_key(key);
237 let mut index = self.hash_index(key);
238 let mut i = 0;
239 while i < N {
240 if self.keys[index] == key { return Some(&mut self.values[index]); }
241 if self.keys[index] == self.empty() { return None; }
242 index = (index + 1) % N;
243 i += 1;
244 }
245 None
246 }
247
248 /// Retrieves an entry for a given key.
249 pub const fn entry(&mut self, key: $KEY) -> $crate::StaticMapEntry<V> {
250 Self::debug_assert_valid_key(key);
251 let mut index = self.hash_index(key);
252 let mut i = 0;
253 let mut tombstone_index = None;
254 while i < N {
255 if self.keys[index] == self.empty() {
256 return $crate::StaticMapEntry::Vacant(index);
257 }
258 if self.keys[index] == key {
259 return $crate::StaticMapEntry::Occupied(&mut self.values[index]);
260 }
261 if self.keys[index] == self.tomb() && tombstone_index.is_none() {
262 tombstone_index = Some(index);
263 }
264 index = (index + 1) % N;
265 i += 1;
266 }
267 // If full, return N (invalid index)
268 $crate::StaticMapEntry::Vacant($crate::unwrap![some_or tombstone_index, N])
269 }
270
271 /* intropection */
272
273 /// Returns the number of occupied slots in the hashmap.
274 pub const fn len(&self) -> usize {
275 let mut count = 0;
276 let mut i = 0;
277 while i < N {
278 if self.keys[i] != self.empty() && self.keys[i] != self.tomb() { count += 1; }
279 i += 1;
280 }
281 count
282 }
283
284 /// Returns `true` if the hashmap contains no entries.
285 pub const fn is_empty(&self) -> bool {
286 self.len() == 0
287 }
288
289 /// Returns `true` if the hashmap is completely full.
290 pub const fn is_full(&self) -> bool {
291 self.len() == N
292 }
293
294 /// Determines if rebuilding the table would improve efficiency.
295 ///
296 /// # Heuristic:
297 /// - Rebuild if `TOMB` slots exceed `N / 2` (half the table size).
298 pub const fn should_rebuild(&self) -> bool {
299 self.deleted_count() >= N / 2
300 }
301
302 /// Returns the number of deleted (TOMB) slots.
303 pub const fn deleted_count(&self) -> usize {
304 let mut count = 0;
305 let mut i = 0;
306 while i < N {
307 if self.keys[i] == self.tomb() { count += 1; }
308 i += 1;
309 }
310 count
311 }
312
313 /// Returns the load factor as a fraction of total capacity.
314 pub const fn load_factor(&self) -> f32 {
315 self.len() as f32 / N as f32
316 }
317
318 /* utility */
319
320 /// Ensures the given key is not EMPTY or TOMB.
321 const fn debug_assert_valid_key(key: $KEY) {
322 debug_assert!(key != $EMPTY, "Key cannot be `EMPTY` marker");
323 debug_assert!(key != $TOMB, "Key cannot be `TOMB` marker");
324 }
325 /// Ensures the type invariants hold.
326 const fn debug_assert_invariants() {
327 debug_assert![$EMPTY != $TOMB, "`$EMPTY` and `$TOMB` must be distinct"];
328 debug_assert![($EMPTY as i128) >= (<$KEY>::MIN as i128)
329 && ($EMPTY as i128) <= (<$KEY>::MAX as i128),
330 "`$EMPTY` value is out of range for type `$KEY`"];
331 debug_assert![($TOMB as i128) >= (<$KEY>::MIN as i128)
332 && ($TOMB as i128) <= (<$KEY>::MAX as i128),
333 "`$TOMB` value is out of range for type `$KEY`"];
334 }
335 }
336
337 #[allow(unused)]
338 impl<V: Copy, const N: usize> $NAME<$KEY, V, N> {
339 /// Inserts a key-value pair.
340 ///
341 /// # Returns
342 /// - `Ok(())` if the insertion succeeds.
343 /// - `Err(`[`NotEnoughSpace`]`)` if no slots are available.
344 ///
345 /// # Behavior
346 /// - Computes the **hash index** of the key.
347 /// - If the slot is `EMPTY`, inserts immediately.
348 /// - If the slot contains `TOMB`, the first `TOMB` encountered is
349 /// **used if no empty slots exist earlier in probing**.
350 /// - If the slot contains another key, **probes forward** until an open slot is found.
351 /// - If no open slots exist, returns an error.
352 #[allow(clippy::float_cmp, clippy::float_cmp_const)]
353 pub const fn insert(&mut self, key: $KEY, value: V)
354 -> Result<(), $crate::NotEnoughSpace> {
355 Self::debug_assert_valid_key(key);
356 let mut index = self.hash_index(key);
357 let mut i = 0;
358 let mut tombstone_index = None;
359 while i < N {
360 if self.keys[index] == self.empty() || self.keys[index] == self.tomb() {
361 let slot = if let Some(tomb) = tombstone_index { tomb } else { index };
362 self.keys[slot] = key;
363 self.values[slot] = value;
364 return Ok(());
365 }
366 if self.keys[index] == key {
367 self.values[index] = value; // Overwrite existing value
368 return Ok(());
369 }
370 if self.keys[index] == self.tomb() && tombstone_index.is_none() {
371 tombstone_index = Some(index);
372 }
373 index = (index + 1) % N;
374 i += 1;
375 }
376 Err($crate::NotEnoughSpace(Some(1)))
377 }
378
379 /// Retrieves a value by key.
380 ///
381 /// # Returns
382 /// - `Some(value)` if the key exists.
383 /// - `None` if the key is missing.
384 ///
385 /// # Behavior
386 /// - Searches for the key using **linear probing**.
387 /// - If a `TOMB` (deleted slot) is encountered, it **continues probing**.
388 /// - If an `EMPTY` slot is reached, the key is **not in the table**.
389 #[allow(clippy::float_cmp, clippy::float_cmp_const)]
390 pub const fn get(&self, key: $KEY) -> Option<V> {
391 Self::debug_assert_valid_key(key);
392 let mut index = self.hash_index(key);
393 let mut i = 0;
394 while i < N {
395 if self.keys[index] == key { return Some(self.values[index]); }
396 if self.keys[index] == self.empty() { return None; } // end of probe chain
397 index = (index + 1) % N;
398 i += 1;
399 }
400 None
401 }
402 }
403
404 #[allow(unused)]
405 impl<V: Copy + $crate::ConstDefault, const N: usize> $NAME<$KEY, V, N> {
406 /// Removes a key-value pair.
407 ///
408 /// # Returns
409 /// - `true` if the key was found and removed.
410 /// - `false` if the key was not found in the map.
411 ///
412 /// # Behavior
413 /// - Marks the slot as deleted (`TOMB`).
414 /// - Future lookups will continue probing past deleted entries.
415 /// - **Does NOT free the slot for immediate reuse**.
416 /// - New insertions only reuse a `TOMB` slot if no earlier `EMPTY` slots exist.
417 #[allow(clippy::float_cmp, clippy::float_cmp_const)]
418 pub const fn remove(&mut self, key: $KEY) -> bool {
419 Self::debug_assert_valid_key(key);
420 let mut index = self.hash_index(key);
421 let mut i = 0;
422 while i < N {
423 if self.keys[index] == key { self.keys[index] = self.tomb(); return true; }
424 if self.keys[index] == self.empty() { return false; }
425 index = (index + 1) % N;
426 i += 1;
427 }
428 false
429 }
430
431 /// Removes a key-value pair and optionally rebuilds the table.
432 ///
433 /// # Behavior
434 /// - Calls `remove()`, returning `true` if the key was found.
435 /// - If `should_rebuild()` returns `true`, calls `rebuild()`.
436 pub const fn remove_rebuild(&mut self, key: $KEY) -> bool {
437 let removed = self.remove(key);
438 if removed && self.should_rebuild() { self.rebuild(); }
439 removed
440 }
441
442 /// Rebuilds the table by removing `TOMB` slots and optimizing key placement.
443 ///
444 /// Calls [`Self::rebuilt()`] and replaces `self` with the optimized table.
445 ///
446 /// # When to Call?
447 /// - When **many deletions have occurred**.
448 /// - If lookups start taking significantly longer.
449 pub const fn rebuild(&mut self) { *self = self.rebuilt(); }
450
451 /// Returns a rebuilt version of the table with `TOMB` slots removed.
452 ///
453 /// Creates a new table and reinserts all valid keys while preserving the probe order.
454 ///
455 /// # Complexity
456 /// - **O(N)** worst-case when all slots are occupied.
457 pub const fn rebuilt(&self) -> Self {
458 let mut new_table = Self::new();
459 let mut i = 0;
460 while i < N {
461 if self.keys[i] != self.empty() && self.keys[i] != self.tomb() {
462 let _ = new_table.insert(self.keys[i], self.values[i]);
463 }
464 i += 1;
465 }
466 new_table
467 }
468 }
469 };
470 // --------------------------------------------------------------------------------------------
471 ( // Default constructor
472 $NAME:ident, KEY:$KEY:ty $(,)?
473 ) => {
474 $crate::define_static_map![$NAME, KEY:$KEY,
475 EMPTY:<$KEY>::MIN, TOMB:<$KEY>::MAX,
476 HASHER:|bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
477 ];
478 };
479 ( // Custom Empty/Tomb, Default Hasher
480 $NAME:ident, KEY:$KEY:ty, EMPTY:$EMPTY:expr, TOMB:$TOMB:expr $(,)?
481 ) => {
482 $crate::define_static_map![ $NAME, KEY:$KEY,
483 EMPTY:$EMPTY, TOMB:$TOMB,
484 HASHER:|bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
485 ];
486 };
487 ( // Custom Hasher, Default Empty/Tomb
488 $NAME:ident, KEY:$KEY:ty, HASHER: | $HASH_ARG:ident | $HASH_EXPR:expr $(,)?
489 ) => {
490 $crate::define_static_map![NAME, KEY:$KEY, EMPTY:<$KEY>::MIN, TOMB:<$KEY>::MAX,
491 HASHER: | $HASH_ARG | $HASH_EXPR
492 ];
493 };
494 ( // Fully customizable
495 $NAME:ident, KEY:$KEY:ty, EMPTY:$EMPTY:expr, TOMB:$TOMB:expr,
496 HASHER: | $HASH_ARG:ident | $HASH_EXPR:expr $(,)?
497 ) => {
498 ///
499 #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
500 pub struct $NAME<K: Copy, V, const N: usize> {
501 keys: [K; N],
502 values: [V; N],
503 empty: K,
504 tomb: K,
505 }
506
507 // implement shared methods
508 $crate::define_static_map![@shared $NAME, KEY:$KEY,
509 HASHER:|bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
510 ];
511
512 #[allow(unused)]
513 impl<V, const N: usize> $NAME<$KEY, V, N> {
514 /// Returns the key value used to mark empty slots.
515 pub fn empty(&self) -> $KEY { self.empty }
516 /// Returns the key value used to mark deleted slots.
517 pub fn tomb(&self) -> $KEY { self.tomb }
518 }
519
520 impl<V: Default, const N: usize> Default for $NAME<$KEY, V, N> {
521 /// Creates an empty hashmap.
522 ///
523 /// # Panics
524 /// Panics in debug if `EMPTY` and `TOMB` are equal,
525 /// or if any of them are out of range for `$KEY`.
526 #[allow(unexpected_cfgs, reason = "array_init")]
527 fn default() -> Self {
528 Self:: debug_assert_invariants();
529 Self {
530 keys: [$EMPTY; N],
531 values: $crate::array_init![default [V; N], "safe_data", "unsafe_array"],
532 empty: $EMPTY,
533 tomb: $TOMB,
534 }
535 }
536 }
537
538 #[allow(unused)]
539 impl<V, const N: usize> $NAME<$KEY, V, N> {
540 /// Constructs a new static map with runtime EMPTY and TOMB values.
541 pub fn new() -> Self where V: Default {
542 Self::default()
543 }
544
545 /// Creates an empty hashmap, by cloning a `value`.
546 ///
547 /// # Panics
548 /// Panics in debug if `EMPTY` and `TOMB` are equal,
549 /// or if any of them are out of range for `$KEY`.
550 #[allow(unexpected_cfgs, reason = "array_init")]
551 fn new_cloned(value: V) -> Self where V: Clone {
552 Self:: debug_assert_invariants();
553 Self {
554 keys: [$EMPTY; N],
555 values: $crate::array_init![clone [V; N], "safe_data", "unsafe_array", value],
556 empty: $EMPTY,
557 tomb: $TOMB,
558 }
559 }
560
561 /// Retrieves some shared reference to the value associated with the given key.
562 pub fn get_ref(&self, key: $KEY) -> Option<&V> {
563 Self::debug_assert_valid_key(key);
564 let mut index = self.hash_index(key);
565 let mut i = 0;
566 while i < N {
567 if self.keys[index] == key { return Some(&self.values[index]); }
568 if self.keys[index] == self.empty() { return None; }
569 index = (index + 1) % N;
570 i += 1;
571 }
572 None
573 }
574
575 /// Retrieves some exclusive reference to the value associated with the given key.
576 pub fn get_mut(&mut self, key: $KEY) -> Option<&mut V> {
577 Self::debug_assert_valid_key(key);
578 let mut index = self.hash_index(key);
579 let mut i = 0;
580 while i < N {
581 if self.keys[index] == key { return Some(&mut self.values[index]); }
582 if self.keys[index] == self.empty() { return None; }
583 index = (index + 1) % N;
584 i += 1;
585 }
586 None
587 }
588
589 /// Retrieves an entry for a given key.
590 pub fn entry(&mut self, key: $KEY) -> $crate::StaticMapEntry<V> {
591 Self::debug_assert_valid_key(key);
592 let mut index = self.hash_index(key);
593 let mut i = 0;
594 let mut tombstone_index = None;
595 while i < N {
596 if self.keys[index] == self.empty() {
597 return $crate::StaticMapEntry::Vacant(index);
598 }
599 if self.keys[index] == key {
600 return $crate::StaticMapEntry::Occupied(&mut self.values[index]);
601 }
602 if self.keys[index] == self.tomb() && tombstone_index.is_none() {
603 tombstone_index = Some(index);
604 }
605 index = (index + 1) % N;
606 i += 1;
607 }
608 // If full, return N (invalid index)
609 $crate::StaticMapEntry::Vacant($crate::unwrap![some_or tombstone_index, N])
610 }
611
612 /* intropection */
613
614 /// Returns the number of occupied slots in the hashmap.
615 pub fn len(&self) -> usize {
616 let mut count = 0;
617 let mut i = 0;
618 while i < N {
619 if self.keys[i] != self.empty() && self.keys[i] != self.tomb() { count += 1; }
620 i += 1;
621 }
622 count
623 }
624
625 /// Returns `true` if the hashmap contains no entries.
626 pub fn is_empty(&self) -> bool {
627 self.len() == 0
628 }
629
630 /// Returns `true` if the hashmap is completely full.
631 pub fn is_full(&self) -> bool {
632 self.len() == N
633 }
634
635 /// Determines if rebuilding the table would improve efficiency.
636 ///
637 /// # Heuristic:
638 /// - Rebuild if `TOMB` slots exceed `N / 2` (half the table size).
639 pub fn should_rebuild(&self) -> bool {
640 self.deleted_count() >= N / 2
641 }
642
643 /// Returns the number of deleted (TOMB) slots.
644 pub fn deleted_count(&self) -> usize {
645 let mut count = 0;
646 let mut i = 0;
647 while i < N {
648 if self.keys[i] == self.tomb() { count += 1; }
649 i += 1;
650 }
651 count
652 }
653
654 /// Returns the load factor as a fraction of total capacity.
655 pub fn load_factor(&self) -> f32 {
656 self.len() as f32 / N as f32
657 }
658
659 /* utility */
660
661 /// Ensures the given key is not EMPTY or TOMB.
662 fn debug_assert_valid_key(key: $KEY) {
663 debug_assert!(key != $EMPTY, "Key cannot be `EMPTY` marker");
664 debug_assert!(key != $TOMB, "Key cannot be `TOMB` marker");
665 }
666 /// Ensures the type invariants hold.
667 fn debug_assert_invariants() {
668 debug_assert![$EMPTY != $TOMB, "`$EMPTY` and `$TOMB` must be distinct"];
669 debug_assert![($EMPTY as i128) >= (<$KEY>::MIN as i128)
670 && ($EMPTY as i128) <= (<$KEY>::MAX as i128),
671 "`$EMPTY` value is out of range for type `$KEY`"];
672 debug_assert![($TOMB as i128) >= (<$KEY>::MIN as i128)
673 && ($TOMB as i128) <= (<$KEY>::MAX as i128),
674 "`$TOMB` value is out of range for type `$KEY`"];
675 }
676
677 /// Inserts a key-value pair.
678 ///
679 /// # Returns
680 /// - `Ok(())` if the insertion succeeds.
681 /// - `Err(`[`NotEnoughSpace`]`)` if no slots are available.
682 ///
683 /// # Behavior
684 /// - Computes the **hash index** of the key.
685 /// - If the slot is `EMPTY`, inserts immediately.
686 /// - If the slot contains `TOMB`, the first `TOMB` encountered is
687 /// **used if no empty slots exist earlier in probing**.
688 /// - If the slot contains another key, **probes forward** until an open slot is found.
689 /// - If no open slots exist, returns an error.
690 #[allow(clippy::float_cmp, clippy::float_cmp_const)]
691 pub fn insert(&mut self, key: $KEY, value: V)
692 -> Result<(), $crate::NotEnoughSpace> {
693 Self::debug_assert_valid_key(key);
694 let mut index = self.hash_index(key);
695 let mut i = 0;
696 let mut tombstone_index = None;
697 while i < N {
698 if self.keys[index] == self.empty() || self.keys[index] == self.tomb() {
699 let slot = if let Some(tomb) = tombstone_index { tomb } else { index };
700 self.keys[slot] = key;
701 self.values[slot] = value;
702 return Ok(());
703 }
704 if self.keys[index] == key {
705 self.values[index] = value; // Overwrite existing value
706 return Ok(());
707 }
708 if self.keys[index] == self.tomb() && tombstone_index.is_none() {
709 tombstone_index = Some(index);
710 }
711 index = (index + 1) % N;
712 i += 1;
713 }
714 Err($crate::NotEnoughSpace(Some(1)))
715 }
716 }
717
718 #[allow(unused)]
719 impl<V: Copy, const N: usize> $NAME<$KEY, V, N> {
720 /// Retrieves a value by key.
721 ///
722 /// # Returns
723 /// - `Some(value)` if the key exists.
724 /// - `None` if the key is missing.
725 ///
726 /// # Behavior
727 /// - Searches for the key using **linear probing**.
728 /// - If a `TOMB` (deleted slot) is encountered, it **continues probing**.
729 /// - If an `EMPTY` slot is reached, the key is **not in the table**.
730 #[allow(clippy::float_cmp, clippy::float_cmp_const)]
731 pub fn get(&self, key: $KEY) -> Option<V> {
732 Self::debug_assert_valid_key(key);
733 let mut index = self.hash_index(key);
734 let mut i = 0;
735 while i < N {
736 if self.keys[index] == key { return Some(self.values[index]); }
737 if self.keys[index] == self.empty() { return None; } // end of probe chain
738 index = (index + 1) % N;
739 i += 1;
740 }
741 None
742 }
743
744 /// Removes a key-value pair.
745 ///
746 /// # Returns
747 /// - `true` if the key was found and removed.
748 /// - `false` if the key was not found in the map.
749 ///
750 /// # Behavior
751 /// - Marks the slot as deleted (`TOMB`).
752 /// - Future lookups will continue probing past deleted entries.
753 /// - **Does NOT free the slot for immediate reuse**.
754 /// - New insertions only reuse a `TOMB` slot if no earlier `EMPTY` slots exist.
755 #[allow(clippy::float_cmp, clippy::float_cmp_const)]
756 pub fn remove(&mut self, key: $KEY) -> bool {
757 Self::debug_assert_valid_key(key);
758 let mut index = self.hash_index(key);
759 let mut i = 0;
760 while i < N {
761 if self.keys[index] == key { self.keys[index] = self.tomb(); return true; }
762 if self.keys[index] == self.empty() { return false; }
763 index = (index + 1) % N;
764 i += 1;
765 }
766 false
767 }
768 }
769
770 #[allow(unused)]
771 impl<V: Copy + Default, const N: usize> $NAME<$KEY, V, N> {
772 /// Removes a key-value pair and optionally rebuilds the table.
773 ///
774 /// # Behavior
775 /// - Calls `remove()`, returning `true` if the key was found.
776 /// - If `should_rebuild()` returns `true`, calls `rebuild()`.
777 pub fn remove_rebuild(&mut self, key: $KEY) -> bool {
778 let removed = self.remove(key);
779 if removed && self.should_rebuild() { self.rebuild(); }
780 removed
781 }
782
783 /// Rebuilds the table by removing `TOMB` slots and optimizing key placement.
784 ///
785 /// Calls [`Self::rebuilt()`] and replaces `self` with the optimized table.
786 ///
787 /// # When to Call?
788 /// - When **many deletions have occurred**.
789 /// - If lookups start taking significantly longer.
790 pub fn rebuild(&mut self) { *self = self.rebuilt(); }
791
792 /// Returns a rebuilt version of the table with `TOMB` slots removed.
793 ///
794 /// Creates a new table and reinserts all valid keys while preserving the probe order.
795 ///
796 /// # Complexity
797 /// - **O(N)** worst-case when all slots are occupied.
798 pub fn rebuilt(&self) -> Self {
799 let mut new_table = Self::new();
800 let mut i = 0;
801 while i < N {
802 if self.keys[i] != self.empty() && self.keys[i] != self.tomb() {
803 let _ = new_table.insert(self.keys[i], self.values[i]);
804 }
805 i += 1;
806 }
807 new_table
808 }
809 }
810 };
811 // --------------------------------------------------------------------------------------------
812 // (typeid // uses 64-bit hashes of `TypeId`s for the keys
813 // $NAME:ident $(,)?) => {
814 // $crate::define_static_map![typeid NAME,
815 // HASHER: |bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
816 // ];
817 // };
818 // // IMPROVE: use custom hasher
819 // // THINK FIX: can't use bytes here. so maybe we have to pass both?
820 // (typeid // with custom Hasher
821 // $NAME:ident, HASHER: | $HASH_ARG:ident | $HASH_EXPR:expr $(,)?
822 // ) => {
823 (typeid // uses 64-bit hashes of `TypeId`s for the keys
824 $NAME:ident $(,)?) => {
825 $crate::define_static_map![$NAME, KEY: u64,
826 EMPTY: type_id_hash::<Empty>(), TOMB: type_id_hash::<Tomb>(),
827 HASHER: |bytes| $crate::HasherFx::<usize>::hash_bytes(bytes)
828 ];
829
830 struct Empty;
831 struct Tomb;
832 fn type_id_hash<T: 'static>() -> u64 {
833 let mut hasher = HasherFx::<u64>::new();
834 $crate::TypeId::of::<T>().hash(&mut hasher);
835 hasher.finish()
836 }
837
838 #[allow(unused)]
839 /// Convenience methods for when the keys are `TypeId`s.
840 impl<V, const N: usize> $NAME<u64, V, N> {
841 /// Returns the hash of `T`'s `TypeId`.
842 pub fn type_id_hash<T: 'static>() -> u64 { type_id_hash::<T>() }
843
844 /// Retrieves some exclusive reference to the value associated with the given type `T`.
845 ///
846 /// Calls [`get_ref`][Self::get_ref] with the hash of its type id.
847 pub fn get_ref_type<T: 'static>(&self) -> Option<&V> {
848 let key = Self::type_id_hash::<T>();
849 self.get_ref(key)
850 }
851 /// Retrieves some exclusive reference to the value associated with the given type `T`.
852 ///
853 /// Calls [`get_mut`][Self::get_mut] with the hash of its type id.
854 pub fn get_mut_type<T: 'static>(&mut self) -> Option<&mut V> {
855 let key = Self::type_id_hash::<T>();
856 self.get_mut(key)
857 }
858
859 /// Inserts a value paired with the given type `T`.
860 ///
861 /// Calls [`insert`][Self::insert] with the hash of its type id.
862 pub fn insert_type<T: 'static>(&mut self, value: V)
863 -> Result<(), $crate::NotEnoughSpace> {
864 let key = Self::type_id_hash::<T>();
865 self.insert(key, value)
866 }
867 }
868 #[allow(unused)]
869 impl<V: Copy, const N: usize> $NAME<u64, V, N> {
870 /// Retrieves some value associated with the given type `T`.
871 ///
872 /// Calls [`get`][Self::get] with the hash of its type id.
873 pub fn get_type<T: 'static>(&self) -> Option<V> {
874 let key = Self::type_id_hash::<T>();
875 self.get(key)
876 }
877 /// Removes the value paired with the given type `T`.
878 ///
879 /// Calls [`remove`][Self::remove] with the hash of its type id.
880 pub fn remove_type<T: 'static>(&mut self) -> bool {
881 let key = Self::type_id_hash::<T>();
882 self.remove(key)
883 }
884 }
885 };
886
887 // --------------------------------------------------------------------------------------------
888 (@shared $NAME:ident, KEY:$KEY:ty, HASHER: | $HASH_ARG:ident | $HASH_EXPR:expr $(,)?) => {
889 #[allow(unused)]
890 impl<V, const N: usize> $NAME<$KEY, V, N> {
891 /// Inserts a key-value pair, consuming the value.
892 pub fn insert_move(&mut self, key: $KEY, value: V)
893 -> Result<(), $crate::NotEnoughSpace> {
894 match self.entry(key) {
895 $crate::StaticMapEntry::Occupied(slot) => {
896 *slot = value; // Overwrite existing value
897 Ok(())
898 }
899 $crate::StaticMapEntry::Vacant(index) if index < N => {
900 self.keys[index] = key;
901 self.values[index] = value;
902 Ok(())
903 }
904 _ => Err($crate::NotEnoughSpace(Some(1))),
905 }
906 }
907
908 /// Removes and returns the value for a given key, replacing it with a provided value.
909 #[rustfmt::skip]
910 pub fn replace(&mut self, key: $KEY, replacement: V) -> Option<V> {
911 match self._replace_internal(key) {
912 Some(slot) => Some($crate::Mem::replace(slot, replacement)),
913 None => None,
914 }
915 }
916 /// Removes and returns the value for a given key, replacing it with `V::default()`.
917 #[rustfmt::skip]
918 pub fn replace_default(&mut self, key: $KEY) -> Option<V> where V: Default {
919 self._replace_internal(key).map(|v| $crate::Mem::replace(v, V::default()))
920 }
921 /// Removes and returns the value for a given key, replacing it with a custom value.
922 #[rustfmt::skip]
923 pub fn replace_with<F>(&mut self, key: $KEY, replacement: F) -> Option<V>
924 where F: FnOnce() -> V {
925 self._replace_internal(key).map(|v| $crate::Mem::replace(v, replacement()))
926 }
927 /// Internal function to locate and mark a key as removed.
928 ///
929 /// Returns a mutable reference to the value slot for replacement.
930 /* const */ fn _replace_internal(&mut self, key: $KEY) -> Option<&mut V> {
931 Self::debug_assert_valid_key(key);
932 let mut index = self.hash_index(key);
933 let mut i = 0;
934 while i < N {
935 if self.keys[index] == key {
936 self.keys[index] = self.tomb();
937 return Some(&mut self.values[index]);
938 }
939 if self.keys[index] == self.empty() { return None; }
940 index = (index + 1) % N;
941 i += 1;
942 }
943 None
944 }
945
946 /* introspection */
947
948 /// Returns the total capacity of the hashmap (fixed at `N`).
949 pub const fn capacity(&self) -> usize {
950 N
951 }
952
953 /* utility */
954
955 /// Computes a hash index.
956 #[$crate::compile(not(same($KEY, char)))] // for integers and floats
957 pub const fn hash_index(&self, key: $KEY) -> usize {
958 let $HASH_ARG = &key.to_le_bytes();
959 let expr = $HASH_EXPR;
960 expr % N
961 }
962 /// Computes a hash index.
963 #[$crate::compile(same($KEY, char))] // only for chars
964 pub const fn hash_index(&self, key: $KEY) -> usize {
965 let $HASH_ARG = &(key as u32).to_le_bytes();
966 let expr = $HASH_EXPR;
967 expr % N
968 }
969 }
970 };
971}
972#[doc(inline)]
973pub use define_static_map;
974
975// MAYBE
976// helper for common bodies
977// macro_rules! fn_body {
978// () => {
979// };
980// }
981// use fn_body;