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

java.lang.Object
  extended by java.util.AbstractCollection<E>
      extended by java.util.AbstractList<E>
          extended by com.sun.sgs.app.util.ScalableList<E>
Type Parameters:
E - the type of the elements stored in the ScalableList
All Implemented Interfaces:
ManagedObject, ManagedObjectRemoval, Serializable, Iterable<E>, Collection<E>, List<E>

public class ScalableList<E>
extends AbstractList<E>
implements Serializable, ManagedObjectRemoval

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 ManagedReferences, which in turn point to ManagedObjects. 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, ListNodes 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 ListNodes. 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 ManagedObjects. 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.

See Also:
Serialized Form

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 DummyConnectors 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

DEFAULT_BRANCHING_FACTOR

public static final int DEFAULT_BRANCHING_FACTOR
Default value for the branchingFactor if one is not explicitly set.

See Also:
Constant Field Values

DEFAULT_BUCKET_SIZE

public static final int DEFAULT_BUCKET_SIZE
Default value for the bucketSize if one is not explicitly set.

See Also:
Constant Field Values
Constructor Detail

ScalableList

public ScalableList()
Constructor which creates a ScalableList object with default values for the bucketSize and branchingFactor.


ScalableList

public ScalableList(int branchingFactor,
                    int bucketSize)
Constructor which creates a 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.

Parameters:
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).
Throws:
IllegalArgumentException - when the arguments are too small

ScalableList

public ScalableList(int branchingFactor,
                    int bucketSize,
                    Collection<E> collection)
Constructor which creates a 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.

Parameters:
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
Throws:
IllegalArgumentException - if the collection is invalid (contains null elements), or if the branchingFactor or bucketSize are not within their respective ranges
Method Detail

add

public boolean add(E e)
Appends the specified element to the end of this list. This implementation accepts all elements except for null.

Specified by:
add in interface Collection<E>
Specified by:
add in interface List<E>
Overrides:
add in class AbstractList<E>
Parameters:
e - element to add
Returns:
this method will always return true

add

public void add(int index,
                E e)
Inserts the specified element at the specified position in this list. Shifts the element currently at that position (if any) and any subsequent elements to the right (adds one to their indices).

Specified by:
add in interface List<E>
Overrides:
add in class AbstractList<E>
Parameters:
index - the index
e - the element to add
Throws:
IndexOutOfBoundsException - if the index is out of bounds

clear

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

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

contains

public boolean contains(Object o)
Returns 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)).

Specified by:
contains in interface Collection<E>
Specified by:
contains in interface List<E>
Overrides:
contains in class AbstractCollection<E>
Parameters:
o - the object which may be in the list
Returns:
whether the object is contained in the list; true if so, false otherwise

indexOf

public 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. More formally, returns the lowest index i such that

(o==null ? get(i)==null : o.equals(get(i))),

or -1 if there is no such index.

Specified by:
indexOf in interface List<E>
Overrides:
indexOf in class AbstractList<E>
Parameters:
o - the element to search for
Returns:
the index in this list of the first occurrence of the specified element, or -1 if this list does not contain this element.

lastIndexOf

public 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. More formally, returns the highest index i such that (o==null ? get(i)==null : o.equals(get(i))), or -1 if there is no such index.

Specified by:
lastIndexOf in interface List<E>
Overrides:
lastIndexOf in class AbstractList<E>
Parameters:
obj - element to search for
Returns:
the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element.

remove

public E remove(int index)
Removes the element at the specified position in this list. Shifts any subsequent elements to the left (subtracts one from their indices). Returns the element that was removed from the list.

Specified by:
remove in interface List<E>
Overrides:
remove in class AbstractList<E>
Parameters:
index - the index of the element to be removed
Returns:
the element previously at the specified position
Throws:
IndexOutOfBoundsException - if the index is out of bounds

retainAll

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

Specified by:
retainAll in interface Collection<E>
Specified by:
retainAll in interface List<E>
Overrides:
retainAll in class AbstractCollection<E>
Parameters:
c - the collection of elements to keep
Returns:
true if this list changed as a result of the call

set

public E set(int index,
             Object obj)
Replaces the element at the specified position in this list with the specified element.

Specified by:
set in interface List<E>
Overrides:
set in class AbstractList<E>
Parameters:
index - the index to set
obj - the object to replace the existing value
Returns:
the old value which was replaced

get

public E get(int index)
Returns the element at the specified position in this list.

Specified by:
get in interface List<E>
Specified by:
get in class AbstractList<E>
Parameters:
index - the index to retrieve
Returns:
the element at the supplied index
Throws:
IndexOutOfBoundsException - if the index is out of bounds

iterator

public Iterator<E> iterator()
Returns an iterator over the elements in this list in proper sequence.

Specified by:
iterator in interface Iterable<E>
Specified by:
iterator in interface Collection<E>
Specified by:
iterator in interface List<E>
Overrides:
iterator in class AbstractList<E>
Returns:
an Iterator over the elements in the list

listIterator

public ListIterator<E> listIterator()
Returns a ListIterator over the elements in this list in proper sequence.

Specified by:
listIterator in interface List<E>
Overrides:
listIterator in class AbstractList<E>
Returns:
a ListIterator over the elements in the list

listIterator

public ListIterator<E> listIterator(int index)
Returns a ListIterator over the elements in this list, starting from the element at the given index.

Specified by:
listIterator in interface List<E>
Overrides:
listIterator in class AbstractList<E>
Parameters:
index - the index
Returns:
a ListIterator over the elements in the list
Throws:
IndexOutOfBoundsException - if the index is out of bounds: index < 0 || index > size()

remove

public boolean remove(Object obj)
Removes the first occurrence in this list of the specified element. If this list does not contain the element, it is unchanged. More formally, removes the element with the lowest index i such that

(o==null ? get(i)==null : o.equals(get(i))) (if such an element exists).

Specified by:
remove in interface Collection<E>
Specified by:
remove in interface List<E>
Overrides:
remove in class AbstractCollection<E>
Parameters:
obj - element to be removed from the list, if present
Returns:
the element previously at the specified position

isEmpty

public boolean isEmpty()
Returns true if this list contains no elements.

Specified by:
isEmpty in interface Collection<E>
Specified by:
isEmpty in interface List<E>
Overrides:
isEmpty in class AbstractCollection<E>
Returns:
true if the list is empty, and false otherwise

size

public int size()
Retrieves the size of the list. The size of the list is obtained by performing a traversal of the root's children and adding each of their sizes. For very large lists, this process can be somewhat expensive as it does not occur in constant-time, but rather in a logarithmic time proportional to the branchingFactor.

Specified by:
size in interface Collection<E>
Specified by:
size in interface List<E>
Specified by:
size in class AbstractCollection<E>
Returns:
the number of elements in the list

removingObject

public void removingObject()
Performs additional operations that are needed when this object is removed.

Specified by:
removingObject in interface ManagedObjectRemoval

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

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