use core::fmt;
use core::iter::FusedIterator;
use crate::tags::TagSet;
const EMPTY_SLOT: u16 = u16::MAX;
fn hash(seed: u64, key: &[u8]) -> u64 {
key.iter().fold(0xcbf2_9ce4_8422_2325_u64 ^ seed, |h, &b| {
(h ^ u64::from(b)).wrapping_mul(0x0000_0100_0000_01b3)
})
}
fn slot(h: u64, shift: u32) -> usize {
let s = h
.wrapping_mul(0x9e37_79b9_7f4a_7c15)
.checked_shr(shift)
.unwrap_or(0);
usize::try_from(s).unwrap_or(0)
}
pub(crate) struct StrIndex {
seed: u64,
shift: u32,
max_probe: u32,
min_len: usize,
max_len: usize,
slots: &'static [u16],
}
impl StrIndex {
pub(crate) const fn new(
seed: u64,
shift: u32,
max_probe: u32,
(min_len, max_len): (usize, usize),
slots: &'static [u16],
) -> Self {
Self {
seed,
shift,
max_probe,
min_len,
max_len,
slots,
}
}
pub(crate) fn find(
&self,
key: &[u8],
key_at: impl Fn(usize) -> Option<&'static str>,
) -> Option<usize> {
if key.len() < self.min_len || key.len() > self.max_len {
return None;
}
let mask = self.slots.len().checked_sub(1)?;
let mut s = slot(hash(self.seed, key), self.shift) & mask;
for _ in 0..=self.max_probe {
let idx = *self.slots.get(s)?;
if idx == EMPTY_SLOT {
return None;
}
let idx = usize::from(idx);
if key_at(idx)?.as_bytes() == key {
return Some(idx);
}
s = (s + 1) & mask;
}
None
}
}
pub struct TagTable {
entries: &'static [(&'static str, TagSet)],
index: StrIndex,
}
impl TagTable {
pub(crate) const fn new(entries: &'static [(&'static str, TagSet)], index: StrIndex) -> Self {
Self { entries, index }
}
#[must_use]
pub fn get(&self, key: &str) -> Option<TagSet> {
self.get_bytes(key.as_bytes())
}
#[must_use]
pub fn get_bytes(&self, key: &[u8]) -> Option<TagSet> {
let i = self
.index
.find(key, |i| self.entries.get(i).map(|(k, _)| *k))?;
self.entries.get(i).map(|(_, tags)| *tags)
}
#[must_use]
pub fn contains_key(&self, key: &str) -> bool {
self.get(key).is_some()
}
#[must_use]
pub const fn len(&self) -> usize {
self.entries.len()
}
#[must_use]
pub const fn is_empty(&self) -> bool {
self.entries.is_empty()
}
#[must_use]
pub const fn entries(&self) -> &'static [(&'static str, TagSet)] {
self.entries
}
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub fn iter(
&self,
) -> impl DoubleEndedIterator<Item = (&'static str, TagSet)> + ExactSizeIterator + FusedIterator
{
self.entries.iter().copied()
}
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub fn keys(
&self,
) -> impl DoubleEndedIterator<Item = &'static str> + ExactSizeIterator + FusedIterator {
self.entries.iter().map(|(k, _)| *k)
}
#[must_use = "iterators are lazy and do nothing unless consumed"]
pub fn values(
&self,
) -> impl DoubleEndedIterator<Item = TagSet> + ExactSizeIterator + FusedIterator {
self.entries.iter().map(|(_, v)| *v)
}
}
impl fmt::Debug for TagTable {
fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
f.debug_map().entries(self.iter()).finish()
}
}
impl<'a> IntoIterator for &'a TagTable {
type Item = &'a (&'static str, TagSet);
type IntoIter = core::slice::Iter<'a, (&'static str, TagSet)>;
fn into_iter(self) -> Self::IntoIter {
self.entries.iter()
}
}
#[cfg(test)]
mod tests {
use crate::extensions::{EXTENSIONS, EXTENSIONS_NEED_BINARY_CHECK, NAMES};
use crate::interpreters::INTERPRETERS;
#[test]
fn every_key_is_found_through_the_index() {
for table in [
&EXTENSIONS,
&EXTENSIONS_NEED_BINARY_CHECK,
&NAMES,
&INTERPRETERS,
] {
assert!(
table.keys().zip(table.keys().skip(1)).all(|(a, b)| a < b),
"sorted"
);
for (key, tags) in table.iter() {
assert_eq!(table.get(key), Some(tags), "{key}");
}
}
}
#[test]
fn misses() {
for key in [
"",
"PY",
"py ",
"xx",
"a-very-long-key-that-is-not-there",
"\u{fffd}",
] {
assert_eq!(EXTENSIONS.get(key), None, "{key}");
}
assert_eq!(NAMES.get_bytes(b"\xff\xfe"), None);
assert!(!INTERPRETERS.is_empty());
assert!(format!("{INTERPRETERS:?}").contains("\"python3\""));
assert_eq!((&NAMES).into_iter().count(), NAMES.len());
}
}