欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Linux内核中的红黑树

程序员文章站 2024-01-23 18:25:52
...

Table of Contents

rbtree.h

rbtree.c

demo.c


 

rbtree.h

#ifndef __CRTL_BITS_TREE_RBTREE_H
#define __CRTL_BITS_TREE_RBTREE_H 1


#include "crtl/crtl_types.h"

#include "crtl/easy/attribute.h"
#include "crtl/easy/macro.h"




/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <[email protected]>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

  linux/include/linux/rbtree.h

  To use rbtrees you'll have to implement your own insert and search cores.
  This will avoid us to use callbacks and to drop drammatically performances.
  I know it's not the cleaner way,  but in C (not in C++) to get
  performances and genericity...

  Some example of insert and search follows here. The search is a plain
  normal search over an ordered tree. The insert instead must be implemented
  in two steps: First, the code must insert the element in order as a red leaf
  in the tree, and then the support library function rb_insert_color() must
  be called. Such function will do the not trivial work to rebalance the
  rbtree, if necessary.

-----------------------------------------------------------------------
static inline struct page * rb_search_page_cache(struct inode * inode,
						 unsigned long offset)
{
	struct rb_node * n = inode->i_rb_page_cache.rb_node;
	struct page * page;

	while (n)
	{
		page = rb_entry(n, struct page, rb_page_cache);

		if (offset < page->offset)
			n = n->rb_left;
		else if (offset > page->offset)
			n = n->rb_right;
		else
			return page;
	}
	return NULL;
}

static inline struct page * __rb_insert_page_cache(struct inode * inode,
						   unsigned long offset,
						   struct rb_node * node)
{
	struct rb_node ** p = &inode->i_rb_page_cache.rb_node;
	struct rb_node * parent = NULL;
	struct page * page;

	while (*p)
	{
		parent = *p;
		page = rb_entry(parent, struct page, rb_page_cache);

		if (offset < page->offset)
			p = &(*p)->rb_left;
		else if (offset > page->offset)
			p = &(*p)->rb_right;
		else
			return page;
	}

	rb_link_node(node, parent, p);

	return NULL;
}

static inline struct page * rb_insert_page_cache(struct inode * inode,
						 unsigned long offset,
						 struct rb_node * node)
{
	struct page * ret;
	if ((ret = __rb_insert_page_cache(inode, offset, node)))
		goto out;
	rb_insert_color(node, &inode->i_rb_page_cache);
 out:
	return ret;
}
-----------------------------------------------------------------------
*/
#ifndef	_LINUX_RBTREE_H
#define	_LINUX_RBTREE_H 1

#include <stdlib.h>

struct rb_node
{
	unsigned long  rb_parent_color;
#define	RB_RED		0
#define	RB_BLACK	1
	struct rb_node *rb_right;
	struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));
    /* The alignment might seem pointless, but allegedly CRIS needs it */

struct rb_root
{
	struct rb_node *rb_node;
};


#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r)   ((r)->rb_parent_color & 1)
#define rb_is_red(r)   (!rb_color(r))
#define rb_is_black(r) rb_color(r)
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)

static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
	rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
	rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}

#define RB_ROOT	(struct rb_root) { NULL, }
#define	rb_entry(ptr, type, member) container_of(ptr, type, member)

#define RB_EMPTY_ROOT(root)	((root)->rb_node == NULL)
#define RB_EMPTY_NODE(node)	(rb_parent(node) == node)
#define RB_CLEAR_NODE(node)	(rb_set_parent(node, node))

extern void rb_insert_color(struct rb_node *, struct rb_root *);
extern void rb_erase(struct rb_node *, struct rb_root *);

typedef void (*rb_augment_f)(struct rb_node *node, void *data);

extern void rb_augment_insert(struct rb_node *node,
			      rb_augment_f func, void *data);
extern struct rb_node *rb_augment_erase_begin(struct rb_node *node);
extern void rb_augment_erase_end(struct rb_node *node,
				 rb_augment_f func, void *data);

/* Find logical next and previous nodes in a tree */
extern struct rb_node *rb_next(const struct rb_node *);
extern struct rb_node *rb_prev(const struct rb_node *);
extern struct rb_node *rb_first(const struct rb_root *);
extern struct rb_node *rb_last(const struct rb_root *);

