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
|
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
|
