Commit | Line | Data |
---|---|---|
805e021f CE |
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 |