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

Sean O'Halpin wrote:
> Hi,
> 
> Does anyone know of a solid, thread-safe priority queue implementation in Ruby?
> 
> The only one I can find is Joel Vanderwerf's
> (http://groups.google.com/group/comp.lang.ruby/browse_thread/thread/9d9db98931e4a74f)
> which doesn't work with more recent versions of ruby (because Queue
> implementation changed from Ruby to C).

It's pretty easy to work around, I think. Try the following code. It's 
based on something I'm using in live code and it seems to pass the test 
referenced in the above link.

Btw, it's great that RBTree is a gem now. Thanks to whoever did that.



require 'thread'
require 'rbtree'

class PriorityQueue
   def size
     @tree.size
   end

   def initialize(*)
     super
     @tree = MultiRBTree.new
     @que = Queue.new
     @mutex = Mutex.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 @que.num_waiting > 0
         @que << obj
       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
     end
     @que.pop # wait
   end
end


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