funny-falcon / atomic_linked_queue.rb

Last active April 12, 2013

# rewrite of https://gist.github.com/jstorimer/5298581  if ruby has Class.attr_atomic
 
  class AtomicLinkedQueue
    class Node
      attr_accessor :item, :successor
      attr_atomic :successor
 
      def initialize(item, successor)
        @item = item
        @successor = successor
      end
    end
    
    attr_reader :head, :tail # may be attr_atomic should provide readers by itself?
    attr_atomic :head, :tail
    def initialize
      @head = @tail = Node.new(item, nil)
    end
    
    def push(item)
      new_node = Item.new(item, nil)
 
      while true
        current_tail = tail_volatile
        current_tail_successor = current_tail.successor
        
        if current_tail_successor.nil?
          if current_tail.successor_cas(nil, new_node)
            tail_cas(current_tail, new_node)
            return true
          end
        else
          tail_cas(current_tail, current_tail_successor)
        end
      end
    end
 
    def pop
      while true
        current_dummy = head
        current_tail = tail
        current_head = current_dummy.successor
 
        if current_dummy == current_tail
          if current_head.nil?
            return nil
          else
            tail_cas(current_tail, current_head)
          end
        elsif head_cas(current_dummy, current_head)
          item = current_head.item
          if item != nil
            current_head.item = nil
          end
          return item
        end
      end
    end
  end