objects/store/pack/
pack_index.rs

1// SPDX-License-Identifier: Apache-2.0
2//! Pack index for fast object lookup within packfiles.
3
4use crate::store::{Result, pack::PackObjectId};
5
6pub(super) const INDEX_MAGIC: &[u8] = b"LMI\0";
7pub(super) const INDEX_VERSION: u32 = 2;
8const MIN_INDEX_ENTRY_LEN: usize = 17 + 8;
9
10/// Entry in the pack index.
11#[derive(Debug, Clone, Copy)]
12pub struct IndexEntry {
13    pub id: PackObjectId,
14    pub offset: u64,
15}
16
17/// Pack index for fast object lookup.
18#[derive(Debug)]
19pub struct PackIndex {
20    entries: Vec<IndexEntry>,
21}
22
23impl PackIndex {
24    /// Create a new empty index.
25    pub fn new() -> Self {
26        Self {
27            entries: Vec::new(),
28        }
29    }
30
31    /// Add an entry.
32    pub fn add(&mut self, id: PackObjectId, offset: u64) {
33        self.entries.push(IndexEntry { id, offset });
34    }
35
36    /// Sort entries by hash for binary search.
37    pub fn sort(&mut self) {
38        self.entries.sort_by_key(|e| e.id);
39    }
40
41    /// Find an entry by hash.
42    pub fn find(&self, id: &PackObjectId) -> Option<u64> {
43        self.entries
44            .binary_search_by_key(id, |e| e.id)
45            .ok()
46            .map(|idx| self.entries[idx].offset)
47    }
48
49    /// Serialize to bytes.
50    pub fn to_bytes(&self) -> Vec<u8> {
51        let mut result = Vec::new();
52        result.extend_from_slice(INDEX_MAGIC);
53        result.extend_from_slice(&INDEX_VERSION.to_be_bytes());
54        result.extend_from_slice(&(self.entries.len() as u64).to_be_bytes());
55        for entry in &self.entries {
56            entry.id.encode_tagged(&mut result);
57            result.extend_from_slice(&entry.offset.to_be_bytes());
58        }
59        result
60    }
61
62    /// Deserialize from bytes.
63    pub fn from_bytes(data: &[u8]) -> Result<Self> {
64        if data.len() < 16 {
65            return Err(crate::store::StoreError::InvalidObject(
66                "Index too short".to_string(),
67            ));
68        }
69        if &data[0..4] != INDEX_MAGIC {
70            return Err(crate::store::StoreError::InvalidObject(
71                "Invalid index magic".to_string(),
72            ));
73        }
74        let version = u32::from_be_bytes([data[4], data[5], data[6], data[7]]);
75        if version != INDEX_VERSION {
76            return Err(crate::store::StoreError::InvalidObject(format!(
77                "Unsupported index version: {}",
78                version
79            )));
80        }
81        let count = u64::from_be_bytes([
82            data[8], data[9], data[10], data[11], data[12], data[13], data[14], data[15],
83        ]);
84        let max_entries = ((data.len() - 16) / MIN_INDEX_ENTRY_LEN) as u64;
85        if count > max_entries {
86            return Err(crate::store::StoreError::InvalidObject(format!(
87                "Index entry count {} exceeds available data capacity {}",
88                count, max_entries
89            )));
90        }
91        let count = usize::try_from(count).map_err(|_| {
92            crate::store::StoreError::InvalidObject(
93                "Index entry count exceeds platform limits".to_string(),
94            )
95        })?;
96        let mut entries = Vec::with_capacity(count);
97        let mut pos = 16;
98        for _ in 0..count {
99            let (id, id_len) = PackObjectId::decode_tagged(&data[pos..])?;
100            pos += id_len;
101            if pos + 8 > data.len() {
102                return Err(crate::store::StoreError::InvalidObject(
103                    "Index data truncated".to_string(),
104                ));
105            }
106            let offset = u64::from_be_bytes(data[pos..pos + 8].try_into().map_err(|_| {
107                crate::store::StoreError::InvalidObject("Invalid offset length".to_string())
108            })?);
109            entries.push(IndexEntry { id, offset });
110            pos += 8;
111        }
112        Ok(Self { entries })
113    }
114}
115
116impl PackIndex {
117    /// Return all ids in this index.
118    pub fn ids(&self) -> Vec<PackObjectId> {
119        self.entries.iter().map(|e| e.id).collect()
120    }
121}
122
123impl Default for PackIndex {
124    fn default() -> Self {
125        Self::new()
126    }
127}
objects/store/pack/pack_index.rs

objects/store/pack/
pack_index.rs
