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 <MTPlatform.h>
26 #include <MTTools.h>
27 #include <MTAppInterop.h>
28 
29 namespace MT
30 {
31 	template<int N>
32 	struct is_power_of_two
33 	{
34 		enum {value = N && !(N & (N - 1))};
35 	};
36 
37 
38 	/// \class ConcurrentRingBuffer
39 	/// \brief Very naive implementation of thread safe ring buffer. When ring buffer is full and a subsequent write is performed, then it starts overwriting the oldest data.
40 	template<typename T, size_t numElements>
41 	class ConcurrentRingBuffer
42 	{
43 		static const int32 ALIGNMENT = 16;
44 
45 		MT::Mutex mutex;
46 
47 		void* data;
48 
49 		size_t writeIndex;
50 		size_t readIndex;
51 		size_t size;
52 
53 		inline T* Buffer()
54 		{
55 			return (T*)(data);
56 		}
57 
58 		inline void MoveCtor(T* element, T && val)
59 		{
60 			new(element) T(std::move(val));
61 		}
62 
63 		inline void Dtor(T* element)
64 		{
65 			MT_UNUSED(element);
66 			element->~T();
67 		}
68 
69 		size_t NextIndex(size_t index)
70 		{
71 			size_t ret = index + 1;
72 			size_t mask = (numElements - 1);
73 			return (ret & mask);
74 		}
75 
76 	public:
77 
78 		MT_NOCOPYABLE(ConcurrentRingBuffer);
79 
80 		ConcurrentRingBuffer()
81 			: writeIndex(0)
82 			, readIndex(0)
83 			, size(0)
84 		{
85 			data = Memory::Alloc(sizeof(T) * numElements, ALIGNMENT);
86 
87 			static_assert(is_power_of_two<numElements>::value == true, "NumElements used in MT::ConcurrentRingBuffer must be power of two");
88 		}
89 
90 		~ConcurrentRingBuffer()
91 		{
92 			Memory::Free(data);
93 			data = nullptr;
94 		}
95 
96 		void Push(T && item)
97 		{
98 			MT::ScopedGuard guard(mutex);
99 
100 			if (size >= numElements)
101 			{
102 				// RingBuffer is full. Overwrite old data.
103 				Dtor(Buffer() + readIndex);
104 				readIndex = NextIndex(readIndex);
105 			} else
106 			{
107 				size++;
108 			}
109 
110 			MoveCtor(Buffer() + writeIndex, std::move(item));
111 			writeIndex = NextIndex(writeIndex);
112 		}
113 
114 		size_t PopAll(T * dstBuffer, size_t dstBufferSize)
115 		{
116 			MT::ScopedGuard guard(mutex);
117 
118 			size_t elementsCount = size;
119 			elementsCount = MT::Min(elementsCount, dstBufferSize);
120 
121 			for (size_t i = 0; i < elementsCount; i++)
122 			{
123 				dstBuffer[i] = std::move(Buffer()[readIndex]);
124 				Dtor(Buffer() + readIndex);
125 				readIndex = NextIndex(readIndex);
126 			}
127 
128 			size -= elementsCount;
129 			return elementsCount;
130 		}
131 
132 
133 
134 
135 	};
136 
137 }
138