Change Details

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.

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.

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.