Open Bug 1168345 Opened 7 years ago Updated 7 years ago

nsTArray::Sort shouldn't need Equals in the comparator

Categories

(Core :: XPCOM, defect)

defect
Not set
normal

Tracking

()

Tracking Status
firefox41 --- affected

People

(Reporter: gcp, Unassigned)

References

Details

https://dxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h#1790

The Equals function is being called here. This mostly looks like legacy cruft from NS_QuickSort() requiring 0 for equality. Even so it could/should be emulated via LessThan alone, which matches STL better. I think requiring an equals operator for a sort() is very unidiomatic C++.

The Equals being used actually violates the documented API: https://dxr.mozilla.org/mozilla-central/source/xpcom/glue/nsTArray.h#1793

The extra operator makes some other bugs more ugly such as Bug 1135022.
Blocks: 1135022
Will this change the stable sort behavior? IIRC we spent some effort to make sort stable.
>Will this change the stable sort behavior? IIRC we spent some effort to make sort stable.

That's rather strange given that QuickSort isn't a stable sort, generally speaking. Are you sure?

See also bug 1082580.

In any case, Equals can be emulated by checking not(x < y) and not(y < x) so you really only need LessThan (cfr. STL and std::stable_sort)
You need to log in before you can comment on or make changes to this bug.