org.eclipse.jgit/src/org/eclipse/jgit/lib/PackIndex.java - jgit - Git at Google

 /*
  * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
  * and other copyright owners as documented in the project's IP log.
  *
  * This program and the accompanying materials are made available
  * under the terms of the Eclipse Distribution License v1.0 which
  * accompanies this distribution, is reproduced below, and is
  * available at http://www.eclipse.org/org/documents/edl-v10.php
  *
  * All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or
  * without modification, are permitted provided that the following
  * conditions are met:
  *
  * - Redistributions of source code must retain the above copyright
  *   notice, this list of conditions and the following disclaimer.
  *
  * - Redistributions in binary form must reproduce the above
  *   copyright notice, this list of conditions and the following
  *   disclaimer in the documentation and/or other materials provided
  *   with the distribution.
  *
  * - Neither the name of the Eclipse Foundation, Inc. nor the
  *   names of its contributors may be used to endorse or promote
  *   products derived from this software without specific prior
  *   written permission.
  *
  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  */

 package org.eclipse.jgit.lib;

 import java.io.File;
 import java.io.FileInputStream;
 import java.io.FileNotFoundException;
 import java.io.IOException;
 import java.util.Iterator;

 import org.eclipse.jgit.errors.MissingObjectException;
 import org.eclipse.jgit.util.IO;
 import org.eclipse.jgit.util.NB;

 /**
  * Access path to locate objects by {@link ObjectId} in a {@link PackFile}.
  * <p>
  * Indexes are strictly redundant information in that we can rebuild all of the
  * data held in the index file from the on disk representation of the pack file
  * itself, but it is faster to access for random requests because data is stored
  * by ObjectId.
  * </p>
  */
 public abstract class PackIndex implements Iterable<PackIndex.MutableEntry> {
 	/**
 	 * Open an existing pack <code>.idx</code> file for reading.
 	 * <p>
 	 * The format of the file will be automatically detected and a proper access
 	 * implementation for that format will be constructed and returned to the
 	 * caller. The file may or may not be held open by the returned instance.
 	 * </p>
 	 *
 	 * @param idxFile
 	 *            existing pack .idx to read.
 	 * @return access implementation for the requested file.
 	 * @throws FileNotFoundException
 	 *             the file does not exist.
 	 * @throws IOException
 	 *             the file exists but could not be read due to security errors,
 	 *             unrecognized data version, or unexpected data corruption.
 	 */
 	public static PackIndex open(final File idxFile) throws IOException {
 		final FileInputStream fd = new FileInputStream(idxFile);
 		try {
 			final byte[] hdr = new byte[8];
 			IO.readFully(fd, hdr, 0, hdr.length);
 			if (isTOC(hdr)) {
 				final int v = NB.decodeInt32(hdr, 4);
 				switch (v) {
 				case 2:
 					return new PackIndexV2(fd);
 				default:
 					throw new IOException("Unsupported pack index version " + v);
 				}
 			}
 			return new PackIndexV1(fd, hdr);
 		} catch (IOException ioe) {
 			final String path = idxFile.getAbsolutePath();
 			final IOException err;
 			err = new IOException("Unreadable pack index: " + path);
 			err.initCause(ioe);
 			throw err;
 		} finally {
 			try {
 				fd.close();
 			} catch (IOException err2) {
 				// ignore
 			}
 		}
 	}

 	private static boolean isTOC(final byte[] h) {
 		final byte[] toc = PackIndexWriter.TOC;
 		for (int i = 0; i < toc.length; i++)
 			if (h[i] != toc[i])
 				return false;
 		return true;
 	}

 	/** Footer checksum applied on the bottom of the pack file. */
 	protected byte[] packChecksum;

 	/**
 	 * Determine if an object is contained within the pack file.
 	 *
 	 * @param id
 	 *            the object to look for. Must not be null.
 	 * @return true if the object is listed in this index; false otherwise.
 	 */
 	public boolean hasObject(final AnyObjectId id) {
 		return findOffset(id) != -1;
 	}

 	/**
 	 * 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
 	 *         pack that this index was generated from.
 	 */
 	abstract long getObjectCount();

 	/**
 	 * Obtain the total number of objects needing 64 bit offsets.
 	 *
 	 * @return number of objects in this index using a 64 bit offset; that is an
 	 *         object positioned after the 2 GB position within the file.
 	 */
 	abstract long getOffset64Count();

 	/**
 	 * Get ObjectId for the n-th object entry returned by {@link #iterator()}.
 	 * <p>
 	 * This method is a constant-time replacement for the following loop:
 	 *
 	 * <pre>
 	 * Iterator&lt;MutableEntry&gt; eItr = index.iterator();
 	 * int curPosition = 0;
 	 * while (eItr.hasNext() &amp;&amp; curPosition++ &lt; nthPosition)
 	 * 	eItr.next();
 	 * ObjectId result = eItr.next().toObjectId();
 	 * </pre>
 	 *
 	 * @param nthPosition
 	 *            position within the traversal of {@link #iterator()} that the
 	 *            caller needs the object for. The first returned
 	 *            {@link MutableEntry} is 0, the second is 1, etc.
 	 * @return the ObjectId for the corresponding entry.
 	 */
 	abstract ObjectId getObjectId(long nthPosition);

 	/**
 	 * Get ObjectId for the n-th object entry returned by {@link #iterator()}.
 	 * <p>
 	 * This method is a constant-time replacement for the following loop:
 	 *
 	 * <pre>
 	 * Iterator&lt;MutableEntry&gt; eItr = index.iterator();
 	 * int curPosition = 0;
 	 * while (eItr.hasNext() &amp;&amp; curPosition++ &lt; nthPosition)
 	 * 	eItr.next();
 	 * ObjectId result = eItr.next().toObjectId();
 	 * </pre>
 	 *
 	 * @param nthPosition
 	 *            unsigned 32 bit position within the traversal of
 	 *            {@link #iterator()} that the caller needs the object for. The
 	 *            first returned {@link MutableEntry} is 0, the second is 1,
 	 *            etc. Positions past 2**31-1 are negative, but still valid.
 	 * @return the ObjectId for the corresponding entry.
 	 */
 	final ObjectId getObjectId(final int nthPosition) {
 		if (nthPosition >= 0)
 			return getObjectId((long) nthPosition);
 		final int u31 = nthPosition >>> 1;
 		final int one = nthPosition & 1;
 		return getObjectId(((long) u31) << 1 | one);
 	}

 	/**
 	 * Locate the file offset position for the requested object.
 	 *
 	 * @param objId
 	 *            name of the object to locate within the pack.
 	 * @return offset of the object's header and compressed content; -1 if the
 	 *         object does not exist in this index and is thus not stored in the
 	 *         associated pack.
 	 */
 	abstract long findOffset(AnyObjectId objId);

 	/**
 	 * Retrieve stored CRC32 checksum of the requested object raw-data
 	 * (including header).
 	 *
 	 * @param objId
 	 *            id of object to look for
 	 * @return CRC32 checksum of specified object (at 32 less significant bits)
 	 * @throws MissingObjectException
 	 *             when requested ObjectId was not found in this index
 	 * @throws UnsupportedOperationException
 	 *             when this index doesn't support CRC32 checksum
 	 */
 	abstract long findCRC32(AnyObjectId objId) throws MissingObjectException,
 			UnsupportedOperationException;

 	/**
 	 * Check whether this index supports (has) CRC32 checksums for objects.
 	 *
 	 * @return true if CRC32 is stored, false otherwise
 	 */
 	abstract boolean hasCRC32Support();

 	/**
 	 * Represent mutable entry of pack index consisting of object id and offset
 	 * in pack (both mutable).
 	 *
 	 */
 	public static class MutableEntry {
 		final MutableObjectId idBuffer = new MutableObjectId();

 		long offset;

 		/**
 		 * Returns offset for this index object entry
 		 *
 		 * @return offset of this object in a pack file
 		 */
 		public long getOffset() {
 			return offset;
 		}

 		/** @return hex string describing the object id of this entry. */
 		public String name() {
 			ensureId();
 			return idBuffer.name();
 		}

 		/** @return a copy of the object id. */
 		public ObjectId toObjectId() {
 			ensureId();
 			return idBuffer.toObjectId();
 		}

 		/** @return a complete copy of this entry, that won't modify */
 		public MutableEntry cloneEntry() {
 			final MutableEntry r = new MutableEntry();
 			ensureId();
 			r.idBuffer.w1 = idBuffer.w1;
 			r.idBuffer.w2 = idBuffer.w2;
 			r.idBuffer.w3 = idBuffer.w3;
 			r.idBuffer.w4 = idBuffer.w4;
 			r.idBuffer.w5 = idBuffer.w5;
 			r.offset = offset;
 			return r;
 		}

 		void ensureId() {
 			// Override in implementations.
 		}
 	}

 	abstract class EntriesIterator implements Iterator<MutableEntry> {
 		protected final MutableEntry entry = initEntry();

 		protected long returnedNumber = 0;

 		protected abstract MutableEntry initEntry();

 		public boolean hasNext() {
 			return returnedNumber < getObjectCount();
 		}

 		/**
 		 * Implementation must update {@link #returnedNumber} before returning
 		 * element.
 		 */
 		public abstract MutableEntry next();

 		public void remove() {
 			throw new UnsupportedOperationException();
 		}
 	}
 }
	/*
	* Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
	* Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
	* and other copyright owners as documented in the project's IP log.
	*
	* This program and the accompanying materials are made available
	* under the terms of the Eclipse Distribution License v1.0 which
	* accompanies this distribution, is reproduced below, and is
	* available at http://www.eclipse.org/org/documents/edl-v10.php
	*
	* All rights reserved.
	*
	* Redistribution and use in source and binary forms, with or
	* without modification, are permitted provided that the following
	* conditions are met:
	*
	* - Redistributions of source code must retain the above copyright
	* notice, this list of conditions and the following disclaimer.
	*
	* - Redistributions in binary form must reproduce the above
	* copyright notice, this list of conditions and the following
	* disclaimer in the documentation and/or other materials provided
	* with the distribution.
	*
	* - Neither the name of the Eclipse Foundation, Inc. nor the
	* names of its contributors may be used to endorse or promote
	* products derived from this software without specific prior
	* written permission.
	*
	* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
	* CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
	* INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
	* OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	* ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
	* CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
	* SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
	* NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
	* LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
	* CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
	* STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
	* ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
	* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
	*/

	package org.eclipse.jgit.lib;

	import java.io.File;
	import java.io.FileInputStream;
	import java.io.FileNotFoundException;
	import java.io.IOException;
	import java.util.Iterator;

	import org.eclipse.jgit.errors.MissingObjectException;
	import org.eclipse.jgit.util.IO;
	import org.eclipse.jgit.util.NB;

	/**
	* Access path to locate objects by {@link ObjectId} in a {@link PackFile}.
	* <p>
	* Indexes are strictly redundant information in that we can rebuild all of the
	* data held in the index file from the on disk representation of the pack file
	* itself, but it is faster to access for random requests because data is stored
	* by ObjectId.
	* </p>
	*/
	public abstract class PackIndex implements Iterable<PackIndex.MutableEntry> {
	/**
	* Open an existing pack <code>.idx</code> file for reading.
	* <p>
	* The format of the file will be automatically detected and a proper access
	* implementation for that format will be constructed and returned to the
	* caller. The file may or may not be held open by the returned instance.
	* </p>
	*
	* @param idxFile
	* existing pack .idx to read.
	* @return access implementation for the requested file.
	* @throws FileNotFoundException
	* the file does not exist.
	* @throws IOException
	* the file exists but could not be read due to security errors,
	* unrecognized data version, or unexpected data corruption.
	*/
	public static PackIndex open(final File idxFile) throws IOException {
	final FileInputStream fd = new FileInputStream(idxFile);
	try {
	final byte[] hdr = new byte[8];
	IO.readFully(fd, hdr, 0, hdr.length);
	if (isTOC(hdr)) {
	final int v = NB.decodeInt32(hdr, 4);
	switch (v) {
	case 2:
	return new PackIndexV2(fd);
	default:
	throw new IOException("Unsupported pack index version " + v);
	}
	}
	return new PackIndexV1(fd, hdr);
	} catch (IOException ioe) {
	final String path = idxFile.getAbsolutePath();
	final IOException err;
	err = new IOException("Unreadable pack index: " + path);
	err.initCause(ioe);
	throw err;
	} finally {
	try {
	fd.close();
	} catch (IOException err2) {
	// ignore
	}
	}
	}

	private static boolean isTOC(final byte[] h) {
	final byte[] toc = PackIndexWriter.TOC;
	for (int i = 0; i < toc.length; i++)
	if (h[i] != toc[i])
	return false;
	return true;
	}

	/** Footer checksum applied on the bottom of the pack file. */
	protected byte[] packChecksum;

	/**
	* Determine if an object is contained within the pack file.
	*
	* @param id
	* the object to look for. Must not be null.
	* @return true if the object is listed in this index; false otherwise.
	*/
	public boolean hasObject(final AnyObjectId id) {
	return findOffset(id) != -1;
	}

	/**
	* 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
	* pack that this index was generated from.
	*/
	abstract long getObjectCount();

	/**
	* Obtain the total number of objects needing 64 bit offsets.
	*
	* @return number of objects in this index using a 64 bit offset; that is an
	* object positioned after the 2 GB position within the file.
	*/
	abstract long getOffset64Count();

	/**
	* Get ObjectId for the n-th object entry returned by {@link #iterator()}.
	* <p>
	* This method is a constant-time replacement for the following loop:
	*
	* <pre>
	* Iterator<MutableEntry> eItr = index.iterator();
	* int curPosition = 0;
	* while (eItr.hasNext() && curPosition++ < nthPosition)
	* eItr.next();
	* ObjectId result = eItr.next().toObjectId();
	* </pre>
	*
	* @param nthPosition
	* position within the traversal of {@link #iterator()} that the
	* caller needs the object for. The first returned
	* {@link MutableEntry} is 0, the second is 1, etc.
	* @return the ObjectId for the corresponding entry.
	*/
	abstract ObjectId getObjectId(long nthPosition);

	/**
	* Get ObjectId for the n-th object entry returned by {@link #iterator()}.
	* <p>
	* This method is a constant-time replacement for the following loop:
	*
	* <pre>
	* Iterator<MutableEntry> eItr = index.iterator();
	* int curPosition = 0;
	* while (eItr.hasNext() && curPosition++ < nthPosition)
	* eItr.next();
	* ObjectId result = eItr.next().toObjectId();
	* </pre>
	*
	* @param nthPosition
	* unsigned 32 bit position within the traversal of
	* {@link #iterator()} that the caller needs the object for. The
	* first returned {@link MutableEntry} is 0, the second is 1,
	* etc. Positions past 2**31-1 are negative, but still valid.
	* @return the ObjectId for the corresponding entry.
	*/
	final ObjectId getObjectId(final int nthPosition) {
	if (nthPosition >= 0)
	return getObjectId((long) nthPosition);
	final int u31 = nthPosition >>> 1;
	final int one = nthPosition & 1;
	return getObjectId(((long) u31) << 1 \| one);
	}

	/**
	* Locate the file offset position for the requested object.
	*
	* @param objId
	* name of the object to locate within the pack.
	* @return offset of the object's header and compressed content; -1 if the
	* object does not exist in this index and is thus not stored in the
	* associated pack.
	*/
	abstract long findOffset(AnyObjectId objId);

	/**
	* Retrieve stored CRC32 checksum of the requested object raw-data
	* (including header).
	*
	* @param objId
	* id of object to look for
	* @return CRC32 checksum of specified object (at 32 less significant bits)
	* @throws MissingObjectException
	* when requested ObjectId was not found in this index
	* @throws UnsupportedOperationException
	* when this index doesn't support CRC32 checksum
	*/
	abstract long findCRC32(AnyObjectId objId) throws MissingObjectException,
	UnsupportedOperationException;

	/**
	* Check whether this index supports (has) CRC32 checksums for objects.
	*
	* @return true if CRC32 is stored, false otherwise
	*/
	abstract boolean hasCRC32Support();

	/**
	* Represent mutable entry of pack index consisting of object id and offset
	* in pack (both mutable).
	*
	*/
	public static class MutableEntry {
	final MutableObjectId idBuffer = new MutableObjectId();

	long offset;

	/**
	* Returns offset for this index object entry
	*
	* @return offset of this object in a pack file
	*/
	public long getOffset() {
	return offset;
	}

	/** @return hex string describing the object id of this entry. */
	public String name() {
	ensureId();
	return idBuffer.name();
	}

	/** @return a copy of the object id. */
	public ObjectId toObjectId() {
	ensureId();
	return idBuffer.toObjectId();
	}

	/** @return a complete copy of this entry, that won't modify */
	public MutableEntry cloneEntry() {
	final MutableEntry r = new MutableEntry();
	ensureId();
	r.idBuffer.w1 = idBuffer.w1;
	r.idBuffer.w2 = idBuffer.w2;
	r.idBuffer.w3 = idBuffer.w3;
	r.idBuffer.w4 = idBuffer.w4;
	r.idBuffer.w5 = idBuffer.w5;
	r.offset = offset;
	return r;
	}

	void ensureId() {
	// Override in implementations.
	}
	}

	abstract class EntriesIterator implements Iterator<MutableEntry> {
	protected final MutableEntry entry = initEntry();

	protected long returnedNumber = 0;

	protected abstract MutableEntry initEntry();

	public boolean hasNext() {
	return returnedNumber < getObjectCount();
	}

	/**
	* Implementation must update {@link #returnedNumber} before returning
	* element.
	*/
	public abstract MutableEntry next();

	public void remove() {
	throw new UnsupportedOperationException();
	}
	}
	}