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