GlueGen v2.6.0-rc-20250712
GlueGen, Native Binding Generator for Java™ (public API).
LFRingbuffer.java
Go to the documentation of this file.
1/**
2 * Copyright 2013 JogAmp Community. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without modification, are
5 * permitted provided that the following conditions are met:
6 *
7 * 1. Redistributions of source code must retain the above copyright notice, this list of
8 * conditions and the following disclaimer.
9 *
10 * 2. Redistributions in binary form must reproduce the above copyright notice, this list
11 * of conditions and the following disclaimer in the documentation and/or other materials
12 * provided with the distribution.
13 *
14 * THIS SOFTWARE IS PROVIDED BY JogAmp Community ``AS IS'' AND ANY EXPRESS OR IMPLIED
15 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND
16 * FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL JogAmp Community OR
17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
18 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
19 * SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON
20 * ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
21 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
22 * ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
23 *
24 * The views and conclusions contained in the software and documentation are those of the
25 * authors and should not be interpreted as representing official policies, either expressed
26 * or implied, of JogAmp Community.
27 */
28
29package com.jogamp.common.util;
30
31import java.io.PrintStream;
32import java.lang.reflect.Array;
33
34/**
35 * Simple implementation of {@link Ringbuffer},
36 * exposing <i>lock-free</i>
37 * {@link #get() get*(..)} and {@link #put(Object) put*(..)} methods.
38 * <p>
39 * Implementation utilizes the <i>Always Keep One Slot Open</i>,
40 * hence implementation maintains an internal array of <code>capacity</code> <i>plus one</i>!
41 * </p>
42 * <p>
43 * Implementation is thread safe if:
44 * <ul>
45 * <li>{@link #get() get*(..)} operations are performed from one thread only.</li>
46 * <li>{@link #put(Object) put*(..)} operations are performed from one thread only.</li>
47 * <li>{@link #get() get*(..)} and {@link #put(Object) put*(..)} thread may be the same.</li>
48 * </ul>
49 * </p>
50 * <p>
51 * Following methods utilize global synchronization:
52 * <ul>
53 * <li>{@link #resetFull(Object[])}</li>
54 * <li>{@link #clear()}</li>
55 * <li>{@link #growEmptyBuffer(Object[])}</li>
56 * </ul>
57 * User needs to synchronize above methods w/ the lock-free
58 * w/ {@link #get() get*(..)} and {@link #put(Object) put*(..)} methods,
59 * e.g. by controlling their threads before invoking the above.
60 * </p>
61 * <p>
62 * Characteristics:
63 * <ul>
64 * <li>Read position points to the last read element.</li>
65 * <li>Write position points to the last written element.</li>
66 * </ul>
67 * <table border="1">
68 * <tr><td>Empty</td><td>writePos == readPos</td><td>size == 0</td></tr>
69 * <tr><td>Full</td><td>writePos == readPos - 1</td><td>size == capacity</td></tr>
70 * </table>
71 * </p>
72 */
73public class LFRingbuffer<T> implements Ringbuffer<T> {
74
75 private final Object syncRead = new Object();
76 private final Object syncWrite = new Object();
77 private final Object syncGlobal = new Object();
78 private /* final */ volatile T[] array; // not final due to grow
79 private /* final */ volatile int capacityPlusOne; // not final due to grow
80 private volatile int readPos;
81 private volatile int writePos;
82 private volatile int size;
83
84 @Override
85 public final String toString() {
86 return "LFRingbuffer<?>[filled "+size+" / "+(capacityPlusOne-1)+", writePos "+writePos+", readPos "+readPos+"]";
87 }
88
89 @Override
90 public final void dump(final PrintStream stream, final String prefix) {
91 stream.println(prefix+" "+toString()+" {");
92 for(int i=0; i<capacityPlusOne; i++) {
93 stream.println("\t["+i+"]: "+array[i]);
94 }
95 stream.println("}");
96 }
97
98 /**
99 * Create a full ring buffer instance w/ the given array's net capacity and content.
100 * <p>
101 * Example for a 10 element Integer array:
102 * <pre>
103 * Integer[] source = new Integer[10];
104 * // fill source with content ..
105 * Ringbuffer<Integer> rb = new LFRingbuffer<Integer>(source);
106 * </pre>
107 * </p>
108 * <p>
109 * {@link #isFull()} returns true on the newly created full ring buffer.
110 * </p>
111 * <p>
112 * Implementation will allocate an internal array with size of array <code>copyFrom</code> <i>plus one</i>,
113 * and copy all elements from array <code>copyFrom</code> into the internal array.
114 * </p>
115 * @param copyFrom mandatory source array determining ring buffer's net {@link #capacity()} and initial content.
116 * @throws IllegalArgumentException if <code>copyFrom</code> is <code>null</code>
117 */
118 @SuppressWarnings("unchecked")
119 public LFRingbuffer(final T[] copyFrom) throws IllegalArgumentException {
120 capacityPlusOne = copyFrom.length + 1;
121 array = (T[]) newArray(copyFrom.getClass(), capacityPlusOne);
122 resetImpl(true, copyFrom);
123 }
124
125 /**
126 * Create an empty ring buffer instance w/ the given net <code>capacity</code>.
127 * <p>
128 * Example for a 10 element Integer array:
129 * <pre>
130 * Ringbuffer<Integer> rb = new LFRingbuffer<Integer>(10, Integer[].class);
131 * </pre>
132 * </p>
133 * <p>
134 * {@link #isEmpty()} returns true on the newly created empty ring buffer.
135 * </p>
136 * <p>
137 * Implementation will allocate an internal array of size <code>capacity</code> <i>plus one</i>.
138 * </p>
139 * @param arrayType the array type of the created empty internal array.
140 * @param capacity the initial net capacity of the ring buffer
141 */
142 public LFRingbuffer(final Class<? extends T[]> arrayType, final int capacity) {
143 capacityPlusOne = capacity+1;
144 array = newArray(arrayType, capacityPlusOne);
145 resetImpl(false, null /* empty, nothing to copy */ );
146 }
147
148 @Override
149 public final int capacity() { return capacityPlusOne-1; }
150
151 @Override
152 public final void clear() {
153 synchronized ( syncGlobal ) {
154 resetImpl(false, null);
155 for(int i=0; i<capacityPlusOne; i++) {
156 this.array[i] = null;
157 }
158 }
159 }
160
161 @Override
162 public final void resetFull(final T[] copyFrom) throws IllegalArgumentException {
163 resetImpl(true, copyFrom);
164 }
165
166 private final void resetImpl(final boolean full, final T[] copyFrom) throws IllegalArgumentException {
167 synchronized ( syncGlobal ) {
168 if( null != copyFrom ) {
169 if( copyFrom.length != capacityPlusOne-1 ) {
170 throw new IllegalArgumentException("copyFrom array length "+copyFrom.length+" != capacity "+this);
171 }
172 System.arraycopy(copyFrom, 0, array, 0, copyFrom.length);
173 array[capacityPlusOne-1] = null; // null 'plus-one' field!
174 } else if ( full ) {
175 throw new IllegalArgumentException("copyFrom array is null");
176 }
177 readPos = capacityPlusOne - 1;
178 if( full ) {
179 writePos = readPos - 1;
180 size = capacityPlusOne - 1;
181 } else {
182 writePos = readPos;
183 size = 0;
184 }
185 }
186 }
187
188 @Override
189 public final int size() { return size; }
190
191 @Override
192 public final int getFreeSlots() { return capacityPlusOne - 1 - size; }
193
194 @Override
195 public final boolean isEmpty() { return 0 == size; }
196
197 @Override
198 public final boolean isFull() { return capacityPlusOne - 1 == size; }
199
200 /**
201 * {@inheritDoc}
202 * <p>
203 * Implementation advances the read position and returns the element at it, if not empty.
204 * </p>
205 */
206 @Override
207 public final T get() {
208 try {
209 return getImpl(false, false);
210 } catch (final InterruptedException ie) { throw new RuntimeException(ie); }
211 }
212
213 /**
214 * {@inheritDoc}
215 * <p>
216 * Implementation advances the read position and returns the element at it, if not empty.
217 * </p>
218 */
219 @Override
220 public final T getBlocking() throws InterruptedException {
221 return getImpl(true, false);
222 }
223
224 @Override
225 public final T peek() {
226 try {
227 return getImpl(false, true);
228 } catch (final InterruptedException ie) { throw new RuntimeException(ie); }
229 }
230 @Override
231 public final T peekBlocking() throws InterruptedException {
232 return getImpl(true, true);
233 }
234
235 private final T getImpl(final boolean blocking, final boolean peek) throws InterruptedException {
236 int localReadPos = readPos;
237 if( localReadPos == writePos ) {
238 if( blocking ) {
239 synchronized( syncRead ) {
240 while( localReadPos == writePos ) {
241 syncRead.wait();
242 }
243 }
244 } else {
245 return null;
246 }
247 }
248 localReadPos = (localReadPos + 1) % capacityPlusOne;
249 final T r = array[localReadPos];
250 if( !peek ) {
251 array[localReadPos] = null;
252 synchronized ( syncWrite ) {
253 size--;
254 readPos = localReadPos;
255 syncWrite.notifyAll(); // notify waiting putter
256 }
257 }
258 return r;
259 }
260
261 /**
262 * {@inheritDoc}
263 * <p>
264 * Implementation advances the write position and stores the given element at it, if not full.
265 * </p>
266 */
267 @Override
268 public final boolean put(final T e) {
269 try {
270 return putImpl(e, false, false);
271 } catch (final InterruptedException ie) { throw new RuntimeException(ie); }
272 }
273
274 /**
275 * {@inheritDoc}
276 * <p>
277 * Implementation advances the write position and stores the given element at it, if not full.
278 * </p>
279 */
280 @Override
281 public final void putBlocking(final T e) throws InterruptedException {
282 if( !putImpl(e, false, true) ) {
283 throw new InternalError("Blocking put failed: "+this);
284 }
285 }
286
287 /**
288 * {@inheritDoc}
289 * <p>
290 * Implementation advances the write position and keeps the element at it, if not full.
291 * </p>
292 */
293 @Override
294 public final boolean putSame(final boolean blocking) throws InterruptedException {
295 return putImpl(null, true, blocking);
296 }
297
298 private final boolean putImpl(final T e, final boolean sameRef, final boolean blocking) throws InterruptedException {
299 int localWritePos = writePos;
300 localWritePos = (localWritePos + 1) % capacityPlusOne;
301 if( localWritePos == readPos ) {
302 if( blocking ) {
303 synchronized( syncWrite ) {
304 while( localWritePos == readPos ) {
305 syncWrite.wait();
306 }
307 }
308 } else {
309 return false;
310 }
311 }
312 if( !sameRef ) {
313 array[localWritePos] = e;
314 }
315 synchronized ( syncRead ) {
316 size++;
317 writePos = localWritePos;
318 syncRead.notifyAll(); // notify waiting getter
319 }
320 return true;
321 }
322
323
324 @Override
325 public final void waitForFreeSlots(final int count) throws InterruptedException {
326 synchronized ( syncRead ) {
327 if( capacityPlusOne - 1 - size < count ) {
328 while( capacityPlusOne - 1 - size < count ) {
329 syncRead.wait();
330 }
331 }
332 }
333 }
334
335 @Override
336 public final void growEmptyBuffer(final T[] newElements) throws IllegalStateException, IllegalArgumentException {
337 synchronized( syncGlobal ) {
338 if( null == newElements ) {
339 throw new IllegalArgumentException("newElements is null");
340 }
341 @SuppressWarnings("unchecked")
342 final Class<? extends T[]> arrayTypeInternal = (Class<? extends T[]>) array.getClass();
343 @SuppressWarnings("unchecked")
344 final Class<? extends T[]> arrayTypeNew = (Class<? extends T[]>) newElements.getClass();
345 if( arrayTypeInternal != arrayTypeNew ) {
346 throw new IllegalArgumentException("newElements array-type mismatch, internal "+arrayTypeInternal+", newElements "+arrayTypeNew);
347 }
348 if( 0 != size ) {
349 throw new IllegalStateException("Buffer is not empty: "+this);
350 }
351 if( readPos != writePos ) {
352 throw new InternalError("R/W pos not equal: "+this);
353 }
354 if( readPos != writePos ) {
355 throw new InternalError("R/W pos not equal at empty: "+this);
356 }
357
358 final int growAmount = newElements.length;
359 final int newCapacity = capacityPlusOne + growAmount;
360 final T[] oldArray = array;
361 final T[] newArray = newArray(arrayTypeInternal, newCapacity);
362
363 // writePos == readPos
364 writePos += growAmount; // warp writePos to the end of the new data location
365
366 if( readPos >= 0 ) {
367 System.arraycopy(oldArray, 0, newArray, 0, readPos+1);
368 }
369 if( growAmount > 0 ) {
370 System.arraycopy(newElements, 0, newArray, readPos+1, growAmount);
371 }
372 final int tail = capacityPlusOne-1-readPos;
373 if( tail > 0 ) {
374 System.arraycopy(oldArray, readPos+1, newArray, writePos+1, tail);
375 }
376 size = growAmount;
377
378 capacityPlusOne = newCapacity;
379 array = newArray;
380 }
381 }
382
383 @Override
384 public final void growFullBuffer(final int growAmount) throws IllegalStateException, IllegalArgumentException {
385 synchronized ( syncGlobal ) {
386 if( 0 > growAmount ) {
387 throw new IllegalArgumentException("amount "+growAmount+" < 0 ");
388 }
389 if( capacityPlusOne-1 != size ) {
390 throw new IllegalStateException("Buffer is not full: "+this);
391 }
392 final int wp1 = ( writePos + 1 ) % capacityPlusOne;
393 if( wp1 != readPos ) {
394 throw new InternalError("R != W+1 pos at full: "+this);
395 }
396 @SuppressWarnings("unchecked")
397 final Class<? extends T[]> arrayTypeInternal = (Class<? extends T[]>) array.getClass();
398
399 final int newCapacity = capacityPlusOne + growAmount;
400 final T[] oldArray = array;
401 final T[] newArray = newArray(arrayTypeInternal, newCapacity);
402
403 // writePos == readPos - 1
404 readPos = ( writePos + 1 + growAmount ) % newCapacity; // warp readPos to the end of the new data location
405
406 if(writePos >= 0) {
407 System.arraycopy(oldArray, 0, newArray, 0, writePos+1);
408 }
409 final int tail = capacityPlusOne-1-writePos;
410 if( tail > 0 ) {
411 System.arraycopy(oldArray, writePos+1, newArray, readPos, tail);
412 }
413
414 capacityPlusOne = newCapacity;
415 array = newArray;
416 }
417 }
418
419 @SuppressWarnings("unchecked")
420 private static <T> T[] newArray(final Class<? extends T[]> arrayType, final int length) {
421 return ((Object)arrayType == (Object)Object[].class)
422 ? (T[]) new Object[length]
423 : (T[]) Array.newInstance(arrayType.getComponentType(), length);
424 }
425}
Simple implementation of Ringbuffer, exposing lock-free get*(..) and put*(..) methods.
final String toString()
Returns a short string representation incl.
final void resetFull(final T[] copyFrom)
Resets the read and write position according to a full ring buffer and fill all slots w/ elements of ...
final int getFreeSlots()
Returns the number of free slots available to put.
final boolean putSame(final boolean blocking)
Enqueues the same element at it's write position, if not full.Returns true if successful,...
final int capacity()
Returns the net capacity of this ring buffer.
final void waitForFreeSlots(final int count)
Blocks until at least count free slots become available.
final boolean put(final T e)
Enqueues the given element.Returns true if successful, otherwise false in case buffer is full....
final T getBlocking()
Dequeues the oldest enqueued element.The returned ring buffer slot will be set to null to release the...
final int size()
Returns the number of elements in this ring buffer.
final void clear()
Resets the read and write position according to an empty ring buffer and set all ring buffer slots to...
final T peek()
Peeks the next element at the read position w/o modifying pointer, nor blocking.
final void putBlocking(final T e)
Enqueues the given element.Method blocks until a free slot becomes available via get.
final void dump(final PrintStream stream, final String prefix)
Debug functionality - Dumps the contents of the internal array.
final boolean isEmpty()
Returns true if this ring buffer is empty, otherwise false.
final T peekBlocking()
Peeks the next element at the read position w/o modifying pointer, but w/ blocking.
final void growEmptyBuffer(final T[] newElements)
Grows an empty ring buffer, increasing it's capacity about the amount.
final boolean isFull()
Returns true if this ring buffer is full, otherwise false.
LFRingbuffer(final Class<? extends T[]> arrayType, final int capacity)
Create an empty ring buffer instance w/ the given net capacity.
final void growFullBuffer(final int growAmount)
Grows a full ring buffer, increasing it's capacity about the amount.
Ring buffer interface, a.k.a circular buffer.
Definition: Ringbuffer.java:45