const Metadata = packed structfingerprint: FingerPrint = freeused: u1 = 0pub fn isUsed(self: Metadata) boolpub fn isTombstone(self: Metadata) boolpub fn isFree(self: Metadata) boolpub fn takeFingerprint(hash: Hash) FingerPrintpub fn fill(self: *Metadata, fp: FingerPrint) voidpub fn remove(self: *Metadata) void587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626 const Metadata = packed struct {
const FingerPrint = u7;
const free: FingerPrint = 0;
const tombstone: FingerPrint = 1;
fingerprint: FingerPrint = free,
used: u1 = 0,
const slot_free: u8 = @bitCast(Metadata{ .fingerprint = free });
const slot_tombstone: u8 = @bitCast(Metadata{ .fingerprint = tombstone });
pub fn isUsed(self: Metadata) bool {
return self.used == 1;
}
pub fn isTombstone(self: Metadata) bool {
return @as(u8, @bitCast(self)) == slot_tombstone;
}
pub fn isFree(self: Metadata) bool {
return @as(u8, @bitCast(self)) == slot_free;
}
pub fn takeFingerprint(hash: Hash) FingerPrint {
const hash_bits = @typeInfo(Hash).int.bits;
const fp_bits = @typeInfo(FingerPrint).int.bits;
return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
}
pub fn fill(self: *Metadata, fp: FingerPrint) void {
self.used = 1;
self.fingerprint = fp;
}
pub fn remove(self: *Metadata) void {
self.used = 0;
self.fingerprint = tombstone;
}
}
Metadata for a slot. It can be in three states: empty, used or tombstone. Tombstones indicate that an entry was previously used, they are a simple way to handle removal. To this state, we add 7 bits from the slot's key hash. These are used as a fast way to disambiguate between entries without having to use the equality function. If two fingerprints are different, we know that we don't have to compare the keys at all. The 7 bits are the highest ones from a 64 bit hash. This way, not only we use the
log2(capacity)lowest bits from the hash to determine a slot index, but we use 7 more bits to quickly resolve collisions when multiple elements with different hashes end up wanting to be in the same slot. Not using the equality function means we don't have to read into the entries array, likely avoiding a cache miss and a potentially costly function call.