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 	/// \class TaskQueue
49 	/// \brief thread safe task queue
50 	///
51 	template<typename T, uint32 CAPACITY>
52 	class TaskQueue
53 	{
54 
55 		//////////////////////////////////////////////////////////////////////////
56 		class Queue
57 		{
58 			static const int32 ALIGNMENT = 16;
59 			static const unsigned int MASK = CAPACITY - 1u;
60 
61 			void* data;
62 			size_t begin;
63 			size_t end;
64 
65 			inline T* Buffer()
66 			{
67 				return (T*)(data);
68 			}
69 
70 			inline void CopyCtor(T* element, const T & val)
71 			{
72 				new(element) T(val);
73 			}
74 
75 			inline void MoveCtor(T* element, T && val)
76 			{
77 				new(element) T(std::move(val));
78 			}
79 
80 			inline void Dtor(T* element)
81 			{
82 				MT_UNUSED(element);
83 				element->~T();
84 			}
85 
86 			inline size_t Size() const
87 			{
88 				if (IsEmpty())
89 				{
90 					return 0;
91 				}
92 
93 				size_t count = ((end & MASK) - (begin & MASK)) & MASK;
94 				return count;
95 			}
96 
97 			inline void Clear()
98 			{
99 				size_t queueSize = Size();
100 				for (size_t i = 0; i < queueSize; i++)
101 				{
102 					T* pElement = Buffer() + ((begin + i) & MASK);
103 					Dtor(pElement);
104 				}
105 
106 				begin = 0;
107 				end = 0;
108 			}
109 
110 		public:
111 
112 			Queue()
113 				: begin(0)
114 				, end(0)
115 			{
116 				size_t bytesCount = sizeof(T) * CAPACITY;
117 				data = Memory::Alloc(bytesCount, ALIGNMENT);
118 			}
119 
120 			~Queue()
121 			{
122 				if (data != nullptr)
123 				{
124 					Memory::Free(data);
125 					data = nullptr;
126 				}
127 			}
128 
129 			inline bool HasSpace(size_t itemCount)
130 			{
131 				if ((Size() + itemCount) >= CAPACITY)
132 				{
133 					return false;
134 				}
135 
136 				return true;
137 			}
138 
139 			inline bool Add(const T& item)
140 			{
141 				if ((Size() + 1) >= CAPACITY)
142 				{
143 					return false;
144 				}
145 
146 				size_t index = (end & MASK);
147 				T* pElement = Buffer() + index;
148 				CopyCtor( pElement, item );
149 				end++;
150 
151 				return true;
152 			}
153 
154 
155 			inline bool TryPopOldest(T & item)
156 			{
157 				if (IsEmpty())
158 				{
159 					return false;
160 				}
161 
162 				size_t index = (begin & MASK);
163 				T* pElement = Buffer() + index;
164 				begin++;
165 				item = *pElement;
166 				Dtor(pElement);
167 				return true;
168 			}
169 
170 			inline bool TryPopNewest(T & item)
171 			{
172 				if (IsEmpty())
173 				{
174 					return false;
175 				}
176 
177 				end--;
178 				size_t index = (end & MASK);
179 				T* pElement = Buffer() + index;
180 				item = *pElement;
181 				Dtor(pElement);
182 				return true;
183 			}
184 
185 			inline bool IsEmpty() const
186 			{
187 				return (begin == end);
188 			}
189 		};
190 		//////////////////////////////////////////////////////////////////////////
191 
192 		MT::Mutex mutex;
193 		Queue queues[TaskPriority::COUNT];
194 
195 	public:
196 
197 		MT_NOCOPYABLE(TaskQueue);
198 
199 		TaskQueue()
200 		{
201 		}
202 
203 		~TaskQueue()
204 		{
205 		}
206 
207 		bool Add(const T* itemArray, size_t count)
208 		{
209 			MT::ScopedGuard guard(mutex);
210 
211 			// Check for space for all queues.
212 			// At the moment it is not known exactly in what queue items will be added.
213 			for(size_t i = 0; i < MT_ARRAY_SIZE(queues); i++)
214 			{
215 				Queue& queue = queues[i];
216 				if (!queue.HasSpace(count))
217 				{
218 					return false;
219 				}
220 			}
221 
222 			// Adding the tasks into the appropriate queue
223 			for(size_t i = 0; i < count; i++)
224 			{
225 				const T& item = itemArray[i];
226 
227 				uint32 queueIndex = (uint32)item.desc.priority;
228 				MT_ASSERT(queueIndex < MT_ARRAY_SIZE(queues), "Invalid task priority");
229 
230 				Queue& queue = queues[queueIndex];
231 				bool res = queue.Add(itemArray[i]);
232 				MT_USED_IN_ASSERT(res);
233 				MT_ASSERT(res == true, "Sanity check failed");
234 			}
235 
236 			return true;
237 		}
238 
239 
240 		bool TryPopOldest(T & item)
241 		{
242 			MT::ScopedGuard guard(mutex);
243 			for(uint32 queueIndex = 0; queueIndex < TaskPriority::COUNT; queueIndex++)
244 			{
245 				Queue& queue = queues[queueIndex];
246 				if (queue.TryPopOldest(item))
247 				{
248 					return true;
249 				}
250 			}
251 			return false;
252 		}
253 
254 		bool TryPopNewest(T & item)
255 		{
256 			MT::ScopedGuard guard(mutex);
257 			for(uint32 queueIndex = 0; queueIndex < TaskPriority::COUNT; queueIndex++)
258 			{
259 				Queue& queue = queues[queueIndex];
260 				if (queue.TryPopNewest(item))
261 				{
262 					return true;
263 				}
264 			}
265 			return false;
266 		}
267 
268 
269 	};
270 }
271