/* Fast replacement of a single node without remove/rebalance/add/rebalance */
extern void rb_replace_node(struct rb_node *victim, struct rb_node *new, 
			    struct rb_root *root);

static inline void rb_link_node(struct rb_node * node, struct rb_node * parent,
				struct rb_node ** rb_link)
{
	node->rb_parent_color = (unsigned long )parent;
	node->rb_left = node->rb_right = NULL;

	*rb_link = node;
}

#endif	/* _LINUX_RBTREE_H */


struct crtl_rbtree_struct;
struct crtl_rbtree_node_struct;


/* 红黑树迭代器 */
struct crtl_rbtree_iterator_struct {
    struct crtl_rbtree_struct *rbtree;
    struct crtl_rbtree_node_struct *curr_node;
    void* (*first)(struct crtl_rbtree_iterator_struct *);
    void* (*next)(struct crtl_rbtree_iterator_struct *); 
    void* (*prev)(struct crtl_rbtree_iterator_struct *);
    void* (*last)(struct crtl_rbtree_iterator_struct *);
    
#define __CRTL_RBTREE_ITER_FIRST(p_iter)  p_iter->first(p_iter)
#define __CRTL_RBTREE_ITER_NEXT(p_iter)  p_iter->next(p_iter)
#define __CRTL_RBTREE_ITER_PREV(p_iter)  p_iter->prev(p_iter)
#define __CRTL_RBTREE_ITER_LAST(p_iter)  p_iter->last(p_iter)
    
};





struct crtl_rbtree_struct {
    struct rb_root root;

    unsigned int nnode;

    int (*cmp)(const void *data1, const void*data2);
    int (*display)(const void *data);

    struct crtl_rbtree_iterator_struct iter;
};



struct crtl_rbtree_node_struct {
	struct rb_node  node;
    void            *data;
    unsigned int    data_size;
};





#endif /*<__CRTL_BITS_TREE_RBTREE_H>*/


rbtree.c

#include <malloc.h>
#include <string.h>

#include "crtl/crtl_types.h"

#include "crtl/bits/crtl_tree_rbtree.h"
#include "crtl/crtl_log.h"
#include "crtl/crtl_assert.h"

/*
  Red Black Trees
  (C) 1999  Andrea Arcangeli <[email protected]>
  (C) 2002  David Woodhouse <[email protected]>
  
  This program is free software; you can redistribute it and/or modify
  it under the terms of the GNU General Public License as published by
  the Free Software Foundation; either version 2 of the License, or
  (at your option) any later version.

  This program is distributed in the hope that it will be useful,
  but WITHOUT ANY WARRANTY; without even the implied warranty of
  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  GNU General Public License for more details.

  You should have received a copy of the GNU General Public License
  along with this program; if not, write to the Free Software
  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA

  linux/lib/rbtree.c
*/

#ifndef EXPORT_SYMBOL
#define EXPORT_SYMBOL(v)
#endif

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *right = node->rb_right;
	struct rb_node *parent = rb_parent(node);

	if ((node->rb_right = right->rb_left))
		rb_set_parent(right->rb_left, node);
	right->rb_left = node;

	rb_set_parent(right, parent);

	if (parent)
	{
		if (node == parent->rb_left)
			parent->rb_left = right;
		else
			parent->rb_right = right;
	}
	else
		root->rb_node = right;
	rb_set_parent(node, right);
}

static void __rb_rotate_right(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *left = node->rb_left;
	struct rb_node *parent = rb_parent(node);

	if ((node->rb_left = left->rb_right))
		rb_set_parent(left->rb_right, node);
	left->rb_right = node;

	rb_set_parent(left, parent);

	if (parent)
	{
		if (node == parent->rb_right)
			parent->rb_right = left;
		else
			parent->rb_left = left;
	}
	else
		root->rb_node = left;
	rb_set_parent(node, left);
}

