Class: Concurrent::Edge::LockFreeLinkedSet

Inherits:
Object
  • Object
show all
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

Note:

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

Constructor Details

#initialize(initial_size = 0, val = nil) ⇒ LockFreeLinkedSet

Returns a new instance of LockFreeLinkedSet.

Parameters:

  • initial_size (Fixnum) (defaults to: 0) —

    the size of the linked_list to initialize

 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.

Parameters:

  • item (Object) —

    the item you wish to insert

Returns:

  • (Object) —

    the set on which the :<< method was invoked

 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.

Parameters:

  • item (Object) —

    the item you wish to insert

Returns:

  • (Boolean) —

    true if successful. A false return indicates

 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

Parameters:

  • item (Object) —

    the item you to check for presence in the set

Returns:

  • (Boolean) —

    whether or not the item is in the set

 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.

Yields:

  • (item) —

    each item in the set

Yield Parameters:

  • item (Object) —

    the item you to remove from the set

Returns:

  • (Object) —

    self: the linked set on which each was called

 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.

Parameters:

  • item (Object) —

    the item you to remove from the set

Returns:

  • (Boolean) —

    whether or not the item was removed from the set

 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