nsTArray should have a Sort() method that takes a function pointer.

NEW
Assigned to

Status

()

enhancement
P5
normal
6 years ago
10 days ago

People

(Reporter: tbsaunde, Assigned: sankha)

Tracking

(Blocks 1 bug)

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [lang=c++])

Attachments

(2 attachments, 4 obsolete attachments)

(Reporter)

Description

6 years ago
nsCOMArray has it, and you don't always want to bother with a class just so you can sort an array.
(Assignee)

Comment 1

6 years ago
Assignee: nobody → sankha93
Attachment #691808 - Flags: feedback?(trev.saunders)
(Reporter)

Comment 2

6 years ago
Comment on attachment 691808 [details] [diff] [review]
sort method with function pointer

> #include "nsAlgorithm.h"
> #include "nscore.h"
>+#include "nsVoidArray.h"

please don't include that here.

>+  // A variation on the Sort method that uses a function pointer directly
>+  // to compare the elements
>+  // @param aFunc The comparator function

it would be more useful if this comment described how the function is supposed to behave.

>+  void Sort(nsVoidArrayComparatorFunc aFunc, void* aData) {

define your own typedef that takes pointers to the element type.
Attachment #691808 - Flags: feedback?(trev.saunders)
(Assignee)

Comment 3

6 years ago
Attachment #691808 - Attachment is obsolete: true
Attachment #692577 - Flags: feedback?(trev.saunders)
(Reporter)

Comment 4

6 years ago
Comment on attachment 692577 [details] [diff] [review]
sort method with function pointer

>+  typedef int (* aComparatorFunc)
>+            (const void* aElement1, const void* aElement2, void* aData);

elem_type* please

>+  // @param aFunc The comparator function

nit, describe how it should behave?
Attachment #692577 - Flags: feedback?(trev.saunders) → feedback+
(Assignee)

Comment 5

6 years ago
Attachment #692577 - Attachment is obsolete: true
Attachment #692905 - Flags: review?(trev.saunders)
(Reporter)

Comment 6

6 years ago
Comment on attachment 692905 [details] [diff] [review]
Addresses the previous comments

aData) {
>+        NS_QuickSort(Elements(), Length(), sizeof(elem_type),
>+                 aFunc, aData);

I'm  dubius that compiles without a cast, but if it does that's cool.

I'm not a xpcom peer so over to jlebar who is.
Attachment #692905 - Flags: review?(trev.saunders) → review?(justin.lebar+bug)
Is this going to be used somewhere?  I'd rather not add a method without using it in a least one place; YAGNI.

Sankha, perhaps you could modify one of the existing calls to Sort() to use this new method, if you can find one where the use of the comparator class is onerous.
Thanks for writing this patch!

>+  typedef int (* aComparatorFunc)
>+            (const elem_type* aElement1, const elem_type* aElement2, void* aData);

|aFoo| is reserved for argument names.  We don't use |aFoo| for type names.
This should be |ComparatorFunc|.

Please wrap your lines at 80 characters.  When wrapping long lines, we prefer
not to indent an arbitrary amount (as the line beginning with "const elem_type"
is indented).  Instead, we'd prefer something like

>   typedef int (* aComparatorFunc) (const elem_type* aElement1,
>                                    const elem_type* aElement2, void* aData);

so the args line up nicely.

>+  // Sort method that sorts the elements of an array using a function
>+  // pointer passed to it as a parameter

Nit: Period at the end of the sentence, please.

>+  // @param aFunc The comparator function that takes the two elements to compare 
>+  // as first two function parameters followed by an other parameter to be passed 
>+  // to the comparator function

s/an other/another

This still does not explain how the comparator function is supposed to behave.
What we mean is, what is the comparator function supposed to return, and under
what circumstances?

>+  // @param aData Any additional data that needs to be passed on to the 
>+  // comparator function
>+  void Sort(aComparatorFunc aFunc, void* aData) {
>+        NS_QuickSort(Elements(), Length(), sizeof(elem_type),
>+                 aFunc, aData);
>+  }

Again, please line up |aFunc| so it's below the "E" in "Elements()".

> I'm dubious that compiles without a cast, but if it does that's cool.

OOC, what cast where you worried about here?  I'm kind of surprised you can
implicitly cast a ComparatorFunc to an |int (*fn)(const void*, const void*,
void*)|, but if it works, that's fine.
Attachment #692905 - Flags: review?(justin.lebar+bug) → feedback+
(Reporter)

Comment 9

6 years ago
(In reply to Justin Lebar [:jlebar] from comment #7)
> Is this going to be used somewhere?  I'd rather not add a method without
> using it in a least one place; YAGNI.
> 
> Sankha, perhaps you could modify one of the existing calls to Sort() to use
> this new method, if you can find one where the use of the comparator class
> is onerous.

I filed this because of the one added in bug 792566, but I think that just used nsQuickSort() directly instead of bothering with a class.
(Assignee)

Comment 10

6 years ago
Posted patch WIP patch (obsolete) — Splinter Review
I have made the suggested changes as well as changed the implementation of bug 792566. But it refuses to compile with that change. I would have asked on IRC, but you were away. Here is the build error I am getting: http://pastebin.mozilla.org/2061328

Please help.
Attachment #692905 - Attachment is obsolete: true
Attachment #702301 - Flags: feedback?(trev.saunders)
Attachment #702301 - Flags: feedback?(justin.lebar+bug)
Comment on attachment 702301 [details] [diff] [review]
WIP patch

> error: no matching function for call to ‘nsTArray<nsCOMPtr<nsIFile>
> >::Sort(int (*&)(const void*, const void*, void*), std::nullptr_t)’

> no known conversion for argument 1 from ‘int (*)(const void*, const void*,
> void*)’ to ‘int (*)(const elem_type*, const elem_type*, void*) {aka int
> (*)(const nsCOMPtr<nsIFile>*, const nsCOMPtr<nsIFile>*, void*)}’

So the problem is that your Sort() function takes a Comparator which takes
|const elem_type*| args, while you're passing a function which takes |const
void*| args.
Attachment #702301 - Flags: feedback?(trev.saunders)
Attachment #702301 - Flags: feedback?(justin.lebar+bug)

Comment 12

6 years ago
Hello there,

My friend and I are interested in helping out.  Is this bug still active?  If so, where/how do we begin?

Thanks.
I think Sankha is actively working on this bug.  You may want to find another mentored bug.

(If you want tarray stuff, bug 723228 is not being worked on.)
A problem with the comparators as implemented is that with nsTArray<nsRefPtr<Something> >, the comparator functions get "nsRefPtr<Something>* a", that is not really nice, cause then have to (*a)->prop.

Comment 16

6 years ago
Sir i want to take this bug i am well acquainted with the knowledge of c/c++ and would give my best effort to solve this bug.
(Assignee)

Comment 17

6 years ago
There is some particular problem when I try to adapt this Sort function to the nsFileView class, because it is defined as nsTArray<nsCOMPtr<nsIFile> > like said in comment 15.

I wrote another method for sort that takes elem_type& as the parameters, but it fails to compile. Errors here: http://bit.ly/ZSibb1
Attachment #702301 - Attachment is obsolete: true
Attachment #725233 - Flags: feedback?(trev.saunders)
Attachment #725233 - Flags: feedback?(justin.lebar+bug)
(Reporter)

Comment 18

6 years ago
(In reply to Sankha Narayan Guria from comment #17)
> Created attachment 725233 [details] [diff] [review]
> Compile errors on 2 different methods
> 
> There is some particular problem when I try to adapt this Sort function to
> the nsFileView class, because it is defined as nsTArray<nsCOMPtr<nsIFile> >
> like said in comment 15.
> 
> I wrote another method for sort that takes elem_type& as the parameters, but
> it fails to compile. Errors here: http://bit.ly/ZSibb1

I'm pretty sure those errors came from a slightly different patch than the one you attached, it looks like after those errors you renamed one of the typedefs to ComparatorFuncNext after which the build gets to building nsFileView.cpp for me locally at which point it fails because you haven't changed the type of the functions you has into the sort method.
Comment on attachment 725233 [details] [diff] [review]
Compile errors on 2 different methods

Looks like Trevor has this one covered.
Attachment #725233 - Flags: feedback?(justin.lebar+bug)
Is this bug still active?
Flags: needinfo?(trev.saunders)
(Reporter)

Comment 21

5 years ago
(In reply to Anuj Agarwal [:anujagarwal464] from comment #20)
> Is this bug still active?

I don't think anything's happend on it in a long time, feel free to work on it if you need it or whatever.
Flags: needinfo?(trev.saunders)
(Reporter)

Comment 22

5 years ago
Comment on attachment 725233 [details] [diff] [review]
Compile errors on 2 different methods

I think I commented on this on irc or something...
Attachment #725233 - Flags: feedback?(trev.saunders)
Mentor: trev.saunders
Whiteboard: [mentor=trev.saunders@gmail.com][lang=c++] → [lang=c++]

Comment 23

2 years ago
Hi, I'd like to take up this bug.
I understand we should implement a sorting algorithm to sort arrays, could I be given a description of the problem?
(Reporter)

Comment 24

2 years ago
(In reply to Dean Zhu from comment #23)
> Hi, I'd like to take up this bug.
> I understand we should implement a sorting algorithm to sort arrays, could I
> be given a description of the problem?

not exactly, there's already code to sort the array.  That's nsTArray::Sort() in xpcom/ds/nsTArray.h.  The task is just to add another overload of that function that at this point should probably accept either a function pointer or a lambda and use that instead of operator < or a comparator object to compare the objects in the array.

Then you should find some places where a comparator is only used in one spot as an argument to Sort() and simplify them with this.

Comment 25

2 years ago
ok, I might be a little busy these days but I'll try and get my hands on it as soon as possible

Comment 26

2 years ago
Sorry, for the delay, couldnt get my hands on a computer these days. How should I start?

Comment 27

2 years ago
I've been trying to read about function pointers etc, and I have a few doubts,
1) After the overload, what sort function should I call?
2) What is Elem_type? I've seen its a typedef for E, but I cant find any documentation about it.
3) What should the comparator function take as parameters, and what should it return? I've seen that the implementation above returns an int instead of a bool, and takes and extra parameter aData.

Thank you very much!

Comment 28

2 years ago
I'm calling
> typedef int (* CompareFunc) (elem_type* aElem1, elem_type* aElem2);
> void Sort(CompareFunc Comp) { Sort(*Comp); }
And it does compile, but I'm not sure how the Sort function behaves. Could someone provide some insight?


> I've been trying to read about function pointers etc, and I have a few
> doubts,
> 1) After the overload, what sort function should I call?
Is what I've done correct?

> 2) What is Elem_type? I've seen its a typedef for E, but I cant find any
> documentation about it.
I've seen that E is a template for a smart pointer.

