Rev 3243 | Rev 5056 | Go to most recent revision | Show entire file | Regard whitespace | Details | Blame | Last modification | View Log | RSS feed
Rev 3243 | Rev 4103 | ||
---|---|---|---|
Line 66... | Line 66... | ||
66 | extern struct rb_node *rb_next(const struct rb_node *); |
66 | extern struct rb_node *rb_next(const struct rb_node *); |
67 | extern struct rb_node *rb_prev(const struct rb_node *); |
67 | extern struct rb_node *rb_prev(const struct rb_node *); |
68 | extern struct rb_node *rb_first(const struct rb_root *); |
68 | extern struct rb_node *rb_first(const struct rb_root *); |
69 | extern struct rb_node *rb_last(const struct rb_root *); |
69 | extern struct rb_node *rb_last(const struct rb_root *); |
Line -... | Line 70... | ||
- | 70 | ||
- | 71 | /* Postorder iteration - always visit the parent after its children */ |
|
- | 72 | extern struct rb_node *rb_first_postorder(const struct rb_root *); |
|
- | 73 | extern struct rb_node *rb_next_postorder(const struct rb_node *); |
|
70 | 74 | ||
71 | /* Fast replacement of a single node without remove/rebalance/add/rebalance */ |
75 | /* Fast replacement of a single node without remove/rebalance/add/rebalance */ |
72 | extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, |
76 | extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, |
Line 73... | Line 77... | ||
73 | struct rb_root *root); |
77 | struct rb_root *root); |
Line 79... | Line 83... | ||
79 | node->rb_left = node->rb_right = NULL; |
83 | node->rb_left = node->rb_right = NULL; |
Line 80... | Line 84... | ||
80 | 84 | ||
81 | *rb_link = node; |
85 | *rb_link = node; |
Line -... | Line 86... | ||
- | 86 | } |
|
- | 87 | ||
- | 88 | /** |
|
- | 89 | * rbtree_postorder_for_each_entry_safe - iterate over rb_root in post order of |
|
- | 90 | * given type safe against removal of rb_node entry |
|
- | 91 | * |
|
- | 92 | * @pos: the 'type *' to use as a loop cursor. |
|
- | 93 | * @n: another 'type *' to use as temporary storage |
|
- | 94 | * @root: 'rb_root *' of the rbtree. |
|
- | 95 | * @field: the name of the rb_node field within 'type'. |
|
- | 96 | */ |
|
- | 97 | #define rbtree_postorder_for_each_entry_safe(pos, n, root, field) \ |
|
- | 98 | for (pos = rb_entry(rb_first_postorder(root), typeof(*pos), field),\ |
|
- | 99 | n = rb_entry(rb_next_postorder(&pos->field), \ |
|
- | 100 | typeof(*pos), field); \ |
|
- | 101 | &pos->field; \ |
|
- | 102 | pos = n, \ |
|
- | 103 | n = rb_entry(rb_next_postorder(&pos->field), \ |
|
82 | } |
104 | typeof(*pos), field)) |