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