123456789_123456789_123456789_123456789_123456789_

Class: Concurrent::Edge::LockFreeLinkedSet

Relationships & Source Files
Namespace Children
Classes:
Head, Node, Tail, Window
Super Chains via Extension / Inclusion / Inheritance
Instance Chain:
self, Enumerable
Inherits: Object
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.

Class Method Summary

Instance Method Summary

Constructor Details

.new(initial_size = 0, val = nil) ⇒ LockFreeLinkedSet

[ GitHub ] 

  


# 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
    

    
  
    • 





  [ GitHub ]


  

  


# 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
    

    
  
    • 





  [ GitHub ]


  

  


# 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
    

    
  
    • 





  [ GitHub ]


  

  


# 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
    

    
  
    • 





  [ GitHub ]


  

  


# 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
    

    
  
    • 





  [ GitHub ]


  

  


# 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