Package org.apache.hadoop.util

Class LightWeightGSet<K,E extends K>

java.lang.Object
org.apache.hadoop.util.LightWeightGSet<K,E>
Type Parameters:
K - Key type for looking up the elements
E - Element type, which must be (1) a subclass of K, and (2) implementing LightWeightGSet.LinkedElement interface.
All Implemented Interfaces:
Iterable<E>, GSet<K,E>
Direct Known Subclasses:
LightWeightCache, LightWeightResizableGSet
@Private public class LightWeightGSet<K,E extends K> extends Object implements GSet<K,E>
A low memory footprint GSet implementation, which uses an array for storing the elements and linked lists for collision resolution. No rehash will be performed. Therefore, the internal array will never be resized. This class does not support null element. This class is not thread safe.

  • Field Details

    • entries

      protected LightWeightGSet.LinkedElement[] entries
      An internal array of entries, which are the rows of the hash table. The size must be a power of two.

    • hash_mask

      protected int hash_mask
      A mask for computing the array index from the hash value of an element.

    • size

      protected int size
      The size of the set (not the entry array).

    • modification

      protected int modification
      Modification version for fail-fast.
      See Also:

  • Constructor Details

    • LightWeightGSet

      protected LightWeightGSet()

    • LightWeightGSet

      public LightWeightGSet(int recommended_length)
      Parameters:
      recommended_length - Recommended size of the internal array.

  • Method Details

    • actualArrayLength

      protected static int actualArrayLength(int recommended)

    • size

      public int size()
      Specified by:
      size in interface GSet<K,E extends K>
      Returns:
      The size of this set.

    • getIndex

      protected int getIndex(K key)

    • convert

      protected E convert(LightWeightGSet.LinkedElement e)

    • get

      public E get(K key)
      Description copied from interface: GSet
      Return the stored element which is equal to the given key. This operation is similar to Map.get(Object).
      Specified by:
      get in interface GSet<K,E extends K>
      Parameters:
      key - The given key.
      Returns:
      The stored element if it exists. Otherwise, return null.

    • contains

      public boolean contains(K key)
      Description copied from interface: GSet
      Does this set contain an element corresponding to the given key?
      Specified by:
      contains in interface GSet<K,E extends K>
      Parameters:
      key - The given key.
      Returns:
      true if the given key equals to a stored element. Otherwise, return false.

    • put

      public E put(E element)
      Description copied from interface: GSet
      Add/replace an element. If the element does not exist, add it to the set. Otherwise, replace the existing element. Note that this operation is similar to Map.put(Object, Object) but is different from Set.add(Object) which does not replace the existing element if there is any.
      Specified by:
      put in interface GSet<K,E extends K>
      Parameters:
      element - The element being put.
      Returns:
      the previous stored element if there is any. Otherwise, return null.

    • remove

      protected E remove(int index, K key)
      Remove the element corresponding to the key, given key.hashCode() == index.
      Parameters:
      key - key.
      index - index.
      Returns:
      If such element exists, return it. Otherwise, return null.

    • remove

      public E remove(K key)
      Description copied from interface: GSet
      Remove the element corresponding to the given key. This operation is similar to Map.remove(Object).
      Specified by:
      remove in interface GSet<K,E extends K>
      Parameters:
      key - The key of the element being removed.
      Returns:
      If such element exists, return it. Otherwise, return null.

    • values

      public Collection<E> values()
      Description copied from interface: GSet
      Returns a Collection view of the values contained in this set. The collection is backed by the set, so changes to the set are reflected in the collection, and vice-versa.
      Specified by:
      values in interface GSet<K,E extends K>
      Returns:
      the collection of values.

    • iterator

      public Iterator<E> iterator()
      Specified by:
      iterator in interface Iterable<K>

    • toString

      public String toString()
      Overrides:
      toString in class Object

    • printDetails

      public void printDetails(PrintStream out)
      Print detailed information of this object.
      Parameters:
      out - out.

    • computeCapacity

      public static int computeCapacity(double percentage, String mapName)
      Let t = percentage of max memory. Let e = round(log_2 t). Then, we choose capacity = 2^e/(size of reference), unless it is outside the close interval [1, 2^30].
      Parameters:
      mapName - mapName.
      percentage - percentage.
      Returns:
      compute capacity.

    • clear

      public void clear()
      Description copied from interface: GSet
      Clear the set.
      Specified by:
      clear in interface GSet<K,E extends K>