[数据结构与算法]Workflow（6）

2021SC@SDUSC

? ? ? ? 继续上一篇博客分析，这里用到了红黑树来组织数据，之前在数据结构课程中并没有详细讲解。红黑树在二叉查找树的基础上，增加了一些额外要求：它的根结点必须是黑色；所有叶子结点也是黑色；每个红色节点的两个结节点都是黑色，即从每个叶子到根的路径上不能有两个连续的红色结点；从任一结点到每个叶子的所有路径都包含相同数目的黑色节点。

? ? ? ? ?这些约束是的红黑树从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。在进行插入、删除和查找某个值等操作的最坏情况下它也是高效的。

struct rb_node
{
	struct rb_node *rb_parent;
	struct rb_node *rb_right;
	struct rb_node *rb_left;
	char rb_color;
#define	RB_RED		0
#define	RB_BLACK	1
};

? ? ? ?红黑树结点的定义在src/kernel/rbtree.h中，每个结点有指向父节点、左子节点、右子节点的指针，还增加了对结点颜色的描述来保持操作的高效性。

class WFNSPolicy
{
public:
	virtual WFRouterTask *create_router_task(const struct WFNSParams *params,
											 router_callback_t callback) = 0;

	virtual void success(RouteManager::RouteResult *result,
						 WFNSTracing *tracing,
						 CommTarget *target)
	{
		RouteManager::notify_available(result->cookie, target);
	}

	virtual void failed(RouteManager::RouteResult *result,
						WFNSTracing *tracing,
						CommTarget *target)
	{
		if (target)
			RouteManager::notify_unavailable(result->cookie, target);
	}

public:
	virtual ~WFNSPolicy() { }
};

? ? ? ? ? WFNameService类中有变量RWlock，它定义在src/util/RWLock.h中，利用信号量和条件变量来实现锁，在多线程情况下，保证数据的正确性与一致性。wlock（）获得锁，unlock（）释放锁。

class WFNameService
{
public:
	int add_policy(const char *name, WFNSPolicy *policy);
	WFNSPolicy *get_policy(const char *name);
	WFNSPolicy *del_policy(const char *name);

private:
	WFNSPolicy *default_policy;
	struct rb_root root;
	RWLock rwlock;

private:
	struct WFNSPolicyEntry *get_policy_entry(const char *name);

public:
	WFNameService(WFNSPolicy *default_policy)
	{
		this->root.rb_node = NULL;
		this->default_policy = default_policy;
	}
};

? ? ? ? ?再看看add_policy（）方法的实现代码，while循环寻找应该插入结点的地方，类似二叉树的操作，比较要插入的name和红黑树里结点的name的大小，如果要插入的小，就应该往左子节点继续深入，反之往右节点继续。需要用malloc为新结点开辟一块内存空间，以及确定节点是红色还是黑色，保证从每个叶子到根的路径上不能有两个连续的红色结点；从任一结点到每个叶子的所有路径都包含相同数目的黑色节点。

int WFNameService::add_policy(const char *name, WFNSPolicy *policy)
{
	struct rb_node **p = &this->root.rb_node;
	struct rb_node *parent = NULL;
	struct WFNSPolicyEntry *entry;
	int n, ret = -1;

	this->rwlock.wlock();
	while (*p)
	{
		parent = *p;
		entry = rb_entry(*p, struct WFNSPolicyEntry, rb);
		n = strcasecmp(name, entry->name);
		if (n < 0)
			p = &(*p)->rb_left;
		else if (n > 0)
			p = &(*p)->rb_right;
		else
			break;
	}

	if (!*p)
	{
		size_t len = strlen(name);
		size_t size = offsetof(struct WFNSPolicyEntry, name) + len + 1;

		entry = (struct WFNSPolicyEntry *)malloc(size);
		if (entry)
		{
			memcpy(entry->name, name, len + 1);
			entry->policy = policy;
			rb_link_node(&entry->rb, parent, p);
			rb_insert_color(&entry->rb, &this->root);
			ret = 0;
		}
	}
	else
		errno = EEXIST;

	this->rwlock.unlock();
	return ret;
}

? ? ? 这里的inline将get_policy_entry()指定为内联函数，解决一些频繁调用的函数大量消耗栈空间的问题。函数的逻辑比较便于理解，与二叉树的查找操作十分类似。

inline struct WFNSPolicyEntry *WFNameService::get_policy_entry(const char *name)
{
	struct rb_node *p = this->root.rb_node;
	struct WFNSPolicyEntry *entry;
	int n;

	while (p)
	{
		entry = rb_entry(p, struct WFNSPolicyEntry, rb);
		n = strcasecmp(name, entry->name);
		if (n < 0)
			p = p->rb_left;
		else if (n > 0)
			p = p->rb_right;
		else
			return entry;
	}

	return NULL;
}

? ? ? ? ?这里的get_policy（const char *name）、del_policy（const char *name）方法都需要调用上面的:get_policy_entry(const char *name)，代码逻辑也不难理解，根据key值name，在红黑树中找到对应的结点。

WFNSPolicy *WFNameService::get_policy(const char *name)
{
	WFNSPolicy *policy = this->default_policy;
	struct WFNSPolicyEntry *entry;

	this->rwlock.rlock();
	entry = this->get_policy_entry(name);
	if (entry)
		policy = entry->policy;

	this->rwlock.unlock();
	return policy;
}

WFNSPolicy *WFNameService::del_policy(const char *name)
{
	WFNSPolicy *policy = NULL;
	struct WFNSPolicyEntry *entry;

	this->rwlock.wlock();
	entry = this->get_policy_entry(name);
	if (entry)
	{
		policy = entry->policy;
		rb_erase(&entry->rb, &this->root);
	}

	this->rwlock.unlock();
	free(entry);
	return policy;
}

?

参考资料：

(60条消息) [linux,kernel,rbtree] rb_node 结构体分析_inuyasha1027的专栏-CSDN博客

红黑树_百度百科 (baidu.com)

面试：各种锁的实现原理 - 简书 (jianshu.com)

C++ inline内联函数详解 (biancheng.net)