void rb_insert_color(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *parent, *gparent;

	while ((parent = rb_parent(node)) && rb_is_red(parent))
	{
		gparent = rb_parent(parent);

		if (parent == gparent->rb_left)
		{
			{
				register struct rb_node *uncle = gparent->rb_right;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}

			if (parent->rb_right == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_left(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_right(gparent, root);
		} else {
			{
				register struct rb_node *uncle = gparent->rb_left;
				if (uncle && rb_is_red(uncle))
				{
					rb_set_black(uncle);
					rb_set_black(parent);
					rb_set_red(gparent);
					node = gparent;
					continue;
				}
			}

			if (parent->rb_left == node)
			{
				register struct rb_node *tmp;
				__rb_rotate_right(parent, root);
				tmp = parent;
				parent = node;
				node = tmp;
			}

			rb_set_black(parent);
			rb_set_red(gparent);
			__rb_rotate_left(gparent, root);
		}
	}

	rb_set_black(root->rb_node);
}
EXPORT_SYMBOL(rb_insert_color);

static void __rb_erase_color(struct rb_node *node, struct rb_node *parent,
			     struct rb_root *root)
{
	struct rb_node *other;

	while ((!node || rb_is_black(node)) && node != root->rb_node)
	{
		if (parent->rb_left == node)
		{
			other = parent->rb_right;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_left(parent, root);
				other = parent->rb_right;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_right || rb_is_black(other->rb_right))
				{
					rb_set_black(other->rb_left);
					rb_set_red(other);
					__rb_rotate_right(other, root);
					other = parent->rb_right;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				rb_set_black(other->rb_right);
				__rb_rotate_left(parent, root);
				node = root->rb_node;
				break;
			}
		}
		else
		{
			other = parent->rb_left;
			if (rb_is_red(other))
			{
				rb_set_black(other);
				rb_set_red(parent);
				__rb_rotate_right(parent, root);
				other = parent->rb_left;
			}
			if ((!other->rb_left || rb_is_black(other->rb_left)) &&
			    (!other->rb_right || rb_is_black(other->rb_right)))
			{
				rb_set_red(other);
				node = parent;
				parent = rb_parent(node);
			}
			else
			{
				if (!other->rb_left || rb_is_black(other->rb_left))
				{
					rb_set_black(other->rb_right);
					rb_set_red(other);
					__rb_rotate_left(other, root);
					other = parent->rb_left;
				}
				rb_set_color(other, rb_color(parent));
				rb_set_black(parent);
				rb_set_black(other->rb_left);
				__rb_rotate_right(parent, root);
				node = root->rb_node;
				break;
			}
		}
	}
	if (node)
		rb_set_black(node);
}

void rb_erase(struct rb_node *node, struct rb_root *root)
{
	struct rb_node *child, *parent;
	int color;

	if (!node->rb_left)
		child = node->rb_right;
	else if (!node->rb_right)
		child = node->rb_left;
	else
	{
		struct rb_node *old = node, *left;

		node = node->rb_right;
		while ((left = node->rb_left) != NULL)
			node = left;

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

		child = node->rb_right;
		parent = rb_parent(node);
		color = rb_color(node);

		if (parent == old) {
			parent = node;
		} else {
			if (child)
				rb_set_parent(child, parent);
			parent->rb_left = child;

			node->rb_right = old->rb_right;
			rb_set_parent(old->rb_right, node);
		}

		node->rb_parent_color = old->rb_parent_color;
		node->rb_left = old->rb_left;
		rb_set_parent(old->rb_left, node);

		goto color;
	}

	parent = rb_parent(node);
	color = rb_color(node);

	if (child)
		rb_set_parent(child, 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);
}
EXPORT_SYMBOL(rb_erase);

static void rb_augment_path(struct rb_node *node, rb_augment_f func, void *data)
{
	struct rb_node *parent;

up:
	func(node, data);
	parent = rb_parent(node);
	if (!parent)
		return;

	if (node == parent->rb_left && parent->rb_right)
		func(parent->rb_right, data);
	else if (parent->rb_left)
		func(parent->rb_left, data);

	node = parent;
	goto up;
}

/*
 * after inserting @node into the tree, update the tree to account for
 * both the new entry and any damage done by rebalance
 */
void rb_augment_insert(struct rb_node *node, rb_augment_f func, void *data)
{
	if (node->rb_left)
		node = node->rb_left;
	else if (node->rb_right)
		node = node->rb_right;

	rb_augment_path(node, func, data);
}
EXPORT_SYMBOL(rb_augment_insert);

/*
 * before removing the node, find the deepest node on the rebalance path
 * that will still be there after @node gets removed
 */
struct rb_node *rb_augment_erase_begin(struct rb_node *node)
{
	struct rb_node *deepest;

	if (!node->rb_right && !node->rb_left)
		deepest = rb_parent(node);
	else if (!node->rb_right)
		deepest = node->rb_left;
	else if (!node->rb_left)
		deepest = node->rb_right;
	else {
		deepest = rb_next(node);
		if (deepest->rb_right)
			deepest = deepest->rb_right;
		else if (rb_parent(deepest) != node)
			deepest = rb_parent(deepest);
	}

	return deepest;
}
EXPORT_SYMBOL(rb_augment_erase_begin);

/*
 * after removal, update the tree to account for the removed entry
 * and any rebalance damage.
 */
void rb_augment_erase_end(struct rb_node *node, rb_augment_f func, void *data)
{
	if (node)
		rb_augment_path(node, func, data);
}
EXPORT_SYMBOL(rb_augment_erase_end);

/*
 * This function returns the first node (in sort order) of the tree.
 */
struct rb_node *rb_first(const struct rb_root *root)
{
	struct rb_node	*n;

	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_left)
		n = n->rb_left;
	return n;
}
EXPORT_SYMBOL(rb_first);

