Git development
 help / color / mirror / Atom feed
* [PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}
From: David Kastrup @ 2007-09-08  8:54 UTC (permalink / raw)
  To: git
In-Reply-To: <0cd39105dcd57a60eca290db598613aafcc8c577.1189243702.git.dak@gnu.org>

The variables for the packed entries are now called just entry and
hash rather than aentry+ahash, and those for the unpacked entries have
been renamed to uentry and uhash from the original entry and hash.

While this makes the diff to the unchanged code larger, it matches the
type declarations better.

Signed-off-by: David Kastrup <dak@gnu.org>
---
 diff-delta.c |   65 ++++++++++++++++++++++++++++-----------------------------
 1 files changed, 32 insertions(+), 33 deletions(-)

diff --git a/diff-delta.c b/diff-delta.c
index 1b4b1c1..e7c33aa 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -135,8 +135,8 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
 	const unsigned char *data, *buffer = buf;
 	struct delta_index *index;
-	struct unpacked_index_entry *entry, **hash;
-	struct index_entry *aentry, **ahash;
+	struct unpacked_index_entry *uentry, **uhash;
+	struct index_entry *entry, **hash;
 	void *mem;
 	unsigned long memsize;
 
@@ -153,21 +153,21 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	hmask = hsize - 1;
 
 	/* allocate lookup index */
-	memsize = sizeof(*hash) * hsize +
-		  sizeof(*entry) * entries;
+	memsize = sizeof(*uhash) * hsize +
+		  sizeof(*uentry) * entries;
 	mem = malloc(memsize);
 	if (!mem)
 		return NULL;
-	hash = mem;
-	mem = hash + hsize;
-	entry = mem;
+	uhash = mem;
+	mem = uhash + hsize;
+	uentry = mem;
 
-	memset(hash, 0, hsize * sizeof(*hash));
+	memset(uhash, 0, hsize * sizeof(*uhash));
 
 	/* allocate an array to count hash entries */
 	hash_count = calloc(hsize, sizeof(*hash_count));
 	if (!hash_count) {
-		free(hash);
+		free(uhash);
 		return NULL;
 	}
 
@@ -181,15 +181,15 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 			val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 		if (val == prev_val) {
 			/* keep the lowest of consecutive identical blocks */
-			entry[-1].entry.ptr = data + RABIN_WINDOW;
+			uentry[-1].entry.ptr = data + RABIN_WINDOW;
 			--entries;
 		} else {
 			prev_val = val;
 			i = val & hmask;
-			entry->entry.ptr = data + RABIN_WINDOW;
-			entry->entry.val = val;
-			entry->next = hash[i];
-			hash[i] = entry++;
+			uentry->entry.ptr = data + RABIN_WINDOW;
+			uentry->entry.val = val;
+			uentry->next = uhash[i];
+			uhash[i] = uentry++;
 			hash_count[i]++;
 		}
 	}
@@ -209,17 +209,17 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	for (i = 0; i < hsize; i++) {
 		if (hash_count[i] < HASH_LIMIT)
 			continue;
-		entry = hash[i];
+		uentry = uhash[i];
 		do {
-			struct unpacked_index_entry *keep = entry;
+			struct unpacked_index_entry *keep = uentry;
 			int skip = hash_count[i] / HASH_LIMIT;
 			do {
 				--entries;
-				entry = entry->next;
-			} while(--skip && entry);
+				uentry = uentry->next;
+			} while(--skip && uentry);
 			++entries;
-			keep->next = entry;
-		} while(entry);
+			keep->next = uentry;
+		} while(uentry);
 	}
 	free(hash_count);
 
@@ -227,13 +227,12 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	 * linked lists */
 
 	memsize = sizeof(*index)
-		+ sizeof(*ahash) * (hsize+1)
-		+ sizeof(*aentry) * entries;
-
+		+ sizeof(*hash) * (hsize+1)
+		+ sizeof(*entry) * entries;
 	mem = malloc(memsize);
 
 	if (!mem) {
-		free(hash);
+		free(uhash);
 		return NULL;
 	}
 
@@ -244,25 +243,25 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	index->hash_mask = hmask;
 
 	mem = index + 1;
-	ahash = mem;
-	mem = ahash + (hsize+1);
-	aentry = mem;
+	hash = mem;
+	mem = hash + (hsize+1);
+	entry = mem;
 
 	/* Coalesce all entries belonging to one linked list into
 	 * consecutive array entries */
 
 	for (i = 0; i < hsize; i++) {
-		ahash[i] = aentry;
-		for (entry = hash[i]; entry; entry = entry->next)
-			*aentry++ = entry->entry;
+		hash[i] = entry;
+		for (uentry = uhash[i]; uentry; uentry = uentry->next)
+			*entry++ = uentry->entry;
 	}
 
 	/* Sentinel value to indicate the length of the last hash
 	 * bucket */
 
-	ahash[hsize] = aentry;
-	assert(aentry - (struct index_entry *)mem == entries);
-	free(hash);
+	hash[hsize] = entry;
+	assert(entry - (struct index_entry *)mem == entries);
+	free(uhash);
 
 	return index;
 }
-- 
1.5.3.GIT

^ permalink raw reply related

* [PATCH] diff-delta.c: pack the index structure
From: David Kastrup @ 2007-09-08  9:31 UTC (permalink / raw)
  To: git

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 <dak@gnu.org>
---
 diff-delta.c |   74 +++++++++++++++++++++++++++++++++++++++++++++------------
 1 files changed, 58 insertions(+), 16 deletions(-)

