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

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

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

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

Now with less crashes

Comment on attachment 436047 [details] [diff] [review] Add heap functions to nsTArray, v2 (redirecting to bsmedberg; joe's not an xpcom peer)

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)

+ 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?

(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.

(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.

+ 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.

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 on attachment 441957 [details] [diff] [review] Add heap functions to nsTArray, v3 Yes, please do get rid of nsTPriorityQueue!!

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

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