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