HomeFreeBSD

To reduce the size of an rb_node, drop the color field. Set the least

Description

To reduce the size of an rb_node, drop the color field. Set the least
significant bit in the pointer to the node from its parent to indicate
that the node is red. Have the tree rotation macros leave the
old-parent/new-child node red and the new-parent/old-child node black.

This change makes RB_LEFT and RB_RIGHT no longer assignable, and
RB_COLOR no longer defined. Any code that modifies the tree or
examines a node color would have to be modified after this change.

Reviewed by: markj
Tested by: pho
Differential Revision: https://reviews.freebsd.org/D25105

Details

Provenance
dougmAuthored on
Reviewer
markj
Differential Revision
D25105: Replace the rb_color field in an rb_node with a tag in the parent's pointer to the rb_node
Parents
rS361983: MFC r361725, r361728:
Branches
Unknown
Tags
Unknown