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
unlink(interior, trail)
click to toggle source
Must have full lock
# File lib/contender/linked_queue.rb, line 282 def unlink(interior, trail) # Release the reference to the element interior.clear_element trail.next = interior.next if @tail == interior @tail = trail end if @count.decrement < @capacity @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