PackBitmapIndexBuilder.java

  1. /*
  2.  * Copyright (C) 2012, Google Inc.
  3.  * and other copyright owners as documented in the project's IP log.
  4.  *
  5.  * This program and the accompanying materials are made available
  6.  * under the terms of the Eclipse Distribution License v1.0 which
  7.  * accompanies this distribution, is reproduced below, and is
  8.  * available at http://www.eclipse.org/org/documents/edl-v10.php
  9.  *
  10.  * All rights reserved.
  11.  *
  12.  * Redistribution and use in source and binary forms, with or
  13.  * without modification, are permitted provided that the following
  14.  * conditions are met:
  15.  *
  16.  * - Redistributions of source code must retain the above copyright
  17.  *   notice, this list of conditions and the following disclaimer.
  18.  *
  19.  * - Redistributions in binary form must reproduce the above
  20.  *   copyright notice, this list of conditions and the following
  21.  *   disclaimer in the documentation and/or other materials provided
  22.  *   with the distribution.
  23.  *
  24.  * - Neither the name of the Eclipse Foundation, Inc. nor the
  25.  *   names of its contributors may be used to endorse or promote
  26.  *   products derived from this software without specific prior
  27.  *   written permission.
  28.  *
  29.  * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
  30.  * CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
  31.  * INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
  32.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  33.  * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
  34.  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  35.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
  36.  * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
  37.  * LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
  38.  * CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
  39.  * STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
  40.  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
  41.  * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  42.  */

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

  46. import java.text.MessageFormat;
  47. import java.util.Collections;
  48. import java.util.Comparator;
  49. import java.util.Iterator;
  50. import java.util.List;
  51. import java.util.NoSuchElementException;

  53. import org.eclipse.jgit.internal.JGitText;
  54. import org.eclipse.jgit.internal.storage.file.BitmapIndexImpl.CompressedBitmap;
  55. import org.eclipse.jgit.internal.storage.pack.ObjectToPack;
  56. import org.eclipse.jgit.lib.AnyObjectId;
  57. import org.eclipse.jgit.lib.BitmapIndex.Bitmap;
  58. import org.eclipse.jgit.lib.BitmapIndex.BitmapBuilder;
  59. import org.eclipse.jgit.lib.Constants;
  60. import org.eclipse.jgit.lib.ObjectId;
  61. import org.eclipse.jgit.lib.ObjectIdOwnerMap;
  62. import org.eclipse.jgit.util.BlockList;

  64. import com.googlecode.javaewah.EWAHCompressedBitmap;

  66. /**
  67.  * Helper for constructing
  68.  * {@link org.eclipse.jgit.internal.storage.file.PackBitmapIndex}es.
  69.  */
  70. public class PackBitmapIndexBuilder extends BasePackBitmapIndex {
  71.     private static final int MAX_XOR_OFFSET_SEARCH = 10;

  73.     private final EWAHCompressedBitmap commits;
  74.     private final EWAHCompressedBitmap trees;
  75.     private final EWAHCompressedBitmap blobs;
  76.     private final EWAHCompressedBitmap tags;
  77.     private final BlockList<PositionEntry> byOffset;
  78.     final BlockList<StoredBitmap>
  79.             byAddOrder = new BlockList<>();
  80.     final ObjectIdOwnerMap<PositionEntry>
  81.             positionEntries = new ObjectIdOwnerMap<>();

  83.     /**
  84.      * Creates a PackBitmapIndex used for building the contents of an index
  85.      * file.
  86.      *
  87.      * @param objects
  88.      *            objects sorted by name. The list must be initially sorted by
  89.      *            ObjectId (name); it will be resorted in place.
  90.      */
  91.     public PackBitmapIndexBuilder(List<ObjectToPack> objects) {
  92.         super(new ObjectIdOwnerMap<StoredBitmap>());
  93.         byOffset = new BlockList<>(objects.size());
  94.         sortByOffsetAndIndex(byOffset, positionEntries, objects);

  96.         // 64 objects fit in a single long word (64 bits).
  97.         // On average a repository is 30% commits, 30% trees, 30% blobs.
  98.         // Initialize bitmap capacity for worst case to minimize growing.
  99.         int sizeInWords = Math.max(4, byOffset.size() / 64 / 3);
  100.         commits = new EWAHCompressedBitmap(sizeInWords);
  101.         trees = new EWAHCompressedBitmap(sizeInWords);
  102.         blobs = new EWAHCompressedBitmap(sizeInWords);
  103.         tags = new EWAHCompressedBitmap(sizeInWords);
  104.         for (int i = 0; i < objects.size(); i++) {
  105.             int type = objects.get(i).getType();
  106.             switch (type) {
  107.             case Constants.OBJ_COMMIT:
  108.                 commits.set(i);
  109.                 break;
  110.             case Constants.OBJ_TREE:
  111.                 trees.set(i);
  112.                 break;
  113.             case Constants.OBJ_BLOB:
  114.                 blobs.set(i);
  115.                 break;
  116.             case Constants.OBJ_TAG:
  117.                 tags.set(i);
  118.                 break;
  119.             default:
  120.                 throw new IllegalArgumentException(MessageFormat.format(
  121.                         JGitText.get().badObjectType, String.valueOf(type)));
  122.             }
  123.         }
  124.         commits.trim();
  125.         trees.trim();
  126.         blobs.trim();
  127.         tags.trim();
  128.     }

  130.     private static void sortByOffsetAndIndex(BlockList<PositionEntry> byOffset,
  131.             ObjectIdOwnerMap<PositionEntry> positionEntries,
  132.             List<ObjectToPack> entries) {
  133.         for (int i = 0; i < entries.size(); i++) {
  134.             positionEntries.add(new PositionEntry(entries.get(i), i));
  135.         }
  136.         Collections.sort(entries, new Comparator<ObjectToPack>() {
  137.             @Override
  138.             public int compare(ObjectToPack a, ObjectToPack b) {
  139.                 return Long.signum(a.getOffset() - b.getOffset());
  140.             }
  141.         });
  142.         for (int i = 0; i < entries.size(); i++) {
  143.             PositionEntry e = positionEntries.get(entries.get(i));
  144.             e.offsetPosition = i;
  145.             byOffset.add(e);
  146.         }
  147.     }

  149.     /**
  150.      * Get set of objects included in the pack.
  151.      *
  152.      * @return set of objects included in the pack.
  153.      */
  154.     public ObjectIdOwnerMap<ObjectIdOwnerMap.Entry> getObjectSet() {
  155.         ObjectIdOwnerMap<ObjectIdOwnerMap.Entry> r = new ObjectIdOwnerMap<>();
  156.         for (PositionEntry e : byOffset) {
  157.             r.add(new ObjectIdOwnerMap.Entry(e) {
  158.                 // A new entry that copies the ObjectId
  159.             });
  160.         }
  161.         return r;
  162.     }

  164.     /**
  165.      * Stores the bitmap for the objectId.
  166.      *
  167.      * @param objectId
  168.      *            the object id key for the bitmap.
  169.      * @param bitmap
  170.      *            the bitmap
  171.      * @param flags
  172.      *            the flags to be stored with the bitmap
  173.      */
  174.     public void addBitmap(AnyObjectId objectId, Bitmap bitmap, int flags) {
  175.         if (bitmap instanceof BitmapBuilder)
  176.             bitmap = ((BitmapBuilder) bitmap).build();

  178.         EWAHCompressedBitmap compressed;
  179.         if (bitmap instanceof CompressedBitmap)
  180.             compressed = ((CompressedBitmap) bitmap).getEwahCompressedBitmap();
  181.         else
  182.             throw new IllegalArgumentException(bitmap.getClass().toString());

  184.         addBitmap(objectId, compressed, flags);
  185.     }

  187.     /**
  188.      * Stores the bitmap for the objectId.
  189.      *
  190.      * @param objectId
  191.      *            the object id key for the bitmap.
  192.      * @param bitmap
  193.      *            the bitmap
  194.      * @param flags
  195.      *            the flags to be stored with the bitmap
  196.      */
  197.     public void addBitmap(
  198.             AnyObjectId objectId, EWAHCompressedBitmap bitmap, int flags) {
  199.         bitmap.trim();
  200.         StoredBitmap result = new StoredBitmap(objectId, bitmap, null, flags);
  201.         getBitmaps().add(result);
  202.         byAddOrder.add(result);
  203.     }

  205.     /** {@inheritDoc} */
  206.     @Override
  207.     public EWAHCompressedBitmap ofObjectType(
  208.             EWAHCompressedBitmap bitmap, int type) {
  209.         switch (type) {
  210.         case Constants.OBJ_BLOB:
  211.             return getBlobs().and(bitmap);
  212.         case Constants.OBJ_TREE:
  213.             return getTrees().and(bitmap);
  214.         case Constants.OBJ_COMMIT:
  215.             return getCommits().and(bitmap);
  216.         case Constants.OBJ_TAG:
  217.             return getTags().and(bitmap);
  218.         }
  219.         throw new IllegalArgumentException();
  220.     }

  222.     /** {@inheritDoc} */
  223.     @Override
  224.     public int findPosition(AnyObjectId objectId) {
  225.         PositionEntry entry = positionEntries.get(objectId);
  226.         if (entry == null)
  227.             return -1;
  228.         return entry.offsetPosition;
  229.     }

  231.     /** {@inheritDoc} */
  232.     @Override
  233.     public ObjectId getObject(int position) throws IllegalArgumentException {
  234.         ObjectId objectId = byOffset.get(position);
  235.         if (objectId == null)
  236.             throw new IllegalArgumentException();
  237.         return objectId;
  238.     }

  240.     /**
  241.      * Get the commit object bitmap.
  242.      *
  243.      * @return the commit object bitmap.
  244.      */
  245.     public EWAHCompressedBitmap getCommits() {
  246.         return commits;
  247.     }

  249.     /**
  250.      * Get the tree object bitmap.
  251.      *
  252.      * @return the tree object bitmap.
  253.      */
  254.     public EWAHCompressedBitmap getTrees() {
  255.         return trees;
  256.     }

  258.     /**
  259.      * Get the blob object bitmap.
  260.      *
  261.      * @return the blob object bitmap.
  262.      */
  263.     public EWAHCompressedBitmap getBlobs() {
  264.         return blobs;
  265.     }

  267.     /**
  268.      * Get the tag object bitmap.
  269.      *
  270.      * @return the tag object bitmap.
  271.      */
  272.     public EWAHCompressedBitmap getTags() {
  273.         return tags;
  274.     }

  276.     /**
  277.      * Get the index storage options.
  278.      *
  279.      * @return the index storage options.
  280.      */
  281.     public int getOptions() {
  282.         return PackBitmapIndexV1.OPT_FULL;
  283.     }

  285.     /** {@inheritDoc} */
  286.     @Override
  287.     public int getBitmapCount() {
  288.         return getBitmaps().size();
  289.     }

  291.     /**
  292.      * Remove all the bitmaps entries added.
  293.      */
  294.     public void clearBitmaps() {
  295.         byAddOrder.clear();
  296.         getBitmaps().clear();
  297.     }

  299.     /** {@inheritDoc} */
  300.     @Override
  301.     public int getObjectCount() {
  302.         return byOffset.size();
  303.     }

  305.     /**
  306.      * Get an iterator over the xor compressed entries.
  307.      *
  308.      * @return an iterator over the xor compressed entries.
  309.      */
  310.     public Iterable<StoredEntry> getCompressedBitmaps() {
  311.         // Add order is from oldest to newest. The reverse add order is the
  312.         // output order.
  313.         return new Iterable<StoredEntry>() {
  314.             @Override
  315.             public Iterator<StoredEntry> iterator() {
  316.                 return new Iterator<StoredEntry>() {
  317.                     private int index = byAddOrder.size() - 1;

  319.                     @Override
  320.                     public boolean hasNext() {
  321.                         return index >= 0;
  322.                     }

  324.                     @Override
  325.                     public StoredEntry next() {
  326.                         if (!hasNext())
  327.                             throw new NoSuchElementException();
  328.                         StoredBitmap item = byAddOrder.get(index);
  329.                         int bestXorOffset = 0;
  330.                         EWAHCompressedBitmap bestBitmap = item.getBitmap();

  332.                         // Attempt to compress the bitmap with an XOR of the
  333.                         // previously written entries.
  334.                         for (int i = 1; i <= MAX_XOR_OFFSET_SEARCH; i++) {
  335.                             int curr = i + index;
  336.                             if (curr >= byAddOrder.size())
  337.                                 break;

  339.                             StoredBitmap other = byAddOrder.get(curr);
  340.                             EWAHCompressedBitmap bitmap = other.getBitmap()
  341.                                     .xor(item.getBitmap());

  343.                             if (bitmap.sizeInBytes()
  344.                                     < bestBitmap.sizeInBytes()) {
  345.                                 bestBitmap = bitmap;
  346.                                 bestXorOffset = i;
  347.                             }
  348.                         }
  349.                         index--;

  351.                         PositionEntry entry = positionEntries.get(item);
  352.                         if (entry == null)
  353.                             throw new IllegalStateException();
  354.                         bestBitmap.trim();
  355.                         return new StoredEntry(entry.namePosition, bestBitmap,
  356.                                 bestXorOffset, item.getFlags());
  357.                     }

  359.                     @Override
  360.                     public void remove() {
  361.                         throw new UnsupportedOperationException();
  362.                     }
  363.                 };
  364.             }
  365.         };
  366.     }

  368.     /** Data object for the on disk representation of a bitmap entry. */
  369.     public static final class StoredEntry {
  370.         private final long objectId;
  371.         private final EWAHCompressedBitmap bitmap;
  372.         private final int xorOffset;
  373.         private final int flags;

  375.         StoredEntry(long objectId, EWAHCompressedBitmap bitmap,
  376.                 int xorOffset, int flags) {
  377.             this.objectId = objectId;
  378.             this.bitmap = bitmap;
  379.             this.xorOffset = xorOffset;
  380.             this.flags = flags;
  381.         }

  383.         /** @return the bitmap */
  384.         public EWAHCompressedBitmap getBitmap() {
  385.             return bitmap;
  386.         }

  388.         /** @return the xorOffset */
  389.         public int getXorOffset() {
  390.             return xorOffset;
  391.         }

  393.         /** @return the flags */
  394.         public int getFlags() {
  395.             return flags;
  396.         }

  398.         /** @return the ObjectId */
  399.         public long getObjectId() {
  400.             return objectId;
  401.         }
  402.     }

  404.     private static final class PositionEntry extends ObjectIdOwnerMap.Entry {
  405.         final int namePosition;

  407.         int offsetPosition;

  409.         PositionEntry(AnyObjectId objectId, int namePosition) {
  410.             super(objectId);
  411.             this.namePosition = namePosition;
  412.         }
  413.     }
  414. }
Created with JaCoCo 0.8.4.201905082037