Debian Codegraph @

mcs/class/referencesource/System/sys/system/collections/concurrent/ConcurrentBag.cs

raw
1 // ==++==
2 //
3 // Copyright (c) Microsoft Corporation. All rights reserved.
4 //
5 // ==--==
6 // =+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+=+
7 //
8 // ConcurrentBag.cs
9 //
10 // <OWNER>Microsoft</OWNER>
11 //
12 //
13 //An unordered collection that allows duplicates and that provides add and get operations.
14 // =-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
15
16 using System;
17 using System.Collections;
18 using System.Collections.Generic;
19 using System.Collections.Concurrent;
20 using System.Runtime.Serialization;
21 using System.Runtime.InteropServices;
22 using System.Diagnostics;
23 using System.Security.Permissions;
24 using System.Threading;
25 using System.Diagnostics.CodeAnalysis;
26 using System.Diagnostics.Contracts;
27
28 namespace System.Collections.Concurrent
29 {
30 /// <summary>
31 /// Represents an thread-safe, unordered collection of objects.
32 /// </summary>
33 /// <typeparam name="T">Specifies the type of elements in the bag.</typeparam>
34 /// <remarks>
35 /// <para>
36 /// Bags are useful for storing objects when ordering doesn't matter, and unlike sets, bags support
37 /// duplicates. <see cref="ConcurrentBag{T}"/> is a thread-safe bag implementation, optimized for
38 /// scenarios where the same thread will be both producing and consuming data stored in the bag.
39 /// </para>
40 /// <para>
41 /// <see cref="ConcurrentBag{T}"/> accepts null reference (Nothing in Visual Basic) as a valid
42 /// value for reference types.
43 /// </para>
44 /// <para>
45 /// All public and protected members of <see cref="ConcurrentBag{T}"/> are thread-safe and may be used
46 /// concurrently from multiple threads.
47 /// </para>
48 /// </remarks>
49 #if !SILVERLIGHT
50 [Serializable]
51 #endif
52 [ComVisible(false)]
53 [DebuggerTypeProxy(typeof(SystemThreadingCollection_IProducerConsumerCollectionDebugView<>))]
54 [DebuggerDisplay("Count = {Count}")]
55 #if !FEATURE_NETCORE
56 [HostProtection(Synchronization = true, ExternalThreading = true)]
57 #endif
58 public class ConcurrentBag<T> : IProducerConsumerCollection<T>, IReadOnlyCollection<T>
59 {
60
61 // ThreadLocalList object that contains the data per thread
62 #if !SILVERLIGHT
63 [NonSerialized]
64 #endif
65 ThreadLocal<ThreadLocalList> m_locals;
66
67 // This head and tail pointers points to the first and last local lists, to allow enumeration on the thread locals objects
68 #if !SILVERLIGHT
69 [NonSerialized]
70 #endif
71 volatile ThreadLocalList m_headList, m_tailList;
72
73 // A flag used to tell the operations thread that it must synchronize the operation, this flag is set/unset within
74 // GlobalListsLock lock
75 #if !SILVERLIGHT
76 [NonSerialized]
77 #endif
78 bool m_needSync;
79
80 #if !SILVERLIGHT
81 // Used for custom serialization.
82 private T[] m_serializationArray;
83 #endif
84
85 /// <summary>
86 /// Initializes a new instance of the <see cref="ConcurrentBag{T}"/>
87 /// class.
88 /// </summary>
89 public ConcurrentBag()
90 {
91 Initialize(null);
92 }
93
94 /// <summary>
95 /// Initializes a new instance of the <see cref="ConcurrentBag{T}"/>
96 /// class that contains elements copied from the specified collection.
97 /// </summary>
98 /// <param name="collection">The collection whose elements are copied to the new <see
99 /// cref="ConcurrentBag{T}"/>.</param>
100 /// <exception cref="ArgumentNullException"><paramref name="collection"/> is a null reference
101 /// (Nothing in Visual Basic).</exception>
102 public ConcurrentBag(IEnumerable<T> collection)
103 {
104 if (collection == null)
105 {
106 throw new ArgumentNullException("collection", SR.GetString(SR.ConcurrentBag_Ctor_ArgumentNullException));
107 }
108 Initialize(collection);
109 }
110
111
112 /// <summary>
113 /// Local helper function to initalize a new bag object
114 /// </summary>
115 /// <param name="collection">An enumeration containing items with which to initialize this bag.</param>
116 private void Initialize(IEnumerable<T> collection)
117 {
118 m_locals = new ThreadLocal<ThreadLocalList>();
119
120 // Copy the collection to the bag
121 if (collection != null)
122 {
123 ThreadLocalList list = GetThreadList(true);
124 foreach (T item in collection)
125 {
126 list.Add(item, false);
127 }
128 }
129 }
130
131 /// <summary>
132 /// Adds an object to the <see cref="ConcurrentBag{T}"/>.
133 /// </summary>
134 /// <param name="item">The object to be added to the
135 /// <see cref="ConcurrentBag{T}"/>. The value can be a null reference
136 /// (Nothing in Visual Basic) for reference types.</param>
137 public void Add(T item)
138 {
139 // Get the local list for that thread, create a new list if this thread doesn't exist
140 //(first time to call add)
141 ThreadLocalList list = GetThreadList(true);
142 AddInternal(list, item);
143 }
144
145 /// <summary>
146 /// </summary>
147 /// <param name="list"></param>
148 /// <param name="item"></param>
149 private void AddInternal(ThreadLocalList list, T item)
150 {
151 bool lockTaken = false;
152 try
153 {
154 #pragma warning disable 0420
155 Interlocked.Exchange(ref list.m_currentOp, (int)ListOperation.Add);
156 #pragma warning restore 0420
157 //Synchronization cases:
158 // if the list count is less than two to avoid conflict with any stealing thread
159 // if m_needSync is set, this means there is a thread that needs to freeze the bag
160 if (list.Count < 2 || m_needSync)
161 {
162 // reset it back to zero to avoid deadlock with stealing thread
163 list.m_currentOp = (int)ListOperation.None;
164 Monitor.Enter(list, ref lockTaken);
165 }
166 list.Add(item, lockTaken);
167 }
168 finally
169 {
170 list.m_currentOp = (int)ListOperation.None;
171 if (lockTaken)
172 {
173 Monitor.Exit(list);
174 }
175 }
176 }
177
178 /// <summary>
179 /// Attempts to add an object to the <see cref="ConcurrentBag{T}"/>.
180 /// </summary>
181 /// <param name="item">The object to be added to the
182 /// <see cref="ConcurrentBag{T}"/>. The value can be a null reference
183 /// (Nothing in Visual Basic) for reference types.</param>
184 /// <returns>Always returns true</returns>
185 bool IProducerConsumerCollection<T>.TryAdd(T item)
186 {
187 Add(item);
188 return true;
189 }
190
191 /// <summary>
192 /// Attempts to remove and return an object from the <see
193 /// cref="ConcurrentBag{T}"/>.
194 /// </summary>
195 /// <param name="result">When this method returns, <paramref name="result"/> contains the object
196 /// removed from the <see cref="ConcurrentBag{T}"/> or the default value
197 /// of <typeparamref name="T"/> if the operation failed.</param>
198 /// <returns>true if an object was removed successfully; otherwise, false.</returns>
199 public bool TryTake(out T result)
200 {
201 return TryTakeOrPeek(out result, true);
202 }
203
204 /// <summary>
205 /// Attempts to return an object from the <see cref="ConcurrentBag{T}"/>
206 /// without removing it.
207 /// </summary>
208 /// <param name="result">When this method returns, <paramref name="result"/> contains an object from
209 /// the <see cref="ConcurrentBag{T}"/> or the default value of
210 /// <typeparamref name="T"/> if the operation failed.</param>
211 /// <returns>true if and object was returned successfully; otherwise, false.</returns>
212 public bool TryPeek(out T result)
213 {
214 return TryTakeOrPeek(out result, false);
215 }
216
217 /// <summary>
218 /// Local helper function to Take or Peek an item from the bag
219 /// </summary>
220 /// <param name="result">To receive the item retrieved from the bag</param>
221 /// <param name="take">True means Take operation, false means Peek operation</param>
222 /// <returns>True if succeeded, false otherwise</returns>
223 private bool TryTakeOrPeek(out T result, bool take)
224 {
225
226 // Get the local list for that thread, return null if the thread doesn't exit
227 //(this thread never add before)
228 ThreadLocalList list = GetThreadList(false);
229 if (list == null || list.Count == 0)
230 {
231 return Steal(out result, take);
232 }
233
234 bool lockTaken = false;
235 try
236 {
237 if (take) // Take operation
238 {
239 #pragma warning disable 0420
240 Interlocked.Exchange(ref list.m_currentOp, (int)ListOperation.Take);
241 #pragma warning restore 0420
242 //Synchronization cases:
243 // if the list count is less than or equal two to avoid conflict with any stealing thread
244 // if m_needSync is set, this means there is a thread that needs to freeze the bag
245 if (list.Count <= 2 || m_needSync)
246 {
247 // reset it back to zero to avoid deadlock with stealing thread
248 list.m_currentOp = (int)ListOperation.None;
249 Monitor.Enter(list, ref lockTaken);
250
251 // Double check the count and steal if it became empty
252 if (list.Count == 0)
253 {
254 // Release the lock before stealing
255 if (lockTaken)
256 {
257 try { }
258 finally
259 {
260 lockTaken = false; // reset lockTaken to avoid calling Monitor.Exit again in the finally block
261 Monitor.Exit(list);
262 }
263 }
264 return Steal(out result, true);
265 }
266 }
267 list.Remove(out result);
268 }
269 else
270 {
271 if (!list.Peek(out result))
272 {
273 return Steal(out result, false);
274 }
275 }
276 }
277 finally
278 {
279 list.m_currentOp = (int)ListOperation.None;
280 if (lockTaken)
281 {
282 Monitor.Exit(list);
283 }
284 }
285 return true;
286 }
287
288
289 /// <summary>
290 /// Local helper function to retrieve a thread local list by a thread object
291 /// </summary>
292 /// <param name="forceCreate">Create a new list if the thread does ot exist</param>
293 /// <returns>The local list object</returns>
294 private ThreadLocalList GetThreadList(bool forceCreate)
295 {
296 ThreadLocalList list = m_locals.Value;
297
298 if (list != null)
299 {
300 return list;
301 }
302 else if (forceCreate)
303 {
304 // Acquire the lock to update the m_tailList pointer
305 lock (GlobalListsLock)
306 {
307 if (m_headList == null)
308 {
309 list = new ThreadLocalList(Thread.CurrentThread);
310 m_headList = list;
311 m_tailList = list;
312 }
313 else
314 {
315
316 list = GetUnownedList();
317 if (list == null)
318 {
319 list = new ThreadLocalList(Thread.CurrentThread);
320 m_tailList.m_nextList = list;
321 m_tailList = list;
322 }
323 }
324 m_locals.Value = list;
325 }
326 }
327 else
328 {
329 return null;
330 }
331 Debug.Assert(list != null);
332 return list;
333
334 }
335
336 /// <summary>
337 /// Try to reuse an unowned list if exist
338 /// unowned lists are the lists that their owner threads are aborted or terminated
339 /// this is workaround to avoid memory leaks.
340 /// </summary>
341 /// <returns>The list object, null if all lists are owned</returns>
342 private ThreadLocalList GetUnownedList()
343 {
344 //the global lock must be held at this point
345 Contract.Assert(Monitor.IsEntered(GlobalListsLock));
346
347 ThreadLocalList currentList = m_headList;
348 while (currentList != null)
349 {
350 if (currentList.m_ownerThread.ThreadState == System.Threading.ThreadState.Stopped)
351 {
352 currentList.m_ownerThread = Thread.CurrentThread; // the caller should acquire a lock to make this line thread safe
353 return currentList;
354 }
355 currentList = currentList.m_nextList;
356 }
357 return null;
358 }
359
360
361 /// <summary>
362 /// Local helper method to steal an item from any other non empty thread
363 /// It enumerate all other threads in two passes first pass acquire the lock with TryEnter if succeeded
364 /// it steals the item, otherwise it enumerate them again in 2nd pass and acquire the lock using Enter
365 /// </summary>
366 /// <param name="result">To receive the item retrieved from the bag</param>
367 /// <param name="take">Whether to remove or peek.</param>
368 /// <returns>True if succeeded, false otherwise.</returns>
369 private bool Steal(out T result, bool take)
370 {
371 #if !FEATURE_PAL && !SILVERLIGHT // PAL doesn't support eventing
372 if (take)
373 CDSCollectionETWBCLProvider.Log.ConcurrentBag_TryTakeSteals();
374 else
375 CDSCollectionETWBCLProvider.Log.ConcurrentBag_TryPeekSteals();
376 #endif
377
378 bool loop;
379 List<int> versionsList = new List<int>(); // save the lists version
380 do
381 {
382 versionsList.Clear(); //clear the list from the previous iteration
383 loop = false;
384
385
386 ThreadLocalList currentList = m_headList;
387 while (currentList != null)
388 {
389 versionsList.Add(currentList.m_version);
390 if (currentList.m_head != null && TrySteal(currentList, out result, take))
391 {
392 return true;
393 }
394 currentList = currentList.m_nextList;
395 }
396
397 // verify versioning, if other items are added to this list since we last visit it, we should retry
398 currentList = m_headList;
399 foreach (int version in versionsList)
400 {
401 if (version != currentList.m_version) //oops state changed
402 {
403 loop = true;
404 if (currentList.m_head != null && TrySteal(currentList, out result, take))
405 return true;
406 }
407 currentList = currentList.m_nextList;
408 }
409 } while (loop);
410
411
412 result = default(T);
413 return false;
414 }
415
416 /// <summary>
417 /// local helper function tries to steal an item from given local list
418 /// </summary>
419 private bool TrySteal(ThreadLocalList list, out T result, bool take)
420 {
421 lock (list)
422 {
423 if (CanSteal(list))
424 {
425 list.Steal(out result, take);
426 return true;
427 }
428 result = default(T);
429 return false;
430 }
431
432 }
433 /// <summary>
434 /// Local helper function to check the list if it became empty after acquiring the lock
435 /// and wait if there is unsynchronized Add/Take operation in the list to be done
436 /// </summary>
437 /// <param name="list">The list to steal</param>
438 /// <returns>True if can steal, false otherwise</returns>
439 private bool CanSteal(ThreadLocalList list)
440 {
441 if (list.Count <= 2 && list.m_currentOp != (int)ListOperation.None)
442 {
443 SpinWait spinner = new SpinWait();
444 while (list.m_currentOp != (int)ListOperation.None)
445 {
446 spinner.SpinOnce();
447 }
448 }
449 if (list.Count > 0)
450 {
451 return true;
452 }
453 return false;
454 }
455
456 /// <summary>
457 /// Copies the <see cref="ConcurrentBag{T}"/> elements to an existing
458 /// one-dimensional <see cref="T:System.Array">Array</see>, starting at the specified array
459 /// index.
460 /// </summary>
461 /// <param name="array">The one-dimensional <see cref="T:System.Array">Array</see> that is the
462 /// destination of the elements copied from the
463 /// <see cref="ConcurrentBag{T}"/>. The <see
464 /// cref="T:System.Array">Array</see> must have zero-based indexing.</param>
465 /// <param name="index">The zero-based index in <paramref name="array"/> at which copying
466 /// begins.</param>
467 /// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference (Nothing in
468 /// Visual Basic).</exception>
469 /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than
470 /// zero.</exception>
471 /// <exception cref="ArgumentException"><paramref name="index"/> is equal to or greater than the
472 /// length of the <paramref name="array"/>
473 /// -or- the number of elements in the source <see
474 /// cref="ConcurrentBag{T}"/> is greater than the available space from
475 /// <paramref name="index"/> to the end of the destination <paramref name="array"/>.</exception>
476 public void CopyTo(T[] array, int index)
477 {
478 if (array == null)
479 {
480 throw new ArgumentNullException("array", SR.GetString(SR.ConcurrentBag_CopyTo_ArgumentNullException));
481 }
482 if (index < 0)
483 {
484 throw new ArgumentOutOfRangeException
485 ("index", SR.GetString(SR.ConcurrentBag_CopyTo_ArgumentOutOfRangeException));
486 }
487
488 // Short path if the bag is empty
489 if (m_headList == null)
490 return;
491
492 bool lockTaken = false;
493 try
494 {
495 FreezeBag(ref lockTaken);
496 ToList().CopyTo(array, index);
497 }
498 finally
499 {
500 UnfreezeBag(lockTaken);
501 }
502 }
503
504 /// <summary>
505 /// Copies the elements of the <see cref="T:System.Collections.ICollection"/> to an <see
506 /// cref="T:System.Array"/>, starting at a particular
507 /// <see cref="T:System.Array"/> index.
508 /// </summary>
509 /// <param name="array">The one-dimensional <see cref="T:System.Array">Array</see> that is the
510 /// destination of the elements copied from the
511 /// <see cref="ConcurrentBag{T}"/>. The <see
512 /// cref="T:System.Array">Array</see> must have zero-based indexing.</param>
513 /// <param name="index">The zero-based index in <paramref name="array"/> at which copying
514 /// begins.</param>
515 /// <exception cref="ArgumentNullException"><paramref name="array"/> is a null reference (Nothing in
516 /// Visual Basic).</exception>
517 /// <exception cref="ArgumentOutOfRangeException"><paramref name="index"/> is less than
518 /// zero.</exception>
519 /// <exception cref="ArgumentException">
520 /// <paramref name="array"/> is multidimensional. -or-
521 /// <paramref name="array"/> does not have zero-based indexing. -or-
522 /// <paramref name="index"/> is equal to or greater than the length of the <paramref name="array"/>
523 /// -or- The number of elements in the source <see cref="T:System.Collections.ICollection"/> is
524 /// greater than the available space from <paramref name="index"/> to the end of the destination
525 /// <paramref name="array"/>. -or- The type of the source <see
526 /// cref="T:System.Collections.ICollection"/> cannot be cast automatically to the type of the
527 /// destination <paramref name="array"/>.
528 /// </exception>
529 void ICollection.CopyTo(Array array, int index)
530 {
531 if (array == null)
532 {
533 throw new ArgumentNullException("array", SR.GetString(SR.ConcurrentBag_CopyTo_ArgumentNullException));
534 }
535
536 bool lockTaken = false;
537 try
538 {
539 FreezeBag(ref lockTaken);
540 ((ICollection)ToList()).CopyTo(array, index);
541 }
542 finally
543 {
544 UnfreezeBag(lockTaken);
545 }
546
547 }
548
549
550 /// <summary>
551 /// Copies the <see cref="ConcurrentBag{T}"/> elements to a new array.
552 /// </summary>
553 /// <returns>A new array containing a snapshot of elements copied from the <see
554 /// cref="ConcurrentBag{T}"/>.</returns>
555 public T[] ToArray()
556 {
557 // Short path if the bag is empty
558 if (m_headList == null)
559 return new T[0];
560
561 bool lockTaken = false;
562 try
563 {
564 FreezeBag(ref lockTaken);
565 return ToList().ToArray();
566 }
567 finally
568 {
569 UnfreezeBag(lockTaken);
570 }
571 }
572
573 /// <summary>
574 /// Returns an enumerator that iterates through the <see
575 /// cref="ConcurrentBag{T}"/>.
576 /// </summary>
577 /// <returns>An enumerator for the contents of the <see
578 /// cref="ConcurrentBag{T}"/>.</returns>
579 /// <remarks>
580 /// The enumeration represents a moment-in-time snapshot of the contents
581 /// of the bag. It does not reflect any updates to the collection after
582 /// <see cref="GetEnumerator"/> was called. The enumerator is safe to use
583 /// concurrently with reads from and writes to the bag.
584 /// </remarks>
585 public IEnumerator<T> GetEnumerator()
586 {
587 // Short path if the bag is empty
588 if (m_headList == null)
589 return new List<T>().GetEnumerator(); // empty list
590
591 bool lockTaken = false;
592 try
593 {
594 FreezeBag(ref lockTaken);
595 return ToList().GetEnumerator();
596 }
597 finally
598 {
599 UnfreezeBag(lockTaken);
600 }
601 }
602
603 /// <summary>
604 /// Returns an enumerator that iterates through the <see
605 /// cref="ConcurrentBag{T}"/>.
606 /// </summary>
607 /// <returns>An enumerator for the contents of the <see
608 /// cref="ConcurrentBag{T}"/>.</returns>
609 /// <remarks>
610 /// The items enumerated represent a moment-in-time snapshot of the contents
611 /// of the bag. It does not reflect any update to the collection after
612 /// <see cref="GetEnumerator"/> was called.
613 /// </remarks>
614 IEnumerator IEnumerable.GetEnumerator()
615 {
616 return ((ConcurrentBag<T>)this).GetEnumerator();
617 }
618 #if !SILVERLIGHT
619 /// <summary>
620 /// Get the data array to be serialized
621 /// </summary>
622 [OnSerializing]
623 private void OnSerializing(StreamingContext context)
624 {
625 // save the data into the serialization array to be saved
626 m_serializationArray = ToArray();
627 }
628
629 /// <summary>
630 /// Construct the stack from a previously seiralized one
631 /// </summary>
632 [OnDeserialized]
633 private void OnDeserialized(StreamingContext context)
634 {
635 m_locals = new ThreadLocal<ThreadLocalList>();
636
637 ThreadLocalList list = GetThreadList(true);
638 foreach (T item in m_serializationArray)
639 {
640 list.Add(item, false);
641 }
642 m_headList = list;
643 m_tailList = list;
644
645 m_serializationArray = null;
646 }
647 #endif
648 /// <summary>
649 /// Gets the number of elements contained in the <see cref="ConcurrentBag{T}"/>.
650 /// </summary>
651 /// <value>The number of elements contained in the <see cref="ConcurrentBag{T}"/>.</value>
652 /// <remarks>
653 /// The count returned represents a moment-in-time snapshot of the contents
654 /// of the bag. It does not reflect any updates to the collection after
655 /// <see cref="GetEnumerator"/> was called.
656 /// </remarks>
657 public int Count
658 {
659 get
660 {
661 // Short path if the bag is empty
662 if (m_headList == null)
663 return 0;
664
665 bool lockTaken = false;
666 try
667 {
668 FreezeBag(ref lockTaken);
669 return GetCountInternal();
670 }
671 finally
672 {
673 UnfreezeBag(lockTaken);
674 }
675 }
676 }
677
678 /// <summary>
679 /// Gets a value that indicates whether the <see cref="ConcurrentBag{T}"/> is empty.
680 /// </summary>
681 /// <value>true if the <see cref="ConcurrentBag{T}"/> is empty; otherwise, false.</value>
682 public bool IsEmpty
683 {
684 get
685 {
686 if (m_headList == null)
687 return true;
688
689 bool lockTaken = false;
690 try
691 {
692 FreezeBag(ref lockTaken);
693 ThreadLocalList currentList = m_headList;
694 while (currentList != null)
695 {
696 if (currentList.m_head != null)
697 //at least this list is not empty, we return false
698 {
699 return false;
700 }
701 currentList = currentList.m_nextList;
702 }
703 return true;
704 }
705 finally
706 {
707 UnfreezeBag(lockTaken);
708 }
709 }
710 }
711
712 /// <summary>
713 /// Gets a value indicating whether access to the <see cref="T:System.Collections.ICollection"/> is
714 /// synchronized with the SyncRoot.
715 /// </summary>
716 /// <value>true if access to the <see cref="T:System.Collections.ICollection"/> is synchronized
717 /// with the SyncRoot; otherwise, false. For <see cref="ConcurrentBag{T}"/>, this property always
718 /// returns false.</value>
719 bool ICollection.IsSynchronized
720 {
721 get { return false; }
722 }
723
724 /// <summary>
725 /// Gets an object that can be used to synchronize access to the <see
726 /// cref="T:System.Collections.ICollection"/>. This property is not supported.
727 /// </summary>
728 /// <exception cref="T:System.NotSupportedException">The SyncRoot property is not supported.</exception>
729 object ICollection.SyncRoot
730 {
731 get
732 {
733 throw new NotSupportedException(SR.GetString(SR.ConcurrentCollection_SyncRoot_NotSupported));
734 }
735 }
736
737
738 /// <summary>
739 /// A global lock object, used in two cases:
740 /// 1- To maintain the m_tailList pointer for each new list addition process ( first time a thread called Add )
741 /// 2- To freeze the bag in GetEnumerator, CopyTo, ToArray and Count members
742 /// </summary>
743 private object GlobalListsLock
744 {
745 get
746 {
747 Contract.Assert(m_locals != null);
748 return m_locals;
749 }
750 }
751
752
753 #region Freeze bag helper methods
754 /// <summary>
755 /// Local helper method to freeze all bag operations, it
756 /// 1- Acquire the global lock to prevent any other thread to freeze the bag, and also new new thread can be added
757 /// to the dictionary
758 /// 2- Then Acquire all local lists locks to prevent steal and synchronized operations
759 /// 3- Wait for all un-synchronized operations to be done
760 /// </summary>
761 /// <param name="lockTaken">Retrieve the lock taken result for the global lock, to be passed to Unfreeze method</param>
762 private void FreezeBag(ref bool lockTaken)
763 {
764 Contract.Assert(!Monitor.IsEntered(GlobalListsLock));
765
766 // global lock to be safe against multi threads calls count and corrupt m_needSync
767 Monitor.Enter(GlobalListsLock, ref lockTaken);
768
769 // This will force any future add/take operation to be synchronized
770 m_needSync = true;
771
772 //Acquire all local lists locks
773 AcquireAllLocks();
774
775 // Wait for all un-synchronized operation to be done
776 WaitAllOperations();
777 }
778
779 /// <summary>
780 /// Local helper method to unfreeze the bag from a frozen state
781 /// </summary>
782 /// <param name="lockTaken">The lock taken result from the Freeze method</param>
783 private void UnfreezeBag(bool lockTaken)
784 {
785 ReleaseAllLocks();
786 m_needSync = false;
787 if (lockTaken)
788 {
789 Monitor.Exit(GlobalListsLock);
790 }
791 }
792
793 /// <summary>
794 /// local helper method to acquire all local lists locks
795 /// </summary>
796 private void AcquireAllLocks()
797 {
798 Contract.Assert(Monitor.IsEntered(GlobalListsLock));
799
800 bool lockTaken = false;
801 ThreadLocalList currentList = m_headList;
802 while (currentList != null)
803 {
804 // Try/Finally bllock to avoid thread aport between acquiring the lock and setting the taken flag
805 try
806 {
807 Monitor.Enter(currentList, ref lockTaken);
808 }
809 finally
810 {
811 if (lockTaken)
812 {
813 currentList.m_lockTaken = true;
814 lockTaken = false;
815 }
816 }
817 currentList = currentList.m_nextList;
818 }
819 }
820
821 /// <summary>
822 /// Local helper method to release all local lists locks
823 /// </summary>
824 private void ReleaseAllLocks()
825 {
826 ThreadLocalList currentList = m_headList;
827 while (currentList != null)
828 {
829
830 if (currentList.m_lockTaken)
831 {
832 currentList.m_lockTaken = false;
833 Monitor.Exit(currentList);
834 }
835 currentList = currentList.m_nextList;
836 }
837 }
838
839 /// <summary>
840 /// Local helper function to wait all unsynchronized operations
841 /// </summary>
842 private void WaitAllOperations()
843 {
844 Contract.Assert(Monitor.IsEntered(GlobalListsLock));
845
846 ThreadLocalList currentList = m_headList;
847 while (currentList != null)
848 {
849 if (currentList.m_currentOp != (int)ListOperation.None)
850 {
851 SpinWait spinner = new SpinWait();
852 while (currentList.m_currentOp != (int)ListOperation.None)
853 {
854 spinner.SpinOnce();
855 }
856 }
857 currentList = currentList.m_nextList;
858 }
859 }
860
861 /// <summary>
862 /// Local helper function to get the bag count, the caller should call it from Freeze/Unfreeze block
863 /// </summary>
864 /// <returns>The current bag count</returns>
865 private int GetCountInternal()
866 {
867 Contract.Assert(Monitor.IsEntered(GlobalListsLock));
868
869 int count = 0;
870 ThreadLocalList currentList = m_headList;
871 while (currentList != null)
872 {
873 checked
874 {
875 count += currentList.Count;
876 }
877 currentList = currentList.m_nextList;
878 }
879 return count;
880 }
881
882 /// <summary>
883 /// Local helper function to return the bag item in a list, this is mainly used by CopyTo and ToArray
884 /// This is not thread safe, should be called in Freeze/UnFreeze bag block
885 /// </summary>
886 /// <returns>List the contains the bag items</returns>
887 private List<T> ToList()
888 {
889 Contract.Assert(Monitor.IsEntered(GlobalListsLock));
890
891 List<T> list = new List<T>();
892 ThreadLocalList currentList = m_headList;
893 while (currentList != null)
894 {
895 Node currentNode = currentList.m_head;
896 while (currentNode != null)
897 {
898 list.Add(currentNode.m_value);
899 currentNode = currentNode.m_next;
900 }
901 currentList = currentList.m_nextList;
902 }
903
904 return list;
905 }
906
907 #endregion
908
909
910 #region Inner Classes
911
912 /// <summary>
913 /// A class that represents a node in the lock thread list
914 /// </summary>
915 #if !SILVERLIGHT
916 [Serializable]
917 #endif
918 internal class Node
919 {
920 public Node(T value)
921 {
922 m_value = value;
923 }
924 public readonly T m_value;
925 public Node m_next;
926 public Node m_prev;
927 }
928
929 /// <summary>
930 /// A class that represents the lock thread list
931 /// </summary>
932 internal class ThreadLocalList
933 {
934 // Tead node in the list, null means the list is empty
935 internal volatile Node m_head;
936
937 // Tail node for the list
938 private volatile Node m_tail;
939
940 // The current list operation
941 internal volatile int m_currentOp;
942
943 // The list count from the Add/Take prespective
944 private int m_count;
945
946 // The stealing count
947 internal int m_stealCount;
948
949 // Next list in the dictionary values
950 internal volatile ThreadLocalList m_nextList;
951
952 // Set if the locl lock is taken
953 internal bool m_lockTaken;
954
955 // The owner thread for this list
956 internal Thread m_ownerThread;
957
958 // the version of the list, incremented only when the list changed from empty to non empty state
959 internal volatile int m_version;
960
961 /// <summary>
962 /// ThreadLocalList constructor
963 /// </summary>
964 /// <param name="ownerThread">The owner thread for this list</param>
965 internal ThreadLocalList(Thread ownerThread)
966 {
967 m_ownerThread = ownerThread;
968 }
969 /// <summary>
970 /// Add new item to head of the list
971 /// </summary>
972 /// <param name="item">The item to add.</param>
973 /// <param name="updateCount">Whether to update the count.</param>
974 internal void Add(T item, bool updateCount)
975 {
976 checked
977 {
978 m_count++;
979 }
980 Node node = new Node(item);
981 if (m_head == null)
982 {
983 Debug.Assert(m_tail == null);
984 m_head = node;
985 m_tail = node;
986 m_version++; // changing from empty state to non empty state
987 }
988 else
989 {
990 node.m_next = m_head;
991 m_head.m_prev = node;
992 m_head = node;
993 }
994 if (updateCount) // update the count to avoid overflow if this add is synchronized
995 {
996 m_count = m_count - m_stealCount;
997 m_stealCount = 0;
998 }
999 }
1000
1001 /// <summary>
1002 /// Remove an item from the head of the list
1003 /// </summary>
1004 /// <param name="result">The removed item</param>
1005 internal void Remove(out T result)
1006 {
1007 Debug.Assert(m_head != null);
1008 Node head = m_head;
1009 m_head = m_head.m_next;
1010 if (m_head != null)
1011 {
1012 m_head.m_prev = null;
1013 }
1014 else
1015 {
1016 m_tail = null;
1017 }
1018 m_count--;
1019 result = head.m_value;
1020
1021 }
1022
1023 /// <summary>
1024 /// Peek an item from the head of the list
1025 /// </summary>
1026 /// <param name="result">the peeked item</param>
1027 /// <returns>True if succeeded, false otherwise</returns>
1028 internal bool Peek(out T result)
1029 {
1030 Node head = m_head;
1031 if (head != null)
1032 {
1033 result = head.m_value;
1034 return true;
1035 }
1036 result = default(T);
1037 return false;
1038 }
1039
1040 /// <summary>
1041 /// Steal an item from the tail of the list
1042 /// </summary>
1043 /// <param name="result">the removed item</param>
1044 /// <param name="remove">remove or peek flag</param>
1045 internal void Steal(out T result, bool remove)
1046 {
1047 Node tail = m_tail;
1048 Debug.Assert(tail != null);
1049 if (remove) // Take operation
1050 {
1051 m_tail = m_tail.m_prev;
1052 if (m_tail != null)
1053 {
1054 m_tail.m_next = null;
1055 }
1056 else
1057 {
1058 m_head = null;
1059 }
1060 // Increment the steal count
1061 m_stealCount++;
1062 }
1063 result = tail.m_value;
1064 }
1065
1066
1067 /// <summary>
1068 /// Gets the total list count, it's not thread safe, may provide incorrect count if it is called concurrently
1069 /// </summary>
1070 internal int Count
1071 {
1072 get
1073 {
1074 return m_count - m_stealCount;
1075 }
1076 }
1077 }
1078
1079 /// <summary>
1080 /// List operations
1081 /// </summary>
1082 internal enum ListOperation
1083 {
1084 None,
1085 Add,
1086 Take
1087 };
1088 #endregion
1089 }
1090
1091
1092 #region Internal Types
1093
1094 /// <summary>
1095 /// A simple class for the debugger view window
1096 /// </summary>
1097 internal sealed class SystemThreadingCollection_IProducerConsumerCollectionDebugView<T>
1098 {
1099 IProducerConsumerCollection<T> m_collection;
1100 public SystemThreadingCollection_IProducerConsumerCollectionDebugView(IProducerConsumerCollection<T> collection)
1101 {
1102 if (collection == null)
1103 {
1104 throw new ArgumentNullException("collection");
1105 }
1106 m_collection = collection;
1107 }
1108
1109 /// <summary>
1110 /// Returns a snapshot of the underlying collection's elements.
1111 /// </summary>
1112 [DebuggerBrowsable(DebuggerBrowsableState.RootHidden)]
1113 public T[] Items
1114 {
1115 get { return m_collection.ToArray(); }
1116 }
1117 }
1118
1119 #endregion
1120
1121 }