struct rb_node *rb_last(const struct rb_root *root)
{
	struct rb_node	*n;

	n = root->rb_node;
	if (!n)
		return NULL;
	while (n->rb_right)
		n = n->rb_right;
	return n;
}
EXPORT_SYMBOL(rb_last);

struct rb_node *rb_next(const struct rb_node *node)
{
	struct rb_node *parent;

	if (rb_parent(node) == node)
		return NULL;

	/* If we have a right-hand child, go down and then left as far
	   as we can. */
	if (node->rb_right) {
		node = node->rb_right; 
		while (node->rb_left)
			node=node->rb_left;
		return (struct rb_node *)node;
	}

	/* No right-hand children.  Everything down and left is
	   smaller than us, so any 'next' node must be in the general
	   direction of our parent. Go up the tree; any time the
	   ancestor is a right-hand child of its parent, keep going
	   up. First time it's a left-hand child of its parent, said
	   parent is our 'next' node. */
	while ((parent = rb_parent(node)) && node == parent->rb_right)
		node = parent;

	return parent;
}
EXPORT_SYMBOL(rb_next);

struct rb_node *rb_prev(const struct rb_node *node)
{
	struct rb_node *parent;

	if (rb_parent(node) == node)
		return NULL;

	/* If we have a left-hand child, go down and then right as far
	   as we can. */
	if (node->rb_left) {
		node = node->rb_left; 
		while (node->rb_right)
			node=node->rb_right;
		return (struct rb_node *)node;
	}

	/* No left-hand children. Go up till we find an ancestor which
	   is a right-hand child of its parent */
	while ((parent = rb_parent(node)) && node == parent->rb_left)
		node = parent;

	return parent;
}
EXPORT_SYMBOL(rb_prev);

void rb_replace_node(struct rb_node *victim, struct rb_node *new,
		     struct rb_root *root)
{
	struct rb_node *parent = rb_parent(victim);

	/* Set the surrounding nodes to point to the replacement */
	if (parent) {
		if (victim == parent->rb_left)
			parent->rb_left = new;
		else
			parent->rb_right = new;
	} else {
		root->rb_node = new;
	}
	if (victim->rb_left)
		rb_set_parent(victim->rb_left, new);
	if (victim->rb_right)
		rb_set_parent(victim->rb_right, new);

	/* Copy the pointers/colour from the victim to the replacement */
	*new = *victim;
}
EXPORT_SYMBOL(rb_replace_node);



inline static void _unused* crtl_rbtree_iterator_first(struct crtl_rbtree_iterator_struct *iter);
inline static void _unused* crtl_rbtree_iterator_next(struct crtl_rbtree_iterator_struct *iter);
inline static void _unused* crtl_rbtree_iterator_prev(struct crtl_rbtree_iterator_struct *iter);
inline static void _unused* crtl_rbtree_iterator_last(struct crtl_rbtree_iterator_struct *iter);

