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