git/diff-delta.c, branch v1.6.2

fix style of a few comments in diff-delta.c

2007-12-18T23:22:28Z

Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano

Fix segfault in diff-delta.c when FLEX_ARRAY is 1

2007-12-18T05:59:26Z

aka don't do pointer arithmetics on structs that have a FLEX_ARRAY member, or you'll end up believing your array is 1 cell off its real address. Signed-off-by: Pierre Habouzit Signed-off-by: Junio C Hamano

diff-delta.c: Rationalize culling of hash buckets

2007-09-10T00:16:49Z

The previous hash bucket culling resulted in a somewhat unpredictable number of hash bucket entries in the order of magnitude of HASH_LIMIT. Replace this with a Bresenham-like algorithm leaving us with exactly HASH_LIMIT entries by uniform culling. Signed-off-by: David Kastrup Acked-by: Nicolas Pitre Signed-off-by: Junio C Hamano

diff-delta.c: pack the index structure

2007-09-10T00:16:49Z

In normal use cases, the performance wins are not overly impressive: we get something like 5-10% due to the slightly better locality of memory accesses using the packed structure. However, since the data structure for index entries saves 33% of memory on 32-bit platforms and 40% on 64-bit platforms, the behavior when memory gets limited should be nicer. This is a rather well-contained change. One obvious improvement would be sorting the elements in one bucket according to their hash, then using binary probing to find the elements with the right hash value. As it stands, the output should be strictly the same as previously unless one uses the option for limiting the amount of used memory, in which case the created packs might be better. Signed-off-by: David Kastrup Acked-by: Nicolas Pitre Signed-off-by: Junio C Hamano

diff-delta.c: Fix broken skip calculation.

2007-08-23T07:04:10Z

A particularly bad case was HASH_LIMIT <= hash_count[i] < 2*HASH_LIMIT: in that case, only a single hash survived. For larger cases, 2*HASH_LIMIT was the actual limiting value after pruning. Signed-off-by: David Kastrup Acked-by: Nicolas Pitre Signed-off-by: Junio C Hamano

Support fetching the memory usage of a delta index

2007-07-12T21:32:35Z

Delta indices, at least on 64-bit platforms, tend to be larger than the actual uncompressed data. As such, keeping track of this storage is important if you want to successfully limit the memory size of your pack window. Squirrel away the total allocation size inside the delta_index struct, and add an accessor "sizeof_delta_index" to access it. Signed-off-by: Brian Downing Acked-by: Nicolas Pitre Signed-off-by: Junio C Hamano

diff-delta: use realloc instead of xrealloc

2007-05-31T07:15:18Z

Commit 83572c1a914d3f7a8dd66d954c11bbc665b7b923 changed many realloc to xrealloc. This change was made in diff-delta.c too, although the code can handle an out of memory failure. This patch reverts this change in diff-delta.c. Signed-off-by: Martin Koegler Signed-off-by: Junio C Hamano

update diff-delta.c copyright

2007-05-27T03:28:13Z

There is actually nothing left from the original LibXDiff code I used over 2 years ago, and even the GIT implementation has diverged quite a bit from LibXDiff's at this point. Let's update the copyright notice to better reflect that fact. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano

improve delta long block matching with big files

2007-05-27T03:28:13Z

Martin Koegler noted that create_delta() performs a new hash lookup after every block copy encoding which are currently limited to 64KB. In case of larger identical blocks, the next hash lookup would normally point to the next 64KB block in the reference buffer and multiple block copy operations will be consecutively encoded. It is however possible that the reference buffer be sparsely indexed if hash buckets have been trimmed down in create_delta_index() when hashing of the reference buffer isn't well balanced. In that case the hash lookup following a block copy might fail to match anything and the fact that the reference buffer still matches beyond the previous 64KB block will be missed. Let's rework the code so that buffer comparison isn't bounded to 64KB anymore. The match size should be as large as possible up front and only then should multiple block copy be encoded to cover it all. Also, fewer hash lookups will be performed in the end. According to Martin, this patch should reduce his 92MB pack down to 75MB with the dataset he has. Tests performed on the Linux kernel repo show a slightly smaller pack and a slightly faster repack. Signed-off-by: Nicolas Pitre Signed-off-by: Junio C Hamano

simplify inclusion of system header files.

2006-12-20T17:51:35Z

This is a mechanical clean-up of the way *.c files include system header files. (1) sources under compat/, platform sha-1 implementations, and xdelta code are exempt from the following rules; (2) the first #include must be "git-compat-util.h" or one of our own header file that includes it first (e.g. config.h, builtin.h, pkt-line.h); (3) system headers that are included in "git-compat-util.h" need not be included in individual C source files. (4) "git-compat-util.h" does not have to include subsystem specific header files (e.g. expat.h). Signed-off-by: Junio C Hamano