← Back to branch summary

~ubuntu-branches/ubuntu/oneiric/monodevelop/oneiric

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Util/BlockList.cs

  • Committer: Bazaar Package Importer
  • Author(s): Jo Shields
  • Date: 2011-06-27 17:03:13 UTC
  • mto: (1.8.1 upstream)
  • mto: This revision was merged to the branch mainline in revision 54.
  • Revision ID: james.westby@ubuntu.com-20110627170313-6cvz3s19x6e9hqe9
Import upstream version 2.5.92+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit.Util/BlockList.cs
 
1
/*
 
2
This code is derived from jgit (http://eclipse.org/jgit).
 
3
Copyright owners are documented in jgit's IP log.
 
4
 
 
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
 
9
 
 
10
All rights reserved.
 
11
 
 
12
Redistribution and use in source and binary forms, with or
 
13
without modification, are permitted provided that the following
 
14
conditions are met:
 
15
 
 
16
- Redistributions of source code must retain the above copyright
 
17
  notice, this list of conditions and the following disclaimer.
 
18
 
 
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.
 
23
 
 
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
 
27
  written permission.
 
28
 
 
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.
 
42
*/
 
43
 
 
44
using System;
 
45
using NGit.Util;
 
46
using Sharpen;
 
47
 
 
48
namespace NGit.Util
 
