| 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 |
} |