struct crtl_rbtree_struct* crtl_rbtree_init(int (*cmp)(const void *, const void *), int (*display)(const void *))
{
    struct crtl_rbtree_struct* rbtree = malloc(sizeof(struct crtl_rbtree_struct));
    if(!rbtree)
    {
        crtl_print_err("null pointer error.\n");
        crtl_assert_fp(stderr, rbtree);
        return NULL;
    }
    
    rbtree->root.rb_node = NULL;

    rbtree->nnode = 0;
    rbtree->cmp = cmp;
    rbtree->display = display;

    /* 初始化迭代器 */
    rbtree->iter.rbtree = rbtree;
    rbtree->iter.curr_node = NULL;
    
    rbtree->iter.first = crtl_rbtree_iterator_first;
    rbtree->iter.next = crtl_rbtree_iterator_next;
    rbtree->iter.prev = crtl_rbtree_iterator_prev;
    rbtree->iter.last = crtl_rbtree_iterator_last;
    
    return rbtree;
}


/* insert */
int crtl_rbtree_insert(struct crtl_rbtree_struct* rbtree, void *data, unsigned int data_size)
{
    crtl_assert_fp(stderr, rbtree);
    if(!data || data_size<=0)
    {
        crtl_print_err("null pointer or out of range error.\n");
        crtl_assert_fp(stderr, 0);
        return CRTL_ERROR;
    }
    
    struct rb_node **tmp = &(rbtree->root.rb_node), *parent= NULL;
    
    struct crtl_rbtree_node_struct *newnode = malloc(sizeof(struct crtl_rbtree_node_struct));
    newnode->data_size = data_size;
    newnode->data = (void*)data;
    
    while(*tmp)
    {
        struct crtl_rbtree_node_struct *this = container_of(*tmp, struct crtl_rbtree_node_struct, node);
        parent = *tmp;
        
        int cmp_ret = rbtree->cmp(this->data, data);
        if(cmp_ret == CRTL_GT) {
            tmp = &((*tmp)->rb_left);
        } else if(cmp_ret == CRTL_LT) {
            tmp = &((*tmp)->rb_right);
        } else {
            crtl_print_err("This RBnode already exist.\n");
            crtl_assert_fp(stderr, 0);
            return CRTL_ERROR;
        }
    }
    rb_link_node(&newnode->node, parent, tmp);
    rb_insert_color(&newnode->node, &rbtree->root);

    rbtree->nnode += 1;
    
    return CRTL_SUCCESS;
}


/* search */
struct crtl_rbtree_node_struct *crtl_rbtree_search(struct crtl_rbtree_struct* rbtree, const void *data)
{
    crtl_assert_fp(stderr, rbtree);
    if(!data)
    {
        crtl_print_err("null pointer error.\n");
        crtl_assert_fp(stderr, data);
        return NULL;
    }
    
    struct rb_node *node = rbtree->root.rb_node;
    while(node)
    {
        struct crtl_rbtree_node_struct *node_data = container_of(node, struct crtl_rbtree_node_struct, node);
        int cmp_ret = rbtree->cmp(node_data->data, data);
        if(cmp_ret == CRTL_GT) {
            node = node->rb_left;
        } else if(cmp_ret == CRTL_LT) {
            node = node->rb_right;
        } else if(cmp_ret == CRTL_EQ) {
            return node_data;
        } else {
            crtl_print_err("This RBnode not exist.\n");
            crtl_assert_fp(stderr, 0);
            return NULL;
        }
    }

    return NULL;
}


/* delete */
int crtl_rbtree_delete(struct crtl_rbtree_struct* rbtree, const void *data)
{
    if(unlikely(!data) || unlikely(!rbtree))
    {
        crtl_print_err("null pointer error.\n");
        crtl_assert_fp(stderr, data);
        return CRTL_ERROR;
    }
    
    struct crtl_rbtree_node_struct *node_data = crtl_rbtree_search(rbtree, data);
    if(!node_data)
    {
        crtl_print_err("Not found rbtree node.\n");
        return CRTL_ERROR;
    }
    rb_erase(&node_data->node, &rbtree->root);
    free(node_data);

    rbtree->nnode -= 1;
    
    return CRTL_SUCCESS;
}


