← Back to branch summary

~ubuntu-branches/ubuntu/wily/monodevelop/wily

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit/ObjectIdSubclassMap.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2012-05-27 18:08:20 UTC
  • mfrom: (19.1.8 experimental)
  • Revision ID: package-import@ubuntu.com-20120527180820-fydl21qnbnfr8w2t
Tags: 3.0.2+dfsg-3
* [fcecfe7] Fix monodevelop-core-addins.pc.in to point to actual 
  installed location of assemblies.
* [26e1a07] DebSrc 3.0 does not support Quilt's -p parameter, so 
  manually adjust the path in the patch file.

Show diffs side-by-side

added added

removed removed

Lines of Context:
contrib/NGit/NGit/ObjectIdSubclassMap.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 specifically for
52
 
        /// <see cref="ObjectId">ObjectId</see>
53
 
        /// subclasses.
54
 
        /// <p>
55
 
        /// This map provides an efficient translation from any ObjectId instance to a
56
 
        /// cached subclass of ObjectId that has the same value.
57
 
        /// <p>
58
 
        /// If object instances are stored in only one map,
59
 
        /// <see cref="ObjectIdOwnerMap{V}">ObjectIdOwnerMap&lt;V&gt;</see>
60
 
        /// is a
61
 
        /// more efficient implementation.
62
 
        /// </summary>
63
 
        /// <?></?>
64
 
        public class ObjectIdSubclassMap<V> : Iterable<V> where V:ObjectId
