|
||||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||
java.lang.Objectjava.util.AbstractCollection<E>
com.sun.sgs.app.util.ScalableDeque<E>
E - the type of elements held by this dequepublic class ScalableDeque<E>
A scalable Deque implementation. This implementation
supports concurrent writers at each of the deque's ends. The
internal representation of the deque is segmented so that
operations do not access the data of entire deque. Note that
concurrent read and write operations on the same end of the
deque will still cause contention.
Developers should use this as a drop-in replaced for any Deque or Queue implementation
if the size of the data
structure will be more than a small number of elements, or if the
data structure needs to support concurrent writers for putting and
removing. A standard Deque or Queue implementation
will likely perform better than an instance of this class if the
number of elements is small, or if the usage instance happens
entirely during the lifetime of a task and the instance is never
persisted.
The iterator will only make a best-effort to reflect any
concurrent change to the deque. If the next element that the
iterator is to return was been removed during a separate task, the
iterator will throw a ConcurrentModificationException. In this behavior, not supporting
concurrent updates incurs no performance overhead for mutating
operations. Furthermore, multiple iterators will not cause any
addtional contention.
Most operations run in constant time. However, there are several
key differences in operation cost between this class and other
Deque implementations. The operations remove, removeAll, removeFirstOccurrence,
and removeLastOccurrence run in time linear to the number of instances
of that object in the deque, not the number of elements in the
deque. In addition, the contains operation is constant time. Due to the distributed nature
of the deque, the size operation takes
time linear to the size of the deque. For large deques, this
method should not be called, as it would take longer than the time
available to a Task. Similarly, the toArray and toArray(T[]) operations should not
be used for anything but small deques. The isEmpty and clear operations however are still constant time.
All elements stored by this deque must be instances of Serializable. This class additionally supports elements
that are instances of ManagedObject. If a ManagedObject is stored within this deque, the developer is still
responsible for removing it from the data store at the end of its
lifetime. Removing a ManagedObject from the deque by any
operation, including clear, will not remove that
object from the data store. These objects should be removed from
the data store after they have been removed from the deque.
This class requires that all elements have a meaningful hashCode and equals operation. Failure to do so will
result in the contains, remove, removeFirstOccurrrence, removeLastOccurrence and removeAll operations not working. The remaining operations will
still operate as normal, however.
This class will mark itself for update as
necessary; no additional calls to the DataManager are
necessary when modifying the deque. Developers should not need to
call markForUpdate or getForUpdate on a deque
instance, as this will eliminate all the concurrency benefits of
this class. However, calling getForUpdate or markForUpdate can be used if an operation needs to prevent all
access to the map.
Since the deque is capable of containing many elements, applications which
use iterators to traverse elements should be aware that prolonged iterative
tasks have the potential to lock out other concurrent tasks on the deque.
Therefore, it is highly recommended (and considered good practice) that
potentially long iterations be broken up into smaller tasks. This strategy
improves the concurrency of the deque as it reduces the
locked elements owned by any one task. Iterators belonging to the deque
implement the java.io.Serializable interface, but not
com.sun.sgs.app.ManagedObject. Therefore, to persist them in the
data manager, it is necessary to wrap them within another
ManagedObject. If the iterators are persisted, the
DataManager.markForUpdate() (with the wrapper as the argument)
should be called when performing iterator operations like next(),
remove(), etc, so that the iterator's state is flushed to the
data manager.
This class and its iterator support all the optional Collection and Iterator operations. This class does not
support null elements.
Deque,
ManagedObject,
Serializable,
Serialized Form| Constructor Summary | |
|---|---|
ScalableDeque()
Creates a new empty ScalableDeque. |
|
ScalableDeque(Collection<? extends E> c)
Creates a ScalableDeque and adds all the elements in the
provided collection according to their traversal ordering. |
|
| Method Summary | |
|---|---|
boolean |
add(E e)
|
void |
addFirst(E e)
|
void |
addLast(E e)
|
void |
clear()
|
boolean |
contains(Object o)
. |
Iterator<E> |
descendingIterator()
|
E |
element()
|
boolean |
equals(Object o)
|
E |
getFirst()
|
E |
getLast()
|
int |
hashCode()
|
boolean |
isEmpty()
|
Iterator<E> |
iterator()
|
boolean |
offer(E e)
|
boolean |
offerFirst(E e)
|
boolean |
offerLast(E e)
|
E |
peek()
|
E |
peekFirst()
|
E |
peekLast()
|
E |
poll()
|
E |
pollFirst()
|
E |
pollLast()
|
E |
pop()
|
void |
push(E e)
|
E |
remove()
|
boolean |
remove(Object o)
Note that this implementation takes time proportinal to the number of instances of o in the
deque, not the number of elements. |
boolean |
removeAll(Collection<?> c)
|
boolean |
removeAllOccurrences(Object o)
Removes all occurrences of the provided object from the deque. |
E |
removeFirst()
|
boolean |
removeFirstOccurrence(Object o)
Note that this implementation takes time proportinal to the number of instances of o in the
deque, not the number of elements. |
E |
removeLast()
|
boolean |
removeLastOccurrence(Object o)
Note that this implementation takes time proportinal to the number of instances of o in the
deque, not the number of elements. |
void |
removingObject()
Clears the backing map, then removes all the Element
instances created by this deque. |
int |
size()
. |
| Methods inherited from class java.util.AbstractCollection |
|---|
addAll, containsAll, retainAll, toArray, toArray, toString |
| Methods inherited from class java.lang.Object |
|---|
getClass, notify, notifyAll, wait, wait, wait |
| Methods inherited from interface java.util.Collection |
|---|
addAll, containsAll, retainAll, toArray, toArray |
| Constructor Detail |
|---|
public ScalableDeque()
ScalableDeque.
Users of this constructor should refer to the class javadoc
regarding the structure's performance.
public ScalableDeque(Collection<? extends E> c)
ScalableDeque and adds all the elements in the
provided collection according to their traversal ordering.
c - the collection of elements the deque will initially
contain| Method Detail |
|---|
public boolean add(E e)
add in interface Collection<E>add in interface Deque<E>add in interface Queue<E>add in class AbstractCollection<E>public void addFirst(E e)
addFirst in interface Deque<E>public void addLast(E e)
addLast in interface Deque<E>public void clear()
clear in interface Collection<E>clear in class AbstractCollection<E>public boolean contains(Object o)
contains in interface Collection<E>contains in interface Deque<E>contains in class AbstractCollection<E>public Iterator<E> descendingIterator()
The iterator implements the java.io.Serializable
interface but does not implement the
com.sun.sgs.app.ManagedObject interface, so
it is not stored in the data manager by default.
The iterator throws a ConcurrentModificationException
if either the next element was removed and hasNext()
was not called before next(), or if the iterator was
serialized and the next element was removed before a call
to retrieve the next element is made.
descendingIterator in interface Deque<E>public E element()
element in interface Deque<E>element in interface Queue<E>public boolean equals(Object o)
equals in interface Collection<E>equals in class Objectpublic E getFirst()
getFirst in interface Deque<E>public E getLast()
getLast in interface Deque<E>public int hashCode()
hashCode in interface Collection<E>hashCode in class Objectpublic boolean isEmpty()
isEmpty in interface Collection<E>isEmpty in class AbstractCollection<E>public Iterator<E> iterator()
The iterator implements the java.io.Serializable
interface but does not implement the
com.sun.sgs.app.ManagedObject interface, so
it is not stored in the data manager by default.
The iterator throws a ConcurrentModificationException
if either the next element was removed and hasNext()
was not called before next(), or if the iterator was
serialized and the next element was removed before a call
to retrieve the next element is made.
iterator in interface Iterable<E>iterator in interface Collection<E>iterator in interface Deque<E>iterator in class AbstractCollection<E>public boolean offer(E e)
offer in interface Deque<E>offer in interface Queue<E>truepublic boolean offerFirst(E e)
offerFirst in interface Deque<E>truepublic boolean offerLast(E e)
offerLast in interface Deque<E>truepublic E peek()
peek in interface Deque<E>peek in interface Queue<E>public E peekFirst()
peekFirst in interface Deque<E>public E peekLast()
peekLast in interface Deque<E>public E poll()
poll in interface Deque<E>poll in interface Queue<E>public E pollFirst()
pollFirst in interface Deque<E>public E pollLast()
pollLast in interface Deque<E>public E pop()
pop in interface Deque<E>public void push(E e)
push in interface Deque<E>public E remove()
remove in interface Deque<E>remove in interface Queue<E>public boolean remove(Object o)
o in the
deque, not the number of elements.
remove in interface Collection<E>remove in interface Deque<E>remove in class AbstractCollection<E>o -
public boolean removeAll(Collection<?> c)
removeAll in interface Collection<E>removeAll in class AbstractCollection<E>public boolean removeAllOccurrences(Object o)
o in the deque, not the
number of elements.
o - the object to to be removed
true if the deque was modified as a result of
this operationpublic E removeFirst()
removeFirst in interface Deque<E>public boolean removeFirstOccurrence(Object o)
o in the
deque, not the number of elements.
removeFirstOccurrence in interface Deque<E>o -
public E removeLast()
removeLast in interface Deque<E>public boolean removeLastOccurrence(Object o)
o in the
deque, not the number of elements.
removeLastOccurrence in interface Deque<E>o -
public void removingObject()
Element
instances created by this deque.
removingObject in interface ManagedObjectRemovalpublic int size()
size in interface Collection<E>size in interface Deque<E>size in class AbstractCollection<E>
|
Project Darkstar, Version 0.9.9.6 2009-05-08 15:39:40 |
|||||||||
| PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
| SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD | |||||||||