view mercurial/bdiff.h @ 40642:9c3c697267db

sparse-revlog: rework the way we enforce chunk size limit

We move from a O(N) algorithm to a O(log(N)) algorithm.

The previous algorithm was traversing the whole delta chain, looking for the
exact point where it became too big. This would result in most of the delta
chain to be traversed.

Instead, we now use a "binary" approach, slicing the chain in two until we
have a chunk of the appropriate size.

We still keep the previous algorithm for the snapshots part. There are few of
them and they are large bits of data distant from each other. So the previous
algorithm should work well in that case.

To take a practical example of restoring manifest revision '59547c40bc4c' for
a reference NetBeans repository (using sparse-revlog). The media time of the
step `slice-sparse-chain` of `perfrevlogrevision` improve from 1.109 ms to
0.660 ms.

#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