前言
在我們嵌入式中，可能會有些人認為資料結構與算法相關知識沒什麼用，很少用得上。
以前，我也是這麼認為的，那東西那麼難學，好像又用不上，學了有什麼用，幹脆就不學了。
直到後面深入學習一些東西之後發現，原來那些知識并不是沒有用，隻是當時我們的認知還不足。廢話不多說，下面進入正題：
對象容器與雙連結清單
1、RT-Thread中的對象容器
RT-Thread
核心對象包括：線程，信号量，互斥量，事件，郵箱，消息隊列和定時器，記憶體池，裝置驅動等。
對象容器中包含了每類核心對象的資訊，包括對象類型，大小等。
對象容器給每類核心對象配置設定了一個連結清單，所有的核心對象都被連結到該連結清單上， RT-Thread 的核心對象容器及連結清單如下圖所示：
這個對象容器對應到代碼上是一個結構體數組，這個結構體數組在
object.c
裡定義，其内容如下（已做删減）：
static struct rt_object_information
rt_object_container[RT_Object_Info_Unknown] =
{
/* 初始化對象容器 - 線程 */
{
RT_Object_Class_Thread,
_OBJ_CONTAINER_LIST_INIT(RT_Object_Info_Thread),
sizeof(struct rt_thread)
},
#ifdef RT_USING_SEMAPHORE
/* 初始化對象容器 - 信号量 */
{
RT_Object_Class_Semaphore,
_OBJ_CONTAINER_LIST_INIT(RT_Object_Info_Semaphore),
sizeof(struct rt_semaphore)
},
#endif
/* 省略部分代碼...*/
/* 初始化對象容器 - 定時器 */
{
RT_Object_Class_Timer,
_OBJ_CONTAINER_LIST_INIT(RT_Object_Info_Timer),
sizeof(struct rt_timer)
},
/* 省略部分代碼...*/
};
其中，核心對象資訊結構體
struct rt_object_information
的定義如下：
struct rt_object_information
{
enum rt_object_class_type type; /**< 對象類型 */
rt_list_t object_list; /**< 對象連結清單節點頭 */
rt_size_t object_size; /**< 對象大小 */
};
RT-Thread 的核心對象的繼承關系如：
在代碼閱讀器
Source Insight
中也可以看出這樣的關系：
每個核心對象的初始化函數裡都有調用對象初始化函數
rt_object_init
。
而對象初始化函數裡做了什麼呢？看其内部實作（已做删減）：
void rt_object_init(struct rt_object *object,
enum rt_object_class_type type,
const char *name)
{
register rt_base_t temp;
struct rt_object_information *information;
/* 擷取對象資訊，即從容器裡拿到對應對象清單頭指針 */
information = rt_object_get_information(type);
RT_ASSERT(information != RT_NULL);
/* 設定對象類型為靜态 */
object->type = type | RT_Object_Class_Static;
/* 拷貝名字 */
rt_strncpy(object->name, name, RT_NAME_MAX);
/* 關中斷 */
temp = rt_hw_interrupt_disable();
/* 把對象資訊插入到對象連結清單中 */
rt_list_insert_after(&(information->object_list), &(object->list));
/* 開中斷 */
rt_hw_interrupt_enable(temp);
}
這裡用到的
rt_list_insert_after
函數就是雙連結清單插入函數。
2、RT-Thread中雙連結清單的操作
RT-Thread的對象容器是依賴于雙連結清單（
雙向循環連結清單
）的，其雙連結清單的相關操作在檔案
rtservice.h
中：
其節點結構體為：
struct rt_list_node
{
struct rt_list_node *next; /**< 指向後一個節點 */
struct rt_list_node *prev; /**< 指向後一個節點 */
};
typedef struct rt_list_node rt_list_t;
下面介紹幾個基本的操作接口（截圖來自野火的RT-Thread書籍）：
（1）初始化連結清單節點：
rt_inline void rt_list_init(rt_list_t *l)
{
l->next = l->prev = l;/* 節點的next指針與prev指針都指向其本身 */
}
（2） 在雙向連結清單表頭後面插入一個節點：
rt_inline void rt_list_insert_after(rt_list_t *l, rt_list_t *n)
{
l->next->prev = n; /* 第（1）步 */
n->next = l->next; /* 第（2）步 */
l->next = n; /* 第（3）步 */
n->prev = l; /* 第（4）步 */
}
（3）在雙向連結清單表頭前面（表尾後面）插入一個節點：
rt_inline void rt_list_insert_before(rt_list_t *l, rt_list_t *n)
{
l->prev->next = n; /* 第（1）步 */
n->prev = l->prev; /* 第（2）步 */
l->prev = n; /* 第（3）步 */
n->next = l; /* 第（4）步 */
}
（4）從雙向連結清單删除一個節點：
rt_inline void rt_list_remove(rt_list_t *n)
{
n->next->prev = n->prev; /* 第（1）步 */
n->prev->next = n->next; /* 第（2）步 */
n->next = n->prev = n; /* 第（3）步 */
}
初始化對象清單節點頭裡面的 next 和 prev 兩個節點指針分别指向自身，如：
若建立兩個led線程對象，則對象容器裡變為：
順便提一個關于連結清單的一個名詞上的疑惑，是
節點
還是
結點
？我之前也看過一些書，有的書寫為節點，有的書寫為結點，我也不知道哪個更準确。不糾結了，知道這麼一回事就可以了，不影響我們學習。
最後
看到了吧，資料結構在嵌入式中還是很有用的吧，更多的細節可以閱讀其源碼。
參考資料：
1、官方的《RT-THREAD 程式設計指南》
2、野火的《RT-Thread 核心實作與應用開發實戰指南》