daily pastebin goal
64%
SHARE
TWEET

Untitled

a guest Mar 24th, 2019 50 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. using System;
  2. using System.Collections.Generic;
  3. using System.Linq;
  4. using System.Text;
  5. using System.Threading;
  6. using System.Threading.Tasks;
  7.  
  8. namespace GZip
  9. {
  10.     /// <summary>
  11.     /// Вспомогательный класс для методов синхронизации потоков
  12.     /// </summary>
  13.     internal static class SyncHelper
  14.     {
  15.         /// <summary>
  16.         /// Атомарная операция сравнения-присваивания
  17.         /// </summary>
  18.         /// <param name="location">Целевой объект</param>
  19.         /// <param name="comparand">Значение, с которым сравниваем <see cref="location"/></param>
  20.         /// <param name="newValue">Новое значение для целевого объекта, если результат сравнения это равенство</param>
  21.         /// <returns>true, если произошла замена целевого объекта</returns>
  22.         public static bool CAS<T>( ref T location, T comparand, T newValue ) where T : class
  23.         {
  24.             return comparand == Interlocked.CompareExchange( ref location, newValue, comparand );
  25.         }
  26.     }
  27.  
  28.     /// <summary>
  29.     /// Потокобезопасная очередь
  30.     /// </summary>
  31.     public class ConcurrentQueue<T> where T : class
  32.     {
  33.         /// <summary>
  34.         /// Узел односвязного списка
  35.         /// </summary>
  36.         private class Node<TItem> where TItem : class
  37.         {
  38.             /// <summary>
  39.             /// Ссылка на следующий элемент в очереди.
  40.             /// </summary>
  41.             /// <remarks>Next должен быть именно полем класса - его нельзя сделать полем класса, т.к. он используется в CAS операции</remarks>
  42.             public Node<TItem> Next;
  43.  
  44.             /// <summary>
  45.             /// Элемент в коллекции
  46.             /// </summary>
  47.             public TItem Item;
  48.         }
  49.  
  50.         private Node<T> head;
  51.         private Node<T> tail;
  52.  
  53.         private int _count;
  54.  
  55.         /// <summary>
  56.         /// Возвращает true если очередь пуста
  57.         /// </summary>
  58.         public bool IsEmpty
  59.         {
  60.             get
  61.             {
  62.                 return head == tail;
  63.             }
  64.         }
  65.  
  66.         /// <summary>
  67.         /// Число объектов в очереди
  68.         /// </summary>
  69.         public int Count
  70.         {
  71.             get
  72.             {
  73.                 return _count;
  74.             }
  75.         }
  76.  
  77.         /// <summary>
  78.         /// Конструктор
  79.         /// </summary>
  80.         public ConcurrentQueue()
  81.         {
  82.             head = new Node<T>();
  83.             tail = head;
  84.         }
  85.  
  86.         /// <summary>
  87.         /// Добавляет элемент в очередь
  88.         /// </summary>
  89.         /// <param name="item">Элемент</param>
  90.         public void Enqueue( T item )
  91.         {
  92.             Node<T> oldTail = null;
  93.  
  94.             var newNode = new Node<T>();
  95.             newNode.Item = item;
  96.  
  97.             var newNodeAdded = false;
  98.             while( !newNodeAdded )
  99.             {
  100.                 oldTail = tail;
  101.                 var oldTailNext = oldTail.Next;
  102.                 if( tail != oldTail )
  103.                     continue;
  104.  
  105.                 if( oldTailNext == null )
  106.                     newNodeAdded = SyncHelper.CAS( ref tail.Next, null, newNode );
  107.                 else
  108.                     SyncHelper.CAS( ref tail, oldTail, oldTailNext );
  109.             }
  110.  
  111.             SyncHelper.CAS( ref tail, oldTail, newNode );
  112.             Interlocked.Increment( ref _count );
  113.         }
  114.  
  115.         /// <summary>
  116.         /// Удаляет элемент из очереди
  117.         /// </summary>
  118.         /// <returns>Удаленный элемент</returns>
  119.         public T Dequeue()
  120.         {
  121.             T item = null;
  122.             var hasAdvancedHead = false;
  123.             while( !hasAdvancedHead )
  124.             {
  125.                 var oldHead = head;
  126.                 var oldTail = tail;
  127.                 var oldHeadNext = oldHead.Next;
  128.                 if( oldHead != head )
  129.                     continue;
  130.  
  131.                 if( oldHead == oldTail )
  132.                 {
  133.                     if( oldHeadNext == null )
  134.                         oldTail.Item = null;
  135.  
  136.                     SyncHelper.CAS( ref tail, oldTail, oldHeadNext );
  137.                 }
  138.                 else
  139.                 {
  140.                     item = oldHeadNext.Item;
  141.                     hasAdvancedHead = SyncHelper.CAS( ref head, oldHead, oldHeadNext );
  142.  
  143.                     if( hasAdvancedHead )
  144.                         oldHead.Item = null;
  145.                 }
  146.             }
  147.  
  148.             Interlocked.Decrement( ref _count );
  149.  
  150.             return item;
  151.         }
  152.     }
  153. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top