kovan_map/hopscotch/conditional.rs
1//! The conditional writes: `remove_if`, `replace_if`, `compute` and their equality forms. Each
2//! runs its closure exactly once, under the key's home guard, on the value the key holds then
3//! (or on its absence), and writes what the closure decided before it releases the guard: the
4//! check and the write are one step, as the existence scan and the slot claim of an insert are.
5//!
6//! A `compute` of an absent key reserves the slot its entry would take before its closure runs
7//! (the slot holds [`Word::reserved`], its hop bit published): placing an entry can need a
8//! displacement that loses a race or a resize, and both make a writer release its guard and try
9//! again, which a closure that already ran cannot. With the slot reserved first, the entry the
10//! closure makes lands without the guard ever being released; a closure that makes none, or
11//! unwinds, gives the slot back. Modelled in `proofs/tla/hopscotch/HopscotchMap.tla` (actions CS to
12//! CA, and IS, IFr and IL for a compute's reservation); deciding on a value read outside the
13//! guard (Mutation "unguarded_check") writes over a value the closure never saw.
14
15extern crate alloc;
16
17use super::displace::Placed;
18use super::table::{Entry, HomeGuard, Table, Word};
19use super::{Blocked, HopscotchMap};
20use crate::sync::spin_hint;
21use core::borrow::Borrow;
22use core::hash::{BuildHasher, Hash};
23use core::sync::atomic::Ordering;
24use kovan::{NodeBox, pin, retire_node};
25
26#[cfg(test)]
27use super::pause;
28
29impl<K, V, S> HopscotchMap<K, V, S>
30where
31 K: Hash + Eq + Clone + Send + 'static,
32 V: Clone + Send + 'static,
33 S: BuildHasher,
34{
35 /// Removes the key's entry if `pred` holds for its value, returning the value removed.
36 ///
37 /// Answers `None` when the key is absent or `pred` refused its value, and then changes
38 /// nothing. Linearizable and exact: `pred` runs exactly once when the key is present (never
39 /// when it is absent), on the value the key holds at the operation's linearization point,
40 /// while the key's home is held, so no write of the key lands between the check and the
41 /// unlink. A slow `pred` stalls every writer of that home (and a resize) until it returns,
42 /// and `pred` must not write to this map (a write to a key of the same home would wait for
43 /// itself). A `pred` that panics leaves the map unchanged.
44 ///
45 /// # Examples
46 ///
47 /// ```
48 /// use kovan_map::HopscotchMap;
49 ///
50 /// let map = HopscotchMap::new();
51 /// map.insert(1, 10);
52 /// assert_eq!(map.remove_if(&2, |_| true), None); // absent
53 /// assert_eq!(map.remove_if(&1, |v| *v > 10), None); // refused, kept
54 /// assert_eq!(map.get(&1), Some(10));
55 /// assert_eq!(map.remove_if(&1, |v| *v == 10), Some(10));
56 /// assert_eq!(map.get(&1), None);
57 /// ```
58 pub fn remove_if<Q, F>(&self, key: &Q, pred: F) -> Option<V>
59 where
60 K: Borrow<Q>,
61 Q: Hash + Eq + ?Sized,
62 F: FnOnce(&V) -> bool,
63 {
64 self.remove_where(key, pred)
65 }
66
67 /// Removes the key's entry if its value equals `expected`, returning the value removed:
68 /// [`remove_if`](Self::remove_if) with an equality predicate.
69 ///
70 /// # Examples
71 ///
72 /// ```
73 /// use kovan_map::HopscotchMap;
74 ///
75 /// let map = HopscotchMap::new();
76 /// map.insert("job", 3);
77 /// assert_eq!(map.compare_and_remove("job", &4), None);
78 /// assert_eq!(map.compare_and_remove("job", &3), Some(3));
79 /// assert!(map.is_empty());
80 /// ```
81 pub fn compare_and_remove<Q>(&self, key: &Q, expected: &V) -> Option<V>
82 where
83 K: Borrow<Q>,
84 Q: Hash + Eq + ?Sized,
85 V: PartialEq,
86 {
87 self.remove_where(key, |value| value == expected)
88 }
89
90 /// Replaces the key's value with `value` if `pred` holds for the present one.
91 ///
92 /// `Ok` with the value replaced when it replaced; `Err(Some(current))` when `pred` refused
93 /// the present value `current`; `Err(None)` when the key is absent (nothing is inserted).
94 /// Either `Err` drops `key` and `value`. Linearizable and exact, as
95 /// [`remove_if`](Self::remove_if): `pred` runs exactly once when the key is present, under
96 /// the key's home guard, on the value the replace would replace, and the same cautions
97 /// hold for a slow, writing or panicking `pred`. Allocates only when it replaces.
98 ///
99 /// # Examples
100 ///
101 /// ```
102 /// use kovan_map::HopscotchMap;
103 ///
104 /// let map = HopscotchMap::new();
105 /// assert_eq!(map.replace_if(1, 20, |_| true), Err(None)); // absent: not inserted
106 /// map.insert(1, 10);
107 /// assert_eq!(map.replace_if(1, 20, |v| *v > 10), Err(Some(10)));
108 /// assert_eq!(map.replace_if(1, 20, |v| *v == 10), Ok(10));
109 /// assert_eq!(map.get(&1), Some(20));
110 /// ```
111 pub fn replace_if<F>(&self, key: K, value: V, pred: F) -> Result<V, Option<V>>
112 where
113 F: FnOnce(&V) -> bool,
114 {
115 let hash = self.hasher.hash_one(&key);
116 loop {
117 self.wait_for_resize();
118 let guard = pin();
119 let (table, home) = match self.home_of(hash, &guard, true) {
120 Ok(held) => held,
121 Err(Blocked::Vacant) => return Err(None),
122 Err(Blocked::Held(_)) => {
123 #[cfg(test)]
124 pause::at(pause::Point::WriterMetHeldGuard);
125 spin_hint();
126 continue;
127 }
128 Err(Blocked::Resizing) => continue,
129 };
130 // The scan reads the home's entries without protecting them: the entry it answers is
131 // borrowed from `home` (only the guard's holder unlinks or retires one), so it is read
132 // only while the guard is held.
133 let Some((offset, word)) = table.find_held(&home, hash, &key, &guard) else {
134 return Err(None);
135 };
136 let Some(found) = word.entry() else {
137 return Err(None);
138 };
139 if !pred(&found.value) {
140 return Err(Some(found.value.clone()));
141 }
142 // Cloned before the write: a panicking clone leaves the map as it was.
143 let old = found.value.clone();
144 // SAFETY: the word names the entry of the slot `offset` past the held home.
145 unsafe {
146 table.replace_held(&home, offset, word.ptr(), Entry::boxed(hash, key, value))
147 };
148 return Ok(old);
149 }
150 }
151
152 /// Replaces the key's value with `value` if the present one equals `expected`:
153 /// [`replace_if`](Self::replace_if) with an equality predicate, answered the same way.
154 ///
155 /// # Examples
156 ///
157 /// ```
158 /// use kovan_map::HopscotchMap;
159 ///
160 /// let map = HopscotchMap::new();
161 /// map.insert(7, 1);
162 /// assert_eq!(map.compare_and_swap(7, &2, 3), Err(Some(1)));
163 /// assert_eq!(map.compare_and_swap(7, &1, 3), Ok(1));
164 /// assert_eq!(map.compare_and_swap(8, &1, 3), Err(None));
165 /// assert_eq!(map.get(&7), Some(3));
166 /// ```
167 pub fn compare_and_swap(&self, key: K, expected: &V, value: V) -> Result<V, Option<V>>
168 where
169 V: PartialEq,
170 {
171 self.replace_if(key, value, |present| present == expected)
172 }
173
174 /// One atomic read-modify-write of the key: `f` sees the present value (`None` when the key
175 /// is absent) and answers the value the key holds next, `Some(new)` to insert or replace,
176 /// `None` to remove (or leave the key absent). Answers the value the map holds for the key
177 /// after the call.
178 ///
179 /// `f` runs exactly once, under the key's home guard, so no write of the key lands between
180 /// what `f` saw and what it wrote: the operation is linearizable. A slow `f` stalls every
181 /// writer of that home (and a resize) until it returns, and `f` must not write to this map
182 /// (a write to a key of the same home would wait for itself). An `f` that panics leaves the
183 /// map unchanged. Allocates only when it links an entry (`f` answered `Some`).
184 ///
185 /// # Examples
186 ///
187 /// ```
188 /// use kovan_map::HopscotchMap;
189 ///
190 /// let hits = HopscotchMap::new();
191 /// let bump = |seen: Option<&u32>| Some(seen.map_or(1, |n| n + 1));
192 /// assert_eq!(hits.compute("page", bump), Some(1));
193 /// assert_eq!(hits.compute("page", bump), Some(2));
194 /// // `None` removes the key.
195 /// assert_eq!(hits.compute("page", |_| None), None);
196 /// assert_eq!(hits.get("page"), None);
197 /// ```
198 pub fn compute<F>(&self, key: K, f: F) -> Option<V>
199 where
200 F: FnOnce(Option<&V>) -> Option<V>,
201 {
202 let hash = self.hasher.hash_one(&key);
203 loop {
204 self.wait_for_resize();
205 let guard = pin();
206 // The guard is taken even for an empty home: `f` decides once, on what it sees,
207 // so no other write of the key may land until what it decided is written.
208 let (table, mut home) = match self.home_of(hash, &guard, false) {
209 Ok(held) => held,
210 Err(Blocked::Held(_)) => {
211 #[cfg(test)]
212 pause::at(pause::Point::WriterMetHeldGuard);
213 spin_hint();
214 continue;
215 }
216 Err(_) => continue,
217 };
218
219 // The scan reads the home's entries without protecting them: the entry it answers is
220 // borrowed from `home` (only the guard's holder unlinks or retires one), so it is read
221 // only while the guard is held.
222 if let Some((offset, word)) = table.find_held(&home, hash, &key, &guard)
223 && let Some(found) = word.entry()
224 {
225 let found_ptr = word.ptr();
226 return match f(Some(&found.value)) {
227 Some(new) => {
228 // Cloned before the write: a panicking clone leaves the map as it was.
229 let answer = new.clone();
230 // SAFETY: `found_ptr` is the entry of the slot `offset` past the held
231 // home.
232 unsafe {
233 table.replace_held(
234 &home,
235 offset,
236 found_ptr,
237 Entry::boxed(hash, key, new),
238 );
239 }
240 Some(answer)
241 }
242 None => {
243 let shrink_to = self.unlink_held(table, &mut home, offset);
244 drop(home);
245 // SAFETY: unlinked above under its home guard, so no other thread
246 // unlinks or retires it; a reader that loaded it holds a guard that
247 // keeps it alive.
248 unsafe { retire_node(found_ptr) };
249 if let Some(capacity) = shrink_to {
250 drop(guard);
251 self.try_resize(capacity);
252 }
253 None
254 }
255 };
256 }
257
258 // Absent. The slot the entry would take is reserved before `f` runs: a displacement
259 // that lost a race, or a table with no room, sends this call around the loop now,
260 // while nothing is decided yet.
261 let offset = match Self::place(table, &mut home, Word::reserved(), &guard) {
262 Placed::At(offset) => offset,
263 Placed::Contended => {
264 drop(home);
265 spin_hint();
266 continue;
267 }
268 Placed::Full => {
269 let capacity = table.capacity * 2;
270 drop(home);
271 drop(guard);
272 self.try_resize(capacity);
273 continue;
274 }
275 };
276 let reserved = Reservation {
277 table,
278 home: &mut home,
279 offset,
280 };
281 #[cfg(test)]
282 pause::at(pause::Point::ComputeReserved);
283 let new = f(None)?;
284 // Cloned before the write: a panicking clone gives the slot back.
285 let answer = new.clone();
286 reserved.fill(Entry::boxed(hash, key, new));
287 let grow_to = self.count_in(table);
288 drop(home);
289 if let Some(capacity) = grow_to {
290 drop(guard);
291 self.try_resize(capacity);
292 }
293 return Some(answer);
294 }
295 }
296
297 /// The one remove, of `remove`, `remove_if` and `compare_and_remove`: under the key's home
298 /// guard, unlink the key's entry if `pred` holds for its value. `pred` runs at most once, on
299 /// the entry the unlink removes.
300 #[inline(always)]
301 pub(super) fn remove_where<Q>(&self, key: &Q, pred: impl FnOnce(&V) -> bool) -> Option<V>
302 where
303 K: Borrow<Q>,
304 Q: Hash + Eq + ?Sized,
305 {
306 let hash = self.hasher.hash_one(key);
307 loop {
308 self.wait_for_resize();
309 let guard = pin();
310 // The home guard, as an insert takes it: the scan below is stable, the check and the
311 // unlink are one step, the unlink cannot race an update or a move of the entry, and
312 // a resize copies the table either before this call takes the guard (and this call
313 // then waits for the new table) or after the unlink. A home without hop bits has no
314 // entry to remove, answered with no guard.
315 let (table, mut home) = match self.home_of(hash, &guard, true) {
316 Ok(held) => held,
317 Err(Blocked::Vacant) => return None,
318 Err(Blocked::Held(_)) => {
319 #[cfg(test)]
320 pause::at(pause::Point::WriterMetHeldGuard);
321 spin_hint();
322 continue;
323 }
324 Err(Blocked::Resizing) => continue,
325 };
326 // The scan reads the home's entries without protecting them: the entry it answers is
327 // borrowed from `home` (only the guard's holder unlinks or retires one), so it is read
328 // only while the guard is held.
329 let (offset, word) = table.find_held(&home, hash, key, &guard)?;
330 let found = word.entry()?;
331 if !pred(&found.value) {
332 return None;
333 }
334 // Cloned before the unlink: a panicking clone leaves the map as it was.
335 let old_value = found.value.clone();
336 let entry_ptr = word.ptr();
337 let shrink_to = self.unlink_held(table, &mut home, offset);
338 drop(home);
339 // SAFETY: unlinked above under its home guard, so no other thread unlinks or
340 // retires it; a reader that loaded it holds a guard that keeps it alive.
341 unsafe { retire_node(entry_ptr) };
342 if let Some(capacity) = shrink_to {
343 drop(guard);
344 self.try_resize(capacity);
345 }
346 return Some(old_value);
347 }
348 }
349}
350
351/// The slot a `compute` of an absent key reserved for the entry its closure may make: the slot
352/// holds [`Word::reserved`] and its hop bit is published, under the home guard `home`. Filled,
353/// it links the entry; dropped unfilled (the closure made none, or unwound), it frees the slot
354/// and stages clearing its bit, so the map is as it was.
355struct Reservation<'r, 'g, K, V> {
356 table: &'g Table<K, V>,
357 home: &'r mut HomeGuard<'g>,
358 offset: usize,
359}
360
361impl<K, V> Reservation<'_, '_, K, V> {
362 /// Link `entry` in the reserved slot: the compute's linearization point, with the slot's hop
363 /// bit published before it, as `link_in` publishes an insert's.
364 #[inline]
365 fn fill(self, entry: NodeBox<Entry<K, V>>) {
366 // A store, not a CAS: no other writer claims a reserved slot. Release: a reader that
367 // acquires the slot sees the entry's fields.
368 self.table
369 .get_bucket(self.home.idx + self.offset)
370 .store(Word::of(entry), Ordering::Release);
371 core::mem::forget(self);
372 }
373}
374
375impl<K, V> Drop for Reservation<'_, '_, K, V> {
376 fn drop(&mut self) {
377 // Release: as a remove frees a slot. A reader passed the reserved word as a free slot
378 // already, so nothing it could find changes.
379 self.table
380 .get_bucket(self.home.idx + self.offset)
381 .store(Word::free(), Ordering::Release);
382 self.home.stage_unlinked(self.offset);
383 }
384}