最近看node源碼的時候注意到libuv中的一個隊列實現(xiàn)，是c風(fēng)格的，也是linux內(nèi)核中常見的寫法，因為一直使用c++的隊列，所以對這種寫法看不太懂，經(jīng)過向牛人請教，終于明白了其中奧妙。
先一窺芳容：
#ifndef QUEUE_H_
#define QUEUE_H_
typedef void *QUEUE[2];
/* Private macros. */
#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1]))
#define QUEUE_PREV_NEXT(q) (QUEUE_NEXT(QUEUE_PREV(q)))
#define QUEUE_NEXT_PREV(q) (QUEUE_PREV(QUEUE_NEXT(q)))
/* Public macros. */
#define QUEUE_DATA(ptr, type, field) \
((type *) ((char *) (ptr) - ((char *) &((type *) 0)->field)))
#define QUEUE_FOREACH(q, h) \
for ((q) = QUEUE_NEXT(h); (q) != (h); (q) = QUEUE_NEXT(q))
#define QUEUE_EMPTY(q) \
((const QUEUE *) (q) == (const QUEUE *) QUEUE_NEXT(q))
#define QUEUE_HEAD(q) \
(QUEUE_NEXT(q))
#define QUEUE_INIT(q) \
do { \
QUEUE_NEXT(q) = (q); \
QUEUE_PREV(q) = (q); \
} \
while (0)
#define QUEUE_ADD(h, n) \
do { \
QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n); \
QUEUE_NEXT_PREV(n) = QUEUE_PREV(h); \
QUEUE_PREV(h) = QUEUE_PREV(n); \
QUEUE_PREV_NEXT(h) = (h); \
} \
while (0)
#define QUEUE_SPLIT(h, q, n) \
do { \
QUEUE_PREV(n) = QUEUE_PREV(h); \
QUEUE_PREV_NEXT(n) = (n); \
QUEUE_NEXT(n) = (q); \
QUEUE_PREV(h) = QUEUE_PREV(q); \
QUEUE_PREV_NEXT(h) = (h); \
QUEUE_PREV(q) = (n); \
} \
while (0)
#define QUEUE_INSERT_HEAD(h, q) \
do { \
QUEUE_NEXT(q) = QUEUE_NEXT(h); \
QUEUE_PREV(q) = (h); \
QUEUE_NEXT_PREV(q) = (q); \
QUEUE_NEXT(h) = (q); \
} \
while (0)
#define QUEUE_INSERT_TAIL(h, q) \
do { \
QUEUE_NEXT(q) = (h); \
QUEUE_PREV(q) = QUEUE_PREV(h); \
QUEUE_PREV_NEXT(q) = (q); \
QUEUE_PREV(h) = (q); \
} \
while (0)
#define QUEUE_REMOVE(q) \
do { \
QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); \
QUEUE_NEXT_PREV(q) = QUEUE_PREV(q); \
} \
while (0)
#endif /* QUEUE_H_ */
第一次看到全部用宏來寫的隊列，看起來也沒多少代碼，真的能實現(xiàn)雙向循環(huán)鏈表嗎？而且數(shù)據(jù)存在哪里呢? 和c++還是有很大區(qū)別的啊，沒有類，也沒有模板。沒有object這樣的基類。源碼可以在這里找到：https://github.com/libuv/libuv
關(guān)鍵點講解
** 1. 定義指針數(shù)組類型**
typedef void *QUEUE[2];
后面就可以這樣定義一個void*的數(shù)組了
/**
* A pointer to a list node.
*/
QUEUE* q;
** 2. 定義基本操作 **
#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1]))
數(shù)組的第0個表示下一個，1表示上一個。
這里使用(*(QUEUE **) &((*(q))[0]))這么復(fù)雜的表達是有兩個原因。一個是轉(zhuǎn)成左值，另一個是保存類型信息。
這樣會丟失類型信息
#define QUEUE_NEXT(q) ((*(q))[0])
這樣不是左值
#define QUEUE_PREV(q) ((QUEUE *) ((*(q))[1]))
** 3. 取值 **
這個隊列的實現(xiàn)和數(shù)據(jù)無關(guān)，所以宏里面看不到data的定義，是不是很神奇，像在c++這種面向?qū)ο蟮恼Z言中，我們一般通過迭代器來實現(xiàn)操作和數(shù)據(jù)的分離，而c語言可以用很巧妙的方式去高效的實現(xiàn)哦。
#define QUEUE_DATA(ptr, type, field) \
((type *) ((char *) (ptr) - ((char *) &((type *) 0)->field)))
((char *) &((type *) 0)->field))是拿到偏移量。為什么這樣就可以拿到偏移量？其實很好理解，把0當(dāng)做其實地址，取field的地址，就是偏移量啦。
我們先簡單看一下如何使用這個QUEUE_DATA
/**
* Retrieve a pointer to our first user john.
*/
q = QUEUE_HEAD(&queue);
//q = ((*(&queue))[0]) ;
/**
* Should retrieve the user behind the "q" pointer.
*/
user = QUEUE_DATA(q, struct user_s, node);
/**
* Should output the name of john.
*/
printf("Received first inserted user: %s who is %d.\n",
user->name, user->age);
現(xiàn)在不用仔細看，后面會把例子都貼出來。只要知道屬性name，age怎么拿到就好。
4. 隊列操作
我們通過上面的代碼，可以知道隊列的操作是通過宏定義的，宏的名稱已經(jīng)很容易看懂啦，所以這里不仔細過了。
例子
例子加上上面難點的講解，應(yīng)該能說的清楚了。
#include "queue.h"
#include <stdio.h>
/**
* A pointer to a list node.
*/
static QUEUE* q;
/**
* Our circulary list.
*/
static QUEUE queue;
/**
* Our item struct we want to store in queue.
*/
struct user_s {
int age;
char* name;
QUEUE node;
};
int main() {
/**
* This will be our user pointer.
* It will point to the user we received from the queue.
*/
struct user_s* user;
/**
* John is 44.
*/
struct user_s john;
john.name = "john";
john.age = 44;
/**
* Henry is 32.
*/
struct user_s henry;
henry.name = "henry";
henry.age = 32;
/**
* Willy is 99.
*/
struct user_s willy;
willy.name = "willy";
willy.age = 99;
/**
* Initialize the queue of each user.
*/
QUEUE_INIT(&queue);
QUEUE_INIT(&john.node);
QUEUE_INIT(&henry.node);
QUEUE_INIT(&willy.node);
((*(&queue))[0]) = john.node;
(*(QUEUE **) &((*(&queue))[0])) = &john.node;
/**
* Lets insert each user to the tail of the list.
*/
QUEUE_INSERT_TAIL(&queue, &john.node);
QUEUE_INSERT_TAIL(&queue, &henry.node);
QUEUE_INSERT_TAIL(&queue, &willy.node);
/**
* Retrieve a pointer to our first user john.
*/
q = QUEUE_HEAD(&queue);
//q = ((*(&queue))[0]) ;
/**
* Should retrieve the user behind the "q" pointer.
*/
user = QUEUE_DATA(q, struct user_s, node);
/**
* Should output the name of john.
*/
printf("Received first inserted user: %s who is %d.\n",
user->name, user->age);
/**
* Now lets remove john from the queue.
*/
QUEUE_REMOVE(q);
/**
* Lets output the other two users through a for each loop.
*/
QUEUE_FOREACH(q, &queue) {
user = QUEUE_DATA(q, struct user_s, node);
printf("Received rest inserted users: %s who is %d.\n",
user->name, user->age);
}
return 0;
}
- 如何拿出數(shù)據(jù)的
user = QUEUE_DATA(q, struct user_s, node);
實際上是用q的地址減去8
注意q實際上是&john.node
找到首地址
- 環(huán)形雙向鏈表圖
上個手抄本，么么噠。
手抄本
總結(jié)
有時間還想把C++，C#和JS如何實現(xiàn)隊列拿出來比較比較，實際上算法的思想應(yīng)該是一樣的，只是有的性能高，有的代碼易讀性好，代碼少。哈哈，由于c語言一直處在浩強老濕那本書的水平，所以今天看到這個實現(xiàn)還是覺得很爽。。。
