HomeFreeBSD

rb_tree: optimize rb_insert

Description

rb_tree: optimize rb_insert

In searching for where to insert a new node, RB_INSERT discards the
address of the pointer that will have to be modified, so that it must
find it again from the values of 'parent' and 'comp'. Stop discarding
that address, and so avoid having to recompute it.

Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36317

(cherry picked from commit b6ce129d24ffe393c43378b1c922d1e56ea2be67)

Details

Provenance
dougmAuthored on Aug 25 2022, 7:26 AM
Reviewer
alc
Differential Revision
D36317: rb_tree: optimize insertion
Parents
rG68ec84dc1bb6: tree(3): allow the compare function to return any signed type
Branches
Unknown
Tags
Unknown