← Back to branch summary

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

« back to all changes in this revision

Viewing changes to contrib/NGit/NGit.Storage.Pack/BaseSearch.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.Pack/BaseSearch.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 NGit;
 
46
using NGit.Revwalk;
 
47
using NGit.Storage.Pack;
 
48
using NGit.Treewalk;
 
49
using Sharpen;
 
50
 
 
51
namespace NGit.Storage.Pack
 
52
{
 
53
        internal class BaseSearch
 
54
        {
 
55
                private static readonly int M_BLOB = FileMode.REGULAR_FILE.GetBits();
 
56
 
 
57
                private static readonly int M_TREE = FileMode.TREE.GetBits();
 
58
 
 
59
                private readonly ProgressMonitor progress;
 
60
 
 
61
                private readonly ObjectReader reader;
 
62
 
 
63
                private readonly ObjectId[] baseTrees;
 
64
 
 
65
                private readonly ObjectIdOwnerMap<ObjectToPack> objectsMap;
 
66
 
 
67
                private readonly IList<ObjectToPack> edgeObjects;
 
68
 
 
69
                private readonly IntSet alreadyProcessed;
 
70
 
 
71
                private readonly ObjectIdOwnerMap<BaseSearch.TreeWithData> treeCache;
 
72
 
 
73
                private readonly CanonicalTreeParser parser;
 
74
 
 
75
                private readonly MutableObjectId idBuf;
 
76
 
 
77
                internal BaseSearch(ProgressMonitor countingMonitor, ICollection<RevTree> bases, 
 
78
                        ObjectIdOwnerMap<ObjectToPack> objects, IList<ObjectToPack> edges, ObjectReader 
 
79
                        or)
 
80
                {
 
81
                        progress = countingMonitor;
 
82
                        reader = or;
 
83
                        baseTrees = Sharpen.Collections.ToArray(bases, new ObjectId[bases.Count]);
 
84
                        objectsMap = objects;
 
85
                        edgeObjects = edges;
 
86
                        alreadyProcessed = new IntSet();
 
87
                        treeCache = new ObjectIdOwnerMap<BaseSearch.TreeWithData>();
 
88
                        parser = new CanonicalTreeParser();
 
89
                        idBuf = new MutableObjectId();
 
90
                }
 
91
 
 
92
                /// <exception cref="System.IO.IOException"></exception>
 
93
                internal virtual void AddBase(int objectType, byte[] pathBuf, int pathLen, int pathHash
 
94
                        )
 
95
                {
 
96
                        int tailMode = ModeForType(objectType);
 
97
                        if (tailMode == 0)
 
98
                        {
 
99
                                return;
 
100
                        }
 
101
                        if (!alreadyProcessed.Add(pathHash))
 
102
                        {
 
103
                                return;
 
104
                        }
 
105
                        if (pathLen == 0)
 
106
                        {
 
107
                                foreach (ObjectId root in baseTrees)
 
108
                                {
 
109
                                        Add(root, Constants.OBJ_TREE, pathHash);
 
110
                                }
 
111
                                return;
 
112
                        }
 
113
                        int firstSlash = NextSlash(pathBuf, 0, pathLen);
 
114
                        foreach (ObjectId root_1 in baseTrees)
 
115
                        {
 
116
                                int ptr = 0;
 
117
                                int end = firstSlash;
 
118
                                int mode = end != pathLen ? M_TREE : tailMode;
 
119
                                parser.Reset(ReadTree(root_1));
 
120
                                while (!parser.Eof)
 
121
                                {
 
122
                                        int cmp = parser.PathCompare(pathBuf, ptr, end, mode);
 
123
                                        if (cmp < 0)
 
124
                                        {
 
125
                                                parser.Next();
 
126
                                                continue;
 
127
                                        }
 
128
                                        if (cmp > 0)
 
129
                                        {
 
130
                                                break;
 
131
                                        }
 
132
                                        if (end == pathLen)
 
133
                                        {
 
134
                                                if (parser.EntryFileMode.GetObjectType() == objectType)
 
135
                                                {
 
136
                                                        idBuf.FromRaw(parser.IdBuffer, parser.IdOffset);
 
137
                                                        Add(idBuf, objectType, pathHash);
 
138
                                                }
 
139
                                                break;
 
140
                                        }
 
141
                                        if (!FileMode.TREE.Equals(parser.EntryRawMode))
 
142
                                        {
 
143
                                                break;
 
144
                                        }
 
145
                                        ptr = end + 1;
 
146
                                        end = NextSlash(pathBuf, ptr, pathLen);
 
147
                                        mode = end != pathLen ? M_TREE : tailMode;
 
148
                                        idBuf.FromRaw(parser.IdBuffer, parser.IdOffset);
 
149
                                        parser.Reset(ReadTree(idBuf));
 
150
                                }
 
151
                        }
 
152
CHECK_BASE_break: ;
 
153
                }
 
154
 
 
155
                private static int ModeForType(int typeCode)
 
156
                {
 
157
                        switch (typeCode)
 
158
                        {
 
159
                                case Constants.OBJ_TREE:
 
160
                                {
 
161
                                        return M_TREE;
 
162
                                }
 
163
 
 
164
                                case Constants.OBJ_BLOB:
 
165
                                {
 
166
                                        return M_BLOB;
 
167
                                }
 
168
 
 
169
                                default:
 
170
                                {
 
171
                                        return 0;
 
172
                                        break;
 
173
                                }
 
174
                        }
 
175
                }
 
176
 
 
177
                private static int NextSlash(byte[] pathBuf, int ptr, int end)
 
178
                {
 
179
                        while (ptr < end && pathBuf[ptr] != '/')
 
180
                        {
 
181
                                ptr++;
 
182
                        }
 
183
                        return ptr;
 
184
                }
 
185
 
 
186
                private void Add(AnyObjectId id, int objectType, int pathHash)
 
187
                {
 
188
                        ObjectToPack obj = new ObjectToPack(id, objectType);
 
189
                        obj.SetEdge();
 
190
                        obj.SetPathHash(pathHash);
 
191
                        if (objectsMap.AddIfAbsent(obj) == obj)
 
192
                        {
 
193
                                edgeObjects.AddItem(obj);
 
194
                                progress.Update(1);
 
195
                        }
 
196
                }
 
197
 
 
198
                /// <exception cref="NGit.Errors.MissingObjectException"></exception>
 
199
                /// <exception cref="NGit.Errors.IncorrectObjectTypeException"></exception>
 
200
                /// <exception cref="System.IO.IOException"></exception>
 
201
                private byte[] ReadTree(AnyObjectId id)
 
202
                {
 
203
                        BaseSearch.TreeWithData tree = treeCache.Get(id);
 
204
                        if (tree != null)
 
205
                        {
 
206
                                return tree.buf;
 
207
                        }
 
208
                        ObjectLoader ldr = reader.Open(id, Constants.OBJ_TREE);
 
209
                        byte[] buf = ldr.GetCachedBytes(int.MaxValue);
 
210
                        treeCache.Add(new BaseSearch.TreeWithData(id, buf));
 
211
                        return buf;
 
212
                }
 
213
 
 
214
                [System.Serializable]
 
215
                private class TreeWithData : ObjectIdOwnerMap.Entry
 
216
                {
 
217
                        internal readonly byte[] buf;
 
218
 
 
219
                        internal TreeWithData(AnyObjectId id, byte[] buf) : base(id)
 
220
                        {
 
221
                                this.buf = buf;
 
222
                        }
 
223
                }
 
224
        }
 
225
}