0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one
0003: * or more contributor license agreements. See the NOTICE file
0004: * distributed with this work for additional information
0005: * regarding copyright ownership. The ASF licenses this file
0006: * to you under the Apache License, Version 2.0 (the
0007: * "License"); you may not use this file except in compliance
0008: * with the License. You may obtain a copy of the License at
0009: *
0010: * http://www.apache.org/licenses/LICENSE-2.0
0011: *
0012: * Unless required by applicable law or agreed to in writing,
0013: * software distributed under the License is distributed on an
0014: * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
0015: * KIND, either express or implied. See the License for the
0016: * specific language governing permissions and limitations
0017: * under the License.
0018: */
0019: /*
0020: * Written by Dawid Kurzyniec, on the basis of public specifications and
0021: * public domain sources from JSR 166, and released to the public domain,
0022: * as explained at http://creativecommons.org/licenses/publicdomain.
0023: */
0024: package org.apache.openjpa.lib.util.concurrent;
0025:
0026: import java.io.IOException;
0027: import java.io.ObjectInputStream;
0028: import java.io.ObjectOutputStream;
0029: import java.io.Serializable;
0030: import java.lang.reflect.Array;
0031: import java.util.Collection;
0032: import java.util.ConcurrentModificationException;
0033: import java.util.Iterator;
0034: import java.util.List;
0035: import java.util.ListIterator;
0036: import java.util.NoSuchElementException;
0037:
0038: public class CopyOnWriteArrayList implements List, Cloneable,
0039: Serializable {
0040:
0041: private static final long serialVersionUID = 8673264195747942595L;
0042:
0043: private volatile transient Object[] array;
0044:
0045: public CopyOnWriteArrayList() {
0046: setArray(new Object[0]);
0047: }
0048:
0049: public CopyOnWriteArrayList(Collection c) {
0050: // must deal with concurrent collections
0051: Object[] array = c.toArray();
0052: // make sure the array is Object[] type
0053: if (array.getClass() != Object[].class) {
0054: array = Arrays.copyOf(array, array.length, Object[].class);
0055: }
0056: // assume that c.toArray() has returned a new array instance, as
0057: // required by the spec
0058: setArray(array);
0059: }
0060:
0061: public CopyOnWriteArrayList(Object[] array) {
0062: setArray(Arrays.copyOf(array, array.length, Object[].class));
0063: }
0064:
0065: final Object[] getArray() {
0066: return array;
0067: }
0068:
0069: final void setArray(Object[] array) {
0070: this .array = array;
0071: }
0072:
0073: public int size() {
0074: return getArray().length;
0075: }
0076:
0077: public boolean isEmpty() {
0078: return getArray().length == 0;
0079: }
0080:
0081: private static int search(Object[] array, Object subject, int pos,
0082: int end) {
0083: if (subject == null) {
0084: for (; pos < end; pos++) {
0085: if (array[pos] == null)
0086: return pos;
0087: }
0088: } else {
0089: for (; pos < end; pos++) {
0090: if (subject.equals(array[pos]))
0091: return pos;
0092: }
0093: }
0094: return -1;
0095: }
0096:
0097: private static int reverseSearch(Object[] array, Object subject,
0098: int start, int pos) {
0099: if (subject == null) {
0100: for (pos--; pos >= start; pos--) {
0101: if (array[pos] == null)
0102: return pos;
0103: }
0104: } else {
0105: for (pos--; pos >= start; pos--) {
0106: if (subject.equals(array[pos]))
0107: return pos;
0108: }
0109: }
0110: return -1;
0111: }
0112:
0113: public boolean contains(Object o) {
0114: Object[] array = getArray();
0115: return search(array, o, 0, array.length) >= 0;
0116: }
0117:
0118: public Iterator iterator() {
0119: return new COWIterator(getArray(), 0);
0120: }
0121:
0122: public Object[] toArray() {
0123: Object[] array = getArray();
0124: return Arrays.copyOf(array, array.length, Object[].class);
0125: }
0126:
0127: public Object[] toArray(Object[] a) {
0128: Object[] array = getArray();
0129: int length = array.length;
0130: if (a.length < length) {
0131: return Arrays.copyOf(array, length, a.getClass());
0132: } else {
0133: System.arraycopy(array, 0, a, 0, length);
0134: if (a.length > length)
0135: a[length] = null;
0136: return a;
0137: }
0138: }
0139:
0140: public boolean add(Object o) {
0141: synchronized (this ) {
0142: Object[] oldarr = getArray();
0143: int length = oldarr.length;
0144: Object[] newarr = new Object[length + 1];
0145: System.arraycopy(oldarr, 0, newarr, 0, length);
0146: newarr[length] = o;
0147: setArray(newarr);
0148: return true;
0149: }
0150: }
0151:
0152: public boolean addIfAbsent(Object o) {
0153: synchronized (this ) {
0154: Object[] oldarr = getArray();
0155: int length = oldarr.length;
0156: if (search(array, o, 0, length) >= 0)
0157: return false;
0158: Object[] newarr = new Object[length + 1];
0159: System.arraycopy(oldarr, 0, newarr, 0, length);
0160: newarr[length] = o;
0161: setArray(newarr);
0162: return true;
0163: }
0164: }
0165:
0166: public int addAllAbsent(Collection c) {
0167: Object[] arr = c.toArray();
0168: if (arr.length == 0)
0169: return 0;
0170: synchronized (this ) {
0171: Object[] oldarr = getArray();
0172: int oldlength = oldarr.length;
0173: Object[] tmp = new Object[arr.length];
0174: int added = 0;
0175: for (int i = 0; i < arr.length; i++) {
0176: Object o = arr[i];
0177: if (search(oldarr, o, 0, oldlength) < 0
0178: && search(tmp, o, 0, added) < 0) {
0179: tmp[added++] = o;
0180: }
0181: }
0182: if (added == 0)
0183: return 0;
0184: Object[] newarr = new Object[oldlength + added];
0185: System.arraycopy(oldarr, 0, newarr, 0, oldlength);
0186: System.arraycopy(tmp, 0, newarr, oldlength, added);
0187: setArray(newarr);
0188: return added;
0189: }
0190: }
0191:
0192: public boolean remove(Object o) {
0193: synchronized (this ) {
0194: Object[] array = getArray();
0195: int length = array.length;
0196: int pos = search(array, o, 0, length);
0197: if (pos < 0)
0198: return false;
0199: Object[] newarr = new Object[length - 1];
0200: int moved = length - pos - 1;
0201: if (pos > 0)
0202: System.arraycopy(array, 0, newarr, 0, pos);
0203: if (moved > 0)
0204: System.arraycopy(array, pos + 1, newarr, pos, moved);
0205: setArray(newarr);
0206: return true;
0207: }
0208: }
0209:
0210: public boolean containsAll(Collection c) {
0211: Object[] array = getArray();
0212: for (Iterator itr = c.iterator(); itr.hasNext();) {
0213: if (search(array, itr.next(), 0, array.length) < 0)
0214: return false;
0215: }
0216: return true;
0217: }
0218:
0219: public boolean addAll(Collection c) {
0220: // must deal with concurrent collections
0221: Object[] ca = c.toArray();
0222: if (ca.length == 0)
0223: return false;
0224: synchronized (this ) {
0225: Object[] oldarr = getArray();
0226: int length = oldarr.length;
0227: Object[] newarr = new Object[length + ca.length];
0228: System.arraycopy(oldarr, 0, newarr, 0, length);
0229: int pos = length;
0230: System.arraycopy(ca, 0, newarr, pos, ca.length);
0231: setArray(newarr);
0232: return true;
0233: }
0234: }
0235:
0236: public boolean addAll(int index, Collection c) {
0237: // must deal with concurrent collections
0238: Object[] ca = c.toArray();
0239: synchronized (this ) {
0240: Object[] oldarr = getArray();
0241: int length = oldarr.length;
0242: if (index < 0 || index > length) {
0243: throw new IndexOutOfBoundsException("Index: " + index
0244: + ", Size: " + length);
0245: }
0246: if (ca.length == 0)
0247: return false;
0248: Object[] newarr = new Object[length + ca.length];
0249: int moved = length - index;
0250: System.arraycopy(oldarr, 0, newarr, 0, index);
0251: System.arraycopy(ca, 0, newarr, index, ca.length);
0252: if (moved > 0) {
0253: System.arraycopy(oldarr, index, newarr, index
0254: + ca.length, moved);
0255: }
0256: setArray(newarr);
0257: return true;
0258: }
0259: }
0260:
0261: public boolean removeAll(Collection c) {
0262: if (c.isEmpty())
0263: return false;
0264: synchronized (this ) {
0265: Object[] array = getArray();
0266: int length = array.length;
0267: Object[] tmp = new Object[length];
0268: int newlen = 0;
0269: for (int i = 0; i < length; i++) {
0270: Object o = array[i];
0271: if (!c.contains(o))
0272: tmp[newlen++] = o;
0273: }
0274: if (newlen == length)
0275: return false;
0276: Object[] newarr = new Object[newlen];
0277: System.arraycopy(tmp, 0, newarr, 0, newlen);
0278: setArray(newarr);
0279: return true;
0280: }
0281: }
0282:
0283: public boolean retainAll(Collection c) {
0284: synchronized (this ) {
0285: Object[] array = getArray();
0286: int length = array.length;
0287: Object[] tmp = new Object[length];
0288: int newlen = 0;
0289: for (int i = 0; i < length; i++) {
0290: Object o = array[i];
0291: if (c.contains(o))
0292: tmp[newlen++] = o;
0293: }
0294: if (newlen == length)
0295: return false;
0296: Object[] newarr = new Object[newlen];
0297: System.arraycopy(tmp, 0, newarr, 0, newlen);
0298: setArray(newarr);
0299: return true;
0300: }
0301: }
0302:
0303: public void clear() {
0304: setArray(new Object[0]);
0305: }
0306:
0307: public Object clone() {
0308: try {
0309: return super .clone();
0310: } catch (CloneNotSupportedException e) {
0311: throw new InternalError();
0312: }
0313: }
0314:
0315: public boolean equals(Object o) {
0316: if (o == this )
0317: return true;
0318: if (!(o instanceof List))
0319: return false;
0320:
0321: ListIterator itr = ((List) o).listIterator();
0322: Object[] array = getArray();
0323: int length = array.length;
0324: int idx = 0;
0325: while (idx < length && itr.hasNext()) {
0326: Object o1 = array[idx++];
0327: Object o2 = itr.next();
0328: if (!eq(o1, o2))
0329: return false;
0330: }
0331: return (idx == length && !itr.hasNext());
0332: }
0333:
0334: public int hashCode() {
0335: int hashCode = 1;
0336: Object[] array = getArray();
0337: int length = array.length;
0338: for (int i = 0; i < length; i++) {
0339: Object o = array[i];
0340: hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
0341: }
0342: return hashCode;
0343: }
0344:
0345: public Object get(int index) {
0346: return getArray()[index];
0347: }
0348:
0349: public Object set(int index, Object element) {
0350: synchronized (this ) {
0351: Object[] oldarr = getArray();
0352: int length = oldarr.length;
0353: // piggyback the array bounds check
0354: Object oldVal = oldarr[index];
0355: if (oldVal == element) {
0356: setArray(oldarr);
0357: } else {
0358: Object[] newarr = new Object[length];
0359: System.arraycopy(oldarr, 0, newarr, 0, length);
0360: newarr[index] = element;
0361: setArray(newarr);
0362: }
0363: return oldVal;
0364: }
0365: }
0366:
0367: public void add(int index, Object element) {
0368: synchronized (this ) {
0369: Object[] oldarr = getArray();
0370: int length = oldarr.length;
0371: if (index < 0 || index > length) {
0372: throw new IndexOutOfBoundsException("Index: " + index
0373: + ", Size: " + length);
0374: }
0375: Object[] newarr = new Object[length + 1];
0376: int moved = length - index;
0377: System.arraycopy(oldarr, 0, newarr, 0, index);
0378: newarr[index] = element;
0379: if (moved > 0) {
0380: System.arraycopy(oldarr, index, newarr, index + 1,
0381: moved);
0382: }
0383: setArray(newarr);
0384: }
0385: }
0386:
0387: public Object remove(int index) {
0388: synchronized (this ) {
0389: Object[] array = getArray();
0390: int length = array.length;
0391: if (index < 0 || index >= length) {
0392: throw new IndexOutOfBoundsException("Index: " + index
0393: + ", Size: " + length);
0394: }
0395: Object result = array[index];
0396: Object[] newarr = new Object[length - 1];
0397: int moved = length - index - 1;
0398: if (index > 0)
0399: System.arraycopy(array, 0, newarr, 0, index);
0400: if (moved > 0)
0401: System
0402: .arraycopy(array, index + 1, newarr, index,
0403: moved);
0404: setArray(newarr);
0405: return result;
0406: }
0407: }
0408:
0409: public int indexOf(Object o) {
0410: Object[] array = getArray();
0411: return search(array, o, 0, array.length);
0412: }
0413:
0414: public int indexOf(Object o, int index) {
0415: Object[] array = getArray();
0416: return search(array, o, index, array.length);
0417: }
0418:
0419: public int lastIndexOf(Object o) {
0420: Object[] array = getArray();
0421: return reverseSearch(array, o, 0, array.length);
0422: }
0423:
0424: public int lastIndexOf(Object o, int index) {
0425: Object[] array = getArray();
0426: return reverseSearch(array, o, 0, index);
0427: }
0428:
0429: public ListIterator listIterator() {
0430: return new COWIterator(getArray(), 0);
0431: }
0432:
0433: public ListIterator listIterator(int index) {
0434: Object[] array = getArray();
0435: if (index < 0 || index > array.length) {
0436: throw new IndexOutOfBoundsException("Index: " + index
0437: + ", Size: " + array.length);
0438: }
0439: return new COWIterator(array, index);
0440: }
0441:
0442: public List subList(int fromIndex, int toIndex) {
0443: Object[] array = getArray();
0444: if (fromIndex < 0 || toIndex > array.length
0445: || fromIndex > toIndex) {
0446: throw new IndexOutOfBoundsException();
0447: }
0448: return new COWSubList(fromIndex, toIndex - fromIndex);
0449: }
0450:
0451: private void writeObject(ObjectOutputStream out) throws IOException {
0452: out.defaultWriteObject();
0453: Object[] array = getArray();
0454: int length = array.length;
0455: out.writeInt(length);
0456: for (int i = 0; i < length; i++)
0457: out.writeObject(array[i]);
0458: }
0459:
0460: private void readObject(ObjectInputStream in) throws IOException,
0461: ClassNotFoundException {
0462: in.defaultReadObject();
0463: int length = in.readInt();
0464: Object[] array = new Object[length];
0465: for (int i = 0; i < length; i++) {
0466: array[i] = in.readObject();
0467: }
0468: setArray(array);
0469: }
0470:
0471: public String toString() {
0472: Object[] array = getArray();
0473: int length = array.length;
0474: StringBuffer buf = new StringBuffer();
0475: buf.append('[');
0476: for (int i = 0; i < length; i++) {
0477: if (i > 0)
0478: buf.append(", ");
0479: buf.append(array[i]);
0480: }
0481: buf.append(']');
0482: return buf.toString();
0483: }
0484:
0485: static class COWIterator implements ListIterator {
0486:
0487: final Object[] array;
0488: int cursor;
0489:
0490: COWIterator(Object[] array, int cursor) {
0491: this .array = array;
0492: this .cursor = cursor;
0493: }
0494:
0495: public boolean hasNext() {
0496: return cursor < array.length;
0497: }
0498:
0499: public boolean hasPrevious() {
0500: return cursor > 0;
0501: }
0502:
0503: public int nextIndex() {
0504: return cursor;
0505: }
0506:
0507: public Object next() {
0508: try {
0509: return array[cursor++];
0510: } catch (IndexOutOfBoundsException e) {
0511: throw new NoSuchElementException();
0512: }
0513: // todo: should decrement cursor on failure?...
0514: }
0515:
0516: public int previousIndex() {
0517: return cursor - 1;
0518: }
0519:
0520: public Object previous() {
0521: try {
0522: return array[--cursor];
0523: } catch (IndexOutOfBoundsException e) {
0524: throw new NoSuchElementException();
0525: }
0526: // todo: should decrement cursor on failure?...
0527: }
0528:
0529: public void add(Object val) {
0530: throw new UnsupportedOperationException();
0531: }
0532:
0533: public void set(Object val) {
0534: throw new UnsupportedOperationException();
0535: }
0536:
0537: public void remove() {
0538: throw new UnsupportedOperationException();
0539: }
0540: }
0541:
0542: class COWSubList implements Serializable, List {
0543:
0544: final int offset;
0545: int length;
0546: Object[] expectedArray;
0547:
0548: COWSubList(int offset, int length) {
0549: this .offset = offset;
0550: this .length = length;
0551: this .expectedArray = getArray();
0552: }
0553:
0554: public int size() {
0555: return length;
0556: }
0557:
0558: public boolean isEmpty() {
0559: return length == 0;
0560: }
0561:
0562: public boolean contains(Object o) {
0563: return search(getArray(), o, offset, offset + length) >= 0;
0564: }
0565:
0566: public Iterator iterator() {
0567: return listIterator();
0568: }
0569:
0570: public Object[] toArray() {
0571: Object[] array = getArray();
0572: Object[] newarr = new Object[length];
0573: System.arraycopy(array, offset, newarr, 0, length);
0574: return newarr;
0575: }
0576:
0577: public Object[] toArray(Object[] a) {
0578: Object[] array = getArray();
0579: if (a.length < length) {
0580: a = (Object[]) Array.newInstance(a.getClass()
0581: .getComponentType(), length);
0582: System.arraycopy(array, offset, a, 0, length);
0583: } else {
0584: System.arraycopy(array, offset, a, 0, length);
0585: if (a.length > length)
0586: a[length] = null;
0587: }
0588: return a;
0589: }
0590:
0591: public boolean add(Object o) {
0592: add(length, o);
0593: return true;
0594: }
0595:
0596: public boolean remove(Object o) {
0597: synchronized (CopyOnWriteArrayList.this ) {
0598: Object[] array = getArray();
0599: if (array != expectedArray)
0600: throw new ConcurrentModificationException();
0601: int fullLength = array.length;
0602: int pos = search(array, o, offset, length);
0603: if (pos < 0)
0604: return false;
0605: Object[] newarr = new Object[fullLength - 1];
0606: int moved = length - pos - 1;
0607: if (pos > 0)
0608: System.arraycopy(array, 0, newarr, 0, pos);
0609: if (moved > 0)
0610: System
0611: .arraycopy(array, pos + 1, newarr, pos,
0612: moved);
0613: setArray(newarr);
0614: expectedArray = newarr;
0615: length--;
0616: return true;
0617: }
0618: }
0619:
0620: public boolean containsAll(Collection c) {
0621: Object[] array = getArray();
0622: for (Iterator itr = c.iterator(); itr.hasNext();) {
0623: if (search(array, itr.next(), offset, length) < 0)
0624: return false;
0625: }
0626: return true;
0627: }
0628:
0629: public boolean addAll(Collection c) {
0630: return addAll(length, c);
0631: }
0632:
0633: public boolean addAll(int index, Collection c) {
0634: int added = c.size();
0635: synchronized (CopyOnWriteArrayList.this ) {
0636: if (index < 0 || index >= length) {
0637: throw new IndexOutOfBoundsException("Index: "
0638: + index + ", Size: " + length);
0639: }
0640: Object[] oldarr = getArray();
0641: if (oldarr != expectedArray)
0642: throw new ConcurrentModificationException();
0643: if (added == 0)
0644: return false;
0645: int fullLength = oldarr.length;
0646: Object[] newarr = new Object[fullLength + added];
0647: int pos = offset + index;
0648: int newpos = pos;
0649: System.arraycopy(oldarr, 0, newarr, 0, pos);
0650: int rem = fullLength - pos;
0651: for (Iterator itr = c.iterator(); itr.hasNext();) {
0652: newarr[newpos++] = itr.next();
0653: }
0654: if (rem > 0)
0655: System.arraycopy(oldarr, pos, newarr, newpos, rem);
0656: setArray(newarr);
0657: expectedArray = newarr;
0658: length += added;
0659: return true;
0660: }
0661: }
0662:
0663: public boolean removeAll(Collection c) {
0664: if (c.isEmpty())
0665: return false;
0666: synchronized (CopyOnWriteArrayList.this ) {
0667: Object[] array = getArray();
0668: if (array != expectedArray)
0669: throw new ConcurrentModificationException();
0670: int fullLength = array.length;
0671: Object[] tmp = new Object[length];
0672: int retained = 0;
0673: for (int i = offset; i < offset + length; i++) {
0674: Object o = array[i];
0675: if (!c.contains(o))
0676: tmp[retained++] = o;
0677: }
0678: if (retained == length)
0679: return false;
0680: Object[] newarr = new Object[fullLength + retained
0681: - length];
0682: int moved = fullLength - offset - length;
0683: if (offset > 0)
0684: System.arraycopy(array, 0, newarr, 0, offset);
0685: if (retained > 0)
0686: System.arraycopy(tmp, 0, newarr, offset, retained);
0687: if (moved > 0)
0688: System.arraycopy(array, offset + length, newarr,
0689: offset + retained, moved);
0690: setArray(newarr);
0691: expectedArray = newarr;
0692: length = retained;
0693: return true;
0694: }
0695: }
0696:
0697: public boolean retainAll(Collection c) {
0698: synchronized (CopyOnWriteArrayList.this ) {
0699: Object[] array = getArray();
0700: if (array != expectedArray)
0701: throw new ConcurrentModificationException();
0702: int fullLength = array.length;
0703: Object[] tmp = new Object[length];
0704: int retained = 0;
0705: for (int i = offset; i < offset + length; i++) {
0706: Object o = array[i];
0707: if (c.contains(o))
0708: tmp[retained++] = o;
0709: }
0710: if (retained == length)
0711: return false;
0712: Object[] newarr = new Object[fullLength + retained
0713: - length];
0714: int moved = fullLength - offset - length;
0715: if (offset > 0)
0716: System.arraycopy(array, 0, newarr, 0, offset);
0717: if (retained > 0)
0718: System.arraycopy(tmp, 0, newarr, offset, retained);
0719: if (moved > 0)
0720: System.arraycopy(array, offset + length, newarr,
0721: offset + retained, moved);
0722: setArray(newarr);
0723: expectedArray = newarr;
0724: length = retained;
0725: return true;
0726: }
0727: }
0728:
0729: public void clear() {
0730: synchronized (CopyOnWriteArrayList.this ) {
0731: Object[] array = getArray();
0732: if (array != expectedArray)
0733: throw new ConcurrentModificationException();
0734: int fullLength = array.length;
0735: Object[] newarr = new Object[fullLength - length];
0736: int moved = fullLength - offset - length;
0737: if (offset > 0)
0738: System.arraycopy(array, 0, newarr, 0, offset);
0739: if (moved > 0)
0740: System.arraycopy(array, offset + length, newarr,
0741: offset, moved);
0742: setArray(newarr);
0743: expectedArray = newarr;
0744: length = 0;
0745: }
0746: }
0747:
0748: public boolean equals(Object o) {
0749: if (o == this )
0750: return true;
0751: if (!(o instanceof List))
0752: return false;
0753: Object[] array;
0754: int last;
0755: synchronized (CopyOnWriteArrayList.this ) {
0756: array = getArray();
0757: if (array != expectedArray)
0758: throw new ConcurrentModificationException();
0759: last = offset + length;
0760: }
0761: ListIterator itr = ((List) o).listIterator();
0762: int idx = offset;
0763: while (idx < last && itr.hasNext()) {
0764: Object o1 = array[idx];
0765: Object o2 = itr.next();
0766: if (!eq(o1, o2))
0767: return false;
0768: }
0769: return (idx == last && !itr.hasNext());
0770: }
0771:
0772: public int hashCode() {
0773: int hashCode = 1;
0774: Object[] array;
0775: int last;
0776: synchronized (CopyOnWriteArrayList.this ) {
0777: array = getArray();
0778: if (array != expectedArray)
0779: throw new ConcurrentModificationException();
0780: last = offset + length;
0781: }
0782: for (int i = offset; i < last; i++) {
0783: Object o = array[i];
0784: hashCode = 31 * hashCode
0785: + (o == null ? 0 : o.hashCode());
0786: }
0787: return hashCode;
0788: }
0789:
0790: public Object get(int index) {
0791: return getArray()[offset + index];
0792: }
0793:
0794: public Object set(int index, Object element) {
0795: synchronized (CopyOnWriteArrayList.this ) {
0796: if (index < 0 || index >= length) {
0797: throw new IndexOutOfBoundsException("Index: "
0798: + index + ", Size: " + length);
0799: }
0800: Object[] oldarr = getArray();
0801: if (oldarr != expectedArray)
0802: throw new ConcurrentModificationException();
0803: int fullLength = oldarr.length;
0804: // piggyback the array bounds check
0805: Object oldVal = oldarr[offset + index];
0806: if (oldVal == element) {
0807: setArray(oldarr);
0808: } else {
0809: Object[] newarr = new Object[fullLength];
0810: System.arraycopy(oldarr, 0, newarr, 0, fullLength);
0811: newarr[offset + index] = element;
0812: setArray(newarr);
0813: expectedArray = newarr;
0814: }
0815: return oldVal;
0816: }
0817: }
0818:
0819: public void add(int index, Object element) {
0820: synchronized (CopyOnWriteArrayList.this ) {
0821: if (index < 0 || index > length) {
0822: throw new IndexOutOfBoundsException("Index: "
0823: + index + ", Size: " + length);
0824: }
0825: Object[] oldarr = getArray();
0826: if (oldarr != expectedArray)
0827: throw new ConcurrentModificationException();
0828: int fullLength = oldarr.length;
0829: Object[] newarr = new Object[fullLength + 1];
0830: int pos = offset + index;
0831: int moved = fullLength - pos;
0832: System.arraycopy(oldarr, 0, newarr, 0, pos);
0833: newarr[pos] = element;
0834: if (moved > 0) {
0835: System.arraycopy(oldarr, pos, newarr, pos + 1,
0836: moved);
0837: }
0838: setArray(newarr);
0839: expectedArray = newarr;
0840: length++;
0841: }
0842: }
0843:
0844: public Object remove(int index) {
0845: synchronized (CopyOnWriteArrayList.this ) {
0846: if (index < 0 || index >= length) {
0847: throw new IndexOutOfBoundsException("Index: "
0848: + index + ", Size: " + length);
0849: }
0850: Object[] array = getArray();
0851: if (array != expectedArray)
0852: throw new ConcurrentModificationException();
0853: int fullLength = array.length;
0854: int pos = offset + index;
0855: Object result = array[pos];
0856: Object[] newarr = new Object[fullLength - 1];
0857: int moved = fullLength - pos - 1;
0858: if (index > 0)
0859: System.arraycopy(array, 0, newarr, 0, pos);
0860: if (moved > 0)
0861: System
0862: .arraycopy(array, pos + 1, newarr, pos,
0863: moved);
0864: setArray(newarr);
0865: expectedArray = newarr;
0866: length--;
0867: return result;
0868: }
0869: }
0870:
0871: public int indexOf(Object o) {
0872: int pos = search(getArray(), o, offset, offset + length);
0873: return pos >= 0 ? pos - offset : -1;
0874: }
0875:
0876: public int indexOf(Object o, int index) {
0877: int pos = search(getArray(), o, offset + index, offset
0878: + length)
0879: - offset;
0880: return pos >= 0 ? pos - offset : -1;
0881: }
0882:
0883: public int lastIndexOf(Object o) {
0884: int pos = reverseSearch(getArray(), o, offset, offset
0885: + length)
0886: - offset;
0887: return pos >= 0 ? pos - offset : -1;
0888: }
0889:
0890: public int lastIndexOf(Object o, int index) {
0891: int pos = reverseSearch(getArray(), o, offset, offset
0892: + index)
0893: - offset;
0894: return pos >= 0 ? pos - offset : -1;
0895: }
0896:
0897: public ListIterator listIterator() {
0898: // must synchronize to atomically obtain the array and length
0899: synchronized (CopyOnWriteArrayList.this ) {
0900: Object[] array = getArray();
0901: if (array != expectedArray)
0902: throw new ConcurrentModificationException();
0903: return new COWSubIterator(array, offset, offset
0904: + length, offset);
0905: }
0906: }
0907:
0908: public ListIterator listIterator(int index) {
0909: // must synchronize to atomically obtain the array and length
0910: synchronized (CopyOnWriteArrayList.this ) {
0911: if (index < 0 || index >= length) {
0912: throw new IndexOutOfBoundsException("Index: "
0913: + index + ", Size: " + length);
0914: }
0915: Object[] array = getArray();
0916: if (array != expectedArray)
0917: throw new ConcurrentModificationException();
0918: return new COWSubIterator(array, offset, offset
0919: + length, offset + index);
0920: }
0921: }
0922:
0923: public List subList(int fromIndex, int toIndex) {
0924: if (fromIndex < 0 || toIndex > length
0925: || fromIndex > toIndex) {
0926: throw new IndexOutOfBoundsException();
0927: }
0928: return new COWSubList(offset + fromIndex, toIndex
0929: - fromIndex);
0930: }
0931:
0932: public String toString() {
0933: Object[] array;
0934: int last;
0935: synchronized (CopyOnWriteArrayList.this ) {
0936: array = getArray();
0937: if (array != expectedArray)
0938: throw new ConcurrentModificationException();
0939: last = offset + length;
0940: }
0941: StringBuffer buf = new StringBuffer();
0942: buf.append('[');
0943: for (int i = offset; i < last; i++) {
0944: if (i > offset)
0945: buf.append(", ");
0946: buf.append(array[i]);
0947: }
0948: buf.append(']');
0949: return buf.toString();
0950: }
0951: }
0952:
0953: static class COWSubIterator implements ListIterator {
0954:
0955: final Object[] array;
0956: int cursor;
0957: int first, last;
0958:
0959: COWSubIterator(Object[] array, int first, int last, int cursor) {
0960: this .array = array;
0961: this .first = first;
0962: this .last = last;
0963: this .cursor = cursor;
0964: }
0965:
0966: public boolean hasNext() {
0967: return cursor < last;
0968: }
0969:
0970: public boolean hasPrevious() {
0971: return cursor > first;
0972: }
0973:
0974: public int nextIndex() {
0975: return cursor - first;
0976: }
0977:
0978: public Object next() {
0979: if (cursor == last)
0980: throw new NoSuchElementException();
0981: return array[cursor++];
0982: }
0983:
0984: public int previousIndex() {
0985: return cursor - first - 1;
0986: }
0987:
0988: public Object previous() {
0989: if (cursor == first)
0990: throw new NoSuchElementException();
0991: return array[--cursor];
0992: }
0993:
0994: public void add(Object val) {
0995: throw new UnsupportedOperationException();
0996: }
0997:
0998: public void set(Object val) {
0999: throw new UnsupportedOperationException();
1000: }
1001:
1002: public void remove() {
1003: throw new UnsupportedOperationException();
1004: }
1005: }
1006:
1007: private static boolean eq(Object o1, Object o2) {
1008: return (o1 == null ? o2 == null : o1.equals(o2));
1009: }
1010: }
|