con-art-rust 0.2.0

A Rust implementation of ART-OLC concurrent adaptive radix tree.
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133

const STACK_KEY_LEN: usize = 56;

/// A trait for Art-specific keys, don't use it unless you know what you are doing.
pub trait RawKey: Eq + PartialEq + Default + PartialOrd + Ord {
    fn len(&self) -> usize;

    fn as_bytes(&self) -> &[u8];

    fn key_from(tid: usize) -> Self;
}

pub struct GeneralKey {
    len: usize,
    stack_keys: [u8; STACK_KEY_LEN],
}

impl RawKey for GeneralKey {
    fn len(&self) -> usize {
        self.len as usize
    }

    fn key_from(tid: usize) -> GeneralKey {
        let mut stack_keys = [0; STACK_KEY_LEN];

        let swapped = std::intrinsics::bswap(tid);

        for (i, v) in swapped.to_le_bytes().iter().enumerate() {
            stack_keys[i] = *v;
        }

        GeneralKey {
            len: std::mem::size_of::<usize>(),
            stack_keys,
        }
    }

    fn as_bytes(&self) -> &[u8] {
        self.stack_keys[..self.len as usize].as_ref()
    }
}
impl Ord for GeneralKey {
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        for i in 0..std::cmp::min(self.len(), other.len()) {
            if self.as_bytes()[i] > other.as_bytes()[i] {
                return std::cmp::Ordering::Greater;
            } else if self.as_bytes()[i] < other.as_bytes()[i] {
                return std::cmp::Ordering::Less;
            }
        }
        if self.len() == other.len() {
            std::cmp::Ordering::Equal
        } else {
            std::cmp::Ordering::Less
        }
    }
}

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

impl PartialEq for GeneralKey {
    fn eq(&self, other: &Self) -> bool {
        if self.len != other.len {
            return false;
        }
        for (i, v) in self.as_bytes().iter().enumerate() {
            if other.as_bytes()[i] != *v {
                return false;
            }
        }
        true
    }
}

impl Eq for GeneralKey {}

impl Default for GeneralKey {
    fn default() -> Self {
        Self::new()
    }
}

impl GeneralKey {
    fn new() -> Self {
        GeneralKey {
            len: 0,
            stack_keys: [0; STACK_KEY_LEN],
        }
    }
}

#[derive(Default, PartialEq, Eq)]
#[repr(C)]
pub struct UsizeKey {
    val: usize,
}

impl Ord for UsizeKey {
    #[inline]
    fn cmp(&self, other: &Self) -> std::cmp::Ordering {
        let a = std::intrinsics::bswap(self.val);
        let b = std::intrinsics::bswap(other.val);
        a.cmp(&b)
    }
}

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

impl RawKey for UsizeKey {
    #[inline]
    fn len(&self) -> usize {
        8
    }

    #[inline]
    fn as_bytes(&self) -> &[u8] {
        unsafe { std::slice::from_raw_parts(&self.val as *const usize as *const u8, 8) }
    }

    fn key_from(tid: usize) -> Self {
        Self {
            val: std::intrinsics::bswap(tid),
        }
    }
}