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

   1 package org.spearce.jgit.lib;
   2
   3 import java.io.EOFException;
   4 import java.io.IOException;
   5 import java.io.InputStream;
   6
   7 import org.spearce.jgit.util.NB;
   8
   9 /** Support for the pack index v2 format. */
  10 class PackIndexV2 extends PackIndex {
  11         private static final long IS_O64 = 1L << 31;
  12
  13         private static final int FANOUT = 256;
  14
  15         private static final int[] NO_INTS = {};
  16
  17         private static final byte[] NO_BYTES = {};
  18
  19         private long objectCnt;
  20
  21         /** 256 arrays of contiguous object names. */
  22         private int[][] names;
  23
  24         /** 256 arrays of the 32 bit offset data, matching {@link #names}. */
  25         private byte[][] offset32;
  26
  27         /** 64 bit offset table. */
  28         private byte[] offset64;
  29
  30         PackIndexV2(final InputStream fd) throws IOException {
  31                 final byte[] fanoutRaw = new byte[4 * FANOUT];
  32                 NB.readFully(fd, fanoutRaw, 0, fanoutRaw.length);
  33                 final long[] fanoutTable = new long[FANOUT];
  34                 for (int k = 0; k < FANOUT; k++)
  35                         fanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);
  36                 objectCnt = fanoutTable[FANOUT - 1];
  37
  38                 names = new int[FANOUT][];
  39                 offset32 = new byte[FANOUT][];
  40
  41                 // Object name table. The size we can permit per fan-out bucket
  42                 // is limited to Java's 2 GB per byte array limitation. That is
  43                 // no more than 107,374,182 objects per fan-out.
  44                 //
  45                 for (int k = 0; k < FANOUT; k++) {
  46                         final long bucketCnt;
  47                         if (k == 0)
  48                                 bucketCnt = fanoutTable[k];
  49                         else
  50                                 bucketCnt = fanoutTable[k] - fanoutTable[k - 1];
  51
  52                         if (bucketCnt == 0) {
  53                                 names[k] = NO_INTS;
  54                                 offset32[k] = NO_BYTES;
  55                                 continue;
  56                         }
  57
  58                         final long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
  59                         if (nameLen > Integer.MAX_VALUE)
  60                                 throw new IOException("Index file is too large for jgit");
  61
  62                         final int intNameLen = (int) nameLen;
  63                         final byte[] raw = new byte[intNameLen];
  64                         final int[] bin = new int[intNameLen >> 2];
  65                         NB.readFully(fd, raw, 0, raw.length);
  66                         for (int i = 0; i < bin.length; i++)
  67                                 bin[i] = NB.decodeInt32(raw, i << 2);
  68
  69                         names[k] = bin;
  70                         offset32[k] = new byte[(int) (bucketCnt * 4)];
  71                 }
  72
  73                 // CRC32 table. Currently unused.
  74                 //
  75                 skipFully(fd, objectCnt * 4);
  76
  77                 // 32 bit offset table. Any entries with the most significant bit
  78                 // set require a 64 bit offset entry in another table.
  79                 //
  80                 int o64cnt = 0;
  81                 for (int k = 0; k < FANOUT; k++) {
  82                         final byte[] ofs = offset32[k];
  83                         NB.readFully(fd, ofs, 0, ofs.length);
  84                         for (int p = 0; p < ofs.length; p += 4)
  85                                 if (ofs[p] < 0)
  86                                         o64cnt++;
  87                 }
  88
  89                 // 64 bit offset table. Most objects should not require an entry.
  90                 //
  91                 if (o64cnt > 0) {
  92                         offset64 = new byte[o64cnt * 8];
  93                         NB.readFully(fd, offset64, 0, offset64.length);
  94                 } else {
  95                         offset64 = NO_BYTES;
  96                 }
  97         }
  98
  99         private static void skipFully(final InputStream fd, long toSkip)
 100                         throws IOException {
 101                 while (toSkip > 0) {
 102                         final long r = fd.skip(toSkip);
 103                         if (r <= 0)
 104                                 throw new EOFException("Cannot skip index section.");
 105                         toSkip -= r;
 106                 }
 107         }
 108
 109         @Override
 110         long getObjectCount() {
 111                 return objectCnt;
 112         }
 113
 114         @Override
 115         long findOffset(final AnyObjectId objId) {
 116                 final int levelOne = objId.getFirstByte();
 117                 final int[] data = names[levelOne];
 118                 int high = offset32[levelOne].length >> 2;
 119                 if (high == 0)
 120                         return -1;
 121                 int low = 0;
 122                 do {
 123                         final int mid = (low + high) >> 1;
 124                         final int mid4 = mid << 2;
 125                         final int cmp;
 126
 127                         cmp = objId.compareTo(data, mid4 + mid); // mid * 5
 128                         if (cmp < 0)
 129                                 high = mid;
 130                         else if (cmp == 0) {
 131                                 final long p = NB.decodeUInt32(offset32[levelOne], mid4);
 132                                 if ((p & IS_O64) != 0)
 133                                         return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
 134                                 return p;
 135                         } else
 136                                 low = mid + 1;
 137                 } while (low < high);
 138                 return -1;
 139         }
 140 }