1use core::{fmt, mem};
2
3/// Single tag in a control group.
4#[derive(Copy, Clone, PartialEq, Eq)]
5#[repr(transparent)]
6pub(crate) struct Tag(pub(super) u8);
7impl Tag {
8 /// Control tag value for an empty bucket.
9 pub(crate) const EMPTY: Tag = Tag(0b1111_1111);
10
11 /// Control tag value for a deleted bucket.
12 pub(crate) const DELETED: Tag = Tag(0b1000_0000);
13
14 /// Checks whether a control tag represents a full bucket (top bit is clear).
15 #[inline]
16 pub(crate) const fn is_full(self) -> bool {
17 self.0 & 0x80 == 0
18 }
19
20 /// Checks whether a control tag represents a special value (top bit is set).
21 #[inline]
22 pub(crate) const fn is_special(self) -> bool {
23 self.0 & 0x80 != 0
24 }
25
26 /// Checks whether a special control value is EMPTY (just check 1 bit).
27 #[inline]
28 pub(crate) const fn special_is_empty(self) -> bool {
29 debug_assert!(self.is_special());
30 self.0 & 0x01 != 0
31 }
32
33 /// Creates a control tag representing a full bucket with the given hash.
34 #[inline]
35 #[allow(clippy::cast_possible_truncation)]
36 pub(crate) const fn full(hash: u64) -> Tag {
37 // Constant for function that grabs the top 7 bits of the hash.
38 const MIN_HASH_LEN: usize = if mem::size_of::<usize>() < mem::size_of::<u64>() {
39 mem::size_of::<usize>()
40 } else {
41 mem::size_of::<u64>()
42 };
43
44 // Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
45 // value, some hash functions (such as FxHash) produce a usize result
46 // instead, which means that the top 32 bits are 0 on 32-bit platforms.
47 // So we use MIN_HASH_LEN constant to handle this.
48 let top7 = hash >> (MIN_HASH_LEN * 8 - 7);
49 Tag((top7 & 0x7f) as u8) // truncation
50 }
51}
52impl fmt::Debug for Tag {
53 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
54 if self.is_special() {
55 if self.special_is_empty() {
56 f.pad("EMPTY")
57 } else {
58 f.pad("DELETED")
59 }
60 } else {
61 f.debug_tuple(name:"full").field(&(self.0 & 0x7F)).finish()
62 }
63 }
64}
65
66/// Extension trait for slices of tags.
67pub(crate) trait TagSliceExt {
68 /// Fills the control with the given tag.
69 fn fill_tag(&mut self, tag: Tag);
70
71 /// Clears out the control.
72 #[inline]
73 fn fill_empty(&mut self) {
74 self.fill_tag(Tag::EMPTY)
75 }
76}
77impl TagSliceExt for [Tag] {
78 #[inline]
79 fn fill_tag(&mut self, tag: Tag) {
80 // SAFETY: We have access to the entire slice, so, we can write to the entire slice.
81 unsafe { self.as_mut_ptr().write_bytes(val:tag.0, self.len()) }
82 }
83}
84