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.codec;
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 */
48 class UnboundedFifoByteBuffer {
49
50 protected byte[] buffer;
51 protected int head;
52 protected int tail;
53
54 /**
55 * Constructs an UnboundedFifoByteBuffer with the default number of elements.
56 * It is exactly the same as performing the following:
57 *
58 * <pre>
59 * new UnboundedFifoByteBuffer(32);
60 * </pre>
61 */
62 public UnboundedFifoByteBuffer() {
63 this(32);
64 }
65
66 /**
67 * Constructs an UnboundedFifoByteBuffer with the specified number of elements.
68 * The integer must be a positive integer.
69 *
70 * @param initialSize the initial size of the buffer
71 * @throws IllegalArgumentException if the size is less than 1
72 */
73 public UnboundedFifoByteBuffer(int initialSize) {
74 if (initialSize <= 0) {
75 throw new IllegalArgumentException("The size must be greater than 0");
76 }
77 buffer = new byte[initialSize + 1];
78 head = 0;
79 tail = 0;
80 }
81
82 /**
83 * Returns the number of elements stored in the buffer.
84 *
85 * @return this buffer's size
86 */
87 public int size() {
88 int size = 0;
89
90 if (tail < head) {
91 size = buffer.length - head + tail;
92 } else {
93 size = tail - head;
94 }
95
96 return size;
97 }
98
99 /**
100 * Returns true if this buffer is empty; false otherwise.
101 *
102 * @return true if this buffer is empty
103 */
104 public boolean isEmpty() {
105 return (size() == 0);
106 }
107
108 /**
109 * Adds the given element to this buffer.
110 *
111 * @param b the byte to add
112 * @return true, always
113 */
114 public boolean add(final byte b) {
115
116 if (size() + 1 >= buffer.length) {
117 byte[] tmp = new byte[((buffer.length - 1) * 2) + 1];
118
119 int j = 0;
120 for (int i = head; i != tail;) {
121 tmp[j] = buffer[i];
122 buffer[i] = 0;
123
124 j++;
125 i++;
126 if (i == buffer.length) {
127 i = 0;
128 }
129 }
130
131 buffer = tmp;
132 head = 0;
133 tail = j;
134 }
135
136 buffer[tail] = b;
137 tail++;
138 if (tail >= buffer.length) {
139 tail = 0;
140 }
141 return true;
142 }
143
144 /**
145 * Returns the next object in the buffer.
146 *
147 * @return the next object in the buffer
148 * @throws BufferUnderflowException if this buffer is empty
149 */
150 public byte get() {
151 if (isEmpty()) {
152 throw new IllegalStateException("The buffer is already empty");
153 }
154
155 return buffer[head];
156 }
157
158 /**
159 * Removes the next object from the buffer
160 *
161 * @return the removed object
162 * @throws BufferUnderflowException if this buffer is empty
163 */
164 public byte remove() {
165 if (isEmpty()) {
166 throw new IllegalStateException("The buffer is already empty");
167 }
168
169 byte element = buffer[head];
170
171 head++;
172 if (head >= buffer.length) {
173 head = 0;
174 }
175
176 return element;
177 }
178
179 /**
180 * Increments the internal index.
181 *
182 * @param index the index to increment
183 * @return the updated index
184 */
185 private int increment(int index) {
186 index++;
187 if (index >= buffer.length) {
188 index = 0;
189 }
190 return index;
191 }
192
193 /**
194 * Decrements the internal index.
195 *
196 * @param index the index to decrement
197 * @return the updated index
198 */
199 private int decrement(int index) {
200 index--;
201 if (index < 0) {
202 index = buffer.length - 1;
203 }
204 return index;
205 }
206
207 /**
208 * Returns an iterator over this buffer's elements.
209 *
210 * @return an iterator over this buffer's elements
211 */
212 public Iterator<Byte> iterator() {
213 return new Iterator<Byte>() {
214
215 private int index = head;
216 private int lastReturnedIndex = -1;
217
218 public boolean hasNext() {
219 return index != tail;
220
221 }
222
223 public Byte next() {
224 if (!hasNext()) {
225 throw new NoSuchElementException();
226 }
227 lastReturnedIndex = index;
228 index = increment(index);
229 return new Byte(buffer[lastReturnedIndex]);
230 }
231
232 public void remove() {
233 if (lastReturnedIndex == -1) {
234 throw new IllegalStateException();
235 }
236
237 // First element can be removed quickly
238 if (lastReturnedIndex == head) {
239 UnboundedFifoByteBuffer.this.remove();
240 lastReturnedIndex = -1;
241 return;
242 }
243
244 // Other elements require us to shift the subsequent elements
245 int i = lastReturnedIndex + 1;
246 while (i != tail) {
247 if (i >= buffer.length) {
248 buffer[i - 1] = buffer[0];
249 i = 0;
250 } else {
251 buffer[i - 1] = buffer[i];
252 i++;
253 }
254 }
255
256 lastReturnedIndex = -1;
257 tail = decrement(tail);
258 buffer[tail] = 0;
259 index = decrement(index);
260 }
261
262 };
263 }
264
265 }