1 /* Left-leaning red/black trees */
3 #ifndef OPENAFS_OPR_RBTREE_H
4 #define OPENAFS_OPR_RBTREE_H 1
6 struct opr_rbtree_node
{
7 struct opr_rbtree_node
*left
;
8 struct opr_rbtree_node
*right
;
9 struct opr_rbtree_node
*parent
;
14 struct opr_rbtree_node
*root
;
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
);