# 环形链表

环形链表也称为循环链表，它是一种特殊的双向链表。双向链表的尾结点指向头结点，就构成了环形链表。

双向环形队列表数据结构定义：

typedef struct __list_ring {
         struct __list_ring      *RING_plistNext;          /*  环形表前向指针     */
         struct __list_ring      *RING_plistPrev;          /*  环形表后向指针     */
} LW_LIST_RING;

• RING_plistNext：环形表前向指针。
• RING_plistPrev：环形表后向指针。

SylixOS 中，环形链表主要有结点查找、插入、删除等链表操作。

# 指向下一个结点

#include <SylixOS.h>
VOID _list_ring_next (PLW_LIST_LINE  *phead);

函数 _list_ring_next 原型分析：

• 参数 phead 是环形链表头结点指针的指针。

调用 _list_ring_next 函数可以让环形链表表头指向下一个结点，如下图所示。

SylixOS 内核中任务就绪表是一个环形链表，因此又有“就绪环”的说法，从任务就绪表中确定一个最需要运行的线程就使用到 _list_ring_next 函数，在 RR 调度策略中，当就绪任务缺少时间片时，会被补充时间片，然后通过 _list_ring_next 函数查找同优先级中下一个最需要运行的任务。

# 获取下一个结点

#include <SylixOS.h>
PLW_LIST_RING  _list_ring_get_next (PLW_LIST_RING  pring);

函数 _list_ring_get_next 原型分析：

• 此函数返回环形链表下一个结点的指针。
• 参数 pring 是环形链表结点的指针。

调用 _list_ring_get_next 函数可以获取环形链表下一个结点的指针，如下图所示。

SylixOS 内核中模块加载、内存分配、处理核间中断调用函数等多个地方均使用到 list_ring_get_next 函数。

# 获取上一个结点

#include <SylixOS.h>
PLW_LIST_RING  _list_ring_get_prev (PLW_LIST_RING  pring);

函数 _list_ring_get_prev 原型分析：

• 此函数返回环形链表上一个结点的指针。
• 参数 pring 是环形链表结点的指针。

调用 _list_ring_get_prev 函数可以获取双链表上一个结点的指针，如下图所示。

# 环形链表头部前方向插入结点

#include <SylixOS.h>
VOID  _List_Ring_Add_Ahead (PLW_LIST_RING          pringNew,
                            LW_LIST_RING_HEADER   *ppringHeader);

函数 _List_Ring_Add_Ahead 原型分析：

• 参数 pringNew 是环形链表中要插入的新结点的指针。
• 参数 ppringHeader 是环形链表头结点指针的指针。

调用 _List_Ring_Add_Ahead 函数可以向形链表表头前方向插入一个结点，参数 pplineHeader 将指向这个结点，如下图所示。

SylixOS 内核中将线程加入到事件等待队里中使用到 _List_Ring_Add_Ahead 函数。

# 环形链表头部后方向插入结点

#include <SylixOS.h>
VOID  _List_Ring_Add_Front (PLW_LIST_RING           pringNew,
                            LW_LIST_RING_HEADER    *ppringHeader);

函数 _List_Ring_Add_Front 原型分析：

• 参数 pringNew 是环形链表中要插入的新结点的指针。
• 参数 ppringHeader 是环形链表中指定结点的指针。

调用 _List_Ring_Add_Front 函数可以向形链表表头后方向插入一个结点，参数 ppringHeader 有结点时，不变化，SylixOS 就绪表使用这种操作方式实现，如下图所示。

SylixOS 内核中将任务加入到“就绪环”中使用到 _List_Ring_Add_Front 函数，对于高速响应线程，会使用 _List_Ring_Add_Front 函数将线程加入到环形链表头部，对于普通响应线程，会使用下面的 _List_Ring_Add_Last 函数将线程加入到环形链表尾部。

# 环形链表尾部后方向插入结点

#include <SylixOS.h>
VOID  _List_Ring_Add_Last (PLW_LIST_RING             pringNew,
                           LW_LIST_RING_HEADER      *ppringHeader);

函数 _List_Ring_Add_Last 原型分析：

• 参数 pringNew 是环形链表中要插入的新结点的指针。
• 参数 ppringHeader 是环形链表头结点指针的指针。

调用 _List_Ring_Add_Last 函数可以向形链表表尾后方向中插入一个结点，如下图所示。

# 环形链表删除结点

#include <SylixOS.h>
VOID  _List_Ring_Del (PLW_LIST_RING           pringDel,
                      LW_LIST_RING_HEADER    *ppringHeader);

函数 _List_Ring_Del 原型分析：

• 参数 pringDel 是要删除的环形链表中的结点的指针。
• 参数 ppringHeader 是环形链表头结点的指针的指针。

调用 _List_Line_Del 函数可以从环形链表中删除一个结点，如下图所示。

SylixOS 内核中双向环形队列表的结点回收会使用到 _List_Ring_Del 函数。