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.  */

  47. package org.eclipse.jgit.internal.storage.file;

  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. import java.util.Set;

  56. import org.eclipse.jgit.errors.CorruptObjectException;
  57. import org.eclipse.jgit.internal.JGitText;
  58. import org.eclipse.jgit.lib.AbbreviatedObjectId;
  59. import org.eclipse.jgit.lib.AnyObjectId;
  60. import org.eclipse.jgit.lib.Constants;
  61. import org.eclipse.jgit.lib.ObjectId;
  62. import org.eclipse.jgit.util.IO;
  63. import org.eclipse.jgit.util.NB;

  65. class PackIndexV1 extends PackIndex {
  66.     private static final int IDX_HDR_LEN = 256 * 4;

  68.     private final long[] idxHeader;

  70.     byte[][] idxdata;

  72.     private long objectCnt;

  74.     PackIndexV1(final InputStream fd, final byte[] hdr)
  75.             throws CorruptObjectException, IOException {
  76.         final byte[] fanoutTable = new byte[IDX_HDR_LEN];
  77.         System.arraycopy(hdr, 0, fanoutTable, 0, hdr.length);
  78.         IO.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length);

  80.         idxHeader = new long[256]; // really unsigned 32-bit...
  81.         for (int k = 0; k < idxHeader.length; k++)
  82.             idxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4);
  83.         idxdata = new byte[idxHeader.length][];
  84.         for (int k = 0; k < idxHeader.length; k++) {
  85.             int n;
  86.             if (k == 0) {
  87.                 n = (int) (idxHeader[k]);
  88.             } else {
  89.                 n = (int) (idxHeader[k] - idxHeader[k - 1]);
  90.             }
  91.             if (n > 0) {
  92.                 final long len = n * (Constants.OBJECT_ID_LENGTH + 4);
  93.                 if (len > Integer.MAX_VALUE - 8) // http://stackoverflow.com/a/8381338
  94.                     throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);

  96.                 idxdata[k] = new byte[(int) len];
  97.                 IO.readFully(fd, idxdata[k], 0, idxdata[k].length);
  98.             }
  99.         }
  100.         objectCnt = idxHeader[255];

  102.         packChecksum = new byte[20];
  103.         IO.readFully(fd, packChecksum, 0, packChecksum.length);
  104.     }

  106.     /** {@inheritDoc} */
  107.     @Override
  108.     public long getObjectCount() {
  109.         return objectCnt;
  110.     }

  112.     /** {@inheritDoc} */
  113.     @Override
  114.     public long getOffset64Count() {
  115.         long n64 = 0;
  116.         for (MutableEntry e : this) {
  117.             if (e.getOffset() >= Integer.MAX_VALUE)
  118.                 n64++;
  119.         }
  120.         return n64;
  121.     }

  123.     private int findLevelOne(long nthPosition) {
  124.         int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
  125.         if (levelOne >= 0) {
  126.             // If we hit the bucket exactly the item is in the bucket, or
  127.             // any bucket before it which has the same object count.
  128.             //
  129.             long base = idxHeader[levelOne];
  130.             while (levelOne > 0 && base == idxHeader[levelOne - 1])
  131.                 levelOne--;
  132.         } else {
  133.             // The item is in the bucket we would insert it into.
  134.             //
  135.             levelOne = -(levelOne + 1);
  136.         }
  137.         return levelOne;
  138.     }

  140.     private int getLevelTwo(long nthPosition, int levelOne) {
  141.         final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
  142.         return (int) (nthPosition - base);
  143.     }

  145.     /** {@inheritDoc} */
  146.     @Override
  147.     public ObjectId getObjectId(long nthPosition) {
  148.         final int levelOne = findLevelOne(nthPosition);
  149.         final int p = getLevelTwo(nthPosition, levelOne);
  150.         final int dataIdx = idOffset(p);
  151.         return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
  152.     }

  154.     @Override
  155.     long getOffset(long nthPosition) {
  156.         final int levelOne = findLevelOne(nthPosition);
  157.         final int levelTwo = getLevelTwo(nthPosition, levelOne);
  158.         final int p = (4 + Constants.OBJECT_ID_LENGTH) * levelTwo;
  159.         return NB.decodeUInt32(idxdata[levelOne], p);
  160.     }

  162.     /** {@inheritDoc} */
  163.     @Override
  164.     public long findOffset(AnyObjectId objId) {
  165.         final int levelOne = objId.getFirstByte();
  166.         byte[] data = idxdata[levelOne];
  167.         if (data == null)
  168.             return -1;
  169.         int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
  170.         int low = 0;
  171.         do {
  172.             final int mid = (low + high) >>> 1;
  173.             final int pos = idOffset(mid);
  174.             final int cmp = objId.compareTo(data, pos);
  175.             if (cmp < 0)
  176.                 high = mid;
  177.             else if (cmp == 0) {
  178.                 int b0 = data[pos - 4] & 0xff;
  179.                 int b1 = data[pos - 3] & 0xff;
  180.                 int b2 = data[pos - 2] & 0xff;
  181.                 int b3 = data[pos - 1] & 0xff;
  182.                 return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
  183.             } else
  184.                 low = mid + 1;
  185.         } while (low < high);
  186.         return -1;
  187.     }

  189.     /** {@inheritDoc} */
  190.     @Override
  191.     public long findCRC32(AnyObjectId objId) {
  192.         throw new UnsupportedOperationException();
  193.     }

  195.     /** {@inheritDoc} */
  196.     @Override
  197.     public boolean hasCRC32Support() {
  198.         return false;
  199.     }

  201.     /** {@inheritDoc} */
  202.     @Override
  203.     public Iterator<MutableEntry> iterator() {
  204.         return new IndexV1Iterator();
  205.     }

  207.     /** {@inheritDoc} */
  208.     @Override
  209.     public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
  210.             int matchLimit) throws IOException {
  211.         byte[] data = idxdata[id.getFirstByte()];
  212.         if (data == null)
  213.             return;
  214.         int max = data.length / (4 + Constants.OBJECT_ID_LENGTH);
  215.         int high = max;
  216.         int low = 0;
  217.         do {
  218.             int p = (low + high) >>> 1;
  219.             final int cmp = id.prefixCompare(data, idOffset(p));
  220.             if (cmp < 0)
  221.                 high = p;
  222.             else if (cmp == 0) {
  223.                 // We may have landed in the middle of the matches.  Move
  224.                 // backwards to the start of matches, then walk forwards.
  225.                 //
  226.                 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
  227.                     p--;
  228.                 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
  229.                     matches.add(ObjectId.fromRaw(data, idOffset(p)));
  230.                     if (matches.size() > matchLimit)
  231.                         break;
  232.                 }
  233.                 return;
  234.             } else
  235.                 low = p + 1;
  236.         } while (low < high);
  237.     }

  239.     private static int idOffset(int mid) {
  240.         return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
  241.     }

  243.     private class IndexV1Iterator extends EntriesIterator {
  244.         int levelOne;

  246.         int levelTwo;

  248.         @Override
  249.         protected MutableEntry initEntry() {
  250.             return new MutableEntry() {
  251.                 @Override
  252.                 protected void ensureId() {
  253.                     idBuffer.fromRaw(idxdata[levelOne], levelTwo
  254.                             - Constants.OBJECT_ID_LENGTH);
  255.                 }
  256.             };
  257.         }

  259.         @Override
  260.         public MutableEntry next() {
  261.             for (; levelOne < idxdata.length; levelOne++) {
  262.                 if (idxdata[levelOne] == null)
  263.                     continue;
  264.                 if (levelTwo < idxdata[levelOne].length) {
  265.                     entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
  266.                     levelTwo += Constants.OBJECT_ID_LENGTH + 4;
  267.                     returnedNumber++;
  268.                     return entry;
  269.                 }
  270.                 levelTwo = 0;
  271.             }
  272.             throw new NoSuchElementException();
  273.         }
  274.     }
  275. }
Created with JaCoCo 0.8.4.201905082037