Advertisement
bestsss

Multi producer, single consumer stack used as queue

Apr 15th, 2014
123
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 5 2.25 KB | None | 0 0
  1. package bestsss.util;
  2.  
  3. import java.util.Collection;
  4.  
  5. import sun.misc.Unsafe;
  6. /**
  7.  *
  8.  * @author Stanimir Simeonoff
  9.  * The code is in public domain: http://creativecommons.org/publicdomain/zero/1.0/
  10.  *
  11.  * The implementation is a very basic concurrent linked stack with a size field for each node. The top of the stack contains the real size of the stack.
  12.  * During drain() the entire stack is consumed all at once and the result is reversed.
  13. */
  14. public class SCMPLinkedStackAsQueue<E> {
  15.     private final int bound;
  16.     private volatile Node<E> head;
  17.    
  18.     public SCMPLinkedStackAsQueue(int bound) {
  19.       super();
  20.       if (bound<=0) throw new IllegalArgumentException();
  21.       this.bound = bound;
  22.   }
  23.     private static class Node<E> {
  24.         Node<E> next;
  25.         int size;
  26.         final E item;
  27.         Node(E item){
  28.             this.item = item;
  29.         }
  30.     }
  31.     public boolean offer(E e){
  32.         if (e==null)
  33.             throw new NullPointerException();
  34.  
  35.         for(final Node<E> h=new Node<E>(e);;){
  36.             Node<E> node = head;
  37.             int size = node!=null?node.size:0;
  38.             if (++size>bound)
  39.                 return false;
  40.            
  41.             h.size = size;
  42.             h.next = node;         
  43.             if (casHead(node, h)){
  44.                 return true;
  45.             }
  46.         }          
  47.     }
  48.     private boolean casHead(Node<E> cmp, Node<E> val){
  49.         return UNSAFE.compareAndSwapObject(this, headOffset, cmp, val);
  50.     }
  51.     public boolean isEmpty(){return head==null;}
  52.     public int size(){Node<?> node = head; return node!=null?node.size:0;}
  53.    
  54.     @SuppressWarnings("unchecked")
  55.     public Collection<E> drain(){
  56.         for (Node<E> node; null!=(node= head);){//start from the head,
  57.             if (casHead(node, null)){//consume the entire stack,
  58.                 Object[] a=new Object[node.size];//reverse it
  59.                 for (;node!=null;node=node.next)
  60.                     a[node.size-1]=node.item;                  
  61.                
  62.                 return (Collection<E>) java.util.Arrays.asList(a);//and return it
  63.             }
  64.         }
  65.         return java.util.Collections.emptyList();
  66.     }
  67.    
  68.  
  69.     private static final sun.misc.Unsafe UNSAFE;
  70.     private static final long headOffset;
  71.     static {
  72.         try {
  73.             java.lang.reflect.Field f =  sun.misc.Unsafe.class.getDeclaredField("theUnsafe");
  74.             f.setAccessible(true);
  75.             UNSAFE = (Unsafe) f.get(null);                 
  76.             headOffset = UNSAFE.objectFieldOffset(SCMPLinkedStackAsQueue.class.getDeclaredField("head"));
  77.         } catch (Exception e) {
  78.             throw new Error(e);
  79.         }
  80.     }
  81. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement