Package org.eclipse.jgit.internal.storage.file

Class PackReverseIndex

  • public class PackReverseIndex
extends java.lang.Object

    Reverse index for forward pack index. Provides operations based on offset instead of object id. Such offset-based reverse lookups are performed in O(log n) time.

    See Also:
    PackIndex, Pack

    • Field Summary

      Fields 
      Modifier and Type Field Description
      private long bucketSize
      The number of bytes per entry in the offsetIndex.
      private PackIndex index
      Index we were created from, and that has our ObjectId data.
      private int[] nth
      Mapping from indices in offset order to indices in SHA-1 order.
      private int[] offsetIndex
      An index into the nth mapping, where the value is the position after the the last index that contains the values of the bucket.

    • Constructor Summary

      Constructors 
      Constructor Description
      PackReverseIndex​(PackIndex packIndex)
      Create reverse index from straight/forward pack index, by indexing all its entries.

    • Method Summary

      All Methods Instance Methods Concrete Methods 
      Modifier and Type Method Description
      private int binarySearch​(long offset)  
      long findNextOffset​(long offset, long maxOffset)
      Search for the next offset to the specified offset in this pack (reverse) index.
      ObjectId findObject​(long offset)
      Search for object id with the specified start offset in this pack (reverse) index.
      (package private) ObjectId findObjectByPosition​(int nthPosition)  
      (package private) int findPostion​(long offset)  

      • Methods inherited from class java.lang.Object

        clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

    • Field Detail

      • index

        private final PackIndex index
        Index we were created from, and that has our ObjectId data.

      • bucketSize

        private final long bucketSize
        The number of bytes per entry in the offsetIndex.

      • offsetIndex

        private final int[] offsetIndex
        An index into the nth mapping, where the value is the position after the the last index that contains the values of the bucket. For example given offset o (and bucket = o / bucketSize), the offset will be contained in the range nth[offsetIndex[bucket - 1]] inclusive to nth[offsetIndex[bucket]] exclusive. See binarySearch(long)

      • nth

        private final int[] nth
        Mapping from indices in offset order to indices in SHA-1 order.

    • Constructor Detail

      • PackReverseIndex

        public PackReverseIndex​(PackIndex packIndex)
        Create reverse index from straight/forward pack index, by indexing all its entries.
        Parameters:
        packIndex - forward index - entries to (reverse) index.

    • Method Detail

      • findObject

        public ObjectId findObject​(long offset)
        Search for object id with the specified start offset in this pack (reverse) index.
        Parameters:
        offset - start offset of object to find.
        Returns:
        object id for this offset, or null if no object was found.

      • findNextOffset

        public long findNextOffset​(long offset,
                           long maxOffset)
                    throws CorruptObjectException
        Search for the next offset to the specified offset in this pack (reverse) index.
        Parameters:
        offset - start offset of previous object (must be valid-existing offset).
        maxOffset - maximum offset in a pack (returned when there is no next offset).
        Returns:
        offset of the next object in a pack or maxOffset if provided offset was the last one.
        Throws:
        CorruptObjectException - when there is no object with the provided offset.

      • findPostion

        int findPostion​(long offset)

      • binarySearch

        private int binarySearch​(long offset)

      • findObjectByPosition

        ObjectId findObjectByPosition​(int nthPosition)