com.sun.sgs.app.util
Class ScalableDeque<E>

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by com.sun.sgs.app.util.ScalableDeque<E>
Type Parameters:
E - the type of elements held by this deque
All Implemented Interfaces:
ManagedObject, ManagedObjectRemoval, Serializable, Iterable<E>, Collection<E>, Deque<E>, Queue<E>

public class ScalableDeque<E>
extends AbstractCollection<E>
implements Deque<E>, Serializable, ManagedObjectRemoval

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.

See Also:
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

ScalableDeque

public ScalableDeque()
Creates a new empty ScalableDeque. Users of this constructor should refer to the class javadoc regarding the structure's performance.


ScalableDeque

public ScalableDeque(Collection<? extends E> c)
Creates a ScalableDeque and adds all the elements in the provided collection according to their traversal ordering.

Parameters:
c - the collection of elements the deque will initially contain
Method Detail

add

public boolean add(E e)

Specified by:
add in interface Collection<E>
Specified by:
add in interface Deque<E>
Specified by:
add in interface Queue<E>
Overrides:
add in class AbstractCollection<E>

addFirst

public void addFirst(E e)

Specified by:
addFirst in interface Deque<E>

addLast

public void addLast(E e)

Specified by:
addLast in interface Deque<E>

clear

public void clear()

Specified by:
clear in interface Collection<E>
Overrides:
clear in class AbstractCollection<E>

contains

public boolean contains(Object o)
. This operation runs in constant time.

Specified by:
contains in interface Collection<E>
Specified by:
contains in interface Deque<E>
Overrides:
contains in class AbstractCollection<E>

descendingIterator

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.

Specified by:
descendingIterator in interface Deque<E>

element

public E element()

Specified by:
element in interface Deque<E>
Specified by:
element in interface Queue<E>

equals

public boolean equals(Object o)

Specified by:
equals in interface Collection<E>
Overrides:
equals in class Object

getFirst

public E getFirst()

Specified by:
getFirst in interface Deque<E>

getLast

public E getLast()

Specified by:
getLast in interface Deque<E>

hashCode

public int hashCode()

Specified by:
hashCode in interface Collection<E>
Overrides:
hashCode in class Object

isEmpty

public boolean isEmpty()

Specified by:
isEmpty in interface Collection<E>
Overrides:
isEmpty in class AbstractCollection<E>

iterator

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.

Specified by:
iterator in interface Iterable<E>
Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface Deque<E>
Specified by:
iterator in class AbstractCollection<E>

offer

public boolean offer(E e)

Specified by:
offer in interface Deque<E>
Specified by:
offer in interface Queue<E>
Returns:
true

offerFirst

public boolean offerFirst(E e)

Specified by:
offerFirst in interface Deque<E>
Returns:
true

offerLast

public boolean offerLast(E e)

Specified by:
offerLast in interface Deque<E>
Returns:
true

peek

public E peek()

Specified by:
peek in interface Deque<E>
Specified by:
peek in interface Queue<E>

peekFirst

public E peekFirst()

Specified by:
peekFirst in interface Deque<E>

peekLast

public E peekLast()

Specified by:
peekLast in interface Deque<E>

poll

public E poll()

Specified by:
poll in interface Deque<E>
Specified by:
poll in interface Queue<E>

pollFirst

public E pollFirst()

Specified by:
pollFirst in interface Deque<E>

pollLast

public E pollLast()

Specified by:
pollLast in interface Deque<E>

pop

public E pop()

Specified by:
pop in interface Deque<E>

push

public void push(E e)

Specified by:
push in interface Deque<E>

remove

public E remove()

Specified by:
remove in interface Deque<E>
Specified by:
remove in interface Queue<E>

remove

public 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.

Specified by:
remove in interface Collection<E>
Specified by:
remove in interface Deque<E>
Overrides:
remove in class AbstractCollection<E>
Parameters:
o -
Returns:

removeAll

public boolean removeAll(Collection<?> c)

Specified by:
removeAll in interface Collection<E>
Overrides:
removeAll in class AbstractCollection<E>

removeAllOccurrences

public boolean removeAllOccurrences(Object o)
Removes all occurrences of the provided object from the deque. Note that this implementation takes time proportinal to the number of instances of o in the deque, not the number of elements.

Parameters:
o - the object to to be removed
Returns:
true if the deque was modified as a result of this operation

removeFirst

public E removeFirst()

Specified by:
removeFirst in interface Deque<E>

removeFirstOccurrence

public 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.

Specified by:
removeFirstOccurrence in interface Deque<E>
Parameters:
o -
Returns:

removeLast

public E removeLast()

Specified by:
removeLast in interface Deque<E>

removeLastOccurrence

public 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.

Specified by:
removeLastOccurrence in interface Deque<E>
Parameters:
o -
Returns:

removingObject

public void removingObject()
Clears the backing map, then removes all the Element instances created by this deque.

Specified by:
removingObject in interface ManagedObjectRemoval

size

public int size()
. This operation runs in time proportinal to the length of this deque.

Specified by:
size in interface Collection<E>
Specified by:
size in interface Deque<E>
Specified by:
size in class AbstractCollection<E>
Returns:
the size of this deque

Project Darkstar, Version 0.9.9.6
2009-05-08 15:39:40

Copyright © 2007-2009 Sun Microsystems, Inc. All rights reserved