int crtl_rbtree_nnode(const struct crtl_rbtree_struct* rbtree)
{
    if(unlikely(!rbtree))
    {
        crtl_print_err("null pointer error.\n");
        crtl_assert_fp(stderr, rbtree);
        return CRTL_ERROR;
    }
    
    return rbtree->nnode;
}

int crtl_rbtree_is_empty(const struct crtl_rbtree_struct* rbtree)
{
    return crtl_rbtree_nnode(rbtree)==0?CRTL_SUCCESS:CRTL_ERROR;
}


/* getfirst */
struct crtl_rbtree_node_struct* crtl_rbtree_getfirst(struct crtl_rbtree_struct* rbtree)
{
    crtl_assert_fp(stderr, rbtree);
    
    struct rb_node *first_rb_node = rb_first(&rbtree->root);
    struct crtl_rbtree_node_struct  *first_rt_rbtree_node = rb_entry(first_rb_node, struct crtl_rbtree_node_struct, node);
    
    if(first_rt_rbtree_node)
        return first_rt_rbtree_node;

    return NULL;
}
/* getfirst */
struct crtl_rbtree_node_struct* crtl_rbtree_getlast(struct crtl_rbtree_struct* rbtree)
{
    crtl_assert_fp(stderr, rbtree);
    
    struct rb_node *first_rb_node = rb_last(&rbtree->root);
    struct crtl_rbtree_node_struct  *first_rt_rbtree_node = rb_entry(first_rb_node, struct crtl_rbtree_node_struct, node);
    
    if(first_rt_rbtree_node)
        return first_rt_rbtree_node;

    return NULL;
}

/* getnext */
struct crtl_rbtree_node_struct* crtl_rbtree_getnext(struct crtl_rbtree_node_struct* node)
{   
    crtl_assert_fp(stderr, node);
    
    struct rb_node *next_rb_node = rb_next(&node->node);
    struct crtl_rbtree_node_struct  *next_rt_rbtree_node = rb_entry(next_rb_node, struct crtl_rbtree_node_struct, node);
    
    if(next_rt_rbtree_node)
        return next_rt_rbtree_node;
    
    return NULL;
}
/* getnext */
struct crtl_rbtree_node_struct* crtl_rbtree_getprev(struct crtl_rbtree_node_struct* node)
{   
    crtl_assert_fp(stderr, node);
    
    struct rb_node *next_rb_node = rb_prev(&node->node);
    struct crtl_rbtree_node_struct  *next_rt_rbtree_node = rb_entry(next_rb_node, struct crtl_rbtree_node_struct, node);
    
    if(next_rt_rbtree_node)
        return next_rt_rbtree_node;
    
    return NULL;
}

/* destroy */
int crtl_rbtree_destroy(struct crtl_rbtree_struct* rbtree)
{
    crtl_assert_fp(stderr, rbtree);
    
    struct crtl_rbtree_node_struct *find_node = NULL;

    for(find_node=crtl_rbtree_getfirst(rbtree); find_node; find_node=crtl_rbtree_getfirst(rbtree))
    {
        crtl_rbtree_delete(rbtree, find_node->data);
    }
    
    free(rbtree);
    rbtree = NULL;
    
    return CRTL_SUCCESS;
}

struct crtl_rbtree_iterator_struct* crtl_rbtree_iterator(struct crtl_rbtree_struct* rbtree)
{
    crtl_assert_fp(stderr, rbtree);
    return &(rbtree->iter);
}

