开源C语言库Melon:红黑树

发布时间:2024年01月08日

本文对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_allocpool_free配合使用。
  • pool_alloc是用于支持用户自定义分配内存之用,该函数指针第一个参数为pool,第二个参数是要分配的内存大小。
  • pool_free是用于支持用户自定义释放内存之用,该函数指针第一个参数为要释放的内存起始地址。
  • cmp是用于对两个树结点所关联的用户自定义数据进行比较大小之用的。
  • data_free是用于对红黑树结点所关联的用户自定义数据进行释放之用的。

这些指针,若无需要可以置NULL

内存池和分配释放函数主要是用于树结点的分配和释放之用。之所以不直接给出一个Melon实现的内存池结构指针,是因为不希望红黑树代码与内存池类型强关联,这样允许红黑树可以接入使用者自己定义的内存管理功能。

演化

早期,红黑树只有cmpdata_free。后来加入了poolpool_allocpool_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仓库

感谢阅读!

文章来源:https://blog.csdn.net/weixin_40960130/article/details/135451085
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。