-// -----------------------------------------------------------------------
-// Copyright (c) Microsoft Corporation. All rights reserved.
-// -----------------------------------------------------------------------
//
-// This code comes from the Managed Extension Frameworks:
-// http://mef.codeplex.com
+// ConditionalWeakTable.cs
//
-// And is licensed under the MS-PL license
+// Author:
+// Rodrigo Kumpera (rkumpera@novell.com)
+//
+// Copyright (C) 2010 Novell, Inc (http://www.novell.com)
+//
+// Permission is hereby granted, free of charge, to any person obtaining
+// a copy of this software and associated documentation files (the
+// "Software"), to deal in the Software without restriction, including
+// without limitation the rights to use, copy, modify, merge, publish,
+// distribute, sublicense, and/or sell copies of the Software, and to
+// permit persons to whom the Software is furnished to do so, subject to
+// the following conditions:
+//
+// The above copyright notice and this permission notice shall be
+// included in all copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
+// EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
+// MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
+// NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
+// LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
+// OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
+// WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
//
- // Glenn said on IRC:
- // "I think our table is weak, but does not do proper compacting"
- //
-#if NET_4_0 || BOOTSTRAP_NET_4_0
+#if NET_4_0 || MOONLIGHT || MOBILE
using System;
using System.Collections;
-using System.Collections.Generic;
-using System.Linq;
namespace System.Runtime.CompilerServices
{
+ internal struct Ephemeron
+ {
+ internal object key;
+ internal object value;
+ }
+
+ /*
+ TODO:
+ The runtime need to inform the table about how many entries were expired.
+ Compact the table when there are too many tombstones.
+ Rehash to a smaller size when there are too few entries.
+ Change rehash condition check to use non-fp code.
+ Look into using quatratic probing/double hashing to reduce clustering problems.
+ Make reads and non-expanding writes (add/remove) lock free.
+ */
+ public sealed class ConditionalWeakTable<TKey, TValue>
+ where TKey : class
+ where TValue : class
+ {
+ const int INITIAL_SIZE = 13;
+ const float LOAD_FACTOR = 0.7f;
+
+ Ephemeron[] data;
+ object _lock = new object ();
+ int size;
+
+ public delegate TValue CreateValueCallback (TKey key);
+
+ public ConditionalWeakTable ()
+ {
+ data = new Ephemeron [INITIAL_SIZE];
+ GC.register_ephemeron_array (data);
+ }
+
+ /*LOCKING: _lock must be held*/
+ void Rehash () {
+ uint newSize = (uint)Hashtable.ToPrime ((data.Length << 1) | 1);
+ //Console.WriteLine ("--- resizing from {0} to {1}", data.Length, newSize);
+
+ Ephemeron[] tmp = new Ephemeron [newSize];
+ GC.register_ephemeron_array (tmp);
+ size = 0;
+
+ for (int i = 0; i < data.Length; ++i) {
+ object key = data[i].key;
+ object value = data[i].value;
+ if (key == null || key == GC.EPHEMERON_TOMBSTONE)
+ continue;
+
+ int len = tmp.Length;
+ int idx, initial_idx;
+ int free_slot = -1;
+
+ idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
+
+ do {
+ object k = tmp [idx].key;
- // This is a broken implementation of ConditionalWeakTable that allows us
- // to compile and work on versions of .Net eariler then 4.0. This class is
- // broken when there are circular dependencies between keys and values, which
- // can only be fixed by using some specific CLR 4.0 features.
- // For code samples of the broken behavior see ConditionalWeakTableTests.cs.
- public class ConditionalWeakTable<TKey, TValue>
- where TKey : class
- where TValue : class
- {
- private readonly Dictionary<object, TValue> _table;
- private int _capacity = 4;
-
- public ConditionalWeakTable()
- {
- this._table = new Dictionary<object, TValue>();
- }
-
- public void Add(TKey key, TValue value)
- {
- CleanupDeadReferences();
- this._table.Add(CreateWeakKey(key), value);
- }
-
- public bool Remove(TKey key)
- {
- return this._table.Remove(key);
- }
-
- public bool TryGetValue(TKey key, out TValue value)
- {
- return this._table.TryGetValue(key, out value);
- }
-
- private void CleanupDeadReferences()
- {
- if (this._table.Count < _capacity)
- {
- return;
- }
-
- ArrayList deadKeys = new ArrayList ();
- foreach (var weakRef in _table.Keys){
- if (!((EquivalentWeakReference)weakRef).IsAlive)
- deadKeys.Add (weakRef);
- }
-
- foreach (var deadKey in deadKeys)
- {
- this._table.Remove(deadKey);
- }
-
- if (this._table.Count >= _capacity)
- {
- _capacity *= 2;
- }
- }
-
- private static object CreateWeakKey(TKey key)
- {
- return new EquivalentWeakReference(key);
- }
-
- private class EquivalentWeakReference
- {
- private readonly WeakReference _weakReference;
- private readonly int _hashCode;
-
- public EquivalentWeakReference(object obj)
- {
- this._hashCode = obj.GetHashCode();
- this._weakReference = new WeakReference(obj);
- }
-
- public bool IsAlive
- {
- get
- {
- return this._weakReference.IsAlive;
- }
- }
-
- public override bool Equals(object obj)
- {
- EquivalentWeakReference weakRef = obj as EquivalentWeakReference;
-
- if (weakRef != null)
- {
- obj = weakRef._weakReference.Target;
- }
-
- if (obj == null)
- {
- return base.Equals(weakRef);
- }
-
- return object.Equals(this._weakReference.Target, obj);
- }
-
- public override int GetHashCode()
- {
- return this._hashCode;
- }
- }
- }
+ //keys might be GC'd during Rehash
+ if (k == null || k == GC.EPHEMERON_TOMBSTONE) {
+ free_slot = idx;
+ break;
+ }
+
+ if (++idx == len) //Wrap around
+ idx = 0;
+ } while (idx != initial_idx);
+
+ tmp [free_slot].key = key;
+ tmp [free_slot].value = value;
+ ++size;
+ }
+ data = tmp;
+ }
+
+
+ public void Add (TKey key, TValue value)
+ {
+ if (key == default (TKey))
+ throw new ArgumentNullException ("Null key", "key");
+
+ lock (_lock) {
+ if (size >= data.Length * LOAD_FACTOR)
+ Rehash ();
+
+ int len = data.Length;
+ int idx,initial_idx;
+ int free_slot = -1;
+
+ idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
+ do {
+ object k = data [idx].key;
+
+ if (k == null) {
+ if (free_slot == -1)
+ free_slot = idx;
+ break;
+ } else if (k == GC.EPHEMERON_TOMBSTONE && free_slot == -1) { //Add requires us to check for dupes :(
+ free_slot = idx;
+ } else if (k == key) {
+ throw new ArgumentException ("Key already in the list", "key");
+ }
+
+ if (++idx == len) //Wrap around
+ idx = 0;
+ } while (idx != initial_idx);
+
+ data [free_slot].key = key;
+ data [free_slot].value = value;
+ ++size;
+ }
+ }
+
+ public bool Remove (TKey key)
+ {
+ if (key == default (TKey))
+ throw new ArgumentNullException ("Null key", "key");
+
+ lock (_lock) {
+ int len = data.Length;
+ int idx, initial_idx;
+ idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
+ do {
+ object k = data[idx].key;
+ if (k == key) {
+ data [idx].key = GC.EPHEMERON_TOMBSTONE;
+ data [idx].value = null;
+ --size;
+ return true;
+ }
+ if (k == null)
+ break;
+ if (++idx == len) //Wrap around
+ idx = 0;
+ } while (idx != initial_idx);
+ }
+ return false;
+ }
+
+ public bool TryGetValue (TKey key, out TValue value)
+ {
+ if (key == default (TKey))
+ throw new ArgumentNullException ("Null key", "key");
+
+ value = default (TValue);
+ lock (_lock) {
+ int len = data.Length;
+ int idx, initial_idx;
+ idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
+
+ do {
+ object k = data [idx].key;
+ if (k == key) {
+ value = (TValue)data [idx].value;
+ return true;
+ }
+ if (k == null)
+ break;
+ if (++idx == len) //Wrap around
+ idx = 0;
+ } while (idx != initial_idx);
+ }
+ return false;
+ }
+
+ public TValue GetOrCreateValue (TKey key)
+ {
+ return GetValue (key, k => Activator.CreateInstance<TValue> ());
+ }
+
+ public TValue GetValue (TKey key, CreateValueCallback createValueCallback)
+ {
+ if (key == default (TKey))
+ throw new ArgumentNullException ("Null key", "key");
+ if (createValueCallback == null)
+ throw new ArgumentNullException ("Null create delegate", "createValueCallback");
+
+ TValue res;
+
+ lock (_lock) {
+ if (TryGetValue (key, out res))
+ return res;
+
+ res = createValueCallback (key);
+ Add (key, res);
+ }
+
+ return res;
+ }
+ }
}
#endif
projects / mono.git / blobdiff