git/list[1] front-page[2] threads[3] people[4] search[5] about
 

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

From
MZMarek Zawirski <marek.zawirski@gmail.com>
Date
Jun 2, 2008, 21:24 UTC
Message-ID
<1212441883-12990-12-git-send-email-marek.zawirski@gmail.com>
In-Reply-To
<1212441883-12990-11-git-send-email-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
Previous: Marek ZawirskiNext: Marek Zawirski
Message 12 of 24 in “Extensions in core needed by PackWriter”
  1. 00/12 Extensions in core needed by PackWriterMarek Zawirski, Jun 2, 2008
  2. 01/12 Format PackFile classMarek Zawirski, Jun 2, 2008
  3. 02/12 Format PackIndex classMarek Zawirski, Jun 2, 2008
  4. 03/12 Format PackIndexV1 classMarek Zawirski, Jun 2, 2008
  5. 04/12 Add getType() method to RevObject hierarchyMarek Zawirski, Jun 2, 2008
  6. 05/12 Replace instanceof in WalkFetchConnection with getType()Marek Zawirski, Jun 2, 2008
  7. 06/12 Move PackFile.SIGNATURE to Constants.PACK_SIGNATUREMarek Zawirski, Jun 2, 2008
  8. 07/12 Add overload of fromRaw() in MutableObjectId accepting int[]Marek Zawirski, Jun 2, 2008
  9. 08/12 Copying constructor of MutableObjectIdMarek Zawirski, Jun 2, 2008
  10. 09/12 Add getSize() method to ObjectIdSubclassMapMarek Zawirski, Jun 2, 2008
  11. 10/12 Add getObjectCount() method to PackFileMarek Zawirski, Jun 2, 2008
  12. 11/12 Entries iterator in PackIndex and indirectly PackFileMarek Zawirski, Jun 2, 2008
  13. 12/12 Add PackIndex specific tests, currently only iterators testsMarek Zawirski, Jun 2, 2008
  14. Robin RosenbergJun 6, 2008
  15. 09/12 Add size() method to ObjectIdSubclassMapMarek Zawirski, Jun 7, 2008
  16. Robin RosenbergJun 6, 2008
  17. 04/12 Add getType() method to RevObject hierarchyMarek Zawirski, Jun 7, 2008
  18. Johannes SchindelinJun 2, 2008
  19. Marek ZawirskiJun 2, 2008
  20. Johannes SchindelinJun 2, 2008
  21. Robin RosenbergJun 6, 2008
  22. Marek ZawirskiJun 7, 2008
  23. Shawn O. PearceJun 7, 2008
  24. Robin RosenbergJun 10, 2008

Read the whole thread, see it on lore, or plain text.

$ cat FOOTERMessages come from the public archive at lore.kernel.org/git, fetched every hour. The front page is chosen and written each morning by an AI editor and can be wrong; the threads themselves are the record. About and API. For agents: an MCP server at https://gitlist.dev/mcp, and any thread, story or person page as Markdown by adding .md to its URL (or sending Accept: text/markdown). Details in /llms.txt.