DateRevQueue.java

  1. /*
  2.  * Copyright (C) 2008, Shawn O. Pearce <spearce@spearce.org>,
  3.  * Copyright (C) 2013, Gustaf Lundh <gustaf.lundh@sonymobile.com> and others
  4.  *
  5.  * This program and the accompanying materials are made available under the
  6.  * terms of the Eclipse Distribution License v. 1.0 which is available at
  7.  * https://www.eclipse.org/org/documents/edl-v10.php.
  8.  *
  9.  * SPDX-License-Identifier: BSD-3-Clause
  10.  */

  11. package org.eclipse.jgit.revwalk;

  12. import java.io.IOException;

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

  15. /**
  16.  * A queue of commits sorted by commit time order.
  17.  */
  18. public class DateRevQueue extends AbstractRevQueue {
  19.     private static final int REBUILD_INDEX_COUNT = 1000;

  20.     private Entry head;

  21.     private Entry free;

  22.     private int inQueue;

  23.     private int sinceLastIndex;

  24.     private Entry[] index;

  25.     private int first;

  26.     private int last = -1;

  27.     /** Create an empty date queue. */
  28.     public DateRevQueue() {
  29.         super(false);
  30.     }

  31.     DateRevQueue(boolean firstParent) {
  32.         super(firstParent);
  33.     }

  34.     DateRevQueue(Generator s) throws MissingObjectException,
  35.             IncorrectObjectTypeException, IOException {
  36.         super(s.firstParent);
  37.         for (;;) {
  38.             final RevCommit c = s.next();
  39.             if (c == null)
  40.                 break;
  41.             add(c);
  42.         }
  43.     }

  44.     /** {@inheritDoc} */
  45.     @Override
  46.     public void add(RevCommit c) {
  47.         sinceLastIndex++;
  48.         if (++inQueue > REBUILD_INDEX_COUNT
  49.                 && sinceLastIndex > REBUILD_INDEX_COUNT)
  50.             buildIndex();

  51.         Entry q = head;
  52.         final long when = c.commitTime;

  53.         if (first <= last && index[first].commit.commitTime > when) {
  54.             int low = first, high = last;
  55.             while (low <= high) {
  56.                 int mid = (low + high) >>> 1;
  57.                 int t = index[mid].commit.commitTime;
  58.                 if (t < when)
  59.                     high = mid - 1;
  60.                 else if (t > when)
  61.                     low = mid + 1;
  62.                 else {
  63.                     low = mid - 1;
  64.                     break;
  65.                 }
  66.             }
  67.             low = Math.min(low, high);
  68.             while (low > first && when == index[low].commit.commitTime)
  69.                 --low;
  70.             q = index[low];
  71.         }

  72.         final Entry n = newEntry(c);
  73.         if (q == null || (q == head && when > q.commit.commitTime)) {
  74.             n.next = q;
  75.             head = n;
  76.         } else {
  77.             Entry p = q.next;
  78.             while (p != null && p.commit.commitTime > when) {
  79.                 q = p;
  80.                 p = q.next;
  81.             }
  82.             n.next = q.next;
  83.             q.next = n;
  84.         }
  85.     }

  86.     /** {@inheritDoc} */
  87.     @Override
  88.     public RevCommit next() {
  89.         final Entry q = head;
  90.         if (q == null)
  91.             return null;

  92.         if (index != null && q == index[first])
  93.             index[first++] = null;
  94.         inQueue--;

  95.         head = q.next;
  96.         freeEntry(q);
  97.         return q.commit;
  98.     }

  99.     private void buildIndex() {
  100.         sinceLastIndex = 0;
  101.         first = 0;
  102.         index = new Entry[inQueue / 100 + 1];
  103.         int qi = 0, ii = 0;
  104.         for (Entry q = head; q != null; q = q.next) {
  105.             if (++qi % 100 == 0)
  106.                 index[ii++] = q;
  107.         }
  108.         last = ii - 1;
  109.     }

  110.     /**
  111.      * Peek at the next commit, without removing it.
  112.      *
  113.      * @return the next available commit; null if there are no commits left.
  114.      */
  115.     public RevCommit peek() {
  116.         return head != null ? head.commit : null;
  117.     }

  118.     /** {@inheritDoc} */
  119.     @Override
  120.     public void clear() {
  121.         head = null;
  122.         free = null;
  123.         index = null;
  124.         inQueue = 0;
  125.         sinceLastIndex = 0;
  126.         last = -1;
  127.     }

  128.     @Override
  129.     boolean everbodyHasFlag(int f) {
  130.         for (Entry q = head; q != null; q = q.next) {
  131.             if ((q.commit.flags & f) == 0)
  132.                 return false;
  133.         }
  134.         return true;
  135.     }

  136.     @Override
  137.     boolean anybodyHasFlag(int f) {
  138.         for (Entry q = head; q != null; q = q.next) {
  139.             if ((q.commit.flags & f) != 0)
  140.                 return true;
  141.         }
  142.         return false;
  143.     }

  144.     @Override
  145.     int outputType() {
  146.         return outputType | SORT_COMMIT_TIME_DESC;
  147.     }

  148.     /** {@inheritDoc} */
  149.     @Override
  150.     public String toString() {
  151.         final StringBuilder s = new StringBuilder();
  152.         for (Entry q = head; q != null; q = q.next)
  153.             describe(s, q.commit);
  154.         return s.toString();
  155.     }

  156.     private Entry newEntry(RevCommit c) {
  157.         Entry r = free;
  158.         if (r == null)
  159.             r = new Entry();
  160.         else
  161.             free = r.next;
  162.         r.commit = c;
  163.         return r;
  164.     }

  165.     private void freeEntry(Entry e) {
  166.         e.next = free;
  167.         free = e;
  168.     }

  169.     static class Entry {
  170.         Entry next;

  171.         RevCommit commit;
  172.     }
  173. }