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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
|
module Concurrent
# @!macro warn.edge
class LockFreeStack < Synchronization::Object
safe_initialization!
class Node
# TODO (pitr-ch 20-Dec-2016): Could be unified with Stack class?
# @return [Node]
attr_reader :next_node
# @return [Object]
attr_reader :value
# @!visibility private
# allow to nil-ify to free GC when the entry is no longer relevant, not synchronised
attr_writer :value
def initialize(value, next_node)
@value = value
@next_node = next_node
end
singleton_class.send :alias_method, :[], :new
end
# The singleton for empty node
EMPTY = Node[nil, nil]
def EMPTY.next_node
self
end
attr_atomic(:head)
private :head, :head=, :swap_head, :compare_and_set_head, :update_head
# @!visibility private
def self.of1(value)
new Node[value, EMPTY]
end
# @!visibility private
def self.of2(value1, value2)
new Node[value1, Node[value2, EMPTY]]
end
# @param [Node] head
def initialize(head = EMPTY)
super()
self.head = head
end
# @param [Node] head
# @return [true, false]
def empty?(head = head())
head.equal? EMPTY
end
# @param [Node] head
# @param [Object] value
# @return [true, false]
def compare_and_push(head, value)
compare_and_set_head head, Node[value, head]
end
# @param [Object] value
# @return [self]
def push(value)
while true
current_head = head
return self if compare_and_set_head current_head, Node[value, current_head]
end
end
# @return [Node]
def peek
head
end
# @param [Node] head
# @return [true, false]
def compare_and_pop(head)
compare_and_set_head head, head.next_node
end
# @return [Object]
def pop
while true
current_head = head
return current_head.value if compare_and_set_head current_head, current_head.next_node
end
end
# @param [Node] head
# @return [true, false]
def compare_and_clear(head)
compare_and_set_head head, EMPTY
end
include Enumerable
# @param [Node] head
# @return [self]
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
# @return [true, false]
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
# @param [Node] head
# @return [true, false]
def clear_if(head)
compare_and_set_head head, EMPTY
end
# @param [Node] head
# @param [Node] new_head
# @return [true, false]
def replace_if(head, new_head)
compare_and_set_head head, new_head
end
# @return [self]
# @yield over the cleared stack
# @yieldparam [Object] value
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
# @return [String] Short string representation.
def to_s
format '%s %s>', super[0..-2], to_a.to_s
end
alias_method :inspect, :to_s
end
end
|
