537339 - Add heap functions to nsTArray

Status: RESOLVED FIXED

(Core :: XPCOM, enhancement)

Description

[Michael Wu [:mwu]]

In order to take imgLoader.cpp off std:vector/algorithm and use nsTArray, heap functions are necessary.

Comment 1

[Michael Wu [:mwu]]

Attachment: Add heap functions to nsTArray

Adds Make/Push/Pop Heap functions to nsTArray. Also adds some tests for the new functions.

Comment 2

[Joe Drew (not getting mail)]

Oh man, who decided it was a good idea to use LessThan rather than operator<()? :(

Comment 3

[Benjamin Smedberg]

Comment on attachment 419720 [details] [diff] [review]
Add heap functions to nsTArray

Delegating review to joe.

Comment 4

[Michael Wu [:mwu]]

Attachment: Add heap functions to nsTArray, v2

Now with less crashes

Comment 5

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Comment on attachment 436047 [details] [diff] [review]
Add heap functions to nsTArray, v2

(redirecting to bsmedberg; joe's not an xpcom peer)

Comment 6

[Vladimir Vukicevic [:vlad] [:vladv] (needinfo me, slow to respond)]

Comment on attachment 436047 [details] [diff] [review]
Add heap functions to nsTArray, v2

(back to joe, I should read the bug before moving review requests)

Comment 7

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+    void SiftDown(index_type index, const Item& item, const Comparator& comp) {
+      if (!Length())
+        return;

If Length() is zero, 'index' must be invalid, so why check for Length() being zero?

+      index_type end = Length() - 1;
+      while ((index * 2) < end) {
+        const index_type left = (index * 2) + 1;
+        const index_type right = (index * 2) + 2;

This can't possibly be right. If index*2 is end-1, then 'right' is Length(), so we'll index out of bounds.

It's kinda confusing that "SiftDown" actually moves the element at 'index' *up* in terms of array indices. And where you say "Sift up the new node", we're actually moving it down in array indices. Could you flip your terminology?

Comment 8

[Michael Wu [:mwu]]

(In reply to comment #7)
> +    void SiftDown(index_type index, const Item& item, const Comparator& comp)
> {
> +      if (!Length())
> +        return;
> 
> If Length() is zero, 'index' must be invalid, so why check for Length() being
> zero?
> 
When PopHeap pops the last item it ends up calling SiftDown with nothing in the array. I'll put this check into PopHeap where it's more obvious.

> +      index_type end = Length() - 1;
> +      while ((index * 2) < end) {
> +        const index_type left = (index * 2) + 1;
> +        const index_type right = (index * 2) + 2;
> 
> This can't possibly be right. If index*2 is end-1, then 'right' is Length(), so
> we'll index out of bounds.
> 
Yup. right can't be used without checking if it's valid, which is done for the cases where we need to check right.

> It's kinda confusing that "SiftDown" actually moves the element at 'index' *up*
> in terms of array indices. And where you say "Sift up the new node", we're
> actually moving it down in array indices. Could you flip your terminology?
Well I think this is the standard terminology. If one thinks of the actual binary tree involved with the root node at the top, sifting a node down does move the node down. 

It seems like someone put up another implementation in nsTPriorityQueue.h that does mostly everything but generate a heap, which imgcache needs. Not sure which approach would be preferred.

Comment 9

[Joe Drew (not getting mail)]

(In reply to comment #8)
> It seems like someone put up another implementation in nsTPriorityQueue.h that
> does mostly everything but generate a heap, which imgcache needs. Not sure
> which approach would be preferred.

Holy crap when did that happen!?

Anyways, after a very brief look over it, it seems inadequate[1]. Still, it's probably a reasonable starting point, since it has a user. My suggestion is either to change the nsTPriorityQueue users to use this & remove nsTPriorityQueue, or enhance nsTPriorityQueue and I'll use it in imgLoader.

1. No ability to remove arbitrary elements, which is really my requirement. You have to be a little clever to implement this such that it doesn't need to reheapify on a remove, which can be pretty bad worst case.

Comment 10

[Robert O'Callahan (:roc) (email my personal email if necessary)]

+        if (comp.LessThan(item, elem[left]))
+          if (left < end &&
+              comp.LessThan(elem[left], elem[right]))
+            index = right;
+          else
+            index = left;
+        else if (left < end &&
+                 comp.LessThan(item, elem[right]))
+          index = right;

Use {} around these if bodies, it's in our style guide and it would really help here as well.

+      SiftDown(0, item, comp);

Shouldn't we be passing Elements()[0] here instead of 'item'? I think it would be better/safer to set Elements()[0] explicitly here and remove the 'item' parameter from SiftDown.

Comment 11

[Michael Wu [:mwu]]

Attachment: Add heap functions to nsTArray, v3

Comments addressed. I think we should switch the one user of nsTPriorityQueue to nsTArray. It allows the use of all the other functions in nsTArray and seems more flexible to me. This nsTArray implementation is also a bit more efficient in terms of making less copies during siftup/siftdown operations though that optimization can also be implemented in nsTPriorityQueue.

Comment 12

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 441957 [details] [diff] [review]
Add heap functions to nsTArray, v3

Yes, please do get rid of nsTPriorityQueue!!

Comment 13

[Joe Drew (not getting mail)]

This is ready to be checked in, and to have a separate bug to remove nsTPriorityQueue and make its user(s) use nsTArray, right?

Comment 14

[Michael Wu [:mwu]]

Yup this is ready to check in. You can check it in if you want - otherwise, I'll try to check it in tomorrow.

Comment 15

[Michael Wu [:mwu]]

http://hg.mozilla.org/mozilla-central/rev/0c65ff82f0e9