Mercurial > hg > blitz_stable
comparison src/EDU/oswego/cs/dl/util/concurrent/CopyOnWriteArrayList.java @ 0:3dc0c5604566
Initial checkin of blitz 2.0 fcs - no installer yet.
author | Dan Creswell <dan.creswell@gmail.com> |
---|---|
date | Sat, 21 Mar 2009 11:00:06 +0000 |
parents | |
children |
comparison
equal
deleted
inserted
replaced
-1:000000000000 | 0:3dc0c5604566 |
---|---|
1 /* | |
2 File: CopyOnWriteArrayList.java | |
3 | |
4 Written by Doug Lea. Adapted from JDK1.2 ArrayList.java | |
5 which carries the following copyright: | |
6 | |
7 * Copyright 1997 by Sun Microsystems, Inc., | |
8 * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. | |
9 * All rights reserved. | |
10 * | |
11 * This software is the confidential and proprietary information | |
12 * of Sun Microsystems, Inc. ("Confidential Information"). You | |
13 * shall not disclose such Confidential Information and shall use | |
14 * it only in accordance with the terms of the license agreement | |
15 * you entered into with Sun. | |
16 | |
17 History: | |
18 Date Who What | |
19 21Jun1998 dl Create public version | |
20 9Oct1999 dl faster equals | |
21 29jun2001 dl Serialization methods now private | |
22 */ | |
23 | |
24 package EDU.oswego.cs.dl.util.concurrent; | |
25 import java.util.*; | |
26 | |
27 /** | |
28 * This class implements a variant of java.util.ArrayList in which | |
29 * all mutative operations (add, set, and so on) are implemented | |
30 * by making a fresh copy of the underlying array. | |
31 * <p> | |
32 * This is ordinarily too costly, but it becomes attractive when traversal | |
33 * operations vastly overwhelm mutations, and, especially, | |
34 * when you cannot or don't want to | |
35 * synchronize traversals, yet need to preclude interference | |
36 * among concurrent threads. | |
37 * The iterator method uses a reference to the | |
38 * state of the array at the point that the | |
39 * iterator was created. This array never changes during | |
40 * the lifetime of the iterator, so interference is impossible. | |
41 * (The iterator will not traverse elements added or changed | |
42 * since the iterator was created, but usually this is a desirable | |
43 * feature.) | |
44 * <p> | |
45 * As much code and documentation as possible was shamelessly copied from | |
46 * java.util.ArrayList (Thanks, Josh!), with the intent of preserving | |
47 * all semantics of ArrayList except for the copy-on-write | |
48 * property. | |
49 * (The java.util | |
50 * collection code could not be subclassed here since all of the existing | |
51 * collection classes assume elementwise mutability.) | |
52 * <p> | |
53 * Because of the copy-on-write policy, some one-by-one | |
54 * mutative operations | |
55 * in the java.util.Arrays and java.util.Collections classes | |
56 * are so time/space intensive as to never | |
57 * be worth calling (except perhaps as benchmarks for garbage collectors :-). | |
58 * <p> | |
59 * Three methods are supported in addition to | |
60 * those described in List and ArrayList. The addIfAbsent | |
61 * and addAllAbsent methods provide Set semantics for add, | |
62 * and are used in CopyOnWriteArraySet. However, they | |
63 * can also be used directly from this List version. | |
64 * The copyIn method (and | |
65 * a constructor that invokes it) allow | |
66 * you to copy in an initial array to use. This method can | |
67 * be useful when you first want to perform many operations | |
68 * on a plain array, and then make a copy available for | |
69 * use through the collection API. | |
70 * <p> | |
71 * Due to their strict read-only nature, | |
72 * element-changing operations on iterators | |
73 * (remove, set, and add) are not supported. These | |
74 * are the only methods throwing UnsupportedOperationException. | |
75 * <p> | |
76 * <p>[<a href="http://gee.cs.oswego.edu/dl/classes/EDU/oswego/cs/dl/util/concurrent/intro.html"> Introduction to this package. </a>] | |
77 * @see CopyOnWriteArraySet | |
78 **/ | |
79 | |
80 | |
81 public class CopyOnWriteArrayList implements List, Cloneable, java.io.Serializable { | |
82 /** | |
83 * The held array. Directly access only within synchronized | |
84 * methods | |
85 */ | |
86 | |
87 protected transient Object[] array_; | |
88 | |
89 /** | |
90 * Accessor to the array intended to be called from | |
91 * within unsynchronized read-only methods | |
92 **/ | |
93 protected synchronized Object[] array() { return array_; } | |
94 | |
95 /** | |
96 * Constructs an empty list | |
97 * | |
98 */ | |
99 public CopyOnWriteArrayList() { | |
100 array_ = new Object[0]; | |
101 } | |
102 | |
103 /** | |
104 * Constructs an list containing the elements of the specified | |
105 * Collection, in the order they are returned by the Collection's | |
106 * iterator. | |
107 */ | |
108 public CopyOnWriteArrayList(Collection c) { | |
109 array_ = new Object[c.size()]; | |
110 Iterator i = c.iterator(); | |
111 int size = 0; | |
112 while (i.hasNext()) | |
113 array_[size++] = i.next(); | |
114 } | |
115 | |
116 /** | |
117 * Create a new CopyOnWriteArrayList holding a copy of given array | |
118 * @param toCopyIn the array. A copy of this array is used as the | |
119 * internal array. | |
120 **/ | |
121 public CopyOnWriteArrayList(Object[] toCopyIn) { | |
122 copyIn(toCopyIn, 0, toCopyIn.length); | |
123 } | |
124 | |
125 /** | |
126 * Replace the held array with a copy of the <code>n</code> | |
127 * elements of the provided array, starting at position <code>first</code>. | |
128 * To copy an entire array, call with arguments (array, 0, array.length). | |
129 * @param toCopyIn the array. A copy of the indicated elements of | |
130 * this array is used as the | |
131 * internal array. | |
132 * @param first The index of first position of the array to | |
133 * start copying from. | |
134 * @param n the number of elements to copy. This will be the new size of | |
135 * the list. | |
136 **/ | |
137 public synchronized void copyIn(Object[] toCopyIn, int first, int n) { | |
138 array_ = new Object[n]; | |
139 System.arraycopy(toCopyIn, first, array_, 0, n); | |
140 } | |
141 | |
142 /** | |
143 * Returns the number of components in this list. | |
144 * | |
145 * @return the number of components in this list. | |
146 */ | |
147 public int size() { | |
148 return array().length; | |
149 } | |
150 | |
151 /** | |
152 * Tests if this list has no components. | |
153 * | |
154 * @return <code>true</code> if this list has no components; | |
155 * <code>false</code> otherwise. | |
156 */ | |
157 public boolean isEmpty() { | |
158 return size() == 0; | |
159 } | |
160 | |
161 /** | |
162 * Returns true if this list contains the specified element. | |
163 * | |
164 * @param o element whose presence in this List is to be tested. | |
165 */ | |
166 public boolean contains(Object elem) { | |
167 Object[] elementData = array(); | |
168 int len = elementData.length; | |
169 return indexOf(elem, elementData, len) >= 0; | |
170 } | |
171 | |
172 /** | |
173 * Searches for the first occurence of the given argument, testing | |
174 * for equality using the <code>equals</code> method. | |
175 * | |
176 * @param elem an object. | |
177 * @return the index of the first occurrence of the argument in this | |
178 * list; returns <code>-1</code> if the object is not found. | |
179 * @see Object#equals(Object) | |
180 */ | |
181 public int indexOf(Object elem) { | |
182 Object[] elementData = array(); | |
183 int len = elementData.length; | |
184 return indexOf(elem, elementData, len); | |
185 } | |
186 | |
187 | |
188 /** | |
189 * static version allows repeated call without needed | |
190 * to grab lock for array each time | |
191 **/ | |
192 | |
193 protected static int indexOf(Object elem, | |
194 Object[] elementData, | |
195 int len) { | |
196 if (elem == null) { | |
197 for (int i = 0; i < len; i++) | |
198 if (elementData[i]==null) | |
199 return i; | |
200 } else { | |
201 for (int i = 0; i < len; i++) | |
202 if (elem.equals(elementData[i])) | |
203 return i; | |
204 } | |
205 return -1; | |
206 } | |
207 | |
208 /** | |
209 * Searches for the first occurence of the given argument, beginning | |
210 * the search at <code>index</code>, and testing for equality using | |
211 * the <code>equals</code> method. | |
212 * | |
213 * @param elem an object. | |
214 * @param index the index to start searching from. | |
215 * @return the index of the first occurrence of the object argument in | |
216 * this List at position <code>index</code> or later in the | |
217 * List; returns <code>-1</code> if the object is not found. | |
218 * @see Object#equals(Object) | |
219 */ | |
220 | |
221 // needed in order to compile on 1.2b3 | |
222 public int indexOf(Object elem, int index) { | |
223 Object[] elementData = array(); | |
224 int elementCount = elementData.length; | |
225 | |
226 if (elem == null) { | |
227 for (int i = index ; i < elementCount ; i++) | |
228 if (elementData[i]==null) | |
229 return i; | |
230 } else { | |
231 for (int i = index ; i < elementCount ; i++) | |
232 if (elem.equals(elementData[i])) | |
233 return i; | |
234 } | |
235 return -1; | |
236 } | |
237 | |
238 /** | |
239 * Returns the index of the last occurrence of the specified object in | |
240 * this list. | |
241 * | |
242 * @param elem the desired component. | |
243 * @return the index of the last occurrence of the specified object in | |
244 * this list; returns -1 if the object is not found. | |
245 */ | |
246 public int lastIndexOf(Object elem) { | |
247 Object[] elementData = array(); | |
248 int len = elementData.length; | |
249 return lastIndexOf(elem, elementData, len); | |
250 } | |
251 | |
252 protected static int lastIndexOf(Object elem, | |
253 Object[] elementData, | |
254 int len) { | |
255 if (elem == null) { | |
256 for (int i = len-1; i >= 0; i--) | |
257 if (elementData[i]==null) | |
258 return i; | |
259 } else { | |
260 for (int i = len-1; i >= 0; i--) | |
261 if (elem.equals(elementData[i])) | |
262 return i; | |
263 } | |
264 return -1; | |
265 } | |
266 | |
267 /** | |
268 * Searches backwards for the specified object, starting from the | |
269 * specified index, and returns an index to it. | |
270 * | |
271 * @param elem the desired component. | |
272 * @param index the index to start searching from. | |
273 * @return the index of the last occurrence of the specified object in this | |
274 * List at position less than index in the List; | |
275 * -1 if the object is not found. | |
276 */ | |
277 | |
278 public int lastIndexOf(Object elem, int index) { | |
279 // needed in order to compile on 1.2b3 | |
280 Object[] elementData = array(); | |
281 if (elem == null) { | |
282 for (int i = index; i >= 0; i--) | |
283 if (elementData[i]==null) | |
284 return i; | |
285 } else { | |
286 for (int i = index; i >= 0; i--) | |
287 if (elem.equals(elementData[i])) | |
288 return i; | |
289 } | |
290 return -1; | |
291 } | |
292 | |
293 /** | |
294 * Returns a shallow copy of this list. (The elements themselves | |
295 * are not copied.) | |
296 * | |
297 * @return a clone of this list. | |
298 */ | |
299 public Object clone() { | |
300 try { | |
301 Object[] elementData = array(); | |
302 CopyOnWriteArrayList v = (CopyOnWriteArrayList)super.clone(); | |
303 v.array_ = new Object[elementData.length]; | |
304 System.arraycopy(elementData, 0, v.array_, 0, elementData.length); | |
305 return v; | |
306 } catch (CloneNotSupportedException e) { | |
307 // this shouldn't happen, since we are Cloneable | |
308 throw new InternalError(); | |
309 } | |
310 } | |
311 | |
312 /** | |
313 * Returns an array containing all of the elements in this list | |
314 * in the correct order. | |
315 */ | |
316 public Object[] toArray() { | |
317 Object[] elementData = array(); | |
318 Object[] result = new Object[elementData.length]; | |
319 System.arraycopy(elementData, 0, result, 0, elementData.length); | |
320 return result; | |
321 } | |
322 | |
323 /** | |
324 * Returns an array containing all of the elements in this list in the | |
325 * correct order. The runtime type of the returned array is that of the | |
326 * specified array. If the list fits in the specified array, it is | |
327 * returned therein. Otherwise, a new array is allocated with the runtime | |
328 * type of the specified array and the size of this list. | |
329 * <p> | |
330 * If the list fits in the specified array with room to spare | |
331 * (i.e., the array has more elements than the list), | |
332 * the element in the array immediately following the end of the | |
333 * collection is set to null. This is useful in determining the length | |
334 * of the list <em>only</em> if the caller knows that the list | |
335 * does not contain any null elements. | |
336 * | |
337 * @param a the array into which the elements of the list are to | |
338 * be stored, if it is big enough; otherwise, a new array of the | |
339 * same runtime type is allocated for this purpose. | |
340 * @return an array containing the elements of the list. | |
341 * @exception ArrayStoreException the runtime type of a is not a supertype | |
342 * of the runtime type of every element in this list. | |
343 */ | |
344 public Object[] toArray(Object a[]) { | |
345 Object[] elementData = array(); | |
346 | |
347 if (a.length < elementData.length) | |
348 a = (Object[]) | |
349 java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), | |
350 elementData.length); | |
351 | |
352 System.arraycopy(elementData, 0, a, 0, elementData.length); | |
353 | |
354 if (a.length > elementData.length) | |
355 a[elementData.length] = null; | |
356 | |
357 return a; | |
358 } | |
359 | |
360 // Positional Access Operations | |
361 | |
362 /** | |
363 * Returns the element at the specified position in this list. | |
364 * | |
365 * @param index index of element to return. | |
366 * @exception IndexOutOfBoundsException index is out of range (index | |
367 * < 0 || index >= size()). | |
368 */ | |
369 public Object get(int index) { | |
370 Object[] elementData = array(); | |
371 rangeCheck(index, elementData.length); | |
372 return elementData[index]; | |
373 } | |
374 | |
375 /** | |
376 * Replaces the element at the specified position in this list with | |
377 * the specified element. | |
378 * | |
379 * @param index index of element to replace. | |
380 * @param element element to be stored at the specified position. | |
381 * @return the element previously at the specified position. | |
382 * @exception IndexOutOfBoundsException index out of range | |
383 * (index < 0 || index >= size()). | |
384 */ | |
385 public synchronized Object set(int index, Object element) { | |
386 int len = array_.length; | |
387 rangeCheck(index, len); | |
388 Object oldValue = array_[index]; | |
389 | |
390 boolean same = (oldValue == element || | |
391 (element != null && element.equals(oldValue))); | |
392 if (!same) { | |
393 Object[] newArray = new Object[len]; | |
394 System.arraycopy(array_, 0, newArray, 0, len); | |
395 newArray[index] = element; | |
396 array_ = newArray; | |
397 } | |
398 return oldValue; | |
399 } | |
400 | |
401 /** | |
402 * Appends the specified element to the end of this list. | |
403 * | |
404 * @param element element to be appended to this list. | |
405 * @return true (as per the general contract of Collection.add). | |
406 */ | |
407 public synchronized boolean add(Object element) { | |
408 int len = array_.length; | |
409 Object[] newArray = new Object[len+1]; | |
410 System.arraycopy(array_, 0, newArray, 0, len); | |
411 newArray[len] = element; | |
412 array_ = newArray; | |
413 return true; | |
414 } | |
415 | |
416 /** | |
417 * Inserts the specified element at the specified position in this | |
418 * list. Shifts the element currently at that position (if any) and | |
419 * any subsequent elements to the right (adds one to their indices). | |
420 * | |
421 * @param index index at which the specified element is to be inserted. | |
422 * @param element element to be inserted. | |
423 * @exception IndexOutOfBoundsException index is out of range | |
424 * (index < 0 || index > size()). | |
425 */ | |
426 public synchronized void add(int index, Object element) { | |
427 int len = array_.length; | |
428 if (index > len || index < 0) | |
429 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len); | |
430 | |
431 Object[] newArray = new Object[len+1]; | |
432 System.arraycopy(array_, 0, newArray, 0, index); | |
433 newArray[index] = element; | |
434 System.arraycopy(array_, index, newArray, index+1, len - index); | |
435 array_ = newArray; | |
436 } | |
437 | |
438 /** | |
439 * Removes the element at the specified position in this list. | |
440 * Shifts any subsequent elements to the left (subtracts one from their | |
441 * indices). Returns the element that was removed from the list. | |
442 * | |
443 * @exception IndexOutOfBoundsException index out of range (index | |
444 * < 0 || index >= size()). | |
445 * @param index the index of the element to removed. | |
446 */ | |
447 public synchronized Object remove(int index) { | |
448 int len = array_.length; | |
449 rangeCheck(index, len); | |
450 Object oldValue = array_[index]; | |
451 Object[] newArray = new Object[len-1]; | |
452 System.arraycopy(array_, 0, newArray, 0, index); | |
453 int numMoved = len - index - 1; | |
454 if (numMoved > 0) | |
455 System.arraycopy(array_, index+1, newArray, index, numMoved); | |
456 array_ = newArray; | |
457 return oldValue; | |
458 } | |
459 | |
460 /** | |
461 * Removes a single instance of the specified element from this Collection, | |
462 * if it is present (optional operation). More formally, removes an | |
463 * element <code>e</code> such that <code>(o==null ? e==null : | |
464 * o.equals(e))</code>, if the Collection contains one or more such | |
465 * elements. Returns true if the Collection contained the specified | |
466 * element (or equivalently, if the Collection changed as a result of the | |
467 * call). | |
468 * | |
469 * @param element element to be removed from this Collection, if present. | |
470 * @return true if the Collection changed as a result of the call. | |
471 */ | |
472 public synchronized boolean remove(Object element) { | |
473 int len = array_.length; | |
474 if (len == 0) return false; | |
475 | |
476 // Copy while searching for element to remove | |
477 // This wins in the normal case of element being present | |
478 | |
479 int newlen = len-1; | |
480 Object[] newArray = new Object[newlen]; | |
481 | |
482 for (int i = 0; i < newlen; ++i) { | |
483 if (element == array_[i] || | |
484 (element != null && element.equals(array_[i]))) { | |
485 // found one; copy remaining and exit | |
486 for (int k = i + 1; k < len; ++k) newArray[k-1] = array_[k]; | |
487 array_ = newArray; | |
488 return true; | |
489 } | |
490 else | |
491 newArray[i] = array_[i]; | |
492 } | |
493 // special handling for last cell | |
494 | |
495 if (element == array_[newlen] || | |
496 (element != null && element.equals(array_[newlen]))) { | |
497 array_ = newArray; | |
498 return true; | |
499 } | |
500 else | |
501 return false; // throw away copy | |
502 | |
503 } | |
504 | |
505 | |
506 /** | |
507 * Removes from this List all of the elements whose index is between | |
508 * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding | |
509 * elements to the left (reduces their index). | |
510 * This call shortens the List by (toIndex - fromIndex) elements. (If | |
511 * toIndex==fromIndex, this operation has no effect.) | |
512 * | |
513 * @param fromIndex index of first element to be removed. | |
514 * @param fromIndex index after last element to be removed. | |
515 * @exception IndexOutOfBoundsException fromIndex or toIndex out of | |
516 * range (fromIndex < 0 || fromIndex >= size() || toIndex | |
517 * > size() || toIndex < fromIndex). | |
518 */ | |
519 public synchronized void removeRange(int fromIndex, int toIndex) { | |
520 int len = array_.length; | |
521 | |
522 if (fromIndex < 0 || fromIndex >= len || | |
523 toIndex > len || toIndex < fromIndex) | |
524 throw new IndexOutOfBoundsException(); | |
525 | |
526 int numMoved = len - toIndex; | |
527 int newlen = len - (toIndex-fromIndex); | |
528 Object[] newArray = new Object[newlen]; | |
529 System.arraycopy(array_, 0, newArray, 0, fromIndex); | |
530 System.arraycopy(array_, toIndex, newArray, fromIndex, numMoved); | |
531 array_ = newArray; | |
532 } | |
533 | |
534 | |
535 /** | |
536 * Append the element if not present. | |
537 * This operation can be used to obtain Set semantics | |
538 * for lists. | |
539 * @param element element to be added to this Collection, if absent. | |
540 * @return true if added | |
541 **/ | |
542 public synchronized boolean addIfAbsent(Object element) { | |
543 // Copy while checking if already present. | |
544 // This wins in the most common case where it is not present | |
545 int len = array_.length; | |
546 Object[] newArray = new Object[len + 1]; | |
547 for (int i = 0; i < len; ++i) { | |
548 if (element == array_[i] || | |
549 (element != null && element.equals(array_[i]))) | |
550 return false; // exit, throwing away copy | |
551 else | |
552 newArray[i] = array_[i]; | |
553 } | |
554 newArray[len] = element; | |
555 array_ = newArray; | |
556 return true; | |
557 } | |
558 | |
559 /** | |
560 * Returns true if this Collection contains all of the elements in the | |
561 * specified Collection. | |
562 * <p> | |
563 * This implementation iterates over the specified Collection, checking | |
564 * each element returned by the Iterator in turn to see if it's | |
565 * contained in this Collection. If all elements are so contained | |
566 * true is returned, otherwise false. | |
567 * | |
568 */ | |
569 public boolean containsAll(Collection c) { | |
570 Object[] elementData = array(); | |
571 int len = elementData.length; | |
572 Iterator e = c.iterator(); | |
573 while (e.hasNext()) | |
574 if(indexOf(e.next(), elementData, len) < 0) | |
575 return false; | |
576 | |
577 return true; | |
578 } | |
579 | |
580 | |
581 /** | |
582 * Removes from this Collection all of its elements that are contained in | |
583 * the specified Collection. This is a particularly expensive operation | |
584 * in this class because of the need for an internal temporary array. | |
585 * <p> | |
586 * | |
587 * @return true if this Collection changed as a result of the call. | |
588 */ | |
589 public synchronized boolean removeAll(Collection c) { | |
590 Object[] elementData = array_; | |
591 int len = elementData.length; | |
592 if (len == 0) return false; | |
593 | |
594 // temp array holds those elements we know we want to keep | |
595 Object[] temp = new Object[len]; | |
596 int newlen = 0; | |
597 for (int i = 0; i < len; ++i) { | |
598 Object element = elementData[i]; | |
599 if (!c.contains(element)) { | |
600 temp[newlen++] = element; | |
601 } | |
602 } | |
603 | |
604 if (newlen == len) return false; | |
605 | |
606 // copy temp as new array | |
607 Object[] newArray = new Object[newlen]; | |
608 System.arraycopy(temp, 0, newArray, 0, newlen); | |
609 array_ = newArray; | |
610 return true; | |
611 } | |
612 | |
613 /** | |
614 * Retains only the elements in this Collection that are contained in the | |
615 * specified Collection (optional operation). In other words, removes from | |
616 * this Collection all of its elements that are not contained in the | |
617 * specified Collection. | |
618 * @return true if this Collection changed as a result of the call. | |
619 */ | |
620 public synchronized boolean retainAll(Collection c) { | |
621 Object[] elementData = array_; | |
622 int len = elementData.length; | |
623 if (len == 0) return false; | |
624 | |
625 Object[] temp = new Object[len]; | |
626 int newlen = 0; | |
627 for (int i = 0; i < len; ++i) { | |
628 Object element = elementData[i]; | |
629 if (c.contains(element)) { | |
630 temp[newlen++] = element; | |
631 } | |
632 } | |
633 | |
634 if (newlen == len) return false; | |
635 | |
636 Object[] newArray = new Object[newlen]; | |
637 System.arraycopy(temp, 0, newArray, 0, newlen); | |
638 array_ = newArray; | |
639 return true; | |
640 } | |
641 | |
642 /** | |
643 * Appends all of the elements in the specified Collection that | |
644 * are not already contained in this list, to the end of | |
645 * this list, in the order that they are returned by the | |
646 * specified Collection's Iterator. | |
647 * | |
648 * @param c elements to be added into this list. | |
649 * @return the number of elements added | |
650 */ | |
651 | |
652 public synchronized int addAllAbsent(Collection c) { | |
653 int numNew = c.size(); | |
654 if (numNew == 0) return 0; | |
655 | |
656 Object[] elementData = array_; | |
657 int len = elementData.length; | |
658 | |
659 Object[] temp = new Object[numNew]; | |
660 int added = 0; | |
661 Iterator e = c.iterator(); | |
662 while (e.hasNext()) { | |
663 Object element = e.next(); | |
664 if (indexOf(element, elementData, len) < 0) { | |
665 if (indexOf(element, temp, added) < 0) { | |
666 temp[added++] = element; | |
667 } | |
668 } | |
669 } | |
670 | |
671 if (added == 0) return 0; | |
672 | |
673 Object[] newArray = new Object[len+added]; | |
674 System.arraycopy(elementData, 0, newArray, 0, len); | |
675 System.arraycopy(temp, 0, newArray, len, added); | |
676 array_ = newArray; | |
677 return added; | |
678 } | |
679 | |
680 /** | |
681 * Removes all of the elements from this list. | |
682 * | |
683 */ | |
684 public synchronized void clear() { | |
685 array_ = new Object[0]; | |
686 } | |
687 | |
688 /** | |
689 * Appends all of the elements in the specified Collection to the end of | |
690 * this list, in the order that they are returned by the | |
691 * specified Collection's Iterator. | |
692 * | |
693 * @param c elements to be inserted into this list. | |
694 */ | |
695 public synchronized boolean addAll(Collection c) { | |
696 int numNew = c.size(); | |
697 if (numNew == 0) return false; | |
698 | |
699 int len = array_.length; | |
700 Object[] newArray = new Object[len+numNew]; | |
701 System.arraycopy(array_, 0, newArray, 0, len); | |
702 Iterator e = c.iterator(); | |
703 for (int i=0; i<numNew; i++) | |
704 newArray[len++] = e.next(); | |
705 array_ = newArray; | |
706 | |
707 return true; | |
708 } | |
709 | |
710 /** | |
711 * Inserts all of the elements in the specified Collection into this | |
712 * list, starting at the specified position. Shifts the element | |
713 * currently at that position (if any) and any subsequent elements to | |
714 * the right (increases their indices). The new elements will appear | |
715 * in the list in the order that they are returned by the | |
716 * specified Collection's iterator. | |
717 * | |
718 * @param index index at which to insert first element | |
719 * from the specified collection. | |
720 * @param c elements to be inserted into this list. | |
721 * @exception IndexOutOfBoundsException index out of range (index | |
722 * < 0 || index > size()). | |
723 */ | |
724 public synchronized boolean addAll(int index, Collection c) { | |
725 int len = array_.length; | |
726 if (index > len || index < 0) | |
727 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len); | |
728 | |
729 int numNew = c.size(); | |
730 if (numNew == 0) return false; | |
731 | |
732 Object[] newArray = new Object[len+numNew]; | |
733 System.arraycopy(array_, 0, newArray, 0, len); | |
734 int numMoved = len - index; | |
735 if (numMoved > 0) | |
736 System.arraycopy(array_, index, newArray, index + numNew, numMoved); | |
737 Iterator e = c.iterator(); | |
738 for (int i=0; i<numNew; i++) | |
739 newArray[index++] = e.next(); | |
740 array_ = newArray; | |
741 | |
742 return true; | |
743 } | |
744 | |
745 /** | |
746 * Check if the given index is in range. If not, throw an appropriate | |
747 * runtime exception. | |
748 */ | |
749 protected void rangeCheck(int index, int length) { | |
750 if (index >= length || index < 0) | |
751 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+ length); | |
752 } | |
753 /** | |
754 * Save the state of the list to a stream (i.e., serialize it). | |
755 * | |
756 * @serialData The length of the array backing the list is emitted | |
757 * (int), followed by all of its elements (each an Object) | |
758 * in the proper order. | |
759 */ | |
760 private void writeObject(java.io.ObjectOutputStream s) | |
761 throws java.io.IOException{ | |
762 // Write out element count, and any hidden stuff | |
763 s.defaultWriteObject(); | |
764 | |
765 Object[] elementData = array(); | |
766 // Write out array length | |
767 s.writeInt(elementData.length); | |
768 | |
769 // Write out all elements in the proper order. | |
770 for (int i=0; i<elementData.length; i++) | |
771 s.writeObject(elementData[i]); | |
772 } | |
773 | |
774 /** | |
775 * Reconstitute the list from a stream (i.e., deserialize it). | |
776 */ | |
777 private synchronized void readObject(java.io.ObjectInputStream s) | |
778 throws java.io.IOException, ClassNotFoundException { | |
779 // Read in size, and any hidden stuff | |
780 s.defaultReadObject(); | |
781 | |
782 // Read in array length and allocate array | |
783 int arrayLength = s.readInt(); | |
784 Object[] elementData = new Object[arrayLength]; | |
785 | |
786 // Read in all elements in the proper order. | |
787 for (int i=0; i<elementData.length; i++) | |
788 elementData[i] = s.readObject(); | |
789 array_ = elementData; | |
790 } | |
791 | |
792 /** | |
793 * Returns a string representation of this Collection, containing | |
794 * the String representation of each element. | |
795 */ | |
796 public String toString() { | |
797 StringBuffer buf = new StringBuffer(); | |
798 Iterator e = iterator(); | |
799 buf.append("["); | |
800 int maxIndex = size() - 1; | |
801 for (int i = 0; i <= maxIndex; i++) { | |
802 buf.append(String.valueOf(e.next())); | |
803 if (i < maxIndex) | |
804 buf.append(", "); | |
805 } | |
806 buf.append("]"); | |
807 return buf.toString(); | |
808 } | |
809 | |
810 | |
811 /** | |
812 * Compares the specified Object with this List for equality. Returns true | |
813 * if and only if the specified Object is also a List, both Lists have the | |
814 * same size, and all corresponding pairs of elements in the two Lists are | |
815 * <em>equal</em>. (Two elements <code>e1</code> and <code>e2</code> are | |
816 * <em>equal</em> if <code>(e1==null ? e2==null : e1.equals(e2))</code>.) | |
817 * In other words, two Lists are defined to be equal if they contain the | |
818 * same elements in the same order. | |
819 * <p> | |
820 * This implementation first checks if the specified object is this | |
821 * List. If so, it returns true; if not, it checks if the specified | |
822 * object is a List. If not, it returns false; if so, it iterates over | |
823 * both lists, comparing corresponding pairs of elements. If any | |
824 * comparison returns false, this method returns false. If either | |
825 * Iterator runs out of elements before before the other it returns false | |
826 * (as the Lists are of unequal length); otherwise it returns true when | |
827 * the iterations complete. | |
828 * | |
829 * @param o the Object to be compared for equality with this List. | |
830 * @return true if the specified Object is equal to this List. | |
831 */ | |
832 public boolean equals(Object o) { | |
833 if (o == this) | |
834 return true; | |
835 if (!(o instanceof List)) | |
836 return false; | |
837 | |
838 List l2 = (List)(o); | |
839 if (size() != l2.size()) | |
840 return false; | |
841 | |
842 ListIterator e1 = listIterator(); | |
843 ListIterator e2 = l2.listIterator(); | |
844 while(e1.hasNext()) { | |
845 Object o1 = e1.next(); | |
846 Object o2 = e2.next(); | |
847 if (!(o1==null ? o2==null : o1.equals(o2))) | |
848 return false; | |
849 } | |
850 return true; | |
851 } | |
852 | |
853 /** | |
854 * Returns the hash code value for this List. | |
855 * <p> | |
856 * This implementation uses exactly the code that is used to define | |
857 * the List hash function in the documentation for List.hashCode. | |
858 */ | |
859 public int hashCode() { | |
860 int hashCode = 1; | |
861 Iterator i = iterator(); | |
862 while (i.hasNext()) { | |
863 Object obj = i.next(); | |
864 hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); | |
865 } | |
866 return hashCode; | |
867 } | |
868 | |
869 /** | |
870 * Returns an Iterator over the elements contained in this collection. | |
871 * The iterator provides a snapshot of the state of the list | |
872 * when the iterator was constructed. No synchronization is | |
873 * needed while traversing the iterator. The iterator does | |
874 * <em>NOT</em> support the <code>remove</code> method. | |
875 */ | |
876 public Iterator iterator() { | |
877 return new COWIterator(array(), 0); | |
878 } | |
879 | |
880 /** | |
881 * Returns an Iterator of the elements in this List (in proper sequence). | |
882 * The iterator provides a snapshot of the state of the list | |
883 * when the iterator was constructed. No synchronization is | |
884 * needed while traversing the iterator. The iterator does | |
885 * <em>NOT</em> support the <code>remove</code>, <code>set</code>, | |
886 * or <code>add</code> methods. | |
887 * | |
888 */ | |
889 | |
890 public ListIterator listIterator() { | |
891 return new COWIterator(array(), 0); | |
892 } | |
893 | |
894 /** | |
895 * Returns a ListIterator of the elements in this List (in proper | |
896 * sequence), starting at the specified position in the List. The | |
897 * specified index indicates the first element that would be returned by | |
898 * an initial call to nextElement. An initial call to previousElement | |
899 * would return the element with the specified index minus one. | |
900 * The ListIterator returned by this implementation will throw | |
901 * an UnsupportedOperationException in its remove, set and | |
902 * add methods. | |
903 * | |
904 * @param index index of first element to be returned from the | |
905 * ListIterator (by a call to getNext). | |
906 * @exception IndexOutOfBoundsException index is out of range | |
907 * (index < 0 || index > size()). | |
908 */ | |
909 public ListIterator listIterator(final int index) { | |
910 Object[] elementData = array(); | |
911 int len = elementData.length; | |
912 if (index<0 || index>len) | |
913 throw new IndexOutOfBoundsException("Index: "+index); | |
914 | |
915 return new COWIterator(array(), index); | |
916 } | |
917 | |
918 protected static class COWIterator implements ListIterator { | |
919 | |
920 /** Snapshot of the array **/ | |
921 protected final Object[] array; | |
922 | |
923 /** | |
924 * Index of element to be returned by subsequent call to next. | |
925 */ | |
926 protected int cursor; | |
927 | |
928 protected COWIterator(Object[] elementArray, int initialCursor) { | |
929 array = elementArray; | |
930 cursor = initialCursor; | |
931 } | |
932 | |
933 public boolean hasNext() { | |
934 return cursor < array.length; | |
935 } | |
936 | |
937 public boolean hasPrevious() { | |
938 return cursor > 0; | |
939 } | |
940 | |
941 public Object next() { | |
942 try { | |
943 return array[cursor++]; | |
944 } | |
945 catch (IndexOutOfBoundsException ex) { | |
946 throw new NoSuchElementException(); | |
947 } | |
948 } | |
949 | |
950 public Object previous() { | |
951 try { | |
952 return array[--cursor]; | |
953 } catch(IndexOutOfBoundsException e) { | |
954 throw new NoSuchElementException(); | |
955 } | |
956 } | |
957 | |
958 public int nextIndex() { | |
959 return cursor; | |
960 } | |
961 | |
962 public int previousIndex() { | |
963 return cursor-1; | |
964 } | |
965 | |
966 /** | |
967 * Not supported. Always throws UnsupportedOperationException. | |
968 * @exception UnsupportedOperationException remove is not supported | |
969 * by this Iterator. | |
970 */ | |
971 | |
972 public void remove() { | |
973 throw new UnsupportedOperationException(); | |
974 } | |
975 | |
976 /** | |
977 * Not supported. Always throws UnsupportedOperationException. | |
978 * @exception UnsupportedOperationException set is not supported | |
979 * by this Iterator. | |
980 */ | |
981 public void set(Object o) { | |
982 throw new UnsupportedOperationException(); | |
983 } | |
984 | |
985 /** | |
986 * Not supported. Always throws UnsupportedOperationException. | |
987 * @exception UnsupportedOperationException add is not supported | |
988 * by this Iterator. | |
989 */ | |
990 public void add(Object o) { | |
991 throw new UnsupportedOperationException(); | |
992 } | |
993 } | |
994 | |
995 | |
996 /** | |
997 * Returns a view of the portion of this List between fromIndex, | |
998 * inclusive, and toIndex, exclusive. The returned List is backed by this | |
999 * List, so changes in the returned List are reflected in this List, and | |
1000 * vice-versa. While mutative operations are supported, they are | |
1001 * probably not very useful for CopyOnWriteArrays. | |
1002 * </p> | |
1003 * The semantics of the List returned by this method become undefined if | |
1004 * the backing list (i.e., this List) is <i>structurally modified</i> in | |
1005 * any way other than via the returned List. (Structural modifications are | |
1006 * those that change the size of the List, or otherwise perturb it in such | |
1007 * a fashion that iterations in progress may yield incorrect results.) | |
1008 * | |
1009 * @param fromIndex low endpoint (inclusive) of the subList. | |
1010 * @param toKey high endpoint (exclusive) of the subList. | |
1011 * @return a view of the specified range within this List. | |
1012 * @exception IndexOutOfBoundsException Illegal endpoint index value | |
1013 * (fromIndex < 0 || toIndex > size || fromIndex > toIndex). | |
1014 */ | |
1015 public synchronized List subList(int fromIndex, int toIndex) { | |
1016 // synchronized since sublist ctor depends on it. | |
1017 int len = array_.length; | |
1018 if (fromIndex<0 || toIndex>len || fromIndex>toIndex) | |
1019 throw new IndexOutOfBoundsException(); | |
1020 return new COWSubList(this, fromIndex, toIndex); | |
1021 } | |
1022 | |
1023 protected static class COWSubList extends AbstractList { | |
1024 | |
1025 /* | |
1026 This is currently a bit sleazy. The class | |
1027 extends AbstractList merely for convenience, | |
1028 to avoid having to define addAll, etc. This | |
1029 doesn't hurt, but is stupid and wasteful. | |
1030 This class does not need or use modCount mechanics | |
1031 in AbstractList, but does need to check for | |
1032 concurrent modification using similar mechanics. | |
1033 On each operation, the array that we expect | |
1034 the backing list to use is checked and updated. | |
1035 Since we do this for all of the base operations | |
1036 invoked by those defined in AbstractList, all is well. | |
1037 | |
1038 It's not clear whether this is worth cleaning up. | |
1039 The kinds of list operations inherited from | |
1040 AbstractList are are already so slow on COW sublists | |
1041 that adding a bit more space/time doesn't seem | |
1042 even noticeable. | |
1043 */ | |
1044 | |
1045 protected final CopyOnWriteArrayList l; | |
1046 protected final int offset; | |
1047 protected int size; | |
1048 protected Object[] expectedArray; | |
1049 | |
1050 protected COWSubList(CopyOnWriteArrayList list, | |
1051 int fromIndex, int toIndex) { | |
1052 l = list; | |
1053 expectedArray = l.array(); | |
1054 offset = fromIndex; | |
1055 size = toIndex - fromIndex; | |
1056 } | |
1057 | |
1058 // only call this holding l's lock | |
1059 protected void checkForComodification() { | |
1060 if (l.array_ != expectedArray) | |
1061 throw new ConcurrentModificationException(); | |
1062 } | |
1063 | |
1064 // only call this holding l's lock | |
1065 protected void rangeCheck(int index) { | |
1066 if (index<0 || index>=size) | |
1067 throw new IndexOutOfBoundsException("Index: "+index+ | |
1068 ",Size: "+size); | |
1069 } | |
1070 | |
1071 | |
1072 public Object set(int index, Object element) { | |
1073 synchronized(l) { | |
1074 rangeCheck(index); | |
1075 checkForComodification(); | |
1076 Object x = l.set(index+offset, element); | |
1077 expectedArray = l.array_; | |
1078 return x; | |
1079 } | |
1080 } | |
1081 | |
1082 public Object get(int index) { | |
1083 synchronized(l) { | |
1084 rangeCheck(index); | |
1085 checkForComodification(); | |
1086 return l.get(index+offset); | |
1087 } | |
1088 } | |
1089 | |
1090 public int size() { | |
1091 synchronized(l) { | |
1092 checkForComodification(); | |
1093 return size; | |
1094 } | |
1095 } | |
1096 | |
1097 public void add(int index, Object element) { | |
1098 synchronized(l) { | |
1099 checkForComodification(); | |
1100 if (index<0 || index>size) | |
1101 throw new IndexOutOfBoundsException(); | |
1102 l.add(index+offset, element); | |
1103 expectedArray = l.array_; | |
1104 size++; | |
1105 } | |
1106 } | |
1107 | |
1108 public Object remove(int index) { | |
1109 synchronized(l) { | |
1110 rangeCheck(index); | |
1111 checkForComodification(); | |
1112 Object result = l.remove(index+offset); | |
1113 expectedArray = l.array_; | |
1114 size--; | |
1115 return result; | |
1116 } | |
1117 } | |
1118 | |
1119 public Iterator iterator() { | |
1120 synchronized(l) { | |
1121 checkForComodification(); | |
1122 return new COWSubListIterator(0); | |
1123 } | |
1124 } | |
1125 | |
1126 public ListIterator listIterator(final int index) { | |
1127 synchronized(l) { | |
1128 checkForComodification(); | |
1129 if (index<0 || index>size) | |
1130 throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); | |
1131 return new COWSubListIterator(index); | |
1132 } | |
1133 } | |
1134 | |
1135 protected class COWSubListIterator implements ListIterator { | |
1136 protected final ListIterator i; | |
1137 protected final int index; | |
1138 protected COWSubListIterator(int index) { | |
1139 this.index = index; | |
1140 i = l.listIterator(index+offset); | |
1141 } | |
1142 | |
1143 public boolean hasNext() { | |
1144 return nextIndex() < size; | |
1145 } | |
1146 | |
1147 public Object next() { | |
1148 if (hasNext()) | |
1149 return i.next(); | |
1150 else | |
1151 throw new NoSuchElementException(); | |
1152 } | |
1153 | |
1154 public boolean hasPrevious() { | |
1155 return previousIndex() >= 0; | |
1156 } | |
1157 | |
1158 public Object previous() { | |
1159 if (hasPrevious()) | |
1160 return i.previous(); | |
1161 else | |
1162 throw new NoSuchElementException(); | |
1163 } | |
1164 | |
1165 public int nextIndex() { | |
1166 return i.nextIndex() - offset; | |
1167 } | |
1168 | |
1169 public int previousIndex() { | |
1170 return i.previousIndex() - offset; | |
1171 } | |
1172 | |
1173 public void remove() { | |
1174 throw new UnsupportedOperationException(); | |
1175 } | |
1176 | |
1177 public void set(Object o) { | |
1178 throw new UnsupportedOperationException(); | |
1179 } | |
1180 | |
1181 public void add(Object o) { | |
1182 throw new UnsupportedOperationException(); | |
1183 } | |
1184 } | |
1185 | |
1186 | |
1187 public List subList(int fromIndex, int toIndex) { | |
1188 synchronized(l) { | |
1189 checkForComodification(); | |
1190 if (fromIndex<0 || toIndex>size) | |
1191 throw new IndexOutOfBoundsException(); | |
1192 return new COWSubList(l, fromIndex+offset, toIndex+offset); | |
1193 } | |
1194 } | |
1195 | |
1196 | |
1197 } | |
1198 | |
1199 } |