9.1 Data Types [ToC] [Index]     [Skip Fwd]     [Prev] [Up] [Next]

To make a RB tree node structure into a threaded RB tree node structure, we just add a pair of tag fields. We also reintroduce a maximum height definition here. It is not used by traversers, only by by the default versions of trb_probe() and trb_delete(), for maximum efficiency.

337. <TRB node structure 337> =
/* Color of a red-black node. */
enum trb_color 
  { TRB_BLACK, /* Black. */ TRB_RED /* Red. */ }; /* Characterizes a link as a child pointer or a thread. */ enum trb_tag
  { TRB_CHILD, /* Child pointer. */ TRB_THREAD /* Thread. */ }; /* An TRB tree node. */ struct trb_node
  { struct trb_node *trb_link[2]; /* Subtrees. */ void *trb_data; /* Pointer to data. */ unsigned char trb_color; /* Color. */ unsigned char trb_tag[2]; /* Tag fields. */ };

This code is included in 335.