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