1 //! Miscellaneous utilities.
2
3 use std::cell::{Cell, UnsafeCell};
4 use std::num::Wrapping;
5 use std::ops::{Deref, DerefMut};
6 use std::sync::atomic::{AtomicBool, Ordering};
7 use std::thread;
8 use std::time::{Duration, Instant};
9
10 use crossbeam_utils::Backoff;
11
12 /// Randomly shuffles a slice.
shuffle<T>(v: &mut [T])13 pub fn shuffle<T>(v: &mut [T]) {
14 let len = v.len();
15 if len <= 1 {
16 return;
17 }
18
19 thread_local! {
20 static RNG: Cell<Wrapping<u32>> = Cell::new(Wrapping(1406868647));
21 }
22
23 let _ = RNG.try_with(|rng| {
24 for i in 1..len {
25 // This is the 32-bit variant of Xorshift.
26 //
27 // Source: https://en.wikipedia.org/wiki/Xorshift
28 let mut x = rng.get();
29 x ^= x << 13;
30 x ^= x >> 17;
31 x ^= x << 5;
32 rng.set(x);
33
34 let x = x.0;
35 let n = i + 1;
36
37 // This is a fast alternative to `let j = x % n`.
38 //
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;
42
43 v.swap(i, j);
44 }
45 });
46 }
47
48 /// Sleeps until the deadline, or forever if the deadline isn't specified.
sleep_until(deadline: Option<Instant>)49 pub fn sleep_until(deadline: Option<Instant>) {
50 loop {
51 match deadline {
52 None => thread::sleep(Duration::from_secs(1000)),
53 Some(d) => {
54 let now = Instant::now();
55 if now >= d {
56 break;
57 }
58 thread::sleep(d - now);
59 }
60 }
61 }
62 }
63
64 /// A simple spinlock-based mutex.
65 pub struct Mutex<T> {
66 flag: AtomicBool,
67 value: UnsafeCell<T>,
68 }
69
70 impl<T> Mutex<T> {
71 /// Returns a new mutex initialized with `value`.
new(value: T) -> Mutex<T>72 pub fn new(value: T) -> Mutex<T> {
73 Mutex {
74 flag: AtomicBool::new(false),
75 value: UnsafeCell::new(value),
76 }
77 }
78
79 /// Locks the mutex.
lock(&self) -> MutexGuard<'_, T>80 pub fn lock(&self) -> MutexGuard<'_, T> {
81 let backoff = Backoff::new();
82 while self.flag.swap(true, Ordering::Acquire) {
83 backoff.snooze();
84 }
85 MutexGuard {
86 parent: self,
87 }
88 }
89 }
90
91 /// A guard holding a mutex locked.
92 pub struct MutexGuard<'a, T: 'a> {
93 parent: &'a Mutex<T>,
94 }
95
96 impl<'a, T> Drop for MutexGuard<'a, T> {
drop(&mut self)97 fn drop(&mut self) {
98 self.parent.flag.store(false, Ordering::Release);
99 }
100 }
101
102 impl<'a, T> Deref for MutexGuard<'a, T> {
103 type Target = T;
104
deref(&self) -> &T105 fn deref(&self) -> &T {
106 unsafe {
107 &*self.parent.value.get()
108 }
109 }
110 }
111
112 impl<'a, T> DerefMut for MutexGuard<'a, T> {
deref_mut(&mut self) -> &mut T113 fn deref_mut(&mut self) -> &mut T {
114 unsafe {
115 &mut *self.parent.value.get()
116 }
117 }
118 }
119