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