hadoop IntrusiveCollection 源码

haddop IntrusiveCollection 代码

文件路径：/hadoop-common-project/hadoop-common/src/main/java/org/apache/hadoop/util/IntrusiveCollection.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.util;

import java.util.Collection;
import java.util.Iterator;
import java.util.NoSuchElementException;

import org.apache.hadoop.classification.InterfaceAudience;

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;

/**
 * Implements an intrusive doubly-linked list.
 *
 * An intrusive linked list is one in which the elements themselves are
 * responsible for storing the pointers to previous and next elements.
 * This can save a lot of memory if there are many elements in the list or
 * many lists.
 */
@InterfaceAudience.Private
public class IntrusiveCollection<E extends IntrusiveCollection.Element>
    implements Collection<E> {
  /**
   * An element contained in this list.
   *
   * We pass the list itself as a parameter so that elements can belong to
   * multiple lists.  (The element will need to store separate prev and next
   * pointers for each.)
   */
  @InterfaceAudience.Private
  public interface Element {
    /**
     * Insert this element into the list.  This is the first thing that will
     * be called on the element.
     *
     * @param list list.
     * @param prev prev.
     * @param next next.
     */
    void insertInternal(IntrusiveCollection<? extends Element> list,
        Element prev, Element next);

    /**
     * Set the prev pointer of an element already in the list.
     *
     * @param list list.
     * @param prev prev.
     */
    void setPrev(IntrusiveCollection<? extends Element> list, Element prev);

    /**
     * Set the next pointer of an element already in the list.
     *
     * @param list list.
     * @param next next.
     */
    void setNext(IntrusiveCollection<? extends Element> list, Element next);

    /**
     * Remove an element from the list.  This is the last thing that will be
     * called on an element.
     *
     * @param list list.
     */
    void removeInternal(IntrusiveCollection<? extends Element> list);

    /**
     * Get the prev pointer of an element.
     *
     * @param list list.
     * @return Element.
     */
    Element getPrev(IntrusiveCollection<? extends Element> list);

    /**
     * Get the next pointer of an element.
     *
     * @param list list.
     * @return Element.
     */
    Element getNext(IntrusiveCollection<? extends Element> list);

    /**
     * Returns true if this element is in the provided list.
     *
     * @param list list.
     * @return if this element is in the provided list true, not false.
     */
    boolean isInList(IntrusiveCollection<? extends Element> list);
  }

  private Element root = new Element() {
    // We keep references to the first and last elements for easy access.
    Element first = this;
    Element last = this;
  
    @Override
    public void insertInternal(IntrusiveCollection<? extends Element> list,
        Element prev, Element next) {
      throw new RuntimeException("Can't insert root element");
    }

    @Override
    public void setPrev(IntrusiveCollection<? extends Element> list,
        Element prev) {
      Preconditions.checkState(list == IntrusiveCollection.this);
      last = prev;
    }

    @Override
    public void setNext(IntrusiveCollection<? extends Element> list,
        Element next) {
      Preconditions.checkState(list == IntrusiveCollection.this);
      first = next;
    }
  
    @Override
    public void removeInternal(IntrusiveCollection<? extends Element> list) {
      throw new RuntimeException("Can't remove root element");
    }
    
    @Override
    public Element getNext(
        IntrusiveCollection<? extends Element> list) {
      Preconditions.checkState(list == IntrusiveCollection.this);
      return first;
    }
  
    @Override
    public Element getPrev(
        IntrusiveCollection<? extends Element> list) {
      Preconditions.checkState(list == IntrusiveCollection.this);
      return last;
    }

    @Override
    public boolean isInList(IntrusiveCollection<? extends Element> list) {
      return list == IntrusiveCollection.this;
    }

    @Override
    public String toString() {
      return "root"; // + IntrusiveCollection.this + "]";
    }
  };

  private int size = 0;

  /**
   * An iterator over the intrusive collection.
   *
   * Currently, you can remove elements from the list using
   * #{IntrusiveIterator#remove()}, but modifying the collection in other
   * ways during the iteration is not supported.
   */
  public class IntrusiveIterator implements Iterator<E> {
    Element cur;
    Element next;

    IntrusiveIterator() {
      this.cur = root;
      this.next = null;
    }

    @Override
    public boolean hasNext() {
      if (next == null) {
        next = cur.getNext(IntrusiveCollection.this);
      }
      return next != root;
    }

    @SuppressWarnings("unchecked")
    @Override
    public E next() {
      if (next == null) {
        next = cur.getNext(IntrusiveCollection.this);
      }
      if (next == root) {
        throw new NoSuchElementException();
      }
      cur = next;
      next = null;
      return (E)cur;
    }

    @Override
    public void remove() {
      if (cur == null) {
        throw new IllegalStateException("Already called remove " +
            "once on this element.");
      }
      next = removeElement(cur);
      cur = null;
    }
  }
  
  private Element removeElement(Element elem) {
    Element prev = elem.getPrev(IntrusiveCollection.this);
    Element next = elem.getNext(IntrusiveCollection.this);
    elem.removeInternal(IntrusiveCollection.this);
    prev.setNext(IntrusiveCollection.this, next);
    next.setPrev(IntrusiveCollection.this, prev);
    size--;
    return next;
  }

  /**
   * Get an iterator over the list.  This can be used to remove elements.
   * It is not safe to do concurrent modifications from other threads while
   * using this iterator.
   * 
   * @return         The iterator.
   */
  public Iterator<E> iterator() {
    return new IntrusiveIterator();
  }

  @Override
  public int size() {
    return size;
  }

  @Override
  public boolean isEmpty() {
    return size == 0;
  }

  @Override
  public boolean contains(Object o) {
    try {
      Element element = (Element)o;
      return element.isInList(this);
    } catch (ClassCastException e) {
      return false;
    }
  }

  @Override
  public Object[] toArray() {
    Object ret[] = new Object[size];
    int i = 0;
    for (Iterator<E> iter = iterator(); iter.hasNext(); ) {
      ret[i++] = iter.next();
    }
    return ret;
  }

  @SuppressWarnings("unchecked")
  @Override
  public <T> T[] toArray(T[] array) {
    if (array.length < size) {
      return (T[])toArray();
    } else {
      int i = 0;
      for (Iterator<E> iter = iterator(); iter.hasNext(); ) {
        array[i++] = (T)iter.next();
      }
    }
    return array;
  }

  /**
   * Add an element to the end of the list.
   * 
   * @param elem     The new element to add.
   * @return add result.
   */
  @Override
  public boolean add(E elem) {
    if (elem == null) {
      return false;
    }
    if (elem.isInList(this)) {
      return false;
    }
    Element prev = root.getPrev(IntrusiveCollection.this);
    prev.setNext(IntrusiveCollection.this, elem);
    root.setPrev(IntrusiveCollection.this, elem);
    elem.insertInternal(IntrusiveCollection.this, prev, root);
    size++;
    return true;
  }

  /**
   * Add an element to the front of the list.
   *
   * @param elem     The new element to add.
   * @return if addFirst success true, not false.
   */
  public boolean addFirst(Element elem) {
    if (elem == null) {
      return false;
    }
    if (elem.isInList(this)) {
      return false;
    }
    Element next = root.getNext(IntrusiveCollection.this);
    next.setPrev(IntrusiveCollection.this, elem);
    root.setNext(IntrusiveCollection.this, elem);
    elem.insertInternal(IntrusiveCollection.this, root, next);
    size++;
    return true;
  }

  public static final Logger LOG =
      LoggerFactory.getLogger(IntrusiveCollection.class);

  @Override
  public boolean remove(Object o) {
    try {
      Element elem = (Element)o;
      if (!elem.isInList(this)) {
        return false;
      }
      removeElement(elem);
      return true;
    } catch (ClassCastException e) {
      return false;
    }
  }

  @Override
  public boolean containsAll(Collection<?> collection) {
    for (Object o : collection) {
      if (!contains(o)) {
        return false;
      }
    }
    return true;
  }

  @Override
  public boolean addAll(Collection<? extends E> collection) {
    boolean changed = false;
    for (E elem : collection) {
      if (add(elem)) {
        changed = true;
      }
    }
    return changed;
  }

  @Override
  public boolean removeAll(Collection<?> collection) {
    boolean changed = false;
    for (Object elem : collection) {
      if (remove(elem)) {
        changed = true;
      }
    }
    return changed;
  }

  @Override
  public boolean retainAll(Collection<?> collection) {
    boolean changed = false;
    for (Iterator<E> iter = iterator();
        iter.hasNext(); ) {
      Element elem = iter.next();
      if (!collection.contains(elem)) {
        iter.remove();
        changed = true;
      }
    }
    return changed;
  }

  /**
   * Remove all elements.
   */
  @Override
  public void clear() {
    for (Iterator<E> iter = iterator(); iter.hasNext(); ) {
      iter.next();
      iter.remove();
    }
  }
}

相关信息

hadoop 源码目录

相关文章

hadoop ApplicationClassLoader 源码

hadoop AsyncDiskService 源码

hadoop AutoCloseableLock 源码

hadoop BasicDiskValidator 源码

hadoop BlockingThreadPoolExecutorService 源码

hadoop CacheableIPList 源码

hadoop ChunkedArrayList 源码

hadoop ClassUtil 源码

hadoop Classpath 源码

hadoop CleanerUtil 源码