KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > info > monitorenter > util > collections > RingBufferArrayFast


1 /*
2  * RingBufferArrayFast, an array- based fast implementation of a RingBuffer.
3  * Copyright (C) 2002 Achim Westermann, Achim.Westermann@gmx.de
4  *
5  * This library is free software; you can redistribute it and/or
6  * modify it under the terms of the GNU Lesser General Public
7  * License as published by the Free Software Foundation; either
8  * version 2.1 of the License, or (at your option) any later version.
9  *
10  * This library is distributed in the hope that it will be useful,
11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13  * Lesser General Public License for more details.
14  *
15  * You should have received a copy of the GNU Lesser General Public
16  * License along with this library; if not, write to the Free Software
17  * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
18  *
19  * If you modify or optimize the code in a useful way please let me know.
20  * Achim.Westermann@gmx.de
21  */
22 package info.monitorenter.util.collections;
23
24 import info.monitorenter.util.StringUtil;
25
26 import java.util.Iterator JavaDoc;
27 import java.util.NoSuchElementException JavaDoc;
28
29
30 /**
31  * Fast ringbuffer implementation.
32  * <p>
33  *
34  * This implementation differs from the <code>RingBufferArray</code> in one
35  * point: <br>
36  * If <code>setBufferSize(int asize)</code> decreases the size of the buffer
37  * and it will get smaller than the actual amount of elements stored, they will
38  * get lost. This avoids the need for an internal List to store elements
39  * overhanging. Some tests may be left out that may speed up this
40  * <code>IRingBuffer</code>. Adding 5000000 elements was about 25 % faster
41  * compared to the <code>RingBufferArray</code> on an Athlon 1200, 256 MB RAM.
42  * <p>
43  *
44  * For allowing high performance single-threaded use this implementation and the
45  * implementations of the retrieveable <code>Iterator</code>- instances are
46  * not synchronized at all.
47  * <p>
48  *
49  * @author <a HREF='mailto:Achim.Westermann@gmx.de'>Achim Westermann </a>
50  */
51 public class RingBufferArrayFast implements Cloneable JavaDoc, IRingBuffer {
52   /**
53    *
54    * Base for ringbuffer iterators that has access to the ringbuffer by being an
55    * non-static inner class.
56    * <p>
57    *
58    * @author <a HREF="mailto:Achim.Westermann@gmx.de">Achim Westermann </a>
59    *
60    * @version $Revision: 1.1 $
61    */
62   protected abstract class ARingBufferIterator implements Iterator JavaDoc {
63     /**
64      * The amount of returned instances, needed for knowing if iterator is
65      * empty.
66      */
67     protected int m_count;
68
69     /** The index of the next instance to return. */
70     protected int m_pos;
71
72     /**
73      * Defcon.
74      * <p>
75      *
76      */
77     ARingBufferIterator() {
78     }
79
80     /**
81      * @see java.util.Iterator#hasNext()
82      */
83     public boolean hasNext() {
84       return (this.m_count < RingBufferArrayFast.this.size());
85     }
86
87     /** Increment the internal read position pointer. */
88     protected abstract void incPos();
89
90     /**
91      * @see java.util.Iterator#next()
92      */
93     public Object JavaDoc next() {
94       if (!this.hasNext()) {
95         throw new NoSuchElementException JavaDoc();
96       }
97       Object JavaDoc result = RingBufferArrayFast.this.m_buffer[this.m_pos];
98       this.m_count++;
99       this.incPos();
100       if (result == null) {
101         throw new NoSuchElementException JavaDoc("RingBufferArrayFast.iteratorF2L returns null: pos:"
102             + this.m_pos + " count: " + this.m_count);
103       }
104       return result;
105     }
106
107     /**
108      * Not supported.
109      * <p>
110      *
111      * @throws UnsupportedOperationException
112      * always as this is not supported.
113      *
114      * @see java.util.Iterator#remove()
115      */
116     public void remove() throws UnsupportedOperationException JavaDoc {
117       throw new UnsupportedOperationException JavaDoc();
118     }
119
120   }
121
122   /**
123    * Flip the switch and you will see how the compiler changes the size of the
124    * classfile.
125    */
126   public static final boolean DEBUG = false;
127
128   /**
129    * Generated <code>serialVersionUID</code>.
130    */
131   private static final long serialVersionUID = 3834590997991404595L;
132
133   /** The internal array used as buffer. */
134   protected Object JavaDoc[] m_buffer;
135
136   /**
137    * Flag that marks wether this buffer is empty or not.
138    * <p>
139    *
140    * <pre>
141    *
142    * headpointer
143    * |
144    * +---+---+---+---+
145    * | 0 | 1 | 2 | 3 |
146    * +---+---+---+---+
147    * |
148    * tailpointer
149    *
150    * From where to where are the elements?
151    * Where is empty space?
152    * empty == true: 0 elements are contained: buffer empty
153    * empty == false: 4 elements are contained: buffer full
154    * remember:
155    * -the headpointer points to the space where the next element will be inserted.
156    * -the tailpointer points to the space to read the next element from.
157    *
158    *
159    * </pre>
160    *
161    * <p>
162    */
163   protected boolean m_empty = true;
164
165   /**
166    * The internal index to buffer where the next element is going to be placed
167    * (not placed yet!).
168    */
169   protected int m_headpointer = 0;
170
171   /**
172    * The internal size of the buffer.
173    * <p>
174    *
175    * For performance reasons the size of the buffer -1!
176    * <p>
177    */
178   protected int m_size;
179
180   /**
181    * The internal index to buffer where the next element is going to be read.
182    */
183   protected int m_tailpointer = 0;
184
185   /**
186    * Constructs a RingBuffer with the given size.
187    *
188    * @param aSize
189    * the size of the buffer.
190    */
191   public RingBufferArrayFast(final int aSize) {
192     this.m_buffer = new Object JavaDoc[aSize];
193     this.m_size = aSize - 1;
194   }
195
196   /**
197    * Adds an element to the ring buffer, potentially removing the first element
198    * to make more room.
199    * <P>
200    *
201    * @param anObject
202    * the instance to add.
203    *
204    * @return the oldes Object, if RingBuffer was filled with 'maxsize' elements
205    * before, or null.
206    */
207   public Object JavaDoc add(final Object JavaDoc anObject) {
208     Object JavaDoc ret = null;
209     if (this.isFull()) {
210       ret = this.m_buffer[this.m_tailpointer];
211       this.incTail();
212     }
213     if (RingBufferArray.DEBUG) {
214       System.out.println("add: tailpointer: " + this.m_tailpointer + " headpointer: "
215           + this.m_headpointer + " size: " + this.size());
216     }
217     this.m_buffer[this.m_headpointer] = anObject;
218     this.incHead();
219     return ret;
220   }
221
222   /**
223    * Fast method to clear the buffer - only needs to set three primitive
224    * members.
225    * <p>
226    *
227    * @see info.monitorenter.util.collections.IRingBuffer#clear()
228    */
229   public void clear() {
230     this.m_headpointer = 0;
231     this.m_tailpointer = 0;
232     this.m_empty = true;
233   }
234
235   /**
236    * @see info.monitorenter.util.collections.IRingBuffer#getBufferSize()
237    */
238   public int getBufferSize() {
239     return this.m_size + 1;
240   }
241
242   /**
243    * @see info.monitorenter.util.collections.IRingBuffer#getOldest()
244    */
245   public Object JavaDoc getOldest() throws RingBufferException {
246     if (this.isEmpty()) {
247       throw new IRingBuffer.RingBufferException("Buffer is empty.");
248     }
249     return this.m_buffer[this.m_tailpointer];
250   }
251
252   /**
253    *
254    * @see info.monitorenter.util.collections.IRingBuffer#getYoungest()
255    */
256   public Object JavaDoc getYoungest() throws RingBufferException {
257     if (isEmpty()) {
258       throw new IRingBuffer.RingBufferException("Buffer is empty.");
259     }
260     int tmp = this.m_headpointer;
261     if (tmp == 0) {
262       tmp = this.m_size;
263     } else {
264       tmp--;
265     }
266     return this.m_buffer[tmp];
267   }
268
269   /**
270    * Internally increases the array index pointer to the head of the buffer.
271    * <p>
272    *
273    */
274   private void incHead() {
275     if (this.m_headpointer == this.m_size) {
276       this.m_headpointer = 0;
277     } else {
278       this.m_headpointer++;
279     }
280     this.m_empty = false;
281   }
282
283   /**
284    * Internally increases the array index pointer to the taill of the buffer.
285    * <p>
286    *
287    */
288   private void incTail() {
289     if (this.m_tailpointer == this.m_size) {
290       this.m_tailpointer = 0;
291     } else {
292       this.m_tailpointer++;
293     }
294     if (this.m_tailpointer == this.m_headpointer) {
295       this.m_empty = true;
296     }
297   }
298
299   /**
300    * @see info.monitorenter.util.collections.IRingBuffer#isEmpty()
301    */
302   public boolean isEmpty() {
303     if (RingBufferArray.DEBUG) {
304       System.out.println("isEmpty: " + this.m_empty + " head: " + this.m_headpointer + " tail: "
305           + this.m_tailpointer);
306     }
307     return this.m_empty;
308   }
309
310   /**
311    * @see info.monitorenter.util.collections.IRingBuffer#isFull()
312    */
313   public boolean isFull() {
314     boolean ret = (this.m_headpointer == this.m_tailpointer) && !this.m_empty;
315     if (RingBufferArray.DEBUG) {
316       System.out.println("isFull: " + ret + " head: " + this.m_headpointer + " tail: "
317           + this.m_tailpointer);
318     }
319     return ret;
320   }
321
322   /**
323    * Returns an <code>Iterator</code> that will return the elements in exactly
324    * the inverse order the subsequent call to <code>remove()</code> would do.
325    * <p>
326    *
327    * The youngest elements are returned first. <b>The <code>Iterator</code>
328    * returned is not thread- safe! </b>
329    * <p>
330    *
331    * @return an <code>Iterator</code> that will return the elements in exactly
332    * the inverse order the subsequent call to <code>remove()</code>
333    * would do.
334    */
335
336   public java.util.Iterator JavaDoc iteratorF2L() {
337     return new ARingBufferIterator() {
338       {
339         this.m_pos = (RingBufferArrayFast.this.m_headpointer == 0) ? RingBufferArrayFast.this
340             .size() - 1 : RingBufferArrayFast.this.m_headpointer - 1;
341       }
342
343       protected void incPos() {
344         if (this.m_pos == 0) {
345           this.m_pos = RingBufferArrayFast.this.m_size;
346         } else {
347           this.m_pos--;
348         }
349       }
350     };
351   }
352
353   /**
354    * Returns an <code>Iterator</code> that will return the elements in exactly
355    * the order the subsequent call to <code>remove()</code> would do.
356    * <p>
357    * The oldest elements are returned first. <b>The <code>Iterator</code>
358    * returned is not thread- safe! </b>
359    * <p>
360    *
361    * @return an <code>Iterator</code> that will return the elements in exactly
362    * the order the subsequent call to <code>remove()</code> would do.
363    */
364   public java.util.Iterator JavaDoc iteratorL2F() {
365     return new ARingBufferIterator() {
366       {
367         this.m_pos = RingBufferArrayFast.this.m_tailpointer;
368       }
369
370       /**
371        * @see info.monitorenter.util.collections.RingBufferArrayFast.RingBufferIterator#incPos()
372        */
373       protected void incPos() {
374         if (this.m_pos == RingBufferArrayFast.this.m_size) {
375           this.m_pos = 0;
376         } else {
377           this.m_pos++;
378         }
379       }
380     };
381   }
382
383   /**
384    * @see info.monitorenter.util.collections.IRingBuffer#remove()
385    */
386   public Object JavaDoc remove() {
387     if (this.isEmpty()) {
388       throw new IRingBuffer.RingBufferException("Buffer is empty.");
389     }
390     Object JavaDoc ret = null;
391     ret = this.m_buffer[this.m_tailpointer];
392     this.incTail();
393     if (RingBufferArray.DEBUG) {
394       System.out.println("Removing element: " + ret + " head: " + this.m_headpointer + " tail: "
395           + this.m_tailpointer + " size: " + this.size());
396     }
397     return ret;
398   }
399
400   /**
401    * @see info.monitorenter.util.collections.IRingBuffer#removeAll()
402    */
403   public Object JavaDoc[] removeAll() {
404     Object JavaDoc[] ret = new Object JavaDoc[this.size()];
405     if (RingBufferArray.DEBUG) {
406       System.out.println("removeAll()");
407     }
408     for (int i = 0; i < ret.length; i++) {
409       ret[i] = this.remove();
410     }
411     return ret;
412   }
413
414   /**
415    * Sets a new buffer- size. <br>
416    * <p>
417    * A new size is assigned but the elements "overhanging" are returned by the
418    * <code>Object remove()</code>- method first. This may take time until the
419    * buffer has its actual size again. Don't pretend on calling this method for
420    * saving of memory very often as the whole buffer has to be copied into a new
421    * array every time- and if newSize < getSize() additional the overhanging
422    * elements references have to be moved to the internal
423    * <code>List pendingremove</code>.
424    *
425    * @param newSize
426    * the new size of the buffer.
427    */
428   public void setBufferSize(final int newSize) {
429     Object JavaDoc[] newbuffer = new Object JavaDoc[newSize];
430     boolean emptyStore = this.m_empty;
431     int i = 0, j = 0;
432     if (RingBufferArray.DEBUG) {
433       System.out.println("setBufferSize(" + newSize + "): isEmpty(): " + this.isEmpty() + " tail: "
434           + this.m_tailpointer + " head: " + this.m_headpointer);
435     }
436     // skip the oldest ones that are discarded
437 int oldSize = this.size();
438     int stop = oldSize - newSize;
439     for (; i < stop && !this.isEmpty(); i++) {
440       this.remove();
441     }
442     // add the ones that are the youngest (if some remaining)
443 for (j = 0; j < newSize && !this.isEmpty(); j++) {
444       newbuffer[j] = this.remove();
445     }
446     this.m_tailpointer = 0;
447     this.m_headpointer = j;
448     if (this.m_headpointer == newSize) {
449       this.m_headpointer = 0;
450     }
451     this.m_buffer = newbuffer;
452     this.m_size = newSize - 1;
453     this.m_empty = emptyStore || (newSize == 0);
454   }
455
456   /**
457    * @see info.monitorenter.util.collections.IRingBuffer#size()
458    */
459   public int size() {
460     if (this.m_empty) {
461       return 0;
462     } else if (this.m_headpointer == this.m_tailpointer) {
463       return this.m_size + 1;
464     } else if (this.m_headpointer > this.m_tailpointer) {
465       return this.m_headpointer - this.m_tailpointer;
466     } else {
467       return this.m_headpointer + this.m_size + 1 - this.m_tailpointer;
468     }
469   }
470
471   /**
472    * Returns a string representation of the RingBuffer and it's contents.
473    * <p>
474    * Don't call this in your application too often: hard arraycopy - operation
475    * an memalloc are triggered.
476    * <p>
477    *
478    * @return a string representation of the RingBuffer and it's contents.
479    */
480   public String JavaDoc toString() {
481     if (this.isEmpty()) {
482       if (RingBufferArray.DEBUG) {
483         System.out.println("toString(): isEmpty: true");
484       }
485       return "[]";
486     }
487     Object JavaDoc[] actualcontent = new Object JavaDoc[this.size()];
488     int tmp = this.m_tailpointer;
489     int i = 0;
490     for (; i < actualcontent.length; i++) {
491       actualcontent[i] = this.m_buffer[tmp];
492       if (tmp == this.m_size) {
493         tmp = 0;
494       } else {
495         tmp++;
496       }
497       if (tmp == this.m_headpointer && this.m_empty) {
498         break;
499       }
500     }
501     return StringUtil.arrayToString(actualcontent);
502   }
503 }
504
Popular Tags