kovan_map/hashmap/conditional.rs
1//! The conditional writes: `remove_if`, `replace_if`, `compute` and their equality forms.
2//!
3//! Each runs its closure exactly once, on a node no other write can change meanwhile: it first
4//! holds the key's link word (its node's `next`, or for a `compute` of an absent key the chain's
5//! last link) by one CAS that sets the word's `HELD` flag, then runs the closure, then writes
6//! what the closure decided with one store: the node marked deleted, marked naming its
7//! replacement, a new node linked at the chain's end, or the word as it was. Only the holder
8//! writes a held word (every other writer's CAS expects the word without the flag, and a
9//! migration waits for the release), so the store is the operation's linearization point and
10//! the value the closure saw is the value it replaces. Readers never wait for a hold. A closure
11//! that unwinds leaves the word as it was.
12//!
13//! A lock-free retry (decide, CAS, decide again on the node that won) would run the closure
14//! more than once, which an `FnOnce` cannot be. Modelled in `proofs/tla/chained/ChainedMap.tla`
15//! (actions H0 to H9); deciding on a node without holding it (Mutation "unheld_check") writes
16//! over a value the closure never saw.
17
18use super::node::{HELD, MARK, Node, with, word};
19use super::table::TableRef;
20use super::walk::Found;
21use super::{Backoff, HashMap, Pending};
22use crate::MaybeSend;
23use core::borrow::Borrow;
24use core::hash::{BuildHasher, Hash};
25use core::sync::atomic::Ordering;
26use kovan::{Atomic, Guard, pin};
27
28impl<K, V, S> HashMap<K, V, S>
29where
30 K: Hash + Eq + Clone + MaybeSend + 'static,
31 V: Clone + MaybeSend + 'static,
32 S: BuildHasher,
33{
34 /// Removes the key's entry if `pred` holds for its value, returning the value removed.
35 ///
36 /// Answers `None` when the key is absent or `pred` refused its value, and then changes
37 /// nothing. Linearizable and exact: `pred` runs exactly once when the key is present (never
38 /// when it is absent), on the value of the key's node, which this call holds while `pred`
39 /// runs, so no write of the key lands between the check and the removal. A slow `pred`
40 /// stalls the writers of that node's link until it returns (the key's writers, an insert
41 /// into the chain when the node is its last, the remover of the node's successor, and a
42 /// resize); readers never wait. `pred` must not write to this map (a write of the key would
43 /// wait for itself). A `pred` that panics leaves the map unchanged.
44 ///
45 /// # Examples
46 ///
47 /// ```
48 /// use kovan_map::HashMap;
49 ///
50 /// let map = HashMap::with_capacity(64);
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::<Q, true>(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::HashMap;
74 ///
75 /// let map = HashMap::with_capacity(64);
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::<Q, true>(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, on the
96 /// value of the node the replace would replace, held while it runs, 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::HashMap;
103 ///
104 /// let map = HashMap::with_capacity(64);
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 let mut backoff = Backoff::new();
117 loop {
118 let guard = pin();
119 let (_, found) = self.find(hash, &key, &guard);
120 let (prev, old, next) = match found {
121 Found::Frozen => {
122 drop(guard);
123 self.wait_for_resize();
124 continue;
125 }
126 Found::Miss { .. } => return Err(None),
127 Found::Hit { prev, node, next } => (prev, node, next),
128 };
129 let Some(held) = Hold::take(&old.next, next, &guard) else {
130 backoff.spin();
131 continue;
132 };
133 if !pred(&old.value) {
134 drop(held);
135 // The node stays protected by `guard` after the release.
136 return Err(Some(old.value.clone()));
137 }
138 // Cloned before the write: a panicking clone leaves the map as it was.
139 let previous = old.value.clone();
140 let node = Pending::Parts { key, value }.into_node(hash, next);
141 // The replace: the old node deleted, naming the new node, which names the old
142 // successor.
143 held.write(with(node, MARK));
144 self.unlink(prev, old, node, hash, &old.key, &guard);
145 return Ok(previous);
146 }
147 }
148
149 /// Replaces the key's value with `value` if the present one equals `expected`:
150 /// [`replace_if`](Self::replace_if) with an equality predicate, answered the same way.
151 ///
152 /// # Examples
153 ///
154 /// ```
155 /// use kovan_map::HashMap;
156 ///
157 /// let map = HashMap::with_capacity(64);
158 /// map.insert(7, 1);
159 /// assert_eq!(map.compare_and_swap(7, &2, 3), Err(Some(1)));
160 /// assert_eq!(map.compare_and_swap(7, &1, 3), Ok(1));
161 /// assert_eq!(map.compare_and_swap(8, &1, 3), Err(None));
162 /// assert_eq!(map.get(&7), Some(3));
163 /// ```
164 pub fn compare_and_swap(&self, key: K, expected: &V, value: V) -> Result<V, Option<V>>
165 where
166 V: PartialEq,
167 {
168 self.replace_if(key, value, |present| present == expected)
169 }
170
171 /// One atomic read-modify-write of the key: `f` sees the present value (`None` when the key
172 /// is absent) and answers the value the key holds next, `Some(new)` to insert or replace,
173 /// `None` to remove (or leave the key absent). Answers the value the map holds for the key
174 /// after the call.
175 ///
176 /// `f` runs exactly once, while this call holds the key's node (or, for an absent key, the
177 /// chain's last link, where the key's node would be linked), so no write of the key lands
178 /// between what `f` saw and what it wrote: the operation is linearizable. A slow `f` stalls
179 /// the writers of the held link until it returns (the key's writers, inserts into the chain
180 /// when the link is its last, the remover of the node's successor, and a resize); readers
181 /// never wait. `f` must not write to this map (a write of the key would wait for itself). An
182 /// `f` that panics leaves the map unchanged. Allocates only when it links a node (`f`
183 /// answered `Some`).
184 ///
185 /// # Examples
186 ///
187 /// ```
188 /// use kovan_map::HashMap;
189 ///
190 /// let hits = HashMap::with_capacity(64);
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 let mut backoff = Backoff::new();
204 loop {
205 let guard = pin();
206 let (table, found) = self.find(hash, &key, &guard);
207 match found {
208 Found::Frozen => {
209 drop(guard);
210 self.wait_for_resize();
211 }
212 Found::Hit {
213 prev,
214 node: old,
215 next,
216 } => {
217 let Some(held) = Hold::take(&old.next, next, &guard) else {
218 backoff.spin();
219 continue;
220 };
221 let Some(new) = f(Some(&old.value)) else {
222 held.write(with(next, MARK));
223 let shrink_to = self.count_out(table);
224 self.unlink(prev, old, next, hash, &key, &guard);
225 if let Some(capacity) = shrink_to {
226 drop(guard);
227 self.try_resize(capacity);
228 }
229 return None;
230 };
231 // Cloned before the write: a panicking clone leaves the map as it was.
232 let answer = new.clone();
233 let node = Pending::Parts { key, value: new }.into_node(hash, next);
234 held.write(with(node, MARK));
235 self.unlink(prev, old, node, hash, &old.key, &guard);
236 return Some(answer);
237 }
238 Found::Miss { tail } => {
239 // The chain's last link, held: no node of the key can be linked in this
240 // chain until the holder writes it (a new key goes at the end).
241 let Some(held) = Hold::take(tail, core::ptr::null_mut(), &guard) else {
242 backoff.spin();
243 continue;
244 };
245 let new = f(None)?;
246 // Cloned before the write: a panicking clone leaves the map as it was.
247 let answer = new.clone();
248 let node =
249 Pending::Parts { key, value: new }.into_node(hash, core::ptr::null_mut());
250 held.write(node);
251 self.landed(table, guard);
252 return Some(answer);
253 }
254 }
255 }
256 }
257
258 /// The one remove, of `remove`, `remove_if` and `compare_and_remove`: mark the key's node
259 /// deleted if `pred` holds for its value, count it out, and unlink it. With `HOLD`, `pred`
260 /// runs once, while this call holds the node's link word, and the mark is the holder's
261 /// store; without it (`remove`, whose predicate always holds) the mark is one CAS.
262 #[inline(always)]
263 pub(super) fn remove_where<Q, const HOLD: bool>(
264 &self,
265 key: &Q,
266 pred: impl FnOnce(&V) -> bool,
267 ) -> Option<V>
268 where
269 K: Borrow<Q>,
270 Q: Hash + Eq + ?Sized,
271 {
272 let hash = self.hasher.hash_one(key);
273 let mut backoff = Backoff::new();
274 loop {
275 let guard = pin();
276 let (table, found) = self.find(hash, key, &guard);
277 let (prev, node, next) = match found {
278 Found::Frozen => {
279 drop(guard);
280 self.wait_for_resize();
281 continue;
282 }
283 Found::Miss { .. } => return None,
284 Found::Hit { prev, node, next } => (prev, node, next),
285 };
286 let value = if HOLD {
287 let Some(held) = Hold::take(&node.next, next, &guard) else {
288 backoff.spin();
289 continue;
290 };
291 if !pred(&node.value) {
292 return None;
293 }
294 // Cloned before the mark: a panicking clone leaves the map as it was.
295 let value = node.value.clone();
296 held.write(with(next, MARK));
297 value
298 } else {
299 // Cloned before the CAS: a panicking clone leaves the map as it was.
300 let value = node.value.clone();
301 // The removal: the node's own word marked, keeping its successor.
302 if node
303 .next
304 .compare_exchange(
305 word(next),
306 word(with(next, MARK)),
307 Ordering::AcqRel,
308 Ordering::Relaxed,
309 &guard,
310 )
311 .is_err()
312 {
313 backoff.spin();
314 continue;
315 }
316 value
317 };
318 let shrink_to = self.count_out(table);
319 self.unlink(prev, node, next, hash, key, &guard);
320 if let Some(capacity) = shrink_to {
321 drop(guard);
322 self.try_resize(capacity);
323 }
324 return Some(value);
325 }
326 }
327
328 /// A node this call marked deleted is counted out of `table`, the table it was deleted in:
329 /// the capacity to shrink the table to when it falls under a quarter full (never below the
330 /// map's floor).
331 #[inline(always)]
332 fn count_out(&self, table: TableRef<K, V>) -> Option<usize> {
333 let remaining = table.count().fetch_sub(1, Ordering::Relaxed) - 1;
334 let capacity = table.capacity();
335 // Integer load-factor check: count/cap < 1/4.
336 (4 * (remaining.max(0) as usize) < capacity && capacity > self.floor)
337 .then_some(capacity / 2)
338 }
339}
340
341/// A link word this call holds: its `HELD` flag set by this call's CAS. Only this call writes
342/// the word until [`Hold::write`] stores the word it decided; dropped unwritten (the closure
343/// refused, or unwound), it stores the word as it was.
344struct Hold<'g, K, V> {
345 link: &'g Atomic<Node<K, V>>,
346 /// The word held, without the flag.
347 word: *mut Node<K, V>,
348}
349
350impl<'g, K, V> Hold<'g, K, V> {
351 /// Hold `link` if it is still `word` (unmarked, unfrozen and not held): `None` when another
352 /// write changed or holds it, and the caller walks again.
353 #[inline]
354 fn take(
355 link: &'g Atomic<Node<K, V>>,
356 word_now: *mut Node<K, V>,
357 guard: &Guard,
358 ) -> Option<Self> {
359 // Acquire: the closure reads the node's fields after the hold, which the link's own
360 // publication made visible; Relaxed on failure: nothing is read.
361 link.compare_exchange(
362 word(word_now),
363 word(with(word_now, HELD)),
364 Ordering::Acquire,
365 Ordering::Relaxed,
366 guard,
367 )
368 .ok()
369 .map(|_| Self {
370 link,
371 word: word_now,
372 })
373 }
374
375 /// Store `decided` in the held link: the conditional write's linearization point. A store,
376 /// not a CAS: no other thread writes a held link. Release: a reader that acquires the word
377 /// sees the fields of a node it newly names.
378 #[inline]
379 fn write(self, decided: *mut Node<K, V>) {
380 self.link.store(word(decided), Ordering::Release);
381 core::mem::forget(self);
382 }
383}
384
385impl<K, V> Drop for Hold<'_, K, V> {
386 fn drop(&mut self) {
387 // The word as it was: the key and the chain are as they were before the hold.
388 self.link.store(word(self.word), Ordering::Release);
389 }
390}