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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
module Concurrent
module Edge
class LockFreeStack < Synchronization::Object
safe_initialization!
class Node
attr_reader :value, :next_node
def initialize(value, next_node)
@value = value
@next_node = next_node
end
singleton_class.send :alias_method, :[], :new
end
class Empty < Node
def next_node
self
end
end
EMPTY = Empty[nil, nil]
private(*attr_atomic(:head))
def initialize
super()
self.head = EMPTY
end
def empty?
head.equal? EMPTY
end
def compare_and_push(head, value)
compare_and_set_head head, Node[value, head]
end
def push(value)
while true
current_head = head
return self if compare_and_set_head current_head, Node[value, current_head]
end
end
def peek
head
end
def compare_and_pop(head)
compare_and_set_head head, head.next_node
end
def pop
while true
current_head = head
return current_head.value if compare_and_set_head current_head, current_head.next_node
end
end
def compare_and_clear(head)
compare_and_set_head head, EMPTY
end
include Enumerable
def each(head = nil)
return to_enum(:each, head) unless block_given?
it = head || peek
until it.equal?(EMPTY)
yield it.value
it = it.next_node
end
self
end
def clear
while true
current_head = head
return false if current_head == EMPTY
return true if compare_and_set_head current_head, EMPTY
end
end
def clear_each(&block)
while true
current_head = head
return self if current_head == EMPTY
if compare_and_set_head current_head, EMPTY
each current_head, &block
return self
end
end
end
end
end
end
|
