gix_pack/index/
access.rs

1use std::{mem::size_of, ops::Range};
2
3use crate::{
4    data,
5    index::{self, EntryIndex, PrefixLookupResult, FAN_LEN},
6};
7
8const N32_SIZE: usize = size_of::<u32>();
9const N64_SIZE: usize = size_of::<u64>();
10const V1_HEADER_SIZE: usize = FAN_LEN * N32_SIZE;
11const V2_HEADER_SIZE: usize = N32_SIZE * 2 + FAN_LEN * N32_SIZE;
12const N32_HIGH_BIT: u32 = 1 << 31;
13
14/// Represents an entry within a pack index file, effectively mapping object [`IDs`][gix_hash::ObjectId] to pack data file locations.
15#[derive(PartialEq, Eq, Debug, Hash, Ord, PartialOrd, Clone)]
16#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
17pub struct Entry {
18    /// The ID of the object
19    pub oid: gix_hash::ObjectId,
20    /// The offset to the object's header in the pack data file
21    pub pack_offset: data::Offset,
22    /// The CRC32 hash over all bytes of the pack data entry.
23    ///
24    /// This can be useful for direct copies of pack data entries from one pack to another with insurance there was no bit rot.
25    /// _Note_: Only available in index version 2 or newer
26    pub crc32: Option<u32>,
27}
28
29/// Iteration and access
30impl index::File {
31    fn iter_v1(&self) -> impl Iterator<Item = Entry> + '_ {
32        match self.version {
33            index::Version::V1 => self.data[V1_HEADER_SIZE..]
34                .chunks_exact(N32_SIZE + self.hash_len)
35                .take(self.num_objects as usize)
36                .map(|c| {
37                    let (ofs, oid) = c.split_at(N32_SIZE);
38                    Entry {
39                        oid: gix_hash::ObjectId::from_bytes_or_panic(oid),
40                        pack_offset: u64::from(crate::read_u32(ofs)),
41                        crc32: None,
42                    }
43                }),
44            _ => panic!("Cannot use iter_v1() on index of type {:?}", self.version),
45        }
46    }
47
48    fn iter_v2(&self) -> impl Iterator<Item = Entry> + '_ {
49        let pack64_offset = self.offset_pack_offset64_v2();
50        let oids = self.data[V2_HEADER_SIZE..]
51            .chunks_exact(self.hash_len)
52            .take(self.num_objects as usize);
53        let crcs = self.data[self.offset_crc32_v2()..]
54            .chunks_exact(N32_SIZE)
55            .take(self.num_objects as usize);
56        let offsets = self.data[self.offset_pack_offset_v2()..]
57            .chunks_exact(N32_SIZE)
58            .take(self.num_objects as usize);
59        assert_eq!(oids.len(), crcs.len());
60        assert_eq!(crcs.len(), offsets.len());
61        match self.version {
62            index::Version::V2 => izip!(oids, crcs, offsets).map(move |(oid, crc32, ofs32)| Entry {
63                oid: gix_hash::ObjectId::from_bytes_or_panic(oid),
64                pack_offset: self.pack_offset_from_offset_v2(ofs32, pack64_offset),
65                crc32: Some(crate::read_u32(crc32)),
66            }),
67            _ => panic!("Cannot use iter_v2() on index of type {:?}", self.version),
68        }
69    }
70
71    /// Returns the object hash at the given index in our list of (sorted) sha1 hashes.
72    /// The index ranges from 0 to `self.num_objects()`
73    ///
74    /// # Panics
75    ///
76    /// If `index` is out of bounds.
77    pub fn oid_at_index(&self, index: EntryIndex) -> &gix_hash::oid {
78        let index = index as usize;
79        let start = match self.version {
80            index::Version::V2 => V2_HEADER_SIZE + index * self.hash_len,
81            index::Version::V1 => V1_HEADER_SIZE + index * (N32_SIZE + self.hash_len) + N32_SIZE,
82        };
83        gix_hash::oid::from_bytes_unchecked(&self.data[start..][..self.hash_len])
84    }
85
86    /// Returns the offset into our pack data file at which to start reading the object at `index`.
87    ///
88    /// # Panics
89    ///
90    /// If `index` is out of bounds.
91    pub fn pack_offset_at_index(&self, index: EntryIndex) -> data::Offset {
92        let index = index as usize;
93        match self.version {
94            index::Version::V2 => {
95                let start = self.offset_pack_offset_v2() + index * N32_SIZE;
96                self.pack_offset_from_offset_v2(&self.data[start..][..N32_SIZE], self.offset_pack_offset64_v2())
97            }
98            index::Version::V1 => {
99                let start = V1_HEADER_SIZE + index * (N32_SIZE + self.hash_len);
100                u64::from(crate::read_u32(&self.data[start..][..N32_SIZE]))
101            }
102        }
103    }
104
105    /// Returns the CRC32 of the object at the given `index`.
106    ///
107    /// _Note_: These are always present for index version 2 or higher.
108    /// # Panics
109    ///
110    /// If `index` is out of bounds.
111    pub fn crc32_at_index(&self, index: EntryIndex) -> Option<u32> {
112        let index = index as usize;
113        match self.version {
114            index::Version::V2 => {
115                let start = self.offset_crc32_v2() + index * N32_SIZE;
116                Some(crate::read_u32(&self.data[start..start + N32_SIZE]))
117            }
118            index::Version::V1 => None,
119        }
120    }
121
122    /// Returns the `index` of the given hash for use with the [`oid_at_index()`][index::File::oid_at_index()],
123    /// [`pack_offset_at_index()`][index::File::pack_offset_at_index()] or [`crc32_at_index()`][index::File::crc32_at_index()].
124    // NOTE: pretty much the same things as in `multi_index::File::lookup`, change things there
125    //       as well.
126    pub fn lookup(&self, id: impl AsRef<gix_hash::oid>) -> Option<EntryIndex> {
127        lookup(id.as_ref(), &self.fan, &|idx| self.oid_at_index(idx))
128    }
129
130    /// Given a `prefix`, find an object that matches it uniquely within this index and return `Some(Ok(entry_index))`.
131    /// If there is more than one object matching the object `Some(Err(())` is returned.
132    ///
133    /// Finally, if no object matches the index, the return value is `None`.
134    ///
135    /// Pass `candidates` to obtain the set of entry-indices matching `prefix`, with the same return value as
136    /// one would have received if it remained `None`. It will be empty if no object matched the `prefix`.
137    ///
138    // NOTE: pretty much the same things as in `index::File::lookup`, change things there
139    //       as well.
140    pub fn lookup_prefix(
141        &self,
142        prefix: gix_hash::Prefix,
143        candidates: Option<&mut Range<EntryIndex>>,
144    ) -> Option<PrefixLookupResult> {
145        lookup_prefix(
146            prefix,
147            candidates,
148            &self.fan,
149            &|idx| self.oid_at_index(idx),
150            self.num_objects,
151        )
152    }
153
154    /// An iterator over all [`Entries`][Entry] of this index file.
155    pub fn iter<'a>(&'a self) -> Box<dyn Iterator<Item = Entry> + 'a> {
156        match self.version {
157            index::Version::V2 => Box::new(self.iter_v2()),
158            index::Version::V1 => Box::new(self.iter_v1()),
159        }
160    }
161
162    /// Return a vector of ascending offsets into our respective pack data file.
163    ///
164    /// Useful to control an iteration over all pack entries in a cache-friendly way.
165    pub fn sorted_offsets(&self) -> Vec<data::Offset> {
166        let mut ofs: Vec<_> = match self.version {
167            index::Version::V1 => self.iter().map(|e| e.pack_offset).collect(),
168            index::Version::V2 => {
169                let offset32_start = &self.data[self.offset_pack_offset_v2()..];
170                let offsets32 = offset32_start.chunks_exact(N32_SIZE).take(self.num_objects as usize);
171                assert_eq!(self.num_objects as usize, offsets32.len());
172                let pack_offset_64_start = self.offset_pack_offset64_v2();
173                offsets32
174                    .map(|offset| self.pack_offset_from_offset_v2(offset, pack_offset_64_start))
175                    .collect()
176            }
177        };
178        ofs.sort_unstable();
179        ofs
180    }
181
182    #[inline]
183    fn offset_crc32_v2(&self) -> usize {
184        V2_HEADER_SIZE + self.num_objects as usize * self.hash_len
185    }
186
187    #[inline]
188    fn offset_pack_offset_v2(&self) -> usize {
189        self.offset_crc32_v2() + self.num_objects as usize * N32_SIZE
190    }
191
192    #[inline]
193    fn offset_pack_offset64_v2(&self) -> usize {
194        self.offset_pack_offset_v2() + self.num_objects as usize * N32_SIZE
195    }
196
197    #[inline]
198    fn pack_offset_from_offset_v2(&self, offset: &[u8], pack64_offset: usize) -> data::Offset {
199        debug_assert_eq!(self.version, index::Version::V2);
200        let ofs32 = crate::read_u32(offset);
201        if (ofs32 & N32_HIGH_BIT) == N32_HIGH_BIT {
202            let from = pack64_offset + (ofs32 ^ N32_HIGH_BIT) as usize * N64_SIZE;
203            crate::read_u64(&self.data[from..][..N64_SIZE])
204        } else {
205            u64::from(ofs32)
206        }
207    }
208}
209
210pub(crate) fn lookup_prefix<'a>(
211    prefix: gix_hash::Prefix,
212    candidates: Option<&mut Range<EntryIndex>>,
213    fan: &[u32; FAN_LEN],
214    oid_at_index: &dyn Fn(EntryIndex) -> &'a gix_hash::oid,
215    num_objects: u32,
216) -> Option<PrefixLookupResult> {
217    let first_byte = prefix.as_oid().first_byte() as usize;
218    let mut upper_bound = fan[first_byte];
219    let mut lower_bound = if first_byte != 0 { fan[first_byte - 1] } else { 0 };
220
221    // Bisect using indices
222    while lower_bound < upper_bound {
223        let mid = (lower_bound + upper_bound) / 2;
224        let mid_sha = oid_at_index(mid);
225
226        use std::cmp::Ordering::*;
227        match prefix.cmp_oid(mid_sha) {
228            Less => upper_bound = mid,
229            Equal => match candidates {
230                Some(candidates) => {
231                    let first_past_entry = ((0..mid).rev())
232                        .take_while(|prev| prefix.cmp_oid(oid_at_index(*prev)) == Equal)
233                        .last();
234
235                    let last_future_entry = ((mid + 1)..num_objects)
236                        .take_while(|next| prefix.cmp_oid(oid_at_index(*next)) == Equal)
237                        .last();
238
239                    *candidates = match (first_past_entry, last_future_entry) {
240                        (Some(first), Some(last)) => first..last + 1,
241                        (Some(first), None) => first..mid + 1,
242                        (None, Some(last)) => mid..last + 1,
243                        (None, None) => mid..mid + 1,
244                    };
245
246                    return if candidates.len() > 1 {
247                        Some(Err(()))
248                    } else {
249                        Some(Ok(mid))
250                    };
251                }
252                None => {
253                    let next = mid + 1;
254                    if next < num_objects && prefix.cmp_oid(oid_at_index(next)) == Equal {
255                        return Some(Err(()));
256                    }
257                    if mid != 0 && prefix.cmp_oid(oid_at_index(mid - 1)) == Equal {
258                        return Some(Err(()));
259                    }
260                    return Some(Ok(mid));
261                }
262            },
263            Greater => lower_bound = mid + 1,
264        }
265    }
266
267    if let Some(candidates) = candidates {
268        *candidates = 0..0;
269    }
270    None
271}
272
273pub(crate) fn lookup<'a>(
274    id: &gix_hash::oid,
275    fan: &[u32; FAN_LEN],
276    oid_at_index: &dyn Fn(EntryIndex) -> &'a gix_hash::oid,
277) -> Option<EntryIndex> {
278    let first_byte = id.first_byte() as usize;
279    let mut upper_bound = fan[first_byte];
280    let mut lower_bound = if first_byte != 0 { fan[first_byte - 1] } else { 0 };
281
282    while lower_bound < upper_bound {
283        let mid = (lower_bound + upper_bound) / 2;
284        let mid_sha = oid_at_index(mid);
285
286        use std::cmp::Ordering::*;
287        match id.cmp(mid_sha) {
288            Less => upper_bound = mid,
289            Equal => return Some(mid),
290            Greater => lower_bound = mid + 1,
291        }
292    }
293    None
294}
gix_pack/index/access.rs

gix_pack/index/
access.rs
