Class: Concurrent::Edge::LockFreeLinkedSet

Inherits:
Object
  • Object
show all
Includes:
Enumerable
Defined in:
lib/concurrent/edge/lock_free_linked_set.rb,
lib/concurrent/edge/lock_free_linked_set/node.rb,
lib/concurrent/edge/lock_free_linked_set/window.rb

Overview

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



27
28
29
30
31
32
33
34
 
# File 'lib/concurrent/edge/lock_free_linked_set.rb', line 27

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) ⇒ Oject

Atomically adds the item to the set if it does not yet exist.

Parameters:

  • item (Object) —

    the item you wish to insert

Returns:

  • (Oject) —

    the set on which the :<< method was invoked



71
72
73
74
 
# File 'lib/concurrent/edge/lock_free_linked_set.rb', line 71

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



47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/concurrent/edge/lock_free_linked_set.rb', line 47

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



86
87
88
89
90
91
92
93
94
95
 
# File 'lib/concurrent/edge/lock_free_linked_set.rb', line 86

def contains?(item)
  curr = @head

  while curr < item
    curr = curr.next_node
    marked = curr.successor_reference.marked?
  end

  curr == item && !marked
end

#each {|Object| ... } ⇒ Object

An iterator to loop through the set.

Yields:

  • (Object) —

    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



131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/concurrent/edge/lock_free_linked_set.rb', line 131

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



104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
 
# File 'lib/concurrent/edge/lock_free_linked_set.rb', line 104

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