From: Joel VanderWerf <vjoel@...>
Date: 2008-07-10T16:09:27+09:00
Subject: Re: Thread-safe priority queue?

Joel VanderWerf wrote:
> 
> Looks like a race condition in that...

Proposed fix, using a condition var... still needs some eyeballing and 
some tests:

require 'thread'
require 'rbtree'

class PriorityQueue
   def size
     @tree.size
   end

   def initialize(*)
     super
     @tree = MultiRBTree.new
     @que = [] # should never have more than one entry
     @num_waiting = 0
     @mutex = Mutex.new
     @cond = ConditionVariable.new
   end

   # Push +obj+ with priority equal to +pri+ if given or, otherwise,
   # the result of sending #queue_priority to +obj+. Objects are
   # dequeued in priority order, and first-in-first-out among objects
   # with equal priorities.
   def push(obj, pri = obj.queue_priority)
     @mutex.synchronize do
       if @num_waiting > 0
         @que << obj
         @cond.signal
       else
         @tree.store(pri, obj)
       end
     end
   end

   def pop(non_block=false)
     @mutex.synchronize do
       if (last=@tree.last)
         return @tree.delete(last[0]) # highest key, oldest first
       end

       if non_block
         raise ThreadError, "priority queue empty"
       end

       @num_waiting += 1
       @cond.wait(@mutex)
       @num_waiting -= 1
       @que.pop
     end
   end
end



-- 
       vjoel : Joel VanderWerf : path berkeley edu : 510 665 3407