1 use core::{fmt, mem}; 2 3 /// Single tag in a control group. 4 #[derive(Copy, Clone, PartialEq, Eq)] 5 #[repr(transparent)] 6 pub(crate) struct Tag(pub(super) u8); 7 impl 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] is_full(self) -> bool16 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] is_special(self) -> bool22 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] special_is_empty(self) -> bool28 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)] full(hash: u64) -> Tag36 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 } 52 impl fmt::Debug for Tag { fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result53 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. 67 pub(crate) trait TagSliceExt { 68 /// Fills the control with the given tag. fill_tag(&mut self, tag: Tag)69 fn fill_tag(&mut self, tag: Tag); 70 71 /// Clears out the control. 72 #[inline] fill_empty(&mut self)73 fn fill_empty(&mut self) { 74 self.fill_tag(Tag::EMPTY) 75 } 76 } 77 impl TagSliceExt for [Tag] { 78 #[inline] fill_tag(&mut self, tag: Tag)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 } 84