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