[concurrency-interest] PriorityQueue bug with mutable object

Brian S O'Neill bronee at gmail.com
Thu Jul 2 11:48:28 EDT 2009


I'm not Doug, but personally I would fix the bug by documenting the 
behavior of priority queues. It doesn't make sense to support your use 
case, because it would require that every poll from the queue resort the 
entire heap. This defeats the purpose of using such a structure.

If you have tasks with variable priority, you should use a binary search 
tree instead. Then you can quickly remove and re-insert tasks when its 
priority changes. Call pollFirstEntry to remove the task with highest 
priority.

Manuel Dominguez Sarmiento wrote:
> Hi Doug,
>
> I recently filed the following bug at Sun's bug database:
>
> http://bugs.sun.com/bugdatabase/view_bug.do?bug_id=6856821
>
> You might want to look into it since this class is used by many 
> concurrent classes and you're listed as one of its authors.
>
> I am well aware of the perils of mutable objects, however 
> PriorityQueue should account for mutability since priorities might 
> change for a queued element at runtime, and it is not always practical 
> to remove and discard the previous element and create a new object. 
> This does not only affect mutable objects but also those whose 
> priority is somehow based on System.currentTimeMillis() or other 
> external data, which is what caused us to find this subtle bug.
>
> Best,
>
> Ing. Manuel Dominguez Sarmiento
> Director General
> Renxo S.A.
> e-mail:    mads at renxo.com
> Phone:    +54 11 4719 6806, ext. 104
>
>
> _______________________________________________
> Concurrency-interest mailing list
> Concurrency-interest at cs.oswego.edu
> http://cs.oswego.edu/mailman/listinfo/concurrency-interest
>


More information about the Concurrency-interest mailing list