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

use std::ops::DerefMut;

use git_object::Kind;

/// A trait to model putting objects at a given pack `offset` into a cache, and fetching them.
///
/// It is used to speed up [pack traversals][crate::index::File::traverse()].
pub trait DecodeEntry {
    /// Store a fully decoded object at `offset` of `kind` with `compressed_size` and `data` in the cache.
    ///
    /// It is up to the cache implementation whether that actually happens or not.
    fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: git_object::Kind, compressed_size: usize);
    /// Attempt to fetch the object at `offset` and store its decoded bytes in `out`, as previously stored with [`DecodeEntry::put()`], and return
    /// its (object `kind`, `decompressed_size`)
    fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec<u8>) -> Option<(git_object::Kind, usize)>;
}

/// A cache that stores nothing and retrieves nothing, thus it _never_ caches.
#[derive(Default)]
pub struct Never;

impl DecodeEntry for Never {
    fn put(&mut self, _pack_id: u32, _offset: u64, _data: &[u8], _kind: git_object::Kind, _compressed_size: usize) {}
    fn get(&mut self, _pack_id: u32, _offset: u64, _out: &mut Vec<u8>) -> Option<(git_object::Kind, usize)> {
        None
    }
}

impl<T: DecodeEntry + ?Sized> DecodeEntry for Box<T> {
    fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: Kind, compressed_size: usize) {
        self.deref_mut().put(pack_id, offset, data, kind, compressed_size)
    }

    fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec<u8>) -> Option<(Kind, usize)> {
        self.deref_mut().get(pack_id, offset, out)
    }
}

/// Various implementations of [`DecodeEntry`] using least-recently-used algorithms.
#[cfg(any(feature = "pack-cache-lru-dynamic", feature = "pack-cache-lru-static"))]
pub mod lru {
    use super::DecodeEntry;

    #[cfg(feature = "pack-cache-lru-dynamic")]
    mod memory {
        use super::DecodeEntry;
        struct Entry {
            data: Vec<u8>,
            kind: git_object::Kind,
            compressed_size: usize,
        }

        impl memory_lru::ResidentSize for Entry {
            fn resident_size(&self) -> usize {
                self.data.len()
            }
        }

        /// An LRU cache with hash map backing and an eviction rule based on the memory usage for object data in bytes.
        pub struct MemoryCappedHashmap(memory_lru::MemoryLruCache<(u32, u64), Entry>);

        impl MemoryCappedHashmap {
            /// Return a new instance which evicts least recently used items if it uses more than `memory_cap_in_bytes`
            /// object data.
            pub fn new(memory_cap_in_bytes: usize) -> MemoryCappedHashmap {
                MemoryCappedHashmap(memory_lru::MemoryLruCache::new(memory_cap_in_bytes))
            }
        }

        impl DecodeEntry for MemoryCappedHashmap {
            fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: git_object::Kind, compressed_size: usize) {
                self.0.insert(
                    (pack_id, offset),
                    Entry {
                        data: Vec::from(data),
                        kind,
                        compressed_size,
                    },
                )
            }

            fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec<u8>) -> Option<(git_object::Kind, usize)> {
                self.0.get(&(pack_id, offset)).map(|e| {
                    out.resize(e.data.len(), 0);
                    out.copy_from_slice(&e.data);
                    (e.kind, e.compressed_size)
                })
            }
        }
    }
    #[cfg(feature = "pack-cache-lru-dynamic")]
    pub use memory::MemoryCappedHashmap;

    #[cfg(feature = "pack-cache-lru-static")]
    mod _static {
        use super::DecodeEntry;
        struct Entry {
            pack_id: u32,
            offset: u64,
            data: Vec<u8>,
            kind: git_object::Kind,
            compressed_size: usize,
        }

        /// A cache using a least-recently-used implementation capable of storing the `SIZE` most recent objects.
        /// The cache must be small as the search is 'naive' and the underlying data structure is a linked list.
        /// Values of 64 seem to improve performance.
        #[derive(Default)]
        pub struct StaticLinkedList<const SIZE: usize>(uluru::LRUCache<Entry, SIZE>);

        impl<const SIZE: usize> DecodeEntry for StaticLinkedList<SIZE> {
            fn put(&mut self, pack_id: u32, offset: u64, data: &[u8], kind: git_object::Kind, compressed_size: usize) {
                self.0.insert(Entry {
                    offset,
                    pack_id,
                    data: Vec::from(data),
                    kind,
                    compressed_size,
                })
            }

            fn get(&mut self, pack_id: u32, offset: u64, out: &mut Vec<u8>) -> Option<(git_object::Kind, usize)> {
                self.0.lookup(|e: &mut Entry| {
                    if e.pack_id == pack_id && e.offset == offset {
                        out.resize(e.data.len(), 0);
                        out.copy_from_slice(&e.data);
                        Some((e.kind, e.compressed_size))
                    } else {
                        None
                    }
                })
            }
        }
    }
    #[cfg(feature = "pack-cache-lru-static")]
    pub use _static::StaticLinkedList;
}