PackBitmapIndexBuilder.java

  1. /*
  2.  * Copyright (C) 2012, Google Inc. and others
  3.  *
  4.  * This program and the accompanying materials are made available under the
  5.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  6.  * https://www.eclipse.org/org/documents/edl-v10.php.
  7.  *
  8.  * SPDX-License-Identifier: BSD-3-Clause
  9.  */

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

  13. import java.text.MessageFormat;
  14. import java.util.ArrayList;
  15. import java.util.Collections;
  16. import java.util.LinkedList;
  17. import java.util.List;

  19. import org.eclipse.jgit.internal.JGitText;
  20. import org.eclipse.jgit.internal.storage.pack.BitmapCommit;
  21. import org.eclipse.jgit.internal.storage.pack.ObjectToPack;
  22. import org.eclipse.jgit.lib.AnyObjectId;
  23. import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
  24. import org.eclipse.jgit.lib.Constants;
  25. import org.eclipse.jgit.lib.ObjectId;
  26. import org.eclipse.jgit.lib.ObjectIdOwnerMap;
  27. import org.eclipse.jgit.util.BlockList;

  29. import com.googlecode.javaewah.EWAHCompressedBitmap;

  31. /**
  32.  * Helper for constructing
  33.  * {@link org.eclipse.jgit.internal.storage.file.PackBitmapIndex}es.
  34.  */
  35. public class PackBitmapIndexBuilder extends BasePackBitmapIndex {
  36.     private static final int MAX_XOR_OFFSET_SEARCH = 10;

  38.     private final EWAHCompressedBitmap commits;
  39.     private final EWAHCompressedBitmap trees;
  40.     private final EWAHCompressedBitmap blobs;
  41.     private final EWAHCompressedBitmap tags;
  42.     private final BlockList<PositionEntry> byOffset;

  44.     private final LinkedList<StoredBitmap>
  45.             bitmapsToWriteXorBuffer = new LinkedList<>();

  47.     private List<StoredEntry> bitmapsToWrite = new ArrayList<>();

  49.     final ObjectIdOwnerMap<PositionEntry>
  50.             positionEntries = new ObjectIdOwnerMap<>();

  52.     /**
  53.      * Creates a PackBitmapIndex used for building the contents of an index
  54.      * file.
  55.      *
  56.      * @param objects
  57.      *            objects sorted by name. The list must be initially sorted by
  58.      *            ObjectId (name); it will be resorted in place.
  59.      */
  60.     public PackBitmapIndexBuilder(List<ObjectToPack> objects) {
  61.         super(new ObjectIdOwnerMap<StoredBitmap>());
  62.         byOffset = new BlockList<>(objects.size());
  63.         sortByOffsetAndIndex(byOffset, positionEntries, objects);

  65.         // 64 objects fit in a single long word (64 bits).
  66.         // On average a repository is 30% commits, 30% trees, 30% blobs.
  67.         // Initialize bitmap capacity for worst case to minimize growing.
  68.         int sizeInWords = Math.max(4, byOffset.size() / 64 / 3);
  69.         commits = new EWAHCompressedBitmap(sizeInWords);
  70.         trees = new EWAHCompressedBitmap(sizeInWords);
  71.         blobs = new EWAHCompressedBitmap(sizeInWords);
  72.         tags = new EWAHCompressedBitmap(sizeInWords);
  73.         for (int i = 0; i < objects.size(); i++) {
  74.             int type = objects.get(i).getType();
  75.             switch (type) {
  76.             case Constants.OBJ_COMMIT:
  77.                 commits.set(i);
  78.                 break;
  79.             case Constants.OBJ_TREE:
  80.                 trees.set(i);
  81.                 break;
  82.             case Constants.OBJ_BLOB:
  83.                 blobs.set(i);
  84.                 break;
  85.             case Constants.OBJ_TAG:
  86.                 tags.set(i);
  87.                 break;
  88.             default:
  89.                 throw new IllegalArgumentException(MessageFormat.format(
  90.                         JGitText.get().badObjectType, String.valueOf(type)));
  91.             }
  92.         }
  93.         commits.trim();
  94.         trees.trim();
  95.         blobs.trim();
  96.         tags.trim();
  97.     }

  99.     private static void sortByOffsetAndIndex(BlockList<PositionEntry> byOffset,
  100.             ObjectIdOwnerMap<PositionEntry> positionEntries,
  101.             List<ObjectToPack> entries) {
  102.         for (int i = 0; i < entries.size(); i++) {
  103.             positionEntries.add(new PositionEntry(entries.get(i), i));
  104.         }
  105.         Collections.sort(entries, (ObjectToPack a, ObjectToPack b) -> Long
  106.                 .signum(a.getOffset() - b.getOffset()));
  107.         for (int i = 0; i < entries.size(); i++) {
  108.             PositionEntry e = positionEntries.get(entries.get(i));
  109.             e.offsetPosition = i;
  110.             byOffset.add(e);
  111.         }
  112.     }

  114.     /**
  115.      * Get set of objects included in the pack.
  116.      *
  117.      * @return set of objects included in the pack.
  118.      */
  119.     public ObjectIdOwnerMap<ObjectIdOwnerMap.Entry> getObjectSet() {
  120.         ObjectIdOwnerMap<ObjectIdOwnerMap.Entry> r = new ObjectIdOwnerMap<>();
  121.         for (PositionEntry e : byOffset) {
  122.             r.add(new ObjectIdOwnerMap.Entry(e) {
  123.                 // A new entry that copies the ObjectId
  124.             });
  125.         }
  126.         return r;
  127.     }

  129.     /**
  130.      * Stores the bitmap for the objectId.
  131.      *
  132.      * @param objectId
  133.      *            the object id key for the bitmap.
  134.      * @param bitmap
  135.      *            the bitmap
  136.      * @param flags
  137.      *            the flags to be stored with the bitmap
  138.      */
  139.     public void addBitmap(AnyObjectId objectId, Bitmap bitmap, int flags) {
  140.         addBitmap(objectId, bitmap.retrieveCompressed(), flags);
  141.     }

  143.     /**
  144.      * Processes a commit and prepares its bitmap to write to the bitmap index
  145.      * file.
  146.      *
  147.      * @param c
  148.      *            the commit corresponds to the bitmap.
  149.      * @param bitmap
  150.      *            the bitmap to be written.
  151.      * @param flags
  152.      *            the flags of the commit.
  153.      */
  154.     public void processBitmapForWrite(BitmapCommit c, Bitmap bitmap,
  155.             int flags) {
  156.         EWAHCompressedBitmap compressed = bitmap.retrieveCompressed();
  157.         compressed.trim();
  158.         StoredBitmap newest = new StoredBitmap(c, compressed, null, flags);

  160.         bitmapsToWriteXorBuffer.add(newest);
  161.         if (bitmapsToWriteXorBuffer.size() > MAX_XOR_OFFSET_SEARCH) {
  162.             bitmapsToWrite.add(
  163.                     generateStoredEntry(bitmapsToWriteXorBuffer.pollFirst()));
  164.         }

  166.         if (c.isAddToIndex()) {
  167.             // The Bitmap map in the base class is used to make revwalks
  168.             // efficient, so only add bitmaps that keep it efficient without
  169.             // bloating memory.
  170.             addBitmap(c, bitmap, flags);
  171.         }
  172.     }

  174.     private StoredEntry generateStoredEntry(StoredBitmap bitmapToWrite) {
  175.         int bestXorOffset = 0;
  176.         EWAHCompressedBitmap bestBitmap = bitmapToWrite.getBitmap();

  178.         int offset = 1;
  179.         for (StoredBitmap curr : bitmapsToWriteXorBuffer) {
  180.             EWAHCompressedBitmap bitmap = curr.getBitmap()
  181.                     .xor(bitmapToWrite.getBitmap());
  182.             if (bitmap.sizeInBytes() < bestBitmap.sizeInBytes()) {
  183.                 bestBitmap = bitmap;
  184.                 bestXorOffset = offset;
  185.             }
  186.             offset++;
  187.         }

  189.         PositionEntry entry = positionEntries.get(bitmapToWrite);
  190.         if (entry == null) {
  191.             throw new IllegalStateException();
  192.         }
  193.         bestBitmap.trim();
  194.         StoredEntry result = new StoredEntry(entry.namePosition, bestBitmap,
  195.                 bestXorOffset, bitmapToWrite.getFlags());

  197.         return result;
  198.     }

  200.     /**
  201.      * Stores the bitmap for the objectId.
  202.      *
  203.      * @param objectId
  204.      *            the object id key for the bitmap.
  205.      * @param bitmap
  206.      *            the bitmap
  207.      * @param flags
  208.      *            the flags to be stored with the bitmap
  209.      */
  210.     public void addBitmap(
  211.             AnyObjectId objectId, EWAHCompressedBitmap bitmap, int flags) {
  212.         bitmap.trim();
  213.         StoredBitmap result = new StoredBitmap(objectId, bitmap, null, flags);
  214.         getBitmaps().add(result);
  215.     }

  217.     /** {@inheritDoc} */
  218.     @Override
  219.     public EWAHCompressedBitmap ofObjectType(
  220.             EWAHCompressedBitmap bitmap, int type) {
  221.         switch (type) {
  222.         case Constants.OBJ_BLOB:
  223.             return getBlobs().and(bitmap);
  224.         case Constants.OBJ_TREE:
  225.             return getTrees().and(bitmap);
  226.         case Constants.OBJ_COMMIT:
  227.             return getCommits().and(bitmap);
  228.         case Constants.OBJ_TAG:
  229.             return getTags().and(bitmap);
  230.         }
  231.         throw new IllegalArgumentException();
  232.     }

  234.     /** {@inheritDoc} */
  235.     @Override
  236.     public int findPosition(AnyObjectId objectId) {
  237.         PositionEntry entry = positionEntries.get(objectId);
  238.         if (entry == null)
  239.             return -1;
  240.         return entry.offsetPosition;
  241.     }

  243.     /** {@inheritDoc} */
  244.     @Override
  245.     public ObjectId getObject(int position) throws IllegalArgumentException {
  246.         ObjectId objectId = byOffset.get(position);
  247.         if (objectId == null)
  248.             throw new IllegalArgumentException();
  249.         return objectId;
  250.     }

  252.     /**
  253.      * Get the commit object bitmap.
  254.      *
  255.      * @return the commit object bitmap.
  256.      */
  257.     public EWAHCompressedBitmap getCommits() {
  258.         return commits;
  259.     }

  261.     /**
  262.      * Get the tree object bitmap.
  263.      *
  264.      * @return the tree object bitmap.
  265.      */
  266.     public EWAHCompressedBitmap getTrees() {
  267.         return trees;
  268.     }

  270.     /**
  271.      * Get the blob object bitmap.
  272.      *
  273.      * @return the blob object bitmap.
  274.      */
  275.     public EWAHCompressedBitmap getBlobs() {
  276.         return blobs;
  277.     }

  279.     /**
  280.      * Get the tag object bitmap.
  281.      *
  282.      * @return the tag object bitmap.
  283.      */
  284.     public EWAHCompressedBitmap getTags() {
  285.         return tags;
  286.     }

  288.     /**
  289.      * Get the index storage options.
  290.      *
  291.      * @return the index storage options.
  292.      */
  293.     public int getOptions() {
  294.         return PackBitmapIndexV1.OPT_FULL;
  295.     }

  297.     /** {@inheritDoc} */
  298.     @Override
  299.     public int getBitmapCount() {
  300.         return bitmapsToWriteXorBuffer.size() + bitmapsToWrite.size();
  301.     }

  303.     /**
  304.      * Remove all the bitmaps entries added.
  305.      *
  306.      * @param size
  307.      *            the expected number of bitmap entries to be written.
  308.      */
  309.     public void resetBitmaps(int size) {
  310.         getBitmaps().clear();
  311.         bitmapsToWrite = new ArrayList<>(size);
  312.     }

  314.     /** {@inheritDoc} */
  315.     @Override
  316.     public int getObjectCount() {
  317.         return byOffset.size();
  318.     }

  320.     /**
  321.      * Get list of xor compressed entries that need to be written.
  322.      *
  323.      * @return a list of the xor compressed entries.
  324.      */
  325.     public List<StoredEntry> getCompressedBitmaps() {
  326.         while (!bitmapsToWriteXorBuffer.isEmpty()) {
  327.             bitmapsToWrite.add(
  328.                     generateStoredEntry(bitmapsToWriteXorBuffer.pollFirst()));
  329.         }

  331.         Collections.reverse(bitmapsToWrite);
  332.         return bitmapsToWrite;
  333.     }

  335.     /** Data object for the on disk representation of a bitmap entry. */
  336.     public static final class StoredEntry {
  337.         private final long objectId;
  338.         private final EWAHCompressedBitmap bitmap;
  339.         private final int xorOffset;
  340.         private final int flags;

  342.         StoredEntry(long objectId, EWAHCompressedBitmap bitmap,
  343.                 int xorOffset, int flags) {
  344.             this.objectId = objectId;
  345.             this.bitmap = bitmap;
  346.             this.xorOffset = xorOffset;
  347.             this.flags = flags;
  348.         }

  350.         /** @return the bitmap */
  351.         public EWAHCompressedBitmap getBitmap() {
  352.             return bitmap;
  353.         }

  355.         /** @return the xorOffset */
  356.         public int getXorOffset() {
  357.             return xorOffset;
  358.         }

  360.         /** @return the flags */
  361.         public int getFlags() {
  362.             return flags;
  363.         }

  365.         /** @return the ObjectId */
  366.         public long getObjectId() {
  367.             return objectId;
  368.         }
  369.     }

  371.     private static final class PositionEntry extends ObjectIdOwnerMap.Entry {
  372.         final int namePosition;

  374.         int offsetPosition;

  376.         PositionEntry(AnyObjectId objectId, int namePosition) {
  377.             super(objectId);
  378.             this.namePosition = namePosition;
  379.         }
  380.     }
  381. }
Created with JaCoCo 0.8.7.202105040129