← Back to branch summary

~ubuntu-branches/ubuntu/quantal/monodevelop/quantal

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Storage.File/PackIndexV2.cs

  • Committer: Bazaar Package Importer
  • Author(s): Andrew Mitchell
  • Date: 2011-06-29 06:56:25 UTC
  • mfrom: (1.8.1 upstream) (1.3.11 experimental)
  • Revision ID: james.westby@ubuntu.com-20110629065625-7xx19c4vb95j65pl
Tags: 2.5.92+dfsg-1ubuntu1
* Merge from Debian experimental:
 - Dropped patches & changes to debian/control for Moonlight
   + debian/patches/remove_support_for_moonlight.patch,
   + debian/patches/dont_add_moonlight_to_core_addins.patch,
 - Remaining patches:
   + debian/patches/no_appmenu:

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit.Storage.File/PackIndexV2.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.Collections.Generic;
 
45
using System.IO;
 
46
using NGit;
 
47
using NGit.Errors;
 
48
using NGit.Storage.File;
 
49
using NGit.Util;
 
50
using Sharpen;
 
51
 
 
52
namespace NGit.Storage.File
 
53
{
 
54
        /// <summary>Support for the pack index v2 format.</summary>
 
55
        /// <remarks>Support for the pack index v2 format.</remarks>
 
56
        internal class PackIndexV2 : PackIndex
 
57
        {
 
58
                private const long IS_O64 = 1L << 31;
 
59
 
 
60
                private const int FANOUT = 256;
 
61
 
 
62
                private static readonly int[] NO_INTS = new int[] {  };
 
63
 
 
64
                private static readonly byte[] NO_BYTES = new byte[] {  };
 
65
 
 
66
                private long objectCnt;
 
67
 
 
68
                private readonly long[] fanoutTable;
 
69
 
 
70
                /// <summary>256 arrays of contiguous object names.</summary>
 
71
                /// <remarks>256 arrays of contiguous object names.</remarks>
 
72
                private int[][] names;
 
73
 
 
74
                /// <summary>
 
75
                /// 256 arrays of the 32 bit offset data, matching
 
76
                /// <see cref="names">names</see>
 
77
                /// .
 
78
                /// </summary>
 
79
                private byte[][] offset32;
 
80
 
 
81
                /// <summary>
 
82
                /// 256 arrays of the CRC-32 of objects, matching
 
83
                /// <see cref="names">names</see>
 
84
                /// .
 
85
                /// </summary>
 
86
                private byte[][] crc32;
 
87
 
 
88
                /// <summary>64 bit offset table.</summary>
 
89
                /// <remarks>64 bit offset table.</remarks>
 
90
                private byte[] offset64;
 
91
 
 
92
                /// <exception cref="System.IO.IOException"></exception>
 
93
                internal PackIndexV2(InputStream fd)
 
94
                {
 
95
                        byte[] fanoutRaw = new byte[4 * FANOUT];
 
96
                        IOUtil.ReadFully(fd, fanoutRaw, 0, fanoutRaw.Length);
 
97
                        fanoutTable = new long[FANOUT];
 
98
                        for (int k = 0; k < FANOUT; k++)
 
99
                        {
 
100
                                fanoutTable[k] = NB.DecodeUInt32(fanoutRaw, k * 4);
 
101
                        }
 
102
                        objectCnt = fanoutTable[FANOUT - 1];
 
103
                        names = new int[FANOUT][];
 
104
                        offset32 = new byte[FANOUT][];
 
105
                        crc32 = new byte[FANOUT][];
 
106
                        // Object name table. The size we can permit per fan-out bucket
 
107
                        // is limited to Java's 2 GB per byte array limitation. That is
 
108
                        // no more than 107,374,182 objects per fan-out.
 
109
                        //
 
110
                        for (int k_1 = 0; k_1 < FANOUT; k_1++)
 
111
                        {
 
112
                                long bucketCnt;
 
113
                                if (k_1 == 0)
 
114
                                {
 
115
                                        bucketCnt = fanoutTable[k_1];
 
116
                                }
 
117
                                else
 
118
                                {
 
119
                                        bucketCnt = fanoutTable[k_1] - fanoutTable[k_1 - 1];
 
120
                                }
 
121
                                if (bucketCnt == 0)
 
122
                                {
 
123
                                        names[k_1] = NO_INTS;
 
124
                                        offset32[k_1] = NO_BYTES;
 
125
                                        crc32[k_1] = NO_BYTES;
 
126
                                        continue;
 
127
                                }
 
128
                                long nameLen = bucketCnt * Constants.OBJECT_ID_LENGTH;
 
129
                                if (nameLen > int.MaxValue)
 
130
                                {
 
131
                                        throw new IOException(JGitText.Get().indexFileIsTooLargeForJgit);
 
132
                                }
 
133
                                int intNameLen = (int)nameLen;
 
134
                                byte[] raw = new byte[intNameLen];
 
135
                                int[] bin = new int[(int)(((uint)intNameLen) >> 2)];
 
136
                                IOUtil.ReadFully(fd, raw, 0, raw.Length);
 
137
                                for (int i = 0; i < bin.Length; i++)
 
138
                                {
 
139
                                        bin[i] = NB.DecodeInt32(raw, i << 2);
 
140
                                }
 
141
                                names[k_1] = bin;
 
142
                                offset32[k_1] = new byte[(int)(bucketCnt * 4)];
 
143
                                crc32[k_1] = new byte[(int)(bucketCnt * 4)];
 
144
                        }
 
145
                        // CRC32 table.
 
146
                        for (int k_2 = 0; k_2 < FANOUT; k_2++)
 
147
                        {
 
148
                                IOUtil.ReadFully(fd, crc32[k_2], 0, crc32[k_2].Length);
 
149
                        }
 
150
                        // 32 bit offset table. Any entries with the most significant bit
 
151
                        // set require a 64 bit offset entry in another table.
 
152
                        //
 
153
                        int o64cnt = 0;
 
154
                        for (int k_3 = 0; k_3 < FANOUT; k_3++)
 
155
                        {
 
156
                                byte[] ofs = offset32[k_3];
 
157
                                IOUtil.ReadFully(fd, ofs, 0, ofs.Length);
 
158
                                for (int p = 0; p < ofs.Length; p += 4)
 
159
                                {
 
160
                                        if (((sbyte)ofs[p]) < 0)
 
161
                                        {
 
162
                                                o64cnt++;
 
163
                                        }
 
164
                                }
 
165
                        }
 
166
                        // 64 bit offset table. Most objects should not require an entry.
 
167
                        //
 
168
                        if (o64cnt > 0)
 
169
                        {
 
170
                                offset64 = new byte[o64cnt * 8];
 
171
                                IOUtil.ReadFully(fd, offset64, 0, offset64.Length);
 
172
                        }
 
173
                        else
 
174
                        {
 
175
                                offset64 = NO_BYTES;
 
176
                        }
 
177
                        packChecksum = new byte[20];
 
178
                        IOUtil.ReadFully(fd, packChecksum, 0, packChecksum.Length);
 
179
                }
 
180
 
 
181
                internal override long GetObjectCount()
 
182
                {
 
183
                        return objectCnt;
 
184
                }
 
185
 
 
186
                internal override long GetOffset64Count()
 
187
                {
 
188
                        return offset64.Length / 8;
 
189
                }
 
190
 
 
191
                internal override ObjectId GetObjectId(long nthPosition)
 
192
                {
 
193
                        int levelOne = System.Array.BinarySearch(fanoutTable, nthPosition + 1);
 
194
                        long @base;
 
195
                        if (levelOne >= 0)
 
196
                        {
 
197
                                // If we hit the bucket exactly the item is in the bucket, or
 
198
                                // any bucket before it which has the same object count.
 
199
                                //
 
200
                                @base = fanoutTable[levelOne];
 
201
                                while (levelOne > 0 && @base == fanoutTable[levelOne - 1])
 
202
                                {
 
203
                                        levelOne--;
 
204
                                }
 
205
                        }
 
206
                        else
 
207
                        {
 
208
                                // The item is in the bucket we would insert it into.
 
209
                                //
 
210
                                levelOne = -(levelOne + 1);
 
211
                        }
 
212
                        @base = levelOne > 0 ? fanoutTable[levelOne - 1] : 0;
 
213
                        int p = (int)(nthPosition - @base);
 
214
                        int p4 = p << 2;
 
215
                        return ObjectId.FromRaw(names[levelOne], p4 + p);
 
216
                }
 
217
 
 
218
                // p * 5
 
219
                internal override long FindOffset(AnyObjectId objId)
 
220
                {
 
221
                        int levelOne = objId.FirstByte;
 
222
                        int levelTwo = BinarySearchLevelTwo(objId, levelOne);
 
223
                        if (levelTwo == -1)
 
224
                        {
 
225
                                return -1;
 
226
                        }
 
227
                        long p = NB.DecodeUInt32(offset32[levelOne], levelTwo << 2);
 
228
                        if ((p & IS_O64) != 0)
 
229
                        {
 
230
                                return NB.DecodeUInt64(offset64, (8 * (int)(p & ~IS_O64)));
 
231
                        }
 
232
                        return p;
 
233
                }
 
234
 
 
235
                /// <exception cref="NGit.Errors.MissingObjectException"></exception>
 
236
                internal override long FindCRC32(AnyObjectId objId)
 
237
                {
 
238
                        int levelOne = objId.FirstByte;
 
239
                        int levelTwo = BinarySearchLevelTwo(objId, levelOne);
 
240
                        if (levelTwo == -1)
 
241
                        {
 
242
                                throw new MissingObjectException(objId.Copy(), "unknown");
 
243
                        }
 
244
                        return NB.DecodeUInt32(crc32[levelOne], levelTwo << 2);
 
245
                }
 
246
 
 
247
                internal override bool HasCRC32Support()
 
248
                {
 
249
                        return true;
 
250
                }
 
251
 
 
252
                public override Sharpen.Iterator<PackIndex.MutableEntry> Iterator()
 
253
                {
 
254
                        return new PackIndexV2.EntriesIteratorV2(this);
 
255
                }
 
256
 
 
257
                /// <exception cref="System.IO.IOException"></exception>
 
258
                internal override void Resolve(ICollection<ObjectId> matches, AbbreviatedObjectId
 
259
                         id, int matchLimit)
 
260
                {
 
261
                        int[] data = names[id.FirstByte];
 
262
                        int max = (int)(((uint)offset32[id.FirstByte].Length) >> 2);
 
263
                        int high = max;
 
264
                        if (high == 0)
 
265
                        {
 
266
                                return;
 
267
                        }
 
268
                        int low = 0;
 
269
                        do
 
270
                        {
 
271
                                int p = (int)(((uint)(low + high)) >> 1);
 
272
                                int cmp = id.PrefixCompare(data, IdOffset(p));
 
273
                                if (cmp < 0)
 
274
                                {
 
275
                                        high = p;
 
276
                                }
 
277
                                else
 
278
                                {
 
279
                                        if (cmp == 0)
 
280
                                        {
 
281
                                                // We may have landed in the middle of the matches.  Move
 
282
                                                // backwards to the start of matches, then walk forwards.
 
283
                                                //
 
284
                                                while (0 < p && id.PrefixCompare(data, IdOffset(p - 1)) == 0)
 
285
                                                {
 
286
                                                        p--;
 
287
                                                }
 
288
                                                for (; p < max && id.PrefixCompare(data, IdOffset(p)) == 0; p++)
 
289
                                                {
 
290
                                                        matches.AddItem(ObjectId.FromRaw(data, IdOffset(p)));
 
291
                                                        if (matches.Count > matchLimit)
 
292
                                                        {
 
293
                                                                break;
 
294
                                                        }
 
295
                                                }
 
296
                                                return;
 
297
                                        }
 
298
                                        else
 
299
                                        {
 
300
                                                low = p + 1;
 
301
                                        }
 
302
                                }
 
303
                        }
 
304
                        while (low < high);
 
305
                }
 
306
 
 
307
                private static int IdOffset(int p)
 
308
                {
 
309
                        return (p << 2) + p;
 
310
                }
 
311
 
 
312
                // p * 5
 
313
                private int BinarySearchLevelTwo(AnyObjectId objId, int levelOne)
 
314
                {
 
315
                        int[] data = names[levelOne];
 
316
                        int high = (int)(((uint)offset32[levelOne].Length) >> 2);
 
317
                        if (high == 0)
 
318
                        {
 
319
                                return -1;
 
320
                        }
 
321
                        int low = 0;
 
322
                        do
 
323
                        {
 
324
                                int mid = (int)(((uint)(low + high)) >> 1);
 
325
                                int mid4 = mid << 2;
 
326
                                int cmp;
 
327
                                cmp = objId.CompareTo(data, mid4 + mid);
 
328
                                // mid * 5
 
329
                                if (cmp < 0)
 
330
                                {
 
331
                                        high = mid;
 
332
                                }
 
333
                                else
 
334
                                {
 
335
                                        if (cmp == 0)
 
336
                                        {
 
337
                                                return mid;
 
338
                                        }
 
339
                                        else
 
340
                                        {
 
341
                                                low = mid + 1;
 
342
                                        }
 
343
                                }
 
344
                        }
 
345
                        while (low < high);
 
346
                        return -1;
 
347
                }
 
348
 
 
349
                private class EntriesIteratorV2 : PackIndex.EntriesIterator
 
350
                {
 
351
                        private int levelOne;
 
352
 
 
353
                        private int levelTwo;
 
354
 
 
355
                        protected internal override PackIndex.MutableEntry InitEntry()
 
356
                        {
 
357
                                return new _MutableEntry_290(this);
 
358
                        }
 
359
 
 
360
                        private sealed class _MutableEntry_290 : PackIndex.MutableEntry
 
361
                        {
 
362
                                public _MutableEntry_290(EntriesIteratorV2 _enclosing)
 
363
                                {
 
364
                                        this._enclosing = _enclosing;
 
365
                                }
 
366
 
 
367
                                internal override void EnsureId()
 
368
                                {
 
369
                                        this.idBuffer.FromRaw(this._enclosing._enclosing.names[this._enclosing.levelOne], 
 
370
                                                this._enclosing.levelTwo - Constants.OBJECT_ID_LENGTH / 4);
 
371
                                }
 
372
 
 
373
                                private readonly EntriesIteratorV2 _enclosing;
 
374
                        }
 
375
 
 
376
                        public override PackIndex.MutableEntry Next()
 
377
                        {
 
378
                                for (; this.levelOne < this._enclosing.names.Length; this.levelOne++)
 
379
                                {
 
380
                                        if (this.levelTwo < this._enclosing.names[this.levelOne].Length)
 
381
                                        {
 
382
                                                int idx = this.levelTwo / (Constants.OBJECT_ID_LENGTH / 4) * 4;
 
383
                                                long offset = NB.DecodeUInt32(this._enclosing.offset32[this.levelOne], idx);
 
384
                                                if ((offset & PackIndexV2.IS_O64) != 0)
 
385
                                                {
 
386
                                                        idx = (8 * (int)(offset & ~PackIndexV2.IS_O64));
 
387
                                                        offset = NB.DecodeUInt64(this._enclosing.offset64, idx);
 
388
                                                }
 
389
                                                this.entry.offset = offset;
 
390
                                                this.levelTwo += Constants.OBJECT_ID_LENGTH / 4;
 
391
                                                this.returnedNumber++;
 
392
                                                return this.entry;
 
393
                                        }
 
394
                                        this.levelTwo = 0;
 
395
                                }
 
396
                                throw new NoSuchElementException();
 
397
                        }
 
398
 
 
399
                        internal EntriesIteratorV2(PackIndexV2 _enclosing) : base(_enclosing)
 
400
                        {
 
401
                                this._enclosing = _enclosing;
 
402
                        }
 
403
 
 
404
                        private readonly PackIndexV2 _enclosing;
 
405
                }
 
406
        }
 
407
}