Linux内核中的红黑树
程序员文章站
2024-01-23 18:25:52
...
Table of Contents
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;
}
上一篇： 测试的程序运行时间简单方法
下一篇： TFTP安装与配置