small_map/raw/
mod.rs

1use core::{marker::PhantomData, mem, ptr::NonNull};
2
3use crate::raw::util::{unlikely, SizedTypeProperties};
4
5cfg_if! {
6    // Use the SSE2 implementation if possible: it allows us to scan 16 buckets
7    // at once instead of 8. We don't bother with AVX since it would require
8    // runtime dispatch and wouldn't gain us much anyways: the probability of
9    // finding a match drops off drastically after the first few buckets.
10    //
11    // I attempted an implementation on ARM using NEON instructions, but it
12    // turns out that most NEON instructions have multi-cycle latency, which in
13    // the end outweighs any gains over the generic implementation.
14    if #[cfg(all(
15        target_feature = "sse2",
16        any(target_arch = "x86", target_arch = "x86_64"),
17    ))] {
18        mod sse2;
19        use sse2 as imp;
20    } else if #[cfg(all(
21        target_arch = "aarch64",
22        target_feature = "neon",
23        // NEON intrinsics are currently broken on big-endian targets.
24        // See https://github.com/rust-lang/stdarch/issues/1484.
25        target_endian = "little",
26    ))] {
27        mod neon;
28        use neon as imp;
29    } else {
30        mod generic;
31        use generic as imp;
32    }
33}
34
35mod bitmask;
36pub mod iter;
37pub mod util;
38
39pub(crate) use imp::{BitMaskWord, Group};
40
41use self::{
42    bitmask::{BitMask, BitMaskIter},
43    util::Bucket,
44};
45
46// Constant for h2 function that grabing the top 7 bits of the hash.
47const MIN_HASH_LEN: usize = if mem::size_of::<usize>() < mem::size_of::<u64>() {
48    mem::size_of::<usize>()
49} else {
50    mem::size_of::<u64>()
51};
52
53/// Control byte value for an empty bucket.
54pub(crate) const EMPTY: u8 = 0b1111_1111;
55/// Control byte value for a deleted bucket.
56pub(crate) const DELETED: u8 = 0b1000_0000;
57
58/// Secondary hash function, saved in the low 7 bits of the control byte.
59#[inline]
60#[allow(clippy::cast_possible_truncation)]
61pub(crate) fn h2(hash: u64) -> u8 {
62    // Grab the top 7 bits of the hash. While the hash is normally a full 64-bit
63    // value, some hash functions (such as FxHash) produce a usize result
64    // instead, which means that the top 32 bits are 0 on 32-bit platforms.
65    // So we use MIN_HASH_LEN constant to handle this.
66    let top7 = hash >> (MIN_HASH_LEN * 8 - 7);
67    (top7 & 0x7f) as u8 // truncation
68}
69
70pub struct RawIterInner<T> {
71    len: usize,
72    current_group: BitMaskIter,
73    group_offset: usize,
74    _marker: PhantomData<T>,
75}
76
77unsafe impl<T> Send for RawIterInner<T> {}
78unsafe impl<T> Sync for RawIterInner<T> {}
79
80impl<T> RawIterInner<T> {
81    #[inline]
82    pub(crate) unsafe fn new(init_group: BitMask, len: usize) -> Self {
83        Self {
84            len,
85            current_group: init_group.into_iter(),
86            group_offset: 0,
87            _marker: PhantomData,
88        }
89    }
90
91    #[inline]
92    unsafe fn next_impl(&mut self, group_base: NonNull<u8>, base: Bucket<T>) -> Bucket<T> {
93        loop {
94            if let Some(index) = self.current_group.next() {
95                return base.next_n(index + self.group_offset);
96            }
97
98            self.group_offset += Group::WIDTH;
99            self.current_group = Group::load_aligned(group_base.as_ptr().add(self.group_offset))
100                .match_full()
101                .into_iter();
102        }
103    }
104
105    #[inline]
106    pub(crate) fn next(&mut self, group_base: NonNull<u8>, base: Bucket<T>) -> Option<Bucket<T>> {
107        if unlikely(self.len == 0) {
108            return None;
109        }
110        self.len -= 1;
111        Some(unsafe { self.next_impl(group_base, base) })
112    }
113
114    #[inline]
115    pub(crate) fn size_hint(&self) -> (usize, Option<usize>) {
116        (self.len, Some(self.len))
117    }
118
119    #[inline]
120    pub(crate) fn len(&self) -> usize {
121        self.len
122    }
123}
124
125impl<T> RawIterInner<T> {
126    pub(crate) unsafe fn drop_elements(&mut self, group_base: NonNull<u8>, base: Bucket<T>) {
127        if T::NEEDS_DROP && self.len != 0 {
128            while let Some(item) = self.next(group_base, base.clone()) {
129                item.drop();
130            }
131        }
132    }
133}
small_map/raw/mod.rs

small_map/raw/
mod.rs
