?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
2010-03-24 Jérémie Laval <jeremie.laval@gmail.com>
[mcs.git] / class / corlib / System.Collections.Concurrent / ConcurrentDictionary.cs
blobede3b3b0d026c8110441fedcc69399c64e4f537f
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 using System.Runtime.Serialization;
31
32 namespace System.Collections.Concurrent
33 {
34 public class ConcurrentDictionary<TKey, TValue> : IDictionary<TKey, TValue>,
35 ICollection<KeyValuePair<TKey, TValue>>, IEnumerable<KeyValuePair<TKey, TValue>>,
36 IDictionary, ICollection, IEnumerable
37 {
38 class Pair
39 {
40 public readonly TKey Key;
41 public TValue Value;
42
43 public Pair (TKey key, TValue value)
44 {
45 Key = key;
46 Value = value;
47 }
48
49 public override bool Equals (object obj)
50 {
51 Pair rhs = obj as Pair;
52 return rhs == null ? false : Key.Equals (rhs.Key) && Value.Equals (rhs.Value);
53 }
54
55 public override int GetHashCode ()
56 {
57 return Key.GetHashCode ();
58 }
59 }
60
61 class Basket: List<Pair>
62 {
63 public SpinLock Lock = new SpinLock ();
64 }
65
66 // Assumption: a List<T> is never empty
67 ConcurrentSkipList<Basket> container
68 = new ConcurrentSkipList<Basket> ((value) => value[0].GetHashCode ());
69 int count;
70 IEqualityComparer<TKey> comparer;
71
72 public ConcurrentDictionary () : this (EqualityComparer<TKey>.Default)
73 {
74 }
75
76 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> values)
77 : this (values, EqualityComparer<TKey>.Default)
78 {
79 foreach (KeyValuePair<TKey, TValue> pair in values)
80 Add (pair.Key, pair.Value);
81 }
82
83 public ConcurrentDictionary (IEqualityComparer<TKey> comparer)
84 {
85 this.comparer = comparer;
86 }
87
88 public ConcurrentDictionary (IEnumerable<KeyValuePair<TKey, TValue>> values, IEqualityComparer<TKey> comparer)
89 : this (comparer)
90 {
91 foreach (KeyValuePair<TKey, TValue> pair in values)
92 Add (pair.Key, pair.Value);
93 }
94
95 // Parameters unused
96 public ConcurrentDictionary (int concurrencyLevel, int capacity)
97 : this (EqualityComparer<TKey>.Default)
98 {
99
100 }
101
102 public ConcurrentDictionary (int concurrencyLevel,
103 IEnumerable<KeyValuePair<TKey, TValue>> values,
104 IEqualityComparer<TKey> comparer)
105 : this (values, comparer)
106 {
107
108 }
109
110 // Parameters unused
111 public ConcurrentDictionary (int concurrencyLevel, int capacity, IEqualityComparer<TKey> comparer)
112 : this (comparer)
113 {
114
115 }
116
117 void Add (TKey key, TValue value)
118 {
119 while (!TryAdd (key, value));
120 }
121
122 void IDictionary<TKey, TValue>.Add (TKey key, TValue value)
123 {
124 Add (key, value);
125 }
126
127 public bool TryAdd (TKey key, TValue value)
128 {
129 Basket basket;
130 bool taken = false;
131
132 // Add a value to an existing basket
133 if (TryGetBasket (key, out basket)) {
134 while (!taken) {
135 try {
136 basket.Lock.Enter (ref taken);
137 if (!taken)
138 continue;
139
140 foreach (var p in basket) {
141 if (comparer.Equals (p.Key, key))
142 return false;
143 }
144 basket.Add (new Pair (key, value));
145 } finally {
146 if (taken)
147 basket.Lock.Exit ();
148 }
149 }
150 } else {
151 // Add a new basket
152 basket = new Basket ();
153 basket.Add (new Pair (key, value));
154
155 if (container.TryAdd (basket)) {
156 Interlocked.Increment (ref count);
157 return true;
158 } else {
159 return false;
160 }
161 }
162
163 Interlocked.Increment (ref count);
164
165 return true;
166 }
167
168 void ICollection<KeyValuePair<TKey,TValue>>.Add (KeyValuePair<TKey, TValue> pair)
169 {
170 Add (pair.Key, pair.Value);
171 }
172
173 public TValue AddOrUpdate (TKey key, Func<TKey, TValue> addValueFactory, Func<TKey, TValue, TValue> updateValueFactory)
174 {
175 Basket basket;
176 TValue temp = default (TValue);
177 bool taken = false;
178
179 if (!TryGetBasket (key, out basket)) {
180 Add (key, (temp = addValueFactory (key)));
181 } else {
182 while (!taken) {
183 try {
184 basket.Lock.Enter (ref taken);
185 if (!taken)
186 continue;
187
188 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
189 if (pair == null)
190 throw new InvalidOperationException ("pair is null, shouldn't be");
191 pair.Value = (temp = updateValueFactory (key, pair.Value));
192 } finally {
193 if (taken)
194 basket.Lock.Exit ();
195 }
196 }
197 }
198
199 return temp;
200 }
201
202 public TValue AddOrUpdate (TKey key, TValue addValue, Func<TKey, TValue, TValue> updateValueFactory)
203 {
204 return AddOrUpdate (key, (_) => addValue, updateValueFactory);
205 }
206
207 TValue GetValue (TKey key)
208 {
209 TValue temp;
210 if (!TryGetValue (key, out temp))
211 // TODO: find a correct Exception
212 throw new ArgumentException ("Not a valid key for this dictionary", "key");
213 return temp;
214 }
215
216 public bool TryGetValue (TKey key, out TValue value)
217 {
218 Basket basket;
219 value = default (TValue);
220 bool taken = false;
221
222 if (!TryGetBasket (key, out basket))
223 return false;
224
225 while (!taken) {
226 try {
227 basket.Lock.Enter (ref taken);
228 if (!taken)
229 continue;
230
231 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
232 if (pair == null)
233 return false;
234 value = pair.Value;
235 } finally {
236 if (taken)
237 basket.Lock.Exit ();
238 }
239 }
240
241 return true;
242 }
243
244 public bool TryUpdate (TKey key, TValue newValue, TValue comparand)
245 {
246 Basket basket;
247 bool taken = false;
248
249 if (!TryGetBasket (key, out basket))
250 return false;
251
252 while (!taken) {
253 try {
254 basket.Lock.Enter (ref taken);
255 if (!taken)
256 continue;
257
258 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
259 if (pair.Value.Equals (comparand)) {
260 pair.Value = newValue;
261
262 return true;
263 }
264 } finally {
265 if (taken)
266 basket.Lock.Exit ();
267 }
268 }
269
270 return false;
271 }
272
273 public TValue this[TKey key] {
274 get {
275 return GetValue (key);
276 }
277 set {
278 Basket basket;
279 bool taken = false;
280
281 if (!TryGetBasket (key, out basket)) {
282 Add (key, value);
283 return;
284 }
285
286 while (!taken) {
287 try {
288 basket.Lock.Enter (ref taken);
289 if (!taken)
290 continue;
291
292 Pair pair = basket.Find ((p) => comparer.Equals (p.Key, key));
293 if (pair == null)
294 throw new InvalidOperationException ("pair is null, shouldn't be");
295 pair.Value = value;
296 } finally {
297 if (taken)
298 basket.Lock.Exit ();
299 }
300 }
301 }
302 }
303
304 public TValue GetOrAdd (TKey key, Func<TKey, TValue> valueFactory)
305 {
306 Basket basket;
307 TValue temp = default (TValue);
308
309 if (TryGetBasket (key, out basket)) {
310 Pair pair = null;
311 bool taken = false;
312
313 while (!taken) {
314 try {
315 basket.Lock.Enter (ref taken);
316 if (!taken)
317 continue;
318 pair = basket.Find ((p) => comparer.Equals (p.Key, key));
319 if (pair != null)
320 temp = pair.Value;
321 } finally {
322 if (taken)
323 basket.Lock.Exit ();
324 }
325 }
326
327 if (pair == null)
328 Add (key, (temp = valueFactory (key)));
329 } else {
330 Add (key, (temp = valueFactory (key)));
331 }
332
333 return temp;
334 }
335
336 public TValue GetOrAdd (TKey key, TValue value)
337 {
338 return GetOrAdd (key, (_) => value);
339 }
340
341 public bool TryRemove(TKey key, out TValue value)
342 {
343 value = default (TValue);
344 Basket b;
345 bool taken = false;
346
347 if (!TryGetBasket (key, out b))
348 return false;
349
350 while (!taken) {
351 try {
352 b.Lock.Enter (ref taken);
353 if (!taken)
354 continue;
355
356 TValue temp = default (TValue);
357 // Should always be == 1 but who know
358 bool result = b.RemoveAll ((p) => {
359 bool r = comparer.Equals (p.Key, key);
360 if (r) temp = p.Value;
361 return r;
362 }) >= 1;
363 value = temp;
364
365 if (result)
366 Interlocked.Decrement (ref count);
367
368 return result;
369 } finally {
370 if (taken)
371 b.Lock.Exit ();
372 }
373 }
374
375 return false;
376 }
377
378 bool Remove (TKey key)
379 {
380 TValue dummy;
381
382 return TryRemove (key, out dummy);
383 }
384
385 bool IDictionary<TKey, TValue>.Remove (TKey key)
386 {
387 return Remove (key);
388 }
389
390 bool ICollection<KeyValuePair<TKey,TValue>>.Remove (KeyValuePair<TKey,TValue> pair)
391 {
392 return Remove (pair.Key);
393 }
394
395 public bool ContainsKey (TKey key)
396 {
397 return container.ContainsFromHash (key.GetHashCode ());
398 }
399
400 bool IDictionary.Contains (object key)
401 {
402 if (!(key is TKey))
403 return false;
404
405 return ContainsKey ((TKey)key);
406 }
407
408 void IDictionary.Remove (object key)
409 {
410 if (!(key is TKey))
411 return;
412
413 Remove ((TKey)key);
414 }
415
416 object IDictionary.this [object key]
417 {
418 get {
419 if (!(key is TKey))
420 throw new ArgumentException ("key isn't of correct type", "key");
421
422 return this[(TKey)key];
423 }
424 set {
425 if (!(key is TKey) || !(value is TValue))
426 throw new ArgumentException ("key or value aren't of correct type");
427
428 this[(TKey)key] = (TValue)value;
429 }
430 }
431
432 void IDictionary.Add (object key, object value)
433 {
434 if (!(key is TKey) || !(value is TValue))
435 throw new ArgumentException ("key or value aren't of correct type");
436
437 Add ((TKey)key, (TValue)value);
438 }
439
440 bool ICollection<KeyValuePair<TKey,TValue>>.Contains (KeyValuePair<TKey, TValue> pair)
441 {
442 return ContainsKey (pair.Key);
443 }
444
445 public KeyValuePair<TKey,TValue>[] ToArray ()
446 {
447 // This is most certainly not optimum but there is
448 // not a lot of possibilities
449
450 return new List<KeyValuePair<TKey,TValue>> (this).ToArray ();
451 }
452
453 public void Clear()
454 {
455 // Pronk
456 container = new ConcurrentSkipList<Basket> ((value) => value [0].GetHashCode ());
457 }
458
459 public int Count {
460 get {
461 return count;
462 }
463 }
464
465 public bool IsEmpty {
466 get {
467 return count == 0;
468 }
469 }
470
471 bool ICollection<KeyValuePair<TKey, TValue>>.IsReadOnly {
472 get {
473 return false;
474 }
475 }
476
477 bool IDictionary.IsReadOnly {
478 get {
479 return false;
480 }
481 }
482
483 public ICollection<TKey> Keys {
484 get {
485 return GetPart<TKey> ((kvp) => kvp.Key);
486 }
487 }
488
489 public ICollection<TValue> Values {
490 get {
491 return GetPart<TValue> ((kvp) => kvp.Value);
492 }
493 }
494
495 ICollection IDictionary.Keys {
496 get {
497 return (ICollection)Keys;
498 }
499 }
500
501 ICollection IDictionary.Values {
502 get {
503 return (ICollection)Values;
504 }
505 }
506
507 ICollection<T> GetPart<T> (Func<KeyValuePair<TKey, TValue>, T> extractor)
508 {
509 List<T> temp = new List<T> ();
510
511 foreach (KeyValuePair<TKey, TValue> kvp in this)
512 temp.Add (extractor (kvp));
513
514 return temp.AsReadOnly ();
515 }
516
517 void ICollection.CopyTo (Array array, int startIndex)
518 {
519 KeyValuePair<TKey, TValue>[] arr = array as KeyValuePair<TKey, TValue>[];
520 if (arr == null)
521 return;
522
523 CopyTo (arr, startIndex, count);
524 }
525
526 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
527 {
528 CopyTo (array, startIndex, count);
529 }
530
531 void ICollection<KeyValuePair<TKey, TValue>>.CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex)
532 {
533 CopyTo (array, startIndex);
534 }
535
536 void CopyTo (KeyValuePair<TKey, TValue>[] array, int startIndex, int num)
537 {
538 // TODO: This is quite unsafe as the count value will likely change during
539 // the copying. Watchout for IndexOutOfRange thingies
540 if (array.Length <= count + startIndex)
541 throw new InvalidOperationException ("The array isn't big enough");
542
543 int i = startIndex;
544
545 foreach (Basket b in container) {
546 bool taken = false;
547
548 while (!taken) {
549 try {
550 b.Lock.Enter (ref taken);
551 if (!taken)
552 continue;
553
554 foreach (Pair p in b) {
555 if (i >= num)
556 break;
557 array[i++] = new KeyValuePair<TKey, TValue> (p.Key, p.Value);
558 }
559 } finally {
560 if (taken)
561 b.Lock.Exit ();
562 }
563 }
564 }
565 }
566
567 public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator ()
568 {
569 return GetEnumeratorInternal ();
570 }
571
572 IEnumerator IEnumerable.GetEnumerator ()
573 {
574 return (IEnumerator)GetEnumeratorInternal ();
575 }
576
577 IEnumerator<KeyValuePair<TKey, TValue>> GetEnumeratorInternal ()
578 {
579 foreach (Basket b in container) {
580 bool taken = false;
581
582 while (!taken) {
583 try {
584 b.Lock.Enter (ref taken);
585 if (!taken)
586 continue;
587
588 foreach (Pair p in b)
589 yield return new KeyValuePair<TKey, TValue> (p.Key, p.Value);
590 } finally {
591 if (taken)
592 b.Lock.Exit ();
593 }
594 }
595 }
596 }
597
598 IDictionaryEnumerator IDictionary.GetEnumerator ()
599 {
600 return new ConcurrentDictionaryEnumerator (GetEnumeratorInternal ());
601 }
602
603 class ConcurrentDictionaryEnumerator : IDictionaryEnumerator
604 {
605 IEnumerator<KeyValuePair<TKey, TValue>> internalEnum;
606
607 public ConcurrentDictionaryEnumerator (IEnumerator<KeyValuePair<TKey, TValue>> internalEnum)
608 {
609 this.internalEnum = internalEnum;
610 }
611
612 public bool MoveNext ()
613 {
614 return internalEnum.MoveNext ();
615 }
616
617 public void Reset ()
618 {
619 internalEnum.Reset ();
620 }
621
622 public object Current {
623 get {
624 return Entry;
625 }
626 }
627
628 public DictionaryEntry Entry {
629 get {
630 KeyValuePair<TKey, TValue> current = internalEnum.Current;
631 return new DictionaryEntry (current.Key, current.Value);
632 }
633 }
634
635 public object Key {
636 get {
637 return internalEnum.Current.Key;
638 }
639 }
640
641 public object Value {
642 get {
643 return internalEnum.Current.Value;
644 }
645 }
646 }
647
648 object ICollection.SyncRoot {
649 get {
650 return this;
651 }
652 }
653
654
655 bool IDictionary.IsFixedSize {
656 get {
657 return false;
658 }
659 }
660
661 bool ICollection.IsSynchronized {
662 get { return true; }
663 }
664
665 bool TryGetBasket (TKey key, out Basket basket)
666 {
667 basket = null;
668 if (!container.GetFromHash (key.GetHashCode (), out basket))
669 return false;
670
671 return true;
672 }
673 }
674 }
675 #endif
git-svn mirror of mcs