键值对容器

键值对容器 的协作图:

结构体
struct	xwlib_map_container
	键值对容器 更多...
struct	xwlib_map
	键值对集合 更多...

宏定义
#define	xwlib_map_itr_forward(map, c)
	向前遍历(从小到大)键值对容器
#define	xwlib_map_itr_backward(map, c)
	向后遍历(从大到小)键值对容器
#define	xwlib_map_itr_forward_safe(map, c, n)
	向前遍历(从小到大)键值对容器，并防止因遍历到的容器被删除而造成的错误
#define	xwlib_map_itr_backward_safe(map, c, n)
	向后遍历(从大到小)键值对容器，并防止因遍历到的容器被删除而造成的错误

类型定义
typedef xwssq_t(*	xwlib_map_cmp_f) (void *, void *)
	键比较函数类型

函数
static void	xwlib_map_init (struct xwlib_map *map, xwlib_map_cmp_f cmp)
	初始化键值对容器的map
static void	xwlib_map_init_container (struct xwlib_map_container *mc, void *key, void *value)
	初始化键值对容器
xwer_t	xwlib_map_insert (struct xwlib_map *map, struct xwlib_map_container *newmc)
	插入键值对容器
xwer_t	xwlib_map_erase (struct xwlib_map *map, struct xwlib_map_container *mc)
	删除键值对容器
xwer_t	xwlib_map_find (struct xwlib_map *map, void *key, struct xwlib_map_container **mcbuf)
	根据 键值 查找容器

详细描述

概述

map是按从 小 到 大 排列的键值对容器的集合。在map中， 键 是唯一的。

宏定义说明

xwlib_map_itr_backward

#define xwlib_map_itr_backward	(		map,
			c
	)

值:

        xwlib_bclst_itr_next_entry((c), \
                                   &(map)->bclh, \
                                   struct xwlib_map_container, bcln)

向后遍历(从大到小)键值对容器

参数

[in]	map	map指针
[in]	c	光标指针，指向当前遍历到的键值对容器

在文件 map.h 第 97 行定义.

xwlib_map_itr_backward_safe

#define xwlib_map_itr_backward_safe	(		map,
			c,
			n
	)

值:

        xwlib_bclst_itr_prev_entry_safe((c), (n), \
                                        &(map)->bclh, \
                                        struct xwlib_map_container, bcln)

向后遍历(从大到小)键值对容器，并防止因遍历到的容器被删除而造成的错误

参数

[in]	map	map指针
[in]	c	光标指针，指向当前遍历到的键值对容器
[in]	n	键值对容器的指针，用于宏内部暂存数据

在文件 map.h 第 119 行定义.

xwlib_map_itr_forward

#define xwlib_map_itr_forward	(		map,
			c
	)

值:

        xwlib_bclst_itr_next_entry((c), \
                                   &(map)->bclh, \
                                   struct xwlib_map_container, bcln)

向前遍历(从小到大)键值对容器

参数

[in]	map	map指针
[in]	c	光标指针，指向当前遍历到的键值对容器

在文件 map.h 第 87 行定义.

xwlib_map_itr_forward_safe

#define xwlib_map_itr_forward_safe	(		map,
			c,
			n
	)

值:

        xwlib_bclst_itr_next_entry_safe((c), \
                                        &(map)->bclh, \
                                        struct xwlib_map_container, bcln)

向前遍历(从小到大)键值对容器，并防止因遍历到的容器被删除而造成的错误

参数

[in]	map	map指针
[in]	c	光标指针，指向当前遍历到的键值对容器
[in]	n	键值对容器的指针，用于宏内部暂存数据

在文件 map.h 第 108 行定义.

类型定义说明

xwlib_map_cmp_f

typedef xwssq_t(* xwlib_map_cmp_f) (void *, void *)

键比较函数类型

在文件 map.h 第 42 行定义.

函数说明

xwlib_map_erase()

xwer_t xwlib_map_erase	(	struct xwlib_map *	map,
		struct xwlib_map_container *	mc
	)

删除键值对容器

参数

[in]	map	map的指针
[in]	mc	待删除的键值对容器的指针

返回

错误码

返回值

XWOK	没有错误
-ESRCH	此键值对容器不在键值对集合中

<No error

在文件 map.c 第 70 行定义.

{
        xwer_t rc;
 
        if (xwlib_rbtree_tst_node_unlinked(&mc->rbn)) {
                rc = -ESRCH;
        } else {
                xwlib_rbtree_remove(&map->rbtree, &mc->rbn);
                xwlib_rbtree_init_node(&mc->rbn);
                xwlib_bclst_del_init(&mc->bcln);
                rc = XWOK;
        }
        return rc;
}

函数调用图:

