9.1 Data Types

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.

335. <TRB node structure 335> =
/* 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 333.