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
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
//! This module provides reference functionalty for referencing elements in a [`LeapMap`]
//! is a thread-safe manner.
use crate::{
leapmap::{AtomicCell, LeapMap},
Value,
};
use core::{
hash::{BuildHasher, Hash},
sync::atomic::Ordering,
};
#[cfg(feature = "stable_alloc")]
use allocator_api2::alloc::Allocator;
#[cfg(not(feature = "stable_alloc"))]
use core::alloc::Allocator;
/// A reference to an atomic cell in a [LeapMap], which cannot mutate
/// the referenced cell value.
pub struct Ref<'a, K, V, H, A: Allocator> {
/// The atomic value which is being referenced.
cell: &'a AtomicCell<K, V>,
/// Reference to the map in which the cell belongs.
map: &'a LeapMap<K, V, H, A>,
/// The hash for the cell at the point when the cell was found
pub(crate) hash: u64,
}
impl<'a, K, V, H, A> Ref<'a, K, V, H, A>
where
A: Allocator,
V: Value,
{
/// Creates a new ref type referencing the specified `cell` and `map`.
pub fn new(
map: &'a LeapMap<K, V, H, A>,
cell: &'a AtomicCell<K, V>,
hash: u64,
) -> Ref<'a, K, V, H, A> {
Ref { map, cell, hash }
}
/// Loads the key for the referenced cell.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the returned value is always the
/// most up to date value.
///
/// It is also possible that the cell has been deleted, in which case the
/// returned value will be `None`
pub fn key(&mut self) -> Option<K>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
self.key_value().map(|(k, _v)| k)
}
/// Loads the value for the referenced cell.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the returned value is always the
/// most up to date value.
///
/// It is also possible that the cell has been deleted, in which case the
/// returned value will be `None`
pub fn value(&mut self) -> Option<V>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
self.key_value().map(|(_k, v)| v)
}
/// Loads the key-value pair for the referenced cell.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the returned value is always the
/// most up to date value.
///
/// It is also possible that the cell has been deleted, in which case the
/// returned value will be `None`.
pub fn key_value(&mut self) -> Option<(K, V)>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
loop {
let value = self.cell.value.load(Ordering::Relaxed);
if value.is_null() {
return None;
}
let key = self.cell.key.load(Ordering::Relaxed);
if value.is_redirect() || self.hash != self.cell.hash.load(Ordering::Relaxed) {
// Map has/is being migrated, help and then try again ...
self.map.participate_in_migration();
if let Some(new_cell) = self.map.find(&key, self.hash) {
self.cell = new_cell;
} else {
// Migration caused removal of cell:
return None;
}
} else {
return Some((key, value));
}
}
}
}
/// A reference type to a cell in a [`LeapMap`] which can mutate the referenced
/// cell value.
pub struct RefMut<'a, K, V, H, A: Allocator> {
/// The atomic value which is being referenced.
cell: &'a AtomicCell<K, V>,
/// Reference to the map in which the cell belongs.
map: &'a LeapMap<K, V, H, A>,
/// The hash for the cell at the point when the cell was found
pub(crate) hash: u64,
}
impl<'a, K, V, H, A> RefMut<'a, K, V, H, A>
where
A: Allocator,
V: Value,
{
/// Creates a new mutable reference type referencing the specified `cell`
/// and `map`.
pub fn new(
map: &'a LeapMap<K, V, H, A>,
cell: &'a AtomicCell<K, V>,
hash: u64,
) -> RefMut<'a, K, V, H, A> {
RefMut { map, cell, hash }
}
/// Loads the key for the referenced cell.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the returned value is always the
/// most up to date value.
///
/// It is also possible that the cell has been deleted, in which case the
/// returned value will be `None`
pub fn key(&mut self) -> Option<K>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
self.key_value().map(|(k, _v)| k)
}
/// Loads the value for the referenced cell.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the returned value is always the
/// most up to date value.
///
/// It is also possible that the cell has been deleted, in which case the
/// returned value will be `None`
pub fn value(&mut self) -> Option<V>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
self.key_value().map(|(_k, v)| v)
}
/// Loads the key-value pair for the referenced cell.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the returned value is always the
/// most up to date value.
///
/// It is also possible that the cell has been deleted, in which case the
/// returned value will be `None`.
pub fn key_value(&mut self) -> Option<(K, V)>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
loop {
let value = self.cell.value.load(Ordering::Relaxed);
if value.is_null() {
return None;
}
let key = self.cell.key.load(Ordering::Relaxed);
if value.is_redirect() || self.hash != self.cell.hash.load(Ordering::Relaxed) {
// Map has/is being migrated, help and then try again ...
self.map.participate_in_migration();
if let Some(new_cell) = self.map.find(&key, self.hash) {
self.cell = new_cell;
} else {
// Migration caused removal of cell:
return None;
}
} else {
return Some((key, value));
}
}
}
/// Sets the value for the referenced cell, returning the old value if the
/// cell is still valid, or `None` if the cell has been deleted.
///
/// This requires `&mut self` since it's possible that the underlying data
/// for the map has been migrated, and that therefore the referenced cell
/// is out of date, and returning the current value will be incorrect. In
/// such a case, the cell needs to be updated to reference the correct cell,
/// hence `mut self`. This ensures that the store is only performed if the
/// referenced cell is still valid.
pub fn set_value(&mut self, value: V) -> Option<V>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
{
loop {
let current = self.cell.value.load(Ordering::Relaxed);
if current.is_redirect() || self.hash != self.cell.hash.load(Ordering::Relaxed) {
// Map has/is being migrated, help and then try again ...
self.map.participate_in_migration();
let key = self.cell.key.load(Ordering::Relaxed);
if let Some(new_cell) = self.map.find(&key, self.hash) {
self.cell = new_cell;
} else {
// Cell has been removed
return None;
}
} else if current.is_null() {
// Value has been erased, we can just return.
return None;
} else if self
.cell
.value
.compare_exchange_weak(current, value, Ordering::Relaxed, Ordering::Relaxed)
.is_ok()
{
return Some(current);
}
}
}
/// Updates the value for the referenced cell, using the `func` to compute
/// the new value, returning the old value if the cell is still in the map,
/// and `None` if the cell has been deleted.
///
/// # Examples
///
/// ```
/// let map = leapfrog::LeapMap::new();
/// map.insert(1, 12);
/// if let Some(mut kv_ref) = map.get_mut(&1) {
/// kv_ref.update(|mut v| {
/// *v += 1;
/// });
/// }
///
/// assert_eq!(map.get(&1).unwrap().value(), Some(13));
pub fn update<F>(&mut self, mut func: F) -> Option<V>
where
K: Eq + Hash + Copy,
H: BuildHasher + Default,
F: FnMut(&mut V),
{
loop {
let current = self.cell.value.load(Ordering::Relaxed);
let mut updated = current;
func(&mut updated);
if current.is_redirect() || self.hash != self.cell.hash.load(Ordering::Relaxed) {
// Map has/is being migrated, help and then try again ...
self.map.participate_in_migration();
let key = self.cell.key.load(Ordering::Relaxed);
if let Some(new_cell) = self.map.find(&key, self.hash) {
self.cell = new_cell;
} else {
// Cell has been removed:
return None;
}
} else if current.is_null() {
// Value has been erased.
return None;
} else if self
.cell
.value
.compare_exchange_weak(current, updated, Ordering::Relaxed, Ordering::Relaxed)
.is_ok()
{
return Some(current);
}
// Lost the race to update the cell, go and try again
}
}
}