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