[PATCH 0/6] Introduce commit notes

@@ -458,7 +458,7 @@ 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)
+int get_line_length(const char *msg, unsigned long len)
 {
 	int ret = 0;
 

@@ -950,7 +950,7 @@ static void pp_header(enum cmit_fmt fmt,
 	for (;;) {
 		const char *line = *msg_p;
 		char *dst;
-		int linelen = get_one_line(*msg_p, *len_p);
+		int linelen = get_line_length(*msg_p, *len_p);
 		unsigned long len;
 
 		if (!linelen)

@@ -1041,7 +1041,7 @@ static void pp_title_line(enum cmit_fmt fmt,
 	title = xmalloc(title_alloc);
 	for (;;) {
 		const char *line = *msg_p;
-		int linelen = get_one_line(line, *len_p);
+		int linelen = get_line_length(line, *len_p);
 		*msg_p += linelen;
 		*len_p -= linelen;
 

@@ -1118,7 +1118,7 @@ static void pp_remainder(enum cmit_fmt fmt,
 	int first = 1;
 	for (;;) {
 		const char *line = *msg_p;
-		int linelen = get_one_line(line, *len_p);
+		int linelen = get_line_length(line, *len_p);
 		*msg_p += linelen;
 		*len_p -= linelen;
 

@@ -1214,7 +1214,7 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt,
 
 	/* Skip excess blank lines at the beginning of body, if any... */
 	for (;;) {
-		int linelen = get_one_line(msg, len);
+		int linelen = get_line_length(msg, len);
 		int ll = linelen;
 		if (!linelen)
 			break;

@@ -60,6 +60,7 @@ enum cmit_fmt {
 	CMIT_FMT_UNSPECIFIED,
 };
 
+extern int get_line_length(const char *msg, unsigned long len);
 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);
 

@@ -285,6 +285,21 @@ core.pager::
 	The command that git will use to paginate output.  Can be overridden
 	with the `GIT_PAGER` environment variable.
 
+core.notesRef::
+	When showing commit messages, also show notes which are stored in
+	the given ref.  This ref is expected to contain paths of the form
+	??/*, where the directory name consists of the first two
+	characters of the commit name, and the base name consists of
+	the remaining 38 characters.
++
+If such a path exists in the given ref, the referenced blob is read, and
+appended to the commit message, separated by a "Notes:" line.  If the
+given ref itself does not exist, it is not an error, but means that no
+notes should be print.
++
+This setting defaults to "refs/notes/commits", and can be overridden by
+the `GIT_NOTES_REF` environment variable.
+
 alias.*::
 	Command aliases for the gitlink:git[1] command wrapper - e.g.
 	after defining "alias.last = cat-file commit HEAD", the invocation

@@ -322,7 +322,8 @@ LIB_OBJS = \
 	write_or_die.o trace.o list-objects.o grep.o match-trees.o \
 	alloc.o merge-file.o path-list.o help.o unpack-trees.o $(DIFF_OBJS) \
 	color.o wt-status.o archive-zip.o archive-tar.o shallow.o utf8.o \
-	convert.o attr.o decorate.o progress.o mailmap.o symlinks.o remote.o
+	convert.o attr.o decorate.o progress.o mailmap.o symlinks.o remote.o \
+	notes.o
 
 BUILTIN_OBJS = \
 	builtin-add.o \

@@ -309,6 +309,7 @@ extern size_t packed_git_window_size;
 extern size_t packed_git_limit;
 extern size_t delta_base_cache_limit;
 extern int auto_crlf;
+extern char *notes_ref_name;
 
 #define GIT_REPO_VERSION 0
 extern int repository_format_version;

@@ -6,6 +6,7 @@
 #include "interpolate.h"
 #include "diff.h"
 #include "revision.h"
+#include "notes.h"
 
 int save_commit_buffer = 1;
 

@@ -1254,6 +1255,10 @@ unsigned long pretty_print_commit(enum cmit_fmt fmt,
 	 */
 	if (fmt == CMIT_FMT_EMAIL && offset <= beginning_of_body)
 		buf[offset++] = '\n';
+
+	if (fmt != CMIT_FMT_ONELINE)
+		get_commit_notes(commit, buf_p, &offset, space_p);
+
 	buf[offset] = '\0';
 	free(reencoded);
 	return offset;

@@ -395,6 +395,11 @@ int git_default_config(const char *var, const char *value)
 		return 0;
 	}
 
+	if (!strcmp(var, "core.notesref")) {
+		notes_ref_name = xstrdup(value);
+		return 0;
+	}
+
 	if (!strcmp(var, "user.name")) {
 		strlcpy(git_default_name, value, sizeof(git_default_name));
 		return 0;

@@ -34,6 +34,7 @@ char *pager_program;
 int pager_in_use;
 int pager_use_color = 1;
 int auto_crlf = 0;	/* 1: both ways, -1: only when adding git objects */
+char *notes_ref_name;
 
 static const char *git_dir;
 static char *git_object_dir, *git_index_file, *git_refs_dir, *git_graft_file;

@@ -0,0 +1,64 @@
+#include "cache.h"
+#include "commit.h"
+#include "notes.h"
+#include "refs.h"
+
+static int initialized;
+
+void get_commit_notes(const struct commit *commit,
+		char **buf_p, unsigned long *offset_p, unsigned long *space_p)
+{
+	char name[80];
+	const char *hex;
+	unsigned char sha1[20];
+	char *msg;
+	unsigned long msgoffset, msglen;
+	enum object_type type;
+
+	if (!initialized) {
+		const char *env = getenv(GIT_NOTES_REF);
+		if (env) {
+			if (notes_ref_name)
+				free(notes_ref_name);
+			notes_ref_name = xstrdup(getenv(GIT_NOTES_REF));
+		} else if (!notes_ref_name)
+			notes_ref_name = xstrdup("refs/notes/commits");
+		if (notes_ref_name && read_ref(notes_ref_name, sha1)) {
+			free(notes_ref_name);
+			notes_ref_name = NULL;
+		}
+		initialized = 1;
+	}
+	if (!notes_ref_name)
+		return;
+
+	hex = sha1_to_hex(commit->object.sha1);
+	snprintf(name, sizeof(name), "%s:%.*s/%.*s",
+			notes_ref_name, 2, hex, 38, hex + 2);
+	if (get_sha1(name, sha1))
+		return;
+
+	if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen)
+		return;
+	/* we will end the annotation by a newline anyway. */
+	if (msg[msglen - 1] == '\n')
+		msglen--;
+
+	ALLOC_GROW(*buf_p, *offset_p + 14 + msglen, *space_p);
+	*offset_p += sprintf(*buf_p + *offset_p, "\nNotes:\n");
+
+	for (msgoffset = 0; msgoffset < msglen;) {
+		int linelen = get_line_length(msg + msgoffset, msglen);
+
+		ALLOC_GROW(*buf_p, *offset_p + linelen + 6, *space_p);
+		*offset_p += sprintf(*buf_p + *offset_p,
+				"    %.*s", linelen, msg + msgoffset);
+		msgoffset += linelen;
+	}
+	ALLOC_GROW(*buf_p, *offset_p + 1, *space_p);
+	(*buf_p)[*offset_p] = '\n';
+	(*offset_p)++;
+	free(msg);
+}
+
+

@@ -0,0 +1,9 @@
+#ifndef NOTES_H
+#define NOTES_H
+
+void get_commit_notes(const struct commit *commit,
+	char **buf_p, unsigned long *offset_p, unsigned long *space_p);
+
+#define GIT_NOTES_REF "GIT_NOTES_REF"
+
+#endif

@@ -83,6 +83,7 @@ git-mktag
 git-mktree
 git-name-rev
 git-mv
+git-notes
 git-pack-redundant
 git-pack-objects
 git-pack-refs

@@ -213,7 +213,7 @@ SCRIPT_SH = \
 	git-merge-resolve.sh git-merge-ours.sh \
 	git-lost-found.sh git-quiltimport.sh git-submodule.sh \
 	git-filter-branch.sh \
-	git-stash.sh
+	git-stash.sh git-notes.sh
 
 SCRIPT_PERL = \
 	git-add--interactive.perl \

@@ -0,0 +1,61 @@
+#!/bin/sh
+
+USAGE="(edit | show) [commit]"
+. git-sh-setup
+
+test -n "$3" && usage
+
+test -z "$GIT_NOTES_REF" && GIT_NOTES_REF="$(git config core.notesref)"
+test -z "$GIT_NOTES_REF" &&
+	die "No notes ref set."
+
+COMMIT=$(git rev-parse --verify --default HEAD "$2")
+NAME=$(echo $COMMIT | sed "s/^../&\//")
+
+case "$1" in
+edit)
+	MESSAGE="$GIT_DIR"/new-notes
+	GIT_NOTES_REF= git log -1 $COMMIT | sed "s/^/#/" > "$MESSAGE"
+
+	GIT_INDEX_FILE="$MESSAGE".idx
+	export GIT_INDEX_FILE
+
+	CURRENT_HEAD=$(git show-ref $GIT_NOTES_REF | cut -f 1 -d ' ')
+	if [ -z "$CURRENT_HEAD" ]; then
+		PARENT=
+	else
+		PARENT="-p $OLDTIP"
+		git read-tree $GIT_NOTES_REF || die "Could not read index"
+		git cat-file blob :$NAME >> "$MESSAGE" 2> /dev/null
+	fi
+
+	${VISUAL:-${EDITOR:-vi}} "$MESSAGE"
+
+	grep -v ^# < "$MESSAGE" | git stripspace > "$MESSAGE".processed
+	mv "$MESSAGE".processed "$MESSAGE"
+	if [ -z "$(cat "$MESSAGE")" ]; then
+		test -z "$CURRENT_HEAD" &&
+			die "Will not initialise with empty tree"
+		git update-index --force-remove $NAME ||
+			die "Could not update index"
+	else
+		BLOB=$(git hash-object -w "$MESSAGE") ||
+			die "Could not write into object database"
+		git update-index --add --cacheinfo 0644 $BLOB $NAME ||
+			die "Could not write index"
+	fi
+
+	TREE=$(git write-tree) || die "Could not write tree"
+	NEW_HEAD=$(: | git commit-tree $TREE $PARENT) ||
+		die "Could not annotate"
+	case "$CURRENT_HEAD" in
+	'') git update-ref $GIT_NOTES_REF $NEW_HEAD ;;
+	*) git update-ref $GIT_NOTES_REF $NEW_HEAD $CURRENT_HEAD;;
+	esac
+;;
+show)
+	git show "$GIT_NOTES_REF":$NAME
+;;
+*)
+	usage
+esac

@@ -0,0 +1,63 @@
+#!/bin/sh
+#
+# Copyright (c) 2007 Johannes E. Schindelin
+#
+
+test_description='Test commit notes'
+
+. ./test-lib.sh
+
+test_expect_success setup '
+	: > a1 &&
+	git add a1 &&
+	test_tick &&
+	git commit -m 1st &&
+	: > a2 &&
+	git add a2 &&
+	test_tick &&
+	git commit -m 2nd
+'
+
+cat > fake_editor.sh << EOF
+echo "\$MSG" > "\$1"
+echo "\$MSG" >& 2
+EOF
+chmod a+x fake_editor.sh
+VISUAL="$(pwd)"/fake_editor.sh
+export VISUAL
+
+
+test_expect_success 'need notes ref' '
+	! MSG=1 git notes edit &&
+	! MSG=2 git notes show
+'
+
+test_expect_success 'create notes' '
+	git config core.notesRef refs/notes/commits &&
+	MSG=b1 git notes edit &&
+cat .git/new-notes &&
+test b1 = "$(cat .git/new-notes)" &&
+	test 1 = $(git ls-tree refs/notes/commits | wc -l) &&
+	test b1 = $(git notes show) &&
+	git show HEAD^ &&
+	! git notes show HEAD^
+'
+
+cat > expect << EOF
+commit 268048bfb8a1fb38e703baceb8ab235421bf80c5
+Author: A U Thor <author@example.com>
+Date:   Thu Apr 7 15:14:13 2005 -0700
+
+    2nd
+
+Notes:
+    b1
+EOF
+
+test_expect_success 'show notes' '
+	! (git cat-file commit HEAD | grep b1) &&
+	git log -1 > output &&
+	git diff expect output
+'
+
+test_done

@@ -140,6 +140,7 @@ git-mergetool                           ancillarymanipulators
 git-mktag                               plumbingmanipulators
 git-mktree                              plumbingmanipulators
 git-mv                                  mainporcelain
+git-notes                               mainporcelain
 git-name-rev                            plumbinginterrogators
 git-pack-objects                        plumbingmanipulators
 git-pack-redundant                      plumbinginterrogators

@@ -0,0 +1,45 @@
+git-notes(1)
+============
+
+NAME
+----
+git-notes - Add commit notes
+
+SYNOPSIS
+--------
+[verse]
+'git-notes' (edit | show) [commit
+
+DESCRIPTION
+-----------
+This command allows you to add notes to commit messages, after the
+fact.  To discern these notes from the message stored in the commit
+object, the notes are indented like the message, after an unindented
+line saying "Notes:".
+
+To enable commit notes, you have to set the config variable
+core.notesRef to something like "refs/notes/commits".  This setting
+can be overridden by the environment variable "GIT_NOTES_REF".
+
+
+SUBCOMMANDS
+-----------
+
+edit::
+	Edit the notes for a given commit (defaults to HEAD).
+
+show::
+	Show the notes for a given commit (defaults to HEAD).
+
+
+Author
+------
+Written by Johannes Schindelin <johannes.schindelin@gmx.de>
+
+Documentation
+-------------
+Documentation by Johannes Schindelin
+
+GIT
+---
+Part of the gitlink:git[7] suite

@@ -1,10 +1,370 @@
 #include "cache.h"
 #include "commit.h"
+#include "tree-walk.h"
 #include "notes.h"
 #include "refs.h"
 
 static int initialized;
 
+/*
+ * There are two choices of data structure for the notes index.
+ *
+ * A) Fan out enhanced sorted list.
+ *
+ * This is a regular sorted list with a 256 entry fan out.  In other words,
+ * every time an entry is looked up, a binary search is performed over the
+ * sublist defined by the first byte of the SHA-1.
+ *
+ * The disadvantage is an average runtime logarithmic in the number of
+ * commit notes.  The advantages are a compact representation on disk,
+ * and a _guaranteed_ logarithmic runtime.
+ *
+ * You could even squeeze out one more byte per entry, since the
+ * first byte is known from the fan out list.  This would complicate our
+ * algorithm, though.
+ *
+ * B) Hash
+ *
+ * This is not your classical hash.  It is _mostly_ like a hash, with
+ * a few notable exceptions:
+ *
+ * - it is possibly larger than size suggests: since it is file based,
+ *   it is easier to write at the end than to wrap around.
+ *
+ * - as a consequence we can make the entries _strictly_ sorted. This
+ *   is not only nice to look at, but makes incremental updates much,
+ *   much easier.
+ *
+ * The disadvantages of a hash is its loose packing.  In order to operate
+ * reasonably well, it needs a size roughly double the number of entries.
+ * It also has a worst runtime linear in the number of entries.
+ *
+ * The advantage is an expected constant lookup time.
+ *
+ * The performance of a hash map depends highly on a good hashing
+ * algorithm, to avoid collisions.  Lucky us!  SHA-1 is a pretty good
+ * hashing algorithm.
+ *
+ * There is another advantage to hash maps: with not much effort, the
+ * incremental update can be performed in place, relying on O_TRUNC to
+ * detect interruptions.  This operation has an expected constant runtime.
+ */
+
+struct notes_entry {
+	unsigned char commit_sha1[20];
+	unsigned char notes_sha1[20];
+};
+
+struct notes_index {
+	char signature[4]; /* FANO for fan our, HASH for hash */
+
+	unsigned char tree_sha1[20];
+	unsigned char subtree_sha1[256][20]; /* for incremental caching */
+	off_t offsets[256]; /* for fan out */
+	off_t count, size; /* for hash */
+} notes_index;
+
+static int notes_index_fd;
+static int (*get_notes)(const unsigned char *commit_sha1,
+		unsigned char *notes_sha1);
+
+#define GIT_NOTES_MODE "GIT_NOTES_MODE"
+static int use_hash;
+
+static int index_uptodate_check(struct tree *tree) {
+	const char *signature = use_hash ? "HASH" : "FANO";
+	int fd = open(git_path("notes-index"), O_RDONLY);
+
+	if (fd < 0)
+		return fd;
+
+	notes_index_fd = fd;
+
+	return read_in_full(fd, &notes_index, sizeof(notes_index)) < 0||
+			memcmp(notes_index.signature, signature, 4) ||
+			memcmp(notes_index.tree_sha1,
+				&tree->object.sha1, 20);
+}
+
+struct lock_file update_lock;
+
+/* this reads the remaining 38 hexchars */
+static int get_remaining_hexchars(unsigned char *sha1, const char *path)
+{
+	int i, j1, j2;
+	for (i = 0; i < 38; i += 2)
+		if ((j1 = hexval(path[i])) < 0 ||
+				(j2 = hexval(path[i + 1])) < 0)
+			return -1;
+		else
+			sha1[1 + i / 2] = (j1 << 4) | j2;
+	return path[38] != '\0';
+}
+
+static int get_notes_hash_count(struct tree *tree) {
+	struct tree_desc desc, desc2;
+	struct name_entry entry;
+	void *buf;
+	unsigned long count = 0;
+
+	buf = fill_tree_descriptor(&desc, notes_index.tree_sha1);
+	if (!buf)
+		return 0;
+	while (tree_entry(&desc, &entry)) {
+		void *buf2 = fill_tree_descriptor(&desc2, entry.sha1);
+		if (!buf2)
+			continue;
+		while (tree_entry(&desc2, &entry))
+			count++;
+		free(buf2);
+	}
+	free(buf);
+
+	return count;
+}
+
+static unsigned long get_hash_index(const unsigned char *sha1)
+{
+	return (ntohl(*(unsigned long *)sha1) % notes_index.size);
+}
+
+static int write_hash_gap(int fd, unsigned char *sha1)
+{
+	off_t min_offset = sizeof(notes_index) +
+		get_hash_index(sha1) * sizeof(struct notes_entry);
+	while (min_offset > lseek(fd, 0, SEEK_CUR))
+		if (write_in_full(fd, null_sha1, 20) < 0 ||
+				write_in_full(fd, null_sha1, 20) < 0)
+			return error("Could not write gaps in notes-index");
+	return 0;
+}
+
+static int update_index(struct tree *tree) {
+	/*
+	 * Fan out sorted list:
+	 *
+	 * Write out the header, and seek back to it, in order to update it.
+	 * Actually only seek at the end, and make sure that you write
+	 * something big-endian.
+	 *
+	 * Plan for incremental: if subtree_sha1 is equal, copy out.
+	 * Otherwise construct, and remember in the copy of the header.
+	 *
+	 * Hash:
+	 *
+	 * Always use a power of two as size.  Not the next higher one, but
+	 * the next next higher one.
+	 *
+	 * Read the tree recursively, and leave as many zeros as needed
+	 * until the next entry comes.  Or if the entry has a hash larger
+	 * than the last free entry, write it at once.
+	 */
+
+	/* Plan for incremental: (not in-place)
+	 * Look at tree differences.  Write null_sha1 until next, or next
+	 * subtree.  Continue writing until original entry is null_sha1 or
+	 * greater than current subtree entry.
+	 */
+
+	int new_fd = hold_lock_file_for_update(&update_lock,
+			git_path("notes-index"), 0);
+	struct tree_desc desc;
+	struct name_entry entry;
+	void *buf;
+	int i;
+
+	if (new_fd < 0)
+		return error("Could not construct notes-index");
+
+	memset(&notes_index, 0, sizeof(notes_index));
+	hashcpy(notes_index.tree_sha1, tree->object.sha1);
+	notes_index.offsets[0] = sizeof(notes_index);
+	if (use_hash) {
+		notes_index.count = get_notes_hash_count(tree);
+		for (notes_index.size = 1; notes_index.size / 2
+				>= notes_index.count; notes_index.size <<= 1)
+			; /* do nothing */
+		memcpy(notes_index.signature, "HASH", 4);
+	} else
+		memcpy(notes_index.signature, "FANO", 4);
+
+	if (write_in_full(new_fd, &notes_index, sizeof(notes_index)) < 0)
+		return error("Could not write notes-index");
+
+	buf = fill_tree_descriptor(&desc, notes_index.tree_sha1);
+	if (!buf)
+		return error("Could not read %s for notes-index",
+				sha1_to_hex(notes_index.tree_sha1));
+
+	i = 0;
+	while (tree_entry(&desc, &entry)) {
+		int j1, j2;
+		unsigned char sha1[20];
+		struct tree_desc desc2;
+		struct name_entry entry2;
+		void *buf2;
+
+		if (!S_ISDIR(entry.mode) ||
+				(j1 = hexval(entry.path[0])) < 0 ||
+				(j2 = hexval(entry.path[1])) < 0)
+			continue;
+		sha1[0] = j1 * 16 + j2;
+		while (++i < sha1[0])
+			notes_index.offsets[i] = notes_index.offsets[i - 1];
+
+		hashcpy(notes_index.subtree_sha1[i], entry.sha1);
+		buf2 = fill_tree_descriptor(&desc2, entry.sha1);
+		if (!buf2)
+			continue;
+		while(tree_entry(&desc2, &entry2)) {
+			if (get_remaining_hexchars(sha1, entry2.path))
+				continue;
+			if (use_hash && write_hash_gap(new_fd, sha1))
+				return -1;
+			if (write_in_full(new_fd, sha1, 20) < 0 ||
+					write_in_full(new_fd,
+						entry2.sha1, 20) < 0)
+				return error("Could not write notes-index");
+		}
+		free(buf2);
+		notes_index.offsets[i] = lseek(new_fd, 0, SEEK_CUR);
+	}
+	free(buf);
+
+	while (++i < 256)
+		notes_index.offsets[i] = notes_index.offsets[i - 1];
+
+	/* update fan_out */
+	lseek(new_fd, 0, SEEK_SET);
+	write(new_fd, &notes_index, sizeof(notes_index));
+	lseek(new_fd, notes_index.offsets[255], SEEK_SET);
+
+	return close(new_fd) || commit_lock_file(&update_lock) ||
+		(notes_index_fd = open(git_path("notes-index"), O_RDONLY));
+}
+
+static void *notes_mmap;
+
+static void unmap_notes_mmap(void)
+{
+	munmap(notes_mmap, notes_index.offsets[255]);
+}
+
+static int get_notes_fan_out(const unsigned char *commit_sha1,
+		unsigned char *notes_sha1)
+{
+	/*
+	 * Header is assumed to be read.
+	 *
+	 * mmap() the area, and bisect.
+	 */
+	off_t off;
+	size_t size;
+	int i, i2, ret = -1;
+	struct notes_entry *list;
+
+	i = commit_sha1[0];
+	off = i ? notes_index.offsets[i - 1] : sizeof(notes_index);
+	size = notes_index.offsets[i] - off;
+	if (!size)
+		return -1;
+
+	if (!notes_mmap) {
+		notes_mmap = xmmap(NULL, notes_index.offsets[255],
+				PROT_READ, MAP_PRIVATE, notes_index_fd, 0);
+		atexit(unmap_notes_mmap);
+	}
+
+	list = (void *)((char *)notes_mmap + off);
+
+	i = 0;
+	i2 = size / sizeof(*list);
+	while (i + 1 < i2) {
+		int middle = (i + i2) / 2;
+		int cmp = hashcmp(commit_sha1, list[middle].commit_sha1);
+		if (cmp < 0)
+			i2 = middle;
+		else if (cmp > 0)
+			i = middle;
+		else {
+			hashcpy(notes_sha1, list[middle].notes_sha1);
+			i = middle;
+			ret = 0;
+			break;
+		}
+	}
+	if (i == 0 && !hashcmp(commit_sha1, list[i].commit_sha1)) {
+		hashcpy(notes_sha1, list[i].notes_sha1);
+		ret = 0;
+	}
+
+	return ret;
+}
+
+static int get_notes_hash(const unsigned char *commit_sha1,
+		unsigned char *notes_sha1)
+{
+	/*
+	 * Header is assumed to be read. fd is still open.
+	 *
+	 * Seek to hash, read until lower or equal (0000... is lower...)
+	 */
+	int i = get_hash_index(commit_sha1);
+	struct notes_entry entry;
+
+	lseek(notes_index_fd,
+			sizeof(notes_index) + i * sizeof(entry), SEEK_SET);
+	while (!read_in_full(notes_index_fd, &entry, sizeof(entry)) &&
+			!is_null_sha1(entry.commit_sha1)) {
+		int cmp = hashcmp(commit_sha1, entry.commit_sha1);
+		if (!cmp) {
+			hashcpy(notes_sha1, entry.notes_sha1);
+			return 0;
+		} else if (cmp < 0)
+			break;
+	}
+	return -1;
+}
+
+static inline void init_notes_index(void)
+{
+	const char *env;
+	struct commit *notes_ref;
+	unsigned char sha1[20];
+
+	if (initialized)
+		return;
+
+	initialized = 1;
+	env = getenv(GIT_NOTES_REF);
+	if (env) {
+		if (notes_ref_name)
+			free(notes_ref_name);
+		notes_ref_name = xstrdup(env);
+	} else if (!notes_ref_name)
+		notes_ref_name = xstrdup("refs/notes/commits");
+
+	if (!notes_ref_name)
+		return;
+	if (read_ref(notes_ref_name, sha1)) {
+		free(notes_ref_name);
+		notes_ref_name = NULL;
+		return;
+	}
+	env = getenv("GIT_NOTES_MODE");
+	if (env && !strcmp("HASH", env)) {
+		use_hash = 1;
+		get_notes = get_notes_hash;
+	} else if (env && !strcmp("FANO", env))
+		get_notes = get_notes_fan_out;
+	if (get_notes && !get_sha1(notes_ref_name, sha1) &&
+			(notes_ref = (struct commit *)parse_object(sha1)) &&
+			notes_ref->object.type == OBJ_COMMIT)
+		if (index_uptodate_check(notes_ref->tree))
+			if (update_index(notes_ref->tree))
+				get_notes = NULL; /* disable notes-index */
+}
+
 void get_commit_notes(const struct commit *commit,
 		char **buf_p, unsigned long *offset_p, unsigned long *space_p)
 {

@@ -15,28 +375,20 @@ void get_commit_notes(const struct commit *commit,
 	unsigned long msgoffset, msglen;
 	enum object_type type;
 
-	if (!initialized) {
-		const char *env = getenv(GIT_NOTES_REF);
-		if (env) {
-			if (notes_ref_name)
-				free(notes_ref_name);
-			notes_ref_name = xstrdup(getenv(GIT_NOTES_REF));
-		} else if (!notes_ref_name)
-			notes_ref_name = xstrdup("refs/notes/commits");
-		if (notes_ref_name && read_ref(notes_ref_name, sha1)) {
-			free(notes_ref_name);
-			notes_ref_name = NULL;
-		}
-		initialized = 1;
-	}
-	if (!notes_ref_name)
-		return;
+	init_notes_index();
 
-	hex = sha1_to_hex(commit->object.sha1);
-	snprintf(name, sizeof(name), "%s:%.*s/%.*s",
-			notes_ref_name, 2, hex, 38, hex + 2);
-	if (get_sha1(name, sha1))
+	if (!notes_ref_name)
 		return;
+	if (get_notes) {
+		if (get_notes(commit->object.sha1, sha1))
+			return;
+	} else {
+		hex = sha1_to_hex(commit->object.sha1);
+		snprintf(name, sizeof(name), "%s:%.*s/%.*s",
+				notes_ref_name, 2, hex, 38, hex + 2);
+		if (get_sha1(name, sha1))
+			return;
+	}
 
 	if (!(msg = read_sha1_file(sha1, &type, &msglen)) || !msglen)
 		return;

@@ -0,0 +1,118 @@
+#!/bin/sh
+#
+# Copyright (c) 2007 Johannes E. Schindelin
+#
+
+test_description='Test commit notes index (expensive!)'
+
+. ./test-lib.sh
+
+test -z "$GIT_NOTES_TIMING_TESTS" && {
+	say Skipping timing tests
+	test_done
+	exit
+}
+
+create_repo () {
+	number_of_commits=$1
+	nr=0
+	parent=
+	test -d .git || {
+	git init &&
+	tree=$(git write-tree) &&
+	while [ $nr -lt $number_of_commits ]; do
+		test_tick &&
+		commit=$(echo $nr | git commit-tree $tree $parent) ||
+			return
+		parent="-p $commit"
+		nr=$(($nr+1))
+	done &&
+	git update-ref refs/heads/master $commit &&
+	{
+		export GIT_INDEX_FILE=.git/temp;
+		git rev-list HEAD | cat -n | sed "s/^[ 	][ 	]*/ /g" |
+		while read nr sha1; do
+			blob=$(echo note $nr | git hash-object -w --stdin) &&
+			echo $sha1 | sed "s/^../0644 $blob 0	&\//"
+		done | git update-index --index-info &&
+		tree=$(git write-tree) &&
+		test_tick &&
+		commit=$(echo notes | git commit-tree $tree) &&
+		git update-ref refs/notes/commits $commit
+	} &&
+	git config core.notesRef refs/notes/commits
+	}
+}
+
+test_notes () {
+	count=$1 &&
+	git config core.notesRef refs/notes/commits &&
+	git log | grep "^    " > output &&
+	i=1 &&
+	while [ $i -le $count ]; do
+		echo "    $(($count-$i))" &&
+		echo "    note $i" &&
+		i=$(($i+1));
+	done > expect &&
+	git diff expect output
+}
+
+cat > time_notes << EOF
+	mode=\$1
+	i=1
+	while [ \$i -lt \$2 ]; do
+		case \$1 in
+		no-notes)
+			export GIT_NOTES_REF=non-existing
+		;;
+		no-cash)
+			unset GIT_NOTES_REF
+			export GIT_NOTES_MODE=NONE
+		;;
+		hash-cache-create)
+			unset GIT_NOTES_REF
+			export GIT_NOTES_MODE=HASH
+			rm .git/notes-index
+		;;
+		hash-cache)
+			unset GIT_NOTES_REF
+			export GIT_NOTES_MODE=HASH
+		;;
+		sorted-list-cache-create)
+			unset GIT_NOTES_REF
+			export GIT_NOTES_MODE=FANO
+			rm .git/notes-index
+		;;
+		sorted-list-cache)
+			unset GIT_NOTES_REF
+			export GIT_NOTES_MODE=FANO
+		;;
+		esac
+		git log >/dev/null
+		i=\$((\$i+1))
+	done
+EOF
+
+time_notes () {
+	for mode in no-notes no-cash \
+			hash-cache-create hash-cache \
+			sorted-list-cache-create sorted-list-cache; do
+		echo $mode
+		/usr/bin/time sh ../trash/time_notes $mode $1
+	done
+}
+
+for count in 10 100 1000; do
+
+	test -d ../trash-$count || mkdir ../trash-$count
+	(cd ../trash-$count;
+
+	test_expect_success "setup $count" "create_repo $count"
+
+	test_expect_success 'notes work' "test_notes $count"
+
+	test_expect_success 'notes timing' "time_notes 100"
+	)
+done
+
+test_done