vendor/crossbeam-queue/tests/array_queue.rs

   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     })
 117     .unwrap();
 118     assert_eq!(q.len(), 0);
 119 }
 120
 121 #[test]
 122 fn spsc() {
 123     const COUNT: usize = 100_000;
 124
 125     let q = ArrayQueue::new(3);
 126
 127     scope(|scope| {
 128         scope.spawn(|_| {
 129             for i in 0..COUNT {
 130                 loop {
 131                     if let Ok(x) = q.pop() {
 132                         assert_eq!(x, i);
 133                         break;
 134                     }
 135                 }
 136             }
 137             assert!(q.pop().is_err());
 138         });
 139
 140         scope.spawn(|_| {
 141             for i in 0..COUNT {
 142                 while q.push(i).is_err() {}
 143             }
 144         });
 145     })
 146     .unwrap();
 147 }
 148
 149 #[test]
 150 fn mpmc() {
 151     const COUNT: usize = 25_000;
 152     const THREADS: usize = 4;
 153
 154     let q = ArrayQueue::<usize>::new(3);
 155     let v = (0..COUNT).map(|_| AtomicUsize::new(0)).collect::<Vec<_>>();
 156
 157     scope(|scope| {
 158         for _ in 0..THREADS {
 159             scope.spawn(|_| {
 160                 for _ in 0..COUNT {
 161                     let n = loop {
 162                         if let Ok(x) = q.pop() {
 163                             break x;
 164                         }
 165                     };
 166                     v[n].fetch_add(1, Ordering::SeqCst);
 167                 }
 168             });
 169         }
 170         for _ in 0..THREADS {
 171             scope.spawn(|_| {
 172                 for i in 0..COUNT {
 173                     while q.push(i).is_err() {}
 174                 }
 175             });
 176         }
 177     })
 178     .unwrap();
 179
 180     for c in v {
 181         assert_eq!(c.load(Ordering::SeqCst), THREADS);
 182     }
 183 }
 184
 185 #[test]
 186 fn drops() {
 187     const RUNS: usize = 100;
 188
 189     static DROPS: AtomicUsize = AtomicUsize::new(0);
 190
 191     #[derive(Debug, PartialEq)]
 192     struct DropCounter;
 193
 194     impl Drop for DropCounter {
 195         fn drop(&mut self) {
 196             DROPS.fetch_add(1, Ordering::SeqCst);
 197         }
 198     }
 199
 200     let mut rng = thread_rng();
 201
 202     for _ in 0..RUNS {
 203         let steps = rng.gen_range(0, 10_000);
 204         let additional = rng.gen_range(0, 50);
 205
 206         DROPS.store(0, Ordering::SeqCst);
 207         let q = ArrayQueue::new(50);
 208
 209         scope(|scope| {
 210             scope.spawn(|_| {
 211                 for _ in 0..steps {
 212                     while q.pop().is_err() {}
 213                 }
 214             });
 215
 216             scope.spawn(|_| {
 217                 for _ in 0..steps {
 218                     while q.push(DropCounter).is_err() {
 219                         DROPS.fetch_sub(1, Ordering::SeqCst);
 220                     }
 221                 }
 222             });
 223         })
 224         .unwrap();
 225
 226         for _ in 0..additional {
 227             q.push(DropCounter).unwrap();
 228         }
 229
 230         assert_eq!(DROPS.load(Ordering::SeqCst), steps);
 231         drop(q);
 232         assert_eq!(DROPS.load(Ordering::SeqCst), steps + additional);
 233     }
 234 }
 235
 236 #[test]
 237 fn linearizable() {
 238     const COUNT: usize = 25_000;
 239     const THREADS: usize = 4;
 240
 241     let q = ArrayQueue::new(THREADS);
 242
 243     scope(|scope| {
 244         for _ in 0..THREADS {
 245             scope.spawn(|_| {
 246                 for _ in 0..COUNT {
 247                     while q.push(0).is_err() {}
 248                     q.pop().unwrap();
 249                 }
 250             });
 251         }
 252     })
 253     .unwrap();
 254 }