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.dircache;
46
47 import static java.nio.charset.StandardCharsets.UTF_8;
48 import static org.eclipse.jgit.lib.FileMode.TREE;
49 import static org.eclipse.jgit.lib.TreeFormatter.entrySize;
50
51 import java.io.IOException;
52 import java.io.OutputStream;
53 import java.nio.ByteBuffer;
54 import java.util.Arrays;
55 import java.util.Comparator;
56
57 import org.eclipse.jgit.errors.UnmergedPathException;
58 import org.eclipse.jgit.lib.Constants;
59 import org.eclipse.jgit.lib.ObjectId;
60 import org.eclipse.jgit.lib.ObjectInserter;
61 import org.eclipse.jgit.lib.TreeFormatter;
62 import org.eclipse.jgit.util.MutableInteger;
63 import org.eclipse.jgit.util.RawParseUtils;
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79 public class DirCacheTree {
80 private static final byte[] NO_NAME = {};
81
82 private static final DirCacheTree[] NO_CHILDREN = {};
83
84 private static final Comparator<DirCacheTree> TREE_CMP = (DirCacheTree o1,
85 DirCacheTree o2) -> {
86 final byte[] a = o1.encodedName;
87 final byte[] b = o2.encodedName;
88 final int aLen = a.length;
89 final int bLen = b.length;
90 int cPos;
91 for (cPos = 0; cPos < aLen && cPos < bLen; cPos++) {
92 final int cmp = (a[cPos] & 0xff) - (b[cPos] & 0xff);
93 if (cmp != 0) {
94 return cmp;
95 }
96 }
97 if (aLen == bLen) {
98 return 0;
99 }
100 if (aLen < bLen) {
101 return '/' - (b[cPos] & 0xff);
102 }
103 return (a[cPos] & 0xff) - '/';
104 };
105
106
107 private DirCacheTree parent;
108
109
110 byte[] encodedName;
111
112
113 private int entrySpan;
114
115
116 private ObjectId id;
117
118
119 private DirCacheTree[] children;
120
121
122 private int childCnt;
123
124 DirCacheTree() {
125 encodedName = NO_NAME;
126 children = NO_CHILDREN;
127 childCnt = 0;
128 entrySpan = -1;
129 }
130
131 private DirCacheTreeirCacheTree.html#DirCacheTree">DirCacheTree(final DirCacheTree myParent, final byte[] path,
132 final int pathOff, final int pathLen) {
133 parent = myParent;
134 encodedName = new byte[pathLen];
135 System.arraycopy(path, pathOff, encodedName, 0, pathLen);
136 children = NO_CHILDREN;
137 childCnt = 0;
138 entrySpan = -1;
139 }
140
141 DirCacheTree(final byte[] in, final MutableInteger off,
142 final DirCacheTree myParent) {
143 parent = myParent;
144
145 int ptr = RawParseUtils.next(in, off.value, '\0');
146 final int nameLen = ptr - off.value - 1;
147 if (nameLen > 0) {
148 encodedName = new byte[nameLen];
149 System.arraycopy(in, off.value, encodedName, 0, nameLen);
150 } else
151 encodedName = NO_NAME;
152
153 entrySpan = RawParseUtils.parseBase10(in, ptr, off);
154 final int subcnt = RawParseUtils.parseBase10(in, off.value, off);
155 off.value = RawParseUtils.next(in, off.value, '\n');
156
157 if (entrySpan >= 0) {
158
159
160
161 id = ObjectId.fromRaw(in, off.value);
162 off.value += Constants.OBJECT_ID_LENGTH;
163 }
164
165 if (subcnt > 0) {
166 boolean alreadySorted = true;
167 children = new DirCacheTree[subcnt];
168 for (int i = 0; i < subcnt; i++) {
169 children[i] = new DirCacheTree(in, off, this);
170
171
172
173
174
175
176 if (alreadySorted && i > 0
177 && TREE_CMP.compare(children[i - 1], children[i]) > 0)
178 alreadySorted = false;
179 }
180 if (!alreadySorted)
181 Arrays.sort(children, 0, subcnt, TREE_CMP);
182 } else {
183
184
185 children = NO_CHILDREN;
186 }
187 childCnt = subcnt;
188 }
189
190 void write(byte[] tmp, OutputStream os) throws IOException {
191 int ptr = tmp.length;
192 tmp[--ptr] = '\n';
193 ptr = RawParseUtils.formatBase10(tmp, ptr, childCnt);
194 tmp[--ptr] = ' ';
195 ptr = RawParseUtils.formatBase10(tmp, ptr, isValid() ? entrySpan : -1);
196 tmp[--ptr] = 0;
197
198 os.write(encodedName);
199 os.write(tmp, ptr, tmp.length - ptr);
200 if (isValid()) {
201 id.copyRawTo(tmp, 0);
202 os.write(tmp, 0, Constants.OBJECT_ID_LENGTH);
203 }
204 for (int i = 0; i < childCnt; i++)
205 children[i].write(tmp, os);
206 }
207
208
209
210
211
212
213
214
215
216
217
218
219
220 public boolean isValid() {
221 return id != null;
222 }
223
224
225
226
227
228
229
230
231
232
233 public int getEntrySpan() {
234 return entrySpan;
235 }
236
237
238
239
240
241
242 public int getChildCount() {
243 return childCnt;
244 }
245
246
247
248
249
250
251
252
253 public DirCacheTree getChild(int i) {
254 return children[i];
255 }
256
257
258
259
260
261
262
263
264
265 public ObjectId getObjectId() {
266 return id;
267 }
268
269
270
271
272
273
274
275
276
277
278
279 public String getNameString() {
280 final ByteBuffer bb = ByteBuffer.wrap(encodedName);
281 return UTF_8.decode(bb).toString();
282 }
283
284
285
286
287
288
289
290
291
292
293
294
295
296 public String getPathString() {
297 final StringBuilder r = new StringBuilder();
298 appendName(r);
299 return r.toString();
300 }
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326 ObjectId writeTree(final DirCacheEntry[] cache, int cIdx,
327 final int pathOffset, final ObjectInserter ow)
328 throws UnmergedPathException, IOException {
329 if (id == null) {
330 final int endIdx = cIdx + entrySpan;
331 final TreeFormatterer.html#TreeFormatter">TreeFormatter fmt = new TreeFormatter(computeSize(cache,
332 cIdx, pathOffset, ow));
333 int childIdx = 0;
334 int entryIdx = cIdx;
335
336 while (entryIdx < endIdx) {
337 final DirCacheEntry e = cache[entryIdx];
338 final byte[] ep = e.path;
339 if (childIdx < childCnt) {
340 final DirCacheTree st = children[childIdx];
341 if (st.contains(ep, pathOffset, ep.length)) {
342 fmt.append(st.encodedName, TREE, st.id);
343 entryIdx += st.entrySpan;
344 childIdx++;
345 continue;
346 }
347 }
348
349 fmt.append(ep, pathOffset, ep.length - pathOffset, e
350 .getFileMode(), e.idBuffer(), e.idOffset());
351 entryIdx++;
352 }
353
354 id = ow.insert(fmt);
355 }
356 return id;
357 }
358
359 private int computeSize(final DirCacheEntry[] cache, int cIdx,
360 final int pathOffset, final ObjectInserter ow)
361 throws UnmergedPathException, IOException {
362 final int endIdx = cIdx + entrySpan;
363 int childIdx = 0;
364 int entryIdx = cIdx;
365 int size = 0;
366
367 while (entryIdx < endIdx) {
368 final DirCacheEntry e = cache[entryIdx];
369 if (e.getStage() != 0)
370 throw new UnmergedPathException(e);
371
372 final byte[] ep = e.path;
373 if (childIdx < childCnt) {
374 final DirCacheTree st = children[childIdx];
375 if (st.contains(ep, pathOffset, ep.length)) {
376 final int stOffset = pathOffset + st.nameLength() + 1;
377 st.writeTree(cache, entryIdx, stOffset, ow);
378
379 size += entrySize(TREE, st.nameLength());
380
381 entryIdx += st.entrySpan;
382 childIdx++;
383 continue;
384 }
385 }
386
387 size += entrySize(e.getFileMode(), ep.length - pathOffset);
388 entryIdx++;
389 }
390
391 return size;
392 }
393
394 private void appendName(StringBuilder r) {
395 if (parent != null) {
396 parent.appendName(r);
397 r.append(getNameString());
398 r.append('/');
399 } else if (nameLength() > 0) {
400 r.append(getNameString());
401 r.append('/');
402 }
403 }
404
405 final int nameLength() {
406 return encodedName.length;
407 }
408
409 final boolean contains(byte[] a, int aOff, int aLen) {
410 final byte[] e = encodedName;
411 final int eLen = e.length;
412 for (int eOff = 0; eOff < eLen && aOff < aLen; eOff++, aOff++)
413 if (e[eOff] != a[aOff])
414 return false;
415 if (aOff >= aLen)
416 return false;
417 return a[aOff] == '/';
418 }
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439 void validate(final DirCacheEntry[] cache, final int cCnt, int cIdx,
440 final int pathOff) {
441 if (entrySpan >= 0 && cIdx + entrySpan <= cCnt) {
442
443
444
445 return;
446 }
447
448 entrySpan = 0;
449 if (cCnt == 0) {
450
451
452 return;
453 }
454
455 final byte[] firstPath = cache[cIdx].path;
456 int stIdx = 0;
457 while (cIdx < cCnt) {
458 final byte[] currPath = cache[cIdx].path;
459 if (pathOff > 0 && !peq(firstPath, currPath, pathOff)) {
460
461
462
463 break;
464 }
465
466 DirCacheTree st = stIdx < childCnt ? children[stIdx] : null;
467 final int cc = namecmp(currPath, pathOff, st);
468 if (cc > 0) {
469
470
471 removeChild(stIdx);
472 continue;
473 }
474
475 if (cc < 0) {
476 final int p = slash(currPath, pathOff);
477 if (p < 0) {
478
479
480
481 cIdx++;
482 entrySpan++;
483 continue;
484 }
485
486
487
488 st = new DirCacheTree(this, currPath, pathOff, p - pathOff);
489 insertChild(stIdx, st);
490 }
491
492
493
494 assert(st != null);
495 st.validate(cache, cCnt, cIdx, pathOff + st.nameLength() + 1);
496 cIdx += st.entrySpan;
497 entrySpan += st.entrySpan;
498 stIdx++;
499 }
500
501
502
503
504 while (stIdx < childCnt)
505 removeChild(childCnt - 1);
506 }
507
508 private void insertChild(int stIdx, DirCacheTree st) {
509 final DirCacheTree[] c = children;
510 if (childCnt + 1 <= c.length) {
511 if (stIdx < childCnt)
512 System.arraycopy(c, stIdx, c, stIdx + 1, childCnt - stIdx);
513 c[stIdx] = st;
514 childCnt++;
515 return;
516 }
517
518 final int n = c.length;
519 final DirCacheTreecheTree.html#DirCacheTree">DirCacheTree[] a = new DirCacheTree[n + 1];
520 if (stIdx > 0)
521 System.arraycopy(c, 0, a, 0, stIdx);
522 a[stIdx] = st;
523 if (stIdx < n)
524 System.arraycopy(c, stIdx, a, stIdx + 1, n - stIdx);
525 children = a;
526 childCnt++;
527 }
528
529 private void removeChild(int stIdx) {
530 final int n = --childCnt;
531 if (stIdx < n)
532 System.arraycopy(children, stIdx + 1, children, stIdx, n - stIdx);
533 children[n] = null;
534 }
535
536 static boolean peq(byte[] a, byte[] b, int aLen) {
537 if (b.length < aLen)
538 return false;
539 for (aLen--; aLen >= 0; aLen--)
540 if (a[aLen] != b[aLen])
541 return false;
542 return true;
543 }
544
545 private static int namecmp(byte[] a, int aPos, DirCacheTree ct) {
546 if (ct == null)
547 return -1;
548 final byte[] b = ct.encodedName;
549 final int aLen = a.length;
550 final int bLen = b.length;
551 int bPos = 0;
552 for (; aPos < aLen && bPos < bLen; aPos++, bPos++) {
553 final int cmp = (a[aPos] & 0xff) - (b[bPos] & 0xff);
554 if (cmp != 0)
555 return cmp;
556 }
557 if (bPos == bLen)
558 return a[aPos] == '/' ? 0 : -1;
559 return aLen - bLen;
560 }
561
562 private static int slash(byte[] a, int aPos) {
563 final int aLen = a.length;
564 for (; aPos < aLen; aPos++)
565 if (a[aPos] == '/')
566 return aPos;
567 return -1;
568 }
569
570
571 @Override
572 public String toString() {
573 return getNameString();
574 }
575 }