Contiki物联网操作系统链表库

Contiki 系统链表库提供了可以在其上放置链表项并在以后可以检索的链表，为了存储进程链表、分组队列、邻居表和各种表，整个Contiki 系统中都会用到链表库。链表中的链表项是使用链表库的模块定义的结构体，链表中的第一项必须是指针，链表库使用该指针把链表上的项链接在一起。

图8-1　链表结构

图8-1 所示为Contiki 操作系统链表结构，链表由链表句柄和链表项集合组成，链表句柄是指向链表中首项的指针，每个链表项是一个结构体，其中链表项的第一个成员next 是链表指针，Contiki 操作系统链接库使用该指针建立链表，链表上最后一个链表项的指针next值设置为NULL，空链表的链表句柄设置为NULL，链表句柄和链表项的内存由使用该链表的模块分配，链表库本身既不分配内存，也不存储它管理链表的任何状态。

与链表定义相关的两个主要文件是list.c 和list.h，这两个文件保存在core/lib 文件夹下。list.h 中有三个宏定义函数：LIST()、LIST_STRUCT()和LIST_STRUCT_INIT()。宏定义函数LIST()把链表声明为list_t 类型，该函数创建两个对象：一个对象用于链表项本身，另一个对象用于指向链表中首项的指针。把这两种对象分离的好处是可以复制list_t 对象，并且可以用一种不易出错的方式引用该list_t对象。文件list.h中宏定义函数LIST()如下：

如果需要使用作为全局对象的链表或在数据结构中使用链表，宏定义函数LIST_STRUCT()在结构体内声明一个链表。这样，在需要全局链表的情况下，可以声明包含链表的全局范围结构体，把它添加到API 函数表并定义相关的参数即可。宏定义函数LIST_STRUCT()如下所示：

宏定义函数LIST_STRUCT_INIT()用于初始化链表，该宏在已经定义为结构体一部分的链表中建立内部指针，在使用链表之前必须调用该宏。宏定义函数中参数struct_ptr 是指向结构体的指针，参数name 是链表的名称，该宏定义函数如下所示：(www.xing528.com)

在链表的操作中，可以把链表项添加到链表的前面或者后面，也可以添加到两个链表项中间。把链表项添加到链表上之后，它将保留其相对于链表上其他链表项的位置。通过删除链表第一个链表项、最后一个链表项或给定链表项而删除链表上的链表项。Contiki 操作系统关于链表操作的API 函数如下所示，这些函数的实现在程序文件list.c中。

以上函数中，其中函数list_head()是访问链表首项（也称为表头元素）的函数，函数list_tail()是访问链表上最后一项（也称为表尾元素）的函数。有两种遍历链表的方法：利用指针next 或利用函数list_item_next()。尽管后者代码量大于直接指针访问方法的代码量，但Contiki 版本的移植中推荐使用函数list_item_next()。链表库也提供了计算链表长度的函数list_length()，链表上没有存储链表长度值，而是使用链表长度函数list_length()遍历链表统计每个链表元素，计算链表长度。可以使用函数list_push()、list_add()或list_insert()在链表上插入链表项，这三个函数插入链表项的方法不同，list_push()函数在链表首部插入链表项，list_add()函数在链表尾部插入链表项，而list_insert()函数在链表的两个链表项中间插入新的链表项。函数list_push()的实现很简单，它仅仅设置要被插入的链表项的next 指针指向链表句柄指向的元素，然后链表句柄指向新插入的链表项即可。如果链表是空的，即链表句柄的值为NULL，设置新插入链表项的next指针值为NULL。函数list_add()的实现比list_push()稍微复杂，因为依赖于链表是否为空，该函数的运行方式不同。对于空链表，链表句柄只是指向新的链表项；而对于非空链表，首先找到链表的最后一个链表项，该链表项的next指针再指向新的链表项。函数list_insert()的实现也很简单，它需要重新设置新插入链表项前后两个链表项的next 指针，如果该链表为空，则只需要设置链表句柄指向新的链表项即可。

函数list_push()、list_add()或list_insert()不检查链表上是否已存在要插入的新链表项，相反，由调用模块确保一个链表项不会被插入两次，采用这种设计方法的原因是考虑到性能的问题，即确保一个链表项不会被添加两次的模块的性能不应该受到影响。

函数list_pop()、list_chop()或list_remove()用于从链表中删除链表项，这三个函数分别用于删除链表首项、最后一个链表项和指定的中间链表项。因为链表操作模块不给链表项分配内存，而是由使用链表操作模块的程序分配，为链表项分配的内存不会随链表项的删除而释放。从链表中删除链表项之后，如果需要，由调用链表处理的模块确保释放分配给这些删除项的内存，因此，除调用list_remove()的函数已经知道删除的链表项的位置之外，这些删除函数需返回一个指向删除链表项的指针。

以下程序是使用链表操作函数的简单应用程序。