mcs/class/corlib/System.Runtime.CompilerServices/ConditionalWeakTable.cs

   1 //
   2 // ConditionalWeakTable.cs
   3 //
   4 // Author:
   5 //   Rodrigo Kumpera (rkumpera@novell.com)
   6 //
   7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
   8 //
   9 // Permission is hereby granted, free of charge, to any person obtaining
  10 // a copy of this software and associated documentation files (the
  11 // "Software"), to deal in the Software without restriction, including
  12 // without limitation the rights to use, copy, modify, merge, publish,
  13 // distribute, sublicense, and/or sell copies of the Software, and to
  14 // permit persons to whom the Software is furnished to do so, subject to
  15 // the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be
  18 // included in all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
  21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
  22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
  23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
  24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
  25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
  26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
  27 //
  28
  29 using System;
  30 using System.Collections;
  31
  32 namespace System.Runtime.CompilerServices
  33 {
  34         internal struct Ephemeron
  35         {
  36                 internal object key;
  37                 internal object value;
  38         }
  39
  40         /*
  41         TODO:
  42                 The runtime need to inform the table about how many entries were expired.
  43                 Compact the table when there are too many tombstones.
  44                 Rehash to a smaller size when there are too few entries.
  45                 Change rehash condition check to use non-fp code.
  46                 Look into using quatratic probing/double hashing to reduce clustering problems.
  47                 Make reads and non-expanding writes (add/remove) lock free.
  48         */
  49         public sealed class ConditionalWeakTable<TKey, TValue>
  50                 where TKey : class
  51                 where TValue : class
  52         {
  53                 const int INITIAL_SIZE = 13;
  54                 const float LOAD_FACTOR = 0.7f;
  55
  56                 Ephemeron[] data;
  57                 object _lock = new object ();
  58                 int size;
  59
  60                 public delegate TValue CreateValueCallback (TKey key);
  61
  62                 public ConditionalWeakTable ()
  63                 {
  64                         data = new Ephemeron [INITIAL_SIZE];
  65                         GC.register_ephemeron_array (data);
  66                 }
  67
  68                 /*LOCKING: _lock must be held*/
  69                 void Rehash () {
  70                         uint newSize = (uint)HashPrimeNumbers.ToPrime ((data.Length << 1) | 1);
  71                         //Console.WriteLine ("--- resizing from {0} to {1}", data.Length, newSize);
  72
  73                         Ephemeron[] tmp = new Ephemeron [newSize];
  74                         GC.register_ephemeron_array (tmp);
  75                         size = 0;
  76
  77                         for (int i = 0; i < data.Length; ++i) {
  78                                 object key = data[i].key;
  79                                 object value = data[i].value;
  80                                 if (key == null || key == GC.EPHEMERON_TOMBSTONE)
  81                                         continue;
  82
  83                                 int len = tmp.Length;
  84                                 int idx, initial_idx;
  85                                 int free_slot = -1;
  86
  87                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
  88
  89                                 do {
  90                                         object k = tmp [idx].key;
  91
  92                                         //keys might be GC'd during Rehash
  93                                         if (k == null || k == GC.EPHEMERON_TOMBSTONE) {
  94                                                 free_slot = idx;
  95                                                 break;
  96                                         }
  97
  98                                         if (++idx == len) //Wrap around
  99                                                 idx = 0;
 100                                 } while (idx != initial_idx);
 101
 102                                 tmp [free_slot].key = key;
 103                                 tmp [free_slot].value = value;
 104                                 ++size;
 105                         }
 106                         data = tmp;
 107                 }
 108
 109
 110                 public void Add (TKey key, TValue value)
 111                 {
 112                         if (key == default (TKey))
 113                                 throw new ArgumentNullException ("Null key", "key");
 114
 115                         lock (_lock) {
 116                                 if (size >= data.Length * LOAD_FACTOR)
 117                                         Rehash ();
 118
 119                                 int len = data.Length;
 120                                 int idx,initial_idx;
 121                                 int free_slot = -1;
 122
 123                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 124                                 do {
 125                                         object k = data [idx].key;
 126
 127                                         if (k == null) {
 128                                                 if (free_slot == -1)
 129                                                         free_slot = idx;
 130                                                 break;
 131                                         } else if (k == GC.EPHEMERON_TOMBSTONE && free_slot == -1) { //Add requires us to check for dupes :(
 132                                                 free_slot = idx;
 133                                         } else if (k == key) {
 134                                                 throw new ArgumentException ("Key already in the list", "key");
 135                                         }
 136
 137                                         if (++idx == len) //Wrap around
 138                                                 idx = 0;
 139                                 } while (idx != initial_idx);
 140
 141                                 data [free_slot].key = key;
 142                                 data [free_slot].value = value;
 143                                 ++size;
 144                         }
 145                 }
 146
 147                 public bool Remove (TKey key)
 148                 {
 149                         if (key == default (TKey))
 150                                 throw new ArgumentNullException ("Null key", "key");
 151
 152                         lock (_lock) {
 153                                 int len = data.Length;
 154                                 int idx, initial_idx;
 155                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 156                                 do {
 157                                         object k = data[idx].key;
 158                                         if (k == key) {
 159                                                 data [idx].key = GC.EPHEMERON_TOMBSTONE;
 160                                                 data [idx].value = null;
 161                                                 --size;
 162                                                 return true;
 163                                         }
 164                                         if (k == null)
 165                                                 break;
 166                                         if (++idx == len) //Wrap around
 167                                                 idx = 0;
 168                                 } while (idx != initial_idx);
 169                         }
 170                         return false;
 171                 }
 172
 173                 public bool TryGetValue (TKey key, out TValue value)
 174                 {
 175                         if (key == null)
 176                                 throw new ArgumentNullException ("Null key", "key");
 177
 178                         value = default (TValue);
 179                         lock (_lock) {
 180                                 int len = data.Length;
 181                                 int idx, initial_idx;
 182                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 183
 184                                 do {
 185                                         object k = data [idx].key;
 186                                         if (k == key) {
 187                                                 value = (TValue)data [idx].value;
 188                                                 return true;
 189                                         }
 190                                         if (k == null)
 191                                                 break;
 192                                         if (++idx == len) //Wrap around
 193                                                 idx = 0;
 194                                 } while (idx != initial_idx);
 195                         }
 196                         return false;
 197                 }
 198
 199                 public TValue GetOrCreateValue (TKey key)
 200                 {
 201                         return GetValue (key, k => Activator.CreateInstance<TValue> ());
 202                 }
 203
 204                 public TValue GetValue (TKey key, CreateValueCallback createValueCallback)
 205                 {
 206                         if (createValueCallback == null)
 207                                 throw new ArgumentNullException ("Null create delegate", "createValueCallback");
 208
 209                         TValue res;
 210
 211                         lock (_lock) {
 212                                 if (TryGetValue (key, out res))
 213                                         return res;
 214
 215                                 res = createValueCallback (key);
 216                                 Add (key, res);
 217                         }
 218
 219                         return res;
 220                 }
 221         }
 222 }