MergedReftable.java

  1. /*
  2.  * Copyright (C) 2017, 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.reftable;

  46. import java.io.IOException;
  47. import java.util.List;
  48. import java.util.PriorityQueue;

  50. import org.eclipse.jgit.lib.AnyObjectId;
  51. import org.eclipse.jgit.lib.Ref;
  52. import org.eclipse.jgit.lib.ReflogEntry;

  54. /**
  55.  * Merges multiple reference tables together.
  56.  * <p>
  57.  * A {@link org.eclipse.jgit.internal.storage.reftable.MergedReftable}
  58.  * merge-joins multiple
  59.  * {@link org.eclipse.jgit.internal.storage.reftable.ReftableReader} on the fly.
  60.  * Tables higher/later in the stack shadow lower/earlier tables, hiding
  61.  * references that been updated/replaced.
  62.  * <p>
  63.  * By default deleted references are skipped and not returned to the caller.
  64.  * {@link #setIncludeDeletes(boolean)} can be used to modify this behavior if
  65.  * the caller needs to preserve deletions during partial compaction.
  66.  * <p>
  67.  * A {@code MergedReftable} is not thread-safe.
  68.  */
  69. public class MergedReftable extends Reftable {
  70.     private final Reftable[] tables;

  72.     /**
  73.      * Initialize a merged table reader.
  74.      * <p>
  75.      * The tables in {@code tableStack} will be closed when this
  76.      * {@code MergedReftable} is closed.
  77.      *
  78.      * @param tableStack
  79.      *            stack of tables to read from. The base of the stack is at
  80.      *            index 0, the most recent should be at the top of the stack at
  81.      *            {@code tableStack.size() - 1}. The top of the stack (higher
  82.      *            index) shadows the base of the stack (lower index).
  83.      */
  84.     public MergedReftable(List<Reftable> tableStack) {
  85.         tables = tableStack.toArray(new Reftable[0]);

  87.         // Tables must expose deletes to this instance to correctly
  88.         // shadow references from lower tables.
  89.         for (Reftable t : tables) {
  90.             t.setIncludeDeletes(true);
  91.         }
  92.     }

  94.     /** {@inheritDoc} */
  95.     @Override
  96.     public RefCursor allRefs() throws IOException {
  97.         MergedRefCursor m = new MergedRefCursor();
  98.         for (int i = 0; i < tables.length; i++) {
  99.             m.add(new RefQueueEntry(tables[i].allRefs(), i));
  100.         }
  101.         return m;
  102.     }

  104.     /** {@inheritDoc} */
  105.     @Override
  106.     public RefCursor seekRef(String name) throws IOException {
  107.         MergedRefCursor m = new MergedRefCursor();
  108.         for (int i = 0; i < tables.length; i++) {
  109.             m.add(new RefQueueEntry(tables[i].seekRef(name), i));
  110.         }
  111.         return m;
  112.     }

  114.     /** {@inheritDoc} */
  115.     @Override
  116.     public RefCursor seekRefsWithPrefix(String prefix) throws IOException {
  117.         MergedRefCursor m = new MergedRefCursor();
  118.         for (int i = 0; i < tables.length; i++) {
  119.             m.add(new RefQueueEntry(tables[i].seekRefsWithPrefix(prefix), i));
  120.         }
  121.         return m;
  122.     }

  124.     /** {@inheritDoc} */
  125.     @Override
  126.     public RefCursor byObjectId(AnyObjectId name) throws IOException {
  127.         MergedRefCursor m = new MergedRefCursor();
  128.         for (int i = 0; i < tables.length; i++) {
  129.             m.add(new RefQueueEntry(tables[i].byObjectId(name), i));
  130.         }
  131.         return m;
  132.     }

  134.     /** {@inheritDoc} */
  135.     @Override
  136.     public LogCursor allLogs() throws IOException {
  137.         MergedLogCursor m = new MergedLogCursor();
  138.         for (int i = 0; i < tables.length; i++) {
  139.             m.add(new LogQueueEntry(tables[i].allLogs(), i));
  140.         }
  141.         return m;
  142.     }

  144.     /** {@inheritDoc} */
  145.     @Override
  146.     public LogCursor seekLog(String refName, long updateIdx)
  147.             throws IOException {
  148.         MergedLogCursor m = new MergedLogCursor();
  149.         for (int i = 0; i < tables.length; i++) {
  150.             m.add(new LogQueueEntry(tables[i].seekLog(refName, updateIdx), i));
  151.         }
  152.         return m;
  153.     }

  155.     /** {@inheritDoc} */
  156.     @Override
  157.     public void close() throws IOException {
  158.         for (Reftable t : tables) {
  159.             t.close();
  160.         }
  161.     }

  163.     int queueSize() {
  164.         return Math.max(1, tables.length);
  165.     }

  167.     private class MergedRefCursor extends RefCursor {
  168.         private final PriorityQueue<RefQueueEntry> queue;
  169.         private RefQueueEntry head;
  170.         private Ref ref;

  172.         MergedRefCursor() {
  173.             queue = new PriorityQueue<>(queueSize(), RefQueueEntry::compare);
  174.         }

  176.         void add(RefQueueEntry t) throws IOException {
  177.             // Common case is many iterations over the same RefQueueEntry
  178.             // for the bottom of the stack (scanning all refs). Its almost
  179.             // always less than the top of the queue. Avoid the queue's
  180.             // O(log N) insertion and removal costs for this common case.
  181.             if (!t.rc.next()) {
  182.                 t.rc.close();
  183.             } else if (head == null) {
  184.                 RefQueueEntry p = queue.peek();
  185.                 if (p == null || RefQueueEntry.compare(t, p) < 0) {
  186.                     head = t;
  187.                 } else {
  188.                     head = queue.poll();
  189.                     queue.add(t);
  190.                 }
  191.             } else if (RefQueueEntry.compare(t, head) > 0) {
  192.                 queue.add(t);
  193.             } else {
  194.                 queue.add(head);
  195.                 head = t;
  196.             }
  197.         }

  199.         @Override
  200.         public boolean next() throws IOException {
  201.             for (;;) {
  202.                 RefQueueEntry t = poll();
  203.                 if (t == null) {
  204.                     return false;
  205.                 }

  207.                 ref = t.rc.getRef();
  208.                 boolean include = includeDeletes || !t.rc.wasDeleted();
  209.                 add(t);
  210.                 skipShadowedRefs(ref.getName());
  211.                 if (include) {
  212.                     return true;
  213.                 }
  214.             }
  215.         }

  217.         private RefQueueEntry poll() {
  218.             RefQueueEntry e = head;
  219.             if (e != null) {
  220.                 head = null;
  221.                 return e;
  222.             }
  223.             return queue.poll();
  224.         }

  226.         private void skipShadowedRefs(String name) throws IOException {
  227.             for (;;) {
  228.                 RefQueueEntry t = head != null ? head : queue.peek();
  229.                 if (t != null && name.equals(t.name())) {
  230.                     add(poll());
  231.                 } else {
  232.                     break;
  233.                 }
  234.             }
  235.         }

  237.         @Override
  238.         public Ref getRef() {
  239.             return ref;
  240.         }

  242.         @Override
  243.         public void close() {
  244.             if (head != null) {
  245.                 head.rc.close();
  246.                 head = null;
  247.             }
  248.             while (!queue.isEmpty()) {
  249.                 queue.remove().rc.close();
  250.             }
  251.         }
  252.     }

  254.     private static class RefQueueEntry {
  255.         static int compare(RefQueueEntry a, RefQueueEntry b) {
  256.             int cmp = a.name().compareTo(b.name());
  257.             if (cmp == 0) {
  258.                 // higher updateIndex shadows lower updateIndex.
  259.                 cmp = Long.signum(b.updateIndex() - a.updateIndex());
  260.             }
  261.             if (cmp == 0) {
  262.                 // higher index shadows lower index, so higher index first.
  263.                 cmp = b.stackIdx - a.stackIdx;
  264.             }
  265.             return cmp;
  266.         }

  268.         final RefCursor rc;
  269.         final int stackIdx;

  271.         RefQueueEntry(RefCursor rc, int stackIdx) {
  272.             this.rc = rc;
  273.             this.stackIdx = stackIdx;
  274.         }

  276.         String name() {
  277.             return rc.getRef().getName();
  278.         }

  280.         long updateIndex() {
  281.             return rc.getRef().getUpdateIndex();
  282.         }
  283.     }

  285.     private class MergedLogCursor extends LogCursor {
  286.         private final PriorityQueue<LogQueueEntry> queue;
  287.         private String refName;
  288.         private long updateIndex;
  289.         private ReflogEntry entry;

  291.         MergedLogCursor() {
  292.             queue = new PriorityQueue<>(queueSize(), LogQueueEntry::compare);
  293.         }

  295.         void add(LogQueueEntry t) throws IOException {
  296.             if (t.lc.next()) {
  297.                 queue.add(t);
  298.             } else {
  299.                 t.lc.close();
  300.             }
  301.         }

  303.         @Override
  304.         public boolean next() throws IOException {
  305.             for (;;) {
  306.                 LogQueueEntry t = queue.poll();
  307.                 if (t == null) {
  308.                     return false;
  309.                 }

  311.                 refName = t.lc.getRefName();
  312.                 updateIndex = t.lc.getUpdateIndex();
  313.                 entry = t.lc.getReflogEntry();
  314.                 boolean include = includeDeletes || entry != null;
  315.                 skipShadowed(refName, updateIndex);
  316.                 add(t);
  317.                 if (include) {
  318.                     return true;
  319.                 }
  320.             }
  321.         }

  323.         private void skipShadowed(String name, long index) throws IOException {
  324.             for (;;) {
  325.                 LogQueueEntry t = queue.peek();
  326.                 if (t != null && name.equals(t.name()) && index == t.index()) {
  327.                     add(queue.remove());
  328.                 } else {
  329.                     break;
  330.                 }
  331.             }
  332.         }

  334.         @Override
  335.         public String getRefName() {
  336.             return refName;
  337.         }

  339.         @Override
  340.         public long getUpdateIndex() {
  341.             return updateIndex;
  342.         }

  344.         @Override
  345.         public ReflogEntry getReflogEntry() {
  346.             return entry;
  347.         }

  349.         @Override
  350.         public void close() {
  351.             while (!queue.isEmpty()) {
  352.                 queue.remove().lc.close();
  353.             }
  354.         }
  355.     }

  357.     private static class LogQueueEntry {
  358.         static int compare(LogQueueEntry a, LogQueueEntry b) {
  359.             int cmp = a.name().compareTo(b.name());
  360.             if (cmp == 0) {
  361.                 // higher update index sorts first.
  362.                 cmp = Long.signum(b.index() - a.index());
  363.             }
  364.             if (cmp == 0) {
  365.                 // higher index comes first.
  366.                 cmp = b.stackIdx - a.stackIdx;
  367.             }
  368.             return cmp;
  369.         }

  371.         final LogCursor lc;
  372.         final int stackIdx;

  374.         LogQueueEntry(LogCursor lc, int stackIdx) {
  375.             this.lc = lc;
  376.             this.stackIdx = stackIdx;
  377.         }

  379.         String name() {
  380.             return lc.getRefName();
  381.         }

  383.         long index() {
  384.             return lc.getUpdateIndex();
  385.         }
  386.     }
  387. }
Created with JaCoCo 0.8.4.201905082037