mcs/class/corlib/System.Threading.Collections/ConcurrentDictionary.cs

   1 #if NET_4_0
   2 // ConcurrentSkipList.cs
   3 //
   4 // Copyright (c) 2009 Jérémie "Garuma" Laval
   5 //
   6 // Permission is hereby granted, free of charge, to any person obtaining a copy
   7 // of this software and associated documentation files (the "Software"), to deal
   8 // in the Software without restriction, including without limitation the rights
   9 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  10 // copies of the Software, and to permit persons to whom the Software is
  11 // furnished to do so, subject to the following conditions:
  12 //
  13 // The above copyright notice and this permission notice shall be included in
  14 // all copies or substantial portions of the Software.
  15 //
  16 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  17 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  18 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  19 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  20 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  21 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  22 // THE SOFTWARE.
  23 //
  24 //
  25
  26 using System;
  27 using System.Threading;
  28 using System.Collections;
  29 using System.Collections.Generic;
  30
  31 namespace System.Threading.Collections
  32 {
  33         public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>
  34         {
  35                 class Pair
  36                 {
  37                         public readonly TKey Key;
  38                         public TValue Value;
  39
  40                         public Pair(TKey key, TValue value)
  41                         {
  42                                 Key = key;
  43                                 Value = value;
  44                         }
  45
  46                         public override bool Equals (object obj)
  47                         {
  48                                 Pair rhs = obj as Pair;
  49                                 return rhs == null ? false : Key.Equals(rhs.Key) && Value.Equals(rhs.Value);
  50                         }
  51
  52                         public override int GetHashCode ()
  53                         {
  54                                 return Key.GetHashCode();
  55                         }
  56                 }
  57
  58                 class Basket: List<Pair>
  59                 {
  60                 }
  61
  62                 // Assumption: a List<T> is never empty
  63                 ConcurrentSkipList<Basket> container
  64                         = new ConcurrentSkipList<Basket>((value) => value[0].GetHashCode());
  65                 int count;
  66                 int stamp = int.MinValue;
  67
  68                 public ConcurrentDictionary()
  69                 {
  70                 }
  71
  72                 public void Add(TKey key, TValue value)
  73                 {
  74                         Basket basket;
  75                         // Add a value to an existing basket
  76                         if (TryGetBasket(key, out basket)) {
  77                                 // Find a maybe more sexy locking scheme later
  78                                 lock (basket) {
  79                                         foreach (var p in basket) {
  80                                                 if (p.Key.Equals(key))
  81                                                         throw new ArgumentException("An element with the same key already exists");
  82                                         }
  83                                         basket.Add(new Pair(key, value));
  84                                 }
  85                         } else {
  86                                 // Add a new basket
  87                                 basket = new Basket();
  88                                 basket.Add(new Pair(key, value));
  89                                 container.Add(basket);
  90                         }
  91                         Interlocked.Increment(ref count);
  92                         Interlocked.Increment(ref stamp);
  93                 }
  94
  95                 void ICollection<KeyValuePair<TKey,TValue>>.Add(KeyValuePair<TKey, TValue> pair)
  96                 {
  97                         Add(pair.Key, pair.Value);
  98                 }
  99
 100                 public TValue GetValue(TKey key)
 101                 {
 102                         TValue temp;
 103                         if (!TryGetValue(key, out temp))
 104                                 // TODO: find a correct Exception
 105                                 throw new ArgumentOutOfRangeException("key");
 106                         return temp;
 107                 }
 108
 109                 public bool TryGetValue(TKey key, out TValue value)
 110                 {
 111                         Basket basket;
 112                         value = default(TValue);
 113
 114                         if (!TryGetBasket(key, out basket))
 115                                 return false;
 116
 117                         lock (basket) {
 118                                 Pair pair = basket.Find((p) => p.Key.Equals(key));
 119                                 if (pair == null)
 120                                         return false;
 121                                 value = pair.Value;
 122                         }
 123
 124                         return true;
 125                 }
 126
 127                 public TValue this[TKey key] {
 128                         get {
 129                                 return GetValue(key);
 130                         }
 131                         set {
 132                                 Basket basket;
 133                                 if (!TryGetBasket(key, out basket)) {
 134                                         Add(key, value);
 135                                         return;
 136                                 }
 137                                 lock (basket) {
 138                                         Pair pair = basket.Find((p) => p.Key.Equals(key));
 139                                         if (pair == null)
 140                                                 throw new InvalidOperationException("pair is null, shouldn't be");
 141                                         pair.Value = value;
 142                                         Interlocked.Increment(ref stamp);
 143                                 }
 144                         }
 145                 }
 146
 147                 public bool Remove(TKey key)
 148                 {
 149                         Basket b;
 150                         if (!TryGetBasket(key, out b))
 151                                 return false;
 152
 153                         lock (b) {
 154                                 // Should always be == 1 but who know
 155                                 return b.RemoveAll((p) => p.Key.Equals(key)) >= 1;
 156                         }
 157                 }
 158
 159                 bool ICollection<KeyValuePair<TKey,TValue>>.Remove(KeyValuePair<TKey,TValue> pair)
 160                 {
 161                         return Remove(pair.Key);
 162                 }
 163
 164                 public bool ContainsKey(TKey key)
 165                 {
 166                         return container.ContainsFromHash(key.GetHashCode());
 167                 }
 168
 169                 bool ICollection<KeyValuePair<TKey,TValue>>.Contains(KeyValuePair<TKey, TValue> pair)
 170                 {
 171                         return ContainsKey(pair.Key);
 172                 }
 173
 174                 public void Clear()
 175                 {
 176                         // Pronk
 177                         container = new ConcurrentSkipList<Basket>((value) => value[0].GetHashCode());
 178                 }
 179
 180                 public int Count {
 181                         get {
 182                                 return count;
 183                         }
 184                 }
 185
 186                 public bool IsReadOnly {
 187                         get {
 188                                 return false;
 189                         }
 190                 }
 191
 192                 public ICollection<TKey> Keys {
 193                         get {
 194                                 return null;
 195                         }
 196                 }
 197
 198                 public ICollection<TValue> Values {
 199                         get {
 200                                 return null;
 201                         }
 202                 }
 203
 204                 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
 205                 {
 206                         return GetEnumeratorInternal();
 207                 }
 208
 209                 IEnumerator IEnumerable.GetEnumerator()
 210                 {
 211                         return (IEnumerator)GetEnumeratorInternal();
 212                 }
 213
 214                 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumeratorInternal()
 215                 {
 216                         foreach (Basket b in container) {
 217                                 lock (b) {
 218                                         foreach (Pair p in b)
 219                                                 yield return new KeyValuePair<TKey, TValue>(p.Key, p.Value);
 220                                 }
 221                         }
 222                 }
 223
 224                 public void CopyTo(KeyValuePair<TKey,TValue>[] array, int startIndex)
 225                 {
 226
 227                 }
 228
 229                 /*void UpdateKeysValuesColl()
 230                 {
 231                         foreach (Pair p in this) {
 232                                 // Read from time to time to see if we became useless
 233                                 if (currStamp != tempStamp)
 234                                         break;
 235                                 keys.Add(p.Key);
 236                                 values.Add(p.Value);
 237                         }
 238                 }*/
 239
 240                 bool TryGetBasket(TKey key, out Basket basket)
 241                 {
 242                         basket = null;
 243                         if (!container.GetFromHash(key.GetHashCode(), out basket))
 244                                 return false;
 245
 246                         return true;
 247                 }
 248         }
 249 }
 250 #endif