1#![cfg_attr(not(any(test, feature = "std")), no_std)]
39#![warn(missing_docs)]
40
41use core::{fmt, mem::MaybeUninit};
42
43#[cfg(feature = "loom")]
47mod atom {
48 pub use loom::cell::UnsafeCell;
49 pub use loom::sync::atomic::{AtomicUsize, Ordering, fence};
50 pub type AtomicIndex = AtomicUsize;
51 pub type Index = usize;
52}
53
54#[cfg(not(feature = "loom"))]
55mod atom {
56 #![allow(unused_imports)]
57 pub use core::cell::UnsafeCell;
58 #[cfg(target_has_atomic = "64")]
59 pub use core::sync::atomic::AtomicU64;
60 pub use core::sync::atomic::{AtomicUsize, Ordering, fence};
61 #[cfg(target_has_atomic = "64")]
62 pub type AtomicIndex = AtomicU64;
63 #[cfg(target_has_atomic = "64")]
64 pub type Index = u64;
65 #[cfg(not(target_has_atomic = "64"))]
66 pub type AtomicIndex = AtomicUsize;
67 #[cfg(not(target_has_atomic = "64"))]
68 pub type Index = usize;
69}
70
71#[allow(unused_imports)]
72use atom::*;
73
74#[repr(align(64))]
80struct Padded<T>(T);
81
82struct Backoff {
85 spins: u32,
86}
87
88impl Backoff {
89 #[inline]
90 fn new() -> Self {
91 Self { spins: 0 }
92 }
93
94 #[inline]
95 fn spin(&mut self) {
96 #[cfg(feature = "std")]
97 if self.spins > 6 {
98 std::thread::yield_now();
99 return;
100 }
101 let n = 1u32 << self.spins.min(6);
102 for _ in 0..n {
103 core::hint::spin_loop();
104 }
105 if self.spins < 8 {
106 self.spins += 1;
107 }
108 }
109
110 #[inline]
111 fn snooze(&mut self) {
112 #[cfg(feature = "std")]
113 if self.spins > 8 {
114 std::thread::yield_now();
115 return;
116 }
117 let n = 1u32 << self.spins.min(8);
118 for _ in 0..n {
119 core::hint::spin_loop();
120 }
121 if self.spins < 10 {
122 self.spins += 1;
123 }
124 }
125}
126
127const fn one_lap_for(cap: Index) -> Index {
130 let need = cap + 1;
131 let mut lap: Index = 2;
132 while lap < need {
133 lap *= 2;
134 }
135 lap
136}
137
138struct Slot<T> {
144 #[cfg(not(feature = "loom"))]
146 stamp: UnsafeCell<AtomicIndex>,
147 #[cfg(feature = "loom")]
148 stamp: AtomicIndex,
149 value: UnsafeCell<MaybeUninit<T>>,
150}
151
152impl<T> Slot<T> {
153 #[cfg(not(feature = "loom"))]
154 #[inline]
157 pub(crate) fn write_value(&self, value: T) {
158 unsafe { self.value.get().write(MaybeUninit::new(value)) }
159 }
160
161 #[cfg(not(feature = "loom"))]
162 #[inline]
163 pub(crate) fn read_value(&self) -> T {
164 unsafe { self.value.get().read().assume_init() }
165 }
166
167 #[cfg(not(feature = "loom"))]
168 #[inline]
169 pub(crate) fn drop_value(&mut self) {
170 unsafe { self.value.get_mut().assume_init_drop() }
171 }
172
173 #[cfg(not(feature = "loom"))]
174 #[inline]
177 pub(crate) fn replace_value(&self, value: T) -> T {
178 unsafe {
179 let old = core::mem::replace(&mut *self.value.get(), MaybeUninit::new(value));
180 old.assume_init()
181 }
182 }
183
184 #[cfg(not(feature = "loom"))]
185 #[inline]
186 pub(crate) fn stamp_load(&self) -> Index {
187 unsafe { (*self.stamp.get()).load(Ordering::Acquire) }
188 }
189
190 #[cfg(not(feature = "loom"))]
191 #[inline]
192 pub(crate) fn stamp_store(&self, val: Index) {
193 unsafe { (*self.stamp.get()).store(val, Ordering::Release) }
194 }
195
196 #[cfg(feature = "loom")]
197 pub(crate) fn write_value(&self, value: T) {
198 self.value.with_mut(|p| unsafe {
201 let _ = (&mut *p).write(value);
202 })
203 }
204
205 #[cfg(feature = "loom")]
206 pub(crate) fn read_value(&self) -> T {
207 self.value
209 .with(|p| unsafe { core::ptr::read(p).assume_init() })
210 }
211
212 #[cfg(feature = "loom")]
213 pub(crate) fn drop_value(&mut self) {
214 self.value
215 .with_mut(|p| unsafe { (&mut *p).assume_init_drop() })
216 }
217
218 #[cfg(feature = "loom")]
219 pub(crate) fn replace_value(&self, value: T) -> T {
220 self.value.with_mut(|p| unsafe {
221 core::ptr::replace(&mut *p, MaybeUninit::new(value)).assume_init()
222 })
223 }
224
225 #[cfg(feature = "loom")]
226 pub(crate) fn stamp_load(&self) -> Index {
227 self.stamp.load(Ordering::Acquire)
228 }
229
230 #[cfg(feature = "loom")]
231 pub(crate) fn stamp_store(&self, val: Index) {
232 self.stamp.store(val, Ordering::Release)
233 }
234}
235
236pub struct Queue<T, const N: usize> {
260 head: Padded<AtomicIndex>,
261 tail: Padded<AtomicIndex>,
262 buffer: [MaybeUninit<Slot<T>>; N],
265 one_lap: Index,
266}
267
268unsafe impl<T: Send, const N: usize> Sync for Queue<T, N> {}
270unsafe impl<T: Send, const N: usize> Send for Queue<T, N> {}
271
272impl<T, const N: usize> Default for Queue<T, N> {
273 fn default() -> Self {
274 Self::new()
275 }
276}
277
278impl<T, const N: usize> Queue<T, N> {
279 #[cfg(not(feature = "loom"))]
285 pub const fn new() -> Self {
286 assert!(N > 0, "capacity must be non-zero");
287 assert!(N <= (isize::MAX as usize) / 2, "capacity is too large");
288
289 let mut buffer: [MaybeUninit<Slot<T>>; N] = unsafe { MaybeUninit::uninit().assume_init() };
290 let mut i = 0;
291 while i < N {
292 buffer[i] = MaybeUninit::new(Slot {
293 stamp: UnsafeCell::new(AtomicIndex::new(i as Index)),
294 value: UnsafeCell::new(MaybeUninit::uninit()),
295 });
296 i += 1;
297 }
298 Self {
299 head: Padded(AtomicIndex::new(0)),
300 tail: Padded(AtomicIndex::new(0)),
301 buffer,
302 one_lap: one_lap_for(N as Index),
303 }
304 }
305
306 #[cfg(feature = "loom")]
309 pub fn new() -> Self {
310 assert!(N > 0, "capacity must be non-zero");
311 assert!(N <= (isize::MAX as usize) / 2, "capacity is too large");
312
313 let mut buffer: [MaybeUninit<Slot<T>>; N] = unsafe { MaybeUninit::uninit().assume_init() };
314 let mut i = 0;
315 while i < N {
316 buffer[i] = MaybeUninit::new(Slot {
317 stamp: AtomicIndex::new(i as Index),
318 value: UnsafeCell::new(MaybeUninit::uninit()),
319 });
320 i += 1;
321 }
322 Self {
323 head: Padded(AtomicIndex::new(0)),
324 tail: Padded(AtomicIndex::new(0)),
325 buffer,
326 one_lap: one_lap_for(N as Index),
327 }
328 }
329
330 #[inline]
332 pub const fn capacity(&self) -> usize {
333 N
334 }
335
336 fn push_or_else<F>(&self, mut value: T, f: F) -> Result<(), T>
337 where
338 F: Fn(T, Index, Index, &Slot<T>) -> Result<T, T>,
339 {
340 let mut backoff = Backoff::new();
341 let mut tail = self.tail.0.load(Ordering::Relaxed);
342
343 loop {
344 let index = (tail & (self.one_lap - 1)) as usize;
345 let lap = tail & !(self.one_lap - 1);
346
347 let new_tail = if index + 1 < N {
348 tail + 1
349 } else {
350 lap.wrapping_add(self.one_lap)
351 };
352
353 let slot = unsafe { self.buffer.get_unchecked(index).assume_init_ref() };
355 let stamp = slot.stamp_load();
356
357 if tail == stamp {
358 match self.tail.0.compare_exchange_weak(
359 tail,
360 new_tail,
361 Ordering::SeqCst,
362 Ordering::Relaxed,
363 ) {
364 Ok(_) => {
365 slot.write_value(value);
367 slot.stamp_store(tail + 1);
368 return Ok(());
369 }
370 Err(t) => {
371 tail = t;
372 backoff.spin();
373 }
374 }
375 } else if stamp.wrapping_add(self.one_lap) == tail + 1 {
376 fence(Ordering::SeqCst);
377 value = f(value, tail, new_tail, slot)?;
378 backoff.spin();
379 tail = self.tail.0.load(Ordering::Relaxed);
380 } else {
381 backoff.snooze();
382 tail = self.tail.0.load(Ordering::Relaxed);
383 }
384 }
385 }
386
387 pub fn push(&self, value: T) -> Result<(), T> {
389 self.push_or_else(value, |v, tail, _, _| {
390 let head = self.head.0.load(Ordering::Relaxed);
391 if head.wrapping_add(self.one_lap) == tail {
392 Err(v)
393 } else {
394 Ok(v)
395 }
396 })
397 }
398
399 #[inline]
401 pub fn enqueue(&self, value: T) -> Result<(), T> {
402 self.push(value)
403 }
404
405 pub fn force_push(&self, value: T) -> Option<T> {
408 self.push_or_else(value, |v, tail, new_tail, slot| {
409 let head = tail.wrapping_sub(self.one_lap);
410 let new_head = new_tail.wrapping_sub(self.one_lap);
411
412 if self
413 .head
414 .0
415 .compare_exchange_weak(head, new_head, Ordering::SeqCst, Ordering::Relaxed)
416 .is_ok()
417 {
418 self.tail.0.store(new_tail, Ordering::SeqCst);
419 let old = slot.replace_value(v);
421 slot.stamp_store(tail + 1);
422 Err(old)
423 } else {
424 Ok(v)
425 }
426 })
427 .err()
428 }
429
430 pub fn pop(&self) -> Option<T> {
432 let mut backoff = Backoff::new();
433 let mut head = self.head.0.load(Ordering::Relaxed);
434
435 loop {
436 let index = (head & (self.one_lap - 1)) as usize;
437 let lap = head & !(self.one_lap - 1);
438
439 let slot = unsafe { self.buffer.get_unchecked(index).assume_init_ref() };
441 let stamp = slot.stamp_load();
442
443 if head + 1 == stamp {
444 let new = if index + 1 < N {
445 head + 1
446 } else {
447 lap.wrapping_add(self.one_lap)
448 };
449
450 match self.head.0.compare_exchange_weak(
451 head,
452 new,
453 Ordering::SeqCst,
454 Ordering::Relaxed,
455 ) {
456 Ok(_) => {
457 let msg = slot.read_value();
458 slot.stamp_store(head.wrapping_add(self.one_lap));
459 return Some(msg);
460 }
461 Err(h) => {
462 head = h;
463 backoff.spin();
464 }
465 }
466 } else if stamp == head {
467 fence(Ordering::SeqCst);
468 let tail = self.tail.0.load(Ordering::Relaxed);
469 if tail == head {
470 return None;
471 }
472 backoff.spin();
473 head = self.head.0.load(Ordering::Relaxed);
474 } else {
475 backoff.snooze();
476 head = self.head.0.load(Ordering::Relaxed);
477 }
478 }
479 }
480
481 #[inline]
483 pub fn dequeue(&self) -> Option<T> {
484 self.pop()
485 }
486
487 pub fn is_empty(&self) -> bool {
489 let head = self.head.0.load(Ordering::SeqCst);
490 let tail = self.tail.0.load(Ordering::SeqCst);
491 tail == head
492 }
493
494 pub fn is_full(&self) -> bool {
496 let tail = self.tail.0.load(Ordering::SeqCst);
497 let head = self.head.0.load(Ordering::SeqCst);
498 head.wrapping_add(self.one_lap) == tail
499 }
500
501 pub fn len(&self) -> usize {
503 loop {
504 let tail = self.tail.0.load(Ordering::SeqCst);
505 let head = self.head.0.load(Ordering::SeqCst);
506
507 if self.tail.0.load(Ordering::SeqCst) == tail {
508 let hix = (head & (self.one_lap - 1)) as usize;
509 let tix = (tail & (self.one_lap - 1)) as usize;
510
511 return if hix < tix {
512 tix - hix
513 } else if hix > tix {
514 N - hix + tix
515 } else if tail == head {
516 0
517 } else {
518 N
519 };
520 }
521 }
522 }
523}
524
525impl<T, const N: usize> Drop for Queue<T, N> {
526 fn drop(&mut self) {
527 if core::mem::needs_drop::<T>() {
528 let head = self.head.0.load(Ordering::SeqCst);
531 let tail = self.tail.0.load(Ordering::SeqCst);
532
533 let hix = (head & (self.one_lap - 1)) as usize;
534 let tix = (tail & (self.one_lap - 1)) as usize;
535
536 let len = if hix < tix {
537 tix - hix
538 } else if hix > tix {
539 N - hix + tix
540 } else if tail == head {
541 0
542 } else {
543 N
544 };
545
546 for i in 0..len {
547 let index = if hix + i < N { hix + i } else { hix + i - N };
548 unsafe {
550 self.buffer
551 .get_unchecked_mut(index)
552 .assume_init_mut()
553 .drop_value();
554 }
555 }
556 }
557 }
558}
559
560impl<T, const N: usize> fmt::Debug for Queue<T, N> {
561 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
562 f.pad("Queue { .. }")
563 }
564}