]>
Commit | Line | Data |
---|---|---|
1b1a35ee XL |
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. | |
13 | pub fn shuffle<T>(v: &mut [T]) { | |
14 | let len = v.len(); | |
15 | if len <= 1 { | |
16 | return; | |
17 | } | |
18 | ||
19 | thread_local! { | |
5869c6ff | 20 | static RNG: Cell<Wrapping<u32>> = Cell::new(Wrapping(1_406_868_647)); |
1b1a35ee XL |
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. | |
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. | |
65 | pub struct Spinlock<T> { | |
66 | flag: AtomicBool, | |
67 | value: UnsafeCell<T>, | |
68 | } | |
69 | ||
70 | impl<T> Spinlock<T> { | |
71 | /// Returns a new spinlock initialized with `value`. | |
72 | pub fn new(value: T) -> Spinlock<T> { | |
73 | Spinlock { | |
74 | flag: AtomicBool::new(false), | |
75 | value: UnsafeCell::new(value), | |
76 | } | |
77 | } | |
78 | ||
79 | /// Locks the spinlock. | |
80 | pub fn lock(&self) -> SpinlockGuard<'_, T> { | |
81 | let backoff = Backoff::new(); | |
82 | while self.flag.swap(true, Ordering::Acquire) { | |
83 | backoff.snooze(); | |
84 | } | |
85 | SpinlockGuard { parent: self } | |
86 | } | |
87 | } | |
88 | ||
89 | /// A guard holding a spinlock locked. | |
5869c6ff | 90 | pub struct SpinlockGuard<'a, T> { |
1b1a35ee XL |
91 | parent: &'a Spinlock<T>, |
92 | } | |
93 | ||
5869c6ff | 94 | impl<T> Drop for SpinlockGuard<'_, T> { |
1b1a35ee XL |
95 | fn drop(&mut self) { |
96 | self.parent.flag.store(false, Ordering::Release); | |
97 | } | |
98 | } | |
99 | ||
5869c6ff | 100 | impl<T> Deref for SpinlockGuard<'_, T> { |
1b1a35ee XL |
101 | type Target = T; |
102 | ||
103 | fn deref(&self) -> &T { | |
104 | unsafe { &*self.parent.value.get() } | |
105 | } | |
106 | } | |
107 | ||
5869c6ff | 108 | impl<T> DerefMut for SpinlockGuard<'_, T> { |
1b1a35ee XL |
109 | fn deref_mut(&mut self) -> &mut T { |
110 | unsafe { &mut *self.parent.value.get() } | |
111 | } | |
112 | } |