0001: /*
0002: * Licensed to the Apache Software Foundation (ASF) under one or more
0003: * contributor license agreements. See the NOTICE file distributed with this
0004: * work for additional information regarding copyright ownership. The ASF
0005: * licenses this file to you under the Apache License, Version 2.0 (the
0006: * "License"); you may not use this file except in compliance with the License.
0007: * You may obtain a copy of the License at
0008: *
0009: * http://www.apache.org/licenses/LICENSE-2.0
0010: *
0011: * Unless required by applicable law or agreed to in writing, software
0012: * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
0013: * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
0014: * License for the specific language governing permissions and limitations under
0015: * the License.
0016: */
0017:
0018: package java.util.concurrent;
0019:
0020: import java.io.IOException;
0021: import java.io.ObjectInputStream;
0022: import java.io.ObjectOutputStream;
0023: import java.io.Serializable;
0024: import java.lang.reflect.Array;
0025: import java.util.Collection;
0026: import java.util.ConcurrentModificationException;
0027: import java.util.Iterator;
0028: import java.util.List;
0029: import java.util.ListIterator;
0030: import java.util.NoSuchElementException;
0031: import java.util.RandomAccess;
0032: import java.util.concurrent.locks.ReentrantLock;
0033:
0034: public class CopyOnWriteArrayList<E> implements List<E>, RandomAccess,
0035: Cloneable, Serializable {
0036:
0037: private static final long serialVersionUID = 8673264195747942595L;
0038:
0039: private transient volatile E[] arr;
0040:
0041: /**
0042: * Lock for the queue write methods
0043: */
0044: private final transient ReentrantLock lock = new ReentrantLock();
0045:
0046: public CopyOnWriteArrayList() {
0047: }
0048:
0049: public CopyOnWriteArrayList(Collection<? extends E> c) {
0050: this ((E[]) c.toArray());
0051: }
0052:
0053: public CopyOnWriteArrayList(E[] array) {
0054: int size = array.length;
0055: E[] data = newElementArray(size);
0056: for (int i = 0; i < size; i++) {
0057: data[i] = array[i];
0058: }
0059: arr = data;
0060: }
0061:
0062: public boolean add(E e) {
0063: lock.lock();
0064: try {
0065: E[] data;
0066: E[] old = getData();
0067: int size = old.length;
0068: data = newElementArray(size + 1);
0069: System.arraycopy(old, 0, data, 0, size);
0070: data[size] = e;
0071: setData(data);
0072: return true;
0073: } finally {
0074: lock.unlock();
0075: }
0076: }
0077:
0078: public void add(int index, E e) {
0079: lock.lock();
0080: try {
0081: E[] data;
0082: E[] old = getData();
0083: int size = old.length;
0084: checkIndexInclusive(index, size);
0085: data = newElementArray(size + 1);
0086: System.arraycopy(old, 0, data, 0, index);
0087: data[index] = e;
0088: if (size > index) {
0089: System.arraycopy(old, index, data, index + 1, size
0090: - index);
0091: }
0092: setData(data);
0093: } finally {
0094: lock.unlock();
0095: }
0096: }
0097:
0098: public boolean addAll(Collection<? extends E> c) {
0099: Iterator it = c.iterator();
0100: int ssize = c.size();
0101: lock.lock();
0102: try {
0103: int size = size();
0104: E[] data;
0105: E[] old = getData();
0106: int nSize = size + ssize;
0107: data = newElementArray(nSize);
0108: System.arraycopy(old, 0, data, 0, size);
0109: while (it.hasNext()) {
0110: data[size++] = (E) it.next();
0111: }
0112: setData(data);
0113: } finally {
0114: lock.unlock();
0115: }
0116: return true;
0117: }
0118:
0119: public boolean addAll(int index, Collection<? extends E> c) {
0120: Iterator it = c.iterator();
0121: int ssize = c.size();
0122: lock.lock();
0123: try {
0124: int size = size();
0125: checkIndexInclusive(index, size);
0126: E[] data;
0127: E[] old = getData();
0128: int nSize = size + ssize;
0129: data = newElementArray(nSize);
0130: System.arraycopy(old, 0, data, 0, index);
0131: int i = index;
0132: while (it.hasNext()) {
0133: data[i++] = (E) it.next();
0134: }
0135: if (size > index) {
0136: System.arraycopy(old, index, data, index + ssize, size
0137: - index);
0138: }
0139: setData(data);
0140: } finally {
0141: lock.unlock();
0142: }
0143: return true;
0144: }
0145:
0146: public int addAllAbsent(Collection<? extends E> c) {
0147: if (c.size() == 0) {
0148: return 0;
0149: }
0150: lock.lock();
0151: try {
0152: E[] old = getData();
0153: int size = old.length;
0154: E[] toAdd = newElementArray(c.size());
0155: int i = 0;
0156: for (Iterator it = c.iterator(); it.hasNext();) {
0157: E o = (E) it.next();
0158: if (indexOf(o) < 0) {
0159: toAdd[i++] = o;
0160: }
0161: }
0162: E[] data = newElementArray(size + i);
0163: System.arraycopy(old, 0, data, 0, size);
0164: System.arraycopy(toAdd, 0, data, size, i);
0165: setData(data);
0166: return i;
0167: } finally {
0168: lock.unlock();
0169: }
0170: }
0171:
0172: public boolean addIfAbsent(E e) {
0173: lock.lock();
0174: try {
0175: E[] data;
0176: E[] old = getData();
0177: int size = old.length;
0178: if (size != 0) {
0179: if (indexOf(e) >= 0) {
0180: return false;
0181: }
0182: }
0183: data = newElementArray(size + 1);
0184: System.arraycopy(old, 0, data, 0, size);
0185: data[size] = e;
0186: setData(data);
0187: return true;
0188: } finally {
0189: lock.unlock();
0190: }
0191: }
0192:
0193: public void clear() {
0194: lock.lock();
0195: try {
0196: setData(newElementArray(0));
0197: } finally {
0198: lock.unlock();
0199: }
0200: }
0201:
0202: @Override
0203: public Object clone() {
0204: try {
0205: CopyOnWriteArrayList this Clone = (CopyOnWriteArrayList) super
0206: .clone();
0207: this Clone.setData(this .getData());
0208: return this Clone;
0209: } catch (CloneNotSupportedException e) {
0210: throw new RuntimeException(
0211: "CloneNotSupportedException is not expected here");
0212: }
0213: }
0214:
0215: public boolean contains(Object o) {
0216: return indexOf(o) >= 0;
0217: }
0218:
0219: public boolean containsAll(Collection<?> c) {
0220: E[] data = getData();
0221: return containsAll(c, data, 0, data.length);
0222: }
0223:
0224: public boolean equals(Object o) {
0225: if (o == this ) {
0226: return true;
0227: }
0228: if (!(o instanceof List)) {
0229: return false;
0230: }
0231: List l = (List) o;
0232: Iterator it = l.listIterator();
0233: Iterator ourIt = listIterator();
0234: while (it.hasNext()) {
0235: if (!ourIt.hasNext()) {
0236: return false;
0237: }
0238: Object this ListElem = it.next();
0239: Object anotherListElem = ourIt.next();
0240: if (!(this ListElem == null ? anotherListElem == null
0241: : this ListElem.equals(anotherListElem))) {
0242: return false;
0243: }
0244: }
0245: if (ourIt.hasNext()) {
0246: return false;
0247: }
0248: return true;
0249: }
0250:
0251: public E get(int index) {
0252: E[] data = getData();
0253: return data[index];
0254: }
0255:
0256: public int hashCode() {
0257: int hashCode = 1;
0258: Iterator it = listIterator();
0259: while (it.hasNext()) {
0260: Object obj = it.next();
0261: hashCode = 31 * hashCode
0262: + (obj == null ? 0 : obj.hashCode());
0263: }
0264: return hashCode;
0265: }
0266:
0267: public int indexOf(E e, int index) {
0268: E[] data = getData();
0269: return indexOf(e, data, index, data.length - index);
0270: }
0271:
0272: public int indexOf(Object o) {
0273: E[] data = getData();
0274: return indexOf(o, data, 0, data.length);
0275: }
0276:
0277: public boolean isEmpty() {
0278: return size() == 0;
0279: }
0280:
0281: public Iterator<E> iterator() {
0282: return new ListIteratorImpl(getData(), 0);
0283: }
0284:
0285: public int lastIndexOf(E e, int index) {
0286: E[] data = getData();
0287: return lastIndexOf(e, data, 0, index);
0288: }
0289:
0290: public int lastIndexOf(Object o) {
0291: E[] data = getData();
0292: return lastIndexOf(o, data, 0, data.length);
0293: }
0294:
0295: public ListIterator<E> listIterator() {
0296: return new ListIteratorImpl(getData(), 0);
0297: }
0298:
0299: public ListIterator<E> listIterator(int index) {
0300: E[] data = getData();
0301: checkIndexInclusive(index, data.length);
0302: return new ListIteratorImpl(data, index);
0303: }
0304:
0305: public E remove(int index) {
0306: return removeRange(index, 1);
0307: }
0308:
0309: public boolean remove(Object o) {
0310: lock.lock();
0311: try {
0312: int index = indexOf(o);
0313: if (index == -1) {
0314: return false;
0315: }
0316: remove(index);
0317: return true;
0318: } finally {
0319: lock.unlock();
0320: }
0321: }
0322:
0323: public boolean removeAll(Collection<?> c) {
0324: lock.lock();
0325: try {
0326: return removeAll(c, 0, getData().length) != 0;
0327: } finally {
0328: lock.unlock();
0329: }
0330: }
0331:
0332: public boolean retainAll(Collection<?> c) {
0333: if (c == null) {
0334: throw new NullPointerException();
0335: }
0336: lock.lock();
0337: try {
0338: return retainAll(c, 0, getData().length) != 0;
0339: } finally {
0340: lock.unlock();
0341: }
0342: }
0343:
0344: public E set(int index, E e) {
0345: lock.lock();
0346: try {
0347: int size = size();
0348: checkIndexExlusive(index, size);
0349: E[] data;
0350: data = newElementArray(size);
0351: E[] oldArr = getData();
0352: System.arraycopy(oldArr, 0, data, 0, size);
0353: E old = data[index];
0354: data[index] = e;
0355: setData(data);
0356: return old;
0357: } finally {
0358: lock.unlock();
0359: }
0360: }
0361:
0362: public int size() {
0363: return getData().length;
0364: }
0365:
0366: public List<E> subList(int fromIndex, int toIndex) {
0367: return new SubList(this , fromIndex, toIndex);
0368: }
0369:
0370: public Object[] toArray() {
0371: E[] data = getData();
0372: return toArray(data, 0, data.length);
0373: }
0374:
0375: public <T> T[] toArray(T[] a) {
0376: E[] data = getData();
0377: return (T[]) toArray(a, data, 0, data.length);
0378: }
0379:
0380: @Override
0381: public String toString() {
0382: StringBuffer sb = new StringBuffer("[");
0383:
0384: Iterator it = listIterator();
0385: while (it.hasNext()) {
0386: sb.append(String.valueOf(it.next()));
0387: sb.append(", ");
0388: }
0389: if (sb.length() > 1) {
0390: sb.setLength(sb.length() - 2);
0391: }
0392: sb.append("]");
0393: return sb.toString();
0394: }
0395:
0396: // private and package private methods
0397:
0398: @SuppressWarnings("unchecked")
0399: private final E[] newElementArray(int size) {
0400: return (E[]) new Object[size];
0401: }
0402:
0403: /**
0404: * sets the internal data array
0405: *
0406: * @param data array to set
0407: */
0408: private final void setData(E[] data) {
0409: arr = data;
0410: }
0411:
0412: /**
0413: * gets the internal data array
0414: *
0415: * @return the data array
0416: */
0417: final E[] getData() {
0418: if (arr == null) {
0419: return newElementArray(0);
0420: }
0421: return arr;
0422: }
0423:
0424: /**
0425: * Removes from the specified range of this list
0426: * all the elements that are contained in the specified collection
0427: * <p/>
0428: * !should be called under lock
0429: *
0430: * @return Returns the number of removed elements
0431: */
0432: final int removeAll(Collection c, int start, int size) {
0433: int ssize = c.size();
0434: if (ssize == 0) {
0435: return 0;
0436: }
0437: Object[] old = getData();
0438: int arrsize = old.length;
0439: if (arrsize == 0) {
0440: return 0;
0441: }
0442: Object[] data = new Object[size];
0443: int j = 0;
0444: for (int i = start; i < (start + size); i++) {
0445: if (!c.contains(old[i])) {
0446: data[j++] = old[i];
0447: }
0448: }
0449: if (j != size) {
0450: E[] result = newElementArray(arrsize - (size - j));
0451: System.arraycopy(old, 0, result, 0, start);
0452: System.arraycopy(data, 0, result, start, j);
0453: System.arraycopy(old, start + size, result, start + j,
0454: arrsize - (start + size));
0455: setData(result);
0456: return (size - j);
0457: }
0458: return 0;
0459: }
0460:
0461: /**
0462: * Retains only the elements in the specified range of this list
0463: * that are contained in the specified collection
0464: *
0465: * @return Returns the number of removed elements
0466: */
0467: // should be called under lock
0468: int retainAll(Collection c, int start, int size) {
0469: Object[] old = getData();
0470: if (size == 0) {
0471: return 0;
0472: }
0473: if (c.size() == 0) {
0474: E[] data;
0475: if (size == old.length) {
0476: data = newElementArray(0);
0477: } else {
0478: data = newElementArray(old.length - size);
0479: System.arraycopy(old, 0, data, 0, start);
0480: System.arraycopy(old, start + size, data, start,
0481: old.length - start - size);
0482: }
0483: setData(data);
0484: return size;
0485: }
0486: Object[] temp = new Object[size];
0487: int pos = 0;
0488: for (int i = start; i < (start + size); i++) {
0489: if (c.contains(old[i])) {
0490: temp[pos++] = old[i];
0491: }
0492: }
0493: if (pos == size) {
0494: return 0;
0495: }
0496: E[] data = newElementArray(pos + old.length - size);
0497: System.arraycopy(old, 0, data, 0, start);
0498: System.arraycopy(temp, 0, data, start, pos);
0499: System.arraycopy(old, start + size, data, start + pos,
0500: old.length - start - size);
0501: setData(data);
0502: return (size - pos);
0503: }
0504:
0505: /**
0506: * Removes specified range from this list
0507: */
0508: E removeRange(int start, int size) {
0509: lock.lock();
0510: try {
0511: int sizeArr = size();
0512: checkIndexExlusive(start, sizeArr);
0513: checkIndexInclusive(start + size, sizeArr);
0514: E[] data;
0515: data = newElementArray(sizeArr - size);
0516: E[] oldArr = getData();
0517: System.arraycopy(oldArr, 0, data, 0, start);
0518: E old = oldArr[start];
0519: if (sizeArr > (start + size)) {
0520: System.arraycopy(oldArr, start + size, data, start,
0521: sizeArr - (start + size));
0522: }
0523: setData(data);
0524: return old;
0525: } finally {
0526: lock.unlock();
0527: }
0528: }
0529:
0530: // some util static functions to use by iterators and methods
0531: /**
0532: * Returns an array containing all of the elements
0533: * in the specified range of the array in proper sequence
0534: */
0535: static Object[] toArray(Object[] data, int start, int size) {
0536: Object[] result = new Object[size];
0537: System.arraycopy(data, start, result, 0, size);
0538: return result;
0539: }
0540:
0541: /**
0542: * Returns an array containing all of the elements
0543: * in the specified range of the array in proper sequence,
0544: * stores the result in the array, specified by first parameter
0545: * (as for public instance method toArray(Object[] to)
0546: */
0547: static Object[] toArray(Object[] to, Object[] data, int start,
0548: int size) {
0549: int l = data.length;
0550: if (to.length < l) {
0551: to = (Object[]) Array.newInstance(to.getClass()
0552: .getComponentType(), l);
0553: } else {
0554: if (to.length > l) {
0555: to[l] = null;
0556: }
0557: }
0558: System.arraycopy(data, start, to, 0, size);
0559: return to;
0560: }
0561:
0562: /**
0563: * Checks if the specified range of the
0564: * array contains all of the elements in the collection
0565: *
0566: * @param c collection with elements
0567: * @param data array where to search the elements
0568: * @param start start index
0569: * @param size size of the range
0570: */
0571: static final boolean containsAll(Collection c, Object[] data,
0572: int start, int size) {
0573: if (size == 0) {
0574: return false;
0575: }
0576: Iterator it = c.iterator();
0577: while (it.hasNext()) {
0578: Object next = it.next();
0579: if (indexOf(next, data, start, size) < 0) {
0580: return false;
0581: }
0582: }
0583: return true;
0584: }
0585:
0586: /**
0587: * Returns the index in the specified range of the data array
0588: * of the last occurrence of the specified element
0589: *
0590: * @param o element to search
0591: * @param data array where to search
0592: * @param start start index
0593: * @param size size of the range
0594: * @return
0595: */
0596: static final int lastIndexOf(Object o, Object[] data, int start,
0597: int size) {
0598: if (size == 0) {
0599: return -1;
0600: }
0601: if (o != null) {
0602: for (int i = start + size - 1; i > start - 1; i--) {
0603: if (o.equals(data[i])) {
0604: return i;
0605: }
0606: }
0607: } else {
0608: for (int i = start + size - 1; i > start - 1; i--) {
0609: if (data[i] == null) {
0610: return i;
0611: }
0612: }
0613: }
0614: return -1;
0615: }
0616:
0617: /**
0618: * Returns the index in the specified range of the data array
0619: * of the first occurrence of the specified element
0620: *
0621: * @param o element to search
0622: * @param data array where to search
0623: * @param start start index
0624: * @param size end index
0625: * @return
0626: */
0627: static final int indexOf(Object o, Object[] data, int start,
0628: int size) {
0629: if (size == 0) {
0630: return -1;
0631: }
0632: if (o == null) {
0633: for (int i = start; i < start + size; i++) {
0634: if (data[i] == null) {
0635: return i;
0636: }
0637: }
0638: } else {
0639: for (int i = start; i < start + size; i++) {
0640: if (o.equals(data[i])) {
0641: return i;
0642: }
0643: }
0644: }
0645: return -1;
0646: }
0647:
0648: /**
0649: * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
0650: * is out of the list bounds.
0651: *
0652: * @param index element index to check.
0653: */
0654: static final void checkIndexInclusive(int index, int size) {
0655: if (index < 0 || index > size) {
0656: throw new IndexOutOfBoundsException("Index is " + index
0657: + ", size is " + size);
0658: }
0659: }
0660:
0661: /**
0662: * Throws <code>IndexOutOfBoundsException</code> if <code>index</code>
0663: * is out of the list bounds. Excluding the last element.
0664: *
0665: * @param index element index to check.
0666: */
0667: static final void checkIndexExlusive(int index, int size) {
0668: if (index < 0 || index >= size) {
0669: throw new IndexOutOfBoundsException("Index is " + index
0670: + ", size is " + size);
0671: }
0672: }
0673:
0674: /**
0675: * list iterator implementation,
0676: * when created gets snapshot of the list,
0677: * so never throws ConcurrentModificationException
0678: */
0679: private static class ListIteratorImpl implements ListIterator {
0680: private final Object[] arr;
0681:
0682: private int current;
0683:
0684: private final int size;
0685:
0686: final int size() {
0687: return size;
0688: }
0689:
0690: public ListIteratorImpl(Object[] data, int current) {
0691: this .current = current;
0692: arr = data;
0693: size = data.length;
0694: }
0695:
0696: public void add(Object o) {
0697: throw new UnsupportedOperationException(
0698: "Unsupported operation add");
0699: }
0700:
0701: public boolean hasNext() {
0702: if (current < size) {
0703: return true;
0704: }
0705: return false;
0706: }
0707:
0708: public boolean hasPrevious() {
0709: return current > 0;
0710: }
0711:
0712: public Object next() {
0713: if (hasNext()) {
0714: return arr[current++];
0715: }
0716: throw new NoSuchElementException("pos is " + current
0717: + ", size is " + size);
0718: }
0719:
0720: public int nextIndex() {
0721: return current;
0722: }
0723:
0724: public Object previous() {
0725: if (hasPrevious()) {
0726: return arr[--current];
0727: }
0728: throw new NoSuchElementException("pos is " + (current - 1)
0729: + ", size is " + size);
0730: }
0731:
0732: public int previousIndex() {
0733: return current - 1;
0734: }
0735:
0736: public void remove() {
0737: throw new UnsupportedOperationException(
0738: "Unsupported operation remove");
0739: }
0740:
0741: public void set(Object o) {
0742: throw new UnsupportedOperationException(
0743: "Unsupported operation set");
0744: }
0745:
0746: }
0747:
0748: /**
0749: * Keeps a state of sublist implementation,
0750: * size and array declared as final,
0751: * so we'll never get the unconsistent state
0752: */
0753: static final class SubListReadData {
0754: final int size;
0755:
0756: final Object[] data;
0757:
0758: SubListReadData(int size, Object[] data) {
0759: this .size = size;
0760: this .data = data;
0761: }
0762: }
0763:
0764: /**
0765: * Represents a list returned by <code>sublist()</code>.
0766: */
0767: static class SubList implements List {
0768: private final CopyOnWriteArrayList list;
0769:
0770: private volatile SubListReadData read;
0771:
0772: private final int start;
0773:
0774: /**
0775: * Sublist constructor.
0776: *
0777: * @param list backing list.
0778: * @param fromIdx startingIndex, inclusive
0779: * @param toIdx endIndex, exclusive
0780: */
0781: public SubList(CopyOnWriteArrayList list, int fromIdx, int toIdx) {
0782: this .list = list;
0783: Object[] data = list.getData();
0784: int size = toIdx - fromIdx;
0785: checkIndexExlusive(fromIdx, data.length);
0786: checkIndexInclusive(toIdx, data.length);
0787: read = new SubListReadData(size, list.getData());
0788: start = fromIdx;
0789: }
0790:
0791: /**
0792: * throws ConcurrentModificationException when the list
0793: * is structurally modified in the other way other than via this subList
0794: * <p/>
0795: * Should be called under lock!
0796: */
0797: private void checkModifications() {
0798: if (read.data != list.getData()) {
0799: throw new ConcurrentModificationException();
0800: }
0801: }
0802:
0803: /**
0804: * @see java.util.List#listIterator(int)
0805: */
0806: public ListIterator listIterator(int startIdx) {
0807: return new SubListIterator(startIdx, read);
0808: }
0809:
0810: /**
0811: * @see java.util.List#set(int, java.lang.Object)
0812: */
0813: public Object set(int index, Object obj) {
0814: list.lock.lock();
0815: try {
0816: checkIndexExlusive(index, read.size);
0817: checkModifications();
0818: Object result = list.set(index + start, obj);
0819: read = new SubListReadData(read.size, list.getData());
0820: return result;
0821: } finally {
0822: list.lock.unlock();
0823: }
0824: }
0825:
0826: /**
0827: * @see java.util.List#get(int)
0828: */
0829: public Object get(int index) {
0830: SubListReadData data = read;
0831: if (data.data != list.getData()) {
0832: list.lock.lock();
0833: try {
0834: data = read;
0835: if (data.data != list.getData()) {
0836: throw new ConcurrentModificationException();
0837: }
0838: } finally {
0839: list.lock.unlock();
0840: }
0841: }
0842: checkIndexExlusive(index, data.size);
0843: return data.data[index + start];
0844: }
0845:
0846: /**
0847: * @see java.util.Collection#size()
0848: */
0849: public int size() {
0850: return read.size;
0851: }
0852:
0853: /**
0854: * @see java.util.List#remove(int)
0855: */
0856: public Object remove(int index) {
0857: list.lock.lock();
0858: try {
0859: checkIndexExlusive(index, read.size);
0860: checkModifications();
0861: Object obj = list.remove(index + start);
0862: read = new SubListReadData(read.size - 1, list
0863: .getData());
0864: return obj;
0865: } finally {
0866: list.lock.unlock();
0867: }
0868: }
0869:
0870: /**
0871: * @see java.util.List#add(int, java.lang.Object)
0872: */
0873: public void add(int index, Object object) {
0874: list.lock.lock();
0875: try {
0876: checkIndexInclusive(index, read.size);
0877: checkModifications();
0878: list.add(index + start, object);
0879: read = new SubListReadData(read.size + 1, list
0880: .getData());
0881: } finally {
0882: list.lock.unlock();
0883: }
0884: }
0885:
0886: public boolean add(Object o) {
0887: list.lock.lock();
0888: try {
0889: checkModifications();
0890: list.add(start + read.size, o);
0891: read = new SubListReadData(read.size + 1, list
0892: .getData());
0893: return true;
0894: } finally {
0895: list.lock.unlock();
0896: }
0897: }
0898:
0899: public boolean addAll(Collection c) {
0900: list.lock.lock();
0901: try {
0902: checkModifications();
0903: int d = list.size();
0904: list.addAll(start + read.size, c);
0905: read = new SubListReadData(read.size
0906: + (list.size() - d), list.getData());
0907: return true;
0908: } finally {
0909: list.lock.unlock();
0910: }
0911: }
0912:
0913: public void clear() {
0914: list.lock.lock();
0915: try {
0916: checkModifications();
0917: list.removeRange(start, read.size);
0918: read = new SubListReadData(0, list.getData());
0919: } finally {
0920: list.lock.unlock();
0921: }
0922: }
0923:
0924: public boolean contains(Object o) {
0925: return indexOf(o) != -1;
0926: }
0927:
0928: public boolean containsAll(Collection c) {
0929: SubListReadData b = read;
0930: return CopyOnWriteArrayList.containsAll(c, b.data, start,
0931: b.size);
0932: }
0933:
0934: public int indexOf(Object o) {
0935: SubListReadData b = read;
0936: int ind = CopyOnWriteArrayList.indexOf(o, b.data, start,
0937: b.size)
0938: - start;
0939: return ind < 0 ? -1 : ind;
0940: }
0941:
0942: public boolean isEmpty() {
0943: return read.size == 0;
0944: }
0945:
0946: public Iterator iterator() {
0947: return new SubListIterator(0, read);
0948: }
0949:
0950: public int lastIndexOf(Object o) {
0951: SubListReadData b = read;
0952: int ind = CopyOnWriteArrayList.lastIndexOf(o, b.data,
0953: start, b.size)
0954: - start;
0955: return ind < 0 ? -1 : ind;
0956: }
0957:
0958: public ListIterator listIterator() {
0959: return new SubListIterator(0, read);
0960: }
0961:
0962: public boolean remove(Object o) {
0963: list.lock.lock();
0964: try {
0965: checkModifications();
0966: int i = indexOf(o);
0967: if (i == -1) {
0968: return false;
0969: }
0970: boolean result = list.remove(i + start) != null;
0971: if (result) {
0972: read = new SubListReadData(read.size - 1, list
0973: .getData());
0974: }
0975: return result;
0976: } finally {
0977: list.lock.unlock();
0978: }
0979: }
0980:
0981: public boolean removeAll(Collection c) {
0982: list.lock.lock();
0983: try {
0984: checkModifications();
0985: int removed = list.removeAll(c, start, read.size);
0986: if (removed > 0) {
0987: read = new SubListReadData(read.size - removed,
0988: list.getData());
0989: return true;
0990: }
0991: } finally {
0992: list.lock.unlock();
0993: }
0994: return false;
0995: }
0996:
0997: public boolean retainAll(Collection c) {
0998: list.lock.lock();
0999: try {
1000: checkModifications();
1001: int removed = list.retainAll(c, start, read.size);
1002: if (removed > 0) {
1003: read = new SubListReadData(read.size - removed,
1004: list.getData());
1005: return true;
1006: }
1007: return false;
1008: } finally {
1009: list.lock.unlock();
1010: }
1011: }
1012:
1013: public List subList(int fromIndex, int toIndex) {
1014: return new SubList(list, start + fromIndex, start + toIndex);
1015: }
1016:
1017: public Object[] toArray() {
1018: SubListReadData r = read;
1019: return CopyOnWriteArrayList.toArray(r.data, start, r.size);
1020: }
1021:
1022: public Object[] toArray(Object[] a) {
1023: SubListReadData r = read;
1024: return CopyOnWriteArrayList.toArray(a, r.data, start,
1025: r.size);
1026: }
1027:
1028: /**
1029: * @see java.util.List#addAll(int, java.util.Collection)
1030: */
1031: public boolean addAll(int index, Collection collection) {
1032: list.lock.lock();
1033: try {
1034: checkIndexInclusive(index, read.size);
1035: checkModifications();
1036: int d = list.size();
1037: boolean rt = list.addAll(index + start, collection);
1038: read = new SubListReadData(read.size + list.size() - d,
1039: list.getData());
1040: return rt;
1041: } finally {
1042: list.lock.unlock();
1043: }
1044: }
1045:
1046: /**
1047: * Implementation of <code>ListIterator</code> for the
1048: * <code>SubList</code>
1049: * gets a snapshot of the sublist,
1050: * never throws ConcurrentModificationException
1051: */
1052: private class SubListIterator extends ListIteratorImpl {
1053: private final SubListReadData dataR;
1054:
1055: /**
1056: * Constructs an iterator starting with the given index
1057: *
1058: * @param index index of the first element to iterate.
1059: */
1060: private SubListIterator(int index, SubListReadData d) {
1061: super (d.data, index + start);
1062: this .dataR = d;
1063: }
1064:
1065: /**
1066: * @see java.util.ListIterator#nextIndex()
1067: */
1068: public int nextIndex() {
1069: return super .nextIndex() - start;
1070: }
1071:
1072: /**
1073: * @see java.util.ListIterator#previousIndex()
1074: */
1075: public int previousIndex() {
1076: return super .previousIndex() - start;
1077: }
1078:
1079: /**
1080: * @see java.util.Iterator#hasNext()
1081: */
1082: public boolean hasNext() {
1083: return nextIndex() < dataR.size;
1084: }
1085:
1086: /**
1087: * @see java.util.ListIterator#hasPrevious()
1088: */
1089: public boolean hasPrevious() {
1090: return previousIndex() > -1;
1091: }
1092: }
1093:
1094: }
1095:
1096: //serialization support
1097: /**
1098: * Writes the object state to the ObjectOutputStream.
1099: *
1100: * @param oos ObjectOutputStream to write object to.
1101: * @throws IOException if an I/O error occur.
1102: */
1103: private void writeObject(ObjectOutputStream oos) throws IOException {
1104: E[] back = getData();
1105: int size = back.length;
1106: oos.defaultWriteObject();
1107: oos.writeInt(size);
1108: for (int i = 0; i < size; i++) {
1109: oos.writeObject(back[i]);
1110: }
1111: }
1112:
1113: /**
1114: * Reads the object state from the ObjectOutputStream.
1115: *
1116: * @param ois ObjectInputStream to read object from.
1117: * @throws IOException if an I/O error occur.
1118: */
1119: private void readObject(ObjectInputStream ois) throws IOException,
1120: ClassNotFoundException {
1121: ois.defaultReadObject();
1122: int length = ois.readInt();
1123: if (length == 0) {
1124: setData(newElementArray(0));
1125: } else {
1126: E[] back = newElementArray(length);
1127: for (int i = 0; i < back.length; i++) {
1128: back[i] = (E) ois.readObject();
1129: }
1130: setData(back);
1131: }
1132: }
1133: }
|