1 // The MIT License (MIT)
2 //
3 // 	Copyright (c) 2015 Sergey Makeev, Vadim Slyusarev
4 //
5 // 	Permission is hereby granted, free of charge, to any person obtaining a copy
6 // 	of this software and associated documentation files (the "Software"), to deal
7 // 	in the Software without restriction, including without limitation the rights
8 // 	to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
9 // 	copies of the Software, and to permit persons to whom the Software is
10 // 	furnished to do so, subject to the following conditions:
11 //
12 //  The above copyright notice and this permission notice shall be included in
13 // 	all copies or substantial portions of the Software.
14 //
15 // 	THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
16 // 	IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
17 // 	FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
18 // 	AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
19 // 	LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
20 // 	OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
21 // 	THE SOFTWARE.
22 
23 #pragma once
24 
25 #include <vector>
26 
27 #include <MTPlatform.h>
28 #include <MTTools.h>
29 #include <MTAppInterop.h>
30 
31 
32 namespace MT
33 {
34 	namespace TaskPriority
35 	{
36 		enum Type
37 		{
38 			HIGH = 0,
39 			NORMAL = 1,
40 			LOW = 2,
41 
42 			COUNT,
43 
44 			INVALID
45 		};
46 	}
47 
48 	namespace DummyQueueFlag
49 	{
50 		enum Type
51 		{
52 			IS_DUMMY_QUEUE = 1
53 		};
54 	}
55 
56 
57 	/// \class TaskQueue
58 	/// \brief thread safe task queue
59 	///
60 	template<typename T, uint32 CAPACITY>
61 	class TaskQueue
62 	{
63 		//////////////////////////////////////////////////////////////////////////
64 		class Queue
65 		{
66 			static const int32 ALIGNMENT = 16;
67 			static const unsigned int MASK = CAPACITY - 1u;
68 
69 			void* data;
70 			size_t begin;
71 			size_t end;
72 
73 			inline T* Buffer()
74 			{
75 				return (T*)(data);
76 			}
77 
78 			inline void CopyCtor(T* element, const T & val)
79 			{
80 				new(element) T(val);
81 			}
82 
83 			inline void MoveCtor(T* element, T && val)
84 			{
85 				new(element) T(std::move(val));
86 			}
87 
88 			inline void Dtor(T* element)
89 			{
90 				MT_UNUSED(element);
91 				element->~T();
92 			}
93 
94 			inline size_t Size() const
95 			{
96 				if (IsEmpty())
97 				{
98 					return 0;
99 				}
100 
101 				size_t count = ((end & MASK) - (begin & MASK)) & MASK;
102 				return count;
103 			}
104 
105 			inline void Clear()
106 			{
107 				size_t queueSize = Size();
108 				for (size_t i = 0; i < queueSize; i++)
109 				{
110 					T* pElement = Buffer() + ((begin + i) & MASK);
111 					Dtor(pElement);
112 				}
113 
114 				begin = 0;
115 				end = 0;
116 			}
117 
118 		public:
119 
120 			Queue()
121 				: data(nullptr)
122 				, begin(0)
123 				, end(0)
124 			{
125 			}
126 
127 			// Queue is just dummy until you call the Create
128 			void Create()
129 			{
130 				size_t bytesCount = sizeof(T) * CAPACITY;
131 				data = Memory::Alloc(bytesCount, ALIGNMENT);
132 			}
133 
134 
135 			~Queue()
136 			{
137 				if (data != nullptr)
138 				{
139 					Memory::Free(data);
140 					data = nullptr;
141 				}
142 			}
143 
144 			inline bool HasSpace(size_t itemCount)
145 			{
146 				if ((Size() + itemCount) >= CAPACITY)
147 				{
148 					return false;
149 				}
150 
151 				return true;
152 			}
153 
154 			inline bool Add(const T& item)
155 			{
156 				MT_VERIFY(data, "Can't add items to dummy queue", return false; );
157 
158 				if ((Size() + 1) >= CAPACITY)
159 				{
160 					return false;
161 				}
162 
163 				size_t index = (end & MASK);
164 				T* pElement = Buffer() + index;
165 				CopyCtor( pElement, item );
166 				end++;
167 
168 				return true;
169 			}
170 
171 
172 			inline bool TryPopOldest(T & item)
173 			{
174 				if (IsEmpty())
175 				{
176 					return false;
177 				}
178 
179 				MT_VERIFY(data, "Can't pop items from dummy queue", return false; );
180 
181 				size_t index = (begin & MASK);
182 				T* pElement = Buffer() + index;
183 				begin++;
184 				item = *pElement;
185 				Dtor(pElement);
186 				return true;
187 			}
188 
189 			inline bool TryPopNewest(T & item)
190 			{
191 				if (IsEmpty())
192 				{
193 					return false;
194 				}
195 
196 				MT_VERIFY(data, "Can't pop items from dummy queue", return false; );
197 
198 				end--;
199 				size_t index = (end & MASK);
200 				T* pElement = Buffer() + index;
201 				item = *pElement;
202 				Dtor(pElement);
203 				return true;
204 			}
205 
206 			inline bool IsEmpty() const
207 			{
208 				return (begin == end);
209 			}
210 		};
211 		//////////////////////////////////////////////////////////////////////////
212 
213 		MT::Mutex mutex;
214 		Queue queues[TaskPriority::COUNT];
215 
216 	public:
217 
218 		MT_NOCOPYABLE(TaskQueue);
219 
220 		TaskQueue()
221 		{
222 			for(uint32 i = 0; i < MT_ARRAY_SIZE(queues); i++)
223 			{
224 				queues[i].Create();
225 			}
226 		}
227 
228 		TaskQueue(DummyQueueFlag::Type)
229 		{
230 			// Create dummy queue.
231 		}
232 
233 		~TaskQueue()
234 		{
235 		}
236 
237 		bool Add(const T* itemArray, size_t count)
238 		{
239 			MT::ScopedGuard guard(mutex);
240 
241 			// Check for space for all queues.
242 			// At the moment it is not known exactly in what queue items will be added.
243 			for(size_t i = 0; i < MT_ARRAY_SIZE(queues); i++)
244 			{
245 				Queue& queue = queues[i];
246 				if (!queue.HasSpace(count))
247 				{
248 					return false;
249 				}
250 			}
251 
252 			// Adding the tasks into the appropriate queue
253 			for(size_t i = 0; i < count; i++)
254 			{
255 				const T& item = itemArray[i];
256 
257 				uint32 queueIndex = (uint32)item.desc.priority;
258 				MT_ASSERT(queueIndex < MT_ARRAY_SIZE(queues), "Invalid task priority");
259 
260 				Queue& queue = queues[queueIndex];
261 				bool res = queue.Add(itemArray[i]);
262 				MT_USED_IN_ASSERT(res);
263 				MT_ASSERT(res == true, "Sanity check failed");
264 			}
265 
266 			return true;
267 		}
268 
269 
270 		bool TryPopOldest(T & item)
271 		{
272 			MT::ScopedGuard guard(mutex);
273 			for(uint32 queueIndex = 0; queueIndex < TaskPriority::COUNT; queueIndex++)
274 			{
275 				Queue& queue = queues[queueIndex];
276 				if (queue.TryPopOldest(item))
277 				{
278 					return true;
279 				}
280 			}
281 			return false;
282 		}
283 
284 		bool TryPopNewest(T & item)
285 		{
286 			MT::ScopedGuard guard(mutex);
287 			for(uint32 queueIndex = 0; queueIndex < TaskPriority::COUNT; queueIndex++)
288 			{
289 				Queue& queue = queues[queueIndex];
290 				if (queue.TryPopNewest(item))
291 				{
292 					return true;
293 				}
294 			}
295 			return false;
296 		}
297 
298 
299 	};
300 }
301