|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Objectjava.util.AbstractCollection<E>
java.util.AbstractList<E>
com.sun.sgs.app.util.ScalableList<E>
E
- the type of the elements stored in the ScalableList
public class ScalableList<E>
This class represents a java.util.List
which supports a concurrent
and scalable behavior. In particular, this List allows for arbitrary
insertions and removals, arbitrary searches for values, and a number of
other methods which are also defined in the java.util.List
interface. This data structure builds upon the AbstractList
class
by implementing methods specific to concurrent and scalable operations. As
an implementation decision, this data structure does not support
null
insertions but does implement all optional operations defined
in the java.util.List
interface.
Those who are interested in using a simple data structure that is not
intended to grow very large, contains simple elements, but offers decent
concurrency should use the
java.util.concurrent.CopyOnWriteArrayList<E>
type. However, if
lists are intended to be very large and cloning the list is infeasible due
to its size or the complexity of its contents, then the
ScalableList
is a better tool as it does not require cloning and it
scales reasonably well.
This class actually stores a collection of ManagedReference
s,
which in turn point to ManagedObject
s. Therefore, each element
stored is converted into a ManagedObject
in the form of an
Element
wrapper if it is not one already, and a
ManagedReference
is created to reference it. The wrapper is
detected during an element removal: if the element is an instance of the
wrapper Element
class, then it is removed from the data manager.
Conversely, if the element had no wrapper (but by definition is still a
ManagedObject
), then it remains within the data manager until the
user explicitly removes it.
The class achieves scalability and concurrency by partitioning an ordinary
list into a number of smaller lists contained in ListNode
objects,
and joining the nodes in a tree format. This implementation bears
similarity to a skip-list in that access to arbitrary elements occurs
through initially large jumps, and then through a finer iteration of the
contained list. To allow for this behaviour, each ListNode
holds a
subset of the contents so that changes in the entries need not propagate to
all elements at once. In fact, each ListNode
only holds onto the
size of its SubList
(its children) and not a cumulative total of
all its previous siblings. This enables intermediate changes to have no
effect on neighbouring nodes, such as re-indexing.
The branchingFactor
is a user-defined parameter which describes how
the underlying tree is organized. A large branchingFactor
means
that each node in the tree contains a large number of children, providing
for a shallower tree, but many more sibling traversals. Concurrency is
somewhat compromised since parent nodes containing a large number of
children are locked during modification. A smaller branching factor reduces
the sibling traversals, but makes the tree deeper, somewhat affecting
performance during split operations. Depending on the use of the list, it
may be desirable to have a large branchingFactor
, such as for
improved scalability, or a smaller branchingFactor
, such as for
better concurrency.
Performing splits and removing unused nodes can be somewhat expensive,
depending on the values set for the branchingFactor
and
bucketSize
. This is because changes that occur at the leaf level
need to propagate to the parents; for a deep tree, this can affect a number
of different nodes. However, it is seen that the benefits provided by the
partitioning of the list that enable concurrency outweigh the performance
hit for these operations.
As mentioned, ListNode
s contain a subset of the total number of
elements in the ScalableList
. When an iterator is referencing an
element, the iterator is not affected by changes that occur in prior
ListNode
s. However, if modifications happen after the current
ListNode
being examined, they will be incorporated in the
iteration, suggesting that the target element may not be the same one as
when the call was initially made. However, if a modification in the form of
an addition or removal happens on the same ListNode
, then the
iterator will throw a ConcurrentModificationException
as a result
of a compromise to the integrity of the node. This exception is not thrown
if an element is replaced using the set()
method because there
would be no change in index to prompt the exception.
Since the ScalableList
type is a ManagedObject
, it is
important to note that applications which instantiate it should be
responsible for removing it from the data manager. This can be done by
statically obtaining the DataManager
through the AppContext
via the call
AppContext.getDataManager().removeObject(ManagedObject)
.
Contrary to the ScalableList
, iterators both within and provided
by the ScalableList
type are not ManagedObject
s.
Therefore, they are not stored within the data manager and do not need to
be removed using the DataManager
.
Since the list 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 list.
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 ScalableList
as it reduces the
locked elements owned by any one task.
Field Summary | |
---|---|
static int |
DEFAULT_BRANCHING_FACTOR
Default value for the branchingFactor if one is not explicitly
set. |
static int |
DEFAULT_BUCKET_SIZE
Default value for the bucketSize if one is not explicitly set. |
Constructor Summary | |
---|---|
ScalableList()
Constructor which creates a ScalableList object with default
values for the bucketSize and branchingFactor . |
|
ScalableList(int branchingFactor,
int bucketSize)
Constructor which creates a ScalableList object with the
branchingFactor and bucketSize supplied as a parameter. |
|
ScalableList(int branchingFactor,
int bucketSize,
Collection<E> collection)
Constructor which creates a ScalableList object with the
branchingFactor , bucketSize , and a collection
supplied as parameters. |
Method Summary | |
---|---|
boolean |
add(E e)
Appends the specified element to the end of this list. |
void |
add(int index,
E e)
Inserts the specified element at the specified position in this list. |
void |
clear()
Removes all of the elements referred to in the list, but retains a basic structure that consists of a SubList , ListNode ,
and a TreeNode , along with DummyConnector s
representing the head and tail of the list. |
boolean |
contains(Object o)
Returns true if this list contains the specified element. |
E |
get(int index)
Returns the element at the specified position in this list. |
int |
indexOf(Object o)
Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element. |
boolean |
isEmpty()
Returns true if this list contains no elements. |
Iterator<E> |
iterator()
Returns an iterator over the elements in this list in proper sequence. |
int |
lastIndexOf(Object obj)
Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element. |
ListIterator<E> |
listIterator()
Returns a ListIterator over the elements in this list in proper
sequence. |
ListIterator<E> |
listIterator(int index)
Returns a ListIterator over the elements in this list, starting
from the element at the given index. |
E |
remove(int index)
Removes the element at the specified position in this list. |
boolean |
remove(Object obj)
Removes the first occurrence in this list of the specified element. |
void |
removingObject()
Performs additional operations that are needed when this object is removed. |
boolean |
retainAll(Collection<?> c)
This operation preserves the order of the elements in the list and keeps multiple copies of the same elements if they exist. |
E |
set(int index,
Object obj)
Replaces the element at the specified position in this list with the specified element. |
int |
size()
Retrieves the size of the list. |
Methods inherited from class java.util.AbstractList |
---|
addAll, equals, hashCode, subList |
Methods inherited from class java.util.AbstractCollection |
---|
addAll, containsAll, removeAll, toArray, toArray, toString |
Methods inherited from class java.lang.Object |
---|
getClass, notify, notifyAll, wait, wait, wait |
Methods inherited from interface java.util.List |
---|
addAll, containsAll, removeAll, toArray, toArray |
Field Detail |
---|
public static final int DEFAULT_BRANCHING_FACTOR
branchingFactor
if one is not explicitly
set.
public static final int DEFAULT_BUCKET_SIZE
bucketSize
if one is not explicitly set.
Constructor Detail |
---|
public ScalableList()
ScalableList
object with default
values for the bucketSize
and branchingFactor
.
public ScalableList(int branchingFactor, int bucketSize)
ScalableList
object with the
branchingFactor
and bucketSize
supplied as a parameter.
The bucketSize
can be any integer larger than 0, however the
branchingFactor
must be larger than 1 so that the tree can be
meaningful. Otherwise, it would only be able to grow to a maximum size
of bucketSize
since branching could not introduce any
additional children.
branchingFactor
- the number of children each node should have. A
branchingFactor
of 2 means that the tree structure is binary.bucketSize
- the size of each partitioned list. This value must be
a positive integer (larger than 0).
IllegalArgumentException
- when the arguments are too smallpublic ScalableList(int branchingFactor, int bucketSize, Collection<E> collection)
ScalableList
object with the
branchingFactor
, bucketSize
, and a collection
supplied as parameters. The bucketSize
can be any integer
larger than 0, however the branchingFactor
must be larger than
1 so that the tree can be meaningful. Otherwise, it would only be able
to grow to a maximum size of bucketSize
since branching could
not introduce any additional children. The collection
represents a Collection
of elements which will be added to the
newly formed ScalableList
.
branchingFactor
- the number of children each node should have. A
branchingFactor
of 2 means that the tree structure is binary.bucketSize
- the size of each partitioned list. This value must be
a positive integer (larger than 0).collection
- a collection of objects to initially populate the
ScalableList
IllegalArgumentException
- if the collection is invalid (contains
null
elements), or if the branchingFactor
or
bucketSize
are not within their respective rangesMethod Detail |
---|
public boolean add(E e)
null
.
add
in interface Collection<E>
add
in interface List<E>
add
in class AbstractList<E>
e
- element to add
true
public void add(int index, E e)
add
in interface List<E>
add
in class AbstractList<E>
index
- the indexe
- the element to add
IndexOutOfBoundsException
- if the index is out of boundspublic void clear()
SubList
, ListNode
,
and a TreeNode
, along with DummyConnector
s
representing the head and tail of the list. The call to
removingObject()
is asynchronous, meaning the objects are
deleted from the data manager in a scheduled task.
clear
in interface Collection<E>
clear
in interface List<E>
clear
in class AbstractList<E>
public boolean contains(Object o)
true
if this list contains the specified element. More
formally, returns true
if and only if this list contains at
least one element e such that
(o==null ? e==null : o.equals(e))
.
contains
in interface Collection<E>
contains
in interface List<E>
contains
in class AbstractCollection<E>
o
- the object which may be in the list
true
if
so, false
otherwisepublic int indexOf(Object o)
(o==null ? get(i)==null : o.equals(get(i)))
,
or -1 if there is no such index.
indexOf
in interface List<E>
indexOf
in class AbstractList<E>
o
- the element to search for
public int lastIndexOf(Object obj)
lastIndexOf
in interface List<E>
lastIndexOf
in class AbstractList<E>
obj
- element to search for
public E remove(int index)
remove
in interface List<E>
remove
in class AbstractList<E>
index
- the index of the element to be removed
IndexOutOfBoundsException
- if the index is out of boundspublic boolean retainAll(Collection<?> c)
retainAll
in interface Collection<E>
retainAll
in interface List<E>
retainAll
in class AbstractCollection<E>
c
- the collection of elements to keep
true
if this list changed as a result of the callpublic E set(int index, Object obj)
set
in interface List<E>
set
in class AbstractList<E>
index
- the index to setobj
- the object to replace the existing value
public E get(int index)
get
in interface List<E>
get
in class AbstractList<E>
index
- the index to retrieve
IndexOutOfBoundsException
- if the index is out of boundspublic Iterator<E> iterator()
iterator
in interface Iterable<E>
iterator
in interface Collection<E>
iterator
in interface List<E>
iterator
in class AbstractList<E>
Iterator
over the elements in the listpublic ListIterator<E> listIterator()
ListIterator
over the elements in this list in proper
sequence.
listIterator
in interface List<E>
listIterator
in class AbstractList<E>
ListIterator
over the elements in the listpublic ListIterator<E> listIterator(int index)
ListIterator
over the elements in this list, starting
from the element at the given index.
listIterator
in interface List<E>
listIterator
in class AbstractList<E>
index
- the index
ListIterator
over the elements in the list
IndexOutOfBoundsException
- if the index is out of bounds:
index < 0 || index > size()
public boolean remove(Object obj)
(o==null ? get(i)==null : o.equals(get(i)))
(if such an element
exists).
remove
in interface Collection<E>
remove
in interface List<E>
remove
in class AbstractCollection<E>
obj
- element to be removed from the list, if present
public boolean isEmpty()
true
if this list contains no elements.
isEmpty
in interface Collection<E>
isEmpty
in interface List<E>
isEmpty
in class AbstractCollection<E>
true
if the list is empty, and false
otherwisepublic int size()
branchingFactor
.
size
in interface Collection<E>
size
in interface List<E>
size
in class AbstractCollection<E>
public void removingObject()
removingObject
in interface ManagedObjectRemoval
|
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 |