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    pub(crate) const fn full(hash: u64) -> Tag {
36        // Constant for function that grabs the top 7 bits of the hash.
37        const MIN_HASH_LEN: usize = if mem::size_of::<usize>() < mem::size_of::<u64>() {
38            mem::size_of::<usize>()
39        } else {
40            mem::size_of::<u64>()
41        };
42
43        // Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
44        // value, some hash functions (such as FxHash) produce a usize result
45        // instead, which means that the top 32 bits are 0 on 32-bit platforms.
46        // So we use MIN_HASH_LEN constant to handle this.
47        let top7 = hash >> (MIN_HASH_LEN * 8 - 7);
48        Tag((top7 & 0x7f) as u8) // truncation
49    }
50}
51impl fmt::Debug for Tag {
52    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
53        if self.is_special() {
54            if self.special_is_empty() {
55                f.pad("EMPTY")
56            } else {
57                f.pad("DELETED")
58            }
59        } else {
60            f.debug_tuple("full").field(&(self.0 & 0x7F)).finish()
61        }
62    }
63}
64
65/// Extension trait for slices of tags.
66pub(crate) trait TagSliceExt {
67    /// Fills the control with the given tag.
68    fn fill_tag(&mut self, tag: Tag);
69
70    /// Clears out the control.
71    #[inline]
72    fn fill_empty(&mut self) {
73        self.fill_tag(Tag::EMPTY);
74    }
75}
76impl TagSliceExt for [mem::MaybeUninit<Tag>] {
77    #[inline]
78    fn fill_tag(&mut self, tag: Tag) {
79        // SAFETY: We have access to the entire slice, so, we can write to the entire slice.
80        unsafe { self.as_mut_ptr().write_bytes(tag.0, self.len()) }
81    }
82}
hashbrown/control/tag.rs

hashbrown/control/
tag.rs
