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.
49
namespace NGit.Revwalk
52
/// An ordered list of
53
/// <see cref="RevObject">RevObject</see>
57
public class RevObjectList<E> : AbstractList<E> where E:RevObject
59
internal const int BLOCK_SHIFT = 8;
61
internal const int BLOCK_SIZE = 1 << BLOCK_SHIFT;
63
/// <summary>Items stored in this list.</summary>
65
/// Items stored in this list.
68
/// <see cref="RevObjectListBlock.shift">RevObjectListBlock.shift</see>
69
/// = 0 this block holds the list elements; otherwise
70
/// it holds pointers to other
71
/// <see cref="RevObjectListBlock">RevObjectListBlock</see>
72
/// instances which use a shift that
74
/// <see cref="RevObjectList{E}.BLOCK_SHIFT">RevObjectList<E>.BLOCK_SHIFT</see>
77
internal RevObjectListBlock contents = new RevObjectListBlock(0);
79
/// <summary>Current number of elements in the list.</summary>
80
/// <remarks>Current number of elements in the list.</remarks>
81
protected internal int size = 0;
83
/// <summary>Create an empty object list.</summary>
84
/// <remarks>Create an empty object list.</remarks>
85
public RevObjectList()
90
public override void Add(int index, E element)
94
throw new NotSupportedException(MessageFormat.Format(JGitText.Get().unsupportedOperationNotAddAtEnd
101
public override E Set(int index, E element)
103
RevObjectListBlock s = contents;
104
while (index >> s.shift >= BLOCK_SIZE)
106
s = new RevObjectListBlock(s.shift + BLOCK_SHIFT);
107
s.contents[0] = contents;
112
int i = index >> s.shift;
113
index -= i << s.shift;
114
if (s.contents[i] == null)
116
s.contents[i] = new RevObjectListBlock(s.shift - BLOCK_SHIFT);
118
s = (RevObjectListBlock)s.contents[i];
120
object old = s.contents[index];
121
s.contents[index] = element;
125
public override E Get(int index)
127
RevObjectListBlock s = contents;
128
if (index >> s.shift >= 1024)
132
while (s != null && s.shift > 0)
134
int i = index >> s.shift;
135
index -= i << s.shift;
136
s = (RevObjectListBlock)s.contents[i];
138
return s != null ? (E)s.contents[index] : null;
141
public override int Count
149
public override void Clear()
151
contents = new RevObjectListBlock(0);
156
/// <summary>One level of contents, either an intermediate level or a leaf level.</summary>
157
/// <remarks>One level of contents, either an intermediate level or a leaf level.</remarks>
158
internal class RevObjectListBlock
160
internal readonly object[] contents = new object[RevObjectList<RevObject>.BLOCK_SIZE];
162
internal readonly int shift;
164
internal RevObjectListBlock(int s)