1 /****************************************************************
2  * Licensed to the Apache Software Foundation (ASF) under one   *
3  * or more contributor license agreements.  See the NOTICE file *
4  * distributed with this work for additional information        *
5  * regarding copyright ownership.  The ASF licenses this file   *
6  * to you under the Apache License, Version 2.0 (the            *
7  * "License"); you may not use this file except in compliance   *
8  * with the License.  You may obtain a copy of the License at   *
9  *                                                              *
10  *   http://www.apache.org/licenses/LICENSE-2.0                 *
11  *                                                              *
12  * Unless required by applicable law or agreed to in writing,   *
13  * software distributed under the License is distributed on an  *
14  * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY       *
15  * KIND, either express or implied.  See the License for the    *
16  * specific language governing permissions and limitations      *
17  * under the License.                                           *
18  ****************************************************************/
19 
20 package org.apache.james.mime4j.decoder;
21 
22 import java.util.Iterator;
23 import java.util.NoSuchElementException;
24 
25 /**
26  * UnboundedFifoByteBuffer is a very efficient buffer implementation.
27  * According to performance testing, it exhibits a constant access time, but it
28  * also outperforms ArrayList when used for the same purpose.
29  * <p>
30  * The removal order of an <code>UnboundedFifoByteBuffer</code> is based on the insertion
31  * order; elements are removed in the same order in which they were added.
32  * The iteration order is the same as the removal order.
33  * <p>
34  * The {@link #remove()} and {@link #get()} operations perform in constant time.
35  * The {@link #add(Object)} operation performs in amortized constant time.  All
36  * other operations perform in linear time or worse.
37  * <p>
38  * Note that this implementation is not synchronized.  The following can be
39  * used to provide synchronized access to your <code>UnboundedFifoByteBuffer</code>:
40  * <pre>
41  *   Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoByteBuffer());
42  * </pre>
43  * <p>
44  * This buffer prevents null objects from being added.
45  *
46  * @since Commons Collections 3.0 (previously in main package v2.1)
47  * @version $Revision: 1.1 $ $Date: 2004/08/24 06:52:02 $
48  *
49  *
50  *
51  *
52  *
53  *
54  */
55 class UnboundedFifoByteBuffer {
56 
57     protected byte[] buffer;
58     protected int head;
59     protected int tail;
60 
61     /**
62      * Constructs an UnboundedFifoByteBuffer with the default number of elements.
63      * It is exactly the same as performing the following:
64      *
65      * <pre>
66      *   new UnboundedFifoByteBuffer(32);
67      * </pre>
68      */
UnboundedFifoByteBuffer()69     public UnboundedFifoByteBuffer() {
70         this(32);
71     }
72 
73     /**
74      * Constructs an UnboundedFifoByteBuffer with the specified number of elements.
75      * The integer must be a positive integer.
76      *
77      * @param initialSize  the initial size of the buffer
78      * @throws IllegalArgumentException  if the size is less than 1
79      */
UnboundedFifoByteBuffer(int initialSize)80     public UnboundedFifoByteBuffer(int initialSize) {
81         if (initialSize <= 0) {
82             throw new IllegalArgumentException("The size must be greater than 0");
83         }
84         buffer = new byte[initialSize + 1];
85         head = 0;
86         tail = 0;
87     }
88 
89     /**
90      * Returns the number of elements stored in the buffer.
91      *
92      * @return this buffer's size
93      */
size()94     public int size() {
95         int size = 0;
96 
97         if (tail < head) {
98             size = buffer.length - head + tail;
99         } else {
100             size = tail - head;
101         }
102 
103         return size;
104     }
105 
106     /**
107      * Returns true if this buffer is empty; false otherwise.
108      *
109      * @return true if this buffer is empty
110      */
isEmpty()111     public boolean isEmpty() {
112         return (size() == 0);
113     }
114 
115     /**
116      * Adds the given element to this buffer.
117      *
118      * @param b  the byte to add
119      * @return true, always
120      */
add(final byte b)121     public boolean add(final byte b) {
122 
123         if (size() + 1 >= buffer.length) {
124             byte[] tmp = new byte[((buffer.length - 1) * 2) + 1];
125 
126             int j = 0;
127             for (int i = head; i != tail;) {
128                 tmp[j] = buffer[i];
129                 buffer[i] = 0;
130 
131                 j++;
132                 i++;
133                 if (i == buffer.length) {
134                     i = 0;
135                 }
136             }
137 
138             buffer = tmp;
139             head = 0;
140             tail = j;
141         }
142 
143         buffer[tail] = b;
144         tail++;
145         if (tail >= buffer.length) {
146             tail = 0;
147         }
148         return true;
149     }
150 
151     /**
152      * Returns the next object in the buffer.
153      *
154      * @return the next object in the buffer
155      * @throws BufferUnderflowException  if this buffer is empty
156      */
get()157     public byte get() {
158         if (isEmpty()) {
159             throw new IllegalStateException("The buffer is already empty");
160         }
161 
162         return buffer[head];
163     }
164 
165     /**
166      * Removes the next object from the buffer
167      *
168      * @return the removed object
169      * @throws BufferUnderflowException  if this buffer is empty
170      */
remove()171     public byte remove() {
172         if (isEmpty()) {
173             throw new IllegalStateException("The buffer is already empty");
174         }
175 
176         byte element = buffer[head];
177 
178         head++;
179         if (head >= buffer.length) {
180             head = 0;
181         }
182 
183         return element;
184     }
185 
186     /**
187      * Increments the internal index.
188      *
189      * @param index  the index to increment
190      * @return the updated index
191      */
increment(int index)192     private int increment(int index) {
193         index++;
194         if (index >= buffer.length) {
195             index = 0;
196         }
197         return index;
198     }
199 
200     /**
201      * Decrements the internal index.
202      *
203      * @param index  the index to decrement
204      * @return the updated index
205      */
decrement(int index)206     private int decrement(int index) {
207         index--;
208         if (index < 0) {
209             index = buffer.length - 1;
210         }
211         return index;
212     }
213 
214     /**
215      * Returns an iterator over this buffer's elements.
216      *
217      * @return an iterator over this buffer's elements
218      */
iterator()219     public Iterator iterator() {
220         return new Iterator() {
221 
222             private int index = head;
223             private int lastReturnedIndex = -1;
224 
225             public boolean hasNext() {
226                 return index != tail;
227 
228             }
229 
230             public Object next() {
231                 if (!hasNext()) {
232                     throw new NoSuchElementException();
233                 }
234                 lastReturnedIndex = index;
235                 index = increment(index);
236                 return new Byte(buffer[lastReturnedIndex]);
237             }
238 
239             public void remove() {
240                 if (lastReturnedIndex == -1) {
241                     throw new IllegalStateException();
242                 }
243 
244                 // First element can be removed quickly
245                 if (lastReturnedIndex == head) {
246                     UnboundedFifoByteBuffer.this.remove();
247                     lastReturnedIndex = -1;
248                     return;
249                 }
250 
251                 // Other elements require us to shift the subsequent elements
252                 int i = lastReturnedIndex + 1;
253                 while (i != tail) {
254                     if (i >= buffer.length) {
255                         buffer[i - 1] = buffer[0];
256                         i = 0;
257                     } else {
258                         buffer[i - 1] = buffer[i];
259                         i++;
260                     }
261                 }
262 
263                 lastReturnedIndex = -1;
264                 tail = decrement(tail);
265                 buffer[tail] = 0;
266                 index = decrement(index);
267             }
268 
269         };
270     }
271 
272 }