社区贡献 | OpenTenBase内核中的基础数据类型简介：列表

列表数据类型是什么？如何实现？

• 第一，我们所储存的元素应当按照什么样的方式来组织？比如，我们往往喜欢使用 int 这一数据类型，在单独的列表数据元素中存储整数。

• 第二，列表整体应当记录怎么样的信息？比如，列表本身是不是需要关注整体目前存储的元素个数，用于便利我们记录当前的内存容量？

• 第三，我们的软件有没有什么“列表数据结构”之外的特殊需求？

OpenTenBase 对于列表类型的定义

/* OpenTenBase 2.6.0 */


typedef struct List
{
    NodeTag        type; 
    /* 
        用于标识节点的类型，这需要联系火山模型来做理解，
        但是它超出了本文的范围，所以我们此处不做展开
    */            
    /* T_List, T_IntList, or T_OidList */
    /* 
        分别代表通用列表、整数列表、Oid 列表，
        其中 Oid 是 OpenTenBase 用于统一管理资源对象的编号 
    */
    int            length;
    /* 列表的长度 */
    /* 列表的头节点与尾节点 */
    ListCell   *head;
    ListCell   *tail;
} List;


struct ListCell
{
    union
    {
        void      *ptr_value; // 在作为 通用元素 时使用
        int       int_value;  // 在作为 整数元素 时使用
        Oid       oid_value;  // 在作为 oid 元素 时使用
    }data;
    /* 指向下一个节点 */
    ListCell   *next;
};

OpenTenBase List 的具体实现：以元素的插入函数实现为例

/* 在 list.c 中提取 */
List *
lcons(void *datum, List *list)
{
    /* 检测列表的类型，本质就是判断 Node 的标签是否为 List */
    /* 在生产版本的 OpenTenBase 中，这行代码没有意义 */
    Assert(IsPointerList(list));


    /* 
        如果列表是不存在的，创建一个新的列表 
        否则，分配一个新的头节点元素，注意 OpenTenBase 的 List 是自头部插入的
    */
    if (list == NIL)
        list = new_list(T_List);
    else 
        new_head_cell(list);


    /* 在分配完节点空间之后，配置数据域，即将整数填充进去 */
    lfirst(list->head) = datum;
    /* 检查插入的数据是否有效 */
    /* 同样的，生产版本中，这行代码没有意义 */
    check_list_invariants(list);
    return list;
}

OpenTenBase 列表的应用：以对 hba 文件的支持为例

/*
 * pre-parsed content of HBA config file: list of HbaLine structs.
 * parsed_hba_context is the memory context where it lives.
 */
/* HbaLine 结构是自定义的类型，因此很明显此处是通用列表 */
static List *parsed_hba_lines = NIL;

写在最后

• AtomGit
  https://atomgit.com/opentenbase
• GitHub
  https://github.com/opentenbase