Class: Concurrent::Edge::LockFreeLinkedSet::Window

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

Instance Attribute Summary collapse

Class Method Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize(pred, curr) ⇒ Window

Returns a new instance of Window.



7
8
9
 
# File 'lib/concurrent/edge/lock_free_linked_set/window.rb', line 7

def initialize(pred, curr)
  @pred, @curr = pred, curr
end

Instance Attribute Details

#curr ⇒ Object

Returns the value of attribute curr.



5
6
7
 
# File 'lib/concurrent/edge/lock_free_linked_set/window.rb', line 5

def curr
  @curr
end

#pred ⇒ Object

Returns the value of attribute pred.



5
6
7
 
# File 'lib/concurrent/edge/lock_free_linked_set/window.rb', line 5

def pred
  @pred
end

Class Method Details

.find(head, item) ⇒ Object

This method is used to find a ‘window’ for which ‘add` and `remove` methods can use to know where to add and remove from the list. However, it has another responsibilility, which is to physically unlink any nodes marked for removal in the set. This prevents adds/removes from having to retraverse the list to physically unlink nodes.



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
 
# File 'lib/concurrent/edge/lock_free_linked_set/window.rb', line 16

def self.find(head, item)
  loop do
    break_inner_loops = false
    pred = head
    curr = pred.next_node

    loop do
      succ, marked = curr.successor_reference.get

      # Remove sequence of marked nodes
      while marked
        removed = pred.successor_reference.compare_and_set curr, succ, false, false

        # If could not remove node, try again
        break_inner_loops = true && break unless removed

        curr = succ
        succ, marked = curr.successor_reference.get
      end

      break if break_inner_loops

      # We have found a window
      return new pred, curr if curr >= item

      pred = curr
      curr = succ
    end
  end
end