Class: Concurrent::Edge::LockFreeLinkedSet
- Inherits:
-
Object
- Object
- Concurrent::Edge::LockFreeLinkedSet
- Includes:
- Enumerable
- Defined in:
- lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb,
lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set/node.rb,
lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set/window.rb
Overview
Edge Features are under active development and may change frequently.
- Deprecations are not added before incompatible changes.
- Edge version: major is always 0, minor bump means incompatible change, patch bump means compatible change.
- Edge features may also lack tests and documentation.
- Features developed in
concurrent-ruby-edge
are expected to move toconcurrent-ruby
when finalised.
This class implements a lock-free linked set. The general idea of this implementation is this: each node has a successor which is an Atomic Markable Reference. This is used to ensure that all modifications to the list are atomic, preserving the structure of the linked list under any circumstance in a multithreaded application.
One interesting aspect of this algorithm occurs with removing a node.
Instead of physically removing a node when remove is called, a node is
logically removed, by 'marking it.' By doing this, we prevent calls to
remove
from traversing the list twice to perform a physical removal.
Instead, we have have calls to add
and remove
clean up all marked
nodes they encounter while traversing the list.
This algorithm is a variation of the Nonblocking Linked Set found in 'The Art of Multiprocessor Programming' by Herlihy and Shavit.
Defined Under Namespace
Classes: Head, Node, Tail, Window
Instance Method Summary collapse
-
#<<(item) ⇒ Object
ock_free_linked_list_method_<<.
-
#add(item) ⇒ Boolean
Atomically adds the item to the set if it does not yet exist.
-
#contains?(item) ⇒ Boolean
Atomically checks to see if the set contains an item.
-
#each {|item| ... } ⇒ Object
An iterator to loop through the set.
-
#initialize(initial_size = 0, val = nil) ⇒ LockFreeLinkedSet
constructor
A new instance of LockFreeLinkedSet.
-
#remove(item) ⇒ Boolean
Atomically attempts to remove an item, comparing using
Object#hash
.
Constructor Details
#initialize(initial_size = 0, val = nil) ⇒ LockFreeLinkedSet
Returns a new instance of LockFreeLinkedSet.
28 29 30 31 32 33 34 35 |
# File 'lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb', line 28 def initialize(initial_size = 0, val = nil) @head = Head.new initial_size.times do val = block_given? ? yield : val add val end end |
Instance Method Details
#<<(item) ⇒ Object
ock_free_linked_list_method_<<
Atomically adds the item to the set if it does not yet exist.
72 73 74 75 |
# File 'lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb', line 72 def <<(item) add item self end |
#add(item) ⇒ Boolean
Atomically adds the item to the set if it does not yet exist. Note:
internally the set uses Object#hash
to compare equality of items,
meaning that Strings and other objects will be considered equal
despite being different objects.
that the item was already in the set.
48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 |
# File 'lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb', line 48 def add(item) loop do window = Window.find @head, item pred, curr = window.pred, window.curr # Item already in set return false if curr == item node = Node.new item, curr if pred.successor_reference.compare_and_set curr, node, false, false return true end end end |
#contains?(item) ⇒ Boolean
Atomically checks to see if the set contains an item. This method
compares equality based on the Object#hash
method, meaning that the
hashed contents of an object is what determines equality instead of
Object#object_id
87 88 89 90 91 92 93 94 95 96 |
# File 'lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb', line 87 def contains?(item) curr = @head while curr < item curr = curr.next_node marked = curr.successor_reference.marked? end curr == item && !marked end |
#each {|item| ... } ⇒ Object
An iterator to loop through the set.
132 133 134 135 136 137 138 139 140 141 142 143 144 145 |
# File 'lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb', line 132 def each return to_enum unless block_given? curr = @head until curr.last? curr = curr.next_node marked = curr.successor_reference.marked? yield curr.data unless marked end self end |
#remove(item) ⇒ Boolean
Atomically attempts to remove an item, comparing using Object#hash
.
105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
# File 'lib/concurrent-ruby-edge/concurrent/edge/lock_free_linked_set.rb', line 105 def remove(item) loop do window = Window.find @head, item pred, curr = window.pred, window.curr return false if curr != item succ = curr.next_node removed = curr.successor_reference.compare_and_set succ, succ, false, true #next_node unless removed next unless removed pred.successor_reference.compare_and_set curr, succ, false, false return true end end |