hadoop LightWeightLinkedSet 源码

haddop LightWeightLinkedSet 代码

文件路径：/hadoop-hdfs-project/hadoop-hdfs/src/main/java/org/apache/hadoop/hdfs/util/LightWeightLinkedSet.java

/**
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *     http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 */
package org.apache.hadoop.hdfs.util;

import java.util.ConcurrentModificationException;
import java.util.Iterator;
import java.util.ArrayList;
import java.util.List;
import java.util.NoSuchElementException;

/**
 * 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.
 *
 */
public class LightWeightLinkedSet<T> extends LightWeightHashSet<T> {
  /**
   * Elements of {@link LightWeightLinkedSet}.
   */
  static class DoubleLinkedElement<T> extends LinkedElement<T> {
    // references to elements within all-element linked list
    private DoubleLinkedElement<T> before;
    private DoubleLinkedElement<T> after;

    public DoubleLinkedElement(T elem, int hashCode) {
      super(elem, hashCode);
      this.before = null;
      this.after = null;
    }

    @Override
    public String toString() {
      return super.toString();
    }
  }

  private DoubleLinkedElement<T> head;
  private DoubleLinkedElement<T> tail;

  private LinkedSetIterator bookmark;

  /**
   * @param initCapacity
   *          Recommended size of the internal array.
   * @param maxLoadFactor
   *          used to determine when to expand the internal array
   * @param minLoadFactor
   *          used to determine when to shrink the internal array
   */
  public LightWeightLinkedSet(int initCapacity, float maxLoadFactor,
      float minLoadFactor) {
    super(initCapacity, maxLoadFactor, minLoadFactor);
    head = null;
    tail = null;
    bookmark = new LinkedSetIterator();
  }

  public LightWeightLinkedSet() {
    this(MINIMUM_CAPACITY, DEFAULT_MAX_LOAD_FACTOR, DEFAUT_MIN_LOAD_FACTOR);
  }

  /**
   * Add given element to the hash table
   *
   * @return true if the element was not present in the table, false otherwise
   */
  @Override
  protected boolean addElem(final T element) {
    // validate element
    if (element == null) {
      throw new IllegalArgumentException("Null element is not supported.");
    }
    // find hashCode & index
    final int hashCode = element.hashCode();
    final int index = getIndex(hashCode);
    // return false if already present
    if (getContainedElem(index, element, hashCode) != null) {
      return false;
    }

    modification++;
    size++;

    // update bucket linked list
    DoubleLinkedElement<T> le = new DoubleLinkedElement<T>(element, hashCode);
    le.next = entries[index];
    entries[index] = le;

    // insert to the end of the all-element linked list
    le.after = null;
    le.before = tail;
    if (tail != null) {
      tail.after = le;
    }
    tail = le;
    if (head == null) {
      head = le;
      bookmark.next = head;
    }

    // Update bookmark, if necessary.
    if (bookmark.next == null) {
      bookmark.next = le;
    }
    return true;
  }

  /**
   * Remove the element corresponding to the key, given key.hashCode() == index.
   *
   * @return Return the entry with the element if exists. Otherwise return null.
   */
  @Override
  protected DoubleLinkedElement<T> removeElem(final T key) {
    DoubleLinkedElement<T> found = (DoubleLinkedElement<T>) (super
        .removeElem(key));
    if (found == null) {
      return null;
    }

    // update linked list
    if (found.after != null) {
      found.after.before = found.before;
    }
    if (found.before != null) {
      found.before.after = found.after;
    }
    if (head == found) {
      head = head.after;
    }
    if (tail == found) {
      tail = tail.before;
    }

    // Update bookmark, if necessary.
    if (found == this.bookmark.next) {
      this.bookmark.next = found.after;
    }
    return found;
  }

  /**
   * Remove and return first element on the linked list of all elements.
   *
   * @return first element
   */
  public T pollFirst() {
    if (head == null) {
      return null;
    }
    T first = head.element;
    this.remove(first);
    return first;
  }

  /**
   * 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.
   *
   * @return first element
   */
  @Override
  public List<T> pollN(int n) {
    if (n >= size) {
      // if we need to remove all elements then do fast polling
      return pollAll();
    }
    List<T> retList = new ArrayList<T>(n);
    while (n-- > 0 && head != null) {
      T curr = head.element;
      this.removeElem(curr);
      retList.add(curr);
    }
    shrinkIfNecessary();
    return retList;
  }

  /**
   * 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.
   */
  @Override
  public List<T> pollAll() {
    List<T> retList = new ArrayList<T>(size);
    while (head != null) {
      retList.add(head.element);
      head = head.after;
    }
    this.clear();
    return retList;
  }

  @Override
  @SuppressWarnings("unchecked")
  public <U> U[] toArray(U[] a) {
    if (a == null) {
      throw new NullPointerException("Input array can not be null");
    }
    if (a.length < size) {
      a = (U[]) java.lang.reflect.Array.newInstance(a.getClass()
          .getComponentType(), size);
    }
    int currentIndex = 0;
    DoubleLinkedElement<T> current = head;
    while (current != null) {
      T curr = current.element;
      a[currentIndex++] = (U) curr;
      current = current.after;
    }
    return a;
  }

  @Override
  public Iterator<T> iterator() {
    return new LinkedSetIterator();
  }

  private class LinkedSetIterator implements Iterator<T> {
    /** The starting modification for fail-fast. */
    private final int startModification = modification;
    /** The next element to return. */
    private DoubleLinkedElement<T> next = head;

    @Override
    public boolean hasNext() {
      return next != null;
    }

    @Override
    public T next() {
      if (modification != startModification) {
        throw new ConcurrentModificationException("modification="
            + modification + " != startModification = " + startModification);
      }
      if (next == null) {
        throw new NoSuchElementException();
      }
      final T e = next.element;
      // find the next element
      next = next.after;
      return e;
    }

    @Override
    public void remove() {
      throw new UnsupportedOperationException("Remove is not supported.");
    }
  }

  /**
   * Clear the set. Resize it to the original capacity.
   */
  @Override
  public void clear() {
    super.clear();
    this.head = null;
    this.tail = null;
    this.resetBookmark();
  }

  /**
   * Returns a new iterator starting at the bookmarked element.
   *
   * @return the iterator to the bookmarked element.
   */
  public Iterator<T> getBookmark() {
    LinkedSetIterator toRet = new LinkedSetIterator();
    toRet.next = this.bookmark.next;
    this.bookmark = toRet;
    return toRet;
  }

  /**
   * Resets the bookmark to the beginning of the list.
   */
  public void resetBookmark() {
    this.bookmark.next = this.head;
  }
}

相关信息

hadoop 源码目录

相关文章

hadoop AtomicFileOutputStream 源码

hadoop BestEffortLongFile 源码

hadoop ByteArray 源码

hadoop Canceler 源码

hadoop ConstEnumCounters 源码

hadoop CyclicIteration 源码

hadoop DataTransferThrottler 源码

hadoop Diff 源码

hadoop EnumCounters 源码

hadoop EnumDoubles 源码