本篇关键词:、、、

下载 >> 离线文档.鸿蒙内核源码分析(百篇博客分析.挖透鸿蒙内核).pdf

进程管理相关篇为:

二叉查找树 | BST

要理解红黑树,需要从二叉查找树(Binary Search Tree)开始说起。其特点是:

  • 1.左子树上所有结点的值均小于或等于它的根结点的值。
  • 2.右子树上所有结点的值均大于或等于它的根结点的值。
  • 3.左、右子树也分别为二叉排序树。

例如:想要找到下图节点 10 就需要经过路径 [ 9 | 13 | 11 ]

在理想的情况下,二叉查找树增删查改的时间复杂度为O(logN)(其中N为节点数),最坏的情况下为O(N)。

BST 的特点是在操作过程中容易失去平衡,数在插入的时候会导致树倾斜,不同的插入顺序会导致树的高度不一样,而树的高度直接的影响了树的查找效率。理想的高度是logN,最坏的情况是所有的节点都在一条斜线上,这样的树的高度为N。例如:下图为初始的二叉查找树 接下来依次插入如下五个结点:7,6,5,4,3,结果将变成简直没法看的

红黑树

基于BST存在的问题,一种新的树——平衡二叉查找树即 红黑树(Red-Black Tree,以下简称RBTree),它在插入和删除的时候,会通过旋转操作将高度保持在logN。通俗的讲就是会自我纠正,跟人睡觉一样,将自己的身体调整到一个让最省力,最舒服的姿势。其实际应用非常广泛,比如Linux内核中的完全公平调度器、高精度计时器、ext3文件系统等等,鸿蒙内核中也使用了红黑树来管理进程线性区。上图经过红黑树调整之后的姿势为:

红黑树有以下几个特点:

  • 1.任何一个节点都有颜色,黑色或者红色。
  • 2.根节点是黑色的。
  • 3.父子节点之间不能出现两个连续的红节点。
  • 4.任何一个节点向下遍历到其子孙的叶子节点,所经过的黑节点个数必须相等。
  • 5.空节点被认为是黑色的。
  • 6.从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。

红黑树具体的调整姿势的方法有两种:

  • 变色 根据红黑树的规则,尝试把红色结点变为黑色,或者把黑色结点变为红色。
  • 旋转,根据旋转方向又分成 左旋转右旋转
    • 左旋转(逆时针旋转) 红黑树的两个结点,使得父结点被自己的右孩子取代,而自己成为自己的左孩子。
    • 右旋转(顺时针旋转) 红黑树的两个结点,使得父结点被自己的左孩子取代,而自己成为自己的右孩子。
  • 有兴趣的可以前往 红黑树演示网站 玩一下,很有意思

在鸿蒙使用

鸿蒙使用红黑树主要用来管理进程的 线性区 ,关于线性区不清楚的请自行翻看系列篇,简单说就是一个虚拟地址连续的内存记录。我们动态申请堆内存其实就是申请了一个线性区,释放内存时就需要查找这个记录,这种使用频率很高,而红黑树的查找效率最高。鸿蒙红黑树功能的核心结构体是 LosRbTree ,每一个进程都有一颗属于自己的红黑树。

typedef struct VmMapRange {//线性区范围结构体
    VADDR_T             base;           /**< vm region base addr | 线性区基地址*/
    UINT32              size;           /**< vm region size | 线性区大小*/
} LosVmMapRange;

typedef struct TagRbNode {//节点
    struct TagRbNode *pstParent; ///< 爸爸是谁 ?
    struct TagRbNode *pstRight;  ///< 右孩子是谁 ?
    struct TagRbNode *pstLeft;	 ///< 左孩子是谁 ?
    ULONG_T lColor; //是红还是黑节点
} LosRbNode;

typedef struct TagRbTree {//红黑树控制块
    LosRbNode *pstRoot;//根节点
    LosRbNode stNilT;//叶子节点
    LOS_DL_LIST stWalkHead;
    ULONG_T ulNodes;

    pfRBCmpKeyFn pfCmpKey; //比较两个节点大小 处理函数
    pfRBFreeFn pfFree;	//释放结点占用内存函数
    pfRBGetKeyFn pfGetKey;//获取指定线性区范围 VmMapRange 函数
} LosRbTree;
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

