From: Liu Yuan <namei.unix at gmail.com> Signed-off-by: Liu Yuan <namei.unix at gmail.com> Reviewed-by: Hitoshi Mitake <mitake.hitoshi at lab.ntt.co.jp> Signed-off-by: MORITA Kazutaka <morita.kazutaka at lab.ntt.co.jp> Conflicts: dog/vdi.c include/rbtree.h sheep/group.c Conflicts were resolved by Hitoshi Mitake. Signed-off-by: Hitoshi Mitake <mitake.hitoshi at lab.ntt.co.jp> --- include/rbtree.h | 113 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 113 insertions(+) diff --git a/include/rbtree.h b/include/rbtree.h index 642d151..aa16be3 100644 --- a/include/rbtree.h +++ b/include/rbtree.h @@ -80,4 +80,117 @@ static inline void rb_link_node(struct rb_node *node, struct rb_node *parent, *rb_link = node; } +/* + * Search for a value in the rbtree. This returns NULL when the key is not + * found in the rbtree. + */ +#define rb_search(root, key, member, compar) \ +({ \ + struct rb_node *__n = (root)->rb_node; \ + typeof(key) __ret = NULL, __data; \ + \ + while (__n) { \ + __data = rb_entry(__n, typeof(*key), member); \ + int __cmp = compar(key, __data); \ + \ + if (__cmp < 0) \ + __n = __n->rb_left; \ + else if (__cmp > 0) \ + __n = __n->rb_right; \ + else { \ + __ret = __data; \ + break; \ + } \ + } \ + __ret; \ +}) + +/* + * Insert a new node into the rbtree. This returns NULL on success, or the + * existing node on error. + */ +#define rb_insert(root, new, member, compar) \ +({ \ + struct rb_node **__n = &(root)->rb_node, *__parent = NULL; \ + typeof(new) __old = NULL, __data; \ + \ + while (*__n) { \ + __data = rb_entry(*__n, typeof(*new), member); \ + int __cmp = compar(new, __data); \ + \ + __parent = *__n; \ + if (__cmp < 0) \ + __n = &((*__n)->rb_left); \ + else if (__cmp > 0) \ + __n = &((*__n)->rb_right); \ + else { \ + __old = __data; \ + break; \ + } \ + } \ + \ + if (__old == NULL) { \ + /* Add new node and rebalance tree. */ \ + rb_link_node(&((new)->member), __parent, __n); \ + rb_insert_color(&((new)->member), root); \ + } \ + \ + __old; \ +}) + +/* + * Search for a value in the rbtree. When the key is not found in the rbtree, + * this returns the next greater node. Note, if key > greatest node, we'll + * return first node. + * + * For an empty tree, we return NULL. + */ +#define rb_nsearch(root, key, member, compar) \ +({ \ + struct rb_node *__n = (root)->rb_node; \ + typeof(key) __ret = NULL, __data; \ + \ + while (__n) { \ + __data = rb_entry(__n, typeof(*key), member); \ + int __cmp = compar(key, __data); \ + \ + if (__cmp < 0) { \ + __ret = __data; \ + __n = __n->rb_left; \ + } else if (__cmp > 0) \ + __n = __n->rb_right; \ + else { \ + __ret = __data; \ + break; \ + } \ + } \ + if (!__ret && !RB_EMPTY_ROOT(root)) \ + __ret = rb_entry(rb_first(root), typeof(*key), member); \ + __ret; \ +}) + +/* Iterate over a rbtree safe against removal of rbnode */ +#define rb_for_each(pos, root) \ + pos = rb_first(root); \ + for (struct rb_node *__n = rb_next(pos); \ + pos && ({ __n = rb_next(pos); 1; }); \ + pos = __n) + +/* Iterate over a rbtree of given type safe against removal of rbnode */ +#define rb_for_each_entry(pos, root, member) \ + for (struct rb_node *__pos = rb_first(root), *__n; \ + __pos && ({ __n = rb_next(__pos); 1; }) && \ + ({ pos = rb_entry(__pos, typeof(*pos), member); 1; }); \ + __pos = __n) + +/* Destroy the tree and free the memory */ +#define rb_destroy(root, type, member) \ +{ \ + type *__dummy; \ + rb_for_each_entry(__dummy, root, member) { \ + rb_erase(&__dummy->member, root); \ + free(__dummy); \ + } \ +} + #endif /* __RBTREE_H_ */ -- 1.7.10.4 |