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

   1 /*
   2  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   3  * and other copyright owners as documented in the project's IP log.
   4  *
   5  * This program and the accompanying materials are made available
   6  * under the terms of the Eclipse Distribution License v1.0 which
   7  * accompanies this distribution, is reproduced below, and is
   8  * available at http://www.eclipse.org/org/documents/edl-v10.php
   9  *
  10  * All rights reserved.
  11  *
  12  * Redistribution and use in source and binary forms, with or
  13  * without modification, are permitted provided that the following
  14  * conditions are met:
  15  *
  16  * - Redistributions of source code must retain the above copyright
  17  *   notice, this list of conditions and the following disclaimer.
  18  *
  19  * - Redistributions in binary form must reproduce the above
  20  *   copyright notice, this list of conditions and the following
  21  *   disclaimer in the documentation and/or other materials provided
  22  *   with the distribution.
  23  *
  24  * - Neither the name of the Eclipse Foundation, Inc. nor the
  25  *   names of its contributors may be used to endorse or promote
  26  *   products derived from this software without specific prior
  27  *   written permission.
  28  *
  29  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  30  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  31  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  32  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  34  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  35  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  36  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  37  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  38  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  39  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  40  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  41  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  42  */
  43
  44 package org.eclipse.jgit.lib;
  45
  46 import java.io.IOException;
  47 import java.io.InputStream;
  48 import java.util.Arrays;
  49 import java.util.Iterator;
  50 import java.util.NoSuchElementException;
  51
  52 import org.eclipse.jgit.errors.MissingObjectException;
  53 import org.eclipse.jgit.util.NB;
  54
  55 /** Support for the pack index v2 format. */
  56 class PackIndexV2 extends PackIndex {
  57         private static final long IS_O64 = 1L << 31;
  58
  59         private static final int FANOUT = 256;
  60
  61         private static final int[] NO_INTS = {};
  62
  63         private static final byte[] NO_BYTES = {};
  64
  65         private long objectCnt;
  66
  67         private final long[] fanoutTable;
  68
  69         /** 256 arrays of contiguous object names. */
  70         private int[][] names;
  71
  72         /** 256 arrays of the 32 bit offset data, matching {@link #names}. */
  73         private byte[][] offset32;
  74
  75         /** 256 arrays of the CRC-32 of objects, matching {@link #names}. */
  76         private byte[][] crc32;
  77
  78         /** 64 bit offset table. */
  79         private byte[] offset64;
  80
  81         PackIndexV2(final InputStream fd) throws IOException {
  82                 final byte[] fanoutRaw = new byte[4 * FANOUT];
  83                 NB.readFully(fd, fanoutRaw, 0, fanoutRaw.length);
  84                 fanoutTable = new long[FANOUT];
  85                 for (int k = 0; k < FANOUT; k++)
  86                         fanoutTable[k] = NB.decodeUInt32(fanoutRaw, k * 4);
  87                 objectCnt = fanoutTable[FANOUT - 1];
  88
  89                 names = new int[FANOUT][];
  90                 offset32 = new byte[FANOUT][];
  91                 crc32 = new byte[FANOUT][];
  92
  93                 // Object name table. The size we can permit per fan-out bucket
  94                 // is limited to Java's 2 GB per byte array limitation. That is
  95                 // no more than 107,374,182 objects per fan-out.
  96                 //
  97                 for (int k = 0; k < FANOUT; k++) {
  98                         final long bucketCnt;
  99                         if (k == 0)
 100                                 bucketCnt = fanoutTable[k];
 101                         else
 102                                 bucketCnt = fanoutTable[k] - fanoutTable[k - 1];
 103
 104                         if (bucketCnt == 0) {
 105                                 names[k] = NO_INTS;
 106                                 offset32[k] = NO_BYTES;
 107                                 crc32[k] = NO_BYTES;
 108                                 continue;
 109                         }
 110
 111                         final long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
 112                         if (nameLen > Integer.MAX_VALUE)
 113                                 throw new IOException("Index file is too large for jgit");
 114
 115                         final int intNameLen = (int) nameLen;
 116                         final byte[] raw = new byte[intNameLen];
 117                         final int[] bin = new int[intNameLen >>> 2];
 118                         NB.readFully(fd, raw, 0, raw.length);
 119                         for (int i = 0; i < bin.length; i++)
 120                                 bin[i] = NB.decodeInt32(raw, i << 2);
 121
 122                         names[k] = bin;
 123                         offset32[k] = new byte[(int) (bucketCnt * 4)];
 124                         crc32[k] = new byte[(int) (bucketCnt * 4)];
 125                 }
 126
 127                 // CRC32 table.
 128                 for (int k = 0; k < FANOUT; k++)
 129                         NB.readFully(fd, crc32[k], 0, crc32[k].length);
 130
 131                 // 32 bit offset table. Any entries with the most significant bit
 132                 // set require a 64 bit offset entry in another table.
 133                 //
 134                 int o64cnt = 0;
 135                 for (int k = 0; k < FANOUT; k++) {
 136                         final byte[] ofs = offset32[k];
 137                         NB.readFully(fd, ofs, 0, ofs.length);
 138                         for (int p = 0; p < ofs.length; p += 4)
 139                                 if (ofs[p] < 0)
 140                                         o64cnt++;
 141                 }
 142
 143                 // 64 bit offset table. Most objects should not require an entry.
 144                 //
 145                 if (o64cnt > 0) {
 146                         offset64 = new byte[o64cnt * 8];
 147                         NB.readFully(fd, offset64, 0, offset64.length);
 148                 } else {
 149                         offset64 = NO_BYTES;
 150                 }
 151
 152                 packChecksum = new byte[20];
 153                 NB.readFully(fd, packChecksum, 0, packChecksum.length);
 154         }
 155
 156         @Override
 157         long getObjectCount() {
 158                 return objectCnt;
 159         }
 160
 161         @Override
 162         long getOffset64Count() {
 163                 return offset64.length / 8;
 164         }
 165
 166         @Override
 167         ObjectId getObjectId(final long nthPosition) {
 168                 int levelOne = Arrays.binarySearch(fanoutTable, nthPosition + 1);
 169                 long base;
 170                 if (levelOne >= 0) {
 171                         // If we hit the bucket exactly the item is in the bucket, or
 172                         // any bucket before it which has the same object count.
 173                         //
 174                         base = fanoutTable[levelOne];
 175                         while (levelOne > 0 && base == fanoutTable[levelOne - 1])
 176                                 levelOne--;
 177                 } else {
 178                         // The item is in the bucket we would insert it into.
 179                         //
 180                         levelOne = -(levelOne + 1);
 181                 }
 182
 183                 base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
 184                 final int p = (int) (nthPosition - base);
 185                 final int p4 = p << 2;
 186                 return ObjectId.fromRaw(names[levelOne], p4 + p); // p * 5
 187         }
 188
 189         @Override
 190         long findOffset(final AnyObjectId objId) {
 191                 final int levelOne = objId.getFirstByte();
 192                 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
 193                 if (levelTwo == -1)
 194                         return -1;
 195                 final long p = NB.decodeUInt32(offset32[levelOne], levelTwo << 2);
 196                 if ((p & IS_O64) != 0)
 197                         return NB.decodeUInt64(offset64, (8 * (int) (p & ~IS_O64)));
 198                 return p;
 199         }
 200
 201         @Override
 202         long findCRC32(AnyObjectId objId) throws MissingObjectException {
 203                 final int levelOne = objId.getFirstByte();
 204                 final int levelTwo = binarySearchLevelTwo(objId, levelOne);
 205                 if (levelTwo == -1)
 206                         throw new MissingObjectException(objId.copy(), "unknown");
 207                 return NB.decodeUInt32(crc32[levelOne], levelTwo << 2);
 208         }
 209
 210         @Override
 211         boolean hasCRC32Support() {
 212                 return true;
 213         }
 214
 215         public Iterator<MutableEntry> iterator() {
 216                 return new EntriesIteratorV2();
 217         }
 218
 219         private int binarySearchLevelTwo(final AnyObjectId objId, final int levelOne) {
 220                 final int[] data = names[levelOne];
 221                 int high = offset32[levelOne].length >>> 2;
 222                 if (high == 0)
 223                         return -1;
 224                 int low = 0;
 225                 do {
 226                         final int mid = (low + high) >>> 1;
 227                         final int mid4 = mid << 2;
 228                         final int cmp;
 229
 230                         cmp = objId.compareTo(data, mid4 + mid); // mid * 5
 231                         if (cmp < 0)
 232                                 high = mid;
 233                         else if (cmp == 0) {
 234                                 return mid;
 235                         } else
 236                                 low = mid + 1;
 237                 } while (low < high);
 238                 return -1;
 239         }
 240
 241         private class EntriesIteratorV2 extends EntriesIterator {
 242                 private int levelOne;
 243
 244                 private int levelTwo;
 245
 246                 @Override
 247                 protected MutableEntry initEntry() {
 248                         return new MutableEntry() {
 249                                 protected void ensureId() {
 250                                         idBuffer.fromRaw(names[levelOne], levelTwo
 251                                                         - Constants.OBJECT_ID_LENGTH / 4);
 252                                 }
 253                         };
 254                 }
 255
 256                 public MutableEntry next() {
 257                         for (; levelOne < names.length; levelOne++) {
 258                                 if (levelTwo < names[levelOne].length) {
 259                                         int idx = levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;
 260                                         long offset = NB.decodeUInt32(offset32[levelOne], idx);
 261                                         if ((offset & IS_O64) != 0) {
 262                                                 idx = (8 * (int) (offset & ~IS_O64));
 263                                                 offset = NB.decodeUInt64(offset64, idx);
 264                                         }
 265                                         entry.offset = offset;
 266
 267                                         levelTwo += Constants.OBJECT_ID_LENGTH / 4;
 268                                         returnedNumber++;
 269                                         return entry;
 270                                 }
 271                                 levelTwo = 0;
 272                         }
 273                         throw new NoSuchElementException();
 274                 }
 275         }
 276
 277 }