Logo Search packages:      
Sourcecode: xdelta3 version File versions  Download package

modify.h

// -*- 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,
    ADD = 2,
    DELETE = 3,
    MOVE = 4,
    COPY = 5,
    OVERWRITE = 6,
  };

  // Constructor for modify, add, delete.
  Change(Kind kind, xoff_t size, xoff_t addr1)
    : kind(kind),
      size(size),
      addr1(addr1),
      insert(NULL) { 
    CHECK(kind != MOVE && kind != COPY && kind != OVERWRITE);
  }

  // Constructor for modify, add w/ provided data.
  Change(Kind kind, xoff_t size, xoff_t addr1, Segment *insert)
    : kind(kind),
      size(size),
      addr1(addr1),
      insert(insert) { 
    CHECK(kind != MOVE && kind != COPY && kind != OVERWRITE);
  }

  // Constructor for move
  Change(Kind kind, xoff_t size, xoff_t addr1, xoff_t addr2)
    : kind(kind),
      size(size),
      addr1(addr1),
      addr2(addr2),
      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<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::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);
  }

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

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

Generated by  Doxygen 1.6.0   Back to index