1
2
3
4
5
6
7
8
9
10
11
12 package org.eclipse.jgit.revwalk;
13
14 import java.io.IOException;
15
16 import org.eclipse.jgit.errors.IncorrectObjectTypeException;
17 import org.eclipse.jgit.errors.MissingObjectException;
18
19
20
21
22 public class DateRevQueue extends AbstractRevQueue {
23 private static final int REBUILD_INDEX_COUNT = 1000;
24
25 private Entry head;
26
27 private Entry free;
28
29 private int inQueue;
30
31 private int sinceLastIndex;
32
33 private Entry[] index;
34
35 private int first;
36
37 private int last = -1;
38
39
40 public DateRevQueue() {
41 super(false);
42 }
43
44 DateRevQueue(boolean firstParent) {
45 super(firstParent);
46 }
47
48 DateRevQueue(Generator s) throws MissingObjectException,
49 IncorrectObjectTypeException, IOException {
50 super(s.firstParent);
51 for (;;) {
52 final RevCommit c = s.next();
53 if (c == null)
54 break;
55 add(c);
56 }
57 }
58
59
60 @Override
61 public void add(RevCommit c) {
62 sinceLastIndex++;
63 if (++inQueue > REBUILD_INDEX_COUNT
64 && sinceLastIndex > REBUILD_INDEX_COUNT)
65 buildIndex();
66
67 Entry q = head;
68 final long when = c.commitTime;
69
70 if (first <= last && index[first].commit.commitTime > when) {
71 int low = first, high = last;
72 while (low <= high) {
73 int mid = (low + high) >>> 1;
74 int t = index[mid].commit.commitTime;
75 if (t < when)
76 high = mid - 1;
77 else if (t > when)
78 low = mid + 1;
79 else {
80 low = mid - 1;
81 break;
82 }
83 }
84 low = Math.min(low, high);
85 while (low > first && when == index[low].commit.commitTime)
86 --low;
87 q = index[low];
88 }
89
90 final Entry n = newEntry(c);
91 if (q == null || (q == head && when > q.commit.commitTime)) {
92 n.next = q;
93 head = n;
94 } else {
95 Entry p = q.next;
96 while (p != null && p.commit.commitTime > when) {
97 q = p;
98 p = q.next;
99 }
100 n.next = q.next;
101 q.next = n;
102 }
103 }
104
105
106 @Override
107 public RevCommit next() {
108 final Entry q = head;
109 if (q == null)
110 return null;
111
112 if (index != null && q == index[first])
113 index[first++] = null;
114 inQueue--;
115
116 head = q.next;
117 freeEntry(q);
118 return q.commit;
119 }
120
121 private void buildIndex() {
122 sinceLastIndex = 0;
123 first = 0;
124 index = new Entry[inQueue / 100 + 1];
125 int qi = 0, ii = 0;
126 for (Entry q = head; q != null; q = q.next) {
127 if (++qi % 100 == 0)
128 index[ii++] = q;
129 }
130 last = ii - 1;
131 }
132
133
134
135
136
137
138 public RevCommit peek() {
139 return head != null ? head.commit : null;
140 }
141
142
143 @Override
144 public void clear() {
145 head = null;
146 free = null;
147 index = null;
148 inQueue = 0;
149 sinceLastIndex = 0;
150 last = -1;
151 }
152
153 @Override
154 boolean everbodyHasFlag(int f) {
155 for (Entry q = head; q != null; q = q.next) {
156 if ((q.commit.flags & f) == 0)
157 return false;
158 }
159 return true;
160 }
161
162 @Override
163 boolean anybodyHasFlag(int f) {
164 for (Entry q = head; q != null; q = q.next) {
165 if ((q.commit.flags & f) != 0)
166 return true;
167 }
168 return false;
169 }
170
171 @Override
172 int outputType() {
173 return outputType | SORT_COMMIT_TIME_DESC;
174 }
175
176
177 @Override
178 public String toString() {
179 final StringBuilder s = new StringBuilder();
180 for (Entry q = head; q != null; q = q.next)
181 describe(s, q.commit);
182 return s.toString();
183 }
184
185 private Entry newEntry(RevCommit c) {
186 Entry r = free;
187 if (r == null)
188 r = new Entry();
189 else
190 free = r.next;
191 r.commit = c;
192 return r;
193 }
194
195 private void freeEntry(Entry e) {
196 e.next = free;
197 free = e;
198 }
199
200 static class Entry {
201 Entry next;
202
203 RevCommit commit;
204 }
205 }