解读

  • 红黑树初始化,在进程空间初始化期间会初始化红黑树,并指定三个回调函数(方便红黑树节点的遍历)。
    //初始化进程的红黑树
    VOID LOS_RbInitTree(LosRbTree *pstTree, pfRBCmpKeyFn pfCmpKey, pfRBFreeFn pfFree, pfRBGetKeyFn pfGetKey)
    {
        OsRbInitTree(pstTree);
        pstTree->pfCmpKey = pfCmpKey;
        pstTree->pfFree = pfFree;
        pstTree->pfGetKey = pfGetKey;
        return;
    }
    //初始化进程虚拟空间
    STATIC BOOL OsVmSpaceInitCommon(LosVmSpace *vmSpace, VADDR_T *virtTtb){
        //...
        LOS_RbInitTree(&vmSpace->regionRbTree, OsRegionRbCmpKeyFn, OsRegionRbFreeFn, OsRegionRbGetKeyFn);
    }
    ///通过红黑树节点找到对应的线性区
    VOID *OsRegionRbGetKeyFn(LosRbNode *pstNode)
    {
        LosVmMapRegion *region = (LosVmMapRegion *)LOS_DL_LIST_ENTRY(pstNode, LosVmMapRegion, rbNode);
        return (VOID *)&region->range;
    }
    ///比较两个红黑树节点
    ULONG_T OsRegionRbCmpKeyFn(const VOID *pNodeKeyA, const VOID *pNodeKeyB)
    {
        LosVmMapRange rangeA = *(LosVmMapRange *)pNodeKeyA;
        LosVmMapRange rangeB = *(LosVmMapRange *)pNodeKeyB;
        UINT32 startA = rangeA.base;
        UINT32 endA = rangeA.base + rangeA.size - 1;
        UINT32 startB = rangeB.base;
        UINT32 endB = rangeB.base + rangeB.size - 1;
    
        if (startA > endB) {// A基地址大于B的结束地址
            return RB_BIGGER; //说明线性区A更大,在右边
        } else if (startA >= startB) {
            if (endA <= endB) {
                return RB_EQUAL; //相等,说明 A在B中
            } else {
                return RB_BIGGER; //说明 A的结束地址更大
            }
        } else if (startA <= startB) { //A基地址小于等于B的基地址
            if (endA >= endB) {
                return RB_EQUAL; //相等 说明 B在A中
            } else {
                return RB_SMALLER;//说明A的结束地址更小
            }
        } else if (endA < startB) {//A结束地址小于B的开始地址
            return RB_SMALLER;//说明A在
        }
        return RB_EQUAL;
    }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
  • 插入结点,注意线性区结构体(VmMapRegion)的首个成员便是红黑树节点,对于红黑树来说线性区只是一个红黑树节点。
    struct VmMapRegion {
      LosRbNode           rbNode;         /**< region red-black tree node | 红黑树节点,通过它将本线性区挂在VmSpace.regionRbTree*/
      // ...
    }
    //插入线性区,指的是向进程的红黑树 `LosRbTree` 插入 `LosRbNode`
    BOOL OsInsertRegion(LosRbTree *regionRbTree, LosVmMapRegion *region)
      {
          if (LOS_RbAddNode(regionRbTree, (LosRbNode *)region) == FALSE) {
              VM_ERR("insert region failed, base: %#x, size: %#x", region->range.base, region->range.size);
              OsDumpAspace(region->space);
              return FALSE;
          }
          return TRUE;
      }
    
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    具体插入过程不去说明,已经是很成熟的算法,通过比较线性区的范围来决定是插入进具体位置,插入过程会涉及到红黑树 颜色翻转左右旋转 两种变化

百文说内核 | 抓住主脉络

  • 百文相当于摸出内核的肌肉和器官系统,让人开始丰满有立体感,因是直接从注释源码起步,在加注释过程中,每每有心得处就整理,慢慢形成了以下文章。内容立足源码,常以生活场景打比方尽可能多的将内核知识点置入某种场景,具有画面感,容易理解记忆。说别人能听得懂的话很重要! 百篇博客绝不是百度教条式的在说一堆诘屈聱牙的概念,那没什么意思。更希望让内核变得栩栩如生,倍感亲切。
  • 与代码需不断debug一样,文章内容会存在不少错漏之处,请多包涵,但会反复修正,持续更新,v**.xx 代表文章序号和修改的次数,精雕细琢,言简意赅,力求打造精品内容。
  • 百文在 < 鸿蒙研究站 | 开源中国 | 博客园 | 51cto | csdn | 知乎 | 掘金 > 站点发布,鸿蒙研究站 | weharmonyos 中回复 百文 可方便阅读。

按功能模块:

百万注源码 | 处处扣细节

  • 百万汉字注解内核目的是要看清楚其毛细血管,细胞结构,等于在拿放大镜看内核。内核并不神秘,带着问题去源码中找答案是很容易上瘾的,你会发现很多文章对一些问题的解读是错误的,或者说不深刻难以自圆其说,你会慢慢形成自己新的解读,而新的解读又会碰到新的问题,如此层层递进,滚滚向前,拿着放大镜根本不愿意放手。

  • < gitee | github | coding | gitcode > 四大码仓推送 | 同步官方源码,鸿蒙研究站 | weharmonyos 中回复 百万 可方便阅读。

关注不迷路 | 代码即人生

据说喜欢点赞分享的,后来都成了大神。😃