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.mina.util.byteaccess;
21
22 import java.util.NoSuchElementException;
23
24 /**
25 * A linked list that stores <code>ByteArray</code>s and maintains several useful invariants.
26 *
27 * Note : this class is *not* thread safe.
28 *
29 * @author <a href="http://mina.apache.org">Apache MINA Project</a>
30 */
31 class ByteArrayList {
32
33 /**
34 * A {@link Node} which indicates the start and end of the list and does not
35 * hold a value. The value of <code>next</code> is the first item in the
36 * list. The value of of <code>previous</code> is the last item in the list.
37 */
38 private final Node header;
39
40 /**
41 * The first byte in the array list
42 */
43 private int firstByte;
44
45 /**
46 * The last byte in the array list
47 */
48 private int lastByte;
49
50 /**
51 *
52 * Creates a new instance of ByteArrayList.
53 *
54 */
55 protected ByteArrayList() {
56 header = new Node();
57 }
58
59 /**
60 * @return The last byte in the array list
61 */
62 public int lastByte() {
63 return lastByte;
64 }
65
66 /**
67 * @return The first byte in the array list
68 */
69 public int firstByte() {
70 return firstByte;
71 }
72
73 /**
74 *
75 * Check to see if this is empty
76 *
77 * @return
78 * True if empty, otherwise false
79 */
80 public boolean isEmpty() {
81 return header.next == header;
82 }
83
84 /**
85 * @return the first node in the byte array
86 */
87 public Node getFirst() {
88 return header.getNextNode();
89 }
90
91 /**
92 * @return the last {@link Node} in the list
93 */
94 public Node getLast() {
95 return header.getPreviousNode();
96 }
97
98 /**
99 * Adds the specified {@link ByteArray} to
100 * the beginning of the list
101 *
102 * @param ba
103 * The ByteArray to be added to the list
104 */
105 public void addFirst(ByteArray ba) {
106 addNode(new Node(ba), header.next);
107 firstByte -= ba.last();
108 }
109
110 /**
111 * Add the specified {@link ByteArray} to
112 * the end of the list
113 *
114 * @param ba
115 * The ByteArray to be added to the list
116 */
117 public void addLast(ByteArray ba) {
118 addNode(new Node(ba), header);
119 lastByte += ba.last();
120 }
121
122 /**
123 * Removes the first node from this list
124 *
125 * @return
126 * The node that was removed
127 */
128 public Node removeFirst() {
129 Node node = header.getNextNode();
130 firstByte += node.ba.last();
131 return removeNode(node);
132 }
133
134 /**
135 * Removes the last node in this list
136 *
137 * @return
138 * The node that was taken off of the list
139 */
140 public Node removeLast() {
141 Node node = header.getPreviousNode();
142 lastByte -= node.ba.last();
143 return removeNode(node);
144 }
145
146 //-----------------------------------------------------------------------
147
148 /**
149 * Inserts a new node into the list.
150 *
151 * @param nodeToInsert new node to insert
152 * @param insertBeforeNode node to insert before
153 */
154 protected void addNode(Node nodeToInsert, Node insertBeforeNode) {
155 // Insert node.
156 nodeToInsert.next = insertBeforeNode;
157 nodeToInsert.previous = insertBeforeNode.previous;
158 insertBeforeNode.previous.next = nodeToInsert;
159 insertBeforeNode.previous = nodeToInsert;
160 }
161
162 /**
163 * Removes the specified node from the list.
164 *
165 * @param node the node to remove
166 */
167 protected Node removeNode(Node node) {
168 // Remove node.
169 node.previous.next = node.next;
170 node.next.previous = node.previous;
171 node.removed = true;
172 return node;
173 }
174
175 //-----------------------------------------------------------------------
176 /**
177 * A node within the linked list.
178 * <p>
179 * From Commons Collections 3.1, all access to the <code>value</code> property
180 * is via the methods on this class.
181 */
182 public class Node {
183
184 /** A pointer to the node before this node */
185 private Node previous;
186
187 /** A pointer to the node after this node */
188 private Node next;
189
190 /** The ByteArray contained within this node */
191 private ByteArray ba;
192
193 private boolean removed;
194
195 /**
196 * Constructs a new header node.
197 */
198 private Node() {
199 previous = this;
200 next = this;
201 }
202
203 /**
204 * Constructs a new node with a value.
205 */
206 private Node(ByteArray ba) {
207 if (ba == null) {
208 throw new IllegalArgumentException("ByteArray must not be null.");
209 }
210
211 this.ba = ba;
212 }
213
214 /**
215 * Gets the previous node.
216 *
217 * @return the previous node
218 */
219 public Node getPreviousNode() {
220 if (!hasPreviousNode()) {
221 throw new NoSuchElementException();
222 }
223
224 return previous;
225 }
226
227 /**
228 * Gets the next node.
229 *
230 * @return the next node
231 */
232 public Node getNextNode() {
233 if (!hasNextNode()) {
234 throw new NoSuchElementException();
235 }
236
237 return next;
238 }
239
240 public boolean hasPreviousNode() {
241 return previous != header;
242 }
243
244 public boolean hasNextNode() {
245 return next != header;
246 }
247
248 public ByteArray getByteArray() {
249 return ba;
250 }
251
252 public boolean isRemoved() {
253 return removed;
254 }
255 }
256 }