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    /// Clears all shard CIDs and compressed sizes (keeps ranges and IDs).
100    pub fn clear_assignments(&mut self) {
101        for range in &mut self.ranges {
102            range.cid = None;
103            range.compressed_size = 0;
104            range.digest = None;
105            range.wrapped_key = None;
106        }
107    }
108
109    /// Splits a range into two halves, keeping the lower half's shard_id.
110    ///
111    /// Returns false if the range is not found or cannot be split.
112    pub fn split_range(&mut self, shard_id: u64) -> bool {
113        let index = match self.ranges.iter().position(|r| r.shard_id == shard_id) {
114            Some(i) => i,
115            None => return false,
116        };
117
118        let range = self.ranges[index].clone();
119        if range.start == range.end {
120            return false;
121        }
122
123        let mid = range.start + (range.end - range.start) / 2;
124        let lower = ShardRange {
125            start: range.start,
126            end: mid,
127            shard_id: range.shard_id,
128            cid: None,
129            compressed_size: 0,
130            digest: None,
131            wrapped_key: None,
132        };
133        let upper_start = mid.saturating_add(1);
134        if upper_start > range.end {
135            return false;
136        }
137        let upper = ShardRange {
138            start: upper_start,
139            end: range.end,
140            shard_id: self.next_shard_id,
141            cid: None,
142            compressed_size: 0,
143            digest: None,
144            wrapped_key: None,
145        };
146        self.next_shard_id = self.next_shard_id.saturating_add(1);
147
148        self.ranges[index] = lower;
149        self.ranges.insert(index + 1, upper);
150        true
151    }
152}
void_core/metadata/shard_map.rs

void_core/metadata/
shard_map.rs
