rbtree.h

浏览该文件的文档.

 
#ifndef __xwos_lib_rbtree_h__
#define __xwos_lib_rbtree_h__
 
#include <xwos/standard.h>
 
enum xwlib_rbtree_pos_em {
        XWLIB_RBTREE_POS_LEFT = 0, 
        XWLIB_RBTREE_POS_RIGHT = 1, 
};
 
enum xwlib_rbtree_color_em {
        XWLIB_RBTREE_COLOR_RED = 0, 
        XWLIB_RBTREE_COLOR_BLACK = 2, 
};
 
struct __xwcc_alignptr xwlib_rbtree_node {
        struct xwlib_rbtree_node * left; 
        struct xwlib_rbtree_node * right; 
        union {
                struct xwlib_rbtree_node ** link; 
                xwptr_t pos; 
                xwptr_t color; 
                xwptr_t v; 
        } lpc; 
};
 
struct __xwcc_alignptr xwlib_rbtree {
        struct xwlib_rbtree_node * root; 
};
 
static __xwlib_inline
void xwlib_rbtree_init(struct xwlib_rbtree * rbt)
{
        rbt->root = NULL;
}
 
static __xwlib_inline
void xwlib_rbtree_init_node(struct xwlib_rbtree_node * rbn)
{
        rbn->left = NULL;
        rbn->right = NULL;
        rbn->lpc.v = 0;
}
 
#define xwlib_rbtree_get_link(lpc) \
        ((struct xwlib_rbtree_node **)(((xwptr_t)(lpc)) & (~((xwptr_t)3UL))))
 
#define xwlib_rbtree_get_lnpos(lpc)     ((xwptr_t)(lpc) & (~((xwptr_t)2UL)))
 
#define xwlib_rbtree_get_pos(lpc)       ((xwptr_t)(((xwptr_t)(lpc)) & (xwptr_t)1UL))
 
#define xwlib_rbtree_tst_right(lpc)     (!!xwlib_rbtree_get_pos(lpc))
 
#define xwlib_rbtree_tst_left(lpc)      (!xwlib_rbtree_tst_right(lpc))
 
#define xwlib_rbtree_gen_lc(n, color) \
        ((xwptr_t)(&((n)->left)) | (xwptr_t)(color))
 
#define xwlib_rbtree_gen_rc(n, color) \
        ((xwptr_t)(&((n)->right)) | (xwptr_t)(color) | (xwptr_t)XWLIB_RBTREE_POS_RIGHT)
 
#define xwlib_rbtree_gen_lr(n) xwlib_rbtree_gen_lc((n), XWLIB_RBTREE_COLOR_RED)
 
#define xwlib_rbtree_gen_lb(n) xwlib_rbtree_gen_lc((n), XWLIB_RBTREE_COLOR_BLACK)
 
#define xwlib_rbtree_gen_rr(n) xwlib_rbtree_gen_rc((n), XWLIB_RBTREE_COLOR_RED)
 
#define xwlib_rbtree_gen_rb(n) xwlib_rbtree_gen_rc((n), XWLIB_RBTREE_COLOR_BLACK)
 
#define xwlib_rbtree_get_color(lpc)             (((xwptr_t)(lpc)) & (xwptr_t)2UL)
 
#define xwlib_rbtree_tst_black(lpc)             (!!xwlib_rbtree_get_color(lpc))
 
#define xwlib_rbtree_tst_red(lpc)               (!xwlib_rbtree_get_color(lpc))
 
#define xwlib_rbtree_entry(ptr, type, member)   xwcc_derof((ptr), type, member)
 
static __xwlib_inline
struct xwlib_rbtree_node * xwlib_rbtree_get_parent(struct xwlib_rbtree_node * node)
{
        xwptr_t pos;
        struct xwlib_rbtree_node ** link;
 
        pos = xwlib_rbtree_get_pos(node->lpc.pos);
        link = &(xwlib_rbtree_get_link(node->lpc.link)[-pos]);
        return (struct xwlib_rbtree_node *)link;
}
 
