1 /*************************************************************************/
2 /*  ring_buffer.h                                                        */
3 /*************************************************************************/
4 /*                       This file is part of:                           */
5 /*                           GODOT ENGINE                                */
6 /*                      https://godotengine.org                          */
7 /*************************************************************************/
8 /* Copyright (c) 2007-2020 Juan Linietsky, Ariel Manzur.                 */
9 /* Copyright (c) 2014-2020 Godot Engine contributors (cf. AUTHORS.md).   */
10 /*                                                                       */
11 /* Permission is hereby granted, free of charge, to any person obtaining */
12 /* a copy of this software and associated documentation files (the       */
13 /* "Software"), to deal in the Software without restriction, including   */
14 /* without limitation the rights to use, copy, modify, merge, publish,   */
15 /* distribute, sublicense, and/or sell copies of the Software, and to    */
16 /* permit persons to whom the Software is furnished to do so, subject to */
17 /* the following conditions:                                             */
18 /*                                                                       */
19 /* The above copyright notice and this permission notice shall be        */
20 /* included in all copies or substantial portions of the Software.       */
21 /*                                                                       */
22 /* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,       */
23 /* EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF    */
24 /* MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.*/
25 /* IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY  */
26 /* CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,  */
27 /* TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE     */
28 /* SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.                */
29 /*************************************************************************/
30 
31 #ifndef RINGBUFFER_H
32 #define RINGBUFFER_H
33 
34 #include "core/vector.h"
35 
36 template <typename T>
37 class RingBuffer {
38 
39 	Vector<T> data;
40 	int read_pos;
41 	int write_pos;
42 	int size_mask;
43 
inc(int & p_var,int p_size)44 	inline int inc(int &p_var, int p_size) const {
45 		int ret = p_var;
46 		p_var += p_size;
47 		p_var = p_var & size_mask;
48 		return ret;
49 	};
50 
51 public:
read()52 	T read() {
53 		ERR_FAIL_COND_V(space_left() < 1, T());
54 		return data.ptr()[inc(read_pos, 1)];
55 	};
56 
57 	int read(T *p_buf, int p_size, bool p_advance = true) {
58 		int left = data_left();
59 		p_size = MIN(left, p_size);
60 		int pos = read_pos;
61 		int to_read = p_size;
62 		int dst = 0;
63 		while (to_read) {
64 			int end = pos + to_read;
65 			end = MIN(end, size());
66 			int total = end - pos;
67 			const T *read = data.ptr();
68 			for (int i = 0; i < total; i++) {
69 				p_buf[dst++] = read[pos + i];
70 			};
71 			to_read -= total;
72 			pos = 0;
73 		};
74 		if (p_advance) {
75 			inc(read_pos, p_size);
76 		};
77 		return p_size;
78 	};
79 
copy(T * p_buf,int p_offset,int p_size)80 	int copy(T *p_buf, int p_offset, int p_size) const {
81 
82 		int left = data_left();
83 		if ((p_offset + p_size) > left) {
84 			p_size -= left - p_offset;
85 			if (p_size <= 0)
86 				return 0;
87 		}
88 		p_size = MIN(left, p_size);
89 		int pos = read_pos;
90 		inc(pos, p_offset);
91 		int to_read = p_size;
92 		int dst = 0;
93 		while (to_read) {
94 			int end = pos + to_read;
95 			end = MIN(end, size());
96 			int total = end - pos;
97 			for (int i = 0; i < total; i++) {
98 				p_buf[dst++] = data[pos + i];
99 			};
100 			to_read -= total;
101 			pos = 0;
102 		};
103 		return p_size;
104 	};
105 
find(const T & t,int p_offset,int p_max_size)106 	int find(const T &t, int p_offset, int p_max_size) const {
107 
108 		int left = data_left();
109 		if ((p_offset + p_max_size) > left) {
110 			p_max_size -= left - p_offset;
111 			if (p_max_size <= 0)
112 				return 0;
113 		}
114 		p_max_size = MIN(left, p_max_size);
115 		int pos = read_pos;
116 		inc(pos, p_offset);
117 		int to_read = p_max_size;
118 		while (to_read) {
119 			int end = pos + to_read;
120 			end = MIN(end, size());
121 			int total = end - pos;
122 			for (int i = 0; i < total; i++) {
123 				if (data[pos + i] == t)
124 					return i + (p_max_size - to_read);
125 			};
126 			to_read -= total;
127 			pos = 0;
128 		}
129 		return -1;
130 	}
131 
advance_read(int p_n)132 	inline int advance_read(int p_n) {
133 		p_n = MIN(p_n, data_left());
134 		inc(read_pos, p_n);
135 		return p_n;
136 	};
137 
decrease_write(int p_n)138 	inline int decrease_write(int p_n) {
139 		p_n = MIN(p_n, data_left());
140 		inc(write_pos, size_mask + 1 - p_n);
141 		return p_n;
142 	}
143 
write(const T & p_v)144 	Error write(const T &p_v) {
145 		ERR_FAIL_COND_V(space_left() < 1, FAILED);
146 		data.write[inc(write_pos, 1)] = p_v;
147 		return OK;
148 	};
149 
write(const T * p_buf,int p_size)150 	int write(const T *p_buf, int p_size) {
151 
152 		int left = space_left();
153 		p_size = MIN(left, p_size);
154 
155 		int pos = write_pos;
156 		int to_write = p_size;
157 		int src = 0;
158 		while (to_write) {
159 
160 			int end = pos + to_write;
161 			end = MIN(end, size());
162 			int total = end - pos;
163 
164 			for (int i = 0; i < total; i++) {
165 				data.write[pos + i] = p_buf[src++];
166 			};
167 			to_write -= total;
168 			pos = 0;
169 		};
170 
171 		inc(write_pos, p_size);
172 		return p_size;
173 	};
174 
space_left()175 	inline int space_left() const {
176 		int left = read_pos - write_pos;
177 		if (left < 0) {
178 			return size() + left - 1;
179 		};
180 		if (left == 0) {
181 			return size() - 1;
182 		};
183 		return left - 1;
184 	};
data_left()185 	inline int data_left() const {
186 		return size() - space_left() - 1;
187 	};
188 
size()189 	inline int size() const {
190 		return data.size();
191 	};
192 
clear()193 	inline void clear() {
194 		read_pos = 0;
195 		write_pos = 0;
196 	}
197 
resize(int p_power)198 	void resize(int p_power) {
199 		int old_size = size();
200 		int new_size = 1 << p_power;
201 		int mask = new_size - 1;
202 		data.resize(1 << p_power);
203 		if (old_size < new_size && read_pos > write_pos) {
204 			for (int i = 0; i < write_pos; i++) {
205 				data.write[(old_size + i) & mask] = data[i];
206 			};
207 			write_pos = (old_size + write_pos) & mask;
208 		} else {
209 			read_pos = read_pos & mask;
210 			write_pos = write_pos & mask;
211 		};
212 
213 		size_mask = mask;
214 	};
215 
216 	RingBuffer<T>(int p_power = 0) {
217 		read_pos = 0;
218 		write_pos = 0;
219 		resize(p_power);
220 	};
221 	~RingBuffer<T>(){};
222 };
223 
224 #endif
225