class Contender::LinkedQueue

Public Class Methods

new(capacity = FIXNUM_MAX) click to toggle source
# File lib/contender/linked_queue.rb, line 3
def initialize(capacity = FIXNUM_MAX)
  raise ArgumentError if capacity <= 0

  @capacity = capacity
  # Invariant: head.item == nil
  # Invariant: tail.next == nil
  @head = @tail = Node.new
  @count = Counter.new

  @take_lock = Monitor.new
  @not_empty = @take_lock.new_cond
  @put_lock = Monitor.new
  @not_full = @put_lock.new_cond
end

Public Instance Methods

capacity_remaining() click to toggle source

@return [Integer]

# File lib/contender/linked_queue.rb, line 221
def capacity_remaining
  @capacity - @count.get
end
clear() click to toggle source

@return [undefined]

# File lib/contender/linked_queue.rb, line 139
def clear
  raise NotImplementedError
end
delete(element) click to toggle source

@param [Object] element @return [Boolean]

# File lib/contender/linked_queue.rb, line 151
def delete(element)
  return false if element.nil?

  full_synchronize do
    trail = @head
    interior = trail.next

    while interior
      if element == interior.element
        unlink interior, trail
        return true
      end

      trail = interior
      interior = interior.next
    end
  end

  return false
end
drain_to(target, max_elements = FIXNUM_MAX) click to toggle source

@param [Array] target @param [Integer] max_elements @return [Integer]

# File lib/contender/linked_queue.rb, line 175
def drain_to(target, max_elements = FIXNUM_MAX)
  should_signal = false

  @take_lock.synchronize do
    n = [max_elements, size].min
    i = 0

    head = @head

    begin
      while i < n
        interior = head.next
        target.add interior.element!
        head.next = head
        head = interior

        i += 1
      end

      return n
    ensure
      if i > 0
        @head = head
        should_signal = @count.get_and_add(-i) == capacity
      end
    end
  end
ensure
  signal_not_full if should_signal
end
each(&block) click to toggle source

@yield [Object] @return [undefined]

# File lib/contender/linked_queue.rb, line 145
def each(&block)
  to_a.each &block
end
include?(element) click to toggle source
# File lib/contender/linked_queue.rb, line 206
def include?(element)
  return false if element.nil?

  full_synchronize do
    current = @head.next
    while current
      return true if element == current.element
      current = current.next
    end
  end

  return false
end
offer(element, timeout = nil) click to toggle source

@param [Object] element @param [Float] timeout @return [Boolean]

# File lib/contender/linked_queue.rb, line 21
def offer(element, timeout = nil)
  validate_element element

  count = 0
  node = Node.new element

  @put_lock.synchronize do
    if size == @capacity
      return false unless timeout

      @not_full.wait timeout
      return false if size == @capacity
    end

    enqueue node
    count = @count.increment
    if count < @capacity
      @not_full.signal
    end
  end

  if count > 0
    signal_not_empty
  end

  return true
end
peek() click to toggle source

@return [Object]

# File lib/contender/linked_queue.rb, line 129
def peek
  return if size == 0

  @take_lock.synchronize do
    first = @head.next
    return first.element if first
  end
end
poll(timeout = nil) click to toggle source

@param [Float] timeout @return [Object]

# File lib/contender/linked_queue.rb, line 76
def poll(timeout = nil)
  count = 0
  element = nil

  @take_lock.synchronize do
    if size == 0
      return unless timeout

      @not_empty.wait timeout
      return if size == 0
    end

    element = dequeue
    count = @count.decrement

    if count > 0
      @not_empty.signal
    end
  end

  if count < @capacity
    signal_not_full
  end

  return element
end
put(element) click to toggle source

@param [Object] element @return [undefined]

# File lib/contender/linked_queue.rb, line 51
def put(element)
  validate_element element

  count = 0
  node = Node.new element

  @put_lock.synchronize do
    while size == @capacity
      @not_full.wait
    end

    enqueue node
    count = @count.increment
    if count < @capacity
      @not_full.signal
    end
  end

  if count > 0
    signal_not_empty
  end
end
size() click to toggle source

@return [Integer]

# File lib/contender/linked_queue.rb, line 226
def size
  @count.get
end
take() click to toggle source

@return [Object]

# File lib/contender/linked_queue.rb, line 104
def take
  count = 0
  element = nil

  @take_lock.synchronize do
    while size == 0
      @not_empty.wait
    end

    element = dequeue
    count = @count.decrement

    if count > 0
      @not_empty.signal
    end
  end

  if count < @capacity
    signal_not_full
  end

  return element
end
to_a() click to toggle source

@return [Array]

# File lib/contender/linked_queue.rb, line 231
def to_a
  full_synchronize do
    result = Array.new size

    current = @head.next
    while current
      result.push current.element
      current = current.next
    end

    result
  end
end

Protected Instance Methods

full_synchronize() { || ... } click to toggle source

@yield @return [undefined]

# File lib/contender/linked_queue.rb, line 249
def full_synchronize
  @take_lock.mon_enter
  @put_lock.mon_enter

  begin
    yield
  ensure
    @take_lock.mon_exit
    @put_lock.mon_exit
  end
end

Private Instance Methods

dequeue() click to toggle source

Must have take lock

# File lib/contender/linked_queue.rb, line 302
def dequeue
  head = @head
  first = head.next
  head.next = head # help GC

  @head = first

  first.element!
end
enqueue(node) click to toggle source

Must have put lock

# File lib/contender/linked_queue.rb, line 297
def enqueue(node)
  @tail = @tail.next = node
end
signal_not_empty() click to toggle source
# File lib/contender/linked_queue.rb, line 269
def signal_not_empty
  @take_lock.synchronize do
    @not_empty.signal
  end
end
signal_not_full() click to toggle source
# File lib/contender/linked_queue.rb, line 275
def signal_not_full
  @put_lock.synchronize do
    @not_full.signal
  end
end
validate_element(element) click to toggle source
# File lib/contender/linked_queue.rb, line 263
def validate_element(element)
  if element.nil?
    raise ArgumentError, 'This queue does not support nil elements'
  end
end