public
Last active

Non blocking queue if we have attr_atomic

  • Download Gist
atomic_linked_queue.rb
Ruby
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59
# 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

Please sign in to comment on this gist.

Something went wrong with that request. Please try again.