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

   1 /*
   2  * Copyright (C) 2007, Robin Rosenberg <robin.rosenberg@dewire.com>
   3  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>
   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.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.errors.CorruptObjectException;
  48 import org.spearce.jgit.util.NB;
  49
  50 class PackIndexV1 extends PackIndex {
  51         private static final int IDX_HDR_LEN = 256 * 4;
  52
  53         private final long[] idxHeader;
  54
  55         private byte[][] idxdata;
  56
  57         private long objectCnt;
  58
  59         PackIndexV1(final InputStream fd, final byte[] hdr)
  60                         throws CorruptObjectException, IOException {
  61                 final byte[] fanoutTable = new byte[IDX_HDR_LEN];
  62                 System.arraycopy(hdr, 0, fanoutTable, 0, hdr.length);
  63                 NB.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length);
  64
  65                 idxHeader = new long[256]; // really unsigned 32-bit...
  66                 for (int k = 0; k < idxHeader.length; k++)
  67                         idxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4);
  68                 idxdata = new byte[idxHeader.length][];
  69                 for (int k = 0; k < idxHeader.length; k++) {
  70                         int n;
  71                         if (k == 0) {
  72                                 n = (int) (idxHeader[k]);
  73                         } else {
  74                                 n = (int) (idxHeader[k] - idxHeader[k - 1]);
  75                         }
  76                         if (n > 0) {
  77                                 idxdata[k] = new byte[n * (Constants.OBJECT_ID_LENGTH + 4)];
  78                                 NB.readFully(fd, idxdata[k], 0, idxdata[k].length);
  79                         }
  80                 }
  81                 objectCnt = idxHeader[255];
  82
  83                 packChecksum = new byte[20];
  84                 NB.readFully(fd, packChecksum, 0, packChecksum.length);
  85         }
  86
  87         long getObjectCount() {
  88                 return objectCnt;
  89         }
  90
  91         @Override
  92         long getOffset64Count() {
  93                 long n64 = 0;
  94                 for (final MutableEntry e : this) {
  95                         if (e.getOffset() >= Integer.MAX_VALUE)
  96                                 n64++;
  97                 }
  98                 return n64;
  99         }
 100
 101         @Override
 102         ObjectId getObjectId(final long nthPosition) {
 103                 int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
 104                 long base;
 105                 if (levelOne >= 0) {
 106                         // If we hit the bucket exactly the item is in the bucket, or
 107                         // any bucket before it which has the same object count.
 108                         //
 109                         base = idxHeader[levelOne];
 110                         while (levelOne > 0 && base == idxHeader[levelOne - 1])
 111                                 levelOne--;
 112                 } else {
 113                         // The item is in the bucket we would insert it into.
 114                         //
 115                         levelOne = -(levelOne + 1);
 116                 }
 117
 118                 base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
 119                 final int p = (int) (nthPosition - base);
 120                 final int dataIdx = ((4 + Constants.OBJECT_ID_LENGTH) * p) + 4;
 121                 return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
 122         }
 123
 124         long findOffset(final AnyObjectId objId) {
 125                 final int levelOne = objId.getFirstByte();
 126                 byte[] data = idxdata[levelOne];
 127                 if (data == null)
 128                         return -1;
 129                 int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
 130                 int low = 0;
 131                 do {
 132                         final int mid = (low + high) / 2;
 133                         final int pos = ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
 134                         final int cmp = objId.compareTo(data, pos);
 135                         if (cmp < 0)
 136                                 high = mid;
 137                         else if (cmp == 0) {
 138                                 int b0 = data[pos - 4] & 0xff;
 139                                 int b1 = data[pos - 3] & 0xff;
 140                                 int b2 = data[pos - 2] & 0xff;
 141                                 int b3 = data[pos - 1] & 0xff;
 142                                 return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
 143                         } else
 144                                 low = mid + 1;
 145                 } while (low < high);
 146                 return -1;
 147         }
 148
 149         @Override
 150         long findCRC32(AnyObjectId objId) {
 151                 throw new UnsupportedOperationException();
 152         }
 153
 154         @Override
 155         boolean hasCRC32Support() {
 156                 return false;
 157         }
 158
 159         public Iterator<MutableEntry> iterator() {
 160                 return new IndexV1Iterator();
 161         }
 162
 163         private class IndexV1Iterator extends EntriesIterator {
 164                 private int levelOne;
 165
 166                 private int levelTwo;
 167
 168                 @Override
 169                 protected MutableEntry initEntry() {
 170                         return new MutableEntry() {
 171                                 protected void ensureId() {
 172                                         idBuffer.fromRaw(idxdata[levelOne], levelTwo
 173                                                         - Constants.OBJECT_ID_LENGTH);
 174                                 }
 175                         };
 176                 }
 177
 178                 public MutableEntry next() {
 179                         for (; levelOne < idxdata.length; levelOne++) {
 180                                 if (idxdata[levelOne] == null)
 181                                         continue;
 182                                 if (levelTwo < idxdata[levelOne].length) {
 183                                         entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
 184                                         levelTwo += Constants.OBJECT_ID_LENGTH + 4;
 185                                         returnedNumber++;
 186                                         return entry;
 187                                 }
 188                                 levelTwo = 0;
 189                         }
 190                         throw new NoSuchElementException();
 191                 }
 192         }
 193 }