{"thread":{"id":"13970","subject":"[EGIT PATCH 01/20] Fix typo in PackIndexV2","startedAt":"2008-06-15T21:45:29Z","lastAt":"2008-06-19T16:26:59Z","messageCount":29,"participants":["Marek Zawirski","Shawn O. Pearce","Robin Rosenberg"],"isPatch":true,"patchVersion":1,"patchTotal":20},"messages":[{"id":"79967","messageId":"1213566349-25395-1-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":null,"subject":"[EGIT PATCH 00/20] PackWriter, first usable attempt","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:29Z","receivedAt":"2008-06-15T21:45:29Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Studying made me busy last week, but I'm back:\nwith another GSoC series, adding some usable feature this time.\n\nAt first, some stuff was still missing to produce packs, mostly\nraw-data access related and ObjectWalk related.\n\nFinally, we've got some support for pack writing! It's not that\npower that C git version offers, but something usable. Delta\ngeneration is not supported. Although we can reuse deltas and objects,\nand support all other (I hope) options of git-pack-objects directly or\nindirectly, most importantly --thin.\n\nPack writing and some other features are tested, seem to work.\n\nThis implementation of packing is not a very valuable thing directly\n(achieving efficient storage), however it's a base for enhancements\nand can be used for sending packs over net (with some assumptions).\nIt's more a \"repacking\" than \"packing\" tool.\n\nSo... I'm switching now to push implementation. If time allows,\ndelta-algorithms will be added later.\n\nRobin,\nthis series is based on master of egit.git when I saw it last time\nbefore repo.or.cz went down (9354293) ;) I'll add packwriter branch\nto my repo when server is up.\n\nMarek Zawirski (20):\n Fix typo in PackIndexV2\n Integer versions of copyRawTo() and fromRaw() in ObjectId\n Add openObjectInAllPacks() to Repository, exposing packed objects\n storage\n WindowedFile fragments copying: copyToStream()\n Reverse pack index implementation: PackReverseIndex\n Tests for PackReverseIndex\n Refactor PackIndexV2 - extract binarySearchLevelTwo()\n CRC32 support for PackIndex\n CRC32 PackIndex tests\n Format PackedObjectLoader class\n Format UnpackedObjectLoader class\n Format DeltaOfsPackedObjectLoader class\n Raw-data operations in ObjectLoaders and PackFile\n Add hasRevSort() in RevWalk for faster sorting strategy checking\n Refactor getRevSort() calls to hasRevSort()\n Support for RevSort.BOUNDARY in ObjectWalk\n Rename confusing objects field in ObjectWalk\n New CountingOutputStream class - stream decorator\n Simplified implementation of pack creation: PackWriter\n PackWriter test suite\n\n .../tst/org/spearce/jgit/lib/PackIndexTest.java | 10 +\n .../tst/org/spearce/jgit/lib/PackIndexV1Test.java | 19 +\n .../tst/org/spearce/jgit/lib/PackIndexV2Test.java | 30 +\n .../org/spearce/jgit/lib/PackReverseIndexTest.java | 115 +++\n .../tst/org/spearce/jgit/lib/PackWriterTest.java | 454 ++++++++++\n org.spearce.jgit.test/tst/pack-huge.idx | Bin 0 -> 2368 bytes\n .../src/org/spearce/jgit/lib/AnyObjectId.java | 16 +\n .../jgit/lib/DeltaOfsPackedObjectLoader.java | 24 +-\n .../spearce/jgit/lib/DeltaPackedObjectLoader.java | 9 +-\n .../jgit/lib/DeltaRefPackedObjectLoader.java | 15 +-\n .../src/org/spearce/jgit/lib/ObjectId.java | 26 +\n .../src/org/spearce/jgit/lib/ObjectLoader.java | 24 +\n .../src/org/spearce/jgit/lib/PackFile.java | 85 ++-\n .../src/org/spearce/jgit/lib/PackIndex.java | 23 +\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 10 +\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 73 +-\n .../src/org/spearce/jgit/lib/PackReverseIndex.java | 179 ++++\n .../src/org/spearce/jgit/lib/PackWriter.java | 882 ++++++++++++++++++++\n .../org/spearce/jgit/lib/PackedObjectLoader.java | 47 +-\n .../src/org/spearce/jgit/lib/Repository.java | 42 +\n .../org/spearce/jgit/lib/UnpackedObjectLoader.java | 26 +-\n .../spearce/jgit/lib/WholePackedObjectLoader.java | 20 +-\n .../src/org/spearce/jgit/lib/WindowedFile.java | 43 +\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 40 +-\n .../src/org/spearce/jgit/revwalk/RevSort.java | 5 +-\n .../src/org/spearce/jgit/revwalk/RevWalk.java | 11 +\n .../org/spearce/jgit/revwalk/StartGenerator.java | 14 +-\n .../spearce/jgit/util/CountingOutputStream.java | 89 ++\n 28 files changed, 2258 insertions(+), 73 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackReverseIndexTest.java\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n create mode 100644 org.spearce.jgit.test/tst/pack-huge.idx\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\n"},{"id":"79965","messageId":"1213566349-25395-2-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-1-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 01/20] Fix typo in PackIndexV2","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:30Z","receivedAt":"2008-06-15T21:45:30Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"levelTWo -> levelTwo\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 12 ++++++------\n 1 files changed, 6 insertions(+), 6 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\nindex 9a695ef..ae70f11 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n@@ -184,13 +184,13 @@ class PackIndexV2 extends PackIndex {\n \tprivate class EntriesIteratorV2 extends EntriesIterator {\n \t\tprivate int levelOne;\n \n-\t\tprivate int levelTWo;\n+\t\tprivate int levelTwo;\n \n \t\tpublic MutableEntry next() {\n \t\t\tfor (; levelOne < names.length; levelOne++) {\n-\t\t\t\tif (levelTWo < names[levelOne].length) {\n-\t\t\t\t\tobjectId.fromRaw(names[levelOne], levelTWo);\n-\t\t\t\t\tint arrayIdx = levelTWo / (Constants.OBJECT_ID_LENGTH / 4)\n+\t\t\t\tif (levelTwo < names[levelOne].length) {\n+\t\t\t\t\tobjectId.fromRaw(names[levelOne], levelTwo);\n+\t\t\t\t\tint arrayIdx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4)\n \t\t\t\t\t\t\t* 4;\n \t\t\t\t\tlong offset = NB.decodeUInt32(offset32[levelOne], arrayIdx);\n \t\t\t\t\tif ((offset & IS_O64) != 0) {\n@@ -199,11 +199,11 @@ class PackIndexV2 extends PackIndex {\n \t\t\t\t\t}\n \t\t\t\t\tobjectId.setOffset(offset);\n \n-\t\t\t\t\tlevelTWo += Constants.OBJECT_ID_LENGTH / 4;\n+\t\t\t\t\tlevelTwo += Constants.OBJECT_ID_LENGTH / 4;\n \t\t\t\t\treturnedNumber++;\n \t\t\t\t\treturn objectId;\n \t\t\t\t} else {\n-\t\t\t\t\tlevelTWo = 0;\n+\t\t\t\t\tlevelTwo = 0;\n \t\t\t\t}\n \t\t\t}\n \t\t\tthrow new NoSuchElementException();\n-- \n1.5.5.1\n"},{"id":"79966","messageId":"1213566349-25395-3-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-2-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 02/20] Integer versions of copyRawTo() and fromRaw() in ObjectId","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:31Z","receivedAt":"2008-06-15T21:45:31Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Helper methods in ObjectId and AnyobjectId for int[], overload existing\nbyte[] versions.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/AnyObjectId.java | 16 ++++++++++++\n .../src/org/spearce/jgit/lib/ObjectId.java | 26 ++++++++++++++++++++\n 2 files changed, 42 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/AnyObjectId.java b/org.spearce.jgit/src/org/spearce/jgit/lib/AnyObjectId.java\nindex c348598..871a76d 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/AnyObjectId.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/AnyObjectId.java\n@@ -276,6 +276,22 @@ public abstract class AnyObjectId implements Comparable {\n \t}\n \n \t/**\n+\t * Copy this ObjectId to an int array.\n+\t * \n+\t * @param b\n+\t * the buffer to copy to.\n+\t * @param o\n+\t * the offset within b to write at.\n+\t */\n+\tpublic void copyRawTo(final int[] b, final int o) {\n+\t\tb[o] = w1;\n+\t\tb[o + 1] = w2;\n+\t\tb[o + 2] = w3;\n+\t\tb[o + 3] = w4;\n+\t\tb[o + 4] = w5;\n+\t}\n+\n+\t/**\n \t * Copy this ObjectId to an output writer in raw binary.\n \t * \n \t * @param w\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java\nindex 9688a2e..7646a7b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectId.java\n@@ -168,6 +168,32 @@ public class ObjectId extends AnyObjectId {\n \t}\n \n \t/**\n+\t * Convert an ObjectId from raw binary representation.\n+\t * \n+\t * @param is\n+\t * the raw integers buffer to read from. At least 5 integers must\n+\t * be available within this int array.\n+\t * @return the converted object id.\n+\t */\n+\tpublic static final ObjectId fromRaw(final int[] is) {\n+\t\treturn fromRaw(is, 0);\n+\t}\n+\n+\t/**\n+\t * Convert an ObjectId from raw binary representation.\n+\t * \n+\t * @param is\n+\t * the raw integers buffer to read from. At least 5 integers\n+\t * after p must be available within this int array.\n+\t * @param p\n+\t * position to read the first integer of data from.\n+\t * @return the converted object id.\n+\t */\n+\tpublic static final ObjectId fromRaw(final int[] is, final int p) {\n+\t\treturn new ObjectId(is[p], is[p + 1], is[p + 2], is[p + 3], is[p + 4]);\n+\t}\n+\n+\t/**\n \t * Convert an ObjectId from hex characters (US-ASCII).\n \t * \n \t * @param buf\n-- \n1.5.5.1\n"},{"id":"79970","messageId":"1213566349-25395-4-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-3-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 03/20] Add openObjectInAllPacks() to Repository, exposing packed objects storage","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:32Z","receivedAt":"2008-06-15T21:45:32Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Gives client a way to access specified object from any pack where it is\nstored (this may be useful when an object is stored in more than 1 pack).\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/Repository.java | 42 ++++++++++++++++++++\n 1 files changed, 42 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\nindex 3efe60b..64f93ff 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/Repository.java\n@@ -48,6 +48,7 @@ import java.io.IOException;\n import java.util.ArrayList;\n import java.util.Collection;\n import java.util.HashMap;\n+import java.util.LinkedList;\n import java.util.Map;\n \n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n@@ -292,6 +293,47 @@ public class Repository {\n \t}\n \n \t/**\n+\t * Open object in all packs containing specified object.\n+\t * \n+\t * @param objectId\n+\t * id of object to search for\n+\t * @param curs\n+\t * temporary working space associated with the calling thread.\n+\t * @return collection of loaders for this object, from all packs containing\n+\t * this object\n+\t * @throws IOException\n+\t */\n+\tpublic Collection openObjectInAllPacks(\n+\t\t\tfinal AnyObjectId objectId, final WindowCursor curs)\n+\t\t\tthrows IOException {\n+\t\tCollection result = new LinkedList();\n+\t\topenObjectInAllPacks(objectId, result, curs);\n+\t\treturn result;\n+\t}\n+\n+\t/**\n+\t * Open object in all packs containing specified object.\n+\t * \n+\t * @param objectId\n+\t * id of object to search for\n+\t * @param resultLoaders\n+\t * result collection of loaders for this object, filled with\n+\t * loaders from all packs containing specified object\n+\t * @param curs\n+\t * temporary working space associated with the calling thread.\n+\t * @throws IOException\n+\t */\n+\tvoid openObjectInAllPacks(final AnyObjectId objectId,\n+\t\t\tfinal Collection resultLoaders,\n+\t\t\tfinal WindowCursor curs) throws IOException {\n+\t\tfor (PackFile pack : packs) {\n+\t\t\tfinal PackedObjectLoader loader = pack.get(curs, objectId);\n+\t\t\tif (loader != null)\n+\t\t\t\tresultLoaders.add(loader);\n+\t\t}\n+\t}\n+\n+\t/**\n \t * @param id\n \t * SHA'1 of a blob\n \t * @return an {@link ObjectLoader} for accessing the data of a named blob\n-- \n1.5.5.1\n"},{"id":"79969","messageId":"1213566349-25395-5-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-4-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 04/20] WindowedFile fragments copying: copyToStream()","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:33Z","receivedAt":"2008-06-15T21:45:33Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Method supports direct rewriting of file segment to the specified output\nstream.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/WindowedFile.java | 43 ++++++++++++++++++++\n 1 files changed, 43 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\nindex 323b396..fff8990 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WindowedFile.java\n@@ -40,6 +40,7 @@ package org.spearce.jgit.lib;\n import java.io.EOFException;\n import java.io.File;\n import java.io.IOException;\n+import java.io.OutputStream;\n import java.io.RandomAccessFile;\n import java.nio.MappedByteBuffer;\n import java.nio.channels.FileChannel.MapMode;\n@@ -195,6 +196,48 @@ public class WindowedFile {\n \t\t\tthrow new EOFException();\n \t}\n \n+\t/**\n+\t * Copy the requested number of bytes to the provided output stream.\n+\t *

\n+\t * This routine always reads until either the requested number of bytes has\n+\t * been copied or EOF has been reached.\n+\t *

\n+\t * \n+\t * @param position\n+\t * the starting offset, as measured in bytes from the beginning\n+\t * of this file, to copy from.\n+\t * @param buf\n+\t * temporary buffer to copy bytes into. In case of a big amount\n+\t * of data to copy, size of at least few kB is recommended. It\n+\t * does not need to be of size cnt, however.\n+\t * @param cnt\n+\t * number of bytes to copy. Must not exceed\n+\t * file.length - position.\n+\t * @param out\n+\t * output stream where read data is written out. No buffering is\n+\t * guaranteed by this method.\n+\t * @param curs\n+\t * current cursor for reading data from the file.\n+\t * @throws IOException\n+\t * a necessary window was not found in the window cache and\n+\t * trying to load it in from the operating system failed.\n+\t * @throws EOFException\n+\t * the file ended before cnt bytes could be read.\n+\t */\n+\tpublic void copyToStream(long position, final byte[] buf, long cnt,\n+\t\t\tfinal OutputStream out, final WindowCursor curs)\n+\t\t\tthrows IOException, EOFException {\n+\t\twhile (cnt > 0) {\n+\t\t\tint toRead = (int) Math.min(cnt, buf.length);\n+\t\t\tint read = read(position, buf, 0, toRead, curs);\n+\t\t\tif (read != toRead)\n+\t\t\t\tthrow new EOFException();\n+\t\t\tposition += read;\n+\t\t\tcnt -= read;\n+\t\t\tout.write(buf, 0, read);\n+\t\t}\n+\t}\n+\n \tvoid readCompressed(final long position, final byte[] dstbuf,\n \t\t\tfinal WindowCursor curs) throws IOException, DataFormatException {\n \t\tfinal Inflater inf = InflaterCache.get();\n-- \n1.5.5.1\n"},{"id":"79971","messageId":"1213566349-25395-6-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-5-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:34Z","receivedAt":"2008-06-15T21:45:34Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Let us quickly find ObjectId or next object for specified offset in a\npack, in O(log n) time.\n\nCurrent implementation uses one level (reverse) indexing by an offset.\nHowever, it tries to take small space as possible, by using 2 distinct\narrays for offsets with value < 2^31 (int[]) and those with value > 2^31\n(long[]). Offsets are stored ordered in these 2 arrays. Binary search is\nperformed during requests.\n\nReverse index is constructed from an existing PackIndex instance, by\nlazy initialization in a PackFile instance.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/PackFile.java | 20 +++\n .../src/org/spearce/jgit/lib/PackReverseIndex.java | 179 ++++++++++++++++++++\n 2 files changed, 199 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex 1b2c167..3880966 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -55,6 +55,8 @@ public class PackFile implements Iterable {\n \n \tprivate final PackIndex idx;\n \n+\tprivate PackReverseIndex reverseIdx;\n+\n \t/**\n \t * Construct a reader for an existing, pre-indexed packfile.\n \t * \n@@ -172,6 +174,18 @@ public class PackFile implements Iterable {\n \t\treturn idx.getObjectCount();\n \t}\n \n+\t/**\n+\t * Search for object id with the specified start offset in associated pack\n+\t * (reverse) index.\n+\t * \n+\t * @param offset\n+\t * start offset of object to find\n+\t * @return object id for this offset, or null if no object was found\n+\t */\n+\tObjectId findObjectForOffset(final long offset) {\n+\t\treturn getReverseIdx().findObject(offset);\n+\t}\n+\n \tfinal UnpackedObjectCache.Entry readCache(final long position) {\n \t\treturn UnpackedObjectCache.get(pack, position);\n \t}\n@@ -264,4 +278,10 @@ public class PackFile implements Iterable {\n \t\t\tthrow new IOException(\"Unknown object type \" + typeCode + \".\");\n \t\t}\n \t}\n+\n+\tprivate PackReverseIndex getReverseIdx() {\n+\t\tif (reverseIdx == null)\n+\t\t\treverseIdx = new PackReverseIndex(idx);\n+\t\treturn reverseIdx;\n+\t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\nnew file mode 100644\nindex 0000000..3dede88\n--- /dev/null\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n@@ -0,0 +1,179 @@\n+/*\n+ * Copyright (C) 2008, Marek Zawirski \n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+import java.util.Arrays;\n+import java.util.Comparator;\n+\n+import org.spearce.jgit.errors.CorruptObjectException;\n+import org.spearce.jgit.lib.PackIndex.MutableEntry;\n+\n+/**\n+ *

\n+ * Reverse index for forward pack index. Provides operations based on offset\n+ * instead of object id. Such offset-based reverse lookups are performed in\n+ * O(log n) time.\n+ *

\n+ * \n+ * @see PackIndex\n+ * @see PackFile\n+ */\n+class PackReverseIndex {\n+\t/**\n+\t * (offset31, truly) Offsets accommodating in 31 bits.\n+\t */\n+\tprivate final int offsets32[];\n+\n+\t/**\n+\t * Offsets not accommodating in 31 bits.\n+\t */\n+\tprivate final long offsets64[];\n+\n+\t/**\n+\t * Object ids corresponding to {@link #offsets32} and {@link #offsets64}.\n+\t */\n+\tprivate final int names[];\n+\n+\t/**\n+\t * Create reverse index from straight/forward pack index, by indexing all\n+\t * its entries.\n+\t * \n+\t * @param index\n+\t * forward index - entries to (reverse) index.\n+\t */\n+\tPackReverseIndex(final PackIndex index) {\n+\t\tfinal long count = index.getObjectCount();\n+\t\tif (count > Integer.MAX_VALUE)\n+\t\t\tthrow new IllegalArgumentException(\n+\t\t\t\t\t\"Huge indexes (> 2^31 entries) are not supported by jgit, yet\");\n+\n+\t\tfinal MutableEntry entries[] = new MutableEntry[(int) count];\n+\t\tint i = 0;\n+\t\tint count32 = 0;\n+\t\tfor (MutableEntry me : index) {\n+\t\t\tentries[i++] = me.cloneEntry();\n+\t\t\tif (me.getOffset() <= Integer.MAX_VALUE)\n+\t\t\t\tcount32++;\n+\t\t}\n+\t\tArrays.sort(entries, new Comparator() {\n+\t\t\tpublic int compare(MutableEntry o1, MutableEntry o2) {\n+\t\t\t\treturn Long.signum(o1.getOffset() - o2.getOffset());\n+\t\t\t}\n+\t\t});\n+\n+\t\tnames = new int[entries.length * Constants.OBJECT_ID_LENGTH / 4];\n+\t\toffsets32 = new int[count32];\n+\t\toffsets64 = new long[entries.length - count32];\n+\t\tfor (int j = 0, j32 = 0; j < entries.length; j++) {\n+\t\t\tfinal long offset = entries[j].getOffset();\n+\t\t\tif (offset <= Integer.MAX_VALUE)\n+\t\t\t\toffsets32[j32++] = (int) offset;\n+\t\t\telse\n+\t\t\t\toffsets64[j - j32] = offset;\n+\t\t\tentries[j].copyRawTo(names, j * Constants.OBJECT_ID_LENGTH / 4);\n+\t\t}\n+\t}\n+\n+\t/**\n+\t * Search for object id with the specified start offset in this pack\n+\t * (reverse) index.\n+\t * \n+\t * @param offset\n+\t * start offset of object to find.\n+\t * @return object id for this offset, or null if no object was found.\n+\t */\n+\tObjectId findObject(final long offset) {\n+\t\tif (offset <= Integer.MAX_VALUE) {\n+\t\t\tfinal int i32 = Arrays.binarySearch(offsets32, (int) offset);\n+\t\t\tif (i32 < 0)\n+\t\t\t\treturn null;\n+\t\t\tfinal int iNames = i32 * Constants.OBJECT_ID_LENGTH / 4;\n+\t\t\treturn ObjectId.fromRaw(names, iNames);\n+\t\t} else {\n+\t\t\tfinal int i64 = Arrays.binarySearch(offsets64, offset);\n+\t\t\tif (i64 < 0)\n+\t\t\t\treturn null;\n+\t\t\tfinal int iNames = (i64 + offsets32.length)\n+\t\t\t\t\t* Constants.OBJECT_ID_LENGTH / 4;\n+\t\t\treturn ObjectId.fromRaw(names, iNames);\n+\t\t}\n+\t}\n+\n+\t/**\n+\t * Search for the next offset to the specified offset in this pack (reverse)\n+\t * index.\n+\t * \n+\t * @param offset\n+\t * start offset of previous object (must be valid-existing\n+\t * offset).\n+\t * @param maxOffset\n+\t * maximum offset in a pack (returned when there is no next\n+\t * offset).\n+\t * @return offset of the next object in a pack or maxOffset if provided\n+\t * offset was the last one.\n+\t * @throws CorruptObjectException\n+\t * when there is no object with the provided offset.\n+\t */\n+\tlong findNextOffset(final long offset, final long maxOffset)\n+\t\t\tthrows CorruptObjectException {\n+\t\tif (offset <= Integer.MAX_VALUE) {\n+\t\t\tfinal int i32 = Arrays.binarySearch(offsets32, (int) offset);\n+\t\t\tif (i32 < 0)\n+\t\t\t\tthrow new CorruptObjectException(\n+\t\t\t\t\t\t\"Can't find object in (reverse) pack index for the specified offset \"\n+\t\t\t\t\t\t\t\t+ offset);\n+\n+\t\t\tif (i32 + 1 == offsets32.length) {\n+\t\t\t\tif (offsets64.length > 0)\n+\t\t\t\t\treturn offsets64[0];\n+\t\t\t\treturn maxOffset;\n+\t\t\t}\n+\t\t\treturn offsets32[i32 + 1];\n+\t\t} else {\n+\t\t\tfinal int i64 = Arrays.binarySearch(offsets64, offset);\n+\t\t\tif (i64 < 0)\n+\t\t\t\tthrow new CorruptObjectException(\n+\t\t\t\t\t\t\"Can't find object in (reverse) pack index for the specified offset \"\n+\t\t\t\t\t\t\t\t+ offset);\n+\n+\t\t\tif (i64 + 1 == offsets64.length)\n+\t\t\t\treturn maxOffset;\n+\t\t\treturn offsets64[i64 + 1];\n+\t\t}\n+\t}\n+}\n-- \n1.5.5.1\n"},{"id":"79968","messageId":"1213566349-25395-7-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-6-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 06/20] Tests for PackReverseIndex","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:35Z","receivedAt":"2008-06-15T21:45:35Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Test cases based on new pack index, with big offsets (> 2^31).\nIndex was generated from artificially generated pack (repository).\n\nSigned-off-by: Marek Zawirski \n---\n .../org/spearce/jgit/lib/PackReverseIndexTest.java | 115 ++++++++++++++++++++\n org.spearce.jgit.test/tst/pack-huge.idx | Bin 0 -> 2368 bytes\n 2 files changed, 115 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackReverseIndexTest.java\n create mode 100644 org.spearce.jgit.test/tst/pack-huge.idx\n\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackReverseIndexTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackReverseIndexTest.java\nnew file mode 100644\nindex 0000000..a06c613\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackReverseIndexTest.java\n@@ -0,0 +1,115 @@\n+/*\n+ * Copyright (C) 2008, Marek Zawirski \n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+import java.io.File;\n+\n+import org.spearce.jgit.errors.CorruptObjectException;\n+import org.spearce.jgit.lib.PackIndex.MutableEntry;\n+\n+public class PackReverseIndexTest extends RepositoryTestCase {\n+\n+\tprivate PackIndex idx;\n+\n+\tprivate PackReverseIndex reverseIdx;\n+\n+\t/**\n+\t * Set up tested class instance, test constructor by the way.\n+\t */\n+\tpublic void setUp() throws Exception {\n+\t\tsuper.setUp();\n+\t\t// index with both small (< 2^31) and big offsets \n+\t\tidx = PackIndex.open(new File(new File(\"tst\"),\n+\t\t\t\t\"pack-huge.idx\"));\n+\t\treverseIdx = new PackReverseIndex(idx);\n+\t}\n+\n+\t/**\n+\t * Test findObject() for all index entries.\n+\t */\n+\tpublic void testFindObject() {\n+\t\tfor (MutableEntry me : idx)\n+\t\t\tassertEquals(me.toObjectId(), reverseIdx.findObject(me.getOffset()));\n+\t}\n+\n+\t/**\n+\t * Test findObject() with illegal argument.\n+\t */\n+\tpublic void testFindObjectWrongOffset() {\n+\t\tassertNull(reverseIdx.findObject(0));\n+\t}\n+\n+\t/**\n+\t * Test findNextOffset() for all index entries.\n+\t * \n+\t * @throws CorruptObjectException\n+\t */\n+\tpublic void testFindNextOffset() throws CorruptObjectException {\n+\t\tlong offset = findFirstOffset();\n+\t\tassertTrue(offset > 0);\n+\t\tfor (int i = 0; i < idx.getObjectCount(); i++) {\n+\t\t\tlong newOffset = reverseIdx.findNextOffset(offset, Long.MAX_VALUE);\n+\t\t\tassertTrue(newOffset > offset);\n+\t\t\tif (i == idx.getObjectCount() - 1)\n+\t\t\t\tassertEquals(newOffset, Long.MAX_VALUE);\n+\t\t\telse\n+\t\t\t\tassertEquals(newOffset, idx.findOffset(reverseIdx\n+\t\t\t\t\t\t.findObject(newOffset)));\n+\t\t\toffset = newOffset;\n+\t\t}\n+\t}\n+\n+\t/**\n+\t * Test findNextOffset() with wrong illegal argument as offset.\n+\t */\n+\tpublic void testFindNextOffsetWrongOffset() {\n+\t\ttry {\n+\t\t\treverseIdx.findNextOffset(0, Long.MAX_VALUE);\n+\t\t\tfail(\"findNextOffset() should throw exception\");\n+\t\t} catch (CorruptObjectException x) {\n+\t\t\t// expected\n+\t\t}\n+\t}\n+\n+\tprivate long findFirstOffset() {\n+\t\tlong min = Long.MAX_VALUE;\n+\t\tfor (MutableEntry me : idx)\n+\t\t\tmin = Math.min(min, me.getOffset());\n+\t\treturn min;\n+\t}\n+}\ndiff --git a/org.spearce.jgit.test/tst/pack-huge.idx b/org.spearce.jgit.test/tst/pack-huge.idx\nnew file mode 100644\nindex 0000000000000000000000000000000000000000..0a5bbfb6a6c1453926f7d1ceaa78af494a8b460d\nGIT binary patch\nliteral 2368\nzcmd7TdoTij`pRd#nQY7F!MKA3*`kQJkj)a;Y_-2T@r>6|DcOwP40#\nzYM}m+Fks%gZ=ep&EWm>Gx4?mO3pBx6>t9&M^kUw-u`-=-wd|mdRKhc%z3Bd_j3ZUc\nzWckHw-5QZ>PpzD%uTgKTG1vcev~<^Nuom1z?blMx=#@?B>gP17cQlPL4MPkyd@=~+\nz)|HBnlU&683U;z@2B$a;m(qG$p;5cvhO{_Zg2(gPZVs&H8s(\nz)cEQS)2k&4x3`wT3Gp6Ioh2V$esJzoU&X+SjMv(5nvQk5RCYO-7~DA<{qUL_r=h{h\nz1XoRW6><+q1Zj+SI)zT5GZWpPCdAa9ada={A2yuYT_;EL_G#TZO0X3TbEK`si)C#x\nzFPtzCHmm2Id6gu_a3jqUev!BEtrs3fUOe@#F`q+Z+Zl_Om!Wm6jhS~a10Ki>>ivbmIqh$0`iA9Exi\nzH;hv_7GB)wA@R(Kt16Usrp1y_+*O0hc>A}{9Efccj-HOy2nHle%=!;`GTj2jo>23\nzQ2u%~`v`ddB5aqX@_@VNknzl@6$F{h20Xn(c\nz)%1rrQTfE_N#7wKNt?zS_7&b8I9BFBjwwJgnVBQaz*|R&\nzInieX+@zRYX5-~`UN%&(>5`ODHJOLD$~YobkVMZLE1j0+kr=IEbq=I(Q|f`5Q1C|v\nz;EM3clORO^Q2@NhBF|7>-*-)LBJeMpcl=)J(n&)cvLceIf4uG;b?o!TN\nzo!C9!zXRpjn2H%FpUPah2jvJWfjFO^=k%hJ)8=Yc1(YSsoT~Z#?$l*jF@l0Nla?U^\ni5q#0RPo(gxfy(+nDH~nU#sqlR)DGh}_SPGh&i(_^HDsp%\n\nliteral 0\nHcmV?d00001\n\n-- \n1.5.5.1\n"},{"id":"79972","messageId":"1213566349-25395-8-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-7-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 07/20] Refactor PackIndexV2 - extract binarySearchLevelTwo()","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:36Z","receivedAt":"2008-06-15T21:45:36Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Signed-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 23 +++++++++++++-------\n 1 files changed, 15 insertions(+), 8 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\nindex ae70f11..a0b9827 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n@@ -153,6 +153,20 @@ class PackIndexV2 extends PackIndex {\n \t@Override\n \tlong findOffset(final AnyObjectId objId) {\n \t\tfinal int levelOne = objId.getFirstByte();\n+\t\tfinal int levelTwo = binarySearchLevelTwo(objId, levelOne);\n+\t\tif (levelTwo == -1)\n+\t\t\treturn -1;\n+\t\tfinal long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);\n+\t\tif ((p & IS_O64) != 0)\n+\t\t\treturn NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));\n+\t\treturn p;\n+\t}\n+\n+\tpublic Iterator iterator() {\n+\t\treturn new EntriesIteratorV2();\n+\t}\n+\n+\tprivate int binarySearchLevelTwo(final AnyObjectId objId, final int levelOne) {\n \t\tfinal int[] data = names[levelOne];\n \t\tint high = offset32[levelOne].length >> 2;\n \t\tif (high == 0)\n@@ -167,20 +181,13 @@ class PackIndexV2 extends PackIndex {\n \t\t\tif (cmp < 0)\n \t\t\t\thigh = mid;\n \t\t\telse if (cmp == 0) {\n-\t\t\t\tfinal long p = NB.decodeUInt32(offset32[levelOne], mid4);\n-\t\t\t\tif ((p & IS_O64) != 0)\n-\t\t\t\t\treturn NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));\n-\t\t\t\treturn p;\n+\t\t\t\treturn mid;\n \t\t\t} else\n \t\t\t\tlow = mid + 1;\n \t\t} while (low < high);\n \t\treturn -1;\n \t}\n \n-\tpublic Iterator iterator() {\n-\t\treturn new EntriesIteratorV2();\n-\t}\n-\n \tprivate class EntriesIteratorV2 extends EntriesIterator {\n \t\tprivate int levelOne;\n \n-- \n1.5.5.1\n"},{"id":"79975","messageId":"1213566349-25395-9-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-8-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 08/20] CRC32 support for PackIndex","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:37Z","receivedAt":"2008-06-15T21:45:37Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Add findCRC32() and hasCRC32Support() methods in PackIndex with\nimplementation for index v2.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/PackIndex.java | 23 ++++++++++++\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 10 +++++\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 38 ++++++++++++-------\n 3 files changed, 57 insertions(+), 14 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\nindex 3935d4f..e34cd36 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\n@@ -44,6 +44,7 @@ import java.io.FileNotFoundException;\n import java.io.IOException;\n import java.util.Iterator;\n \n+import org.spearce.jgit.errors.MissingObjectException;\n import org.spearce.jgit.util.NB;\n \n /**\n@@ -151,6 +152,28 @@ public abstract class PackIndex implements Iterable {\n \tabstract long findOffset(AnyObjectId objId);\n \n \t/**\n+\t * Retrieve stored CRC32 checksum of the requested object raw-data\n+\t * (including header).\n+\t * \n+\t * @param objId\n+\t * id of object to look for\n+\t * @return CRC32 checksum of specified object (at 32 less significant bits)\n+\t * @throws MissingObjectException\n+\t * when requested ObjectId was not found in this index\n+\t * @throws UnsupportedOperationException\n+\t * when this index doesn't support CRC32 checksum\n+\t */\n+\tabstract long findCRC32(AnyObjectId objId) throws MissingObjectException,\n+\t\t\tUnsupportedOperationException;\n+\n+\t/**\n+\t * Check whether this index supports (has) CRC32 checksums for objects.\n+\t * \n+\t * @return true if CRC32 is stored, false otherwise\n+\t */\n+\tabstract boolean hasCRC32Support();\n+\n+\t/**\n \t * Represent mutable entry of pack index consisting of object id and offset\n \t * in pack (both mutable).\n \t * \ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\nindex b8d9de3..86b939a 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n@@ -107,6 +107,16 @@ class PackIndexV1 extends PackIndex {\n \t\treturn -1;\n \t}\n \n+\t@Override\n+\tlong findCRC32(AnyObjectId objId) {\n+\t\tthrow new UnsupportedOperationException();\n+\t}\n+\n+\t@Override\n+\tboolean hasCRC32Support() {\n+\t\treturn false;\n+\t}\n+\n \tpublic Iterator iterator() {\n \t\treturn new IndexV1Iterator();\n \t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\nindex a0b9827..fc1f08b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n@@ -37,12 +37,12 @@\n \n package org.spearce.jgit.lib;\n \n-import java.io.EOFException;\n import java.io.IOException;\n import java.io.InputStream;\n import java.util.Iterator;\n import java.util.NoSuchElementException;\n \n+import org.spearce.jgit.errors.MissingObjectException;\n import org.spearce.jgit.util.NB;\n \n /** Support for the pack index v2 format. */\n@@ -63,6 +63,9 @@ class PackIndexV2 extends PackIndex {\n \t/** 256 arrays of the 32 bit offset data, matching {@link #names}. */\n \tprivate byte[][] offset32;\n \n+\t/** 256 arrays of the CRC-32 of objects, matching {@link #names}. */\n+\tprivate byte[][] crc32;\n+\n \t/** 64 bit offset table. */\n \tprivate byte[] offset64;\n \n@@ -76,6 +79,7 @@ class PackIndexV2 extends PackIndex {\n \n \t\tnames = new int[FANOUT][];\n \t\toffset32 = new byte[FANOUT][];\n+\t\tcrc32 = new byte[FANOUT][];\n \n \t\t// Object name table. The size we can permit per fan-out bucket\n \t\t// is limited to Java's 2 GB per byte array limitation. That is\n@@ -91,6 +95,7 @@ class PackIndexV2 extends PackIndex {\n \t\t\tif (bucketCnt == 0) {\n \t\t\t\tnames[k] = NO_INTS;\n \t\t\t\toffset32[k] = NO_BYTES;\n+\t\t\t\tcrc32[k] = NO_BYTES;\n \t\t\t\tcontinue;\n \t\t\t}\n \n@@ -107,11 +112,12 @@ class PackIndexV2 extends PackIndex {\n \n \t\t\tnames[k] = bin;\n \t\t\toffset32[k] = new byte[(int) (bucketCnt * 4)];\n+\t\t\tcrc32[k] = new byte[(int) (bucketCnt * 4)];\n \t\t}\n \n-\t\t// CRC32 table. Currently unused.\n-\t\t//\n-\t\tskipFully(fd, objectCnt * 4);\n+\t\t// CRC32 table.\n+\t\tfor (int k = 0; k < FANOUT; k++)\n+\t\t\tNB.readFully(fd, crc32[k], 0, crc32[k].length);\n \n \t\t// 32 bit offset table. Any entries with the most significant bit\n \t\t// set require a 64 bit offset entry in another table.\n@@ -135,16 +141,6 @@ class PackIndexV2 extends PackIndex {\n \t\t}\n \t}\n \n-\tprivate static void skipFully(final InputStream fd, long toSkip)\n-\t\t\tthrows IOException {\n-\t\twhile (toSkip > 0) {\n-\t\t\tfinal long r = fd.skip(toSkip);\n-\t\t\tif (r <= 0)\n-\t\t\t\tthrow new EOFException(\"Cannot skip index section.\");\n-\t\t\ttoSkip -= r;\n-\t\t}\n-\t}\n-\n \t@Override\n \tlong getObjectCount() {\n \t\treturn objectCnt;\n@@ -162,6 +158,20 @@ class PackIndexV2 extends PackIndex {\n \t\treturn p;\n \t}\n \n+\t@Override\n+\tlong findCRC32(AnyObjectId objId) throws MissingObjectException {\n+\t\tfinal int levelOne = objId.getFirstByte();\n+\t\tfinal int levelTwo = binarySearchLevelTwo(objId, levelOne);\n+\t\tif (levelTwo == -1)\n+\t\t\tthrow new MissingObjectException(objId.copy(), \"unknown\");\n+\t\treturn NB.decodeUInt32(crc32[levelOne], levelTwo << 2);\n+\t}\n+\n+\t@Override\n+\tboolean hasCRC32Support() {\n+\t\treturn true;\n+\t}\n+\n \tpublic Iterator iterator() {\n \t\treturn new EntriesIteratorV2();\n \t}\n-- \n1.5.5.1\n"},{"id":"79974","messageId":"1213566349-25395-10-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-9-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 09/20] CRC32 PackIndex tests","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:38Z","receivedAt":"2008-06-15T21:45:38Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Signed-off-by: Marek Zawirski \n---\n .../tst/org/spearce/jgit/lib/PackIndexTest.java | 10 ++++++\n .../tst/org/spearce/jgit/lib/PackIndexV1Test.java | 19 ++++++++++++\n .../tst/org/spearce/jgit/lib/PackIndexV2Test.java | 30 ++++++++++++++++++++\n 3 files changed, 59 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java\nindex c682153..fd7b646 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexTest.java\n@@ -41,6 +41,7 @@ import java.io.File;\n import java.util.Iterator;\n import java.util.NoSuchElementException;\n \n+import org.spearce.jgit.errors.MissingObjectException;\n import org.spearce.jgit.lib.PackIndex.MutableEntry;\n \n public abstract class PackIndexTest extends RepositoryTestCase {\n@@ -70,6 +71,15 @@ public abstract class PackIndexTest extends RepositoryTestCase {\n \tpublic abstract File getFileForPackdf2982f28();\n \n \t/**\n+\t * Verify CRC32 support.\n+\t * \n+\t * @throws MissingObjectException\n+\t * @throws UnsupportedOperationException\n+\t */\n+\tpublic abstract void testCRC32() throws MissingObjectException,\n+\t\t\tUnsupportedOperationException;\n+\n+\t/**\n \t * Test contracts of Iterator methods and this implementation remove()\n \t * limitations.\n \t */\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV1Test.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV1Test.java\nindex dda3ef4..bb9e83e 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV1Test.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV1Test.java\n@@ -39,6 +39,8 @@ package org.spearce.jgit.lib;\n \n import java.io.File;\n \n+import org.spearce.jgit.errors.MissingObjectException;\n+\n public class PackIndexV1Test extends PackIndexTest {\n \t@Override\n \tpublic File getFileForPack34be9032() {\n@@ -51,4 +53,21 @@ public class PackIndexV1Test extends PackIndexTest {\n \t\treturn new File(new File(\"tst\"),\n \t\t\t\t\"pack-df2982f284bbabb6bdb59ee3fcc6eb0983e20371.idx\");\n \t}\n+\n+\t/**\n+\t * Verify CRC32 - V1 should not index anything.\n+\t * \n+\t * @throws MissingObjectException\n+\t */\n+\t@Override\n+\tpublic void testCRC32() throws MissingObjectException {\n+\t\tassertFalse(smallIdx.hasCRC32Support());\n+\t\ttry {\n+\t\t\tsmallIdx.findCRC32(ObjectId\n+\t\t\t\t\t.fromString(\"4b825dc642cb6eb9a060e54bf8d69288fbee4904\"));\n+\t\t\tfail(\"index V1 shouldn't support CRC\");\n+\t\t} catch (UnsupportedOperationException x) {\n+\t\t\t// expected\n+\t\t}\n+\t}\n }\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV2Test.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV2Test.java\nindex 8267e48..b21a7e9 100644\n--- a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV2Test.java\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackIndexV2Test.java\n@@ -39,6 +39,8 @@ package org.spearce.jgit.lib;\n \n import java.io.File;\n \n+import org.spearce.jgit.errors.MissingObjectException;\n+\n public class PackIndexV2Test extends PackIndexTest {\n \t@Override\n \tpublic File getFileForPack34be9032() {\n@@ -51,4 +53,32 @@ public class PackIndexV2Test extends PackIndexTest {\n \t\treturn new File(new File(\"tst\"),\n \t\t\t\t\"pack-df2982f284bbabb6bdb59ee3fcc6eb0983e20371.idxV2\");\n \t}\n+\n+\t/**\n+\t * Verify CRC32 indexing.\n+\t * \n+\t * @throws UnsupportedOperationException\n+\t * @throws MissingObjectException\n+\t */\n+\t@Override\n+\tpublic void testCRC32() throws MissingObjectException,\n+\t\t\tUnsupportedOperationException {\n+\t\tassertTrue(smallIdx.hasCRC32Support());\n+\t\tassertEquals(0x00000000C2B64258l, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"4b825dc642cb6eb9a060e54bf8d69288fbee4904\")));\n+\t\tassertEquals(0x0000000072AD57C2l, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"540a36d136cf413e4b064c2b0e0a4db60f77feab\")));\n+\t\tassertEquals(0x00000000FF10A479l, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"5b6e7c66c276e7610d4a73c70ec1a1f7c1003259\")));\n+\t\tassertEquals(0x0000000034B27DDCl, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"6ff87c4664981e4397625791c8ea3bbb5f2279a3\")));\n+\t\tassertEquals(0x000000004743F1E4l, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\")));\n+\t\tassertEquals(0x00000000640B358Bl, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"902d5476fa249b7abc9d84c611577a81381f0327\")));\n+\t\tassertEquals(0x000000002A17CB5El, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"aabf2ffaec9b497f0950352b3e582d73035c2035\")));\n+\t\tassertEquals(0x000000000B3B5BA6l, smallIdx.findCRC32(ObjectId\n+\t\t\t\t.fromString(\"c59759f143fb1fe21c197981df75a7ee00290799\")));\n+\t}\n }\n-- \n1.5.5.1\n"},{"id":"79973","messageId":"1213566349-25395-11-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-10-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 10/20] Format PackedObjectLoader class","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:39Z","receivedAt":"2008-06-15T21:45:39Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Signed-off-by: Marek Zawirski \n---\n .../org/spearce/jgit/lib/PackedObjectLoader.java | 3 +--\n 1 files changed, 1 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\nindex 743484e..43d43e6 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n@@ -41,8 +41,7 @@ package org.spearce.jgit.lib;\n import java.io.IOException;\n \n /**\n- * Base class for a set of object loader classes for packed\n- * objects.\n+ * Base class for a set of object loader classes for packed objects.\n */\n abstract class PackedObjectLoader extends ObjectLoader {\n \tprotected final PackFile pack;\n-- \n1.5.5.1\n"},{"id":"79976","messageId":"1213566349-25395-12-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-11-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 11/20] Format UnpackedObjectLoader class","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:40Z","receivedAt":"2008-06-15T21:45:40Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Signed-off-by: Marek Zawirski \n---\n .../org/spearce/jgit/lib/UnpackedObjectLoader.java | 16 ++++++++++------\n 1 files changed, 10 insertions(+), 6 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\nindex 4e95387..a5c484b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\n@@ -49,8 +49,7 @@ import org.spearce.jgit.util.MutableInteger;\n import org.spearce.jgit.util.RawParseUtils;\n \n /**\n- * Loose object loader. This class loads an object not\n- * stored in a pack.\n+ * Loose object loader. This class loads an object not stored in a pack.\n */\n public class UnpackedObjectLoader extends ObjectLoader {\n \tprivate final int objectType;\n@@ -61,8 +60,11 @@ public class UnpackedObjectLoader extends ObjectLoader {\n \n \t/**\n \t * Construct an ObjectLoader for the specified SHA-1\n-\t * @param db repository\n-\t * @param id SHA-1\n+\t * \n+\t * @param db\n+\t * repository\n+\t * @param id\n+\t * SHA-1\n \t * @throws IOException\n \t */\n \tpublic UnpackedObjectLoader(final Repository db, final ObjectId id)\n@@ -94,11 +96,13 @@ public class UnpackedObjectLoader extends ObjectLoader {\n \t * The compressed data supplied does not match the format for a\n \t * valid loose object.\n \t */\n-\tpublic UnpackedObjectLoader(final byte[] compressed) throws CorruptObjectException {\n+\tpublic UnpackedObjectLoader(final byte[] compressed)\n+\t\t\tthrows CorruptObjectException {\n \t\tthis(compressed, null);\n \t}\n \n-\tprivate UnpackedObjectLoader(final byte[] compressed, final ObjectId id) throws CorruptObjectException {\n+\tprivate UnpackedObjectLoader(final byte[] compressed, final ObjectId id)\n+\t\t\tthrows CorruptObjectException {\n \t\tsetId(id);\n \n \t\t// Try to determine if this is a legacy format loose object or\n-- \n1.5.5.1\n"},{"id":"79977","messageId":"1213566349-25395-13-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-12-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 12/20] Format DeltaOfsPackedObjectLoader class","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:41Z","receivedAt":"2008-06-15T21:45:41Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Signed-off-by: Marek Zawirski \n---\n .../jgit/lib/DeltaOfsPackedObjectLoader.java | 5 ++---\n 1 files changed, 2 insertions(+), 3 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java\nindex 75fda45..edbeef9 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java\n@@ -44,9 +44,8 @@ import java.io.IOException;\n class DeltaOfsPackedObjectLoader extends DeltaPackedObjectLoader {\n \tprivate final long deltaBase;\n \n-\tDeltaOfsPackedObjectLoader(final WindowCursor curs,\n-\t\t\tfinal PackFile pr, final long offset,\n-\t\t\tfinal int deltaSz, final long base) {\n+\tDeltaOfsPackedObjectLoader(final WindowCursor curs, final PackFile pr,\n+\t\t\tfinal long offset, final int deltaSz, final long base) {\n \t\tsuper(curs, pr, offset, deltaSz);\n \t\tdeltaBase = base;\n \t}\n-- \n1.5.5.1\n"},{"id":"79978","messageId":"1213566349-25395-14-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-13-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 13/20] Raw-data operations in ObjectLoaders and PackFile","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:42Z","receivedAt":"2008-06-15T21:45:42Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Expose operations on raw-data (storage specific) in ObjectLoaders and\nsubclasses:\n- getRawType() giving access to the object type at PackFile header level\n- getRawSize() giving access to the size of this object at PackFile\n header level\n- getDeltaBase() determining delta base if applicable\n- copyRawData() allowing direct copying raw (compressed or delitified)\n object data if possible\n+ helper fields, methods in ObjectLoaders\n+ helper methods/core engine in PackFile\n\nNew operations do not introduce any signifficant performance overhead\nwhen not used.\n\nSigned-off-by: Marek Zawirski \n---\n .../jgit/lib/DeltaOfsPackedObjectLoader.java | 21 ++++++-\n .../spearce/jgit/lib/DeltaPackedObjectLoader.java | 9 ++-\n .../jgit/lib/DeltaRefPackedObjectLoader.java | 15 ++++-\n .../src/org/spearce/jgit/lib/ObjectLoader.java | 24 +++++++\n .../src/org/spearce/jgit/lib/PackFile.java | 65 ++++++++++++++++++-\n .../org/spearce/jgit/lib/PackedObjectLoader.java | 44 +++++++++++++-\n .../org/spearce/jgit/lib/UnpackedObjectLoader.java | 10 +++\n .../spearce/jgit/lib/WholePackedObjectLoader.java | 20 ++++++-\n 8 files changed, 194 insertions(+), 14 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java\nindex edbeef9..5c9fb00 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaOfsPackedObjectLoader.java\n@@ -40,17 +40,34 @@ package org.spearce.jgit.lib;\n \n import java.io.IOException;\n \n+import org.spearce.jgit.errors.CorruptObjectException;\n+\n /** Reads a deltified object which uses an offset to find its base. */\n class DeltaOfsPackedObjectLoader extends DeltaPackedObjectLoader {\n \tprivate final long deltaBase;\n \n \tDeltaOfsPackedObjectLoader(final WindowCursor curs, final PackFile pr,\n-\t\t\tfinal long offset, final int deltaSz, final long base) {\n-\t\tsuper(curs, pr, offset, deltaSz);\n+\t\t\tfinal long dataOffset, final long objectOffset, final int deltaSz,\n+\t\t\tfinal long base) {\n+\t\tsuper(curs, pr, dataOffset, objectOffset, deltaSz);\n \t\tdeltaBase = base;\n \t}\n \n \tprotected PackedObjectLoader getBaseLoader() throws IOException {\n \t\treturn pack.resolveBase(curs, deltaBase);\n \t}\n+\n+\t@Override\n+\tpublic int getRawType() {\n+\t\treturn Constants.OBJ_OFS_DELTA;\n+\t}\n+\n+\t@Override\n+\tpublic ObjectId getDeltaBase() throws IOException {\n+\t\tfinal ObjectId id = pack.findObjectForOffset(deltaBase);\n+\t\tif (id == null)\n+\t\t\tthrow new CorruptObjectException(\n+\t\t\t\t\t\"Offset-written delta base for object not found in a pack\");\n+\t\treturn id;\n+\t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\nindex 4813572..e73f8e5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaPackedObjectLoader.java\n@@ -50,8 +50,8 @@ abstract class DeltaPackedObjectLoader extends PackedObjectLoader {\n \tprivate final int deltaSize;\n \n \tDeltaPackedObjectLoader(final WindowCursor curs, final PackFile pr,\n-\t\t\tfinal long offset, final int deltaSz) {\n-\t\tsuper(curs, pr, offset);\n+\t\t\tfinal long dataOffset, final long objectOffset, final int deltaSz) {\n+\t\tsuper(curs, pr, dataOffset, objectOffset);\n \t\tobjectType = -1;\n \t\tdeltaSize = deltaSz;\n \t}\n@@ -98,6 +98,11 @@ abstract class DeltaPackedObjectLoader extends PackedObjectLoader {\n \t\t}\n \t}\n \n+\t@Override\n+\tpublic long getRawSize() {\n+\t\treturn deltaSize;\n+\t}\n+\n \t/**\n \t * @return the object loader for the base object\n \t * @throws IOException\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaRefPackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaRefPackedObjectLoader.java\nindex fb87abc..042d3a8 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaRefPackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/DeltaRefPackedObjectLoader.java\n@@ -47,8 +47,9 @@ class DeltaRefPackedObjectLoader extends DeltaPackedObjectLoader {\n \tprivate final ObjectId deltaBase;\n \n \tDeltaRefPackedObjectLoader(final WindowCursor curs, final PackFile pr,\n-\t\t\tfinal long offset, final int deltaSz, final ObjectId base) {\n-\t\tsuper(curs, pr, offset, deltaSz);\n+\t\t\tfinal long dataOffset, final long objectOffset, final int deltaSz,\n+\t\t\tfinal ObjectId base) {\n+\t\tsuper(curs, pr, dataOffset, objectOffset, deltaSz);\n \t\tdeltaBase = base;\n \t}\n \n@@ -58,4 +59,14 @@ class DeltaRefPackedObjectLoader extends DeltaPackedObjectLoader {\n \t\t\tthrow new MissingObjectException(deltaBase, \"delta base\");\n \t\treturn or;\n \t}\n+\n+\t@Override\n+\tpublic int getRawType() throws IOException {\n+\t\treturn Constants.OBJ_REF_DELTA;\n+\t}\n+\n+\t@Override\n+\tpublic ObjectId getDeltaBase() throws IOException {\n+\t\treturn deltaBase;\n+\t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java\nindex 3a96dd1..5282491 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/ObjectLoader.java\n@@ -66,6 +66,13 @@ public abstract class ObjectLoader {\n \t}\n \n \t/**\n+\t * @return true if id of loaded object is already known, false otherwise.\n+\t */\n+\tprotected boolean hasComputedId() {\n+\t\treturn objectId != null;\n+\t}\n+\n+\t/**\n \t * Set the SHA-1 id of the object handled by this loader\n \t * \n \t * @param id\n@@ -113,4 +120,21 @@ public abstract class ObjectLoader {\n \t * the object cannot be read.\n \t */\n \tpublic abstract byte[] getCachedBytes() throws IOException;\n+\n+\t/**\n+\t * @return raw object type from object header, as stored in storage (pack,\n+\t * loose file). This may be different from {@link #getType()} result\n+\t * for packs (see {@link Constants}).\n+\t * @throws IOException\n+\t * when type cannot be read from the object header.\n+\t */\n+\tpublic abstract int getRawType() throws IOException;\n+\n+\t/**\n+\t * @return raw size of object from object header (pack, loose file).\n+\t * Interpretation of this value depends on {@link #getRawType()}.\n+\t * @throws IOException\n+\t * when raw size cannot be read from the object header.\n+\t */\n+\tpublic abstract long getRawSize() throws IOException;\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\nindex 3880966..9992615 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java\n@@ -38,11 +38,16 @@\n \n package org.spearce.jgit.lib;\n \n+import java.io.EOFException;\n import java.io.File;\n import java.io.IOException;\n+import java.io.OutputStream;\n import java.util.Iterator;\n+import java.util.zip.CRC32;\n+import java.util.zip.CheckedOutputStream;\n import java.util.zip.DataFormatException;\n \n+import org.spearce.jgit.errors.CorruptObjectException;\n import org.spearce.jgit.util.NB;\n \n /**\n@@ -201,6 +206,52 @@ public class PackFile implements Iterable {\n \t\treturn dstbuf;\n \t}\n \n+\tfinal void copyRawData(final PackedObjectLoader loader,\n+\t\t\tfinal OutputStream out, final byte buf[]) throws IOException {\n+\t\tfinal long objectOffset = loader.objectOffset;\n+\t\tfinal long dataOffset = loader.dataOffset;\n+\t\tfinal int cnt = (int) (findEndOffset(objectOffset) - dataOffset);\n+\t\tfinal WindowCursor curs = loader.curs;\n+\n+\t\tif (idx.hasCRC32Support()) {\n+\t\t\tfinal CRC32 crc = new CRC32();\n+\t\t\tint headerCnt = (int) (dataOffset - objectOffset);\n+\t\t\twhile (headerCnt > 0) {\n+\t\t\t\tint toRead = Math.min(headerCnt, buf.length);\n+\t\t\t\tint read = pack.read(objectOffset, buf, 0, toRead, curs);\n+\t\t\t\tif (read != toRead)\n+\t\t\t\t\tthrow new EOFException();\n+\t\t\t\tcrc.update(buf, 0, read);\n+\t\t\t\theaderCnt -= toRead;\n+\t\t\t}\n+\t\t\tfinal CheckedOutputStream crcOut = new CheckedOutputStream(out, crc);\n+\t\t\tpack.copyToStream(dataOffset, buf, cnt, crcOut, curs);\n+\t\t\tfinal long computed = crc.getValue();\n+\n+\t\t\tObjectId id;\n+\t\t\tif (loader.hasComputedId())\n+\t\t\t\tid = loader.getId();\n+\t\t\telse\n+\t\t\t\tid = findObjectForOffset(objectOffset);\n+\t\t\tfinal long expected = idx.findCRC32(id);\n+\t\t\tif (computed != expected)\n+\t\t\t\tthrow new CorruptObjectException(id,\n+\t\t\t\t\t\t\"Possible data corruption - CRC32 of raw pack data (object offset \"\n+\t\t\t\t\t\t\t\t+ objectOffset\n+\t\t\t\t\t\t\t\t+ \") mismatch CRC32 from pack index\");\n+\t\t} else {\n+\t\t\tpack.copyToStream(dataOffset, buf, cnt, out, curs);\n+\n+\t\t\t// read to verify against Adler32 zlib checksum\n+\t\t\tloader.getCachedBytes();\n+\t\t}\n+\t}\n+\t\n+\tboolean supportsFastCopyRawData() {\n+\t\treturn idx.hasCRC32Support();\n+\t}\n+\n+\n \tprivate void readPackHeader() throws IOException {\n \t\tfinal WindowCursor curs = new WindowCursor();\n \t\tlong position = 0;\n@@ -252,8 +303,8 @@ public class PackFile implements Iterable {\n \t\tcase Constants.OBJ_TREE:\n \t\tcase Constants.OBJ_BLOB:\n \t\tcase Constants.OBJ_TAG:\n-\t\t\treturn new WholePackedObjectLoader(curs, this, pos, typeCode,\n-\t\t\t\t\t(int) dataSize);\n+\t\t\treturn new WholePackedObjectLoader(curs, this, pos, objOffset,\n+\t\t\t\t\ttypeCode, (int) dataSize);\n \n \t\tcase Constants.OBJ_OFS_DELTA: {\n \t\t\tpack.readFully(pos, ib, curs);\n@@ -267,18 +318,24 @@ public class PackFile implements Iterable {\n \t\t\t\tofs += (c & 127);\n \t\t\t}\n \t\t\treturn new DeltaOfsPackedObjectLoader(curs, this, pos + p,\n-\t\t\t\t\t(int) dataSize, objOffset - ofs);\n+\t\t\t\t\tobjOffset, (int) dataSize, objOffset - ofs);\n \t\t}\n \t\tcase Constants.OBJ_REF_DELTA: {\n \t\t\tpack.readFully(pos, ib, curs);\n \t\t\treturn new DeltaRefPackedObjectLoader(curs, this, pos + ib.length,\n-\t\t\t\t\t(int) dataSize, ObjectId.fromRaw(ib));\n+\t\t\t\t\tobjOffset, (int) dataSize, ObjectId.fromRaw(ib));\n \t\t}\n \t\tdefault:\n \t\t\tthrow new IOException(\"Unknown object type \" + typeCode + \".\");\n \t\t}\n \t}\n \n+\tprivate long findEndOffset(final long startOffset)\n+\t\t\tthrows CorruptObjectException {\n+\t\tfinal long maxOffset = pack.length() - Constants.OBJECT_ID_LENGTH;\n+\t\treturn getReverseIdx().findNextOffset(startOffset, maxOffset);\n+\t}\n+\n \tprivate PackReverseIndex getReverseIdx() {\n \t\tif (reverseIdx == null)\n \t\t\treverseIdx = new PackReverseIndex(idx);\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\nindex 43d43e6..b433609 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackedObjectLoader.java\n@@ -39,6 +39,7 @@\n package org.spearce.jgit.lib;\n \n import java.io.IOException;\n+import java.io.OutputStream;\n \n /**\n * Base class for a set of object loader classes for packed objects.\n@@ -50,15 +51,18 @@ abstract class PackedObjectLoader extends ObjectLoader {\n \n \tprotected final long dataOffset;\n \n+\tprotected final long objectOffset;\n+\n \tprotected int objectType;\n \n \tprotected int objectSize;\n \n \tPackedObjectLoader(final WindowCursor c, final PackFile pr,\n-\t\t\tfinal long offset) {\n+\t\t\tfinal long dataOffset, final long objectOffset) {\n \t\tcurs = c;\n \t\tpack = pr;\n-\t\tdataOffset = offset;\n+\t\tthis.dataOffset = dataOffset;\n+\t\tthis.objectOffset = objectOffset;\n \t}\n \n \tpublic int getType() throws IOException {\n@@ -82,4 +86,40 @@ abstract class PackedObjectLoader extends ObjectLoader {\n \t\tSystem.arraycopy(data, 0, copy, 0, data.length);\n \t\treturn data;\n \t}\n+\n+\t/**\n+\t * Copy raw object representation from storage to provided output stream.\n+\t *

\n+\t * Copied data doesn't include object header. User must provide temporary\n+\t * buffer used during copying by underlying I/O layer.\n+\t *

\n+\t * \n+\t * @param out\n+\t * output stream when data is copied. No buffering is guaranteed.\n+\t * @param buf\n+\t * temporary buffer used during copying. Recommended size is at\n+\t * least few kB.\n+\t * @throws IOException\n+\t * when the object cannot be read.\n+\t */\n+\tpublic void copyRawData(OutputStream out, byte buf[]) throws IOException {\n+\t\tpack.copyRawData(this, out, buf);\n+\t}\n+\n+\t/**\n+\t * @return true if this loader is capable of fast raw-data copying basing on\n+\t * compressed data checksum; false if raw-data copying needs\n+\t * uncompressing and compressing data\n+\t */\n+\tpublic boolean supportsFastCopyRawData() {\n+\t\treturn pack.supportsFastCopyRawData();\n+\t}\n+\n+\t/**\n+\t * @return id of delta base object for this object representation. null if\n+\t * object is not stored as delta.\n+\t * @throws IOException\n+\t * when delta base cannot read.\n+\t */\n+\tpublic abstract ObjectId getDeltaBase() throws IOException;\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\nindex a5c484b..65072f0 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/UnpackedObjectLoader.java\n@@ -208,4 +208,14 @@ public class UnpackedObjectLoader extends ObjectLoader {\n \tpublic byte[] getCachedBytes() throws IOException {\n \t\treturn bytes;\n \t}\n+\n+\t@Override\n+\tpublic int getRawType() {\n+\t\treturn objectType;\n+\t}\n+\n+\t@Override\n+\tpublic long getRawSize() {\n+\t\treturn objectSize;\n+\t}\n }\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java b/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java\nindex e54fba6..7185df5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/WholePackedObjectLoader.java\n@@ -47,8 +47,9 @@ class WholePackedObjectLoader extends PackedObjectLoader {\n \tprivate static final int OBJ_COMMIT = Constants.OBJ_COMMIT;\n \n \tWholePackedObjectLoader(final WindowCursor curs, final PackFile pr,\n-\t\t\tfinal long offset, final int type, final int size) {\n-\t\tsuper(curs, pr, offset);\n+\t\t\tfinal long dataOffset, final long objectOffset, final int type,\n+\t\t\tfinal int size) {\n+\t\tsuper(curs, pr, dataOffset, objectOffset);\n \t\tobjectType = type;\n \t\tobjectSize = size;\n \t}\n@@ -76,4 +77,19 @@ class WholePackedObjectLoader extends PackedObjectLoader {\n \t\t\tthrow coe;\n \t\t}\n \t}\n+\n+\t@Override\n+\tpublic int getRawType() {\n+\t\treturn objectType;\n+\t}\n+\n+\t@Override\n+\tpublic long getRawSize() {\n+\t\treturn objectSize;\n+\t}\n+\n+\t@Override\n+\tpublic ObjectId getDeltaBase() {\n+\t\treturn null;\n+\t}\n }\n-- \n1.5.5.1\n"},{"id":"79980","messageId":"1213566349-25395-15-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-14-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 14/20] Add hasRevSort() in RevWalk for faster sorting strategy checking","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:43Z","receivedAt":"2008-06-15T21:45:43Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Direct calls to this method let us avoid unnecessary cloning of\ngetRevSort() output just for checking existance of some strategy.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/revwalk/RevWalk.java | 11 +++++++++++\n 1 files changed, 11 insertions(+), 0 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java\nindex 4cb75ec..fc757a5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevWalk.java\n@@ -389,6 +389,17 @@ public class RevWalk implements Iterable {\n \t}\n \n \t/**\n+\t * Check whether the provided sorting strategy is enabled.\n+\t * \n+\t * @param sort\n+\t * a sorting strategy to look for.\n+\t * @return true if this strategy is enabled, false otherwise\n+\t */\n+\tpublic boolean hasRevSort(RevSort sort) {\n+\t\treturn sorting.contains(sort);\n+\t}\n+\n+\t/**\n \t * Select a single sorting strategy for the returned commits.\n \t *

\n \t * Disables all sorting strategies, then enables only the single strategy\n-- \n1.5.5.1\n"},{"id":"79982","messageId":"1213566349-25395-16-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-15-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 15/20] Refactor getRevSort() calls to hasRevSort()","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:44Z","receivedAt":"2008-06-15T21:45:44Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"It is not signifficant performance improvement, just avoids creation of\nfew unnecessary objects.\nHowever, it improves encapsulation and keeps existing RevSort checking\ncode consistent with further use of hasRevSort().\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 2 +-\n .../org/spearce/jgit/revwalk/StartGenerator.java | 14 +++++++-------\n 2 files changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\nindex a36c1cc..68ed861 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n@@ -198,7 +198,7 @@ public class ObjectWalk extends RevWalk {\n \t\t\t\treturn null;\n \t\t\tif ((r.flags & UNINTERESTING) != 0) {\n \t\t\t\tmarkTreeUninteresting(r.getTree());\n-\t\t\t\tif (getRevSort().contains(RevSort.BOUNDARY))\n+\t\t\t\tif (hasRevSort(RevSort.BOUNDARY))\n \t\t\t\t\treturn r;\n \t\t\t\tcontinue;\n \t\t\t}\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java\nindex debd168..7ddcd3c 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/StartGenerator.java\n@@ -38,7 +38,6 @@\n package org.spearce.jgit.revwalk;\n \n import java.io.IOException;\n-import java.util.EnumSet;\n \n import org.spearce.jgit.errors.IncorrectObjectTypeException;\n import org.spearce.jgit.errors.MissingObjectException;\n@@ -91,8 +90,7 @@ class StartGenerator extends Generator {\n \t\t\treturn mbg.next();\n \t\t}\n \n-\t\tfinal EnumSet sort = w.getRevSort();\n-\t\tboolean boundary = sort.contains(RevSort.BOUNDARY);\n+\t\tboolean boundary = walker.hasRevSort(RevSort.BOUNDARY);\n \n \t\tif (!boundary && walker instanceof ObjectWalk) {\n \t\t\t// The object walker requires boundary support to color\n@@ -110,9 +108,10 @@ class StartGenerator extends Generator {\n \t\t}\n \n \t\tint pendingOutputType = 0;\n-\t\tif (sort.contains(RevSort.START_ORDER) && !(q instanceof FIFORevQueue))\n+\t\tif (walker.hasRevSort(RevSort.START_ORDER)\n+\t\t\t\t&& !(q instanceof FIFORevQueue))\n \t\t\tq = new FIFORevQueue(q);\n-\t\tif (sort.contains(RevSort.COMMIT_TIME_DESC)\n+\t\tif (walker.hasRevSort(RevSort.COMMIT_TIME_DESC)\n \t\t\t\t&& !(q instanceof DateRevQueue))\n \t\t\tq = new DateRevQueue(q);\n \t\tif (tf != TreeFilter.ALL) {\n@@ -141,9 +140,10 @@ class StartGenerator extends Generator {\n \t\t\tg = new RewriteGenerator(g);\n \t\t}\n \n-\t\tif (sort.contains(RevSort.TOPO) && (g.outputType() & SORT_TOPO) == 0)\n+\t\tif (walker.hasRevSort(RevSort.TOPO)\n+\t\t\t\t&& (g.outputType() & SORT_TOPO) == 0)\n \t\t\tg = new TopoSortGenerator(g);\n-\t\tif (sort.contains(RevSort.REVERSE))\n+\t\tif (walker.hasRevSort(RevSort.REVERSE))\n \t\t\tg = new LIFORevQueue(q);\n \t\tif (boundary)\n \t\t\tg = new BoundaryGenerator(w, g);\n-- \n1.5.5.1\n"},{"id":"79981","messageId":"1213566349-25395-17-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-16-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 16/20] Support for RevSort.BOUNDARY in ObjectWalk","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:45Z","receivedAt":"2008-06-15T21:45:45Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"When RevSort.BOUNDARY strategy in enabled, ObjectWalk now includes in\nnextObjects() all objects associated with boundary commits (trees,\nblobs) and all other objects explictly marked as uninteresting\n(boundary).\n\nThis behavior is something more than original C git-rev-list offers in\nthis matter - it is impossible to get such a behavior (to include all\nboundary objects, not only commits, at output) directly from:\n$ git-rev-list --objects-edge\nHere, it is added for compactness - callers usually need also boundary\nobjects (e.g. for preparing thin-pack). If not, they can still easily\nfilter out such objects from nextObject() by checking for UNINTERESTING\nflag or just use next() if interested only in commits.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 26 +++++++++++++++----\n .../src/org/spearce/jgit/revwalk/RevSort.java | 5 +++-\n 2 files changed, 24 insertions(+), 7 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\nindex 68ed861..81cebbd 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n@@ -66,8 +66,6 @@ import org.spearce.jgit.treewalk.TreeWalk;\n * commits that are returned first.\n */\n public class ObjectWalk extends RevWalk {\n-\tprivate static final int SEEN_OR_UNINTERESTING = SEEN | UNINTERESTING;\n-\n \tprivate final TreeWalk treeWalk;\n \n \tprivate BlockObjQueue objects;\n@@ -177,6 +175,8 @@ public class ObjectWalk extends RevWalk {\n \t\t\tIncorrectObjectTypeException, IOException {\n \t\twhile (o instanceof RevTag) {\n \t\t\to.flags |= UNINTERESTING;\n+\t\t\tif (hasRevSort(RevSort.BOUNDARY))\n+\t\t\t\taddObject(o);\n \t\t\to = ((RevTag) o).getObject();\n \t\t\tparse(o);\n \t\t}\n@@ -187,6 +187,10 @@ public class ObjectWalk extends RevWalk {\n \t\t\tmarkTreeUninteresting((RevTree) o);\n \t\telse\n \t\t\to.flags |= UNINTERESTING;\n+\n+\t\tif (o.getType() != Constants.OBJ_COMMIT && hasRevSort(RevSort.BOUNDARY)) {\n+\t\t\taddObject(o);\n+\t\t}\n \t}\n \n \t@Override\n@@ -198,8 +202,10 @@ public class ObjectWalk extends RevWalk {\n \t\t\t\treturn null;\n \t\t\tif ((r.flags & UNINTERESTING) != 0) {\n \t\t\t\tmarkTreeUninteresting(r.getTree());\n-\t\t\t\tif (hasRevSort(RevSort.BOUNDARY))\n+\t\t\t\tif (hasRevSort(RevSort.BOUNDARY)) {\n+\t\t\t\t\tobjects.add(r.getTree());\n \t\t\t\t\treturn r;\n+\t\t\t\t}\n \t\t\t\tcontinue;\n \t\t\t}\n \t\t\tobjects.add(r.getTree());\n@@ -237,17 +243,23 @@ public class ObjectWalk extends RevWalk {\n \t\t\tswitch (sType) {\n \t\t\tcase Constants.OBJ_BLOB: {\n \t\t\t\tfinal RevObject o = lookupAny(treeWalk.getObjectId(0), sType);\n-\t\t\t\tif ((o.flags & SEEN_OR_UNINTERESTING) != 0)\n+\t\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\t\tcontinue;\n \t\t\t\to.flags |= SEEN;\n+\t\t\t\tif ((o.flags & UNINTERESTING) != 0\n+\t\t\t\t\t\t&& !hasRevSort(RevSort.BOUNDARY))\n+\t\t\t\t\tcontinue;\n \t\t\t\tfromTreeWalk = true;\n \t\t\t\treturn o;\n \t\t\t}\n \t\t\tcase Constants.OBJ_TREE: {\n \t\t\t\tfinal RevObject o = lookupAny(treeWalk.getObjectId(0), sType);\n-\t\t\t\tif ((o.flags & SEEN_OR_UNINTERESTING) != 0)\n+\t\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\t\tcontinue;\n \t\t\t\to.flags |= SEEN;\n+\t\t\t\tif ((o.flags & UNINTERESTING) != 0\n+\t\t\t\t\t\t&& !hasRevSort(RevSort.BOUNDARY))\n+\t\t\t\t\tcontinue;\n \t\t\t\tenterSubtree = true;\n \t\t\t\tfromTreeWalk = true;\n \t\t\t\treturn o;\n@@ -265,9 +277,11 @@ public class ObjectWalk extends RevWalk {\n \t\t\tfinal RevObject o = objects.next();\n \t\t\tif (o == null)\n \t\t\t\treturn null;\n-\t\t\tif ((o.flags & SEEN_OR_UNINTERESTING) != 0)\n+\t\t\tif ((o.flags & SEEN) != 0)\n \t\t\t\tcontinue;\n \t\t\to.flags |= SEEN;\n+\t\t\tif ((o.flags & UNINTERESTING) != 0 && !hasRevSort(RevSort.BOUNDARY))\n+\t\t\t\tcontinue;\n \t\t\tif (o instanceof RevTree) {\n \t\t\t\tcurrentTree = (RevTree) o;\n \t\t\t\ttreeWalk.reset(new ObjectId[] { currentTree });\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java\nindex 8688f7f..b0a03ad 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/RevSort.java\n@@ -37,7 +37,7 @@\n \n package org.spearce.jgit.revwalk;\n \n-/** Sorting strategies supported by {@link RevWalk}. */\n+/** Sorting strategies supported by {@link RevWalk} and {@link ObjectWalk}. */\n public enum RevSort {\n \t/**\n \t * No specific sorting is requested.\n@@ -83,6 +83,9 @@ public enum RevSort {\n \n \t/**\n \t * Include {@link RevFlag#UNINTERESTING} boundary commits after all others.\n+\t * In {@link ObjectWalk}, objects associated with such commits (trees,\n+\t * blobs), and all other objects marked explicitly as UNINTERESTING are also\n+\t * included.\n \t *

\n \t * A boundary commit is a UNINTERESTING parent of an interesting commit that\n \t * was previously output.\n-- \n1.5.5.1\n"},{"id":"79979","messageId":"1213566349-25395-18-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-17-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 17/20] Rename confusing objects field in ObjectWalk","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:46Z","receivedAt":"2008-06-15T21:45:46Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Rename ObjectWalk#objects field to pendingObjects, as private objects\nfield already existed in superclass - RevWalk. These 2 fields have\ndifferent meaning and just leaded to confusion.\n\nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/revwalk/ObjectWalk.java | 16 ++++++++--------\n 1 files changed, 8 insertions(+), 8 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\nindex 81cebbd..6a5b857 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/revwalk/ObjectWalk.java\n@@ -68,7 +68,7 @@ import org.spearce.jgit.treewalk.TreeWalk;\n public class ObjectWalk extends RevWalk {\n \tprivate final TreeWalk treeWalk;\n \n-\tprivate BlockObjQueue objects;\n+\tprivate BlockObjQueue pendingObjects;\n \n \tprivate RevTree currentTree;\n \n@@ -85,7 +85,7 @@ public class ObjectWalk extends RevWalk {\n \tpublic ObjectWalk(final Repository repo) {\n \t\tsuper(repo);\n \t\ttreeWalk = new TreeWalk(repo);\n-\t\tobjects = new BlockObjQueue();\n+\t\tpendingObjects = new BlockObjQueue();\n \t}\n \n \t/**\n@@ -203,12 +203,12 @@ public class ObjectWalk extends RevWalk {\n \t\t\tif ((r.flags & UNINTERESTING) != 0) {\n \t\t\t\tmarkTreeUninteresting(r.getTree());\n \t\t\t\tif (hasRevSort(RevSort.BOUNDARY)) {\n-\t\t\t\t\tobjects.add(r.getTree());\n+\t\t\t\t\tpendingObjects.add(r.getTree());\n \t\t\t\t\treturn r;\n \t\t\t\t}\n \t\t\t\tcontinue;\n \t\t\t}\n-\t\t\tobjects.add(r.getTree());\n+\t\t\tpendingObjects.add(r.getTree());\n \t\t\treturn r;\n \t\t}\n \t}\n@@ -274,7 +274,7 @@ public class ObjectWalk extends RevWalk {\n \t\t}\n \n \t\tfor (;;) {\n-\t\t\tfinal RevObject o = objects.next();\n+\t\t\tfinal RevObject o = pendingObjects.next();\n \t\t\tif (o == null)\n \t\t\t\treturn null;\n \t\t\tif ((o.flags & SEEN) != 0)\n@@ -348,7 +348,7 @@ public class ObjectWalk extends RevWalk {\n \t@Override\n \tpublic void dispose() {\n \t\tsuper.dispose();\n-\t\tobjects = new BlockObjQueue();\n+\t\tpendingObjects = new BlockObjQueue();\n \t\tenterSubtree = false;\n \t\tcurrentTree = null;\n \t}\n@@ -356,14 +356,14 @@ public class ObjectWalk extends RevWalk {\n \t@Override\n \tprotected void reset(final int retainFlags) {\n \t\tsuper.reset(retainFlags);\n-\t\tobjects = new BlockObjQueue();\n+\t\tpendingObjects = new BlockObjQueue();\n \t\tenterSubtree = false;\n \t}\n \n \tprivate void addObject(final RevObject o) {\n \t\tif ((o.flags & SEEN) == 0) {\n \t\t\to.flags |= SEEN;\n-\t\t\tobjects.add(o);\n+\t\t\tpendingObjects.add(o);\n \t\t}\n \t}\n \n-- \n1.5.5.1\n"},{"id":"79983","messageId":"1213566349-25395-19-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-18-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 18/20] New CountingOutputStream class - stream decorator","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:47Z","receivedAt":"2008-06-15T21:45:47Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"This decorator provides information about number of already written\nbytes.\n\nSigned-off-by: Marek Zawirski \n---\n .../spearce/jgit/util/CountingOutputStream.java | 89 ++++++++++++++++++++\n 1 files changed, 89 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java b/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\nnew file mode 100644\nindex 0000000..574bb96\n--- /dev/null\n+++ b/org.spearce.jgit/src/org/spearce/jgit/util/CountingOutputStream.java\n@@ -0,0 +1,89 @@\n+/*\n+ * Copyright (C) 2008, Marek Zawirski \n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.util;\n+\n+import java.io.FilterOutputStream;\n+import java.io.IOException;\n+import java.io.OutputStream;\n+\n+/**\n+ * Counting output stream decoration. Counts bytes written to stream.\n+ */\n+public class CountingOutputStream extends FilterOutputStream {\n+\n+\tprivate int count;\n+\n+\t/**\n+\t * Create counting stream being decorated to provided real output stream.\n+\t * \n+\t * @param out\n+\t * output stream where data should be written\n+\t */\n+\tpublic CountingOutputStream(OutputStream out) {\n+\t\tsuper(out);\n+\t}\n+\n+\t@Override\n+\tpublic void write(int b) throws IOException {\n+\t\tout.write(b);\n+\t\tcount++;\n+\t}\n+\n+\t@Override\n+\tpublic void write(byte[] b, int off, int len) throws IOException {\n+\t\tout.write(b, off, len);\n+\t\tcount += len;\n+\t}\n+\n+\t/**\n+\t * Return number of already written bytes.\n+\t * \n+\t * @return number of written bytes since last reset (object is reset upon\n+\t * creation)\n+\t */\n+\tpublic int getCount() {\n+\t\treturn count;\n+\t}\n+\n+\t/**\n+\t * Reset counter to zero value.\n+\t */\n+\tpublic void reset() {\n+\t\tcount = 0;\n+\t}\n+}\n-- \n1.5.5.1\n"},{"id":"79984","messageId":"1213566349-25395-20-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-19-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 19/20] Simplified implementation of pack creation: PackWriter","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:48Z","receivedAt":"2008-06-15T21:45:48Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"This class is able to create a pack basing on provided objects\nspecification and options.\n\nThe core unimplemented feature comparing to the original\ngit-pack-objects is windowed delta searching algorithm (and needed\nbinary delta between 2 files).\n\nThis implementation can create an always correct pack, with\nappropriate objects set and optimized order (as in original git).\nObjects are written as whole objects or deltas to another objects (ref\nor offset). Existing deltas and objects may be reused if set writer is\nset up accordingly. Thin-packs and delta-depth options are also\nsupported.\n\nComparing to the original implementation, delta reuse is performed in a\nslightly different way - allowing delta-chains longer than 2.\nDelta-depth and delta-cycles are checked on-line when writing out\nobjects. These changes were introduced (possibly temporary) to give us\nsensible pack creation implementation without binary delta generation\nalgorithm which is not yet implemented.\n\nMentored-by: Shawn O. Pearce \nSigned-off-by: Marek Zawirski \n---\n .../src/org/spearce/jgit/lib/PackWriter.java | 882 ++++++++++++++++++++\n 1 files changed, 882 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nnew file mode 100644\nindex 0000000..18d3ec2\n--- /dev/null\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -0,0 +1,882 @@\n+/*\n+ * Copyright (C) 2008, Marek Zawirski \n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+import java.io.IOException;\n+import java.io.OutputStream;\n+import java.security.DigestOutputStream;\n+import java.security.MessageDigest;\n+import java.util.ArrayList;\n+import java.util.Collection;\n+import java.util.Collections;\n+import java.util.Iterator;\n+import java.util.LinkedList;\n+import java.util.List;\n+import java.util.zip.Deflater;\n+import java.util.zip.DeflaterOutputStream;\n+\n+import org.spearce.jgit.errors.IncorrectObjectTypeException;\n+import org.spearce.jgit.errors.MissingObjectException;\n+import org.spearce.jgit.revwalk.ObjectWalk;\n+import org.spearce.jgit.revwalk.RevFlag;\n+import org.spearce.jgit.revwalk.RevObject;\n+import org.spearce.jgit.revwalk.RevSort;\n+import org.spearce.jgit.util.CountingOutputStream;\n+import org.spearce.jgit.util.NB;\n+\n+/**\n+ *

\n+ * PackWriter class is responsible for generating pack files from specified set\n+ * of objects from repository. This implementation produce pack files in format\n+ * version 2.\n+ *

\n+ *

\n+ * Source of objects may be specified in two ways:\n+ *

    \n+ *
  • (usually) by providing sets of interesting and uninteresting objects in\n+ * repository - all interesting objects and their ancestors except uninteresting\n+ * objects and their ancestors will be included in pack, or
    • \n+ *
  • by providing iterator of {@link RevObject} specifying exact list and\n+ * order of objects in pack
    • \n+ *
\n+ * Typical usage consists of creating instance intended for some pack,\n+ * configuring options through accessors methods and finally call\n+ * {@link #writePack(Iterator)} or\n+ * {@link #writePack(Collection, Collection, boolean)} with objects\n+ * specification, to generate a pack stream.\n+ *

\n+ *

\n+ * Class provide set of configurable options and {@link ProgressMonitor}\n+ * support, as operations may take a long time for big repositories. Deltas\n+ * searching algorithm is NOT IMPLEMENTED yet - this implementation\n+ * relies only on deltas and objects reuse.\n+ *

\n+ *

\n+ * This class is not thread safe, it is intended to be used in one thread, with\n+ * one instance per created pack. Subsequent calls to writePack result in\n+ * undefined behavior.\n+ *

\n+ */\n+\n+public class PackWriter {\n+\t/**\n+\t * Title of {@link ProgressMonitor} task used during counting objects to\n+\t * pack.\n+\t * \n+\t * @see #writePack(Collection, Collection, boolean)\n+\t */\n+\tpublic static final String COUNTING_OBJECTS_PROGRESS = \"Counting objects to pack\";\n+\n+\t/**\n+\t * Title of {@link ProgressMonitor} task used during searching for objects\n+\t * reuse or delta reuse.\n+\t * \n+\t * @see #writePack(Iterator)\n+\t * @see #writePack(Collection, Collection, boolean)\n+\t */\n+\tpublic static final String SEARCHING_REUSE_PROGRESS = \"Searching for delta and object reuse\";\n+\n+\t/**\n+\t * Title of {@link ProgressMonitor} task used during writing out pack\n+\t * (objects)\n+\t * \n+\t * @see #writePack(Iterator)\n+\t * @see #writePack(Collection, Collection, boolean)\n+\t */\n+\tpublic static final String WRITING_OBJECTS_PROGRESS = \"Writing objects\";\n+\n+\t/**\n+\t * Default value of deltas reuse option.\n+\t * \n+\t * @see #setReuseDeltas(boolean)\n+\t */\n+\tpublic static final boolean DEFAULT_REUSE_DELTAS = true;\n+\n+\t/**\n+\t * Default value of objects reuse option.\n+\t * \n+\t * @see #setReuseObjects(boolean)\n+\t */\n+\tpublic static final boolean DEFAULT_REUSE_OBJECTS = true;\n+\n+\t/**\n+\t * Default value of delta base as offset option.\n+\t * \n+\t * @see #setDeltaBaseAsOffset(boolean)\n+\t */\n+\tpublic static final boolean DEFAULT_DELTA_BASE_AS_OFFSET = false;\n+\n+\t/**\n+\t * Default value of maximum delta chain depth.\n+\t * \n+\t * @see #setMaxDeltaDepth(int)\n+\t */\n+\tpublic static final int DEFAULT_MAX_DELTA_DEPTH = 50;\n+\n+\tprivate static final int PACK_VERSION_GENERATED = 2;\n+\n+\t@SuppressWarnings(\"unchecked\")\n+\tprivate final List objectsLists[] = new List[Constants.OBJ_TAG + 1];\n+\t{\n+\t\tobjectsLists[0] = Collections. emptyList();\n+\t\tobjectsLists[Constants.OBJ_COMMIT] = new ArrayList();\n+\t\tobjectsLists[Constants.OBJ_TREE] = new ArrayList();\n+\t\tobjectsLists[Constants.OBJ_BLOB] = new ArrayList();\n+\t\tobjectsLists[Constants.OBJ_TAG] = new ArrayList();\n+\t}\n+\n+\tprivate final ObjectIdSubclassMap objectsMap = new ObjectIdSubclassMap();\n+\n+\t// edge objects for thin packs\n+\tprivate final ObjectIdSubclassMap edgeObjects = new ObjectIdSubclassMap();\n+\n+\tprivate final Repository db;\n+\n+\tprivate final DigestOutputStream out;\n+\n+\tprivate final CountingOutputStream countingOut;\n+\n+\tprivate final Deflater deflater;\n+\n+\tprivate final ProgressMonitor monitor;\n+\n+\tprivate final byte[] buf = new byte[16384]; // 16 KB\n+\n+\tprivate final WindowCursor windowCursor = new WindowCursor();\n+\n+\tprivate boolean reuseDeltas = DEFAULT_REUSE_DELTAS;\n+\n+\tprivate boolean reuseObjects = DEFAULT_REUSE_OBJECTS;\n+\n+\tprivate boolean deltaBaseAsOffset = DEFAULT_DELTA_BASE_AS_OFFSET;\n+\n+\tprivate int maxDeltaDepth = DEFAULT_MAX_DELTA_DEPTH;\n+\n+\tprivate boolean thin;\n+\n+\t/**\n+\t * Create writer for specified repository, that will write a pack to\n+\t * provided output stream. Objects for packing are specified in\n+\t * {@link #writePack(Iterator)} or\n+\t * {@link #writePack(Collection, Collection, boolean)}.\n+\t * \n+\t * @param repo\n+\t * repository where objects are stored.\n+\t * @param out\n+\t * output stream of pack data; no buffering is guaranteed by\n+\t * writer.\n+\t * @param monitor\n+\t * operations progress monitor, used within\n+\t * {@link #writePack(Iterator)} or\n+\t * {@link #writePack(Collection, Collection, boolean)}.\n+\t */\n+\tpublic PackWriter(final Repository repo, final OutputStream out,\n+\t\t\tfinal ProgressMonitor monitor) {\n+\t\tthis.db = repo;\n+\t\tthis.monitor = monitor;\n+\t\tthis.countingOut = new CountingOutputStream(out);\n+\t\tthis.out = new DigestOutputStream(countingOut, Constants\n+\t\t\t\t.newMessageDigest());\n+\t\tthis.deflater = new Deflater(db.getConfig().getCore().getCompression());\n+\t}\n+\n+\t/**\n+\t * Check whether object is configured to reuse deltas existing in\n+\t * repository.\n+\t *

\n+\t * Default setting: {@value #DEFAULT_REUSE_DELTAS}\n+\t *

\n+\t * \n+\t * @return true if object is configured to reuse deltas; false otherwise.\n+\t */\n+\tpublic boolean isReuseDeltas() {\n+\t\treturn reuseDeltas;\n+\t}\n+\n+\t/**\n+\t * Set reuse deltas configuration option for this writer. When enabled,\n+\t * writer will search for delta representation of object in repository and\n+\t * use it if possible. Normally, only deltas with base to another object\n+\t * existing in set of objects to pack will be used. Exception is however\n+\t * thin-pack (see {@link #writePack(Collection, Collection, boolean)} and\n+\t * {@link #writePack(Iterator)}) where base object must exist on other side\n+\t * machine.\n+\t *

\n+\t * When raw delta data is directly copied from a pack file, checksum is\n+\t * computed to verify data.\n+\t *

\n+\t *

\n+\t * Default setting: {@value #DEFAULT_REUSE_DELTAS}\n+\t *

\n+\t * \n+\t * @param reuseDeltas\n+\t * boolean indicating whether or not try to reuse deltas.\n+\t */\n+\tpublic void setReuseDeltas(boolean reuseDeltas) {\n+\t\tthis.reuseDeltas = reuseDeltas;\n+\t}\n+\n+\t/**\n+\t * Checks whether object is configured to reuse existing objects\n+\t * representation in repository.\n+\t *

\n+\t * Default setting: {@value #DEFAULT_REUSE_OBJECTS}\n+\t *

\n+\t * \n+\t * @return true if writer is configured to reuse objects representation from\n+\t * pack; false otherwise.\n+\t */\n+\tpublic boolean isReuseObjects() {\n+\t\treturn reuseObjects;\n+\t}\n+\n+\t/**\n+\t * Set reuse objects configuration option for this writer. If enabled,\n+\t * writer searches for representation in a pack file. If possible,\n+\t * compressed data is directly copied from such a pack file. Data checksum\n+\t * is verified.\n+\t *

\n+\t * Default setting: {@value #DEFAULT_REUSE_OBJECTS}\n+\t *

\n+\t * \n+\t * @param reuseObjects\n+\t * boolean indicating whether or not writer should reuse existing\n+\t * objects representation.\n+\t */\n+\tpublic void setReuseObjects(boolean reuseObjects) {\n+\t\tthis.reuseObjects = reuseObjects;\n+\t}\n+\n+\t/**\n+\t * Check whether writer can store delta base as an offset (new style\n+\t * reducing pack size) or should store it as an object id (legacy style,\n+\t * compatible with old readers).\n+\t *

\n+\t * Default setting: {@value #DEFAULT_DELTA_BASE_AS_OFFSET}\n+\t *

\n+\t * \n+\t * @return true if delta base is stored as an offset; false if it is stored\n+\t * as an object id.\n+\t */\n+\tpublic boolean isDeltaBaseAsOffset() {\n+\t\treturn deltaBaseAsOffset;\n+\t}\n+\n+\t/**\n+\t * Set writer delta base format. Delta base can be written as an offset in a\n+\t * pack file (new approach reducing file size) or as an object id (legacy\n+\t * approach, compatible with old readers).\n+\t *

\n+\t * Default setting: {@value #DEFAULT_DELTA_BASE_AS_OFFSET}\n+\t *

\n+\t * \n+\t * @param deltaBaseAsOffset\n+\t * boolean indicating whether delta base can be stored as an\n+\t * offset.\n+\t */\n+\tpublic void setDeltaBaseAsOffset(boolean deltaBaseAsOffset) {\n+\t\tthis.deltaBaseAsOffset = deltaBaseAsOffset;\n+\t}\n+\n+\t/**\n+\t * Get maximum depth of delta chain set up for this writer. Generated chains\n+\t * are not longer than this value.\n+\t *

\n+\t * Default setting: {@value #DEFAULT_MAX_DELTA_DEPTH}\n+\t *

\n+\t * \n+\t * @return maximum delta chain depth.\n+\t */\n+\tpublic int getMaxDeltaDepth() {\n+\t\treturn maxDeltaDepth;\n+\t}\n+\n+\t/**\n+\t * Set up maximum depth of delta chain for this writer. Generated chains are\n+\t * not longer than this value. Too low value causes low compression level,\n+\t * while too big makes unpacking (reading) longer.\n+\t *

\n+\t * Default setting: {@value #DEFAULT_MAX_DELTA_DEPTH}\n+\t *

\n+\t * \n+\t * @param maxDeltaDepth\n+\t * maximum delta chain depth.\n+\t */\n+\tpublic void setMaxDeltaDepth(int maxDeltaDepth) {\n+\t\tthis.maxDeltaDepth = maxDeltaDepth;\n+\t}\n+\n+\t/**\n+\t * Returns objects number in a pack file that was created by this writer.\n+\t * \n+\t * @return number of objects in pack.\n+\t */\n+\tpublic int getObjectsNumber() {\n+\t\treturn objectsMap.size();\n+\t}\n+\n+\t/**\n+\t * Write pack to output stream according to current writer configuration for\n+\t * provided source iterator of objects.\n+\t *

\n+\t * Iterator exactly determines which objects are included in a pack\n+\t * and order they appear in pack (except that objects order by type is not\n+\t * needed at input). This order should conform general rules of ordering\n+\t * objects in git - by recency and path (type and delta-base first is\n+\t * internally secured) and responsibility for guaranteeing this order is on\n+\t * a caller side. Iterator must return each id of object to write exactly\n+\t * once.\n+\t *

\n+\t *

\n+\t * When iterator returns object that has {@link RevFlag#UNINTERESTING} flag,\n+\t * this object won't be included in an output pack. Instead, it is recorded\n+\t * as edge-object (known to remote repository) for thin-pack. In such a case\n+\t * writer may pack objects with delta base object not within set of objects\n+\t * to pack, but belonging to party repository - those marked with\n+\t * {@link RevFlag#UNINTERESTING} flag. This type of pack is used only for\n+\t * transport.\n+\t *

\n+\t *

\n+\t * At first, this method collects and sorts objects to pack, then deltas\n+\t * search is performed if set up accordingly, finally pack stream is\n+\t * written. {@link ProgressMonitor} tasks {@value #SEARCHING_REUSE_PROGRESS}\n+\t * (only if resueDeltas or reuseObjects is enabled) and\n+\t * {@value #WRITING_OBJECTS_PROGRESS} are updated during packing.\n+\t *

\n+\t *

\n+\t * All reused objects data checksum (Adler32/CRC32) is computed and\n+\t * validated against existing checksum.\n+\t *

\n+\t * \n+\t * @param objectsSource\n+\t * iterator of object to store in a pack; order of objects within\n+\t * each type is important, ordering by type is not needed;\n+\t * allowed types for objects are {@link Constants#OBJ_COMMIT},\n+\t * {@link Constants#OBJ_TREE}, {@link Constants#OBJ_BLOB} and\n+\t * {@link Constants#OBJ_TAG}; objects returned by iterator may\n+\t * be later reused by caller as object id and type are internally\n+\t * copied in each iteration; if object returned by iterator has\n+\t * {@link RevFlag#UNINTERESTING} flag set, it won't be included\n+\t * in a pack, but is considered as edge-object for thin-pack.\n+\t * @throws IOException\n+\t * when some I/O problem occur during reading objects for pack\n+\t * or writing pack stream.\n+\t */\n+\tpublic void writePack(final Iterator objectsSource)\n+\t\t\tthrows IOException {\n+\t\twhile (objectsSource.hasNext()) {\n+\t\t\taddObject(objectsSource.next());\n+\t\t}\n+\t\twritePackInternal();\n+\t}\n+\n+\t/**\n+\t * Write pack to output stream according to current writer configuration for\n+\t * provided sets of interesting and uninteresting objects.\n+\t *

\n+\t * Basing on these 2 sets, another set of objects to put in a pack file is\n+\t * created: this set consists of all objects reachable (ancestors) from\n+\t * interesting objects, except uninteresting objects and their ancestors.\n+\t * This method uses class {@link ObjectWalk} extensively to find out that\n+\t * appropriate set of output objects and their optimal order in output pack.\n+\t * Order is consistent with general git in-pack rules: sort by object type,\n+\t * recency, path and delta-base first.\n+\t *

\n+\t *

\n+\t * At first, this method collects and sorts objects to pack, then deltas\n+\t * search is performed if set up accordingly, finally pack stream is\n+\t * written. {@link ProgressMonitor} tasks\n+\t * {@value #COUNTING_OBJECTS_PROGRESS}, {@value #SEARCHING_REUSE_PROGRESS}\n+\t * (only if resueDeltas or reuseObjects is enabled) and\n+\t * {@value #WRITING_OBJECTS_PROGRESS} are updated during packing.\n+\t *

\n+\t *

\n+\t * All reused objects data checksum (Adler32/CRC32) is computed and\n+\t * validated against existing checksum.\n+\t *

\n+\t * \n+\t * @param interestingObjects\n+\t * collection of objects to be marked as interesting (start\n+\t * points of graph traversal).\n+\t * @param uninterestingObjects\n+\t * collection of objects to be marked as uninteresting (end\n+\t * points of graph traversal).\n+\t * @param thin\n+\t * a boolean indicating whether writer may pack objects with\n+\t * delta base object not within set of objects to pack, but\n+\t * belonging to party repository (uninteresting/boundary) as\n+\t * determined by set; this kind of pack is used only for\n+\t * transport; true - to produce thin pack, false - otherwise.\n+\t * @throws IOException\n+\t * when some I/O problem occur during reading objects for pack\n+\t * or writing pack stream.\n+\t */\n+\tpublic void writePack(final Collection interestingObjects,\n+\t\t\tfinal Collection uninterestingObjects, boolean thin)\n+\t\t\tthrows IOException {\n+\t\tObjectWalk walker = setUpWalker(interestingObjects,\n+\t\t\t\tuninterestingObjects, thin);\n+\t\tfindObjectsToPack(walker);\n+\t\twritePackInternal();\n+\t}\n+\n+\t/**\n+\t * Computes SHA-1 of lexicographically sorted objects ids written in this\n+\t * pack, as used to name a pack file in repository.\n+\t * \n+\t * @return ObjectId representing SHA-1 name of a pack that was created.\n+\t */\n+\tpublic ObjectId computeName() {\n+\t\tfinal ArrayList sorted = new ArrayList(\n+\t\t\t\tobjectsMap.size());\n+\t\tfor (List list : objectsLists) {\n+\t\t\tfor (ObjectToPack otp : list)\n+\t\t\t\tsorted.add(otp);\n+\t\t}\n+\n+\t\tfinal MessageDigest md = Constants.newMessageDigest();\n+\t\tCollections.sort(sorted);\n+\t\tfor (ObjectToPack otp : sorted) {\n+\t\t\totp.copyRawTo(buf, 0);\n+\t\t\tmd.update(buf, 0, Constants.OBJECT_ID_LENGTH);\n+\t\t}\n+\t\treturn ObjectId.fromRaw(md.digest());\n+\t}\n+\n+\tprivate void writePackInternal() throws IOException {\n+\t\tif (reuseDeltas || reuseObjects)\n+\t\t\tsearchForReuse();\n+\n+\t\tmonitor.beginTask(WRITING_OBJECTS_PROGRESS, getObjectsNumber());\n+\t\twriteHeader();\n+\t\twriteObjects();\n+\t\twriteChecksum();\n+\n+\t\tout.flush();\n+\t\twindowCursor.release();\n+\t\tmonitor.endTask();\n+\t}\n+\n+\tprivate void searchForReuse() throws IOException {\n+\t\tmonitor.beginTask(SEARCHING_REUSE_PROGRESS, getObjectsNumber());\n+\t\tfinal Collection reuseLoaders = new LinkedList();\n+\n+\t\tfor (List list : objectsLists) {\n+\t\t\tfor (ObjectToPack otp : list) {\n+\t\t\t\tif (monitor.isCancelled())\n+\t\t\t\t\tthrow new IOException(\n+\t\t\t\t\t\t\t\"Packing cancelled during objects writing\");\n+\t\t\t\treuseLoaders.clear();\n+\t\t\t\tdb.openObjectInAllPacks(otp, reuseLoaders, windowCursor);\n+\t\t\t\tif (reuseDeltas) {\n+\t\t\t\t\tselectDeltaReuseForObject(otp, reuseLoaders);\n+\t\t\t\t}\n+\t\t\t\t// delta reuse is preferred over object reuse\n+\t\t\t\tif (reuseObjects && !otp.hasReuseLoader()) {\n+\t\t\t\t\tselectObjectReuseForObject(otp, reuseLoaders);\n+\t\t\t\t}\n+\t\t\t\tmonitor.update(1);\n+\t\t\t}\n+\t\t}\n+\n+\t\tmonitor.endTask();\n+\t}\n+\n+\tprivate void selectDeltaReuseForObject(final ObjectToPack otp,\n+\t\t\tfinal Collection loaders) throws IOException {\n+\t\tPackedObjectLoader bestLoader = null;\n+\t\tObjectId bestBase = null;\n+\n+\t\tfor (PackedObjectLoader loader : loaders) {\n+\t\t\tObjectId idBase = loader.getDeltaBase();\n+\t\t\tif (idBase == null)\n+\t\t\t\tcontinue;\n+\t\t\tObjectToPack otpBase = objectsMap.get(idBase);\n+\n+\t\t\t// only if base is in set of objects to write or thin-pack's edge\n+\t\t\tif ((otpBase != null || (thin && edgeObjects.get(idBase) != null))\n+\t\t\t// select smallest possible delta if > 1 available\n+\t\t\t\t\t&& isBetterDeltaReuseLoader(bestLoader, loader)) {\n+\t\t\t\tbestLoader = loader;\n+\t\t\t\tbestBase = (otpBase != null ? otpBase : idBase);\n+\t\t\t}\n+\t\t}\n+\n+\t\tif (bestLoader != null) {\n+\t\t\totp.setReuseLoader(bestLoader);\n+\t\t\totp.setDeltaBase(bestBase);\n+\t\t}\n+\t}\n+\n+\tprivate boolean isBetterDeltaReuseLoader(PackedObjectLoader currentLoader,\n+\t\t\tPackedObjectLoader loader) throws IOException {\n+\t\tif (currentLoader == null)\n+\t\t\treturn true;\n+\t\tif (loader.getRawSize() < currentLoader.getRawSize())\n+\t\t\treturn true;\n+\t\treturn (loader.getRawSize() == currentLoader.getRawSize()\n+\t\t\t\t&& loader.supportsFastCopyRawData() && !currentLoader\n+\t\t\t\t.supportsFastCopyRawData());\n+\t}\n+\n+\tprivate void selectObjectReuseForObject(final ObjectToPack otp,\n+\t\t\tfinal Collection loaders) {\n+\t\tfor (final PackedObjectLoader loader : loaders) {\n+\t\t\tif (loader instanceof WholePackedObjectLoader) {\n+\t\t\t\totp.setReuseLoader(loader);\n+\t\t\t\treturn;\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tprivate void writeHeader() throws IOException {\n+\t\tout.write(Constants.PACK_SIGNATURE);\n+\n+\t\tNB.encodeInt32(buf, 0, PACK_VERSION_GENERATED);\n+\t\tout.write(buf, 0, 4);\n+\n+\t\tNB.encodeInt32(buf, 0, getObjectsNumber());\n+\t\tout.write(buf, 0, 4);\n+\t}\n+\n+\tprivate void writeObjects() throws IOException {\n+\t\tfor (List list : objectsLists) {\n+\t\t\tfor (ObjectToPack otp : list) {\n+\t\t\t\tif (monitor.isCancelled())\n+\t\t\t\t\tthrow new IOException(\n+\t\t\t\t\t\t\t\"Packing cancelled during objects writing\");\n+\t\t\t\tif (!otp.isWritten())\n+\t\t\t\t\twriteObject(otp);\n+\t\t\t}\n+\t\t}\n+\t}\n+\n+\tprivate void writeObject(final ObjectToPack otp) throws IOException {\n+\t\totp.markWantWrite();\n+\t\tif (otp.isDeltaRepresentation()) {\n+\t\t\tObjectToPack deltaBase = otp.getDeltaBase();\n+\t\t\tassert deltaBase != null || thin;\n+\t\t\tif (deltaBase != null && !deltaBase.isWritten()) {\n+\t\t\t\tif (deltaBase.wantWrite()) {\n+\t\t\t\t\totp.clearDeltaBase(); // cycle detected\n+\t\t\t\t\totp.disposeLoader();\n+\t\t\t\t} else {\n+\t\t\t\t\twriteObject(deltaBase);\n+\t\t\t\t}\n+\t\t\t}\n+\n+\t\t\totp.updateDeltaDepth();\n+\t\t\tif (otp.getDeltaDepth() > maxDeltaDepth) {\n+\t\t\t\totp.clearDeltaBase();\n+\t\t\t\totp.disposeLoader();\n+\t\t\t}\n+\t\t}\n+\n+\t\tassert !otp.isWritten();\n+\n+\t\totp.markWritten(countingOut.getCount());\n+\t\tif (otp.isDeltaRepresentation())\n+\t\t\twriteDeltaObject(otp);\n+\t\telse\n+\t\t\twriteWholeObject(otp);\n+\n+\t\tmonitor.update(1);\n+\t}\n+\n+\tprivate void writeWholeObject(final ObjectToPack otp) throws IOException {\n+\t\tif (otp.hasReuseLoader()) {\n+\t\t\tfinal PackedObjectLoader loader = otp.getReuseLoader();\n+\t\t\twriteObjectHeader(loader.getType(), loader.getSize());\n+\t\t\tloader.copyRawData(out, buf);\n+\t\t\totp.disposeLoader();\n+\t\t} else {\n+\t\t\tfinal ObjectLoader loader = db.openObject(windowCursor, otp);\n+\t\t\tfinal DeflaterOutputStream deflaterOut = new DeflaterOutputStream(\n+\t\t\t\t\tout, deflater);\n+\t\t\twriteObjectHeader(loader.getType(), loader.getSize());\n+\t\t\tdeflaterOut.write(loader.getCachedBytes());\n+\t\t\tdeflaterOut.finish();\n+\t\t\tdeflater.reset();\n+\t\t}\n+\t}\n+\n+\tprivate void writeDeltaObject(final ObjectToPack otp) throws IOException {\n+\t\tfinal PackedObjectLoader loader = otp.getReuseLoader();\n+\t\tif (deltaBaseAsOffset && otp.getDeltaBase() != null) {\n+\t\t\twriteObjectHeader(Constants.OBJ_OFS_DELTA, loader.getRawSize());\n+\n+\t\t\tfinal ObjectToPack deltaBase = otp.getDeltaBase();\n+\t\t\tlong offsetDiff = otp.getOffset() - deltaBase.getOffset();\n+\t\t\tint pos = buf.length - 1;\n+\t\t\tbuf[pos] = (byte) (offsetDiff & 0x7F);\n+\t\t\twhile ((offsetDiff >>= 7) > 0) {\n+\t\t\t\tbuf[--pos] = (byte) (0x80 | (--offsetDiff & 0x7F));\n+\t\t\t}\n+\n+\t\t\tout.write(buf, pos, buf.length - pos);\n+\t\t} else {\n+\t\t\twriteObjectHeader(Constants.OBJ_REF_DELTA, loader.getRawSize());\n+\t\t\totp.getDeltaBaseId().copyRawTo(buf, 0);\n+\t\t\tout.write(buf, 0, Constants.OBJECT_ID_LENGTH);\n+\t\t}\n+\t\tloader.copyRawData(out, buf);\n+\t\totp.disposeLoader();\n+\t}\n+\n+\tprivate void writeObjectHeader(final int objectType, long dataLength)\n+\t\t\tthrows IOException {\n+\t\tlong nextLength = dataLength >>> 4;\n+\t\tint size = 0;\n+\t\tbuf[size++] = (byte) ((nextLength > 0 ? 0x80 : 0x00)\n+\t\t\t\t| (objectType << 4) | (dataLength & 0x0F));\n+\t\tdataLength = nextLength;\n+\t\twhile (dataLength > 0) {\n+\t\t\tnextLength >>>= 7;\n+\t\t\tbuf[size++] = (byte) ((nextLength > 0 ? 0x80 : 0x00) | (dataLength & 0x7F));\n+\t\t\tdataLength = nextLength;\n+\t\t}\n+\t\tout.write(buf, 0, size);\n+\t}\n+\n+\tprivate void writeChecksum() throws IOException {\n+\t\tout.on(false);\n+\t\tfinal byte checksum[] = out.getMessageDigest().digest();\n+\t\tout.write(checksum);\n+\t}\n+\n+\tprivate ObjectWalk setUpWalker(\n+\t\t\tfinal Collection interestingObjects,\n+\t\t\tfinal Collection uninterestingObjects, boolean thin)\n+\t\t\tthrows MissingObjectException, IOException,\n+\t\t\tIncorrectObjectTypeException {\n+\t\tfinal ObjectWalk walker = new ObjectWalk(db);\n+\t\twalker.sort(RevSort.TOPO, true);\n+\t\twalker.sort(RevSort.COMMIT_TIME_DESC, true);\n+\t\tif (thin)\n+\t\t\twalker.sort(RevSort.BOUNDARY);\n+\n+\t\tfor (ObjectId id : interestingObjects) {\n+\t\t\tRevObject o = walker.parseAny(id);\n+\t\t\twalker.markStart(o);\n+\t\t}\n+\t\tfor (ObjectId id : uninterestingObjects) {\n+\t\t\tRevObject o = walker.parseAny(id);\n+\t\t\twalker.markUninteresting(o);\n+\t\t}\n+\t\treturn walker;\n+\t}\n+\n+\tprivate void findObjectsToPack(final ObjectWalk walker)\n+\t\t\tthrows MissingObjectException, IncorrectObjectTypeException,\n+\t\t\tIOException {\n+\t\tmonitor.beginTask(COUNTING_OBJECTS_PROGRESS, ProgressMonitor.UNKNOWN);\n+\t\tRevObject o;\n+\n+\t\twhile ((o = walker.next()) != null) {\n+\t\t\taddObject(o);\n+\t\t\tmonitor.update(1);\n+\t\t}\n+\t\twhile ((o = walker.nextObject()) != null) {\n+\t\t\taddObject(o);\n+\t\t\tmonitor.update(1);\n+\t\t}\n+\t\tmonitor.endTask();\n+\t}\n+\n+\tprivate void addObject(RevObject object)\n+\t\t\tthrows IncorrectObjectTypeException {\n+\t\tif (object.has(RevFlag.UNINTERESTING)) {\n+\t\t\tedgeObjects.add(object);\n+\t\t\tthin = true;\n+\t\t\treturn;\n+\t\t}\n+\n+\t\tfinal ObjectToPack otp = new ObjectToPack(object);\n+\t\ttry {\n+\t\t\tobjectsLists[object.getType()].add(otp);\n+\t\t} catch (ArrayIndexOutOfBoundsException x) {\n+\t\t\tthrow new IncorrectObjectTypeException(object,\n+\t\t\t\t\t\"COMMIT nor TREE nor BLOB nor TAG\");\n+\t\t} catch (UnsupportedOperationException x) {\n+\t\t\t// index pointing to \"dummy\" empty list\n+\t\t\tthrow new IncorrectObjectTypeException(object,\n+\t\t\t\t\t\"COMMIT nor TREE nor BLOB nor TAG\");\n+\t\t}\n+\t\tobjectsMap.add(otp);\n+\t}\n+\n+\t/**\n+\t * Class holding information about object that is going to be packed by\n+\t * {@link PackWriter}. Information include object representation in a\n+\t * pack-file and object status.\n+\t * \n+\t */\n+\tstatic class ObjectToPack extends ObjectId {\n+\t\tprivate ObjectId deltaBase;\n+\n+\t\tprivate PackedObjectLoader reuseLoader;\n+\n+\t\tprivate long offset = -1;\n+\n+\t\tprivate int deltaDepth;\n+\n+\t\tprivate boolean wantWrite;\n+\n+\t\t/**\n+\t\t * Construct object for specified object id.
By default object is\n+\t\t * marked as not written and non-delta packed (as a whole object).\n+\t\t * \n+\t\t * @param src\n+\t\t * object id of object for packing\n+\t\t */\n+\t\tObjectToPack(AnyObjectId src) {\n+\t\t\tsuper(src);\n+\t\t}\n+\n+\t\t/**\n+\t\t * @return delta base object id if object is going to be packed in delta\n+\t\t * representation; null otherwise - if going to be packed as a\n+\t\t * whole object.\n+\t\t */\n+\t\tObjectId getDeltaBaseId() {\n+\t\t\treturn deltaBase;\n+\t\t}\n+\n+\t\t/**\n+\t\t * @return delta base object to pack if object is going to be packed in\n+\t\t * delta representation and delta is specified as object to\n+\t\t * pack; null otherwise - if going to be packed as a whole\n+\t\t * object or delta base is specified only as id.\n+\t\t */\n+\t\tObjectToPack getDeltaBase() {\n+\t\t\tif (deltaBase instanceof ObjectToPack)\n+\t\t\t\treturn (ObjectToPack) deltaBase;\n+\t\t\treturn null;\n+\t\t}\n+\n+\t\t/**\n+\t\t * Set delta base for the object. Delta base set by this method is used\n+\t\t * by {@link PackWriter} to write object - determines its representation\n+\t\t * in a created pack.\n+\t\t * \n+\t\t * @param deltaBase\n+\t\t * delta base object or null if object should be packed as a\n+\t\t * whole object.\n+\t\t * \n+\t\t */\n+\t\tvoid setDeltaBase(ObjectId deltaBase) {\n+\t\t\tthis.deltaBase = deltaBase;\n+\t\t}\n+\n+\t\tvoid clearDeltaBase() {\n+\t\t\tthis.deltaBase = null;\n+\t\t}\n+\n+\t\t/**\n+\t\t * @return true if object is going to be written as delta; false\n+\t\t * otherwise.\n+\t\t */\n+\t\tboolean isDeltaRepresentation() {\n+\t\t\treturn deltaBase != null;\n+\t\t}\n+\n+\t\t/**\n+\t\t * Check if object is already written in a pack. This information is\n+\t\t * used to achieve delta-base precedence in a pack file.\n+\t\t * \n+\t\t * @return true if object is already written; false otherwise.\n+\t\t */\n+\t\tboolean isWritten() {\n+\t\t\treturn offset != -1;\n+\t\t}\n+\n+\t\t/**\n+\t\t * @return offset in pack when object has been already written, or -1 if\n+\t\t * it has not been written yet\n+\t\t */\n+\t\tlong getOffset() {\n+\t\t\treturn offset;\n+\t\t}\n+\n+\t\t/**\n+\t\t * Mark object as written. This information is used to achieve\n+\t\t * delta-base precedence in a pack file.\n+\t\t * \n+\t\t * @param offset\n+\t\t * offset where written object starts\n+\t\t */\n+\t\tvoid markWritten(long offset) {\n+\t\t\tthis.offset = offset;\n+\t\t}\n+\n+\t\tPackedObjectLoader getReuseLoader() {\n+\t\t\treturn reuseLoader;\n+\t\t}\n+\n+\t\tboolean hasReuseLoader() {\n+\t\t\treturn reuseLoader != null;\n+\t\t}\n+\n+\t\tvoid setReuseLoader(PackedObjectLoader reuseLoader) {\n+\t\t\tthis.reuseLoader = reuseLoader;\n+\t\t}\n+\n+\t\tvoid disposeLoader() {\n+\t\t\tthis.reuseLoader = null;\n+\t\t}\n+\n+\t\tint getDeltaDepth() {\n+\t\t\treturn deltaDepth;\n+\t\t}\n+\n+\t\tvoid updateDeltaDepth() {\n+\t\t\tif (deltaBase instanceof ObjectToPack)\n+\t\t\t\tdeltaDepth = ((ObjectToPack) deltaBase).deltaDepth + 1;\n+\t\t\telse if (deltaBase != null)\n+\t\t\t\tdeltaDepth = 1;\n+\t\t}\n+\n+\t\tboolean wantWrite() {\n+\t\t\treturn wantWrite;\n+\t\t}\n+\n+\t\tvoid markWantWrite() {\n+\t\t\tthis.wantWrite = true;\n+\t\t}\n+\t}\n+}\n-- \n1.5.5.1\n"},{"id":"79985","messageId":"1213566349-25395-21-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-20-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 20/20] PackWriter test suite","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-15T21:45:49Z","receivedAt":"2008-06-15T21:45:49Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Test suite is provided relying on IndexPack and PackIndex to verify\nPackWriter output for various configurations.\n\nSigned-off-by: Marek Zawirski \n---\n .../tst/org/spearce/jgit/lib/PackWriterTest.java | 454 ++++++++++++++++++++\n 1 files changed, 454 insertions(+), 0 deletions(-)\n create mode 100644 org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n\ndiff --git a/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\nnew file mode 100644\nindex 0000000..9572342\n--- /dev/null\n+++ b/org.spearce.jgit.test/tst/org/spearce/jgit/lib/PackWriterTest.java\n@@ -0,0 +1,454 @@\n+/*\n+ * Copyright (C) 2008, Marek Zawirski \n+ *\n+ * All rights reserved.\n+ *\n+ * Redistribution and use in source and binary forms, with or\n+ * without modification, are permitted provided that the following\n+ * conditions are met:\n+ *\n+ * - Redistributions of source code must retain the above copyright\n+ * notice, this list of conditions and the following disclaimer.\n+ *\n+ * - Redistributions in binary form must reproduce the above\n+ * copyright notice, this list of conditions and the following\n+ * disclaimer in the documentation and/or other materials provided\n+ * with the distribution.\n+ *\n+ * - Neither the name of the Git Development Community nor the\n+ * names of its contributors may be used to endorse or promote\n+ * products derived from this software without specific prior\n+ * written permission.\n+ *\n+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND\n+ * CONTRIBUTORS \"AS IS\" AND ANY EXPRESS OR IMPLIED WARRANTIES,\n+ * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES\n+ * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE\n+ * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR\n+ * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,\n+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT\n+ * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;\n+ * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER\n+ * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,\n+ * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)\n+ * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF\n+ * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.\n+ */\n+\n+package org.spearce.jgit.lib;\n+\n+import java.io.ByteArrayInputStream;\n+import java.io.ByteArrayOutputStream;\n+import java.io.File;\n+import java.io.IOException;\n+import java.io.InputStream;\n+import java.util.ArrayList;\n+import java.util.Arrays;\n+import java.util.Collection;\n+import java.util.Collections;\n+import java.util.Comparator;\n+import java.util.Iterator;\n+import java.util.LinkedList;\n+import java.util.List;\n+\n+import org.spearce.jgit.errors.MissingObjectException;\n+import org.spearce.jgit.lib.PackIndex.MutableEntry;\n+import org.spearce.jgit.revwalk.RevObject;\n+import org.spearce.jgit.revwalk.RevWalk;\n+import org.spearce.jgit.transport.IndexPack;\n+import org.spearce.jgit.util.CountingOutputStream;\n+\n+public class PackWriterTest extends RepositoryTestCase {\n+\n+\tprivate static final List EMPTY_LIST_OBJECT = Collections\n+\t\t\t. emptyList();\n+\n+\tprivate static final List EMPTY_LIST_REVS = Collections\n+\t\t\t. emptyList();\n+\n+\tprivate PackWriter writer;\n+\n+\tprivate ByteArrayOutputStream os;\n+\n+\tprivate CountingOutputStream cos;\n+\n+\tprivate File packBase;\n+\n+\tprivate File packFile;\n+\n+\tprivate File indexFile;\n+\n+\tprivate PackFile pack;\n+\n+\tpublic void setUp() throws Exception {\n+\t\tsuper.setUp();\n+\t\tos = new ByteArrayOutputStream();\n+\t\tcos = new CountingOutputStream(os);\n+\t\tpackBase = new File(trash, \"tmp_pack\");\n+\t\tpackFile = new File(trash, \"tmp_pack.pack\");\n+\t\tindexFile = new File(trash, \"tmp_pack.idx\");\n+\t\twriter = new PackWriter(db, cos, new TextProgressMonitor());\n+\t}\n+\n+\t/**\n+\t * Test constructor for exceptions, default settings, initialization.\n+\t */\n+\tpublic void testContructor() {\n+\t\tassertEquals(false, writer.isDeltaBaseAsOffset());\n+\t\tassertEquals(true, writer.isReuseDeltas());\n+\t\tassertEquals(true, writer.isReuseObjects());\n+\t\tassertEquals(0, writer.getObjectsNumber());\n+\t}\n+\n+\t/**\n+\t * Change default settings and verify them.\n+\t */\n+\tpublic void testModifySettings() {\n+\t\twriter.setDeltaBaseAsOffset(true);\n+\t\twriter.setReuseDeltas(false);\n+\t\twriter.setReuseObjects(false);\n+\n+\t\tassertEquals(true, writer.isDeltaBaseAsOffset());\n+\t\tassertEquals(false, writer.isReuseDeltas());\n+\t\tassertEquals(false, writer.isReuseObjects());\n+\t}\n+\n+\t/**\n+\t * Write empty pack by providing empty sets of interesting/uninteresting\n+\t * objects and check for correct format.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWriteEmptyPack1() throws IOException {\n+\t\tcreateVerifyOpenPack(EMPTY_LIST_OBJECT, EMPTY_LIST_OBJECT, false);\n+\n+\t\tassertEquals(0, writer.getObjectsNumber());\n+\t\tassertEquals(0, pack.getObjectCount());\n+\t\tassertEquals(\"da39a3ee5e6b4b0d3255bfef95601890afd80709\", writer\n+\t\t\t\t.computeName().toString());\n+\t}\n+\n+\t/**\n+\t * Write empty pack by providing empty iterator of objects to write and\n+\t * check for correct format.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWriteEmptyPack2() throws IOException {\n+\t\tcreateVerifyOpenPack(EMPTY_LIST_REVS.iterator());\n+\n+\t\tassertEquals(0, writer.getObjectsNumber());\n+\t\tassertEquals(0, pack.getObjectCount());\n+\t}\n+\n+\t/**\n+\t * Create pack basing on only interesting objects, then precisely verify\n+\t * content. No delta reuse here.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack1() throws IOException {\n+\t\twriter.setReuseDeltas(false);\n+\t\twriteVerifyPack1();\n+\t}\n+\n+\t/**\n+\t * Test writing pack without object reuse. Pack content/preparation as in\n+\t * {@link #testWritePack1()}.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack1NoObjectReuse() throws IOException {\n+\t\twriter.setReuseDeltas(false);\n+\t\twriter.setReuseObjects(false);\n+\t\twriteVerifyPack1();\n+\t}\n+\n+\t/**\n+\t * Create pack basing on both interesting and uninteresting objects, then\n+\t * precisely verify content. No delta reuse here.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack2() throws IOException {\n+\t\twriteVerifyPack2(false);\n+\t}\n+\n+\t/**\n+\t * Test pack writing with deltas reuse, delta-base first rule. Pack\n+\t * content/preparation as in {@link #testWritePack2()}.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack2DeltasReuseRefs() throws IOException {\n+\t\twriteVerifyPack2(true);\n+\t}\n+\n+\t/**\n+\t * Test pack writing with delta reuse. Delta bases referred as offsets. Pack\n+\t * configuration as in {@link #testWritePack2DeltasReuseRefs()}.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack2DeltasReuseOffsets() throws IOException {\n+\t\twriter.setDeltaBaseAsOffset(true);\n+\t\twriteVerifyPack2(true);\n+\t}\n+\n+\t/**\n+\t * Test pack writing with delta reuse. Raw-data copy (reuse) is made on a\n+\t * pack with CRC32 index. Pack configuration as in\n+\t * {@link #testWritePack2DeltasReuseRefs()}.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack2DeltasCRC32Copy() throws IOException {\n+\t\tfinal File packDir = new File(db.getObjectsDirectory(), \"pack\");\n+\t\tfinal File crc32Pack = new File(packDir,\n+\t\t\t\t\"pack-34be9032ac282b11fa9babdc2b2a93ca996c9c2f.pack\");\n+\t\tfinal File crc32Idx = new File(packDir,\n+\t\t\t\t\"pack-34be9032ac282b11fa9babdc2b2a93ca996c9c2f.idx\");\n+\t\tcopyFile(new File(new File(\"tst\"),\n+\t\t\t\t\"pack-34be9032ac282b11fa9babdc2b2a93ca996c9c2f.idxV2\"),\n+\t\t\t\tcrc32Idx);\n+\t\tdb.openPack(crc32Pack, crc32Idx);\n+\n+\t\twriteVerifyPack2(true);\n+\t}\n+\n+\t/**\n+\t * Create pack basing on fixed objects list, then precisely verify content.\n+\t * No delta reuse here.\n+\t * \n+\t * @throws IOException\n+\t * @throws MissingObjectException\n+\t * \n+\t */\n+\tpublic void testWritePack3() throws MissingObjectException, IOException {\n+\t\twriter.setReuseDeltas(false);\n+\t\tfinal ObjectId forcedOrder[] = new ObjectId[] {\n+\t\t\t\tObjectId.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"),\n+\t\t\t\tObjectId.fromString(\"c59759f143fb1fe21c197981df75a7ee00290799\"),\n+\t\t\t\tObjectId.fromString(\"aabf2ffaec9b497f0950352b3e582d73035c2035\"),\n+\t\t\t\tObjectId.fromString(\"902d5476fa249b7abc9d84c611577a81381f0327\"),\n+\t\t\t\tObjectId.fromString(\"5b6e7c66c276e7610d4a73c70ec1a1f7c1003259\"),\n+\t\t\t\tObjectId.fromString(\"6ff87c4664981e4397625791c8ea3bbb5f2279a3\") };\n+\t\tfinal RevWalk parser = new RevWalk(db);\n+\t\tfinal RevObject forcedOrderRevs[] = new RevObject[forcedOrder.length];\n+\t\tfor (int i = 0; i < forcedOrder.length; i++)\n+\t\t\tforcedOrderRevs[i] = parser.parseAny(forcedOrder[i]);\n+\n+\t\tcreateVerifyOpenPack(Arrays.asList(forcedOrderRevs).iterator());\n+\n+\t\tassertEquals(forcedOrder.length, writer.getObjectsNumber());\n+\t\tverifyObjectsOrder(forcedOrder);\n+\t\tassertEquals(\"ed3f96b8327c7c66b0f8f70056129f0769323d86\", writer\n+\t\t\t\t.computeName().toString());\n+\t}\n+\n+\t/**\n+\t * Another pack creation: basing on both interesting and uninteresting\n+\t * objects. No delta reuse possible here, as this is a specific case when we\n+\t * write only 1 commit, associated with 1 tree, 1 blob.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack4() throws IOException {\n+\t\twriteVerifyPack4(false);\n+\t}\n+\n+\t/**\n+\t * Test thin pack writing: 1 blob delta base is on objects edge. Pack\n+\t * configuration as in {@link #testWritePack4()}.\n+\t * \n+\t * @throws IOException\n+\t */\n+\tpublic void testWritePack4ThinPack() throws IOException {\n+\t\twriteVerifyPack4(true);\n+\t}\n+\n+\t/**\n+\t * Compare sizes of packs created using {@link #testWritePack2()} and\n+\t * {@link #testWritePack2DeltasReuseRefs()}. The pack using deltas should\n+\t * be smaller.\n+\t * \n+\t * @throws Exception\n+\t */\n+\tpublic void testWritePack2SizeDeltasVsNoDeltas() throws Exception {\n+\t\ttestWritePack2();\n+\t\tfinal int sizePack2NoDeltas = cos.getCount();\n+\t\tsetUp();\n+\t\ttestWritePack2DeltasReuseRefs();\n+\t\tfinal int sizePack2DeltasRefs = cos.getCount();\n+\n+\t\tassertTrue(sizePack2NoDeltas > sizePack2DeltasRefs);\n+\t}\n+\n+\t/**\n+\t * Compare sizes of packs created using\n+\t * {@link #testWritePack2DeltasReuseRefs()} and\n+\t * {@link #testWritePack2DeltasReuseOffsets()}. The pack with delta bases\n+\t * written as offsets should be smaller.\n+\t * \n+\t * @throws Exception\n+\t */\n+\tpublic void testWritePack2SizeOffsetsVsRefs() throws Exception {\n+\t\ttestWritePack2DeltasReuseRefs();\n+\t\tfinal int sizePack2DeltasRefs = cos.getCount();\n+\t\tsetUp();\n+\t\ttestWritePack2DeltasReuseOffsets();\n+\t\tfinal int sizePack2DeltasOffsets = cos.getCount();\n+\n+\t\tassertTrue(sizePack2DeltasRefs > sizePack2DeltasOffsets);\n+\t}\n+\n+\t/**\n+\t * Compare sizes of packs created using {@link #testWritePack4()} and\n+\t * {@link #testWritePack4ThinPack()}. Obviously, the thin pack should be\n+\t * smaller.\n+\t * \n+\t * @throws Exception\n+\t */\n+\tpublic void testWritePack4SizeThinVsNoThin() throws Exception {\n+\t\ttestWritePack4();\n+\t\tfinal int sizePack4 = cos.getCount();\n+\t\tsetUp();\n+\t\ttestWritePack4ThinPack();\n+\t\tfinal int sizePack4Thin = cos.getCount();\n+\n+\t\tassertTrue(sizePack4 > sizePack4Thin);\n+\t}\n+\n+\t// TODO: testWritePackDeltasCycle()\n+\t// TODO: testWritePackDeltasDepth()\n+\n+\tprivate void writeVerifyPack1() throws IOException {\n+\t\tfinal LinkedList interestings = new LinkedList();\n+\t\tinterestings.add(ObjectId\n+\t\t\t\t.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"));\n+\t\tcreateVerifyOpenPack(interestings, EMPTY_LIST_OBJECT, false);\n+\n+\t\tfinal ObjectId expectedOrder[] = new ObjectId[] {\n+\t\t\t\tObjectId.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"),\n+\t\t\t\tObjectId.fromString(\"c59759f143fb1fe21c197981df75a7ee00290799\"),\n+\t\t\t\tObjectId.fromString(\"540a36d136cf413e4b064c2b0e0a4db60f77feab\"),\n+\t\t\t\tObjectId.fromString(\"aabf2ffaec9b497f0950352b3e582d73035c2035\"),\n+\t\t\t\tObjectId.fromString(\"902d5476fa249b7abc9d84c611577a81381f0327\"),\n+\t\t\t\tObjectId.fromString(\"4b825dc642cb6eb9a060e54bf8d69288fbee4904\"),\n+\t\t\t\tObjectId.fromString(\"5b6e7c66c276e7610d4a73c70ec1a1f7c1003259\"),\n+\t\t\t\tObjectId.fromString(\"6ff87c4664981e4397625791c8ea3bbb5f2279a3\") };\n+\n+\t\tassertEquals(expectedOrder.length, writer.getObjectsNumber());\n+\t\tverifyObjectsOrder(expectedOrder);\n+\t\tassertEquals(\"34be9032ac282b11fa9babdc2b2a93ca996c9c2f\", writer\n+\t\t\t\t.computeName().toString());\n+\t}\n+\n+\tprivate void writeVerifyPack2(boolean deltaReuse) throws IOException {\n+\t\twriter.setReuseDeltas(deltaReuse);\n+\t\tfinal LinkedList interestings = new LinkedList();\n+\t\tinterestings.add(ObjectId\n+\t\t\t\t.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"));\n+\t\tfinal LinkedList uninterestings = new LinkedList();\n+\t\tuninterestings.add(ObjectId\n+\t\t\t\t.fromString(\"540a36d136cf413e4b064c2b0e0a4db60f77feab\"));\n+\t\tcreateVerifyOpenPack(interestings, uninterestings, false);\n+\n+\t\tfinal ObjectId expectedOrder[] = new ObjectId[] {\n+\t\t\t\tObjectId.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"),\n+\t\t\t\tObjectId.fromString(\"c59759f143fb1fe21c197981df75a7ee00290799\"),\n+\t\t\t\tObjectId.fromString(\"aabf2ffaec9b497f0950352b3e582d73035c2035\"),\n+\t\t\t\tObjectId.fromString(\"902d5476fa249b7abc9d84c611577a81381f0327\"),\n+\t\t\t\tObjectId.fromString(\"5b6e7c66c276e7610d4a73c70ec1a1f7c1003259\"),\n+\t\t\t\tObjectId.fromString(\"6ff87c4664981e4397625791c8ea3bbb5f2279a3\") };\n+\t\tif (deltaReuse) {\n+\t\t\t// objects order influenced (swapped) by delta-base first rule\n+\t\t\tObjectId temp = expectedOrder[4];\n+\t\t\texpectedOrder[4] = expectedOrder[5];\n+\t\t\texpectedOrder[5] = temp;\n+\t\t}\n+\t\tassertEquals(expectedOrder.length, writer.getObjectsNumber());\n+\t\tverifyObjectsOrder(expectedOrder);\n+\t\tassertEquals(\"ed3f96b8327c7c66b0f8f70056129f0769323d86\", writer\n+\t\t\t\t.computeName().toString());\n+\t}\n+\n+\tprivate void writeVerifyPack4(final boolean thin) throws IOException {\n+\t\tfinal LinkedList interestings = new LinkedList();\n+\t\tinterestings.add(ObjectId\n+\t\t\t\t.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"));\n+\t\tfinal LinkedList uninterestings = new LinkedList();\n+\t\tuninterestings.add(ObjectId\n+\t\t\t\t.fromString(\"c59759f143fb1fe21c197981df75a7ee00290799\"));\n+\t\tcreateVerifyOpenPack(interestings, uninterestings, thin);\n+\n+\t\tfinal ObjectId writtenObjects[] = new ObjectId[] {\n+\t\t\t\tObjectId.fromString(\"82c6b885ff600be425b4ea96dee75dca255b69e7\"),\n+\t\t\t\tObjectId.fromString(\"aabf2ffaec9b497f0950352b3e582d73035c2035\"),\n+\t\t\t\tObjectId.fromString(\"5b6e7c66c276e7610d4a73c70ec1a1f7c1003259\") };\n+\t\tassertEquals(writtenObjects.length, writer.getObjectsNumber());\n+\t\tObjectId expectedObjects[];\n+\t\tif (thin) {\n+\t\t\texpectedObjects = new ObjectId[4];\n+\t\t\tSystem.arraycopy(writtenObjects, 0, expectedObjects, 0,\n+\t\t\t\t\twrittenObjects.length);\n+\t\t\texpectedObjects[3] = ObjectId\n+\t\t\t\t\t.fromString(\"6ff87c4664981e4397625791c8ea3bbb5f2279a3\");\n+\n+\t\t} else {\n+\t\t\texpectedObjects = writtenObjects;\n+\t\t}\n+\t\tverifyObjectsOrder(expectedObjects);\n+\t\tassertEquals(\"cded4b74176b4456afa456768b2b5aafb41c44fc\", writer\n+\t\t\t\t.computeName().toString());\n+\t}\n+\n+\tprivate void createVerifyOpenPack(final Collection interestings,\n+\t\t\tfinal Collection uninterestings, final boolean thin)\n+\t\t\tthrows MissingObjectException, IOException {\n+\t\twriter.writePack(interestings, uninterestings, thin);\n+\t\tverifyOpenPack(thin);\n+\t}\n+\n+\tprivate void createVerifyOpenPack(final Iterator objectSource)\n+\t\t\tthrows MissingObjectException, IOException {\n+\t\twriter.writePack(objectSource);\n+\t\tverifyOpenPack(false);\n+\t}\n+\n+\tprivate void verifyOpenPack(final boolean thin) throws IOException {\n+\t\tif (thin) {\n+\t\t\tfinal InputStream is = new ByteArrayInputStream(os.toByteArray());\n+\t\t\tfinal IndexPack indexer = new IndexPack(db, is, packBase);\n+\t\t\ttry {\n+\t\t\t\tindexer.index(new TextProgressMonitor());\n+\t\t\t\tfail(\"indexer should grumble about missing object\");\n+\t\t\t} catch (IOException x) {\n+\t\t\t\t// expected\n+\t\t\t}\n+\t\t}\n+\t\tfinal InputStream is = new ByteArrayInputStream(os.toByteArray());\n+\t\tfinal IndexPack indexer = new IndexPack(db, is, packBase);\n+\t\tindexer.setFixThin(thin);\n+\t\tindexer.index(new TextProgressMonitor());\n+\t\tpack = new PackFile(db, indexFile, packFile);\n+\t}\n+\n+\tprivate void verifyObjectsOrder(final ObjectId objectsOrder[]) {\n+\t\tfinal List entries = new ArrayList();\n+\n+\t\tfor (MutableEntry me : pack) {\n+\t\t\tentries.add(me.cloneEntry());\n+\t\t}\n+\t\tCollections.sort(entries, new Comparator() {\n+\t\t\tpublic int compare(MutableEntry o1, MutableEntry o2) {\n+\t\t\t\treturn Long.signum(o1.getOffset() - o2.getOffset());\n+\t\t\t}\n+\t\t});\n+\n+\t\tint i = 0;\n+\t\tfor (MutableEntry me : entries) {\n+\t\t\tassertEquals(objectsOrder[i++], me.copy());\n+\t\t}\n+\t}\n+}\n-- \n1.5.5.1\n"},{"id":"80002","messageId":"20080616040635.GU11793@spearce.org","threadId":"13970","inReplyTo":"1213566349-25395-6-git-send-email-marek.zawirski@gmail.com","subject":"Re: [EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-06-16T04:06:36Z","receivedAt":"2008-06-16T04:06:36Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Marek Zawirski wrote:\n> Let us quickly find ObjectId or next object for specified offset in a\n> pack, in O(log n) time.\n...\n> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n...\n> +\t/**\n> +\t * Object ids corresponding to {@link #offsets32} and {@link #offsets64}.\n> +\t */\n> +\tprivate final int names[];\n\nThis could be smaller if it was an array of indexes into the index,\nrather than the ObjectId itself. Thus we need only 1 int per object\nand not 5 ints per object.\n\nBut I see why you are doing it; PackIndex.MutableEntry exposes the\nObjectId and not the nth position of the object within the index.\n\n> +\tPackReverseIndex(final PackIndex index) {\n> +\t\tfinal long count = index.getObjectCount();\n> +\t\tif (count > Integer.MAX_VALUE)\n> +\t\t\tthrow new IllegalArgumentException(\n> +\t\t\t\t\t\"Huge indexes (> 2^31 entries) are not supported by jgit, yet\");\n\nFor what its worth, this limit is actually:\n\n\tInteger.MAX_VALUE / Constants.OBJECT_ID_LENGTH / 4\n\nas you store the entire ObjectId data for the index in a single int[]\narray called names. So you'll get an ArrayIndexOutOfBoundsException\nor maybe OutOfMemoryError when you try to build names later on, and\nnever really hit this case here.\n\n> +\tObjectId findObject(final long offset) {\n> +\t\tif (offset <= Integer.MAX_VALUE) {\n> +\t\t\tfinal int i32 = Arrays.binarySearch(offsets32, (int) offset);\n> +\t\t\tif (i32 < 0)\n> +\t\t\t\treturn null;\n> +\t\t\tfinal int iNames = i32 * Constants.OBJECT_ID_LENGTH / 4;\n\nThis probably should be:\n\n\tfinal int iNames = i32 * (Constants.OBJECT_ID_LENGTH / 4);\n\nas then we don't overflow the precision of int when i32 is large.\n\n> +\t\t\treturn ObjectId.fromRaw(names, iNames);\n> +\t\t} else {\n> +\t\t\tfinal int i64 = Arrays.binarySearch(offsets64, offset);\n> +\t\t\tif (i64 < 0)\n> +\t\t\t\treturn null;\n> +\t\t\tfinal int iNames = (i64 + offsets32.length)\n> +\t\t\t\t\t* Constants.OBJECT_ID_LENGTH / 4;\n\nAgain, watch out for overflow.\n\n-- \nShawn.\n"},{"id":"80004","messageId":"20080616051927.GV11793@spearce.org","threadId":"13970","inReplyTo":"1213566349-25395-1-git-send-email-marek.zawirski@gmail.com","subject":"Re: [EGIT PATCH 00/20] PackWriter, first usable attempt","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-06-16T05:19:27Z","receivedAt":"2008-06-16T05:19:27Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Marek Zawirski wrote:\n> At first, some stuff was still missing to produce packs, mostly\n> raw-data access related and ObjectWalk related.\n\nI'm glad it turned out to be so little missing actually. Reusing\nObjectWalk saved a lot of code in the pack writer, and for the most\npart our existing data access structures were already well organized.\n\nIt is too early to say how the performance is going to work, but\nobject packing with delta reuse can be difficult and I'm happy to\nsee that our abstractions more-or-less supported it. Tuning can\ncome later, once we better understand the code, and have something\nfor end-users to complain (or praise) about.\n \n> Finally, we've got some support for pack writing! It's not that\n> power that C git version offers, but something usable. Delta\n> generation is not supported. Although we can reuse deltas and objects,\n> and support all other (I hope) options of git-pack-objects directly or\n> indirectly, most importantly --thin.\n> \n> Pack writing and some other features are tested, seem to work.\n> \n> This implementation of packing is not a very valuable thing directly\n> (achieving efficient storage), however it's a base for enhancements\n> and can be used for sending packs over net (with some assumptions).\n> It's more a \"repacking\" than \"packing\" tool.\n\nYup. The critical part here is jgit can now format a pack file,\nwhich means we can now actually implement native push over the\nlocal pipe (to fork+exec'd git-receive-pack) or over SSH. That\nis one of the major missing features in the Eclipse plugin, so\nthis is a huge milestone for us. Thank you Marek.\n\n> So... I'm switching now to push implementation. If time allows,\n> delta-algorithms will be added later.\n\nYay.\n\nNative push protocol support at this point is much more important\nthan delta generation. Although delta generation is one of the\nkey features that makes git so damn efficient it is pointless if we\ncannot actually communicate with a remote repository to send them\nour changes. Early adopters of the push support coming from this\nplugin can at least use it on local area networks, where bandwidth\nis not (usually) a limiting factor.\n\n> 28 files changed, 2258 insertions(+), 73 deletions(-)\n\nNice to see it didn't take that much code either.\n\n-- \nShawn.\n"},{"id":"80046","messageId":"48569460.4000401@gmail.com","threadId":"13970","inReplyTo":"20080616040635.GU11793@spearce.org","subject":"Re: [EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-16T16:27:12Z","receivedAt":"2008-06-16T16:27:12Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Shawn O. Pearce wrote:\n> Marek Zawirski wrote:\n>> Let us quickly find ObjectId or next object for specified offset in a\n>> pack, in O(log n) time.\n> ...\n>> diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n> ...\n>> +\t/**\n>> +\t * Object ids corresponding to {@link #offsets32} and {@link #offsets64}.\n>> +\t */\n>> +\tprivate final int names[];\n> \n> This could be smaller if it was an array of indexes into the index,\n> rather than the ObjectId itself. Thus we need only 1 int per object\n> and not 5 ints per object.\n> \n> But I see why you are doing it; PackIndex.MutableEntry exposes the\n> ObjectId and not the nth position of the object within the index.\n\nHmm, that's smart.\nI can change array of names to second level indices, but I think that in \nsuch a case PackReverseIndex should be an inner class of PackIndex and \nsome refactor/additional assumptions at PackIndex may be needed. What do \nyou think?\n\n>> +\tPackReverseIndex(final PackIndex index) {\n>> +\t\tfinal long count = index.getObjectCount();\n>> +\t\tif (count > Integer.MAX_VALUE)\n>> +\t\t\tthrow new IllegalArgumentException(\n>> +\t\t\t\t\t\"Huge indexes (> 2^31 entries) are not supported by jgit, yet\");\n> \n> For what its worth, this limit is actually:\n> \n> \tInteger.MAX_VALUE / Constants.OBJECT_ID_LENGTH / 4\n> \n> as you store the entire ObjectId data for the index in a single int[]\n> array called names. So you'll get an ArrayIndexOutOfBoundsException\n> or maybe OutOfMemoryError when you try to build names later on, and\n> never really hit this case here.\n>> +\tObjectId findObject(final long offset) {\n>> +\t\tif (offset <= Integer.MAX_VALUE) {\n>> +\t\t\tfinal int i32 = Arrays.binarySearch(offsets32, (int) offset);\n>> +\t\t\tif (i32 < 0)\n>> +\t\t\t\treturn null;\n>> +\t\t\tfinal int iNames = i32 * Constants.OBJECT_ID_LENGTH / 4;\n> \n> This probably should be:\n> \n> \tfinal int iNames = i32 * (Constants.OBJECT_ID_LENGTH / 4);\n> \n> as then we don't overflow the precision of int when i32 is large.\n> \n>> +\t\t\treturn ObjectId.fromRaw(names, iNames);\n>> +\t\t} else {\n>> +\t\t\tfinal int i64 = Arrays.binarySearch(offsets64, offset);\n>> +\t\t\tif (i64 < 0)\n>> +\t\t\t\treturn null;\n>> +\t\t\tfinal int iNames = (i64 + offsets32.length)\n>> +\t\t\t\t\t* Constants.OBJECT_ID_LENGTH / 4;\n> \n> Again, watch out for overflow.\n\nRight, my faults.\n\n-- \nMarek Zawirski [zawir]\nmarek.zawirski@gmail.com\n"},{"id":"80047","messageId":"485696BE.4010608@gmail.com","threadId":"13970","inReplyTo":"20080616051927.GV11793@spearce.org","subject":"Re: [EGIT PATCH 00/20] PackWriter, first usable attempt","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-16T16:37:18Z","receivedAt":"2008-06-16T16:37:18Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Shawn O. Pearce wrote:\n> Marek Zawirski wrote:\n>> At first, some stuff was still missing to produce packs, mostly\n>> raw-data access related and ObjectWalk related.\n> \n> I'm glad it turned out to be so little missing actually. Reusing\n> ObjectWalk saved a lot of code in the pack writer, and for the most\n> part our existing data access structures were already well organized.\n\nYeah, I actually expected that this feature implementation would cause \nmore changes. But existence of transport and rev-walking frameworks in \njgit helped a lot. Jgit code changed significantly between my first look \nat it (march/april) and GSoC start date.\n\n(...)\n>> Finally, we've got some support for pack writing! It's not that\n>> power that C git version offers, but something usable. Delta\n>> generation is not supported. Although we can reuse deltas and objects,\n>> and support all other (I hope) options of git-pack-objects directly or\n>> indirectly, most importantly --thin.\n>>\n>> Pack writing and some other features are tested, seem to work.\n>>\n>> This implementation of packing is not a very valuable thing directly\n>> (achieving efficient storage), however it's a base for enhancements\n>> and can be used for sending packs over net (with some assumptions).\n>> It's more a \"repacking\" than \"packing\" tool.\n> \n> Yup. The critical part here is jgit can now format a pack file,\n> which means we can now actually implement native push over the\n> local pipe (to fork+exec'd git-receive-pack) or over SSH. That\n> is one of the major missing features in the Eclipse plugin, so\n> this is a huge milestone for us. Thank you Marek.\n\nHey, I'm here for doing this, they even pay me for that fun;)\n\n-- \nMarek Zawirski [zawir]\nmarek.zawirski@gmail.com\n"},{"id":"80098","messageId":"20080617020242.GW11793@spearce.org","threadId":"13970","inReplyTo":"48569460.4000401@gmail.com","subject":"Re: [EGIT PATCH 05/20] Reverse pack index implementation: PackReverseIndex","fromName":"Shawn O. Pearce","fromEmail":"spearce@spearce.org","sentAt":"2008-06-17T02:02:42Z","receivedAt":"2008-06-17T02:02:42Z","isPatch":true,"sender":{"key":"spearce@spearce.org","avatar":"https://avatars.githubusercontent.com/u/34844?v=4"},"body":"Marek Zawirski wrote:\n> Shawn O. Pearce wrote:\n> >Marek Zawirski wrote:\n> >>Let us quickly find ObjectId or next object for specified offset in a\n> >>pack, in O(log n) time.\n...\n> >This could be smaller if it was an array of indexes into the index,\n> >rather than the ObjectId itself. Thus we need only 1 int per object\n> >and not 5 ints per object.\n> \n> Hmm, that's smart.\n> I can change array of names to second level indices, but I think that in \n> such a case PackReverseIndex should be an inner class of PackIndex and \n> some refactor/additional assumptions at PackIndex may be needed. What do \n> you think?\n\nSo I coded this up today. It can either squash to this patch I\nam replying to, or maybe follow-on in the series.\n\nThe advantage of this change is we use the minimum amount of memory\npossible to build the reverse index. The disadvantage is the\nconstruction of the reverse index now runs in O(N + 2 * (N log N)),\nwhere the prior version was O(N + N log N), ignoring all GC costs.\n\nWe could be doing worse here, but I suspect the additional running\ntime is better than the memory usage from cloning every MutableEntry\nduring traversal. GC costs are not free.\n\nWith this patch ObjectId lookup is still constant time, though\nwe do perform a binary search on a 256 element array. log 256 is\nstill a constant, even though it is not 1. :-)\n\nWe support up to 2^32 objects per index, which is the limit of the\nfile format, however we only support the first 2 billion objects\nbeing in the first 2 GB of the pack file. Given that each object\nneeds _at least_ two bytes of data the first 2 billion objects will\neasily require the first 4 GB of the pack file, pushing us into the\noffsets64 table. Which is then itself limited to 2 billion objects.\nSo our real limit here is we cannot have more than 2 billion objects\nrequiring 64 bit offsets. But PackIndexV2 only supports (2**31-1)/8\nsuch 64 bit offsets so we'll blow that out long before we blow the\nPackReverseIndex limits.\n\nYes, PackIndexV2 is currently limited by its implementation and\nnot by what the file format would permit.\n\n\n--8<--\nImproved PackReverseIndex\n\n---\n .../src/org/spearce/jgit/lib/PackIndex.java | 57 ++++++++++++++\n .../src/org/spearce/jgit/lib/PackIndexV1.java | 38 +++++++++-\n .../src/org/spearce/jgit/lib/PackIndexV2.java | 33 ++++++++-\n .../src/org/spearce/jgit/lib/PackReverseIndex.java | 82 +++++++++++---------\n 4 files changed, 170 insertions(+), 40 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\nindex 3935d4f..6debf3b 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java\n@@ -140,6 +140,63 @@ public abstract class PackIndex implements Iterable {\n \tabstract long getObjectCount();\n \n \t/**\n+\t * Obtain the total number of objects needing 64 bit offsets.\n+\t * \n+\t * @return number of objects in this index using a 64 bit offset; that is an\n+\t * object positioned after the 2 GB position within the file.\n+\t */\n+\tabstract long getOffset64Count();\n+\n+\t/**\n+\t * Get ObjectId for the n-th object entry returned by {@link #iterator()}.\n+\t *

\n+\t * This method is a constant-time replacement for the following loop:\n+\t * \n+\t * 

\n+\t * Iterator<MutableEntry> eItr = index.iterator();\n+\t * int curPosition = 0;\n+\t * while (eItr.hasNext() && curPosition++ < nthPosition)\n+\t * \teItr.next();\n+\t * ObjectId result = eItr.next().toObjectId();\n+\t *
\n+\t * \n+\t * @param nthPosition\n+\t * position within the traversal of {@link #iterator()} that the\n+\t * caller needs the object for. The first returned\n+\t * {@link MutableEntry} is 0, the second is 1, etc.\n+\t * @return the ObjectId for the corresponding entry.\n+\t */\n+\tabstract ObjectId getObjectId(long nthPosition);\n+\n+\t/**\n+\t * Get ObjectId for the n-th object entry returned by {@link #iterator()}.\n+\t *

\n+\t * This method is a constant-time replacement for the following loop:\n+\t * \n+\t * 

\n+\t * Iterator<MutableEntry> eItr = index.iterator();\n+\t * int curPosition = 0;\n+\t * while (eItr.hasNext() && curPosition++ < nthPosition)\n+\t * \teItr.next();\n+\t * ObjectId result = eItr.next().toObjectId();\n+\t *
\n+\t * \n+\t * @param nthPosition\n+\t * unsigned 32 bit position within the traversal of\n+\t * {@link #iterator()} that the caller needs the object for. The\n+\t * first returned {@link MutableEntry} is 0, the second is 1,\n+\t * etc. Positions past 2**31-1 are negative, but still valid.\n+\t * @return the ObjectId for the corresponding entry.\n+\t */\n+\tfinal ObjectId getObjectId(final int nthPosition) {\n+\t\tif (nthPosition >= 0)\n+\t\t\treturn getObjectId((long) nthPosition);\n+\t\tfinal int u31 = nthPosition >>> 1;\n+\t\tfinal int one = nthPosition & 1;\n+\t\treturn getObjectId(((long) u31) << 1 | one);\n+\t}\n+\n+\t/**\n \t * Locate the file offset position for the requested object.\n \t * \n \t * @param objId\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\nindex b8d9de3..b58dfdf 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java\n@@ -40,6 +40,7 @@ package org.spearce.jgit.lib;\n \n import java.io.IOException;\n import java.io.InputStream;\n+import java.util.Arrays;\n import java.util.Iterator;\n import java.util.NoSuchElementException;\n \n@@ -49,6 +50,8 @@ import org.spearce.jgit.util.NB;\n class PackIndexV1 extends PackIndex {\n \tprivate static final int IDX_HDR_LEN = 256 * 4;\n \n+\tprivate final long[] idxHeader;\n+\n \tprivate byte[][] idxdata;\n \n \tprivate long objectCnt;\n@@ -59,7 +62,7 @@ class PackIndexV1 extends PackIndex {\n \t\tSystem.arraycopy(hdr, 0, fanoutTable, 0, hdr.length);\n \t\tNB.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length);\n \n-\t\tfinal long[] idxHeader = new long[256]; // really unsigned 32-bit...\n+\t\tidxHeader = new long[256]; // really unsigned 32-bit...\n \t\tfor (int k = 0; k < idxHeader.length; k++)\n \t\t\tidxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4);\n \t\tidxdata = new byte[idxHeader.length][];\n@@ -82,6 +85,39 @@ class PackIndexV1 extends PackIndex {\n \t\treturn objectCnt;\n \t}\n \n+\t@Override\n+\tlong getOffset64Count() {\n+\t\tlong n64 = 0;\n+\t\tfor (final MutableEntry e : this) {\n+\t\t\tif (e.getOffset() >= Integer.MAX_VALUE)\n+\t\t\t\tn64++;\n+\t\t}\n+\t\treturn n64;\n+\t}\n+\n+\t@Override\n+\tObjectId getObjectId(final long nthPosition) {\n+\t\tint levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);\n+\t\tlong base;\n+\t\tif (levelOne >= 0) {\n+\t\t\t// If we hit the bucket exactly the item is in the bucket, or\n+\t\t\t// any bucket before it which has the same object count.\n+\t\t\t//\n+\t\t\tbase = idxHeader[levelOne];\n+\t\t\twhile (levelOne > 0 && base == idxHeader[levelOne - 1])\n+\t\t\t\tlevelOne--;\n+\t\t} else {\n+\t\t\t// The item is in the bucket we would insert it into.\n+\t\t\t//\n+\t\t\tlevelOne = -(levelOne + 1);\n+\t\t}\n+\n+\t\tbase = levelOne > 0 ? idxHeader[levelOne - 1] : 0;\n+\t\tfinal int p = (int) (nthPosition - base);\n+\t\tfinal int dataIdx = ((4 + Constants.OBJECT_ID_LENGTH) * p) + 4;\n+\t\treturn ObjectId.fromRaw(idxdata[levelOne], dataIdx);\n+\t}\n+\n \tlong findOffset(final AnyObjectId objId) {\n \t\tfinal int levelOne = objId.getFirstByte();\n \t\tbyte[] data = idxdata[levelOne];\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\nindex ae70f11..8b2c6d6 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java\n@@ -40,6 +40,7 @@ package org.spearce.jgit.lib;\n import java.io.EOFException;\n import java.io.IOException;\n import java.io.InputStream;\n+import java.util.Arrays;\n import java.util.Iterator;\n import java.util.NoSuchElementException;\n \n@@ -57,6 +58,8 @@ class PackIndexV2 extends PackIndex {\n \n \tprivate long objectCnt;\n \n+\tprivate final long[] fanoutTable;\n+\n \t/** 256 arrays of contiguous object names. */\n \tprivate int[][] names;\n \n@@ -69,7 +72,7 @@ class PackIndexV2 extends PackIndex {\n \tPackIndexV2(final InputStream fd) throws IOException {\n \t\tfinal byte[] fanoutRaw = new byte[4 * FANOUT];\n \t\tNB.readFully(fd, fanoutRaw, 0, fanoutRaw.length);\n-\t\tfinal long[] fanoutTable = new long[FANOUT];\n+\t\tfanoutTable = new long[FANOUT];\n \t\tfor (int k = 0; k < FANOUT; k++)\n \t\t\tfanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);\n \t\tobjectCnt = fanoutTable[FANOUT - 1];\n@@ -151,6 +154,34 @@ class PackIndexV2 extends PackIndex {\n \t}\n \n \t@Override\n+\tlong getOffset64Count() {\n+\t\treturn offset64.length / 8;\n+\t}\n+\n+\t@Override\n+\tObjectId getObjectId(final long nthPosition) {\n+\t\tint levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);\n+\t\tlong base;\n+\t\tif (levelOne >= 0) {\n+\t\t\t// If we hit the bucket exactly the item is in the bucket, or\n+\t\t\t// any bucket before it which has the same object count.\n+\t\t\t//\n+\t\t\tbase = fanoutTable[levelOne];\n+\t\t\twhile (levelOne > 0 && base == fanoutTable[levelOne - 1])\n+\t\t\t\tlevelOne--;\n+\t\t} else {\n+\t\t\t// The item is in the bucket we would insert it into.\n+\t\t\t//\n+\t\t\tlevelOne = -(levelOne + 1);\n+\t\t}\n+\n+\t\tbase = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;\n+\t\tfinal int p = (int) (nthPosition - base);\n+\t\tfinal int p4 = p << 2;\n+\t\treturn ObjectId.fromRaw(names[levelOne], p4 + p); // p * 5\n+\t}\n+\n+\t@Override\n \tlong findOffset(final AnyObjectId objId) {\n \t\tfinal int levelOne = objId.getFirstByte();\n \t\tfinal int[] data = names[levelOne];\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\nindex 3dede88..bac7477 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackReverseIndex.java\n@@ -38,7 +38,6 @@\n package org.spearce.jgit.lib;\n \n import java.util.Arrays;\n-import java.util.Comparator;\n \n import org.spearce.jgit.errors.CorruptObjectException;\n import org.spearce.jgit.lib.PackIndex.MutableEntry;\n@@ -54,6 +53,9 @@ import org.spearce.jgit.lib.PackIndex.MutableEntry;\n * @see PackFile\n */\n class PackReverseIndex {\n+\t/** Index we were created from, and that has our ObjectId data. */\n+\tprivate final PackIndex index;\n+\n \t/**\n \t * (offset31, truly) Offsets accommodating in 31 bits.\n \t */\n@@ -64,48 +66,55 @@ class PackReverseIndex {\n \t */\n \tprivate final long offsets64[];\n \n-\t/**\n-\t * Object ids corresponding to {@link #offsets32} and {@link #offsets64}.\n-\t */\n-\tprivate final int names[];\n+\t/** Position of the corresponding {@link #offsets32} in {@link #index}. */\n+\tprivate final int nth32[];\n+\n+\t/** Position of the corresponding {@link #offsets64} in {@link #index}. */\n+\tprivate final int nth64[];\n \n \t/**\n \t * Create reverse index from straight/forward pack index, by indexing all\n \t * its entries.\n \t * \n-\t * @param index\n+\t * @param packIndex\n \t * forward index - entries to (reverse) index.\n \t */\n-\tPackReverseIndex(final PackIndex index) {\n-\t\tfinal long count = index.getObjectCount();\n-\t\tif (count > Integer.MAX_VALUE)\n+\tPackReverseIndex(final PackIndex packIndex) {\n+\t\tindex = packIndex;\n+\n+\t\tfinal long cnt = index.getObjectCount();\n+\t\tfinal long n64 = index.getOffset64Count();\n+\t\tfinal long n32 = cnt - n64;\n+\t\tif (n32 > Integer.MAX_VALUE || n64 > Integer.MAX_VALUE\n+\t\t\t\t|| cnt > 0xffffffffL)\n \t\t\tthrow new IllegalArgumentException(\n-\t\t\t\t\t\"Huge indexes (> 2^31 entries) are not supported by jgit, yet\");\n-\n-\t\tfinal MutableEntry entries[] = new MutableEntry[(int) count];\n-\t\tint i = 0;\n-\t\tint count32 = 0;\n-\t\tfor (MutableEntry me : index) {\n-\t\t\tentries[i++] = me.cloneEntry();\n-\t\t\tif (me.getOffset() <= Integer.MAX_VALUE)\n-\t\t\t\tcount32++;\n+\t\t\t\t\t\"Huge indexes are not supported by jgit, yet\");\n+\n+\t\toffsets32 = new int[(int) n32];\n+\t\toffsets64 = new long[(int) n64];\n+\t\tnth32 = new int[offsets32.length];\n+\t\tnth64 = new int[offsets64.length];\n+\n+\t\tint i32 = 0;\n+\t\tint i64 = 0;\n+\t\tfor (final MutableEntry me : index) {\n+\t\t\tfinal long o = me.getOffset();\n+\t\t\tif (o < Integer.MAX_VALUE)\n+\t\t\t\toffsets32[i32++] = (int) o;\n+\t\t\telse\n+\t\t\t\toffsets64[i64++] = o;\n \t\t}\n-\t\tArrays.sort(entries, new Comparator() {\n-\t\t\tpublic int compare(MutableEntry o1, MutableEntry o2) {\n-\t\t\t\treturn Long.signum(o1.getOffset() - o2.getOffset());\n-\t\t\t}\n-\t\t});\n-\n-\t\tnames = new int[entries.length * Constants.OBJECT_ID_LENGTH / 4];\n-\t\toffsets32 = new int[count32];\n-\t\toffsets64 = new long[entries.length - count32];\n-\t\tfor (int j = 0, j32 = 0; j < entries.length; j++) {\n-\t\t\tfinal long offset = entries[j].getOffset();\n-\t\t\tif (offset <= Integer.MAX_VALUE)\n-\t\t\t\toffsets32[j32++] = (int) offset;\n+\n+\t\tArrays.sort(offsets32);\n+\t\tArrays.sort(offsets64);\n+\n+\t\tint nth = 0;\n+\t\tfor (final MutableEntry me : index) {\n+\t\t\tfinal long o = me.getOffset();\n+\t\t\tif (o < Integer.MAX_VALUE)\n+\t\t\t\tnth32[Arrays.binarySearch(offsets32, (int) o)] = nth++;\n \t\t\telse\n-\t\t\t\toffsets64[j - j32] = offset;\n-\t\t\tentries[j].copyRawTo(names, j * Constants.OBJECT_ID_LENGTH / 4);\n+\t\t\t\tnth64[Arrays.binarySearch(offsets64, o)] = nth++;\n \t\t}\n \t}\n \n@@ -122,15 +131,12 @@ class PackReverseIndex {\n \t\t\tfinal int i32 = Arrays.binarySearch(offsets32, (int) offset);\n \t\t\tif (i32 < 0)\n \t\t\t\treturn null;\n-\t\t\tfinal int iNames = i32 * Constants.OBJECT_ID_LENGTH / 4;\n-\t\t\treturn ObjectId.fromRaw(names, iNames);\n+\t\t\treturn index.getObjectId(nth32[i32]);\n \t\t} else {\n \t\t\tfinal int i64 = Arrays.binarySearch(offsets64, offset);\n \t\t\tif (i64 < 0)\n \t\t\t\treturn null;\n-\t\t\tfinal int iNames = (i64 + offsets32.length)\n-\t\t\t\t\t* Constants.OBJECT_ID_LENGTH / 4;\n-\t\t\treturn ObjectId.fromRaw(names, iNames);\n+\t\t\treturn index.getObjectId(nth64[i64]);\n \t\t}\n \t}\n \n-- \n1.5.6.rc2.181.gbb495\n\n\n-- \nShawn.\n"},{"id":"80164","messageId":"1213738134-6221-1-git-send-email-marek.zawirski@gmail.com","threadId":"13970","inReplyTo":"1213566349-25395-20-git-send-email-marek.zawirski@gmail.com","subject":"[EGIT PATCH 21/20] Make isBetterDeltaReuseLoader() static in PackWriter","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-17T21:28:54Z","receivedAt":"2008-06-17T21:28:54Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Implementation was already static, it's just a fix for clarity and\npotential speed-up.\n\nReported-by: Shawn O. Pearce \nSigned-off-by: Marek Zawirski \n---\nIt could be squashed with patch 19/20. I can clean up this mess, adding \nalso Shawn's patch - just let me know what is preferred way (squash\ncommits, commits on top?).\n\n .../src/org/spearce/jgit/lib/PackWriter.java | 5 +++--\n 1 files changed, 3 insertions(+), 2 deletions(-)\n\ndiff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\nindex 18d3ec2..ba43da5 100644\n--- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n+++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackWriter.java\n@@ -543,8 +543,9 @@ public class PackWriter {\n \t\t}\n \t}\n \n-\tprivate boolean isBetterDeltaReuseLoader(PackedObjectLoader currentLoader,\n-\t\t\tPackedObjectLoader loader) throws IOException {\n+\tprivate static boolean isBetterDeltaReuseLoader(\n+\t\t\tPackedObjectLoader currentLoader, PackedObjectLoader loader)\n+\t\t\tthrows IOException {\n \t\tif (currentLoader == null)\n \t\t\treturn true;\n \t\tif (loader.getRawSize() < currentLoader.getRawSize())\n-- \n1.5.5.1\n"},{"id":"80172","messageId":"200806180007.01061.robin.rosenberg.lists@dewire.com","threadId":"13970","inReplyTo":"1213738134-6221-1-git-send-email-marek.zawirski@gmail.com","subject":"Re: [EGIT PATCH 21/20] Make isBetterDeltaReuseLoader() static in PackWriter","fromName":"Robin Rosenberg","fromEmail":"robin.rosenberg.lists@dewire.com","sentAt":"2008-06-17T22:07:00Z","receivedAt":"2008-06-17T22:07:00Z","isPatch":true,"sender":{"key":"robin.rosenberg@dewire.com","avatar":"https://avatars.githubusercontent.com/u/46357?v=4"},"body":"tisdagen den 17 juni 2008 23.28.54 skrev Marek Zawirski:\n> Implementation was already static, it's just a fix for clarity and\n> potential speed-up.\n> \n> Reported-by: Shawn O. Pearce \n> Signed-off-by: Marek Zawirski \n> ---\n> It could be squashed with patch 19/20. I can clean up this mess, adding \n> also Shawn's patch - just let me know what is preferred way (squash\n> commits, commits on top?).\n\nIf the code is already merged then patch on top, else squashing or rebase,\nunless you feel there is a reason not to. We can pretend it was right from\nthe start :) I see no educational value in having a separate patch in this case.\n\n-- robin\n"},{"id":"80329","messageId":"485A88D3.9020901@gmail.com","threadId":"13970","inReplyTo":"200806180007.01061.robin.rosenberg.lists@dewire.com","subject":"Re: [EGIT PATCH 21/20] Make isBetterDeltaReuseLoader() static in PackWriter","fromName":"Marek Zawirski","fromEmail":"marek.zawirski@gmail.com","sentAt":"2008-06-19T16:26:59Z","receivedAt":"2008-06-19T16:26:59Z","isPatch":true,"sender":{"key":"marek.zawirski@gmail.com","avatar":null},"body":"Robin Rosenberg wrote:\n> tisdagen den 17 juni 2008 23.28.54 skrev Marek Zawirski:\n>> Implementation was already static, it's just a fix for clarity and\n>> potential speed-up.\n>>\n>> Reported-by: Shawn O. Pearce \n>> Signed-off-by: Marek Zawirski \n>> ---\n>> It could be squashed with patch 19/20. I can clean up this mess, adding \n>> also Shawn's patch - just let me know what is preferred way (squash\n>> commits, commits on top?).\n> \n> If the code is already merged then patch on top, else squashing or rebase,\n> unless you feel there is a reason not to. We can pretend it was right from\n> the start :) \n\nSo let's pretend that...\nI have squashed these 2 additional patches (Shawn's improvement for \nreverse index and my minor fix) into appropriate commits. \"packwriter\" \nbranch was updated (non fast-forward):\nhttp://repo.or.cz/w/egit/zawir.git?a=shortlog;h=refs/heads/packwriter\n\n > I see no educational value in having a separate patch in this case.\n\nThe only educational value was to type Reported-by on my own ;)\n\n\n-- \nMarek Zawirski [zawir]\nmarek.zawirski@gmail.com\n"}]}