static __xwlib_inline
struct xwlib_rbtree_node * xwlib_rbtree_get_parent_from_lpc(xwptr_t lpc)
{
        xwptr_t pos;
        struct xwlib_rbtree_node ** link;
 
        pos = xwlib_rbtree_get_pos(lpc);
        link = &(xwlib_rbtree_get_link(lpc)[-pos]);
        return (struct xwlib_rbtree_node *)link;
}
 
static __xwlib_inline
bool xwlib_rbtree_tst_root(struct xwlib_rbtree * rbt,
                           struct xwlib_rbtree_node * node)
{
        struct xwlib_rbtree_node * p;
 
        p = xwlib_rbtree_get_parent(node);
        return !!(p == (struct xwlib_rbtree_node *)&rbt->root);
}
 
static __xwlib_inline
bool xwlib_rbtree_tst_link_root(struct xwlib_rbtree * rbt,
                                struct xwlib_rbtree_node ** link)
{
        return !!(link == &rbt->root);
}
 
static __xwlib_inline
void xwlib_rbtree_flip_color(struct xwlib_rbtree_node * node)
{
        node->lpc.color ^= (xwptr_t)2UL;
}
 
static __xwlib_inline
void xwlib_rbtree_set_black(struct xwlib_rbtree_node * node)
{
        node->lpc.color |= (xwptr_t)2UL;
}
 
static __xwlib_inline
void xwlib_rbtree_set_red(struct xwlib_rbtree_node * node)
{
        node->lpc.color &= ~((xwptr_t)(2UL));
}
 
static __xwlib_inline
void xwlib_rbtree_link(struct xwlib_rbtree_node * node, xwptr_t lpc)
{
        node->lpc.v = lpc;
        *xwlib_rbtree_get_link(lpc) = node;
}
 
static __xwlib_inline
void xwlib_rbtree_link_nil(struct xwlib_rbtree_node ** link)
{
        *link = NULL;
}
 
static __xwlib_inline
struct xwlib_rbtree_node *
xwlib_rbtree_get_predecessor(struct xwlib_rbtree_node * node)
{
        struct xwlib_rbtree_node * c = node->left;
        if (!c) {
                c = node;
        } else {
                while (NULL != c->right) {
                        c = c->right;
                }
        }
        return c;
}
 
static __xwlib_inline
struct xwlib_rbtree_node *
xwlib_rbtree_get_successor(struct xwlib_rbtree_node * node)
{
        struct xwlib_rbtree_node * c = node->right;
        if (!c) {
                c = node;
        } else {
                while (NULL != c->left) {
                        c = c->left;
                }
        }
        return c;
}
 
static __xwlib_inline
void xwlib_rbtree_transplant(struct xwlib_rbtree_node * newn,
                             struct xwlib_rbtree_node * oldn)
{
        newn->lpc.v = oldn->lpc.v;
        *xwlib_rbtree_get_link(oldn->lpc.v) = newn;
}
 
static __xwlib_inline
void xwlib_rbtree_transplant_nil(struct xwlib_rbtree_node * oldn)
{
        *xwlib_rbtree_get_link(oldn->lpc.v) = NULL;
}
 
static __xwlib_inline
bool xwlib_rbtree_tst_empty(struct xwlib_rbtree * t)
{
        return !!(NULL == t->root);
}
 
static __xwlib_inline
bool xwlib_rbtree_tst_node_unlinked(struct xwlib_rbtree_node * n)
{
        return !!((xwptr_t)0 == n->lpc.v);
}
 
void xwlib_rbtree_insert_color(struct xwlib_rbtree * tree,
                               struct xwlib_rbtree_node * node);
 
void xwlib_rbtree_remove(struct xwlib_rbtree * tree,
                         struct xwlib_rbtree_node * node);
 
void xwlib_rbtree_replace(struct xwlib_rbtree_node * newn,
                          struct xwlib_rbtree_node * oldn);
 
#endif /* xwos/lib/rbtree.h */