← Back to branch summary

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

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit/ObjectIdOwnerMap.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/ObjectIdOwnerMap.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;
 
46
using Sharpen;
 
47
 
 
48
namespace NGit
 
49
{
 
50
        /// <summary>
 
51
        /// Fast, efficient map for
 
52
        /// <see cref="ObjectId">ObjectId</see>
 
53
        /// subclasses in only one map.
 
54
        /// <p>
 
55
        /// To use this map type, applications must have their entry value type extend
 
56
        /// from
 
57
        /// <see cref="Entry">Entry</see>
 
58
        /// , which itself extends from ObjectId.
 
59
        /// <p>
 
60
        /// Object instances may only be stored in <b>ONE</b> ObjectIdOwnerMap. This
 
61
        /// restriction exists because the map stores internal map state within each
 
62
        /// object instance. If an instance is be placed in another ObjectIdOwnerMap it
 
63
        /// could corrupt one or both map's internal state.
 
64
        /// <p>
 
65
        /// If an object instance must be in more than one map, applications may use
 
66
        /// ObjectIdOwnerMap for one of the maps, and
 
67
        /// <see cref="ObjectIdSubclassMap{V}">ObjectIdSubclassMap&lt;V&gt;</see>
 
68
        /// for the
 
69
        /// other map(s). It is encouraged to use ObjectIdOwnerMap for the map that is
 
70
        /// accessed most often, as this implementation runs faster than the more general
 
71
        /// ObjectIdSubclassMap implementation.
 
72
        /// </summary>
 
73
        /// <?></?>
 
74
        public class ObjectIdOwnerMap<V> : Iterable<V> where V:ObjectIdOwnerMap.Entry
 
75
        {
 
76
                /// <summary>Size of the initial directory, will grow as necessary.</summary>
 
77
                /// <remarks>Size of the initial directory, will grow as necessary.</remarks>
 
78
                private const int INITIAL_DIRECTORY = 1024;
 
79
 
 
80
                /// <summary>Number of bits in a segment's index.</summary>
 
81
                /// <remarks>Number of bits in a segment's index. Segments are 2^11 in size.</remarks>
 
82
                private const int SEGMENT_BITS = 11;
 
83
 
 
84
                private const int SEGMENT_SHIFT = 32 - SEGMENT_BITS;
 
85
 
 
86
                /// <summary>Top level directory of the segments.</summary>
 
87
                /// <remarks>
 
88
                /// Top level directory of the segments.
 
89
                /// <p>
 
90
                /// The low
 
91
                /// <see cref="ObjectIdOwnerMap{V}.bits">ObjectIdOwnerMap&lt;V&gt;.bits</see>
 
92
                /// of the SHA-1 are used to select the segment from
 
93
                /// this directory. Each segment is constant sized at 2^SEGMENT_BITS.
 
94
                /// </remarks>
 
95
                private V[][] directory;
 
96
 
 
97
                /// <summary>Total number of objects in this map.</summary>
 
98
                /// <remarks>Total number of objects in this map.</remarks>
 
99
                private int size;
 
100
 
 
101
                /// <summary>
 
102
                /// The map doubles in capacity when
 
103
                /// <see cref="ObjectIdOwnerMap{V}.size">ObjectIdOwnerMap&lt;V&gt;.size</see>
 
104
                /// reaches this target.
 
105
                /// </summary>
 
106
                private int grow;
 
107
 
 
108
                /// <summary>
 
109
                /// Number of low bits used to form the index into
 
110
                /// <see cref="ObjectIdOwnerMap{V}.directory">ObjectIdOwnerMap&lt;V&gt;.directory</see>
 
111
                /// .
 
112
                /// </summary>
 
113
                private int bits;
 
114
 
 
115
                /// <summary>
 
116
                /// Low bit mask to index into
 
117
                /// <see cref="ObjectIdOwnerMap{V}.directory">ObjectIdOwnerMap&lt;V&gt;.directory</see>
 
118
                /// ,
 
119
                /// <code>2^bits-1</code>
 
120
                /// .
 
121
                /// </summary>
 
122
                private int mask;
 
123
 
 
124
                /// <summary>Create an empty map.</summary>
 
125
                /// <remarks>Create an empty map.</remarks>
 
126
                public ObjectIdOwnerMap()
 
127
                {
 
128
                        bits = 0;
 
129
                        mask = 0;
 
130
                        grow = ComputeGrowAt(bits);
 
131
                        directory = new V[INITIAL_DIRECTORY][];
 
132
                        directory[0] = NewSegment();
 
133
                }
 
134
 
 
135
                /// <summary>Remove all entries from this map.</summary>
 
136
                /// <remarks>Remove all entries from this map.</remarks>
 
137
                public virtual void Clear()
 
138
                {
 
139
                        size = 0;
 
140
                        foreach (V[] tbl in directory)
 
141
                        {
 
142
                                if (tbl == null)
 
143
                                {
 
144
                                        break;
 
145
                                }
 
146
                                Arrays.Fill(tbl, null);
 
147
                        }
 
148
                }
 
149
 
 
150
                /// <summary>Lookup an existing mapping.</summary>
 
151
                /// <remarks>Lookup an existing mapping.</remarks>
 
152
                /// <param name="toFind">the object identifier to find.</param>
 
153
                /// <returns>the instance mapped to toFind, or null if no mapping exists.</returns>
 
154
                public virtual V Get(AnyObjectId toFind)
 
155
                {
 
156
                        int h = toFind.w1;
 
157
                        V obj = directory[h & mask][(int)(((uint)h) >> SEGMENT_SHIFT)];
 
158
                        for (; obj != null; obj = (V)obj.next)
 
159
                        {
 
160
                                if (Equals(obj, toFind))
 
161
                                {
 
162
                                        return obj;
 
163
                                }
 
164
                        }
 
165
                        return null;
 
166
                }
 
167
 
 
168
                /// <summary>Returns true if this map contains the specified object.</summary>
 
169
                /// <remarks>Returns true if this map contains the specified object.</remarks>
 
170
                /// <param name="toFind">object to find.</param>
 
171
                /// <returns>true if the mapping exists for this object; false otherwise.</returns>
 
172
                public virtual bool Contains(AnyObjectId toFind)
 
173
                {
 
174
                        return Get(toFind) != null;
 
175
                }
 
176
 
 
177
                /// <summary>Store an object for future lookup.</summary>
 
178
                /// <remarks>
 
179
                /// Store an object for future lookup.
 
180
                /// <p>
 
181
                /// An existing mapping for <b>must not</b> be in this map. Callers must
 
182
                /// first call
 
183
                /// <see cref="ObjectIdOwnerMap{V}.Get(AnyObjectId)">ObjectIdOwnerMap&lt;V&gt;.Get(AnyObjectId)
 
184
                ///     </see>
 
185
                /// to verify there is no current
 
186
                /// mapping prior to adding a new mapping, or use
 
187
                /// <see cref="ObjectIdOwnerMap{V}.AddIfAbsent{Q}(Entry)">ObjectIdOwnerMap&lt;V&gt;.AddIfAbsent&lt;Q&gt;(Entry)
 
188
                ///     </see>
 
189
                /// .
 
190
                /// </remarks>
 
191
                /// <param name="newValue">the object to store.</param>
 
192
                /// <?></?>
 
193
                public virtual void Add<Q>(Q newValue) where Q:V
 
194
                {
 
195
                        if (++size == grow)
 
196
                        {
 
197
                                Grow();
 
198
                        }
 
199
                        int h = ((V)newValue).w1;
 
200
                        V[] table = directory[h & mask];
 
201
                        h = (int)(((uint)h) >> SEGMENT_SHIFT);
 
202
                        newValue.next = table[h];
 
203
                        table[h] = newValue;
 
204
                }
 
205
 
 
206
                /// <summary>Store an object for future lookup.</summary>
 
207
                /// <remarks>
 
208
                /// Store an object for future lookup.
 
209
                /// <p>
 
210
                /// Stores
 
211
                /// <code>newValue</code>
 
212
                /// , but only if there is not already an object for
 
213
                /// the same object name. Callers can tell if the value is new by checking
 
214
                /// the return value with reference equality:
 
215
                /// <pre>
 
216
                /// V obj = ...;
 
217
                /// boolean wasNew = map.addIfAbsent(obj) == obj;
 
218
                /// </pre>
 
219
                /// </remarks>
 
220
                /// <param name="newValue">the object to store.</param>
 
221
                /// <returns>
 
222
                /// 
 
223
                /// <code>newValue</code>
 
224
                /// if stored, or the prior value already stored and
 
225
                /// that would have been returned had the caller used
 
226
                /// <code>get(newValue)</code>
 
227
                /// first.
 
228
                /// </returns>
 
229
                /// <?></?>
 
230
                public virtual V AddIfAbsent<Q>(Q newValue) where Q:V
 
231
                {
 
232
                        int h = ((V)newValue).w1;
 
233
                        V[] table = directory[h & mask];
 
234
                        h = (int)(((uint)h) >> SEGMENT_SHIFT);
 
235
                        for (V obj = table[h]; obj != null; obj = (V)obj.next)
 
236
                        {
 
237
                                if (Equals(obj, newValue))
 
238
                                {
 
239
                                        return obj;
 
240
                                }
 
241
                        }
 
242
                        newValue.next = table[h];
 
243
                        table[h] = newValue;
 
244
                        if (++size == grow)
 
245
                        {
 
246
                                Grow();
 
247
                        }
 
248
                        return newValue;
 
249
                }
 
250
 
 
251
                /// <returns>number of objects in this map.</returns>
 
252
                public virtual int Size()
 
253
                {
 
254
                        return size;
 
255
                }
 
256
 
 
257
                /// <returns>
 
258
                /// true if
 
259
                /// <see cref="ObjectIdOwnerMap{V}.Size()">ObjectIdOwnerMap&lt;V&gt;.Size()</see>
 
260
                /// is 0.
 
261
                /// </returns>
 
262
                public virtual bool IsEmpty()
 
263
                {
 
264
                        return size == 0;
 
265
                }
 
266
 
 
267
                public override Sharpen.Iterator<V> Iterator()
 
268
                {
 
269
                        return new _Iterator_223(this);
 
270
                }
 
271
 
 
272
                private sealed class _Iterator_223 : Sharpen.Iterator<V>
 
273
                {
 
274
                        public _Iterator_223(ObjectIdOwnerMap<V> _enclosing)
 
275
                        {
 
276
                                this._enclosing = _enclosing;
 
277
                        }
 
278
 
 
279
                        private int found;
 
280
 
 
281
                        private int dirIdx;
 
282
 
 
283
                        private int tblIdx;
 
284
 
 
285
                        private V nextv;
 
286
 
 
287
                        public override bool HasNext()
 
288
                        {
 
289
                                return this.found < this._enclosing.size;
 
290
                        }
 
291
 
 
292
                        public override V Next()
 
293
                        {
 
294
                                if (this.nextv != null)
 
295
                                {
 
296
                                        return this.Foundv(this.nextv);
 
297
                                }
 
298
                                for (; ; )
 
299
                                {
 
300
                                        V[] table = this._enclosing.directory[this.dirIdx];
 
301
                                        if (this.tblIdx == table.Length)
 
302
                                        {
 
303
                                                if (++this.dirIdx >= (1 << this._enclosing.bits))
 
304
                                                {
 
305
                                                        throw new NoSuchElementException();
 
306
                                                }
 
307
                                                table = this._enclosing.directory[this.dirIdx];
 
308
                                                this.tblIdx = 0;
 
309
                                        }
 
310
                                        while (this.tblIdx < table.Length)
 
311
                                        {
 
312
                                                V v = table[this.tblIdx++];
 
313
                                                if (v != null)
 
314
                                                {
 
315
                                                        return this.Foundv(v);
 
316
                                                }
 
317
                                        }
 
318
                                }
 
319
                        }
 
320
 
 
321
                        private V Foundv(V v)
 
322
                        {
 
323
                                this.found++;
 
324
                                this.nextv = (V)v.next;
 
325
                                return v;
 
326
                        }
 
327
 
 
328
                        public override void Remove()
 
329
                        {
 
330
                                throw new NotSupportedException();
 
331
                        }
 
332
 
 
333
                        private readonly ObjectIdOwnerMap<V> _enclosing;
 
334
                }
 
335
 
 
336
                private void Grow()
 
337
                {
 
338
                        int oldDirLen = 1 << bits;
 
339
                        int s = 1 << bits;
 
340
                        bits++;
 
341
                        mask = (1 << bits) - 1;
 
342
                        grow = ComputeGrowAt(bits);
 
343
                        // Quadruple the directory if it needs to expand. Expanding the
 
344
                        // directory is expensive because it generates garbage, so try
 
345
                        // to avoid doing it often.
 
346
                        //
 
347
                        int newDirLen = 1 << bits;
 
348
                        if (directory.Length < newDirLen)
 
349
                        {
 
350
                                V[][] newDir = (V[][])new ObjectIdOwnerMap.Entry[newDirLen << 1][];
 
351
                                System.Array.Copy(directory, 0, newDir, 0, oldDirLen);
 
352
                                directory = newDir;
 
353
                        }
 
354
                        // For every bucket of every old segment, split the chain between
 
355
                        // the old segment and the new segment's corresponding bucket. To
 
356
                        // select between them use the lowest bit that was just added into
 
357
                        // the mask above. This causes the table to double in capacity.
 
358
                        //
 
359
                        for (int dirIdx = 0; dirIdx < oldDirLen; dirIdx++)
 
360
                        {
 
361
                                V[] oldTable = directory[dirIdx];
 
362
                                V[] newTable = NewSegment();
 
363
                                for (int i = 0; i < oldTable.Length; i++)
 
364
                                {
 
365
                                        V chain0 = null;
 
366
                                        V chain1 = null;
 
367
                                        V next;
 
368
                                        for (V obj = oldTable[i]; obj != null; obj = next)
 
369
                                        {
 
370
                                                next = (V)obj.next;
 
371
                                                if ((obj.w1 & s) == 0)
 
372
                                                {
 
373
                                                        obj.next = chain0;
 
374
                                                        chain0 = obj;
 
375
                                                }
 
376
                                                else
 
377
                                                {
 
378
                                                        obj.next = chain1;
 
379
                                                        chain1 = obj;
 
380
                                                }
 
381
                                        }
 
382
                                        oldTable[i] = chain0;
 
383
                                        newTable[i] = chain1;
 
384
                                }
 
385
                                directory[oldDirLen + dirIdx] = newTable;
 
386
                        }
 
387
                }
 
388
 
 
389
                private V[] NewSegment()
 
390
                {
 
391
                        return new V[1 << SEGMENT_BITS];
 
392
                }
 
393
 
 
394
                private static int ComputeGrowAt(int bits)
 
395
                {
 
396
                        return 1 << (bits + SEGMENT_BITS);
 
397
                }
 
398
 
 
399
                private static bool Equals(AnyObjectId firstObjectId, AnyObjectId secondObjectId)
 
400
                {
 
401
                        return firstObjectId.w2 == secondObjectId.w2 && firstObjectId.w3 == secondObjectId
 
402
                                .w3 && firstObjectId.w4 == secondObjectId.w4 && firstObjectId.w5 == secondObjectId
 
403
                                .w5 && firstObjectId.w1 == secondObjectId.w1;
 
404
                }
 
405
        }
 
406
        
 
407
        public class ObjectIdOwnerMap
 
408
        {
 
409
                /// <summary>
 
410
                /// Type of entry stored in the
 
411
                /// <see cref="ObjectIdOwnerMap{V}">ObjectIdOwnerMap&lt;V&gt;</see>
 
412
                /// .
 
413
                /// </summary>
 
414
                [System.Serializable]
 
415
                public abstract class Entry : ObjectId
 
416
                {
 
417
                        internal ObjectIdOwnerMap.Entry next;
 
418
 
 
419
                        /// <summary>Initialize this entry with a specific ObjectId.</summary>
 
420
                        /// <remarks>Initialize this entry with a specific ObjectId.</remarks>
 
421
                        /// <param name="id">the id the entry represents.</param>
 
422
                        protected internal Entry(AnyObjectId id) : base(id)
 
423
                        {
 
424
                        }
 
425
                }
 
426
        }
 
427
}