1
2
3
4
5
6
7
8
9
10
11 package org.eclipse.jgit.internal.storage.reftable;
12
13 import java.io.IOException;
14 import java.util.List;
15 import java.util.PriorityQueue;
16
17 import org.eclipse.jgit.lib.AnyObjectId;
18 import org.eclipse.jgit.lib.Ref;
19 import org.eclipse.jgit.lib.ReflogEntry;
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36 public class MergedReftable extends Reftable {
37 private final ReftableReader[] tables;
38
39
40
41
42
43
44
45
46
47
48
49 public MergedReftable(List<ReftableReader> tableStack) {
50 tables = tableStack.toArray(new ReftableReader[0]);
51
52
53
54 for (ReftableReader t : tables) {
55 t.setIncludeDeletes(true);
56 }
57 }
58
59
60
61
62 @Override
63 public long maxUpdateIndex() throws IOException {
64 if (tables.length == 0) {
65 return 0;
66 }
67 long maxUpdateIndex = tables[tables.length - 1].maxUpdateIndex();
68 for (int i = tables.length - 2; i >= 0; i--) {
69 if (maxUpdateIndex < tables[i].maxUpdateIndex()) {
70 maxUpdateIndex = tables[i].maxUpdateIndex();
71 }
72 }
73 return maxUpdateIndex;
74 }
75
76
77
78
79 @Override
80 public long minUpdateIndex() throws IOException {
81 if (tables.length == 0) {
82 return 0;
83 }
84 long minUpdateIndex = tables[0].minUpdateIndex();
85 for (int i = 1; i < tables.length; i++) {
86 if (tables[i].minUpdateIndex() < minUpdateIndex) {
87 minUpdateIndex = tables[i].minUpdateIndex();
88 }
89 }
90 return minUpdateIndex;
91 }
92
93
94 @Override
95 public boolean hasObjectMap() throws IOException {
96 boolean has = true;
97 for (int i = 0; has && i < tables.length; i++) {
98 has = has && tables[i].hasObjectMap();
99 }
100 return has;
101 }
102
103
104 @Override
105 public RefCursor allRefs() throws IOException {
106 MergedRefCursor m = new MergedRefCursor();
107 for (int i = 0; i < tables.length; i++) {
108 m.add(new RefQueueEntry(tables[i].allRefs(), i));
109 }
110 return m;
111 }
112
113
114 @Override
115 public RefCursor seekRef(String name) throws IOException {
116 MergedRefCursor m = new MergedRefCursor();
117 for (int i = 0; i < tables.length; i++) {
118 m.add(new RefQueueEntry(tables[i].seekRef(name), i));
119 }
120 return m;
121 }
122
123
124 @Override
125 public RefCursor seekRefsWithPrefix(String prefix) throws IOException {
126 MergedRefCursor m = new MergedRefCursor();
127 for (int i = 0; i < tables.length; i++) {
128 m.add(new RefQueueEntry(tables[i].seekRefsWithPrefix(prefix), i));
129 }
130 return m;
131 }
132
133
134 @Override
135 public RefCursor byObjectId(AnyObjectId name) throws IOException {
136 MergedRefCursor m = new FilteringMergedRefCursor(name);
137 for (int i = 0; i < tables.length; i++) {
138 m.add(new RefQueueEntry(tables[i].byObjectId(name), i));
139 }
140 return m;
141 }
142
143
144 @Override
145 public LogCursor allLogs() throws IOException {
146 MergedLogCursor m = new MergedLogCursor();
147 for (int i = 0; i < tables.length; i++) {
148 m.add(new LogQueueEntry(tables[i].allLogs(), i));
149 }
150 return m;
151 }
152
153
154 @Override
155 public LogCursor seekLog(String refName, long updateIdx)
156 throws IOException {
157 MergedLogCursor m = new MergedLogCursor();
158 for (int i = 0; i < tables.length; i++) {
159 m.add(new LogQueueEntry(tables[i].seekLog(refName, updateIdx), i));
160 }
161 return m;
162 }
163
164 int queueSize() {
165 return Math.max(1, tables.length);
166 }
167
168 private class MergedRefCursor extends RefCursor {
169 private final PriorityQueue<RefQueueEntry> queue;
170 private RefQueueEntry head;
171 private Ref ref;
172
173 MergedRefCursor() {
174 queue = new PriorityQueue<>(queueSize(), RefQueueEntry::compare);
175 }
176
177 void add(RefQueueEntry t) throws IOException {
178
179
180
181
182 if (!t.rc.next()) {
183 t.rc.close();
184 } else if (head == null) {
185 RefQueueEntry p = queue.peek();
186 if (p == null || RefQueueEntry.compare(t, p) < 0) {
187 head = t;
188 } else {
189 head = queue.poll();
190 queue.add(t);
191 }
192 } else if (RefQueueEntry.compare(t, head) > 0) {
193 queue.add(t);
194 } else {
195 queue.add(head);
196 head = t;
197 }
198 }
199
200 @Override
201 public boolean next() throws IOException {
202 for (;;) {
203 RefQueueEntry t = poll();
204 if (t == null) {
205 return false;
206 }
207
208 ref = t.rc.getRef();
209 boolean include = includeDeletes || !t.rc.wasDeleted();
210 add(t);
211 skipShadowedRefs(ref.getName());
212 if (include) {
213 return true;
214 }
215 }
216 }
217
218 private RefQueueEntry poll() {
219 RefQueueEntry e = head;
220 if (e != null) {
221 head = null;
222 return e;
223 }
224 return queue.poll();
225 }
226
227 private void skipShadowedRefs(String name) throws IOException {
228 for (;;) {
229 RefQueueEntry t = head != null ? head : queue.peek();
230 if (t != null && name.equals(t.name())) {
231 add(poll());
232 } else {
233 break;
234 }
235 }
236 }
237
238 @Override
239 public Ref getRef() {
240 return ref;
241 }
242
243 @Override
244 public void close() {
245 if (head != null) {
246 head.rc.close();
247 head = null;
248 }
249 while (!queue.isEmpty()) {
250 queue.remove().rc.close();
251 }
252 }
253 }
254
255 private class FilteringMergedRefCursor extends MergedRefCursor {
256 final AnyObjectId filterId;
257 Ref filteredRef;
258
259 FilteringMergedRefCursor(AnyObjectId id) {
260 filterId = id;
261 filteredRef = null;
262 }
263
264 @Override
265 public Ref getRef() {
266 return filteredRef;
267 }
268
269 @Override
270 public boolean next() throws IOException {
271 for (;;) {
272 boolean ok = super.next();
273 if (!ok) {
274 return false;
275 }
276
277 String name = super.getRef().getName();
278
279 try (RefCursor c = seekRef(name)) {
280 if (c.next()) {
281 if (filterId.equals(c.getRef().getObjectId())) {
282 filteredRef = c.getRef();
283 return true;
284 }
285 }
286 }
287 }
288 }
289 }
290
291 private static class RefQueueEntry {
292 static int compare(RefQueueEntry a, RefQueueEntry b) {
293 int cmp = a.name().compareTo(b.name());
294 if (cmp == 0) {
295
296 cmp = Long.signum(b.updateIndex() - a.updateIndex());
297 }
298 if (cmp == 0) {
299
300 cmp = b.stackIdx - a.stackIdx;
301 }
302 return cmp;
303 }
304
305 final RefCursor rc;
306 final int stackIdx;
307
308 RefQueueEntry(RefCursor rc, int stackIdx) {
309 this.rc = rc;
310 this.stackIdx = stackIdx;
311 }
312
313 String name() {
314 return rc.getRef().getName();
315 }
316
317 long updateIndex() {
318 return rc.getRef().getUpdateIndex();
319 }
320 }
321
322 private class MergedLogCursor extends LogCursor {
323 private final PriorityQueue<LogQueueEntry> queue;
324 private String refName;
325 private long updateIndex;
326 private ReflogEntry entry;
327
328 MergedLogCursor() {
329 queue = new PriorityQueue<>(queueSize(), LogQueueEntry::compare);
330 }
331
332 void add(LogQueueEntry t) throws IOException {
333 if (t.lc.next()) {
334 queue.add(t);
335 } else {
336 t.lc.close();
337 }
338 }
339
340 @Override
341 public boolean next() throws IOException {
342 for (;;) {
343 LogQueueEntry t = queue.poll();
344 if (t == null) {
345 return false;
346 }
347
348 refName = t.lc.getRefName();
349 updateIndex = t.lc.getUpdateIndex();
350 entry = t.lc.getReflogEntry();
351 boolean include = includeDeletes || entry != null;
352 skipShadowed(refName, updateIndex);
353 add(t);
354 if (include) {
355 return true;
356 }
357 }
358 }
359
360 private void skipShadowed(String name, long index) throws IOException {
361 for (;;) {
362 LogQueueEntry t = queue.peek();
363 if (t != null && name.equals(t.name()) && index == t.index()) {
364 add(queue.remove());
365 } else {
366 break;
367 }
368 }
369 }
370
371 @Override
372 public String getRefName() {
373 return refName;
374 }
375
376 @Override
377 public long getUpdateIndex() {
378 return updateIndex;
379 }
380
381 @Override
382 public ReflogEntry getReflogEntry() {
383 return entry;
384 }
385
386 @Override
387 public void close() {
388 while (!queue.isEmpty()) {
389 queue.remove().lc.close();
390 }
391 }
392 }
393
394 private static class LogQueueEntry {
395 static int compare(LogQueueEntry a, LogQueueEntry b) {
396 int cmp = a.name().compareTo(b.name());
397 if (cmp == 0) {
398
399 cmp = Long.signum(b.index() - a.index());
400 }
401 if (cmp == 0) {
402
403 cmp = b.stackIdx - a.stackIdx;
404 }
405 return cmp;
406 }
407
408 final LogCursor lc;
409 final int stackIdx;
410
411 LogQueueEntry(LogCursor lc, int stackIdx) {
412 this.lc = lc;
413 this.stackIdx = stackIdx;
414 }
415
416 String name() {
417 return lc.getRefName();
418 }
419
420 long index() {
421 return lc.getUpdateIndex();
422 }
423 }
424 }