Return-Path: Delivered-To: apmail-incubator-harmony-commits-archive@www.apache.org Received: (qmail 2471 invoked from network); 12 Jul 2006 04:12:52 -0000 Received: from hermes.apache.org (HELO mail.apache.org) (209.237.227.199) by minotaur.apache.org with SMTP; 12 Jul 2006 04:12:52 -0000 Received: (qmail 48255 invoked by uid 500); 12 Jul 2006 04:12:50 -0000 Delivered-To: apmail-incubator-harmony-commits-archive@incubator.apache.org Received: (qmail 48179 invoked by uid 500); 12 Jul 2006 04:12:50 -0000 Mailing-List: contact harmony-commits-help@incubator.apache.org; run by ezmlm Precedence: bulk List-Help: List-Unsubscribe: List-Post: List-Id: Reply-To: harmony-dev@incubator.apache.org Delivered-To: mailing list harmony-commits@incubator.apache.org Received: (qmail 48141 invoked by uid 99); 12 Jul 2006 04:12:50 -0000 Received: from asf.osuosl.org (HELO asf.osuosl.org) (140.211.166.49) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 11 Jul 2006 21:12:50 -0700 X-ASF-Spam-Status: No, hits=-9.4 required=10.0 tests=ALL_TRUSTED,NO_REAL_NAME X-Spam-Check-By: apache.org Received-SPF: pass (asf.osuosl.org: local policy) Received: from [140.211.166.113] (HELO eris.apache.org) (140.211.166.113) by apache.org (qpsmtpd/0.29) with ESMTP; Tue, 11 Jul 2006 21:12:41 -0700 Received: by eris.apache.org (Postfix, from userid 65534) id C09901A9820; Tue, 11 Jul 2006 21:12:20 -0700 (PDT) Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit Subject: svn commit: r421111 [3/11] - in /incubator/harmony/enhanced/classlib/trunk/sandbox: ./ juc-proposal/ juc-proposal/concurrent/ juc-proposal/concurrent/.settings/ juc-proposal/concurrent/META-INF/ juc-proposal/concurrent/src/ juc-proposal/concurrent/src/... Date: Wed, 12 Jul 2006 04:12:08 -0000 To: harmony-commits@incubator.apache.org From: ndbeyer@apache.org X-Mailer: svnmailer-1.0.8 Message-Id: <20060712041220.C09901A9820@eris.apache.org> X-Virus-Checked: Checked by ClamAV on apache.org X-Spam-Rating: minotaur.apache.org 1.6.2 0/1000/N Added: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java?rev=421111&view=auto ============================================================================== --- incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java (added) +++ incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java Tue Jul 11 21:12:04 2006 @@ -0,0 +1,1178 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group. Adapted and released, under explicit permission, + * from JDK ArrayList.java which carries the following copyright: + * + * Copyright 1997 by Sun Microsystems, Inc., + * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A. + * All rights reserved. + * + * This software is the confidential and proprietary information + * of Sun Microsystems, Inc. ("Confidential Information"). You + * shall not disclose such Confidential Information and shall use + * it only in accordance with the terms of the license agreement + * you entered into with Sun. + */ + +package java.util.concurrent; +import java.util.*; + +/** + * A variant of {@link java.util.ArrayList} in which all mutative + * operations (add, set, and so on) are implemented by making a fresh + * copy of the underlying array. + * + *

This is ordinarily too costly, but may be more efficient + * than alternatives when traversal operations vastly outnumber + * mutations, and is useful when you cannot or don't want to + * synchronize traversals, yet need to preclude interference among + * concurrent threads. The "snapshot" style iterator method uses a + * reference to the state of the array at the point that the iterator + * was created. This array never changes during the lifetime of the + * iterator, so interference is impossible and the iterator is + * guaranteed not to throw ConcurrentModificationException. + * The iterator will not reflect additions, removals, or changes to + * the list since the iterator was created. Element-changing + * operations on iterators themselves (remove, set, and add) are not + * supported. These methods throw + * UnsupportedOperationException. + * + *

This class is a member of the + * + * Java Collections Framework. + * + * @since 1.5 + * @author Doug Lea + * @param the type of elements held in this collection + */ +public class CopyOnWriteArrayList + implements List, RandomAccess, Cloneable, java.io.Serializable { + private static final long serialVersionUID = 8673264195747942595L; + + /** + * The held array. Directly accessed only within synchronized + * methods + */ + private volatile transient E[] array; + + /** + * Accessor to the array intended to be called from + * within unsynchronized read-only methods + **/ + private E[] array() { return array; } + + /** + * Creates an empty list. + */ + public CopyOnWriteArrayList() { + array = (E[]) new Object[0]; + } + + /** + * Creates a list containing the elements of the specified + * Collection, in the order they are returned by the Collection's + * iterator. + * @param c the collection of initially held elements + */ + public CopyOnWriteArrayList(Collection c) { + array = (E[]) new Object[c.size()]; + Iterator i = c.iterator(); + int size = 0; + while (i.hasNext()) + array[size++] = i.next(); + } + + /** + * Create a new CopyOnWriteArrayList holding a copy of given array. + * + * @param toCopyIn the array (a copy of this array is used as the + * internal array) + **/ + public CopyOnWriteArrayList(E[] toCopyIn) { + copyIn(toCopyIn, 0, toCopyIn.length); + } + + /** + * Replace the held array with a copy of the n elements + * of the provided array, starting at position first. To + * copy an entire array, call with arguments (array, 0, + * array.length). + * @param toCopyIn the array. A copy of the indicated elements of + * this array is used as the internal array. + * @param first The index of first position of the array to + * start copying from. + * @param n the number of elements to copy. This will be the new size of + * the list. + **/ + private synchronized void copyIn(E[] toCopyIn, int first, int n) { + array = (E[]) new Object[n]; + System.arraycopy(toCopyIn, first, array, 0, n); + } + + /** + * Returns the number of elements in this list. + * + * @return the number of elements in this list. + */ + public int size() { + return array().length; + } + + /** + * Tests if this list has no elements. + * + * @return true if this list has no elements; + * false otherwise. + */ + public boolean isEmpty() { + return size() == 0; + } + + /** + * Returns true if this list contains the specified element. + * + * @param elem element whose presence in this List is to be tested. + * @return true if the specified element is present; + * false otherwise. + */ + public boolean contains(Object elem) { + E[] elementData = array(); + int len = elementData.length; + return indexOf(elem, elementData, len) >= 0; + } + + /** + * Searches for the first occurrence of the given argument, testing + * for equality using the equals method. + * + * @param elem an object. + * @return the index of the first occurrence of the argument in this + * list; returns -1 if the object is not found. + * @see Object#equals(Object) + */ + public int indexOf(Object elem) { + E[] elementData = array(); + int len = elementData.length; + return indexOf(elem, elementData, len); + } + + /** + * static version allows repeated call without needed + * to grab lock for array each time + **/ + private static int indexOf(Object elem, Object[] elementData, int len) { + if (elem == null) { + for (int i = 0; i < len; i++) + if (elementData[i]==null) + return i; + } else { + for (int i = 0; i < len; i++) + if (elem.equals(elementData[i])) + return i; + } + return -1; + } + + /** + * Searches for the first occurrence of the given argument, beginning + * the search at index, and testing for equality using + * the equals method. + * + * @param elem an object. + * @param index the index to start searching from. + * @return the index of the first occurrence of the object argument in + * this List at position index or later in the + * List; returns -1 if the object is not found. + * @see Object#equals(Object) + */ + public int indexOf(E elem, int index) { + E[] elementData = array(); + int elementCount = elementData.length; + + if (elem == null) { + for (int i = index ; i < elementCount ; i++) + if (elementData[i]==null) + return i; + } else { + for (int i = index ; i < elementCount ; i++) + if (elem.equals(elementData[i])) + return i; + } + return -1; + } + + /** + * Returns the index of the last occurrence of the specified object in + * this list. + * + * @param elem the desired element. + * @return the index of the last occurrence of the specified object in + * this list; returns -1 if the object is not found. + */ + public int lastIndexOf(Object elem) { + E[] elementData = array(); + int len = elementData.length; + return lastIndexOf(elem, elementData, len); + } + + private static int lastIndexOf(Object elem, Object[] elementData, int len) { + if (elem == null) { + for (int i = len-1; i >= 0; i--) + if (elementData[i]==null) + return i; + } else { + for (int i = len-1; i >= 0; i--) + if (elem.equals(elementData[i])) + return i; + } + return -1; + } + + /** + * Searches backwards for the specified object, starting from the + * specified index, and returns an index to it. + * + * @param elem the desired element. + * @param index the index to start searching from. + * @return the index of the last occurrence of the specified object in this + * List at position less than index in the List; + * -1 if the object is not found. + */ + public int lastIndexOf(E elem, int index) { + // needed in order to compile on 1.2b3 + E[] elementData = array(); + if (elem == null) { + for (int i = index; i >= 0; i--) + if (elementData[i]==null) + return i; + } else { + for (int i = index; i >= 0; i--) + if (elem.equals(elementData[i])) + return i; + } + return -1; + } + + /** + * Returns a shallow copy of this list. (The elements themselves + * are not copied.) + * + * @return a clone of this list. + */ + public Object clone() { + try { + E[] elementData = array(); + CopyOnWriteArrayList v = (CopyOnWriteArrayList)super.clone(); + v.array = (E[]) new Object[elementData.length]; + System.arraycopy(elementData, 0, v.array, 0, elementData.length); + return v; + } catch (CloneNotSupportedException e) { + // this shouldn't happen, since we are Cloneable + throw new InternalError(); + } + } + + /** + * Returns an array containing all of the elements in this list + * in the correct order. + * @return an array containing all of the elements in this list + * in the correct order. + */ + public Object[] toArray() { + Object[] elementData = array(); + Object[] result = new Object[elementData.length]; + System.arraycopy(elementData, 0, result, 0, elementData.length); + return result; + } + + /** + * Returns an array containing all of the elements in this list in the + * correct order. The runtime type of the returned array is that of the + * specified array. If the list fits in the specified array, it is + * returned therein. Otherwise, a new array is allocated with the runtime + * type of the specified array and the size of this list. + *

+ * If the list fits in the specified array with room to spare + * (i.e., the array has more elements than the list), + * the element in the array immediately following the end of the + * collection is set to null. This is useful in determining the length + * of the list only if the caller knows that the list + * does not contain any null elements. + * + * @param a the array into which the elements of the list are to + * be stored, if it is big enough; otherwise, a new array of the + * same runtime type is allocated for this purpose. + * @return an array containing the elements of the list. + * @throws ArrayStoreException the runtime type of a is not a supertype + * of the runtime type of every element in this list. + */ + public T[] toArray(T a[]) { + E[] elementData = array(); + + if (a.length < elementData.length) + a = (T[]) + java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), + elementData.length); + + System.arraycopy(elementData, 0, a, 0, elementData.length); + + if (a.length > elementData.length) + a[elementData.length] = null; + + return a; + } + + // Positional Access Operations + + /** + * Returns the element at the specified position in this list. + * + * @param index index of element to return. + * @return the element at the specified position in this list. + * @throws IndexOutOfBoundsException if index is out of range (index + * < 0 || index >= size()). + */ + public E get(int index) { + E[] elementData = array(); + rangeCheck(index, elementData.length); + return elementData[index]; + } + + /** + * Replaces the element at the specified position in this list with + * the specified element. + * + * @param index index of element to replace. + * @param element element to be stored at the specified position. + * @return the element previously at the specified position. + * @throws IndexOutOfBoundsException if index out of range + * (index < 0 || index >= size()). + */ + public synchronized E set(int index, E element) { + int len = array.length; + rangeCheck(index, len); + E oldValue = array[index]; + + boolean same = (oldValue == element || + (element != null && element.equals(oldValue))); + if (!same) { + E[] newArray = (E[]) new Object[len]; + System.arraycopy(array, 0, newArray, 0, len); + newArray[index] = element; + array = newArray; + } + return oldValue; + } + + /** + * Appends the specified element to the end of this list. + * + * @param element element to be appended to this list. + * @return true (as per the general contract of Collection.add). + */ + public synchronized boolean add(E element) { + int len = array.length; + E[] newArray = (E[]) new Object[len+1]; + System.arraycopy(array, 0, newArray, 0, len); + newArray[len] = element; + array = newArray; + return true; + } + + /** + * Inserts the specified element at the specified position in this + * list. Shifts the element currently at that position (if any) and + * any subsequent elements to the right (adds one to their indices). + * + * @param index index at which the specified element is to be inserted. + * @param element element to be inserted. + * @throws IndexOutOfBoundsException if index is out of range + * (index < 0 || index > size()). + */ + public synchronized void add(int index, E element) { + int len = array.length; + if (index > len || index < 0) + throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len); + + E[] newArray = (E[]) new Object[len+1]; + System.arraycopy(array, 0, newArray, 0, index); + newArray[index] = element; + System.arraycopy(array, index, newArray, index+1, len - index); + array = newArray; + } + + /** + * Removes the element at the specified position in this list. + * Shifts any subsequent elements to the left (subtracts one from their + * indices). + * + * @param index the index of the element to removed. + * @return the element that was removed from the list. + * @throws IndexOutOfBoundsException if index out of range (index + * < 0 || index >= size()). + */ + public synchronized E remove(int index) { + int len = array.length; + rangeCheck(index, len); + E oldValue = array[index]; + E[] newArray = (E[]) new Object[len-1]; + System.arraycopy(array, 0, newArray, 0, index); + int numMoved = len - index - 1; + if (numMoved > 0) + System.arraycopy(array, index+1, newArray, index, numMoved); + array = newArray; + return oldValue; + } + + /** + * Removes a single instance of the specified element from this + * list, if it is present (optional operation). More formally, + * removes an element e such that (o==null ? e==null : + * o.equals(e)), if the list contains one or more such + * elements. Returns true if the list contained the + * specified element (or equivalently, if the list changed as a + * result of the call).

