Java/Threads/Collections Threads
Содержание
- 1 A multithreaded queue used for implementing producer-consumer style threading patterns
- 2 A work queue is used to coordinate work between a producer and a set of worker threads.
- 3 Communicate between threads using a Queue
- 4 Current set
- 5 Customized java.util.ArrayList: operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes.
- 6 Customized java.util.HashMap: operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes.
- 7 Customized java.util.TreeMap: operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes.
- 8 Java 1.5 (5.0) new feature: collection and thread
- 9 Java 1.5 (5.0) new features: PriorityQueue
- 10 Java Thread Performance: AtomicTest
- 11 Java Thread Performance: Collection Test
- 12 Return a value from a thread.
- 13 Rhyming Words
- 14 Safe collection operation
- 15 Safe list copy
- 16 Safe vector copy
- 17 Using a Thread-Local Variable
A multithreaded queue used for implementing producer-consumer style threading patterns
/*
* Funambol is a mobile platform developed by Funambol, Inc.
* Copyright (C) 2003 - 2007 Funambol, Inc.
*
* This program is free software; you can redistribute it and/or modify it under
* the terms of the GNU Affero General Public License version 3 as published by
* the Free Software Foundation with the addition of the following permission
* added to Section 15 as permitted in Section 7(a): FOR ANY PART OF THE COVERED
* WORK IN WHICH THE COPYRIGHT IS OWNED BY FUNAMBOL, FUNAMBOL DISCLAIMS THE
* WARRANTY OF NON INFRINGEMENT OF THIRD PARTY RIGHTS.
*
* This program is distributed in the hope that it will be useful, but WITHOUT
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
* FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
* details.
*
* You should have received a copy of the GNU Affero General Public License
* along with this program; if not, see http://www.gnu.org/licenses or write to
* the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
* MA 02110-1301 USA.
*
* You can contact Funambol, Inc. headquarters at 643 Bair Island Road, Suite
* 305, Redwood City, CA 94063, USA, or at email address info@funambol.ru.
*
* The interactive user interfaces in modified source and object code versions
* of this program must display Appropriate Legal Notices, as required under
* Section 5 of the GNU Affero General Public License version 3.
*
* In accordance with Section 7(b) of the GNU Affero General Public License
* version 3, these Appropriate Legal Notices must retain the display of the
* "Powered by Funambol" logo. If the display of the logo is not reasonably
* feasible for technical reasons, the Appropriate Legal Notices must display
* the words "Powered by Funambol".
*/
import java.util.Stack;
/**
* A multithreaded queue used for
* implementing producer-consumer style threading patterns.
* Multiple threads can wait for runnable objects being added
* to the queue while other threads add to the queue.
*/
public class Queue {
private Stack tasks = new Stack();
private long defaultTimeout = 100;
public Queue() {
}
/**
* Returns the current number of runnable objects in the queue
*/
public synchronized int size() {
return tasks.size();
}
/**
* adds a runnable object to the end of the queue.
* At least one thread will be notified.
*/
public synchronized void add(Object runnable) {
tasks.push(runnable);
notifyAll();
}
/**
* Removes the first runnable object from the queue, blocking until one is available.
*/
public synchronized Object remove() {
while (true) {
Object runnable = removeNoWait();
if ( runnable != null ) {
return runnable;
}
try {
wait( defaultTimeout );
}
catch (InterruptedException e) {
e.printStackTrace();
}
}
}
/**
* Removes the first runnable object from the queue without blocking.
* This method will return immediately with an item from the queue or null.
* @return the first runnable object removed from the queue or null if the
* queue is empty
*/
public synchronized Object removeNoWait() {
if ( ! tasks.empty() ) {
return tasks.pop();
} else {
return null;
}
}
}
A work queue is used to coordinate work between a producer and a set of worker threads.
import java.util.LinkedList;
public class Main {
public static void main(String[] argv) {
WorkQueue queue = new WorkQueue();
int numWorkers = 2;
Worker[] workers = new Worker[numWorkers];
for (int i = 0; i < workers.length; i++) {
workers[i] = new Worker(queue);
workers[i].start();
}
for (int i = 0; i < 100; i++) {
queue.addWork(i);
}
}
}
class WorkQueue {
LinkedList<Object> queue = new LinkedList<Object>();
public synchronized void addWork(Object o) {
queue.addLast(o);
notify();
}
public synchronized Object getWork() throws InterruptedException {
while (queue.isEmpty()) {
wait();
}
return queue.removeFirst();
}
}
class Worker extends Thread {
WorkQueue q;
Worker(WorkQueue q) {
this.q = q;
}
public void run() {
try {
while (true) {
Object x = q.getWork();
if (x == null) {
break;
}
System.out.println(x);
}
} catch (InterruptedException e) {
}
}
}
Communicate between threads using a Queue
import java.util.concurrent.BlockingQueue;
import java.util.concurrent.LinkedBlockingQueue;
class PrepareProduction implements Runnable {
BlockingQueue<String> queue;
PrepareProduction(BlockingQueue<String> q) {
queue = q;
}
public void run() {
String thisLine;
try {
queue.put("1");
queue.put("done");
} catch (Exception e) {
e.printStackTrace();
}
}
}
class DoProduction implements Runnable {
private final BlockingQueue<String> queue;
DoProduction(BlockingQueue<String> q) {
queue = q;
}
public void run() {
try {
String value = queue.take();
while (!value.equals("done")) {
value = queue.take();
System.out.println(value);
}
} catch (Exception e) {
System.out.println(Thread.currentThread().getName() + " "
+ e.getMessage());
}
}
}
public class Main {
public static void main(String[] args) throws Exception {
BlockingQueue<String> q = new LinkedBlockingQueue<String>();
Thread p1 = new Thread(new PrepareProduction(q));
Thread c1 = new Thread(new DoProduction(q));
p1.start();
c1.start();
p1.join();
c1.join();
}
}
Current set
/*
* Copyright Ben Meadowcroft 2006
* Version: $Revision: 1.1 $
* Date: $Date: 2006/02/24 22:24:46 $
*/
//com.agnotion.util.concurrent;
import java.util.Collection;
import java.util.Iterator;
import java.util.Set;
import java.util.concurrent.ConcurrentHashMap;
/**
* @author Ben Meadowcroft
*/
public class ConcurrentSet<Q> implements Set<Q>
{
/** Piggy back off a concurrent hash map to get "weekly consistent" iterators etc */
private ConcurrentHashMap<Q, Object> map = new ConcurrentHashMap<Q, Object>();
/**
*
*/
public ConcurrentSet() {
this.map = new ConcurrentHashMap<Q, Object>();
}
/* (non-Javadoc)
* @see java.util.Set#add(E)
*/
public boolean add(Q item) {
boolean containsObj = map.containsKey(item);
if (containsObj == false)
{
/* ConcurrentHashMap doesn"t allow null keys or values so we simply
* use the item added to the collection as the key and the Boolean
* TRUE object as the value. */
map.put(item, Boolean.TRUE);
}
return !containsObj;
}
/* (non-Javadoc)
* @see java.util.Set#addAll(java.util.Collection)
*/
public boolean addAll(Collection<? extends Q> items) {
boolean changed = false;
for (Q item : items)
{
/* update flag determining whether set has changed or not */
changed = add(item) || changed;
}
return changed;
}
/* (non-Javadoc)
* @see java.util.Set#clear()
*/
public void clear() {
map.clear();
}
/* (non-Javadoc)
* @see java.util.Set#contains(java.lang.Object)
*/
public boolean contains(Object item) {
return map.containsKey(item);
}
/* (non-Javadoc)
* @see java.util.Set#containsAll(java.util.Collection)
*/
public boolean containsAll(Collection<?> items) {
return map.keySet().containsAll(items);
}
/* (non-Javadoc)
* @see java.util.Set#isEmpty()
*/
public boolean isEmpty() {
return map.isEmpty();
}
/* (non-Javadoc)
* @see java.util.Set#iterator()
*/
public Iterator<Q> iterator() {
return map.keySet().iterator();
}
/* (non-Javadoc)
* @see java.util.Set#remove(java.lang.Object)
*/
public boolean remove(Object item) {
/* we double up argument as both key and value */
return map.remove(item, Boolean.TRUE);
}
/* (non-Javadoc)
* @see java.util.Set#removeAll(java.util.Collection)
*/
public boolean removeAll(Collection<?> items) {
return map.keySet().removeAll(items);
}
/* (non-Javadoc)
* @see java.util.Set#retainAll(java.util.Collection)
*/
public boolean retainAll(Collection<?> items) {
return map.keySet().retainAll(items);
}
/* (non-Javadoc)
* @see java.util.Set#size()
*/
public int size() {
return map.size();
}
/* (non-Javadoc)
* @see java.util.Set#toArray()
*/
public Object[] toArray() {
return map.keySet().toArray();
}
/* (non-Javadoc)
* @see java.util.Set#toArray(T[])
*/
public <T> T[] toArray(T[] array) {
return map.keySet().toArray(array);
}
}
Customized java.util.ArrayList: operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.ArrayList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
/**
* <p>A customized implementation of <code>java.util.ArrayList</code> designed
* to operate in a multithreaded environment where the large majority of
* method calls are read-only, instead of structural changes. When operating
* in "fast" mode, read calls are non-synchronized and write calls perform the
* following steps:</p>
* <ul>
* <li>Clone the existing collection
* <li>Perform the modification on the clone
* <li>Replace the existing collection with the (modified) clone
* </ul>
* <p>When first created, objects of this class default to "slow" mode, where
* all accesses of any type are synchronized but no cloning takes place. This
* is appropriate for initially populating the collection, followed by a switch
* to "fast" mode (by calling <code>setFast(true)</code>) after initialization
* is complete.</p>
*
* <p><strong>NOTE</strong>: If you are creating and accessing an
* <code>ArrayList</code> only within a single thread, you should use
* <code>java.util.ArrayList</code> directly (with no synchronization), for
* maximum performance.</p>
*
* <p><strong>NOTE</strong>: <i>This class is not cross-platform.
* Using it may cause unexpected failures on some architectures.</i>
* It suffers from the same problems as the double-checked locking idiom.
* In particular, the instruction that clones the internal collection and the
* instruction that sets the internal reference to the clone can be executed
* or perceived out-of-order. This means that any read operation might fail
* unexpectedly, as it may be reading the state of the internal collection
* before the internal collection is fully formed.
* For more information on the double-checked locking idiom, see the
* .</p>
*
* @since Commons Collections 1.0
* @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
*
* @author Craig R. McClanahan
* @author Stephen Colebourne
*/
public class FastArrayList extends ArrayList {
// ----------------------------------------------------------- Constructors
/**
* Construct a an empty list.
*/
public FastArrayList() {
super();
this.list = new ArrayList();
}
/**
* Construct an empty list with the specified capacity.
*
* @param capacity The initial capacity of the empty list
*/
public FastArrayList(int capacity) {
super();
this.list = new ArrayList(capacity);
}
/**
* Construct a list containing the elements of the specified collection,
* in the order they are returned by the collection"s iterator.
*
* @param collection The collection whose elements initialize the contents
* of this list
*/
public FastArrayList(Collection collection) {
super();
this.list = new ArrayList(collection);
}
// ----------------------------------------------------- Instance Variables
/**
* The underlying list we are managing.
*/
protected ArrayList list = null;
// ------------------------------------------------------------- Properties
/**
* Are we operating in "fast" mode?
*/
protected boolean fast = false;
/**
* Returns true if this list is operating in fast mode.
*
* @return true if this list is operating in fast mode
*/
public boolean getFast() {
return (this.fast);
}
/**
* Sets whether this list will operate in fast mode.
*
* @param fast true if the list should operate in fast mode
*/
public void setFast(boolean fast) {
this.fast = fast;
}
// --------------------------------------------------------- Public Methods
/**
* Appends the specified element to the end of this list.
*
* @param element The element to be appended
*/
public boolean add(Object element) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
boolean result = temp.add(element);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.add(element));
}
}
}
/**
* Insert the specified element at the specified position in this list,
* and shift all remaining elements up one position.
*
* @param index Index at which to insert this element
* @param element The element to be inserted
*
* @exception IndexOutOfBoundsException if the index is out of range
*/
public void add(int index, Object element) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
temp.add(index, element);
list = temp;
}
} else {
synchronized (list) {
list.add(index, element);
}
}
}
/**
* Append 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 collection The collection to be appended
*/
public boolean addAll(Collection collection) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
boolean result = temp.addAll(collection);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.addAll(collection));
}
}
}
/**
* Insert all of the elements in the specified Collection at the specified
* position in this list, and shift any previous elements upwards as
* needed.
*
* @param index Index at which insertion takes place
* @param collection The collection to be added
*
* @exception IndexOutOfBoundsException if the index is out of range
*/
public boolean addAll(int index, Collection collection) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
boolean result = temp.addAll(index, collection);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.addAll(index, collection));
}
}
}
/**
* Remove all of the elements from this list. The list will be empty
* after this call returns.
*
* @exception UnsupportedOperationException if <code>clear()</code>
* is not supported by this list
*/
public void clear() {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
temp.clear();
list = temp;
}
} else {
synchronized (list) {
list.clear();
}
}
}
/**
* Return a shallow copy of this <code>FastArrayList</code> instance.
* The elements themselves are not copied.
*/
public Object clone() {
FastArrayList results = null;
if (fast) {
results = new FastArrayList(list);
} else {
synchronized (list) {
results = new FastArrayList(list);
}
}
results.setFast(getFast());
return (results);
}
/**
* Return <code>true</code> if this list contains the specified element.
*
* @param element The element to test for
*/
public boolean contains(Object element) {
if (fast) {
return (list.contains(element));
} else {
synchronized (list) {
return (list.contains(element));
}
}
}
/**
* Return <code>true</code> if this list contains all of the elements
* in the specified Collection.
*
* @param collection Collection whose elements are to be checked
*/
public boolean containsAll(Collection collection) {
if (fast) {
return (list.containsAll(collection));
} else {
synchronized (list) {
return (list.containsAll(collection));
}
}
}
/**
* Increase the capacity of this <code>ArrayList</code> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param capacity The new minimum capacity
*/
public void ensureCapacity(int capacity) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
temp.ensureCapacity(capacity);
list = temp;
}
} else {
synchronized (list) {
list.ensureCapacity(capacity);
}
}
}
/**
* Compare the specified object with this list for equality. This
* implementation uses exactly the code that is used to define the
* list equals function in the documentation for the
* <code>List.equals</code> method.
*
* @param o Object to be compared to this list
*/
public boolean equals(Object o) {
// Simple tests that require no synchronization
if (o == this)
return (true);
else if (!(o instanceof List))
return (false);
List lo = (List) o;
// Compare the sets of elements for equality
if (fast) {
ListIterator li1 = list.listIterator();
ListIterator li2 = lo.listIterator();
while (li1.hasNext() && li2.hasNext()) {
Object o1 = li1.next();
Object o2 = li2.next();
if (!(o1 == null ? o2 == null : o1.equals(o2)))
return (false);
}
return (!(li1.hasNext() || li2.hasNext()));
} else {
synchronized (list) {
ListIterator li1 = list.listIterator();
ListIterator li2 = lo.listIterator();
while (li1.hasNext() && li2.hasNext()) {
Object o1 = li1.next();
Object o2 = li2.next();
if (!(o1 == null ? o2 == null : o1.equals(o2)))
return (false);
}
return (!(li1.hasNext() || li2.hasNext()));
}
}
}
/**
* Return the element at the specified position in the list.
*
* @param index The index of the element to return
*
* @exception IndexOutOfBoundsException if the index is out of range
*/
public Object get(int index) {
if (fast) {
return (list.get(index));
} else {
synchronized (list) {
return (list.get(index));
}
}
}
/**
* Return the hash code value for this list. This implementation uses
* exactly the code that is used to define the list hash function in the
* documentation for the <code>List.hashCode</code> method.
*/
public int hashCode() {
if (fast) {
int hashCode = 1;
java.util.Iterator i = list.iterator();
while (i.hasNext()) {
Object o = i.next();
hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
}
return (hashCode);
} else {
synchronized (list) {
int hashCode = 1;
java.util.Iterator i = list.iterator();
while (i.hasNext()) {
Object o = i.next();
hashCode = 31 * hashCode + (o == null ? 0 : o.hashCode());
}
return (hashCode);
}
}
}
/**
* Search for the first occurrence of the given argument, testing
* for equality using the <code>equals()</code> method, and return
* the corresponding index, or -1 if the object is not found.
*
* @param element The element to search for
*/
public int indexOf(Object element) {
if (fast) {
return (list.indexOf(element));
} else {
synchronized (list) {
return (list.indexOf(element));
}
}
}
/**
* Test if this list has no elements.
*/
public boolean isEmpty() {
if (fast) {
return (list.isEmpty());
} else {
synchronized (list) {
return (list.isEmpty());
}
}
}
/**
* Return an iterator over the elements in this list in proper sequence.
* <p>
* <b>Thread safety</b><br />
* The iterator returned is thread-safe ONLY in FAST mode.
* In slow mode there is no way to synchronize, or make the iterator thread-safe.
* <p>
* In fast mode iteration and modification may occur in parallel on different threads,
* however there is a restriction. Modification must be EITHER via the Iterator
* interface methods OR the List interface. If a mixture of modification
* methods is used a ConcurrentModificationException is thrown from the iterator
* modification method. If the List modification methods are used the changes are
* NOT visible in the iterator (it shows the list contents at the time the iterator
* was created).
*
* @return the iterator
*/
public Iterator iterator() {
if (fast) {
return new ListIter(0);
} else {
return list.iterator();
}
}
/**
* Search for the last occurrence of the given argument, testing
* for equality using the <code>equals()</code> method, and return
* the corresponding index, or -1 if the object is not found.
*
* @param element The element to search for
*/
public int lastIndexOf(Object element) {
if (fast) {
return (list.lastIndexOf(element));
} else {
synchronized (list) {
return (list.lastIndexOf(element));
}
}
}
/**
* Return an iterator of the elements of this list, in proper sequence.
* <p>
* <b>Thread safety</b><br />
* The iterator returned is thread-safe ONLY in FAST mode.
* In slow mode there is no way to synchronize, or make the iterator thread-safe.
* <p>
* In fast mode iteration and modification may occur in parallel on different threads,
* however there is a restriction. Modification must be EITHER via the Iterator
* interface methods OR the List interface. If a mixture of modification
* methods is used a ConcurrentModificationException is thrown from the iterator
* modification method. If the List modification methods are used the changes are
* NOT visible in the iterator (it shows the list contents at the time the iterator
* was created).
*
* @return the list iterator
*/
public ListIterator listIterator() {
if (fast) {
return new ListIter(0);
} else {
return list.listIterator();
}
}
/**
* Return an iterator of the elements of this list, in proper sequence,
* starting at the specified position.
* <p>
* <b>Thread safety</b><br />
* The iterator returned is thread-safe ONLY in FAST mode.
* In slow mode there is no way to synchronize, or make the iterator thread-safe.
* <p>
* In fast mode iteration and modification may occur in parallel on different threads,
* however there is a restriction. Modification must be EITHER via the Iterator
* interface methods OR the List interface. If a mixture of modification
* methods is used a ConcurrentModificationException is thrown from the iterator
* modification method. If the List modification methods are used the changes are
* NOT visible in the iterator (it shows the list contents at the time the iterator
* was created).
*
* @param index The starting position of the iterator to return
* @return the list iterator
* @exception IndexOutOfBoundsException if the index is out of range
*/
public ListIterator listIterator(int index) {
if (fast) {
return new ListIter(index);
} else {
return list.listIterator(index);
}
}
/**
* Remove the element at the specified position in the list, and shift
* any subsequent elements down one position.
*
* @param index Index of the element to be removed
*
* @exception IndexOutOfBoundsException if the index is out of range
*/
public Object remove(int index) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
Object result = temp.remove(index);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.remove(index));
}
}
}
/**
* Remove the first occurrence of the specified element from the list,
* and shift any subsequent elements down one position.
*
* @param element Element to be removed
*/
public boolean remove(Object element) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
boolean result = temp.remove(element);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.remove(element));
}
}
}
/**
* Remove from this collection all of its elements that are contained
* in the specified collection.
*
* @param collection Collection containing elements to be removed
*
* @exception UnsupportedOperationException if this optional operation
* is not supported by this list
*/
public boolean removeAll(Collection collection) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
boolean result = temp.removeAll(collection);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.removeAll(collection));
}
}
}
/**
* Remove from this collection all of its elements except those that are
* contained in the specified collection.
*
* @param collection Collection containing elements to be retained
*
* @exception UnsupportedOperationException if this optional operation
* is not supported by this list
*/
public boolean retainAll(Collection collection) {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
boolean result = temp.retainAll(collection);
list = temp;
return (result);
}
} else {
synchronized (list) {
return (list.retainAll(collection));
}
}
}
/**
* Replace the element at the specified position in this list with
* the specified element. Returns the previous object at that position.
* <br><br>
* <strong>IMPLEMENTATION NOTE</strong> - This operation is specifically
* documented to not be a structural change, so it is safe to be performed
* without cloning.
*
* @param index Index of the element to replace
* @param element The new element to be stored
*
* @exception IndexOutOfBoundsException if the index is out of range
*/
public Object set(int index, Object element) {
if (fast) {
return (list.set(index, element));
} else {
synchronized (list) {
return (list.set(index, element));
}
}
}
/**
* Return the number of elements in this list.
*/
public int size() {
if (fast) {
return (list.size());
} else {
synchronized (list) {
return (list.size());
}
}
}
/**
* Return a view of the portion of this list between fromIndex
* (inclusive) and toIndex (exclusive). The returned list is backed
* by this list, so non-structural changes in the returned list are
* reflected in this list. The returned list supports
* all of the optional list operations supported by this list.
*
* @param fromIndex The starting index of the sublist view
* @param toIndex The index after the end of the sublist view
*
* @exception IndexOutOfBoundsException if an index is out of range
*/
public List subList(int fromIndex, int toIndex) {
if (fast) {
return new SubList(fromIndex, toIndex);
} else {
return list.subList(fromIndex, toIndex);
}
}
/**
* Return an array containing all of the elements in this list in the
* correct order.
*/
public Object[] toArray() {
if (fast) {
return (list.toArray());
} else {
synchronized (list) {
return (list.toArray());
}
}
}
/**
* Return 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.
*
* @param array Array defining the element type of the returned list
*
* @exception ArrayStoreException if the runtime type of <code>array</code>
* is not a supertype of the runtime type of every element in this list
*/
public Object[] toArray(Object array[]) {
if (fast) {
return (list.toArray(array));
} else {
synchronized (list) {
return (list.toArray(array));
}
}
}
/**
* Return a String representation of this object.
*/
public String toString() {
StringBuffer sb = new StringBuffer("FastArrayList[");
sb.append(list.toString());
sb.append("]");
return (sb.toString());
}
/**
* Trim the capacity of this <code>ArrayList</code> instance to be the
* list"s current size. An application can use this operation to minimize
* the storage of an <code>ArrayList</code> instance.
*/
public void trimToSize() {
if (fast) {
synchronized (this) {
ArrayList temp = (ArrayList) list.clone();
temp.trimToSize();
list = temp;
}
} else {
synchronized (list) {
list.trimToSize();
}
}
}
private class SubList implements List {
private int first;
private int last;
private List expected;
public SubList(int first, int last) {
this.first = first;
this.last = last;
this.expected = list;
}
private List get(List l) {
if (list != expected) {
throw new ConcurrentModificationException();
}
return l.subList(first, last);
}
public void clear() {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
get(temp).clear();
last = first;
list = temp;
expected = temp;
}
} else {
synchronized (list) {
get(expected).clear();
}
}
}
public boolean remove(Object o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
boolean r = get(temp).remove(o);
if (r) last--;
list = temp;
expected = temp;
return r;
}
} else {
synchronized (list) {
return get(expected).remove(o);
}
}
}
public boolean removeAll(Collection o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
List sub = get(temp);
boolean r = sub.removeAll(o);
if (r) last = first + sub.size();
list = temp;
expected = temp;
return r;
}
} else {
synchronized (list) {
return get(expected).removeAll(o);
}
}
}
public boolean retainAll(Collection o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
List sub = get(temp);
boolean r = sub.retainAll(o);
if (r) last = first + sub.size();
list = temp;
expected = temp;
return r;
}
} else {
synchronized (list) {
return get(expected).retainAll(o);
}
}
}
public int size() {
if (fast) {
return get(expected).size();
} else {
synchronized (list) {
return get(expected).size();
}
}
}
public boolean isEmpty() {
if (fast) {
return get(expected).isEmpty();
} else {
synchronized (list) {
return get(expected).isEmpty();
}
}
}
public boolean contains(Object o) {
if (fast) {
return get(expected).contains(o);
} else {
synchronized (list) {
return get(expected).contains(o);
}
}
}
public boolean containsAll(Collection o) {
if (fast) {
return get(expected).containsAll(o);
} else {
synchronized (list) {
return get(expected).containsAll(o);
}
}
}
public Object[] toArray(Object[] o) {
if (fast) {
return get(expected).toArray(o);
} else {
synchronized (list) {
return get(expected).toArray(o);
}
}
}
public Object[] toArray() {
if (fast) {
return get(expected).toArray();
} else {
synchronized (list) {
return get(expected).toArray();
}
}
}
public boolean equals(Object o) {
if (o == this) return true;
if (fast) {
return get(expected).equals(o);
} else {
synchronized (list) {
return get(expected).equals(o);
}
}
}
public int hashCode() {
if (fast) {
return get(expected).hashCode();
} else {
synchronized (list) {
return get(expected).hashCode();
}
}
}
public boolean add(Object o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
boolean r = get(temp).add(o);
if (r) last++;
list = temp;
expected = temp;
return r;
}
} else {
synchronized (list) {
return get(expected).add(o);
}
}
}
public boolean addAll(Collection o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
boolean r = get(temp).addAll(o);
if (r) last += o.size();
list = temp;
expected = temp;
return r;
}
} else {
synchronized (list) {
return get(expected).addAll(o);
}
}
}
public void add(int i, Object o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
get(temp).add(i, o);
last++;
list = temp;
expected = temp;
}
} else {
synchronized (list) {
get(expected).add(i, o);
}
}
}
public boolean addAll(int i, Collection o) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
boolean r = get(temp).addAll(i, o);
list = temp;
if (r) last += o.size();
expected = temp;
return r;
}
} else {
synchronized (list) {
return get(expected).addAll(i, o);
}
}
}
public Object remove(int i) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
Object o = get(temp).remove(i);
last--;
list = temp;
expected = temp;
return o;
}
} else {
synchronized (list) {
return get(expected).remove(i);
}
}
}
public Object set(int i, Object a) {
if (fast) {
synchronized (FastArrayList.this) {
ArrayList temp = (ArrayList) list.clone();
Object o = get(temp).set(i, a);
list = temp;
expected = temp;
return o;
}
} else {
synchronized (list) {
return get(expected).set(i, a);
}
}
}
public Iterator iterator() {
return new SubListIter(0);
}
public ListIterator listIterator() {
return new SubListIter(0);
}
public ListIterator listIterator(int i) {
return new SubListIter(i);
}
public Object get(int i) {
if (fast) {
return get(expected).get(i);
} else {
synchronized (list) {
return get(expected).get(i);
}
}
}
public int indexOf(Object o) {
if (fast) {
return get(expected).indexOf(o);
} else {
synchronized (list) {
return get(expected).indexOf(o);
}
}
}
public int lastIndexOf(Object o) {
if (fast) {
return get(expected).lastIndexOf(o);
} else {
synchronized (list) {
return get(expected).lastIndexOf(o);
}
}
}
public List subList(int f, int l) {
if (list != expected) {
throw new ConcurrentModificationException();
}
return new SubList(first + f, f + l);
}
private class SubListIter implements ListIterator {
private List expected;
private ListIterator iter;
private int lastReturnedIndex = -1;
public SubListIter(int i) {
this.expected = list;
this.iter = SubList.this.get(expected).listIterator(i);
}
private void checkMod() {
if (list != expected) {
throw new ConcurrentModificationException();
}
}
List get() {
return SubList.this.get(expected);
}
public boolean hasNext() {
checkMod();
return iter.hasNext();
}
public Object next() {
checkMod();
lastReturnedIndex = iter.nextIndex();
return iter.next();
}
public boolean hasPrevious() {
checkMod();
return iter.hasPrevious();
}
public Object previous() {
checkMod();
lastReturnedIndex = iter.previousIndex();
return iter.previous();
}
public int previousIndex() {
checkMod();
return iter.previousIndex();
}
public int nextIndex() {
checkMod();
return iter.nextIndex();
}
public void remove() {
checkMod();
if (lastReturnedIndex < 0) {
throw new IllegalStateException();
}
get().remove(lastReturnedIndex);
last--;
expected = list;
iter = get().listIterator(lastReturnedIndex);
lastReturnedIndex = -1;
}
public void set(Object o) {
checkMod();
if (lastReturnedIndex < 0) {
throw new IllegalStateException();
}
get().set(lastReturnedIndex, o);
expected = list;
iter = get().listIterator(previousIndex() + 1);
}
public void add(Object o) {
checkMod();
int i = nextIndex();
get().add(i, o);
last++;
expected = list;
iter = get().listIterator(i + 1);
lastReturnedIndex = -1;
}
}
}
private class ListIter implements ListIterator {
private List expected;
private ListIterator iter;
private int lastReturnedIndex = -1;
public ListIter(int i) {
this.expected = list;
this.iter = get().listIterator(i);
}
private void checkMod() {
if (list != expected) {
throw new ConcurrentModificationException();
}
}
List get() {
return expected;
}
public boolean hasNext() {
return iter.hasNext();
}
public Object next() {
lastReturnedIndex = iter.nextIndex();
return iter.next();
}
public boolean hasPrevious() {
return iter.hasPrevious();
}
public Object previous() {
lastReturnedIndex = iter.previousIndex();
return iter.previous();
}
public int previousIndex() {
return iter.previousIndex();
}
public int nextIndex() {
return iter.nextIndex();
}
public void remove() {
checkMod();
if (lastReturnedIndex < 0) {
throw new IllegalStateException();
}
get().remove(lastReturnedIndex);
expected = list;
iter = get().listIterator(lastReturnedIndex);
lastReturnedIndex = -1;
}
public void set(Object o) {
checkMod();
if (lastReturnedIndex < 0) {
throw new IllegalStateException();
}
get().set(lastReturnedIndex, o);
expected = list;
iter = get().listIterator(previousIndex() + 1);
}
public void add(Object o) {
checkMod();
int i = nextIndex();
get().add(i, o);
expected = list;
iter = get().listIterator(i + 1);
lastReturnedIndex = -1;
}
}
}
Customized java.util.HashMap: operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
/**
* <p>A customized implementation of <code>java.util.HashMap</code> designed
* to operate in a multithreaded environment where the large majority of
* method calls are read-only, instead of structural changes. When operating
* in "fast" mode, read calls are non-synchronized and write calls perform the
* following steps:</p>
* <ul>
* <li>Clone the existing collection
* <li>Perform the modification on the clone
* <li>Replace the existing collection with the (modified) clone
* </ul>
* <p>When first created, objects of this class default to "slow" mode, where
* all accesses of any type are synchronized but no cloning takes place. This
* is appropriate for initially populating the collection, followed by a switch
* to "fast" mode (by calling <code>setFast(true)</code>) after initialization
* is complete.</p>
*
* <p><strong>NOTE</strong>: If you are creating and accessing a
* <code>HashMap</code> only within a single thread, you should use
* <code>java.util.HashMap</code> directly (with no synchronization), for
* maximum performance.</p>
*
* <p><strong>NOTE</strong>: <i>This class is not cross-platform.
* Using it may cause unexpected failures on some architectures.</i>
* It suffers from the same problems as the double-checked locking idiom.
* In particular, the instruction that clones the internal collection and the
* instruction that sets the internal reference to the clone can be executed
* or perceived out-of-order. This means that any read operation might fail
* unexpectedly, as it may be reading the state of the internal collection
* before the internal collection is fully formed.
* For more information on the double-checked locking idiom, see the
* .</p>
*
* @since Commons Collections 1.0
* @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
*
* @author Craig R. McClanahan
* @author Stephen Colebourne
*/
public class FastHashMap extends HashMap {
/**
* The underlying map we are managing.
*/
protected HashMap map = null;
/**
* Are we currently operating in "fast" mode?
*/
protected boolean fast = false;
// Constructors
// ----------------------------------------------------------------------
/**
* Construct an empty map.
*/
public FastHashMap() {
super();
this.map = new HashMap();
}
/**
* Construct an empty map with the specified capacity.
*
* @param capacity the initial capacity of the empty map
*/
public FastHashMap(int capacity) {
super();
this.map = new HashMap(capacity);
}
/**
* Construct an empty map with the specified capacity and load factor.
*
* @param capacity the initial capacity of the empty map
* @param factor the load factor of the new map
*/
public FastHashMap(int capacity, float factor) {
super();
this.map = new HashMap(capacity, factor);
}
/**
* Construct a new map with the same mappings as the specified map.
*
* @param map the map whose mappings are to be copied
*/
public FastHashMap(Map map) {
super();
this.map = new HashMap(map);
}
// Property access
// ----------------------------------------------------------------------
/**
* Returns true if this map is operating in fast mode.
*
* @return true if this map is operating in fast mode
*/
public boolean getFast() {
return (this.fast);
}
/**
* Sets whether this map is operating in fast mode.
*
* @param fast true if this map should operate in fast mode
*/
public void setFast(boolean fast) {
this.fast = fast;
}
// Map access
// ----------------------------------------------------------------------
// These methods can forward straight to the wrapped Map in "fast" mode.
// (because they are query methods)
/**
* Return the value to which this map maps the specified key. Returns
* <code>null</code> if the map contains no mapping for this key, or if
* there is a mapping with a value of <code>null</code>. Use the
* <code>containsKey()</code> method to disambiguate these cases.
*
* @param key the key whose value is to be returned
* @return the value mapped to that key, or null
*/
public Object get(Object key) {
if (fast) {
return (map.get(key));
} else {
synchronized (map) {
return (map.get(key));
}
}
}
/**
* Return the number of key-value mappings in this map.
*
* @return the current size of the map
*/
public int size() {
if (fast) {
return (map.size());
} else {
synchronized (map) {
return (map.size());
}
}
}
/**
* Return <code>true</code> if this map contains no mappings.
*
* @return is the map currently empty
*/
public boolean isEmpty() {
if (fast) {
return (map.isEmpty());
} else {
synchronized (map) {
return (map.isEmpty());
}
}
}
/**
* Return <code>true</code> if this map contains a mapping for the
* specified key.
*
* @param key the key to be searched for
* @return true if the map contains the key
*/
public boolean containsKey(Object key) {
if (fast) {
return (map.containsKey(key));
} else {
synchronized (map) {
return (map.containsKey(key));
}
}
}
/**
* Return <code>true</code> if this map contains one or more keys mapping
* to the specified value.
*
* @param value the value to be searched for
* @return true if the map contains the value
*/
public boolean containsValue(Object value) {
if (fast) {
return (map.containsValue(value));
} else {
synchronized (map) {
return (map.containsValue(value));
}
}
}
// Map modification
// ----------------------------------------------------------------------
// These methods perform special behaviour in "fast" mode.
// The map is cloned, updated and then assigned back.
// See the comments at the top as to why this won"t always work.
/**
* Associate the specified value with the specified key in this map.
* If the map previously contained a mapping for this key, the old
* value is replaced and returned.
*
* @param key the key with which the value is to be associated
* @param value the value to be associated with this key
* @return the value previously mapped to the key, or null
*/
public Object put(Object key, Object value) {
if (fast) {
synchronized (this) {
HashMap temp = (HashMap) map.clone();
Object result = temp.put(key, value);
map = temp;
return (result);
}
} else {
synchronized (map) {
return (map.put(key, value));
}
}
}
/**
* Copy all of the mappings from the specified map to this one, replacing
* any mappings with the same keys.
*
* @param in the map whose mappings are to be copied
*/
public void putAll(Map in) {
if (fast) {
synchronized (this) {
HashMap temp = (HashMap) map.clone();
temp.putAll(in);
map = temp;
}
} else {
synchronized (map) {
map.putAll(in);
}
}
}
/**
* Remove any mapping for this key, and return any previously
* mapped value.
*
* @param key the key whose mapping is to be removed
* @return the value removed, or null
*/
public Object remove(Object key) {
if (fast) {
synchronized (this) {
HashMap temp = (HashMap) map.clone();
Object result = temp.remove(key);
map = temp;
return (result);
}
} else {
synchronized (map) {
return (map.remove(key));
}
}
}
/**
* Remove all mappings from this map.
*/
public void clear() {
if (fast) {
synchronized (this) {
map = new HashMap();
}
} else {
synchronized (map) {
map.clear();
}
}
}
// Basic object methods
// ----------------------------------------------------------------------
/**
* Compare the specified object with this list for equality. This
* implementation uses exactly the code that is used to define the
* list equals function in the documentation for the
* <code>Map.equals</code> method.
*
* @param o the object to be compared to this list
* @return true if the two maps are equal
*/
public boolean equals(Object o) {
// Simple tests that require no synchronization
if (o == this) {
return (true);
} else if (!(o instanceof Map)) {
return (false);
}
Map mo = (Map) o;
// Compare the two maps for equality
if (fast) {
if (mo.size() != map.size()) {
return (false);
}
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
Object key = e.getKey();
Object value = e.getValue();
if (value == null) {
if (!(mo.get(key) == null && mo.containsKey(key))) {
return (false);
}
} else {
if (!value.equals(mo.get(key))) {
return (false);
}
}
}
return (true);
} else {
synchronized (map) {
if (mo.size() != map.size()) {
return (false);
}
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
Object key = e.getKey();
Object value = e.getValue();
if (value == null) {
if (!(mo.get(key) == null && mo.containsKey(key))) {
return (false);
}
} else {
if (!value.equals(mo.get(key))) {
return (false);
}
}
}
return (true);
}
}
}
/**
* Return the hash code value for this map. This implementation uses
* exactly the code that is used to define the list hash function in the
* documentation for the <code>Map.hashCode</code> method.
*
* @return suitable integer hash code
*/
public int hashCode() {
if (fast) {
int h = 0;
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
h += i.next().hashCode();
}
return (h);
} else {
synchronized (map) {
int h = 0;
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
h += i.next().hashCode();
}
return (h);
}
}
}
/**
* Return a shallow copy of this <code>FastHashMap</code> instance.
* The keys and values themselves are not copied.
*
* @return a clone of this map
*/
public Object clone() {
FastHashMap results = null;
if (fast) {
results = new FastHashMap(map);
} else {
synchronized (map) {
results = new FastHashMap(map);
}
}
results.setFast(getFast());
return (results);
}
// Map views
// ----------------------------------------------------------------------
/**
* Return a collection view of the mappings contained in this map. Each
* element in the returned collection is a <code>Map.Entry</code>.
*/
public Set entrySet() {
return new EntrySet();
}
/**
* Return a set view of the keys contained in this map.
*/
public Set keySet() {
return new KeySet();
}
/**
* Return a collection view of the values contained in this map.
*/
public Collection values() {
return new Values();
}
// Map view inner classes
// ----------------------------------------------------------------------
/**
* Abstract collection implementation shared by keySet(), values() and entrySet().
*/
private abstract class CollectionView implements Collection {
public CollectionView() {
}
protected abstract Collection get(Map map);
protected abstract Object iteratorNext(Map.Entry entry);
public void clear() {
if (fast) {
synchronized (FastHashMap.this) {
map = new HashMap();
}
} else {
synchronized (map) {
get(map).clear();
}
}
}
public boolean remove(Object o) {
if (fast) {
synchronized (FastHashMap.this) {
HashMap temp = (HashMap) map.clone();
boolean r = get(temp).remove(o);
map = temp;
return r;
}
} else {
synchronized (map) {
return get(map).remove(o);
}
}
}
public boolean removeAll(Collection o) {
if (fast) {
synchronized (FastHashMap.this) {
HashMap temp = (HashMap) map.clone();
boolean r = get(temp).removeAll(o);
map = temp;
return r;
}
} else {
synchronized (map) {
return get(map).removeAll(o);
}
}
}
public boolean retainAll(Collection o) {
if (fast) {
synchronized (FastHashMap.this) {
HashMap temp = (HashMap) map.clone();
boolean r = get(temp).retainAll(o);
map = temp;
return r;
}
} else {
synchronized (map) {
return get(map).retainAll(o);
}
}
}
public int size() {
if (fast) {
return get(map).size();
} else {
synchronized (map) {
return get(map).size();
}
}
}
public boolean isEmpty() {
if (fast) {
return get(map).isEmpty();
} else {
synchronized (map) {
return get(map).isEmpty();
}
}
}
public boolean contains(Object o) {
if (fast) {
return get(map).contains(o);
} else {
synchronized (map) {
return get(map).contains(o);
}
}
}
public boolean containsAll(Collection o) {
if (fast) {
return get(map).containsAll(o);
} else {
synchronized (map) {
return get(map).containsAll(o);
}
}
}
public Object[] toArray(Object[] o) {
if (fast) {
return get(map).toArray(o);
} else {
synchronized (map) {
return get(map).toArray(o);
}
}
}
public Object[] toArray() {
if (fast) {
return get(map).toArray();
} else {
synchronized (map) {
return get(map).toArray();
}
}
}
public boolean equals(Object o) {
if (o == this) return true;
if (fast) {
return get(map).equals(o);
} else {
synchronized (map) {
return get(map).equals(o);
}
}
}
public int hashCode() {
if (fast) {
return get(map).hashCode();
} else {
synchronized (map) {
return get(map).hashCode();
}
}
}
public boolean add(Object o) {
throw new UnsupportedOperationException();
}
public boolean addAll(Collection c) {
throw new UnsupportedOperationException();
}
public Iterator iterator() {
return new CollectionViewIterator();
}
private class CollectionViewIterator implements Iterator {
private Map expected;
private Map.Entry lastReturned = null;
private Iterator iterator;
public CollectionViewIterator() {
this.expected = map;
this.iterator = expected.entrySet().iterator();
}
public boolean hasNext() {
if (expected != map) {
throw new ConcurrentModificationException();
}
return iterator.hasNext();
}
public Object next() {
if (expected != map) {
throw new ConcurrentModificationException();
}
lastReturned = (Map.Entry)iterator.next();
return iteratorNext(lastReturned);
}
public void remove() {
if (lastReturned == null) {
throw new IllegalStateException();
}
if (fast) {
synchronized (FastHashMap.this) {
if (expected != map) {
throw new ConcurrentModificationException();
}
FastHashMap.this.remove(lastReturned.getKey());
lastReturned = null;
expected = map;
}
} else {
iterator.remove();
lastReturned = null;
}
}
}
}
/**
* Set implementation over the keys of the FastHashMap
*/
private class KeySet extends CollectionView implements Set {
protected Collection get(Map map) {
return map.keySet();
}
protected Object iteratorNext(Map.Entry entry) {
return entry.getKey();
}
}
/**
* Collection implementation over the values of the FastHashMap
*/
private class Values extends CollectionView {
protected Collection get(Map map) {
return map.values();
}
protected Object iteratorNext(Map.Entry entry) {
return entry.getValue();
}
}
/**
* Set implementation over the entries of the FastHashMap
*/
private class EntrySet extends CollectionView implements Set {
protected Collection get(Map map) {
return map.entrySet();
}
protected Object iteratorNext(Map.Entry entry) {
return entry;
}
}
}
Customized java.util.TreeMap: operate in a multithreaded environment where the large majority of method calls are read-only, instead of structural changes.
/*
* Licensed to the Apache Software Foundation (ASF) under one or more
* contributor license agreements. See the NOTICE file distributed with
* this work for additional information regarding copyright ownership.
* The ASF licenses this file to You under the Apache License, Version 2.0
* (the "License"); you may not use this file except in compliance with
* the License. You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
import java.util.Collection;
import java.util.ruparator;
import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.Map;
import java.util.Set;
import java.util.SortedMap;
import java.util.TreeMap;
/**
* <p>A customized implementation of <code>java.util.TreeMap</code> designed
* to operate in a multithreaded environment where the large majority of
* method calls are read-only, instead of structural changes. When operating
* in "fast" mode, read calls are non-synchronized and write calls perform the
* following steps:</p>
* <ul>
* <li>Clone the existing collection
* <li>Perform the modification on the clone
* <li>Replace the existing collection with the (modified) clone
* </ul>
* <p>When first created, objects of this class default to "slow" mode, where
* all accesses of any type are synchronized but no cloning takes place. This
* is appropriate for initially populating the collection, followed by a switch
* to "fast" mode (by calling <code>setFast(true)</code>) after initialization
* is complete.</p>
*
* <p><strong>NOTE</strong>: If you are creating and accessing a
* <code>TreeMap</code> only within a single thread, you should use
* <code>java.util.TreeMap</code> directly (with no synchronization), for
* maximum performance.</p>
*
* <p><strong>NOTE</strong>: <i>This class is not cross-platform.
* Using it may cause unexpected failures on some architectures.</i>
* It suffers from the same problems as the double-checked locking idiom.
* In particular, the instruction that clones the internal collection and the
* instruction that sets the internal reference to the clone can be executed
* or perceived out-of-order. This means that any read operation might fail
* unexpectedly, as it may be reading the state of the internal collection
* before the internal collection is fully formed.
* For more information on the double-checked locking idiom, see the
* .</p>
*
* @since Commons Collections 1.0
* @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
*
* @author Craig R. McClanahan
* @author Stephen Colebourne
*/
public class FastTreeMap extends TreeMap {
/**
* The underlying map we are managing.
*/
protected TreeMap map = null;
/**
* Are we operating in "fast" mode?
*/
protected boolean fast = false;
// Constructors
// ----------------------------------------------------------------------
/**
* Construct a an empty map.
*/
public FastTreeMap() {
super();
this.map = new TreeMap();
}
/**
* Construct an empty map with the specified comparator.
*
* @param comparator the comparator to use for ordering tree elements
*/
public FastTreeMap(Comparator comparator) {
super();
this.map = new TreeMap(comparator);
}
/**
* Construct a new map with the same mappings as the specified map,
* sorted according to the keys"s natural order
*
* @param map the map whose mappings are to be copied
*/
public FastTreeMap(Map map) {
super();
this.map = new TreeMap(map);
}
/**
* Construct a new map with the same mappings as the specified map,
* sorted according to the same ordering
*
* @param map the map whose mappings are to be copied
*/
public FastTreeMap(SortedMap map) {
super();
this.map = new TreeMap(map);
}
// Property access
// ----------------------------------------------------------------------
/**
* Returns true if this map is operating in fast mode.
*
* @return true if this map is operating in fast mode
*/
public boolean getFast() {
return (this.fast);
}
/**
* Sets whether this map is operating in fast mode.
*
* @param fast true if this map should operate in fast mode
*/
public void setFast(boolean fast) {
this.fast = fast;
}
// Map access
// ----------------------------------------------------------------------
// These methods can forward straight to the wrapped Map in "fast" mode.
// (because they are query methods)
/**
* Return the value to which this map maps the specified key. Returns
* <code>null</code> if the map contains no mapping for this key, or if
* there is a mapping with a value of <code>null</code>. Use the
* <code>containsKey()</code> method to disambiguate these cases.
*
* @param key the key whose value is to be returned
* @return the value mapped to that key, or null
*/
public Object get(Object key) {
if (fast) {
return (map.get(key));
} else {
synchronized (map) {
return (map.get(key));
}
}
}
/**
* Return the number of key-value mappings in this map.
*
* @return the current size of the map
*/
public int size() {
if (fast) {
return (map.size());
} else {
synchronized (map) {
return (map.size());
}
}
}
/**
* Return <code>true</code> if this map contains no mappings.
*
* @return is the map currently empty
*/
public boolean isEmpty() {
if (fast) {
return (map.isEmpty());
} else {
synchronized (map) {
return (map.isEmpty());
}
}
}
/**
* Return <code>true</code> if this map contains a mapping for the
* specified key.
*
* @param key the key to be searched for
* @return true if the map contains the key
*/
public boolean containsKey(Object key) {
if (fast) {
return (map.containsKey(key));
} else {
synchronized (map) {
return (map.containsKey(key));
}
}
}
/**
* Return <code>true</code> if this map contains one or more keys mapping
* to the specified value.
*
* @param value the value to be searched for
* @return true if the map contains the value
*/
public boolean containsValue(Object value) {
if (fast) {
return (map.containsValue(value));
} else {
synchronized (map) {
return (map.containsValue(value));
}
}
}
/**
* Return the comparator used to order this map, or <code>null</code>
* if this map uses its keys" natural order.
*
* @return the comparator used to order the map, or null if natural order
*/
public Comparator comparator() {
if (fast) {
return (map.ruparator());
} else {
synchronized (map) {
return (map.ruparator());
}
}
}
/**
* Return the first (lowest) key currently in this sorted map.
*
* @return the first key in the map
*/
public Object firstKey() {
if (fast) {
return (map.firstKey());
} else {
synchronized (map) {
return (map.firstKey());
}
}
}
/**
* Return the last (highest) key currently in this sorted map.
*
* @return the last key in the map
*/
public Object lastKey() {
if (fast) {
return (map.lastKey());
} else {
synchronized (map) {
return (map.lastKey());
}
}
}
// Map modification
// ----------------------------------------------------------------------
// These methods perform special behaviour in "fast" mode.
// The map is cloned, updated and then assigned back.
// See the comments at the top as to why this won"t always work.
/**
* Associate the specified value with the specified key in this map.
* If the map previously contained a mapping for this key, the old
* value is replaced and returned.
*
* @param key the key with which the value is to be associated
* @param value the value to be associated with this key
* @return the value previously mapped to the key, or null
*/
public Object put(Object key, Object value) {
if (fast) {
synchronized (this) {
TreeMap temp = (TreeMap) map.clone();
Object result = temp.put(key, value);
map = temp;
return (result);
}
} else {
synchronized (map) {
return (map.put(key, value));
}
}
}
/**
* Copy all of the mappings from the specified map to this one, replacing
* any mappings with the same keys.
*
* @param in the map whose mappings are to be copied
*/
public void putAll(Map in) {
if (fast) {
synchronized (this) {
TreeMap temp = (TreeMap) map.clone();
temp.putAll(in);
map = temp;
}
} else {
synchronized (map) {
map.putAll(in);
}
}
}
/**
* Remove any mapping for this key, and return any previously
* mapped value.
*
* @param key the key whose mapping is to be removed
* @return the value removed, or null
*/
public Object remove(Object key) {
if (fast) {
synchronized (this) {
TreeMap temp = (TreeMap) map.clone();
Object result = temp.remove(key);
map = temp;
return (result);
}
} else {
synchronized (map) {
return (map.remove(key));
}
}
}
/**
* Remove all mappings from this map.
*/
public void clear() {
if (fast) {
synchronized (this) {
map = new TreeMap();
}
} else {
synchronized (map) {
map.clear();
}
}
}
// Basic object methods
// ----------------------------------------------------------------------
/**
* Compare the specified object with this list for equality. This
* implementation uses exactly the code that is used to define the
* list equals function in the documentation for the
* <code>Map.equals</code> method.
*
* @param o the object to be compared to this list
* @return true if the two maps are equal
*/
public boolean equals(Object o) {
// Simple tests that require no synchronization
if (o == this) {
return (true);
} else if (!(o instanceof Map)) {
return (false);
}
Map mo = (Map) o;
// Compare the two maps for equality
if (fast) {
if (mo.size() != map.size()) {
return (false);
}
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
Object key = e.getKey();
Object value = e.getValue();
if (value == null) {
if (!(mo.get(key) == null && mo.containsKey(key))) {
return (false);
}
} else {
if (!value.equals(mo.get(key))) {
return (false);
}
}
}
return (true);
} else {
synchronized (map) {
if (mo.size() != map.size()) {
return (false);
}
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
Map.Entry e = (Map.Entry) i.next();
Object key = e.getKey();
Object value = e.getValue();
if (value == null) {
if (!(mo.get(key) == null && mo.containsKey(key))) {
return (false);
}
} else {
if (!value.equals(mo.get(key))) {
return (false);
}
}
}
return (true);
}
}
}
/**
* Return the hash code value for this map. This implementation uses
* exactly the code that is used to define the list hash function in the
* documentation for the <code>Map.hashCode</code> method.
*
* @return a suitable integer hash code
*/
public int hashCode() {
if (fast) {
int h = 0;
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
h += i.next().hashCode();
}
return (h);
} else {
synchronized (map) {
int h = 0;
Iterator i = map.entrySet().iterator();
while (i.hasNext()) {
h += i.next().hashCode();
}
return (h);
}
}
}
/**
* Return a shallow copy of this <code>FastTreeMap</code> instance.
* The keys and values themselves are not copied.
*
* @return a clone of this map
*/
public Object clone() {
FastTreeMap results = null;
if (fast) {
results = new FastTreeMap(map);
} else {
synchronized (map) {
results = new FastTreeMap(map);
}
}
results.setFast(getFast());
return (results);
}
// Sub map views
// ----------------------------------------------------------------------
/**
* Return a view of the portion of this map whose keys are strictly
* less than the specified key.
*
* @param key Key higher than any in the returned map
* @return a head map
*/
public SortedMap headMap(Object key) {
if (fast) {
return (map.headMap(key));
} else {
synchronized (map) {
return (map.headMap(key));
}
}
}
/**
* Return a view of the portion of this map whose keys are in the
* range fromKey (inclusive) to toKey (exclusive).
*
* @param fromKey Lower limit of keys for the returned map
* @param toKey Upper limit of keys for the returned map
* @return a sub map
*/
public SortedMap subMap(Object fromKey, Object toKey) {
if (fast) {
return (map.subMap(fromKey, toKey));
} else {
synchronized (map) {
return (map.subMap(fromKey, toKey));
}
}
}
/**
* Return a view of the portion of this map whose keys are greater than
* or equal to the specified key.
*
* @param key Key less than or equal to any in the returned map
* @return a tail map
*/
public SortedMap tailMap(Object key) {
if (fast) {
return (map.tailMap(key));
} else {
synchronized (map) {
return (map.tailMap(key));
}
}
}
// Map views
// ----------------------------------------------------------------------
/**
* Return a collection view of the mappings contained in this map. Each
* element in the returned collection is a <code>Map.Entry</code>.
*/
public Set entrySet() {
return new EntrySet();
}
/**
* Return a set view of the keys contained in this map.
*/
public Set keySet() {
return new KeySet();
}
/**
* Return a collection view of the values contained in this map.
*/
public Collection values() {
return new Values();
}
// Map view inner classes
// ----------------------------------------------------------------------
/**
* Abstract collection implementation shared by keySet(), values() and entrySet().
*/
private abstract class CollectionView implements Collection {
public CollectionView() {
}
protected abstract Collection get(Map map);
protected abstract Object iteratorNext(Map.Entry entry);
public void clear() {
if (fast) {
synchronized (FastTreeMap.this) {
map = new TreeMap();
}
} else {
synchronized (map) {
get(map).clear();
}
}
}
public boolean remove(Object o) {
if (fast) {
synchronized (FastTreeMap.this) {
TreeMap temp = (TreeMap) map.clone();
boolean r = get(temp).remove(o);
map = temp;
return r;
}
} else {
synchronized (map) {
return get(map).remove(o);
}
}
}
public boolean removeAll(Collection o) {
if (fast) {
synchronized (FastTreeMap.this) {
TreeMap temp = (TreeMap) map.clone();
boolean r = get(temp).removeAll(o);
map = temp;
return r;
}
} else {
synchronized (map) {
return get(map).removeAll(o);
}
}
}
public boolean retainAll(Collection o) {
if (fast) {
synchronized (FastTreeMap.this) {
TreeMap temp = (TreeMap) map.clone();
boolean r = get(temp).retainAll(o);
map = temp;
return r;
}
} else {
synchronized (map) {
return get(map).retainAll(o);
}
}
}
public int size() {
if (fast) {
return get(map).size();
} else {
synchronized (map) {
return get(map).size();
}
}
}
public boolean isEmpty() {
if (fast) {
return get(map).isEmpty();
} else {
synchronized (map) {
return get(map).isEmpty();
}
}
}
public boolean contains(Object o) {
if (fast) {
return get(map).contains(o);
} else {
synchronized (map) {
return get(map).contains(o);
}
}
}
public boolean containsAll(Collection o) {
if (fast) {
return get(map).containsAll(o);
} else {
synchronized (map) {
return get(map).containsAll(o);
}
}
}
public Object[] toArray(Object[] o) {
if (fast) {
return get(map).toArray(o);
} else {
synchronized (map) {
return get(map).toArray(o);
}
}
}
public Object[] toArray() {
if (fast) {
return get(map).toArray();
} else {
synchronized (map) {
return get(map).toArray();
}
}
}
public boolean equals(Object o) {
if (o == this) return true;
if (fast) {
return get(map).equals(o);
} else {
synchronized (map) {
return get(map).equals(o);
}
}
}
public int hashCode() {
if (fast) {
return get(map).hashCode();
} else {
synchronized (map) {
return get(map).hashCode();
}
}
}
public boolean add(Object o) {
throw new UnsupportedOperationException();
}
public boolean addAll(Collection c) {
throw new UnsupportedOperationException();
}
public Iterator iterator() {
return new CollectionViewIterator();
}
private class CollectionViewIterator implements Iterator {
private Map expected;
private Map.Entry lastReturned = null;
private Iterator iterator;
public CollectionViewIterator() {
this.expected = map;
this.iterator = expected.entrySet().iterator();
}
public boolean hasNext() {
if (expected != map) {
throw new ConcurrentModificationException();
}
return iterator.hasNext();
}
public Object next() {
if (expected != map) {
throw new ConcurrentModificationException();
}
lastReturned = (Map.Entry)iterator.next();
return iteratorNext(lastReturned);
}
public void remove() {
if (lastReturned == null) {
throw new IllegalStateException();
}
if (fast) {
synchronized (FastTreeMap.this) {
if (expected != map) {
throw new ConcurrentModificationException();
}
FastTreeMap.this.remove(lastReturned.getKey());
lastReturned = null;
expected = map;
}
} else {
iterator.remove();
lastReturned = null;
}
}
}
}
/**
* Set implementation over the keys of the FastTreeMap
*/
private class KeySet extends CollectionView implements Set {
protected Collection get(Map map) {
return map.keySet();
}
protected Object iteratorNext(Map.Entry entry) {
return entry.getKey();
}
}
/**
* Collection implementation over the values of the FastTreeMap
*/
private class Values extends CollectionView {
protected Collection get(Map map) {
return map.values();
}
protected Object iteratorNext(Map.Entry entry) {
return entry.getValue();
}
}
/**
* Set implementation over the entries of the FastTreeMap
*/
private class EntrySet extends CollectionView implements Set {
protected Collection get(Map map) {
return map.entrySet();
}
protected Object iteratorNext(Map.Entry entry) {
return entry;
}
}
}
Java 1.5 (5.0) new feature: collection and thread
/*
License for Java 1.5 "Tiger": A Developer"s Notebook
(O"Reilly) example package
Java 1.5 "Tiger": A Developer"s Notebook (O"Reilly)
by Brett McLaughlin and David Flanagan.
ISBN: 0-596-00738-8
You can use the examples and the source code any way you want, but
please include a reference to where it comes from if you use it in
your own products or services. Also note that this software is
provided by the author "as is", with no expressed or implied warranties.
In no event shall the author be liable for any direct or indirect
damages arising in any way out of the use of this software.
*/
import java.util.concurrent.locks.Condition;
import java.util.concurrent.locks.Lock;
import java.util.concurrent.locks.ReentrantLock;
public class LinkList<E> {
// The value of this node
E value;
// The rest of the list
LinkList<E> rest;
// A lock for this node
Lock lock;
// Signals when the value of this node changes
Condition valueChanged;
// Signals when the node this is connected to changes
Condition linkChanged;
public LinkList(E value) {
this.value = value;
rest = null;
lock = new ReentrantLock();
valueChanged = lock.newCondition();
linkChanged = lock.newCondition();
}
public void setValue(E value) {
lock.lock();
try {
this.value = value;
// Let waiting threads that the value has changed
valueChanged.signalAll();
} finally {
lock.unlock();
}
}
public void executeOnValue(E desiredValue, Runnable task)
throws InterruptedException {
lock.lock();
try {
// Checks the value against the desired value
while (!value.equals(desiredValue)) {
// This will wait until the value changes
valueChanged.await();
}
// When we get here, the value is correct -- Run the task
task.run();
} finally {
lock.unlock();
}
}
public void append(E value) {
// Start the pointer at this node
LinkList<E> node = this;
node.lock.lock();
while (node.rest != null) {
LinkList<E> next = node.rest;
// Here"s the hand-over-hand locking
try {
// Lock the next node
next.lock.lock();
} finally {
// unlock the current node
node.lock.unlock();
}
// Traverse
node = next;
}
// We"re at the final node, so append and then unlock
try {
node.rest = new LinkList<E>(value);
// Let any waiting threads know that this node"s link has changed
node.linkChanged.signalAll();
} finally {
node.lock.unlock();
}
}
public void printUntilInterrupted(String prefix) {
// Start the pointer at this node
LinkList<E> node = this;
node.lock.lock();
while (true) {
LinkList<E> next;
try {
System.out.println(prefix + ": " + node.value);
// Wait for the next node if not available
while (node.rest == null) {
node.linkChanged.await();
}
// Get the next node
next = node.rest;
// Lock it - more hand-to-hand locking
next.lock.lock();
} catch (InterruptedException e) {
// reset the interrupt status
Thread.currentThread().interrupt();
return;
} finally {
node.lock.unlock();
}
// Traverse
node = next;
}
}
}
Java 1.5 (5.0) new features: PriorityQueue
/*
License for Java 1.5 "Tiger": A Developer"s Notebook
(O"Reilly) example package
Java 1.5 "Tiger": A Developer"s Notebook (O"Reilly)
by Brett McLaughlin and David Flanagan.
ISBN: 0-596-00738-8
You can use the examples and the source code any way you want, but
please include a reference to where it comes from if you use it in
your own products or services. Also note that this software is
provided by the author "as is", with no expressed or implied warranties.
In no event shall the author be liable for any direct or indirect
damages arising in any way out of the use of this software.
*/
import java.util.ruparator;
import java.util.PriorityQueue;
import java.util.Queue;
public class PriorityQueueTester {
public static void main(String[] args) {
PriorityQueue<Integer> pq =
new PriorityQueue<Integer>(20,
new Comparator<Integer>() {
public int compare(Integer i, Integer j) {
int result = i%2 - j%2;
if (result == 0)
result = i-j;
return result;
}
}
);
// Fill up with data, in an odd order
for (int i=0; i<20; i++) {
pq.offer(20-i);
}
// Print out and check ordering
for (int i=0; i<20; i++) {
System.out.println(pq.poll());
}
}
}
Java Thread Performance: AtomicTest
/*
Java Threads, 3rd Edition
By Scott Oaks, Henry Wong
3rd Edition September 2004
ISBN: 0-596-00782-5
*/
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
public class AtomicTest {
static int nLoops;
static int nThreads;
public static void main(String[] args) {
nLoops = 10000;
nThreads = 1;
doTest(new AtomicRunnable());
doTest(new SyncRunnable());
nLoops = Integer.parseInt(args[0]);
nThreads = Integer.parseInt(args[1]);
System.out.println("Starting atomic test");
cleanGC();
Timestamp atomicTS = new Timestamp();
doTest(new AtomicRunnable());
atomicTS.stop();
System.out.println("Atomic took " + atomicTS);
System.out.println("Starting sync test");
cleanGC();
Timestamp syncTS = new Timestamp();
doTest(new SyncRunnable());
syncTS.stop();
System.out.println("Local sync took " + syncTS);
double d = ((double) (syncTS.elapsedTime() - atomicTS.elapsedTime()))
/ (nLoops * nThreads);
System.out.println("Atomic operation saves " + d + " " + syncTS.units()
+ " per call");
}
static void cleanGC() {
System.gc();
System.runFinalization();
System.gc();
}
static class AtomicRunnable implements Runnable {
AtomicInteger ai = new AtomicInteger(1);
public void run() {
for (int i = 0; i < nLoops; i++)
ai.incrementAndGet();
}
}
static class SyncRunnable implements Runnable {
int testVar;
synchronized void incrVar() {
testVar++;
}
public void run() {
for (int i = 0; i < nLoops; i++)
incrVar();
}
}
static void doTest(Runnable r) {
Thread threads[] = new Thread[nThreads];
for (int i = 0; i < nThreads; i++) {
threads[i] = new Thread(r);
}
for (int i = 0; i < nThreads; i++) {
threads[i].start();
}
for (int i = 0; i < nThreads; i++) {
try {
threads[i].join();
} catch (InterruptedException ie) {
}
}
}
}
class Timestamp {
private long startTime;
private long stopTime;
private boolean stopped = false;
private TimeUnit ts;
public Timestamp() {
this(TimeUnit.NANOSECONDS);
}
public Timestamp(TimeUnit ts) {
this.ts = ts;
start();
}
public void start() {
startTime = System.nanoTime();
stopped = false;
}
public void stop() {
stopTime = System.nanoTime();
stopped = true;
}
public long elapsedTime() {
if (!stopped)
throw new IllegalStateException("Timestamp not stopped");
return ts.convert(stopTime - startTime, TimeUnit.NANOSECONDS);
}
public String toString() {
try {
return elapsedTime() + " " + ts;
} catch (IllegalStateException ise) {
return "Timestamp (not stopped)";
}
}
public String units() {
return ts.toString();
}
}
Java Thread Performance: Collection Test
/*
Java Threads, 3rd Edition
By Scott Oaks, Henry Wong
3rd Edition September 2004
ISBN: 0-596-00782-5
*/
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
public class CollectionTest {
static int nLoops;
public static void main(String[] args) {
nLoops = 10000;
doTest(new Vector());
doTest(new ArrayList());
doTest(Collections.synchronizedList(new ArrayList()));
nLoops = Integer.parseInt(args[0]);
System.out.println("Starting synchronized vector test");
cleanGC();
Timestamp syncTS = new Timestamp();
doTest(new Vector());
syncTS.stop();
System.out.println("Synchronized vector took " + syncTS);
System.out.println("Starting unsynchronized vector test");
cleanGC();
Timestamp unsyncTS = new Timestamp();
unsyncTS.stop();
System.out.println("Unsynchronized vector took " + unsyncTS);
double d = ((double) (syncTS.elapsedTime() - unsyncTS.elapsedTime()))
/ nLoops;
System.out.println("Unsynchronized operation saves " + d + " "
+ syncTS.units() + " per call");
System.out.println("Starting synchronized array list test");
cleanGC();
syncTS = new Timestamp();
doTest(Collections.synchronizedList(new ArrayList()));
syncTS.stop();
System.out.println("Synchronized array list took " + syncTS);
System.out.println("Starting unsynchronized array list test");
cleanGC();
unsyncTS = new Timestamp();
doTest(new ArrayList());
unsyncTS.stop();
System.out.println("Unsynchronized aray list took " + unsyncTS);
d = ((double) (syncTS.elapsedTime() - unsyncTS.elapsedTime())) / nLoops;
System.out.println("Unsynchronized operation saves " + d + " "
+ syncTS.units() + " per call");
}
static void cleanGC() {
System.gc();
System.runFinalization();
System.gc();
}
static void doTest(List l) {
Integer n = new Integer(0);
for (int i = 0; i < nLoops; i++)
l.add(n);
}
}
class Timestamp {
private long startTime;
private long stopTime;
private boolean stopped = false;
private TimeUnit ts;
public Timestamp() {
this(TimeUnit.NANOSECONDS);
}
public Timestamp(TimeUnit ts) {
this.ts = ts;
start();
}
public void start() {
startTime = System.nanoTime();
stopped = false;
}
public void stop() {
stopTime = System.nanoTime();
stopped = true;
}
public long elapsedTime() {
if (!stopped)
throw new IllegalStateException("Timestamp not stopped");
return ts.convert(stopTime - startTime, TimeUnit.NANOSECONDS);
}
public String toString() {
try {
return elapsedTime() + " " + ts;
} catch (IllegalStateException ise) {
return "Timestamp (not stopped)";
}
}
public String units() {
return ts.toString();
}
}
Return a value from a thread.
import java.util.concurrent.Callable;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;
import java.util.concurrent.Future;
public class Main {
public static void main(String args[]) throws Exception{
ExecutorService es = Executors.newFixedThreadPool(3);
Future<Double> f = es.submit(new Avg());
Future<Integer> f2 = es.submit(new Factorial());
System.out.println(f.get());
System.out.println(f2.get());
es.shutdown();
}
}
class Avg implements Callable<Double> {
Avg() {
}
public Double call() {
return 0.0;
}
}
class Factorial implements Callable<Integer> {
Factorial() {
}
public Integer call() {
return 1;
}
}
Rhyming Words
/* From http://java.sun.ru/docs/books/tutorial/index.html */
/*
* Copyright (c) 2006 Sun Microsystems, Inc. All Rights Reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* -Redistribution of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
*
* -Redistribution in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of Sun Microsystems, Inc. or the names of contributors may
* be used to endorse or promote products derived from this software without
* specific prior written permission.
*
* This software is provided "AS IS," without a warranty of any kind. ALL
* EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND WARRANTIES, INCLUDING
* ANY IMPLIED WARRANTY OF MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE
* OR NON-INFRINGEMENT, ARE HEREBY EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN")
* AND ITS LICENSORS SHALL NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE
* AS A RESULT OF USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
* DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR ANY LOST
* REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL, CONSEQUENTIAL,
* INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND REGARDLESS OF THE THEORY
* OF LIABILITY, ARISING OUT OF THE USE OF OR INABILITY TO USE THIS SOFTWARE,
* EVEN IF SUN HAS BEEN ADVISED OF THE POSSIBILITY OF SUCH DAMAGES.
*
* You acknowledge that this software is not designed, licensed or intended
* for use in the design, construction, operation or maintenance of any
* nuclear facility.
*/
import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.PipedReader;
import java.io.PipedWriter;
import java.io.PrintWriter;
import java.io.Reader;
public class RhymingWords {
public static void main(String[] args) throws IOException {
FileReader words = new FileReader("words.txt");
// do the reversing and sorting
Reader rhymedWords = reverse(sort(reverse(words)));
// write new list to standard out
BufferedReader in = new BufferedReader(rhymedWords);
String input;
while ((input = in.readLine()) != null)
System.out.println(input);
in.close();
}
public static Reader reverse(Reader source) throws IOException {
BufferedReader in = new BufferedReader(source);
PipedWriter pipeOut = new PipedWriter();
PipedReader pipeIn = new PipedReader(pipeOut);
PrintWriter out = new PrintWriter(pipeOut);
new ReverseThread(out, in).start();
return pipeIn;
}
public static Reader sort(Reader source) throws IOException {
BufferedReader in = new BufferedReader(source);
PipedWriter pipeOut = new PipedWriter();
PipedReader pipeIn = new PipedReader(pipeOut);
PrintWriter out = new PrintWriter(pipeOut);
new SortThread(out, in).start();
return pipeIn;
}
}
class SortThread extends Thread {
private PrintWriter out = null;
private BufferedReader in = null;
public SortThread(PrintWriter out, BufferedReader in) {
this.out = out;
this.in = in;
}
public void run() {
int MAXWORDS = 50;
if (out != null && in != null) {
try {
String[] listOfWords = new String[MAXWORDS];
int numwords = 0;
while ((listOfWords[numwords] = in.readLine()) != null)
numwords++;
quicksort(listOfWords, 0, numwords - 1);
for (int i = 0; i < numwords; i++)
out.println(listOfWords[i]);
out.close();
} catch (IOException e) {
System.err.println("SortThread run: " + e);
}
}
}
private static void quicksort(String[] a, int lo0, int hi0) {
int lo = lo0;
int hi = hi0;
if (lo >= hi)
return;
String mid = a[(lo + hi) / 2];
while (lo < hi) {
while (lo < hi && a[lo].rupareTo(mid) < 0)
lo++;
while (lo < hi && a[hi].rupareTo(mid) > 0)
hi--;
if (lo < hi) {
String T = a[lo];
a[lo] = a[hi];
a[hi] = T;
lo++;
hi--;
}
}
if (hi < lo) {
int T = hi;
hi = lo;
lo = T;
}
quicksort(a, lo0, lo);
quicksort(a, lo == lo0 ? lo + 1 : lo, hi0);
}
}
class ReverseThread extends Thread {
private PrintWriter out = null;
private BufferedReader in = null;
public ReverseThread(PrintWriter out, BufferedReader in) {
this.out = out;
this.in = in;
}
public void run() {
if (out != null && in != null) {
try {
String input;
while ((input = in.readLine()) != null) {
out.println(reverseIt(input));
out.flush();
}
out.close();
} catch (IOException e) {
System.err.println("ReverseThread run: " + e);
}
}
}
private String reverseIt(String source) {
int i, len = source.length();
StringBuffer dest = new StringBuffer(len);
for (i = (len - 1); i >= 0; i--)
dest.append(source.charAt(i));
return dest.toString();
}
}
//word.txt
/*
anatomy
animation
applet
application
argument
bolts
class
communicate
component
container
development
environment
exception
graphics
image
input
integrate
interface
Java
language
native
network
nuts
object
output
primer
program
security
stream
string
threads
tools
user
*/
Safe collection operation
import java.util.ArrayList;
import java.util.Collections;
import java.util.Iterator;
import java.util.List;
public class SafeCollectionIteration extends Object {
public static void main(String[] args) {
List wordList = Collections.synchronizedList(new ArrayList());
wordList.add("Iterators");
wordList.add("require");
wordList.add("special");
wordList.add("handling");
synchronized (wordList) {
Iterator iter = wordList.iterator();
while (iter.hasNext()) {
String s = (String) iter.next();
System.out.println("found string: " + s + ", length="
+ s.length());
}
}
}
}
Safe list copy
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
public class SafeListCopy extends Object {
public static void printWords(String[] word) {
System.out.println("word.length=" + word.length);
for (int i = 0; i < word.length; i++) {
System.out.println("word[" + i + "]=" + word[i]);
}
}
public static void main(String[] args) {
List wordList = Collections.synchronizedList(new ArrayList());
wordList.add("Synchronization");
wordList.add("is");
wordList.add("important");
String[] wordA = (String[]) wordList.toArray(new String[0]);
printWords(wordA);
String[] wordB;
synchronized (wordList) {
int size = wordList.size();
wordB = new String[size];
wordList.toArray(wordB);
}
printWords(wordB);
// Third technique (the "synchronized" *is* necessary)
String[] wordC;
synchronized (wordList) {
wordC = (String[]) wordList.toArray(new String[wordList.size()]);
}
printWords(wordC);
}
}
Safe vector copy
import java.util.Vector;
public class SafeVectorCopy {
public static void main(String[] args) {
Vector vect = new Vector();
vect.addElement("Synchronization");
vect.addElement("is");
vect.addElement("important");
String[] word;
synchronized (vect) {
int size = vect.size();
word = new String[size];
for (int i = 0; i < word.length; i++) {
word[i] = (String) vect.elementAt(i);
}
}
System.out.println("word.length" + word.length);
for (int i = 0; i < word.length; i++) {
System.out.println("[" + i + "]=" + word[i]);
}
}
}
Using a Thread-Local Variable
public class Main {
public static void main(String[] argv) throws Exception {
ThreadLocal localThread = new ThreadLocal();
Object o = localThread.get();
localThread.set(o);
}
}
