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 public DateRevQueue() {
74 super(false);
75 }
76
77 DateRevQueue(boolean firstParent) {
78 super(firstParent);
79 }
80
81 DateRevQueue(Generator s) throws MissingObjectException,
82 IncorrectObjectTypeException, IOException {
83 super(s.firstParent);
84 for (;;) {
85 final RevCommit c = s.next();
86 if (c == null)
87 break;
88 add(c);
89 }
90 }
91
92
93 @Override
94 public void add(RevCommit c) {
95 sinceLastIndex++;
96 if (++inQueue > REBUILD_INDEX_COUNT
97 && sinceLastIndex > REBUILD_INDEX_COUNT)
98 buildIndex();
99
100 Entry q = head;
101 final long when = c.commitTime;
102
103 if (first <= last && index[first].commit.commitTime > when) {
104 int low = first, high = last;
105 while (low <= high) {
106 int mid = (low + high) >>> 1;
107 int t = index[mid].commit.commitTime;
108 if (t < when)
109 high = mid - 1;
110 else if (t > when)
111 low = mid + 1;
112 else {
113 low = mid - 1;
114 break;
115 }
116 }
117 low = Math.min(low, high);
118 while (low > first && when == index[low].commit.commitTime)
119 --low;
120 q = index[low];
121 }
122
123 final Entry n = newEntry(c);
124 if (q == null || (q == head && when > q.commit.commitTime)) {
125 n.next = q;
126 head = n;
127 } else {
128 Entry p = q.next;
129 while (p != null && p.commit.commitTime > when) {
130 q = p;
131 p = q.next;
132 }
133 n.next = q.next;
134 q.next = n;
135 }
136 }
137
138
139 @Override
140 public RevCommit next() {
141 final Entry q = head;
142 if (q == null)
143 return null;
144
145 if (index != null && q == index[first])
146 index[first++] = null;
147 inQueue--;
148
149 head = q.next;
150 freeEntry(q);
151 return q.commit;
152 }
153
154 private void buildIndex() {
155 sinceLastIndex = 0;
156 first = 0;
157 index = new Entry[inQueue / 100 + 1];
158 int qi = 0, ii = 0;
159 for (Entry q = head; q != null; q = q.next) {
160 if (++qi % 100 == 0)
161 index[ii++] = q;
162 }
163 last = ii - 1;
164 }
165
166
167
168
169
170
171 public RevCommit peek() {
172 return head != null ? head.commit : null;
173 }
174
175
176 @Override
177 public void clear() {
178 head = null;
179 free = null;
180 index = null;
181 inQueue = 0;
182 sinceLastIndex = 0;
183 last = -1;
184 }
185
186 @Override
187 boolean everbodyHasFlag(int f) {
188 for (Entry q = head; q != null; q = q.next) {
189 if ((q.commit.flags & f) == 0)
190 return false;
191 }
192 return true;
193 }
194
195 @Override
196 boolean anybodyHasFlag(int f) {
197 for (Entry q = head; q != null; q = q.next) {
198 if ((q.commit.flags & f) != 0)
199 return true;
200 }
201 return false;
202 }
203
204 @Override
205 int outputType() {
206 return outputType | SORT_COMMIT_TIME_DESC;
207 }
208
209
210 @Override
211 public String toString() {
212 final StringBuilder s = new StringBuilder();
213 for (Entry q = head; q != null; q = q.next)
214 describe(s, q.commit);
215 return s.toString();
216 }
217
218 private Entry newEntry(RevCommit c) {
219 Entry r = free;
220 if (r == null)
221 r = new Entry();
222 else
223 free = r.next;
224 r.commit = c;
225 return r;
226 }
227
228 private void freeEntry(Entry e) {
229 e.next = free;
230 free = e;
231 }
232
233 static class Entry {
234 Entry next;
235
236 RevCommit commit;
237 }
238 }