| /* |
| * 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 com.google.common.base.Preconditions; |
| 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. |
| */ |
| void insertInternal(IntrusiveCollection<? extends Element> list, |
| Element prev, Element next); |
| |
| /** |
| * Set the prev pointer of an element already in the list. |
| */ |
| void setPrev(IntrusiveCollection<? extends Element> list, Element prev); |
| |
| /** |
| * Set the next pointer of an element already in the list. |
| */ |
| 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. |
| */ |
| void removeInternal(IntrusiveCollection<? extends Element> list); |
| |
| /** |
| * Get the prev pointer of an element. |
| */ |
| Element getPrev(IntrusiveCollection<? extends Element> list); |
| |
| /** |
| * Get the next pointer of an element. |
| */ |
| Element getNext(IntrusiveCollection<? extends Element> list); |
| |
| /** |
| * Returns true if this element is in the provided list. |
| */ |
| 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. |
| */ |
| @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. |
| */ |
| 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(); |
| } |
| } |
| } |