sys/queue.h
概述
??????? sys/queue.h是LINUX/UNIX系統(tǒng)下面的一個(gè)標(biāo)準(zhǔn)頭文件，用一系列的數(shù)據(jù)結(jié)構(gòu)定義了一隊(duì)列。包括singly-lined list, list, simple queue(Singly-linked Tail queue), tail queue, circle queue五種。
??????? 引用此頭文件對(duì)這五種數(shù)據(jù)結(jié)構(gòu)的描述：
A singly-linked list is headed by a single forward pointer. The
elements are singly linked for minimum space and pointer manipulation
overhead at the expense of O(n) removal for arbitrary elements. New
elements can be added to the list after an existing element or at the
head of the list.? Elements being removed from the head of the list
should use the explicit macro for this purpose for optimum
efficiency. A singly-linked list may only be traversed in the forward
direction.? Singly-linked lists are ideal for applications with large
datasets and few or no removals or for implementing a LIFO queue.
A list is headed by a single forward pointer (or an array of forward
pointers for a hash table header). The elements are doubly linked
so that an arbitrary element can be removed without a need to
traverse the list. New elements can be added to the list before
or after an existing element or at the head of the list. A list
may only be traversed in the forward direction.
A simple queue is headed by a pair of pointers, one the head of the
list and the other to the tail of the list. The elements are singly
linked to save space, so elements can only be removed from the
head of the list. New elements can be added to the list after
an existing element, at the head of the list, or at the end of the
list. A simple queue may only be traversed in the forward direction.
A tail queue is headed by a pair of pointers, one to the head of the
list and the other to the tail of the list. The elements are doubly
linked so that an arbitrary element can be removed without a need to
traverse the list. New elements can be added to the list before or
after an existing element, at the head of the list, or at the end of
the list. A tail queue may be traversed in either direction.
A circle queue is headed by a pair of pointers, one to the head of the
list and the other to the tail of the list. The elements are doubly
linked so that an arbitrary element can be removed without a need to
traverse the list. New elements can be added to the list before or after
an existing element, at the head of the list, or at the end of the list.
A circle queue may be traversed in either direction, but has a more
complex end of list detection.
??????? 簡(jiǎn)單來(lái)說(shuō)，即是單鏈表，雙鏈表，單鏈隊(duì)列，雙向隊(duì)列（尾隊(duì)列）和雙向循環(huán)隊(duì)列。
??????? 雖然這是LINUX/UNIX里面的文件，但此文件本身沒(méi)有用到LINUX/UNIX的系統(tǒng)特性，因而可以跨平臺(tái)使用。queue.h下載。
??????? 下面對(duì)各數(shù)據(jù)結(jié)構(gòu)簡(jiǎn)單描述之。
單鏈表(singly-linked list)
??????? singly-linked list就是一單鏈表。
??????? singly-linked list相關(guān)的定義：
| 宏定義 | 說(shuō)明 |
| SLIST_HEAD(name, type) | 定義表頭結(jié)點(diǎn)。 name: 表頭結(jié)點(diǎn)名。 type: 結(jié)點(diǎn)類(lèi)型。 |
| SLIST_HEAD_INITIALIZER(head) | 初始化頭結(jié)點(diǎn)。 head: 表頭結(jié)點(diǎn)。 |
| SLIST_ENTRY(type) | 定義鏈表的鏈域。 type: 結(jié)點(diǎn)類(lèi)型。 |
??????? singly-linked list函數(shù)：
| 宏定義 | 說(shuō)明 |
| SLIST_INIT(head) | 初始化頭結(jié)點(diǎn)。 head: 表頭結(jié)點(diǎn)。 |
| SLIST_INSERT_AFTER(slistelm, elm, field) | 將結(jié)點(diǎn)elm插入到結(jié)點(diǎn)slistelm后面。 slistelm：鏈表中某結(jié)點(diǎn)。 elm:要插入的結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| SLIST_INSERT_HEAD(head, elm, field) | 將結(jié)點(diǎn)elm插入到頭結(jié)點(diǎn)head后面。 head: 表頭結(jié)點(diǎn)。 elm:要插入的結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| SLIST_REMOVE_HEAD(head, field) | 移除將表頭結(jié)點(diǎn)下面一個(gè)結(jié)點(diǎn)。 head: 表頭結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| SLIST_REMOVE(head, elm, type, field) | 移除將elm結(jié)點(diǎn)，elm結(jié)點(diǎn)一定要是鏈表中一結(jié)點(diǎn)。 head: 表頭結(jié)點(diǎn)。 elm:某結(jié)點(diǎn)。 type: 結(jié)點(diǎn)類(lèi)型。 field:鏈表中鏈域的名稱(chēng)。 |
| SLIST_FOREACH(var, head, field) | 遍歷鏈表，相當(dāng)于for循環(huán)。 var: 結(jié)點(diǎn)類(lèi)型的變量名稱(chēng)。 head: 表頭結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
??????? singly-linked list 訪問(wèn)方法：
| 宏定義 | 說(shuō)明 |
| SLIST_EMPTY(head) | 判斷鏈表是否為空。 head: 表頭結(jié)點(diǎn)。 |
| SLIST_FIRST(head) | 訪問(wèn)鏈表里的第一個(gè)元素。 head: 表頭結(jié)點(diǎn)。 |
| SLIST_NEXT(elm, field) | 訪問(wèn)elm結(jié)點(diǎn)后一個(gè)元素。 elm:某結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
??????? 簡(jiǎn)單例子：
struct SListItem {int data;SLIST_ENTRY(SListItem) entry; }; /*struct SListItem{int data;struct {struct SListItem* sle_next;} entry;}*/ void slist_demo() {struct SListItem* item = NULL;SLIST_HEAD(SListHead, SListItem) shead;/*struct SListHead {struct SListItem* slh_first;} shead;*/SLIST_INIT(&shead);item = (struct SListItem*)malloc(sizeof(struct SListItem));item->data = 1;SLIST_INSERT_HEAD(&shead, item, entry);/*item->entry.sle_next = (&shead)->slh_first;(&shead)->slh_first = item;*/item = (struct SListItem*)malloc(sizeof(struct SListItem));item->data = 2;SLIST_INSERT_HEAD(&shead, item, entry);/*item->entry.sle_next = (&shead)->slh_first;(&shead)->slh_first = item;*/SLIST_FOREACH(item, &shead, entry){printf("%d ", item->data);}/*for(item = (&shead)->slh_first; item; item = item->entry.sle_next){...}*/printf("\n");while(!SLIST_EMPTY(&shead)){item = SLIST_FIRST(&shead);printf("remove %d\n", item->data);SLIST_REMOVE(&shead, item, SListItem, entry);free(item);}/*while(!((&shead)->slh_first == NULL)){item = (&shead)->slh_first;...(&shead)->slh_first = (&shead)->slh_first->entry.sle_next;...}*/ } /*結(jié)果 2 1 remove 2 remove 1 */雙向鏈表(list)
??????? list就是雙向鏈表，不過(guò)鏈域有點(diǎn)古怪，指向前一個(gè)結(jié)點(diǎn)是指針的指針。
??????? list 相關(guān)定義
| 宏定義 | 說(shuō)明 |
| LIST_HEAD(name, type) | 定義表頭結(jié)點(diǎn)。 name: 表頭結(jié)點(diǎn)名。 type: 結(jié)點(diǎn)類(lèi)型。 |
| LIST_HEAD_INITIALIZER(head) | 初始化頭結(jié)點(diǎn)。 head: 表頭結(jié)點(diǎn)。 |
| LIST_ENTRY(type) | 定義鏈表的鏈域。 type: 結(jié)點(diǎn)類(lèi)型。 |
??????? list函數(shù)
| 宏定義 | 說(shuō)明 |
| LIST_INIT(head) | 初始化頭結(jié)點(diǎn)。 head: 表頭結(jié)點(diǎn)。 |
| LIST_INSERT_AFTER(listelm, elm, field) | 將結(jié)點(diǎn)elm插入到結(jié)點(diǎn)listelm后面。 listelm：鏈表中某結(jié)點(diǎn)。 elm:要插入的結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| LIST_INSERT_BEFORE(listelm, elm, field) | 將結(jié)點(diǎn)elm插入到結(jié)點(diǎn)listelm前面。 listelm：鏈表中某結(jié)點(diǎn)。 elm:要插入的結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| LIST_INSERT_HEAD(head, elm, field) | 將結(jié)點(diǎn)elm插入到頭結(jié)點(diǎn)head后面。 head: 表頭結(jié)點(diǎn)。 elm:要插入的結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| LIST_REMOVE(elm, field) | 移除將elm結(jié)點(diǎn)。 elm:某結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
| LIST_FOREACH(var, head, field) | 遍歷鏈表，相當(dāng)于for循環(huán)。 var: 結(jié)點(diǎn)類(lèi)型的變量名稱(chēng)。 head: 表頭結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
??????? list訪問(wèn)方法
| 宏定義 | 說(shuō)明 |
| LIST_EMPTY(head) | 判斷鏈表是否為空。 head: 表頭結(jié)點(diǎn)。 |
| LIST_FIRST(head) | 訪問(wèn)鏈表里的第一個(gè)元素。 head: 表頭結(jié)點(diǎn)。 |
| LIST_NEXT(elm, field) | 訪問(wèn)elm結(jié)點(diǎn)后一個(gè)元素。 elm:某結(jié)點(diǎn)。 field:鏈表中鏈域的名稱(chēng)。 |
??????? 注意，因?yàn)閘ist是雙向鏈表，但在訪問(wèn)方法里沒(méi)有寫(xiě)出訪問(wèn)前一個(gè)元素的宏。因而可以這樣寫(xiě)一個(gè)，參數(shù)含義和LIST_NEXT一樣：
#define LIST_PRE(elm, field) \ (((elm)->field.le_pre) != &elm ? *((elm)->field.le_pre) : NULL)??????? 簡(jiǎn)單例子:
struct ListItem {int data;LIST_ENTRY(ListItem) entry; }; /* struct ListItem {int data;struct{struct ListItem* le_next;struct ListItem** le_prev;} entry; }; */ void list_demo() {struct ListItem* item = NULL;LIST_HEAD(ListHead, ListItem) lhead;/*struct ListHead {struct ListItem* lh_first;} lhead;*/LIST_INIT(&lhead);/*do{(&lhead)->lh_first = NULL;}while(0);*/item = (struct ListItem*)malloc(sizeof(struct ListItem));item->data = 1;LIST_INSERT_HEAD(&lhead, item, entry);item = (struct ListItem*)malloc(sizeof(struct ListItem));item->data = 2;LIST_INSERT_HEAD(&lhead, item, entry);/*do{if(((item)->entry.le_next = (&lhead)->lh_first) != NULL)(&lhead)->lh_first->entry.le_pre = &(elm)->entry.le_next;(&lhead)->lh_first = (item);(item)->entry.le_prev = &(&lhead)->lh_first;}while(0);*/LIST_FOREACH(item, &lhead, entry){printf("%d ", item->data);}/*for ((item) = ((&lhead)->lh_first);(item);(item) = ((item)->entry.le_next)){...} */printf("\n");while(!LIST_EMPTY(&lhead)){item = LIST_FIRST(&lhead);printf("remove %d\n", item->data);LIST_REMOVE(item, entry);free(item);}/*while(!((&lhead)->lh_first == NULL)){item = ((&lhead)->lh_first);...do{if ((item)->entry.le_next != NULL) \(item)->entry.le_next->entry.le_prev = \(item)->entry.le_prev; \*(item)->entry.le_prev = (item)->entry.le_next; \} while (0);...}*/ } /* 結(jié)果 2 1 remove 2 remove 1 */簡(jiǎn)單隊(duì)列(simple queue)
??????? 簡(jiǎn)單來(lái)說(shuō)，就是表對(duì)有兩個(gè)鏈域，分別指向頭和尾。
??????? simple queue 定義（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| SIMPLEQ_HEAD(name, type) | ? |
| SIMPLEQ_HEAD_INITIALIZER(head) | ? |
| SIMPLEQ_ENTRY(type) | ? |
??????? simple queue函數(shù)（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| SIMPLEQ_INIT(head) | ? |
| SIMPLEQ_INSERT_HEAD(head, elm, field) | ? |
| SIMPLEQ_INSERT_TAIL(head, elm, field) | ? |
| SIMPLEQ_INSERT_AFTER(head, listelm, elm, field) | ? |
| SIMPLEQ_REMOVE_HEAD(head, field) | ? |
| SIMPLEQ_REMOVE(head, elm, type, field) | ? |
| SIMPLEQ_FOREACH(var, head, field) | ? |
??????? simple queue方法（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| SIMPLEQ_EMPTY(head) | ? |
| SIMPLEQ_FIRST(head) | ? |
| SIMPLEQ_NEXT(elm, field) | ? |
??????? 簡(jiǎn)單例子：
??????? 用法與list用法類(lèi)似，不再重復(fù)。
單鏈尾隊(duì)列(singled-linked tail queue)
??????? 這個(gè)和Simple queue是一樣的，參考simple queue
??????? singled-linked tail queue定義(具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏)
| 宏定義 | 說(shuō)明 |
| STAILQ_HEAD(name, type) | ? |
| STAILQ_HEAD_INITIALIZER(head) | ? |
| STAILQ_ENTRY(type) | ? |
?????? tail queue 函數(shù)（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| STAILQ_INIT(head) | ? |
| STAILQ_INSERT_HEAD(head, elm, field) | ? |
| STAILQ_INSERT_TAIL(head, elm, field) | ? |
| STAILQ_INSERT_AFTER(head, listelm, elm, field) | ? |
| STAILQ_REMOVE_HEAD(head, field) | ? |
| STAILQ_REMOVE(head, elm, type, field) | ? |
| STAILQ_FOREACH(var, head, field) | ? |
??????? tail queue方法（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| STAILQ_EMPTY(head) | ? |
| STAILQ_FIRST(head) | ? |
| STAILQ_NEXT(elm, field) | ? |
??????? 簡(jiǎn)單例子：
??????? 用法與list用法類(lèi)似，不再重復(fù)。
循環(huán)隊(duì)列(circle queue)
??????? 循環(huán)隊(duì)列。
??????? circle queue定義（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| LIST_HEAD(name, type) | ? |
| LIST_HEAD_INITIALIZER(head) | ? |
| LIST_ENTRY(type) | ? |
??????? circle queue函數(shù)（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| LIST_INIT(head) | ? |
| LIST_INSERT_AFTER(listelm, elm, field) | ? |
| LIST_INSERT_BEFORE(listelm, elm, field) | ? |
| LIST_INSERT_HEAD(head, elm, field) | ? |
| LIST_REMOVE(elm, field) | ? |
| LIST_FOREACH(var, head, field) | ? |
??????? circle queue訪問(wèn)方法（具體說(shuō)明不再寫(xiě)，可以參考list的，或者就直接展開(kāi)宏）
| 宏定義 | 說(shuō)明 |
| LIST_EMPTY(head) | ? |
| LIST_FIRST(head) | ? |
| LIST_NEXT(elm, field) | ? |
??????? 簡(jiǎn)單例子
??????? 用法與list用法類(lèi)似，不再重復(fù)。
小結(jié)
??????? 雖然這是linux/unix實(shí)現(xiàn)的經(jīng)過(guò)長(zhǎng)時(shí)間考驗(yàn)的成熟的數(shù)據(jù)結(jié)構(gòu)，但是如果不是很熟悉的話，第一次用起來(lái)還是感覺(jué)挺不習(xí)慣的。但是好在各個(gè)數(shù)據(jù)結(jié)構(gòu)的定義和方法都非常類(lèi)似，接口比較統(tǒng)一，如果用多的了，熟悉了，感覺(jué)就不錯(cuò)了。
總結(jié)
以上是生活随笔為你收集整理的sys/queue.h的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。
- 上一篇： 试管婴儿黄体酮的作用
- 下一篇： sys/queue.h分析(图片复制不过