class Immutable::LazyList

A `LazyList` takes a block that returns a `List`, i.e. an object that responds to `#head`, `#tail` and `#empty?`. The list is only realized (i.e. the block is only called) when one of these operations is performed.

By returning a `Cons` that in turn has a {LazyList} as its tail, one can construct infinite `List`s.

@private

Constants

MUTEX
QUEUE

Public Class Methods

new(&block) click to toggle source
# File lib/immutable/list.rb, line 1311
def initialize(&block)
  @head   = block # doubles as storage for block while yet unrealized
  @tail   = nil
  @atomic = Concurrent::Atom.new(0) # haven't yet run block
  @size   = nil
end

Public Instance Methods

cached_size?() click to toggle source
# File lib/immutable/list.rb, line 1339
def cached_size?
  @size != nil
end
empty?() click to toggle source
# File lib/immutable/list.rb, line 1329
def empty?
  realize if @atomic.value != 2
  @size == 0
end
first()
Alias for: head
head() click to toggle source
# File lib/immutable/list.rb, line 1318
def head
  realize if @atomic.value != 2
  @head
end
Also aliased as: first
length()
Alias for: size
size() click to toggle source
Calls superclass method Immutable::List#size
# File lib/immutable/list.rb, line 1334
def size
  @size ||= super
end
Also aliased as: length
tail() click to toggle source
# File lib/immutable/list.rb, line 1324
def tail
  realize if @atomic.value != 2
  @tail
end

Private Instance Methods

realize() click to toggle source
# File lib/immutable/list.rb, line 1348
def realize
  while true
    # try to "claim" the right to run the block which realizes target
    if @atomic.compare_and_set(0,1) # full memory barrier here
      begin
        list = @head.call
        if list.empty?
          @head, @tail, @size = nil, self, 0
        else
          @head, @tail = list.head, list.tail
        end
      rescue
        @atomic.reset(0)
        MUTEX.synchronize { QUEUE.broadcast }
        raise
      end
      @atomic.reset(2)
      MUTEX.synchronize { QUEUE.broadcast }
      return
    end
    # we failed to "claim" it, another thread must be running it
    if @atomic.value == 1 # another thread is running the block
      MUTEX.synchronize do
        # check value of @atomic again, in case another thread already changed it
        #   *and* went past the call to QUEUE.broadcast before we got here
        QUEUE.wait(MUTEX) if @atomic.value == 1
      end
    elsif @atomic.value == 2 # another thread finished the block
      return
    end
  end
end