1use crate::pad::CachePadded;
26use crate::sync::{AtomicU32, AtomicU64, Ordering, spin};
27
28const TOP_BITS: u32 = 24;
30const TOP_MASK: u64 = (1 << TOP_BITS) - 1;
31
32pub struct IndexStack {
34 head: CachePadded<AtomicU64>,
35 next: Box<[AtomicU32]>,
36}
37
38#[inline]
40fn pack(tag: u64, top_plus_one: u32) -> u64 {
41 (tag << TOP_BITS) | u64::from(top_plus_one)
42}
43
44#[inline]
45#[allow(clippy::cast_possible_truncation)]
46fn unpack(word: u64) -> (u64, u32) {
47 (word >> TOP_BITS, (word & TOP_MASK) as u32)
48}
49
50impl IndexStack {
51 pub const MAX_CAPACITY: u32 = (1 << TOP_BITS) - 1;
53
54 #[must_use]
57 pub fn with_capacity(capacity: u32) -> Self {
58 let capacity = capacity.min(Self::MAX_CAPACITY);
59 Self {
60 head: CachePadded::new(AtomicU64::new(0)),
61 next: (0..capacity).map(|_| AtomicU32::new(0)).collect(),
62 }
63 }
64
65 #[must_use]
67 pub fn capacity(&self) -> usize {
68 self.next.len()
69 }
70
71 pub fn push(&self, value: u32) -> Result<(), u32> {
77 let Some(slot) = self.next.get(value as usize) else {
78 return Err(value);
79 };
80 let mut head = self.head.load(Ordering::Acquire);
81 loop {
82 let (tag, top) = unpack(head);
83 slot.store(top, Ordering::Relaxed);
85 match self.head.compare_exchange_weak(
86 head,
87 pack(tag.wrapping_add(1), value + 1),
88 Ordering::Release,
89 Ordering::Acquire,
90 ) {
91 Ok(_) => return Ok(()),
92 Err(current) => {
93 head = current;
94 spin();
95 }
96 }
97 }
98 }
99
100 pub fn pop(&self) -> Option<u32> {
103 let mut head = self.head.load(Ordering::Acquire);
104 loop {
105 let (tag, top) = unpack(head);
106 let index = top.checked_sub(1)?;
107 let below = self.next[index as usize].load(Ordering::Relaxed);
111 match self.head.compare_exchange_weak(
112 head,
113 pack(tag.wrapping_add(1), below),
114 Ordering::Acquire,
115 Ordering::Acquire,
116 ) {
117 Ok(_) => return Some(index),
118 Err(current) => {
119 head = current;
120 spin();
121 }
122 }
123 }
124 }
125}
126
127#[cfg(all(test, not(loom)))]
128mod tests {
129 #![allow(clippy::unwrap_used)]
130
131 use std::sync::Arc;
132
133 use super::*;
134
135 #[test]
136 fn test_stack_is_lifo_and_empty_and_bounded() {
137 let s = IndexStack::with_capacity(4);
138 assert_eq!(s.capacity(), 4);
139 assert_eq!(s.pop(), None);
140 for i in 0..4 {
141 assert_eq!(s.push(i), Ok(()));
142 }
143 assert_eq!(s.push(4), Err(4), "a value outside the capacity");
144 for i in (0..4).rev() {
145 assert_eq!(s.pop(), Some(i));
146 }
147 assert_eq!(s.pop(), None);
148 s.push(2).unwrap();
150 s.push(0).unwrap();
151 assert_eq!(s.pop(), Some(0));
152 s.push(3).unwrap();
153 assert_eq!(s.pop(), Some(3));
154 assert_eq!(s.pop(), Some(2));
155 assert_eq!(s.pop(), None);
156 }
157
158 #[test]
161 fn test_stack_head_word_packing() {
162 let top = IndexStack::MAX_CAPACITY - 1;
163 let tag = u64::MAX >> TOP_BITS;
164 assert_eq!(unpack(pack(tag, top + 1)), (tag, top + 1));
165 assert_eq!(unpack(pack(3, 0)), (3, 0));
166 assert_eq!(unpack(pack(tag.wrapping_add(1), 5)), (0, 5));
167 }
168
169 #[test]
172 #[cfg_attr(miri, ignore)]
173 fn test_stack_largest_capacity_holds_its_largest_value() {
174 let top = IndexStack::MAX_CAPACITY - 1;
175 let s = IndexStack::with_capacity(u32::MAX);
176 assert_eq!(s.capacity(), IndexStack::MAX_CAPACITY as usize);
177 assert_eq!(s.push(top + 1), Err(top + 1));
178 for _ in 0..3 {
179 s.push(top).unwrap();
180 s.push(0).unwrap();
181 assert_eq!(s.pop(), Some(0));
182 assert_eq!(s.pop(), Some(top));
183 assert_eq!(s.pop(), None);
184 }
185 }
186
187 #[test]
190 fn test_stack_concurrent_values_are_never_shared_or_lost() {
191 const N: u32 = 64;
192 let s = Arc::new(IndexStack::with_capacity(N));
193 for i in 0..N {
194 s.push(i).unwrap();
195 }
196 let held: Arc<Vec<AtomicU32>> = Arc::new((0..N).map(|_| AtomicU32::new(0)).collect());
197 let threads: Vec<_> = (0..8)
198 .map(|_| {
199 let (s, held) = (Arc::clone(&s), Arc::clone(&held));
200 std::thread::spawn(move || {
201 for _ in 0..if cfg!(miri) { 50 } else { 20_000 } {
202 if let Some(v) = s.pop() {
203 let was = held[v as usize].fetch_add(1, Ordering::AcqRel);
204 assert_eq!(was, 0, "value {v} handed out twice");
205 let _released = held[v as usize].fetch_sub(1, Ordering::AcqRel);
206 s.push(v).unwrap();
207 }
208 }
209 })
210 })
211 .collect();
212 for t in threads {
213 t.join().unwrap();
214 }
215 let mut all: Vec<u32> = std::iter::from_fn(|| s.pop()).collect();
216 all.sort_unstable();
217 assert_eq!(
218 all,
219 (0..N).collect::<Vec<_>>(),
220 "a value was lost or duplicated"
221 );
222 }
223}
224
225#[cfg(all(test, loom))]
226mod loom_tests {
227 use loom::sync::Arc;
228
229 use super::*;
230
231 #[test]
235 fn loom_a_stale_pop_never_hands_out_a_held_value() {
236 loom::model(|| {
237 let s = Arc::new(IndexStack::with_capacity(3));
238 for i in 0..3 {
239 s.push(i).unwrap();
240 }
241 let a = {
242 let s = Arc::clone(&s);
243 loom::thread::spawn(move || s.pop())
244 };
245 let b = {
246 let s = Arc::clone(&s);
247 loom::thread::spawn(move || {
248 let x = s.pop();
249 let y = s.pop();
250 if let Some(x) = x {
251 s.push(x).unwrap();
252 }
253 y
254 })
255 };
256 let got_a = a.join().unwrap();
257 let held_b = b.join().unwrap();
258 if let (Some(va), Some(vb)) = (got_a, held_b) {
259 assert_ne!(va, vb, "a value held by one thread was handed to another");
260 }
261 let mut rest: Vec<u32> = std::iter::from_fn(|| s.pop()).collect();
263 for held in [got_a, held_b].into_iter().flatten() {
264 assert!(!rest.contains(&held), "a held value is still on the stack");
265 }
266 rest.extend(got_a);
267 rest.extend(held_b);
268 rest.sort_unstable();
269 assert_eq!(rest, vec![0, 1, 2]);
270 });
271 }
272}