49
{
 
50
        /// <summary>Random access list that allocates entries in blocks.</summary>
 
51
        /// <remarks>
 
52
        /// Random access list that allocates entries in blocks.
 
53
        /// <p>
 
54
        /// Unlike
 
55
        /// <see cref="System.Collections.ArrayList{E}">System.Collections.ArrayList&lt;E&gt;
 
56
        ///     </see>
 
57
        /// , this type does not need to reallocate the
 
58
        /// internal array in order to expand the capacity of the list. Access to any
 
59
        /// element is constant time, but requires two array lookups instead of one.
 
60
        /// <p>
 
61
        /// To handle common usages,
 
62
        /// <see cref="BlockList{T}.AddItem(object)">BlockList&lt;T&gt;.AddItem(object)</see>
 
63
        /// and
 
64
        /// <see cref="BlockList{T}.Iterator()">BlockList&lt;T&gt;.Iterator()</see>
 
65
        /// use
 
66
        /// internal code paths to amortize out the second array lookup, making addition
 
67
        /// and simple iteration closer to one array operation per element processed.
 
68
        /// <p>
 
69
        /// Similar to
 
70
        /// <code>ArrayList</code>
 
71
        /// , adding or removing from any position except the
 
72
        /// end of the list requires O(N) time to copy all elements between the
 
73
        /// modification point and the end of the list. Applications are strongly
 
74
        /// encouraged to not use this access pattern with this list implementation.
 
75
        /// </remarks>
 
76
        /// <?></?>
 
77
        public class BlockList<T> : AbstractList<T>
 
78
        {
 
79
                private const int BLOCK_BITS = 10;
 
80
 
 
81
                internal const int BLOCK_SIZE = 1 << BLOCK_BITS;
 
82
 
 
83
                private const int BLOCK_MASK = BLOCK_SIZE - 1;
 
84
 
 
85
                private T[][] directory;
 
86
 
 
87
                private int size;
 
88
 
 
89
                private int tailDirIdx;
 
90
 
 
91
                private int tailBlkIdx;
 
92
 
 
93
                private T[] tailBlock;
 
94
 
 
95
                /// <summary>Initialize an empty list.</summary>
 
96
                /// <remarks>Initialize an empty list.</remarks>
 
97
                public BlockList()
 
98
                {
 
99
                        directory = NGit.Util.BlockList<T>.NewDirectory(256);
 
100
                        directory[0] = NGit.Util.BlockList<T>.NewBlock();
 
101
                        tailBlock = directory[0];
 
102
                }
 
103
 
 
104
                /// <summary>Initialize an empty list with an expected capacity.</summary>
 
105
                /// <remarks>Initialize an empty list with an expected capacity.</remarks>
 
106
                /// <param name="capacity">number of elements expected to be in the list.</param>
 
107
                public BlockList(int capacity)
 
108
                {
 
109
                        int dirSize = ToDirectoryIndex(capacity);
 
110
                        if ((capacity & BLOCK_MASK) != 0 || dirSize == 0)
 
111
                        {
 
112
                                dirSize++;
 
113
                        }
 
114
                        directory = NGit.Util.BlockList<T>.NewDirectory(dirSize);
 
115
                        directory[0] = NGit.Util.BlockList<T>.NewBlock();
 
116
                        tailBlock = directory[0];
 
117
                }
 
118
 
 
119
                public override int Count
 
120
                {
 
121
                        get
 
122
                        {
 
123
                                return size;
 
124
                        }
 
125
                }
 
126
 
 
127
                public override void Clear()
 
128
                {
 
129
                        foreach (T[] block in directory)
 
130
                        {
 
131
                                if (block != null)
 
132
                                {
 
133
                                        Arrays.Fill(block, default(T));
 
134
                                }
 
135
                        }
 
136
                        size = 0;
 
137
                        tailDirIdx = 0;
 
138
                        tailBlkIdx = 0;
 
139
                        tailBlock = directory[0];
 
140
                }
 
141
 
 
142
                public override T Get(int index)
 
143
                {
 
144
                        if (index < 0 || size <= index)
 
145
                        {
 
146
                                throw new IndexOutOfRangeException(index.ToString());
 
147
                        }
 
148
                        return directory[ToDirectoryIndex(index)][ToBlockIndex(index)];
 
149
                }
 
150
 
 
151
                public override T Set(int index, T element)
 
152
                {
 
153
                        if (index < 0 || size <= index)
 
154
                        {
 
155
                                throw new IndexOutOfRangeException(index.ToString());
 
156
                        }
 
157
                        T[] blockRef = directory[ToDirectoryIndex(index)];
 
158
                        int blockIdx = ToBlockIndex(index);
 
159
                        T old = blockRef[blockIdx];
 
160
                        blockRef[blockIdx] = element;
 
161
                        return old;
 
162
                }
 
163
 
 
164
                /// <summary>Quickly append all elements of another BlockList.</summary>
 
165
                /// <remarks>Quickly append all elements of another BlockList.</remarks>
 
166
                /// <param name="src">the list to copy elements from.</param>
 
167
                public virtual void AddAll(NGit.Util.BlockList<T> src)
 
168
                {
 
169
                        if (src.size == 0)
 
170
                        {
 
171
                                return;
 
172
                        }
 
173
                        int srcDirIdx = 0;
 
174
                        for (; srcDirIdx < src.tailDirIdx; srcDirIdx++)
 
175
                        {
 
176
                                AddAll(src.directory[srcDirIdx], 0, BLOCK_SIZE);
 
177
                        }
 
178
                        if (src.tailBlkIdx != 0)
 
179
                        {
 
180
                                AddAll(src.tailBlock, 0, src.tailBlkIdx);
 
181
                        }
 
182
                }
 
183
 
 
184
                /// <summary>Quickly append all elements from an array.</summary>
 
185
                /// <remarks>Quickly append all elements from an array.</remarks>
 
186
                /// <param name="src">the source array.</param>
 
187
                /// <param name="srcIdx">first index to copy.</param>
 
188
                /// <param name="srcCnt">number of elements to copy.</param>
 
189
                public virtual void AddAll(T[] src, int srcIdx, int srcCnt)
 
190
                {
 
191
                        while (0 < srcCnt)
 
192
                        {
 
193
                                int i = tailBlkIdx;
 
194
                                int n = Math.Min(srcCnt, BLOCK_SIZE - i);
 
195
                                if (n == 0)
 
196
                                {
 
197
                                        // Our tail is full, expand by one.
 
198
                                        AddItem(src[srcIdx++]);
 
199
                                        srcCnt--;
 
200
                                        continue;
 
201
                                }
 
202
                                System.Array.Copy(src, srcIdx, tailBlock, i, n);
 
203
                                tailBlkIdx += n;
 
204
                                size += n;
 
205
                                srcIdx += n;
 
206
                                srcCnt -= n;
 
207
                        }
 
208
                }
 
209
 
 
210
                public override bool AddItem(T element)
 
211
                {
 
212
                        int i = tailBlkIdx;
 
213
                        if (i < BLOCK_SIZE)
 
214
                        {
 
215
                                // Fast-path: Append to current tail block.
 
216
                                tailBlock[i] = element;
 
217
                                tailBlkIdx = i + 1;
 
218
                                size++;
 
219
                                return true;
 
220
                        }
 
221
                        // Slow path: Move to the next block, expanding if necessary.
 
222
                        if (++tailDirIdx == directory.Length)
 
223
                        {
 
224
                                T[][] newDir = NGit.Util.BlockList<T>.NewDirectory(directory.Length << 1);
 
225
                                System.Array.Copy(directory, 0, newDir, 0, directory.Length);
 
226
                                directory = newDir;
 
227
                        }
 
228
                        T[] blockRef = directory[tailDirIdx];
 
229
                        if (blockRef == null)
 
230
                        {
 
231
                                blockRef = NGit.Util.BlockList<T>.NewBlock();
 
232
                                directory[tailDirIdx] = blockRef;
 
233
                        }
 
234
                        blockRef[0] = element;
 
235
                        tailBlock = blockRef;
 
236
                        tailBlkIdx = 1;
 
237
                        size++;
 
238
                        return true;
 
239
                }
 
240
 
 
241
                public override void Add(int index, T element)
 
242
                {
 
243
                        if (index == size)
 
244
                        {
 
245
                                // Fast-path: append onto the end of the list.
 
246
                                AddItem(element);
 
247
                        }
 
248
                        else
 
249
                        {
 
250
                                if (index < 0 || size < index)
 
251
                                {
 
252
                                        throw new IndexOutOfRangeException(index.ToString());
 
253
                                }
 
254
                                else
 
255
                                {
 
256
                                        // Slow-path: the list needs to expand and insert.
 
257
                                        // Do this the naive way, callers shouldn't abuse
 
258
                                        // this class by entering this code path.
 
259
                                        //
 
260
                                        AddItem(default(T));
 
261
                                        // expand the list by one
 
262
                                        for (int oldIdx = size - 2; index <= oldIdx; oldIdx--)
 
263
                                        {
 
264
                                                Set(oldIdx + 1, this[oldIdx]);
 
265
                                        }
 
266
                                        Set(index, element);
 
267
                                }
 
268
                        }
 
269
                }
 
270
 
 
271
                public override T Remove(int index)
 
272
                {
 
273
                        if (index == size - 1)
 
274
                        {
 
275
                                // Fast-path: remove the last element.
 
276
                                T[] blockRef = directory[ToDirectoryIndex(index)];
 
277
                                int blockIdx = ToBlockIndex(index);
 
278
                                T old = blockRef[blockIdx];
 
279
                                blockRef[blockIdx] = default(T);
 
280
                                size--;
 
281
                                if (0 < tailBlkIdx)
 
282
                                {
 
283
                                        tailBlkIdx--;
 
284
                                }
 
285
                                else
 
286
                                {
 
287
                                        ResetTailBlock();
 
288
                                }
 
289
                                return old;
 
290
                        }
 
291
                        else
 
292
                        {
 
293
                                if (index < 0 || size <= index)
 
294
                                {
 
295
                                        throw new IndexOutOfRangeException(index.ToString());
 
296
                                }
 
297
                                else
 
298
                                {
 
299
                                        // Slow-path: the list needs to contract and remove.
 
300
                                        // Do this the naive way, callers shouldn't abuse
 
301
                                        // this class by entering this code path.
 
302
                                        //
 
303
                                        T old = this[index];
 
304
                                        for (; index < size - 1; index++)
 
305
                                        {
 
306
                                                Set(index, this[index + 1]);
 
307
                                        }
 
308
                                        Set(size - 1, default(T));
 
309
                                        size--;
 
310
                                        ResetTailBlock();
 
311
                                        return old;
 
312
                                }
 
313
                        }
 
314
                }
 
315
 
 
316
                private void ResetTailBlock()
 
317
                {
 
318
                        tailDirIdx = ToDirectoryIndex(size);
 
319
                        tailBlkIdx = ToBlockIndex(size);
 
320
                        tailBlock = directory[tailDirIdx];
 
321
                }
 
322
 
 
323
                public override Sharpen.Iterator<T> Iterator()
 
324
                {
 
325
                        return new BlockList<T>.MyIterator(this);
 
326
                }
 
327
 
 
328
                private static int ToDirectoryIndex(int index)
 
329
                {
 
330
                        return (int)(((uint)index) >> BLOCK_BITS);
 
331
                }
 
332
 
 
333
                private static int ToBlockIndex(int index)
 
334
                {
 
335
                        return index & BLOCK_MASK;
 
336
                }
 
337
 
 
338
                private static T[][] NewDirectory(int size)
 
339
                {
 
340
                        return new T[size][];
 
341
                }
 
342
 
 
343
                private static T[] NewBlock()
 
344
                {
 
345
                        return new T[BLOCK_SIZE];
 
346
                }
 
347
 
 
348
                private class MyIterator : Iterator<T>
 
349
                {
 
350
                        private int index;
 
351
 
 
352
                        private int dirIdx;
 
353
 
 
354
                        private int blkIdx;
 
355
 
 
356
                        private T[] block;
 
357
 
 
358
                        public override bool HasNext()
 
359
                        {
 
360
                                return this.index < this._enclosing.size;
 
361
                        }
 
362
 
 
363
                        public override T Next()
 
364
                        {
 
365
                                if (this._enclosing.size <= this.index)
 
366
                                {
 
367
                                        throw new NoSuchElementException();
 
368
                                }
 
369
                                T res = this.block[this.blkIdx];
 
370
                                if (++this.blkIdx == BlockList<T>.BLOCK_SIZE)
 
371
                                {
 
372
                                        if (++this.dirIdx < this._enclosing.directory.Length)
 
373
                                        {
 
374
                                                this.block = this._enclosing.directory[this.dirIdx];
 
375
                                        }
 
376
                                        else
 
377
                                        {
 
378
                                                this.block = null;
 
379
                                        }
 
380
                                        this.blkIdx = 0;
 
381
                                }
 
382
                                this.index++;
 
383
                                return res;
 
384
                        }
 
385
 
 
386
                        public override void Remove()
 
387
                        {
 
388
                                if (this.index == 0)
 
389
                                {
 
390
                                        throw new InvalidOperationException();
 
391
                                }
 
392
                                this._enclosing.Remove(--this.index);
 
393
                                this.dirIdx = BlockList<T>.ToDirectoryIndex(this.index);
 
394
                                this.blkIdx = BlockList<T>.ToBlockIndex(this.index);
 
395
                                this.block = this._enclosing.directory[this.dirIdx];
 
396
                        }
 
397
 
 
398
                        internal MyIterator(BlockList<T> _enclosing)
 
399
                        {
 
400
                                this._enclosing = _enclosing;
 
401
                                block = this._enclosing.directory[0];
 
402
                        }
 
403
 
 
404
                        private readonly BlockList<T> _enclosing;
 
405
                }
 
406
        }
 
407
}