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