[JGIT PATCH 11/12] Entries iterator in PackIndex and indirectly PackFile

[Marek Zawirski <marek.zawirski@gmail.com>]

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 <marek.zawirski@gmail.com>
---
 .../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 84562aa..1b2c167 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<PackIndex.MutableEntry> {
 	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.
+	 * <p>
+	 * Iterator returns objects in SHA-1 lexicographical order.
+	 * </p>
+	 * 
+	 * @return iterator over entries of associated pack index
+	 * 
+	 * @see PackIndex#iterator()
+	 */
+	public Iterator<PackIndex.MutableEntry> 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 104c361..3935d4f 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 <spearce@spearce.org>
+ * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
  *
  * 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.
  * </p>
  */
-public abstract class PackIndex {
+public abstract class PackIndex implements Iterable<PackIndex.MutableEntry> {
 	/**
 	 * Open an existing pack <code>.idx</code> file for reading.
 	 * <p>
@@ -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.
+	 * <p>
+	 * Iterator returns objects in SHA-1 lexicographical order.
+	 * </p>
+	 * 
+	 * @return iterator over pack index entries
+	 */
+	public abstract Iterator<MutableEntry> 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<MutableEntry> {
+		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 cfd18da..b8d9de3 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<MutableEntry> 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 b1b4d73..9a695ef 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<MutableEntry> 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();
+		}
+	}
+
 }
-- 
1.5.5.1