1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
use std::ops::RangeBounds;
use crate::hash::{BlockHash, BlockHasher};
use super::types::{
BlockEncoding, BlockId, BlockIndex, BlockLen, BlockList, BlockSignature, FileId, FileOffset,
HoleLen,
};
/// The result of reading a block from the block store.
#[derive(Debug, Clone, PartialEq, Eq)]
pub struct ReadBlock {
pub signature: BlockSignature,
pub encoding: BlockEncoding,
}
/// The backing store for file data.
pub trait DataStore {
/// List the blocks that comprise the given file's contents.
fn list_blocks(&mut self, file: FileId) -> crate::Result<BlockList>;
/// Read the contents of the block with a given ID.
///
/// If the block is a data block, `buf` will be filled with the block's data. If the block is a
/// hole, `buf` will be ignored.
fn read_block(&mut self, block: BlockId, buf: &mut Vec<u8>) -> crate::Result<ReadBlock>;
/// Insert a block into the block store.
///
/// This writes the given data at the given offset from the start of the file, overwriting
/// in-place. This method is responsible for splitting and merging blocks as needed; the
/// algorithm for doing so is up to the implementation.
///
/// This method is responsible for checking if a block with the given hash already exists in
/// the block store and deduplicating it.
///
/// This method returns the new list of blocks for the file.
fn write_block(
&mut self,
file: FileId,
offset: FileOffset,
block_list: BlockList,
input: BlockStoreInput,
) -> crate::Result<BlockList>;
/// Truncate the given file to the given length.
///
/// If `len` is larger than the size of the file, this is a no-op. This method does not grow
/// the file or create sparse holes.
fn truncate(
&mut self,
file: FileId,
block_list: BlockList,
len: FileOffset,
) -> crate::Result<BlockList>;
}
#[derive(Debug, Clone)]
pub enum BlockStoreInput<'a> {
Data {
bytes: &'a [u8],
hash: BlockHash,
encoding: BlockEncoding,
/// The logical (uncompressed) length of this block. If `None`, this defaults to
/// `bytes.len()`.
len: Option<BlockLen>,
},
Hole {
len: HoleLen,
},
}
impl<'a> From<&'a [u8]> for BlockStoreInput<'a> {
fn from(bytes: &'a [u8]) -> Self {
BlockStoreInput::Data {
bytes,
hash: BlockHasher::hash(bytes),
encoding: BlockEncoding::NONE,
len: None,
}
}
}
impl<'a> BlockStoreInput<'a> {
pub fn len(&self) -> BlockLen {
match self {
BlockStoreInput::Data {
bytes,
len: logical_len,
..
} => logical_len.unwrap_or(bytes.len()),
BlockStoreInput::Hole { len } => *len as BlockLen,
}
}
pub fn encoding(&self) -> BlockEncoding {
match self {
BlockStoreInput::Data { encoding, .. } => *encoding,
BlockStoreInput::Hole { .. } => BlockEncoding::NONE,
}
}
}
/// A backing store for blocks of data.
///
/// Each file consists of a list of blocks, which may be either data blocks or holes.
pub trait BlockStore {
/// List the blocks that comprise the given file's contents.
fn list_blocks(&self, file: FileId) -> crate::Result<BlockList>;
/// Read the contents of the block with a given ID.
///
/// If the block is a data block, the block's data will be appended to `buf` (meaning you'll
/// usually want to clear the vector first). If the block is a hole, `buf` will be ignored.
fn read_block(&mut self, block: BlockId, buf: &mut Vec<u8>) -> crate::Result<ReadBlock>;
/// Replace the block at a given index in the file's block list.
///
/// This returns the block ID of the new block.
fn replace_block(
&mut self,
file: FileId,
index: BlockIndex,
input: BlockStoreInput,
) -> crate::Result<BlockId>;
/// Insert a block at the given index in file's block list, shifting all subsequent blocks
/// forward.
///
/// This returns the block ID of the new block.
fn insert_block(
&mut self,
file: FileId,
index: BlockIndex,
input: BlockStoreInput,
) -> crate::Result<BlockId>;
/// Append a block to the end of a file's block list.
///
/// As a performance optimization, this accepts the index of the new block, because we already
/// have the length of the block list in memory. This index MUST be correct; the behavior is
/// unspecified if it is not.
///
/// This returns the block ID of the new block.
fn append_block(
&mut self,
file: FileId,
index: BlockIndex,
input: BlockStoreInput,
) -> crate::Result<BlockId>;
/// Remove a slice of blocks from the given file's block list, shifting all subsequent blocks
/// backward.
///
/// This returns the block IDs of the removed blocks.
fn remove_blocks<R: RangeBounds<usize>>(
&mut self,
file: FileId,
blocks: R,
) -> crate::Result<Vec<BlockId>>;
}