Sha256: 32adb64a2929c2425145511516bbb840358e6f00713a22a09af440ad6f326e50
Contents?: true
Size: 1.43 KB
Versions: 21
Compression:
Stored size: 1.43 KB
Contents
module Concurrent
module Edge
class LockFreeLinkedSet
class Window
attr_accessor :pred, :curr
def initialize(pred, curr)
@pred, @curr = pred, curr
end
# This method is used to find a 'window' for which `add` and `remove`
# methods can use to know where to add and remove from the list. However,
# it has another responsibilility, which is to physically unlink any
# nodes marked for removal in the set. This prevents adds/removes from
# having to retraverse the list to physically unlink nodes.
def self.find(head, item)
loop do
break_inner_loops = false
pred = head
curr = pred.next_node
loop do
succ, marked = curr.successor_reference.get
# Remove sequence of marked nodes
while marked
removed = pred.successor_reference.compare_and_set curr, succ, false, false
# If could not remove node, try again
break_inner_loops = true && break unless removed
curr = succ
succ, marked = curr.successor_reference.get
end
break if break_inner_loops
# We have found a window
return new pred, curr if curr >= item
pred = curr
curr = succ
end
end
end
end
end
end
end
Version data entries
21 entries across 21 versions & 1 rubygems