org.apache.hadoop.hdfs.util

Class LightWeightLinkedSet<T>

java.lang.Object

org.apache.hadoop.hdfs.util.LightWeightHashSet<T>

org.apache.hadoop.hdfs.util.LightWeightLinkedSet<T>

All Implemented Interfaces:

Iterable<T>, Collection<T>

public class LightWeightLinkedSet<T>
extends LightWeightHashSet<T>

A low memory linked hash set implementation, which uses an array for storing the elements and linked lists for collision resolution. In addition it stores elements in a linked list to ensure ordered traversal. This class does not support null element. This class is not thread safe.

Field Summary

Fields inherited from class org.apache.hadoop.hdfs.util.LightWeightHashSet

DEFAULT_MAX_LOAD_FACTOR, DEFAUT_MIN_LOAD_FACTOR, entries, MINIMUM_CAPACITY, modification, size

Constructor Summary

Constructors

Constructor and Description
LightWeightLinkedSet()
LightWeightLinkedSet(int initCapacity, float maxLoadFactor, float minLoadFactor)

Method Summary

Methods

Modifier and Type	Method and Description
protected boolean	addElem(T element) Add given element to the hash table
void	clear() Clear the set.
Iterator<T>	getBookmark() Returns a new iterator starting at the bookmarked element.
Iterator<T>	iterator()
List<T>	pollAll() Remove all elements from the set and return them in order.
T	pollFirst() Remove and return first element on the linked list of all elements.
List<T>	pollN(int n) Remove and return n elements from the hashtable.
protected org.apache.hadoop.hdfs.util.LightWeightLinkedSet.DoubleLinkedElement<T>	removeElem(T key) Remove the element corresponding to the key, given key.hashCode() == index.
void	resetBookmark() Resets the bookmark to the beginning of the list.
<U> U[]	toArray(U[] a)

Methods inherited from class org.apache.hadoop.hdfs.util.LightWeightHashSet

add, addAll, contains, containsAll, expandIfNecessary, getCapacity, getContainedElem, getElement, getIndex, isEmpty, pollToArray, printDetails, remove, removeAll, retainAll, shrinkIfNecessary, size, toArray, toString

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, wait, wait, wait

Methods inherited from interface java.util.Collection

equals, hashCode

Constructor Detail

LightWeightLinkedSet

public LightWeightLinkedSet(int initCapacity,
                    float maxLoadFactor,
                    float minLoadFactor)

Parameters:

initCapacity - Recommended size of the internal array.

maxLoadFactor - used to determine when to expand the internal array

minLoadFactor - used to determine when to shrink the internal array

LightWeightLinkedSet

public LightWeightLinkedSet()

Method Detail

addElem

protected boolean addElem(T element)

Add given element to the hash table

Overrides:

addElem in class LightWeightHashSet<T>

Returns:

true if the element was not present in the table, false otherwise

removeElem

protected org.apache.hadoop.hdfs.util.LightWeightLinkedSet.DoubleLinkedElement<T> removeElem(T key)

Remove the element corresponding to the key, given key.hashCode() == index.

Overrides:

removeElem in class LightWeightHashSet<T>

Returns:

Return the entry with the element if exists. Otherwise return null.

pollFirst

public T pollFirst()

Remove and return first element on the linked list of all elements.

Returns:

first element

pollN

public List<T> pollN(int n)

Remove and return n elements from the hashtable. The order in which entries are removed is corresponds to the order in which they were inserted.

Overrides:

pollN in class LightWeightHashSet<T>

Returns:

first element

pollAll

public List<T> pollAll()

Remove all elements from the set and return them in order. Traverse the link list, don't worry about hashtable - faster version of the parent method.

Overrides:

pollAll in class LightWeightHashSet<T>

toArray

public <U> U[] toArray(U[] a)

Specified by:

toArray in interface Collection<T>

Overrides:

toArray in class LightWeightHashSet<T>

iterator

public Iterator<T> iterator()

Specified by:

iterator in interface Iterable<T>

Specified by:

iterator in interface Collection<T>

Overrides:

iterator in class LightWeightHashSet<T>

clear

public void clear()

Clear the set. Resize it to the original capacity.

Specified by:

clear in interface Collection<T>

Overrides:

clear in class LightWeightHashSet<T>

getBookmark

public Iterator<T> getBookmark()

Returns a new iterator starting at the bookmarked element.

Returns:

the iterator to the bookmarked element.

resetBookmark

public void resetBookmark()

Resets the bookmark to the beginning of the list.