"Fossies" - the Fresh Open Source Software Archive 
Member "xdelta3-3.0.11/testing/modify.h" (13 Jul 2015, 10117 Bytes) of package /linux/misc/xdelta3-3.0.11.tar.gz:
As a special service "Fossies" has tried to format the requested source page into HTML format using (guessed) C and C++ source code syntax highlighting (style:
standard) with prefixed line numbers and
code folding option.
Alternatively you can here
view or
download the uninterpreted source code file.
1 // -*- Mode: C++ -*-
2 class Mutator {
3 public:
4 virtual ~Mutator() { }
5 virtual void Mutate(SegmentMap *table,
6 const SegmentMap *source_table,
7 MTRandom *rand) const = 0;
8 };
9
10 class Change {
11 public:
12 enum Kind {
13 MODIFY = 1, // Mutate a certain range w/ random or supplied data
14 ADD = 2, // Insert random or supplied data
15 DELRANGE = 3, // Delete a specified range of data
16 COPY = 4, // Copy from one region, inserting elsewhere
17 MOVE = 5, // Copy then delete copied-from range
18 COPYOVER = 6 // Copy then delete copied-to range
19
20 // ADD, DELRANGE, and COPY change the file size
21 // MODIFY, MOVE, COPYOVER preserve the file size
22 };
23
24 // Constructor for modify, add, delete.
25 Change(Kind kind0, xoff_t size0, xoff_t addr1_0)
26 : kind(kind0),
27 size(size0),
28 addr1(addr1_0),
29 addr2(0),
30 insert(NULL) {
31 CHECK(kind != MOVE && kind != COPY && kind != COPYOVER);
32 }
33
34 // Constructor for modify, add w/ provided data.
35 Change(Kind kind0, xoff_t size0, xoff_t addr1_0, Segment *insert0)
36 : kind(kind0),
37 size(size0),
38 addr1(addr1_0),
39 addr2(0),
40 insert(insert0) {
41 CHECK(kind != MOVE && kind != COPY && kind != COPYOVER);
42 }
43
44 // Constructor for move, copy, overwrite
45 Change(Kind kind0, xoff_t size0, xoff_t addr1_0, xoff_t addr2_0)
46 : kind(kind0),
47 size(size0),
48 addr1(addr1_0),
49 addr2(addr2_0),
50 insert(NULL) {
51 CHECK(kind == MOVE || kind == COPY || kind == COPYOVER);
52 }
53
54 Kind kind;
55 xoff_t size;
56 xoff_t addr1;
57 xoff_t addr2;
58 Segment *insert; // For modify and/or add
59 };
60
61 typedef list<Change> ChangeList;
62 typedef typename ChangeList::const_iterator ConstChangeListIterator;
63 typedef typename ChangeList::iterator ChangeListIterator;
64
65 class ChangeListMutator : public Mutator {
66 public:
67 ChangeListMutator(const ChangeList &cl)
68 : cl_(cl) { }
69
70 ChangeListMutator() { }
71
72 void Mutate(SegmentMap *table,
73 const SegmentMap *source_table,
74 MTRandom *rand) const {
75 // The speed of processing gigabytes of data is so slow compared with
76 // these table-copy operations, no attempt to make this fast.
77 SegmentMap tmp;
78
79 for (ConstChangeListIterator iter(cl_.begin());
80 iter != cl_.end(); ++iter) {
81 const Change &ch = *iter;
82 tmp.clear();
83 Mutate(ch, &tmp, source_table, rand);
84 tmp.swap(*table);
85 source_table = table;
86 }
87 }
88
89 static void Mutate(const Change &ch,
90 SegmentMap *table,
91 const SegmentMap *source_table,
92 MTRandom *rand) {
93 switch (ch.kind) {
94 case Change::ADD:
95 AddChange(ch, table, source_table, rand);
96 break;
97 case Change::MODIFY:
98 ModifyChange(ch, table, source_table, rand);
99 break;
100 case Change::DELRANGE:
101 DeleteChange(ch, table, source_table, rand);
102 break;
103 case Change::COPY:
104 CopyChange(ch, table, source_table, rand);
105 break;
106 case Change::MOVE:
107 MoveChange(ch, table, source_table, rand);
108 break;
109 case Change::COPYOVER:
110 OverwriteChange(ch, table, source_table, rand);
111 break;
112 }
113 }
114
115 static void ModifyChange(const Change &ch,
116 SegmentMap *table,
117 const SegmentMap *source_table,
118 MTRandom *rand) {
119 xoff_t m_start = ch.addr1;
120 xoff_t m_end = m_start + ch.size;
121 xoff_t i_start = 0;
122 xoff_t i_end = 0;
123
124 for (ConstSegmentMapIterator iter(source_table->begin());
125 iter != source_table->end();
126 ++iter) {
127 const Segment &seg = iter->second;
128 i_start = iter->first;
129 i_end = i_start + seg.Size();
130
131 if (i_end <= m_start || i_start >= m_end) {
132 table->insert(table->end(), make_pair(i_start, seg));
133 continue;
134 }
135
136 if (i_start < m_start) {
137 table->insert(table->end(),
138 make_pair(i_start,
139 seg.Subseg(0, m_start - i_start)));
140 }
141
142 // Insert the entire segment, even though it may extend into later
143 // segments. This condition avoids inserting it during later
144 // segments.
145 if (m_start >= i_start) {
146 if (ch.insert != NULL) {
147 table->insert(table->end(), make_pair(m_start, *ch.insert));
148 } else {
149 Segment part(m_end - m_start, rand);
150 table->insert(table->end(), make_pair(m_start, part));
151 }
152 }
153
154 if (i_end > m_end) {
155 table->insert(table->end(),
156 make_pair(m_end,
157 seg.Subseg(m_end - i_start, i_end - m_end)));
158 }
159 }
160
161 // This check verifies that the modify does not extend past the
162 // source_table EOF.
163 CHECK_LE(m_end, i_end);
164 }
165
166 static void AddChange(const Change &ch,
167 SegmentMap *table,
168 const SegmentMap *source_table,
169 MTRandom *rand) {
170 xoff_t m_start = ch.addr1;
171 xoff_t i_start = 0;
172 xoff_t i_end = 0;
173
174 for (ConstSegmentMapIterator iter(source_table->begin());
175 iter != source_table->end();
176 ++iter) {
177 const Segment &seg = iter->second;
178 i_start = iter->first;
179 i_end = i_start + seg.Size();
180
181 if (i_end <= m_start) {
182 table->insert(table->end(), make_pair(i_start, seg));
183 continue;
184 }
185
186 if (i_start > m_start) {
187 table->insert(table->end(), make_pair(i_start + ch.size, seg));
188 continue;
189 }
190
191 if (i_start < m_start) {
192 table->insert(table->end(),
193 make_pair(i_start,
194 seg.Subseg(0, m_start - i_start)));
195 }
196
197 if (ch.insert != NULL) {
198 table->insert(table->end(), make_pair(m_start, *ch.insert));
199 } else {
200 Segment addseg(ch.size, rand);
201 table->insert(table->end(), make_pair(m_start, addseg));
202 }
203
204 if (m_start < i_end) {
205 table->insert(table->end(),
206 make_pair(m_start + ch.size,
207 seg.Subseg(m_start - i_start,
208 i_end - m_start)));
209 }
210 }
211
212 CHECK_LE(m_start, i_end);
213
214 // Special case for add at end-of-input.
215 if (m_start == i_end) {
216 Segment addseg(ch.size, rand);
217 table->insert(table->end(), make_pair(m_start, addseg));
218 }
219 }
220
221 static void DeleteChange(const Change &ch,
222 SegmentMap *table,
223 const SegmentMap *source_table,
224 MTRandom *rand) {
225 xoff_t m_start = ch.addr1;
226 xoff_t m_end = m_start + ch.size;
227 xoff_t i_start = 0;
228 xoff_t i_end = 0;
229
230 for (ConstSegmentMapIterator iter(source_table->begin());
231 iter != source_table->end();
232 ++iter) {
233 const Segment &seg = iter->second;
234 i_start = iter->first;
235 i_end = i_start + seg.Size();
236
237 if (i_end <= m_start) {
238 table->insert(table->end(), make_pair(i_start, seg));
239 continue;
240 }
241
242 if (i_start >= m_end) {
243 table->insert(table->end(), make_pair(i_start - ch.size, seg));
244 continue;
245 }
246
247 if (i_start < m_start) {
248 table->insert(table->end(),
249 make_pair(i_start,
250 seg.Subseg(0, m_start - i_start)));
251 }
252
253 if (i_end > m_end) {
254 table->insert(table->end(),
255 make_pair(m_end - ch.size,
256 seg.Subseg(m_end - i_start, i_end - m_end)));
257 }
258 }
259
260 CHECK_LT(m_start, i_end);
261 CHECK_LE(m_end, i_end);
262 }
263
264 // A move is a copy followed by delete of the copied-from range.
265 static void MoveChange(const Change &ch,
266 SegmentMap *table,
267 const SegmentMap *source_table,
268 MTRandom *rand) {
269 SegmentMap tmp;
270 CHECK_NE(ch.addr1, ch.addr2);
271 CopyChange(ch, &tmp, source_table, rand);
272 Change d(Change::DELRANGE, ch.size,
273 ch.addr1 < ch.addr2 ? ch.addr1 : ch.addr1 + ch.size);
274 DeleteChange(d, table, &tmp, rand);
275 }
276
277 // An overwrite is a copy followed by a delete of the copied-to range.
278 static void OverwriteChange(const Change &ch,
279 SegmentMap *table,
280 const SegmentMap *source_table,
281 MTRandom *rand) {
282 SegmentMap tmp;
283 CHECK_NE(ch.addr1, ch.addr2);
284 CopyChange(ch, &tmp, source_table, rand);
285 Change d(Change::DELRANGE, ch.size, ch.addr2 + ch.size);
286 DeleteChange(d, table, &tmp, rand);
287 }
288
289 static void CopyChange(const Change &ch,
290 SegmentMap *table,
291 const SegmentMap *source_table,
292 MTRandom *ignore) {
293 xoff_t m_start = ch.addr2;
294 xoff_t c_start = ch.addr1;
295 xoff_t i_start = 0;
296 xoff_t i_end = 0;
297
298 // Like AddChange() with AppendCopy instead of a random segment.
299 for (ConstSegmentMapIterator iter(source_table->begin());
300 iter != source_table->end();
301 ++iter) {
302 const Segment &seg = iter->second;
303 i_start = iter->first;
304 i_end = i_start + seg.Size();
305
306 if (i_end <= m_start) {
307 table->insert(table->end(), make_pair(i_start, seg));
308 continue;
309 }
310
311 if (i_start > m_start) {
312 table->insert(table->end(), make_pair(i_start + ch.size, seg));
313 continue;
314 }
315
316 if (i_start < m_start) {
317 table->insert(table->end(),
318 make_pair(i_start,
319 seg.Subseg(0, m_start - i_start)));
320 }
321
322 AppendCopy(table, source_table, c_start, m_start, ch.size);
323
324 if (m_start < i_end) {
325 table->insert(table->end(),
326 make_pair(m_start + ch.size,
327 seg.Subseg(m_start - i_start, i_end - m_start)));
328 }
329 }
330
331 CHECK_LE(m_start, i_end);
332
333 // Special case for copy to end-of-input.
334 if (m_start == i_end) {
335 AppendCopy(table, source_table, c_start, m_start, ch.size);
336 }
337 }
338
339 static void AppendCopy(SegmentMap *table,
340 const SegmentMap *source_table,
341 xoff_t copy_offset,
342 xoff_t append_offset,
343 xoff_t length) {
344 ConstSegmentMapIterator pos(source_table->upper_bound(copy_offset));
345 --pos;
346 xoff_t got = 0;
347
348 while (got < length) {
349 size_t seg_offset = copy_offset - pos->first;
350 size_t advance = min(pos->second.Size() - seg_offset,
351 (size_t)(length - got));
352
353 table->insert(table->end(),
354 make_pair(append_offset,
355 pos->second.Subseg(seg_offset,
356 advance)));
357
358 got += advance;
359 copy_offset += advance;
360 append_offset += advance;
361 ++pos;
362 }
363 }
364
365 ChangeList* Changes() {
366 return &cl_;
367 }
368
369 const ChangeList* Changes() const {
370 return &cl_;
371 }
372
373 private:
374 ChangeList cl_;
375 };
376
377 class Modify1stByte : public Mutator {
378 public:
379 void Mutate(SegmentMap *table,
380 const SegmentMap *source_table,
381 MTRandom *rand) const {
382 ChangeListMutator::Mutate(Change(Change::MODIFY, 1, 0),
383 table, source_table, rand);
384 }
385 };