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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

use logvec::LogVec;
use std::hint::black_box;

#[derive(Clone, Eq, PartialEq, Ord, PartialOrd)]
pub struct LargeKey {
    key: u64,
    _padding: [u64; 8],
}

impl LargeKey {
    fn new(key: u64) -> Self {
        Self {
            key,
            _padding: [0; 8],
        }
    }
}

#[inline(never)]
pub fn insert_u64_seq(n: u64) -> LogVec<u64> {
    let mut arr = LogVec::new();
    for i in 0..n {
        arr.insert(black_box(i));
    }
    arr
}

#[inline(never)]
pub fn insert_u128_seq(n: u64) -> LogVec<u128> {
    let mut arr = LogVec::new();
    for i in 0..n {
        arr.insert(black_box(i as u128));
    }
    arr
}

#[inline(never)]
pub fn insert_large_seq(n: u64) -> LogVec<LargeKey> {
    let mut arr = LogVec::new();
    for i in 0..n {
        arr.insert(black_box(LargeKey::new(i)));
    }
    arr
}

#[inline(never)]
pub fn contains_u64(arr: &LogVec<u64>, q: u64) -> bool {
    black_box(arr.contains(black_box(&q)))
}

#[inline(never)]
pub fn contains_u128(arr: &LogVec<u128>, q: u128) -> bool {
    black_box(arr.contains(black_box(&q)))
}

fn main() {
    let arr_u64 = insert_u64_seq(black_box(1024));
    let _ = black_box(contains_u64(&arr_u64, black_box(777)));

    let arr_u128 = insert_u128_seq(black_box(1024));
    let _ = black_box(contains_u128(&arr_u128, black_box(777)));

    let _ = black_box(insert_large_seq(black_box(256)));
}