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
use crate::{BTreeMap, Data, Storage};
use std::cmp::min;
/// Slice of Data to be written to storage.
pub struct DataSlice {
///
pub off: usize,
///
pub len: usize,
///
pub data: Data,
}
impl DataSlice {
///
pub fn data(&self) -> &[u8] {
&self.data[self.off..self.off + self.len]
}
}
/// Implements an updateable file based on some underlying storage.
pub struct WMap {
/// Map of outstanding writes which have not yet been written to the underlying file.
pub map: BTreeMap<u64, DataSlice>,
}
impl Default for WMap {
/// Construct a new WMap
fn default() -> Self {
Self {
map: BTreeMap::new(),
}
}
}
impl WMap {
/// Read from file, taking writes into account. Unwritten ranges are read from underlying storage.
pub fn read(&self, start: u64, data: &mut [u8], u: &dyn Storage) {
let mut todo: usize = data.len();
if todo == 0 {
return;
}
let mut done: usize = 0;
for (&k, v) in self.map.range(start..) {
let estart = k + 1 - v.len as u64;
if estart > start + done as u64 {
let lim = (estart - (start + done as u64)) as usize;
let amount = min(todo, lim);
u.read(start + done as u64, &mut data[done..done + amount]);
done += amount;
todo -= amount;
}
if estart > start + data.len() as u64 {
break;
} else {
let skip = (start + done as u64 - estart) as usize;
let amount = min(todo, v.len - skip);
data[done..done + amount]
.copy_from_slice(&v.data[v.off + skip..v.off + skip + amount]);
done += amount;
todo -= amount;
}
if todo == 0 {
break;
}
}
if todo > 0 {
u.read(start + done as u64, &mut data[done..done + todo]);
}
}
/// Write to file. Existing writes which overlap with new write need to be trimmed or removed.
pub fn write(&mut self, start: u64, data: Data, off: usize, len: usize) {
if len == 0 {
return;
}
let mut remove = Vec::new();
let mut add = Vec::new();
let end = start + len as u64;
for (&k, v) in self.map.range_mut(start..) {
let eend = k + 1; // end of existing write.
let estart = eend - v.len as u64; // start of existing write.
// (a) New write ends before existing write.
if end <= estart {
break;
}
// (b) New write subsumes existing write entirely, remove existing write.
else if start <= estart && end >= eend {
remove.push(eend - 1);
}
// (c) New write starts before existing write, but doesn't subsume it. Trim existing write.
else if start <= estart {
let trim = (end - estart) as usize;
v.len -= trim;
v.off += trim;
}
// (d) New write starts in middle of existing write, ends before end of existing write...
// .. put start of existing write in add list, trim existing write.
else if start > estart && end < eend {
let remain = (start - estart) as usize;
add.push((estart, v.data.clone(), v.off, remain));
let trim = (end - estart) as usize;
v.len -= trim;
v.off += trim;
}
// (e) New write starts in middle of existing write, ends after existing write...
// ... put start of existing write in add list, remove existing write,
else {
let remain = (start - estart) as usize;
add.push((estart, v.data.clone(), v.off, remain));
remove.push(eend - 1);
}
}
for k in remove {
self.map.remove(&k);
}
for (start, data, off, len) in add {
self.map
.insert(start + len as u64 - 1, DataSlice { data, off, len });
}
self.map
.insert(start + len as u64 - 1, DataSlice { data, off, len });
}
}