+ * + * @param o element to be removed from this list, if present. + * @return true if the list contained the specified element. + */ + public synchronized boolean remove(Object o) { + int len = array.length; + if (len == 0) return false; + + // Copy while searching for element to remove + // This wins in the normal case of element being present + + int newlen = len-1; + E[] newArray = (E[]) new Object[newlen]; + + for (int i = 0; i < newlen; ++i) { + if (o == array[i] || + (o != null && o.equals(array[i]))) { + // found one; copy remaining and exit + for (int k = i + 1; k < len; ++k) newArray[k-1] = array[k]; + array = newArray; + return true; + } else + newArray[i] = array[i]; + } + // special handling for last cell + + if (o == array[newlen] || + (o != null && o.equals(array[newlen]))) { + array = newArray; + return true; + } else + return false; // throw away copy + } + + + /** + * Removes from this List all of the elements whose index is between + * fromIndex, inclusive and toIndex, exclusive. Shifts any succeeding + * elements to the left (reduces their index). + * This call shortens the list by (toIndex - fromIndex) elements. + * (If toIndex==fromIndex, this operation has no effect.) + * + * @param fromIndex index of first element to be removed. + * @param toIndex index after last element to be removed. + * @throws IndexOutOfBoundsException fromIndex or toIndex out of + * range (fromIndex < 0 || fromIndex >= size() || toIndex + * > size() || toIndex < fromIndex). + */ + private synchronized void removeRange(int fromIndex, int toIndex) { + int len = array.length; + + if (fromIndex < 0 || fromIndex >= len || + toIndex > len || toIndex < fromIndex) + throw new IndexOutOfBoundsException(); + + int numMoved = len - toIndex; + int newlen = len - (toIndex-fromIndex); + E[] newArray = (E[]) new Object[newlen]; + System.arraycopy(array, 0, newArray, 0, fromIndex); + System.arraycopy(array, toIndex, newArray, fromIndex, numMoved); + array = newArray; + } + + + /** + * Append the element if not present. + * @param element element to be added to this Collection, if absent. + * @return true if added + **/ + public synchronized boolean addIfAbsent(E element) { + // Copy while checking if already present. + // This wins in the most common case where it is not present + int len = array.length; + E[] newArray = (E[]) new Object[len + 1]; + for (int i = 0; i < len; ++i) { + if (element == array[i] || + (element != null && element.equals(array[i]))) + return false; // exit, throwing away copy + else + newArray[i] = array[i]; + } + newArray[len] = element; + array = newArray; + return true; + } + + /** + * Returns true if this Collection contains all of the elements in the + * specified Collection. + *

+ * This implementation iterates over the specified Collection, checking + * each element returned by the Iterator in turn to see if it's + * contained in this Collection. If all elements are so contained + * true is returned, otherwise false. + * @param c the collection + * @return true if all elements are contained + */ + public boolean containsAll(Collection c) { + E[] elementData = array(); + int len = elementData.length; + Iterator e = c.iterator(); + while (e.hasNext()) + if (indexOf(e.next(), elementData, len) < 0) + return false; + + return true; + } + + + /** + * Removes from this Collection all of its elements that are contained in + * the specified Collection. This is a particularly expensive operation + * in this class because of the need for an internal temporary array. + *

+ * + * @param c the collection + * @return true if this Collection changed as a result of the call. + */ + public synchronized boolean removeAll(Collection c) { + E[] elementData = array; + int len = elementData.length; + if (len == 0) return false; + + // temp array holds those elements we know we want to keep + E[] temp = (E[]) new Object[len]; + int newlen = 0; + for (int i = 0; i < len; ++i) { + E element = elementData[i]; + if (!c.contains(element)) { + temp[newlen++] = element; + } + } + + if (newlen == len) return false; + + // copy temp as new array + E[] newArray = (E[]) new Object[newlen]; + System.arraycopy(temp, 0, newArray, 0, newlen); + array = newArray; + return true; + } + + /** + * Retains only the elements in this Collection that are contained in the + * specified Collection (optional operation). In other words, removes from + * this Collection all of its elements that are not contained in the + * specified Collection. + * @param c the collection + * @return true if this Collection changed as a result of the call. + */ + public synchronized boolean retainAll(Collection c) { + E[] elementData = array; + int len = elementData.length; + if (len == 0) return false; + + E[] temp = (E[]) new Object[len]; + int newlen = 0; + for (int i = 0; i < len; ++i) { + E element = elementData[i]; + if (c.contains(element)) { + temp[newlen++] = element; + } + } + + if (newlen == len) return false; + + E[] newArray = (E[]) new Object[newlen]; + System.arraycopy(temp, 0, newArray, 0, newlen); + array = newArray; + return true; + } + + /** + * Appends all of the elements in the specified Collection that + * are not already contained in this list, to the end of + * this list, in the order that they are returned by the + * specified Collection's Iterator. + * + * @param c elements to be added into this list. + * @return the number of elements added + */ + public synchronized int addAllAbsent(Collection c) { + int numNew = c.size(); + if (numNew == 0) return 0; + + E[] elementData = array; + int len = elementData.length; + + E[] temp = (E[]) new Object[numNew]; + int added = 0; + Iterator e = c.iterator(); + while (e.hasNext()) { + E element = e.next(); + if (indexOf(element, elementData, len) < 0) { + if (indexOf(element, temp, added) < 0) { + temp[added++] = element; + } + } + } + + if (added == 0) return 0; + + E[] newArray = (E[]) new Object[len+added]; + System.arraycopy(elementData, 0, newArray, 0, len); + System.arraycopy(temp, 0, newArray, len, added); + array = newArray; + return added; + } + + /** + * Removes all of the elements from this list. + * + */ + public synchronized void clear() { + array = (E[]) new Object[0]; + } + + /** + * Appends all of the elements in the specified Collection to the end of + * this list, in the order that they are returned by the + * specified Collection's Iterator. + * + * @param c elements to be inserted into this list. + * @return true if any elements are added + */ + public synchronized boolean addAll(Collection c) { + int numNew = c.size(); + if (numNew == 0) return false; + + int len = array.length; + E[] newArray = (E[]) new Object[len+numNew]; + System.arraycopy(array, 0, newArray, 0, len); + Iterator e = c.iterator(); + for (int i=0; i c) { + int len = array.length; + if (index > len || index < 0) + throw new IndexOutOfBoundsException("Index: "+index+", Size: "+len); + + int numNew = c.size(); + if (numNew == 0) return false; + + E[] newArray = (E[]) new Object[len+numNew]; + System.arraycopy(array, 0, newArray, 0, len); + int numMoved = len - index; + if (numMoved > 0) + System.arraycopy(array, index, newArray, index + numNew, numMoved); + Iterator e = c.iterator(); + for (int i=0; i= length || index < 0) + throw new IndexOutOfBoundsException("Index: "+index+", Size: "+ length); + } + + /** + * Save the state of the list to a stream (i.e., serialize it). + * + * @serialData The length of the array backing the list is emitted + * (int), followed by all of its elements (each an Object) + * in the proper order. + * @param s the stream + */ + private void writeObject(java.io.ObjectOutputStream s) + throws java.io.IOException{ + + // Write out element count, and any hidden stuff + s.defaultWriteObject(); + + E[] elementData = array(); + // Write out array length + s.writeInt(elementData.length); + + // Write out all elements in the proper order. + for (int i=0; i

+ * This implementation first checks if the specified object is this + * List. If so, it returns true; if not, it checks if the specified + * object is a List. If not, it returns false; if so, it iterates over + * both lists, comparing corresponding pairs of elements. If any + * comparison returns false, this method returns false. If either + * Iterator runs out of elements before the other it returns false + * (as the Lists are of unequal length); otherwise it returns true when + * the iterations complete. + * + * @param o the Object to be compared for equality with this List. + * @return true if the specified Object is equal to this List. + */ + public boolean equals(Object o) { + if (o == this) + return true; + if (!(o instanceof List)) + return false; + + List l2 = (List)(o); + if (size() != l2.size()) + return false; + + ListIterator e1 = listIterator(); + ListIterator e2 = l2.listIterator(); + while(e1.hasNext()) { + E o1 = e1.next(); + E o2 = e2.next(); + if (!(o1==null ? o2==null : o1.equals(o2))) + return false; + } + return true; + } + + /** + * Returns the hash code value for this List. + * + *

This implementation uses the definition in {@link + * List#hashCode}. + * @return the hash code + */ + public int hashCode() { + int hashCode = 1; + Iterator i = iterator(); + while (i.hasNext()) { + E obj = i.next(); + hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); + } + return hashCode; + } + + /** + * Returns an Iterator over the elements contained in this collection. + * The iterator provides a snapshot of the state of the list + * when the iterator was constructed. No synchronization is + * needed while traversing the iterator. The iterator does + * NOT support the remove method. + * @return the iterator + */ + public Iterator iterator() { + return new COWIterator(array(), 0); + } + + /** + * Returns an Iterator of the elements in this List (in proper sequence). + * The iterator provides a snapshot of the state of the list + * when the iterator was constructed. No synchronization is + * needed while traversing the iterator. The iterator does + * NOT support the remove, set, + * or add methods. + * @return the iterator + * + */ + public ListIterator listIterator() { + return new COWIterator(array(), 0); + } + + /** + * Returns a ListIterator of the elements in this List (in proper + * sequence), starting at the specified position in the List. The + * specified index indicates the first element that would be returned by + * an initial call to nextElement. An initial call to previousElement + * would return the element with the specified index minus one. + * The ListIterator returned by this implementation will throw + * an UnsupportedOperationException in its remove, set and + * add methods. + * + * @param index index of first element to be returned from the + * ListIterator (by a call to getNext). + * @return the iterator + * @throws IndexOutOfBoundsException index is out of range + * (index < 0 || index > size()). + */ + public ListIterator listIterator(final int index) { + E[] elementData = array(); + int len = elementData.length; + if (index<0 || index>len) + throw new IndexOutOfBoundsException("Index: "+index); + + return new COWIterator(array(), index); + } + + private static class COWIterator implements ListIterator { + + /** Snapshot of the array **/ + private final E[] array; + + /** + * Index of element to be returned by subsequent call to next. + */ + private int cursor; + + private COWIterator(E[] elementArray, int initialCursor) { + array = elementArray; + cursor = initialCursor; + } + + public boolean hasNext() { + return cursor < array.length; + } + + public boolean hasPrevious() { + return cursor > 0; + } + + public E next() { + try { + return array[cursor++]; + } catch (IndexOutOfBoundsException ex) { + throw new NoSuchElementException(); + } + } + + public E previous() { + try { + return array[--cursor]; + } catch(IndexOutOfBoundsException e) { + throw new NoSuchElementException(); + } + } + + public int nextIndex() { + return cursor; + } + + public int previousIndex() { + return cursor-1; + } + + /** + * Not supported. Always throws UnsupportedOperationException. + * @throws UnsupportedOperationException remove is not supported + * by this Iterator. + */ + + public void remove() { + throw new UnsupportedOperationException(); + } + + /** + * Not supported. Always throws UnsupportedOperationException. + * @throws UnsupportedOperationException set is not supported + * by this Iterator. + */ + public void set(E o) { + throw new UnsupportedOperationException(); + } + + /** + * Not supported. Always throws UnsupportedOperationException. + * @throws UnsupportedOperationException add is not supported + * by this Iterator. + */ + public void add(E o) { + throw new UnsupportedOperationException(); + } + } + + + /** + * Returns a view of the portion of this List between fromIndex, + * inclusive, and toIndex, exclusive. The returned List is backed by this + * List, so changes in the returned List are reflected in this List, and + * vice-versa. While mutative operations are supported, they are + * probably not very useful for CopyOnWriteArrayLists. + *

+ * The semantics of the List returned by this method become undefined if + * the backing list (i.e., this List) is structurally modified in + * any way other than via the returned List. (Structural modifications are + * those that change the size of the List, or otherwise perturb it in such + * a fashion that iterations in progress may yield incorrect results.) + * + * @param fromIndex low endpoint (inclusive) of the subList. + * @param toIndex high endpoint (exclusive) of the subList. + * @return a view of the specified range within this List. + * @throws IndexOutOfBoundsException Illegal endpoint index value + * (fromIndex < 0 || toIndex > size || fromIndex > toIndex). + */ + public synchronized List subList(int fromIndex, int toIndex) { + // synchronized since sublist constructor depends on it. + int len = array.length; + if (fromIndex<0 || toIndex>len || fromIndex>toIndex) + throw new IndexOutOfBoundsException(); + return new COWSubList(this, fromIndex, toIndex); + } + + private static class COWSubList extends AbstractList { + + /* + This class extends AbstractList merely for convenience, to + avoid having to define addAll, etc. This doesn't hurt, but + is wasteful. This class does not need or use modCount + mechanics in AbstractList, but does need to check for + concurrent modification using similar mechanics. On each + operation, the array that we expect the backing list to use + is checked and updated. Since we do this for all of the + base operations invoked by those defined in AbstractList, + all is well. While inefficient, this is not worth + improving. The kinds of list operations inherited from + AbstractList are already so slow on COW sublists that + adding a bit more space/time doesn't seem even noticeable. + */ + + private final CopyOnWriteArrayList l; + private final int offset; + private int size; + private E[] expectedArray; + + private COWSubList(CopyOnWriteArrayList list, + int fromIndex, int toIndex) { + l = list; + expectedArray = l.array(); + offset = fromIndex; + size = toIndex - fromIndex; + } + + // only call this holding l's lock + private void checkForComodification() { + if (l.array != expectedArray) + throw new ConcurrentModificationException(); + } + + // only call this holding l's lock + private void rangeCheck(int index) { + if (index<0 || index>=size) + throw new IndexOutOfBoundsException("Index: "+index+ ",Size: "+size); + } + + + public E set(int index, E element) { + synchronized(l) { + rangeCheck(index); + checkForComodification(); + E x = l.set(index+offset, element); + expectedArray = l.array; + return x; + } + } + + public E get(int index) { + synchronized(l) { + rangeCheck(index); + checkForComodification(); + return l.get(index+offset); + } + } + + public int size() { + synchronized(l) { + checkForComodification(); + return size; + } + } + + public void add(int index, E element) { + synchronized(l) { + checkForComodification(); + if (index<0 || index>size) + throw new IndexOutOfBoundsException(); + l.add(index+offset, element); + expectedArray = l.array; + size++; + } + } + + public void clear() { + synchronized(l) { + checkForComodification(); + l.removeRange(offset, offset+size); + expectedArray = l.array; + size = 0; + } + } + + public E remove(int index) { + synchronized(l) { + rangeCheck(index); + checkForComodification(); + E result = l.remove(index+offset); + expectedArray = l.array; + size--; + return result; + } + } + + public Iterator iterator() { + synchronized(l) { + checkForComodification(); + return new COWSubListIterator(l, 0, offset, size); + } + } + + public ListIterator listIterator(final int index) { + synchronized(l) { + checkForComodification(); + if (index<0 || index>size) + throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size); + return new COWSubListIterator(l, index, offset, size); + } + } + + public List subList(int fromIndex, int toIndex) { + synchronized(l) { + checkForComodification(); + if (fromIndex<0 || toIndex>size) + throw new IndexOutOfBoundsException(); + return new COWSubList(l, fromIndex+offset, toIndex+offset); + } + } + + } + + + private static class COWSubListIterator implements ListIterator { + private final ListIterator i; + private final int index; + private final int offset; + private final int size; + private COWSubListIterator(List l, int index, int offset, int size) { + this.index = index; + this.offset = offset; + this.size = size; + i = l.listIterator(index+offset); + } + + public boolean hasNext() { + return nextIndex() < size; + } + + public E next() { + if (hasNext()) + return i.next(); + else + throw new NoSuchElementException(); + } + + public boolean hasPrevious() { + return previousIndex() >= 0; + } + + public E previous() { + if (hasPrevious()) + return i.previous(); + else + throw new NoSuchElementException(); + } + + public int nextIndex() { + return i.nextIndex() - offset; + } + + public int previousIndex() { + return i.previousIndex() - offset; + } + + public void remove() { + throw new UnsupportedOperationException(); + } + + public void set(E o) { + throw new UnsupportedOperationException(); + } + + public void add(E o) { + throw new UnsupportedOperationException(); + } + } + +} Propchange: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArrayList.java ------------------------------------------------------------------------------ svn:eol-style = native Added: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java?rev=421111&view=auto ============================================================================== --- incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java (added) +++ incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CopyOnWriteArraySet.java Tue Jul 11 21:12:04 2006 @@ -0,0 +1,101 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain. Use, modify, and + * redistribute this code in any way without acknowledgement. + */ + +package java.util.concurrent; +import java.util.*; + +/** + * A {@link java.util.Set} that uses {@link + * java.util.concurrent.CopyOnWriteArrayList} for all of its + * operations. Thus, it shares the same basic properties: + *

It is best suited for applications in which set sizes generally + * stay small, read-only operations + * vastly outnumber mutative operations, and you need + * to prevent interference among threads during traversal. + *
Mutative operations(add, set, remove, etc) are expensive + * since they usually entail copying the entire underlying array. + *
Iterators do not support the mutative remove operation + *
Traversal via iterators is very fast and cannot ever encounter + * interference from other threads. Iterators rely on + * unchanging snapshots of the array at the time the iterators were + * constructed. + *

+ *

+ * Sample Usage. Probably the main application + * of copy-on-write sets are classes that maintain + * sets of Handler objects + * that must be multicasted to upon an update command. This + * is a classic case where you do not want to be holding a + * lock while sending a message, and where traversals normally + * vastly overwhelm additions. + *

+ * class Handler { void handle(); ... }
+ *
+ * class X {
+ *    private final CopyOnWriteArraySet<Handler> handlers = new CopyOnWriteArraySet<Handler>();
+ *    public void addHandler(Handler h) { handlers.add(h); }
+ *
+ *    private long internalState;
+ *    private synchronized void changeState() { internalState = ...; }
+ *
+ *    public void update() {
+ *       changeState();
+ *       Iterator it = handlers.iterator();
+ *       while (it.hasNext())
+ *          it.next().handle();
+ *    }
+ * }
+ *

+ * @see CopyOnWriteArrayList + * + *

A CountDownLatch is initialized with a given + * count. The {@link #await await} methods block until the current + * {@link #getCount count} reaches zero due to invocations of the + * {@link #countDown} method, after which all waiting threads are + * released and any subsequent invocations of {@link #await await} return + * immediately. This is a one-shot phenomenon -- the count cannot be + * reset. If you need a version that resets the count, consider using + * a {@link CyclicBarrier}. + * + *

A CountDownLatch is a versatile synchronization tool + * and can be used for a number of purposes. A + * CountDownLatch initialized with a count of one serves as a + * simple on/off latch, or gate: all threads invoking {@link #await await} + * wait at the gate until it is opened by a thread invoking {@link + * #countDown}. A CountDownLatch initialized to N + * can be used to make one thread wait until N threads have + * completed some action, or some action has been completed N times. + *

A useful property of a CountDownLatch is that it + * doesn't require that threads calling countDown wait for + * the count to reach zero before proceeding, it simply prevents any + * thread from proceeding past an {@link #await await} until all + * threads could pass. + * + *

Sample usage: Here is a pair of classes in which a group + * of worker threads use two countdown latches: + *

The first is a start signal that prevents any worker from proceeding + * until the driver is ready for them to proceed; + *
The second is a completion signal that allows the driver to wait + * until all workers have completed. + *

+ * + *

+ * class Driver { // ...
+ *   void main() throws InterruptedException {
+ *     CountDownLatch startSignal = new CountDownLatch(1);
+ *     CountDownLatch doneSignal = new CountDownLatch(N);
+ *
+ *     for (int i = 0; i < N; ++i) // create and start threads
+ *       new Thread(new Worker(startSignal, doneSignal)).start();
+ *
+ *     doSomethingElse();            // don't let run yet
+ *     startSignal.countDown();      // let all threads proceed
+ *     doSomethingElse();
+ *     doneSignal.await();           // wait for all to finish
+ *   }
+ * }
+ *
+ * class Worker implements Runnable {
+ *   private final CountDownLatch startSignal;
+ *   private final CountDownLatch doneSignal;
+ *   Worker(CountDownLatch startSignal, CountDownLatch doneSignal) {
+ *      this.startSignal = startSignal;
+ *      this.doneSignal = doneSignal;
+ *   }
+ *   public void run() {
+ *      try {
+ *        startSignal.await();
+ *        doWork();
+ *        doneSignal.countDown();
+ *      } catch (InterruptedException ex) {} // return;
+ *   }
+ *
+ *   void doWork() { ... }
+ * }
+ *
+ *

+ * + *

Another typical usage would be to divide a problem into N parts, + * describe each part with a Runnable that executes that portion and + * counts down on the latch, and queue all the Runnables to an + * Executor. When all sub-parts are complete, the coordinating thread + * will be able to pass through await. (When threads must repeatedly + * count down in this way, instead use a {@link CyclicBarrier}.) + * + *

+ * class Driver2 { // ...
+ *   void main() throws InterruptedException {
+ *     CountDownLatch doneSignal = new CountDownLatch(N);
+ *     Executor e = ...
+ *
+ *     for (int i = 0; i < N; ++i) // create and start threads
+ *       e.execute(new WorkerRunnable(doneSignal, i));
+ *
+ *     doneSignal.await();           // wait for all to finish
+ *   }
+ * }
+ *
+ * class WorkerRunnable implements Runnable {
+ *   private final CountDownLatch doneSignal;
+ *   private final int i;
+ *   WorkerRunnable(CountDownLatch doneSignal, int i) {
+ *      this.doneSignal = doneSignal;
+ *      this.i = i;
+ *   }
+ *   public void run() {
+ *      try {
+ *        doWork(i);
+ *        doneSignal.countDown();
+ *      } catch (InterruptedException ex) {} // return;
+ *   }
+ *
+ *   void doWork() { ... }
+ * }
+ *
+ *

+ * + * @since 1.5 + * @author Doug Lea + */ +public class CountDownLatch { + /** + * Synchronization control For CountDownLatch. + * Uses AQS state to represent count. + */ + private static final class Sync extends AbstractQueuedSynchronizer { + Sync(int count) { + setState(count); + } + + int getCount() { + return getState(); + } + + public int tryAcquireShared(int acquires) { + return getState() == 0? 1 : -1; + } + + public boolean tryReleaseShared(int releases) { + // Decrement count; signal when transition to zero + for (;;) { + int c = getState(); + if (c == 0) + return false; + int nextc = c-1; + if (compareAndSetState(c, nextc)) + return nextc == 0; + } + } + } + + private final Sync sync; + /** + * Constructs a CountDownLatch initialized with the given + * count. + * + * @param count the number of times {@link #countDown} must be invoked + * before threads can pass through {@link #await}. + * + * @throws IllegalArgumentException if count is less than zero. + */ + public CountDownLatch(int count) { + if (count < 0) throw new IllegalArgumentException("count < 0"); + this.sync = new Sync(count); + } + + /** + * Causes the current thread to wait until the latch has counted down to + * zero, unless the thread is {@link Thread#interrupt interrupted}. + * + *

If the current {@link #getCount count} is zero then this method + * returns immediately. + *

If the current {@link #getCount count} is greater than zero then + * the current thread becomes disabled for thread scheduling + * purposes and lies dormant until one of two things happen: + *

The count reaches zero due to invocations of the + * {@link #countDown} method; or + *
Some other thread {@link Thread#interrupt interrupts} the current + * thread. + *

+ *

If the current thread: + *

has its interrupted status set on entry to this method; or + *
is {@link Thread#interrupt interrupted} while waiting, + *

+ * then {@link InterruptedException} is thrown and the current thread's + * interrupted status is cleared. + * + * @throws InterruptedException if the current thread is interrupted + * while waiting. + */ + public void await() throws InterruptedException { + sync.acquireSharedInterruptibly(1); + } + + /** + * Causes the current thread to wait until the latch has counted down to + * zero, unless the thread is {@link Thread#interrupt interrupted}, + * or the specified waiting time elapses. + * + *

If the current {@link #getCount count} is zero then this method + * returns immediately with the value true. + * + *

If the current {@link #getCount count} is greater than zero then + * the current thread becomes disabled for thread scheduling + * purposes and lies dormant until one of three things happen: + *

The count reaches zero due to invocations of the + * {@link #countDown} method; or + *
Some other thread {@link Thread#interrupt interrupts} the current + * thread; or + *
The specified waiting time elapses. + *

+ *

If the count reaches zero then the method returns with the + * value true. + *

If the current thread: + *

has its interrupted status set on entry to this method; or + *
is {@link Thread#interrupt interrupted} while waiting, + *

+ * then {@link InterruptedException} is thrown and the current thread's + * interrupted status is cleared. + * + *

If the specified waiting time elapses then the value false + * is returned. + * If the time is + * less than or equal to zero, the method will not wait at all. + * + * @param timeout the maximum time to wait + * @param unit the time unit of the timeout argument. + * @return true if the count reached zero and false + * if the waiting time elapsed before the count reached zero. + * + * @throws InterruptedException if the current thread is interrupted + * while waiting. + */ + public boolean await(long timeout, TimeUnit unit) + throws InterruptedException { + return sync.tryAcquireSharedNanos(1, unit.toNanos(timeout)); + } + + /** + * Decrements the count of the latch, releasing all waiting threads if + * the count reaches zero. + *

If the current {@link #getCount count} is greater than zero then + * it is decremented. If the new count is zero then all waiting threads + * are re-enabled for thread scheduling purposes. + *

If the current {@link #getCount count} equals zero then nothing + * happens. + */ + public void countDown() { + sync.releaseShared(1); + } + + /** + * Returns the current count. + *

This method is typically used for debugging and testing purposes. + * @return the current count. + */ + public long getCount() { + return sync.getCount(); + } + + /** + * Returns a string identifying this latch, as well as its state. + * The state, in brackets, includes the String + * "Count =" followed by the current count. + * @return a string identifying this latch, as well as its + * state + */ + public String toString() { + return super.toString() + "[Count = " + sync.getCount() + "]"; + } + +} Propchange: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CountDownLatch.java ------------------------------------------------------------------------------ svn:eol-style = native Added: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CyclicBarrier.java URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CyclicBarrier.java?rev=421111&view=auto ============================================================================== --- incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CyclicBarrier.java (added) +++ incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CyclicBarrier.java Tue Jul 11 21:12:04 2006 @@ -0,0 +1,430 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + +package java.util.concurrent; +import java.util.concurrent.locks.*; + +/** + * A synchronization aid that allows a set of threads to all wait for + * each other to reach a common barrier point. CyclicBarriers are + * useful in programs involving a fixed sized party of threads that + * must occasionally wait for each other. The barrier is called + * cyclic because it can be re-used after the waiting threads + * are released. + * + *

A CyclicBarrier supports an optional {@link Runnable} command + * that is run once per barrier point, after the last thread in the party + * arrives, but before any threads are released. + * This barrier action is useful + * for updating shared-state before any of the parties continue. + * + *

Sample usage: Here is an example of + * using a barrier in a parallel decomposition design: + *

+ * class Solver {
+ *   final int N;
+ *   final float[][] data;
+ *   final CyclicBarrier barrier;
+ *   
+ *   class Worker implements Runnable {
+ *     int myRow;
+ *     Worker(int row) { myRow = row; }
+ *     public void run() {
+ *       while (!done()) {
+ *         processRow(myRow);
+ *
+ *         try {
+ *           barrier.await(); 
+ *         } catch (InterruptedException ex) { 
+ *           return; 
+ *         } catch (BrokenBarrierException ex) { 
+ *           return; 
+ *         }
+ *       }
+ *     }
+ *   }
+ *
+ *   public Solver(float[][] matrix) {
+ *     data = matrix;
+ *     N = matrix.length;
+ *     barrier = new CyclicBarrier(N, 
+ *                                 new Runnable() {
+ *                                   public void run() { 
+ *                                     mergeRows(...); 
+ *                                   }
+ *                                 });
+ *     for (int i = 0; i < N; ++i) 
+ *       new Thread(new Worker(i)).start();
+ *
+ *     waitUntilDone();
+ *   }
+ * }
+ *

+ * Here, each worker thread processes a row of the matrix then waits at the + * barrier until all rows have been processed. When all rows are processed + * the supplied {@link Runnable} barrier action is executed and merges the + * rows. If the merger + * determines that a solution has been found then done() will return + * true and each worker will terminate. + * + *

If the barrier action does not rely on the parties being suspended when + * it is executed, then any of the threads in the party could execute that + * action when it is released. To facilitate this, each invocation of + * {@link #await} returns the arrival index of that thread at the barrier. + * You can then choose which thread should execute the barrier action, for + * example: + *

  if (barrier.await() == 0) {
+ *     // log the completion of this iteration
+ *   }

+ * + *

The CyclicBarrier uses a fast-fail all-or-none breakage + * model for failed synchronization attempts: If a thread leaves a + * barrier point prematurely because of interruption, failure, or + * timeout, all other threads, even those that have not yet resumed + * from a previous {@link #await}. will also leave abnormally via + * {@link BrokenBarrierException} (or InterruptedException if + * they too were interrupted at about the same time). + * + * @since 1.5 + * @see CountDownLatch + * + * @author Doug Lea + */ +public class CyclicBarrier { + /** The lock for guarding barrier entry */ + private final ReentrantLock lock = new ReentrantLock(); + /** Condition to wait on until tripped */ + private final Condition trip = lock.newCondition(); + /** The number of parties */ + private final int parties; + /* The command to run when tripped */ + private final Runnable barrierCommand; + + /** + * The generation number. Incremented upon barrier trip. + * Retracted upon reset. + */ + private long generation; + + /** + * Breakage indicator. + */ + private boolean broken; + + /** + * Number of parties still waiting. Counts down from parties to 0 + * on each cycle. + */ + private int count; + + /** + * Updates state on barrier trip and wake up everyone. + */ + private void nextGeneration() { + count = parties; + ++generation; + trip.signalAll(); + } + + /** + * Sets barrier as broken and wake up everyone + */ + private void breakBarrier() { + broken = true; + trip.signalAll(); + } + + /** + * Main barrier code, covering the various policies. + */ + private int dowait(boolean timed, long nanos) + throws InterruptedException, BrokenBarrierException, TimeoutException { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + int index = --count; + long g = generation; + + if (broken) + throw new BrokenBarrierException(); + + if (Thread.interrupted()) { + breakBarrier(); + throw new InterruptedException(); + } + + if (index == 0) { // tripped + nextGeneration(); + boolean ranAction = false; + try { + Runnable command = barrierCommand; + if (command != null) + command.run(); + ranAction = true; + return 0; + } finally { + if (!ranAction) + breakBarrier(); + } + } + + for (;;) { + try { + if (!timed) + trip.await(); + else if (nanos > 0L) + nanos = trip.awaitNanos(nanos); + } catch (InterruptedException ie) { + breakBarrier(); + throw ie; + } + + if (broken || + g > generation) // true if a reset occurred while waiting + throw new BrokenBarrierException(); + + if (g < generation) + return index; + + if (timed && nanos <= 0L) { + breakBarrier(); + throw new TimeoutException(); + } + } + + } finally { + lock.unlock(); + } + } + + /** + * Creates a new CyclicBarrier that will trip when the + * given number of parties (threads) are waiting upon it, and which + * will execute the given barrier action when the barrier is tripped, + * performed by the last thread entering the barrier. + * + * @param parties the number of threads that must invoke {@link #await} + * before the barrier is tripped. + * @param barrierAction the command to execute when the barrier is + * tripped, or null if there is no action. + * + * @throws IllegalArgumentException if parties is less than 1. + */ + public CyclicBarrier(int parties, Runnable barrierAction) { + if (parties <= 0) throw new IllegalArgumentException(); + this.parties = parties; + this.count = parties; + this.barrierCommand = barrierAction; + } + + /** + * Creates a new CyclicBarrier that will trip when the + * given number of parties (threads) are waiting upon it, and + * does not perform a predefined action upon each barrier. + * + * @param parties the number of threads that must invoke {@link #await} + * before the barrier is tripped. + * + * @throws IllegalArgumentException if parties is less than 1. + */ + public CyclicBarrier(int parties) { + this(parties, null); + } + + /** + * Returns the number of parties required to trip this barrier. + * @return the number of parties required to trip this barrier. + **/ + public int getParties() { + return parties; + } + + /** + * Waits until all {@link #getParties parties} have invoked await + * on this barrier. + * + *

If the current thread is not the last to arrive then it is + * disabled for thread scheduling purposes and lies dormant until + * one of following things happens: + *

The last thread arrives; or + *
Some other thread {@link Thread#interrupt interrupts} the current + * thread; or + *
Some other thread {@link Thread#interrupt interrupts} one of the + * other waiting threads; or + *
Some other thread times out while waiting for barrier; or + *
Some other thread invokes {@link #reset} on this barrier. + *

+ *

If the current thread: + *

has its interrupted status set on entry to this method; or + *
is {@link Thread#interrupt interrupted} while waiting + *

+ * then {@link InterruptedException} is thrown and the current thread's + * interrupted status is cleared. + * + *

If the barrier is {@link #reset} while any thread is waiting, or if + * the barrier {@link #isBroken is broken} when await is invoked, + * or while any thread is waiting, + * then {@link BrokenBarrierException} is thrown. + * + *

If any thread is {@link Thread#interrupt interrupted} while waiting, + * then all other waiting threads will throw + * {@link BrokenBarrierException} and the barrier is placed in the broken + * state. + * + *

If the current thread is not the last to arrive then it is + * disabled for thread scheduling purposes and lies dormant until + * one of the following things happens: + *

The last thread arrives; or + *
The specified timeout elapses; or + *
Some other thread {@link Thread#interrupt interrupts} the current + * thread; or + *
Some other thread {@link Thread#interrupt interrupts} one of the + * other waiting threads; or + *
Some other thread times out while waiting for barrier; or + *
Some other thread invokes {@link #reset} on this barrier. + *

+ *

If the current thread: + *

has its interrupted status set on entry to this method; or + *
is {@link Thread#interrupt interrupted} while waiting + *

+ * then {@link InterruptedException} is thrown and the current thread's + * interrupted status is cleared. + * + *

If the current thread is the last thread to arrive, and a + * non-null barrier action was supplied in the constructor, then the + * current thread runs the action before allowing the other threads to + * continue. + * If an exception occurs during the barrier action then that exception + * will be propagated in the current thread and the barrier is placed in + * the broken state. + * + * @param timeout the time to wait for the barrier + * @param unit the time unit of the timeout parameter + * @return the arrival index of the current thread, where index + * {@link #getParties()} - 1 indicates the first to arrive and + * zero indicates the last to arrive. + * + * @throws InterruptedException if the current thread was interrupted + * while waiting + * @throws TimeoutException if the specified timeout elapses. + * @throws BrokenBarrierException if another thread was + * interrupted while the current thread was waiting, or the barrier was + * reset, or the barrier was broken when await was called, + * or the barrier action (if present) failed due an exception. + */ + public int await(long timeout, TimeUnit unit) + throws InterruptedException, + BrokenBarrierException, + TimeoutException { + return dowait(true, unit.toNanos(timeout)); + } + + /** + * Queries if this barrier is in a broken state. + * @return true if one or more parties broke out of this + * barrier due to interruption or timeout since construction or + * the last reset, or a barrier action failed due to an exception; + * and false otherwise. + */ + public boolean isBroken() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return broken; + } finally { + lock.unlock(); + } + } + + /** + * Resets the barrier to its initial state. If any parties are + * currently waiting at the barrier, they will return with a + * {@link BrokenBarrierException}. Note that resets after + * a breakage has occurred for other reasons can be complicated to + * carry out; threads need to re-synchronize in some other way, + * and choose one to perform the reset. It may be preferable to + * instead create a new barrier for subsequent use. + */ + public void reset() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + /* + * Retract generation number enough to cover threads + * currently waiting on current and still resuming from + * previous generation, plus similarly accommodating spans + * after the reset. + */ + generation -= 4; + broken = false; + trip.signalAll(); + } finally { + lock.unlock(); + } + } + + /** + * Returns the number of parties currently waiting at the barrier. + * This method is primarily useful for debugging and assertions. + * + * @return the number of parties currently blocked in {@link #await} + **/ + public int getNumberWaiting() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return parties - count; + } finally { + lock.unlock(); + } + } + +} Propchange: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/CyclicBarrier.java ------------------------------------------------------------------------------ svn:eol-style = native Added: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/DelayQueue.java URL: http://svn.apache.org/viewvc/incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/DelayQueue.java?rev=421111&view=auto ============================================================================== --- incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/DelayQueue.java (added) +++ incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/DelayQueue.java Tue Jul 11 21:12:04 2006 @@ -0,0 +1,366 @@ +/* + * Written by Doug Lea with assistance from members of JCP JSR-166 + * Expert Group and released to the public domain, as explained at + * http://creativecommons.org/licenses/publicdomain + */ + + +package java.util.concurrent; +import java.util.concurrent.locks.*; +import java.util.*; + +/** + * An unbounded {@linkplain BlockingQueue blocking queue} of Delayed + * elements, in which an element can only be taken when its delay has expired. + * The head of the queue is that Delayed element whose delay + * expired furthest in the past - if no delay has expired there is no head and + * poll will return null. + * This queue does not permit null elements. + *

This class implements all of the optional methods + * of the {@link Collection} and {@link Iterator} interfaces. + * + *

This class is a member of the + * + * Java Collections Framework. + * + * @since 1.5 + * @author Doug Lea + * @param the type of elements held in this collection + */ + +public class DelayQueue extends AbstractQueue + implements BlockingQueue { + + private transient final ReentrantLock lock = new ReentrantLock(); + private transient final Condition available = lock.newCondition(); + private final PriorityQueue q = new PriorityQueue(); + + /** + * Creates a new DelayQueue that is initially empty. + */ + public DelayQueue() {} + + /** + * Creates a DelayQueue initially containing the elements of the + * given collection of {@link Delayed} instances. + * + * @param c the collection + * @throws NullPointerException if c or any element within it + * is null + * + */ + public DelayQueue(Collection c) { + this.addAll(c); + } + + /** + * Inserts the specified element into this delay queue. + * + * @param o the element to add + * @return true + * @throws NullPointerException if the specified element is null. + */ + public boolean offer(E o) { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + E first = q.peek(); + q.offer(o); + if (first == null || o.compareTo(first) < 0) + available.signalAll(); + return true; + } finally { + lock.unlock(); + } + } + + + /** + * Adds the specified element to this delay queue. As the queue is + * unbounded this method will never block. + * @param o the element to add + * @throws NullPointerException if the specified element is null. + */ + public void put(E o) { + offer(o); + } + + /** + * Inserts the specified element into this delay queue. As the queue is + * unbounded this method will never block. + * @param o the element to add + * @param timeout This parameter is ignored as the method never blocks + * @param unit This parameter is ignored as the method never blocks + * @return true + * @throws NullPointerException if the specified element is null. + */ + public boolean offer(E o, long timeout, TimeUnit unit) { + return offer(o); + } + + /** + * Adds the specified element to this queue. + * @param o the element to add + * @return true (as per the general contract of + * Collection.add). + * + * @throws NullPointerException if the specified element is null. + */ + public boolean add(E o) { + return offer(o); + } + + public E take() throws InterruptedException { + final ReentrantLock lock = this.lock; + lock.lockInterruptibly(); + try { + for (;;) { + E first = q.peek(); + if (first == null) { + available.await(); + } else { + long delay = first.getDelay(TimeUnit.NANOSECONDS); + if (delay > 0) { + long tl = available.awaitNanos(delay); + } else { + E x = q.poll(); + assert x != null; + if (q.size() != 0) + available.signalAll(); // wake up other takers + return x; + + } + } + } + } finally { + lock.unlock(); + } + } + + public E poll(long time, TimeUnit unit) throws InterruptedException { + final ReentrantLock lock = this.lock; + lock.lockInterruptibly(); + long nanos = unit.toNanos(time); + try { + for (;;) { + E first = q.peek(); + if (first == null) { + if (nanos <= 0) + return null; + else + nanos = available.awaitNanos(nanos); + } else { + long delay = first.getDelay(TimeUnit.NANOSECONDS); + if (delay > 0) { + if (delay > nanos) + delay = nanos; + long timeLeft = available.awaitNanos(delay); + nanos -= delay - timeLeft; + } else { + E x = q.poll(); + assert x != null; + if (q.size() != 0) + available.signalAll(); + return x; + } + } + } + } finally { + lock.unlock(); + } + } + + + public E poll() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + E first = q.peek(); + if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0) + return null; + else { + E x = q.poll(); + assert x != null; + if (q.size() != 0) + available.signalAll(); + return x; + } + } finally { + lock.unlock(); + } + } + + public E peek() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return q.peek(); + } finally { + lock.unlock(); + } + } + + public int size() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return q.size(); + } finally { + lock.unlock(); + } + } + + public int drainTo(Collection c) { + if (c == null) + throw new NullPointerException(); + if (c == this) + throw new IllegalArgumentException(); + final ReentrantLock lock = this.lock; + lock.lock(); + try { + int n = 0; + for (;;) { + E first = q.peek(); + if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0) + break; + c.add(q.poll()); + ++n; + } + if (n > 0) + available.signalAll(); + return n; + } finally { + lock.unlock(); + } + } + + public int drainTo(Collection c, int maxElements) { + if (c == null) + throw new NullPointerException(); + if (c == this) + throw new IllegalArgumentException(); + if (maxElements <= 0) + return 0; + final ReentrantLock lock = this.lock; + lock.lock(); + try { + int n = 0; + while (n < maxElements) { + E first = q.peek(); + if (first == null || first.getDelay(TimeUnit.NANOSECONDS) > 0) + break; + c.add(q.poll()); + ++n; + } + if (n > 0) + available.signalAll(); + return n; + } finally { + lock.unlock(); + } + } + + /** + * Atomically removes all of the elements from this delay queue. + * The queue will be empty after this call returns. + */ + public void clear() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + q.clear(); + } finally { + lock.unlock(); + } + } + + /** + * Always returns Integer.MAX_VALUE because + * a DelayQueue is not capacity constrained. + * @return Integer.MAX_VALUE + */ + public int remainingCapacity() { + return Integer.MAX_VALUE; + } + + public Object[] toArray() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return q.toArray(); + } finally { + lock.unlock(); + } + } + + public T[] toArray(T[] array) { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return q.toArray(array); + } finally { + lock.unlock(); + } + } + + public boolean remove(Object o) { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return q.remove(o); + } finally { + lock.unlock(); + } + } + + /** + * Returns an iterator over the elements in this queue. The iterator + * does not return the elements in any particular order. The + * returned iterator is a thread-safe "fast-fail" iterator that will + * throw {@link java.util.ConcurrentModificationException} + * upon detected interference. + * + * @return an iterator over the elements in this queue. + */ + public Iterator iterator() { + final ReentrantLock lock = this.lock; + lock.lock(); + try { + return new Itr(q.iterator()); + } finally { + lock.unlock(); + } + } + + private class Itr implements Iterator { + private final Iterator iter; + Itr(Iterator i) { + iter = i; + } + + public boolean hasNext() { + return iter.hasNext(); + } + + public E next() { + final ReentrantLock lock = DelayQueue.this.lock; + lock.lock(); + try { + return iter.next(); + } finally { + lock.unlock(); + } + } + + public void remove() { + final ReentrantLock lock = DelayQueue.this.lock; + lock.lock(); + try { + iter.remove(); + } finally { + lock.unlock(); + } + } + } + +} Propchange: incubator/harmony/enhanced/classlib/trunk/sandbox/juc-proposal/concurrent/src/main/java/java/util/concurrent/DelayQueue.java ------------------------------------------------------------------------------ svn:eol-style = native