← Back to branch summary

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

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Notes/LeafBucket.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.Notes/LeafBucket.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 NGit.Notes;
 
47
using Sharpen;
 
48
 
 
49
namespace NGit.Notes
 
50
{
 
51
        /// <summary>A note tree holding only notes, with no subtrees.</summary>
 
52
        /// <remarks>
 
53
        /// A note tree holding only notes, with no subtrees.
 
54
        /// The leaf bucket contains on average less than 256 notes, all of whom share
 
55
        /// the same leading prefix. If a notes branch has less than 256 notes, the top
 
56
        /// level tree of the branch should be a LeafBucket. Once a notes branch has more
 
57
        /// than 256 notes, the root should be a
 
58
        /// <see cref="FanoutBucket">FanoutBucket</see>
 
59
        /// and the LeafBucket
 
60
        /// will appear only as a cell of a FanoutBucket.
 
61
        /// Entries within the LeafBucket are stored sorted by ObjectId, and lookup is
 
62
        /// performed using binary search. As the entry list should contain fewer than
 
63
        /// 256 elements, the average number of compares to find an element should be
 
64
        /// less than 8 due to the O(log N) lookup behavior.
 
65
        /// A LeafBucket must be parsed from a tree object by
 
66
        /// <see cref="NoteParser">NoteParser</see>
 
67
        /// .
 
68
        /// </remarks>
 
69
        internal class LeafBucket : InMemoryNoteBucket
 
70
        {
 
71
                internal const int MAX_SIZE = 256;
 
72
 
 
73
                /// <summary>All note blobs in this bucket, sorted sequentially.</summary>
 
74
                /// <remarks>All note blobs in this bucket, sorted sequentially.</remarks>
 
75
                private Note[] notes;
 
76
 
 
77
                /// <summary>
 
78
                /// Number of items in
 
79
                /// <see cref="notes">notes</see>
 
80
                /// .
 
81
                /// </summary>
 
82
                private int cnt;
 
83
 
 
84
                internal LeafBucket(int prefixLen) : base(prefixLen)
 
85
                {
 
86
                        notes = new Note[4];
 
87
                }
 
88
 
 
89
                private int Search(AnyObjectId objId)
 
90
                {
 
91
                        int low = 0;
 
92
                        int high = cnt;
 
93
                        while (low < high)
 
94
                        {
 
95
                                int mid = (int)(((uint)(low + high)) >> 1);
 
96
                                int cmp = objId.CompareTo(notes[mid]);
 
97
                                if (cmp < 0)
 
98
                                {
 
99
                                        high = mid;
 
100
                                }
 
101
                                else
 
102
                                {
 
103
                                        if (cmp == 0)
 
104
                                        {
 
105
                                                return mid;
 
106
                                        }
 
107
                                        else
 
108
                                        {
 
109
                                                low = mid + 1;
 
110
                                        }
 
111
                                }
 
112
                        }
 
113
                        return -(low + 1);
 
114
                }
 
115
 
 
116
                internal override Note GetNote(AnyObjectId objId, ObjectReader or)
 
117
                {
 
118
                        int idx = Search(objId);
 
119
                        return 0 <= idx ? notes[idx] : null;
 
120
                }
 
121
 
 
122
                internal virtual Note Get(int index)
 
123
                {
 
124
                        return notes[index];
 
125
                }
 
126
 
 
127
                internal virtual int Size()
 
128
                {
 
129
                        return cnt;
 
130
                }
 
131
 
 
132
                internal override Sharpen.Iterator<Note> Iterator(AnyObjectId objId, ObjectReader
 
133
                         reader)
 
134
                {
 
135
                        return new _Iterator_121(this);
 
136
                }
 
137
 
 
138
                private sealed class _Iterator_121 : Sharpen.Iterator<Note>
 
139
                {
 
140
                        public _Iterator_121(LeafBucket _enclosing)
 
141
                        {
 
142
                                this._enclosing = _enclosing;
 
143
                        }
 
144
 
 
145
                        private int idx;
 
146
 
 
147
                        public override bool HasNext()
 
148
                        {
 
149
                                return this.idx < this._enclosing.cnt;
 
150
                        }
 
151
 
 
152
                        public override Note Next()
 
153
                        {
 
154
                                if (this.HasNext())
 
155
                                {
 
156
                                        return this._enclosing.notes[this.idx++];
 
157
                                }
 
158
                                else
 
159
                                {
 
160
                                        throw new NoSuchElementException();
 
161
                                }
 
162
                        }
 
163
 
 
164
                        public override void Remove()
 
165
                        {
 
166
                                throw new NotSupportedException();
 
167
                        }
 
168
 
 
169
                        private readonly LeafBucket _enclosing;
 
170
                }
 
171
 
 
172
                /// <exception cref="System.IO.IOException"></exception>
 
173
                internal override int EstimateSize(AnyObjectId noteOn, ObjectReader or)
 
174
                {
 
175
                        return cnt;
 
176
                }
 
177
 
 
178
                /// <exception cref="System.IO.IOException"></exception>
 
179
                internal override InMemoryNoteBucket Set(AnyObjectId noteOn, AnyObjectId noteData
 
180
                        , ObjectReader or)
 
181
                {
 
182
                        int p = Search(noteOn);
 
183
                        if (0 <= p)
 
184
                        {
 
185
                                if (noteData != null)
 
186
                                {
 
187
                                        notes[p].SetData(noteData.Copy());
 
188
                                        return this;
 
189
                                }
 
190
                                else
 
191
                                {
 
192
                                        System.Array.Copy(notes, p + 1, notes, p, cnt - p - 1);
 
193
                                        cnt--;
 
194
                                        return 0 < cnt ? this : null;
 
195
                                }
 
196
                        }
 
197
                        else
 
198
                        {
 
199
                                if (noteData != null)
 
200
                                {
 
201
                                        if (ShouldSplit())
 
202
                                        {
 
203
                                                return Split().Set(noteOn, noteData, or);
 
204
                                        }
 
205
                                        else
 
206
                                        {
 
207
                                                GrowIfFull();
 
208
                                                p = -(p + 1);
 
209
                                                if (p < cnt)
 
210
                                                {
 
211
                                                        System.Array.Copy(notes, p, notes, p + 1, cnt - p);
 
212
                                                }
 
213
                                                notes[p] = new Note(noteOn, noteData.Copy());
 
214
                                                cnt++;
 
215
                                                return this;
 
216
                                        }
 
217
                                }
 
218
                                else
 
219
                                {
 
220
                                        return this;
 
221
                                }
 
222
                        }
 
223
                }
 
224
 
 
225
                /// <exception cref="System.IO.IOException"></exception>
 
226
                internal override ObjectId WriteTree(ObjectInserter inserter)
 
227
                {
 
228
                        return inserter.Insert(Build());
 
229
                }
 
230
 
 
231
                internal override ObjectId GetTreeId()
 
232
                {
 
233
                        return new ObjectInserter.Formatter().IdFor(Build());
 
234
                }
 
235
 
 
236
                private TreeFormatter Build()
 
237
                {
 
238
                        byte[] nameBuf = new byte[Constants.OBJECT_ID_STRING_LENGTH];
 
239
                        int nameLen = Constants.OBJECT_ID_STRING_LENGTH - prefixLen;
 
240
                        TreeFormatter fmt = new TreeFormatter(TreeSize(nameLen));
 
241
                        NonNoteEntry e = nonNotes;
 
242
                        for (int i = 0; i < cnt; i++)
 
243
                        {
 
244
                                Note n = notes[i];
 
245
                                n.CopyTo(nameBuf, 0);
 
246
                                while (e != null && e.PathCompare(nameBuf, prefixLen, nameLen, FileMode.REGULAR_FILE
 
247
                                        ) < 0)
 
248
                                {
 
249
                                        e.Format(fmt);
 
250
                                        e = e.next;
 
251
                                }
 
252
                                fmt.Append(nameBuf, prefixLen, nameLen, FileMode.REGULAR_FILE, n.GetData());
 
253
                        }
 
254
                        for (; e != null; e = e.next)
 
255
                        {
 
256
                                e.Format(fmt);
 
257
                        }
 
258
                        return fmt;
 
259
                }
 
260
 
 
261
                private int TreeSize(int nameLen)
 
262
                {
 
263
                        int sz = cnt * TreeFormatter.EntrySize(FileMode.REGULAR_FILE, nameLen);
 
264
                        for (NonNoteEntry e = nonNotes; e != null; e = e.next)
 
265
                        {
 
266
                                sz += e.TreeEntrySize();
 
267
                        }
 
268
                        return sz;
 
269
                }
 
270
 
 
271
                internal virtual void ParseOneEntry(AnyObjectId noteOn, AnyObjectId noteData)
 
272
                {
 
273
                        GrowIfFull();
 
274
                        notes[cnt++] = new Note(noteOn, noteData.Copy());
 
275
                }
 
276
 
 
277
                internal override InMemoryNoteBucket Append(Note note)
 
278
                {
 
279
                        if (ShouldSplit())
 
280
                        {
 
281
                                return Split().Append(note);
 
282
                        }
 
283
                        else
 
284
                        {
 
285
                                GrowIfFull();
 
286
                                notes[cnt++] = note;
 
287
                                return this;
 
288
                        }
 
289
                }
 
290
 
 
291
                private void GrowIfFull()
 
292
                {
 
293
                        if (notes.Length == cnt)
 
294
                        {
 
295
                                Note[] n = new Note[notes.Length * 2];
 
296
                                System.Array.Copy(notes, 0, n, 0, cnt);
 
297
                                notes = n;
 
298
                        }
 
299
                }
 
300
 
 
301
                private bool ShouldSplit()
 
302
                {
 
303
                        return MAX_SIZE <= cnt && prefixLen + 2 < Constants.OBJECT_ID_STRING_LENGTH;
 
304
                }
 
305
 
 
306
                internal virtual FanoutBucket Split()
 
307
                {
 
308
                        FanoutBucket n = new FanoutBucket(prefixLen);
 
309
                        for (int i = 0; i < cnt; i++)
 
310
                        {
 
311
                                n.Append(notes[i]);
 
312
                        }
 
313
                        n.nonNotes = nonNotes;
 
314
                        return n;
 
315
                }
 
316
        }
 
317
}