view mercurial/bdiff.h @ 39492:a33f394b2bfd

snapshot: try intermediate snapshot against parents' base

# Regarding The Series Started By This Changeset

This is the first changesets of a group adjusting delta chain strategy to
build a useful chain of intermediate snapshots. The series will introduce a
full strategy to produce chains of multiple snapshots on top of which a
"usual" delta chain will be built.

That strategy will have multiple steps to maximize snapshot reuse, avoiding
pathological cases and improving overall compression in very branchy
repositories. An important property of sparse-revlog using such snapshot-chain
is that they can use very short delta chain without problematic impact on the
resulting compression. Shorter delta chains are important to achieve good
performance.

To make each step clear, we'll introduce them one by one.

See the end of this series for full details.

# Regarding This Changeset

Before this change, if we cannot store the current revision as a delta against
a "simple" candidate (p1, p2, prev), we created a new level-0 snapshot (also
called full snapshot).

As the first step, we introduce a simple strategy: try an intermediate level-1
snapshot against the chain base of the "current revision" parents.
The "current revision" is the one we are currently trying to store in the
revlog, triggering this search for a good delta base.
The first item in the chain is always a level-0 snapshot.

# Effect On The Test Repository

We can already see the effect on the test-repository. Most of the snapshots
have shifted from level 0 to level 1. The overall size has slightly decreased.
(However, keep in mind that this repository only emulates real data)

# Regarding Statistic

The current series focuses on improving the chain built. Improving the
performance of this logic will be done as a second step. Sparse-revlog is
still experimental and disabled by default.

We'll provide more statistic about resulting size and delta chain at the end
of this series.

#ifndef _HG_BDIFF_H_
#define _HG_BDIFF_H_

#include "compat.h"

struct bdiff_line {
	int hash, n, e;
	ssize_t len;
	const char *l;
};

struct bdiff_hunk;
struct bdiff_hunk {
	int a1, a2, b1, b2;
	struct bdiff_hunk *next;
};

int bdiff_splitlines(const char *a, ssize_t len, struct bdiff_line **lr);
int bdiff_diff(struct bdiff_line *a, int an, struct bdiff_line *b, int bn,
               struct bdiff_hunk *base);
void bdiff_freehunks(struct bdiff_hunk *l);

#endif