Sophie

Sophie

distrib > Mageia > 3 > x86_64 > by-pkgid > ed855f7c18d8f7387426873c5d69401e > files > 943

bzr-2.5.1-3.3.mga3.x86_64.rpm

Bundle Creation
===============
1. Find common ancestor [O(a)] **O(b)**
2. Emit bundle [O(a)] **O(b) O(h)**

  Per revision

  1. emit metadata O(1)
  2. emit changes for files

    1. find changed files [O(c)] **O(f)**
    2. emit file metadata O(d)
    3. emit diff [O(e * e) * O(f) + O(h)] **O(i)**
    4. base64 encode O(g)

3. **emit overal diff (or maybe do interdiff) O(e * e) * O(f)**

:a: nodes in revision graph
:b: number of descendants of common ancestor
:c: number of files in the tree
:d: length of metadata
:e: number of lines
:f: number of modified files
:g: length of diff
:h: nodes in knit graph of modified files
:i: length of stored diff

Needs
-----
- Improved common ancestor algorithm
- Access to partial revision graph proportional to relevant revisions
- Access to changed files proportional to number of change files and
  intervening revisions
- Use knit deltas without recomputing
- Access to knit deltas in O(1) time
- Access to snapshots in O(1) amortized time
- All snapshots must have knit deltas