redblack.cpp

用C 语言编写的红黑树

		node->rb_parent = old->rb_parent;
		node->rb_color = old->rb_color;
		node->rb_right = old->rb_right;
		node->rb_left = old->rb_left;

		if (old->rb_parent)
		{
			if (old->rb_parent->rb_left == old)
				old->rb_parent->rb_left = node;
			else
				old->rb_parent->rb_right = node;
		} else
			root->rb_node = node;

		old->rb_left->rb_parent = node;
		if (old->rb_right)
			old->rb_right->rb_parent = node;
		goto color;
	}

	parent = node->rb_parent;
	color = node->rb_color;

	if (child)
		child->rb_parent = parent;
	if (parent)
	{
		if (parent->rb_left == node)
			parent->rb_left = child;
		else
			parent->rb_right = child;
	}
	else
		root->rb_node = child;

 color:
	if (color == RB_BLACK)
		__rb_erase_color(child, parent, root);
}

#endif	/* _LINUX_RBTREE_H */

test.c
#include <sys/types.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <unistd.h>
#include <errno.h>
#include "rbtree.h"

typedef unsigned int	CORE_ADDR;
typedef struct rb_addr_s {
	rb_node_t	rb_node;
	CORE_ADDR	addr;
}rb_addr_t;

static inline rb_addr_t *
rb_find_addr_struct(CORE_ADDR addr, rb_root_t *root, rb_node_t **ret_parent, rb_node_t ***ret_link)
{
	rb_node_t	**link = &root->rb_node;
	rb_node_t	*parent = NULL;
	rb_addr_t	*rb_addr = NULL;
	rb_addr_t	*ret_rb_addr = NULL;

	while (*link) {
		parent = *link;
		rb_addr = rb_entry(parent, rb_addr_t, rb_node);

		if (addr < rb_addr->addr) {
			link = &(*link)->rb_left;
		}
		else if (addr > rb_addr->addr) {
			link = &(*link)->rb_right;
		}
		else {
			ret_rb_addr = rb_addr;
			break;
		}
	}
	if (ret_parent) {
		*ret_parent = parent;
	}
	if (ret_link) {
		*ret_link = link;
	}

	return(ret_rb_addr);
}

int
rb_insert_addr(CORE_ADDR addr, rb_root_t *root)
{
	rb_node_t	**rb_link;
	rb_node_t	*rb_parent;
	rb_addr_t	*rb_addr = NULL;

	if (rb_find_addr_struct(addr, root, &rb_parent, &rb_link)) {
		return(-1);
	}
	rb_addr = (rb_addr_t *)malloc(sizeof(rb_addr_t));
	if (!rb_addr) {
		return(-1);
	}
	rb_addr->addr = addr;
	rb_link_node(&rb_addr->rb_node, rb_parent, rb_link);
	rb_insert_color(&rb_addr->rb_node, root);

	return(0);
}

int
rb_remove_addr(CORE_ADDR addr, rb_root_t *root)
{
	rb_addr_t	*rb_addr = rb_find_addr_struct(addr, root, NULL, NULL);

	if (!rb_addr) {
		return(-1);
	}
	rb_erase(&rb_addr->rb_node, root);
	free(rb_addr);

	return(0);
}

static inline int
rb_find_addr(CORE_ADDR addr, rb_root_t *root)
{
	rb_node_t	**link = &root->rb_node;
	rb_node_t	*parent = NULL;
	rb_addr_t	*rb_addr;

	while (*link) {
		parent = *link;
		rb_addr = rb_entry(parent, rb_addr_t, rb_node);

		if (addr < rb_addr->addr) {
			link = &(*link)->rb_left;
		}
		else if (addr > rb_addr->addr) {
			link = &(*link)->rb_right;
		}
		else {
			return(1);
		}
	}

	return(0);
}

int
main(int argc,char *argv[], char *envp[])
{
	rb_root_t	addr_root;

	addr_root = RB_ROOT;

	//right insert
	printf("right insert\n");
	if (rb_insert_addr(0x1, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc0028018, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xd014cb68, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x74697277, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc00959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xe3740ffa, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x31321, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x765702, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xf123, &addr_root)) {
		printf("rb_insert_addr error\n");
	}

	//wrong insert
	printf("wrong insert\n");
	if (rb_insert_addr(0x1, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc0028018, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xd014cb68, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x74697277, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xc00959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x959f8, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xe3740ffa, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x31321, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0x765702, &addr_root)) {
		printf("rb_insert_addr error\n");
	}
	if (rb_insert_addr(0xf123, &addr_root)) {
		printf("rb_insert_addr error\n");
	}

	//right find
	printf("right find\n");
	if (rb_find_addr(0x1, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xc0028018, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xd014cb68, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x74697277, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xc00959f8, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x959f8, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xe3740ffa, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x31321, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0x765702, &addr_root)) {
		printf("rb_find_addr ok\n");
	}
	if (rb_find_addr(0xf123, &addr_root)) {
		printf("rb_find_addr ok\n");
	}

	//wrong find
	printf("wrong find\n");
	if (rb_find_addr(0x0, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xc002801, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xd014cb6, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x7469727, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xc00959f, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x959f, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xe3740ff, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x3132, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0x76570, &addr_root)) {
		printf("rb_find_addr error\n");
	}
	if (rb_find_addr(0xf12, &addr_root)) {
		printf("rb_find_addr error\n");
	}

	//right remove
	printf("right remove\n");
	if (rb_remove_addr(0x1, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc0028018, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xd014cb68, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x74697277, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc00959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xe3740ffa, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x31321, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x765702, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xf123, &addr_root)) {
		printf("rb_remove_addr error\n");
	}

	//wrong remove
	printf("wrong remove\n");
	if (rb_remove_addr(0x1, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc0028018, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xd014cb68, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x74697277, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xc00959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x959f8, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xe3740ffa, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x31321, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0x765702, &addr_root)) {
		printf("rb_remove_addr error\n");
	}
	if (rb_remove_addr(0xf123, &addr_root)) {
		printf("rb_remove_addr error\n");
	}

	return(0);
}