xwlib_map_find()

xwer_t xwlib_map_find	(	struct xwlib_map *	map,
		void *	key,
		struct xwlib_map_container **	mcbuf
	)

根据 键值 查找容器

参数

[in]	map	map的指针
[in]	key	键值对容器的指针
[out]	mcbuf	指向指针缓存的指针，此指针缓存用于返回查找到的键值对容器的指针

返回

错误码

返回值

XWOK	没有错误
-ESRCH	目标不存在

<No error

在文件 map.c 第 86 行定义.

{
        struct xwlib_rbtree_node * rbn;
        struct xwlib_map_container * mc;
        xwssq_t cmprc;
        xwer_t rc;
 
        rbn = map->rbtree.root;
        while (NULL != rbn) {
                mc = xwlib_rbtree_entry(rbn, struct xwlib_map_container, rbn);
                cmprc = map->cmp(key, mc->key);
                if (cmprc < 0) {
                        rbn = rbn->left;
                } else if (cmprc > 0) {
                        rbn = rbn->right;
                } else {
                        break;
                }
        }
        if (NULL != rbn) {
                *mcbuf = xwlib_rbtree_entry(rbn, struct xwlib_map_container, rbn);
                rc = XWOK;
        } else {
                *mcbuf = NULL;
                rc = -ESRCH;
        }
        return rc;
}

xwlib_map_init()

static void xwlib_map_init ( struct xwlib_map *  map, xwlib_map_cmp_f  cmp  )

inlinestatic

初始化键值对容器的map

参数

[in]	map	map指针
[in]	cmp	比较键大小的函数指针

在文件 map.h 第 59 行定义.

{
        xwlib_rbtree_init(&map->rbtree);
        xwlib_bclst_init_head(&map->bclh);
        map->cmp = cmp;
}

函数调用图:

xwlib_map_init_container()

static void xwlib_map_init_container ( struct xwlib_map_container *  mc, void *  key, void *  value  )

inlinestatic

初始化键值对容器

参数

[in]	mc	键值对容器的指针
[in]	key	键
[in]	value	值

在文件 map.h 第 73 行定义.

{
        xwlib_rbtree_init_node(&mc->rbn);
        xwlib_bclst_init_node(&mc->bcln);
        mc->key = key;
        mc->value = value;
}

函数调用图:

xwlib_map_insert()

xwer_t xwlib_map_insert	(	struct xwlib_map *	map,
		struct xwlib_map_container *	newmc
	)

插入键值对容器

参数

[in]	map	map的指针
[in]	newmc	待插入的键值对容器的指针

返回

错误码

返回值

XWOK	没有错误
-EEXIST	键值对已经存在

<No error

在文件 map.c 第 17 行定义.

{
        struct xwlib_rbtree_node ** pos;
        struct xwlib_rbtree_node * rbn;
        struct xwlib_map_container * mc;
        struct xwlib_map_container * parent;
        xwptr_t lpc;
        xwssq_t cmprc;
        xwer_t rc;
 
        pos = &map->rbtree.root;
        lpc = (xwptr_t)pos;
        rbn = *pos;
        while (NULL != rbn) {
                mc = xwlib_rbtree_entry(rbn, struct xwlib_map_container, rbn);
                cmprc = map->cmp(newmc->key, mc->key);
                if (cmprc < 0) {
                        pos = &rbn->left;
                        lpc = (xwptr_t)pos;
                        rbn = rbn->left;
                } else if (cmprc > 0) {
                        pos = &rbn->right;
                        lpc = (xwptr_t)pos | (xwptr_t)XWLIB_RBTREE_POS_RIGHT;
                        rbn = rbn->right;
                } else {
                        lpc = (xwptr_t)0;
                        break;
                }
        }
        if ((xwptr_t)0 != lpc) {
                if (xwlib_rbtree_tst_link_root(&map->rbtree,
                                               xwlib_rbtree_get_link(lpc))) {
                        xwlib_bclst_add_head(&map->bclh, &newmc->bcln);
                } else {
                        rbn = xwlib_rbtree_get_parent_from_lpc(lpc);
                        parent = xwlib_rbtree_entry(rbn, struct xwlib_map_container,
                                                    rbn);
                        if (xwlib_rbtree_tst_left(lpc)) {
                                xwlib_bclst_add_front(&newmc->bcln, &parent->bcln);
                        } else {
                                xwlib_bclst_add_behind(&newmc->bcln, &parent->bcln);
                        }
                }
                xwlib_rbtree_link(&newmc->rbn, lpc);
                xwlib_rbtree_insert_color(&map->rbtree, &newmc->rbn);
                rc = XWOK;
        } else {
                rc = -EEXIST;
        }
        return rc;
}

函数调用图: