本文对Melon库中的红黑树进行介绍，对于Melon库，这是一个开源的C语言库，它具备：开箱即用、无第三方依赖、装置部署简略、中英文文档齐全等劣势。

Github repo

简介

红黑树是一种被利用的十分宽泛的数据结构，用于疾速搜寻指定数据集中的数据。

这里咱们不对红黑树的原理进行开展，仅给出其工夫复杂度和应用场景介绍。

工夫复杂度

  • 插入：O(logN)
  • 删除：O(logN)
  • 搜寻：O(logN)

应用场景

  • 实现字典查问，即kv查问
  • 文件描述符索引，例如保护socket fd

应用

Melon库中的红黑树经验了若干次迭代，最终造成了以后的应用状态。咱们先给出代码，再进而阐明为何会演变至此。

红黑树

#include <stdio.h>#include <stdlib.h>#include "mln_core.h"#include "mln_log.h"#include "mln_rbtree.h"static int cmp_handler(const void *data1, const void *data2){    return *(int *)data1 - *(int *)data2;}int main(int argc, char *argv[]){    int n = 10;    mln_rbtree_t *t;    mln_rbtree_node_t *rn;    struct mln_rbtree_attr rbattr;    struct mln_core_attr cattr;    cattr.argc = argc;    cattr.argv = argv;    cattr.global_init = NULL;    cattr.master_process = NULL;    cattr.worker_process = NULL;    if (mln_core_init(&cattr) < 0) {        fprintf(stderr, "init failed\n");        return -1;    }    rbattr.pool = NULL;    rbattr.pool_alloc = NULL;    rbattr.pool_free = NULL;    rbattr.cmp = cmp_handler;    rbattr.data_free = NULL;    rbattr.cache = 0;    if ((t = mln_rbtree_new(&rbattr)) == NULL) {        mln_log(error, "rbtree init failed.\n");        return -1;    }    rn = mln_rbtree_node_new(t, &n);    if (rn == NULL) {        mln_log(error, "rbtree node init failed.\n");        return -1;    }    mln_rbtree_insert(t, rn);    rn = mln_rbtree_root_search(t, &n);    if (mln_rbtree_null(rn, t)) {        mln_log(error, "node not found\n");        return -1;    }    mln_log(debug, "%d\n", *((int *)mln_rbtree_node_data(rn)));    mln_rbtree_delete(t, rn);    mln_rbtree_node_free(t, rn);    mln_rbtree_free(t);    return 0;}

main函数大抵流程如下：

  1. 定义变量
  2. 初始化Melon库
  3. 设置红黑树初始化属性
  4. 创立红黑树
  5. 创立红黑树结点
  6. 插入结点
  7. 搜寻结点
  8. 删除结点
  9. 销毁结点
  10. 销毁红黑树结构

Melon中，应用红黑树须要引入mln_rbtree.h头文件。

这里咱们须要对红黑树初始化属性进行一番阐明，这也是演变至今逐步变简单的中央。

struct mln_rbtree_attr {    void                      *pool;    rbtree_pool_alloc_handler  pool_alloc;    rbtree_pool_free_handler   pool_free;    rbtree_cmp                 cmp;    rbtree_free_data           data_free;};typedef void *(*rbtree_pool_alloc_handler)(void *, mln_size_t);typedef void (*rbtree_pool_free_handler)(void *);typedef int (*rbtree_cmp)(const void *, const void *);typedef void (*rbtree_free_data)(void *);

其中：

  • pool是用于反对用户自定义内存池之用的，该指针将于pool_alloc和pool_free配合应用。
  • pool_alloc是用于反对用户自定义分配内存之用，该函数指针第一个参数为pool，第二个参数是要调配的内存大小。
  • pool_free是用于反对用户自定义开释内存之用，该函数指针第一个参数为要开释的内存起始地址。
  • cmp是用于对两个树结点所关联的用户自定义数据进行比拟大小之用的。
  • data_free是用于对红黑树结点所关联的用户自定义数据进行开释之用的。

这些指针，若无须要能够置NULL。

内存池和调配开释函数次要是用于树结点的调配和开释之用。之所以不间接给出一个Melon实现的内存池构造指针，是因为不心愿红黑树代码与内存池类型强关联，这样容许红黑树能够接入使用者本人定义的内存治理性能。

演变

晚期，红黑树只有cmp和data_free。起初退出了pool、pool_alloc和pool_free来减少内存调配起源。

从14年至今的应用中，会一直遇到新的应用场景，因而对红黑树内部结构做各种调整，例如：

  • 遍历红黑树所有结点
  • 遍历红黑树所有结点的同时删除其中的结点
  • 减少结点计数

因而，如果读者浏览源码，会发现树结构中还有一个双向链表构造用来辅助结点遍历。

可能有的读者会提出，为什么树结点不能与关联的自定义数据结构一起调配，相似如下代码：

struct some_struct {    int val;    ...    mln_rbtree_node_t node;}void some_function(...){    struct some_struct *s;    mln_rbtree_t *tree;        s = malloc(...);//allocate struct some_struct    mln_rbtree_node_init(&s->node, s);    ...    mln_rbtree_insert(tree, &s->node);    ...}

这段代码不能实在执行。

之所以不这样设计，并非没有构想和尝试过。然而发现如此设计存在一下优劣势：

  • 劣势：少了一次树结点内存调配动作
  • 劣势：如果结点要退出多个树结构，则须要在构造体中给出多个node成员，若并不一定每一个树结构都退出，则会造成肯定的内存节约。且后续性能扩大时引入了红黑树结构，也有可能要给很多构造体中引入node结点，能力实现红黑树的性能，这减少了二开的老本。

结语

Melon中的红黑树目前演变至此，置信也不会是其最终状态。也心愿宽广开发者敌人提出宝贵意见和倡议。

另外对于Melon库感兴趣的读者，能够拜访Github仓库。

感激浏览！