1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
|
use super::u128::AtomicU128;
use std::borrow::Borrow;
use std::cell::UnsafeCell;
use std::hash::{BuildHasher, Hash, Hasher};
use std::mem::MaybeUninit;
use std::sync::atomic::{AtomicU64, Ordering};
use std::sync::{Arc, Mutex};
const TOMBSTONE_BIT: u64 = 1 << 63;
const ALLOCATED_BIT: u64 = 1 << 62;
const POINTER_MASK: u64 = 0x3FFFFFFFFFFFFFFF;
fn hash<S, K>(hasher: &S, key: &K) -> u64
where
S: BuildHasher,
K: Hash,
{
let mut hasher = hasher.build_hasher();
key.hash(&mut hasher);
hasher.finish()
}
struct Slot<K, V> {
data: AtomicU64,
pair: UnsafeCell<MaybeUninit<(K, V)>>,
}
pub struct Table<K, V, S> {
hash: Arc<S>,
slots: Box<[Slot<K, V>]>,
mask: usize,
}
impl<K, V, S> Table<K, V, S>
where
K: Eq + Hash,
S: BuildHasher,
{
pub fn new(hasher: Arc<S>, capacity: usize) -> Self {
debug_assert!(capacity.is_power_of_two());
let slots = (0..capacity)
.map(|_| Slot {
data: AtomicU64::new(0),
pair: UnsafeCell::new(MaybeUninit::uninit()),
})
.collect::<Vec<_>>();
Table {
hash: hasher,
slots: slots.into_boxed_slice(),
mask: capacity - 1,
}
}
pub fn get<Q>(&self, key: &Q) -> Option<*mut (K, V)>
where
K: Borrow<Q>,
Q: Eq + Hash,
{
let hash = hash(&*self.hash, key);
let mut idx = hash as usize & self.mask;
let mut i = 0;
loop {
let slot = &self.slots[idx];
let data = slot.data.load(Ordering::Relaxed);
let ptr = (data & POINTER_MASK) as *mut (K, V);
if !ptr.is_null() {
let stored = unsafe { (*ptr).0.borrow() };
if stored == key {
return Some(ptr);
}
} else if data & TOMBSTONE_BIT != TOMBSTONE_BIT || i > self.mask {
return None;
}
idx = (idx + 1) & self.mask;
i += 1;
}
}
}
|
