1use core::fmt;
11use core::iter::FusedIterator;
12
13use crate::tags::TagSet;
14
15const EMPTY_SLOT: u16 = u16::MAX;
16
17fn hash(seed: u64, key: &[u8]) -> u64 {
19 key.iter().fold(0xcbf2_9ce4_8422_2325_u64 ^ seed, |h, &b| {
20 (h ^ u64::from(b)).wrapping_mul(0x0000_0100_0000_01b3)
21 })
22}
23
24fn slot(h: u64, shift: u32) -> usize {
26 let s = h
27 .wrapping_mul(0x9e37_79b9_7f4a_7c15)
28 .checked_shr(shift)
29 .unwrap_or(0);
30 usize::try_from(s).unwrap_or(0)
31}
32
33pub(crate) struct StrIndex {
36 seed: u64,
37 shift: u32,
38 max_probe: u32,
39 min_len: usize,
41 max_len: usize,
42 slots: &'static [u16],
43}
44
45impl StrIndex {
46 pub(crate) const fn new(
47 seed: u64,
48 shift: u32,
49 max_probe: u32,
50 (min_len, max_len): (usize, usize),
51 slots: &'static [u16],
52 ) -> Self {
53 Self {
54 seed,
55 shift,
56 max_probe,
57 min_len,
58 max_len,
59 slots,
60 }
61 }
62
63 pub(crate) fn find(
65 &self,
66 key: &[u8],
67 key_at: impl Fn(usize) -> Option<&'static str>,
68 ) -> Option<usize> {
69 if key.len() < self.min_len || key.len() > self.max_len {
70 return None;
71 }
72 let mask = self.slots.len().checked_sub(1)?;
73 let mut s = slot(hash(self.seed, key), self.shift) & mask;
74 for _ in 0..=self.max_probe {
75 let idx = *self.slots.get(s)?;
76 if idx == EMPTY_SLOT {
77 return None;
78 }
79 let idx = usize::from(idx);
80 if key_at(idx)?.as_bytes() == key {
81 return Some(idx);
82 }
83 s = (s + 1) & mask;
84 }
85 None
86 }
87}
88
89pub struct TagTable {
96 entries: &'static [(&'static str, TagSet)],
97 index: StrIndex,
98}
99
100impl TagTable {
101 pub(crate) const fn new(entries: &'static [(&'static str, TagSet)], index: StrIndex) -> Self {
102 Self { entries, index }
103 }
104
105 #[must_use]
107 pub fn get(&self, key: &str) -> Option<TagSet> {
108 self.get_bytes(key.as_bytes())
109 }
110
111 #[must_use]
114 pub fn get_bytes(&self, key: &[u8]) -> Option<TagSet> {
115 let i = self
116 .index
117 .find(key, |i| self.entries.get(i).map(|(k, _)| *k))?;
118 self.entries.get(i).map(|(_, tags)| *tags)
119 }
120
121 #[must_use]
123 pub fn contains_key(&self, key: &str) -> bool {
124 self.get(key).is_some()
125 }
126
127 #[must_use]
129 pub const fn len(&self) -> usize {
130 self.entries.len()
131 }
132
133 #[must_use]
135 pub const fn is_empty(&self) -> bool {
136 self.entries.is_empty()
137 }
138
139 #[must_use]
141 pub const fn entries(&self) -> &'static [(&'static str, TagSet)] {
142 self.entries
143 }
144
145 #[must_use = "iterators are lazy and do nothing unless consumed"]
147 pub fn iter(
148 &self,
149 ) -> impl DoubleEndedIterator<Item = (&'static str, TagSet)> + ExactSizeIterator + FusedIterator
150 {
151 self.entries.iter().copied()
152 }
153
154 #[must_use = "iterators are lazy and do nothing unless consumed"]
156 pub fn keys(
157 &self,
158 ) -> impl DoubleEndedIterator<Item = &'static str> + ExactSizeIterator + FusedIterator {
159 self.entries.iter().map(|(k, _)| *k)
160 }
161
162 #[must_use = "iterators are lazy and do nothing unless consumed"]
164 pub fn values(
165 &self,
166 ) -> impl DoubleEndedIterator<Item = TagSet> + ExactSizeIterator + FusedIterator {
167 self.entries.iter().map(|(_, v)| *v)
168 }
169}
170
171impl fmt::Debug for TagTable {
172 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
173 f.debug_map().entries(self.iter()).finish()
174 }
175}
176
177impl<'a> IntoIterator for &'a TagTable {
178 type Item = &'a (&'static str, TagSet);
179 type IntoIter = core::slice::Iter<'a, (&'static str, TagSet)>;
180
181 fn into_iter(self) -> Self::IntoIter {
182 self.entries.iter()
183 }
184}
185
186#[cfg(test)]
187mod tests {
188 use crate::extensions::{EXTENSIONS, EXTENSIONS_NEED_BINARY_CHECK, NAMES};
189 use crate::interpreters::INTERPRETERS;
190
191 #[test]
192 fn every_key_is_found_through_the_index() {
193 for table in [
194 &EXTENSIONS,
195 &EXTENSIONS_NEED_BINARY_CHECK,
196 &NAMES,
197 &INTERPRETERS,
198 ] {
199 assert!(
200 table.keys().zip(table.keys().skip(1)).all(|(a, b)| a < b),
201 "sorted"
202 );
203 for (key, tags) in table.iter() {
204 assert_eq!(table.get(key), Some(tags), "{key}");
205 }
206 }
207 }
208
209 #[test]
210 fn misses() {
211 for key in [
212 "",
213 "PY",
214 "py ",
215 "xx",
216 "a-very-long-key-that-is-not-there",
217 "\u{fffd}",
218 ] {
219 assert_eq!(EXTENSIONS.get(key), None, "{key}");
220 }
221 assert_eq!(NAMES.get_bytes(b"\xff\xfe"), None);
222 assert!(!INTERPRETERS.is_empty());
223 assert!(format!("{INTERPRETERS:?}").contains("\"python3\""));
224 assert_eq!((&NAMES).into_iter().count(), NAMES.len());
225 }
226}