diff options
author | Doug Moore <dougm@FreeBSD.org> | 2022-08-19 23:11:29 +0000 |
---|---|---|
committer | Doug Moore <dougm@FreeBSD.org> | 2022-08-19 23:11:29 +0000 |
commit | 02d0c43c9e53b3055b17719a184a813032040f79 (patch) | |
tree | 9c5d806fb1cf1192f2b94f1f8a4d666bdf5436a4 /sys/net/if_tuntap.c | |
parent | f6cc21e8e14344ca698c19a2931c04867249dd60 (diff) | |
download | src-02d0c43c9e53b3055b17719a184a813032040f79.tar.gz src-02d0c43c9e53b3055b17719a184a813032040f79.zip |
rb_tree: speed-up double rotation
RB_ROTATE_LEFT (and it symmetric twin) modify the rb-tree, adjusting
pointers so that what started as a proper tree ends up a proper
tree. When two consecutive rotations move the same node up the tree,
some of the pointers changed in the first rotation are immediately
changed again in the second - namely, the pointer from the rising node
to its new parent, and the pointer from that parent back to the rising
node. This change removes from RB_ROTATE macros the responsibility for
managing those two pointers, and leaves it to the code that calls for
rotations to fix up those pointers afterward. That drops a comparison
and a pair of assignments from every INSERT_COLOR or REMOVE_COLOR call
that ends in a double rotation.
A side-effect of this change is that the SWAP_CHILD macro must take as
a parameter a pointer to the node that is changing children, where it
is now computed from the old child. Since this macro is called in a
couple of places besides the RB_ROTATE macros, those calls are also
affected.
Reviewed by: alc
MFC after: 3 weeks
Differential Revision: https://reviews.freebsd.org/D36266
Diffstat (limited to 'sys/net/if_tuntap.c')
0 files changed, 0 insertions, 0 deletions