inline static void _unused* crtl_rbtree_iterator_first(struct crtl_rbtree_iterator_struct *iter)
{
    crtl_assert_fp(stderr, iter);
//    container_of(ptr, type, member)
    iter->curr_node = crtl_rbtree_getfirst(iter->rbtree);
    return iter->curr_node?(void*)iter->curr_node->data:NULL;
}
inline static void _unused* crtl_rbtree_iterator_next(struct crtl_rbtree_iterator_struct *iter)
{
    crtl_assert_fp(stderr, iter);
    
    struct crtl_rbtree_node_struct _unused *tmp_node = iter->curr_node;
    
    iter->curr_node = crtl_rbtree_getnext(iter->curr_node);
    
    if(iter->curr_node == NULL) {//如果想获取最后一个的下一个,currentnode指向最后一个节点,返回NULL
        iter->curr_node = tmp_node;
        return NULL;
    } else {
        return (void*)iter->curr_node->data;
    }
}
inline static void _unused* crtl_rbtree_iterator_prev(struct crtl_rbtree_iterator_struct *iter)
{
    crtl_assert_fp(stderr, iter);
    struct crtl_rbtree_node_struct _unused *tmp_node = iter->curr_node;
    
    iter->curr_node = crtl_rbtree_getprev(iter->curr_node);
    
    if(iter->curr_node == NULL) { //如果想获取第一个的上一个,currentnode指向第一个节点,返回NULL
        iter->curr_node = tmp_node;
        return NULL;
    } else {
        return (void*)iter->curr_node->data;
    }
}
inline static void _unused* crtl_rbtree_iterator_last(struct crtl_rbtree_iterator_struct *iter)
{
    crtl_assert_fp(stderr, iter);
    iter->curr_node = crtl_rbtree_getlast(iter->rbtree);
    return iter->curr_node?(void*)iter->curr_node->data:NULL;
}




#ifdef ______cPP___iterator_demo______rongtao


#include <iostream>
#include <vector>
using namespace std;
int main()
{
    vector<int> v;  //v是存放int类型变量的可变长数组,开始时没有元素
    for (int n = 0; n<5; ++n)
        v.push_back(n);  //push_back成员函数在vector容器尾部添加一个元素
    vector<int>::iterator i;  //定义正向迭代器
    for (i = v.begin(); i != v.end(); ++i) {  //用迭代器遍历容器
        cout << *i << " ";  //*i 就是迭代器i指向的元素
        *i *= 2;  //每个元素变为原来的2倍
    }
    cout << endl;
    //用反向迭代器遍历容器
    for (vector<int>::reverse_iterator j = v.rbegin(); j != v.rend(); ++j)
        cout << *j << " ";
    return 0;
}

#endif

 

demo.c

#include <crtl/crtl_tree.h>
#include <crtl/crtl_log.h>



struct mytype {
	struct rb_node my_node;
	int num;
};

struct mytype *my_search(struct rb_root *root, int num)
{
	struct rb_node *node = root->rb_node;
	while(node)
	{
		struct mytype *data = container_of(node, struct mytype, my_node);
		if(num < data->num)
		{
			node = node->rb_left;
		}
		else if(num > data->num)
		{
			node = node->rb_right;
		}
		else
			return data;
	}
	return NULL;
}

int my_insert(struct rb_root *root, struct mytype *data)
{
	struct rb_node **tmp = &(root->rb_node), *parent = NULL;
	while(*tmp)
	{
		struct mytype *this = container_of(*tmp, struct mytype, my_node);
		parent = *tmp;
		if(data->num < this->num)
		{
			tmp = &((*tmp)->rb_left);
		}
		else if(data->num > this->num)
		{
			tmp = &((*tmp)->rb_right);
		}
		else 
		{
			return -1;
		}
	}
	rb_link_node(&data->my_node, parent, tmp);
	rb_insert_color(&data->my_node, root);
	return 0;
}

void my_delete(struct rb_root *root, int num)
{
    struct mytype *data = my_search(root, num);
    if(!data)
    {
        crtl_print_debug("Not found %d.\n", num);
        return;
    }
    rb_erase(&data->my_node, root);
    free(data);
}

void print_rbtree(struct rb_root *tree)
{
    struct rb_node *node;
    for(node=rb_first(tree); node; node=rb_next(node))
    {
        crtl_print_debug("%2d \n", rb_entry(node, struct mytype, my_node)->num);
    }
    crtl_print_debug("\n");
}

void demo_rbtree_original()
{
    struct rb_root mytree = RB_ROOT;
    int i, ret, num, nums[] = {2,6,9,8,3,4,7,1,12,1,5,6,9,83,6, 4,87,65,45,85,21,36,64,74,75};
    struct mytype *tmp;

    for(i=0;i<sizeof(nums)/sizeof(nums[0]);i++)
    {
        tmp = malloc(sizeof(struct mytype));
        if(!tmp)
            crtl_print_debug("Allocate dynamic memory error.\n");

        num = nums[i];
        tmp->num = num;
        
        ret = my_insert(&mytree, tmp);
        if(ret <0)
        {
            crtl_print_debug("The %d already exist.\n", tmp->num);
            free(tmp);
        }
    }
    print_rbtree(&mytree);

    my_delete(&mytree, 3);
    
    print_rbtree(&mytree);
}


