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 using System.Collections.Generic;
  32
  33 namespace System.Runtime.CompilerServices
  34 {
  35         internal struct Ephemeron
  36         {
  37                 internal object key;
  38                 internal object value;
  39         }
  40
  41         /*
  42         TODO:
  43                 The runtime need to inform the table about how many entries were expired.
  44                 Compact the table when there are too many tombstones.
  45                 Rehash to a smaller size when there are too few entries.
  46                 Change rehash condition check to use non-fp code.
  47                 Look into using quatratic probing/double hashing to reduce clustering problems.
  48                 Make reads and non-expanding writes (add/remove) lock free.
  49         */
  50         public sealed class ConditionalWeakTable<TKey, TValue>
  51                 where TKey : class
  52                 where TValue : class
  53         {
  54                 const int INITIAL_SIZE = 13;
  55                 const float LOAD_FACTOR = 0.7f;
  56
  57                 Ephemeron[] data;
  58                 object _lock = new object ();
  59                 int size;
  60
  61                 public delegate TValue CreateValueCallback (TKey key);
  62
  63                 public ConditionalWeakTable ()
  64                 {
  65                         data = new Ephemeron [INITIAL_SIZE];
  66                         GC.register_ephemeron_array (data);
  67                 }
  68
  69                 /*LOCKING: _lock must be held*/
  70                 void Rehash () {
  71                         uint newSize = (uint)HashHelpers.GetPrime ((data.Length << 1) | 1);
  72                         //Console.WriteLine ("--- resizing from {0} to {1}", data.Length, newSize);
  73
  74                         Ephemeron[] tmp = new Ephemeron [newSize];
  75                         GC.register_ephemeron_array (tmp);
  76                         size = 0;
  77
  78                         for (int i = 0; i < data.Length; ++i) {
  79                                 object key = data[i].key;
  80                                 object value = data[i].value;
  81                                 if (key == null || key == GC.EPHEMERON_TOMBSTONE)
  82                                         continue;
  83
  84                                 int len = tmp.Length;
  85                                 int idx, initial_idx;
  86                                 int free_slot = -1;
  87
  88                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
  89
  90                                 do {
  91                                         object k = tmp [idx].key;
  92
  93                                         //keys might be GC'd during Rehash
  94                                         if (k == null || k == GC.EPHEMERON_TOMBSTONE) {
  95                                                 free_slot = idx;
  96                                                 break;
  97                                         }
  98
  99                                         if (++idx == len) //Wrap around
 100                                                 idx = 0;
 101                                 } while (idx != initial_idx);
 102
 103                                 tmp [free_slot].key = key;
 104                                 tmp [free_slot].value = value;
 105                                 ++size;
 106                         }
 107                         data = tmp;
 108                 }
 109
 110
 111                 public void Add (TKey key, TValue value)
 112                 {
 113                         if (key == default (TKey))
 114                                 throw new ArgumentNullException ("Null key", "key");
 115
 116                         lock (_lock) {
 117                                 if (size >= data.Length * LOAD_FACTOR)
 118                                         Rehash ();
 119
 120                                 int len = data.Length;
 121                                 int idx,initial_idx;
 122                                 int free_slot = -1;
 123
 124                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 125                                 do {
 126                                         object k = data [idx].key;
 127
 128                                         if (k == null) {
 129                                                 if (free_slot == -1)
 130                                                         free_slot = idx;
 131                                                 break;
 132                                         } else if (k == GC.EPHEMERON_TOMBSTONE && free_slot == -1) { //Add requires us to check for dupes :(
 133                                                 free_slot = idx;
 134                                         } else if (k == key) {
 135                                                 throw new ArgumentException ("Key already in the list", "key");
 136                                         }
 137
 138                                         if (++idx == len) //Wrap around
 139                                                 idx = 0;
 140                                 } while (idx != initial_idx);
 141
 142                                 data [free_slot].key = key;
 143                                 data [free_slot].value = value;
 144                                 ++size;
 145                         }
 146                 }
 147
 148                 public bool Remove (TKey key)
 149                 {
 150                         if (key == default (TKey))
 151                                 throw new ArgumentNullException ("Null key", "key");
 152
 153                         lock (_lock) {
 154                                 int len = data.Length;
 155                                 int idx, initial_idx;
 156                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 157                                 do {
 158                                         object k = data[idx].key;
 159                                         if (k == key) {
 160                                                 data [idx].key = GC.EPHEMERON_TOMBSTONE;
 161                                                 data [idx].value = null;
 162                                                 --size;
 163                                                 return true;
 164                                         }
 165                                         if (k == null)
 166                                                 break;
 167                                         if (++idx == len) //Wrap around
 168                                                 idx = 0;
 169                                 } while (idx != initial_idx);
 170                         }
 171                         return false;
 172                 }
 173
 174                 public bool TryGetValue (TKey key, out TValue value)
 175                 {
 176                         if (key == null)
 177                                 throw new ArgumentNullException ("Null key", "key");
 178
 179                         value = default (TValue);
 180                         lock (_lock) {
 181                                 int len = data.Length;
 182                                 int idx, initial_idx;
 183                                 idx = initial_idx = (RuntimeHelpers.GetHashCode (key) & int.MaxValue) % len;
 184
 185                                 do {
 186                                         object k = data [idx].key;
 187                                         if (k == key) {
 188                                                 value = (TValue)data [idx].value;
 189                                                 return true;
 190                                         }
 191                                         if (k == null)
 192                                                 break;
 193                                         if (++idx == len) //Wrap around
 194                                                 idx = 0;
 195                                 } while (idx != initial_idx);
 196                         }
 197                         return false;
 198                 }
 199
 200                 public TValue GetOrCreateValue (TKey key)
 201                 {
 202                         return GetValue (key, k => Activator.CreateInstance<TValue> ());
 203                 }
 204
 205                 public TValue GetValue (TKey key, CreateValueCallback createValueCallback)
 206                 {
 207                         if (createValueCallback == null)
 208                                 throw new ArgumentNullException ("Null create delegate", "createValueCallback");
 209
 210                         TValue res;
 211
 212                         lock (_lock) {
 213                                 if (TryGetValue (key, out res))
 214                                         return res;
 215
 216                                 res = createValueCallback (key);
 217                                 Add (key, res);
 218                         }
 219
 220                         return res;
 221                 }
 222
 223                 // extracted from ../../../../external/referencesource/mscorlib/system/runtime/compilerservices/
 224                 internal ICollection<TKey> Keys
 225                 {
 226                         [System.Security.SecuritySafeCritical]
 227                         get
 228                         {
 229                                 List<TKey> list = new List<TKey>(data.Length);
 230                                 lock (_lock)
 231                                 {
 232                                         for (int i = 0; i < data.Length; ++i)
 233                                         {
 234                                                 list.Add ((TKey) data [i].key);
 235                                         }
 236                                 }
 237                                 return list;
 238                         }
 239                 }
 240         }
 241 }