mcs/class/corlib/System.Threading.Tasks/Internal/CyclicDeque.cs

   1 #if NET_4_0 || BOOTSTRAP_NET_4_0
   2 //
   3 // CyclicDeque.cs
   4 //
   5 // Author:
   6 //       Jérémie "Garuma" Laval <jeremie.laval@gmail.com>
   7 //
   8 // Copyright (c) 2009 Jérémie "Garuma" Laval
   9 //
  10 // Permission is hereby granted, free of charge, to any person obtaining a copy
  11 // of this software and associated documentation files (the "Software"), to deal
  12 // in the Software without restriction, including without limitation the rights
  13 // to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
  14 // copies of the Software, and to permit persons to whom the Software is
  15 // furnished to do so, subject to the following conditions:
  16 //
  17 // The above copyright notice and this permission notice shall be included in
  18 // all copies or substantial portions of the Software.
  19 //
  20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
  21 // IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
  22 // FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
  23 // AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
  24 // LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
  25 // OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
  26 // THE SOFTWARE.
  27
  28 using System;
  29 using System.Collections.Generic;
  30 using System.Threading;
  31
  32 namespace System.Threading.Tasks
  33 {
  34   internal enum PopResult       {
  35                 Succeed,
  36                 Empty,
  37                 Abort
  38         }
  39
  40         internal interface IDequeOperations<T>
  41         {
  42                 void PushBottom (T obj);
  43                 PopResult PopBottom (out T obj);
  44                 PopResult PopTop (out T obj);
  45         }
  46
  47         internal interface IValueReader
  48         {
  49                 long Read (ref long value);
  50         }
  51
  52         internal class CyclicDeque<T> : IDequeOperations<T>
  53         {
  54                 readonly IValueReader reader;
  55                 const int BaseSize = 11;
  56
  57                 class Reader32 : IValueReader
  58                 {
  59                         public long Read (ref long value)
  60                         {
  61                                 return Interlocked.Read (ref value);
  62                         }
  63                 }
  64
  65                 class Reader64 : IValueReader
  66                 {
  67                         public long Read (ref long value)
  68                         {
  69                                 return value;
  70                         }
  71                 }
  72
  73                 public CyclicDeque ()
  74                 {
  75                         // We do the distinction between 32bits and 64bits
  76                         if (IntPtr.Size == 4)
  77                                 reader = new Reader32 ();
  78                         else
  79                                 reader = new Reader64 ();
  80                 }
  81
  82                 long bottom;
  83                 long top;
  84                 long upperBound;
  85                 CircularArray<T> array = new CircularArray<T> (BaseSize);
  86
  87                 public void PushBottom (T obj)
  88                 {
  89                         long b = reader.Read (ref bottom);
  90                         var a = array;
  91
  92                         // Take care of growing
  93                         if (b - upperBound >= a.Size - 1) {
  94                                 upperBound = reader.Read (ref top);
  95                                 a = a.Grow (b, upperBound);
  96                                 Interlocked.Exchange (ref array, a);
  97                         }
  98
  99                         // Register the new value
 100                         a[b] = obj;
 101                         Interlocked.Increment (ref bottom);
 102                 }
 103
 104                 public PopResult PopBottom (out T obj)
 105                 {
 106                         obj = default (T);
 107
 108                         long b = Interlocked.Decrement (ref bottom);
 109                         var a = array;
 110                         long t = reader.Read (ref top);
 111                         long size = b - t;
 112
 113                         if (size < 0) {
 114                                 // Set bottom to t
 115                                 Interlocked.Add (ref bottom, t - b);
 116                                 return PopResult.Empty;
 117                         }
 118
 119                         obj = a[b];
 120                         if (size > 0)
 121                                 return PopResult.Succeed;
 122                         Interlocked.Add (ref bottom, t + 1 - b);
 123
 124                         if (Interlocked.CompareExchange (ref top, t + 1, t) != t)
 125                                 return PopResult.Empty;
 126
 127                         return PopResult.Succeed;
 128                 }
 129
 130                 public PopResult PopTop (out T obj)
 131                 {
 132                         obj = default (T);
 133
 134                         long t = reader.Read (ref top);
 135                         long b = reader.Read (ref bottom);
 136
 137                         if (b - t <= 0)
 138                                 return PopResult.Empty;
 139
 140                         if (Interlocked.CompareExchange (ref top, t + 1, t) != t)
 141                                 return PopResult.Abort;
 142
 143                         var a = array;
 144                         obj = a[t];
 145
 146                         return PopResult.Succeed;
 147                 }
 148
 149                 public IEnumerable<T> GetEnumerable ()
 150                 {
 151                         var a = array;
 152                         return a.GetEnumerable ();
 153                 }
 154         }
 155
 156         internal class CircularArray<T>
 157         {
 158                 readonly int baseSize;
 159                 readonly int size;
 160                 readonly T[] segment;
 161
 162                 public CircularArray (int baseSize)
 163                 {
 164                         this.baseSize = baseSize;
 165                         this.size = 1 << baseSize;
 166                         this.segment = new T[size];
 167                 }
 168
 169                 public long Size {
 170                         get {
 171                                 return size;
 172                         }
 173                 }
 174
 175                 public T this[long index] {
 176                         get {
 177                                 return segment[index % Size];
 178                         }
 179                         set {
 180                                 segment[index % Size] = value;
 181                         }
 182                 }
 183
 184                 public CircularArray<T> Grow (long bottom, long top)
 185                 {
 186                         var grow = new CircularArray<T> (baseSize + 1);
 187
 188                         for (long i = top; i < bottom; i++) {
 189                                 grow[i] = this[i];
 190                         }
 191
 192                         return grow;
 193                 }
 194
 195                 public IEnumerable<T> GetEnumerable ()
 196                 {
 197                         return ((IEnumerable<T>)segment);
 198                 }
 199         }
 200 }
 201 #endif