typedef struct {
  unsigned red : 1 ;
  unsigned internal : 1 ;
  unsigned left : 1 ;
  unsigned root : 1 ;
  unsigned head : 1 ;
} status;

typedef struct rb_node {
  union {
    struct {
      struct rb_node *flink;
      struct rb_node *blink;
    } list;
    struct {
      struct rb_node *left;
      struct rb_node *right;
    } child;
  } c;
  union {
    struct rb_node *parent;
    struct rb_node *root;
  } p;
  status s;
  union {
    int ikey;
    char *key;
    struct rb_node *lext;
  } k;
  union {
    char *val;
    struct rb_node *rext;
  } v;
} *Rb_node;

extern Rb_node make_rb();
extern Rb_node rb_insert_b(/* node, char *key, char *value */);

extern Rb_node rb_find_key(/* tree, char *key */);
extern Rb_node rb_find_ikey(/* tree, int ikey */);
extern Rb_node rb_find_gkey(/* tree, char *key, cmpfxn */);

extern Rb_node rb_find_key_n(/* tree, char *key, int *found */);
extern Rb_node rb_find_ikey_n(/* tree, int ikey, int *found */);
extern Rb_node rb_find_gkey_n(/* tree, char *key, cmpfxn, int *found */);
extern rb_delete_node(/* node */);
extern rb_free_tree(/* node */);  /* Deletes and frees an entire tree */
extern char *rb_val(/* node */);  /* Returns node->v.val (this is to shut
				     lint up */

#define rb_insert_a(n, k, v) rb_insert_b(n->c.list.flink, k, v)
#define rb_insert(t, k, v) rb_insert_b(rb_find_key(t, k), k, v)
#define rb_inserti(t, k, v) rb_insert_b(rb_find_ikey(t, k), (char *) k, v)
#define rb_insertg(t, k, v, f) rb_insert_b(rb_find_gkey(t, k, f), k, v)
#define rb_first(n) (n->c.list.flink)
#define rb_last(n) (n->c.list.blink)
#define rb_next(n) (n->c.list.flink)
#define rb_prev(n) (n->c.list.blink)
#define rb_empty(t) (t->c.list.flink == t)
#ifndef nil
#define nil(t) (t)
#endif

#define rb_traverse(ptr, lst) \
  for(ptr = rb_first(lst); ptr != nil(lst); ptr = rb_next(ptr))