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
|
require 'concurrent/atomic/atomic_markable_reference'
module Concurrent
module Edge
class LockFreeLinkedSet
class Node < Synchronization::Object
include Comparable
safe_initialization!
def initialize(data = nil, successor = nil)
super()
@SuccessorReference = AtomicMarkableReference.new(successor || Tail.new)
@Data = data
@Key = key_for data
end
def data
@Data
end
def successor_reference
@SuccessorReference
end
def key
@Key
end
# Check to see if the node is the last in the list.
def last?
@SuccessorReference.value.is_a? Tail
end
# Next node in the list. Note: this is not the AtomicMarkableReference
# of the next node, this is the actual Node itself.
def next_node
@SuccessorReference.value
end
# This method provides a unqiue key for the data which will be used for
# ordering. This is configurable, and changes depending on how you wish
# the nodes to be ordered.
def key_for(data)
data.hash
end
# We use `Object#hash` as a way to enforce ordering on the nodes. This
# can be configurable in the future; for example, you could enforce a
# split-ordering on the nodes in the set.
def <=>(other)
@Key <=> other.hash
end
end
# Internal sentinel node for the Tail. It is always greater than all
# other nodes, and it is self-referential; meaning its successor is
# a self-loop.
class Tail < Node
def initialize(_data = nil, _succ = nil)
@SuccessorReference = AtomicMarkableReference.new self
end
# Always greater than other nodes. This means that traversal will end
# at the tail node since we are comparing node size in the traversal.
def <=>(_other)
1
end
end
# Internal sentinel node for the Head of the set. Head is always smaller
# than any other node.
class Head < Node
def <=>(_other)
-1
end
end
end
end
end
|
