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 <MTAllocator.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 		MT::Mutex mutex;
44 
45 		void* data;
46 
47 		size_t writeIndex;
48 		size_t readIndex;
49 		size_t size;
50 
51 		inline T* Buffer()
52 		{
53 			return (T*)(data);
54 		}
55 
56 		inline void MoveCtor(T* element, T && val)
57 		{
58 			new(element) T(std::move(val));
59 		}
60 
61 		inline void Dtor(T* element)
62 		{
63 			MT_UNUSED(element);
64 			element->~T();
65 		}
66 
67 		size_t NextIndex(size_t index)
68 		{
69 			size_t ret = index + 1;
70 			size_t mask = (numElements - 1);
71 			return (ret & mask);
72 		}
73 
74 	public:
75 
76 		MT_NOCOPYABLE(ConcurrentRingBuffer);
77 
78 		ConcurrentRingBuffer()
79 			: writeIndex(0)
80 			, readIndex(0)
81 			, size(0)
82 		{
83 			data = Memory::Alloc(sizeof(T) * numElements);
84 
85 			static_assert(is_power_of_two<numElements>::value == true, "NumElements used in MT::ConcurrentRingBuffer must be power of two");
86 		}
87 
88 		~ConcurrentRingBuffer()
89 		{
90 			Memory::Free(data);
91 			data = nullptr;
92 		}
93 
94 		void Push(T && item)
95 		{
96 			MT::ScopedGuard guard(mutex);
97 
98 			if (size >= numElements)
99 			{
100 				// RingBuffer is full. Overwrite old data.
101 				Dtor(Buffer() + readIndex);
102 				readIndex = NextIndex(readIndex);
103 			} else
104 			{
105 				size++;
106 			}
107 
108 			MoveCtor(Buffer() + writeIndex, std::move(item));
109 			writeIndex = NextIndex(writeIndex);
110 		}
111 
112 		size_t PopAll(T * dstBuffer, size_t dstBufferSize)
113 		{
114 			MT::ScopedGuard guard(mutex);
115 
116 			size_t elementsCount = size;
117 			elementsCount = MT::Min(elementsCount, dstBufferSize);
118 
119 			for (size_t i = 0; i < elementsCount; i++)
120 			{
121 				dstBuffer[i] = std::move(Buffer()[readIndex]);
122 				Dtor(Buffer() + readIndex);
123 				readIndex = NextIndex(readIndex);
124 			}
125 
126 			size -= elementsCount;
127 			return elementsCount;
128 		}
129 
130 
131 
132 
133 	};
134 
135 }