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 	/// \class TaskQueue
35 	/// \brief thread safe task queue
36 	///
37 	template<typename T>
38 	class TaskQueue
39 	{
40 		static const int32 ALIGNMENT = 16;
41 
42 	public:
43 		static const unsigned int CAPACITY = 4096u;
44 	private:
45 		static const unsigned int MASK = CAPACITY - 1u;
46 
47 		MT::Mutex mutex;
48 
49 		void* data;
50 
51 		size_t begin;
52 		size_t end;
53 
54 		inline T* Buffer()
55 		{
56 			return (T*)(data);
57 		}
58 
59 		inline void CopyCtor(T* element, const T & val)
60 		{
61 			new(element) T(val);
62 		}
63 
64 		inline void MoveCtor(T* element, T && val)
65 		{
66 			new(element) T(std::move(val));
67 		}
68 
69 		inline void Dtor(T* element)
70 		{
71 			MT_UNUSED(element);
72 			element->~T();
73 		}
74 
75 		inline bool _IsEmpty() const
76 		{
77 			return (begin == end);
78 		}
79 
80 		inline size_t Size() const
81 		{
82 			if (_IsEmpty())
83 			{
84 				return 0;
85 			}
86 
87 			size_t count = ((end & MASK) - (begin & MASK)) & MASK;
88 			return count;
89 		}
90 
91 		inline void Clear()
92 		{
93 			size_t queueSize = Size();
94 			for (size_t i = 0; i < queueSize; i++)
95 			{
96 				T* pElement = Buffer() + ((begin + i) & MASK);
97 				Dtor(pElement);
98 			}
99 
100 			begin = 0;
101 			end = 0;
102 		}
103 
104 
105 	public:
106 
107 		MT_NOCOPYABLE(TaskQueue);
108 
109 		/// \name Initializes a new instance of the TaskQueue class.
110 		/// \brief
111 		TaskQueue()
112 			: begin(0)
113 			, end(0)
114 		{
115 			size_t bytesCount = sizeof(T) * CAPACITY;
116 			data = Memory::Alloc(bytesCount, ALIGNMENT);
117 		}
118 
119 		~TaskQueue()
120 		{
121 			if (data != nullptr)
122 			{
123 				Memory::Free(data);
124 				data = nullptr;
125 			}
126 		}
127 
128 		/// \brief Add multiple tasks onto queue.
129 		/// \param itemArray A pointer to first item. Must not be nullptr
130 		/// \param count Items count.
131 		bool Add(const T* itemArray, size_t count)
132 		{
133 			MT::ScopedGuard guard(mutex);
134 
135 			if ((Size() + count) >= CAPACITY)
136 			{
137 				return false;
138 			}
139 
140 			for (size_t i = 0; i < count; ++i)
141 			{
142 				size_t index = (end & MASK);
143 				T* pElement = Buffer() + index;
144 				CopyCtor( pElement, itemArray[i] );
145 				end++;
146 			}
147 
148 			return true;
149 		}
150 
151 
152 		/// \brief Try pop oldest item from queue.
153 		/// \param item Resultant item
154 		/// \return true on success or false if the queue is empty.
155 		bool TryPopOldest(T & item)
156 		{
157 			MT::ScopedGuard guard(mutex);
158 
159 			if (_IsEmpty())
160 			{
161 				return false;
162 			}
163 
164 			size_t index = (begin & MASK);
165 			T* pElement = Buffer() + index;
166 			begin++;
167 			item = *pElement;
168 			Dtor(pElement);
169 			return true;
170 		}
171 
172 		/// \brief Try pop a newest item (recently added) from queue.
173 		/// \param item Resultant item
174 		/// \return true on success or false if the queue is empty.
175 		bool TryPopNewest(T & item)
176 		{
177 			MT::ScopedGuard guard(mutex);
178 
179 			if (_IsEmpty())
180 			{
181 				return false;
182 			}
183 
184 			end--;
185 			size_t index = (end & MASK);
186 			T* pElement = Buffer() + index;
187 			item = *pElement;
188 			Dtor(pElement);
189 			return true;
190 		}
191 
192 		/// \brief Check if queue is empty.
193 		/// \return true - if queue is empty.
194 		bool IsEmpty()
195 		{
196 			MT::ScopedGuard guard(mutex);
197 
198 			return _IsEmpty();
199 		}
200 
201 	};
202 }
203