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 import java.util.Arrays;
  44 import java.util.Iterator;
  45 import java.util.NoSuchElementException;
  46
  47 import org.spearce.jgit.util.NB;
  48
  49 /** Support for the pack index v2 format. */
  50 class PackIndexV2 extends PackIndex {
  51         private static final long IS_O64 = 1L << 31;
  52
  53         private static final int FANOUT = 256;
  54
  55         private static final int[] NO_INTS = {};
  56
  57         private static final byte[] NO_BYTES = {};
  58
  59         private long objectCnt;
  60
  61         private final long[] fanoutTable;
  62
  63         /** 256 arrays of contiguous object names. */
  64         private int[][] names;
  65
  66         /** 256 arrays of the 32 bit offset data, matching {@link #names}. */
  67         private byte[][] offset32;
  68
  69         /** 64 bit offset table. */
  70         private byte[] offset64;
  71
  72         PackIndexV2(final InputStream fd) throws IOException {
  73                 final byte[] fanoutRaw = new byte[4 * FANOUT];
  74                 NB.readFully(fd, fanoutRaw, 0, fanoutRaw.length);
  75                 fanoutTable = new long[FANOUT];
  76                 for (int k = 0; k < FANOUT; k++)
  77                         fanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);
  78                 objectCnt = fanoutTable[FANOUT - 1];
  79
  80                 names = new int[FANOUT][];
  81                 offset32 = new byte[FANOUT][];
  82
  83                 // Object name table. The size we can permit per fan-out bucket
  84                 // is limited to Java's 2 GB per byte array limitation. That is
  85                 // no more than 107,374,182 objects per fan-out.
  86                 //
  87                 for (int k = 0; k < FANOUT; k++) {
  88                         final long bucketCnt;
  89                         if (k == 0)
  90                                 bucketCnt = fanoutTable[k];
  91                         else
  92                                 bucketCnt = fanoutTable[k] - fanoutTable[k - 1];
  93
  94                         if (bucketCnt == 0) {
  95                                 names[k] = NO_INTS;
  96                                 offset32[k] = NO_BYTES;
  97                                 continue;
  98                         }
  99
 100                         final long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
 101                         if (nameLen > Integer.MAX_VALUE)
 102                                 throw new IOException("Index file is too large for jgit");
 103
 104                         final int intNameLen = (int) nameLen;
 105                         final byte[] raw = new byte[intNameLen];
 106                         final int[] bin = new int[intNameLen >> 2];
 107                         NB.readFully(fd, raw, 0, raw.length);
 108                         for (int i = 0; i < bin.length; i++)
 109                                 bin[i] = NB.decodeInt32(raw, i << 2);
 110
 111                         names[k] = bin;
 112                         offset32[k] = new byte[(int) (bucketCnt * 4)];
 113                 }
 114
 115                 // CRC32 table. Currently unused.
 116                 //
 117                 skipFully(fd, objectCnt * 4);
 118
 119                 // 32 bit offset table. Any entries with the most significant bit
 120                 // set require a 64 bit offset entry in another table.
 121                 //
 122                 int o64cnt = 0;
 123                 for (int k = 0; k < FANOUT; k++) {
 124                         final byte[] ofs = offset32[k];
 125                         NB.readFully(fd, ofs, 0, ofs.length);
 126                         for (int p = 0; p < ofs.length; p += 4)
 127                                 if (ofs[p] < 0)
 128                                         o64cnt++;
 129                 }
 130
 131                 // 64 bit offset table. Most objects should not require an entry.
 132                 //
 133                 if (o64cnt > 0) {
 134                         offset64 = new byte[o64cnt * 8];
 135                         NB.readFully(fd, offset64, 0, offset64.length);
 136                 } else {
 137                         offset64 = NO_BYTES;
 138                 }
 139         }
 140
 141         private static void skipFully(final InputStream fd, long toSkip)
 142                         throws IOException {
 143                 while (toSkip > 0) {
 144                         final long r = fd.skip(toSkip);
 145                         if (r <= 0)
 146                                 throw new EOFException("Cannot skip index section.");
 147                         toSkip -= r;
 148                 }
 149         }
 150
 151         @Override
 152         long getObjectCount() {
 153                 return objectCnt;
 154         }
 155
 156         @Override
 157         long getOffset64Count() {
 158                 return offset64.length / 8;
 159         }
 160
 161         @Override
 162         ObjectId getObjectId(final long nthPosition) {
 163                 int levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);
 164                 long base;
 165                 if (levelOne >= 0) {
 166                         // If we hit the bucket exactly the item is in the bucket, or
 167                         // any bucket before it which has the same object count.
 168                         //
 169                         base = fanoutTable[levelOne];
 170                         while (levelOne > 0 && base == fanoutTable[levelOne - 1])
 171                                 levelOne--;
 172                 } else {
 173                         // The item is in the bucket we would insert it into.
 174                         //
 175                         levelOne = -(levelOne + 1);
 176                 }
 177
 178                 base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
 179                 final int p = (int) (nthPosition - base);
 180                 final int p4 = p << 2;
 181                 return ObjectId.fromRaw(names[levelOne], p4 + p); // p * 5
 182         }
 183
 184         @Override
 185         long findOffset(final AnyObjectId objId) {
 186                 final int levelOne = objId.getFirstByte();
 187                 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
 188                 if (levelTwo == -1)
 189                         return -1;
 190                 final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
 191                 if ((p & IS_O64) != 0)
 192                         return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
 193                 return p;
 194         }
 195
 196         public Iterator<MutableEntry> iterator() {
 197                 return new EntriesIteratorV2();
 198         }
 199
 200         private int binarySearchLevelTwo(final AnyObjectId objId, final int levelOne) {
 201                 final int[] data = names[levelOne];
 202                 int high = offset32[levelOne].length >> 2;
 203                 if (high == 0)
 204                         return -1;
 205                 int low = 0;
 206                 do {
 207                         final int mid = (low + high) >> 1;
 208                         final int mid4 = mid << 2;
 209                         final int cmp;
 210
 211                         cmp = objId.compareTo(data, mid4 + mid); // mid * 5
 212                         if (cmp < 0)
 213                                 high = mid;
 214                         else if (cmp == 0) {
 215                                 return mid;
 216                         } else
 217                                 low = mid + 1;
 218                 } while (low < high);
 219                 return -1;
 220         }
 221
 222         private class EntriesIteratorV2 extends EntriesIterator {
 223                 private int levelOne;
 224
 225                 private int levelTwo;
 226
 227                 public MutableEntry next() {
 228                         for (; levelOne < names.length; levelOne++) {
 229                                 if (levelTwo < names[levelOne].length) {
 230                                         objectId.fromRaw(names[levelOne], levelTwo);
 231                                         int arrayIdx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4)
 232                                                         * 4;
 233                                         long offset = NB.decodeUInt32(offset32[levelOne], arrayIdx);
 234                                         if ((offset & IS_O64) != 0) {
 235                                                 arrayIdx = (8 * (int) (offset & ~IS_O64));
 236                                                 offset = NB.decodeUInt64(offset64, arrayIdx);
 237                                         }
 238                                         objectId.setOffset(offset);
 239
 240                                         levelTwo += Constants.OBJECT_ID_LENGTH / 4;
 241                                         returnedNumber++;
 242                                         return objectId;
 243                                 } else {
 244                                         levelTwo = 0;
 245                                 }
 246                         }
 247                         throw new NoSuchElementException();
 248                 }
 249         }
 250
 251 }