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