qualia_core_db/bundle/stream/index/
admit.rs1use super::cbor::{checked, decode_row};
3use super::{CheckedHeader, EntryIter, EntryView, IndexError, IndexReadLimits};
4use crate::bundle::BundleEntry;
5use minicbor::Decoder;
6
7#[derive(Clone, Copy, Debug)]
8pub struct EntryScratch<'a> {
9 key: &'a str,
10 offset: u64,
11 end: u64,
12 length: u64,
13}
14impl EntryScratch<'_> {
15 pub const EMPTY: Self = Self {
16 key: "",
17 offset: 0,
18 end: 0,
19 length: 0,
20 };
21}
22
23#[derive(Clone, Copy, Debug, PartialEq, Eq)]
24pub struct IndexSizing {
25 entry_count: usize,
26 retained_bytes: usize,
27 scratch_bytes: usize,
28 aggregate_bytes: usize,
29}
30impl IndexSizing {
31 pub const fn entry_count(self) -> usize {
32 self.entry_count
33 }
34 pub const fn retained_bytes(self) -> usize {
35 self.retained_bytes
36 }
37 pub const fn scratch_bytes(self) -> usize {
38 self.scratch_bytes
39 }
40 pub const fn aggregate_bytes(self) -> usize {
41 self.aggregate_bytes
42 }
43}
44
45#[derive(Debug)]
47pub struct AdmittedIndex<'a> {
48 header: CheckedHeader,
49 bytes: &'a [u8],
50 sizing: IndexSizing,
51 limits: IndexReadLimits,
52}
53impl<'a> AdmittedIndex<'a> {
54 pub const fn header(&self) -> CheckedHeader {
55 self.header
56 }
57 pub const fn encoded_bytes(&self) -> &'a [u8] {
58 self.bytes
59 }
60 pub const fn sizing(&self) -> IndexSizing {
61 self.sizing
62 }
63 pub fn entries(&self) -> EntryIter<'a> {
64 EntryIter::new(self.bytes, self.sizing.entry_count, self.limits)
65 }
66}
67
68fn scan<'a>(
69 h: &CheckedHeader,
70 bytes: &'a [u8],
71 l: IndexReadLimits,
72 mut visit: impl FnMut(usize, EntryView<'a>, u64) -> Result<(), IndexError>,
73) -> Result<IndexSizing, IndexError> {
74 h.check_limits(l)?;
75 if u64::try_from(bytes.len()).map_err(|_| IndexError::Overflow)? != h.index_length() {
76 return Err(IndexError::Footer);
77 }
78 let mut d = Decoder::new(bytes);
79 let count = checked(d.array())?.ok_or(IndexError::Malformed)?;
80 if count != u64::from(h.entry_count()) {
81 return Err(IndexError::Count);
82 }
83 let count = usize::try_from(count).map_err(|_| IndexError::Overflow)?;
84 let scratch_bytes = count
85 .checked_mul(core::mem::size_of::<EntryScratch<'_>>())
86 .ok_or(IndexError::Overflow)?;
87 let mut retained_bytes = count
88 .checked_mul(core::mem::size_of::<BundleEntry>())
89 .ok_or(IndexError::Overflow)?;
90 let aggregate = |n: usize| {
91 n.checked_mul(4)
92 .and_then(|n| n.checked_add(scratch_bytes))
93 .ok_or(IndexError::Overflow)
94 };
95 if aggregate(retained_bytes)? > l.decoded_index_bytes {
96 return Err(IndexError::ResidentLimit);
97 }
98 for i in 0..count {
99 let row = decode_row(&mut d, l)?;
100 let end = row
101 .offset
102 .checked_add(row.length)
103 .ok_or(IndexError::Overflow)?;
104 if row.offset < 64 || end > h.index_offset() {
105 return Err(IndexError::EntryBounds);
106 }
107 if row.offset % h.alignment() != 0 {
108 return Err(IndexError::Alignment);
109 }
110 retained_bytes = retained_bytes
111 .checked_add(row.retained_bytes()?)
112 .ok_or(IndexError::Overflow)?;
113 if aggregate(retained_bytes)? > l.decoded_index_bytes {
114 return Err(IndexError::ResidentLimit);
115 }
116 visit(i, row, end)?;
117 }
118 if d.position() != bytes.len() {
119 return Err(IndexError::Malformed);
120 }
121 Ok(IndexSizing {
122 entry_count: count,
123 retained_bytes,
124 scratch_bytes,
125 aggregate_bytes: aggregate(retained_bytes)?,
126 })
127}
128
129pub fn measure_index(
130 h: &CheckedHeader,
131 bytes: &[u8],
132 l: IndexReadLimits,
133) -> Result<IndexSizing, IndexError> {
134 scan(h, bytes, l, |_, _, _| Ok(()))
135}
136
137pub fn admit_index<'a>(
138 h: &CheckedHeader,
139 bytes: &'a [u8],
140 l: IndexReadLimits,
141 scratch: &mut [EntryScratch<'a>],
142) -> Result<AdmittedIndex<'a>, IndexError> {
143 let count = usize::try_from(h.entry_count()).map_err(|_| IndexError::Overflow)?;
144 if scratch.len() < count {
145 return Err(IndexError::Scratch);
146 }
147 let sizing = scan(h, bytes, l, |i, row, end| {
148 scratch[i] = EntryScratch {
149 key: row.key,
150 offset: row.offset,
151 end,
152 length: row.length,
153 };
154 Ok(())
155 })?;
156 let rows = &mut scratch[..count];
157 rows.sort_unstable_by(|a, b| a.key.cmp(b.key));
158 if rows.windows(2).any(|p| p[0].key == p[1].key) {
159 return Err(IndexError::DuplicateKey);
160 }
161 rows.sort_unstable_by_key(|r| (r.offset, r.end));
162 let mut occupied_end = 64;
163 for row in rows {
164 if row.length == 0 {
166 continue;
167 }
168 if row.offset < occupied_end {
169 return Err(IndexError::Overlap);
170 }
171 occupied_end = row.end;
172 }
173 Ok(AdmittedIndex {
174 header: *h,
175 bytes,
176 sizing,
177 limits: l,
178 })
179}