struct structA{
    int a;
};
int demo_crtl_rbtree_cmp(void *d1, void *d2)
{
    struct structA *a1 = (struct structA *)d1;
    struct structA *a2 = (struct structA *)d2;
    if(a1->a > a2->a) return CRTL_GT;
    else if(a1->a == a2->a) return CRTL_EQ;
    else if(a1->a < a2->a) return CRTL_LT;

    return CRTL_EQ;
}
int demo_crtl_rbtree_display(void *data)
{
    struct structA *a1 = (struct structA *)data;
    return printf("%d\n", a1->a);
}

struct structA aaa[] = {{71},{64},{5},{7},{12}};

void demo_crtl_rbtree()
{
    crtl_rbtree_t rbt = crtl_rbtree_init(&demo_crtl_rbtree_cmp, &demo_crtl_rbtree_display);

    crtl_print_debug(">>nnode %d.\n", crtl_rbtree_nnode(rbt));
    crtl_print_debug(">>nnode %d. is empty %s\n", 
                                crtl_rbtree_nnode(rbt), crtl_rbtree_is_empty(rbt)==CRTL_SUCCESS?"YES":"NO");

    int i;
    for(i=0;i<sizeof(aaa)/sizeof(aaa[0]); i++)
        crtl_rbtree_insert(rbt, &aaa[i], sizeof(struct structA));

    crtl_print_debug(">>nnode %d.\n", crtl_rbtree_nnode(rbt));
    crtl_print_debug(">>nnode %d. is empty %s\n", 
                                crtl_rbtree_nnode(rbt), crtl_rbtree_is_empty(rbt)==CRTL_SUCCESS?"YES":"NO");


    crtl_rbtree_node_t *node = NULL;
    for(node=crtl_rbtree_getfirst(rbt); node; node = crtl_rbtree_getnext(node))
    {
        struct structA *a1 = (struct structA *)(node->data);
        rbt->display(a1);
    }
    crtl_print_debug(">>nnode %d.\n", crtl_rbtree_nnode(rbt));
    crtl_print_debug(">>nnode %d. is empty %s\n", 
                                crtl_rbtree_nnode(rbt), crtl_rbtree_is_empty(rbt)==CRTL_SUCCESS?"YES":"NO");
    crtl_rbtree_delete(rbt, &aaa[3]);
    crtl_print_debug(">>nnode %d.\n", crtl_rbtree_nnode(rbt));
    crtl_rbtree_delete(rbt, &aaa[2]);
    crtl_print_debug(">>nnode %d.\n", crtl_rbtree_nnode(rbt));
    crtl_print_debug(">>nnode %d. is empty %s\n", 
                                crtl_rbtree_nnode(rbt), crtl_rbtree_is_empty(rbt)==CRTL_SUCCESS?"YES":"NO");
    
    node = NULL;
    for(node=crtl_rbtree_getfirst(rbt); node; node = crtl_rbtree_getnext(node))
    {
        struct structA *a1 = CRTL_RBTREE_DATA(node);
        rbt->display(a1);
    }
    crtl_print_debug(">>nnode %d.\n", crtl_rbtree_nnode(rbt));

    
    crtl_print_debug("Use crtl_rbtree_iterator_t\n");
    
    struct structA *a1 = NULL;
    crtl_rbtree_iterator_t iter = crtl_rbtree_iterator(rbt);
    for(a1 = iter->first(iter); a1; a1 = iter->next(iter))
    {
        rbt->display(a1);
    }
    for(a1 = iter->prev(iter); a1; a1 = iter->prev(iter))
    {
        rbt->display(a1);
    }
    for(a1 = iter->next(iter); a1; a1 = iter->next(iter))
    {
        rbt->display(a1);
    }
    
    crtl_rbtree_destroy(rbt);
}


int main()
{
//    demo_rbtree_original();

    demo_crtl_rbtree();

    return 0;
}