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