Split note leaf buckets at 256 elements

Leaf level notes trees are split into a new fan-out tree if an
insertion occurs and the tree already contains >= 256 notes in it.

The splitting may occur multiple times if all of the notes have the
same prefix; in the worst case this produces a tree path such as
"00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/00/be" if all
of the notes begin with zeros.

Change-Id: I2d7d98f35108def9ec49936ddbdc34b13822a3c7
Signed-off-by: Shawn O. Pearce <spearce@spearce.org>

1 files changed, 41 insertions, 0 deletions

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 f22b020989..d740ffaf15 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
@@ -47,6 +47,7 @@ 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;
@@ -361,6 +362,46 @@ public class NoteMapTest extends RepositoryTestCase {
 				.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");