1 /*
2 * Copyright (c) 1998-2002 The Jgroup Team.
3 *
4 * This program is free software; you can redistribute it and/or modify
5 * it under the terms of the GNU Lesser General Public License version 2 as
6 * published by the Free Software Foundation.
7 *
8 * This program is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
11 * GNU Lesser General Public License for more details.
12 *
13 * You should have received a copy of the GNU Lesser General Public License
14 * along with this program; if not, write to the Free Software
15 * Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
16 *
17 */
18
19 package jgroup.util;
20
21 import java.util.ConcurrentModificationException;
22 import java.util.Iterator;
23 import java.util.NoSuchElementException;
24
25 /**
26 * The <code>Queue</code> class implements a queue with last-in,
27 * first-out semantics. The queue is implemented as a linked list of
28 * buckets, each of them contains a fixed number of objects. Appended
29 * objects are inserted in the last bucket (if full, a new bucket is
30 * allocated), while removed object are extracted from the first
31 * bucket.
32 *
33 * @author Alberto Montresor
34 * @author Hein Meling
35 * @since Jgroup 0.1
36 */
37 public final class Queue
38 {
39
40 ////////////////////////////////////////////////////////////////////////////////////////////
41 // Constants
42 ////////////////////////////////////////////////////////////////////////////////////////////
43
44 /* The default bucket size */
45 private final static int QUEUE_BUCKET_SIZE = 32;
46
47
48 ////////////////////////////////////////////////////////////////////////////////////////////
49 // Fields
50 ////////////////////////////////////////////////////////////////////////////////////////////
51
52 /** First bucket in the queue */
53 private Bucket head;
54
55 /** Last bucket in the queue */
56 private Bucket tail;
57
58 /** Number of object in a single bucket */
59 private int bucketSize;
60
61 /** Current object index in the first bucket */
62 private int first = 0;
63
64 /** Current object index in the last bucket */
65 private int last = 0;
66
67 /** Number of elements in the queue */
68 private int ncount = 0;
69
70 /**
71 * The number of times this Queue has been structurally modified.
72 * Structural modifications are those that change the number of
73 * elements in the queue. This field is used to make the iterator
74 * fail-fast, without risk of rendering the datastructure in an
75 * inconsistent state. (See ConcurrentModificationException).
76 */
77 private transient int modCount = 0;
78
79
80 ////////////////////////////////////////////////////////////////////////////////////////////
81 // Constructors
82 ////////////////////////////////////////////////////////////////////////////////////////////
83
84 /**
85 * Allocates a queue with bucket size equal to <code>bucketSize</code>.
86 *
87 * @param bucketSize
88 * The size of internal buckets.
89 */
90 public Queue(int bucketSize)
91 {
92 if (bucketSize < 1)
93 throw new IllegalArgumentException("Bucket size must be greater than zero");
94 this.bucketSize = bucketSize;
95 head = new Bucket(bucketSize);
96 tail = head;
97 }
98
99
100 /**
101 * Allocates a queue with default bucket size.
102 */
103 public Queue()
104 {
105 this(QUEUE_BUCKET_SIZE);
106 }
107
108
109 ////////////////////////////////////////////////////////////////////////////////////////////
110 // Methods
111 ////////////////////////////////////////////////////////////////////////////////////////////
112
113 /**
114 * Append <code>object</code> to the end of the queue.
115 *
116 * @param object
117 * The object to be inserted.
118 */
119 public void insert(Object object)
120 {
121 tail.objects[last] = object;
122 last++;
123 if (last == bucketSize) {
124 if (tail.next == null)
125 tail.next = new Bucket(bucketSize);
126 tail = tail.next;
127 last = 0;
128 }
129 modCount++;
130 ncount++;
131 }
132
133
134 /**
135 * Returns the size of the queue.
136 */
137 public int size()
138 {
139 return ncount;
140 }
141
142
143 /**
144 * Returns true if the queue is empty.
145 */
146 public boolean isEmpty()
147 {
148 return (ncount == 0);
149 }
150
151
152 /**
153 * Returns the first element of the queue; null if the queue is
154 * empty.
155 */
156 public Object getFirst()
157 {
158 if (ncount == 0)
159 return null;
160
161 return head.objects[first];
162 }
163
164
165 /**
166 * Removes the first element of the queue.
167 *
168 * @return the first element of the queue; null if the queue is empty.
169 */
170 public Object removeFirst()
171 {
172 if (ncount == 0)
173 return null;
174 modCount++;
175
176 Object ret = head.objects[first];
177 head.objects[first] = null;
178 ncount--;
179 first++;
180 if (first == bucketSize) {
181 Bucket temp = tail.next;
182 tail.next = head; // This avoid useless allocations
183 head = head.next;
184 tail.next.next = temp;
185 first = 0;
186 }
187 return ret;
188 }
189
190
191 /**
192 * Add the elements of the addend queue at the end of this queue.
193 *
194 * @param addend
195 * The queue to be added to the end of this queue.
196 */
197 public void add(Queue addend)
198 {
199 modCount++;
200
201 Object obj;
202 while ((obj = addend.removeFirst()) != null)
203 insert(obj);
204 }
205
206
207 /**
208 * Removes all the elements from the queue.
209 */
210 public void clear()
211 {
212 modCount++;
213 for (int i = first; i < bucketSize; i++)
214 head.objects[i] = null;
215 head.next = null;
216 tail = head;
217 first = 0;
218 last = 0;
219 ncount = 0;
220 }
221
222
223 /**
224 * Copies the element of the queue in an array of objects, in the
225 * queue order.
226 */
227 // public Object[] toArray()
228 // {
229 // Object[] ret = new Object[ncount];
230 // Bucket scan = head;
231 // int pos = first;
232 // for (int i = 0; i < ncount; i++) {
233 // ret[i] = scan.objects[pos];
234 // pos++;
235 // if (pos == bucketSize) {
236 // pos = 0;
237 // scan = scan.next;
238 // }
239 // }
240 // return ret;
241 // }
242
243
244 /**
245 * Returns an iterator over the queue content.
246 */
247 public Iterator iterator()
248 {
249 return new QueueIterator();
250 }
251
252
253 public String toString()
254 {
255 StringBuilder buf = new StringBuilder("[Queue: ");
256 for (Iterator qi = iterator(); qi.hasNext();) {
257 buf.append(qi.next());
258 if (qi.hasNext())
259 buf.append(", ");
260 }
261 buf.append("]");
262 return buf.toString();
263 }
264
265
266 /**
267 * Provides an iterator over the elements in the queue.
268 *
269 * @author Hein Meling
270 * @since Jgroup 1.2
271 */
272 private class QueueIterator
273 implements Iterator
274 {
275 private Bucket scan = head;
276 private int pos = first;
277 private int nextIndex = 0;
278
279 /**
280 * The modCount value that the iterator believes that the backing
281 * Queue should have. If this expectation is violated, the iterator
282 * has detected concurrent modification.
283 */
284 private int expectedModCount = modCount;
285
286
287 public boolean hasNext()
288 {
289 return nextIndex != ncount;
290 }
291
292
293 public Object next()
294 {
295 if (modCount != expectedModCount)
296 throw new ConcurrentModificationException();
297 if (nextIndex == ncount)
298 throw new NoSuchElementException();
299
300 Object obj = scan.objects[pos++];
301 if (pos == bucketSize) {
302 pos = 0;
303 scan = scan.next;
304 }
305 nextIndex++;
306 return obj;
307 }
308
309
310 public void remove()
311 {
312 throw new UnsupportedOperationException();
313 }
314
315 } // END QueueIterator
316
317
318 /**
319 * The <code>Bucket</code> class represents the container class used
320 * in queue to avoid expensive allocations and to save memory.
321 *
322 * @author Alberto Montresor
323 * @since Jgroup 0.1
324 */
325 private class Bucket {
326
327 //////////////////////////////////////////////////////////////////////////////////////////
328 // Fields
329 //////////////////////////////////////////////////////////////////////////////////////////
330
331 /** Stored objects */
332 Object[] objects;
333
334 /** Next element */
335 Bucket next;
336
337
338 //////////////////////////////////////////////////////////////////////////////////////////
339 // Constructor
340 //////////////////////////////////////////////////////////////////////////////////////////
341
342 /**
343 * Constructs a QueueBucket with the specified size
344 *
345 * @param bucketSize
346 * Number of elements in a bucket.
347 */
348 Bucket(int bucketSize)
349 {
350 this.objects = new Object[bucketSize];
351 this.next = null;
352 }
353
354 } // END Bucket
355
356 } // END Queue
357