bf-tree 0.5.0

Bf-Tree is a modern read-write-optimized concurrent larger-than-memory range index in Rust from Microsoft Research.
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

// Copyright (c) Microsoft Corporation.
// Licensed under the MIT license.

use crate::sync::atomic::Ordering;
use std::cell::UnsafeCell;

use crate::{error::TreeError, nodes::InnerNode};

pub(crate) fn is_locked(version: u16) -> bool {
    (version & 0b10) == 0b10
}

#[derive(Debug)]
pub(crate) struct ReadGuard<'a> {
    version: u16,
    node: &'a UnsafeCell<InnerNode>,
}

impl<'a> ReadGuard<'a> {
    pub(crate) fn new(v: u16, node: &'a InnerNode) -> Self {
        Self {
            version: v,
            node: unsafe { &*(node as *const InnerNode as *const UnsafeCell<InnerNode>) }, // todo: the caller should pass UnsafeCell<BaseNode> instead
        }
    }
    pub(crate) fn try_read(ptr: *const InnerNode) -> Result<ReadGuard<'a>, TreeError> {
        let node = unsafe { &*ptr };
        let v = node.version_lock.load(Ordering::Acquire);
        if is_locked(v) {
            Err(TreeError::Locked)
        } else {
            Ok(Self::new(v, node))
        }
    }

    pub(crate) fn check_version(&self) -> Result<u16, TreeError> {
        let v = self.as_ref().version_lock.load(Ordering::Acquire);

        if v == self.version {
            Ok(v)
        } else {
            Err(TreeError::Locked)
        }
    }

    pub(crate) fn as_ref(&self) -> &InnerNode {
        unsafe { &*self.node.get() }
    }

    pub(crate) fn upgrade(self) -> Result<WriteGuard<'a>, (Self, TreeError)> {
        let new_version = self.version + 0b10;
        match self.as_ref().version_lock.compare_exchange_weak(
            self.version,
            new_version,
            Ordering::Release,
            Ordering::Relaxed,
        ) {
            Ok(_) => Ok(WriteGuard { node: self.node }),
            Err(_v) => Err((self, TreeError::Locked)),
        }
    }
}

#[derive(Debug)]
pub struct WriteGuard<'a> {
    pub(crate) node: &'a UnsafeCell<InnerNode>,
}

impl<'a> WriteGuard<'a> {
    pub(crate) fn as_ref(&self) -> &'a InnerNode {
        unsafe { &*self.node.get() }
    }

    pub(crate) fn as_mut(&mut self) -> &'a mut InnerNode {
        unsafe { &mut *self.node.get() }
    }

    #[allow(dead_code)]
    pub(crate) fn mark_obsolete(&mut self) {
        self.as_mut()
            .version_lock
            .fetch_add(0b01, Ordering::Release);
    }

    pub(crate) fn downgrade(self) -> ReadGuard<'a> {
        let new_v = self
            .as_ref()
            .version_lock
            .fetch_add(0b10, Ordering::Release)
            + 0b10;
        let n = self.node.get();
        let rt = ReadGuard::new(new_v, unsafe { &*n });
        std::mem::forget(self);
        rt
    }
}

impl Drop for WriteGuard<'_> {
    fn drop(&mut self) {
        self.as_mut()
            .version_lock
            .fetch_add(0b10, Ordering::Release);
    }
}