817769 - Add priority queue utility class

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Brian Hackett [Laid off!]]

Attachment: patch

Bug 814966 needs an efficient priority queue implementation.  Rather than do this as a one/off implementation it'd be nice to have a generic class.  Heap based priority queues represent a binary tree with a fixed array of data, so a Vector can be used for backing storage and little new logic is required.  (No uses of the class are included in this patch, but with an in progress one for bug 814966 this stuff does actually work).

Comment 1

[Luke Wagner [:luke]]

Comment on attachment 687909 [details] [diff] [review]
patch

Review of attachment 687909 [details] [diff] [review]:
-----------------------------------------------------------------

Looks great!

I remembered after talking on IRC that js/src/ds/PriorityQueue.h might be a better initial place for this since ds/* headers aren't exported whereas, as the name implies, js/public/* headers are and PriorityQueue.h isn't needed outside js/src.

::: js/public/PriorityQueue.h
@@ +125,5 @@
> +                continue;
> +            }
> +
> +            break;
> +        }

Although this loop structure is symmetric with shiftDown, I think it would read a little nicer as:

  while (n > 0) {
    size_t parent = (n - 1) / 2;
    if (P::priority(heap[parent]) >= P::priority(heap[n]))
      break;
    swap(n, parent);
    n = parent;
  }

Comment 2

[Brian Hackett [Laid off!]]

https://hg.mozilla.org/integration/mozilla-inbound/rev/af912a40cd59

Comment 3

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/mozilla-central/rev/af912a40cd59