Show More
@@ -8,7 +8,7 b' use byteorder::{BigEndian, ByteOrder};' | |||||
8 | /// - a replacement when `!data.is_empty() && start < end` |
|
8 | /// - a replacement when `!data.is_empty() && start < end` | |
9 | /// - not doing anything when `data.is_empty() && start == end` |
|
9 | /// - not doing anything when `data.is_empty() && start == end` | |
10 | #[derive(Debug, Clone)] |
|
10 | #[derive(Debug, Clone)] | |
11 |
struct |
|
11 | struct Chunk<'a> { | |
12 | /// The start position of the chunk of data to replace |
|
12 | /// The start position of the chunk of data to replace | |
13 | start: i32, |
|
13 | start: i32, | |
14 | /// The end position of the chunk of data to replace (open end interval) |
|
14 | /// The end position of the chunk of data to replace (open end interval) | |
@@ -17,7 +17,7 b" struct PatchFrag<'a> {" | |||||
17 | data: &'a [u8], |
|
17 | data: &'a [u8], | |
18 | } |
|
18 | } | |
19 |
|
19 | |||
20 |
impl<'a> |
|
20 | impl<'a> Chunk<'a> { | |
21 | /// Adjusted start of the chunk to replace. |
|
21 | /// Adjusted start of the chunk to replace. | |
22 | /// |
|
22 | /// | |
23 | /// Offset allow to take into account the growth/shrinkage of data |
|
23 | /// Offset allow to take into account the growth/shrinkage of data | |
@@ -54,35 +54,35 b" pub struct PatchList<'a> {" | |||||
54 | /// - ordered from the left-most replacement to the right-most replacement |
|
54 | /// - ordered from the left-most replacement to the right-most replacement | |
55 | /// - non-overlapping, meaning that two chucks can not change the same |
|
55 | /// - non-overlapping, meaning that two chucks can not change the same | |
56 | /// chunk of the patched data |
|
56 | /// chunk of the patched data | |
57 |
|
|
57 | chunks: Vec<Chunk<'a>>, | |
58 | } |
|
58 | } | |
59 |
|
59 | |||
60 | impl<'a> PatchList<'a> { |
|
60 | impl<'a> PatchList<'a> { | |
61 | /// Create a `PatchList` from bytes. |
|
61 | /// Create a `PatchList` from bytes. | |
62 | pub fn new(data: &'a [u8]) -> Self { |
|
62 | pub fn new(data: &'a [u8]) -> Self { | |
63 |
let mut |
|
63 | let mut chunks = vec![]; | |
64 | let mut data = data; |
|
64 | let mut data = data; | |
65 | while !data.is_empty() { |
|
65 | while !data.is_empty() { | |
66 | let start = BigEndian::read_i32(&data[0..]); |
|
66 | let start = BigEndian::read_i32(&data[0..]); | |
67 | let end = BigEndian::read_i32(&data[4..]); |
|
67 | let end = BigEndian::read_i32(&data[4..]); | |
68 | let len = BigEndian::read_i32(&data[8..]); |
|
68 | let len = BigEndian::read_i32(&data[8..]); | |
69 | assert!(0 <= start && start <= end && len >= 0); |
|
69 | assert!(0 <= start && start <= end && len >= 0); | |
70 |
|
|
70 | chunks.push(Chunk { | |
71 | start, |
|
71 | start, | |
72 | end, |
|
72 | end, | |
73 | data: &data[12..12 + (len as usize)], |
|
73 | data: &data[12..12 + (len as usize)], | |
74 | }); |
|
74 | }); | |
75 | data = &data[12 + (len as usize)..]; |
|
75 | data = &data[12 + (len as usize)..]; | |
76 | } |
|
76 | } | |
77 |
PatchList { |
|
77 | PatchList { chunks } | |
78 | } |
|
78 | } | |
79 |
|
79 | |||
80 | /// Return the final length of data after patching |
|
80 | /// Return the final length of data after patching | |
81 | /// given its initial length . |
|
81 | /// given its initial length . | |
82 | fn size(&self, initial_size: i32) -> i32 { |
|
82 | fn size(&self, initial_size: i32) -> i32 { | |
83 |
self. |
|
83 | self.chunks | |
84 | .iter() |
|
84 | .iter() | |
85 |
.fold(initial_size, |acc, |
|
85 | .fold(initial_size, |acc, chunk| acc + chunk.len_diff()) | |
86 | } |
|
86 | } | |
87 |
|
87 | |||
88 | /// Apply the patch to some data. |
|
88 | /// Apply the patch to some data. | |
@@ -90,7 +90,7 b" impl<'a> PatchList<'a> {" | |||||
90 | let mut last: usize = 0; |
|
90 | let mut last: usize = 0; | |
91 | let mut vec = |
|
91 | let mut vec = | |
92 | Vec::with_capacity(self.size(initial.len() as i32) as usize); |
|
92 | Vec::with_capacity(self.size(initial.len() as i32) as usize); | |
93 |
for |
|
93 | for Chunk { start, end, data } in self.chunks.iter() { | |
94 | vec.extend(&initial[last..(*start as usize)]); |
|
94 | vec.extend(&initial[last..(*start as usize)]); | |
95 | vec.extend(data.iter()); |
|
95 | vec.extend(data.iter()); | |
96 | last = *end as usize; |
|
96 | last = *end as usize; | |
@@ -105,7 +105,7 b" impl<'a> PatchList<'a> {" | |||||
105 | /// as the changes introduced by one patch can be overridden by the next. |
|
105 | /// as the changes introduced by one patch can be overridden by the next. | |
106 | /// Combining patches optimizes the whole patching sequence. |
|
106 | /// Combining patches optimizes the whole patching sequence. | |
107 | fn combine(&mut self, other: &mut Self) -> Self { |
|
107 | fn combine(&mut self, other: &mut Self) -> Self { | |
108 |
let mut |
|
108 | let mut chunks = vec![]; | |
109 |
|
109 | |||
110 | // Keep track of each growth/shrinkage resulting from applying a chunk |
|
110 | // Keep track of each growth/shrinkage resulting from applying a chunk | |
111 | // in order to adjust the start/end of subsequent chunks. |
|
111 | // in order to adjust the start/end of subsequent chunks. | |
@@ -116,15 +116,15 b" impl<'a> PatchList<'a> {" | |||||
116 |
|
116 | |||
117 | // For each chunk of `other`, chunks of `self` are processed |
|
117 | // For each chunk of `other`, chunks of `self` are processed | |
118 | // until they start after the end of the current chunk. |
|
118 | // until they start after the end of the current chunk. | |
119 |
for |
|
119 | for Chunk { start, end, data } in other.chunks.iter() { | |
120 | // Add chunks of `self` that start before this chunk of `other` |
|
120 | // Add chunks of `self` that start before this chunk of `other` | |
121 | // without overlap. |
|
121 | // without overlap. | |
122 |
while pos < self. |
|
122 | while pos < self.chunks.len() | |
123 |
&& self. |
|
123 | && self.chunks[pos].end_offseted_by(offset) <= *start | |
124 | { |
|
124 | { | |
125 |
let first = self. |
|
125 | let first = self.chunks[pos].clone(); | |
126 | offset += first.len_diff(); |
|
126 | offset += first.len_diff(); | |
127 |
|
|
127 | chunks.push(first); | |
128 | pos += 1; |
|
128 | pos += 1; | |
129 | } |
|
129 | } | |
130 |
|
130 | |||
@@ -132,15 +132,15 b" impl<'a> PatchList<'a> {" | |||||
132 | // with overlap. |
|
132 | // with overlap. | |
133 | // The left-most part of data is added as an insertion chunk. |
|
133 | // The left-most part of data is added as an insertion chunk. | |
134 | // The right-most part data is kept in the chunk. |
|
134 | // The right-most part data is kept in the chunk. | |
135 |
if pos < self. |
|
135 | if pos < self.chunks.len() | |
136 |
&& self. |
|
136 | && self.chunks[pos].start_offseted_by(offset) < *start | |
137 | { |
|
137 | { | |
138 |
let first = &mut self. |
|
138 | let first = &mut self.chunks[pos]; | |
139 |
|
139 | |||
140 | let (data_left, data_right) = first.data.split_at( |
|
140 | let (data_left, data_right) = first.data.split_at( | |
141 | (*start - first.start_offseted_by(offset)) as usize, |
|
141 | (*start - first.start_offseted_by(offset)) as usize, | |
142 | ); |
|
142 | ); | |
143 |
let left = |
|
143 | let left = Chunk { | |
144 | start: first.start, |
|
144 | start: first.start, | |
145 | end: first.start, |
|
145 | end: first.start, | |
146 | data: data_left, |
|
146 | data: data_left, | |
@@ -150,7 +150,7 b" impl<'a> PatchList<'a> {" | |||||
150 |
|
150 | |||
151 | offset += left.len_diff(); |
|
151 | offset += left.len_diff(); | |
152 |
|
152 | |||
153 |
|
|
153 | chunks.push(left); | |
154 |
|
154 | |||
155 | // There is no index incrementation because the right-most part |
|
155 | // There is no index incrementation because the right-most part | |
156 | // needs further examination. |
|
156 | // needs further examination. | |
@@ -167,20 +167,20 b" impl<'a> PatchList<'a> {" | |||||
167 |
|
167 | |||
168 | // Discard the chunks of `self` that are totally overridden |
|
168 | // Discard the chunks of `self` that are totally overridden | |
169 | // by the current chunk of `other` |
|
169 | // by the current chunk of `other` | |
170 |
while pos < self. |
|
170 | while pos < self.chunks.len() | |
171 |
&& self. |
|
171 | && self.chunks[pos].end_offseted_by(next_offset) <= *end | |
172 | { |
|
172 | { | |
173 |
let first = &self. |
|
173 | let first = &self.chunks[pos]; | |
174 | next_offset += first.len_diff(); |
|
174 | next_offset += first.len_diff(); | |
175 | pos += 1; |
|
175 | pos += 1; | |
176 | } |
|
176 | } | |
177 |
|
177 | |||
178 | // Truncate the left-most part of chunk of `self` that overlaps |
|
178 | // Truncate the left-most part of chunk of `self` that overlaps | |
179 | // the current chunk of `other`. |
|
179 | // the current chunk of `other`. | |
180 |
if pos < self. |
|
180 | if pos < self.chunks.len() | |
181 |
&& self. |
|
181 | && self.chunks[pos].start_offseted_by(next_offset) < *end | |
182 | { |
|
182 | { | |
183 |
let first = &mut self. |
|
183 | let first = &mut self.chunks[pos]; | |
184 |
|
184 | |||
185 | let how_much_to_discard = |
|
185 | let how_much_to_discard = | |
186 | *end - first.start_offseted_by(next_offset); |
|
186 | *end - first.start_offseted_by(next_offset); | |
@@ -191,7 +191,7 b" impl<'a> PatchList<'a> {" | |||||
191 | } |
|
191 | } | |
192 |
|
192 | |||
193 | // Add the chunk of `other` with adjusted position. |
|
193 | // Add the chunk of `other` with adjusted position. | |
194 |
|
|
194 | chunks.push(Chunk { | |
195 | start: *start - offset, |
|
195 | start: *start - offset, | |
196 | end: *end - next_offset, |
|
196 | end: *end - next_offset, | |
197 | data, |
|
197 | data, | |
@@ -202,10 +202,10 b" impl<'a> PatchList<'a> {" | |||||
202 | } |
|
202 | } | |
203 |
|
203 | |||
204 | // Add remaining chunks of `self`. |
|
204 | // Add remaining chunks of `self`. | |
205 |
for elt in &self. |
|
205 | for elt in &self.chunks[pos..] { | |
206 |
|
|
206 | chunks.push(elt.clone()); | |
207 | } |
|
207 | } | |
208 |
PatchList { |
|
208 | PatchList { chunks } | |
209 | } |
|
209 | } | |
210 | } |
|
210 | } | |
211 |
|
211 | |||
@@ -213,7 +213,7 b" impl<'a> PatchList<'a> {" | |||||
213 | pub fn fold_patch_lists<'a>(lists: &[PatchList<'a>]) -> PatchList<'a> { |
|
213 | pub fn fold_patch_lists<'a>(lists: &[PatchList<'a>]) -> PatchList<'a> { | |
214 | if lists.len() <= 1 { |
|
214 | if lists.len() <= 1 { | |
215 | if lists.is_empty() { |
|
215 | if lists.is_empty() { | |
216 |
PatchList { |
|
216 | PatchList { chunks: vec![] } | |
217 | } else { |
|
217 | } else { | |
218 | lists[0].clone() |
|
218 | lists[0].clone() | |
219 | } |
|
219 | } |
General Comments 0
You need to be logged in to leave comments.
Login now