org.spearce.jgit/src/org/spearce/jgit/lib/PackIndex.java

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
   4  *
   5  * All rights reserved.
   6  *
   7  * Redistribution and use in source and binary forms, with or
   8  * without modification, are permitted provided that the following
   9  * conditions are met:
  10  *
  11  * - Redistributions of source code must retain the above copyright
  12  *   notice, this list of conditions and the following disclaimer.
  13  *
  14  * - Redistributions in binary form must reproduce the above
  15  *   copyright notice, this list of conditions and the following
  16  *   disclaimer in the documentation and/or other materials provided
  17  *   with the distribution.
  18  *
  19  * - Neither the name of the Git Development Community nor the
  20  *   names of its contributors may be used to endorse or promote
  21  *   products derived from this software without specific prior
  22  *   written permission.
  23  *
  24  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  25  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  26  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  27  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  28  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  29  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  30  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  31  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  32  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  33  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  34  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  35  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  36  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  37  */
  38
  39 package org.spearce.jgit.lib;
  40
  41 import java.io.File;
  42 import java.io.FileInputStream;
  43 import java.io.FileNotFoundException;
  44 import java.io.IOException;
  45 import java.util.Iterator;
  46
  47 import org.spearce.jgit.errors.MissingObjectException;
  48 import org.spearce.jgit.util.NB;
  49
  50 /**
  51  * Access path to locate objects by {@link ObjectId} in a {@link PackFile}.
  52  * <p>
  53  * Indexes are strictly redundant information in that we can rebuild all of the
  54  * data held in the index file from the on disk representation of the pack file
  55  * itself, but it is faster to access for random requests because data is stored
  56  * by ObjectId.
  57  * </p>
  58  */
  59 public abstract class PackIndex implements Iterable<PackIndex.MutableEntry> {
  60         /**
  61          * Open an existing pack <code>.idx</code> file for reading.
  62          * <p>
  63          * The format of the file will be automatically detected and a proper access
  64          * implementation for that format will be constructed and returned to the
  65          * caller. The file may or may not be held open by the returned instance.
  66          * </p>
  67          *
  68          * @param idxFile
  69          *            existing pack .idx to read.
  70          * @return access implementation for the requested file.
  71          * @throws FileNotFoundException
  72          *             the file does not exist.
  73          * @throws IOException
  74          *             the file exists but could not be read due to security errors,
  75          *             unrecognized data version, or unexpected data corruption.
  76          */
  77         public static PackIndex open(final File idxFile) throws IOException {
  78                 final FileInputStream fd = new FileInputStream(idxFile);
  79                 try {
  80                         final byte[] hdr = new byte[8];
  81                         NB.readFully(fd, hdr, 0, hdr.length);
  82                         if (isTOC(hdr)) {
  83                                 final int v = NB.decodeInt32(hdr, 4);
  84                                 switch (v) {
  85                                 case 2:
  86                                         return new PackIndexV2(fd);
  87                                 default:
  88                                         throw new IOException("Unsupported pack index version " + v);
  89                                 }
  90                         }
  91                         return new PackIndexV1(fd, hdr);
  92                 } catch (IOException ioe) {
  93                         final String path = idxFile.getAbsolutePath();
  94                         final IOException err;
  95                         err = new IOException("Unreadable pack index: " + path);
  96                         err.initCause(ioe);
  97                         throw err;
  98                 } finally {
  99                         try {
 100                                 fd.close();
 101                         } catch (IOException err2) {
 102                                 // ignore
 103                         }
 104                 }
 105         }
 106
 107         private static boolean isTOC(final byte[] h) {
 108                 final byte[] toc = PackIndexWriter.TOC;
 109                 for (int i = 0; i < toc.length; i++)
 110                         if (h[i] != toc[i])
 111                                 return false;
 112                 return true;
 113         }
 114
 115         /**
 116          * Determine if an object is contained within the pack file.
 117          *
 118          * @param id
 119          *            the object to look for. Must not be null.
 120          * @return true if the object is listed in this index; false otherwise.
 121          */
 122         public boolean hasObject(final AnyObjectId id) {
 123                 return findOffset(id) != -1;
 124         }
 125
 126         /**
 127          * Provide iterator that gives access to index entries. Note, that iterator
 128          * returns reference to mutable object, the same reference in each call -
 129          * for performance reason. If client needs immutable objects, it must copy
 130          * returned object on its own.
 131          * <p>
 132          * Iterator returns objects in SHA-1 lexicographical order.
 133          * </p>
 134          *
 135          * @return iterator over pack index entries
 136          */
 137         public abstract Iterator<MutableEntry> iterator();
 138
 139         /**
 140          * Obtain the total number of objects described by this index.
 141          *
 142          * @return number of objects in this index, and likewise in the associated
 143          *         pack that this index was generated from.
 144          */
 145         abstract long getObjectCount();
 146
 147         /**
 148          * Obtain the total number of objects needing 64 bit offsets.
 149          *
 150          * @return number of objects in this index using a 64 bit offset; that is an
 151          *         object positioned after the 2 GB position within the file.
 152          */
 153         abstract long getOffset64Count();
 154
 155         /**
 156          * Get ObjectId for the n-th object entry returned by {@link #iterator()}.
 157          * <p>
 158          * This method is a constant-time replacement for the following loop:
 159          *
 160          * <pre>
 161          * Iterator&lt;MutableEntry&gt; eItr = index.iterator();
 162          * int curPosition = 0;
 163          * while (eItr.hasNext() &amp;&amp; curPosition++ &lt; nthPosition)
 164          *      eItr.next();
 165          * ObjectId result = eItr.next().toObjectId();
 166          * </pre>
 167          *
 168          * @param nthPosition
 169          *            position within the traversal of {@link #iterator()} that the
 170          *            caller needs the object for. The first returned
 171          *            {@link MutableEntry} is 0, the second is 1, etc.
 172          * @return the ObjectId for the corresponding entry.
 173          */
 174         abstract ObjectId getObjectId(long nthPosition);
 175
 176         /**
 177          * Get ObjectId for the n-th object entry returned by {@link #iterator()}.
 178          * <p>
 179          * This method is a constant-time replacement for the following loop:
 180          *
 181          * <pre>
 182          * Iterator&lt;MutableEntry&gt; eItr = index.iterator();
 183          * int curPosition = 0;
 184          * while (eItr.hasNext() &amp;&amp; curPosition++ &lt; nthPosition)
 185          *      eItr.next();
 186          * ObjectId result = eItr.next().toObjectId();
 187          * </pre>
 188          *
 189          * @param nthPosition
 190          *            unsigned 32 bit position within the traversal of
 191          *            {@link #iterator()} that the caller needs the object for. The
 192          *            first returned {@link MutableEntry} is 0, the second is 1,
 193          *            etc. Positions past 2**31-1 are negative, but still valid.
 194          * @return the ObjectId for the corresponding entry.
 195          */
 196         final ObjectId getObjectId(final int nthPosition) {
 197                 if (nthPosition >= 0)
 198                         return getObjectId((long) nthPosition);
 199                 final int u31 = nthPosition >>> 1;
 200                 final int one = nthPosition & 1;
 201                 return getObjectId(((long) u31) << 1 | one);
 202         }
 203
 204         /**
 205          * Locate the file offset position for the requested object.
 206          *
 207          * @param objId
 208          *            name of the object to locate within the pack.
 209          * @return offset of the object's header and compressed content; -1 if the
 210          *         object does not exist in this index and is thus not stored in the
 211          *         associated pack.
 212          */
 213         abstract long findOffset(AnyObjectId objId);
 214
 215         /**
 216          * Retrieve stored CRC32 checksum of the requested object raw-data
 217          * (including header).
 218          *
 219          * @param objId
 220          *            id of object to look for
 221          * @return CRC32 checksum of specified object (at 32 less significant bits)
 222          * @throws MissingObjectException
 223          *             when requested ObjectId was not found in this index
 224          * @throws UnsupportedOperationException
 225          *             when this index doesn't support CRC32 checksum
 226          */
 227         abstract long findCRC32(AnyObjectId objId) throws MissingObjectException,
 228                         UnsupportedOperationException;
 229
 230         /**
 231          * Check whether this index supports (has) CRC32 checksums for objects.
 232          *
 233          * @return true if CRC32 is stored, false otherwise
 234          */
 235         abstract boolean hasCRC32Support();
 236
 237         /**
 238          * Represent mutable entry of pack index consisting of object id and offset
 239          * in pack (both mutable).
 240          *
 241          */
 242         public static class MutableEntry extends MutableObjectId {
 243                 private long offset;
 244
 245                 /**
 246                  * Empty constructor. Object fields should be filled in later.
 247                  */
 248                 public MutableEntry() {
 249                         super();
 250                 }
 251
 252                 /**
 253                  * Returns offset for this index object entry
 254                  *
 255                  * @return offset of this object in a pack file
 256                  */
 257                 public long getOffset() {
 258                         return offset;
 259                 }
 260
 261                 void setOffset(long offset) {
 262                         this.offset = offset;
 263                 }
 264
 265                 private MutableEntry(MutableEntry src) {
 266                         super(src);
 267                         this.offset = src.offset;
 268                 }
 269
 270                 /**
 271                  * Returns mutable copy of this mutable entry.
 272                  *
 273                  * @return copy of this mutable entry
 274                  */
 275                 public MutableEntry cloneEntry() {
 276                         return new MutableEntry(this);
 277                 }
 278         }
 279
 280         protected abstract class EntriesIterator implements Iterator<MutableEntry> {
 281                 protected MutableEntry objectId = new MutableEntry();
 282
 283                 protected long returnedNumber = 0;
 284
 285                 public boolean hasNext() {
 286                         return returnedNumber < getObjectCount();
 287                 }
 288
 289                 /**
 290                  * Implementation must update {@link #returnedNumber} before returning
 291                  * element.
 292                  */
 293                 public abstract MutableEntry next();
 294
 295                 public void remove() {
 296                         throw new UnsupportedOperationException();
 297                 }
 298         }
 299 }