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
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,
}
/// 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 });
}
}