1 //! Miscellaneous utilities.
3 use std
::cell
::{Cell, UnsafeCell}
;
4 use std
::num
::Wrapping
;
5 use std
::ops
::{Deref, DerefMut}
;
6 use std
::sync
::atomic
::{AtomicBool, Ordering}
;
8 use std
::time
::{Duration, Instant}
;
10 use crossbeam_utils
::Backoff
;
12 /// Randomly shuffles a slice.
13 pub fn shuffle
<T
>(v
: &mut [T
]) {
20 static RNG
: Cell
<Wrapping
<u32>> = Cell
::new(Wrapping(1406868647));
23 let _
= RNG
.try_with(|rng
| {
25 // This is the 32-bit variant of Xorshift.
27 // Source: https://en.wikipedia.org/wiki/Xorshift
28 let mut x
= rng
.get();
37 // This is a fast alternative to `let j = x % n`.
39 // Author: Daniel Lemire
40 // Source: https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/
41 let j
= ((x
as u64).wrapping_mul(n
as u64) >> 32) as u32 as usize;
48 /// Sleeps until the deadline, or forever if the deadline isn't specified.
49 pub fn sleep_until(deadline
: Option
<Instant
>) {
52 None
=> thread
::sleep(Duration
::from_secs(1000)),
54 let now
= Instant
::now();
58 thread
::sleep(d
- now
);
64 /// A simple spinlock.
65 pub struct Spinlock
<T
> {
71 /// Returns a new spinlock initialized with `value`.
72 pub fn new(value
: T
) -> Spinlock
<T
> {
74 flag
: AtomicBool
::new(false),
75 value
: UnsafeCell
::new(value
),
79 /// Locks the spinlock.
80 pub fn lock(&self) -> SpinlockGuard
<'_
, T
> {
81 let backoff
= Backoff
::new();
82 while self.flag
.swap(true, Ordering
::Acquire
) {
85 SpinlockGuard { parent: self }
89 /// A guard holding a spinlock locked.
90 pub struct SpinlockGuard
<'a
, T
: 'a
> {
91 parent
: &'a Spinlock
<T
>,
94 impl<'a
, T
> Drop
for SpinlockGuard
<'a
, T
> {
96 self.parent
.flag
.store(false, Ordering
::Release
);
100 impl<'a
, T
> Deref
for SpinlockGuard
<'a
, T
> {
103 fn deref(&self) -> &T
{
104 unsafe { &*self.parent.value.get() }
108 impl<'a
, T
> DerefMut
for SpinlockGuard
<'a
, T
> {
109 fn deref_mut(&mut self) -> &mut T
{
110 unsafe { &mut *self.parent.value.get() }