1#![allow(clippy::inline_always)]
5
6use std::fmt::{Debug, Formatter};
7use std::hash::{BuildHasher, BuildHasherDefault, Hash, Hasher};
8use std::ops::{Index, IndexMut};
9
10const SEED: u64 = 0xa076_1d64_78bd_642f;
12const MUL: u64 = 0xe703_7ed1_a0b4_28db;
14
15#[derive(Clone, Debug)]
56pub struct FastHasher {
57 state: u64,
58 pending: u64,
59 bits: u32,
60}
61
62impl Default for FastHasher {
63 #[inline(always)]
64 fn default() -> Self {
65 FastHasher {
66 state: SEED,
67 pending: 0,
68 bits: 0,
69 }
70 }
71}
72
73impl FastHasher {
74 #[inline]
75 fn fold(state: u64, value: u64) -> u64 {
76 let (lo, hi) = (state ^ value).carrying_mul(MUL, 0);
77 lo ^ hi
78 }
79
80 #[inline(always)]
81 fn write_bits(&mut self, value: u64, bits: u32) {
82 if self.bits + bits > 64 {
83 self.state = Self::fold(self.state, self.pending);
84 self.pending = 0;
85 self.bits = 0;
86 }
87
88 self.pending = (self.pending << bits) | value;
89 self.bits += bits;
90 }
91}
92
93impl Hasher for FastHasher {
94 #[inline(always)]
95 fn finish(&self) -> u64 {
96 if self.bits > 0 {
97 Self::fold(self.state, self.pending ^ (u64::from(self.bits & 63) << 56))
99 } else {
100 self.state
101 }
102 }
103
104 #[inline]
105 fn write(&mut self, mut bytes: &[u8]) {
106 while let Some((chunk, rest)) = bytes.split_first_chunk() {
107 self.write_u64(u64::from_ne_bytes(*chunk));
108 bytes = rest;
109 }
110
111 if let Some((chunk, rest)) = bytes.split_first_chunk() {
112 self.write_u32(u32::from_ne_bytes(*chunk));
113 bytes = rest;
114 }
115
116 if let Some((chunk, rest)) = bytes.split_first_chunk() {
117 self.write_u16(u16::from_ne_bytes(*chunk));
118 bytes = rest;
119 }
120
121 if let Some(&byte) = bytes.first() {
122 self.write_u8(byte);
123 }
124 }
125
126 #[inline(always)]
127 fn write_u8(&mut self, n: u8) {
128 self.write_bits(u64::from(n), 8);
129 }
130
131 #[inline(always)]
132 fn write_u16(&mut self, n: u16) {
133 self.write_bits(u64::from(n), 16);
134 }
135
136 #[inline(always)]
137 fn write_u32(&mut self, n: u32) {
138 self.write_bits(u64::from(n), 32);
139 }
140
141 #[inline(always)]
142 fn write_u64(&mut self, n: u64) {
143 self.state = Self::fold(self.state, n);
144 }
145
146 #[inline(always)]
147 #[expect(clippy::cast_possible_truncation)]
148 fn write_u128(&mut self, n: u128) {
149 self.write_u64(n as u64);
150 self.write_u64((n >> 64) as u64);
151 }
152
153 #[inline(always)]
154 #[cfg(target_pointer_width = "16")]
155 #[expect(clippy::cast_possible_truncation)]
156 fn write_usize(&mut self, n: usize) {
157 self.write_u16(n as u16);
158 }
159
160 #[inline(always)]
161 #[cfg(target_pointer_width = "32")]
162 #[expect(clippy::cast_possible_truncation)]
163 fn write_usize(&mut self, n: usize) {
164 self.write_u32(n as u32);
165 }
166
167 #[inline(always)]
168 #[cfg(target_pointer_width = "64")]
169 fn write_usize(&mut self, n: usize) {
170 self.write_u64(n as u64);
171 }
172}
173
174pub type BuildFastHasher = BuildHasherDefault<FastHasher>;
176#[expect(clippy::disallowed_types)]
178pub type FastMap<K, V> = std::collections::HashMap<K, V, BuildFastHasher>;
179#[expect(clippy::disallowed_types)]
181pub type FastSet<T> = std::collections::HashSet<T, BuildFastHasher>;
182
183pub trait FastCollectionBuilder {
185 fn new() -> Self;
187
188 fn with_capacity(capacity: usize) -> Self;
190}
191
192#[expect(clippy::implicit_hasher)]
193impl<K, V> FastCollectionBuilder for FastMap<K, V> {
194 #[inline]
195 fn new() -> Self {
196 Self::with_hasher(BuildFastHasher::default())
197 }
198
199 #[inline]
200 fn with_capacity(capacity: usize) -> Self {
201 Self::with_capacity_and_hasher(capacity, BuildFastHasher::default())
202 }
203}
204
205#[expect(clippy::implicit_hasher)]
206impl<T> FastCollectionBuilder for FastSet<T> {
207 #[inline]
208 fn new() -> Self {
209 Self::with_hasher(BuildFastHasher::default())
210 }
211
212 #[inline]
213 fn with_capacity(capacity: usize) -> Self {
214 Self::with_capacity_and_hasher(capacity, BuildFastHasher::default())
215 }
216}
217
218#[derive(Clone)]
238pub struct IndexedMap<K, V> {
239 entries: Vec<(K, V)>,
240 table: Vec<u32>,
241}
242
243pub type IndexedSet<K> = IndexedMap<K, ()>;
259
260const EMPTY: u32 = u32::MAX;
261
262impl<K: Hash + Eq, V> IndexedMap<K, V> {
263 #[inline]
265 #[must_use]
266 pub fn new() -> Self {
267 Self::with_capacity(0)
268 }
269
270 #[inline]
272 #[must_use]
273 pub fn with_capacity(capacity: usize) -> Self {
274 Self {
275 entries: Vec::with_capacity(capacity),
276 table: vec![EMPTY; (capacity * 4).next_power_of_two().max(64)],
277 }
278 }
279
280 #[inline(always)]
284 #[expect(clippy::cast_possible_truncation)]
285 pub fn try_insert_with(&mut self, key: K, f: impl FnOnce() -> V) -> Result<usize, usize> {
286 if (self.entries.len() + 1) * 4 > self.table.len() {
287 self.grow();
288 }
289 match self.find(&key) {
290 Ok(index) => Err(index),
291 Err(slot) => {
292 let index = self.entries.len();
293 self.table[slot] = index as u32;
294 self.entries.push((key, f()));
295 Ok(index)
296 }
297 }
298 }
299
300 #[inline(always)]
304 pub fn try_insert(&mut self, key: K) -> Result<usize, usize>
305 where
306 V: Default,
307 {
308 self.try_insert_with(key, V::default)
309 }
310
311 #[inline]
313 pub fn insert(&mut self, key: K) -> bool
314 where
315 V: Default,
316 {
317 self.try_insert(key).is_ok()
318 }
319
320 #[inline]
322 pub fn intern(&mut self, key: K) -> usize
323 where
324 V: Default,
325 {
326 let (Ok(index) | Err(index)) = self.try_insert(key);
327 index
328 }
329
330 #[inline]
332 pub fn index_of(&self, key: &K) -> Option<usize> {
333 self.find(key).ok()
334 }
335
336 #[inline]
338 pub fn into_values(self) -> impl Iterator<Item = V> {
339 self.entries.into_iter().map(|(_, v)| v)
340 }
341
342 #[inline]
344 #[must_use]
345 pub fn len(&self) -> usize {
346 self.entries.len()
347 }
348
349 #[inline]
351 #[must_use]
352 pub fn is_empty(&self) -> bool {
353 self.entries.is_empty()
354 }
355
356 #[inline]
358 pub fn clear(&mut self) {
359 if !self.entries.is_empty() {
360 self.entries.clear();
361 self.table.fill(EMPTY);
362 }
363 }
364
365 #[inline]
366 #[expect(clippy::cast_possible_truncation)]
367 fn find(&self, key: &K) -> Result<usize, usize> {
368 let mask = self.table.len() - 1;
369 let mut slot = BuildFastHasher::default().hash_one(key) as usize & mask;
370 loop {
371 match self.table[slot] {
372 EMPTY => return Err(slot),
373 index if self.entries[index as usize].0 == *key => return Ok(index as usize),
374 _ => slot = (slot + 1) & mask,
375 }
376 }
377 }
378
379 #[cold]
380 #[inline(never)]
381 #[expect(clippy::cast_possible_truncation)]
382 fn grow(&mut self) {
383 let len = self.table.len() * 2;
384 assert!(len / 4 < EMPTY as usize, "too many keys");
385 self.table = vec![EMPTY; len];
386 for (index, (key, _)) in self.entries.iter().enumerate() {
387 let mut slot = BuildFastHasher::default().hash_one(key) as usize & (len - 1);
388 while self.table[slot] != EMPTY {
389 slot = (slot + 1) & (len - 1);
390 }
391 self.table[slot] = index as u32;
392 }
393 }
394}
395
396impl<K: Hash + Eq, V> Default for IndexedMap<K, V> {
397 #[inline]
398 fn default() -> Self {
399 Self::new()
400 }
401}
402
403impl<K, V> Index<usize> for IndexedMap<K, V> {
404 type Output = V;
405
406 #[inline]
407 fn index(&self, index: usize) -> &V {
408 &self.entries[index].1
409 }
410}
411
412impl<K, V> IndexMut<usize> for IndexedMap<K, V> {
413 #[inline]
414 fn index_mut(&mut self, index: usize) -> &mut V {
415 &mut self.entries[index].1
416 }
417}
418
419impl<K: Debug, V: Debug> Debug for IndexedMap<K, V> {
420 fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
421 f.debug_map()
422 .entries(self.entries.iter().map(|(k, v)| (k, v)))
423 .finish()
424 }
425}
426
427#[cfg(test)]
428mod tests {
429 use super::*;
430
431 fn hash_of(f: impl FnOnce(&mut FastHasher)) -> u64 {
432 let mut hasher = FastHasher::default();
433 f(&mut hasher);
434 hasher.finish()
435 }
436
437 #[test]
438 fn packs_small_writes() {
439 let a = hash_of(|h| {
440 h.write_u16(0x1234);
441 h.write_u16(0x5678);
442 h.write_u32(0x9abc_def0);
443 });
444 let b = hash_of(|h| h.write_u64(0x1234_5678_9abc_def0));
445 assert_eq!(a, b);
446 }
447
448 #[test]
449 fn packs_partial_writes_with_length() {
450 let a = hash_of(|h| {
451 h.write_u16(0x1234);
452 h.write_u16(0x5678);
453 h.write_u8(0x9a);
454 });
455 let b = hash_of(|h| h.write_u64(0x2800_0012_3456_789a));
456 assert_eq!(a, b);
457 }
458
459 #[test]
460 fn field_order_matters() {
461 let a = hash_of(|h| {
462 h.write_u32(1);
463 h.write_u32(2);
464 });
465 let packed_a = hash_of(|h| h.write_u64(0x0000_0001_0000_0002));
466 assert_eq!(a, packed_a);
467
468 let b = hash_of(|h| {
469 h.write_u32(2);
470 h.write_u32(1);
471 });
472 let packed_b = hash_of(|h| h.write_u64(0x0000_0002_0000_0001));
473 assert_eq!(b, packed_b);
474
475 assert_ne!(a, b);
476 }
477
478 #[test]
479 fn packs_full_word_then_tags_tail() {
480 let a = hash_of(|h| {
481 h.write_u32(1);
482 h.write_u32(2);
483 h.write_u32(3);
484 });
485 let b = hash_of(|h| {
486 h.write_u64(0x0000_0001_0000_0002);
487 h.write_u64(0x2000_0000_0000_0003);
488 });
489 assert_eq!(a, b);
490 }
491
492 #[test]
493 fn u64_write_order_matters() {
494 let a = hash_of(|h| {
495 h.write_u64(1);
496 h.write_u64(2);
497 h.write_u64(3);
498 });
499 let b = hash_of(|h| {
500 h.write_u64(3);
501 h.write_u64(2);
502 h.write_u64(1);
503 });
504 assert_ne!(a, b);
505 }
506
507 #[test]
508 fn zero_bytes_are_significant() {
509 let inputs: &[&[u8]] = &[
510 b"a",
511 b"ab",
512 b"ab\0",
513 b"a\0\0\0",
514 b"\0a",
515 b"\0a\0",
516 b"\0\0\0a",
517 b"\0\0\0\0\0\0\0\0a",
518 b"a\0\0\0\0\0\0\0\0",
519 b"\0",
520 b"\0\0",
521 b"\0\0\0",
522 b"\0\0\0\0",
523 b"\0\0\0\0\0\0\0\0",
524 b"\0\0\0\0\0\0\0\0\0",
525 b"\0\0\0\0\0\0\0\0\0\0",
526 ];
527 for (i, a) in inputs.iter().enumerate() {
528 for b in &inputs[i + 1..] {
529 assert_ne!(
530 hash_of(|h| h.write(a)),
531 hash_of(|h| h.write(b)),
532 "{a:?} and {b:?} hashed the same",
533 );
534 }
535 }
536 }
537
538 #[test]
539 fn indexed_map_resizes() {
540 let mut map = IndexedMap::new();
541 for i in 0..1000u32 {
542 assert_eq!(map.try_insert_with(i * 3, || i * 5), Ok(i as usize));
543 }
544 assert_eq!(map.len(), 1000);
545 for i in 0..1000u32 {
546 let index = map.index_of(&(i * 3)).unwrap();
547 assert_eq!((index, map[index]), (i as usize, i * 5));
548 }
549
550 map.clear();
551 assert!(map.is_empty());
552 assert_eq!(map.index_of(&3), None);
553 assert_eq!(map.try_insert(6), Ok(0));
554 }
555}