tbox链表list和list_entry的使用

Easter79
• 阅读 439

TBOX中提供了各种列表操作:

  1. list: 元素在内部维护的双向链表

  2. list_entry: 元素在外部维护的双向链表

  3. single_list: 元素在内部维护的单向链表

  4. single_list_entry: 元素在外部维护的单向链表

由于双链和单链的接口使用类似,这里主要就讲解双链的具体使用。

那什么是内部维护和外部维护呢? 简单地说:

  • 外部维护:就是链表容器本身不存储元素,不开辟内存空间,仅仅是一个节点头,这样比较节省内存,更加灵活。(尤其是在多个链表间元素迁移的时候,或者多个链表需要统一内存池维护的时候)。

  • 内部维护:就是链表容器本身回去开辟一块空间,去单独存储元素内容,这种方式对接口的操作比较简单,但是灵活性和性能不如前一种,如果不需要多个链表维护同一种元素,那么使用这种模式简单操作下,更为妥当。(而且内部元素的存储也是用内存池优化过的)。

list的使用

list的使用很简单,接口用起来也很方便,这里给个简单的例子:

// 创建一个long类型的双链,参数0表示采用默认的自动元素增长大小,也可以手动设置更适合的大小
tb_list_ref_t list = tb_list_init(0, tb_element_long());
if (list)
{
    // 在链表头部插入元素:1,并返回这个新元素的迭代器索引
    tb_size_t itor = tb_list_insert_head(list, (tb_pointer_t)1);

    // 在之前新的元素后面插入一个新元素:2
    tb_list_insert_next(list, itor, (tb_pointer_t)2);

    // 在链表尾部插入元素:3
    tb_list_insert_tail(list, (tb_pointer_t)3);

    // 移除指定的元素
    tb_list_remove(list, itor);

    // 遍历所有链表元素,
    tb_for_all(tb_long_t, item, list)
    {
        // 打印元素值
        tb_trace_i("%ld", item);
    }

    // 销毁list
    tb_list_exit(list);
}

list_entry的使用

list_entry由于是外置式的容器,需要在外面自己定义的结构体上进行操作,例如定义:

// 链表元素结构体
typedef struct __tb_demo_entry_t 
{
    // 外置双链的节点,用于链表维护
    tb_list_entry_t     entry;

    // 元素的实际数据
    tb_size_t           data;

}tb_demo_entry_t;

对链表的具体操作如下:

// 定义一些静态元素,用于插入链表(实际使用可能需要自己动态创建他们)
tb_demo_entry_t entries[12] = 
{
    { {0}, 0 }
,   { {0}, 1 }
,   { {0}, 2 }
,   { {0}, 3 }
,   { {0}, 4 }
,   { {0}, 5 }
,   { {0}, 6 }
,   { {0}, 7 }
,   { {0}, 8 }
,   { {0}, 9 }
,   { {0}, 10}
,   { {0}, 11}
};

// 初始化链表,需要指定外置元素的结构体类型,链表的节点名字
tb_list_entry_head_t list;
tb_list_entry_init(&list, tb_demo_entry_t, entry, tb_null);

// 插入一些元素,注意:所有操作都是在外置结构体中的list_entry节点上操作
tb_list_entry_insert_tail(&list, &entries[5].entry);
tb_list_entry_insert_tail(&list, &entries[6].entry);
tb_list_entry_insert_tail(&list, &entries[7].entry);
tb_list_entry_insert_tail(&list, &entries[8].entry);
tb_list_entry_insert_tail(&list, &entries[9].entry);
tb_list_entry_insert_head(&list, &entries[4].entry);
tb_list_entry_insert_head(&list, &entries[3].entry);
tb_list_entry_insert_head(&list, &entries[2].entry);
tb_list_entry_insert_head(&list, &entries[1].entry);
tb_list_entry_insert_head(&list, &entries[0].entry);

// 访问具体某个节点的元素数据
tb_demo_entry_t* entry = (tb_demo_entry_t*)tb_list_entry(&list, &entries[5].entry);
tb_trace_i("entry: %lu", entry->data);

// 遍历所有元素
tb_trace_i("insert: %lu", tb_list_entry_size(&list));
tb_for_all_if(tb_demo_entry_t*, item0, tb_list_entry_itor(&list), item0)
{
    tb_trace_i("%lu", item0->data);
}

// 替换头尾的元素
tb_list_entry_replace_head(&list, &entries[10].entry);
tb_list_entry_replace_last(&list, &entries[11].entry);

