← 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/UnpackedObjectCache.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/UnpackedObjectCache.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.Storage.File;
 
47
using Sharpen;
 
48
 
 
49
namespace NGit.Storage.File
 
50
{
 
51
        /// <summary>Remembers objects that are currently unpacked.</summary>
 
52
        /// <remarks>Remembers objects that are currently unpacked.</remarks>
 
53
        internal class UnpackedObjectCache
 
54
        {
 
55
                private const int INITIAL_BITS = 5;
 
56
 
 
57
                private const int MAX_BITS = 11;
 
58
 
 
59
                private volatile UnpackedObjectCache.Table table;
 
60
 
 
61
                public UnpackedObjectCache()
 
62
                {
 
63
                        // size = 32
 
64
                        // size = 2048
 
65
                        table = new UnpackedObjectCache.Table(INITIAL_BITS);
 
66
                }
 
67
 
 
68
                internal virtual bool IsUnpacked(AnyObjectId objectId)
 
69
                {
 
70
                        return table.Contains(objectId);
 
71
                }
 
72
 
 
73
                internal virtual void Add(AnyObjectId objectId)
 
74
                {
 
75
                        UnpackedObjectCache.Table t = table;
 
76
                        if (t.Add(objectId))
 
77
                        {
 
78
                        }
 
79
                        else
 
80
                        {
 
81
                                // The object either already exists in the table, or was
 
82
                                // successfully added. Either way leave the table alone.
 
83
                                //
 
84
                                // The object won't fit into the table. Implement a crude
 
85
                                // cache removal by just dropping the table away, but double
 
86
                                // it in size for the next incarnation.
 
87
                                //
 
88
                                UnpackedObjectCache.Table n = new UnpackedObjectCache.Table(Math.Min(t.bits + 1, 
 
89
                                        MAX_BITS));
 
90
                                n.Add(objectId);
 
91
                                table = n;
 
92
                        }
 
93
                }
 
94
 
 
95
                internal virtual void Remove(AnyObjectId objectId)
 
96
                {
 
97
                        if (IsUnpacked(objectId))
 
98
                        {
 
99
                                Clear();
 
100
                        }
 
101
                }
 
102
 
 
103
                internal virtual void Clear()
 
104
                {
 
105
                        table = new UnpackedObjectCache.Table(INITIAL_BITS);
 
106
                }
 
107
 
 
108
                private class Table
 
109
                {
 
110
                        private const int MAX_CHAIN = 8;
 
111
 
 
112
                        private readonly AtomicReferenceArray<ObjectId> ids;
 
113
 
 
114
                        private readonly int shift;
 
115
 
 
116
                        internal readonly int bits;
 
117
 
 
118
                        internal Table(int bits)
 
119
                        {
 
120
                                this.ids = new AtomicReferenceArray<ObjectId>(1 << bits);
 
121
                                this.shift = 32 - bits;
 
122
                                this.bits = bits;
 
123
                        }
 
124
 
 
125
                        internal virtual bool Contains(AnyObjectId toFind)
 
126
                        {
 
127
                                int i = Index(toFind);
 
128
                                for (int n = 0; n < MAX_CHAIN; n++)
 
129
                                {
 
130
                                        ObjectId obj = ids.Get(i);
 
131
                                        if (obj == null)
 
132
                                        {
 
133
                                                break;
 
134
                                        }
 
135
                                        if (AnyObjectId.Equals(obj, toFind))
 
136
                                        {
 
137
                                                return true;
 
138
                                        }
 
139
                                        if (++i == ids.Length())
 
140
                                        {
 
141
                                                i = 0;
 
142
                                        }
 
143
                                }
 
144
                                return false;
 
145
                        }
 
146
 
 
147
                        internal virtual bool Add(AnyObjectId toAdd)
 
148
                        {
 
149
                                int i = Index(toAdd);
 
150
                                for (int n = 0; n < MAX_CHAIN; )
 
151
                                {
 
152
                                        ObjectId obj = ids.Get(i);
 
153
                                        if (obj == null)
 
154
                                        {
 
155
                                                if (ids.CompareAndSet(i, null, toAdd.Copy()))
 
156
                                                {
 
157
                                                        return true;
 
158
                                                }
 
159
                                                else
 
160
                                                {
 
161
                                                        continue;
 
162
                                                }
 
163
                                        }
 
164
                                        if (AnyObjectId.Equals(obj, toAdd))
 
165
                                        {
 
166
                                                return true;
 
167
                                        }
 
168
                                        if (++i == ids.Length())
 
169
                                        {
 
170
                                                i = 0;
 
171
                                        }
 
172
                                        n++;
 
173
                                }
 
174
                                return false;
 
175
                        }
 
176
 
 
177
                        private int Index(AnyObjectId id)
 
178
                        {
 
179
                                return (int)(((uint)id.GetHashCode()) >> shift);
 
180
                        }
 
181
                }
 
182
        }
 
183
}