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