Linux内核中红黑树算法的实现详解_unix linux

一、简介

平衡二叉树(BalancedBinary Tree或Height-Balanced Tree)

又称AVL树。它或者是一棵空树,或者是具有下列性质的二叉树:它的左子树和右子树都是平衡二叉树,且左子树和右子树的深度之差的绝对值不超过1。若将二叉树上结点的平衡因子BF(BalanceFactor)定义为该结点的左子树的深度减去它的右子树的深度,则平衡二叉树上所有结点的平衡因子只可能是-1、0和1。(此段定义来自严蔚敏的《数据结构(C语言版)》)

红黑树

R-B Tree,全称是Red-Black Tree,又称为“红黑树”,它一种特殊的二叉查找树。红黑树的每个节点上都有存储位表示节点的颜色,可以是红(Red)或黑(Black)。

红黑树是一种在插入或删除结点时都需要维持平衡的二叉查找树,并且每个结点都具有颜色属性:

(1)、一个结点要么是红色的,要么是黑色的。

(2)、根结点是黑色的。

(3)、如果一个结点是红色的,那么它的子结点必须是黑色的,也就是说在沿着从根结点出发的任何路径上都不会出现两个连续的红色结点。

(4)、从一个结点到一个NULL指针的每条路径上必须包含相同数目的黑色结点。

 

Linux内核红黑树的算法都定义在linux-2.6.38.8/include/linux/rbtree.hlinux-2.6.38.8/lib/rbtree.c两个文件中。

二、结构体

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)))); 

这里的巧妙之处是使用成员rb_parent_color同时存储两种数据,一是其双亲结点的地址,另一是此结点的着色。  __attribute__((aligned(sizeof(long))))属性保证了红黑树中的每个结点的首地址都是32位对齐的(在32位机上),也就是说每个结点首地址的bit[1]bit[0]都是0,因此就可以使用bit[0]来存储结点的颜色属性而不干扰到其双亲结点首地址的存储。

操作rb_parent_color的函数:

#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;
} 

初始化新结点:

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;  //设置其双亲结点的首地址(根结点的双亲结点为NULL),且颜色属性设为黑色
  node->rb_left = node->rb_right = NULL;  //初始化新结点的左右子树 

  *rb_link = node; //指向新结点
} 

指向红黑树根结点的指针:

struct rb_root
{
  struct rb_node *rb_node;
}; 

#define RB_ROOT (struct rb_root) { NULL, } //初始化指向红黑树根结点的指针
#define rb_entry(ptr, type, member) container_of(ptr, type, member) //用来获得包含struct rb_node的结构体的首地址 

#define RB_EMPTY_ROOT(root) ((root)->rb_node == NULL) //判断树是否为空
#define RB_EMPTY_NODE(node) (rb_parent(node) == node) //判断node的双亲结点是否为自身
#define RB_CLEAR_NODE(node) (rb_set_parent(node, node)) //设置双亲结点为自身 

三、插入

首先像二叉查找树一样插入一个新结点,然后根据情况作出相应的调整,以使其满足红黑树的颜色属性(其实质是维持红黑树的平衡)。

函数rb_insert_color使用while循环不断地判断双亲结点是否存在,且颜色属性为红色。

若判断条件为真,则分成两部分执行后续的操作:

    (1)、当双亲结点是祖父结点左子树的根时,则:

           a、存在叔父结点,且颜色属性为红色。

 

           b、当node是其双亲结点右子树的根时,则左旋,然后执行第c步。

 

            c、当node是其双亲结点左子树的根时。

 

    (2)、当双亲结点是祖父结点右子树的根时的操作与第(1)步大致相同,这里略过不谈。

         若为假,则始终设置根结点的颜色属性为黑色。

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)) //双亲结点不为NULL,且颜色属性为红色
  {
    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; //node指向祖父结点
          continue; //继续下一个while循环
        }
      } 

      if (parent->rb_right == node) //当node是其双亲结点右子树的根时
      {
        register struct rb_node *tmp;
        __rb_rotate_left(parent, root); //左旋
        tmp = parent; //调整parent和node指针的指向
        parent = node;
        node = tmp;
      } 

      rb_set_black(parent); //设置双亲结点为黑色
      rb_set_red(gparent); //设置祖父结点为红色
      __rb_rotate_right(gparent, root); //右旋
    } else { // !(parent == gparent->rb_left)
      {
        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);
    } //end if (parent == gparent->rb_left)
  } //end while ((parent = rb_parent(node)) && rb_is_red(parent)) 

  rb_set_black(root->rb_node);
} 

四、删除

像二叉查找树的删除操作一样,首先需要找到所需删除的结点,然后根据该结点左右子树的有无分为三种情形:

 

node结点的颜色属性为黑色,则需要调用__rb_erase_color函数来进行调整。

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;
  } //end else 

  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函数来进行调整
    __rb_erase_color(child, parent, root);
} 

五、遍历

rb_firstrb_next函数可组成中序遍历,即以升序遍历红黑树中的所有结点。

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;
} 

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;
} 

六、在应用程序中使用

