Merge branch 'lt/objlist' into next

* lt/objlist:
  Add "named object array" concept
  xdiff: minor changes to match libxdiff-0.21
  fix rfc2047 formatter.
  Fix t8001-annotate and t8002-blame for ActiveState Perl
  Add specialized object allocator

24 files changed, 241 insertions, 148 deletions

diff --git a/Makefile b/Makefile
index 99c9ec205..22bb47319 100644
--- a/Makefile
+++ b/Makefile
@@ -215,7 +215,7 @@ LIB_OBJS = \
 	server-info.o setup.o sha1_file.o sha1_name.o strbuf.o \
 	tag.o tree.o usage.o config.o environment.o ctype.o copy.o \
 	fetch-clone.o revision.o pager.o tree-walk.o xdiff-interface.o \
-	$(DIFF_OBJS)
+	alloc.o $(DIFF_OBJS)
 
 BUILTIN_OBJS = \
 	builtin-log.o builtin-help.o builtin-count.o builtin-diff.o builtin-push.o \
diff --git a/alloc.c b/alloc.c
new file mode 100644
index 000000000..e3b22f432
--- /dev/null
+++ b/alloc.c
@@ -0,0 +1,51 @@
+/*
+ * alloc.c  - specialized allocator for internal objects
+ *
+ * Copyright (C) 2006 Linus Torvalds
+ *
+ * The standard malloc/free wastes too much space for objects, partly because
+ * it maintains all the allocation infrastructure (which isn't needed, since
+ * we never free an object descriptor anyway), but even more because it ends
+ * up with maximal alignment because it doesn't know what the object alignment
+ * for the new allocation is.
+ */
+#include "cache.h"
+#include "object.h"
+#include "blob.h"
+#include "tree.h"
+#include "commit.h"
+#include "tag.h"
+
+#define BLOCKING 1024
+
+#define DEFINE_ALLOCATOR(name)					\
+static unsigned int name##_allocs;				\
+struct name *alloc_##name##_node(void)				\
+{								\
+	static int nr;						\
+	static struct name *block;				\
+								\
+	if (!nr) {						\
+		nr = BLOCKING;					\
+		block = xcalloc(BLOCKING, sizeof(struct name));	\
+	}							\
+	nr--;							\
+	name##_allocs++;					\
+	return block++;						\
+}
+
+DEFINE_ALLOCATOR(blob)
+DEFINE_ALLOCATOR(tree)
+DEFINE_ALLOCATOR(commit)
+DEFINE_ALLOCATOR(tag)
+
+#define REPORT(name)	\
+	fprintf(stderr, "%10s: %8u (%zu kB)\n", #name, name##_allocs, name##_allocs*sizeof(struct name) >> 10)
+
+void alloc_report(void)
+{
+	REPORT(blob);
+	REPORT(tree);
+	REPORT(commit);
+	REPORT(tag);
+}
diff --git a/blob.c b/blob.c
index 737700874..496f27004 100644
--- a/blob.c
+++ b/blob.c
@@ -8,7 +8,7 @@ struct blob *lookup_blob(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
 	if (!obj) {
-		struct blob *ret = xcalloc(1, sizeof(struct blob));
+		struct blob *ret = alloc_blob_node();
 		created_object(sha1, &ret->object);
 		ret->object.type = TYPE_BLOB;
 		return ret;
diff --git a/builtin-diff-files.c b/builtin-diff-files.c
index cebda828e..5afc1d720 100644
--- a/builtin-diff-files.c
+++ b/builtin-diff-files.c
@@ -41,7 +41,7 @@ int cmd_diff_files(int argc, const char **argv, char **envp)
 	 * rev.max_count is reasonable (0 <= n <= 3),
 	 * there is no other revision filtering parameters.
 	 */
-	if (rev.pending_objects ||
+	if (rev.pending.nr ||
 	    rev.min_age != -1 || rev.max_age != -1)
 		usage(diff_files_usage);
 	/*
diff --git a/builtin-diff-index.c b/builtin-diff-index.c
index 1958580d8..c42ef9a7a 100644
--- a/builtin-diff-index.c
+++ b/builtin-diff-index.c
@@ -32,7 +32,7 @@ int cmd_diff_index(int argc, const char **argv, char **envp)
 	 * Make sure there is one revision (i.e. pending object),
 	 * and there is no revision filtering parameters.
 	 */
-	if (!rev.pending_objects || rev.pending_objects->next ||
+	if (rev.pending.nr != 1 ||
 	    rev.max_count != -1 || rev.min_age != -1 || rev.max_age != -1)
 		usage(diff_cache_usage);
 	return run_diff_index(&rev, cached);
diff --git a/builtin-diff-tree.c b/builtin-diff-tree.c
index 58cf65856..3409a39a9 100644
--- a/builtin-diff-tree.c
+++ b/builtin-diff-tree.c
@@ -65,7 +65,6 @@ int cmd_diff_tree(int argc, const char **argv, char **envp)
 	char line[1000];
 	struct object *tree1, *tree2;
 	static struct rev_info *opt = &log_tree_opt;
-	struct object_list *list;
 	int read_stdin = 0;
 
 	git_config(git_diff_config);
@@ -86,45 +85,28 @@ int cmd_diff_tree(int argc, const char **argv, char **envp)
 	}
 
 	/*
-	 * NOTE! "setup_revisions()" will have inserted the revisions
-	 * it parsed in reverse order. So if you do
-	 *
-	 *	git-diff-tree a b
-	 *
-	 * the commit list will be "b" -> "a" -> NULL, so we reverse
-	 * the order of the objects if the first one is not marked
-	 * UNINTERESTING.
+	 * NOTE! We expect "a ^b" to be equal to "a..b", so we
+	 * reverse the order of the objects if the second one
+	 * is marked UNINTERESTING.
 	 */
-	nr_sha1 = 0;
-	list = opt->pending_objects;
-	if (list) {
-		nr_sha1++;
-		tree1 = list->item;
-		list = list->next;
-		if (list) {
-			nr_sha1++;
-			tree2 = tree1;
-			tree1 = list->item;
-			if (list->next)
-				usage(diff_tree_usage);
-			/* Switch them around if the second one was uninteresting.. */
-			if (tree2->flags & UNINTERESTING) {
-				struct object *tmp = tree2;
-				tree2 = tree1;
-				tree1 = tmp;
-			}
-		}
-	}
-
+	nr_sha1 = opt->pending.nr;
 	switch (nr_sha1) {
 	case 0:
 		if (!read_stdin)
 			usage(diff_tree_usage);
 		break;
 	case 1:
+		tree1 = opt->pending.objects[0].item;
 		diff_tree_commit_sha1(tree1->sha1);
 		break;
 	case 2:
+		tree1 = opt->pending.objects[0].item;
+		tree2 = opt->pending.objects[1].item;
+		if (tree2->flags & UNINTERESTING) {
+			struct object *tmp = tree2;
+			tree2 = tree1;
+			tree1 = tmp;
+		}
 		diff_tree_sha1(tree1->sha1,
 			       tree2->sha1,
 			       "", &opt->diffopt);
diff --git a/builtin-diff.c b/builtin-diff.c
index 6ac3d4b8c..99a2f7660 100644
--- a/builtin-diff.c
+++ b/builtin-diff.c
@@ -50,7 +50,7 @@ static int builtin_diff_files(struct rev_info *revs,
 	 * specified rev.max_count is reasonable (0 <= n <= 3), and
 	 * there is no other revision filtering parameter.
 	 */
-	if (revs->pending_objects ||
+	if (revs->pending.nr ||
 	    revs->min_age != -1 ||
 	    revs->max_age != -1 ||
 	    3 < revs->max_count)
@@ -172,7 +172,7 @@ static int builtin_diff_index(struct rev_info *revs,
 	 * Make sure there is one revision (i.e. pending object),
 	 * and there is no revision filtering parameters.
 	 */
-	if (!revs->pending_objects || revs->pending_objects->next ||
+	if (revs->pending.nr != 1 ||
 	    revs->max_count != -1 || revs->min_age != -1 ||
 	    revs->max_age != -1)
 		usage(builtin_diff_usage);
@@ -181,10 +181,10 @@ static int builtin_diff_index(struct rev_info *revs,
 
 static int builtin_diff_tree(struct rev_info *revs,
 			     int argc, const char **argv,
-			     struct object_list *ent)
+			     struct object_array_entry *ent)
 {
 	const unsigned char *(sha1[2]);
-	int swap = 1;
+	int swap = 0;
 	while (1 < argc) {
 		const char *arg = argv[1];
 		if (!strcmp(arg, "--raw"))
@@ -195,10 +195,10 @@ static int builtin_diff_tree(struct rev_info *revs,
 	}
 
 	/* We saw two trees, ent[0] and ent[1].
-	 * unless ent[0] is unintesting, they are swapped
+	 * if ent[1] is unintesting, they are swapped
 	 */
-	if (ent[0].item->flags & UNINTERESTING)
-		swap = 0;
+	if (ent[1].item->flags & UNINTERESTING)
+		swap = 1;
 	sha1[swap] = ent[0].item->sha1;
 	sha1[1-swap] = ent[1].item->sha1;
 	diff_tree_sha1(sha1[0], sha1[1], "", &revs->diffopt);
@@ -208,7 +208,7 @@ static int builtin_diff_tree(struct rev_info *revs,
 
 static int builtin_diff_combined(struct rev_info *revs,
 				 int argc, const char **argv,
-				 struct object_list *ent,
+				 struct object_array_entry *ent,
 				 int ents)
 {
 	const unsigned char (*parent)[20];
@@ -242,13 +242,14 @@ void add_head(struct rev_info *revs)
 	obj = parse_object(sha1);
 	if (!obj)
 		return;
-	add_object(obj, &revs->pending_objects, NULL, "HEAD");
+	add_pending_object(revs, obj, "HEAD");
 }
 
 int cmd_diff(int argc, const char **argv, char **envp)
 {
+	int i;
 	struct rev_info rev;
-	struct object_list *list, ent[100];
+	struct object_array_entry ent[100];
 	int ents = 0, blobs = 0, paths = 0;
 	const char *path = NULL;
 	struct blobinfo blob[2];
@@ -281,7 +282,7 @@ int cmd_diff(int argc, const char **argv, char **envp)
 	/* Do we have --cached and not have a pending object, then
 	 * default to HEAD by hand.  Eek.
 	 */
-	if (!rev.pending_objects) {
+	if (!rev.pending.nr) {
 		int i;
 		for (i = 1; i < argc; i++) {
 			const char *arg = argv[i];
@@ -294,7 +295,8 @@ int cmd_diff(int argc, const char **argv, char **envp)
 		}
 	}
 
-	for (list = rev.pending_objects; list; list = list->next) {
+	for (i = 0; i < rev.pending.nr; i++) {
+		struct object_array_entry *list = rev.pending.objects+i;
 		struct object *obj = list->item;
 		const char *name = list->name;
 		int flags = (obj->flags & UNINTERESTING);
diff --git a/builtin-grep.c b/builtin-grep.c
index 980649926..6a240fb6e 100644
--- a/builtin-grep.c
+++ b/builtin-grep.c
@@ -657,7 +657,7 @@ int cmd_grep(int argc, const char **argv, char **envp)
 	int cached = 0;
 	int seen_dashdash = 0;
 	struct grep_opt opt;
-	struct object_list *list, **tail, *object_list = NULL;
+	struct object_array list = { 0, 0, NULL };
 	const char *prefix = setup_git_directory();
 	const char **paths = NULL;
 	int i;
@@ -677,7 +677,6 @@ int cmd_grep(int argc, const char **argv, char **envp)
 	 * that continues up to the -- (if exists), and then paths.
 	 */
 
-	tail = &object_list;
 	while (1 < argc) {
 		const char *arg = argv[1];
 		argc--; argv++;
@@ -851,12 +850,9 @@ int cmd_grep(int argc, const char **argv, char **envp)
 		/* Is it a rev? */
 		if (!get_sha1(arg, sha1)) {
 			struct object *object = parse_object(sha1);
-			struct object_list *elem;
 			if (!object)
 				die("bad object %s", arg);
-			elem = object_list_insert(object, tail);
-			elem->name = arg;
-			tail = &elem->next;
+			add_object_array(object, arg, &list);
 			continue;
 		}
 		if (!strcmp(arg, "--")) {
@@ -881,16 +877,16 @@ int cmd_grep(int argc, const char **argv, char **envp)
 		paths[1] = NULL;
 	}
 
-	if (!object_list)
+	if (!list.nr)
 		return !grep_cache(&opt, paths, cached);
 
 	if (cached)
 		die("both --cached and trees are given.");
 
-	for (list = object_list; list; list = list->next) {
+	for (i = 0; i < list.nr; i++) {
 		struct object *real_obj;
-		real_obj = deref_tag(list->item, NULL, 0);
-		if (grep_object(&opt, paths, real_obj, list->name))
+		real_obj = deref_tag(list.objects[i].item, NULL, 0);
+		if (grep_object(&opt, paths, real_obj, list.objects[i].name))
 			hit = 1;
 	}
 	return !hit;
diff --git a/builtin-log.c b/builtin-log.c
index 9187fd337..5a8a50b81 100644
--- a/builtin-log.c
+++ b/builtin-log.c
@@ -257,8 +257,8 @@ int cmd_format_patch(int argc, const char **argv, char **envp)
 			    output_directory);
 	}
 
-	if (rev.pending_objects && rev.pending_objects->next == NULL) {
-		rev.pending_objects->item->flags |= UNINTERESTING;
+	if (rev.pending.nr == 1) {
+		rev.pending.objects[0].item->flags |= UNINTERESTING;
 		add_head(&rev);
 	}
 
diff --git a/builtin-rev-list.c b/builtin-rev-list.c
index 71353eb19..63bad0e96 100644
--- a/builtin-rev-list.c
+++ b/builtin-rev-list.c
@@ -99,26 +99,26 @@ static void show_commit(struct commit *commit)
 	}
 }
 
-static struct object_list **process_blob(struct blob *blob,
-					 struct object_list **p,
-					 struct name_path *path,
-					 const char *name)
+static void process_blob(struct blob *blob,
+			 struct object_array *p,
+			 struct name_path *path,
+			 const char *name)
 {
 	struct object *obj = &blob->object;
 
 	if (!revs.blob_objects)
-		return p;
+		return;
 	if (obj->flags & (UNINTERESTING | SEEN))
-		return p;
+		return;
 	obj->flags |= SEEN;
 	name = strdup(name);
-	return add_object(obj, p, path, name);
+	add_object(obj, p, path, name);
 }
 
-static struct object_list **process_tree(struct tree *tree,
-					 struct object_list **p,
-					 struct name_path *path,
-					 const char *name)
+static void process_tree(struct tree *tree,
+			 struct object_array *p,
+			 struct name_path *path,
+			 const char *name)
 {
 	struct object *obj = &tree->object;
 	struct tree_desc desc;
@@ -126,14 +126,14 @@ static struct object_list **process_tree(struct tree *tree,
 	struct name_path me;
 
 	if (!revs.tree_objects)
-		return p;
+		return;
 	if (obj->flags & (UNINTERESTING | SEEN))
-		return p;
+		return;
 	if (parse_tree(tree) < 0)
 		die("bad tree object %s", sha1_to_hex(obj->sha1));
 	obj->flags |= SEEN;
 	name = strdup(name);
-	p = add_object(obj, p, path, name);
+	add_object(obj, p, path, name);
 	me.up = path;
 	me.elem = name;
 	me.elem_len = strlen(name);
@@ -143,57 +143,59 @@ static struct object_list **process_tree(struct tree *tree,
 
 	while (tree_entry(&desc, &entry)) {
 		if (S_ISDIR(entry.mode))
-			p = process_tree(lookup_tree(entry.sha1), p, &me, entry.path);
+			process_tree(lookup_tree(entry.sha1), p, &me, entry.path);
 		else
-			p = process_blob(lookup_blob(entry.sha1), p, &me, entry.path);
+			process_blob(lookup_blob(entry.sha1), p, &me, entry.path);
 	}
 	free(tree->buffer);
 	tree->buffer = NULL;
-	return p;
 }
 
 static void show_commit_list(struct rev_info *revs)
 {
+	int i;
 	struct commit *commit;
-	struct object_list *objects = NULL, **p = &objects, *pending;
+	struct object_array objects = { 0, 0, NULL };
 
 	while ((commit = get_revision(revs)) != NULL) {
-		p = process_tree(commit->tree, p, NULL, "");
+		process_tree(commit->tree, &objects, NULL, "");
 		show_commit(commit);
 	}
-	for (pending = revs->pending_objects; pending; pending = pending->next) {
+	for (i = 0; i < revs->pending.nr; i++) {
+		struct object_array_entry *pending = revs->pending.objects + i;
 		struct object *obj = pending->item;
 		const char *name = pending->name;
 		if (obj->flags & (UNINTERESTING | SEEN))
 			continue;
 		if (obj->type == TYPE_TAG) {
 			obj->flags |= SEEN;
-			p = add_object(obj, p, NULL, name);
+			add_object_array(obj, name, &objects);
 			continue;
 		}
 		if (obj->type == TYPE_TREE) {
-			p = process_tree((struct tree *)obj, p, NULL, name);
+			process_tree((struct tree *)obj, &objects, NULL, name);
 			continue;
 		}
 		if (obj->type == TYPE_BLOB) {
-			p = process_blob((struct blob *)obj, p, NULL, name);
+			process_blob((struct blob *)obj, &objects, NULL, name);
 			continue;
 		}
 		die("unknown pending object %s (%s)", sha1_to_hex(obj->sha1), name);
 	}
-	while (objects) {
+	for (i = 0; i < objects.nr; i++) {
+		struct object_array_entry *p = objects.objects + i;
+
 		/* An object with name "foo\n0000000..." can be used to
 		 * confuse downstream git-pack-objects very badly.
 		 */
-		const char *ep = strchr(objects->name, '\n');
+		const char *ep = strchr(p->name, '\n');
 		if (ep) {
-			printf("%s %.*s\n", sha1_to_hex(objects->item->sha1),
-			       (int) (ep - objects->name),
-			       objects->name);
+			printf("%s %.*s\n", sha1_to_hex(p->item->sha1),
+			       (int) (ep - p->name),
+			       p->name);
 		}
 		else
-			printf("%s %s\n", sha1_to_hex(objects->item->sha1), objects->name);
-		objects = objects->next;
+			printf("%s %s\n", sha1_to_hex(p->item->sha1), p->name);
 	}
 }
 
@@ -348,7 +350,7 @@ int cmd_rev_list(int argc, const char **argv, char **envp)
 
 	if ((!list &&
 	     (!(revs.tag_objects||revs.tree_objects||revs.blob_objects) &&
-	      !revs.pending_objects)) ||
+	      !revs.pending.nr)) ||
 	    revs.diff)
 		usage(rev_list_usage);
 
diff --git a/cache.h b/cache.h
index 7fcb6d406..eaa5c0c35 100644
--- a/cache.h
+++ b/cache.h
@@ -384,4 +384,15 @@ extern void setup_pager(void);
 int decode_85(char *dst, char *line, int linelen);
 void encode_85(char *buf, unsigned char *data, int bytes);
 
+/* alloc.c */
+struct blob;
+struct tree;
+struct commit;
+struct tag;
+extern struct blob *alloc_blob_node(void);
+extern struct tree *alloc_tree_node(void);
+extern struct commit *alloc_commit_node(void);
+extern struct tag *alloc_tag_node(void);
+extern void alloc_report(void);
+
 #endif /* CACHE_H */
diff --git a/commit.c b/commit.c
index 5914200a2..946615d2a 100644
--- a/commit.c
+++ b/commit.c
@@ -84,7 +84,7 @@ struct commit *lookup_commit(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
 	if (!obj) {
-		struct commit *ret = xcalloc(1, sizeof(struct commit));
+		struct commit *ret = alloc_commit_node();
 		created_object(sha1, &ret->object);
 		ret->object.type = TYPE_COMMIT;
 		return ret;
@@ -447,7 +447,7 @@ static int add_rfc2047(char *buf, const char *line, int len)
 	memcpy(bp, q_utf8, sizeof(q_utf8)-1);
 	bp += sizeof(q_utf8)-1;
 	for (i = 0; i < len; i++) {
-		unsigned ch = line[i];
+		unsigned ch = line[i] & 0xFF;
 		if (is_rfc2047_special(ch)) {
 			sprintf(bp, "=%02X", ch);
 			bp += 3;
@@ -571,10 +571,23 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt, const struct commit *commit
 	 * to say this is not a 7-bit ASCII.
 	 */
 	if (fmt == CMIT_FMT_EMAIL && !after_subject) {
-		int i;
-		for (i = 0; !plain_non_ascii && msg[i] && i < len; i++)
-			if (msg[i] & 0x80)
+		int i, ch, in_body;
+
+		for (in_body = i = 0; (ch = msg[i]) && i < len; i++) {
+			if (!in_body) {
+				/* author could be non 7-bit ASCII but
+				 * the log may so; skip over the
+				 * header part first.
+				 */
+				if (ch == '\n' &&
+				    i + 1 < len && msg[i+1] == '\n')
+					in_body = 1;
+			}
+			else if (ch & 0x80) {
 				plain_non_ascii = 1;
+				break;
+			}
+		}
 	}
 
 	for (;;) {
diff --git a/diff-lib.c b/diff-lib.c
index fdc11732d..116b5a9d6 100644
--- a/diff-lib.c
+++ b/diff-lib.c
@@ -332,8 +332,8 @@ int run_diff_index(struct rev_info *revs, int cached)
 	}
 	mark_merge_entries();
 
-	ent = revs->pending_objects->item;
-	tree_name = revs->pending_objects->name;
+	ent = revs->pending.objects[0].item;
+	tree_name = revs->pending.objects[0].name;
 	tree = parse_tree_indirect(ent->sha1);
 	if (!tree)
 		return error("bad tree object %s", tree_name);
diff --git a/http-push.c b/http-push.c
index aaf155c5b..2e7d02281 100644
--- a/http-push.c
+++ b/http-push.c
@@ -1172,7 +1172,7 @@ static void one_remote_object(const char *hex)
 
 	obj->flags |= REMOTE;
 	if (!object_list_contains(objects, obj))
-		add_object(obj, &objects, NULL, "");
+		object_list_insert(obj, &objects);
 }
 
 static void handle_lockprop_ctx(struct xml_ctx *ctx, int tag_closed)
@@ -1700,6 +1700,15 @@ static int locking_available(void)
 	return lock_flags;
 }
 
+struct object_list **add_one_object(struct object *obj, struct object_list **p)
+{
+	struct object_list *entry = xmalloc(sizeof(struct object_list));
+	entry->item = obj;
+	entry->next = *p;
+	*p = entry;
+	return &entry->next;
+}
+
 static struct object_list **process_blob(struct blob *blob,
 					 struct object_list **p,
 					 struct name_path *path,
@@ -1713,8 +1722,7 @@ static struct object_list **process_blob(struct blob *blob,
 		return p;
 
 	obj->flags |= SEEN;
-	name = strdup(name);
-	return add_object(obj, p, path, name);
+	return add_one_object(obj, p);
 }
 
 static struct object_list **process_tree(struct tree *tree,
@@ -1736,7 +1744,7 @@ static struct object_list **process_tree(struct tree *tree,
 
 	obj->flags |= SEEN;
 	name = strdup(name);
-	p = add_object(obj, p, NULL, name);
+	p = add_one_object(obj, p);
 	me.up = path;
 	me.elem = name;
 	me.elem_len = strlen(name);
@@ -1757,8 +1765,9 @@ static struct object_list **process_tree(struct tree *tree,
 
 static int get_delta(struct rev_info *revs, struct remote_lock *lock)
 {
+	int i;
 	struct commit *commit;
-	struct object_list **p = &objects, *pending;
+	struct object_list **p = &objects;
 	int count = 0;
 
 	while ((commit = get_revision(revs)) != NULL) {
@@ -1768,15 +1777,16 @@ static int get_delta(struct rev_info *revs, struct remote_lock *lock)
 			count += add_send_request(&commit->object, lock);
 	}
 
-	for (pending = revs->pending_objects; pending; pending = pending->next) {
-		struct object *obj = pending->item;
-		const char *name = pending->name;
+	for (i = 0; i < revs->pending.nr; i++) {
+		struct object_array_entry *entry = revs->pending.objects + i;
+		struct object *obj = entry->item;
+		const char *name = entry->name;
 
 		if (obj->flags & (UNINTERESTING | SEEN))
 			continue;
 		if (obj->type == TYPE_TAG) {
 			obj->flags |= SEEN;
-			p = add_object(obj, p, NULL, name);
+			p = add_one_object(obj, p);
 			continue;
 		}
 		if (obj->type == TYPE_TREE) {
diff --git a/name-rev.c b/name-rev.c
index c29b93ea7..3a5ac35d1 100644
--- a/name-rev.c
+++ b/name-rev.c
@@ -125,11 +125,10 @@ static const char* get_rev_name(struct object *o)
 
 	return buffer;
 }
-	
+
 int main(int argc, char **argv)
 {
-	struct object_list *revs = NULL;
-	struct object_list **walker = &revs;
+	struct object_array revs = { 0, 0, NULL };
 	int as_is = 0, all = 0, transform_stdin = 0;
 
 	setup_git_directory();
@@ -184,9 +183,7 @@ int main(int argc, char **argv)
 		if (cutoff > commit->date)
 			cutoff = commit->date;
 
-		object_list_append((struct object *)commit, walker);
-		(*walker)->name = *argv;
-		walker = &((*walker)->next);
+		add_object_array((struct object *)commit, *argv, &revs);
 	}
 
 	for_each_ref(name_ref);
@@ -243,9 +240,13 @@ int main(int argc, char **argv)
 			if (objs[i])
 				printf("%s %s\n", sha1_to_hex(objs[i]->sha1),
 						get_rev_name(objs[i]));
-	} else
-		for ( ; revs; revs = revs->next)
-			printf("%s %s\n", revs->name, get_rev_name(revs->item));
+	} else {
+		int i;
+		for (i = 0; i < revs.nr; i++)
+			printf("%s %s\n",
+				revs.objects[i].name,
+				get_rev_name(revs.objects[i].item));
+	}
 
 	return 0;
 }
diff --git a/object.c b/object.c
index e26e319cc..37784cee9 100644
--- a/object.c
+++ b/object.c
@@ -200,3 +200,20 @@ int object_list_contains(struct object_list *list, struct object *obj)
 	}
 	return 0;
 }
+
+void add_object_array(struct object *obj, const char *name, struct object_array *array)
+{
+	unsigned nr = array->nr;
+	unsigned alloc = array->alloc;
+	struct object_array_entry *objects = array->objects;
+
+	if (nr >= alloc) {
+		alloc = (alloc + 32) * 2;
+		objects = xrealloc(objects, alloc * sizeof(*objects));
+		array->alloc = alloc;
+		array->objects = objects;
+	}
+	objects[nr].item = obj;
+	objects[nr].name = name;
+	array->nr = ++nr;
+}
diff --git a/object.h b/object.h
index c537b4b72..6f23a9a18 100644
--- a/object.h
+++ b/object.h
@@ -4,7 +4,6 @@
 struct object_list {
 	struct object *item;
 	struct object_list *next;
-	const char *name;
 };
 
 struct object_refs {
@@ -13,6 +12,15 @@ struct object_refs {
 	struct object *ref[FLEX_ARRAY]; /* more */
 };
 
+struct object_array {
+	unsigned int nr;
+	unsigned int alloc;
+	struct object_array_entry {
+		struct object *item;
+		const char *name;
+	} *objects;
+};
+
 #define TYPE_BITS   3
 #define FLAG_BITS  27
 
@@ -72,4 +80,7 @@ unsigned object_list_length(struct object_list *list);
 
 int object_list_contains(struct object_list *list, struct object *obj);
 
+/* Object array handling .. */
+void add_object_array(struct object *obj, const char *name, struct object_array *array);
+
 #endif /* OBJECT_H */
diff --git a/revision.c b/revision.c
index 7bff2a10b..b963f2adf 100644
--- a/revision.c
+++ b/revision.c
@@ -31,17 +31,12 @@ static char *path_name(struct name_path *path, const char *name)
 	return n;
 }
 
-struct object_list **add_object(struct object *obj,
-				       struct object_list **p,
-				       struct name_path *path,
-				       const char *name)
+void add_object(struct object *obj,
+		struct object_array *p,
+		struct name_path *path,
+		const char *name)
 {
-	struct object_list *entry = xmalloc(sizeof(*entry));
-	entry->item = obj;
-	entry->next = *p;
-	entry->name = path_name(path, name);
-	*p = entry;
-	return &entry->next;
+	add_object_array(obj, path_name(path, name), p);
 }
 
 static void mark_blob_uninteresting(struct blob *blob)
@@ -117,9 +112,9 @@ void mark_parents_uninteresting(struct commit *commit)
 	}
 }
 
-static void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)
+void add_pending_object(struct rev_info *revs, struct object *obj, const char *name)
 {
-	add_object(obj, &revs->pending_objects, NULL, name);
+	add_object_array(obj, name, &revs->pending);
 }
 
 static struct object *get_reference(struct rev_info *revs, const char *name, const unsigned char *sha1, unsigned int flags)
@@ -836,7 +831,7 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 		object = get_reference(revs, arg, sha1, flags ^ local_flags);
 		add_pending_object(revs, object, arg);
 	}
-	if (def && !revs->pending_objects) {
+	if (def && !revs->pending.nr) {
 		unsigned char sha1[20];
 		struct object *object;
 		if (get_sha1(def, sha1))
@@ -868,11 +863,13 @@ int setup_revisions(int argc, const char **argv, struct rev_info *revs, const ch
 
 void prepare_revision_walk(struct rev_info *revs)
 {
-	struct object_list *list;
+	int nr = revs->pending.nr;
+	struct object_array_entry *list = revs->pending.objects;
 
-	list = revs->pending_objects;
-	revs->pending_objects = NULL;
-	while (list) {
+	revs->pending.nr = 0;
+	revs->pending.alloc = 0;
+	revs->pending.objects = NULL;
+	while (--nr >= 0) {
 		struct commit *commit = handle_commit(revs, list->item, list->name);
 		if (commit) {
 			if (!(commit->object.flags & SEEN)) {
@@ -880,7 +877,7 @@ void prepare_revision_walk(struct rev_info *revs)
 				insert_by_date(commit, &revs->commits);
 			}
 		}
-		list = list->next;
+		list++;
 	}
 
 	if (revs->no_walk)
diff --git a/revision.h b/revision.h
index 4020e25c3..c010a0811 100644
--- a/revision.h
+++ b/revision.h
@@ -18,7 +18,7 @@ typedef void (prune_fn_t)(struct rev_info *revs, struct commit *commit);
 struct rev_info {
 	/* Starting list */
 	struct commit_list *commits;
-	struct object_list *pending_objects;
+	struct object_array pending;
 
 	/* Basic information */
 	const char *prefix;
@@ -99,9 +99,11 @@ struct name_path {
 	const char *elem;
 };
 
-extern struct object_list **add_object(struct object *obj,
-				       struct object_list **p,
-				       struct name_path *path,
-				       const char *name);
+extern void add_object(struct object *obj,
+		       struct object_array *p,
+		       struct name_path *path,
+		       const char *name);
+
+extern void add_pending_object(struct rev_info *revs, struct object *obj, const char *name);
 
 #endif
diff --git a/t/annotate-tests.sh b/t/annotate-tests.sh
index c04f0e154..1148b0257 100644
--- a/t/annotate-tests.sh
+++ b/t/annotate-tests.sh
@@ -111,7 +111,7 @@ test_expect_success \
 
 test_expect_success \
     'some edit' \
-    'perl -pi -e "s/^1A.*\n$//; s/^3A/99/" file &&
+    'perl -p -i.orig -e "s/^1A.*\n$//; s/^3A/99/" file &&
     GIT_AUTHOR_NAME="D" git commit -a -m "edit"'
 
 test_expect_success \
diff --git a/tag.c b/tag.c
index 919133327..5f70a5b81 100644
--- a/tag.c
+++ b/tag.c
@@ -19,7 +19,7 @@ struct tag *lookup_tag(const unsigned char *sha1)
 {
         struct object *obj = lookup_object(sha1);
         if (!obj) {
-                struct tag *ret = xcalloc(1, sizeof(struct tag));
+                struct tag *ret = alloc_tag_node();
                 created_object(sha1, &ret->object);
                 ret->object.type = TYPE_TAG;
                 return ret;
diff --git a/tree.c b/tree.c
index 64422fd27..10236555c 100644
--- a/tree.c
+++ b/tree.c
@@ -129,7 +129,7 @@ struct tree *lookup_tree(const unsigned char *sha1)
 {
 	struct object *obj = lookup_object(sha1);
 	if (!obj) {
-		struct tree *ret = xcalloc(1, sizeof(struct tree));
+		struct tree *ret = alloc_tree_node();
 		created_object(sha1, &ret->object);
 		ret->object.type = TYPE_TREE;
 		return ret;
diff --git a/xdiff/xutils.c b/xdiff/xutils.c
index 21ab8e7e2..f91b40347 100644
--- a/xdiff/xutils.c
+++ b/xdiff/xutils.c
@@ -44,21 +44,18 @@ long xdl_bogosqrt(long n) {
 
 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
 		     xdemitcb_t *ecb) {
+	int i = 2;
 	mmbuffer_t mb[3];
-	int i;
 
 	mb[0].ptr = (char *) pre;
 	mb[0].size = psize;
 	mb[1].ptr = (char *) rec;
 	mb[1].size = size;
-	i = 2;
-
-	if (!size || rec[size-1] != '\n') {
-		mb[2].ptr = "\n\\ No newline at end of file\n";
+	if (size > 0 && rec[size - 1] != '\n') {
+		mb[2].ptr = (char *) "\n\\ No newline at end of file\n";
 		mb[2].size = strlen(mb[2].ptr);
-		i = 3;
+		i++;
 	}
-
 	if (ecb->outf(ecb->priv, mb, i) < 0) {
 
 		return -1;
diff --git a/xdiff/xutils.h b/xdiff/xutils.h
index ea38ee903..08691a244 100644
--- a/xdiff/xutils.h
+++ b/xdiff/xutils.h
@@ -24,6 +24,7 @@
 #define XUTILS_H
 
 
+
 long xdl_bogosqrt(long n);
 int xdl_emit_diffrec(char const *rec, long size, char const *pre, long psize,
 		     xdemitcb_t *ecb);