// 移除头尾的元素
tb_list_entry_remove_head(&list);
tb_list_entry_remove_last(&list);

// 移动元素位置,这里吧头尾的元素对调了下
tb_list_entry_ref_t head = tb_list_entry_head(&list);
tb_list_entry_moveto_head(&list, tb_list_entry_last(&list));
tb_list_entry_moveto_tail(&list, head);

// 退出列表
tb_list_entry_exit(&list);

怎么样,也不是很复杂吧,由于元素的内存都在外面自己维护,所以灵活性提升了不少,并且可以多个链表同时维护,然后共用一个内存池进行优化,效率和内存都能得到最大的提升,这种模式在linux内核里面很常见。

如果要做比喻的话,list就是傻瓜式操作,list_entry就是定制化操作。。。

本文分享自微信公众号 - TBOOX开源工程(tboox-os)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

点赞
收藏
评论区
推荐文章
blmius blmius
2年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
22 22
2年前
【数据结构之链表】详细图文教你花样玩链表
【系列文章推荐阅读】0.提要钩玄文章已经介绍了链式存储结构,介绍了链式存储结构的最基本(简单)实现——单向链表。单向链表,顾名思义,它是单向的。因为单链表的每个结点只有一个数据域和一个指针域,而该指针域只存储了下一个结点的地址,所以我们只能通过某结点找到其直接后继结点,却不能通过某节点找到其直接前驱结点。此外,由于单链表到尾结点(链表的最后一
Stella981 Stella981
2年前
Redis基本操作——队列 List(原理篇)
Redis基本操作——List(原理篇)  学习过数据结构的同学,一定对链表(LinkedList)十分的熟悉。相信我们自己也曾经使用过这种数据结构。  链表分为很多种:单向链表,双向链表,循环链表,块状链表\1(https://www.oschina.net/action/GoToLink?url
Stella981 Stella981
2年前
LinkedList
Base:JDK1.81、LinkedListLinkedList也是一个比较常见的数据结构,链表。在C/C中,链表也是一个典型的线性结构,链表分为单向跟双向的两种链表。在java里面的LinkedList是一个双向的链表。链表最好的好处就在于来一个数据加一个长度,没有多余的冗余,也是支
Wesley13 Wesley13
2年前
JAVA实现双向链表的增删功能
JAVA实现双向链表的增删功能,完整代码  1.packagelinked;3.classLinkedTable{5.}6.publicclassLinkedTableTest{8.  //构造单链表9.  staticNodenode1newNode("name1");10.
Stella981 Stella981
2年前
Redis的列表(List)类型
列表类型(List)可以存储一个有序的字符串列表,常用的操作就是向列表两端添加元素,或者获取列表中某一个片段。列表类型内部使用双向链表(doublelinkedlist)实现的,所以向列表两端添加或删除元素的速度非常快,越是接近两端的元素就越快,但是,也有弊端,就是通过索引访问元素的速度比较慢。因为使用了双向链表实现存储的,所以在命令上也有
Stella981 Stella981
2年前
Django中Admin中的一些参数配置
设置在列表中显示的字段,id为django模型默认的主键list_display('id','name','sex','profession','email','qq','phone','status','create_time')设置在列表可编辑字段list_editable
Stella981 Stella981
2年前
C#Redis列表List
转载自:https://www.cnblogs.com/5ishare/p/6291034.html一、前戏 在Redis中,List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表一样,我们可以在其头部(left)和尾部(right)添加新的元素。在插入时,如果该键并不存在,Redis将为该键创建一个新的链表。与此相反,如果链表中所有的元
Stella981 Stella981
2年前
Redis(四)——消息队列
Redis不仅可作为缓存服务器,还可用作消息队列。它的列表类型天生支持用作消息队列。\\性质:\\由于Redis的列表是使用双向链表实现的,保存了头尾节点,所以在列表头尾两边插取元素都是非常快的。所以可以直接使用Redis的List实现消息队列,只需简单的两个指令lpush和rpop或者rpush和lpop。(列表常用命令)R
菜园前端 菜园前端
10个月前
什么是链表?
原文链接:什么是链表?链表是有序的数据结构,链表中的每个部分称为节点。可以首、尾、中间进行数据存取,链表的元素在内存中不必是连续的空间,每个节点通过next指针指向下一个节点。优点链表的添加和删除不会导致其余元素位移。缺点无法根据索引快速定位元素。数组和链
Easter79
Easter79
Lv1
今生可爱与温柔,每一样都不能少。
文章
2.8k
粉丝
5
获赞
1.2k