// -*- Mode: C++ -*- class Mutator { public: virtual ~Mutator() { } virtual void Mutate(SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) const = 0; }; class Change { public: enum Kind { MODIFY = 1, // Mutate a certain range w/ random or supplied data ADD = 2, // Insert random or supplied data DELETE = 3, // Delete a specified range of data COPY = 4, // Copy from one region, inserting elsewhere MOVE = 5, // Copy then delete copied-from range OVERWRITE = 6 // Copy then delete copied-to range // ADD, DELETE, and COPY change the file size // MODIFY, MOVE, OVERWRITE preserve the file size }; // Constructor for modify, add, delete. Change(Kind kind0, xoff_t size0, xoff_t addr1_0) : kind(kind0), size(size0), addr1(addr1_0), addr2(0), insert(NULL) { CHECK(kind != MOVE && kind != COPY && kind != OVERWRITE); } // Constructor for modify, add w/ provided data. Change(Kind kind0, xoff_t size0, xoff_t addr1_0, Segment *insert0) : kind(kind0), size(size0), addr1(addr1_0), addr2(0), insert(insert0) { CHECK(kind != MOVE && kind != COPY && kind != OVERWRITE); } // Constructor for move, copy, overwrite Change(Kind kind0, xoff_t size0, xoff_t addr1_0, xoff_t addr2_0) : kind(kind0), size(size0), addr1(addr1_0), addr2(addr2_0), insert(NULL) { CHECK(kind == MOVE || kind == COPY || kind == OVERWRITE); } Kind kind; xoff_t size; xoff_t addr1; xoff_t addr2; Segment *insert; // For modify and/or add }; typedef list ChangeList; typedef typename ChangeList::const_iterator ConstChangeListIterator; typedef typename ChangeList::iterator ChangeListIterator; class ChangeListMutator : public Mutator { public: ChangeListMutator(const ChangeList &cl) : cl_(cl) { } ChangeListMutator() { } void Mutate(SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) const { // The speed of processing gigabytes of data is so slow compared with // these table-copy operations, no attempt to make this fast. SegmentMap tmp; for (ConstChangeListIterator iter(cl_.begin()); iter != cl_.end(); ++iter) { const Change &ch = *iter; tmp.clear(); Mutate(ch, &tmp, source_table, rand); tmp.swap(*table); source_table = table; } } static void Mutate(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) { switch (ch.kind) { case Change::ADD: AddChange(ch, table, source_table, rand); break; case Change::MODIFY: ModifyChange(ch, table, source_table, rand); break; case Change::DELETE: DeleteChange(ch, table, source_table, rand); break; case Change::COPY: CopyChange(ch, table, source_table, rand); break; case Change::MOVE: MoveChange(ch, table, source_table, rand); break; case Change::OVERWRITE: OverwriteChange(ch, table, source_table, rand); break; } } static void ModifyChange(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) { xoff_t m_start = ch.addr1; xoff_t m_end = m_start + ch.size; xoff_t i_start = 0; xoff_t i_end = 0; for (ConstSegmentMapIterator iter(source_table->begin()); iter != source_table->end(); ++iter) { const Segment &seg = iter->second; i_start = iter->first; i_end = i_start + seg.Size(); if (i_end <= m_start || i_start >= m_end) { table->insert(table->end(), make_pair(i_start, seg)); continue; } if (i_start < m_start) { table->insert(table->end(), make_pair(i_start, seg.Subseg(0, m_start - i_start))); } // Insert the entire segment, even though it may extend into later // segments. This condition avoids inserting it during later // segments. if (m_start >= i_start) { if (ch.insert != NULL) { table->insert(table->end(), make_pair(m_start, *ch.insert)); } else { Segment part(m_end - m_start, rand); table->insert(table->end(), make_pair(m_start, part)); } } if (i_end > m_end) { table->insert(table->end(), make_pair(m_end, seg.Subseg(m_end - i_start, i_end - m_end))); } } // This check verifies that the modify does not extend past the // source_table EOF. CHECK_LE(m_end, i_end); } static void AddChange(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) { xoff_t m_start = ch.addr1; xoff_t i_start = 0; xoff_t i_end = 0; for (ConstSegmentMapIterator iter(source_table->begin()); iter != source_table->end(); ++iter) { const Segment &seg = iter->second; i_start = iter->first; i_end = i_start + seg.Size(); if (i_end <= m_start) { table->insert(table->end(), make_pair(i_start, seg)); continue; } if (i_start > m_start) { table->insert(table->end(), make_pair(i_start + ch.size, seg)); continue; } if (i_start < m_start) { table->insert(table->end(), make_pair(i_start, seg.Subseg(0, m_start - i_start))); } if (ch.insert != NULL) { table->insert(table->end(), make_pair(m_start, *ch.insert)); } else { Segment addseg(ch.size, rand); table->insert(table->end(), make_pair(m_start, addseg)); } if (m_start < i_end) { table->insert(table->end(), make_pair(m_start + ch.size, seg.Subseg(m_start - i_start, i_end - m_start))); } } CHECK_LE(m_start, i_end); // Special case for add at end-of-input. if (m_start == i_end) { Segment addseg(ch.size, rand); table->insert(table->end(), make_pair(m_start, addseg)); } } static void DeleteChange(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) { xoff_t m_start = ch.addr1; xoff_t m_end = m_start + ch.size; xoff_t i_start = 0; xoff_t i_end = 0; for (ConstSegmentMapIterator iter(source_table->begin()); iter != source_table->end(); ++iter) { const Segment &seg = iter->second; i_start = iter->first; i_end = i_start + seg.Size(); if (i_end <= m_start) { table->insert(table->end(), make_pair(i_start, seg)); continue; } if (i_start >= m_end) { table->insert(table->end(), make_pair(i_start - ch.size, seg)); continue; } if (i_start < m_start) { table->insert(table->end(), make_pair(i_start, seg.Subseg(0, m_start - i_start))); } if (i_end > m_end) { table->insert(table->end(), make_pair(m_end - ch.size, seg.Subseg(m_end - i_start, i_end - m_end))); } } CHECK_LT(m_start, i_end); CHECK_LE(m_end, i_end); } // A move is a copy followed by delete of the copied-from range. static void MoveChange(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) { SegmentMap tmp; CHECK_NE(ch.addr1, ch.addr2); CopyChange(ch, &tmp, source_table, rand); Change d(Change::DELETE, ch.size, ch.addr1 < ch.addr2 ? ch.addr1 : ch.addr1 + ch.size); DeleteChange(d, table, &tmp, rand); } // An overwrite is a copy followed by a delete of the copied-to range. static void OverwriteChange(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) { SegmentMap tmp; CHECK_NE(ch.addr1, ch.addr2); CopyChange(ch, &tmp, source_table, rand); Change d(Change::DELETE, ch.size, ch.addr2 + ch.size); DeleteChange(d, table, &tmp, rand); } static void CopyChange(const Change &ch, SegmentMap *table, const SegmentMap *source_table, MTRandom *ignore) { xoff_t m_start = ch.addr2; xoff_t c_start = ch.addr1; xoff_t i_start = 0; xoff_t i_end = 0; // Like AddChange() with AppendCopy instead of a random segment. for (ConstSegmentMapIterator iter(source_table->begin()); iter != source_table->end(); ++iter) { const Segment &seg = iter->second; i_start = iter->first; i_end = i_start + seg.Size(); if (i_end <= m_start) { table->insert(table->end(), make_pair(i_start, seg)); continue; } if (i_start > m_start) { table->insert(table->end(), make_pair(i_start + ch.size, seg)); continue; } if (i_start < m_start) { table->insert(table->end(), make_pair(i_start, seg.Subseg(0, m_start - i_start))); } AppendCopy(table, source_table, c_start, m_start, ch.size); if (m_start < i_end) { table->insert(table->end(), make_pair(m_start + ch.size, seg.Subseg(m_start - i_start, i_end - m_start))); } } CHECK_LE(m_start, i_end); // Special case for copy to end-of-input. if (m_start == i_end) { AppendCopy(table, source_table, c_start, m_start, ch.size); } } static void AppendCopy(SegmentMap *table, const SegmentMap *source_table, xoff_t copy_offset, xoff_t append_offset, xoff_t length) { ConstSegmentMapIterator pos(source_table->upper_bound(copy_offset)); --pos; xoff_t got = 0; while (got < length) { size_t seg_offset = copy_offset - pos->first; size_t advance = min(pos->second.Size() - seg_offset, (size_t)(length - got)); table->insert(table->end(), make_pair(append_offset, pos->second.Subseg(seg_offset, advance))); got += advance; copy_offset += advance; append_offset += advance; ++pos; } } ChangeList* Changes() { return &cl_; } const ChangeList* Changes() const { return &cl_; } private: ChangeList cl_; }; class Modify1stByte : public Mutator { public: void Mutate(SegmentMap *table, const SegmentMap *source_table, MTRandom *rand) const { ChangeListMutator::Mutate(Change(Change::MODIFY, 1, 0), table, source_table, rand); } };