1use crate::errors::{ParquetError, Result};
12use crate::file::metadata::memory::HeapSize;
13use std::collections::HashMap;
14
15#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
16pub(crate) struct ColumnChunkKey(u64);
17
18impl ColumnChunkKey {
19 pub(crate) fn try_new(row_group_idx: usize, column_idx: usize) -> Result<Self> {
20 let row_group_idx = u32::try_from(row_group_idx).map_err(|_| {
21 ParquetError::General(format!(
22 "row group index exceeds packed coordinate limit: {row_group_idx}"
23 ))
24 })?;
25 let column_idx = u32::try_from(column_idx).map_err(|_| {
26 ParquetError::General(format!(
27 "column index exceeds packed coordinate limit: {column_idx}"
28 ))
29 })?;
30 Ok(Self(
31 (u64::from(row_group_idx) << u32::BITS) | u64::from(column_idx),
32 ))
33 }
34
35 pub(crate) fn coordinates(self) -> (usize, usize) {
36 ((self.0 >> u32::BITS) as usize, (self.0 as u32) as usize)
37 }
38}
39
40impl HeapSize for ColumnChunkKey {
41 fn heap_size(&self) -> usize {
42 0
43 }
44}
45
46fn validate_dimensions(num_row_groups: usize, num_columns: usize) -> Result<()> {
47 i32::try_from(num_row_groups).map_err(|_| {
49 ParquetError::General(format!(
50 "row group count exceeds i32::MAX: {num_row_groups}"
51 ))
52 })?;
53 i32::try_from(num_columns).map_err(|_| {
54 ParquetError::General(format!("column count exceeds i32::MAX: {num_columns}"))
55 })?;
56 Ok(())
57}
58
59#[derive(Debug, Clone, PartialEq)]
61pub(crate) struct ColumnChunkMap<T> {
62 num_row_groups: usize,
63 num_columns: usize,
64 entries: HashMap<ColumnChunkKey, T>,
65}
66
67impl<T> ColumnChunkMap<T> {
68 pub(crate) fn try_new(num_row_groups: usize, num_columns: usize) -> Result<Self> {
69 validate_dimensions(num_row_groups, num_columns)?;
70 Ok(Self {
71 num_row_groups,
72 num_columns,
73 entries: HashMap::new(),
74 })
75 }
76
77 pub(crate) fn num_row_groups(&self) -> usize {
78 self.num_row_groups
79 }
80
81 pub(crate) fn num_columns(&self) -> usize {
82 self.num_columns
83 }
84
85 pub(crate) fn is_empty(&self) -> bool {
86 self.entries.is_empty()
87 }
88
89 fn key(&self, row_group_idx: usize, column_idx: usize) -> Result<ColumnChunkKey> {
90 if row_group_idx >= self.num_row_groups || column_idx >= self.num_columns {
91 return Err(ParquetError::General(format!(
92 "column chunk coordinate out of bounds: row group {row_group_idx}, column \
93 {column_idx}; dimensions are {} by {}",
94 self.num_row_groups, self.num_columns
95 )));
96 }
97 ColumnChunkKey::try_new(row_group_idx, column_idx)
98 }
99
100 pub(crate) fn try_insert(
102 &mut self,
103 row_group_idx: usize,
104 column_idx: usize,
105 value: T,
106 ) -> Result<Option<T>> {
107 let key = self.key(row_group_idx, column_idx)?;
108 if let Some(existing) = self.entries.get_mut(&key) {
109 return Ok(Some(std::mem::replace(existing, value)));
110 }
111
112 self.entries.try_reserve(1).map_err(|err| {
113 ParquetError::General(format!(
114 "failed to reserve storage for column chunk at row group {row_group_idx}, \
115 column {column_idx}: {err}"
116 ))
117 })?;
118 Ok(self.entries.insert(key, value))
119 }
120
121 pub(crate) fn try_freeze(self) -> Result<ColumnChunkEntries<T>> {
122 validate_dimensions(self.num_row_groups, self.num_columns)?;
123 let num_entries = self.entries.len();
124 let mut entries = Vec::new();
125 entries.try_reserve_exact(num_entries).map_err(|err| {
126 ParquetError::General(format!(
127 "failed to allocate storage for {num_entries} column chunk entries: {err}"
128 ))
129 })?;
130 for entry in self.entries {
131 entries.push(entry);
132 }
133 entries.sort_unstable_by_key(|(key, _)| *key);
134 ColumnChunkEntries::try_from_sorted_entries(self.num_row_groups, self.num_columns, entries)
135 }
136}
137
138impl<T: HeapSize> HeapSize for ColumnChunkMap<T> {
139 fn heap_size(&self) -> usize {
140 self.entries.heap_size()
141 }
142}
143
144#[derive(Debug, Clone, PartialEq)]
146pub(crate) struct ColumnChunkEntries<T> {
147 num_row_groups: usize,
148 num_columns: usize,
149 entries: Box<[(ColumnChunkKey, T)]>,
150}
151
152impl<T> ColumnChunkEntries<T> {
153 pub(crate) fn try_from_sorted_entries(
156 num_row_groups: usize,
157 num_columns: usize,
158 entries: Vec<(ColumnChunkKey, T)>,
159 ) -> Result<Self> {
160 validate_dimensions(num_row_groups, num_columns)?;
161 let mut previous = None;
162 for (key, _) in &entries {
163 let (row_group_idx, column_idx) = key.coordinates();
164 if row_group_idx >= num_row_groups || column_idx >= num_columns {
165 return Err(ParquetError::General(format!(
166 "column chunk coordinate out of bounds: row group {row_group_idx}, column \
167 {column_idx}; dimensions are {num_row_groups} by {num_columns}"
168 )));
169 }
170 if previous.is_some_and(|previous| previous >= *key) {
171 return Err(ParquetError::General(
172 "column chunk entries must be unique and in row-major order".to_string(),
173 ));
174 }
175 previous = Some(*key);
176 }
177 Ok(Self {
178 num_row_groups,
179 num_columns,
180 entries: entries.into_boxed_slice(),
181 })
182 }
183
184 pub(crate) fn try_from_rows(rows: Vec<Vec<Option<T>>>) -> Result<Self> {
185 let num_row_groups = rows.len();
186 let num_columns = rows.iter().map(Vec::len).max().unwrap_or_default();
187 validate_dimensions(num_row_groups, num_columns)?;
188 let num_entries = rows
189 .iter()
190 .map(|columns| columns.iter().filter(|value| value.is_some()).count())
191 .try_fold(0_usize, |total, count| total.checked_add(count))
192 .ok_or_else(|| {
193 ParquetError::General("column chunk entry count exceeds usize::MAX".to_string())
194 })?;
195 let mut entries = Vec::new();
196 entries.try_reserve_exact(num_entries).map_err(|err| {
197 ParquetError::General(format!(
198 "failed to allocate storage for {num_entries} column chunk entries: {err}"
199 ))
200 })?;
201 for (row_group_idx, columns) in rows.into_iter().enumerate() {
202 for (column_idx, value) in columns.into_iter().enumerate() {
203 if let Some(value) = value {
204 entries.push((ColumnChunkKey::try_new(row_group_idx, column_idx)?, value));
205 }
206 }
207 }
208 Self::try_from_sorted_entries(num_row_groups, num_columns, entries)
209 }
210
211 pub(crate) fn is_empty(&self) -> bool {
212 self.entries.is_empty()
213 }
214
215 fn key(&self, row_group_idx: usize, column_idx: usize) -> Result<ColumnChunkKey> {
216 if row_group_idx >= self.num_row_groups || column_idx >= self.num_columns {
217 return Err(ParquetError::General(format!(
218 "column chunk coordinate out of bounds: row group {row_group_idx}, column \
219 {column_idx}; dimensions are {} by {}",
220 self.num_row_groups, self.num_columns
221 )));
222 }
223 ColumnChunkKey::try_new(row_group_idx, column_idx)
224 }
225
226 pub(crate) fn get(&self, row_group_idx: usize, column_idx: usize) -> Result<Option<&T>> {
227 let key = self.key(row_group_idx, column_idx)?;
228 let Ok(entry_idx) = self
229 .entries
230 .binary_search_by_key(&key, |(entry_key, _)| *entry_key)
231 else {
232 return Ok(None);
233 };
234 let Some((_, value)) = self.entries.get(entry_idx) else {
235 return Err(ParquetError::General(format!(
236 "column chunk binary search returned invalid entry index {entry_idx}"
237 )));
238 };
239 Ok(Some(value))
240 }
241
242 #[cfg_attr(not(test), expect(unused))]
243 pub(crate) fn iter(&self) -> impl Iterator<Item = (ColumnChunkKey, &T)> {
244 self.entries.iter().map(|(key, value)| (*key, value))
245 }
246
247 pub(crate) fn into_iter(self) -> impl Iterator<Item = (ColumnChunkKey, T)> {
248 self.entries.into_vec().into_iter()
249 }
250
251 pub(crate) fn try_into_map(self) -> Result<ColumnChunkMap<T>> {
252 let mut map = ColumnChunkMap::try_new(self.num_row_groups, self.num_columns)?;
253 for (key, value) in self.entries {
254 let (row_group_idx, column_idx) = key.coordinates();
255 map.try_insert(row_group_idx, column_idx, value)?;
256 }
257 Ok(map)
258 }
259}
260
261impl<V: HeapSize> HeapSize for ColumnChunkEntries<V> {
262 fn heap_size(&self) -> usize {
263 self.entries.len() * std::mem::size_of::<(ColumnChunkKey, V)>()
264 + self
265 .entries
266 .iter()
267 .map(|(_, value)| value.heap_size())
268 .sum::<usize>()
269 }
270}
271
272#[cfg(test)]
273mod tests {
274 use super::*;
275
276 #[test]
277 fn sparse_storage_is_sorted_and_validates_coordinates() {
278 let mut map = ColumnChunkMap::try_new(2, 3).unwrap();
279 map.try_insert(1, 2, 12).unwrap();
280 map.try_insert(0, 1, 1).unwrap();
281 let entries = map.try_freeze().unwrap();
282
283 let coordinates = entries
284 .iter()
285 .map(|(key, _)| key.coordinates())
286 .collect::<Vec<_>>();
287 assert_eq!(coordinates, vec![(0, 1), (1, 2)]);
288 assert_eq!(entries.get(0, 1).unwrap(), Some(&1));
289 assert_eq!(entries.get(0, 2).unwrap(), None);
290 assert!(entries.get(2, 0).is_err());
291 assert!(entries.get(0, 3).is_err());
292 }
293
294 #[test]
295 fn sorted_entries_preserve_sparse_coordinates() {
296 let entries = ColumnChunkEntries::try_from_sorted_entries(
297 100,
298 1_000,
299 vec![
300 (ColumnChunkKey::try_new(0, 3).unwrap(), 3_i32),
301 (ColumnChunkKey::try_new(99, 999).unwrap(), 999),
302 ],
303 )
304 .unwrap();
305 assert_eq!(entries.get(0, 3).unwrap(), Some(&3));
306 assert_eq!(entries.get(0, 2).unwrap(), None);
307 assert_eq!(entries.get(99, 999).unwrap(), Some(&999));
308 assert_eq!(
309 entries.heap_size(),
310 2 * std::mem::size_of::<(ColumnChunkKey, i32)>()
311 );
312 assert!(
313 ColumnChunkEntries::<i32>::try_from_sorted_entries(0, 0, vec![])
314 .unwrap()
315 .is_empty()
316 );
317 }
318
319 #[test]
320 fn sorted_entries_reject_invalid_coordinates_and_order() {
321 let first = ColumnChunkKey::try_new(0, 0).unwrap();
322 let second = ColumnChunkKey::try_new(1, 1).unwrap();
323 for entries in [vec![(first, 1), (first, 2)], vec![(second, 1), (first, 2)]] {
324 assert!(ColumnChunkEntries::try_from_sorted_entries(2, 2, entries).is_err());
325 }
326 assert!(ColumnChunkEntries::try_from_sorted_entries(1, 2, vec![(second, 1)]).is_err());
327 assert!(ColumnChunkEntries::try_from_sorted_entries(2, 1, vec![(second, 1)]).is_err());
328 assert!(
329 ColumnChunkEntries::<i32>::try_from_sorted_entries(i32::MAX as usize + 1, 1, vec![],)
330 .is_err()
331 );
332 }
333
334 #[test]
335 fn zero_and_invalid_dimensions() {
336 assert!(ColumnChunkMap::<()>::try_new(0, 0).is_ok());
337 assert!(ColumnChunkMap::<()>::try_new(i32::MAX as usize + 1, 1).is_err());
338 assert!(ColumnChunkMap::<()>::try_new(1, i32::MAX as usize + 1).is_err());
339 }
340
341 #[test]
342 fn insertion_replaces_existing_value_without_growing() {
343 let mut map = ColumnChunkMap::try_new(1, 1).unwrap();
344 assert_eq!(map.try_insert(0, 0, "first").unwrap(), None);
345 let capacity = map.entries.capacity();
346
347 assert_eq!(map.try_insert(0, 0, "replacement").unwrap(), Some("first"));
348 assert_eq!(map.entries.len(), 1);
349 assert_eq!(map.entries.capacity(), capacity);
350 }
351
352 #[test]
353 fn freeze_and_thaw_preserve_entries() {
354 let mut map = ColumnChunkMap::try_new(2, 2).unwrap();
355 map.try_insert(1, 0, 3).unwrap();
356 let expected_entries = map.try_freeze().unwrap();
357
358 let mut map = ColumnChunkMap::try_new(2, 2).unwrap();
359 map.try_insert(1, 0, 3).unwrap();
360 let entries = map.try_freeze().unwrap();
361 let thawed = entries.try_into_map().unwrap();
362 assert_eq!(thawed.try_freeze().unwrap(), expected_entries);
363 }
364
365 #[test]
366 fn frozen_heap_size_uses_packed_key_layout() {
367 let entries = ColumnChunkEntries::try_from_rows(vec![vec![Some(1_i32)]]).unwrap();
368 assert_eq!(
369 entries.heap_size(),
370 std::mem::size_of::<(ColumnChunkKey, i32)>()
371 );
372 }
373}