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