1 module ringbuffer; 2 3 /** 4 * a simple template ringbuffer, compatible with @safe, @nogc, pure and nothrow code. 5 * Authors: Susan 6 * Date: 2022-02-03 7 * Licence: AGPL-3.0 or later 8 * Copyright: Susan, 2022 9 * special thanks to my good friend flussence, whose advice while making this module was invaluable. <3 10 */ 11 12 struct RingBuffer(DataType, size_t maxLength) 13 { 14 private size_t readIndex; //todo: size_t is overkill in 99.999% of cases 15 private size_t writeIndex; 16 private DataType[maxLength] data; 17 18 private auto _length() const 19 { 20 //todo: there is almost certainly a better way to go about this 21 if (writeIndex == readIndex) 22 { 23 return 0; 24 } 25 26 immutable write = sanitize(writeIndex); 27 immutable read = sanitize(readIndex); 28 29 if (write == read) 30 { 31 return maxLength; 32 } 33 34 if (write > read) 35 { 36 return write - read; 37 } 38 else 39 { 40 return (write + maxLength) - read; 41 } 42 } 43 44 invariant(_length <= maxLength); 45 46 private auto next(in size_t rhs) @safe @nogc pure nothrow const 47 { 48 return rhs % (maxLength * 2); 49 } 50 51 private auto sanitize(in size_t rhs) @safe @nogc pure nothrow const 52 { 53 return rhs % maxLength; 54 } 55 56 /// 57 @property auto length() const 58 { 59 return _length; 60 } 61 62 /// 63 @property auto capacity() const 64 { 65 return maxLength - length; 66 } 67 68 /// assignment 69 void opAssign(in DataType[] rhs) 70 in (rhs.length <= maxLength) 71 { 72 data[0 .. rhs.length] = rhs; 73 readIndex = 0; 74 writeIndex = rhs.length; 75 } 76 77 /// push to buffer 78 void push(in DataType rhs) 79 { 80 data[sanitize(writeIndex)] = rhs; 81 writeIndex = next(writeIndex + 1); 82 } 83 84 /// ditto 85 void push(in DataType[] rhs) 86 { 87 foreach(DataType d; rhs) 88 { 89 push(d); 90 } 91 } 92 93 /// ditto 94 void opOpAssign(string op)(in DataType rhs) 95 if (op == "~") 96 in (length + 1 <= maxLength) 97 { 98 push(rhs); 99 } 100 101 /// ditto 102 void opOpAssign(string op)(in DataType[] rhs) 103 if (op == "~") 104 in (length + rhs.length <= maxLength) 105 { 106 push(rhs); 107 } 108 109 /// retrieve item from buffer (fifo) 110 DataType shift() 111 in (length > 0) 112 { 113 immutable result = data[sanitize(readIndex)]; 114 readIndex = next(readIndex + 1); 115 return result; 116 } 117 118 /// retrieve item from buffer (lifo) 119 DataType pop() 120 in (length > 0) 121 { 122 writeIndex = next(writeIndex - 1); 123 return data[sanitize(writeIndex)]; 124 } 125 126 /// empty the buffer 127 void clear() 128 { 129 data[] = DataType.init; 130 writeIndex = readIndex; 131 } 132 133 /// range interface 134 auto opIndex() const 135 { 136 return RingBufferRangeInterface!DataType(data[], readIndex, length); 137 } 138 } 139 140 /// example 141 @safe @nogc nothrow pure unittest 142 { 143 RingBuffer!(int, 5) buff; 144 buff.push(69); 145 buff ~= 420; // equivilent to the push syntax 146 assert(buff.shift == 69); 147 assert(buff.shift == 420); 148 149 import std.array : staticArray; 150 import std.range : iota; 151 immutable int[5] temp = staticArray!(iota(5)); 152 153 buff.push(temp); // multiple items may be pushed in a single call 154 155 assert(buff.length == 5); 156 assert(buff.capacity == 0); 157 158 assert(buff.pop == 4); 159 160 assert(buff.length == 4); 161 assert(buff.capacity == 1); 162 163 buff.clear(); 164 165 assert(buff.length == 0); 166 assert(buff.capacity == 5); 167 } 168 169 private struct RingBufferRangeInterface(DataType) 170 { 171 private const(DataType[]) source; 172 private size_t startIndex; 173 private size_t length; 174 175 @disable this(); 176 177 package this(in DataType[] source, in size_t startIndex, in size_t length) 178 { 179 this.source = source; 180 this.startIndex = startIndex; 181 this.length = length; 182 } 183 184 bool empty() const 185 { 186 return length == 0; 187 } 188 189 DataType front() 190 { 191 return source[startIndex % source.length]; 192 } 193 194 void popFront() 195 { 196 ++startIndex; 197 --length; 198 } 199 } 200 201 @safe @nogc nothrow pure unittest 202 { 203 RingBuffer!(int, 8) foo; 204 assert(foo.length == 0); 205 assert(foo.capacity == 8); 206 207 foo.push(0); //0 208 assert(foo.length == 1); 209 assert(foo.capacity == 7); 210 211 import std.array : staticArray; 212 import std.range : iota; 213 immutable int[5] temp = staticArray!(iota(5)); 214 215 foo ~= temp[1 .. 3]; //0, 1, 2 216 foo.push(temp[3 .. 5]); //0, 1, 2, 3, 4 217 assert(foo.length == 5); 218 assert(foo.capacity == 3); 219 220 assert(foo.shift == 0); //1, 2, 3, 4 221 assert(foo.pop == 4); //1, 2, 3 222 223 assert(foo.length == 3); 224 assert(foo.capacity == 5); 225 226 foo.push(temp); //1, 2, 3, 0, 1, 2, 3, 4 227 assert(foo.length == 8); //not empty. a nasty bug. 228 assert(foo.capacity == 0); 229 assert(foo.shift == 1); 230 231 foo.clear(); 232 assert(foo.length == 0); 233 assert(foo.capacity == 8); 234 235 foo ~= temp; 236 assert(foo.length == temp.length); 237 assert(foo.shift == 0); 238 assert(foo.pop == 4); 239 assert(foo.length == 3); 240 assert(foo.capacity == 5); 241 242 foo = temp; 243 assert(foo.shift == 0); 244 assert(foo.pop == 4); 245 assert(foo.length == 3); 246 assert(foo.capacity == 5); 247 248 foreach(i; 0 .. 100) //one last stomp 249 { 250 foo.push(i); 251 foo.shift; 252 } 253 254 immutable bar = foo; 255 256 // range test 257 int i; 258 foreach(val; bar) 259 { 260 switch(i) 261 { 262 case 0: assert(val == 97); break; 263 case 1: assert(val == 98); break; 264 case 2: assert(val == 99); break; 265 default: assert(false); 266 } 267 268 ++i; 269 } 270 }