← Back to branch summary

~ubuntu-branches/ubuntu/trusty/monodevelop/trusty-proposed

« back to all changes in this revision

Viewing changes to external/ikvm/runtime/PassiveWeakDictionary.cs

  • Committer: Package Import Robot
  • Author(s): Jo Shields
  • Date: 2013-05-12 09:46:03 UTC
  • mto: This revision was merged to the branch mainline in revision 29.
  • Revision ID: package-import@ubuntu.com-20130512094603-mad323bzcxvmcam0
Tags: upstream-4.0.5+dfsg
Import upstream version 4.0.5+dfsg

Show diffs side-by-side

added added

removed removed

Lines of Context:
external/ikvm/runtime/PassiveWeakDictionary.cs
 
1
/*
 
2
  Copyright (C) 2008 Jeroen Frijters
 
3
 
 
4
  This software is provided 'as-is', without any express or implied
 
5
  warranty.  In no event will the authors be held liable for any damages
 
6
  arising from the use of this software.
 
7
 
 
8
  Permission is granted to anyone to use this software for any purpose,
 
9
  including commercial applications, and to alter it and redistribute it
 
10
  freely, subject to the following restrictions:
 
11
 
 
12
  1. The origin of this software must not be misrepresented; you must not
 
13
     claim that you wrote the original software. If you use this software
 
14
     in a product, an acknowledgment in the product documentation would be
 
15
     appreciated but is not required.
 
16
  2. Altered source versions must be plainly marked as such, and must not be
 
17
     misrepresented as being the original software.
 
18
  3. This notice may not be removed or altered from any source distribution.
 
19
 
 
20
  Jeroen Frijters
 
21
  jeroen@frijters.net
 
22
  
 
23
*/
 
24
using System;
 
25
using System.Collections.Generic;
 
26
using System.Runtime.CompilerServices;
 
27
 
 
28
namespace IKVM.Internal
 
