hashbrown/control/
tag.rs

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("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(tag.0, self.len()) }
82    }
83}
hashbrown/control/tag.rs

hashbrown/control/
tag.rs
