logvec 1.1.1

A cache-friendly Bentley-Saxe logarithmic array data structure.
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46

#![allow(dead_code)]

#[derive(Clone, Eq, PartialEq)]
pub struct LargeStruct {
    pub key: u64,
    _padding: [u64; 32],
}

impl PartialOrd for LargeStruct {
    fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
        Some(self.cmp(other))
    }
}

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

impl LargeStruct {
    pub fn new(key: u64) -> Self {
        Self {
            key,
            _padding: [0; 32],
        }
    }
}

pub const N: usize = 10_000;

pub fn shuffled_keys(n: usize) -> Vec<u64> {
    let mut keys: Vec<u64> = (0..n as u64).collect();
    let mut seed = 0x9E37_79B9_7F4A_7C15u64;

    for i in (1..n).rev() {
        seed = seed
            .wrapping_mul(6364136223846793005)
            .wrapping_add(1442695040888963407);
        let j = (seed as usize) % (i + 1);
        keys.swap(i, j);
    }

    keys
}