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

   1 /*
   2  * Copyright (C) 2008-2009, Google Inc.
   3  * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com>
   4  * Copyright (C) 2007-2009, Robin Rosenberg <robin.rosenberg@dewire.com>
   5  * Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org>
   6  * and other copyright owners as documented in the project's IP log.
   7  *
   8  * This program and the accompanying materials are made available
   9  * under the terms of the Eclipse Distribution License v1.0 which
  10  * accompanies this distribution, is reproduced below, and is
  11  * available at http://www.eclipse.org/org/documents/edl-v10.php
  12  *
  13  * All rights reserved.
  14  *
  15  * Redistribution and use in source and binary forms, with or
  16  * without modification, are permitted provided that the following
  17  * conditions are met:
  18  *
  19  * - Redistributions of source code must retain the above copyright
  20  *   notice, this list of conditions and the following disclaimer.
  21  *
  22  * - Redistributions in binary form must reproduce the above
  23  *   copyright notice, this list of conditions and the following
  24  *   disclaimer in the documentation and/or other materials provided
  25  *   with the distribution.
  26  *
  27  * - Neither the name of the Eclipse Foundation, Inc. nor the
  28  *   names of its contributors may be used to endorse or promote
  29  *   products derived from this software without specific prior
  30  *   written permission.
  31  *
  32  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  33  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  34  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  35  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  36  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  37  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  38  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  39  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  40  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  41  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  42  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  43  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  44  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  45  */
  46
  47 package org.eclipse.jgit.lib;
  48
  49 import java.io.IOException;
  50 import java.io.InputStream;
  51 import java.util.Arrays;
  52 import java.util.Iterator;
  53 import java.util.NoSuchElementException;
  54
  55 import org.eclipse.jgit.errors.CorruptObjectException;
  56 import org.eclipse.jgit.util.IO;
  57 import org.eclipse.jgit.util.NB;
  58
  59 class PackIndexV1 extends PackIndex {
  60         private static final int IDX_HDR_LEN = 256 * 4;
  61
  62         private final long[] idxHeader;
  63
  64         private byte[][] idxdata;
  65
  66         private long objectCnt;
  67
  68         PackIndexV1(final InputStream fd, final byte[] hdr)
  69                         throws CorruptObjectException, IOException {
  70                 final byte[] fanoutTable = new byte[IDX_HDR_LEN];
  71                 System.arraycopy(hdr, 0, fanoutTable, 0, hdr.length);
  72                 IO.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length);
  73
  74                 idxHeader = new long[256]; // really unsigned 32-bit...
  75                 for (int k = 0; k < idxHeader.length; k++)
  76                         idxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4);
  77                 idxdata = new byte[idxHeader.length][];
  78                 for (int k = 0; k < idxHeader.length; k++) {
  79                         int n;
  80                         if (k == 0) {
  81                                 n = (int) (idxHeader[k]);
  82                         } else {
  83                                 n = (int) (idxHeader[k] - idxHeader[k - 1]);
  84                         }
  85                         if (n > 0) {
  86                                 idxdata[k] = new byte[n * (Constants.OBJECT_ID_LENGTH + 4)];
  87                                 IO.readFully(fd, idxdata[k], 0, idxdata[k].length);
  88                         }
  89                 }
  90                 objectCnt = idxHeader[255];
  91
  92                 packChecksum = new byte[20];
  93                 IO.readFully(fd, packChecksum, 0, packChecksum.length);
  94         }
  95
  96         long getObjectCount() {
  97                 return objectCnt;
  98         }
  99
 100         @Override
 101         long getOffset64Count() {
 102                 long n64 = 0;
 103                 for (final MutableEntry e : this) {
 104                         if (e.getOffset() >= Integer.MAX_VALUE)
 105                                 n64++;
 106                 }
 107                 return n64;
 108         }
 109
 110         @Override
 111         ObjectId getObjectId(final long nthPosition) {
 112                 int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
 113                 long base;
 114                 if (levelOne >= 0) {
 115                         // If we hit the bucket exactly the item is in the bucket, or
 116                         // any bucket before it which has the same object count.
 117                         //
 118                         base = idxHeader[levelOne];
 119                         while (levelOne > 0 && base == idxHeader[levelOne - 1])
 120                                 levelOne--;
 121                 } else {
 122                         // The item is in the bucket we would insert it into.
 123                         //
 124                         levelOne = -(levelOne + 1);
 125                 }
 126
 127                 base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
 128                 final int p = (int) (nthPosition - base);
 129                 final int dataIdx = ((4 + Constants.OBJECT_ID_LENGTH) * p) + 4;
 130                 return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
 131         }
 132
 133         long findOffset(final AnyObjectId objId) {
 134                 final int levelOne = objId.getFirstByte();
 135                 byte[] data = idxdata[levelOne];
 136                 if (data == null)
 137                         return -1;
 138                 int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
 139                 int low = 0;
 140                 do {
 141                         final int mid = (low + high) >>> 1;
 142                         final int pos = ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
 143                         final int cmp = objId.compareTo(data, pos);
 144                         if (cmp < 0)
 145                                 high = mid;
 146                         else if (cmp == 0) {
 147                                 int b0 = data[pos - 4] & 0xff;
 148                                 int b1 = data[pos - 3] & 0xff;
 149                                 int b2 = data[pos - 2] & 0xff;
 150                                 int b3 = data[pos - 1] & 0xff;
 151                                 return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
 152                         } else
 153                                 low = mid + 1;
 154                 } while (low < high);
 155                 return -1;
 156         }
 157
 158         @Override
 159         long findCRC32(AnyObjectId objId) {
 160                 throw new UnsupportedOperationException();
 161         }
 162
 163         @Override
 164         boolean hasCRC32Support() {
 165                 return false;
 166         }
 167
 168         public Iterator<MutableEntry> iterator() {
 169                 return new IndexV1Iterator();
 170         }
 171
 172         private class IndexV1Iterator extends EntriesIterator {
 173                 private int levelOne;
 174
 175                 private int levelTwo;
 176
 177                 @Override
 178                 protected MutableEntry initEntry() {
 179                         return new MutableEntry() {
 180                                 protected void ensureId() {
 181                                         idBuffer.fromRaw(idxdata[levelOne], levelTwo
 182                                                         - Constants.OBJECT_ID_LENGTH);
 183                                 }
 184                         };
 185                 }
 186
 187                 public MutableEntry next() {
 188                         for (; levelOne < idxdata.length; levelOne++) {
 189                                 if (idxdata[levelOne] == null)
 190                                         continue;
 191                                 if (levelTwo < idxdata[levelOne].length) {
 192                                         entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
 193                                         levelTwo += Constants.OBJECT_ID_LENGTH + 4;
 194                                         returnedNumber++;
 195                                         return entry;
 196                                 }
 197                                 levelTwo = 0;
 198                         }
 199                         throw new NoSuchElementException();
 200                 }
 201         }
 202 }