google / crumsort-rs Goto Github PK

use std::collections::HashSet;
use std::sync::Mutex;

struct ObjStore {
    scratch_arena: Vec<String>,
    occupied_indices: Vec<ObjIndex>,
}

impl ObjStore {
    fn new(values: &[usize]) -> Self {
        // Ensure that there are no duplicate values.
        let values_check = HashSet::<usize>::from_iter(values.iter().copied());
        assert_eq!(values_check.len(), values.len());

        let max_value = (*values.iter().max().unwrap()) + 1;
        let mut scratch_arena: Vec<String> = Vec::with_capacity(max_value);

        let scratch_arena_ptr = scratch_arena.as_mut_ptr();
        for idx in values {
            // SAFETY: We made sure that scratch_arena is large enough so that
            // scratch_arena_ptr.add(*idx) is a valid pointer. And we made sure that idx only shows
            // up once.
            unsafe {
                scratch_arena_ptr.add(*idx).write(format!("{idx:010}"));
            }
        }

        Self {
            scratch_arena,
            occupied_indices: values.iter().map(|val| ObjIndex { val: *val }).collect(),
        }
    }
}

impl Drop for ObjStore {
    fn drop(&mut self) {
        let scratch_arena_ptr = self.scratch_arena.as_mut_ptr();
        for idx in &self.occupied_indices {
            // SAFETY: We made sure that scratch_arena is large enough and the ensured that
            // scratch_arena and occupied_indices stay in sync, so that
            // scratch_arena_ptr.add(idx.val) is a valid pointer. And we made sure that idx only
            // shows up once.
            unsafe {
                std::ptr::drop_in_place(scratch_arena_ptr.add(idx.val));
            }
        }
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Default)]
struct ObjIndex {
    val: usize,
}

static COMP_PANIC_TRIGGER_COUNT: Mutex<usize> = Mutex::new(0);
static COMP_COUNT: Mutex<usize> = Mutex::new(0);

impl PartialOrd for ObjIndex {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        // const COMP_PANIC_TRIGGER_COUNT: usize = 24;

        let mut comp_count_lock_guard = COMP_COUNT.lock().unwrap();
        if *comp_count_lock_guard == *COMP_PANIC_TRIGGER_COUNT.lock().unwrap() {
            drop(comp_count_lock_guard);
            panic!();
        }
        *comp_count_lock_guard += 1;

        self.val.partial_cmp(&other.val)
    }
}

impl Ord for ObjIndex {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        self.partial_cmp(other).unwrap()
    }
}

fn main() {
    *COMP_COUNT.lock().unwrap() = 0;
    *COMP_PANIC_TRIGGER_COUNT.lock().unwrap() = 14;

    let mut obj_store = ObjStore::new(&[218, 47, 7, 124, 163, 135, 222, 36, 31, 212]);

    // Duplicates elements -> UB
    crumsort::ParCrumSort::par_crumsort(obj_store.occupied_indices.as_mut_slice());

    // works
    // obj_store.occupied_indices.sort();
    // obj_store.occupied_indices.sort_unstable();
}

use std::cmp::Ordering;
use std::collections::HashSet;
use std::sync::Mutex;

struct ObjStore {
    scratch_arena: Vec<String>,
    occupied_indices: Vec<ObjIndex>,
}

impl ObjStore {
    fn new(values: &[usize]) -> Self {
        // Ensure that there are no duplicate values.
        let values_check = HashSet::<usize>::from_iter(values.iter().copied());
        assert_eq!(values_check.len(), values.len());

        let max_value = (*values.iter().max().unwrap()) + 1;
        let mut scratch_arena: Vec<String> = Vec::with_capacity(max_value);

        let scratch_arena_ptr = scratch_arena.as_mut_ptr();
        for idx in values {
            // SAFETY: We made sure that scratch_arena is large enough so that
            // scratch_arena_ptr.add(*idx) is a valid pointer.
            unsafe {
                scratch_arena_ptr.add(*idx).write(format!("{idx:010}"));
            }
        }

        Self {
            scratch_arena,
            occupied_indices: values.iter().map(|val| ObjIndex { val: *val }).collect(),
        }
    }
}

impl Drop for ObjStore {
    fn drop(&mut self) {
        let scratch_arena_ptr = self.scratch_arena.as_mut_ptr();
        for idx in &self.occupied_indices {
            // SAFETY: We made sure that scratch_arena is large enough and the ensured that
            // scratch_arena and occupied_indices stay in sync, so that
            // scratch_arena_ptr.add(idx.val) is a valid pointer.
            unsafe {
                std::ptr::drop_in_place(scratch_arena_ptr.add(idx.val));
            }
        }
    }
}

#[derive(Copy, Clone, PartialEq, Eq, Default)]
struct ObjIndex {
    val: usize,
}

const ORD_VALS: [Ordering; 8] = [
    Ordering::Less,
    Ordering::Equal,
    Ordering::Less,
    Ordering::Greater,
    Ordering::Greater,
    Ordering::Greater,
    Ordering::Less,
    Ordering::Equal,
];

static COMP_COUNT: Mutex<usize> = Mutex::new(0);

impl PartialOrd for ObjIndex {
    fn partial_cmp(&self, _other: &Self) -> Option<Ordering> {
        // A logically wrong Ord implementation that doesn't implement a total order is considered
        // safe code in Rust.

        // This is here to have something simple and deterministic, real code would be more complex.
        let comp_count = {
            let mut c = COMP_COUNT.lock().unwrap();
            let comp_count = *c;
            *c += 1;
            comp_count
        };

        Some(ORD_VALS[comp_count % ORD_VALS.len()])
    }
}

impl Ord for ObjIndex {
    fn cmp(&self, other: &Self) -> Ordering {
        self.partial_cmp(other).unwrap()
    }
}

fn main() {
    let mut obj_store = ObjStore::new(&[218, 47, 7, 124, 163, 135, 222, 36, 31, 212]);

    // Duplicates elements -> UB
    crumsort::ParCrumSort::par_crumsort(obj_store.occupied_indices.as_mut_slice());

    // works
    // obj_store.occupied_indices.sort();
    // obj_store.occupied_indices.sort_unstable();
}