Import from upstream 3.1.0

1 files changed, 385 insertions, 0 deletions

diff --git a/testing/modify.h b/testing/modify.h
new file mode 100644
index 0000000..93f7bde
--- /dev/null
+++ b/testing/modify.h
@@ -0,0 +1,385 @@
+// -*- 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
+    DELRANGE = 3,     // Delete a specified range of data
+    COPY = 4,       // Copy from one region, inserting elsewhere
+    MOVE = 5,       // Copy then delete copied-from range
+    COPYOVER = 6    // Copy then delete copied-to range
+
+    // ADD, DELRANGE, and COPY change the file size
+    // MODIFY, MOVE, COPYOVER 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 != COPYOVER);
+  }
+
+  // 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 != COPYOVER);
+  }
+
+  // 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 == COPYOVER);
+  }
+
+  Kind kind;
+  xoff_t size;
+  xoff_t addr1;
+  xoff_t addr2;
+  Segment *insert;  // For modify and/or add
+};
+
+typedef list<Change> 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::DELRANGE:
+      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::COPYOVER:
+      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::DELRANGE, 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::DELRANGE, 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);
+  }
+};