| /* |
| * Copyright (C) 2008-2009, Google Inc. |
| * Copyright (C) 2008, Marek Zawirski <marek.zawirski@gmail.com> |
| * Copyright (C) 2007-2009, Robin Rosenberg <robin.rosenberg@dewire.com> |
| * Copyright (C) 2006-2008, Shawn O. Pearce <spearce@spearce.org> |
| * and other copyright owners as documented in the project's IP log. |
| * |
| * This program and the accompanying materials are made available |
| * under the terms of the Eclipse Distribution License v1.0 which |
| * accompanies this distribution, is reproduced below, and is |
| * available at http://www.eclipse.org/org/documents/edl-v10.php |
| * |
| * All rights reserved. |
| * |
| * Redistribution and use in source and binary forms, with or |
| * without modification, are permitted provided that the following |
| * conditions are met: |
| * |
| * - Redistributions of source code must retain the above copyright |
| * notice, this list of conditions and the following disclaimer. |
| * |
| * - Redistributions in binary form must reproduce the above |
| * copyright notice, this list of conditions and the following |
| * disclaimer in the documentation and/or other materials provided |
| * with the distribution. |
| * |
| * - Neither the name of the Eclipse Foundation, Inc. nor the |
| * names of its contributors may be used to endorse or promote |
| * products derived from this software without specific prior |
| * written permission. |
| * |
| * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND |
| * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, |
| * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES |
| * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE |
| * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR |
| * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
| * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT |
| * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; |
| * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER |
| * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, |
| * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) |
| * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF |
| * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
| */ |
| |
| package org.eclipse.jgit.internal.storage.file; |
| |
| import java.io.IOException; |
| import java.io.InputStream; |
| import java.util.Arrays; |
| import java.util.Iterator; |
| import java.util.NoSuchElementException; |
| import java.util.Set; |
| |
| import org.eclipse.jgit.errors.CorruptObjectException; |
| import org.eclipse.jgit.internal.JGitText; |
| import org.eclipse.jgit.lib.AbbreviatedObjectId; |
| import org.eclipse.jgit.lib.AnyObjectId; |
| import org.eclipse.jgit.lib.Constants; |
| import org.eclipse.jgit.lib.ObjectId; |
| import org.eclipse.jgit.util.IO; |
| import org.eclipse.jgit.util.NB; |
| |
| class PackIndexV1 extends PackIndex { |
| private static final int IDX_HDR_LEN = 256 * 4; |
| |
| private final long[] idxHeader; |
| |
| byte[][] idxdata; |
| |
| private long objectCnt; |
| |
| PackIndexV1(final InputStream fd, final byte[] hdr) |
| throws CorruptObjectException, IOException { |
| final byte[] fanoutTable = new byte[IDX_HDR_LEN]; |
| System.arraycopy(hdr, 0, fanoutTable, 0, hdr.length); |
| IO.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length); |
| |
| idxHeader = new long[256]; // really unsigned 32-bit... |
| for (int k = 0; k < idxHeader.length; k++) |
| idxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4); |
| idxdata = new byte[idxHeader.length][]; |
| for (int k = 0; k < idxHeader.length; k++) { |
| int n; |
| if (k == 0) { |
| n = (int) (idxHeader[k]); |
| } else { |
| n = (int) (idxHeader[k] - idxHeader[k - 1]); |
| } |
| if (n > 0) { |
| final long len = n * (Constants.OBJECT_ID_LENGTH + 4); |
| if (len > Integer.MAX_VALUE - 8) // http://stackoverflow.com/a/8381338 |
| throw new IOException(JGitText.get().indexFileIsTooLargeForJgit); |
| |
| idxdata[k] = new byte[(int) len]; |
| IO.readFully(fd, idxdata[k], 0, idxdata[k].length); |
| } |
| } |
| objectCnt = idxHeader[255]; |
| |
| packChecksum = new byte[20]; |
| IO.readFully(fd, packChecksum, 0, packChecksum.length); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public long getObjectCount() { |
| return objectCnt; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public long getOffset64Count() { |
| long n64 = 0; |
| for (MutableEntry e : this) { |
| if (e.getOffset() >= Integer.MAX_VALUE) |
| n64++; |
| } |
| return n64; |
| } |
| |
| private int findLevelOne(long nthPosition) { |
| int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1); |
| if (levelOne >= 0) { |
| // If we hit the bucket exactly the item is in the bucket, or |
| // any bucket before it which has the same object count. |
| // |
| long base = idxHeader[levelOne]; |
| while (levelOne > 0 && base == idxHeader[levelOne - 1]) |
| levelOne--; |
| } else { |
| // The item is in the bucket we would insert it into. |
| // |
| levelOne = -(levelOne + 1); |
| } |
| return levelOne; |
| } |
| |
| private int getLevelTwo(long nthPosition, int levelOne) { |
| final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0; |
| return (int) (nthPosition - base); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public ObjectId getObjectId(long nthPosition) { |
| final int levelOne = findLevelOne(nthPosition); |
| final int p = getLevelTwo(nthPosition, levelOne); |
| final int dataIdx = idOffset(p); |
| return ObjectId.fromRaw(idxdata[levelOne], dataIdx); |
| } |
| |
| @Override |
| long getOffset(long nthPosition) { |
| final int levelOne = findLevelOne(nthPosition); |
| final int levelTwo = getLevelTwo(nthPosition, levelOne); |
| final int p = (4 + Constants.OBJECT_ID_LENGTH) * levelTwo; |
| return NB.decodeUInt32(idxdata[levelOne], p); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public long findOffset(AnyObjectId objId) { |
| final int levelOne = objId.getFirstByte(); |
| byte[] data = idxdata[levelOne]; |
| if (data == null) |
| return -1; |
| int high = data.length / (4 + Constants.OBJECT_ID_LENGTH); |
| int low = 0; |
| do { |
| final int mid = (low + high) >>> 1; |
| final int pos = idOffset(mid); |
| final int cmp = objId.compareTo(data, pos); |
| if (cmp < 0) |
| high = mid; |
| else if (cmp == 0) { |
| int b0 = data[pos - 4] & 0xff; |
| int b1 = data[pos - 3] & 0xff; |
| int b2 = data[pos - 2] & 0xff; |
| int b3 = data[pos - 1] & 0xff; |
| return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3); |
| } else |
| low = mid + 1; |
| } while (low < high); |
| return -1; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public long findCRC32(AnyObjectId objId) { |
| throw new UnsupportedOperationException(); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public boolean hasCRC32Support() { |
| return false; |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public Iterator<MutableEntry> iterator() { |
| return new IndexV1Iterator(); |
| } |
| |
| /** {@inheritDoc} */ |
| @Override |
| public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id, |
| int matchLimit) throws IOException { |
| byte[] data = idxdata[id.getFirstByte()]; |
| if (data == null) |
| return; |
| int max = data.length / (4 + Constants.OBJECT_ID_LENGTH); |
| int high = max; |
| int low = 0; |
| do { |
| int p = (low + high) >>> 1; |
| final int cmp = id.prefixCompare(data, idOffset(p)); |
| if (cmp < 0) |
| high = p; |
| else if (cmp == 0) { |
| // We may have landed in the middle of the matches. Move |
| // backwards to the start of matches, then walk forwards. |
| // |
| while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0) |
| p--; |
| for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) { |
| matches.add(ObjectId.fromRaw(data, idOffset(p))); |
| if (matches.size() > matchLimit) |
| break; |
| } |
| return; |
| } else |
| low = p + 1; |
| } while (low < high); |
| } |
| |
| private static int idOffset(int mid) { |
| return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4; |
| } |
| |
| private class IndexV1Iterator extends EntriesIterator { |
| int levelOne; |
| |
| int levelTwo; |
| |
| @Override |
| protected MutableEntry initEntry() { |
| return new MutableEntry() { |
| @Override |
| protected void ensureId() { |
| idBuffer.fromRaw(idxdata[levelOne], levelTwo |
| - Constants.OBJECT_ID_LENGTH); |
| } |
| }; |
| } |
| |
| @Override |
| public MutableEntry next() { |
| for (; levelOne < idxdata.length; levelOne++) { |
| if (idxdata[levelOne] == null) |
| continue; |
| if (levelTwo < idxdata[levelOne].length) { |
| entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo); |
| levelTwo += Constants.OBJECT_ID_LENGTH + 4; |
| returnedNumber++; |
| return entry; |
| } |
| levelTwo = 0; |
| } |
| throw new NoSuchElementException(); |
| } |
| } |
| } |