|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |
java.lang.Object | +--ConcurrentList
Implementation of a concurrent list, similar, although not identical, to the List interface. Implements all list operations, and permits all elements (including null) to be stored in the list; however, still not supported operations (especially bulk operations) cause an UnSupportedOperationException. Note that the size of a ConcurrentList has a special semantics: it is defined as the number of iterations, the executing threads needs to traverse the list. In addition to implementing the List interface, the ConcurrentList class provides uniformly named methods to access, insert and remove an element at the beginning and end of the list. These operations allow a concurrent list to be used as a stack, queue, or double-ended queue (deque).
Note that this implementation allows for concurrent operations to take place. Multiple threads may access the same list concurrently, the list need not to be synchronized externally. All available methods including iteration can be performed concurrently, but please note the following special semantics of concurrently manipulating a list.
All of the operations perform as could be expected for a doubly-linked list. Operations that index into the list will traverse the list from the begining to the end. Additionally to this linear iteration, the indexing thread must compete for locks during the iteration, which possibly makes such operations quite slow.
Semantics of manipulating a list concurrently:
List
Nested Class Summary | |
private class |
ConcurrentList.ListItr
Private implementation of the ConcurrentIterator. |
Field Summary | |
private ConcurrentItem |
head
There are two dummy items which mark the head and the tail of this list. |
private ConcurrentItem |
tail
There are two dummy items which mark the head and the tail of this list. |
Constructor Summary | |
ConcurrentList()
Constructs an empty concurrent list. |
Method Summary | |
void |
add(int index,
java.lang.Object element)
Inserts the specified element at the specified position in this list. |
ConcurrentItem |
add(java.lang.Object element)
Appends the given element to the end of this list. |
boolean |
addAll(java.util.Collection c)
Appends 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 (optional operation). |
boolean |
addAll(int index,
java.util.Collection c)
Inserts all of the elements in the specified collection into this list at the specified position (optional operation). |
private ConcurrentItem |
addBefore(java.lang.Object element,
ConcurrentItem item)
Basic method to insert an item into this list. |
ConcurrentItem |
addFirst(java.lang.Object element)
Inserts the given element at the beginning of this list. |
ConcurrentItem |
addItem(java.lang.Object element,
ConcurrentItem item)
Inserts the given element to this list before of the given item. |
ConcurrentItem |
addLast(java.lang.Object element)
Appends the given element to the end of this list. |
void |
clear()
Makes this list the empty list. |
protected java.lang.Object |
clone()
Clones this list as currently seen by an iterator constructed for the thread. |
boolean |
contains(java.lang.Object element)
Returns true if this list contains the specified element. |
boolean |
containsAll(java.util.Collection c)
Returns true if this list contains all of the elements of the specified collection. |
boolean |
equals(java.lang.Object obj)
Compares the specified object with this list for equality. |
java.lang.Object |
get(int index)
Returns the element at the specified position in this list. |
java.lang.Object |
getFirst()
Returns the first element in this list. |
ConcurrentItem |
getFirstItem()
Returns the first item in this list. |
ConcurrentItem |
getItem(int index)
Returns the item at the specified position in this list. |
ConcurrentItem |
getItem(int index,
ConcurrentItem item)
Returns the item at the specified position in this list and fills atomicly the parameter item with the element encountered. |
(package private) ConcurrentItem |
getItem(int index,
java.lang.Object[] elementArray)
Returns the item at the specified position in this list and fills atomicly the array with the element encountered. |
java.lang.Object |
getLast()
Returns the last element in this list. |
ConcurrentItem |
getLastItem()
Returns the last item in this list. |
int |
hashCode()
Returns the hash code value for this list. |
int |
indexOf(java.lang.Object element)
Returns the index in this list of the first occurrence of the specified element, or -1 if this list does not contain the element. |
boolean |
isEmpty()
Indicates whether this list is currently empty. |
int |
lastIndexOf(java.lang.Object element)
Returns the index in this list of the last occurrence of the specified element, or -1 if this list does not contain this element. |
ConcurrentIterator |
listIterator()
Returns a ConcurrentIterator of the items or elements in this list (in proper sequence), starting at the beginning of this list. |
ConcurrentIterator |
listIterator(int index)
Returns a ConcurrentIterator of the items or elements in this list (in proper sequence), starting at the specified position in the list. |
private void |
remove(ConcurrentItem item)
Basic method to remove an item from this list. |
java.lang.Object |
remove(int index)
Removes the element at the specified position in this list. |
boolean |
remove(java.lang.Object element)
Removes the first occurrence of the specified element in this list. |
boolean |
removeAll(java.util.Collection c)
Removes from this list all the elements that are contained in the specified collection (optional operation). |
java.lang.Object |
removeFirst()
Removes and returns the first element from this list. |
void |
removeItem(ConcurrentItem item)
Removes an item from this list. |
java.lang.Object |
removeLast()
Removes and returns the last element from this list. |
boolean |
retainAll(java.util.Collection c)
Retains only the elements in this list that are contained in the specified collection (optional operation). |
java.lang.Object |
set(int index,
java.lang.Object element)
Sets the element at the specified position. |
int |
size()
The size of a ConcurrentList is defined as the number of iterations currently needed by this thread to traverse this list. |
ConcurrentList |
subList(int fromIndex,
int toIndex)
Returns a view of the portion of this list between the specified fromIndex, inclusive, and toIndex, exclusive. |
java.lang.Object[] |
toArray()
Returns an array containing all elements of this list as seen currently by an iteration of the thread over this list. |
(package private) java.lang.Object[] |
toArray(java.lang.Object[] a)
Returns an array containing all elements of this list as seen currently by an iteration of the thread over this list. |
Methods inherited from class java.lang.Object |
finalize, getClass, notify, notifyAll, toString, wait, wait, wait |
Field Detail |
private transient volatile ConcurrentItem head
private transient volatile ConcurrentItem tail
Constructor Detail |
public ConcurrentList()
Method Detail |
public boolean isEmpty()
public java.lang.Object getFirst()
java.util.NoSuchElementException
- if this list is currently empty.public java.lang.Object getLast()
java.util.NoSuchElementException
- if this list is currently empty.public ConcurrentItem getFirstItem()
public ConcurrentItem getLastItem()
public java.lang.Object removeFirst() throws java.lang.InterruptedException
java.util.NoSuchElementException
- if this list is currently empty.
java.lang.InterruptedException
- if the thread is interrupted while
waiting for iterators releasing the first item.public java.lang.Object removeLast() throws java.lang.InterruptedException
java.util.NoSuchElementException
- if this list is currently empty.
java.lang.InterruptedException
- if the thread is interrupted while
waiting for iterators releasing the last item.public void removeItem(ConcurrentItem item) throws java.lang.InterruptedException
item
- the item to be removed.
Precondition: item is part of this list.
java.util.NoSuchElementException
- of the this list is currently empty.
java.lang.InterruptedException
- if the thread is interrupted while
waiting for iterators releasing the last item.public ConcurrentItem addFirst(java.lang.Object element)
element
- the element to be inserted at the beginning of this list.
public ConcurrentItem addLast(java.lang.Object element)
element
- the element to be inserted at the end of this list.
public ConcurrentItem add(java.lang.Object element)
element
- the element to be inserted at the end of this list.
public ConcurrentItem addItem(java.lang.Object element, ConcurrentItem item)
element
- the element to be inserted.item
- the item which the element is inserted before.
Precondition: item is part of this list.
java.util.NoSuchElementException
- if the item has been deleted while waiting.public void clear() throws java.lang.InterruptedException
java.lang.InterruptedException
public ConcurrentIterator listIterator()
Note that you must use the removeCurrent method of the iterator to remove the current item while iterating. It is a severe bug to call the remove method of the list instead, because it will deadlock. The implementation can neither detect nor prevent this deadlock.
Iterator
public ConcurrentIterator listIterator(int index)
Note that you must use the removeCurrent() method of the iterator to remove the current item while iterating. It is a severe bug to call the remove() method of the list instead, because it will deadlock. The implementation can neither detect nor prevent this deadlock.
index
- index of first element to be returned from the
iterator (by a call to next()).
java.lang.IndexOutOfBoundsException
- if index is out of range.private ConcurrentItem addBefore(java.lang.Object element, ConcurrentItem item)
element
- the element to be inserteditem
- the item in front of which the element is to be inserted.
Precondition: item is part of the list.
java.util.NoSuchElementException
- if the item in front of which the element
has to be inserted has been removed from this list while the thread
is waiting for the necessary locks.private void remove(ConcurrentItem item) throws java.lang.InterruptedException
item
- the item to be removed.
Precondition: item is part of this list.
java.lang.InterruptedException
- if the thread is interrupted while
waiting for iterators releasing the item.
java.util.NoSuchElementException
- if this list is empty.protected java.lang.Object clone() throws java.lang.CloneNotSupportedException
clone
in class java.lang.Object
java.lang.CloneNotSupportedException
public java.lang.Object get(int index)
index
- the index of the element to be returned.
java.lang.IndexOutOfBoundsException
- if the specified index is out of range.public ConcurrentItem getItem(int index)
index
- the index of the item to be returned.
ConcurrentItem getItem(int index, java.lang.Object[] elementArray)
index
- the index of the item to be returned.
public ConcurrentItem getItem(int index, ConcurrentItem item)
index
- the index of the item to be returned.
public java.lang.Object set(int index, java.lang.Object element)
index
- the index of the item to be returned.element
- the element used to replace
java.lang.IndexOutOfBoundsException
- if the specified index is out of range.public boolean contains(java.lang.Object element)
element
- element whose presence in this list is to be tested.
public int indexOf(java.lang.Object element)
element
- element to search for.
public void add(int index, java.lang.Object element)
index
- index at which the specified element is to be inserted.element
- element to be inserted.
java.lang.IndexOutOfBoundsException
- if the specified index is out of range.public java.lang.Object remove(int index) throws java.lang.InterruptedException
index
- the index of the element to removed.
java.lang.IndexOutOfBoundsException
- if the specified index is out of range.
java.lang.InterruptedException
- if the thread is interrupted while
waiting for iterators releasing the itempublic boolean remove(java.lang.Object element) throws java.lang.InterruptedException
element
- element to be removed from this list, if present.
java.lang.InterruptedException
- if the thread is interrupted while
waiting for iterators releasing the item holding the element.public boolean addAll(java.util.Collection c)
c
- collection whose elements are to be added to this list.
java.lang.UnsupportedOperationException
- if the addAll() method is
not supported by this list.
java.lang.ClassCastException
- if the class of an element in the specified
collection prevents it from being added to this list.
java.lang.IllegalArgumentException
- if some aspect of an element in the
specified collection prevents it from being added to this
list.add(Object)
public boolean addAll(int index, java.util.Collection c)
index
- index at which to insert first element from the specified
collection.c
- elements to be inserted into this list.
java.lang.UnsupportedOperationException
- if the addAll() method is
not supported by this list.
java.lang.ClassCastException
- if the class of one of elements of the
specified collection prevents it from being added to this
list.
java.lang.IllegalArgumentException
- if some aspect of one of elements of
the specified collection prevents it from being added to
this list.
java.lang.IndexOutOfBoundsException
- if the index is out of range.public boolean containsAll(java.util.Collection c)
c
- collection to be checked for containment in this list.
contains(Object)
public boolean removeAll(java.util.Collection c)
c
- collection that defines which elements will be removed from
this list.
java.lang.UnsupportedOperationException
- if the removeAll() method
is not supported by this list.remove(Object)
,
contains(Object)
public boolean retainAll(java.util.Collection c)
c
- collection that defines which elements this set will retain.
java.lang.UnsupportedOperationException
- if the retainAll() method
is not supported by this list.remove(Object)
,
contains(Object)
public boolean equals(java.lang.Object obj)
equals
in class java.lang.Object
obj
- the object to be compared for equality with this list.
java.lang.UnsupportedOperationException
- if the retainAll() method
is not supported by this list.public int hashCode()
hashCode = 1; Iterator i = list.iterator(); while (i.hasNext()) { Object obj = i.next(); hashCode = 31*hashCode + (obj==null ? 0 : obj.hashCode()); }This ensures that list1.equals(list2) implies that list1.hashCode()==list2.hashCode() for any two lists, list1 and list2, as required by the general contract of Object.hashCode.
hashCode
in class java.lang.Object
java.lang.UnsupportedOperationException
- if the retainAll() method
is not supported by this list.Object.hashCode()
,
Object.equals(Object)
,
equals(Object)
public int lastIndexOf(java.lang.Object element)
element
- element to search for.
java.lang.UnsupportedOperationException
- if the retainAll() method
is not supported by this list.public int size()
public java.lang.Object[] toArray()
java.lang.Object[] toArray(java.lang.Object[] a)
a
- the array to hold the elements of this list.
java.lang.IndexOutOfBoundsException
- if the array is not sufficiently
large to hold all elementspublic ConcurrentList subList(int fromIndex, int toIndex)
This method eliminates the need for explicit range operations (of the sort that commonly exist for arrays). Any operation that expects a list can be used as a range operation by passing a subList view instead of a whole list. For example, the following idiom removes a range of elements from a list:
list.subList(from, to).clear();Similar idioms may be constructed for indexOf and lastIndexOf, and all of the algorithms in the Collections class can be applied to a subList.
The semantics of this list returned by this method become undefined if the backing list (i.e., this list) is structurally modified in any way other than via the returned list. (Structural modifications are those that change the size of this list, or otherwise perturb it in such a fashion that iterations in progress may yield incorrect results.)
fromIndex
- low endpoint (inclusive) of the subList.toIndex
- high endpoint (exclusive) of the subList.
java.lang.IndexOutOfBoundsException
- for an illegal endpoint index value
(fromIndex < 0 || toIndex > size || fromIndex > toIndex).
java.lang.UnsupportedOperationException
- if the method
is not supported by this list.
|
||||||||||
PREV CLASS NEXT CLASS | FRAMES NO FRAMES | |||||||||
SUMMARY: NESTED | FIELD | CONSTR | METHOD | DETAIL: FIELD | CONSTR | METHOD |