BlockRevQueue.java

  1. /*
  2.  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org> 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.  */

  10. package org.eclipse.jgit.revwalk;

  11. import java.io.IOException;

  12. import org.eclipse.jgit.errors.IncorrectObjectTypeException;
  13. import org.eclipse.jgit.errors.MissingObjectException;

  14. abstract class BlockRevQueue extends AbstractRevQueue {
  15.     protected BlockFreeList free;

  16.     /**
  17.      * Create an empty revision queue.
  18.      *
  19.      * @param firstParent
  20.      *            whether only first-parent links should be followed when
  21.      *            walking
  22.      */
  23.     protected BlockRevQueue(boolean firstParent) {
  24.         super(firstParent);
  25.         free = new BlockFreeList();
  26.     }

  27.     BlockRevQueue(Generator s) throws MissingObjectException,
  28.             IncorrectObjectTypeException, IOException {
  29.         super(s.firstParent);
  30.         free = new BlockFreeList();
  31.         outputType = s.outputType();
  32.         s.shareFreeList(this);
  33.         for (;;) {
  34.             final RevCommit c = s.next();
  35.             if (c == null)
  36.                 break;
  37.             add(c);
  38.         }
  39.     }

  40.     /**
  41.      * {@inheritDoc}
  42.      * <p>
  43.      * Reconfigure this queue to share the same free list as another.
  44.      * <p>
  45.      * Multiple revision queues can be connected to the same free list, making
  46.      * it less expensive for applications to shuttle commits between them. This
  47.      * method arranges for the receiver to take from / return to the same free
  48.      * list as the supplied queue.
  49.      * <p>
  50.      * Free lists are not thread-safe. Applications must ensure that all queues
  51.      * sharing the same free list are doing so from only a single thread.
  52.      */
  53.     @Override
  54.     public void shareFreeList(BlockRevQueue q) {
  55.         free = q.free;
  56.     }

  57.     static final class BlockFreeList {
  58.         private Block next;

  59.         Block newBlock() {
  60.             Block b = next;
  61.             if (b == null)
  62.                 return new Block();
  63.             next = b.next;
  64.             b.clear();
  65.             return b;
  66.         }

  67.         void freeBlock(Block b) {
  68.             b.next = next;
  69.             next = b;
  70.         }

  71.         void clear() {
  72.             next = null;
  73.         }
  74.     }

  75.     static final class Block {
  76.         static final int BLOCK_SIZE = 256;

  77.         /** Next block in our chain of blocks; null if we are the last. */
  78.         Block next;

  79.         /** Our table of queued commits. */
  80.         final RevCommit[] commits = new RevCommit[BLOCK_SIZE];

  81.         /** Next valid entry in {@link #commits}. */
  82.         int headIndex;

  83.         /** Next free entry in {@link #commits} for addition at. */
  84.         int tailIndex;

  85.         boolean isFull() {
  86.             return tailIndex == BLOCK_SIZE;
  87.         }

  88.         boolean isEmpty() {
  89.             return headIndex == tailIndex;
  90.         }

  91.         boolean canUnpop() {
  92.             return headIndex > 0;
  93.         }

  94.         void add(RevCommit c) {
  95.             commits[tailIndex++] = c;
  96.         }

  97.         void unpop(RevCommit c) {
  98.             commits[--headIndex] = c;
  99.         }

  100.         RevCommit pop() {
  101.             return commits[headIndex++];
  102.         }

  103.         RevCommit peek() {
  104.             return commits[headIndex];
  105.         }

  106.         void clear() {
  107.             next = null;
  108.             headIndex = 0;
  109.             tailIndex = 0;
  110.         }

  111.         void resetToMiddle() {
  112.             headIndex = tailIndex = BLOCK_SIZE / 2;
  113.         }

  114.         void resetToEnd() {
  115.             headIndex = tailIndex = BLOCK_SIZE;
  116.         }
  117.     }
  118. }