2
This code is derived from jgit (http://eclipse.org/jgit).
3
Copyright owners are documented in jgit's IP log.
5
This program and the accompanying materials are made available
6
under the terms of the Eclipse Distribution License v1.0 which
7
accompanies this distribution, is reproduced below, and is
8
available at http://www.eclipse.org/org/documents/edl-v10.php
12
Redistribution and use in source and binary forms, with or
13
without modification, are permitted provided that the following
16
- Redistributions of source code must retain the above copyright
17
notice, this list of conditions and the following disclaimer.
19
- Redistributions in binary form must reproduce the above
20
copyright notice, this list of conditions and the following
21
disclaimer in the documentation and/or other materials provided
22
with the distribution.
24
- Neither the name of the Eclipse Foundation, Inc. nor the
25
names of its contributors may be used to endorse or promote
26
products derived from this software without specific prior
29
THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND
30
CONTRIBUTORS "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES,
31
INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
32
OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
33
ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR
34
CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
35
SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT
36
NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
37
LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
38
CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT,
39
STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
40
ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
41
ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
44
using System.Collections.Generic;
52
namespace NGit.Dircache
55
/// Single tree record from the 'TREE'
56
/// <see cref="DirCache">DirCache</see>
59
/// A valid cache tree record contains the object id of a tree object and the
61
/// <see cref="DirCacheEntry">DirCacheEntry</see>
62
/// instances (counted recursively) from
63
/// the DirCache contained within the tree. This information facilitates faster
64
/// traversal of the index and quicker generation of tree objects prior to
65
/// creating a new commit.
67
/// An invalid cache tree record indicates a known subtree whose file entries
68
/// have changed in ways that cause the tree to no longer have a known object id.
69
/// Invalid cache tree records must be revalidated prior to use.
71
public class DirCacheTree
73
private static readonly byte[] NO_NAME = new byte[] { };
75
private static readonly NGit.Dircache.DirCacheTree[] NO_CHILDREN = new NGit.Dircache.DirCacheTree
78
private sealed class _IComparer_82 : IComparer<NGit.Dircache.DirCacheTree>
80
public _IComparer_82()
84
public int Compare(NGit.Dircache.DirCacheTree o1, NGit.Dircache.DirCacheTree o2)
86
byte[] a = o1.encodedName;
87
byte[] b = o2.encodedName;
91
for (cPos = 0; cPos < aLen && cPos < bLen; cPos++)
93
int cmp = (a[cPos] & unchecked((int)(0xff))) - (b[cPos] & unchecked((int)(0xff)));
105
return '/' - (b[cPos] & unchecked((int)(0xff)));
107
return (a[cPos] & unchecked((int)(0xff))) - '/';
111
private static readonly IComparer<NGit.Dircache.DirCacheTree> TREE_CMP = new _IComparer_82
114
/// <summary>Tree this tree resides in; null if we are the root.</summary>
115
/// <remarks>Tree this tree resides in; null if we are the root.</remarks>
116
private NGit.Dircache.DirCacheTree parent;
118
/// <summary>Name of this tree within its parent.</summary>
119
/// <remarks>Name of this tree within its parent.</remarks>
120
private byte[] encodedName;
124
/// <see cref="DirCacheEntry">DirCacheEntry</see>
125
/// records that belong to this tree.
127
private int entrySpan;
129
/// <summary>Unique SHA-1 of this tree; null if invalid.</summary>
130
/// <remarks>Unique SHA-1 of this tree; null if invalid.</remarks>
134
/// Child trees, if any, sorted by
135
/// <see cref="encodedName">encodedName</see>
138
private NGit.Dircache.DirCacheTree[] children;
141
/// Number of valid children in
142
/// <see cref="children">children</see>
145
private int childCnt;
147
public DirCacheTree()
149
encodedName = NO_NAME;
150
children = NO_CHILDREN;
155
private DirCacheTree(NGit.Dircache.DirCacheTree myParent, byte[] path, int pathOff
159
encodedName = new byte[pathLen];
160
System.Array.Copy(path, pathOff, encodedName, 0, pathLen);
161
children = NO_CHILDREN;
166
internal DirCacheTree(byte[] @in, MutableInteger off, NGit.Dircache.DirCacheTree
170
int ptr = RawParseUtils.Next(@in, off.value, '\0');
171
int nameLen = ptr - off.value - 1;
174
encodedName = new byte[nameLen];
175
System.Array.Copy(@in, off.value, encodedName, 0, nameLen);
179
encodedName = NO_NAME;
181
entrySpan = RawParseUtils.ParseBase10(@in, ptr, off);
182
int subcnt = RawParseUtils.ParseBase10(@in, off.value, off);
183
off.value = RawParseUtils.Next(@in, off.value, '\n');
186
// Valid trees have a positive entry count and an id of a
187
// tree object that should exist in the object database.
189
id = ObjectId.FromRaw(@in, off.value);
190
off.value += Constants.OBJECT_ID_LENGTH;
194
bool alreadySorted = true;
195
children = new NGit.Dircache.DirCacheTree[subcnt];
196
for (int i = 0; i < subcnt; i++)
198
children[i] = new NGit.Dircache.DirCacheTree(@in, off, this);
199
// C Git's ordering differs from our own; it prefers to
200
// sort by length first. This sometimes produces a sort
201
// we do not desire. On the other hand it may have been
202
// created by us, and be sorted the way we want.
204
if (alreadySorted && i > 0 && TREE_CMP.Compare(children[i - 1], children[i]) > 0)
206
alreadySorted = false;
211
Arrays.Sort(children, 0, subcnt, TREE_CMP);
216
// Leaf level trees have no children, only (file) entries.
218
children = NO_CHILDREN;
223
/// <exception cref="System.IO.IOException"></exception>
224
internal virtual void Write(byte[] tmp, OutputStream os)
226
int ptr = tmp.Length;
227
tmp[--ptr] = (byte)('\n');
228
ptr = RawParseUtils.FormatBase10(tmp, ptr, childCnt);
229
tmp[--ptr] = (byte)(' ');
230
ptr = RawParseUtils.FormatBase10(tmp, ptr, IsValid() ? entrySpan : -1);
232
os.Write(encodedName);
233
os.Write(tmp, ptr, tmp.Length - ptr);
236
id.CopyRawTo(tmp, 0);
237
os.Write(tmp, 0, Constants.OBJECT_ID_LENGTH);
239
for (int i = 0; i < childCnt; i++)
241
children[i].Write(tmp, os);
245
/// <summary>Determine if this cache is currently valid.</summary>
247
/// Determine if this cache is currently valid.
249
/// A valid cache tree knows how many
250
/// <see cref="DirCacheEntry">DirCacheEntry</see>
253
/// <see cref="DirCache">DirCache</see>
254
/// reside within this tree (recursively
255
/// enumerated). It also knows the object id of the tree, as the tree should
256
/// be readily available from the repository's object database.
259
/// true if this tree is knows key details about itself; false if the
260
/// tree needs to be regenerated.
262
public virtual bool IsValid()
267
/// <summary>Get the number of entries this tree spans within the DirCache.</summary>
269
/// Get the number of entries this tree spans within the DirCache.
271
/// If this tree is not valid (see
272
/// <see cref="IsValid()">IsValid()</see>
273
/// ) this method's return
274
/// value is always strictly negative (less than 0) but is otherwise an
275
/// undefined result.
277
/// <returns>total number of entries (recursively) contained within this tree.</returns>
278
public virtual int GetEntrySpan()
283
/// <summary>Get the number of cached subtrees contained within this tree.</summary>
284
/// <remarks>Get the number of cached subtrees contained within this tree.</remarks>
285
/// <returns>number of child trees available through this tree.</returns>
286
public virtual int GetChildCount()
291
/// <summary>Get the i-th child cache tree.</summary>
292
/// <remarks>Get the i-th child cache tree.</remarks>
293
/// <param name="i">index of the child to obtain.</param>
294
/// <returns>the child tree.</returns>
295
public virtual NGit.Dircache.DirCacheTree GetChild(int i)
300
internal virtual ObjectId GetObjectId()
305
/// <summary>Get the tree's name within its parent.</summary>
307
/// Get the tree's name within its parent.
309
/// This method is not very efficient and is primarily meant for debugging
310
/// and final output generation. Applications should try to avoid calling it,
311
/// and if invoked do so only once per interesting entry, where the name is
312
/// absolutely required for correct function.
314
/// <returns>name of the tree. This does not contain any '/' characters.</returns>
315
public virtual string GetNameString()
317
ByteBuffer bb = ByteBuffer.Wrap(encodedName);
318
return Constants.CHARSET.Decode(bb).ToString();
321
/// <summary>Get the tree's path within the repository.</summary>
323
/// Get the tree's path within the repository.
325
/// This method is not very efficient and is primarily meant for debugging
326
/// and final output generation. Applications should try to avoid calling it,
327
/// and if invoked do so only once per interesting entry, where the name is
328
/// absolutely required for correct function.
331
/// path of the tree, relative to the repository root. If this is not
332
/// the root tree the path ends with '/'. The root tree's path string
333
/// is the empty string ("").
335
public virtual string GetPathString()
337
StringBuilder r = new StringBuilder();
342
/// <summary>Write (if necessary) this tree to the object store.</summary>
343
/// <remarks>Write (if necessary) this tree to the object store.</remarks>
344
/// <param name="cache">the complete cache from DirCache.</param>
345
/// <param name="cIdx">
346
/// first position of <code>cache</code> that is a member of this
347
/// tree. The path of <code>cache[cacheIdx].path</code> for the
348
/// range <code>[0,pathOff-1)</code> matches the complete path of
349
/// this tree, from the root of the repository.
351
/// <param name="pathOffset">
352
/// number of bytes of <code>cache[cacheIdx].path</code> that
353
/// matches this tree's path. The value at array position
354
/// <code>cache[cacheIdx].path[pathOff-1]</code> is always '/' if
355
/// <code>pathOff</code> is > 0.
357
/// <param name="ow">the writer to use when serializing to the store.</param>
358
/// <returns>identity of this tree.</returns>
359
/// <exception cref="NGit.Errors.UnmergedPathException">
360
/// one or more paths contain higher-order stages (stage > 0),
361
/// which cannot be stored in a tree object.
363
/// <exception cref="System.IO.IOException">an unexpected error occurred writing to the object store.
365
internal virtual ObjectId WriteTree(DirCacheEntry[] cache, int cIdx, int pathOffset
370
int endIdx = cIdx + entrySpan;
371
TreeFormatter fmt = new TreeFormatter(ComputeSize(cache, cIdx, pathOffset, ow));
374
while (entryIdx < endIdx)
376
DirCacheEntry e = cache[entryIdx];
378
if (childIdx < childCnt)
380
NGit.Dircache.DirCacheTree st = children[childIdx];
381
if (st.Contains(ep, pathOffset, ep.Length))
383
fmt.Append(st.encodedName, FileMode.TREE, st.id);
384
entryIdx += st.entrySpan;
389
fmt.Append(ep, pathOffset, ep.Length - pathOffset, e.FileMode, e.IdBuffer, e.IdOffset
398
/// <exception cref="NGit.Errors.UnmergedPathException"></exception>
399
/// <exception cref="System.IO.IOException"></exception>
400
private int ComputeSize(DirCacheEntry[] cache, int cIdx, int pathOffset, ObjectInserter
403
int endIdx = cIdx + entrySpan;
407
while (entryIdx < endIdx)
409
DirCacheEntry e = cache[entryIdx];
412
throw new UnmergedPathException(e);
415
if (childIdx < childCnt)
417
NGit.Dircache.DirCacheTree st = children[childIdx];
418
if (st.Contains(ep, pathOffset, ep.Length))
420
int stOffset = pathOffset + st.NameLength() + 1;
421
st.WriteTree(cache, entryIdx, stOffset, ow);
422
size += TreeFormatter.EntrySize(FileMode.TREE, st.NameLength());
423
entryIdx += st.entrySpan;
428
size += TreeFormatter.EntrySize(e.FileMode, ep.Length - pathOffset);
434
private void AppendName(StringBuilder r)
438
parent.AppendName(r);
439
r.Append(GetNameString());
444
if (NameLength() > 0)
446
r.Append(GetNameString());
452
internal int NameLength()
454
return encodedName.Length;
457
internal bool Contains(byte[] a, int aOff, int aLen)
459
byte[] e = encodedName;
461
for (int eOff = 0; eOff < eLen && aOff < aLen; eOff++, aOff++)
463
if (e[eOff] != a[aOff])
472
return a[aOff] == '/';
475
/// <summary>Update (if necessary) this tree's entrySpan.</summary>
476
/// <remarks>Update (if necessary) this tree's entrySpan.</remarks>
477
/// <param name="cache">the complete cache from DirCache.</param>
478
/// <param name="cCnt">
479
/// number of entries in <code>cache</code> that are valid for
482
/// <param name="cIdx">
483
/// first position of <code>cache</code> that is a member of this
484
/// tree. The path of <code>cache[cacheIdx].path</code> for the
485
/// range <code>[0,pathOff-1)</code> matches the complete path of
486
/// this tree, from the root of the repository.
488
/// <param name="pathOff">
489
/// number of bytes of <code>cache[cacheIdx].path</code> that
490
/// matches this tree's path. The value at array position
491
/// <code>cache[cacheIdx].path[pathOff-1]</code> is always '/' if
492
/// <code>pathOff</code> is > 0.
494
internal virtual void Validate(DirCacheEntry[] cache, int cCnt, int cIdx, int pathOff
499
// If we are valid, our children are also valid.
500
// We have no need to validate them.
507
// Special case of an empty index, and we are the root tree.
511
byte[] firstPath = cache[cIdx].path;
515
byte[] currPath = cache[cIdx].path;
516
if (pathOff > 0 && !Peq(firstPath, currPath, pathOff))
518
// The current entry is no longer in this tree. Our
519
// span is updated and the remainder goes elsewhere.
523
NGit.Dircache.DirCacheTree st = stIdx < childCnt ? children[stIdx] : null;
524
int cc = Namecmp(currPath, pathOff, st);
527
// This subtree is now empty.
534
int p = Slash(currPath, pathOff);
537
// The entry has no '/' and thus is directly in this
538
// tree. Count it as one of our own.
544
// Build a new subtree for this entry.
546
st = new NGit.Dircache.DirCacheTree(this, currPath, pathOff, p - pathOff);
547
InsertChild(stIdx, st);
549
// The entry is contained in this subtree.
551
st.Validate(cache, cCnt, cIdx, pathOff + st.NameLength() + 1);
552
cIdx += st.entrySpan;
553
entrySpan += st.entrySpan;
556
// None of our remaining children can be in this tree
557
// as the current cache entry is after our own name.
559
while (stIdx < childCnt)
561
RemoveChild(childCnt - 1);
565
private void InsertChild(int stIdx, NGit.Dircache.DirCacheTree st)
567
NGit.Dircache.DirCacheTree[] c = children;
568
if (childCnt + 1 <= c.Length)
570
if (stIdx < childCnt)
572
System.Array.Copy(c, stIdx, c, stIdx + 1, childCnt - stIdx);
579
NGit.Dircache.DirCacheTree[] a = new NGit.Dircache.DirCacheTree[n + 1];
582
System.Array.Copy(c, 0, a, 0, stIdx);
587
System.Array.Copy(c, stIdx, a, stIdx + 1, n - stIdx);
593
private void RemoveChild(int stIdx)
598
System.Array.Copy(children, stIdx + 1, children, stIdx, n - stIdx);
603
internal static bool Peq(byte[] a, byte[] b, int aLen)
609
for (aLen--; aLen >= 0; aLen--)
611
if (a[aLen] != b[aLen])
619
private static int Namecmp(byte[] a, int aPos, NGit.Dircache.DirCacheTree ct)
625
byte[] b = ct.encodedName;
629
for (; aPos < aLen && bPos < bLen; aPos++, bPos++)
631
int cmp = (a[aPos] & unchecked((int)(0xff))) - (b[bPos] & unchecked((int)(0xff)));
639
return a[aPos] == '/' ? 0 : -1;
644
private static int Slash(byte[] a, int aPos)
647
for (; aPos < aLen; aPos++)
added
removed
contrib/NGit/NGit.Dircache/DirCacheTree.cs
