src/opr/rbtree.h

   1 /* Left-leaning red/black trees */
   2
   3 #ifndef OPENAFS_OPR_RBTREE_H
   4 #define OPENAFS_OPR_RBTREE_H 1
   5
   6 struct opr_rbtree_node {
   7     struct opr_rbtree_node *left;
   8     struct opr_rbtree_node *right;
   9     struct opr_rbtree_node *parent;
  10     int red;
  11 };
  12
  13 struct opr_rbtree {
  14     struct opr_rbtree_node *root;
  15 };
  16
  17 extern void opr_rbtree_init(struct opr_rbtree *head);
  18 extern struct opr_rbtree_node *opr_rbtree_first(struct opr_rbtree *head);
  19 extern struct opr_rbtree_node *opr_rbtree_last(struct opr_rbtree *head);
  20 extern struct opr_rbtree_node *opr_rbtree_next(struct opr_rbtree_node *node);
  21 extern struct opr_rbtree_node *opr_rbtree_prev(struct opr_rbtree_node *node);
  22 extern void opr_rbtree_insert(struct opr_rbtree *head,
  23                               struct opr_rbtree_node *parent,
  24                               struct opr_rbtree_node **childptr,
  25                               struct opr_rbtree_node *node);
  26 extern void opr_rbtree_remove(struct opr_rbtree *head,
  27                               struct opr_rbtree_node *node);
  28 extern void opr_rbtree_replace(struct opr_rbtree *head,
  29                                struct opr_rbtree_node *old,
  30                                struct opr_rbtree_node *replacement);
  31
  32 #endif