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> and others
  6.  *
  7.  * This program and the accompanying materials are made available under the
  8.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  9.  * https://www.eclipse.org/org/documents/edl-v10.php.
  10.  *
  11.  * SPDX-License-Identifier: BSD-3-Clause
  12.  */

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

  16. import java.io.IOException;
  17. import java.io.InputStream;
  18. import java.util.Arrays;
  19. import java.util.Iterator;
  20. import java.util.NoSuchElementException;
  21. import java.util.Set;

  23. import org.eclipse.jgit.errors.CorruptObjectException;
  24. import org.eclipse.jgit.internal.JGitText;
  25. import org.eclipse.jgit.lib.AbbreviatedObjectId;
  26. import org.eclipse.jgit.lib.AnyObjectId;
  27. import org.eclipse.jgit.lib.Constants;
  28. import org.eclipse.jgit.lib.ObjectId;
  29. import org.eclipse.jgit.util.IO;
  30. import org.eclipse.jgit.util.NB;

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

  35.     private final long[] idxHeader;

  37.     byte[][] idxdata;

  39.     private long objectCnt;

  41.     PackIndexV1(final InputStream fd, final byte[] hdr)
  42.             throws CorruptObjectException, IOException {
  43.         final byte[] fanoutTable = new byte[IDX_HDR_LEN];
  44.         System.arraycopy(hdr, 0, fanoutTable, 0, hdr.length);
  45.         IO.readFully(fd, fanoutTable, hdr.length, IDX_HDR_LEN - hdr.length);

  47.         idxHeader = new long[256]; // really unsigned 32-bit...
  48.         for (int k = 0; k < idxHeader.length; k++)
  49.             idxHeader[k] = NB.decodeUInt32(fanoutTable, k * 4);
  50.         idxdata = new byte[idxHeader.length][];
  51.         for (int k = 0; k < idxHeader.length; k++) {
  52.             long n;
  53.             if (k == 0) {
  54.                 n = idxHeader[k];
  55.             } else {
  56.                 n = idxHeader[k] - idxHeader[k - 1];
  57.             }
  58.             if (n > 0) {
  59.                 final long len = n * (Constants.OBJECT_ID_LENGTH + 4);
  60.                 if (len > Integer.MAX_VALUE - 8) // http://stackoverflow.com/a/8381338
  61.                     throw new IOException(JGitText.get().indexFileIsTooLargeForJgit);

  63.                 idxdata[k] = new byte[(int) len];
  64.                 IO.readFully(fd, idxdata[k], 0, idxdata[k].length);
  65.             }
  66.         }
  67.         objectCnt = idxHeader[255];

  69.         packChecksum = new byte[20];
  70.         IO.readFully(fd, packChecksum, 0, packChecksum.length);
  71.     }

  73.     /** {@inheritDoc} */
  74.     @Override
  75.     public long getObjectCount() {
  76.         return objectCnt;
  77.     }

  79.     /** {@inheritDoc} */
  80.     @Override
  81.     public long getOffset64Count() {
  82.         long n64 = 0;
  83.         for (MutableEntry e : this) {
  84.             if (e.getOffset() >= Integer.MAX_VALUE)
  85.                 n64++;
  86.         }
  87.         return n64;
  88.     }

  90.     private int findLevelOne(long nthPosition) {
  91.         int levelOne = Arrays.binarySearch(idxHeader, nthPosition + 1);
  92.         if (levelOne >= 0) {
  93.             // If we hit the bucket exactly the item is in the bucket, or
  94.             // any bucket before it which has the same object count.
  95.             //
  96.             long base = idxHeader[levelOne];
  97.             while (levelOne > 0 && base == idxHeader[levelOne - 1])
  98.                 levelOne--;
  99.         } else {
  100.             // The item is in the bucket we would insert it into.
  101.             //
  102.             levelOne = -(levelOne + 1);
  103.         }
  104.         return levelOne;
  105.     }

  107.     private int getLevelTwo(long nthPosition, int levelOne) {
  108.         final long base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
  109.         return (int) (nthPosition - base);
  110.     }

  112.     /** {@inheritDoc} */
  113.     @Override
  114.     public ObjectId getObjectId(long nthPosition) {
  115.         final int levelOne = findLevelOne(nthPosition);
  116.         final int p = getLevelTwo(nthPosition, levelOne);
  117.         final int dataIdx = idOffset(p);
  118.         return ObjectId.fromRaw(idxdata[levelOne], dataIdx);
  119.     }

  121.     @Override
  122.     long getOffset(long nthPosition) {
  123.         final int levelOne = findLevelOne(nthPosition);
  124.         final int levelTwo = getLevelTwo(nthPosition, levelOne);
  125.         final int p = (4 + Constants.OBJECT_ID_LENGTH) * levelTwo;
  126.         return NB.decodeUInt32(idxdata[levelOne], p);
  127.     }

  129.     /** {@inheritDoc} */
  130.     @Override
  131.     public long findOffset(AnyObjectId objId) {
  132.         final int levelOne = objId.getFirstByte();
  133.         byte[] data = idxdata[levelOne];
  134.         if (data == null)
  135.             return -1;
  136.         int high = data.length / (4 + Constants.OBJECT_ID_LENGTH);
  137.         int low = 0;
  138.         do {
  139.             final int mid = (low + high) >>> 1;
  140.             final int pos = idOffset(mid);
  141.             final int cmp = objId.compareTo(data, pos);
  142.             if (cmp < 0)
  143.                 high = mid;
  144.             else if (cmp == 0) {
  145.                 int b0 = data[pos - 4] & 0xff;
  146.                 int b1 = data[pos - 3] & 0xff;
  147.                 int b2 = data[pos - 2] & 0xff;
  148.                 int b3 = data[pos - 1] & 0xff;
  149.                 return (((long) b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
  150.             } else
  151.                 low = mid + 1;
  152.         } while (low < high);
  153.         return -1;
  154.     }

  156.     /** {@inheritDoc} */
  157.     @Override
  158.     public long findCRC32(AnyObjectId objId) {
  159.         throw new UnsupportedOperationException();
  160.     }

  162.     /** {@inheritDoc} */
  163.     @Override
  164.     public boolean hasCRC32Support() {
  165.         return false;
  166.     }

  168.     /** {@inheritDoc} */
  169.     @Override
  170.     public Iterator<MutableEntry> iterator() {
  171.         return new IndexV1Iterator();
  172.     }

  174.     /** {@inheritDoc} */
  175.     @Override
  176.     public void resolve(Set<ObjectId> matches, AbbreviatedObjectId id,
  177.             int matchLimit) throws IOException {
  178.         byte[] data = idxdata[id.getFirstByte()];
  179.         if (data == null)
  180.             return;
  181.         int max = data.length / (4 + Constants.OBJECT_ID_LENGTH);
  182.         int high = max;
  183.         int low = 0;
  184.         do {
  185.             int p = (low + high) >>> 1;
  186.             final int cmp = id.prefixCompare(data, idOffset(p));
  187.             if (cmp < 0)
  188.                 high = p;
  189.             else if (cmp == 0) {
  190.                 // We may have landed in the middle of the matches.  Move
  191.                 // backwards to the start of matches, then walk forwards.
  192.                 //
  193.                 while (0 < p && id.prefixCompare(data, idOffset(p - 1)) == 0)
  194.                     p--;
  195.                 for (; p < max && id.prefixCompare(data, idOffset(p)) == 0; p++) {
  196.                     matches.add(ObjectId.fromRaw(data, idOffset(p)));
  197.                     if (matches.size() > matchLimit)
  198.                         break;
  199.                 }
  200.                 return;
  201.             } else
  202.                 low = p + 1;
  203.         } while (low < high);
  204.     }

  206.     private static int idOffset(int mid) {
  207.         return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
  208.     }

  210.     private class IndexV1Iterator extends EntriesIterator {
  211.         int levelOne;

  213.         int levelTwo;

  215.         @Override
  216.         protected MutableEntry initEntry() {
  217.             return new MutableEntry() {
  218.                 @Override
  219.                 protected void ensureId() {
  220.                     idBuffer.fromRaw(idxdata[levelOne], levelTwo
  221.                             - Constants.OBJECT_ID_LENGTH);
  222.                 }
  223.             };
  224.         }

  226.         @Override
  227.         public MutableEntry next() {
  228.             for (; levelOne < idxdata.length; levelOne++) {
  229.                 if (idxdata[levelOne] == null)
  230.                     continue;
  231.                 if (levelTwo < idxdata[levelOne].length) {
  232.                     entry.offset = NB.decodeUInt32(idxdata[levelOne], levelTwo);
  233.                     levelTwo += Constants.OBJECT_ID_LENGTH + 4;
  234.                     returnedNumber++;
  235.                     return entry;
  236.                 }
  237.                 levelTwo = 0;
  238.             }
  239.             throw new NoSuchElementException();
  240.         }
  241.     }
  242. }
Created with JaCoCo 0.8.6.202009150832