Linux内核中红黑树算法的实现非常通用、巧妙,而且免费又开源,因此完全可以把它运用到自己的应用程序中。

    (1)、从内核中拷贝源文件:

$ mkdir redblack
$ cd redblack/
$ cp ../linux-2.6.38.8/lib/rbtree.c .
$ cp ../linux-2.6.38.8/include/linux/rbtree.h . 

    (2)、修改源文件:

          a、C文件rbtree.c

            修改包含头文件的代码

//删除以下两行代码
#include <linux/rbtree.h>
#include <linux/module.h>
//新增以下代码,即包含当前目录中的头文件rbtree.h
#include "rbtree.h" 

           删除所有的EXPORT_SYMBOL宏

EXPORT_SYMBOL(rb_insert_color);
EXPORT_SYMBOL(rb_erase);
EXPORT_SYMBOL(rb_augment_insert);
EXPORT_SYMBOL(rb_augment_erase_begin);
EXPORT_SYMBOL(rb_augment_erase_end);
EXPORT_SYMBOL(rb_first);
EXPORT_SYMBOL(rb_last);
EXPORT_SYMBOL(rb_next);
EXPORT_SYMBOL(rb_prev);
EXPORT_SYMBOL(rb_replace_node); 

          b、头文件rbtree.h

             删除包含头文件的代码,并添加三个宏定义

//删除以下两行代码
#include <linux/kernel.h>
#include <linux/stddef.h> 

/* linux-2.6.38.8/include/linux/stddef.h */
#undef NULL
#if defined(__cplusplus)
#define NULL 0
#else
#define NULL ((void *)0)
#endif 

/* linux-2.6.38.8/include/linux/stddef.h */
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 

/* linux-2.6.38.8/include/linux/kernel.h */
#define container_of(ptr, type, member) ({     \
  const typeof( ((type *)0)->member ) *__mptr = (ptr); \
  (type *)( (char *)__mptr - offsetof(type,member) );}) 

    (3)、示例代码

    Linux内核红黑树的使用方法请参考linux-2.6.38.8/Documentation/rbtree.txt文件。