29
{
 
30
        /*
 
31
         * This is a special purpose dictionary. It only keeps weak references to the keys,
 
32
         * thereby making them eligable for GC at any time.
 
33
         * 
 
34
         * However, it does not make any promises about cleaning up the values (hence "passive").
 
35
         * This class should only be used if memory consumption and lifetime of the values is of no consequence.
 
36
         * 
 
37
         * Furthermore, the type also assumes that it needs to continue to work during AppDomain unload,
 
38
         * meaning that it uses GC.SuppressFinalize() on the WeakReference objects it uses to prevent
 
39
         * them from being finalized during AppDomain unload.
 
40
         * As a consequence, if you want to dispose on object of this type prior to AppDomain unload, you *must*
 
41
         * call Dispose() or you will leak GC handles. After calling Dispose() you should not call any other
 
42
         * methods.
 
43
         * 
 
44
         * This class is thread safe and TryGetValue is lock free.
 
45
         * 
 
46
         */
 
47
        sealed class PassiveWeakDictionary<TKey, TValue>
 
48
                where TKey : class
 
49
                where TValue : class
 
50
        {
 
51
                private volatile Bucket[] table = new Bucket[37];
 
52
                private int count;
 
53
                private FreeNode freeList;
 
54
                private int freeCount;
 
55
 
 
56
                internal void Dispose()
 
57
                {
 
58
                        Bucket[] table = this.table;
 
59
                        for (int i = 0; i < table.Length; i++)
 
60
                        {
 
61
                                for (Bucket b = table[i]; b != null; b = b.Next)
 
62
                                {
 
63
                                        GC.ReRegisterForFinalize(b.WeakRef);
 
64
                                }
 
65
                        }
 
66
                        for (FreeNode b = freeList; b != null; b = b.Next)
 
67
                        {
 
68
                                GC.ReRegisterForFinalize(b.WeakRef);
 
69
                        }
 
70
                }
 
71
 
 
72
                internal void Add(TKey key, TValue value)
 
73
                {
 
74
                        if (key == null)
 
75
                                throw new ArgumentNullException("key");
 
76
 
 
77
                        lock (this)
 
78
                        {
 
79
                                if (count > table.Length)
 
80
                                {
 
81
                                        Rehash();
 
82
                                }
 
83
                                int index = GetHashCode(key) % table.Length;
 
84
                                for (Bucket b = table[index]; b != null; b = b.Next)
 
85
                                {
 
86
                                        if (b.Key == key)
 
87
                                        {
 
88
                                                throw new ArgumentException("Key already exists");
 
89
                                        }
 
90
                                }
 
91
                                table[index] = new Bucket(AllocWeakRef(key), value, table[index]);
 
92
                                count++;
 
93
                        }
 
94
                }
 
95
 
 
96
                private WeakReference AllocWeakRef(TKey key)
 
97
                {
 
98
                        WeakReference weakRef;
 
99
                        if (freeList != null)
 
100
                        {
 
101
                                weakRef = freeList.WeakRef;
 
102
                                freeList = freeList.Next;
 
103
                                freeCount--;
 
104
                                weakRef.Target = key;
 
105
                        }
 
106
                        else
 
107
                        {
 
108
                                weakRef = new WeakReference(key, true);
 
109
                                GC.SuppressFinalize(weakRef);
 
110
                        }
 
111
                        return weakRef;
 
112
                }
 
113
 
 
114
                private static readonly int[] primes = {
 
115
                        37, 67, 131, 257, 521, 1031, 2053, 4099, 8209, 16411, 32771, 65537, 131101, 262147, 524309, 1048583, 2097169,
 
116
                        4194319, 8388617, 16777259, 33554467, 67108879, 134217757, 268435459, 536870923, 1073741827, 2147483647 };
 
117
 
 
118
                private static int GetPrime(int count)
 
119
                {
 
120
                        foreach (int p in primes)
 
121
                        {
 
122
                                if (p > count)
 
123
                                        return p;
 
124
                        }
 
125
                        return count;
 
126
                }
 
127
 
 
128
                private static int GetHashCode(TKey key)
 
129
                {
 
130
                        return RuntimeHelpers.GetHashCode(key) & 0x7FFFFFFF;
 
131
                }
 
132
 
 
133
                private void Rehash()
 
134
                {
 
135
                        count = 0;
 
136
                        for (int i = 0; i < table.Length; i++)
 
137
                        {
 
138
                                for (Bucket b = table[i]; b != null; b = b.Next)
 
139
                                {
 
140
                                        if (b.Key != null)
 
141
                                        {
 
142
                                                count++;
 
143
                                        }
 
144
                                }
 
145
                        }
 
146
                        Bucket[] newTable = new Bucket[GetPrime(count * 2)];
 
147
                        for (int i = 0; i < table.Length; i++)
 
148
                        {
 
149
                                for (Bucket b = table[i]; b != null; b = b.Next)
 
150
                                {
 
151
                                        TKey key = b.Key;
 
152
                                        if (key != null)
 
153
                                        {
 
154
                                                int index = GetHashCode(key) % newTable.Length;
 
155
                                                WeakReference weakRef = AllocWeakRef(key);
 
156
                                                newTable[index] = new Bucket(weakRef, b.Value, newTable[index]);
 
157
                                        }
 
158
                                        else
 
159
                                        {
 
160
                                                // don't cache an infinite amount,
 
161
                                                // busy loop garbage allocation benchmarking shows that 8K is enough with current gen0 size
 
162
                                                if (freeCount < 8192)
 
163
                                                {
 
164
                                                        WeakReference weakRef = b.WeakRef;
 
165
                                                        b.Clear();
 
166
                                                        freeList = new FreeNode(weakRef, freeList);
 
167
                                                        freeCount++;
 
168
                                                }
 
169
                                                else
 
170
                                                {
 
171
                                                        GC.ReRegisterForFinalize(b.WeakRef);
 
172
                                                        b.Clear();
 
173
                                                }
 
174
                                        }
 
175
                                }
 
176
                        }
 
177
                        this.table = newTable;
 
178
                }
 
179
 
 
180
                internal bool TryGetValue(TKey key, out TValue value)
 
181
                {
 
182
                        if (key == null)
 
183
                                throw new ArgumentNullException("key");
 
184
 
 
185
                        Bucket[] table = this.table;
 
186
                        int index = GetHashCode(key) % table.Length;
 
187
                        for (Bucket b = table[index]; b != null; b = b.Next)
 
188
                        {
 
189
                                if (b.Key == key)
 
190
                                {
 
191
                                        value = b.Value;
 
192
                                        return true;
 
193
                                }
 
194
                        }
 
195
                        value = null;
 
196
                        return false;
 
197
                }
 
198
 
 
199
                private sealed class Bucket
 
200
                {
 
201
                        private volatile WeakReference weakRef;
 
202
                        internal TValue Value;
 
203
                        internal readonly Bucket Next;
 
204
 
 
205
                        internal Bucket(WeakReference weakRef, TValue value, Bucket next)
 
206
                        {
 
207
                                this.weakRef = weakRef;
 
208
                                this.Value = value;
 
209
                                this.Next = next;
 
210
                        }
 
211
 
 
212
                        internal WeakReference WeakRef
 
213
                        {
 
214
                                get
 
215
                                {
 
216
                                        return weakRef;
 
217
                                }
 
218
                        }
 
219
 
 
220
                        internal TKey Key
 
221
                        {
 
222
                                get
 
223
                                {
 
224
                                        WeakReference weakRef = this.weakRef;
 
225
                                        if (weakRef != null)
 
226
                                        {
 
227
                                                TKey key = (TKey)weakRef.Target;
 
228
                                                // this extra null check is to guard against the case where there was a GC and a Rehash and the weak ref was reused for another slot
 
229
                                                // between the initial read of weakRef and accessing its Target property
 
230
                                                if (this.weakRef != null)
 
231
                                                {
 
232
                                                        return key;
 
233
                                                }
 
234
                                        }
 
235
                                        return null;
 
236
                                }
 
237
                        }
 
238
 
 
239
                        internal void Clear()
 
240
                        {
 
241
                                weakRef = null;
 
242
                        }
 
243
                }
 
244
 
 
245
                private sealed class FreeNode
 
246
                {
 
247
                        internal readonly WeakReference WeakRef;
 
248
                        internal readonly FreeNode Next;
 
249
 
 
250
                        internal FreeNode(WeakReference weakRef, FreeNode next)
 
251
                        {
 
252
                                this.WeakRef = weakRef;
 
253
                                this.Next = next;
 
254
                        }
 
255
                }
 
256
        }
 
257
}