> 3) What should the comparator function take as parameters, and what should
> it return? I've seen that the implementation above returns an int instead of
> a bool, and takes and extra parameter aData.
Still not sure about this.

Comment 29

17 days ago

Hi, I would like to work on this bug. Can anyone assign this to me?

Comment 30

17 days ago

From the previous code and comments this is what I have understood.

  1. The function mustake a function pointer that does the sorting.
  2. The elements to be sorted must be of the type elem_type
  3. Should internally use NS_QuickSort

Here are my doubts.

  1. When NS_QuickSort is doing exactly the same why do we need another function? What are we supposed to do here that NS_QuickSort does not?

  2. elem_type seems to be typedef of class E. I could find class E anywhere.

  3. Much of the code seems to have moved. I couldnt find nsTArray.h in glue/ . Where are we supposed to code this?

(In reply to Srujana Peddinti from comment #30)

  1. When NS_QuickSort is doing exactly the same why do we need another function? What are we supposed to do here that NS_QuickSort does not?

NS_QuickSort requires extracting various bits from nsTArray; it should be more convenient to just ask the array to sort itself, and let the array figure out what needs to be passed to NS_QuickSort.

  1. elem_type seems to be typedef of class E. I could find class E anywhere.

https://searchfox.org/mozilla-central/rev/14dc5b7d8a6da1854b2f9f33f1da77a97368cd54/xpcom/ds/nsTArray.h#857

E is one of the template parameters of nsTArray_Impl.

  1. Much of the code seems to have moved. I couldnt find nsTArray.h in glue/ . Where are we supposed to code this?

Ideally you should see where nsTArray.h is as a result of answer to question 2. :)

