bestsss

ConcurrentLinkedPool (bounded)

May 26th, 2012
166
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.AbstractQueue;
  2. import java.util.Iterator;
  3. import java.util.NoSuchElementException;
  4. import java.util.concurrent.Callable;
  5.  
  6. import java.util.concurrent.atomic.AtomicReference;
  7.  
  8. /**
  9.  * Concurrent stack, useful for implementing pools since the recently added data is more likely to be in the memory cache
  10.  * Cache-hits are good.
  11.  *
  12.  * The pool creates new objects in case it cannot satisfy the pool request by an existing element.
  13.  * The current version is NOT serializable and doesn't support null elements.
  14.  *
  15.  *
  16.  * @author Stanimir Simeonoff
  17.  * @version 1.1
  18.  * @param <E> The desired pooled type
  19.  */
  20. public class ConcurrentLinkedPool<E> extends AbstractQueue<E>{
  21.     final int maxSize;
  22.     final Callable<E> creator;
  23.    
  24.     private static class Node<E> extends AtomicReference<E>{
  25.         private static final long serialVersionUID = -2678632089894452271L;
  26.     //extend AtomicReference instead AtomicFieldUpdater, much simpler and cleaner      
  27.         Node next;
  28.         int size;
  29.         Node(E value){
  30.             lazySet(value);
  31.         }
  32.     }
  33.    
  34.     private final AtomicReference<Node> head=new AtomicReference<Node>();
  35.    
  36.    
  37.     public ConcurrentLinkedPool(int maxSize, Callable<E> creator){
  38.         if (maxSize<1)
  39.             throw new IllegalArgumentException("size too low");
  40.         this.maxSize = maxSize;
  41.         this.creator = creator;
  42.     }
  43.    
  44.     public static <T> ConcurrentLinkedPool<T> newInstance(Class<T> clazz){
  45.         return new ConcurrentLinkedPool<T>(ConcurrentArrayPool.CPUs*2, ConcurrentArrayPool.newCallable(clazz));
  46.     }
  47.    
  48.     protected E newInstance(){
  49.         try {
  50.             return creator.call();
  51.         } catch (Exception e) {
  52.             throw new RuntimeException("failed create instance", e);       
  53.         }
  54.     }
  55.    
  56.     /**
  57.      * the size is atomically updated with the head of the stack and usually it's correct.
  58.      * However, the size is not immediately updated if a node is removed from the middle of the stack
  59.      * until it's relinked by a poll() operation
  60.      * @return current size
  61.      */
  62.    
  63.     public int size(){
  64.         Node n = head.get();
  65.         return n==null?0:n.size;
  66.     }
  67.    
  68.     /**
  69.      * the method never returns null unless newInstance returns so
  70.      * @return the head of stack or a newly creaed instance via newInstance
  71.      */
  72.     public E poll(){
  73.         for(;;){
  74.             final Node<E> node = head.get();
  75.            
  76.             if (node==null){
  77.                 return newInstance();
  78.             }
  79.            
  80.             final E result = node.get();
  81.             if (head.compareAndSet(node, node.next)){              
  82.                 if (result!=null){
  83.                     return result;
  84.                 }
  85.             }
  86.         }
  87.     }
  88.    
  89.     /**
  90.      * Offers the element to the pool. The method ignores null elements.
  91.      * @return true, if successful (i.e. below the capcity), false otheriwse
  92.      */
  93.     public boolean offer(E e){
  94.         if (e==null)
  95.             return false;//silently ignore nulls
  96.  
  97.          
  98.        
  99.         final Node h=new Node(e);
  100.         for(;;){
  101.             Node<E> node = head.get();
  102.             int size = node!=null?node.size:0;
  103.             if (size>=maxSize)
  104.                 return false;
  105.            
  106.             h.next = node;
  107.             h.size = size+1;
  108.             if (head.compareAndSet(node, h)){
  109.                 return true;
  110.             }
  111.         }          
  112.     }
  113.        
  114.     public boolean isEmpty(){
  115.         return head.get()==null;//should be peek()!=null but meh
  116.     }
  117.    
  118.     public void clear() {
  119.         head.set(null);    
  120.     }
  121.    
  122.     public E peek(){
  123.         for(;;){
  124.             Node<E> node = head.get();
  125.             if (node==null){
  126.                 return null;
  127.             }
  128.             E value = node.get();
  129.             if (value!=null)
  130.                 return value;
  131.            
  132.             head.compareAndSet(node, node.next);                   
  133.         }
  134.     }
  135.     /**
  136.      * Provides an ad-hoc possibility to introduce custom equals impl. for instance just ==
  137.      * @param object  - the object passed to methods like contains, remove, etc
  138.      * @param element - already existing object in the stack
  139.      * @return true if the object equals the element, false otherwise
  140.      */
  141.     protected boolean equals(Object object, E element){
  142.         return object==element || object.equals(element);
  143.     }
  144.    
  145.     /**
  146.      * Removes an element from the pool.
  147.      * Note: the size will not be updated immediately.
  148.      * @param o Element to be removed
  149.      * @return true if the pool has been modified, false otherwise; it might return true if another thread is removing the same element
  150.      */
  151.     public boolean remove(Object o){
  152.         for(Node<E> node = head.get();node!=null;node=node.next){      
  153.             E value = node.get();
  154.             if (equals(o, value)){
  155.                 return node.compareAndSet(value, null);
  156.             }
  157.         }      
  158.         return false;
  159.     }
  160.  
  161.     public boolean contains(Object o){
  162.         if (o==null)
  163.             return false;
  164.        
  165.         for(Node<E> node = head.get();node!=null;node=node.next){      
  166.             E value = node.get();
  167.             if (equals(o, value)){
  168.                 return true;
  169.             }
  170.         }      
  171.         return false;
  172.     }
  173.  
  174.     public Iterator<E> iterator(){
  175.         return new Itr();
  176.     }
  177.    
  178.     private class Itr implements Iterator<E> {//stolen from ConcurrentLinkedQueue
  179.         /**
  180.          * Next node to return item for.
  181.          */
  182.         private Node<E> nextNode;
  183.  
  184.         /**
  185.          * nextItem holds on to item fields because once we claim
  186.          * that an element exists in hasNext(), we must return it in
  187.          * the following next() call even if it was in the process of
  188.          * being removed when hasNext() was called.
  189.          */
  190.         private E nextItem;
  191.  
  192.         /**
  193.          * Node of the last returned item, to support remove.
  194.          */
  195.         private Node<E> lastRet;
  196.  
  197.         Itr() {
  198.             advance();
  199.         }
  200.  
  201.         /**
  202.          * Moves to next valid node and returns item to return for
  203.          * next(), or null if no such.
  204.          */
  205.         private E advance() {
  206.             lastRet = nextNode;
  207.             E x = nextItem;
  208.  
  209.             Node<E> p = (nextNode == null)? head.get() : nextNode.next;
  210.             for (;;) {
  211.                 if (p == null) {
  212.                     nextNode = null;
  213.                     nextItem = null;
  214.                     return x;
  215.                 }
  216.                 E item = p.get();
  217.                 if (item != null) {
  218.                     nextNode = p;
  219.                     nextItem = item;
  220.                     return x;
  221.                 } else // skip nulls
  222.                 p = p.next;
  223.             }
  224.         }
  225.  
  226.         public boolean hasNext() {
  227.             return nextNode != null;
  228.         }
  229.  
  230.         public E next() {
  231.             if (nextNode == null) throw new NoSuchElementException();
  232.             return advance();
  233.         }
  234.  
  235.         public void remove() {
  236.             Node<E> l = lastRet;
  237.             if (l == null) throw new IllegalStateException();
  238.             // rely on a future traversal to relink.
  239.             l.set(null);
  240.             lastRet = null;
  241.             if (l==head.get()) head.compareAndSet(l, l.next);//unlink the head immediately
  242.         }
  243.     }
  244. }
RAW Paste Data