diff --git a/diff-delta.c b/diff-delta.c
index 0dde2f2..1b4b1c1 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -115,9 +115,13 @@ static const unsigned int U[256] = {
 struct index_entry {
 	const unsigned char *ptr;
 	unsigned int val;
-	struct index_entry *next;
 };
 
+struct unpacked_index_entry {
+	struct index_entry entry;
+	struct unpacked_index_entry *next;
+};	
+
 struct delta_index {
 	unsigned long memsize;
 	const void *src_buf;
@@ -131,7 +135,8 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
 	const unsigned char *data, *buffer = buf;
 	struct delta_index *index;
-	struct index_entry *entry, **hash;
+	struct unpacked_index_entry *entry, **hash;
+	struct index_entry *aentry, **ahash;
 	void *mem;
 	unsigned long memsize;
 
@@ -148,28 +153,21 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	hmask = hsize - 1;
 
 	/* allocate lookup index */
-	memsize = sizeof(*index) +
-		  sizeof(*hash) * hsize +
+	memsize = sizeof(*hash) * hsize +
 		  sizeof(*entry) * entries;
 	mem = malloc(memsize);
 	if (!mem)
 		return NULL;
-	index = mem;
-	mem = index + 1;
 	hash = mem;
 	mem = hash + hsize;
 	entry = mem;
 
-	index->memsize = memsize;
-	index->src_buf = buf;
-	index->src_size = bufsize;
-	index->hash_mask = hmask;
 	memset(hash, 0, hsize * sizeof(*hash));
 
 	/* allocate an array to count hash entries */
 	hash_count = calloc(hsize, sizeof(*hash_count));
 	if (!hash_count) {
-		free(index);
+		free(hash);
 		return NULL;
 	}
 
@@ -183,12 +181,13 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 			val = ((val << 8) | data[i]) ^ T[val >> RABIN_SHIFT];
 		if (val == prev_val) {
 			/* keep the lowest of consecutive identical blocks */
-			entry[-1].ptr = data + RABIN_WINDOW;
+			entry[-1].entry.ptr = data + RABIN_WINDOW;
+			--entries;
 		} else {
 			prev_val = val;
 			i = val & hmask;
-			entry->ptr = data + RABIN_WINDOW;
-			entry->val = val;
+			entry->entry.ptr = data + RABIN_WINDOW;
+			entry->entry.val = val;
 			entry->next = hash[i];
 			hash[i] = entry++;
 			hash_count[i]++;
@@ -212,16 +211,59 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 			continue;
 		entry = hash[i];
 		do {
-			struct index_entry *keep = entry;
+			struct unpacked_index_entry *keep = entry;
 			int skip = hash_count[i] / HASH_LIMIT;
 			do {
+				--entries;
 				entry = entry->next;
 			} while(--skip && entry);
+			++entries;
 			keep->next = entry;
 		} while(entry);
 	}
 	free(hash_count);
 
+	/* Now create the packed index in array form rather than
+	 * linked lists */
+
+	memsize = sizeof(*index)
+		+ sizeof(*ahash) * (hsize+1)
+		+ sizeof(*aentry) * entries;
+
+	mem = malloc(memsize);
+
+	if (!mem) {
+		free(hash);
+		return NULL;
+	}
+
+	index = mem;
+	index->memsize = memsize;
+	index->src_buf = buf;
+	index->src_size = bufsize;
+	index->hash_mask = hmask;
+
+	mem = index + 1;
+	ahash = mem;
+	mem = ahash + (hsize+1);
+	aentry = mem;
+
+	/* Coalesce all entries belonging to one linked list into
+	 * consecutive array entries */
+
+	for (i = 0; i < hsize; i++) {
+		ahash[i] = aentry;
+		for (entry = hash[i]; entry; entry = entry->next)
+			*aentry++ = entry->entry;
+	}
+
+	/* Sentinel value to indicate the length of the last hash
+	 * bucket */
+
+	ahash[hsize] = aentry;
+	assert(aentry - (struct index_entry *)mem == entries);
+	free(hash);
+
 	return index;
 }
 
@@ -302,7 +344,7 @@ create_delta(const struct delta_index *index,
 			val ^= U[data[-RABIN_WINDOW]];
 			val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 			i = val & index->hash_mask;
-			for (entry = index->hash[i]; entry; entry = entry->next) {
+			for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
 				const unsigned char *ref = entry->ptr;
 				const unsigned char *src = data;
 				unsigned int ref_size = ref_top - ref;
-- 
1.5.3.GIT

^ permalink raw reply related

* [PATCH] make sha1_file.c::matches_pack_name() available to others
From: Junio C Hamano @ 2007-09-08  9:50 UTC (permalink / raw)
  To: Nicolas Pitre
  Cc: Linus Torvalds, Johannes Schindelin, Nix, Steven Grimm,
	Git Mailing List
In-Reply-To: <7vwsv36q6p.fsf@gitster.siamese.dyndns.org>

Even though our convention is "zero return means good", it goes a
bit too far for matches_pack_name() to return 0 when it found
the pack is what the name refers to.  This fixes that silly and
obvious interface bug.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 Junio C Hamano <gitster@pobox.com> writes:

 > Nicolas Pitre <nico@cam.org> writes:
 > ...
 >> In fact, since we want to _also_ perform a repack of loose objects in 
 >> the context of automatic repacking, I wonder why we wouldn't use that 
 >> --unpacked= argument to also repack smallish packs at the same time in 
 >> only one pack-objects pass.  Or maybe I'm missing something?
 >
 > I think this is a much better idea.  You obviously need some
 > twist to the pack-objects, and being lazy that was the reason I
 > did not want to do this that way.

 So what follows is two-patch series, which still is a rough
 sketch, as I am feeling a bit too tired to do tests and
 documentation (help is always welcomed, hint hint).

 This message contains the first one, which is more or less
 independent, that exposes matches_pack_name() function from
 sha1_file.c, while fixing a silly and obvious interface bug.

 cache.h     |    1 +
 sha1_file.c |   14 +++++++-------
 2 files changed, 8 insertions(+), 7 deletions(-)

diff --git a/cache.h b/cache.h
index 70abbd5..3fa5b8e 100644
--- a/cache.h
+++ b/cache.h
@@ -529,6 +529,7 @@ extern void *unpack_entry(struct packed_git *, off_t, enum object_type *, unsign
 extern unsigned long unpack_object_header_gently(const unsigned char *buf, unsigned long len, enum object_type *type, unsigned long *sizep);
 extern unsigned long get_size_from_delta(struct packed_git *, struct pack_window **, off_t);
 extern const char *packed_object_info_detail(struct packed_git *, off_t, unsigned long *, unsigned long *, unsigned int *, unsigned char *);
+extern int matches_pack_name(struct packed_git *p, const char *name);
 
 /* Dumb servers support */
 extern int update_server_info(int);
diff --git a/sha1_file.c b/sha1_file.c
index 9978a58..5801c3e 100644
--- a/sha1_file.c
+++ b/sha1_file.c
@@ -1684,22 +1684,22 @@ off_t find_pack_entry_one(const unsigned char *sha1,
 	return 0;
 }
 
-static int matches_pack_name(struct packed_git *p, const char *ig)
+int matches_pack_name(struct packed_git *p, const char *name)
 {
 	const char *last_c, *c;
 
-	if (!strcmp(p->pack_name, ig))
-		return 0;
+	if (!strcmp(p->pack_name, name))
+		return 1;
 
 	for (c = p->pack_name, last_c = c; *c;)
 		if (*c == '/')
 			last_c = ++c;
 		else
 			++c;
-	if (!strcmp(last_c, ig))
-		return 0;
+	if (!strcmp(last_c, name))
+		return 1;
 
-	return 1;
+	return 0;
 }
 
 static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, const char **ignore_packed)
@@ -1717,7 +1717,7 @@ static int find_pack_entry(const unsigned char *sha1, struct pack_entry *e, cons
 		if (ignore_packed) {
 			const char **ig;
 			for (ig = ignore_packed; *ig; ig++)
-				if (!matches_pack_name(p, *ig))
+				if (matches_pack_name(p, *ig))
 					break;
 			if (*ig)
 				goto next;

^ permalink raw reply related

* [PATCH] pack-objects --repack-unpacked
From: Junio C Hamano @ 2007-09-08 10:01 UTC (permalink / raw)
  To: Nicolas Pitre
  Cc: Linus Torvalds, Johannes Schindelin, Nix, Steven Grimm,
	Git Mailing List
In-Reply-To: <7vwsv36q6p.fsf@gitster.siamese.dyndns.org>

The usual command line that uses "--unpacked=<existing>" option
looks like this:

	git pack-objects --non-empty --all --reflog \
        	--unpacked --unpacked=<existing> \
                packname-prefix

This packs loose objects and objects in the named existing
packs that are reachable from any and all refs and reflog
entries.  It is typically used by "git repack -a -d", which
then removes the named existing packs from the repository, and
has an effect of getting rid of unreachable objects these packs
hold.

This adds "--repack-unpacked" option to pack-objects to help
combining small packs into one, without losing unreferenced
objects that are in the packs.  When this option is given in
addition to the above command line, we also make sure all the
objects in the named existing packs are included in the result.

This allows us to safely remove the packs that were named on the
command line after installing the resulting pack in the
repository.

Signed-off-by: Junio C Hamano <gitster@pobox.com>
---

 I am too tired to keep staring at this code now.  Fixes,
 improvements, replacements and enhancements, in the code,
 documentation and tests, are very much welcomed.

 builtin-pack-objects.c |   95 +++++++++++++++++++++++++++++++++++++++++++++++-
 1 files changed, 93 insertions(+), 2 deletions(-)

diff --git a/builtin-pack-objects.c b/builtin-pack-objects.c
index 12509fa..9bc2faa 100644
--- a/builtin-pack-objects.c
+++ b/builtin-pack-objects.c
@@ -21,7 +21,7 @@ git-pack-objects [{ -q | --progress | --all-progress }] \n\
 	[--window=N] [--window-memory=N] [--depth=N] \n\
 	[--no-reuse-delta] [--no-reuse-object] [--delta-base-offset] \n\
 	[--non-empty] [--revs [--unpacked | --all]*] [--reflog] \n\
-	[--stdout | base-name] [<ref-list | <object-list]";
+	[--stdout | base-name] [--repack-unpacked] [<ref-list | <object-list]";
 
 struct object_entry {
 	struct pack_idx_entry idx;
@@ -57,7 +57,7 @@ static struct object_entry **written_list;
 static uint32_t nr_objects, nr_alloc, nr_result, nr_written;
 
 static int non_empty;
-static int no_reuse_delta, no_reuse_object;
+static int no_reuse_delta, no_reuse_object, repack_unpacked;
 static int local;
 static int incremental;
 static int allow_ofs_delta;
@@ -1625,15 +1625,21 @@ static void read_object_list_from_stdin(void)
 	}
 }
 
+#define OBJECT_ADDED (1u<<20)
+
 static void show_commit(struct commit *commit)
 {
 	add_object_entry(commit->object.sha1, OBJ_COMMIT, NULL, 0);
+	commit->object.flags |= OBJECT_ADDED;
 }
 
 static void show_object(struct object_array_entry *p)
 {
+	struct object *o = lookup_unknown_object(p->item->sha1);
+
 	add_preferred_base_object(p->name);
 	add_object_entry(p->item->sha1, p->item->type, p->name, 0);
+	o->flags |= OBJECT_ADDED;
 }
 
 static void show_edge(struct commit *commit)
@@ -1641,6 +1647,84 @@ static void show_edge(struct commit *commit)
 	add_preferred_base(commit->object.sha1);
 }
 
+struct in_pack_object {
+	off_t offset;
+	const unsigned char *sha1;
+};
+
+struct in_pack {
+	int alloc;
+	int nr;
+	struct in_pack_object *array;
+};
+
+static void mark_in_pack_object(const unsigned char *sha1, struct packed_git *p, struct in_pack *in_pack)
+{
+	in_pack->array[in_pack->nr].offset = find_pack_entry_one(sha1, p);
+	in_pack->array[in_pack->nr].sha1 = sha1;
+	in_pack->nr++;
+}
+
+/*
+ * Compare the objects in the offset order, in order to emulate the
+ * "git-rev-list --objects" output that produced the pack originally.
+ */
+static int ofscmp(const void *a_, const void *b_)
+{
+	struct in_pack_object *a = (struct in_pack_object *)a_;
+	struct in_pack_object *b = (struct in_pack_object *)b_;
+
+	if (a->offset < b->offset)
+		return -1;
+	else if (a->offset > b->offset)
+		return 1;
+	else
+		return hashcmp(a->sha1, b->sha1);
+}
+
+static void add_objects_in_unpacked_packs(struct rev_info *revs)
+{
+	struct packed_git *p;
+
+	for (p = packed_git; p; p = p->next) {
+		struct in_pack in_pack;
+		const unsigned char *sha1;
+		struct object *o;
+		uint32_t i;
+
+		for (i = 0; i < revs->num_ignore_packed; i++) {
+			if (matches_pack_name(p, revs->ignore_packed[i]))
+				break;
+		}
+		if (revs->num_ignore_packed <= i)
+			continue;
+		if (open_pack_index(p))
+			die("cannot open pack index");
+
+		in_pack.alloc = p->num_objects;
+		in_pack.nr = 0;
+		in_pack.array = xmalloc(sizeof(in_pack.array[0]) *
+					p->num_objects);
+		for (i = 0; i < p->num_objects; i++) {
+			sha1 = nth_packed_object_sha1(p, i);
+			o = lookup_unknown_object(sha1);
+			if (!(o->flags & OBJECT_ADDED))
+				mark_in_pack_object(sha1, p, &in_pack);
+			o->flags |= OBJECT_ADDED;
+		}
+		if (!in_pack.nr)
+			continue;
+		qsort(in_pack.array, in_pack.nr, sizeof(in_pack.array[0]),
+		      ofscmp);
+		for (i = 0; i < in_pack.nr; i++) {
+			sha1 = in_pack.array[i].sha1;
+			o = lookup_unknown_object(sha1);
+			add_object_entry(sha1, o->type, "", 0);
+		}
+		free(in_pack.array);
+	}
+}
+
 static void get_object_list(int ac, const char **av)
 {
 	struct rev_info revs;
@@ -1672,6 +1756,9 @@ static void get_object_list(int ac, const char **av)
 	prepare_revision_walk(&revs);
 	mark_edges_uninteresting(revs.commits, &revs, show_edge);
 	traverse_commit_list(&revs, show_commit, show_object);
+
+	if (repack_unpacked)
+		add_objects_in_unpacked_packs(&revs);
 }
 
 static int adjust_perm(const char *path, mode_t mode)
@@ -1789,6 +1876,10 @@ int cmd_pack_objects(int argc, const char **argv, const char *prefix)
 			use_internal_rev_list = 1;
 			continue;
 		}
+		if (!strcmp("--repack-unpacked", arg)) {
+			repack_unpacked = 1;
+			continue;
+		}
 		if (!strcmp("--unpacked", arg) ||
 		    !prefixcmp(arg, "--unpacked=") ||
 		    !strcmp("--reflog", arg) ||

^ permalink raw reply related

* [PATCH] git-diff: don't squelch the new SHA1 in submodule diffs
From: Sven Verdoolaege @ 2007-09-08 10:30 UTC (permalink / raw)
  To: Junio C Hamano; +Cc: Git Mailing List

The code to squelch empty diffs introduced by commit
fb13227e089f22dc31a3b1624559153821056848 would inadvertently
populate filespec "two" of a submodule change using the uninitialized
(null) SHA1, thereby replacing the submodule SHA1 by 0{40} in the output.

This change teaches diffcore_skip_stat_unmatch to handle
submodule changes correctly.

Signed-off-by: Sven Verdoolaege <skimo@kotnet.org>
---
 diff.c                     |   21 +++++++++++++++++----
 t/t7400-submodule-basic.sh |    4 ++++
 2 files changed, 21 insertions(+), 4 deletions(-)

diff --git a/diff.c b/diff.c
index 0d30d05..1aca5df 100644
--- a/diff.c
+++ b/diff.c
@@ -3144,6 +3144,22 @@ static void diffcore_apply_filter(const char *filter)
 	*q = outq;
 }
 
+/* Check whether two filespecs with the same mode and size are identical */
+static int diff_filespec_is_identical(struct diff_filespec *one,
+				      struct diff_filespec *two)
+{
+	if (S_ISGITLINK(one->mode)) {
+		diff_fill_sha1_info(one);
+		diff_fill_sha1_info(two);
+		return !hashcmp(one->sha1, two->sha1);
+	}
+	if (diff_populate_filespec(one, 0))
+		return 0;
+	if (diff_populate_filespec(two, 0))
+		return 0;
+	return !memcmp(one->data, two->data, one->size);
+}
+
 static void diffcore_skip_stat_unmatch(struct diff_options *diffopt)
 {
 	int i;
@@ -3175,10 +3191,7 @@ static void diffcore_skip_stat_unmatch(struct diff_options *diffopt)
 		    diff_populate_filespec(p->one, 1) ||
 		    diff_populate_filespec(p->two, 1) ||
 		    (p->one->size != p->two->size) ||
-
-		    diff_populate_filespec(p->one, 0) || /* (2) */
-		    diff_populate_filespec(p->two, 0) ||
-		    memcmp(p->one->data, p->two->data, p->one->size))
+		    !diff_filespec_is_identical(p->one, p->two)) /* (2) */
 			diff_q(&outq, p);
 		else {
 			/*
diff --git a/t/t7400-submodule-basic.sh b/t/t7400-submodule-basic.sh
index 9d142ed..4fe3a41 100755
--- a/t/t7400-submodule-basic.sh
+++ b/t/t7400-submodule-basic.sh
@@ -152,6 +152,10 @@ test_expect_success 'the --cached sha1 should be rev1' '
 	git-submodule --cached status | grep "^+$rev1"
 '
 
+test_expect_success 'git diff should report the SHA1 of the new submodule commit' '
+	git-diff | grep "^+Subproject commit $rev2"
+'
+
 test_expect_success 'update should checkout rev1' '
 	git-submodule update &&
 	head=$(cd lib && git rev-parse HEAD) &&
-- 
1.5.3.1.20.g3d038

^ permalink raw reply related

* Re: .git/info/exclude w/ CFLF fails in cygwin
From: Robin Rosenberg @ 2007-09-08 10:36 UTC (permalink / raw)
  To: Jing Xue; +Cc: git
In-Reply-To: <20070908010139.GA5501@falcon.digizenstudio.com>

lördag 08 september 2007 skrev Jing Xue:
> (1.5.3.1 in cygwin, Win XP)
> I have cygwin configured to operate in the DOS/text mode, which means
> cygwin translates LF to CRLF when writing a file, and CRLF to LF when
> reading.  Unfortunately cygwin's fstat() implementation doesn't take the
> mode into account when reporting stat.st_size, presumably for the sake
> of performance, while read() does actually do the conversion.

This is not just cygwin and applies to all CRLF environments.

> That causes the function add_excludes_from_file_1() in dir.c to reject a
> .git/info/exclude file with CRLF ending, because the size actually read
> is not the same as the size reported by fstat().

> The simplest fix I have found is to explicitly open the exclude file in
> binary mode, because the rest of the exclude file parsing code actually
> deals with CRLF quite fine.
> 
> I would submit a patch but I am not sure if this is the appropriate fix.
doubt it is worth it..
> 
> By the way, parsing .git/config with CRLF in the same environment works
> fine because the code reads the file by byte and doesn't do any size
> validation.
> 
> Any thoughts?

I have cygwin in CRLF mode too, but I have binary-mounted the paths' where
I use git to avoid the problem. I did a half-hearted attempt to fix git in CRLF mode,
but it failed because in some places plumbing commands communicate via files
and in other pipes are used making it hard to get then right translation mode.

That is not to say it is impossible, but as I understand it the Cygwin project have
essentially given up on CRLF mode, so it will probably go away as programs get
updated and no longer works in translated mode.

Try git in unix mode and, if you need it, use the core.autocrl setting to have git
translate explicitly. There are plenty editors that honour line endings in Windows
so LF mode works out quite well nowadays (for me, on my machines).

-- robin

^ permalink raw reply

* RE: git-svn 1.5.3 does not understand grafts?
From: Joakim Tjernlund @ 2007-09-08 11:04 UTC (permalink / raw)
  To: 'Eric Wong'; +Cc: 'git'
In-Reply-To: <20070908050146.GA28855@soma>

> -----Original Message-----
> From: Eric Wong [mailto:normalperson@yhbt.net] 
> Sent: den 8 september 2007 07:02
> To: Joakim Tjernlund
> Cc: git
> Subject: Re: git-svn 1.5.3 does not understand grafts?
> 
> Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> > On Fri, 2007-09-07 at 18:52 +0200, Joakim Tjernlund wrote:
> > > On Fri, 2007-09-07 at 18:41 +0200, Joakim Tjernlund wrote:
> > > > svnadmin create /usr/local/src/TM/svn-tst/7720-svn/
> > > > svn mkdir  
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk -m "Add trunk dir"
> > > > svn mkdir  
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp -m "Add swp dir"
> > > > 
> > > > In my git repo I do
> > > > git-svn init  
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp 
> > > > git-svn fetch
> > > > git branch svn remotes/git-svn
> > > > #make remotes/git-svn parent to the initial commit in 
> my git tree
> > > > graftid=`git-show-ref -s svn`
> > > > echo da783cce390ce013b19f1d308ea6813269c6a6b5 $graftid 
> > .git/info/grafts
> > > > #da783... is the initial commit in my git tree.
> > > > git-svn dcommit
> > > > 
> > > > fails with:
> > > > Committing to 
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp ...
> > > > Commit da783cce390ce013b19f1d308ea6813269c6a6b5
> > > > has no parent commit, and therefore nothing to diff against.
> > > > You should be working from a repository originally 
> created by git-svn
> > > 
> > > Using filter-branch helps, but git-svn isn't too happy:
> > > 
> > > git-svn init  file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp 
> > > git-svn fetch
> > > git branch svn remotes/git-svn
> > > #make remotes/git-svn parent to the initial commit in my git tree
> > > graftid=`git-show-ref -s svn`
> > > echo da783cce390ce013b19f1d308ea6813269c6a6b5 $graftid > 
> .git/info/grafts
> > > #da783... is the initial commit in my git tree.
> > > git filter-branch $graftid..HEAD
> > > git-svn dcommit
> > > 
> > > Now I get alot of complaints, but it commits to svn.
> > > It takes forever though:
> > > r3 = 55a489bd4f66dd1f641a4676359d7b8911dc7d83 (git-svn)
> > > W: HEAD and refs/remotes/git-svn differ, using rebase:
> > > :100644 100644 f85ae11af7715a224015582724cb2bab87ec914a
> 
> I haven't used filter-branch myself, but you probably need to 
> remove all
> .rev_db* files in $GIT_DIR after running it (git-svn can recreate them
> unless you use the svmRevProps or noMetadata options.

havn't used it either, but I wanted to see if it makes a difference.
I will remember to remove the .rev_db* files next time I try.

filter branch is overkill if the grafts file works as git-svn will rewrite
the commits so once the first dcommit has been made, I can remove the
grafts file.

I do have another project though were I want to fix som odd parenting caused
by set-tree, there I will have to used filter-branch to make it permanet.

> 
> > [SNIP]
> > 
> > Just wanted to add that 1.5.2.2 works with grafts and 
> > that I suspect sub read_commit_parents in git-svn, but as I don't
> > do perl I am stuck.
> 
> Crap, it looks like I completely forgot about the existence
> of grafts while doing this function.

:)
Do you have to worry about grafts in git-svn? 
Can't git plumbing do this for you?

> 
> >      Jocke
> > Oh, Eric W. CC:ed as well this time
> 
> Thanks.
> 
> -- 
> Eric Wong
> 
> 

^ permalink raw reply

* [PATCH 1/3] Add strbuf_rtrim (to remove trailing spaces).
From: Pierre Habouzit @ 2007-09-08 11:53 UTC (permalink / raw)
  To: git; +Cc: Pierre Habouzit
In-Reply-To: <11892523992761-git-send-email-madcoder@debian.org>

Signed-off-by: Pierre Habouzit <madcoder@debian.org>
---
 strbuf.c |    7 +++++++
 strbuf.h |    3 +++
 2 files changed, 10 insertions(+), 0 deletions(-)

diff --git a/strbuf.c b/strbuf.c
index acc7fc8..565c343 100644
--- a/strbuf.c
+++ b/strbuf.c
@@ -28,6 +28,13 @@ void strbuf_grow(struct strbuf *sb, size_t extra) {
 	ALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);
 }
 
+void strbuf_rtrim(struct strbuf *sb)
+{
+    while (sb->len > 0 && isspace((unsigned char)sb->buf[sb->len - 1]))
+        sb->len--;
+    sb->buf[sb->len] = '\0';
+}
+
 void strbuf_add(struct strbuf *sb, const void *data, size_t len) {
 	strbuf_grow(sb, len);
 	memcpy(sb->buf + sb->len, data, len);
diff --git a/strbuf.h b/strbuf.h
index b40dc99..9b708cc 100644
--- a/strbuf.h
+++ b/strbuf.h
@@ -68,6 +68,9 @@ static inline void strbuf_setlen(struct strbuf *sb, size_t len) {
 
 extern void strbuf_grow(struct strbuf *, size_t);
 
+/*----- content related -----*/
+extern void strbuf_rtrim(struct strbuf *);
+
 /*----- add data in your buffer -----*/
 static inline void strbuf_addch(struct strbuf *sb, int c) {
 	strbuf_grow(sb, 1);
-- 
1.5.3.1

^ permalink raw reply related

* Use strbufs in commit.c (pretty printing)
From: Pierre Habouzit @ 2007-09-08 11:53 UTC (permalink / raw)
  To: git
In-Reply-To: <20070902224213.GB431@artemis.corp>

  Here is a 3 patch series to use strbufs for the pretty printing
functions in commit.c.

  * The first one adds a needed useful function to strbufs (rtrim).
  * The second one changes the semantics of interpolate (as the third
    will need that) and fixes the rest of the code accordingly.
  * Do the change.

  Testsuite passes after step 2 and 3.

^ permalink raw reply

* [PATCH 2/3] Change semantics of interpolate to work like snprintf.
From: Pierre Habouzit @ 2007-09-08 11:53 UTC (permalink / raw)
  To: git; +Cc: Pierre Habouzit
In-Reply-To: <1189252399433-git-send-email-madcoder@debian.org>

  Also fix many off-by-ones and a useless memset.

Signed-off-by: Pierre Habouzit <madcoder@debian.org>
---
 commit.c      |    9 ++++-----
 interpolate.c |   20 ++++++++------------
 2 files changed, 12 insertions(+), 17 deletions(-)

diff --git a/commit.c b/commit.c
index dc5a064..30db9f4 100644
--- a/commit.c
+++ b/commit.c
@@ -922,15 +922,14 @@ static long format_commit_message(const struct commit *commit,
 
 	do {
 		char *buf = *buf_p;
-		unsigned long space = *space_p;
+		unsigned long len;
 
-		space = interpolate(buf, space, user_format,
+		len = interpolate(buf, *space_p, user_format,
 				    table, ARRAY_SIZE(table));
-		if (!space)
+		if (len < *space_p)
 			break;
-		buf = xrealloc(buf, space);
+		ALLOC_GROW(buf, len + 1, *space_p);
 		*buf_p = buf;
-		*space_p = space;
 	} while (1);
 	interp_clear_table(table, ARRAY_SIZE(table));
 
diff --git a/interpolate.c b/interpolate.c
index 0082677..ff4fb10 100644
--- a/interpolate.c
+++ b/interpolate.c
@@ -44,9 +44,8 @@ void interp_clear_table(struct interp *table, int ninterps)
  *        { "%%", "%"},
  *    }
  *
- * Returns 0 on a successful substitution pass that fits in result,
- * Returns a number of bytes needed to hold the full substituted
- * string otherwise.
+ * Returns the length of the substituted string (not including the final \0).
+ * Like with snprintf, if the result is >= reslen, then it overflowed.
  */
 
 unsigned long interpolate(char *result, unsigned long reslen,
@@ -61,8 +60,6 @@ unsigned long interpolate(char *result, unsigned long reslen,
 	int i;
 	char c;
 
-        memset(result, 0, reslen);
-
 	while ((c = *src)) {
 		if (c == '%') {
 			/* Try to match an interpolation string. */
@@ -78,9 +75,9 @@ unsigned long interpolate(char *result, unsigned long reslen,
 				value = interps[i].value;
 				valuelen = strlen(value);
 
-				if (newlen + valuelen + 1 < reslen) {
+				if (newlen + valuelen < reslen) {
 					/* Substitute. */
-					strncpy(dest, value, valuelen);
+					memcpy(dest, value, valuelen);
 					dest += valuelen;
 				}
 				newlen += valuelen;
@@ -89,14 +86,13 @@ unsigned long interpolate(char *result, unsigned long reslen,
 			}
 		}
 		/* Straight copy one non-interpolation character. */
-		if (newlen + 1 < reslen)
+		if (newlen < reslen)
 			*dest++ = *src;
 		src++;
 		newlen++;
 	}
 
-	if (newlen + 1 < reslen)
-		return 0;
-	else
-		return newlen + 2;
+	if (reslen > 0)
+		*dest = '\0';
+	return newlen;
 }
-- 
1.5.3.1

^ permalink raw reply related

* [PATCH 3/3] Rework pretty_print_commit to use strbufs instead of custom buffers.
From: Pierre Habouzit @ 2007-09-08 11:53 UTC (permalink / raw)
  To: git; +Cc: Pierre Habouzit
In-Reply-To: <1189252399316-git-send-email-madcoder@debian.org>

  Also remove the "len" parameter, as:
  (1) it was used as a max boundary, and every caller used ~0u
  (2) we check for final NUL no matter what, so it doesn't help for speed.

  As a result most of the pp_* function takes 3 arguments less, and we need
a lot less local variables, this makes the code way more readable, and
easier to extend if needed.

  This patch also fixes some spacing and cosmetic issues.

Signed-off-by: Pierre Habouzit <madcoder@debian.org>
---
 builtin-branch.c      |   15 +--
 builtin-log.c         |   12 +-
 builtin-rev-list.c    |   13 +-
 builtin-show-branch.c |   13 +-
 commit.c              |  330 ++++++++++++++++++-------------------------------
 commit.h              |    6 +-
 log-tree.c            |   56 +++------
 7 files changed, 171 insertions(+), 274 deletions(-)

diff --git a/builtin-branch.c b/builtin-branch.c
index 5f5c182..68cd5f9 100644
--- a/builtin-branch.c
+++ b/builtin-branch.c
@@ -268,23 +268,22 @@ static void print_ref_item(struct ref_item *item, int maxwidth, int verbose,
 	}
 
 	if (verbose) {
-		char *subject = NULL;
-		unsigned long subject_len = 0;
+		struct strbuf subject;
 		const char *sub = " **** invalid ref ****";
 
+		strbuf_init(&subject);
+
 		commit = lookup_commit(item->sha1);
 		if (commit && !parse_commit(commit)) {
-			pretty_print_commit(CMIT_FMT_ONELINE, commit, ~0,
-					    &subject, &subject_len, 0,
-					    NULL, NULL, 0);
-			sub = subject;
+			pretty_print_commit(CMIT_FMT_ONELINE, commit,
+					    &subject, 0, NULL, NULL, 0);
+			sub = subject.buf;
 		}
 		printf("%c %s%-*s%s %s %s\n", c, branch_get_color(color),
 		       maxwidth, item->name,
 		       branch_get_color(COLOR_BRANCH_RESET),
 		       find_unique_abbrev(item->sha1, abbrev), sub);
-		if (subject)
-			free(subject);
+		strbuf_release(&subject);
 	} else {
 		printf("%c %s%s%s\n", c, branch_get_color(color), item->name,
 		       branch_get_color(COLOR_BRANCH_RESET));
diff --git a/builtin-log.c b/builtin-log.c
index fa81c25..21b35a1 100644
--- a/builtin-log.c
+++ b/builtin-log.c
@@ -763,13 +763,13 @@ int cmd_cherry(int argc, const char **argv, const char *prefix)
 			sign = '-';
 
 		if (verbose) {
-			char *buf = NULL;
-			unsigned long buflen = 0;
-			pretty_print_commit(CMIT_FMT_ONELINE, commit, ~0,
-			                    &buf, &buflen, 0, NULL, NULL, 0);
+			struct strbuf buf;
+			strbuf_init(&buf);
+			pretty_print_commit(CMIT_FMT_ONELINE, commit,
+			                    &buf, 0, NULL, NULL, 0);
 			printf("%c %s %s\n", sign,
-			       sha1_to_hex(commit->object.sha1), buf);
-			free(buf);
+			       sha1_to_hex(commit->object.sha1), buf.buf);
+			strbuf_release(&buf);
 		}
 		else {
 			printf("%c %s\n", sign,
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index ac551d5..7967f86 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -80,13 +80,12 @@ static void show_commit(struct commit *commit)
 		putchar('\n');
 
 	if (revs.verbose_header) {
-		char *buf = NULL;
-		unsigned long buflen = 0;
-		pretty_print_commit(revs.commit_format, commit, ~0,
-				    &buf, &buflen,
-				    revs.abbrev, NULL, NULL, revs.date_mode);
-		printf("%s%c", buf, hdr_termination);
-		free(buf);
+		struct strbuf buf;
+		strbuf_init(&buf);
+		pretty_print_commit(revs.commit_format, commit,
+					&buf, revs.abbrev, NULL, NULL, revs.date_mode);
+		printf("%s%c", buf.buf, hdr_termination);
+		strbuf_release(&buf);
 	}
 	maybe_flush_or_die(stdout, "stdout");
 	if (commit->parents) {
diff --git a/builtin-show-branch.c b/builtin-show-branch.c
index 4fa87f6..020116f 100644
--- a/builtin-show-branch.c
+++ b/builtin-show-branch.c
@@ -259,16 +259,15 @@ static void join_revs(struct commit_list **list_p,
 
 static void show_one_commit(struct commit *commit, int no_name)
 {
-	char *pretty = NULL;
+	struct strbuf pretty;
 	const char *pretty_str = "(unavailable)";
-	unsigned long pretty_len = 0;
 	struct commit_name *name = commit->util;
 
+	strbuf_init(&pretty);
 	if (commit->object.parsed) {
-		pretty_print_commit(CMIT_FMT_ONELINE, commit, ~0,
-				    &pretty, &pretty_len,
-				    0, NULL, NULL, 0);
-		pretty_str = pretty;
+		pretty_print_commit(CMIT_FMT_ONELINE, commit,
+					&pretty, 0, NULL, NULL, 0);
+		pretty_str = pretty.buf;
 	}
 	if (!prefixcmp(pretty_str, "[PATCH] "))
 		pretty_str += 8;
@@ -289,7 +288,7 @@ static void show_one_commit(struct commit *commit, int no_name)
 			       find_unique_abbrev(commit->object.sha1, 7));
 	}
 	puts(pretty_str);
-	free(pretty);
+	strbuf_release(&pretty);
 }
 
 static char *ref_name[MAX_REVS + 1];
diff --git a/commit.c b/commit.c
index 30db9f4..dafa821 100644
--- a/commit.c
+++ b/commit.c
@@ -458,11 +458,11 @@ void clear_commit_marks(struct commit *commit, unsigned int mark)
 /*
  * Generic support for pretty-printing the header
  */
-static int get_one_line(const char *msg, unsigned long len)
+static int get_one_line(const char *msg)
 {
 	int ret = 0;
 
-	while (len--) {
+	for (;;) {
 		char c = *msg++;
 		if (!c)
 			break;
@@ -485,31 +485,24 @@ static int is_rfc2047_special(char ch)
 	return (non_ascii(ch) || (ch == '=') || (ch == '?') || (ch == '_'));
 }
 
-static int add_rfc2047(char *buf, const char *line, int len,
+static void add_rfc2047(struct strbuf *sb, const char *line, int len,
 		       const char *encoding)
 {
-	char *bp = buf;
-	int i, needquote;
-	char q_encoding[128];
-	const char *q_encoding_fmt = "=?%s?q?";
+	int i, last;
 
-	for (i = needquote = 0; !needquote && i < len; i++) {
+	for (i = 0; i < len; i++) {
 		int ch = line[i];
 		if (non_ascii(ch))
-			needquote++;
-		if ((i + 1 < len) &&
-		    (ch == '=' && line[i+1] == '?'))
-			needquote++;
+			goto needquote;
+		if ((i + 1 < len) && (ch == '=' && line[i+1] == '?'))
+			goto needquote;
 	}
-	if (!needquote)
-		return sprintf(buf, "%.*s", len, line);
-
-	i = snprintf(q_encoding, sizeof(q_encoding), q_encoding_fmt, encoding);
-	if (sizeof(q_encoding) < i)
-		die("Insanely long encoding name %s", encoding);
-	memcpy(bp, q_encoding, i);
-	bp += i;
-	for (i = 0; i < len; i++) {
+	strbuf_add(sb, line, len);
+	return;
+
+needquote:
+	strbuf_addf(sb, "=?%s?q?", encoding);
+	for (i = last = 0; i < len; i++) {
 		unsigned ch = line[i] & 0xFF;
 		/*
 		 * We encode ' ' using '=20' even though rfc2047
@@ -518,15 +511,13 @@ static int add_rfc2047(char *buf, const char *line, int len,
 		 * leave the underscore in place.
 		 */
 		if (is_rfc2047_special(ch) || ch == ' ') {
-			sprintf(bp, "=%02X", ch);
-			bp += 3;
+			strbuf_add(sb, line + last, i - last);
+			strbuf_addf(sb, "=%02X", ch);
+			last = i + 1;
 		}
-		else
-			*bp++ = ch;
 	}
-	memcpy(bp, "?=", 2);
-	bp += 2;
-	return bp - buf;
+	strbuf_add(sb, line + last, len - last);
+	strbuf_addstr(sb, "?=");
 }
 
 static unsigned long bound_rfc2047(unsigned long len, const char *encoding)
@@ -537,21 +528,21 @@ static unsigned long bound_rfc2047(unsigned long len, const char *encoding)
 	return len * 3 + elen + 100;
 }
 
-static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf,
+static void add_user_info(const char *what, enum cmit_fmt fmt, struct strbuf *sb,
 			 const char *line, enum date_mode dmode,
 			 const char *encoding)
 {
 	char *date;
 	int namelen;
 	unsigned long time;
-	int tz, ret;
+	int tz;
 	const char *filler = "    ";
 
 	if (fmt == CMIT_FMT_ONELINE)
-		return 0;
+		return;
 	date = strchr(line, '>');
 	if (!date)
-		return 0;
+		return;
 	namelen = ++date - line;
 	time = strtoul(date, &date, 10);
 	tz = strtol(date, NULL, 10);
@@ -560,42 +551,35 @@ static int add_user_info(const char *what, enum cmit_fmt fmt, char *buf,
 		char *name_tail = strchr(line, '<');
 		int display_name_length;
 		if (!name_tail)
-			return 0;
+			return;
 		while (line < name_tail && isspace(name_tail[-1]))
 			name_tail--;
 		display_name_length = name_tail - line;
 		filler = "";
-		strcpy(buf, "From: ");
-		ret = strlen(buf);
-		ret += add_rfc2047(buf + ret, line, display_name_length,
-				   encoding);
-		memcpy(buf + ret, name_tail, namelen - display_name_length);
-		ret += namelen - display_name_length;
-		buf[ret++] = '\n';
+		strbuf_addstr(sb, "From: ");
+		add_rfc2047(sb, line, display_name_length, encoding);
+		strbuf_add(sb, name_tail, namelen - display_name_length);
+		strbuf_addch(sb, '\n');
 	}
 	else {
-		ret = sprintf(buf, "%s: %.*s%.*s\n", what,
+		strbuf_addf(sb, "%s: %.*s%.*s\n", what,
 			      (fmt == CMIT_FMT_FULLER) ? 4 : 0,
 			      filler, namelen, line);
 	}
 	switch (fmt) {
 	case CMIT_FMT_MEDIUM:
-		ret += sprintf(buf + ret, "Date:   %s\n",
-			       show_date(time, tz, dmode));
+		strbuf_addf(sb, "Date:   %s\n", show_date(time, tz, dmode));
 		break;
 	case CMIT_FMT_EMAIL:
-		ret += sprintf(buf + ret, "Date: %s\n",
-			       show_date(time, tz, DATE_RFC2822));
+		strbuf_addf(sb, "Date: %s\n", show_date(time, tz, DATE_RFC2822));
 		break;
 	case CMIT_FMT_FULLER:
-		ret += sprintf(buf + ret, "%sDate: %s\n", what,
-			       show_date(time, tz, dmode));
+		strbuf_addf(sb, "%sDate: %s\n", what, show_date(time, tz, dmode));
 		break;
 	default:
 		/* notin' */
 		break;
 	}
-	return ret;
 }
 
 static int is_empty_line(const char *line, int *len_p)
@@ -607,16 +591,16 @@ static int is_empty_line(const char *line, int *len_p)
 	return !len;
 }
 
-static int add_merge_info(enum cmit_fmt fmt, char *buf, const struct commit *commit, int abbrev)
+static void add_merge_info(enum cmit_fmt fmt, struct strbuf *sb,
+			const struct commit *commit, int abbrev)
 {
 	struct commit_list *parent = commit->parents;
-	int offset;
 
 	if ((fmt == CMIT_FMT_ONELINE) || (fmt == CMIT_FMT_EMAIL) ||
 	    !parent || !parent->next)
-		return 0;
+		return;
 
-	offset = sprintf(buf, "Merge:");
+	strbuf_addstr(sb, "Merge:");
 
 	while (parent) {
 		struct commit *p = parent->item;
@@ -629,10 +613,9 @@ static int add_merge_info(enum cmit_fmt fmt, char *buf, const struct commit *com
 		dots = (abbrev && strlen(hex) != 40) ?  "..." : "";
 		parent = parent->next;
 
-		offset += sprintf(buf + offset, " %s%s", hex, dots);
+		strbuf_addf(sb, " %s%s", hex, dots);
 	}
-	buf[offset++] = '\n';
-	return offset;
+	strbuf_addch(sb, '\n');
 }
 
 static char *get_header(const struct commit *commit, const char *key)
@@ -787,8 +770,8 @@ static void fill_person(struct interp *table, const char *msg, int len)
 	interp_set_entry(table, 6, show_date(date, tz, DATE_ISO8601));
 }
 
-static long format_commit_message(const struct commit *commit,
-		const char *msg, char **buf_p, unsigned long *space_p)
+static void format_commit_message(const struct commit *commit,
+		const char *msg, struct strbuf *sb)
 {
 	struct interp table[] = {
 		{ "%H" },	/* commit hash */
@@ -841,6 +824,7 @@ static long format_commit_message(const struct commit *commit,
 	};
 	struct commit_list *p;
 	char parents[1024];
+	unsigned long len;
 	int i;
 	enum { HEADER, SUBJECT, BODY } state;
 
@@ -920,20 +904,15 @@ static long format_commit_message(const struct commit *commit,
 		if (!table[i].value)
 			interp_set_entry(table, i, "<unknown>");
 
-	do {
-		char *buf = *buf_p;
-		unsigned long len;
-
-		len = interpolate(buf, *space_p, user_format,
-				    table, ARRAY_SIZE(table));
-		if (len < *space_p)
-			break;
-		ALLOC_GROW(buf, len + 1, *space_p);
-		*buf_p = buf;
-	} while (1);
+	len = interpolate(sb->buf + sb->len, strbuf_avail(sb),
+				user_format, table, ARRAY_SIZE(table));
+	if (len > strbuf_avail(sb)) {
+		strbuf_grow(sb, len);
+		interpolate(sb->buf + sb->len, strbuf_avail(sb) + 1,
+					user_format, table, ARRAY_SIZE(table));
+	}
+	strbuf_setlen(sb, sb->len + len);
 	interp_clear_table(table, ARRAY_SIZE(table));
-
-	return strlen(*buf_p);
 }
 
 static void pp_header(enum cmit_fmt fmt,
@@ -942,34 +921,24 @@ static void pp_header(enum cmit_fmt fmt,
 		      const char *encoding,
 		      const struct commit *commit,
 		      const char **msg_p,
-		      unsigned long *len_p,
-		      unsigned long *ofs_p,
-		      char **buf_p,
-		      unsigned long *space_p)
+		      struct strbuf *sb)
 {
 	int parents_shown = 0;
 
 	for (;;) {
 		const char *line = *msg_p;
-		char *dst;
-		int linelen = get_one_line(*msg_p, *len_p);
-		unsigned long len;
+		int linelen = get_one_line(*msg_p);
 
 		if (!linelen)
 			return;
 		*msg_p += linelen;
-		*len_p -= linelen;
 
 		if (linelen == 1)
 			/* End of header */
 			return;
 
-		ALLOC_GROW(*buf_p, linelen + *ofs_p + 20, *space_p);
-		dst = *buf_p + *ofs_p;
-
 		if (fmt == CMIT_FMT_RAW) {
-			memcpy(dst, line, linelen);
-			*ofs_p += linelen;
+			strbuf_add(sb, line, linelen);
 			continue;
 		}
 
@@ -987,10 +956,8 @@ static void pp_header(enum cmit_fmt fmt,
 			     parent = parent->next, num++)
 				;
 			/* with enough slop */
-			num = *ofs_p + num * 50 + 20;
-			ALLOC_GROW(*buf_p, num, *space_p);
-			dst = *buf_p + *ofs_p;
-			*ofs_p += add_merge_info(fmt, dst, commit, abbrev);
+			strbuf_grow(sb, num * 50 + 20);
+			add_merge_info(fmt, sb, commit, abbrev);
 			parents_shown = 1;
 		}
 
@@ -1000,129 +967,100 @@ static void pp_header(enum cmit_fmt fmt,
 		 * FULLER shows both authors and dates.
 		 */
 		if (!memcmp(line, "author ", 7)) {
-			len = linelen;
+			unsigned long len = linelen;
 			if (fmt == CMIT_FMT_EMAIL)
 				len = bound_rfc2047(linelen, encoding);
-			ALLOC_GROW(*buf_p, *ofs_p + len + 80, *space_p);
-			dst = *buf_p + *ofs_p;
-			*ofs_p += add_user_info("Author", fmt, dst,
-						line + 7, dmode, encoding);
+			strbuf_grow(sb, len + 80);
+			add_user_info("Author", fmt, sb, line + 7, dmode, encoding);
 		}
 
 		if (!memcmp(line, "committer ", 10) &&
 		    (fmt == CMIT_FMT_FULL || fmt == CMIT_FMT_FULLER)) {
-			len = linelen;
+			unsigned long len = linelen;
 			if (fmt == CMIT_FMT_EMAIL)
 				len = bound_rfc2047(linelen, encoding);
-			ALLOC_GROW(*buf_p, *ofs_p + len + 80, *space_p);
-			dst = *buf_p + *ofs_p;
-			*ofs_p += add_user_info("Commit", fmt, dst,
-						line + 10, dmode, encoding);
+			strbuf_grow(sb, len + 80);
+			add_user_info("Commit", fmt, sb, line + 10, dmode, encoding);
 		}
 	}
 }
 
 static void pp_title_line(enum cmit_fmt fmt,
 			  const char **msg_p,
-			  unsigned long *len_p,
-			  unsigned long *ofs_p,
-			  char **buf_p,
-			  unsigned long *space_p,
-			  int indent,
+			  struct strbuf *sb,
 			  const char *subject,
 			  const char *after_subject,
 			  const char *encoding,
 			  int plain_non_ascii)
 {
-	char *title;
-	unsigned long title_alloc, title_len;
+	struct strbuf title;
 	unsigned long len;
 
-	title_len = 0;
-	title_alloc = 80;
-	title = xmalloc(title_alloc);
+	strbuf_init(&title);
+	strbuf_grow(&title, 80);
+
 	for (;;) {
 		const char *line = *msg_p;
-		int linelen = get_one_line(line, *len_p);
-		*msg_p += linelen;
-		*len_p -= linelen;
+		int linelen = get_one_line(line);
 
+		*msg_p += linelen;
 		if (!linelen || is_empty_line(line, &linelen))
 			break;
 
-		if (title_alloc <= title_len + linelen + 2) {
-			title_alloc = title_len + linelen + 80;
-			title = xrealloc(title, title_alloc);
-		}
-		len = 0;
-		if (title_len) {
+		strbuf_grow(&title, linelen + 2);
+		if (title.len) {
 			if (fmt == CMIT_FMT_EMAIL) {
-				len++;
-				title[title_len++] = '\n';
+				strbuf_addch(&title, '\n');
 			}
-			len++;
-			title[title_len++] = ' ';
+			strbuf_addch(&title, ' ');
 		}
-		memcpy(title + title_len, line, linelen);
-		title_len += linelen;
+		strbuf_add(&title, line, linelen);
 	}
 
 	/* Enough slop for the MIME header and rfc2047 */
-	len = bound_rfc2047(title_len, encoding)+ 1000;
+	len = bound_rfc2047(title.len, encoding) + 1000;
 	if (subject)
 		len += strlen(subject);
 	if (after_subject)
 		len += strlen(after_subject);
 	if (encoding)
 		len += strlen(encoding);
-	ALLOC_GROW(*buf_p, title_len + *ofs_p + len, *space_p);
 
+	strbuf_grow(sb, title.len + len);
 	if (subject) {
-		len = strlen(subject);
-		memcpy(*buf_p + *ofs_p, subject, len);
-		*ofs_p += len;
-		*ofs_p += add_rfc2047(*buf_p + *ofs_p,
-				      title, title_len, encoding);
+		strbuf_addstr(sb, subject);
+		add_rfc2047(sb, title.buf, title.len, encoding);
 	} else {
-		memcpy(*buf_p + *ofs_p, title, title_len);
-		*ofs_p += title_len;
+		strbuf_addbuf(sb, &title);
 	}
-	(*buf_p)[(*ofs_p)++] = '\n';
+	strbuf_addch(sb, '\n');
+
 	if (plain_non_ascii) {
 		const char *header_fmt =
 			"MIME-Version: 1.0\n"
 			"Content-Type: text/plain; charset=%s\n"
 			"Content-Transfer-Encoding: 8bit\n";
-		*ofs_p += snprintf(*buf_p + *ofs_p,
-				   *space_p - *ofs_p,
-				   header_fmt, encoding);
+		strbuf_addf(sb, header_fmt, encoding);
 	}
 	if (after_subject) {
-		len = strlen(after_subject);
-		memcpy(*buf_p + *ofs_p, after_subject, len);
-		*ofs_p += len;
+		strbuf_addstr(sb, after_subject);
 	}
-	free(title);
 	if (fmt == CMIT_FMT_EMAIL) {
-		ALLOC_GROW(*buf_p, *ofs_p + 20, *space_p);
-		(*buf_p)[(*ofs_p)++] = '\n';
+		strbuf_addch(sb, '\n');
 	}
+	strbuf_release(&title);
 }
 
 static void pp_remainder(enum cmit_fmt fmt,
 			 const char **msg_p,
-			 unsigned long *len_p,
-			 unsigned long *ofs_p,
-			 char **buf_p,
-			 unsigned long *space_p,
+			 struct strbuf *sb,
 			 int indent)
 {
 	int first = 1;
 	for (;;) {
 		const char *line = *msg_p;
-		int linelen = get_one_line(line, *len_p);
+		int linelen = get_one_line(line);
 		*msg_p += linelen;
-		*len_p -= linelen;
 
 		if (!linelen)
 			break;
@@ -1135,36 +1073,30 @@ static void pp_remainder(enum cmit_fmt fmt,
 		}
 		first = 0;
 
-		ALLOC_GROW(*buf_p, *ofs_p + linelen + indent + 20, *space_p);
+		strbuf_grow(sb, linelen + indent + 20);
 		if (indent) {
-			memset(*buf_p + *ofs_p, ' ', indent);
-			*ofs_p += indent;
+			memset(sb->buf + sb->len, ' ', indent);
+			strbuf_setlen(sb, sb->len + indent);
 		}
-		memcpy(*buf_p + *ofs_p, line, linelen);
-		*ofs_p += linelen;
-		(*buf_p)[(*ofs_p)++] = '\n';
+		strbuf_add(sb, line, linelen);
+		strbuf_addch(sb, '\n');
 	}
 }
 
-unsigned long pretty_print_commit(enum cmit_fmt fmt,
-				  const struct commit *commit,
-				  unsigned long len,
-				  char **buf_p, unsigned long *space_p,
-				  int abbrev, const char *subject,
-				  const char *after_subject,
+void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
+				  struct strbuf *sb, int abbrev,
+				  const char *subject, const char *after_subject,
 				  enum date_mode dmode)
 {
-	unsigned long offset = 0;
 	unsigned long beginning_of_body;
 	int indent = 4;
 	const char *msg = commit->buffer;
 	int plain_non_ascii = 0;
 	char *reencoded;
 	const char *encoding;
-	char *buf;
 
 	if (fmt == CMIT_FMT_USERFORMAT)
-		return format_commit_message(commit, msg, buf_p, space_p);
+		return format_commit_message(commit, msg, sb);
 
 	encoding = (git_log_output_encoding
 		    ? git_log_output_encoding
@@ -1174,7 +1106,6 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt,
 	reencoded = logmsg_reencode(commit, encoding);
 	if (reencoded) {
 		msg = reencoded;
-		len = strlen(reencoded);
 	}
 
 	if (fmt == CMIT_FMT_ONELINE || fmt == CMIT_FMT_EMAIL)
@@ -1189,14 +1120,13 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt,
 	if (fmt == CMIT_FMT_EMAIL && !after_subject) {
 		int i, ch, in_body;
 
-		for (in_body = i = 0; (ch = msg[i]) && i < len; i++) {
+		for (in_body = i = 0; (ch = msg[i]); i++) {
 			if (!in_body) {
 				/* author could be non 7-bit ASCII but
 				 * the log may be so; skip over the
 				 * header part first.
 				 */
-				if (ch == '\n' &&
-				    i + 1 < len && msg[i+1] == '\n')
+				if (ch == '\n' && msg[i+1] == '\n')
 					in_body = 1;
 			}
 			else if (non_ascii(ch)) {
@@ -1206,59 +1136,44 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt,
 		}
 	}
 
-	pp_header(fmt, abbrev, dmode, encoding,
-		  commit, &msg, &len,
-		  &offset, buf_p, space_p);
+	pp_header(fmt, abbrev, dmode, encoding, commit, &msg, sb);
 	if (fmt != CMIT_FMT_ONELINE && !subject) {
-		ALLOC_GROW(*buf_p, offset + 20, *space_p);
-		(*buf_p)[offset++] = '\n';
+		strbuf_addch(sb, '\n');
 	}
 
 	/* Skip excess blank lines at the beginning of body, if any... */
 	for (;;) {
-		int linelen = get_one_line(msg, len);
+		int linelen = get_one_line(msg);
 		int ll = linelen;
 		if (!linelen)
 			break;
 		if (!is_empty_line(msg, &ll))
 			break;
 		msg += linelen;
-		len -= linelen;
 	}
 
 	/* These formats treat the title line specially. */
-	if (fmt == CMIT_FMT_ONELINE
-	    || fmt == CMIT_FMT_EMAIL)
-		pp_title_line(fmt, &msg, &len, &offset,
-			      buf_p, space_p, indent,
-			      subject, after_subject, encoding,
-			      plain_non_ascii);
-
-	beginning_of_body = offset;
-	if (fmt != CMIT_FMT_ONELINE)
-		pp_remainder(fmt, &msg, &len, &offset,
-			     buf_p, space_p, indent);
-
-	while (offset && isspace((*buf_p)[offset-1]))
-		offset--;
+	if (fmt == CMIT_FMT_ONELINE || fmt == CMIT_FMT_EMAIL)
+		pp_title_line(fmt, &msg, sb, subject,
+			      after_subject, encoding, plain_non_ascii);
 
-	ALLOC_GROW(*buf_p, offset + 20, *space_p);
-	buf = *buf_p;
+	beginning_of_body = sb->len;
+	if (fmt != CMIT_FMT_ONELINE)
+		pp_remainder(fmt, &msg, sb, indent);
+	strbuf_rtrim(sb);
 
 	/* Make sure there is an EOLN for the non-oneline case */
 	if (fmt != CMIT_FMT_ONELINE)
-		buf[offset++] = '\n';
+		strbuf_addch(sb, '\n');
 
 	/*
 	 * The caller may append additional body text in e-mail
 	 * format.  Make sure we did not strip the blank line
 	 * between the header and the body.
 	 */
-	if (fmt == CMIT_FMT_EMAIL && offset <= beginning_of_body)
-		buf[offset++] = '\n';
-	buf[offset] = '\0';
+	if (fmt == CMIT_FMT_EMAIL && sb->len <= beginning_of_body)
+		strbuf_addch(sb, '\n');
 	free(reencoded);
-	return offset;
 }
 
 struct commit *pop_commit(struct commit_list **stack)
@@ -1337,12 +1252,12 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
 		next=next->next;
 	}
 	/*
-         * find the tips
-         *
-         * tips are nodes not reachable from any other node in the list
-         *
-         * the tips serve as a starting set for the work queue.
-         */
+	 * find the tips
+	 *
+	 * tips are nodes not reachable from any other node in the list
+	 *
+	 * the tips serve as a starting set for the work queue.
+	 */
 	next=*list;
 	insert = &work;
 	while (next) {
@@ -1369,9 +1284,9 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
 			if (pn) {
 				/*
 				 * parents are only enqueued for emission
-                                 * when all their children have been emitted thereby
-                                 * guaranteeing topological order.
-                                 */
+				 * when all their children have been emitted thereby
+				 * guaranteeing topological order.
+				 */
 				pn->indegree--;
 				if (!pn->indegree) {
 					if (!lifo)
@@ -1383,9 +1298,9 @@ void sort_in_topological_order_fn(struct commit_list ** list, int lifo,
 			parents=parents->next;
 		}
 		/*
-                 * work_item is a commit all of whose children
-                 * have already been emitted. we can emit it now.
-                 */
+		 * work_item is a commit all of whose children
+		 * have already been emitted. we can emit it now.
+		 */
 		*pptr = work_node->list_item;
 		pptr = &(*pptr)->next;
 		*pptr = NULL;
@@ -1481,8 +1396,7 @@ static struct commit_list *merge_bases(struct commit *one, struct commit *two)
 }
 
 struct commit_list *get_merge_bases(struct commit *one,
-				    struct commit *two,
-                                    int cleanup)
+					struct commit *two, int cleanup)
 {
 	struct commit_list *list;
 	struct commit **rslt;
diff --git a/commit.h b/commit.h
index 467872e..745f538 100644
--- a/commit.h
+++ b/commit.h
@@ -3,6 +3,7 @@
 
 #include "object.h"
 #include "tree.h"
+#include "strbuf.h"
 #include "decorate.h"
 
 struct commit_list {
@@ -61,7 +62,10 @@ enum cmit_fmt {
 };
 
 extern enum cmit_fmt get_commit_format(const char *arg);
-extern unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *, unsigned long len, char **buf_p, unsigned long *space_p, int abbrev, const char *subject, const char *after_subject, enum date_mode dmode);
+extern void pretty_print_commit(enum cmit_fmt fmt, const struct commit*,
+                                struct strbuf *,
+                                int abbrev, const char *subject,
+                                const char *after_subject, enum date_mode);
 
 /** Removes the first commit from a list sorted by date, and adds all
  * of its parents.
diff --git a/log-tree.c b/log-tree.c
index a642371..5186939 100644
--- a/log-tree.c
+++ b/log-tree.c
@@ -79,25 +79,14 @@ static int detect_any_signoff(char *letter, int size)
 	return seen_head && seen_name;
 }
 
-static unsigned long append_signoff(char **buf_p, unsigned long *buf_sz_p,
-				    unsigned long at, const char *signoff)
+static void append_signoff(struct strbuf *sb, const char *signoff)
 {
 	static const char signed_off_by[] = "Signed-off-by: ";
 	size_t signoff_len = strlen(signoff);
 	int has_signoff = 0;
 	char *cp;
-	char *buf;
-	unsigned long buf_sz;
-
-	buf = *buf_p;
-	buf_sz = *buf_sz_p;
-	if (buf_sz <= at + strlen(signed_off_by) + signoff_len + 3) {
-		buf_sz += strlen(signed_off_by) + signoff_len + 3;
-		buf = xrealloc(buf, buf_sz);
-		*buf_p = buf;
-		*buf_sz_p = buf_sz;
-	}
-	cp = buf;
+
+	cp = sb->buf;
 
 	/* First see if we already have the sign-off by the signer */
 	while ((cp = strstr(cp, signed_off_by))) {
@@ -105,29 +94,25 @@ static unsigned long append_signoff(char **buf_p, unsigned long *buf_sz_p,
 		has_signoff = 1;
 
 		cp += strlen(signed_off_by);
-		if (cp + signoff_len >= buf + at)
+		if (cp + signoff_len >= sb->buf + sb->len)
 			break;
 		if (strncmp(cp, signoff, signoff_len))
 			continue;
 		if (!isspace(cp[signoff_len]))
 			continue;
 		/* we already have him */
-		return at;
+		return;
 	}
 
 	if (!has_signoff)
-		has_signoff = detect_any_signoff(buf, at);
+		has_signoff = detect_any_signoff(sb->buf, sb->len);
 
 	if (!has_signoff)
-		buf[at++] = '\n';
-
-	strcpy(buf + at, signed_off_by);
-	at += strlen(signed_off_by);
-	strcpy(buf + at, signoff);
-	at += signoff_len;
-	buf[at++] = '\n';
-	buf[at] = 0;
-	return at;
+		strbuf_addch(sb, '\n');
+
+	strbuf_addstr(sb, signed_off_by);
+	strbuf_add(sb, signoff, signoff_len);
+	strbuf_addch(sb, '\n');
 }
 
 static unsigned int digits_in_number(unsigned int number)
@@ -142,14 +127,12 @@ static unsigned int digits_in_number(unsigned int number)
 
 void show_log(struct rev_info *opt, const char *sep)
 {
-	char *msgbuf = NULL;
-	unsigned long msgbuf_len = 0;
+	struct strbuf msgbuf;
 	struct log_info *log = opt->loginfo;
 	struct commit *commit = log->commit, *parent = log->parent;
 	int abbrev = opt->diffopt.abbrev;
 	int abbrev_commit = opt->abbrev_commit ? opt->abbrev : 40;
 	const char *extra;
-	int len;
 	const char *subject = NULL, *extra_headers = opt->extra_headers;
 
 	opt->loginfo = NULL;
@@ -288,18 +271,17 @@ void show_log(struct rev_info *opt, const char *sep)
 	/*
 	 * And then the pretty-printed message itself
 	 */
-	len = pretty_print_commit(opt->commit_format, commit, ~0u,
-				  &msgbuf, &msgbuf_len, abbrev, subject,
-				  extra_headers, opt->date_mode);
+	strbuf_init(&msgbuf);
+	pretty_print_commit(opt->commit_format, commit, &msgbuf,
+				  abbrev, subject, extra_headers, opt->date_mode);
 
 	if (opt->add_signoff)
-		len = append_signoff(&msgbuf, &msgbuf_len, len,
-				     opt->add_signoff);
+		append_signoff(&msgbuf, opt->add_signoff);
 	if (opt->show_log_size)
-		printf("log size %i\n", len);
+		printf("log size %i\n", (int)msgbuf.len);
 
-	printf("%s%s%s", msgbuf, extra, sep);
-	free(msgbuf);
+	printf("%s%s%s", msgbuf.buf, extra, sep);
+	strbuf_release(&msgbuf);
 }
 
 int log_tree_diff_flush(struct rev_info *opt)
-- 
1.5.3.1

^ permalink raw reply related

* Re: [PATCH 3/3] Rework pretty_print_commit to use strbufs instead of custom buffers.
From: David Kastrup @ 2007-09-08 11:59 UTC (permalink / raw)
  To: Pierre Habouzit; +Cc: git
In-Reply-To: <11892523992038-git-send-email-madcoder@debian.org>

Pierre Habouzit <madcoder@debian.org> writes:

>   Also remove the "len" parameter, as:
>   (1) it was used as a max boundary, and every caller used ~0u
>   (2) we check for final NUL no matter what, so it doesn't help for speed.

That sounds like a change that makes improvement of callers impossible
when it is found out that it leads to a performance issue.  Is it only
the pretty-print that is affected?

-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

^ permalink raw reply

* Re: [PATCH 3/3] Rework pretty_print_commit to use strbufs instead of custom buffers.
From: Pierre Habouzit @ 2007-09-08 12:17 UTC (permalink / raw)
  To: David Kastrup; +Cc: git
In-Reply-To: <851wd9xt98.fsf@lola.goethe.zz>

[-- Attachment #1: Type: text/plain, Size: 2126 bytes --]

On Sat, Sep 08, 2007 at 11:59:31AM +0000, David Kastrup wrote:
> Pierre Habouzit <madcoder@debian.org> writes:
> 
> >   Also remove the "len" parameter, as:
> >   (1) it was used as a max boundary, and every caller used ~0u
> >   (2) we check for final NUL no matter what, so it doesn't help for speed.
> 
> That sounds like a change that makes improvement of callers impossible
> when it is found out that it leads to a performance issue.  Is it only
> the pretty-print that is affected?

  I removed the "len" argument of pretty_print_commit and all the sub
pp_* functions it uses. This argument was supposed to tell which size
the commit message you want to read to format the pretty printing.

  It leads to a lot of code that works like this:

  if (position < len || *msg) /* test if len is overflowed or if we are
                                 at the end of the string */
    break;

  This impose us to maintain the len of the message while we make the
"msg" pointer progress, and so on. And it's a limit of what to read in the
commit message.

Seeing where pretty_print_commit is used:

builtin-branch.c:			pretty_print_commit(CMIT_FMT_ONELINE, commit,
builtin-log.c:			pretty_print_commit(CMIT_FMT_ONELINE, commit,
builtin-rev-list.c:		pretty_print_commit(revs.commit_format, commit,
builtin-show-branch.c:		pretty_print_commit(CMIT_FMT_ONELINE, commit,
commit.c:void pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit,
log-tree.c:	pretty_print_commit(opt->commit_format, commit, &msgbuf,


  I assume that the user would not be very pleased if we decide to crop
his commits logs when he uses git-log. And given that git log in the
linux repository on my laptop takes:

  2,13s user 0,06s system 99% cpu 2,213 total

when the repo is hot ... I hardly think it can ever be a performance
issue :)

  But if people disagree I can refactor a patch with the "len" argument
kept.
-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

^ permalink raw reply

* Re: [PATCH 3/3] Rework pretty_print_commit to use strbufs instead of custom buffers.
From: Pierre Habouzit @ 2007-09-08 12:28 UTC (permalink / raw)
  To: David Kastrup; +Cc: git
In-Reply-To: <851wd9xt98.fsf@lola.goethe.zz>

[-- Attachment #1: Type: text/plain, Size: 2863 bytes --]

On sam, sep 08, 2007 at 11:59:31 +0000, David Kastrup wrote:
> Pierre Habouzit <madcoder@debian.org> writes:
> 
> >   Also remove the "len" parameter, as:
> >   (1) it was used as a max boundary, and every caller used ~0u
> >   (2) we check for final NUL no matter what, so it doesn't help for speed.
> 
> That sounds like a change that makes improvement of callers impossible
> when it is found out that it leads to a performance issue.  Is it only
> the pretty-print that is affected?

  Speaking of performance, here is a small interesting bench:

$ for i in `seq 1 10`; do time git-log >| /dev/null; done
git-log >| /dev/null  2,12s user 0,08s system 99% cpu 2,205 total
git-log >| /dev/null  2,14s user 0,06s system 99% cpu 2,208 total
git-log >| /dev/null  2,12s user 0,08s system 99% cpu 2,205 total
git-log >| /dev/null  2,10s user 0,10s system 99% cpu 2,209 total
git-log >| /dev/null  2,14s user 0,07s system 99% cpu 2,211 total
git-log >| /dev/null  2,11s user 0,09s system 99% cpu 2,210 total
git-log >| /dev/null  2,15s user 0,05s system 99% cpu 2,213 total
git-log >| /dev/null  2,12s user 0,07s system 99% cpu 2,203 total
git-log >| /dev/null  2,13s user 0,06s system 99% cpu 2,204 total
git-log >| /dev/null  2,17s user 0,09s system 100% cpu 2,254 total

$ for i in `seq 1 10`; do time ~/dev/scm/git/git-log >| /dev/null; done
~/dev/scm/git/git-log >| /dev/null  2,06s user 0,11s system 99% cpu 2,185 total
~/dev/scm/git/git-log >| /dev/null  2,11s user 0,07s system 99% cpu 2,192 total
~/dev/scm/git/git-log >| /dev/null  2,10s user 0,10s system 99% cpu 2,207 total
~/dev/scm/git/git-log >| /dev/null  2,10s user 0,08s system 99% cpu 2,188 total
~/dev/scm/git/git-log >| /dev/null  2,10s user 0,08s system 99% cpu 2,187 total
~/dev/scm/git/git-log >| /dev/null  2,10s user 0,10s system 100% cpu 2,196 total
~/dev/scm/git/git-log >| /dev/null  2,08s user 0,11s system 99% cpu 2,195 total
~/dev/scm/git/git-log >| /dev/null  2,11s user 0,08s system 99% cpu 2,193 total
~/dev/scm/git/git-log >| /dev/null  2,10s user 0,08s system 100% cpu 2,188 total
~/dev/scm/git/git-log >| /dev/null  2,12s user 0,07s system 98% cpu 2,213 total

$ git rev-list --all | wc -l
64271


  The underling repository is a not so old linux-2.6 git repository.
git-log is the default unstable git-log, (a pristine 1.5.3.1,
pre-new-strbuf).

  ~/dev/scm/git/git-log is obviously the new one with the whole strbuf
patch series applied. Strbufs definitely made the code more readable (at
least it's my impression), here is the proof that it did not affected an
inch from performance (we even seem to have a marginal 0.5% gain in
performance ;p).

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

^ permalink raw reply

* gitweb on MAC OSX 10.3 Panther
From: Brian Mc Enery @ 2007-09-08 14:05 UTC (permalink / raw)
  To: git

Hi there,

I have just completed the installation of gitweb (git version 1.5.3.1) 
on Mac OSX 10.3 Panther, and I thought that you may be interested in 
including  a note with your distribution, to enable an easier 
experience for others.

Essentially the commands I used were variations on the following.

****** Start installation of gitweb on Mac OSX ******

make    	prefix="/usr/local" \
         	PERL_PATH="/usr/local/ActivePerl-5.8/bin/perl" \
         	all

sudo      make prefix=/usr/local install


make   	PERL_PATH="/usr/local/ActivePerl-5.8/bin/perl" \
         	GITWEB_PROJECTROOT="/Library/WebServer/Documents/gitweb/rep" \
		GITWEB_CSS="/gitweb/res/gitweb.css" \
		GITWEB_LOGO="/gitweb/res/git-logo.png" \
		GITWEB_FAVICON="/gitweb/res/git-favicon.png" \
         	GITWEB_SITENAME="Local Git" \
		bindir=/usr/local/bin \
		gitweb/gitweb.cgi

cp -fv  ./gitweb/gitweb.cgi /Library/WebServer/CGI-Executables/gitweb

cp -fv  	./gitweb/gitweb.css \
         	./gitweb/git-{favicon,logo}.png \
         	/Library/WebServer/Documents/gitweb/res

****** End installation of gitweb on Mac OSX ******

Notes:

Perl_Path was necessary in order to change the shebang line in any perl 
or cgi scripts to use my non-standard
perl interpreter, i.e. different from usr/bin/perl.

The gitweb.cgi script and the configuration file gitweb_configure.perl 
must be placed in a directory under /Library/WebServer/CGI-Executables, 
as this is equivalent to localhost/cgi-bin. In this case I used 
/Library/WebServer/CGI-Executables/gitweb.


The gitweb resources *must* be placed in a folder in 
/Library/WebServer/Documents, not in 
/Library/WebServer/CGI-Executables. In this case I placed the resources 
in  /Library/WebServer/Documents/gitweb/res, and used 
/Library/WebServer/Documents/gitweb/rep, as the project root. The 
absolute url for the project root must be specified.

In order to use symbolic links from a live project to the projectroot 
it was not necessary to make any changes to the Apache configuration 
file, however the files being linked to i.e. the project/.git files 
*must*(it took forever to work this out), be in a publicly accessible 
area, even if you are accessing using a browser under you own username. 
In my case I placed those projects in the Public folder, under my own 
username.

Relevant file permissions must of course be tweaked.

If all goes according to plan repositories are accessible from 
http://localhost/cgi-bin/gitweb/gitweb.cgi



Thank you,

Brían




Brían Mach Aon Innéirghthe
Corcaigh
Éire

^ permalink raw reply

* how to export git repository?
From: Tamas K Papp @ 2007-09-08 14:55 UTC (permalink / raw)
  To: git

Sorry, but I didn't find this in the documentation.  How can I export
the contents of a repository (just the files, not the version control
information)?

I am looking for something similar to svn export.

Thanks,

Tamas

^ permalink raw reply

* Re: how to export git repository?
From: Jeff King @ 2007-09-08 15:08 UTC (permalink / raw)
  To: Tamas K Papp; +Cc: git
In-Reply-To: <20070908145555.GA24132@pu100877.student.princeton.edu>

On Sat, Sep 08, 2007 at 04:55:55PM +0200, Tamas K Papp wrote:

> Sorry, but I didn't find this in the documentation.  How can I export
> the contents of a repository (just the files, not the version control
> information)?
> 
> I am looking for something similar to svn export.

Try "git-archive".

-Peff

^ permalink raw reply

* Re: [PATCH 1/3] Add strbuf_rtrim (to remove trailing spaces).
From: René Scharfe @ 2007-09-08 16:18 UTC (permalink / raw)
  To: Pierre Habouzit; +Cc: git
In-Reply-To: <1189252399433-git-send-email-madcoder@debian.org>

Pierre Habouzit schrieb:
> diff --git a/strbuf.c b/strbuf.c
> index acc7fc8..565c343 100644
> --- a/strbuf.c
> +++ b/strbuf.c
> @@ -28,6 +28,13 @@ void strbuf_grow(struct strbuf *sb, size_t extra) {
>  	ALLOC_GROW(sb->buf, sb->len + extra + 1, sb->alloc);
>  }
>  
> +void strbuf_rtrim(struct strbuf *sb)
> +{
> +    while (sb->len > 0 && isspace((unsigned char)sb->buf[sb->len - 1]))
> +        sb->len--;
> +    sb->buf[sb->len] = '\0';
> +}

Please use tabs instead of spaces to indent, just like you did in your
other patches. :)

René

^ permalink raw reply

* RE: git-svn 1.5.3 does not understand grafts?
From: Joakim Tjernlund @ 2007-09-08 17:43 UTC (permalink / raw)
  To: 'Eric Wong'; +Cc: 'git'
In-Reply-To: <20070908050146.GA28855@soma>

 

> -----Original Message-----
> From: Eric Wong [mailto:normalperson@yhbt.net] 
> Sent: den 8 september 2007 07:02
> To: Joakim Tjernlund
> Cc: git
> Subject: Re: git-svn 1.5.3 does not understand grafts?
> 
> Joakim Tjernlund <joakim.tjernlund@transmode.se> wrote:
> > On Fri, 2007-09-07 at 18:52 +0200, Joakim Tjernlund wrote:
> > > On Fri, 2007-09-07 at 18:41 +0200, Joakim Tjernlund wrote:
> > > > svnadmin create /usr/local/src/TM/svn-tst/7720-svn/
> > > > svn mkdir  
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk -m "Add trunk dir"
> > > > svn mkdir  
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp -m "Add swp dir"
> > > > 
> > > > In my git repo I do
> > > > git-svn init  
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp 
> > > > git-svn fetch
> > > > git branch svn remotes/git-svn
> > > > #make remotes/git-svn parent to the initial commit in 
> my git tree
> > > > graftid=`git-show-ref -s svn`
> > > > echo da783cce390ce013b19f1d308ea6813269c6a6b5 $graftid 
> > .git/info/grafts
> > > > #da783... is the initial commit in my git tree.
> > > > git-svn dcommit
> > > > 
> > > > fails with:
> > > > Committing to 
> file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp ...
> > > > Commit da783cce390ce013b19f1d308ea6813269c6a6b5
> > > > has no parent commit, and therefore nothing to diff against.
> > > > You should be working from a repository originally 
> created by git-svn
> > > 
> > > Using filter-branch helps, but git-svn isn't too happy:
> > > 
> > > git-svn init  file:///usr/local/src/TM/svn-tst/7720-svn/trunk/swp 
> > > git-svn fetch
> > > git branch svn remotes/git-svn
> > > #make remotes/git-svn parent to the initial commit in my git tree
> > > graftid=`git-show-ref -s svn`
> > > echo da783cce390ce013b19f1d308ea6813269c6a6b5 $graftid > 
> .git/info/grafts
> > > #da783... is the initial commit in my git tree.
> > > git filter-branch $graftid..HEAD
> > > git-svn dcommit
> > > 
> > > Now I get alot of complaints, but it commits to svn.
> > > It takes forever though:
> > > r3 = 55a489bd4f66dd1f641a4676359d7b8911dc7d83 (git-svn)
> > > W: HEAD and refs/remotes/git-svn differ, using rebase:
> > > :100644 100644 f85ae11af7715a224015582724cb2bab87ec914a
> 
> I haven't used filter-branch myself, but you probably need to 
> remove all
> .rev_db* files in $GIT_DIR after running it (git-svn can recreate them
> unless you use the svmRevProps or noMetadata options.
> 
> > [SNIP]
> > 
> > Just wanted to add that 1.5.2.2 works with grafts and 
> > that I suspect sub read_commit_parents in git-svn, but as I don't
> > do perl I am stuck.
> 
> Crap, it looks like I completely forgot about the existence
> of grafts while doing this function.

hmm, I think git-cat-file is to blame.
git-cat-file commit da783cce390ce013b19f1d308ea6813269c6a6b5 does
not list list any parent even though I did
graftid=`git-show-ref -s remotes/git-svn`
echo da783cce390ce013b19f1d308ea6813269c6a6b5 $graftid > .git/info/grafts

 Jocke

^ permalink raw reply

* Re: [PATCH 3/3] Rework pretty_print_commit to use strbufs instead of custom buffers.
From: René Scharfe @ 2007-09-08 18:40 UTC (permalink / raw)
  To: Pierre Habouzit; +Cc: Git Mailing List
In-Reply-To: <11892523992038-git-send-email-madcoder@debian.org>

Pierre Habouzit schrieb:
>   Also remove the "len" parameter, as:
>   (1) it was used as a max boundary, and every caller used ~0u
>   (2) we check for final NUL no matter what, so it doesn't help for speed.
> 
>   As a result most of the pp_* function takes 3 arguments less, and we need
> a lot less local variables, this makes the code way more readable, and
> easier to extend if needed.
> 
>   This patch also fixes some spacing and cosmetic issues.
> 
> Signed-off-by: Pierre Habouzit <madcoder@debian.org>
> ---
>  builtin-branch.c      |   15 +--
>  builtin-log.c         |   12 +-
>  builtin-rev-list.c    |   13 +-
>  builtin-show-branch.c |   13 +-
>  commit.c              |  330 ++++++++++++++++++-------------------------------
>  commit.h              |    6 +-
>  log-tree.c            |   56 +++------
>  7 files changed, 171 insertions(+), 274 deletions(-)

Nice!  I wonder if we should #include strbuf.h from git-compat-util.h
(just like e.g. string.h) instead of from commit.h, in order to have
strbuf available everywhere in git.

Please be aware of the changes to commit.c already in next which your
patch conflicts with: format_commit_message() has been exported and is
used in builtin-archive.c there.

René

^ permalink raw reply

* Re: [PATCH 3/3] Rework pretty_print_commit to use strbufs instead  of custom buffers.
From: Pierre Habouzit @ 2007-09-08 18:49 UTC (permalink / raw)
  To: René Scharfe; +Cc: Git Mailing List
In-Reply-To: <46E2EC88.6000500@lsrfire.ath.cx>

[-- Attachment #1: Type: text/plain, Size: 1767 bytes --]

On Sat, Sep 08, 2007 at 06:40:08PM +0000, René Scharfe wrote:
> Pierre Habouzit schrieb:
> >   Also remove the "len" parameter, as:
> >   (1) it was used as a max boundary, and every caller used ~0u
> >   (2) we check for final NUL no matter what, so it doesn't help for speed.
> > 
> >   As a result most of the pp_* function takes 3 arguments less, and we need
> > a lot less local variables, this makes the code way more readable, and
> > easier to extend if needed.
> > 
> >   This patch also fixes some spacing and cosmetic issues.
> > 
> > Signed-off-by: Pierre Habouzit <madcoder@debian.org>
> > ---
> >  builtin-branch.c      |   15 +--
> >  builtin-log.c         |   12 +-
> >  builtin-rev-list.c    |   13 +-
> >  builtin-show-branch.c |   13 +-
> >  commit.c              |  330 ++++++++++++++++++-------------------------------
> >  commit.h              |    6 +-
> >  log-tree.c            |   56 +++------
> >  7 files changed, 171 insertions(+), 274 deletions(-)
> 
> Nice!  I wonder if we should #include strbuf.h from git-compat-util.h
> (just like e.g. string.h) instead of from commit.h, in order to have
> strbuf available everywhere in git.
> 
> Please be aware of the changes to commit.c already in next which your
> patch conflicts with: format_commit_message() has been exported and is
> used in builtin-archive.c there.

  Okay, then I'll hope than Junio will merge the first series and then
rebase this one on next. If I'm going to propose more of those patches,
should I write them rather on next or master (like I do now) ?

-- 
·O·  Pierre Habouzit
··O                                                madcoder@debian.org
OOO                                                http://www.madism.org

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

^ permalink raw reply

* [PATCH] diff-delta.c: Rationalize culling of hash buckets
From: David Kastrup @ 2007-09-08 19:41 UTC (permalink / raw)
  To: git
In-Reply-To: <f1161c08aeeca60b6c33af34ccea68fd99b9ea4e.1189243702.git.dak@gnu.org>

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.
---

This is assuming that the previous patch series has been applied
(lacking any final comments or Acks on it; but I think I addressed the
issues).  The hash bucket code culling has really annoyed me with its
unintuitive results.  If the preceding patch series is thrown out (I
can't think why it would), one could rework this to fit the current
master if really needed.

 diff-delta.c |   41 +++++++++++++++++++++++++++++++----------
 1 files changed, 31 insertions(+), 10 deletions(-)

diff --git a/diff-delta.c b/diff-delta.c
index e7c33aa..98795c6 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -207,19 +207,40 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	 * the reference buffer.
 	 */
 	for (i = 0; i < hsize; i++) {
-		if (hash_count[i] < HASH_LIMIT)
+		int acc;
+
+		if (hash_count[i] <= HASH_LIMIT)
 			continue;
+
+		entries -= hash_count[i] - HASH_LIMIT;
+		/* We leave exactly HASH_LIMIT entries in the bucket */
+
 		uentry = uhash[i];
+		acc = 0;
 		do {
-			struct unpacked_index_entry *keep = uentry;
-			int skip = hash_count[i] / HASH_LIMIT;
-			do {
-				--entries;
-				uentry = uentry->next;
-			} while(--skip && uentry);
-			++entries;
-			keep->next = uentry;
-		} while(uentry);
+			acc += hash_count[i] - HASH_LIMIT;
+			if (acc > 0) {
+				struct unpacked_index_entry *keep = uentry;
+				do {
+					uentry = uentry->next;
+					acc -= HASH_LIMIT;
+				} while (acc > 0);
+				keep->next = uentry->next;
+			}
+			uentry = uentry->next;
+		} while (uentry);
+
+		/* Assume that this loop is gone through exactly
+		 * HASH_LIMIT times and is entered and left with
+		 * acc==0.  So the first statement in the loop
+		 * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
+		 * to the accumulator, and the inner loop consequently
+		 * is run (hash_count[i]-HASH_LIMIT) times, removing
+		 * one element from the list each time.  Since acc
+		 * balances out to 0 at the final run, the inner loop
+		 * body can't be left with uentry==NULL.  So we indeed
+		 * encounter uentry==NULL in the outer loop only.
+		 */
 	}
 	free(hash_count);
 
-- 
1.5.3.GIT

^ permalink raw reply related

* Re: git-svn 1.5.3 does not understand grafts?
From: Junio C Hamano @ 2007-09-08 19:53 UTC (permalink / raw)
  To: Joakim Tjernlund; +Cc: 'Eric Wong', 'git'
In-Reply-To: <045501c7f23f$c359c450$5267a8c0@Jocke>

"Joakim Tjernlund" <joakim.tjernlund@transmode.se> writes:

> hmm, I think git-cat-file is to blame.
> git-cat-file commit da783cce390ce013b19f1d308ea6813269c6a6b5 does
> not list list any parent...

The plumbing cat-file does not deal with grafts and this is
deliberate.  Otherwise you would not be able to find the true
set of parents when you'd want to.

So do not blame cat-file, but blame the Porcelain that uses
cat-file to read a commit object, without annotating what it
read with what is in grafts, in this case your command line
experiment ;-).

The log family of commands and rev-list plumbing while
traversing commit ancestry chain do take grafts into account.

One caveat is pretty=raw output format shows true parents
without grafts on "parent " header line, while the "commit "
fake header prepended in the output for each commit shows the
parents that takes into account.

To illustrate, if you forge the history and say the parent of
1ddea77 is 5da1606 (when the true parent is 820eca68) with
grafts mechanism, here is what happens:

    $ echo '1ddea77e449ef28d8a7c74521af21121ab01abc0 5da1606d0bf5b970fadfa0ca91618a1e871f6755' >.git/info/grafts
    $ git show -s --pretty=raw --parents 1ddea77
    commit 1ddea77e449ef28d8a7c74521af21121ab01abc0 5da1606d0bf5b970fadfa0ca91618a1e871f6755
    tree e9e61bc801438062978ff47b0963c536ed1e51a9
    parent 820eca68c2577d7499d203d7f4f7ae479b577683
    author Nick Hengeveld <nickh@reactrix.com> 1127757131 -0700
    committer Junio C Hamano <junkio@cox.net> 1127805558 -0700

        [PATCH] Return CURL error message when object transfer fails

        Return CURL error message when object transfer fails
        ...
    $ git-cat-file commit 1ddea77
    tree e9e61bc801438062978ff47b0963c536ed1e51a9
    parent 820eca68c2577d7499d203d7f4f7ae479b577683
    author Nick Hengeveld <nickh@reactrix.com> 1127757131 -0700
    committer Junio C Hamano <junkio@cox.net> 1127805558 -0700

    [PATCH] Return CURL error message when object transfer fails

    Return CURL error message when object transfer fails
    ...

^ permalink raw reply

* Re: [PATCH] diff-delta.c: pack the index structure
From: David Kastrup @ 2007-09-08 20:50 UTC (permalink / raw)
  To: Nicolas Pitre; +Cc: git
In-Reply-To: <854pi5zh8q.fsf@lola.goethe.zz>

[-- Attachment #1: Type: text/plain, Size: 1794 bytes --]

David Kastrup <dak@gnu.org> writes:

> Another option avoiding the realloc would be not to use linked lists
> at all but just collect all entries sequentually in "packed" form,
> and sort them into order afterwards.  That's an O(n lg n) operation
> with a large n.  Even if one has a sorting algorithm with good
> memory locality, I doubt that the locality would compensate for the
> lg n factor, even when taking into account that we save ourselves
> the copying.  And that is not even taken the possibility of having
> to cull some buckets into account, another O(n) operation (which
> amounts to copying everything once, too).

As an illustration, I have implemented a proof-of-concept.  This is a
patch (not formatted for submission) against the current master.  It
takes about a 20% performance hit on the whole git-pack-objects run,
so the diffing code itself is likely affected worse.  For the
proof-of-concept I did not do the hash bucket collision culling, nor
did I realloc to the possibly reduced size.  So a fairer comparison
would likely involve removing the culling code from master (or
implementing the culling in the proof-of-concept, but I am too lazy
for that).

I hope this addresses the not-in-place complaint.  It is conceivable
that under tight memory conditions, this approach might actually work
out better.  However, the glibc qsort implementation (at least it did
so at one time) reverts to a mergesort for large numbers, and
allocates a temporary buffer of the same size as the original data.
If that is still the case, the memory impact would actually be worse
here.  One would need to implement a custom _real_ in place sorter to
get around this.  All in all, I don't think this approach is worth the
trouble: the sorting overhead factor of lg n is just too much.


[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #2: Type: text/x-patch, Size: 4158 bytes --]

diff --git a/diff-delta.c b/diff-delta.c
index 0dde2f2..f6e2416 100644
--- a/diff-delta.c
+++ b/diff-delta.c
@@ -115,7 +115,6 @@ static const unsigned int U[256] = {
 struct index_entry {
 	const unsigned char *ptr;
 	unsigned int val;
-	struct index_entry *next;
 };
 
 struct delta_index {
@@ -126,12 +125,24 @@ struct delta_index {
 	struct index_entry *hash[FLEX_ARRAY];
 };
 
+static unsigned int cmp_hmask;
+
+static int cmp_index_entry(const void *va, const void *vb)
+{
+	const struct index_entry *a = va, *b = vb;
+	if ((a->val & cmp_hmask) != (b->val & cmp_hmask))
+		return (a->val & cmp_hmask) < (b->val & cmp_hmask) ? -1 : 1;
+	if (a->val != b->val)
+		return a->val < b->val ? -1 : 1;
+	return a->ptr < b->ptr ? -1 : 1;
+}
+
 struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 {
-	unsigned int i, hsize, hmask, entries, prev_val, *hash_count;
+	unsigned int i, hsize, hmask, entries, prev_val, ihash;
 	const unsigned char *data, *buffer = buf;
 	struct delta_index *index;
-	struct index_entry *entry, **hash;
+	struct index_entry *entry, **hash, *entry_base;
 	void *mem;
 	unsigned long memsize;
 
@@ -149,7 +160,7 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 
 	/* allocate lookup index */
 	memsize = sizeof(*index) +
-		  sizeof(*hash) * hsize +
+		  sizeof(*hash) * (hsize + 1) +
 		  sizeof(*entry) * entries;
 	mem = malloc(memsize);
 	if (!mem)
@@ -157,21 +168,14 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 	index = mem;
 	mem = index + 1;
 	hash = mem;
-	mem = hash + hsize;
-	entry = mem;
+	mem = hash + hsize + 1;
+	entry_base = mem;
+	entry = entry_base;
 
 	index->memsize = memsize;
 	index->src_buf = buf;
 	index->src_size = bufsize;
 	index->hash_mask = hmask;
-	memset(hash, 0, hsize * sizeof(*hash));
-
-	/* allocate an array to count hash entries */
-	hash_count = calloc(hsize, sizeof(*hash_count));
-	if (!hash_count) {
-		free(index);
-		return NULL;
-	}
 
 	/* then populate the index */
 	prev_val = ~0;
@@ -184,29 +188,33 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 		if (val == prev_val) {
 			/* keep the lowest of consecutive identical blocks */
 			entry[-1].ptr = data + RABIN_WINDOW;
+			--entries;
 		} else {
 			prev_val = val;
 			i = val & hmask;
 			entry->ptr = data + RABIN_WINDOW;
 			entry->val = val;
-			entry->next = hash[i];
-			hash[i] = entry++;
-			hash_count[i]++;
+			entry++;
 		}
 	}
+	cmp_hmask = hmask;
+	qsort(entry_base, entries, sizeof(struct index_entry), cmp_index_entry);
+	ihash = 0;
+	
+	for (i=0; i<entries; i++) {
+		entry = &entry_base[i];
+		if ((entry->val & hmask) >= ihash) {
+			/* cull here */
+			do {
+				hash[ihash++] = entry;
+			} while ((entry->val & hmask) >= ihash);
+		}
+	}
+	while (ihash <= hsize) {
+		hash[ihash++] = &entry_base[entries];
+	}
 
-	/*
-	 * Determine a limit on the number of entries in the same hash
-	 * bucket.  This guards us against pathological data sets causing
-	 * really bad hash distribution with most entries in the same hash
-	 * bucket that would bring us to O(m*n) computing costs (m and n
-	 * corresponding to reference and target buffer sizes).
-	 *
-	 * Make sure none of the hash buckets has more entries than
-	 * we're willing to test.  Otherwise we cull the entry list
-	 * uniformly to still preserve a good repartition across
-	 * the reference buffer.
-	 */
+#if 0
 	for (i = 0; i < hsize; i++) {
 		if (hash_count[i] < HASH_LIMIT)
 			continue;
@@ -221,6 +229,7 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
 		} while(entry);
 	}
 	free(hash_count);
+#endif
 
 	return index;
 }
@@ -302,7 +311,7 @@ create_delta(const struct delta_index *index,
 			val ^= U[data[-RABIN_WINDOW]];
 			val = ((val << 8) | *data) ^ T[val >> RABIN_SHIFT];
 			i = val & index->hash_mask;
-			for (entry = index->hash[i]; entry; entry = entry->next) {
+			for (entry = index->hash[i]; entry < index->hash[i+1]; entry++) {
 				const unsigned char *ref = entry->ptr;
 				const unsigned char *src = data;
 				unsigned int ref_size = ref_top - ref;

[-- Attachment #3: Type: text/plain, Size: 52 bytes --]



-- 
David Kastrup, Kriemhildstr. 15, 44793 Bochum

^ permalink raw reply related

* Re: [PATCH] diff-delta.c: rename {a,}{entry,hash} to {,u}{entry,hash}
From: Nicolas Pitre @ 2007-09-08 20:52 UTC (permalink / raw)
  To: David Kastrup; +Cc: git
In-Reply-To: <f1161c08aeeca60b6c33af34ccea68fd99b9ea4e.1189243702.git.dak@gnu.org>

On Sat, 8 Sep 2007, David Kastrup wrote:

> The variables for the packed entries are now called just entry and
> hash rather than aentry+ahash, and those for the unpacked entries have
> been renamed to uentry and uhash from the original entry and hash.
> 
> While this makes the diff to the unchanged code larger, it matches the
> type declarations better.

Since the packed version is used less often, could you rename that one 
instead, and use packed_entry and packed_hash forclarity.

Also please fold this with your other patch (not the culling one).

Then you can add my ACK.


Nicolas

^ permalink raw reply


This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox