From b06e934780fcacc8e68ab34533c5071633569e9e Mon Sep 17 00:00:00 2001 From: Marek Zawirski Date: Mon, 2 Jun 2008 10:00:28 +0200 Subject: [PATCH] Entries iterator in PackIndex and indirectly PackFile New iterators operate on MutableEntry to achieve high performance. Information about objects (and its offset) in pack is needed in several places in original git, and it will be also useful here. Signed-off-by: Marek Zawirski --- .../src/org/spearce/jgit/lib/PackFile.java | 19 ++++- .../src/org/spearce/jgit/lib/PackIndex.java | 80 +++++++++++++++++++++- .../src/org/spearce/jgit/lib/PackIndexV1.java | 31 +++++++++ .../src/org/spearce/jgit/lib/PackIndexV2.java | 36 ++++++++++ 4 files changed, 164 insertions(+), 2 deletions(-) diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java index 84562aa8..1b2c167d 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackFile.java @@ -40,6 +40,7 @@ package org.spearce.jgit.lib; import java.io.File; import java.io.IOException; +import java.util.Iterator; import java.util.zip.DataFormatException; import org.spearce.jgit.util.NB; @@ -49,7 +50,7 @@ import org.spearce.jgit.util.NB; * delta packed format yielding high compression of lots of object where some * objects are similar. */ -public class PackFile { +public class PackFile implements Iterable { private final WindowedFile pack; private final PackIndex idx; @@ -146,6 +147,22 @@ public class PackFile { } /** + * Provide iterator over entries in associated pack index, that should also + * exist in this pack file. Objects returned by such iterator are mutable + * during iteration. + *

+ * Iterator returns objects in SHA-1 lexicographical order. + *

+ * + * @return iterator over entries of associated pack index + * + * @see PackIndex#iterator() + */ + public Iterator iterator() { + return idx.iterator(); + } + + /** * Obtain the total number of objects available in this pack. This method * relies on pack index, giving number of effectively available objects. * diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java index 104c361e..3935d4f8 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java @@ -1,5 +1,6 @@ /* * Copyright (C) 2008, Shawn O. Pearce + * Copyright (C) 2008, Marek Zawirski * * All rights reserved. * @@ -41,6 +42,7 @@ import java.io.File; import java.io.FileInputStream; import java.io.FileNotFoundException; import java.io.IOException; +import java.util.Iterator; import org.spearce.jgit.util.NB; @@ -53,7 +55,7 @@ import org.spearce.jgit.util.NB; * by ObjectId. *

*/ -public abstract class PackIndex { +public abstract class PackIndex implements Iterable { /** * Open an existing pack .idx file for reading. *

@@ -117,6 +119,19 @@ public abstract class PackIndex { } /** + * Provide iterator that gives access to index entries. Note, that iterator + * returns reference to mutable object, the same reference in each call - + * for performance reason. If client needs immutable objects, it must copy + * returned object on its own. + *

+ * Iterator returns objects in SHA-1 lexicographical order. + *

+ * + * @return iterator over pack index entries + */ + public abstract Iterator iterator(); + + /** * Obtain the total number of objects described by this index. * * @return number of objects in this index, and likewise in the associated @@ -134,4 +149,67 @@ public abstract class PackIndex { * associated pack. */ abstract long findOffset(AnyObjectId objId); + + /** + * Represent mutable entry of pack index consisting of object id and offset + * in pack (both mutable). + * + */ + public static class MutableEntry extends MutableObjectId { + private long offset; + + /** + * Empty constructor. Object fields should be filled in later. + */ + public MutableEntry() { + super(); + } + + /** + * Returns offset for this index object entry + * + * @return offset of this object in a pack file + */ + public long getOffset() { + return offset; + } + + void setOffset(long offset) { + this.offset = offset; + } + + private MutableEntry(MutableEntry src) { + super(src); + this.offset = src.offset; + } + + /** + * Returns mutable copy of this mutable entry. + * + * @return copy of this mutable entry + */ + public MutableEntry cloneEntry() { + return new MutableEntry(this); + } + } + + protected abstract class EntriesIterator implements Iterator { + protected MutableEntry objectId = new MutableEntry(); + + protected long returnedNumber = 0; + + public boolean hasNext() { + return returnedNumber < getObjectCount(); + } + + /** + * Implementation must update {@link #returnedNumber} before returning + * element. + */ + public abstract MutableEntry next(); + + public void remove() { + throw new UnsupportedOperationException(); + } + } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java index cfd18da5..b8d9de33 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV1.java @@ -40,6 +40,8 @@ package org.spearce.jgit.lib; import java.io.IOException; import java.io.InputStream; +import java.util.Iterator; +import java.util.NoSuchElementException; import org.spearce.jgit.errors.CorruptObjectException; import org.spearce.jgit.util.NB; @@ -104,4 +106,33 @@ class PackIndexV1 extends PackIndex { } while (low < high); return -1; } + + public Iterator iterator() { + return new IndexV1Iterator(); + } + + private class IndexV1Iterator extends EntriesIterator { + private int levelOne; + + private int levelTwo; + + public MutableEntry next() { + for (; levelOne < idxdata.length; levelOne++) { + if (idxdata[levelOne] == null) + continue; + + if (levelTwo < idxdata[levelOne].length) { + long offset = NB.decodeUInt32(idxdata[levelOne], levelTwo); + objectId.setOffset(offset); + objectId.fromRaw(idxdata[levelOne], levelTwo + 4); + levelTwo += Constants.OBJECT_ID_LENGTH + 4; + returnedNumber++; + return objectId; + } else { + levelTwo = 0; + } + } + throw new NoSuchElementException(); + } + } } diff --git a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java index b1b4d73f..9a695ef5 100644 --- a/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java +++ b/org.spearce.jgit/src/org/spearce/jgit/lib/PackIndexV2.java @@ -40,6 +40,8 @@ package org.spearce.jgit.lib; import java.io.EOFException; import java.io.IOException; import java.io.InputStream; +import java.util.Iterator; +import java.util.NoSuchElementException; import org.spearce.jgit.util.NB; @@ -174,4 +176,38 @@ class PackIndexV2 extends PackIndex { } while (low < high); return -1; } + + public Iterator iterator() { + return new EntriesIteratorV2(); + } + + private class EntriesIteratorV2 extends EntriesIterator { + private int levelOne; + + private int levelTWo; + + public MutableEntry next() { + for (; levelOne < names.length; levelOne++) { + if (levelTWo < names[levelOne].length) { + objectId.fromRaw(names[levelOne], levelTWo); + int arrayIdx = levelTWo / (Constants.OBJECT_ID_LENGTH / 4) + * 4; + long offset = NB.decodeUInt32(offset32[levelOne], arrayIdx); + if ((offset & IS_O64) != 0) { + arrayIdx = (8 * (int) (offset & ~IS_O64)); + offset = NB.decodeUInt64(offset64, arrayIdx); + } + objectId.setOffset(offset); + + levelTWo += Constants.OBJECT_ID_LENGTH / 4; + returnedNumber++; + return objectId; + } else { + levelTWo = 0; + } + } + throw new NoSuchElementException(); + } + } + } -- 2.11.4.GIT