Add heap functions to nsTArray

RESOLVED FIXED

Status

()

Core
XPCOM
--
enhancement
RESOLVED FIXED
9 years ago
7 years ago

People

(Reporter: mwu, Assigned: mwu)

Tracking

(Blocks: 1 bug)

Trunk
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

Attachments

(1 attachment, 2 obsolete attachments)

(Assignee)

Description

9 years ago
In order to take imgLoader.cpp off std:vector/algorithm and use nsTArray, heap functions are necessary.
(Assignee)

Comment 1

9 years ago
Created attachment 419720 [details] [diff] [review]
Add heap functions to nsTArray

Adds Make/Push/Pop Heap functions to nsTArray. Also adds some tests for the new functions.
Attachment #419720 - Flags: review?
(Assignee)

Updated

9 years ago
Attachment #419720 - Flags: review? → review?(benjamin)
Oh man, who decided it was a good idea to use LessThan rather than operator<()? :(

Comment 3

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

Delegating review to joe.
Attachment #419720 - Flags: review?(benjamin) → review?(joe)

Updated

8 years ago
Blocks: 549980
(Assignee)

Comment 4

8 years ago
Created attachment 436047 [details] [diff] [review]
Add heap functions to nsTArray, v2

Now with less crashes
Attachment #419720 - Attachment is obsolete: true
Attachment #436047 - Flags: review?(joe)
Attachment #419720 - Flags: review?(joe)
Comment on attachment 436047 [details] [diff] [review]
Add heap functions to nsTArray, v2

(redirecting to bsmedberg; joe's not an xpcom peer)
Attachment #436047 - Flags: review?(joe) → review?(benjamin)
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)
Attachment #436047 - Flags: review?(benjamin) → review?(joe)
Attachment #436047 - Flags: review?(joe) → review?(roc)
+    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?
(Assignee)

Comment 8

8 years ago
(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.
(Assignee)

Comment 11

8 years ago
Created attachment 441957 [details] [diff] [review]
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.
Attachment #436047 - Attachment is obsolete: true
Attachment #441957 - Flags: review?(roc)
Attachment #436047 - Flags: review?(roc)
Comment on attachment 441957 [details] [diff] [review]
Add heap functions to nsTArray, v3

Yes, please do get rid of nsTPriorityQueue!!
Attachment #441957 - Flags: review?(roc) → review+
This is ready to be checked in, and to have a separate bug to remove nsTPriorityQueue and make its user(s) use nsTArray, right?
(Assignee)

Comment 14

8 years ago
Yup this is ready to check in. You can check it in if you want - otherwise, I'll try to check it in tomorrow.
(Assignee)

Comment 15

8 years ago
http://hg.mozilla.org/mozilla-central/rev/0c65ff82f0e9
Status: NEW → RESOLVED
Last Resolved: 8 years ago
Resolution: --- → FIXED
Depends on: 565748
(Assignee)

Updated

7 years ago
Blocks: 656982
You need to log in before you can comment on or make changes to this bug.