/* test.c */
#include <stdio.h>
#include <stdlib.h>
#include "rbtree.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; 

  /* Figure out where to put new node */
  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;
  } 

  /* Add new node and rebalance tree. */
  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) {
  fprintf(stderr, "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))
  printf("%d ", rb_entry(node, struct mytype, my_node)->num); 

  printf("\n");
} 

int main(int argc, char *argv[])
{
  struct rb_root mytree = RB_ROOT;
  int i, ret, num;
  struct mytype *tmp; 

  if (argc < 2) {
  fprintf(stderr, "Usage: %s num\n", argv[0]);
  exit(-1);
  } 

  num = atoi(argv[1]); 

  printf("Please enter %d integers:\n", num);
  for (i = 0; i < num; i++) {
  tmp = malloc(sizeof(struct mytype));
  if (!tmp)
    perror("Allocate dynamic memory"); 

  scanf("%d", &tmp->num); 

  ret = my_insert(&mytree, tmp);
  if (ret < 0) {
    fprintf(stderr, "The %d already exists.\n", tmp->num);
    free(tmp);
  }
  } 

  printf("\nthe first test\n");
  print_rbtree(&mytree); 

  my_delete(&mytree, 21); 

  printf("\nthe second test\n");
  print_rbtree(&mytree); 

  return 0;
} 

编译并执行:

$ gcc rbtree.c test.c -o test
richard@tanglinux:~/algorithm/redblack$ ./test 10
Please enter 10 integers:
23
4
56
32
89
122
12
21
45
23
The 23 already exists. 

the first test
4 12 21 23 32 45 56 89 122  

the second test
4 12 23 32 45 56 89 122  

七、总结

以上就是关于Linux内核中红黑树算法实现的全部内容,文章介绍的很详细,希望对大家的工作和学习能有所帮助,如果有疑问可以留言交流。

以上是小编为您精心准备的的内容,在的博客、问答、公众号、人物、课程等栏目也有的相关内容,欢迎继续使用右上角搜索按钮进行搜索linux内核红黑树
, linux内核算法
红黑树算法实现
linux 内核之红黑树、linux内核红黑树、内核 红黑树、红黑树算法、红黑树删除详解,以便于您获取更多的相关知识。

时间: 2024-09-24 00:13:35

Linux内核中红黑树算法的实现详解_unix linux的相关文章

Linux top命令的用法详细详解_unix linux

查看多核CPU命令mpstat -P ALL  和  sar -P ALL    说明:sar -P ALL > aaa.txt   重定向输出内容到文件 aaa.txt top命令经常用来监控linux的系统状况,比如cpu.内存的使用,程序员基本都知道这个命令,但比较奇怪的是能用好它的人却很少,例如top监控视图中内存数值的含义就有不少的曲解. 本文通过一个运行中的WEB服务器的top监控截图,讲述top视图中的各种数据的含义,还包括视图中各进程(任务)的字段的排序. top进入视图 top

Linux内核的文件预读详解

  Linux文件预读算法磁盘I/O性能的发展远远滞后于CPU和内存,因而成为现代计算机系统的一个主要瓶颈.预读可以有效的减少磁盘的寻道次数和应用程序的I/O等待时间,是改进磁盘读I/O性能的重要优化手段之一.本文作者是中国科学技术大学自动化系的博士生,他在1998年开始学习Linux,为了优化服务器的性能,他开始尝试改进Linux kernel,并最终重写了内核的文件预读部分,这些改进被收录到Linux Kernel 2.6.23及其后续版本中. 从寄存器.L1/L2高速缓存.内存.闪存,到磁

Linux操作系统内核编译详解_unix linux

    内核简介 内核,是一个操作系统的核心.它负责管理系统的进程.内存.设备驱动程序.文件和网络系统,决定着系统的性能和稳定性.   Linux的一个重要的特点就是其源代码的公开性,所有的内核源程序都可以在/usr/src/linux下找到,大部分应用软件也都是遵循GPL而设计的,你都可以获取相应的源程序代码.全世界任何一个软件工程师都可以将自己认为优秀的代码加入到其中,由此引发的一个明显的好处就是Linux修补漏洞的快速以及对最新软件技术的利用.而Linux的内核则是这些特点的最直接

Linux/Unix环境下的Make和Makefile详解_unix linux

Linux/Unix环境下的Make和Makefile详解  无论是在Linux还是在Unix环境中,make都是一个非常重要的编译命令.不管是自己进行项目开发还是安装应用软件,我们都经常要用到make或make install.利用make工具,我们可以将大型的开发项目分解成为多个更易于管理的模块,对于一个包括几百个源文件的应用程序,使用make和makefile工具就可以简洁明快地理顺各个源文件之间纷繁复杂的相互关系.而且如此多的源文件,如果每次都要键入gcc命令进行编译的话,那对程序员来说

深入数据驱动编程之表驱动法的详解_unix linux

数据驱动编程之表驱动法 本文示例代码采用的是c语言.之前介绍过数据驱动编程<浅谈:什么是数据驱动编程的详解>.里面介绍了一个简单的数据驱动手法.今天更进一步,介绍一个稍微复杂,更加实用的一点手法--表驱动法.关于表驱动法,在<unix编程艺术>中有提到,更详细的描述可以看一下<代码大全>,有一章专门进行描述(大概是第八章).简单的表驱动:<浅谈:什么是数据驱动编程的详解>中有一个代码示例.它其实也可以看做是一种表驱动手法,只不过这个表相对比较简单,它在收到消

Linux tcpdump操作命令详解_unix linux

简介 用简单的话来定义tcpdump,就是:dump the traffic on a network,根据使用者的定义对网络上的数据包进行截获的包分析工具. tcpdump可以将网络中传送的数据包的"头"完全截获下来提供分析.它支持针对网络层.协议.主机.网络或端口的过滤,并提供and.or.not等逻辑语句来帮助你去掉无用的信息. 实用命令实例 默认启动 复制代码 代码如下: tcpdump 普通情况下,直接启动tcpdump将监视第一个网络接口上所有流过的数据包. 监视指定网络接

Linux IPC命令的用法详解_unix linux

进程间通信概述 进程间通信有如下的目的:1.数据传输,一个进程需要将它的数据发送给另一个进程,发送的数据量在一个字节到几M之间: 2.共享数据,多个进程想要操作共享数据,一个进程对数据的修改,其他进程应该立刻看到: 3.通知事件,一个进程需要向另一个或一组进程发送消息,通知它们发生了某件事情: 4.资源共享,多个进程之间共享同样的资源.为了做到这一点,需要内核提供锁和同步机制: 5.进程控制,有些进程希望完全控制另一个进程的执行(如Debug进程),此时控制进程希望能够拦截另一个进程的所有陷入和

Linux ipcs命令与ipcrm命令的用法详解_unix linux

是linux/uinx上提供关于一些进程间通信方式的信息,包括共享内存,消息队列,信号 ipcs用法 ipcs -a  是默认的输出信息 打印出当前系统中所有的进程间通信方式的信息ipcs -m  打印出使用共享内存进行进程间通信的信息ipcs -q   打印出使用消息队列进行进程间通信的信息ipcs -s  打印出使用信号进行进程间通信的信息 输出格式的控制ipcs -t   输出信息的详细变化时间 ipcs -p  输出ipc方式的进程IDipcs -c  输出ipc方式的创建者/拥有者 i

浅谈:什么是数据驱动编程的详解_unix linux

前言:最近在学习<Unix编程艺术>.以前粗略的翻过,以为是介绍unix工具的.现在认真的看了下,原来是介绍设计原则的.它的核心就是第一章介绍的unix的哲学以及17个设计原则,而后面的内容就是围绕它来展开的.以前说过,要学习适合自己的资料,而判断是否适合的一个方法就是看你是否能够读得下去.我对这本书有一种相见恨晚的感觉.推荐有4~6年工作经验的朋友可以读一下.正题:作者在介绍Unix设计原则时,其中有一条为"表示原则:把知识叠入数据以求逻辑质朴而健壮".结合之前自己的一些