2022-08-24 17:09:13 +00:00
|
|
|
use core::mem::MaybeUninit;
|
2024-03-30 23:38:05 +00:00
|
|
|
use core::ptr;
|
2020-08-05 16:57:58 +00:00
|
|
|
|
2022-10-07 13:48:10 +00:00
|
|
|
use crate::sync::atomic::{AtomicUsize, Ordering};
|
|
|
|
use crate::sync::cell::UnsafeCell;
|
|
|
|
#[allow(unused_imports)]
|
|
|
|
use crate::sync::prelude::*;
|
2024-03-30 23:38:05 +00:00
|
|
|
use crate::{busy_wait, ForcePushError, PopError, PushError};
|
2020-08-05 16:57:58 +00:00
|
|
|
|
|
|
|
const LOCKED: usize = 1 << 0;
|
|
|
|
const PUSHED: usize = 1 << 1;
|
|
|
|
const CLOSED: usize = 1 << 2;
|
|
|
|
|
|
|
|
/// A single-element queue.
|
|
|
|
pub struct Single<T> {
|
|
|
|
state: AtomicUsize,
|
|
|
|
slot: UnsafeCell<MaybeUninit<T>>,
|
|
|
|
}
|
|
|
|
|
|
|
|
impl<T> Single<T> {
|
|
|
|
/// Creates a new single-element queue.
|
|
|
|
pub fn new() -> Single<T> {
|
|
|
|
Single {
|
|
|
|
state: AtomicUsize::new(0),
|
|
|
|
slot: UnsafeCell::new(MaybeUninit::uninit()),
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Attempts to push an item into the queue.
|
|
|
|
pub fn push(&self, value: T) -> Result<(), PushError<T>> {
|
|
|
|
// Lock and fill the slot.
|
|
|
|
let state = self
|
|
|
|
.state
|
2020-12-24 12:28:40 +00:00
|
|
|
.compare_exchange(0, LOCKED | PUSHED, Ordering::SeqCst, Ordering::SeqCst)
|
|
|
|
.unwrap_or_else(|x| x);
|
2020-08-05 16:57:58 +00:00
|
|
|
|
|
|
|
if state == 0 {
|
|
|
|
// Write the value and unlock.
|
2022-10-07 13:48:10 +00:00
|
|
|
self.slot.with_mut(|slot| unsafe {
|
|
|
|
slot.write(MaybeUninit::new(value));
|
|
|
|
});
|
2020-08-05 16:57:58 +00:00
|
|
|
self.state.fetch_and(!LOCKED, Ordering::Release);
|
|
|
|
Ok(())
|
|
|
|
} else if state & CLOSED != 0 {
|
|
|
|
Err(PushError::Closed(value))
|
|
|
|
} else {
|
|
|
|
Err(PushError::Full(value))
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2024-03-30 23:38:05 +00:00
|
|
|
/// Attempts to push an item into the queue, displacing another if necessary.
|
|
|
|
pub fn force_push(&self, value: T) -> Result<Option<T>, ForcePushError<T>> {
|
|
|
|
// Attempt to lock the slot.
|
|
|
|
let mut state = 0;
|
|
|
|
|
|
|
|
loop {
|
|
|
|
// Lock the slot.
|
|
|
|
let prev = self
|
|
|
|
.state
|
|
|
|
.compare_exchange(state, LOCKED | PUSHED, Ordering::SeqCst, Ordering::SeqCst)
|
|
|
|
.unwrap_or_else(|x| x);
|
|
|
|
|
|
|
|
if prev & CLOSED != 0 {
|
|
|
|
return Err(ForcePushError(value));
|
|
|
|
}
|
|
|
|
|
|
|
|
if prev == state {
|
2024-04-26 05:53:55 +00:00
|
|
|
// If the value was pushed, swap out the value.
|
2024-03-30 23:38:05 +00:00
|
|
|
let prev_value = if prev & PUSHED == 0 {
|
2024-04-26 05:53:55 +00:00
|
|
|
// SAFETY: write is safe because we have locked the state.
|
|
|
|
self.slot.with_mut(|slot| unsafe {
|
|
|
|
slot.write(MaybeUninit::new(value));
|
|
|
|
});
|
2024-03-30 23:38:05 +00:00
|
|
|
None
|
|
|
|
} else {
|
2024-04-26 05:53:55 +00:00
|
|
|
// SAFETY: replace is safe because we have locked the state, and
|
|
|
|
// assume_init is safe because we have checked that the value was pushed.
|
|
|
|
let prev_value = unsafe {
|
|
|
|
self.slot.with_mut(move |slot| {
|
|
|
|
ptr::replace(slot, MaybeUninit::new(value)).assume_init()
|
|
|
|
})
|
|
|
|
};
|
|
|
|
Some(prev_value)
|
2024-03-30 23:38:05 +00:00
|
|
|
};
|
|
|
|
|
2024-04-26 05:53:55 +00:00
|
|
|
// We can unlock the slot now.
|
|
|
|
self.state.fetch_and(!LOCKED, Ordering::Release);
|
|
|
|
|
2024-03-30 23:38:05 +00:00
|
|
|
// Return the old value.
|
|
|
|
return Ok(prev_value);
|
|
|
|
}
|
|
|
|
|
|
|
|
// Try to go for the current (pushed) state.
|
|
|
|
if prev & LOCKED == 0 {
|
|
|
|
state = prev;
|
|
|
|
} else {
|
|
|
|
// State is locked.
|
|
|
|
busy_wait();
|
|
|
|
state = prev & !LOCKED;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
2020-08-05 16:57:58 +00:00
|
|
|
/// Attempts to pop an item from the queue.
|
|
|
|
pub fn pop(&self) -> Result<T, PopError> {
|
|
|
|
let mut state = PUSHED;
|
|
|
|
loop {
|
|
|
|
// Lock and empty the slot.
|
2020-12-24 12:28:40 +00:00
|
|
|
let prev = self
|
|
|
|
.state
|
|
|
|
.compare_exchange(
|
|
|
|
state,
|
|
|
|
(state | LOCKED) & !PUSHED,
|
|
|
|
Ordering::SeqCst,
|
|
|
|
Ordering::SeqCst,
|
|
|
|
)
|
|
|
|
.unwrap_or_else(|x| x);
|
2020-08-05 16:57:58 +00:00
|
|
|
|
|
|
|
if prev == state {
|
|
|
|
// Read the value and unlock.
|
2022-10-07 13:48:10 +00:00
|
|
|
let value = self
|
|
|
|
.slot
|
|
|
|
.with_mut(|slot| unsafe { slot.read().assume_init() });
|
2020-08-05 16:57:58 +00:00
|
|
|
self.state.fetch_and(!LOCKED, Ordering::Release);
|
|
|
|
return Ok(value);
|
|
|
|
}
|
|
|
|
|
|
|
|
if prev & PUSHED == 0 {
|
|
|
|
if prev & CLOSED == 0 {
|
|
|
|
return Err(PopError::Empty);
|
|
|
|
} else {
|
|
|
|
return Err(PopError::Closed);
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
if prev & LOCKED == 0 {
|
|
|
|
state = prev;
|
|
|
|
} else {
|
2022-08-24 17:09:13 +00:00
|
|
|
busy_wait();
|
2020-08-05 16:57:58 +00:00
|
|
|
state = prev & !LOCKED;
|
|
|
|
}
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns the number of items in the queue.
|
|
|
|
pub fn len(&self) -> usize {
|
2022-12-16 12:08:10 +00:00
|
|
|
usize::from(self.state.load(Ordering::SeqCst) & PUSHED != 0)
|
2020-08-05 16:57:58 +00:00
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns `true` if the queue is empty.
|
|
|
|
pub fn is_empty(&self) -> bool {
|
|
|
|
self.len() == 0
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns `true` if the queue is full.
|
|
|
|
pub fn is_full(&self) -> bool {
|
|
|
|
self.len() == 1
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Closes the queue.
|
|
|
|
///
|
|
|
|
/// Returns `true` if this call closed the queue.
|
|
|
|
pub fn close(&self) -> bool {
|
|
|
|
let state = self.state.fetch_or(CLOSED, Ordering::SeqCst);
|
|
|
|
state & CLOSED == 0
|
|
|
|
}
|
|
|
|
|
|
|
|
/// Returns `true` if the queue is closed.
|
|
|
|
pub fn is_closed(&self) -> bool {
|
|
|
|
self.state.load(Ordering::SeqCst) & CLOSED != 0
|
|
|
|
}
|
|
|
|
}
|
|
|
|
|
|
|
|
impl<T> Drop for Single<T> {
|
|
|
|
fn drop(&mut self) {
|
|
|
|
// Drop the value in the slot.
|
2022-10-07 13:48:10 +00:00
|
|
|
let Self { state, slot } = self;
|
|
|
|
state.with_mut(|state| {
|
|
|
|
if *state & PUSHED != 0 {
|
|
|
|
slot.with_mut(|slot| unsafe {
|
|
|
|
let value = &mut *slot;
|
|
|
|
value.as_mut_ptr().drop_in_place();
|
|
|
|
});
|
2022-07-21 14:58:22 +00:00
|
|
|
}
|
2022-10-07 13:48:10 +00:00
|
|
|
});
|
2020-08-05 16:57:58 +00:00
|
|
|
}
|
|
|
|
}
|