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

Inherits:
Object
  • Object
show all
Defined in:
lib-edge/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-edge/concurrent/edge/lock_free_linked_set/window.rb', line 7

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

Instance Attribute Details

#currundocumented



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

def curr
  @curr
end

#predundocumented



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

def pred
  @pred
end

Class Method Details

.find(head, item) ⇒ undocumented

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-edge/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