void_core/metadata/
shard_map.rs

1//! ShardMap implementation.
2
3use super::{hash_dir_path_u64, hash_path_u64, ShardMap, ShardRange};
4use void_crypto::{RepoSecret, ShardCid, WrappedKey};
5
6impl ShardMap {
7    pub const VERSION: u32 = 1;
8    pub const HASH_BYTES: u8 = 8;
9
10    /// Creates a new shard map with evenly-sized ranges.
11    ///
12    /// The range count is rounded up to the next power of two to simplify
13    /// future splits and keep ranges aligned.
14    pub fn new(range_count: u64) -> Self {
15        let count = range_count.max(1).next_power_of_two();
16        let total_space = u128::from(u64::MAX) + 1;
17        let range_size = total_space / u128::from(count);
18        let mut ranges = Vec::with_capacity(count as usize);
19        let mut start = 0u64;
20
21        for i in 0..count {
22            let end = if i == count - 1 {
23                u64::MAX
24            } else {
25                let end_u128 = u128::from(start) + range_size - 1;
26                end_u128 as u64
27            };
28
29            ranges.push(ShardRange {
30                start,
31                end,
32                shard_id: i,
33                cid: None,
34                compressed_size: 0,
35                digest: None,
36                wrapped_key: None,
37            });
38
39            start = end.saturating_add(1);
40        }
41
42        Self {
43            version: Self::VERSION,
44            hash_bytes: Self::HASH_BYTES,
45            ranges,
46            next_shard_id: count,
47        }
48    }
49
50    /// Finds the range index for a given hash key.
51    pub fn range_index_for_hash(&self, key: u64) -> Option<usize> {
52        self.ranges
53            .binary_search_by(|range| {
54                if key < range.start {
55                    std::cmp::Ordering::Greater
56                } else if key > range.end {
57                    std::cmp::Ordering::Less
58                } else {
59                    std::cmp::Ordering::Equal
60                }
61            })
62            .ok()
63    }
64
65    /// Returns the shard range for a given hash key.
66    pub fn range_for_hash(&self, key: u64) -> Option<&ShardRange> {
67        self.range_index_for_hash(key).map(|idx| &self.ranges[idx])
68    }
69
70    /// Returns the shard range for a given path.
71    pub fn range_for_path(&self, repo_secret: &RepoSecret, path: &str) -> Option<&ShardRange> {
72        self.range_for_hash(hash_path_u64(repo_secret, path))
73    }
74
75    /// Returns the shard range for a given directory path.
76    pub fn range_for_dir(&self, repo_secret: &RepoSecret, dir_path: &str) -> Option<&ShardRange> {
77        self.range_for_hash(hash_dir_path_u64(repo_secret, dir_path))
78    }
79
80    /// Updates shard CID and size by shard ID.
81    pub fn update_range(
82        &mut self,
83        shard_id: u64,
84        cid: ShardCid,
85        compressed_size: u64,
86        digest: Option<[u8; 32]>,
87        wrapped_key: Option<WrappedKey>,
88    ) -> bool {
89        if let Some(range) = self.ranges.iter_mut().find(|r| r.shard_id == shard_id) {
90            range.cid = Some(cid);
91            range.compressed_size = compressed_size;
92            range.digest = digest;
93            range.wrapped_key = wrapped_key;
94            return true;
95        }
96        false
97    }
98
99    /// Allocate a new shard ID (for large file chunks that bypass hash assignment).
100    pub fn allocate_shard_id(&mut self) -> u64 {
101        let id = self.next_shard_id;
102        self.next_shard_id = self.next_shard_id.saturating_add(1);
103        id
104    }
105
106    /// Clears all shard CIDs and compressed sizes (keeps ranges and IDs).
107    pub fn clear_assignments(&mut self) {
108        for range in &mut self.ranges {
109            range.cid = None;
110            range.compressed_size = 0;
111            range.digest = None;
112            range.wrapped_key = None;
113        }
114    }
115
116    /// Splits a range into two halves, keeping the lower half's shard_id.
117    ///
118    /// Returns false if the range is not found or cannot be split.
119    pub fn split_range(&mut self, shard_id: u64) -> bool {
120        let index = match self.ranges.iter().position(|r| r.shard_id == shard_id) {
121            Some(i) => i,
122            None => return false,
123        };
124
125        let range = self.ranges[index].clone();
126        if range.start == range.end {
127            return false;
128        }
129
130        let mid = range.start + (range.end - range.start) / 2;
131        let lower = ShardRange {
132            start: range.start,
133            end: mid,
134            shard_id: range.shard_id,
135            cid: None,
136            compressed_size: 0,
137            digest: None,
138            wrapped_key: None,
139        };
140        let upper_start = mid.saturating_add(1);
141        if upper_start > range.end {
142            return false;
143        }
144        let upper = ShardRange {
145            start: upper_start,
146            end: range.end,
147            shard_id: self.next_shard_id,
148            cid: None,
149            compressed_size: 0,
150            digest: None,
151            wrapped_key: None,
152        };
153        self.next_shard_id = self.next_shard_id.saturating_add(1);
154
155        self.ranges[index] = lower;
156        self.ranges.insert(index + 1, upper);
157        true
158    }
159}
void_core/metadata/shard_map.rs

void_core/metadata/
shard_map.rs
