| /**************************************************************** |
| * Licensed to the Apache Software Foundation (ASF) under one * |
| * or more contributor license agreements. See the NOTICE file * |
| * distributed with this work for additional information * |
| * regarding copyright ownership. The ASF licenses this file * |
| * to you under the Apache License, Version 2.0 (the * |
| * "License"); you may not use this file except in compliance * |
| * with the License. You may obtain a copy of the License at * |
| * * |
| * http://www.apache.org/licenses/LICENSE-2.0 * |
| * * |
| * Unless required by applicable law or agreed to in writing, * |
| * software distributed under the License is distributed on an * |
| * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY * |
| * KIND, either express or implied. See the License for the * |
| * specific language governing permissions and limitations * |
| * under the License. * |
| ****************************************************************/ |
| |
| package org.apache.james.mime4j.decoder; |
| |
| import java.util.Iterator; |
| import java.util.NoSuchElementException; |
| |
| /** |
| * UnboundedFifoByteBuffer is a very efficient buffer implementation. |
| * According to performance testing, it exhibits a constant access time, but it |
| * also outperforms ArrayList when used for the same purpose. |
| * <p> |
| * The removal order of an <code>UnboundedFifoByteBuffer</code> is based on the insertion |
| * order; elements are removed in the same order in which they were added. |
| * The iteration order is the same as the removal order. |
| * <p> |
| * The {@link #remove()} and {@link #get()} operations perform in constant time. |
| * The {@link #add(Object)} operation performs in amortized constant time. All |
| * other operations perform in linear time or worse. |
| * <p> |
| * Note that this implementation is not synchronized. The following can be |
| * used to provide synchronized access to your <code>UnboundedFifoByteBuffer</code>: |
| * <pre> |
| * Buffer fifo = BufferUtils.synchronizedBuffer(new UnboundedFifoByteBuffer()); |
| * </pre> |
| * <p> |
| * This buffer prevents null objects from being added. |
| * |
| * @since Commons Collections 3.0 (previously in main package v2.1) |
| * @version $Revision: 1.1 $ $Date: 2004/08/24 06:52:02 $ |
| * |
| * |
| * |
| * |
| * |
| * |
| */ |
| class UnboundedFifoByteBuffer { |
| |
| protected byte[] buffer; |
| protected int head; |
| protected int tail; |
| |
| /** |
| * Constructs an UnboundedFifoByteBuffer with the default number of elements. |
| * It is exactly the same as performing the following: |
| * |
| * <pre> |
| * new UnboundedFifoByteBuffer(32); |
| * </pre> |
| */ |
| public UnboundedFifoByteBuffer() { |
| this(32); |
| } |
| |
| /** |
| * Constructs an UnboundedFifoByteBuffer with the specified number of elements. |
| * The integer must be a positive integer. |
| * |
| * @param initialSize the initial size of the buffer |
| * @throws IllegalArgumentException if the size is less than 1 |
| */ |
| public UnboundedFifoByteBuffer(int initialSize) { |
| if (initialSize <= 0) { |
| throw new IllegalArgumentException("The size must be greater than 0"); |
| } |
| buffer = new byte[initialSize + 1]; |
| head = 0; |
| tail = 0; |
| } |
| |
| /** |
| * Returns the number of elements stored in the buffer. |
| * |
| * @return this buffer's size |
| */ |
| public int size() { |
| int size = 0; |
| |
| if (tail < head) { |
| size = buffer.length - head + tail; |
| } else { |
| size = tail - head; |
| } |
| |
| return size; |
| } |
| |
| /** |
| * Returns true if this buffer is empty; false otherwise. |
| * |
| * @return true if this buffer is empty |
| */ |
| public boolean isEmpty() { |
| return (size() == 0); |
| } |
| |
| /** |
| * Adds the given element to this buffer. |
| * |
| * @param b the byte to add |
| * @return true, always |
| */ |
| public boolean add(final byte b) { |
| |
| if (size() + 1 >= buffer.length) { |
| byte[] tmp = new byte[((buffer.length - 1) * 2) + 1]; |
| |
| int j = 0; |
| for (int i = head; i != tail;) { |
| tmp[j] = buffer[i]; |
| buffer[i] = 0; |
| |
| j++; |
| i++; |
| if (i == buffer.length) { |
| i = 0; |
| } |
| } |
| |
| buffer = tmp; |
| head = 0; |
| tail = j; |
| } |
| |
| buffer[tail] = b; |
| tail++; |
| if (tail >= buffer.length) { |
| tail = 0; |
| } |
| return true; |
| } |
| |
| /** |
| * Returns the next object in the buffer. |
| * |
| * @return the next object in the buffer |
| * @throws BufferUnderflowException if this buffer is empty |
| */ |
| public byte get() { |
| if (isEmpty()) { |
| throw new IllegalStateException("The buffer is already empty"); |
| } |
| |
| return buffer[head]; |
| } |
| |
| /** |
| * Removes the next object from the buffer |
| * |
| * @return the removed object |
| * @throws BufferUnderflowException if this buffer is empty |
| */ |
| public byte remove() { |
| if (isEmpty()) { |
| throw new IllegalStateException("The buffer is already empty"); |
| } |
| |
| byte element = buffer[head]; |
| |
| head++; |
| if (head >= buffer.length) { |
| head = 0; |
| } |
| |
| return element; |
| } |
| |
| /** |
| * Increments the internal index. |
| * |
| * @param index the index to increment |
| * @return the updated index |
| */ |
| private int increment(int index) { |
| index++; |
| if (index >= buffer.length) { |
| index = 0; |
| } |
| return index; |
| } |
| |
| /** |
| * Decrements the internal index. |
| * |
| * @param index the index to decrement |
| * @return the updated index |
| */ |
| private int decrement(int index) { |
| index--; |
| if (index < 0) { |
| index = buffer.length - 1; |
| } |
| return index; |
| } |
| |
| /** |
| * Returns an iterator over this buffer's elements. |
| * |
| * @return an iterator over this buffer's elements |
| */ |
| public Iterator iterator() { |
| return new Iterator() { |
| |
| private int index = head; |
| private int lastReturnedIndex = -1; |
| |
| public boolean hasNext() { |
| return index != tail; |
| |
| } |
| |
| public Object next() { |
| if (!hasNext()) { |
| throw new NoSuchElementException(); |
| } |
| lastReturnedIndex = index; |
| index = increment(index); |
| return new Byte(buffer[lastReturnedIndex]); |
| } |
| |
| public void remove() { |
| if (lastReturnedIndex == -1) { |
| throw new IllegalStateException(); |
| } |
| |
| // First element can be removed quickly |
| if (lastReturnedIndex == head) { |
| UnboundedFifoByteBuffer.this.remove(); |
| lastReturnedIndex = -1; |
| return; |
| } |
| |
| // Other elements require us to shift the subsequent elements |
| int i = lastReturnedIndex + 1; |
| while (i != tail) { |
| if (i >= buffer.length) { |
| buffer[i - 1] = buffer[0]; |
| i = 0; |
| } else { |
| buffer[i - 1] = buffer[i]; |
| i++; |
| } |
| } |
| |
| lastReturnedIndex = -1; |
| tail = decrement(tail); |
| buffer[tail] = 0; |
| index = decrement(index); |
| } |
| |
| }; |
| } |
| |
| } |