alice.pds.demo.boltless.dev
This repository has no description
did:plc:3fwecdnvtcscjnrx2p4n7a…
1use std::collections::HashMap;
2
3use knot_types::Oid;
4
5use super::{BitPosition, IndexPosition};
6
7pub(crate) trait Order {
8 fn len(&self) -> usize;
9 fn index_of(&self, oid: Oid) -> Option<IndexPosition>;
10 fn bit_at_index(&self, position: IndexPosition) -> BitPosition;
11 fn oid_at_bit(&self, bit: BitPosition) -> Oid;
12}
13
14pub(crate) struct OrderTable {
15 oids: Vec<Oid>,
16 bit_to_index: Vec<IndexPosition>,
17 index_to_bit: Vec<BitPosition>,
18 by_oid: HashMap<Oid, IndexPosition>,
19}
20
21impl OrderTable {
22 fn build<K: Ord>(oids: Vec<Oid>, placement: impl Fn(u32) -> K) -> Self {
23 let count = oids.len() as u32;
24 let mut order: Vec<u32> = (0..count).collect();
25 order.sort_by_key(|position| placement(*position));
26 let bit_to_index: Vec<IndexPosition> = order
27 .iter()
28 .map(|position| IndexPosition::new(*position))
29 .collect();
30 let index_to_bit = order.iter().enumerate().fold(
31 vec![BitPosition::new(0); oids.len()],
32 |mut table, (bit, position)| {
33 table[*position as usize] = BitPosition::new(bit as u32);
34 table
35 },
36 );
37 let by_oid: HashMap<Oid, IndexPosition> = oids
38 .iter()
39 .enumerate()
40 .map(|(position, oid)| (*oid, IndexPosition::new(position as u32)))
41 .collect();
42 Self {
43 oids,
44 bit_to_index,
45 index_to_bit,
46 by_oid,
47 }
48 }
49
50 pub(crate) fn from_index(index: &gix_pack::index::File) -> Self {
51 let count = index.num_objects();
52 let oids: Vec<Oid> = (0..count)
53 .map(|position| Oid::from(index.oid_at_index(position).to_owned()))
54 .collect();
55 let offsets: Vec<u64> = (0..count)
56 .map(|position| index.pack_offset_at_index(position))
57 .collect();
58 Self::build(oids, |position| offsets[position as usize])
59 }
60
61 pub(crate) fn from_file(file: &gix_pack::multi_index::File) -> Self {
62 let count = file.num_objects();
63 let oids: Vec<Oid> = (0..count)
64 .map(|position| Oid::from(file.oid_at_index(position).to_owned()))
65 .collect();
66 let placement: Vec<(u32, u64)> = (0..count)
67 .map(|position| file.pack_id_and_pack_offset_at_index(position))
68 .collect();
69 Self::build(oids, |position| placement[position as usize])
70 }
71
72 pub(crate) fn index_positions_in_bit_order(&self) -> &[IndexPosition] {
73 &self.bit_to_index
74 }
75}
76
77impl Order for OrderTable {
78 fn len(&self) -> usize {
79 self.oids.len()
80 }
81
82 fn index_of(&self, oid: Oid) -> Option<IndexPosition> {
83 self.by_oid.get(&oid).copied()
84 }
85
86 fn bit_at_index(&self, position: IndexPosition) -> BitPosition {
87 self.index_to_bit[position.get() as usize]
88 }
89
90 fn oid_at_bit(&self, bit: BitPosition) -> Oid {
91 self.oids[self.bit_to_index[bit.get() as usize].get() as usize]
92 }
93}