[cp-patches] FYI: CopyOnWriteArrayList fixlets, part II
This should fix the last stuff. Maybe the Iterator returned by this subList needs some love too, but for now I'm happy. It passes all the tck public domain tests :) I've just pushed a mauve test also. Ciao, Mario 2008-03-26 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java (SubList.set): (SubList.clear): new method. (SubList.checkMod): fix indentation. (SubList.checkBoundsInclusive): likewise. (SubList.checkBoundsExclusive): likewise. (SubList): added synchronization. Now throw IndexOutOfBoundsException instead of IllegalArgumentException when index are out of range. (SubList.size): added synchronization. (SubList.get): likewise. (SubList.listIterator): fixed indentation. (SubList.set): added synchronization. Update the state of the storage after modification. (SubList.add): likewise. (SubList.remove): likewise. (SubList.addAll): likewise. -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ ### Eclipse Workspace Patch 1.0 #P classpath Index: java/util/concurrent/CopyOnWriteArrayList.java === RCS file: /sources/classpath/classpath/java/util/concurrent/CopyOnWriteArrayList.java,v retrieving revision 1.8 diff -u -r1.8 CopyOnWriteArrayList.java --- java/util/concurrent/CopyOnWriteArrayList.java 26 Mar 2008 11:23:40 - 1.8 +++ java/util/concurrent/CopyOnWriteArrayList.java 26 Mar 2008 16:03:15 - @@ -53,7 +53,6 @@ import java.util.ListIterator; import java.util.NoSuchElementException; import java.util.RandomAccess; -import java.util.concurrent.ConcurrentSkipListMap.Iter; /** * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is @@ -911,16 +910,16 @@ * @return a List backed by a subsection of this list * @throws IndexOutOfBoundsException if fromIndex lt; 0 * || toIndex gt; size() - * @throws IllegalArgumentException if fromIndex gt; toIndex + * @throws IndexOutOfBoundsException if fromIndex gt; toIndex * @see ConcurrentModificationException * @see RandomAccess */ - public ListE subList(int fromIndex, int toIndex) + public synchronized ListE subList(int fromIndex, int toIndex) { // This follows the specification of AbstractList, but is inconsistent // with the one in List. Don't you love Sun's inconsistencies? if (fromIndex toIndex) - throw new IllegalArgumentException(fromIndex ++ toIndex); + throw new IndexOutOfBoundsException(fromIndex ++ toIndex); if (fromIndex 0 || toIndex size()) throw new IndexOutOfBoundsException(); @@ -976,7 +975,7 @@ void checkMod() { if (data != backingList.data) - throw new ConcurrentModificationException(); +throw new ConcurrentModificationException(); } /** @@ -990,8 +989,8 @@ private void checkBoundsInclusive(int index) { if (index 0 || index size) - throw new IndexOutOfBoundsException(Index: + index + , Size: - + size); +throw new IndexOutOfBoundsException(Index: + index + +, Size: + size); } /** @@ -1005,8 +1004,8 @@ private void checkBoundsExclusive(int index) { if (index 0 || index = size) - throw new IndexOutOfBoundsException(Index: + index + , Size: - + size); +throw new IndexOutOfBoundsException(Index: + index + +, Size: + size); } /** @@ -1018,8 +1017,30 @@ */ public int size() { - checkMod(); - return size; + synchronized (backingList) +{ + checkMod(); + return size; +} +} + +public void clear() +{ + synchronized (backingList) +{ + E[] snapshot = backingList.data; + E[] newData = (E[]) new Object[snapshot.length - size]; + + int toIndex = size + offset; + + System.arraycopy(snapshot, 0, newData, 0, offset); + System.arraycopy(snapshot, toIndex, newData, offset, + snapshot.length - toIndex); + + backingList.data = newData; + this.data = backingList.data; + this.size = 0; +} } /** @@ -1040,9 +1061,16 @@ */ public E set(int index, E o) { - checkMod(); - checkBoundsExclusive(index); - return
Re: [cp-patches] FYI: CopyOnWriteArrayList fixlets, part II
On 26/03/2008, Mario Torre [EMAIL PROTECTED] wrote: This should fix the last stuff. Maybe the Iterator returned by this subList needs some love too, but for now I'm happy. It passes all the tck public domain tests :) I've just pushed a mauve test also. Ciao, Mario 2008-03-26 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java (SubList.set): (SubList.clear): new method. (SubList.checkMod): fix indentation. (SubList.checkBoundsInclusive): likewise. (SubList.checkBoundsExclusive): likewise. (SubList): added synchronization. Now throw IndexOutOfBoundsException instead of IllegalArgumentException when index are out of range. (SubList.size): added synchronization. (SubList.get): likewise. (SubList.listIterator): fixed indentation. (SubList.set): added synchronization. Update the state of the storage after modification. (SubList.add): likewise. (SubList.remove): likewise. (SubList.addAll): likewise. -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ Looks good. Thanks. -- Andrew :-) Support Free Java! Contribute to GNU Classpath and the OpenJDK http://www.gnu.org/software/classpath http://openjdk.java.net PGP Key: 94EFD9D8 (http://subkeys.pgp.net) Fingerprint: F8EF F1EA 401E 2E60 15FA 7927 142C 2591 94EF D9D8
[cp-patches] FYI: CopyOnWriteArrayList fixlets, part II
This fixes the hashCode method to comply with the OpenJDK documentation. Now we pass all the public domain tck tests for this class, except the SubList one. Thanks, Mario 2008-03-26 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java (equals): removed useless local variable. (hashCode): new method. -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ ### Eclipse Workspace Patch 1.0 #P classpath Index: java/util/concurrent/CopyOnWriteArrayList.java === RCS file: /sources/classpath/classpath/java/util/concurrent/CopyOnWriteArrayList.java,v retrieving revision 1.7 diff -u -r1.7 CopyOnWriteArrayList.java --- java/util/concurrent/CopyOnWriteArrayList.java 25 Mar 2008 19:56:29 - 1.7 +++ java/util/concurrent/CopyOnWriteArrayList.java 26 Mar 2008 11:18:33 - @@ -705,8 +705,6 @@ if (this == o) return true; -boolean _equals = false; - // let's see if 'o' is a list, if so, we need to compare the elements // as returned by the iterator if (o instanceof List) @@ -723,10 +721,21 @@ return false; } -_equals = true; +return true; + } + +return false; + } + + public int hashCode() + { +// see http://java.sun.com/6/docs/api/java/util/List.html#hashcode() +int hashcode = 1; +for (E element : this) + { +hashcode = 31 * hashcode + (element == null ? 0 : element.hashCode()); } - -return _equals; +return hashcode; } /** Index: ChangeLog === RCS file: /sources/classpath/classpath/ChangeLog,v retrieving revision 1.9566 diff -u -r1.9566 ChangeLog --- ChangeLog 25 Mar 2008 19:56:30 - 1.9566 +++ ChangeLog 26 Mar 2008 11:18:33 - @@ -1,3 +1,9 @@ +2008-03-26 Mario Torre [EMAIL PROTECTED] + + * java/util/concurrent/CopyOnWriteArrayList.java (equals): removed useless + local variable. + (hashCode): new method. + 2008-03-25 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java (clone): clone method
Re: [cp-patches] FYI: CopyOnWriteArrayList fixlets, part II
On 26/03/2008, Mario Torre [EMAIL PROTECTED] wrote: This fixes the hashCode method to comply with the OpenJDK documentation. Now we pass all the public domain tck tests for this class, except the SubList one. Not sure what the failure is, but looking at the code I guess that the sublist should be acquiring the same lock that the main set, etc. methods do (i.e. on the list itself) for each operation so that the array is not modified behind its back. snip... Thanks, Mario Cheers, -- Andrew :-) Document Freedom Day - March 26th http://documentfreedom.org Support Free Java! Contribute to GNU Classpath and the OpenJDK http://www.gnu.org/software/classpath http://openjdk.java.net PGP Key: 94EFD9D8 (http://subkeys.pgp.net) Fingerprint: F8EF F1EA 401E 2E60 15FA 7927 142C 2591 94EF D9D8
Re: [cp-patches] FYI: CopyOnWriteArrayList fixlets, part II
On Wed, 2008-03-26 at 12:32 +, Andrew John Hughes wrote: Not sure what the failure is, but looking at the code I guess that the sublist should be acquiring the same lock that the main set, etc. methods do (i.e. on the list itself) for each operation so that the array is not modified behind its back. Yeah, exactly, I'm just adding the code for that. I'll post a patch in few minutes, so stay tuned :) Cheers, Mario -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/
[cp-patches] FYI: CopyOnWriteArrayList fixlets, part II
This should fix the last stuff. Maybe the Iterator returned by this subList needs some love too, but for now I'm happy. It passes all the tck public domain tests :) I've just pushed a mauve test also. Ciao, Mario 2008-03-26 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java (SubList.set): (SubList.clear): new method. (SubList.checkMod): fix indentation. (SubList.checkBoundsInclusive): likewise. (SubList.checkBoundsExclusive): likewise. (SubList): added synchronization. Now throw IndexOutOfBoundsException instead of IllegalArgumentException when index are out of range. (SubList.size): added synchronization. (SubList.get): likewise. (SubList.listIterator): fixed indentation. (SubList.set): added synchronization. Update the state of the storage after modification. (SubList.add): likewise. (SubList.remove): likewise. (SubList.addAll): likewise. -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ ### Eclipse Workspace Patch 1.0 #P classpath Index: java/util/concurrent/CopyOnWriteArrayList.java === RCS file: /sources/classpath/classpath/java/util/concurrent/CopyOnWriteArrayList.java,v retrieving revision 1.8 diff -u -r1.8 CopyOnWriteArrayList.java --- java/util/concurrent/CopyOnWriteArrayList.java 26 Mar 2008 11:23:40 - 1.8 +++ java/util/concurrent/CopyOnWriteArrayList.java 26 Mar 2008 16:03:15 - @@ -53,7 +53,6 @@ import java.util.ListIterator; import java.util.NoSuchElementException; import java.util.RandomAccess; -import java.util.concurrent.ConcurrentSkipListMap.Iter; /** * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is @@ -911,16 +910,16 @@ * @return a List backed by a subsection of this list * @throws IndexOutOfBoundsException if fromIndex lt; 0 * || toIndex gt; size() - * @throws IllegalArgumentException if fromIndex gt; toIndex + * @throws IndexOutOfBoundsException if fromIndex gt; toIndex * @see ConcurrentModificationException * @see RandomAccess */ - public ListE subList(int fromIndex, int toIndex) + public synchronized ListE subList(int fromIndex, int toIndex) { // This follows the specification of AbstractList, but is inconsistent // with the one in List. Don't you love Sun's inconsistencies? if (fromIndex toIndex) - throw new IllegalArgumentException(fromIndex ++ toIndex); + throw new IndexOutOfBoundsException(fromIndex ++ toIndex); if (fromIndex 0 || toIndex size()) throw new IndexOutOfBoundsException(); @@ -976,7 +975,7 @@ void checkMod() { if (data != backingList.data) - throw new ConcurrentModificationException(); +throw new ConcurrentModificationException(); } /** @@ -990,8 +989,8 @@ private void checkBoundsInclusive(int index) { if (index 0 || index size) - throw new IndexOutOfBoundsException(Index: + index + , Size: - + size); +throw new IndexOutOfBoundsException(Index: + index + +, Size: + size); } /** @@ -1005,8 +1004,8 @@ private void checkBoundsExclusive(int index) { if (index 0 || index = size) - throw new IndexOutOfBoundsException(Index: + index + , Size: - + size); +throw new IndexOutOfBoundsException(Index: + index + +, Size: + size); } /** @@ -1018,8 +1017,30 @@ */ public int size() { - checkMod(); - return size; + synchronized (backingList) +{ + checkMod(); + return size; +} +} + +public void clear() +{ + synchronized (backingList) +{ + E[] snapshot = backingList.data; + E[] newData = (E[]) new
[cp-patches] FYI: CopyOnWriteArrayList fixlets
This patch is the first of a series that I'm preparing about CopyOnWriteArrayList, my goal is to pass the public domain JCK on this class. 2008-03-25 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java (clone): clone method in CopyOnWriteArrayList should just do a shallow copy. Fixed. (equals): new method, override from base class. (toString): likewise. -- Mario Torre, Software Developer, http://www.jroller.com/neugens/ aicas Allerton Interworks Computer Automated Systems GmbH Haid-und-Neu-Straße 18 * D-76131 Karlsruhe * Germany http://www.aicas.com * Tel: +49-721-663 968-53 pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF USt-Id: DE216375633, Handelsregister HRB 109481, AG Mannheim Geschäftsführer: Dr. James J. Hunt Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/
[cp-patches] FYI: CopyOnWriteArrayList fixlets
I'm committing this one. It fixes few methods on CopyOnWriteArrayList and also improves performances in a couple of points (not much, to be honest). Mauve tests will follow shortly. Thanks, Mario 2007-11-23 Mario Torre [EMAIL PROTECTED] * java/util/concurrent/CopyOnWriteArrayList.java: Added javadoc. (serialVersionUID): new field. (iterator): new method, override from base class. (remove): likewise. (listIterator): likewise. (removeAll): likewise. (retainAll): likewise. (contains): fixed typo in javadoc. (addIfAbsent): added javadoc. (addAllAbsent): Rewrite to improve performance. Also add javadoc. -- Lima Software - http://www.limasoftware.net/ GNU Classpath Developer - http://www.classpath.org/ Fedora Ambassador - http://fedoraproject.org/wiki/MarioTorre Jabber: [EMAIL PROTECTED] pgp key: http://subkeys.pgp.net/ PGP Key ID: 80F240CF Fingerprint: BA39 9666 94EC 8B73 27FA FC7C 4086 63E3 80F2 40CF Please, support open standards: http://opendocumentfellowship.org/petition/ http://www.nosoftwarepatents.com/ ### Eclipse Workspace Patch 1.0 #P classpath Index: java/util/concurrent/CopyOnWriteArrayList.java === RCS file: /sources/classpath/classpath/java/util/concurrent/CopyOnWriteArrayList.java,v retrieving revision 1.3 diff -u -r1.3 CopyOnWriteArrayList.java --- java/util/concurrent/CopyOnWriteArrayList.java 31 Mar 2007 10:01:39 - 1.3 +++ java/util/concurrent/CopyOnWriteArrayList.java 23 Nov 2007 21:26:22 - @@ -46,13 +46,61 @@ import java.util.Collection; import java.util.Iterator; import java.util.List; +import java.util.ListIterator; import java.util.RandomAccess; -/** @since 1.5 */ +/** + * A thread-safe implementation of an ArrayList. A CopyOnWriteArrayList is + * as special ArrayList which performs copies of the underlying storage + * each time a write (coderemove/code, codeadd/code etc..) operation + * is performed.br / + * br / + * The update operation in this class run usually in codeO(n)/code or worse, + * but traversal operations are fast and efficient, especially when running in + * a multi-thread environment without the need to design complex synchronize + * mechanisms.br / + * br / + * codeIterator/codes in this class work on a snapshot of the backing store + * at the moment the iterator itself was created, hence the iterator will not + * reflect changes in the underlying storage. Thus, update operation on the + * codeIterator/codes are not supported, but as interferences from other + * threads are impossible, no codeConcurrentModificationException/code + * will be ever thrown from within the codeIterator/code. + * br /br / + * This class is especially useful when used with event handling, like the + * following code demonstrates:br / + * codepre + * + * CopyOnWriteArrayListEventListener listeners = + * new CopyOnWriteArrayListEventListener(); + * + * [...] + * + * for (final EventListener listener : listeners) + * { + * Runnable dispatcher = new Runnable() { + * public void run() + * { + * listener.preferenceChange(event); + * } + * }; + * + * Executor executor = Executors.newSingleThreadExecutor(); + * executor.execute(dispatcher); + * } + * /pre/code + * + * @since 1.5 + */ public class CopyOnWriteArrayListE extends AbstractListE implements ListE, RandomAccess, Cloneable, Serializable { /** + * + */ + private static final long serialVersionUID = 8673264195747942595L; + + /** * Where the data is stored. */ private transient E[] data; @@ -118,7 +166,7 @@ } /** - * Returns true iff element is in this ArrayList. + * Returns true if element is in this ArrayList. * * @param e * the element whose inclusion in the List is being tested @@ -359,6 +407,134 @@ } /** + * Remove the first occurrence, if any, of the given object from this list, + * returning codetrue/code if the object was removed, codefalse/code + * otherwise. + * + * @param element the object to be removed. + * @return true if element was removed, false otherwise. false means also that + * the underlying storage was unchanged after this operation concluded. + */ + public synchronized boolean remove(Object element) + { +E[] data = this.data; +E[] newData = (E[]) new Object[data.length - 1]; + +// search the element to remove while filling the backup array +// this way we can run this method in O(n) +int elementIndex = -1; +for (int i = 0; i this.data.length; i++) + { +if (equals(element, this.data[i])) + { +elementIndex = i; +break; + } + +if (i newData.length) + newData[i] = this.data[i]; + } + +if (elementIndex 0) + return false; + +System.arraycopy(this.data, elementIndex + 1,