Comment 32

17 days ago

Yes, I found nsTArray.h but I wasnt sure if this is the file I have to code in because its folder changed.
So as I have understood, I need to code it in nsTArray.h but in ds/ directory using NS_QuickSort.
And write the necessary tests.

I will be right on it. Is there anything else I have to know?

Comment 33

17 days ago
  1. In nsQuickSort.cpp the function NS_QuickSort() is taking void* and (unsigned)int as first 2 parameters. In the file there is no other declaration of NS_QuickSort(). But in nsTArray.h file the functions Elements(), Length() are passed. How come this works? I ve searched ds/ folder. Couldnt find an alternate declaration.

  2. Also to the NS_QuickSort() function what is the last argument we pass? In the file nsQuickSort.h it was mentioned that it is extra data to pass to comparison function. But I couldn't understand it. Isnt the first argument ie array of elem_type* enough for comparison function to sort the array?

(In reply to Srujana Peddinti from comment #33)

  1. In nsQuickSort.cpp the function NS_QuickSort() is taking void* and (unsigned)int as first 2 parameters. In the file there is no other declaration of NS_QuickSort(). But in nsTArray.h file the functions Elements(), Length() are passed. How come this works? I ve searched ds/ folder. Couldnt find an alternate declaration.

Pointers automatically convert to void*. The result of Length() implicitly converts to unsigned int (and fortunately always fits into unsigned int due to the way nsTArray works).

  1. Also to the NS_QuickSort() function what is the last argument we pass? In the file nsQuickSort.h it was mentioned that it is extra data to pass to comparison function. But I couldn't understand it. Isnt the first argument ie array of elem_type* enough for comparison function to sort the array?

Not if the elements require external data to be sorted. Maybe the elements of the array are indices into some other data structure, and you want to sort the indices in a particular order. See e.g. the use of NS_QuickSort in dom/bindings/BindingUtils.cpp.

Mentor: tbsaunde+mozbugs
Type: defect → enhancement
Priority: -- → P5

I'm pretty sure we already have a sort function in nsTArray that does what this wants.

Comment 36

15 days ago

(In reply to Nathan Froyd [:froydnj] from comment #34)

(In reply to Srujana Peddinti from comment #33)

Pointers automatically convert to void*. The result of Length() implicitly converts to unsigned int (and fortunately always fits into unsigned int due to the way nsTArray works).
How come functions are passed without any arguments? Where are we telling that the array is the argument for Length() function?

Not if the elements require external data to be sorted. Maybe the elements of the array are indices into some other data structure, and you want to sort the indices in a particular order. See e.g. the use of NS_QuickSort in dom/bindings/BindingUtils.cpp.

Yes, this makes sense.

Comment 37

14 days ago

I have read the documentations but I did not understand how to run the gtests on a subset of tests.

I have tried

  1. changing GTEST_FILTER env. variable

  2. mach gtest Testname

  3. Using --gtest_filter= 'Testname' option.

These are the docs I read from.
https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Build_Instructions/GTest
https://github.com/google/googletest/blob/master/googletest/docs/advanced.md#running-test-programs-advanced-options

Can anyone help me out in running gtests?

(In reply to Srujana Peddinti from comment #37)

I have read the documentations but I did not understand how to run the gtests on a subset of tests.

I have tried

  1. changing GTEST_FILTER env. variable

  2. mach gtest Testname

  3. Using --gtest_filter= 'Testname' option.

These are the docs I read from.
https://developer.mozilla.org/en-US/docs/Mozilla/Developer_guide/Build_Instructions/GTest
https://github.com/google/googletest/blob/master/googletest/docs/advanced.md#running-test-programs-advanced-options

Can anyone help me out in running gtests?

The format for the filter is <suite_name>.<test_name>, so for example a command for testing the nsTArray sort function is:

./mach gtest TArray.test_comparator_objects

to run all nsTArray tests you can do:

./mach gtest TArray.*

Comment 39

13 days ago

The compare function in the quicksort function takes void pointers as arguments. But in one of the comments, it was decided to use elem_type pointers. So should I change the compare function declaration in quicksort from void* to elem_type*?

(In reply to Eric Rahm [:erahm] from comment #35)

I'm pretty sure we already have a sort function in nsTArray that does what this wants.

This is supposed to be more generic -- that method works on a type with a int Compare(const elem_type&, const elem_type&) method but this should use anything with the right signature as a comparator like e.g. a lambda.

(In reply to David Parks (dparks) [:handyman] from comment #40)

(In reply to Eric Rahm [:erahm] from comment #35)

I'm pretty sure we already have a sort function in nsTArray that does what this wants.

This is supposed to be more generic -- that method works on a type with a int Compare(const elem_type&, const elem_type&) method but this should use anything with the right signature as a comparator like e.g. a lambda.

nsTArray<int> foo({3, 2, 10});
foo.Sort([](int a, int b) { return a - b; })

works fine.

So is this bug still valid?

(In reply to Masatoshi Kimura [:emk] from comment #42)

So is this bug still valid?

If I understand correctly, no, but it's hard for me to figure out way the original purpose was. At this point we could definitely use better docs for nsTArray::Sort and converting a bunch of one-off comparators to lambdas would be useful (I think that was the original goal).

(In reply to Eric Rahm [:erahm] from comment #41)

nsTArray<int> foo({3, 2, 10});
foo.Sort([](int a, int b) { return a - b; })

works fine.

Ah, I missed that there is an implicitly constructable CompareWrapper class.

You need to log in before you can comment on or make changes to this bug.