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
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153

mod lru_cache;

pub use lru_cache::LRUCache;

use std::ptr::NonNull;

use anyhow::Result;

use crate::storage::mkvs::{
    cache::lru_cache::CacheItemBox,
    sync::{Proof, ReadSync},
    tree::{Depth, Key, NodeKind, NodePtrRef, NodeRef, Root, Value},
};

/// Statistics about the contents of the cache.
#[derive(Debug, Default)]
#[cfg(test)]
pub struct CacheStats {
    /// Count of internal nodes held by the cache.
    pub internal_node_count: usize,
    /// Total size of values held by the cache.
    pub leaf_value_size: usize,
}

/// Used to fetch proofs from a remote tree via the ReadSyncer interface.
pub trait ReadSyncFetcher {
    /// Fetch proof.
    fn fetch(&self, root: Root, ptr: NodePtrRef, rs: &mut Box<dyn ReadSync>) -> Result<Proof>;
}

impl<F> ReadSyncFetcher for F
where
    F: Fn(Root, NodePtrRef, &mut Box<dyn ReadSync>) -> Result<Proof>,
{
    fn fetch(&self, root: Root, ptr: NodePtrRef, rs: &mut Box<dyn ReadSync>) -> Result<Proof> {
        (*self)(root, ptr, rs)
    }
}

/// Cache interface for the in-mmory tree cache.
pub trait Cache {
    /// Return statistics about the contents of the cache.
    #[cfg(test)]
    fn stats(&self) -> CacheStats;

    /// Get a pointer to the current uncommitted root node.
    fn get_pending_root(&self) -> NodePtrRef;
    /// Set the root node for the tree to the given pointer.
    fn set_pending_root(&mut self, new_root: NodePtrRef);
    /// Set the root of the tree after committing.
    fn set_sync_root(&mut self, root: Root);

    /// Get the read syncer backing this cache.
    #[cfg(test)]
    fn get_read_syncer(&self) -> &Box<dyn ReadSync>;

    /// Create a new internal node and returns a pointer to it.
    fn new_internal_node(
        &mut self,
        label: &Key,
        label_bit_length: Depth,
        leaf_node: NodePtrRef,
        left: NodePtrRef,
        right: NodePtrRef,
    ) -> NodePtrRef;
    /// Create a new leaf node and returns a pointer to it.
    fn new_leaf_node(&mut self, key: &Key, value: Value) -> NodePtrRef;

    /// Try removing a node from the cache.
    fn remove_node(&mut self, ptr: NodePtrRef);

    /// Dereference a node pointer into a concrete node object.
    ///
    /// Calling this method may invoke the underlying read syncer.
    /// Giving a None fetcher forces the dereference to be local-only,
    /// without invoking the read syncer.
    fn deref_node_ptr<F: ReadSyncFetcher>(
        &mut self,
        ptr: NodePtrRef,
        fetcher: Option<F>,
    ) -> Result<Option<NodeRef>>;
    /// Perform a remote sync with the configured remote syncer.
    fn remote_sync<F: ReadSyncFetcher>(&mut self, ptr: NodePtrRef, fetcher: F) -> Result<()>;

    /// Mark that a tree node was just used.
    fn use_node(&mut self, ptr: NodePtrRef) -> bool;

    /// Commit a node into the cache.
    ///
    /// This method may evict some nodes in order to make space
    /// for the one being committed.
    fn commit_node(&mut self, ptr: NodePtrRef);

    // Mark a tree node as no longer being eligible for eviction
    // due to it becoming dirty.
    fn rollback_node(&mut self, ptr: NodePtrRef, kind: NodeKind);

    /// Mark the current LRU queue positions as the ones before any nodes are
    /// visited. Any new nodes committed into the cache after this is called
    /// will be inserted after the marked position.
    ///
    /// This makes it possible to keep the path from the root to the derefed
    /// node in the cache instead of evicting it.
    fn mark_position(&mut self);
}

/// Shorthand for the type that cacheable items must hold to aid caching.
pub type CacheExtra<T> = Option<NonNull<CacheItemBox<T>>>;

/// Cacheable objects must implement this trait to enable the cache to cache them.
pub trait CacheItem<Item = Self>
where
    Item: CacheItem + Default,
{
    /// Get the item's caching hint.
    ///
    /// For e.g. the LRU cache, this may be a used timestamp.
    fn get_cache_extra(&self) -> CacheExtra<Item>;
    /// Set the item's caching hint.
    fn set_cache_extra(&mut self, new_val: CacheExtra<Item>);
    /// Return the size, in bytes, of the item when cached.
    fn get_cached_size(&self) -> usize;
}

/// Callback type used for updating cache items after a commit.
pub type CacheUpdater<C> = Box<dyn Fn(&mut C)>;

/// A list of cache update callbacks.
pub struct UpdateList<C: Cache> {
    updates: Vec<CacheUpdater<C>>,
}

impl<C: Cache> UpdateList<C> {
    /// Construct a new UpdateList instance.
    pub fn new() -> UpdateList<C> {
        UpdateList {
            updates: Vec::new(),
        }
    }

    /// Push a new callback to the end of the list.
    pub fn push(&mut self, updater: CacheUpdater<C>) {
        self.updates.push(updater);
    }

    /// Commit the update list by calling all callbacks in order and destroying the list.
    pub fn commit(&mut self, cache: &mut C) {
        for update in &self.updates {
            (update)(cache);
        }
        self.updates.clear();
    }
}