]>
Commit | Line | Data |
---|---|---|
f035d41b XL |
1 | extern crate crossbeam_queue; |
2 | extern crate crossbeam_utils; | |
3 | extern crate rand; | |
4 | ||
5 | use std::sync::atomic::{AtomicUsize, Ordering}; | |
6 | ||
7 | use crossbeam_queue::ArrayQueue; | |
8 | use crossbeam_utils::thread::scope; | |
9 | use rand::{thread_rng, Rng}; | |
10 | ||
11 | #[test] | |
12 | fn smoke() { | |
13 | let q = ArrayQueue::new(1); | |
14 | ||
15 | q.push(7).unwrap(); | |
16 | assert_eq!(q.pop(), Ok(7)); | |
17 | ||
18 | q.push(8).unwrap(); | |
19 | assert_eq!(q.pop(), Ok(8)); | |
20 | assert!(q.pop().is_err()); | |
21 | } | |
22 | ||
23 | #[test] | |
24 | fn capacity() { | |
25 | for i in 1..10 { | |
26 | let q = ArrayQueue::<i32>::new(i); | |
27 | assert_eq!(q.capacity(), i); | |
28 | } | |
29 | } | |
30 | ||
31 | #[test] | |
32 | #[should_panic(expected = "capacity must be non-zero")] | |
33 | fn zero_capacity() { | |
34 | let _ = ArrayQueue::<i32>::new(0); | |
35 | } | |
36 | ||
37 | #[test] | |
38 | fn len_empty_full() { | |
39 | let q = ArrayQueue::new(2); | |
40 | ||
41 | assert_eq!(q.len(), 0); | |
42 | assert_eq!(q.is_empty(), true); | |
43 | assert_eq!(q.is_full(), false); | |
44 | ||
45 | q.push(()).unwrap(); | |
46 | ||
47 | assert_eq!(q.len(), 1); | |
48 | assert_eq!(q.is_empty(), false); | |
49 | assert_eq!(q.is_full(), false); | |
50 | ||
51 | q.push(()).unwrap(); | |
52 | ||
53 | assert_eq!(q.len(), 2); | |
54 | assert_eq!(q.is_empty(), false); | |
55 | assert_eq!(q.is_full(), true); | |
56 | ||
57 | q.pop().unwrap(); | |
58 | ||
59 | assert_eq!(q.len(), 1); | |
60 | assert_eq!(q.is_empty(), false); | |
61 | assert_eq!(q.is_full(), false); | |
62 | } | |
63 | ||
64 | #[test] | |
65 | fn len() { | |
66 | const COUNT: usize = 25_000; | |
67 | const CAP: usize = 1000; | |
68 | ||
69 | let q = ArrayQueue::new(CAP); | |
70 | assert_eq!(q.len(), 0); | |
71 | ||
72 | for _ in 0..CAP / 10 { | |
73 | for i in 0..50 { | |
74 | q.push(i).unwrap(); | |
75 | assert_eq!(q.len(), i + 1); | |
76 | } | |
77 | ||
78 | for i in 0..50 { | |
79 | q.pop().unwrap(); | |
80 | assert_eq!(q.len(), 50 - i - 1); | |
81 | } | |
82 | } | |
83 | assert_eq!(q.len(), 0); | |
84 | ||
85 | for i in 0..CAP { | |
86 | q.push(i).unwrap(); | |
87 | assert_eq!(q.len(), i + 1); | |
88 | } | |
89 | ||
90 | for _ in 0..CAP { | |
91 | q.pop().unwrap(); | |
92 | } | |
93 | assert_eq!(q.len(), 0); | |
94 | ||
95 | scope(|scope| { | |
96 | scope.spawn(|_| { | |
97 | for i in 0..COUNT { | |
98 | loop { | |
99 | if let Ok(x) = q.pop() { | |
100 | assert_eq!(x, i); | |
101 | break; | |
102 | } | |
103 | } | |
104 | let len = q.len(); | |
105 | assert!(len <= CAP); | |
106 | } | |
107 | }); | |
108 | ||
109 | scope.spawn(|_| { | |
110 | for i in 0..COUNT { | |
111 | while q.push(i).is_err() {} | |
112 | let len = q.len(); | |
113 | assert!(len <= CAP); | |
114 | } | |
115 | }); | |
116 | }).unwrap(); | |
117 | assert_eq!(q.len(), 0); | |
118 | } | |
119 | ||
120 | #[test] | |
121 | fn spsc() { | |
122 | const COUNT: usize = 100_000; | |
123 | ||
124 | let q = ArrayQueue::new(3); | |
125 | ||
126 | scope(|scope| { | |
127 | scope.spawn(|_| { | |
128 | for i in 0..COUNT { | |
129 | loop { | |
130 | if let Ok(x) = q.pop() { | |
131 | assert_eq!(x, i); | |
132 | break; | |
133 | } | |
134 | } | |
135 | } | |
136 | assert!(q.pop().is_err()); | |
137 | }); | |
138 | ||
139 | scope.spawn(|_| { | |
140 | for i in 0..COUNT { | |
141 | while q.push(i).is_err() {} | |
142 | } | |
143 | }); | |
144 | }).unwrap(); | |
145 | } | |
146 | ||
147 | #[test] | |
148 | fn mpmc() { | |
149 | const COUNT: usize = 25_000; | |
150 | const THREADS: usize = 4; | |
151 | ||
152 | let q = ArrayQueue::<usize>::new(3); | |
153 | let v = (0..COUNT).map(|_| AtomicUsize::new(0)).collect::<Vec<_>>(); | |
154 | ||
155 | scope(|scope| { | |
156 | for _ in 0..THREADS { | |
157 | scope.spawn(|_| { | |
158 | for _ in 0..COUNT { | |
159 | let n = loop { | |
160 | if let Ok(x) = q.pop() { | |
161 | break x; | |
162 | } | |
163 | }; | |
164 | v[n].fetch_add(1, Ordering::SeqCst); | |
165 | } | |
166 | }); | |
167 | } | |
168 | for _ in 0..THREADS { | |
169 | scope.spawn(|_| { | |
170 | for i in 0..COUNT { | |
171 | while q.push(i).is_err() {} | |
172 | } | |
173 | }); | |
174 | } | |
175 | }).unwrap(); | |
176 | ||
177 | for c in v { | |
178 | assert_eq!(c.load(Ordering::SeqCst), THREADS); | |
179 | } | |
180 | } | |
181 | ||
182 | #[test] | |
183 | fn drops() { | |
184 | const RUNS: usize = 100; | |
185 | ||
186 | static DROPS: AtomicUsize = AtomicUsize::new(0); | |
187 | ||
188 | #[derive(Debug, PartialEq)] | |
189 | struct DropCounter; | |
190 | ||
191 | impl Drop for DropCounter { | |
192 | fn drop(&mut self) { | |
193 | DROPS.fetch_add(1, Ordering::SeqCst); | |
194 | } | |
195 | } | |
196 | ||
197 | let mut rng = thread_rng(); | |
198 | ||
199 | for _ in 0..RUNS { | |
200 | let steps = rng.gen_range(0, 10_000); | |
201 | let additional = rng.gen_range(0, 50); | |
202 | ||
203 | DROPS.store(0, Ordering::SeqCst); | |
204 | let q = ArrayQueue::new(50); | |
205 | ||
206 | scope(|scope| { | |
207 | scope.spawn(|_| { | |
208 | for _ in 0..steps { | |
209 | while q.pop().is_err() {} | |
210 | } | |
211 | }); | |
212 | ||
213 | scope.spawn(|_| { | |
214 | for _ in 0..steps { | |
215 | while q.push(DropCounter).is_err() { | |
216 | DROPS.fetch_sub(1, Ordering::SeqCst); | |
217 | } | |
218 | } | |
219 | }); | |
220 | }).unwrap(); | |
221 | ||
222 | for _ in 0..additional { | |
223 | q.push(DropCounter).unwrap(); | |
224 | } | |
225 | ||
226 | assert_eq!(DROPS.load(Ordering::SeqCst), steps); | |
227 | drop(q); | |
228 | assert_eq!(DROPS.load(Ordering::SeqCst), steps + additional); | |
229 | } | |
230 | } | |
231 | ||
232 | #[test] | |
233 | fn linearizable() { | |
234 | const COUNT: usize = 25_000; | |
235 | const THREADS: usize = 4; | |
236 | ||
237 | let q = ArrayQueue::new(THREADS); | |
238 | ||
239 | scope(|scope| { | |
240 | for _ in 0..THREADS { | |
241 | scope.spawn(|_| { | |
242 | for _ in 0..COUNT { | |
243 | while q.push(0).is_err() {} | |
244 | q.pop().unwrap(); | |
245 | } | |
246 | }); | |
247 | } | |
248 | }).unwrap(); | |
249 | } |