diff --git a/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/TestRepository.java b/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/TestRepository.java
index 7a95ccd..e74af8c 100644
--- a/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/TestRepository.java
+++ b/org.eclipse.jgit.junit/src/org/eclipse/jgit/junit/TestRepository.java
@@ -184,6 +184,17 @@ public void tick(final int secDelta) {
 	}
 
 	/**
+	 * Set the author and committer using {@link #getClock()}.
+	 *
+	 * @param c
+	 *            the commit builder to store.
+	 */
+	public void setAuthorAndCommitter(org.eclipse.jgit.lib.CommitBuilder c) {
+		c.setAuthor(new PersonIdent(author, new Date(now)));
+		c.setCommitter(new PersonIdent(committer, new Date(now)));
+	}
+
+	/**
 	 * Create a new blob object in the repository.
 	 *
 	 * @param content
@@ -815,8 +826,7 @@ public RevCommit create() throws Exception {
 
 				c = new org.eclipse.jgit.lib.CommitBuilder();
 				c.setParentIds(parents);
-				c.setAuthor(new PersonIdent(author, new Date(now)));
-				c.setCommitter(new PersonIdent(committer, new Date(now)));
+				setAuthorAndCommitter(c);
 				c.setMessage(message);
 
 				ObjectId commitId;
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/SimilarityIndexTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/SimilarityIndexTest.java
index 7e42e53..1da5828 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/SimilarityIndexTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/diff/SimilarityIndexTest.java
@@ -48,10 +48,11 @@
 
 import junit.framework.TestCase;
 
+import org.eclipse.jgit.diff.SimilarityIndex.TableFullException;
 import org.eclipse.jgit.lib.Constants;
 
 public class SimilarityIndexTest extends TestCase {
-	public void testIndexingSmallObject() {
+	public void testIndexingSmallObject() throws TableFullException {
 		SimilarityIndex si = hash("" //
 				+ "A\n" //
 				+ "B\n" //
@@ -70,7 +71,8 @@ public void testIndexingSmallObject() {
 		assertEquals(2, si.count(si.findIndex(key_D)));
 	}
 
-	public void testIndexingLargeObject() throws IOException {
+	public void testIndexingLargeObject() throws IOException,
+			TableFullException {
 		byte[] in = ("" //
 				+ "A\n" //
 				+ "B\n" //
@@ -81,7 +83,7 @@ public void testIndexingLargeObject() throws IOException {
 		assertEquals(2, si.size());
 	}
 
-	public void testCommonScore_SameFiles() {
+	public void testCommonScore_SameFiles() throws TableFullException {
 		String text = "" //
 				+ "A\n" //
 				+ "B\n" //
@@ -96,21 +98,22 @@ public void testCommonScore_SameFiles() {
 		assertEquals(100, dst.score(src, 100));
 	}
 
-	public void testCommonScore_EmptyFiles() {
+	public void testCommonScore_EmptyFiles() throws TableFullException {
 		SimilarityIndex src = hash("");
 		SimilarityIndex dst = hash("");
 		assertEquals(0, src.common(dst));
 		assertEquals(0, dst.common(src));
 	}
 
-	public void testCommonScore_TotallyDifferentFiles() {
+	public void testCommonScore_TotallyDifferentFiles()
+			throws TableFullException {
 		SimilarityIndex src = hash("A\n");
 		SimilarityIndex dst = hash("D\n");
 		assertEquals(0, src.common(dst));
 		assertEquals(0, dst.common(src));
 	}
 
-	public void testCommonScore_SimiliarBy75() {
+	public void testCommonScore_SimiliarBy75() throws TableFullException {
 		SimilarityIndex src = hash("A\nB\nC\nD\n");
 		SimilarityIndex dst = hash("A\nB\nC\nQ\n");
 		assertEquals(6, src.common(dst));
@@ -120,10 +123,11 @@ public void testCommonScore_SimiliarBy75() {
 		assertEquals(75, dst.score(src, 100));
 	}
 
-	private static SimilarityIndex hash(String text) {
+	private static SimilarityIndex hash(String text) throws TableFullException {
 		SimilarityIndex src = new SimilarityIndex() {
 			@Override
-			void hash(byte[] raw, int ptr, final int end) {
+			void hash(byte[] raw, int ptr, final int end)
+					throws TableFullException {
 				while (ptr < end) {
 					int hash = raw[ptr] & 0xff;
 					int start = ptr;
@@ -143,7 +147,7 @@ void hash(byte[] raw, int ptr, final int end) {
 		return src;
 	}
 
-	private static int keyFor(String line) {
+	private static int keyFor(String line) throws TableFullException {
 		SimilarityIndex si = hash(line);
 		assertEquals("single line scored", 1, si.size());
 		return si.key(0);
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/LeafBucketTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/LeafBucketTest.java
new file mode 100644
index 0000000..68b0e2b
--- /dev/null
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/LeafBucketTest.java
@@ -0,0 +1,226 @@
+/*
+ * Copyright (C) 2010, Google Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.notes;
+
+import java.io.IOException;
+
+import junit.framework.TestCase;
+
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.MutableObjectId;
+
+public class LeafBucketTest extends TestCase {
+	public void testEmpty() {
+		LeafBucket b = new LeafBucket(0);
+		assertNull(b.get(id(0x00), null));
+		assertNull(b.get(id(0x01), null));
+		assertNull(b.get(id(0xfe), null));
+	}
+
+	public void testParseFive() {
+		LeafBucket b = new LeafBucket(0);
+
+		b.parseOneEntry(id(0x11), id(0x81));
+		b.parseOneEntry(id(0x22), id(0x82));
+		b.parseOneEntry(id(0x33), id(0x83));
+		b.parseOneEntry(id(0x44), id(0x84));
+		b.parseOneEntry(id(0x55), id(0x85));
+
+		assertNull(b.get(id(0x01), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertEquals(id(0x83), b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertEquals(id(0x85), b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testSetFive_InOrder() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertSame(b, b.set(id(0x22), id(0x82), null));
+		assertSame(b, b.set(id(0x33), id(0x83), null));
+		assertSame(b, b.set(id(0x44), id(0x84), null));
+		assertSame(b, b.set(id(0x55), id(0x85), null));
+
+		assertNull(b.get(id(0x01), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertEquals(id(0x83), b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertEquals(id(0x85), b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testSetFive_ReverseOrder() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x55), id(0x85), null));
+		assertSame(b, b.set(id(0x44), id(0x84), null));
+		assertSame(b, b.set(id(0x33), id(0x83), null));
+		assertSame(b, b.set(id(0x22), id(0x82), null));
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+
+		assertNull(b.get(id(0x01), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertEquals(id(0x83), b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertEquals(id(0x85), b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testSetFive_MixedOrder() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertSame(b, b.set(id(0x33), id(0x83), null));
+		assertSame(b, b.set(id(0x55), id(0x85), null));
+
+		assertSame(b, b.set(id(0x22), id(0x82), null));
+		assertSame(b, b.set(id(0x44), id(0x84), null));
+
+		assertNull(b.get(id(0x01), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertEquals(id(0x83), b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertEquals(id(0x85), b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testSet_Replace() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+
+		assertSame(b, b.set(id(0x11), id(0x01), null));
+		assertEquals(id(0x01), b.get(id(0x11), null));
+	}
+
+	public void testRemoveMissingNote() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+		assertNull(b.get(id(0x11), null));
+		assertSame(b, b.set(id(0x11), null, null));
+		assertNull(b.get(id(0x11), null));
+	}
+
+	public void testRemoveFirst() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertSame(b, b.set(id(0x22), id(0x82), null));
+		assertSame(b, b.set(id(0x33), id(0x83), null));
+		assertSame(b, b.set(id(0x44), id(0x84), null));
+		assertSame(b, b.set(id(0x55), id(0x85), null));
+
+		assertSame(b, b.set(id(0x11), null, null));
+
+		assertNull(b.get(id(0x01), null));
+		assertNull(b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertEquals(id(0x83), b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertEquals(id(0x85), b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testRemoveMiddle() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertSame(b, b.set(id(0x22), id(0x82), null));
+		assertSame(b, b.set(id(0x33), id(0x83), null));
+		assertSame(b, b.set(id(0x44), id(0x84), null));
+		assertSame(b, b.set(id(0x55), id(0x85), null));
+
+		assertSame(b, b.set(id(0x33), null, null));
+
+		assertNull(b.get(id(0x01), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertNull(b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertEquals(id(0x85), b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testRemoveLast() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertSame(b, b.set(id(0x22), id(0x82), null));
+		assertSame(b, b.set(id(0x33), id(0x83), null));
+		assertSame(b, b.set(id(0x44), id(0x84), null));
+		assertSame(b, b.set(id(0x55), id(0x85), null));
+
+		assertSame(b, b.set(id(0x55), null, null));
+
+		assertNull(b.get(id(0x01), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+		assertEquals(id(0x82), b.get(id(0x22), null));
+		assertEquals(id(0x83), b.get(id(0x33), null));
+		assertEquals(id(0x84), b.get(id(0x44), null));
+		assertNull(b.get(id(0x55), null));
+		assertNull(b.get(id(0x66), null));
+	}
+
+	public void testRemoveMakesEmpty() throws IOException {
+		LeafBucket b = new LeafBucket(0);
+
+		assertSame(b, b.set(id(0x11), id(0x81), null));
+		assertEquals(id(0x81), b.get(id(0x11), null));
+
+		assertNull(b.set(id(0x11), null, null));
+		assertNull(b.get(id(0x11), null));
+	}
+
+	private static AnyObjectId id(int first) {
+		MutableObjectId id = new MutableObjectId();
+		id.setByte(1, first);
+		return id;
+	}
+}
diff --git a/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapTest.java b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapTest.java
index 786f1b9..d740ffa 100644
--- a/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapTest.java
+++ b/org.eclipse.jgit.test/tst/org/eclipse/jgit/notes/NoteMapTest.java
@@ -43,12 +43,20 @@
 
 package org.eclipse.jgit.notes;
 
+import java.io.IOException;
+
 import org.eclipse.jgit.junit.TestRepository;
+import org.eclipse.jgit.lib.CommitBuilder;
+import org.eclipse.jgit.lib.Constants;
+import org.eclipse.jgit.lib.MutableObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.lib.Repository;
 import org.eclipse.jgit.lib.RepositoryTestCase;
 import org.eclipse.jgit.revwalk.RevBlob;
 import org.eclipse.jgit.revwalk.RevCommit;
+import org.eclipse.jgit.revwalk.RevTree;
+import org.eclipse.jgit.treewalk.TreeWalk;
 import org.eclipse.jgit.util.RawParseUtils;
 
 public class NoteMapTest extends RepositoryTestCase {
@@ -56,17 +64,21 @@ public class NoteMapTest extends RepositoryTestCase {
 
 	private ObjectReader reader;
 
+	private ObjectInserter inserter;
+
 	@Override
 	protected void setUp() throws Exception {
 		super.setUp();
 
 		tr = new TestRepository<Repository>(db);
 		reader = db.newObjectReader();
+		inserter = db.newObjectInserter();
 	}
 
 	@Override
 	protected void tearDown() throws Exception {
 		reader.release();
+		inserter.release();
 		super.tearDown();
 	}
 
@@ -182,6 +194,240 @@ public void testGetCachedBytes() throws Exception {
 		assertEquals(exp, RawParseUtils.decode(act));
 	}
 
+	public void testWriteUnchangedFlat() throws Exception {
+		RevBlob a = tr.blob("a");
+		RevBlob b = tr.blob("b");
+		RevBlob data1 = tr.blob("data1");
+		RevBlob data2 = tr.blob("data2");
+
+		RevCommit r = tr.commit() //
+				.add(a.name(), data1) //
+				.add(b.name(), data2) //
+				.add(".gitignore", "") //
+				.add("zoo-animals.txt", "") //
+				.create();
+		tr.parseBody(r);
+
+		NoteMap map = NoteMap.read(reader, r);
+		assertTrue("has note for a", map.contains(a));
+		assertTrue("has note for b", map.contains(b));
+
+		RevCommit n = commitNoteMap(map);
+		assertNotSame("is new commit", r, n);
+		assertSame("same tree", r.getTree(), n.getTree());
+	}
+
+	public void testWriteUnchangedFanout2_38() throws Exception {
+		RevBlob a = tr.blob("a");
+		RevBlob b = tr.blob("b");
+		RevBlob data1 = tr.blob("data1");
+		RevBlob data2 = tr.blob("data2");
+
+		RevCommit r = tr.commit() //
+				.add(fanout(2, a.name()), data1) //
+				.add(fanout(2, b.name()), data2) //
+				.add(".gitignore", "") //
+				.add("zoo-animals.txt", "") //
+				.create();
+		tr.parseBody(r);
+
+		NoteMap map = NoteMap.read(reader, r);
+		assertTrue("has note for a", map.contains(a));
+		assertTrue("has note for b", map.contains(b));
+
+		// This is a non-lazy map, so we'll be looking at the leaf buckets.
+		RevCommit n = commitNoteMap(map);
+		assertNotSame("is new commit", r, n);
+		assertSame("same tree", r.getTree(), n.getTree());
+
+		// Use a lazy-map for the next round of the same test.
+		map = NoteMap.read(reader, r);
+		n = commitNoteMap(map);
+		assertNotSame("is new commit", r, n);
+		assertSame("same tree", r.getTree(), n.getTree());
+	}
+
+	public void testCreateFromEmpty() throws Exception {
+		RevBlob a = tr.blob("a");
+		RevBlob b = tr.blob("b");
+		RevBlob data1 = tr.blob("data1");
+		RevBlob data2 = tr.blob("data2");
+
+		NoteMap map = NoteMap.newEmptyMap();
+		assertFalse("no a", map.contains(a));
+		assertFalse("no b", map.contains(b));
+
+		map.set(a, data1);
+		map.set(b, data2);
+
+		assertEquals(data1, map.get(a));
+		assertEquals(data2, map.get(b));
+
+		map.remove(a);
+		map.remove(b);
+
+		assertFalse("no a", map.contains(a));
+		assertFalse("no b", map.contains(b));
+
+		map.set(a, "data1", inserter);
+		assertEquals(data1, map.get(a));
+
+		map.set(a, null, inserter);
+		assertFalse("no a", map.contains(a));
+	}
+
+	public void testEditFlat() throws Exception {
+		RevBlob a = tr.blob("a");
+		RevBlob b = tr.blob("b");
+		RevBlob data1 = tr.blob("data1");
+		RevBlob data2 = tr.blob("data2");
+
+		RevCommit r = tr.commit() //
+				.add(a.name(), data1) //
+				.add(b.name(), data2) //
+				.add(".gitignore", "") //
+				.add("zoo-animals.txt", b) //
+				.create();
+		tr.parseBody(r);
+
+		NoteMap map = NoteMap.read(reader, r);
+		map.set(a, data2);
+		map.set(b, null);
+		map.set(data1, b);
+		map.set(data2, null);
+
+		assertEquals(data2, map.get(a));
+		assertEquals(b, map.get(data1));
+		assertFalse("no b", map.contains(b));
+		assertFalse("no data2", map.contains(data2));
+
+		MutableObjectId id = new MutableObjectId();
+		for (int p = 42; p > 0; p--) {
+			id.setByte(1, p);
+			map.set(id, data1);
+		}
+
+		for (int p = 42; p > 0; p--) {
+			id.setByte(1, p);
+			assertTrue("contains " + id, map.contains(id));
+		}
+
+		RevCommit n = commitNoteMap(map);
+		map = NoteMap.read(reader, n);
+		assertEquals(data2, map.get(a));
+		assertEquals(b, map.get(data1));
+		assertFalse("no b", map.contains(b));
+		assertFalse("no data2", map.contains(data2));
+		assertEquals(b, TreeWalk
+				.forPath(reader, "zoo-animals.txt", n.getTree()).getObjectId(0));
+	}
+
+	public void testEditFanout2_38() throws Exception {
+		RevBlob a = tr.blob("a");
+		RevBlob b = tr.blob("b");
+		RevBlob data1 = tr.blob("data1");
+		RevBlob data2 = tr.blob("data2");
+
+		RevCommit r = tr.commit() //
+				.add(fanout(2, a.name()), data1) //
+				.add(fanout(2, b.name()), data2) //
+				.add(".gitignore", "") //
+				.add("zoo-animals.txt", b) //
+				.create();
+		tr.parseBody(r);
+
+		NoteMap map = NoteMap.read(reader, r);
+		map.set(a, data2);
+		map.set(b, null);
+		map.set(data1, b);
+		map.set(data2, null);
+
+		assertEquals(data2, map.get(a));
+		assertEquals(b, map.get(data1));
+		assertFalse("no b", map.contains(b));
+		assertFalse("no data2", map.contains(data2));
+		RevCommit n = commitNoteMap(map);
+
+		map.set(a, null);
+		map.set(data1, null);
+		assertFalse("no a", map.contains(a));
+		assertFalse("no data1", map.contains(data1));
+
+		map = NoteMap.read(reader, n);
+		assertEquals(data2, map.get(a));
+		assertEquals(b, map.get(data1));
+		assertFalse("no b", map.contains(b));
+		assertFalse("no data2", map.contains(data2));
+		assertEquals(b, TreeWalk
+				.forPath(reader, "zoo-animals.txt", n.getTree()).getObjectId(0));
+	}
+
+	public void testLeafSplitsWhenFull() throws Exception {
+		RevBlob data1 = tr.blob("data1");
+		MutableObjectId idBuf = new MutableObjectId();
+
+		RevCommit r = tr.commit() //
+				.add(data1.name(), data1) //
+				.create();
+		tr.parseBody(r);
+
+		NoteMap map = NoteMap.read(reader, r);
+		for (int i = 0; i < 254; i++) {
+			idBuf.setByte(Constants.OBJECT_ID_LENGTH - 1, i);
+			map.set(idBuf, data1);
+		}
+
+		RevCommit n = commitNoteMap(map);
+		TreeWalk tw = new TreeWalk(reader);
+		tw.reset(n.getTree());
+		while (tw.next())
+			assertFalse("no fan-out subtree", tw.isSubtree());
+
+		for (int i = 254; i < 256; i++) {
+			idBuf.setByte(Constants.OBJECT_ID_LENGTH - 1, i);
+			map.set(idBuf, data1);
+		}
+		idBuf.setByte(Constants.OBJECT_ID_LENGTH - 2, 1);
+		map.set(idBuf, data1);
+		n = commitNoteMap(map);
+
+		// The 00 bucket is fully split.
+		String path = fanout(38, idBuf.name());
+		tw = TreeWalk.forPath(reader, path, n.getTree());
+		assertNotNull("has " + path, tw);
+
+		// The other bucket is not.
+		path = fanout(2, data1.name());
+		tw = TreeWalk.forPath(reader, path, n.getTree());
+		assertNotNull("has " + path, tw);
+	}
+
+	public void testRemoveDeletesTreeFanout2_38() throws Exception {
+		RevBlob a = tr.blob("a");
+		RevBlob data1 = tr.blob("data1");
+		RevTree empty = tr.tree();
+
+		RevCommit r = tr.commit() //
+				.add(fanout(2, a.name()), data1) //
+				.create();
+		tr.parseBody(r);
+
+		NoteMap map = NoteMap.read(reader, r);
+		map.set(a, null);
+
+		RevCommit n = commitNoteMap(map);
+		assertEquals("empty tree", empty, n.getTree());
+	}
+
+	private RevCommit commitNoteMap(NoteMap map) throws IOException {
+		tr.tick(600);
+
+		CommitBuilder builder = new CommitBuilder();
+		builder.setTreeId(map.writeTree(inserter));
+		tr.setAuthorAndCommitter(builder);
+		return tr.getRevWalk().parseCommit(inserter.insert(builder));
+	}
+
 	private static String fanout(int prefix, String name) {
 		StringBuilder r = new StringBuilder();
 		int i = 0;
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
index 66218f6..dfaf588 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/RenameDetector.java
@@ -57,6 +57,7 @@
 
 import org.eclipse.jgit.JGitText;
 import org.eclipse.jgit.diff.DiffEntry.ChangeType;
+import org.eclipse.jgit.diff.SimilarityIndex.TableFullException;
 import org.eclipse.jgit.lib.AbbreviatedObjectId;
 import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.NullProgressMonitor;
@@ -356,9 +357,17 @@ public List<DiffEntry> compute(ContentSource.Pair reader, ProgressMonitor pm)
 
 			if (pm == null)
 				pm = NullProgressMonitor.INSTANCE;
+
+			if (0 < breakScore)
 				breakModifies(reader, pm);
+
+			if (!added.isEmpty() && !deleted.isEmpty())
 				findExactRenames(pm);
+
+			if (!added.isEmpty() && !deleted.isEmpty())
 				findContentRenames(reader, pm);
+
+			if (0 < breakScore && !added.isEmpty() && !deleted.isEmpty())
 				rejoinModifies(pm);
 
 			entries.addAll(added);
@@ -382,9 +391,6 @@ public void reset() {
 
 	private void breakModifies(ContentSource.Pair reader, ProgressMonitor pm)
 			throws IOException {
-		if (breakScore <= 0)
-			return;
-
 		ArrayList<DiffEntry> newEntries = new ArrayList<DiffEntry>(entries.size());
 
 		pm.beginTask(JGitText.get().renamesBreakingModifies, entries.size());
@@ -445,29 +451,36 @@ private void rejoinModifies(ProgressMonitor pm) {
 
 	private int calculateModifyScore(ContentSource.Pair reader, DiffEntry d)
 			throws IOException {
-		SimilarityIndex src = new SimilarityIndex();
-		src.hash(reader.open(OLD, d));
-		src.sort();
+		try {
+			SimilarityIndex src = new SimilarityIndex();
+			src.hash(reader.open(OLD, d));
+			src.sort();
 
-		SimilarityIndex dst = new SimilarityIndex();
-		dst.hash(reader.open(NEW, d));
-		dst.sort();
-		return src.score(dst, 100);
+			SimilarityIndex dst = new SimilarityIndex();
+			dst.hash(reader.open(NEW, d));
+			dst.sort();
+			return src.score(dst, 100);
+		} catch (TableFullException tableFull) {
+			// If either table overflowed while being constructed, don't allow
+			// the pair to be broken. Returning 1 higher than breakScore will
+			// ensure its not similar, but not quite dissimilar enough to break.
+			//
+			overRenameLimit = true;
+			return breakScore + 1;
+		}
 	}
 
 	private void findContentRenames(ContentSource.Pair reader,
 			ProgressMonitor pm)
 			throws IOException {
 		int cnt = Math.max(added.size(), deleted.size());
-		if (cnt == 0)
-			return;
-
 		if (getRenameLimit() == 0 || cnt <= getRenameLimit()) {
 			SimilarityRenameDetector d;
 
 			d = new SimilarityRenameDetector(reader, deleted, added);
 			d.setRenameScore(getRenameScore());
 			d.compute(pm);
+			overRenameLimit |= d.isTableOverflow();
 			deleted = d.getLeftOverSources();
 			added = d.getLeftOverDestinations();
 			entries.addAll(d.getMatches());
@@ -478,9 +491,6 @@ private void findContentRenames(ContentSource.Pair reader,
 
 	@SuppressWarnings("unchecked")
 	private void findExactRenames(ProgressMonitor pm) {
-		if (added.isEmpty() || deleted.isEmpty())
-			return;
-
 		pm.beginTask(JGitText.get().renamesFindingExact, //
 				added.size() + added.size() + deleted.size()
 						+ added.size() * deleted.size());
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java
index 6627268..17ccb97 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityIndex.java
@@ -65,8 +65,8 @@
  * file are discovered.
  */
 class SimilarityIndex {
-	/** The {@link #idHash} table stops growing at {@code 1 << MAX_HASH_BITS}. */
-	private static final int MAX_HASH_BITS = 17;
+	/** A special {@link TableFullException} used in place of OutOfMemoryError. */
+	private static final TableFullException TABLE_FULL_OUT_OF_MEMORY = new TableFullException();
 
 	/**
 	 * Shift to apply before storing a key.
@@ -76,20 +76,26 @@ class SimilarityIndex {
 	 */
 	private static final int KEY_SHIFT = 32;
 
+	/** Maximum value of the count field, also mask to extract the count. */
+	private static final long MAX_COUNT = (1L << KEY_SHIFT) - 1;
+
 	/** Total size of the file we hashed into the structure. */
 	private long fileSize;
 
 	/** Number of non-zero entries in {@link #idHash}. */
 	private int idSize;
 
+	/** {@link #idSize} that triggers {@link #idHash} to double in size. */
+	private int idGrowAt;
+
 	/**
 	 * Pairings of content keys and counters.
 	 * <p>
 	 * Slots in the table are actually two ints wedged into a single long. The
-	 * upper {@link #MAX_HASH_BITS} bits stores the content key, and the
-	 * remaining lower bits stores the number of bytes associated with that key.
-	 * Empty slots are denoted by 0, which cannot occur because the count cannot
-	 * be 0. Values can only be positive, which we enforce during key addition.
+	 * upper 32 bits stores the content key, and the remaining lower bits stores
+	 * the number of bytes associated with that key. Empty slots are denoted by
+	 * 0, which cannot occur because the count cannot be 0. Values can only be
+	 * positive, which we enforce during key addition.
 	 */
 	private long[] idHash;
 
@@ -99,6 +105,7 @@ class SimilarityIndex {
 	SimilarityIndex() {
 		idHashBits = 8;
 		idHash = new long[1 << idHashBits];
+		idGrowAt = growAt(idHashBits);
 	}
 
 	long getFileSize() {
@@ -109,7 +116,8 @@ void setFileSize(long size) {
 		fileSize = size;
 	}
 
-	void hash(ObjectLoader obj) throws MissingObjectException, IOException {
+	void hash(ObjectLoader obj) throws MissingObjectException, IOException,
+			TableFullException {
 		if (obj.isLarge()) {
 			ObjectStream in = obj.openStream();
 			try {
@@ -125,7 +133,7 @@ void hash(ObjectLoader obj) throws MissingObjectException, IOException {
 		}
 	}
 
-	void hash(byte[] raw, int ptr, final int end) {
+	void hash(byte[] raw, int ptr, final int end) throws TableFullException {
 		while (ptr < end) {
 			int hash = 5381;
 			int start = ptr;
@@ -141,7 +149,8 @@ void hash(byte[] raw, int ptr, final int end) {
 		}
 	}
 
-	void hash(InputStream in, long remaining) throws IOException {
+	void hash(InputStream in, long remaining) throws IOException,
+			TableFullException {
 		byte[] buf = new byte[4096];
 		int ptr = 0;
 		int cnt = 0;
@@ -190,11 +199,11 @@ int score(SimilarityIndex dst, int maxScore) {
 		return (int) ((common(dst) * maxScore) / max);
 	}
 
-	int common(SimilarityIndex dst) {
+	long common(SimilarityIndex dst) {
 		return common(this, dst);
 	}
 
-	private static int common(SimilarityIndex src, SimilarityIndex dst) {
+	private static long common(SimilarityIndex src, SimilarityIndex dst) {
 		int srcIdx = src.packedIndex(0);
 		int dstIdx = dst.packedIndex(0);
 		long[] srcHash = src.idHash;
@@ -202,12 +211,12 @@ private static int common(SimilarityIndex src, SimilarityIndex dst) {
 		return common(srcHash, srcIdx, dstHash, dstIdx);
 	}
 
-	private static int common(long[] srcHash, int srcIdx, //
+	private static long common(long[] srcHash, int srcIdx, //
 			long[] dstHash, int dstIdx) {
 		if (srcIdx == srcHash.length || dstIdx == dstHash.length)
 			return 0;
 
-		int common = 0;
+		long common = 0;
 		int srcKey = keyOf(srcHash[srcIdx]);
 		int dstKey = keyOf(dstHash[dstIdx]);
 
@@ -230,8 +239,8 @@ private static int common(long[] srcHash, int srcIdx, //
 					break;
 				srcKey = keyOf(srcHash[srcIdx]);
 
-			} else /* if (srcKey > dstKey) */{
-				// Regions of dst which do not appear in dst.
+			} else /* if (dstKey < srcKey) */{
+				// Regions of dst which do not appear in src.
 				if (++dstIdx == dstHash.length)
 					break;
 				dstKey = keyOf(dstHash[dstIdx]);
@@ -268,7 +277,7 @@ private int packedIndex(int idx) {
 		return (idHash.length - idSize) + idx;
 	}
 
-	void add(int key, int cnt) {
+	void add(int key, int cnt) throws TableFullException {
 		key = (key * 0x9e370001) >>> 1; // Mix bits and ensure not negative.
 
 		int j = slot(key);
@@ -276,18 +285,20 @@ void add(int key, int cnt) {
 			long v = idHash[j];
 			if (v == 0) {
 				// Empty slot in the table, store here.
-				if (shouldGrow()) {
+				if (idGrowAt <= idSize) {
 					grow();
 					j = slot(key);
 					continue;
 				}
-				idHash[j] = (((long) key) << KEY_SHIFT) | cnt;
+				idHash[j] = pair(key, cnt);
 				idSize++;
 				return;
 
 			} else if (keyOf(v) == key) {
-				// Same key, increment the counter.
-				idHash[j] = v + cnt;
+				// Same key, increment the counter. If it overflows, fail
+				// indexing to prevent the key from being impacted.
+				//
+				idHash[j] = pair(key, countOf(v) + cnt);
 				return;
 
 			} else if (++j >= idHash.length) {
@@ -296,6 +307,12 @@ void add(int key, int cnt) {
 		}
 	}
 
+	private static long pair(int key, long cnt) throws TableFullException {
+		if (MAX_COUNT < cnt)
+			throw new TableFullException();
+		return (((long) key) << KEY_SHIFT) | cnt;
+	}
+
 	private int slot(int key) {
 		// We use 31 - idHashBits because the upper bit was already forced
 		// to be 0 and we want the remaining high bits to be used as the
@@ -304,16 +321,26 @@ private int slot(int key) {
 		return key >>> (31 - idHashBits);
 	}
 
-	private boolean shouldGrow() {
-		return idHashBits < MAX_HASH_BITS && idHash.length <= idSize * 2;
+	private static int growAt(int idHashBits) {
+		return (1 << idHashBits) * (idHashBits - 3) / idHashBits;
 	}
 
-	private void grow() {
+	private void grow() throws TableFullException {
+		if (idHashBits == 30)
+			throw new TableFullException();
+
 		long[] oldHash = idHash;
 		int oldSize = idHash.length;
 
 		idHashBits++;
-		idHash = new long[1 << idHashBits];
+		idGrowAt = growAt(idHashBits);
+
+		try {
+			idHash = new long[1 << idHashBits];
+		} catch (OutOfMemoryError noMemory) {
+			throw TABLE_FULL_OUT_OF_MEMORY;
+		}
+
 		for (int i = 0; i < oldSize; i++) {
 			long v = oldHash[i];
 			if (v != 0) {
@@ -330,7 +357,11 @@ private static int keyOf(long v) {
 		return (int) (v >>> KEY_SHIFT);
 	}
 
-	private static int countOf(long v) {
-		return (int) v;
+	private static long countOf(long v) {
+		return v & MAX_COUNT;
+	}
+
+	static class TableFullException extends Exception {
+		private static final long serialVersionUID = 1L;
 	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java b/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java
index 3075c22..3a98475 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/diff/SimilarityRenameDetector.java
@@ -49,10 +49,12 @@
 import java.io.IOException;
 import java.util.ArrayList;
 import java.util.Arrays;
+import java.util.BitSet;
 import java.util.List;
 
 import org.eclipse.jgit.JGitText;
 import org.eclipse.jgit.diff.DiffEntry.ChangeType;
+import org.eclipse.jgit.diff.SimilarityIndex.TableFullException;
 import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.NullProgressMonitor;
 import org.eclipse.jgit.lib.ProgressMonitor;
@@ -110,6 +112,9 @@ class SimilarityRenameDetector {
 	/** Score a pair must exceed to be considered a rename. */
 	private int renameScore = 60;
 
+	/** Set if any {@link SimilarityIndex.TableFullException} occurs. */
+	private boolean tableOverflow;
+
 	private List<DiffEntry> out;
 
 	SimilarityRenameDetector(ContentSource.Pair reader, List<DiffEntry> srcs,
@@ -182,6 +187,10 @@ List<DiffEntry> getLeftOverDestinations() {
 		return dsts;
 	}
 
+	boolean isTableOverflow() {
+		return tableOverflow;
+	}
+
 	private static List<DiffEntry> compactSrcList(List<DiffEntry> in) {
 		ArrayList<DiffEntry> r = new ArrayList<DiffEntry>(in.size());
 		for (DiffEntry e : in) {
@@ -208,25 +217,22 @@ private int buildMatrix(ProgressMonitor pm) throws IOException {
 
 		long[] srcSizes = new long[srcs.size()];
 		long[] dstSizes = new long[dsts.size()];
-
-		// Init the size arrays to some value that indicates that we haven't
-		// calculated the size yet. Since sizes cannot be negative, -1 will work
-		Arrays.fill(srcSizes, -1);
-		Arrays.fill(dstSizes, -1);
+		BitSet dstTooLarge = null;
 
 		// Consider each pair of files, if the score is above the minimum
 		// threshold we need record that scoring in the matrix so we can
 		// later find the best matches.
 		//
 		int mNext = 0;
-		for (int srcIdx = 0; srcIdx < srcs.size(); srcIdx++) {
+		SRC: for (int srcIdx = 0; srcIdx < srcs.size(); srcIdx++) {
 			DiffEntry srcEnt = srcs.get(srcIdx);
 			if (!isFile(srcEnt.oldMode)) {
 				pm.update(dsts.size());
 				continue;
 			}
 
-			SimilarityIndex s = hash(OLD, srcEnt);
+			SimilarityIndex s = null;
+
 			for (int dstIdx = 0; dstIdx < dsts.size(); dstIdx++) {
 				DiffEntry dstEnt = dsts.get(dstIdx);
 
@@ -240,15 +246,20 @@ private int buildMatrix(ProgressMonitor pm) throws IOException {
 					continue;
 				}
 
+				if (dstTooLarge != null && dstTooLarge.get(dstIdx)) {
+					pm.update(1);
+					continue;
+				}
+
 				long srcSize = srcSizes[srcIdx];
-				if (srcSize < 0) {
-					srcSize = size(OLD, srcEnt);
+				if (srcSize == 0) {
+					srcSize = size(OLD, srcEnt) + 1;
 					srcSizes[srcIdx] = srcSize;
 				}
 
 				long dstSize = dstSizes[dstIdx];
-				if (dstSize < 0) {
-					dstSize = size(NEW, dstEnt);
+				if (dstSize == 0) {
+					dstSize = size(NEW, dstEnt) + 1;
 					dstSizes[dstIdx] = dstSize;
 				}
 
@@ -260,7 +271,27 @@ private int buildMatrix(ProgressMonitor pm) throws IOException {
 					continue;
 				}
 
-				SimilarityIndex d = hash(NEW, dstEnt);
+				if (s == null) {
+					try {
+						s = hash(OLD, srcEnt);
+					} catch (TableFullException tableFull) {
+						tableOverflow = true;
+						continue SRC;
+					}
+				}
+
+				SimilarityIndex d;
+				try {
+					d = hash(NEW, dstEnt);
+				} catch (TableFullException tableFull) {
+					if (dstTooLarge == null)
+						dstTooLarge = new BitSet(dsts.size());
+					dstTooLarge.set(dstIdx);
+					tableOverflow = true;
+					pm.update(1);
+					continue;
+				}
+
 				int contentScore = s.score(d, 10000);
 
 				// nameScore returns a value between 0 and 100, but we want it
@@ -336,7 +367,7 @@ static int nameScore(String a, String b) {
 	}
 
 	private SimilarityIndex hash(DiffEntry.Side side, DiffEntry ent)
-			throws IOException {
+			throws IOException, TableFullException {
 		SimilarityIndex r = new SimilarityIndex();
 		r.hash(reader.open(side, ent));
 		r.sort();
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheCheckout.java b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheCheckout.java
index bc51aa5..d262972 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheCheckout.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/dircache/DirCacheCheckout.java
@@ -144,8 +144,8 @@ public List<String> getRemoved() {
 	}
 
 	/**
-	 * Constructs a DirCacheCeckout for fast-forwarding from one tree to
-	 * another, merging it with the index
+	 * Constructs a DirCacheCeckout for merging and checking out two trees (HEAD
+	 * and mergeCommitTree) and the index.
 	 *
 	 * @param repo
 	 *            the repository in which we do the checkout
@@ -170,9 +170,9 @@ public DirCacheCheckout(Repository repo, ObjectId headCommitTree, DirCache dc,
 	}
 
 	/**
-	 * Constructs a DirCacheCeckout for checking out one tree, merging with the
-	 * index. As iterator over the working tree this constructor creates a
-	 * standard {@link FileTreeIterator}
+	 * Constructs a DirCacheCeckout for merging and checking out two trees (HEAD
+	 * and mergeCommitTree) and the index. As iterator over the working tree
+	 * this constructor creates a standard {@link FileTreeIterator}
 	 *
 	 * @param repo
 	 *            the repository in which we do the checkout
@@ -184,14 +184,54 @@ public DirCacheCheckout(Repository repo, ObjectId headCommitTree, DirCache dc,
 	 *            the id of the tree of the
 	 * @throws IOException
 	 */
-	public DirCacheCheckout(Repository repo, ObjectId headCommitTree, DirCache dc,
-			ObjectId mergeCommitTree) throws IOException {
+	public DirCacheCheckout(Repository repo, ObjectId headCommitTree,
+			DirCache dc, ObjectId mergeCommitTree) throws IOException {
 		this(repo, headCommitTree, dc, mergeCommitTree, new FileTreeIterator(
 				repo.getWorkTree(), repo.getFS(),
 				WorkingTreeOptions.createDefaultInstance()));
 	}
 
 	/**
+	 * Constructs a DirCacheCeckout for checking out one tree, merging with the
+	 * index.
+	 *
+	 * @param repo
+	 *            the repository in which we do the checkout
+	 * @param dc
+	 *            the (already locked) Dircache for this repo
+	 * @param mergeCommitTree
+	 *            the id of the tree we want to fast-forward to
+	 * @param workingTree
+	 *            an iterator over the repositories Working Tree
+	 * @throws IOException
+	 */
+	public DirCacheCheckout(Repository repo, DirCache dc,
+			ObjectId mergeCommitTree, WorkingTreeIterator workingTree)
+			throws IOException {
+		this(repo, null, dc, mergeCommitTree, workingTree);
+	}
+
+	/**
+	 * Constructs a DirCacheCeckout for checking out one tree, merging with the
+	 * index. As iterator over the working tree this constructor creates a
+	 * standard {@link FileTreeIterator}
+	 *
+	 * @param repo
+	 *            the repository in which we do the checkout
+	 * @param dc
+	 *            the (already locked) Dircache for this repo
+	 * @param mergeCommitTree
+	 *            the id of the tree of the
+	 * @throws IOException
+	 */
+	public DirCacheCheckout(Repository repo, DirCache dc,
+			ObjectId mergeCommitTree) throws IOException {
+		this(repo, null, dc, mergeCommitTree, new FileTreeIterator(
+				repo.getWorkTree(), repo.getFS(),
+				WorkingTreeOptions.createDefaultInstance()));
+	}
+
+	/**
 	 * Scan head, index and merge tree. Used during normal checkout or merge
 	 * operations.
 	 *
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java
index 85337c8..e1b96ea 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/FanoutBucket.java
@@ -43,12 +43,19 @@
 
 package org.eclipse.jgit.notes;
 
+import static org.eclipse.jgit.lib.FileMode.TREE;
+
 import java.io.IOException;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
 
 import org.eclipse.jgit.lib.AbbreviatedObjectId;
 import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.MutableObjectId;
 import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.ObjectReader;
+import org.eclipse.jgit.lib.TreeFormatter;
 
 /**
  * A note tree holding only note subtrees, each named using a 2 digit hex name.
@@ -84,6 +91,9 @@ class FanoutBucket extends InMemoryNoteBucket {
 	 */
 	private final NoteBucket[] table;
 
+	/** Number of non-null slots in {@link #table}. */
+	private int cnt;
+
 	FanoutBucket(int prefixLen) {
 		super(prefixLen);
 		table = new NoteBucket[256];
@@ -91,6 +101,7 @@ class FanoutBucket extends InMemoryNoteBucket {
 
 	void parseOneEntry(int cell, ObjectId id) {
 		table[cell] = new LazyNoteBucket(id);
+		cnt++;
 	}
 
 	@Override
@@ -99,6 +110,178 @@ ObjectId get(AnyObjectId objId, ObjectReader or) throws IOException {
 		return b != null ? b.get(objId, or) : null;
 	}
 
+	@Override
+	Iterator<Note> iterator(AnyObjectId objId, final ObjectReader reader)
+			throws IOException {
+		final MutableObjectId id = new MutableObjectId();
+		id.fromObjectId(objId);
+
+		return new Iterator<Note>() {
+			private int cell;
+
+			private Iterator<Note> itr;
+
+			public boolean hasNext() {
+				if (itr != null && itr.hasNext())
+					return true;
+
+				for (; cell < table.length; cell++) {
+					NoteBucket b = table[cell];
+					if (b == null)
+						continue;
+
+					try {
+						id.setByte(prefixLen >> 1, cell);
+						itr = b.iterator(id, reader);
+					} catch (IOException err) {
+						throw new RuntimeException(err);
+					}
+
+					if (itr.hasNext()) {
+						cell++;
+						return true;
+					}
+				}
+				return false;
+			}
+
+			public Note next() {
+				if (hasNext())
+					return itr.next();
+				else
+					throw new NoSuchElementException();
+			}
+
+			public void remove() {
+				throw new UnsupportedOperationException();
+			}
+		};
+	}
+
+	@Override
+	int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
+		// If most of this fan-out is full, estimate it should still be split.
+		if (LeafBucket.MAX_SIZE * 3 / 4 <= cnt)
+			return 1 + LeafBucket.MAX_SIZE;
+
+		// Due to the uniform distribution of ObjectIds, having less nodes full
+		// indicates a good chance the total number of children below here
+		// is less than the MAX_SIZE split point. Get a more accurate count.
+
+		MutableObjectId id = new MutableObjectId();
+		id.fromObjectId(noteOn);
+
+		int sz = 0;
+		for (int cell = 0; cell < 256; cell++) {
+			NoteBucket b = table[cell];
+			if (b == null)
+				continue;
+
+			id.setByte(prefixLen >> 1, cell);
+			sz += b.estimateSize(id, or);
+			if (LeafBucket.MAX_SIZE < sz)
+				break;
+		}
+		return sz;
+	}
+
+	@Override
+	InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
+			ObjectReader or) throws IOException {
+		int cell = cell(noteOn);
+		NoteBucket b = table[cell];
+
+		if (b == null) {
+			if (noteData == null)
+				return this;
+
+			LeafBucket n = new LeafBucket(prefixLen + 2);
+			table[cell] = n.set(noteOn, noteData, or);
+			cnt++;
+			return this;
+
+		} else {
+			NoteBucket n = b.set(noteOn, noteData, or);
+			if (n == null) {
+				table[cell] = null;
+				cnt--;
+
+				if (cnt == 0)
+					return null;
+
+				if (estimateSize(noteOn, or) < LeafBucket.MAX_SIZE) {
+					// We are small enough to just contract to a single leaf.
+					InMemoryNoteBucket r = new LeafBucket(prefixLen);
+					for (Iterator<Note> i = iterator(noteOn, or); i.hasNext();)
+						r = r.append(i.next());
+					r.nonNotes = nonNotes;
+					return r;
+				}
+
+				return this;
+
+			} else if (n != b) {
+				table[cell] = n;
+			}
+			return this;
+		}
+	}
+
+	private static final byte[] hexchar = { '0', '1', '2', '3', '4', '5', '6',
+			'7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f' };
+
+	@Override
+	ObjectId writeTree(ObjectInserter inserter) throws IOException {
+		byte[] nameBuf = new byte[2];
+		TreeFormatter fmt = new TreeFormatter(treeSize());
+		NonNoteEntry e = nonNotes;
+
+		for (int cell = 0; cell < 256; cell++) {
+			NoteBucket b = table[cell];
+			if (b == null)
+				continue;
+
+			nameBuf[0] = hexchar[cell >>> 4];
+			nameBuf[1] = hexchar[cell & 0x0f];
+
+			while (e != null && e.pathCompare(nameBuf, 0, 2, TREE) < 0) {
+				e.format(fmt);
+				e = e.next;
+			}
+
+			fmt.append(nameBuf, 0, 2, TREE, b.writeTree(inserter));
+		}
+
+		for (; e != null; e = e.next)
+			e.format(fmt);
+		return fmt.insert(inserter);
+	}
+
+	private int treeSize() {
+		int sz = cnt * TreeFormatter.entrySize(TREE, 2);
+		for (NonNoteEntry e = nonNotes; e != null; e = e.next)
+			sz += e.treeEntrySize();
+		return sz;
+	}
+
+	@Override
+	InMemoryNoteBucket append(Note note) {
+		int cell = cell(note);
+		InMemoryNoteBucket b = (InMemoryNoteBucket) table[cell];
+
+		if (b == null) {
+			LeafBucket n = new LeafBucket(prefixLen + 2);
+			table[cell] = n.append(note);
+			cnt++;
+
+		} else {
+			InMemoryNoteBucket n = b.append(note);
+			if (n != b)
+				table[cell] = n;
+		}
+		return this;
+	}
+
 	private int cell(AnyObjectId id) {
 		return id.getByte(prefixLen >> 1);
 	}
@@ -115,6 +298,28 @@ ObjectId get(AnyObjectId objId, ObjectReader or) throws IOException {
 			return load(objId, or).get(objId, or);
 		}
 
+		@Override
+		Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader)
+				throws IOException {
+			return load(objId, reader).iterator(objId, reader);
+		}
+
+		@Override
+		int estimateSize(AnyObjectId objId, ObjectReader or) throws IOException {
+			return load(objId, or).estimateSize(objId, or);
+		}
+
+		@Override
+		InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
+				ObjectReader or) throws IOException {
+			return load(noteOn, or).set(noteOn, noteData, or);
+		}
+
+		@Override
+		ObjectId writeTree(ObjectInserter inserter) {
+			return treeId;
+		}
+
 		private NoteBucket load(AnyObjectId objId, ObjectReader or)
 				throws IOException {
 			AbbreviatedObjectId p = objId.abbreviate(prefixLen + 2);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/InMemoryNoteBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/InMemoryNoteBucket.java
index 7d0df73..0f45f82 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/InMemoryNoteBucket.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/InMemoryNoteBucket.java
@@ -54,7 +54,20 @@ abstract class InMemoryNoteBucket extends NoteBucket {
 	 */
 	final int prefixLen;
 
+	/**
+	 * Chain of non-note tree entries found at this path in the tree.
+	 *
+	 * During parsing of a note tree into the in-memory representation,
+	 * {@link NoteParser} keeps track of all non-note tree entries and stores
+	 * them here as a sorted linked list. That list can be merged back with the
+	 * note data that is held by the subclass, allowing the tree to be
+	 * recreated.
+	 */
+	NonNoteEntry nonNotes;
+
 	InMemoryNoteBucket(int prefixLen) {
 		this.prefixLen = prefixLen;
 	}
+
+	abstract InMemoryNoteBucket append(Note note);
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java
index 66d773a..af6c6f4 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/LeafBucket.java
@@ -43,9 +43,18 @@
 
 package org.eclipse.jgit.notes;
 
+import static org.eclipse.jgit.lib.Constants.OBJECT_ID_STRING_LENGTH;
+import static org.eclipse.jgit.lib.FileMode.REGULAR_FILE;
+
+import java.io.IOException;
+import java.util.Iterator;
+import java.util.NoSuchElementException;
+
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.ObjectReader;
+import org.eclipse.jgit.lib.TreeFormatter;
 
 /**
  * A note tree holding only notes, with no subtrees.
@@ -64,6 +73,8 @@
  * A LeafBucket must be parsed from a tree object by {@link NoteParser}.
  */
 class LeafBucket extends InMemoryNoteBucket {
+	static final int MAX_SIZE = 256;
+
 	/** All note blobs in this bucket, sorted sequentially. */
 	private Note[] notes;
 
@@ -96,11 +107,116 @@ ObjectId get(AnyObjectId objId, ObjectReader or) {
 		return 0 <= idx ? notes[idx].getData() : null;
 	}
 
+	@Override
+	Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader) {
+		return new Iterator<Note>() {
+			private int idx;
+
+			public boolean hasNext() {
+				return idx < cnt;
+			}
+
+			public Note next() {
+				if (hasNext())
+					return notes[idx++];
+				else
+					throw new NoSuchElementException();
+			}
+
+			public void remove() {
+				throw new UnsupportedOperationException();
+			}
+		};
+	}
+
+	@Override
+	int estimateSize(AnyObjectId noteOn, ObjectReader or) throws IOException {
+		return cnt;
+	}
+
+	InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
+			ObjectReader or) throws IOException {
+		int p = search(noteOn);
+		if (0 <= p) {
+			if (noteData != null) {
+				notes[p].setData(noteData.copy());
+				return this;
+
+			} else {
+				System.arraycopy(notes, p + 1, notes, p, cnt - p - 1);
+				cnt--;
+				return 0 < cnt ? this : null;
+			}
+
+		} else if (noteData != null) {
+			if (shouldSplit()) {
+				return split().set(noteOn, noteData, or);
+
+			} else {
+				growIfFull();
+				p = -(p + 1);
+				if (p < cnt)
+					System.arraycopy(notes, p, notes, p + 1, cnt - p);
+				notes[p] = new Note(noteOn, noteData.copy());
+				cnt++;
+				return this;
+			}
+
+		} else {
+			return this;
+		}
+	}
+
+	@Override
+	ObjectId writeTree(ObjectInserter inserter) throws IOException {
+		byte[] nameBuf = new byte[OBJECT_ID_STRING_LENGTH];
+		int nameLen = OBJECT_ID_STRING_LENGTH - prefixLen;
+		TreeFormatter fmt = new TreeFormatter(treeSize(nameLen));
+		NonNoteEntry e = nonNotes;
+
+		for (int i = 0; i < cnt; i++) {
+			Note n = notes[i];
+
+			n.copyTo(nameBuf, 0);
+
+			while (e != null
+					&& e.pathCompare(nameBuf, prefixLen, nameLen, REGULAR_FILE) < 0) {
+				e.format(fmt);
+				e = e.next;
+			}
+
+			fmt.append(nameBuf, prefixLen, nameLen, REGULAR_FILE, n.getData());
+		}
+
+		for (; e != null; e = e.next)
+			e.format(fmt);
+		return fmt.insert(inserter);
+	}
+
+	private int treeSize(final int nameLen) {
+		int sz = cnt * TreeFormatter.entrySize(REGULAR_FILE, nameLen);
+		for (NonNoteEntry e = nonNotes; e != null; e = e.next)
+			sz += e.treeEntrySize();
+		return sz;
+	}
+
 	void parseOneEntry(AnyObjectId noteOn, AnyObjectId noteData) {
 		growIfFull();
 		notes[cnt++] = new Note(noteOn, noteData.copy());
 	}
 
+	@Override
+	InMemoryNoteBucket append(Note note) {
+		if (shouldSplit()) {
+			return split().append(note);
+
+		} else {
+			growIfFull();
+			notes[cnt++] = note;
+			return this;
+		}
+	}
+
 	private void growIfFull() {
 		if (notes.length == cnt) {
 			Note[] n = new Note[notes.length * 2];
@@ -108,4 +224,16 @@ private void growIfFull() {
 			notes = n;
 		}
 	}
+
+	private boolean shouldSplit() {
+		return MAX_SIZE <= cnt && prefixLen + 2 < OBJECT_ID_STRING_LENGTH;
+	}
+
+	private InMemoryNoteBucket split() {
+		FanoutBucket n = new FanoutBucket(prefixLen);
+		for (int i = 0; i < cnt; i++)
+			n.append(notes[i]);
+		n.nonNotes = nonNotes;
+		return n;
+	}
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java
new file mode 100644
index 0000000..6a2d44b
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NonNoteEntry.java
@@ -0,0 +1,100 @@
+/*
+ * Copyright (C) 2010, Google Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.notes;
+
+import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.FileMode;
+import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.TreeFormatter;
+
+/** A tree entry found in a note branch that isn't a valid note. */
+class NonNoteEntry extends ObjectId {
+	/** Name of the entry in the tree, in raw format. */
+	private final byte[] name;
+
+	/** Mode of the entry as parsed from the tree. */
+	private final FileMode mode;
+
+	/** The next non-note entry in the same tree, as defined by tree order. */
+	NonNoteEntry next;
+
+	NonNoteEntry(byte[] name, FileMode mode, AnyObjectId id) {
+		super(id);
+		this.name = name;
+		this.mode = mode;
+	}
+
+	void format(TreeFormatter fmt) {
+		fmt.append(name, mode, this);
+	}
+
+	int treeEntrySize() {
+		return TreeFormatter.entrySize(mode, name.length);
+	}
+
+	int pathCompare(byte[] bBuf, int bPos, int bLen, FileMode bMode) {
+		return pathCompare(name, 0, name.length, mode, //
+				bBuf, bPos, bLen, bMode);
+	}
+
+	private static int pathCompare(final byte[] aBuf, int aPos, final int aEnd,
+			final FileMode aMode, final byte[] bBuf, int bPos, final int bEnd,
+			final FileMode bMode) {
+		while (aPos < aEnd && bPos < bEnd) {
+			int cmp = (aBuf[aPos++] & 0xff) - (bBuf[bPos++] & 0xff);
+			if (cmp != 0)
+				return cmp;
+		}
+
+		if (aPos < aEnd)
+			return (aBuf[aPos] & 0xff) - lastPathChar(bMode);
+		if (bPos < bEnd)
+			return lastPathChar(aMode) - (bBuf[bPos] & 0xff);
+		return 0;
+	}
+
+	private static int lastPathChar(final FileMode mode) {
+		return FileMode.TREE.equals(mode.getBits()) ? '/' : '\0';
+	}
+}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java
index 286f140..defc37d 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteBucket.java
@@ -44,9 +44,11 @@
 package org.eclipse.jgit.notes;
 
 import java.io.IOException;
+import java.util.Iterator;
 
 import org.eclipse.jgit.lib.AnyObjectId;
 import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.ObjectReader;
 
 /**
@@ -58,4 +60,15 @@
 abstract class NoteBucket {
 	abstract ObjectId get(AnyObjectId objId, ObjectReader reader)
 			throws IOException;
+
+	abstract Iterator<Note> iterator(AnyObjectId objId, ObjectReader reader)
+			throws IOException;
+
+	abstract int estimateSize(AnyObjectId noteOn, ObjectReader or)
+			throws IOException;
+
+	abstract InMemoryNoteBucket set(AnyObjectId noteOn, AnyObjectId noteData,
+			ObjectReader reader) throws IOException;
+
+	abstract ObjectId writeTree(ObjectInserter inserter) throws IOException;
 }
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java
index d2f0727..6a7b5cf 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteMap.java
@@ -51,7 +51,9 @@
 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.lib.AbbreviatedObjectId;
 import org.eclipse.jgit.lib.AnyObjectId;
+import org.eclipse.jgit.lib.Constants;
 import org.eclipse.jgit.lib.ObjectId;
+import org.eclipse.jgit.lib.ObjectInserter;
 import org.eclipse.jgit.lib.ObjectReader;
 import org.eclipse.jgit.revwalk.RevCommit;
 import org.eclipse.jgit.revwalk.RevTree;
@@ -66,6 +68,17 @@
  */
 public class NoteMap {
 	/**
+	 * Construct a new empty note map.
+	 *
+	 * @return an empty note map.
+	 */
+	public static NoteMap newEmptyMap() {
+		NoteMap r = new NoteMap(null /* no reader */);
+		r.root = new LeafBucket(0);
+		return r;
+	}
+
+	/**
 	 * Load a collection of notes from a branch.
 	 *
 	 * @param reader
@@ -213,6 +226,104 @@ public boolean contains(AnyObjectId id) throws IOException {
 			return null;
 	}
 
+	/**
+	 * Attach (or remove) a note on an object.
+	 *
+	 * If no note exists, a new note is stored. If a note already exists for the
+	 * given object, it is replaced (or removed).
+	 *
+	 * This method only updates the map in memory.
+	 *
+	 * If the caller wants to attach a UTF-8 encoded string message to an
+	 * object, {@link #set(AnyObjectId, String, ObjectInserter)} is a convenient
+	 * way to encode and update a note in one step.
+	 *
+	 * @param noteOn
+	 *            the object to attach the note to. This same ObjectId can later
+	 *            be used as an argument to {@link #get(AnyObjectId)} or
+	 *            {@link #getCachedBytes(AnyObjectId, int)} to read back the
+	 *            {@code noteData}.
+	 * @param noteData
+	 *            data to associate with the note. This must be the ObjectId of
+	 *            a blob that already exists in the repository. If null the note
+	 *            will be deleted, if present.
+	 * @throws IOException
+	 *             a portion of the note space is not accessible.
+	 */
+	public void set(AnyObjectId noteOn, ObjectId noteData) throws IOException {
+		InMemoryNoteBucket newRoot = root.set(noteOn, noteData, reader);
+		if (newRoot == null) {
+			newRoot = new LeafBucket(0);
+			newRoot.nonNotes = root.nonNotes;
+		}
+		root = newRoot;
+	}
+
+	/**
+	 * Attach a note to an object.
+	 *
+	 * If no note exists, a new note is stored. If a note already exists for the
+	 * given object, it is replaced (or removed).
+	 *
+	 * @param noteOn
+	 *            the object to attach the note to. This same ObjectId can later
+	 *            be used as an argument to {@link #get(AnyObjectId)} or
+	 *            {@link #getCachedBytes(AnyObjectId, int)} to read back the
+	 *            {@code noteData}.
+	 * @param noteData
+	 *            text to store in the note. The text will be UTF-8 encoded when
+	 *            stored in the repository. If null the note will be deleted, if
+	 *            the empty string a note with the empty string will be stored.
+	 * @param ins
+	 *            inserter to write the encoded {@code noteData} out as a blob.
+	 *            The caller must ensure the inserter is flushed before the
+	 *            updated note map is made available for reading.
+	 * @throws IOException
+	 *             the note data could not be stored in the repository.
+	 */
+	public void set(AnyObjectId noteOn, String noteData, ObjectInserter ins)
+			throws IOException {
+		ObjectId dataId;
+		if (noteData != null) {
+			byte[] dataUTF8 = Constants.encode(noteData);
+			dataId = ins.insert(Constants.OBJ_BLOB, dataUTF8);
+		} else {
+			dataId = null;
+		}
+		set(noteOn, dataId);
+	}
+
+	/**
+	 * Remove a note from an object.
+	 *
+	 * If no note exists, no action is performed.
+	 *
+	 * This method only updates the map in memory.
+	 *
+	 * @param noteOn
+	 *            the object to remove the note from.
+	 * @throws IOException
+	 *             a portion of the note space is not accessible.
+	 */
+	public void remove(AnyObjectId noteOn) throws IOException {
+		set(noteOn, null);
+	}
+
+	/**
+	 * Write this note map as a tree.
+	 *
+	 * @param inserter
+	 *            inserter to use when writing trees to the object database.
+	 *            Caller is responsible for flushing the inserter before trying
+	 *            to read the objects, or exposing them through a reference.
+	 * @return the top level tree.
+	 * @throws IOException
+	 *             a tree could not be written.
+	 */
+	public ObjectId writeTree(ObjectInserter inserter) throws IOException {
+		return root.writeTree(inserter);
+	}
+
 	private void load(ObjectId rootTree) throws MissingObjectException,
 			IncorrectObjectTypeException, CorruptObjectException, IOException {
 		AbbreviatedObjectId none = AbbreviatedObjectId.fromString("");
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java
index 04e260a..d916e35 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/notes/NoteParser.java
@@ -52,6 +52,7 @@
 
 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
 import org.eclipse.jgit.lib.AbbreviatedObjectId;
+import org.eclipse.jgit.lib.FileMode;
 import org.eclipse.jgit.lib.MutableObjectId;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectReader;
@@ -87,13 +88,17 @@ final class NoteParser extends CanonicalTreeParser {
 	static InMemoryNoteBucket parse(AbbreviatedObjectId prefix,
 			final ObjectId treeId, final ObjectReader reader)
 			throws IOException {
-		return new NoteParser(prefix, reader, treeId).parseTree();
+		return new NoteParser(prefix, reader, treeId).parse();
 	}
 
 	private final AbbreviatedObjectId prefix;
 
 	private final int pathPadding;
 
+	private NonNoteEntry firstNonNote;
+
+	private NonNoteEntry lastNonNote;
+
 	private NoteParser(AbbreviatedObjectId p, ObjectReader r, ObjectId t)
 			throws IncorrectObjectTypeException, IOException {
 		super(encodeASCII(p.name()), r, t);
@@ -106,6 +111,12 @@ private NoteParser(AbbreviatedObjectId p, ObjectReader r, ObjectId t)
 			System.arraycopy(path, 0, path, pathPadding, prefix.length());
 	}
 
+	private InMemoryNoteBucket parse() {
+		InMemoryNoteBucket r = parseTree();
+		r.nonNotes = firstNonNote;
+		return r;
+	}
+
 	private InMemoryNoteBucket parseTree() {
 		for (; !eof(); next(1)) {
 			if (pathLen == pathPadding + OBJECT_ID_STRING_LENGTH && isHex())
@@ -113,6 +124,9 @@ private InMemoryNoteBucket parseTree() {
 
 			else if (getNameLength() == 2 && isHex() && isTree())
 				return parseFanoutTree();
+
+			else
+				storeNonNote();
 		}
 
 		// If we cannot determine the style used, assume its a leaf.
@@ -126,6 +140,8 @@ private LeafBucket parseLeafTree() {
 		for (; !eof(); next(1)) {
 			if (parseObjectId(idBuf))
 				leaf.parseOneEntry(idBuf, getEntryObjectId());
+			else
+				storeNonNote();
 		}
 
 		return leaf;
@@ -150,6 +166,8 @@ private FanoutBucket parseFanoutTree() {
 			final int cell = parseFanoutCell();
 			if (0 <= cell)
 				fanout.parseOneEntry(cell, getEntryObjectId());
+			else
+				storeNonNote();
 		}
 
 		return fanout;
@@ -168,6 +186,21 @@ private int parseFanoutCell() {
 		}
 	}
 
+	private void storeNonNote() {
+		ObjectId id = getEntryObjectId();
+		FileMode fileMode = getEntryFileMode();
+
+		byte[] name = new byte[getNameLength()];
+		getName(name, 0);
+
+		NonNoteEntry ent = new NonNoteEntry(name, fileMode, id);
+		if (firstNonNote == null)
+			firstNonNote = ent;
+		if (lastNonNote != null)
+			lastNonNote.next = ent;
+		lastNonNote = ent;
+	}
+
 	private boolean isTree() {
 		return TREE.equals(mode);
 	}
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LockFile.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LockFile.java
index e8bc3e2..6199f4c 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LockFile.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/LockFile.java
@@ -44,7 +44,6 @@
 
 package org.eclipse.jgit.storage.file;
 
-import java.io.BufferedOutputStream;
 import java.io.File;
 import java.io.FileInputStream;
 import java.io.FileNotFoundException;
@@ -52,8 +51,9 @@
 import java.io.FilenameFilter;
 import java.io.IOException;
 import java.io.OutputStream;
-import java.nio.channels.FileLock;
-import java.nio.channels.OverlappingFileLockException;
+import java.nio.ByteBuffer;
+import java.nio.channels.Channels;
+import java.nio.channels.FileChannel;
 import java.text.MessageFormat;
 
 import org.eclipse.jgit.JGitText;
@@ -85,14 +85,14 @@ public boolean accept(File dir, String name) {
 
 	private final File lck;
 
-	private FileLock fLck;
-
 	private boolean haveLck;
 
 	private FileOutputStream os;
 
 	private boolean needStatInformation;
 
+	private boolean fsync;
+
 	private long commitLastModified;
 
 	private final FS fs;
@@ -127,23 +127,6 @@ public boolean lock() throws IOException {
 			haveLck = true;
 			try {
 				os = new FileOutputStream(lck);
-				try {
-					fLck = os.getChannel().tryLock();
-					if (fLck == null)
-						throw new OverlappingFileLockException();
-				} catch (OverlappingFileLockException ofle) {
-					// We cannot use unlock() here as this file is not
-					// held by us, but we thought we created it. We must
-					// not delete it, as it belongs to some other process.
-					//
-					haveLck = false;
-					try {
-						os.close();
-					} catch (IOException ioe) {
-						// Fail by returning haveLck = false.
-					}
-					os = null;
-				}
 			} catch (IOException ioe) {
 				unlock();
 				throw ioe;
@@ -192,10 +175,21 @@ public void copyCurrentContent() throws IOException {
 		try {
 			final FileInputStream fis = new FileInputStream(ref);
 			try {
-				final byte[] buf = new byte[2048];
-				int r;
-				while ((r = fis.read(buf)) >= 0)
-					os.write(buf, 0, r);
+				if (fsync) {
+					FileChannel in = fis.getChannel();
+					long pos = 0;
+					long cnt = in.size();
+					while (0 < cnt) {
+						long r = os.getChannel().transferFrom(in, pos, cnt);
+						pos += r;
+						cnt -= r;
+					}
+				} else {
+					final byte[] buf = new byte[2048];
+					int r;
+					while ((r = fis.read(buf)) >= 0)
+						os.write(buf, 0, r);
+				}
 			} finally {
 				fis.close();
 			}
@@ -229,26 +223,10 @@ public void copyCurrentContent() throws IOException {
 	 *             before throwing the underlying exception to the caller.
 	 */
 	public void write(final ObjectId id) throws IOException {
-		requireLock();
-		try {
-			final BufferedOutputStream b;
-			b = new BufferedOutputStream(os, Constants.OBJECT_ID_STRING_LENGTH + 1);
-			id.copyTo(b);
-			b.write('\n');
-			b.flush();
-			fLck.release();
-			b.close();
-			os = null;
-		} catch (IOException ioe) {
-			unlock();
-			throw ioe;
-		} catch (RuntimeException ioe) {
-			unlock();
-			throw ioe;
-		} catch (Error ioe) {
-			unlock();
-			throw ioe;
-		}
+		byte[] buf = new byte[Constants.OBJECT_ID_STRING_LENGTH + 1];
+		id.copyTo(buf, 0);
+		buf[Constants.OBJECT_ID_STRING_LENGTH] = '\n';
+		write(buf);
 	}
 
 	/**
@@ -268,9 +246,15 @@ public void write(final ObjectId id) throws IOException {
 	public void write(final byte[] content) throws IOException {
 		requireLock();
 		try {
-			os.write(content);
-			os.flush();
-			fLck.release();
+			if (fsync) {
+				FileChannel fc = os.getChannel();
+				ByteBuffer buf = ByteBuffer.wrap(content);
+				while (0 < buf.remaining())
+					fc.write(buf);
+				fc.force(true);
+			} else {
+				os.write(content);
+			}
 			os.close();
 			os = null;
 		} catch (IOException ioe) {
@@ -296,34 +280,36 @@ public void write(final byte[] content) throws IOException {
 	 */
 	public OutputStream getOutputStream() {
 		requireLock();
+
+		final OutputStream out;
+		if (fsync)
+			out = Channels.newOutputStream(os.getChannel());
+		else
+			out = os;
+
 		return new OutputStream() {
 			@Override
 			public void write(final byte[] b, final int o, final int n)
 					throws IOException {
-				os.write(b, o, n);
+				out.write(b, o, n);
 			}
 
 			@Override
 			public void write(final byte[] b) throws IOException {
-				os.write(b);
+				out.write(b);
 			}
 
 			@Override
 			public void write(final int b) throws IOException {
-				os.write(b);
-			}
-
-			@Override
-			public void flush() throws IOException {
-				os.flush();
+				out.write(b);
 			}
 
 			@Override
 			public void close() throws IOException {
 				try {
-					os.flush();
-					fLck.release();
-					os.close();
+					if (fsync)
+						os.getChannel().force(true);
+					out.close();
 					os = null;
 				} catch (IOException ioe) {
 					unlock();
@@ -357,6 +343,16 @@ public void setNeedStatInformation(final boolean on) {
 	}
 
 	/**
+	 * Request that {@link #commit()} force dirty data to the drive.
+	 *
+	 * @param on
+	 *            true if dirty data should be forced to the drive.
+	 */
+	public void setFSync(final boolean on) {
+		fsync = on;
+	}
+
+	/**
 	 * Wait until the lock file information differs from the old file.
 	 * <p>
 	 * This method tests both the length and the last modification date. If both
@@ -447,14 +443,6 @@ public long getCommitLastModified() {
 	 */
 	public void unlock() {
 		if (os != null) {
-			if (fLck != null) {
-				try {
-					fLck.release();
-				} catch (IOException ioe) {
-					// Huh?
-				}
-				fLck = null;
-			}
 			try {
 				os.close();
 			} catch (IOException ioe) {
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/ObjectDirectoryInserter.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/ObjectDirectoryInserter.java
index 16cb8aa..d922beb 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/ObjectDirectoryInserter.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/ObjectDirectoryInserter.java
@@ -52,6 +52,7 @@
 import java.io.IOException;
 import java.io.InputStream;
 import java.io.OutputStream;
+import java.nio.channels.Channels;
 import java.security.DigestOutputStream;
 import java.security.MessageDigest;
 import java.util.zip.Deflater;
@@ -60,7 +61,6 @@
 import org.eclipse.jgit.errors.ObjectWritingException;
 import org.eclipse.jgit.lib.Config;
 import org.eclipse.jgit.lib.Constants;
-import org.eclipse.jgit.lib.CoreConfig;
 import org.eclipse.jgit.lib.ObjectId;
 import org.eclipse.jgit.lib.ObjectInserter;
 
@@ -68,13 +68,13 @@
 class ObjectDirectoryInserter extends ObjectInserter {
 	private final FileObjectDatabase db;
 
-	private final Config config;
+	private final WriteConfig config;
 
 	private Deflater deflate;
 
 	ObjectDirectoryInserter(final FileObjectDatabase dest, final Config cfg) {
 		db = dest;
-		config = cfg;
+		config = cfg.get(WriteConfig.KEY);
 	}
 
 	@Override
@@ -121,9 +121,13 @@ private File toTemp(final MessageDigest md, final int type, long len,
 		boolean delete = true;
 		File tmp = newTempFile();
 		try {
-			DigestOutputStream dOut = new DigestOutputStream(
-					compress(new FileOutputStream(tmp)), md);
+			FileOutputStream fOut = new FileOutputStream(tmp);
 			try {
+				OutputStream out = fOut;
+				if (config.getFSyncObjectFiles())
+					out = Channels.newOutputStream(fOut.getChannel());
+				DeflaterOutputStream cOut = compress(out);
+				DigestOutputStream dOut = new DigestOutputStream(cOut, md);
 				writeHeader(dOut, type, len);
 
 				final byte[] buf = buffer();
@@ -134,8 +138,12 @@ private File toTemp(final MessageDigest md, final int type, long len,
 					dOut.write(buf, 0, n);
 					len -= n;
 				}
+				dOut.flush();
+				cOut.finish();
 			} finally {
-				dOut.close();
+				if (config.getFSyncObjectFiles())
+					fOut.getChannel().force(true);
+				fOut.close();
 			}
 
 			delete = false;
@@ -160,7 +168,7 @@ File newTempFile() throws IOException {
 
 	DeflaterOutputStream compress(final OutputStream out) {
 		if (deflate == null)
-			deflate = new Deflater(config.get(CoreConfig.KEY).getCompression());
+			deflate = new Deflater(config.getCompression());
 		else
 			deflate.reset();
 		return new DeflaterOutputStream(out, deflate);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectory.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectory.java
index 96c8361..2af7ca3 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectory.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectory.java
@@ -67,6 +67,8 @@
 import java.io.FileOutputStream;
 import java.io.IOException;
 import java.io.InputStreamReader;
+import java.nio.ByteBuffer;
+import java.nio.channels.FileChannel;
 import java.text.MessageFormat;
 import java.util.Arrays;
 import java.util.LinkedList;
@@ -606,6 +608,7 @@ else if (log.isFile())
 			write = false;
 
 		if (write) {
+			WriteConfig wc = getRepository().getConfig().get(WriteConfig.KEY);
 			FileOutputStream out;
 			try {
 				out = new FileOutputStream(log, true);
@@ -618,7 +621,15 @@ else if (log.isFile())
 				out = new FileOutputStream(log, true);
 			}
 			try {
-				out.write(rec);
+				if (wc.getFSyncRefFiles()) {
+					FileChannel fc = out.getChannel();
+					ByteBuffer buf = ByteBuffer.wrap(rec);
+					while (0 < buf.remaining())
+						fc.write(buf);
+					fc.force(true);
+				} else {
+					out.write(rec);
+				}
 			} finally {
 				out.close();
 			}
@@ -757,6 +768,7 @@ private void commitPackedRefs(final LockFile lck, final RefList<Ref> refs,
 			@Override
 			protected void writeFile(String name, byte[] content)
 					throws IOException {
+				lck.setFSync(true);
 				lck.setNeedStatInformation(true);
 				try {
 					lck.write(content);
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectoryUpdate.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectoryUpdate.java
index a9f0548..109960d 100644
--- a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectoryUpdate.java
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/RefDirectoryUpdate.java
@@ -99,6 +99,10 @@ protected void unlock() {
 
 	@Override
 	protected Result doUpdate(final Result status) throws IOException {
+		WriteConfig wc = database.getRepository().getConfig()
+				.get(WriteConfig.KEY);
+
+		lock.setFSync(wc.getFSyncRefFiles());
 		lock.setNeedStatInformation(true);
 		lock.write(getNewObjectId());
 
@@ -143,6 +147,10 @@ protected Result doDelete(final Result status) throws IOException {
 
 	@Override
 	protected Result doLink(final String target) throws IOException {
+		WriteConfig wc = database.getRepository().getConfig()
+				.get(WriteConfig.KEY);
+
+		lock.setFSync(wc.getFSyncRefFiles());
 		lock.setNeedStatInformation(true);
 		lock.write(encode(RefDirectory.SYMREF + target + '\n'));
 
diff --git a/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WriteConfig.java b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WriteConfig.java
new file mode 100644
index 0000000..fd467a5
--- /dev/null
+++ b/org.eclipse.jgit/src/org/eclipse/jgit/storage/file/WriteConfig.java
@@ -0,0 +1,81 @@
+/*
+ * Copyright (C) 2010, Google Inc.
+ * and other copyright owners as documented in the project's IP log.
+ *
+ * This program and the accompanying materials are made available
+ * under the terms of the Eclipse Distribution License v1.0 which
+ * accompanies this distribution, is reproduced below, and is
+ * available at http://www.eclipse.org/org/documents/edl-v10.php
+ *
+ * All rights reserved.
+ *
+ * Redistribution and use in source and binary forms, with or
+ * without modification, are permitted provided that the following
+ * conditions are met:
+ *
+ * - Redistributions of source code must retain the above copyright
+ *   notice, this list of conditions and the following disclaimer.
+ *
+ * - Redistributions in binary form must reproduce the above
+ *   copyright notice, this list of conditions and the following
+ *   disclaimer in the documentation and/or other materials provided
+ *   with the distribution.
+ *
+ * - Neither the name of the Eclipse Foundation, Inc. nor the
+ *   names of its contributors may be used to endorse or promote
+ *   products derived from this software without specific prior
+ *   written permission.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
+ * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+package org.eclipse.jgit.storage.file;
+
+import org.eclipse.jgit.lib.Config;
+import org.eclipse.jgit.lib.Config.SectionParser;
+import org.eclipse.jgit.lib.CoreConfig;
+
+class WriteConfig {
+	/** Key for {@link Config#get(SectionParser)}. */
+	static final Config.SectionParser<WriteConfig> KEY = new SectionParser<WriteConfig>() {
+		public WriteConfig parse(final Config cfg) {
+			return new WriteConfig(cfg);
+		}
+	};
+
+	private final int compression;
+
+	private final boolean fsyncObjectFiles;
+
+	private final boolean fsyncRefFiles;
+
+	private WriteConfig(final Config rc) {
+		compression = rc.get(CoreConfig.KEY).getCompression();
+		fsyncObjectFiles = rc.getBoolean("core", "fsyncobjectfiles", false);
+		fsyncRefFiles = rc.getBoolean("core", "fsyncreffiles", false);
+	}
+
+	int getCompression() {
+		return compression;
+	}
+
+	boolean getFSyncObjectFiles() {
+		return fsyncObjectFiles;
+	}
+
+	boolean getFSyncRefFiles() {
+		return fsyncRefFiles;
+	}
+}