Org.Lwes/SimpleLockFreeQueue.cs

   1 //
   2 // This file is part of the LWES .NET Binding (LWES.net)
   3 //
   4 // Code in this file is based on code by Idaho Edokpayi found at
   5 // http://www.codeproject.com/KB/cpp/lockfreeq.aspx?fid=996469&df=90&mpp=25&noise=3&sort=Position&view=Quick
   6 // Idaho Edokpayi's code is covered by the Code Project Open License (CPOL)
   7 // found at http://www.codeproject.com/info/cpol10.aspx
   8 //
   9 // I have modified the code to use C# idioms that I am fond of; previously
  10 // it resembled a port of C++ code and carried over those idioms.
  11 //
  12 // COPYRIGHT (C) 2009, Phillip Clark (cerebralkungfu[at*g mail[dot*com)
  13 //   original .NET implementation
  14 //
  15 // LWES.net is free software: you can redistribute it and/or modify
  16 // it under the terms of the Lesser GNU General Public License as published by
  17 // the Free Software Foundation, either version 3 of the License, or
  18 // (at your option) any later version.
  19 //
  20 // LWES.net is distributed in the hope that it will be useful,
  21 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  22 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  23 // GNU General Public License for more details.
  24 //
  25 // You should have received a copy of the Lesser GNU General Public License
  26 // along with LWES.net.  If not, see <http://www.gnu.org/licenses/>.
  27 //
  28 namespace Org.Lwes
  29 {
  30         using System;
  31         using System.Threading;
  32
  33         /// <summary>
  34         /// Simple implementation of a lock-free queue.
  35         /// </summary>
  36         /// <typeparam name="T">queued item type T</typeparam>
  37         public class SimpleLockFreeQueue<T>
  38         {
  39                 #region Fields
  40
  41                 private NodeRec _head;
  42                 private NodeRec _tail;
  43
  44                 #endregion Fields
  45
  46                 #region Constructors
  47
  48                 /// <summary>
  49                 /// Creates a new instance.
  50                 /// </summary>
  51                 public SimpleLockFreeQueue()
  52                 {
  53                         Node node = new Node();
  54                         _head.Node = _tail.Node = node;
  55                 }
  56
  57                 #endregion Constructors
  58
  59                 #region Properties
  60
  61                 /// <summary>
  62                 /// Determines if the queue is empty. Because of the non-blocking nature of the queue there is no guarantee
  63                 /// made about the availablility of items in the queue after this call. At best it can serve as an indicator.
  64                 /// </summary>
  65                 public bool IsEmpty
  66                 {
  67                         get
  68                         {
  69                                 NodeRec head = _head;
  70                                 NodeRec tail = _tail;
  71                                 NodeRec next = head.Node.Next;
  72
  73                                 // Are head, tail, and next consistent?
  74                                 if (head.Count == _head.Count
  75                                         && head.Node == _head.Node
  76                                         && head.Node == tail.Node
  77                                         && null == next.Node)
  78                                 {
  79                                         return true;
  80                                 }
  81
  82                                 return false;
  83                         }
  84                 }
  85
  86                 #endregion Properties
  87
  88                 #region Methods
  89
  90                 /// <summary>
  91                 /// Dequeues an item if it is available in the queue.
  92                 /// </summary>
  93                 /// <param name="item">the next available item in the queue, otherwise default(T).</param>
  94                 /// <returns><em>true</em> if an queued item was retreived by the call, otherwise <em>false</em></returns>
  95                 public bool Dequeue(out T item)
  96                 {
  97                         NodeRec head;
  98
  99                         // Keep trying until we get an item or the queue is empty
 100                         while (true)
 101                         {
 102                                 // read head
 103                                 head = _head;
 104
 105                                 // read tail
 106                                 NodeRec tail = _tail;
 107
 108                                 // read next
 109                                 NodeRec next = head.Node.Next;
 110
 111                                 // Are head, tail, and next consistent?
 112                                 if (head.Count == _head.Count && head.Node == _head.Node)
 113                                 {
 114                                         // is tail falling behind
 115                                         if (head.Node == tail.Node)
 116                                         {
 117                                                 if (null == next.Node)
 118                                                 {
 119                                                         // queue is empty, we're done.
 120                                                         break;
 121                                                 }
 122
 123                                                 // Tail is falling behind. try to advance it
 124                                                 CAS(ref _tail, tail, new NodeRec(next.Node, tail.Count + 1));
 125                                         }
 126                                         else
 127                                         {
 128                                                 // No need to deal with tail,
 129                                                 // read value before CAS otherwise concurrent op might try to free the next node
 130                                                 item = next.Node.Value;
 131
 132                                                 // try to swing the head to the next node
 133                                                 if (CAS(ref _head, head, new NodeRec(next.Node, head.Count + 1)))
 134                                                 {
 135                                                         return true;
 136                                                 }
 137                                         }
 138                                 }
 139                         }
 140
 141                         item = default(T);
 142                         return false;
 143                 }
 144
 145                 /// <summary>
 146                 /// Enqueues an item.
 147                 /// </summary>
 148                 /// <param name="item">The item to place in the queue</param>
 149                 public void Enqueue(T item)
 150                 {
 151                         Node node = new Node();
 152                         node.Value = item;
 153
 154                         while (true)
 155                         {
 156                                 NodeRec tail = _tail;
 157                                 NodeRec next = tail.Node.Next;
 158
 159                                 if (tail.Count == _tail.Count && tail.Node == _tail.Node)
 160                                 {
 161                                         if (null == next.Node)
 162                                         {
 163                                                 // Tail was pointing at the last node
 164                                                 if (CAS(ref tail.Node.Next, next, new NodeRec(node, next.Count + 1)))
 165                                                 {
 166                                                         break;
 167                                                 }
 168                                         }
 169                                         else
 170                                         {
 171                                                 // tail was not pointing at the last node,
 172                                                 // try to swing Tail to the next node
 173                                                 CAS(ref _tail, tail, new NodeRec(next.Node, tail.Count + 1));
 174                                         }
 175                                 }
 176                         }
 177                 }
 178
 179                 private bool CAS(ref NodeRec destination, NodeRec compared, NodeRec exchange)
 180                 {
 181                         if (compared.Node == Interlocked.CompareExchange(ref destination.Node, exchange.Node, compared.Node))
 182                         {
 183                                 Interlocked.Exchange(ref destination.Count, exchange.Count);
 184                                 return true;
 185                         }
 186
 187                         return false;
 188                 }
 189
 190                 #endregion Methods
 191
 192                 #region Nested Types
 193
 194                 struct NodeRec
 195                 {
 196                         #region Fields
 197
 198                         public long Count;
 199                         public Node Node;
 200
 201                         #endregion Fields
 202
 203                         #region Constructors
 204
 205                         public NodeRec(Node node, long c)
 206                         {
 207                                 Node = node;
 208                                 Count = c;
 209                         }
 210
 211                         #endregion Constructors
 212
 213                         #if DEBUG
 214
 215                         public override string ToString()
 216                         {
 217                                 return String.Concat("NodeRec { Count = ", Count.ToString(), ", Node = ", Node.ToString(), "}");
 218                         }
 219
 220                         #endif
 221                 }
 222
 223                 class Node
 224                 {
 225                         #region Fields
 226
 227                         public NodeRec Next;
 228                         public T Value;
 229
 230                         #endregion Fields
 231
 232                         #if DEBUG
 233
 234                         // Helpful in the debugger when inspecting the node list
 235                         public override string ToString()
 236                         {
 237                                 return String.Concat("Node { Next = ", Next.Count.ToString(), ", Value = ",
 238                                         (Value != null) ? Value.ToString() : "null", "}");
 239                         }
 240
 241                         #endif
 242                 }
 243
 244                 #endregion Nested Types
 245         }
 246 }