001/* 002Copyright (c) 2022-2023 Steve Shering 003 004All rights reserved. 005 006As a special exception, the copyright holder of this software gives you permission 007to use this software for personal, not-for-profit purposes. 008 009For any other purpose, a license must be obtained from the copyright holder. 010 011This copyright notice and this permission notice must be included in all copies 012of this software, including copies of parts of this software. 013 014THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR 015IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, 016FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE 017AUTHOR OR COPYRIGHT HOLDER BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER 018LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, 019OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN 020THE SOFTWARE. 021*/ 022package net.sherst.util; 023 024import java.io.Reader; 025import java.util.Collection; 026 027/** 028 * A thread-safe ring buffer (circular buffer) implementation for Java. 029 * <p> 030 * A ring buffer is a fixed-size first in - first out buffer 031 * typically backed by an array with head and tail pointers. 032 * Elements are added to the tail of the buffer and removed from the head. 033 * When the end of the array is reached, the pointers wrap around to the beginning. 034 * When the buffer is full, adding new elements overwrites the oldest elements 035 * (but see the {@link offer(E)} and {@link offer(E[])} methods in this implementation). 036 * <p> 037 * Pros: Fast, simple. 038 * <p> 039 * Cons: Size fixed at creation time, 040 * adding new elements overwrites the oldest ones if the buffer is full, 041 * elements can only be added or removed in FIFO order. 042 * <p> 043 * There are some useful look-ahead methods, {@link #peek()}, {@link #peek(int)}, {@link #at(E)}, 044 * {@link #at(E[])}, {@link #atSkip(E)} 045 * and {@link #atSkip(E[])}. 046 * <p> 047 * These are simple, hopefully fast, implementations. 048 * They deliberately do not implement Java's {@link java.util.Collection} or {@link java.util.Queue} interfaces, 049 * although the API is similar. 050 * <p> 051 * Variants:<ul> 052 * <li>{@link FastRingBuffer}: Simplest, fastest, not thread safe. 053 * <li>{@link SafeRingBuffer}: Thread safe. 054 * <li>{@link BlockingRingBuffer}: add and remove methods block if necessary; offer and poll methods are non-blocking. 055 * </ul> 056 * <p> 057 * {@link #remove()} sets the underlying array slot to {@code null} to avoid memory leaks. 058 * All other {@code remove} and {@code poll} methods call {@link #remove()}. 059 * <p> 060 * {@link #clear()} discards the underlying array to avoid memory leaks. 061 * {@link #removeAll()} calls {@link #clear()}. 062 * <p> 063 * Elements can be {@code null}, but this means that, 064 * if {@link #peek()}, {@link #poll()} or {@link #remove()} return null, 065 * this could be because an element was {@code null} or because the buffer was empty. 066 * Consider using {@link #isEmpty()} or {@link #size()} to disambiguate. 067 * <p> 068 * {@link #poll()} might seem redundant, but is overridden in {@link BlockingRingBuffer}. 069 * 070 * @param <E> the type of elements in the buffer 071 * @author sherstDotNet@yahoo.com 072 */ 073public class SafeRingBuffer<E> extends net.sherst.util.FastRingBuffer<E> { 074 075 /** 076 * Creates a new buffer. 077 * 078 * @param capacity Maximum capacity of the buffer 079 */ 080 public SafeRingBuffer(int capacity) { 081 super(capacity); 082 } 083 084 /** 085 * Adds an element to the buffer. 086 * If the buffer is full, silently overwrites the oldest element. 087 * 088 * @param e the element to add 089 */ 090 @Override 091 public synchronized boolean add(E e) { 092 return super.add(e); 093 } 094 095 /** 096 * Adds elements to the buffer, preserving their ordering in the array. 097 * If the buffer is full, silently overwrites the oldest elements. 098 * 099 * @param a the elements to add 100 * @return <b>true</b> 101 */ 102 @Override 103 public synchronized boolean addAll(E[] a) { 104 return super.addAll(a); 105 } 106 107 /** 108 * Adds elements to the buffer, preserving their ordering in the collection. 109 * If the buffer is full, silently overwrites the oldest elements. 110 * 111 * @param c the elements to add 112 * @return <b>true</b> 113 */ 114 @Override 115 public synchronized boolean addAll(Collection<E> c) { 116 return super.addAll(c); 117 } 118 119 /** 120 * Returns {@code true} if the head of the buffer (the next element that will be removed) 121 * is equal to {@code o}, 122 * compared using {@link java.util.Objects#equals}. 123 * 124 * @param o the value to be compared 125 * @return {@code true} if the head of the buffer equals {@code o}; 126 * {@code false} if the buffer is empty 127 */ 128 @Override 129 public synchronized boolean at(E o) { 130 return super.at(o); 131 } 132 133 /** 134 * Returns {@code true} if the elements at the head of the buffer (the next elements that will be removed) 135 * are equal to the contents of {@code a}, 136 * compared using {@link java.util.Objects#equals}. 137 * 138 * @param a the values to be compared 139 * @return {@code true} if the elements at head of the buffer are equal to the elements of {@code a}; 140 * {@code false} if the buffer doesn't contain enough elements to match. 141 */ 142 @Override 143 public synchronized boolean at(E[] a) { 144 return super.at(a); 145 } 146 147 /** 148 * Compares the head of the buffer (the next element that will be removed) to {@code o} 149 * using {@link java.util.Objects#equals} 150 * and removes it from the buffer if there is a match. 151 * 152 * @param o the value to be compared 153 * @return {@code true} if the head of the buffer equals {@code o} and is removed; 154 * {@code false} if the buffer is empty 155 */ 156 @Override 157 public synchronized boolean atSkip(E o) { 158 return super.atSkip(o); 159 } 160 161 /** 162 * Compares the head of the buffer (the next elements that will be removed) to {@code a} 163 * using {@link java.util.Objects#equals} 164 * and removes them from the buffer if there is a match. 165 * 166 * @param a the values to be compared 167 * @return {@code true} if the elements at head of the buffer are equal to the elements of {@code a}; 168 * {@code false} if the buffer doesn't contain enough elements to match. 169 */ 170 @Override 171 public synchronized boolean atSkip(E[] a) { 172 return super.atSkip(a); 173 } 174 175 /** 176 * Empties the buffer. 177 */ 178 @Override 179 public synchronized void clear() { 180 super.clear(); 181 notifyAll(); 182 } 183 184 /** 185 * Returns the maximum capacity of this buffer. 186 * 187 * @return the maximum capacity of this buffer 188 */ 189 @Override 190 public int getCapacity() { 191 return super.getCapacity(); 192 } 193 194 /** 195 * Returns {@code true} if the buffer is empty. 196 * 197 * @return {@code true} if the buffer is empty 198 */ 199 @Override 200 public synchronized boolean isEmpty() { 201 return super.isEmpty(); 202 } 203 204 /** 205 * Adds an element to the buffer if there is space for it. 206 * 207 * @param e the element to add. 208 * @return {@code true} if there was space in the buffer and the element was added 209 */ 210 @Override 211 public synchronized boolean offer(E e) { 212 return super.offer(e); 213 } 214 215 /** 216 * Adds elements to the buffer if there is space for them. 217 * 218 * @param e the element to add. 219 * @return {@code true} if there was space in the buffer and the elements were added 220 */ 221 @Override 222 public synchronized boolean offer(E[] a) { 223 return super.offer(a); 224 } 225 226 /** 227 * Adds elements to the buffer if there is space for them. 228 * 229 * @param e the element to add. 230 * @return {@code true} if there was space in the buffer and the elements were added 231 */ 232 @Override 233 public synchronized boolean offer(Collection<E> c) { 234 return super.offer(c); 235 } 236 237 /** 238 * Returns the head of the buffer (the next element that will be removed) without actually removing it. 239 * 240 * @return the element at the head of the buffer or {@code null} if the buffer is empty 241 */ 242 @Override 243 public synchronized E peek() { 244 return super.peek(); 245 } 246 247 /** 248 * Returns the {@code n}<i>th</i> element that will be removed from the buffer, 249 * counting from 0 ({@code peek(0)} returns the first element that will be removed), 250 * or {@code null} if the buffer does not contain that many elements. 251 * 252 * @param n 253 * @return the {@code n}<i>th</i> element that will be removed from the buffer 254 * or {@code null} if the buffer does not contain that many elements 255 */ 256 @Override 257 public synchronized E peek(int n) { 258 return super.peek(n); 259 } 260 261 /** 262 * Removes and returns the element at the head of the buffer, 263 * or {@code null} if the buffer is empty. 264 * 265 * @return the element that was at the head of the buffer which was removed, 266 * or {@code null} if the buffer is empty 267 */ 268 @Override 269 public synchronized E poll() { 270 return super.poll(); 271 } 272 273 /** 274 * Removes and returns {@code n} consecutive elements from the head of the buffer 275 * in the order they were added, or {@code null} if the buffer does not contain {@code n} elements. 276 * 277 * @param n the number of elements to remove 278 * @param cls the {@code Class} of the elements in the buffer (needed to create the array) 279 * @return the elements that were at the head of the buffer which were removed, 280 * or {@code null} if the buffer does not contain {@code n} elements 281 */ 282 @Override 283 public synchronized E[] poll(int n, Class<E> cls) { 284 return super.poll(n, cls); 285 } 286 287 /** 288 * Removes and returns the element at the head of the buffer, 289 * or {@code null} if the buffer is empty. 290 * 291 * @return the element that was at the head of the buffer which was removed, 292 * or {@code null} if the buffer is empty 293 */ 294 @Override 295 public synchronized E remove() { 296 return super.remove(); 297 } 298 299 /** 300 * Removes and returns up to {@code n} consecutive elements from the head of the buffer 301 * in the order they were added. 302 * 303 * @param n the number of elements to remove 304 * @param cls the {@code Class} of the elements in the buffer (needed to create the array) 305 * @return the elements that were at the head of the buffer which were removed; 306 * the length of the array reflects the number of elements that were available 307 */ 308 @Override 309 public synchronized E[] remove(int n, Class<E> cls) { 310 return super.remove(n, cls); 311 } 312 313/** 314* Empties the buffer. 315* 316* @return {@code true} 317*/ 318 @Override 319 public synchronized boolean removeAll() { 320 return super.removeAll(); 321 } 322 323 /** 324 * Returns the number of elements in the buffer. 325 * 326 * @return the number of elements in the buffer 327 */ 328 @Override 329 public synchronized int size() { 330 return super.size(); 331 } 332 333 /** 334 * Removes {@code n} elements from the head of the buffer (and discards them). 335 * If {@code n}>{@link size()}, only {@link size()} elements are removed. 336 * Does not block if the buffer is empty. 337 * Inspired by and named after similar methods in 338 * {@link java.io.InputStream}s and {@link Reader}s. 339 * 340 * @param n the number of elements to remove 341 * @return the number of elements actually removed 342 */ 343 @Override 344 public synchronized int skip(int n) { 345 return super.skip(n); 346 } 347 }