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