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

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  *
   4  * All rights reserved.
   5  *
   6  * Redistribution and use in source and binary forms, with or
   7  * without modification, are permitted provided that the following
   8  * conditions are met:
   9  *
  10  * - Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * - Redistributions in binary form must reproduce the above
  14  *   copyright notice, this list of conditions and the following
  15  *   disclaimer in the documentation and/or other materials provided
  16  *   with the distribution.
  17  *
  18  * - Neither the name of the Git Development Community nor the
  19  *   names of its contributors may be used to endorse or promote
  20  *   products derived from this software without specific prior
  21  *   written permission.
  22  *
  23  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  24  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  25  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  26  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  27  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  28  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  29  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  30  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  31  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  32  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  33  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  34  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  35  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  36  */
  37
  38 package org.spearce.jgit.lib;
  39
  40 import java.io.EOFException;
  41 import java.io.IOException;
  42 import java.io.InputStream;
  43
  44 import org.spearce.jgit.util.NB;
  45
  46 /** Support for the pack index v2 format. */
  47 class PackIndexV2 extends PackIndex {
  48         private static final long IS_O64 = 1L << 31;
  49
  50         private static final int FANOUT = 256;
  51
  52         private static final int[] NO_INTS = {};
  53
  54         private static final byte[] NO_BYTES = {};
  55
  56         private long objectCnt;
  57
  58         /** 256 arrays of contiguous object names. */
  59         private int[][] names;
  60
  61         /** 256 arrays of the 32 bit offset data, matching {@link #names}. */
  62         private byte[][] offset32;
  63
  64         /** 64 bit offset table. */
  65         private byte[] offset64;
  66
  67         PackIndexV2(final InputStream fd) throws IOException {
  68                 final byte[] fanoutRaw = new byte[4 * FANOUT];
  69                 NB.readFully(fd, fanoutRaw, 0, fanoutRaw.length);
  70                 final long[] fanoutTable = new long[FANOUT];
  71                 for (int k = 0; k < FANOUT; k++)
  72                         fanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);
  73                 objectCnt = fanoutTable[FANOUT - 1];
  74
  75                 names = new int[FANOUT][];
  76                 offset32 = new byte[FANOUT][];
  77
  78                 // Object name table. The size we can permit per fan-out bucket
  79                 // is limited to Java's 2 GB per byte array limitation. That is
  80                 // no more than 107,374,182 objects per fan-out.
  81                 //
  82                 for (int k = 0; k < FANOUT; k++) {
  83                         final long bucketCnt;
  84                         if (k == 0)
  85                                 bucketCnt = fanoutTable[k];
  86                         else
  87                                 bucketCnt = fanoutTable[k] - fanoutTable[k - 1];
  88
  89                         if (bucketCnt == 0) {
  90                                 names[k] = NO_INTS;
  91                                 offset32[k] = NO_BYTES;
  92                                 continue;
  93                         }
  94
  95                         final long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
  96                         if (nameLen > Integer.MAX_VALUE)
  97                                 throw new IOException("Index file is too large for jgit");
  98
  99                         final int intNameLen = (int) nameLen;
 100                         final byte[] raw = new byte[intNameLen];
 101                         final int[] bin = new int[intNameLen >> 2];
 102                         NB.readFully(fd, raw, 0, raw.length);
 103                         for (int i = 0; i < bin.length; i++)
 104                                 bin[i] = NB.decodeInt32(raw, i << 2);
 105
 106                         names[k] = bin;
 107                         offset32[k] = new byte[(int) (bucketCnt * 4)];
 108                 }
 109
 110                 // CRC32 table. Currently unused.
 111                 //
 112                 skipFully(fd, objectCnt * 4);
 113
 114                 // 32 bit offset table. Any entries with the most significant bit
 115                 // set require a 64 bit offset entry in another table.
 116                 //
 117                 int o64cnt = 0;
 118                 for (int k = 0; k < FANOUT; k++) {
 119                         final byte[] ofs = offset32[k];
 120                         NB.readFully(fd, ofs, 0, ofs.length);
 121                         for (int p = 0; p < ofs.length; p += 4)
 122                                 if (ofs[p] < 0)
 123                                         o64cnt++;
 124                 }
 125
 126                 // 64 bit offset table. Most objects should not require an entry.
 127                 //
 128                 if (o64cnt > 0) {
 129                         offset64 = new byte[o64cnt * 8];
 130                         NB.readFully(fd, offset64, 0, offset64.length);
 131                 } else {
 132                         offset64 = NO_BYTES;
 133                 }
 134         }
 135
 136         private static void skipFully(final InputStream fd, long toSkip)
 137                         throws IOException {
 138                 while (toSkip > 0) {
 139                         final long r = fd.skip(toSkip);
 140                         if (r <= 0)
 141                                 throw new EOFException("Cannot skip index section.");
 142                         toSkip -= r;
 143                 }
 144         }
 145
 146         @Override
 147         long getObjectCount() {
 148                 return objectCnt;
 149         }
 150
 151         @Override
 152         long findOffset(final AnyObjectId objId) {
 153                 final int levelOne = objId.getFirstByte();
 154                 final int[] data = names[levelOne];
 155                 int high = offset32[levelOne].length >> 2;
 156                 if (high == 0)
 157                         return -1;
 158                 int low = 0;
 159                 do {
 160                         final int mid = (low + high) >> 1;
 161                         final int mid4 = mid << 2;
 162                         final int cmp;
 163
 164                         cmp = objId.compareTo(data, mid4 + mid); // mid * 5
 165                         if (cmp < 0)
 166                                 high = mid;
 167                         else if (cmp == 0) {
 168                                 final long p = NB.decodeUInt32(offset32[levelOne], mid4);
 169                                 if ((p & IS_O64) != 0)
 170                                         return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
 171                                 return p;
 172                         } else
 173                                 low = mid + 1;
 174                 } while (low < high);
 175                 return -1;
 176         }
 177 }