implab/ImplabNet Files · Implab/Parallels/MTQueue.cs

service locator refactoring

cin - - Load All Authors

File last commit:

r24:ee04e1fa78da default


                r69:48763f3b5db8

default

Download file

             MTQueue.cs
        
                    75 lines
            
             | 2.5 KiB
            
                | text/x-csharp
            
             |
                CSharpLexer
            
             / Implab / Parallels / MTQueue.cs
          
                    History
                
                 |
                  Annotation
                 | Raw
                 |Copy content
                 |Copy permalink

      using System;

      using System.Collections.Generic;

      using System.Linq;

      using System.Text;

      using System.Threading;

      namespace Implab.Parallels {

          public class MTQueue<T> {

              class Node {

                  public Node(T value) {

                      this.value = value;

                  }

                  public readonly T value;

                  public Node next;

              }

              Node m_first;

              Node m_last;

              public void Enqueue(T value) {

                  var last = m_last;

                  var next = new Node(value);

                  while (last != Interlocked.CompareExchange(ref m_last, next, last))

                      last = m_last;

                  if (last != null)

                      last.next = next;

                  else

                      m_first = next;

              }

              public bool TryDequeue(out T value) {

                  Node first;

                  Node next = null;

                  value = default(T);

                  do {

                      first = m_first;

                      if (first == null)

                          return false;

                      next = first.next;

                      if (next == null) {

                          // this is the last element,

                          // then try to update the tail

                          if (first != Interlocked.CompareExchange(ref m_last, null, first)) {

                              // this is a race condition

                              if (m_last == null)

                                  // the queue is empty

                                  return false;

                              // tail has been changed, than we need to restart

                              continue; 

                          }

                          // tail succesfully updated and first.next will never be changed

                          // other readers will fail due to inconsistency m_last != m_fist, but m_first.next == null

                          // but the writer may update the m_first since the m_last is null

                          // so we need to fix inconsistency by setting m_first to null, but if it already has been

                          // updated by a writer then we should just give up

                          Interlocked.CompareExchange(ref m_first, null, first);

                          break;

                      } else {

                              if (first == Interlocked.CompareExchange(ref m_first, next, first))

                                  // head succesfully updated

                                  break;

                      }

                  } while (true);

                  value = first.value;

                  return true;

              }

          }

      }

	Site-wide shortcuts
/	Use quick search box
g h	Goto home page
g g	Goto my private gists page
g G	Goto my public gists page
g 0-9	Goto bookmarked items from 0-9
n r	New repository page
n g	New gist page

	Repositories
g s	Goto summary page
g c	Goto changelog page
g f	Goto files page
g F	Goto files page with file search activated
g p	Goto pull requests page
g o	Goto repository settings
g O	Goto repository access permissions settings
t s	Toggle sidebar on some pages

				using System;
				using System.Collections.Generic;
				using System.Linq;
				using System.Text;
				using System.Threading;

				namespace Implab.Parallels {
				public class MTQueue<T> {
				class Node {
				public Node(T value) {
				this.value = value;
				}
				public readonly T value;
				public Node next;
				}

				Node m_first;
				Node m_last;

				public void Enqueue(T value) {
				var last = m_last;
				var next = new Node(value);

				while (last != Interlocked.CompareExchange(ref m_last, next, last))
				last = m_last;

				if (last != null)
				last.next = next;
				else
				m_first = next;
				}

				public bool TryDequeue(out T value) {
				Node first;
				Node next = null;
				value = default(T);

				do {
				first = m_first;
				if (first == null)
				return false;
				next = first.next;
				if (next == null) {
				// this is the last element,
				// then try to update the tail
				if (first != Interlocked.CompareExchange(ref m_last, null, first)) {
				// this is a race condition
				if (m_last == null)
				// the queue is empty
				return false;
				// tail has been changed, than we need to restart
				continue;
				}

				// tail succesfully updated and first.next will never be changed
				// other readers will fail due to inconsistency m_last != m_fist, but m_first.next == null
				// but the writer may update the m_first since the m_last is null

				// so we need to fix inconsistency by setting m_first to null, but if it already has been
				// updated by a writer then we should just give up
				Interlocked.CompareExchange(ref m_first, null, first);
				break;

				} else {
				if (first == Interlocked.CompareExchange(ref m_first, next, first))
				// head succesfully updated
				break;
				}
				} while (true);

				value = first.value;
				return true;
				}
				}
				}