Closed Bug 1419217 Opened 2 years ago Closed 2 years ago

Change comparison functions for red-black trees

Categories

(Core :: Memory Allocator, enhancement)

enhancement
Not set

Tracking

()

RESOLVED FIXED
mozilla59
Tracking Status
firefox59 --- fixed

People

(Reporter: glandium, Assigned: glandium)

Details

Attachments

(1 file)

No description provided.
Comment on attachment 8930297 [details]
Bug 1419217 - Change comparison functions for red-black trees.

https://reviewboard.mozilla.org/r/201434/#review206604

Nice change.

::: memory/build/Utils.h:22
(Diff revision 1)
>    using mozilla::tl::CeilingLog2<N>::value;
>    static_assert(1ULL << value == N, "Number is not a power of 2");
>  };
>  #define LOG2(N) Log2<N>::value
>  
> -// Compare two addresses. Returns whether the first address is smaller (-1),
> +enum Order

enum class?

::: memory/build/Utils.h:37
(Diff revision 1)
> -int
> -CompareAddr(T* aAddr1, T* aAddr2)
> +Order
> +CompareInt(T aValue1, T aValue2)
>  {
> -  uintptr_t addr1 = reinterpret_cast<uintptr_t>(aAddr1);
> -  uintptr_t addr2 = reinterpret_cast<uintptr_t>(aAddr2);
> +  static_assert(mozilla::IsIntegral<T>::value, "Type must be integral");
> +  if (aValue1 == aValue2) {
> +    return Order::eEqual;

Won't eEqual be the least frequent result? I suggest checking for eLess and eGreater first, and have eEqual as the fallback, like in Chen's blog post.
Attachment #8930297 - Flags: review?(n.nethercote) → review+
(In reply to Nicholas Nethercote [:njn] from comment #2)
> Comment on attachment 8930297 [details]
> Bug 1419217 - Change comparison functions for red-black trees.
> 
> https://reviewboard.mozilla.org/r/201434/#review206604
> 
> Nice change.
> 
> ::: memory/build/Utils.h:22
> (Diff revision 1)
> >    using mozilla::tl::CeilingLog2<N>::value;
> >    static_assert(1ULL << value == N, "Number is not a power of 2");
> >  };
> >  #define LOG2(N) Log2<N>::value
> >  
> > -// Compare two addresses. Returns whether the first address is smaller (-1),
> > +enum Order
> 
> enum class?

Yes! This even found a missing change in rb.h :)

> ::: memory/build/Utils.h:37
> (Diff revision 1)
> > -int
> > -CompareAddr(T* aAddr1, T* aAddr2)
> > +Order
> > +CompareInt(T aValue1, T aValue2)
> >  {
> > -  uintptr_t addr1 = reinterpret_cast<uintptr_t>(aAddr1);
> > -  uintptr_t addr2 = reinterpret_cast<uintptr_t>(aAddr2);
> > +  static_assert(mozilla::IsIntegral<T>::value, "Type must be integral");
> > +  if (aValue1 == aValue2) {
> > +    return Order::eEqual;
> 
> Won't eEqual be the least frequent result? I suggest checking for eLess and
> eGreater first, and have eEqual as the fallback, like in Chen's blog post.

FWIW, I don't think that makes any practical difference (I think the order is dictated by how the result is used more than how the comparisons are done), but it does make the code nicer, so I'll do it anyways. I actually wrote it with eEqual last originally, then had this weird idea to account for types that have weird definitions of == (like float), but then, those types aren't integral, and eLess wouldn't be the proper fallback anyways.
Pushed by mh@glandium.org:
https://hg.mozilla.org/integration/autoland/rev/c5f14418da24
Change comparison functions for red-black trees. r=njn
https://hg.mozilla.org/mozilla-central/rev/c5f14418da24
Status: NEW → RESOLVED
Closed: 2 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla59
You need to log in before you can comment on or make changes to this bug.