rbtree.h 文件参考

XWOS通用库：红黑树 更多...

#include <xwos/standard.h>

rbtree.h 的引用(Include)关系图:

此图展示该文件直接或间接的被哪些文件引用了:

浏览源代码.

结构体
struct	xwlib_rbtree_node
	红黑树节点 更多...
struct	xwlib_rbtree
	红黑树 更多...

宏定义
#define	xwlib_rbtree_get_link(lpc)    ((struct xwlib_rbtree_node **)(((xwptr_t)(lpc)) & (~((xwptr_t)3UL))))
	获取lpc信息中的link指针
#define	xwlib_rbtree_get_lnpos(lpc)   ((xwptr_t)(lpc) & (~((xwptr_t)2UL)))
	获取lpc信息中的link指针和位置信息（屏蔽颜色信息）
#define	xwlib_rbtree_get_pos(lpc)   ((xwptr_t)(((xwptr_t)(lpc)) & (xwptr_t)1UL))
	获取lpc信息中的位置信息
#define	xwlib_rbtree_tst_right(lpc)   (!!xwlib_rbtree_get_pos(lpc))
	测试当前lpc中的位置信息是否为右侧
#define	xwlib_rbtree_tst_left(lpc)   (!xwlib_rbtree_tst_right(lpc))
	测试当前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)
	获取lpc信息中的颜色信息
#define	xwlib_rbtree_tst_black(lpc)   (!!xwlib_rbtree_get_color(lpc))
	测试当前lpc中的颜色信息是否为黑色
#define	xwlib_rbtree_tst_red(lpc)   (!xwlib_rbtree_get_color(lpc))
	测试当前lpc中的颜色信息是否为红色
#define	xwlib_rbtree_entry(ptr, type, member)   xwcc_derof((ptr), type, member)
	从红黑树节点指针值计算出包含该节点成员的外层结构体的指针值

枚举
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 }
	红黑树节点颜色枚举 更多...

函数
static void	xwlib_rbtree_init (struct xwlib_rbtree *rbt)
	初始化红黑树
static void	xwlib_rbtree_init_node (struct xwlib_rbtree_node *rbn)
	初始化红黑树节点
static struct xwlib_rbtree_node *	xwlib_rbtree_get_parent (struct xwlib_rbtree_node *node)
	返回节点的父节点指针
static struct xwlib_rbtree_node *	xwlib_rbtree_get_parent_from_lpc (xwptr_t lpc)
	从lpc信息返回父节点指针
static bool	xwlib_rbtree_tst_root (struct xwlib_rbtree *rbt, struct xwlib_rbtree_node *node)
	测试当前节点是否为根节点
static bool	xwlib_rbtree_tst_link_root (struct xwlib_rbtree *rbt, struct xwlib_rbtree_node **link)
	测试是否连接到根节点（是否为根节点的子节点）
static void	xwlib_rbtree_flip_color (struct xwlib_rbtree_node *node)
	反转节点的颜色
static void	xwlib_rbtree_set_black (struct xwlib_rbtree_node *node)
	将节点设置为黑色
static void	xwlib_rbtree_set_red (struct xwlib_rbtree_node *node)
	将节点设置为红色
static void	xwlib_rbtree_link (struct xwlib_rbtree_node *node, xwptr_t lpc)
	链接节点，并设置位置及颜色信息
static void	xwlib_rbtree_link_nil (struct xwlib_rbtree_node **link)
	链接空（叶子）节点
static struct xwlib_rbtree_node *	xwlib_rbtree_get_predecessor (struct xwlib_rbtree_node *node)
	返回节点的前趋节点
static struct xwlib_rbtree_node *	xwlib_rbtree_get_successor (struct xwlib_rbtree_node *node)
	返回节点的后继节点
static void	xwlib_rbtree_transplant (struct xwlib_rbtree_node *newn, struct xwlib_rbtree_node *oldn)
	用新节点代替旧节点并继承它的链指针、颜色和位置信息， 但新节点并不接管旧节点的子节点
static void	xwlib_rbtree_transplant_nil (struct xwlib_rbtree_node *oldn)
	用叶子(NIL)替换一个旧节点
static bool	xwlib_rbtree_tst_empty (struct xwlib_rbtree *t)
	测试一棵红黑树是否为空树
static bool	xwlib_rbtree_tst_node_unlinked (struct xwlib_rbtree_node *n)
	测试红黑树节点是否已经链接到红黑树中
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)
	用一个新节点代替旧节点，继承它的颜色、位置信息并接管它的子树

详细描述

XWOS通用库：红黑树

作者

• 隐星魂 (Roy Sun) xwos@.nosp@m.xwos.nosp@m..tech

版权所有

• Copyright © 2015 xwos.tech, All Rights Reserved.

  ‍This Source Code Form is subject to the terms of the Mozilla Public License, v. 2.0. If a copy of the MPL was not distributed with this file, You can obtain one at http://mozilla.org/MPL/2.0/.

在文件 rbtree.h 中定义.