65
 
        {
66
 
                private const int INITIAL_TABLE_SIZE = 2048;
67
 
 
68
 
                private int size;
69
 
 
70
 
                private int grow;
71
 
 
72
 
                private int mask;
73
 
 
74
 
                private V[] table;
75
 
 
76
 
                /// <summary>Create an empty map.</summary>
77
 
                /// <remarks>Create an empty map.</remarks>
78
 
                public ObjectIdSubclassMap()
79
 
                {
80
 
                        InitTable(INITIAL_TABLE_SIZE);
81
 
                }
82
 
 
83
 
                /// <summary>Remove all entries from this map.</summary>
84
 
                /// <remarks>Remove all entries from this map.</remarks>
85
 
                public virtual void Clear()
86
 
                {
87
 
                        size = 0;
88
 
                        InitTable(INITIAL_TABLE_SIZE);
89
 
                }
90
 
 
91
 
                /// <summary>Lookup an existing mapping.</summary>
92
 
                /// <remarks>Lookup an existing mapping.</remarks>
93
 
                /// <param name="toFind">the object identifier to find.</param>
94
 
                /// <returns>the instance mapped to toFind, or null if no mapping exists.</returns>
95
 
                public virtual V Get(AnyObjectId toFind)
96
 
                {
97
 
                        int msk = mask;
98
 
                        int i = toFind.w1 & msk;
99
 
                        V[] tbl = table;
100
 
                        V obj;
101
 
                        while ((obj = tbl[i]) != null)
102
 
                        {
103
 
                                if (AnyObjectId.Equals(obj, toFind))
104
 
                                {
105
 
                                        return obj;
106
 
                                }
107
 
                                i = (i + 1) & msk;
108
 
                        }
109
 
                        return null;
110
 
                }
111
 
 
112
 
                /// <summary>Returns true if this map contains the specified object.</summary>
113
 
                /// <remarks>Returns true if this map contains the specified object.</remarks>
114
 
                /// <param name="toFind">object to find.</param>
115
 
                /// <returns>true if the mapping exists for this object; false otherwise.</returns>
116
 
                public virtual bool Contains(AnyObjectId toFind)
117
 
                {
118
 
                        return Get(toFind) != null;
119
 
                }
120
 
 
121
 
                /// <summary>Store an object for future lookup.</summary>
122
 
                /// <remarks>
123
 
                /// Store an object for future lookup.
124
 
                /// <p>
125
 
                /// An existing mapping for <b>must not</b> be in this map. Callers must
126
 
                /// first call
127
 
                /// <see cref="ObjectIdSubclassMap{V}.Get(AnyObjectId)">ObjectIdSubclassMap&lt;V&gt;.Get(AnyObjectId)
128
 
                ///     </see>
129
 
                /// to verify there is no current
130
 
                /// mapping prior to adding a new mapping, or use
131
 
                /// <see cref="ObjectIdSubclassMap{V}.AddIfAbsent{Q}(ObjectId)">ObjectIdSubclassMap&lt;V&gt;.AddIfAbsent&lt;Q&gt;(ObjectId)
132
 
                ///     </see>
133
 
                /// .
134
 
                /// </remarks>
135
 
                /// <param name="newValue">the object to store.</param>
136
 
                /// <?></?>
137
 
                public virtual void Add<Q>(Q newValue) where Q:V
138
 
                {
139
 
                        if (++size == grow)
140
 
                        {
141
 
                                Grow();
142
 
                        }
143
 
                        Insert(newValue);
144
 
                }
145
 
 
146
 
                /// <summary>Store an object for future lookup.</summary>
147
 
                /// <remarks>
148
 
                /// Store an object for future lookup.
149
 
                /// <p>
150
 
                /// Stores
151
 
                /// <code>newValue</code>
152
 
                /// , but only if there is not already an object for
153
 
                /// the same object name. Callers can tell if the value is new by checking
154
 
                /// the return value with reference equality:
155
 
                /// <pre>
156
 
                /// V obj = ...;
157
 
                /// boolean wasNew = map.addIfAbsent(obj) == obj;
158
 
                /// </pre>
159
 
                /// </remarks>
160
 
                /// <param name="newValue">the object to store.</param>
161
 
                /// <returns>
162
 
                /// 
163
 
                /// <code>newValue</code>
164
 
                /// if stored, or the prior value already stored and
165
 
                /// that would have been returned had the caller used
166
 
                /// <code>get(newValue)</code>
167
 
                /// first.
168
 
                /// </returns>
169
 
                /// <?></?>
170
 
                public virtual V AddIfAbsent<Q>(Q newValue) where Q:V
171
 
                {
172
 
                        int msk = mask;
173
 
                        int i = ((ObjectId)newValue).w1 & msk;
174
 
                        V[] tbl = table;
175
 
                        V obj;
176
 
                        while ((obj = tbl[i]) != null)
177
 
                        {
178
 
                                if (AnyObjectId.Equals(obj, newValue))
179
 
                                {
180
 
                                        return obj;
181
 
                                }
182
 
                                i = (i + 1) & msk;
183
 
                        }
184
 
                        if (++size == grow)
185
 
                        {
186
 
                                Grow();
187
 
                                Insert(newValue);
188
 
                        }
189
 
                        else
190
 
                        {
191
 
                                tbl[i] = newValue;
192
 
                        }
193
 
                        return newValue;
194
 
                }
195
 
 
196
 
                /// <returns>number of objects in map</returns>
197
 
                public virtual int Size()
198
 
                {
199
 
                        return size;
200
 
                }
201
 
 
202
 
                /// <returns>
203
 
                /// true if
204
 
                /// <see cref="ObjectIdSubclassMap{V}.Size()">ObjectIdSubclassMap&lt;V&gt;.Size()</see>
205
 
                /// is 0.
206
 
                /// </returns>
207
 
                public virtual bool IsEmpty()
208
 
                {
209
 
                        return size == 0;
210
 
                }
211
 
 
212
 
                public override Sharpen.Iterator<V> Iterator()
213
 
                {
214
 
                        return new _Iterator_190(this);
215
 
                }
216
 
 
217
 
                private sealed class _Iterator_190 : Sharpen.Iterator<V>
218
 
                {
219
 
                        public _Iterator_190(ObjectIdSubclassMap<V> _enclosing)
220
 
                        {
221
 
                                this._enclosing = _enclosing;
222
 
                        }
223
 
 
224
 
                        private int found;
225
 
 
226
 
                        private int i;
227
 
 
228
 
                        public override bool HasNext()
229
 
                        {
230
 
                                return this.found < this._enclosing.size;
231
 
                        }
232
 
 
233
 
                        public override V Next()
234
 
                        {
235
 
                                while (this.i < this._enclosing.table.Length)
236
 
                                {
237
 
                                        V v = this._enclosing.table[this.i++];
238
 
                                        if (v != null)
239
 
                                        {
240
 
                                                this.found++;
241
 
                                                return v;
242
 
                                        }
243
 
                                }
244
 
                                throw new NoSuchElementException();
245
 
                        }
246
 
 
247
 
                        public override void Remove()
248
 
                        {
249
 
                                throw new NotSupportedException();
250
 
                        }
251
 
 
252
 
                        private readonly ObjectIdSubclassMap<V> _enclosing;
253
 
                }
254
 
 
255
 
                private void Insert(V newValue)
256
 
                {
257
 
                        int msk = mask;
258
 
                        int j = newValue.w1 & msk;
259
 
                        V[] tbl = table;
260
 
                        while (tbl[j] != null)
261
 
                        {
262
 
                                j = (j + 1) & msk;
263
 
                        }
264
 
                        tbl[j] = newValue;
265
 
                }
266
 
 
267
 
                private void Grow()
268
 
                {
269
 
                        V[] oldTable = table;
270
 
                        int oldSize = table.Length;
271
 
                        InitTable(oldSize << 1);
272
 
                        for (int i = 0; i < oldSize; i++)
273
 
                        {
274
 
                                V obj = oldTable[i];
275
 
                                if (obj != null)
276
 
                                {
277
 
                                        Insert(obj);
278
 
                                }
279
 
                        }
280
 
                }
281
 
 
282
 
                private void InitTable(int sz)
283
 
                {
284
 
                        grow = sz >> 1;
285
 
                        mask = sz - 1;
286
 
                        table = CreateArray(sz);
287
 
                }
288
 
 
289
 
                private V[] CreateArray(int sz)
290
 
                {
291
 
                        return new V[sz];
292
 
                }
293
 
        }
294
 
}