1 // Copyright 2013 The Rust Project Developers. See the COPYRIGHT
2 // file at the top-level directory of this distribution and at
3 // http://rust-lang.org/COPYRIGHT.
5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
8 // option. This file may not be copied, modified, or distributed
9 // except according to those terms.
11 // ignore-emscripten no threads support
15 #![feature(sort_unstable)]
17 use std::__rand::{thread_rng, Rng};
19 use std::cmp::Ordering;
21 use std::sync::atomic::{ATOMIC_USIZE_INIT, AtomicUsize};
22 use std::sync::atomic::Ordering::Relaxed;
25 const MAX_LEN: usize = 80;
27 static DROP_COUNTS: [AtomicUsize; MAX_LEN] = [
28 // FIXME #5244: AtomicUsize is not Copy.
29 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
30 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
31 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
32 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
33 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
34 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
35 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
36 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
37 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
38 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
39 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
40 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
41 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
42 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
43 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
44 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
45 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
46 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
47 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
48 AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0), AtomicUsize::new(0),
51 static VERSIONS: AtomicUsize = ATOMIC_USIZE_INIT;
60 impl PartialEq for DropCounter {
61 fn eq(&self, other: &Self) -> bool {
62 self.partial_cmp(other) == Some(Ordering::Equal)
66 impl PartialOrd for DropCounter {
67 fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
68 self.version.set(self.version.get() + 1);
69 other.version.set(other.version.get() + 1);
70 VERSIONS.fetch_add(2, Relaxed);
71 self.x.partial_cmp(&other.x)
75 impl Ord for DropCounter {
76 fn cmp(&self, other: &Self) -> Ordering {
77 self.partial_cmp(other).unwrap()
81 impl Drop for DropCounter {
83 DROP_COUNTS[self.id].fetch_add(1, Relaxed);
84 VERSIONS.fetch_sub(self.version.get(), Relaxed);
89 ($input:ident, $func:ident) => {
90 let len = $input.len();
92 // Work out the total number of comparisons required to sort
94 let mut count = 0usize;
95 $input.to_owned().$func(|a, b| { count += 1; a.cmp(b) });
97 // ... and then panic on each and every single one.
98 for panic_countdown in 0..count {
99 // Refresh the counters.
100 VERSIONS.store(0, Relaxed);
102 DROP_COUNTS[i].store(0, Relaxed);
105 let v = $input.to_owned();
106 let _ = thread::spawn(move || {
108 let mut panic_countdown = panic_countdown;
110 if panic_countdown == 0 {
111 SILENCE_PANIC.with(|s| s.set(true));
114 panic_countdown -= 1;
119 // Check that the number of things dropped is exactly
120 // what we expect (i.e. the contents of `v`).
121 for (i, c) in DROP_COUNTS.iter().enumerate().take(len) {
122 let count = c.load(Relaxed);
124 "found drop count == {} for i == {}, len == {}",
128 // Check that the most recent versions of values were dropped.
129 assert_eq!(VERSIONS.load(Relaxed), 0);
134 thread_local!(static SILENCE_PANIC: Cell<bool> = Cell::new(false));
137 let prev = panic::take_hook();
138 panic::set_hook(Box::new(move |info| {
139 if !SILENCE_PANIC.with(|s| s.get()) {
144 let mut rng = thread_rng();
146 for len in (1..20).chain(70..MAX_LEN) {
147 for &modulus in &[5, 20, 50] {
148 for &has_runs in &[false, true] {
149 let mut input = (0..len)
152 x: rng.next_u32() % modulus,
154 version: Cell::new(0),
157 .collect::<Vec<_>>();
160 for c in &mut input {
165 let a = rng.gen::<usize>() % len;
166 let b = rng.gen::<usize>() % len;
168 input[a..b].reverse();
175 test!(input, sort_by);
176 test!(input, sort_unstable_by);