← Back to branch summary

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

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Storage.File/PackIndexV1.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.Storage.File/PackIndexV1.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 System.Collections.Generic;
 
46
using NGit;
 
47
using NGit.Storage.File;
 
48
using NGit.Util;
 
49
using Sharpen;
 
50
 
 
51
namespace NGit.Storage.File
 
52
{
 
53
        internal class PackIndexV1 : PackIndex
 
54
        {
 
55
                private const int IDX_HDR_LEN = 256 * 4;
 
56
 
 
57
                private readonly long[] idxHeader;
 
58
 
 
59
                private byte[][] idxdata;
 
60
 
 
61
                private long objectCnt;
 
62
 
 
63
                /// <exception cref="NGit.Errors.CorruptObjectException"></exception>
 
64
                /// <exception cref="System.IO.IOException"></exception>
 
65
                internal PackIndexV1(InputStream fd, byte[] hdr)
 
66
                {
 
67
                        byte[] fanoutTable = new byte[IDX_HDR_LEN];
 
68
                        System.Array.Copy(hdr, 0, fanoutTable, 0, hdr.Length);
 
69
                        IOUtil.ReadFully(fd, fanoutTable, hdr.Length, IDX_HDR_LEN - hdr.Length);
 
70
                        idxHeader = new long[256];
 
71
                        // really unsigned 32-bit...
 
72
                        for (int k = 0; k < idxHeader.Length; k++)
 
73
                        {
 
74
                                idxHeader[k] = NB.DecodeUInt32(fanoutTable, k * 4);
 
75
                        }
 
76
                        idxdata = new byte[idxHeader.Length][];
 
77
                        for (int k_1 = 0; k_1 < idxHeader.Length; k_1++)
 
78
                        {
 
79
                                int n;
 
80
                                if (k_1 == 0)
 
81
                                {
 
82
                                        n = (int)(idxHeader[k_1]);
 
83
                                }
 
84
                                else
 
85
                                {
 
86
                                        n = (int)(idxHeader[k_1] - idxHeader[k_1 - 1]);
 
87
                                }
 
88
                                if (n > 0)
 
89
                                {
 
90
                                        idxdata[k_1] = new byte[n * (Constants.OBJECT_ID_LENGTH + 4)];
 
91
                                        IOUtil.ReadFully(fd, idxdata[k_1], 0, idxdata[k_1].Length);
 
92
                                }
 
93
                        }
 
94
                        objectCnt = idxHeader[255];
 
95
                        packChecksum = new byte[20];
 
96
                        IOUtil.ReadFully(fd, packChecksum, 0, packChecksum.Length);
 
97
                }
 
98
 
 
99
                internal override long GetObjectCount()
 
100
                {
 
101
                        return objectCnt;
 
102
                }
 
103
 
 
104
                internal override long GetOffset64Count()
 
105
                {
 
106
                        long n64 = 0;
 
107
                        foreach (PackIndex.MutableEntry e in this)
 
108
                        {
 
109
                                if (e.GetOffset() >= int.MaxValue)
 
110
                                {
 
111
                                        n64++;
 
112
                                }
 
113
                        }
 
114
                        return n64;
 
115
                }
 
116
 
 
117
                internal override ObjectId GetObjectId(long nthPosition)
 
118
                {
 
119
                        int levelOne = System.Array.BinarySearch(idxHeader, nthPosition + 1);
 
120
                        long @base;
 
121
                        if (levelOne >= 0)
 
122
                        {
 
123
                                // If we hit the bucket exactly the item is in the bucket, or
 
124
                                // any bucket before it which has the same object count.
 
125
                                //
 
126
                                @base = idxHeader[levelOne];
 
127
                                while (levelOne > 0 && @base == idxHeader[levelOne - 1])
 
128
                                {
 
129
                                        levelOne--;
 
130
                                }
 
131
                        }
 
132
                        else
 
133
                        {
 
134
                                // The item is in the bucket we would insert it into.
 
135
                                //
 
136
                                levelOne = -(levelOne + 1);
 
137
                        }
 
138
                        @base = levelOne > 0 ? idxHeader[levelOne - 1] : 0;
 
139
                        int p = (int)(nthPosition - @base);
 
140
                        int dataIdx = IdOffset(p);
 
141
                        return ObjectId.FromRaw(idxdata[levelOne], dataIdx);
 
142
                }
 
143
 
 
144
                internal override long FindOffset(AnyObjectId objId)
 
145
                {
 
146
                        int levelOne = objId.FirstByte;
 
147
                        byte[] data = idxdata[levelOne];
 
148
                        if (data == null)
 
149
                        {
 
150
                                return -1;
 
151
                        }
 
152
                        int high = data.Length / (4 + Constants.OBJECT_ID_LENGTH);
 
153
                        int low = 0;
 
154
                        do
 
155
                        {
 
156
                                int mid = (int)(((uint)(low + high)) >> 1);
 
157
                                int pos = IdOffset(mid);
 
158
                                int cmp = objId.CompareTo(data, pos);
 
159
                                if (cmp < 0)
 
160
                                {
 
161
                                        high = mid;
 
162
                                }
 
163
                                else
 
164
                                {
 
165
                                        if (cmp == 0)
 
166
                                        {
 
167
                                                int b0 = data[pos - 4] & unchecked((int)(0xff));
 
168
                                                int b1 = data[pos - 3] & unchecked((int)(0xff));
 
169
                                                int b2 = data[pos - 2] & unchecked((int)(0xff));
 
170
                                                int b3 = data[pos - 1] & unchecked((int)(0xff));
 
171
                                                return (((long)b0) << 24) | (b1 << 16) | (b2 << 8) | (b3);
 
172
                                        }
 
173
                                        else
 
174
                                        {
 
175
                                                low = mid + 1;
 
176
                                        }
 
177
                                }
 
178
                        }
 
179
                        while (low < high);
 
180
                        return -1;
 
181
                }
 
182
 
 
183
                internal override long FindCRC32(AnyObjectId objId)
 
184
                {
 
185
                        throw new NotSupportedException();
 
186
                }
 
187
 
 
188
                internal override bool HasCRC32Support()
 
189
                {
 
190
                        return false;
 
191
                }
 
192
 
 
193
                public override Sharpen.Iterator<PackIndex.MutableEntry> Iterator()
 
194
                {
 
195
                        return new PackIndexV1.IndexV1Iterator(this);
 
196
                }
 
197
 
 
198
                /// <exception cref="System.IO.IOException"></exception>
 
199
                internal override void Resolve(ICollection<ObjectId> matches, AbbreviatedObjectId
 
200
                         id, int matchLimit)
 
201
                {
 
202
                        byte[] data = idxdata[id.FirstByte];
 
203
                        if (data == null)
 
204
                        {
 
205
                                return;
 
206
                        }
 
207
                        int max = data.Length / (4 + Constants.OBJECT_ID_LENGTH);
 
208
                        int high = max;
 
209
                        int low = 0;
 
210
                        do
 
211
                        {
 
212
                                int p = (int)(((uint)(low + high)) >> 1);
 
213
                                int cmp = id.PrefixCompare(data, IdOffset(p));
 
214
                                if (cmp < 0)
 
215
                                {
 
216
                                        high = p;
 
217
                                }
 
218
                                else
 
219
                                {
 
220
                                        if (cmp == 0)
 
221
                                        {
 
222
                                                // We may have landed in the middle of the matches.  Move
 
223
                                                // backwards to the start of matches, then walk forwards.
 
224
                                                //
 
225
                                                while (0 < p && id.PrefixCompare(data, IdOffset(p - 1)) == 0)
 
226
                                                {
 
227
                                                        p--;
 
228
                                                }
 
229
                                                for (; p < max && id.PrefixCompare(data, IdOffset(p)) == 0; p++)
 
230
                                                {
 
231
                                                        matches.AddItem(ObjectId.FromRaw(data, IdOffset(p)));
 
232
                                                        if (matches.Count > matchLimit)
 
233
                                                        {
 
234
                                                                break;
 
235
                                                        }
 
236
                                                }
 
237
                                                return;
 
238
                                        }
 
239
                                        else
 
240
                                        {
 
241
                                                low = p + 1;
 
242
                                        }
 
243
                                }
 
244
                        }
 
245
                        while (low < high);
 
246
                }
 
247
 
 
248
                private static int IdOffset(int mid)
 
249
                {
 
250
                        return ((4 + Constants.OBJECT_ID_LENGTH) * mid) + 4;
 
251
                }
 
252
 
 
253
                private class IndexV1Iterator : PackIndex.EntriesIterator
 
254
                {
 
255
                        private int levelOne;
 
256
 
 
257
                        private int levelTwo;
 
258
 
 
259
                        protected internal override PackIndex.MutableEntry InitEntry()
 
260
                        {
 
261
                                return new _MutableEntry_219(this);
 
262
                        }
 
263
 
 
264
                        private sealed class _MutableEntry_219 : PackIndex.MutableEntry
 
265
                        {
 
266
                                public _MutableEntry_219(IndexV1Iterator _enclosing)
 
267
                                {
 
268
                                        this._enclosing = _enclosing;
 
269
                                }
 
270
 
 
271
                                internal override void EnsureId()
 
272
                                {
 
273
                                        this.idBuffer.FromRaw(this._enclosing._enclosing.idxdata[this._enclosing.levelOne
 
274
                                                ], this._enclosing.levelTwo - Constants.OBJECT_ID_LENGTH);
 
275
                                }
 
276
 
 
277
                                private readonly IndexV1Iterator _enclosing;
 
278
                        }
 
279
 
 
280
                        public override PackIndex.MutableEntry Next()
 
281
                        {
 
282
                                for (; this.levelOne < this._enclosing.idxdata.Length; this.levelOne++)
 
283
                                {
 
284
                                        if (this._enclosing.idxdata[this.levelOne] == null)
 
285
                                        {
 
286
                                                continue;
 
287
                                        }
 
288
                                        if (this.levelTwo < this._enclosing.idxdata[this.levelOne].Length)
 
289
                                        {
 
290
                                                this.entry.offset = NB.DecodeUInt32(this._enclosing.idxdata[this.levelOne], this.
 
291
                                                        levelTwo);
 
292
                                                this.levelTwo += Constants.OBJECT_ID_LENGTH + 4;
 
293
                                                this.returnedNumber++;
 
294
                                                return this.entry;
 
295
                                        }
 
296
                                        this.levelTwo = 0;
 
297
                                }
 
298
                                throw new NoSuchElementException();
 
299
                        }
 
300
 
 
301
                        internal IndexV1Iterator(PackIndexV1 _enclosing) : base(_enclosing)
 
302
                        {
 
303
                                this._enclosing = _enclosing;
 
304
                        }
 
305
 
 
306
                        private readonly PackIndexV1 _enclosing;
 
307
                }
 
308
        }
 
309
}