qubit_cas/fast/fast_cas.rs
1/*******************************************************************************
2 *
3 * Copyright (c) 2025 - 2026 Haixing Hu.
4 *
5 * SPDX-License-Identifier: Apache-2.0
6 *
7 * Licensed under the Apache License, Version 2.0.
8 *
9 ******************************************************************************/
10//! Compare-and-swap executor for compact [`usize`] state codes.
11//!
12//! The main type is [`FastCas`]. See the [`crate::fast`] module documentation
13//! for how this layer relates to [`crate::CasExecutor`] and which APIs honor
14//! [`FastCasPolicy`] retries.
15
16use std::convert::Infallible;
17use std::thread;
18
19use super::{
20 FastCasDecision,
21 FastCasError,
22 FastCasPolicy,
23 FastCasState,
24 FastCasSuccess,
25};
26
27/// Ultra-light compare-and-swap executor for `usize` state codes.
28///
29/// Use `FastCas` on hot paths where shared state is a compact integer code (for
30/// example a small state-machine phase or lock word). The executor:
31///
32/// - Stores only a [`FastCasPolicy`] (`Copy`, no heap).
33/// - Retries when [`FastCasState::compare_set`] fails because another writer
34/// changed the value between your read and CAS (**conflict**). Business
35/// errors returned as [`FastCasDecision::Abort`] do **not** trigger retries.
36/// - Expects the operation closure passed to [`Self::execute`] /
37/// [`Self::update_by`] to be safe to call again after conflicts: re-read the
38/// current code from the closure argument each time; avoid non-idempotent side
39/// effects inside the closure.
40///
41/// [`FastCas::compare_update`] and [`FastCas::compare_update_with`] perform a
42/// **single** CAS attempt per call and **ignore** the configured policy (no
43/// spin or retry loop).
44///
45/// # Examples
46///
47/// Pick a constructor, share one [`FastCasState`] across threads, then run
48/// [`Self::execute`], [`Self::update_by`], or a compare-update helper.
49///
50/// ```
51/// use qubit_cas::{FastCas, FastCasDecision, FastCasState};
52///
53/// const IDLE: usize = 0;
54/// const BUSY: usize = 1;
55///
56/// let cas = FastCas::spin(32);
57/// let state = FastCasState::new(IDLE);
58///
59/// let ok = cas
60/// .execute(&state, |current| {
61/// if current == IDLE {
62/// FastCasDecision::update(BUSY, "go")
63/// } else {
64/// FastCasDecision::abort("not idle")
65/// }
66/// })
67/// .unwrap();
68///
69/// assert_eq!(ok.current(), BUSY);
70/// assert_eq!(*ok.output(), "go");
71/// ```
72#[derive(Debug, Clone, Copy, Eq, PartialEq)]
73pub struct FastCas {
74 /// Retry policy used for CAS conflicts.
75 policy: FastCasPolicy,
76}
77
78impl FastCas {
79 /// Creates a [`FastCas`] executor that performs one CAS attempt.
80 ///
81 /// Equivalent to [`FastCasPolicy::once`]. After the first lost CAS,
82 /// [`FastCasError::Conflict`] is returned with the observed state.
83 ///
84 /// # Returns
85 /// A single-attempt executor.
86 ///
87 /// # Examples
88 ///
89 /// ```
90 /// use qubit_cas::{FastCas, FastCasState};
91 ///
92 /// let cas = FastCas::once();
93 /// assert_eq!(cas.policy().max_attempts(), 1);
94 /// let _state = FastCasState::new(0);
95 /// ```
96 #[inline]
97 pub const fn once() -> Self {
98 Self {
99 policy: FastCasPolicy::once(),
100 }
101 }
102
103 /// Creates a [`FastCas`] executor that retries CAS conflicts immediately.
104 ///
105 /// Retries busy-spin in the current thread (no `thread::yield_now`) until
106 /// success, abort, or the attempt budget is exhausted.
107 ///
108 /// # Parameters
109 /// - `max_attempts`: Maximum number of CAS attempts. Zero is normalized to
110 /// one attempt.
111 ///
112 /// # Returns
113 /// A spin executor.
114 ///
115 /// # Examples
116 ///
117 /// ```
118 /// use qubit_cas::FastCas;
119 ///
120 /// let cas = FastCas::spin(64);
121 /// assert_eq!(cas.policy().max_attempts(), 64);
122 /// ```
123 #[inline]
124 pub const fn spin(max_attempts: u32) -> Self {
125 Self {
126 policy: FastCasPolicy::spin(max_attempts),
127 }
128 }
129
130 /// Creates a [`FastCas`] executor that spins first and then yields.
131 ///
132 /// After `spin_attempts` attempts, [`std::thread::yield_now`] runs before
133 /// subsequent retries. Caps internal spin budget to `max_attempts` when
134 /// `spin_attempts` is larger.
135 ///
136 /// # Parameters
137 /// - `spin_attempts`: Number of attempts to run before yielding.
138 /// - `max_attempts`: Maximum number of CAS attempts. Zero is normalized to
139 /// one attempt.
140 ///
141 /// # Returns
142 /// A spin-yield executor.
143 ///
144 /// # Examples
145 ///
146 /// ```
147 /// use qubit_cas::FastCas;
148 ///
149 /// let cas = FastCas::spin_yield(8, 128);
150 /// let p = cas.policy();
151 /// assert_eq!(p.max_attempts(), 128);
152 /// ```
153 #[inline]
154 pub const fn spin_yield(spin_attempts: u32, max_attempts: u32) -> Self {
155 Self {
156 policy: FastCasPolicy::spin_yield(spin_attempts, max_attempts),
157 }
158 }
159
160 /// Creates a [`FastCas`] executor from an explicit policy.
161 ///
162 /// # Parameters
163 /// - `policy`: Retry policy used for CAS conflicts.
164 ///
165 /// # Returns
166 /// An executor using `policy`.
167 #[inline]
168 pub const fn with_policy(policy: FastCasPolicy) -> Self {
169 Self { policy }
170 }
171
172 /// Returns the retry policy used by this executor.
173 ///
174 /// # Returns
175 /// The configured retry policy.
176 #[inline]
177 pub const fn policy(&self) -> FastCasPolicy {
178 self.policy
179 }
180
181 /// Executes a CAS operation described by a decision-returning closure.
182 ///
183 /// The closure receives the current state code from [`FastCasState::load`].
184 /// It may run **multiple times** when another thread wins the CAS between
185 /// your decision and the write; only [`FastCasDecision::Update`] performs a
186 /// write. [`FastCasDecision::Finish`] succeeds without mutating `state`.
187 ///
188 /// # Parameters
189 /// - `state`: Shared state code.
190 /// - `operation`: Operation to evaluate for each observed state.
191 ///
192 /// # Returns
193 /// A success result when the operation updates or finishes.
194 ///
195 /// # Errors
196 /// Returns [`FastCasError::Abort`] when the operation aborts. Returns
197 /// [`FastCasError::Conflict`] when CAS conflicts exhaust the retry policy.
198 ///
199 /// # Examples
200 ///
201 /// ```
202 /// use qubit_cas::{FastCas, FastCasDecision, FastCasState};
203 ///
204 /// let cas = FastCas::spin(16);
205 /// let state = FastCasState::new(0);
206 ///
207 /// let ok = cas
208 /// .execute(&state, |n| -> FastCasDecision<&str, ()> {
209 /// if n == 0 {
210 /// FastCasDecision::update(1, "first")
211 /// } else {
212 /// FastCasDecision::finish("noop")
213 /// }
214 /// })
215 /// .unwrap();
216 ///
217 /// assert_eq!(ok.current(), 1);
218 /// assert_eq!(*ok.output(), "first");
219 /// ```
220 #[inline(always)]
221 pub fn execute<R, E, F>(&self, state: &FastCasState, operation: F) -> Result<FastCasSuccess<R>, FastCasError<E>>
222 where
223 F: Fn(usize) -> FastCasDecision<R, E>,
224 {
225 let max_attempts = self.policy.max_attempts();
226 let mut attempts = 1;
227 loop {
228 let current = state.load();
229 match operation(current) {
230 FastCasDecision::Update { next, output } => match state.compare_set(current, next) {
231 Ok(()) => {
232 return Ok(FastCasSuccess::updated(current, next, output, attempts));
233 }
234 Err(actual) if attempts >= max_attempts => {
235 return Err(FastCasError::Conflict {
236 current: actual,
237 attempts,
238 });
239 }
240 Err(_) => {}
241 },
242 FastCasDecision::Finish { output } => {
243 return Ok(FastCasSuccess::finished(current, output, attempts));
244 }
245 FastCasDecision::Abort { error } => {
246 return Err(FastCasError::Abort {
247 current,
248 error,
249 attempts,
250 });
251 }
252 }
253 attempts += 1;
254 if self.policy.should_yield_before(attempts) {
255 thread::yield_now();
256 }
257 }
258 }
259
260 /// Executes a compact update operation.
261 ///
262 /// `Ok((next, output))` maps to [`FastCasDecision::Update`] and attempts to
263 /// install `next`, returning `output` after the CAS succeeds.
264 /// `Err(error)` maps to [`FastCasDecision::Abort`] and performs no write.
265 ///
266 /// This is a thin wrapper over [`Self::execute`]; the same re-entrancy and
267 /// conflict-retry rules apply.
268 ///
269 /// # Parameters
270 /// - `state`: Shared state code.
271 /// - `operation`: Operation to evaluate for each observed state.
272 ///
273 /// # Returns
274 /// A success result after `next` is installed.
275 ///
276 /// # Errors
277 /// Returns [`FastCasError::Abort`] when `operation` returns `Err`. Returns
278 /// [`FastCasError::Conflict`] when CAS conflicts exhaust the retry policy.
279 ///
280 /// # Examples
281 ///
282 /// ```
283 /// use qubit_cas::{FastCas, FastCasState};
284 ///
285 /// let cas = FastCas::default();
286 /// let state = FastCasState::new(2);
287 ///
288 /// let ok = cas
289 /// .update_by(&state, |current| Ok::<(usize, usize), ()>((current + 1, current + 1)))
290 /// .unwrap();
291 ///
292 /// assert_eq!(ok.current(), 3);
293 /// assert_eq!(ok.into_output(), 3);
294 /// ```
295 #[inline(always)]
296 pub fn update_by<R, E, F>(&self, state: &FastCasState, operation: F) -> Result<FastCasSuccess<R>, FastCasError<E>>
297 where
298 F: Fn(usize) -> Result<(usize, R), E>,
299 {
300 self.execute(state, |current| match operation(current) {
301 Ok((next, output)) => FastCasDecision::update(next, output),
302 Err(error) => FastCasDecision::abort(error),
303 })
304 }
305
306 /// Attempts one fixed expected-to-next transition.
307 ///
308 /// Performs exactly **one** [`FastCasState::compare_set`] call. The
309 /// executor's [`FastCasPolicy`] is **not** used: there is no retry loop. If
310 /// the loaded value is not `expected`, or the CAS fails, this returns
311 /// [`FastCasError::Conflict`] with the observed `current` state.
312 ///
313 /// For multi-step or observe-then-decide logic, use [`Self::execute`] or
314 /// [`Self::update_by`] instead.
315 ///
316 /// # Parameters
317 /// - `state`: Shared state code.
318 /// - `expected`: Required current state code.
319 /// - `next`: State code to install when `expected` matches.
320 ///
321 /// # Returns
322 /// A success result with unit output when the transition is installed.
323 ///
324 /// # Errors
325 /// Returns conflict if the current state is not `expected` or if the CAS
326 /// write loses the race.
327 ///
328 /// # Examples
329 ///
330 /// ```
331 /// use qubit_cas::{FastCas, FastCasState};
332 ///
333 /// let cas = FastCas::once();
334 /// let state = FastCasState::new(0);
335 ///
336 /// let ok = cas.compare_update(&state, 0, 1).unwrap();
337 /// assert!(ok.is_updated());
338 /// assert_eq!(ok.current(), 1);
339 /// ```
340 #[inline(always)]
341 pub fn compare_update(
342 &self,
343 state: &FastCasState,
344 expected: usize,
345 next: usize,
346 ) -> Result<FastCasSuccess<()>, FastCasError<Infallible>> {
347 self.compare_update_with(state, expected, next, |_, _| ())
348 }
349
350 /// Attempts one fixed expected-to-next transition and computes output after
351 /// success.
352 ///
353 /// Same single-CAS semantics as [`Self::compare_update`]. The `output`
354 /// closure runs **only** after a successful CAS; it receives `(expected,
355 /// next)` so callers can build messages or metrics without observing stale
356 /// races.
357 ///
358 /// # Parameters
359 /// - `state`: Shared state code.
360 /// - `expected`: Required current state code.
361 /// - `next`: State code to install when `expected` matches.
362 /// - `output`: Output factory invoked after a successful CAS write.
363 ///
364 /// # Returns
365 /// A success result with the computed output.
366 ///
367 /// # Errors
368 /// Returns conflict if the current state is not `expected` or if the CAS
369 /// write loses the race.
370 ///
371 /// # Examples
372 ///
373 /// ```
374 /// use qubit_cas::{FastCas, FastCasState};
375 ///
376 /// let cas = FastCas::once();
377 /// let state = FastCasState::new(10);
378 ///
379 /// let ok = cas
380 /// .compare_update_with(&state, 10, 11, |prev, next| prev + next)
381 /// .unwrap();
382 ///
383 /// assert_eq!(ok.into_output(), 21);
384 /// ```
385 #[inline(always)]
386 pub fn compare_update_with<R, F>(
387 &self,
388 state: &FastCasState,
389 expected: usize,
390 next: usize,
391 output: F,
392 ) -> Result<FastCasSuccess<R>, FastCasError<Infallible>>
393 where
394 F: Fn(usize, usize) -> R,
395 {
396 let attempts = 1;
397 match state.compare_set(expected, next) {
398 Ok(()) => Ok(FastCasSuccess::updated(
399 expected,
400 next,
401 output(expected, next),
402 attempts,
403 )),
404 Err(current) => Err(FastCasError::Conflict { current, attempts }),
405 }
406 }
407}
408
409impl Default for FastCas {
410 /// Creates the default fast CAS executor.
411 ///
412 /// Equivalent to calling [`FastCas::spin`] with `16` attempts: a small spin
413 /// bound suitable for low-latency contention without yielding by default.
414 ///
415 /// # Returns
416 /// A latency-oriented executor with a small spin budget.
417 #[inline]
418 fn default() -> Self {
419 Self::spin(16)
420 }
421}