最近看node源码的时候注意到libuv中的一个队列实现，是c风格的，也是linux内核中常见的写法，因为一直使用c++的队列，所以对这种写法看不太懂，经过向牛人请教，终于明白了其中奥妙。
先一窥芳容：
#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_ */
第一次看到全部用宏来写的队列，看起来也没多少代码，真的能实现双向循环链表吗？而且数据存在哪里呢? 和c++还是有很大区别的啊，没有类，也没有模板。没有object这样的基类。源码可以在这里找到：https://github.com/libuv/libuv
关键点讲解
** 1. 定义指针数组类型**
typedef void *QUEUE[2];
后面就可以这样定义一个void*的数组了
/**
* A pointer to a list node.
*/
QUEUE* q;
** 2. 定义基本操作 **
#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1]))
数组的第0个表示下一个，1表示上一个。
这里使用(*(QUEUE **) &((*(q))[0]))这么复杂的表达是有两个原因。一个是转成左值，另一个是保存类型信息。
这样会丢失类型信息
#define QUEUE_NEXT(q) ((*(q))[0])
这样不是左值
#define QUEUE_PREV(q) ((QUEUE *) ((*(q))[1]))
** 3. 取值 **
这个队列的实现和数据无关，所以宏里面看不到data的定义，是不是很神奇，像在c++这种面向对象的语言中，我们一般通过迭代器来实现操作和数据的分离，而c语言可以用很巧妙的方式去高效的实现哦。
#define QUEUE_DATA(ptr, type, field) \
((type *) ((char *) (ptr) - ((char *) &((type *) 0)->field)))
((char *) &((type *) 0)->field))是拿到偏移量。为什么这样就可以拿到偏移量？其实很好理解，把0当做其实地址，取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);
现在不用仔细看，后面会把例子都贴出来。只要知道属性name，age怎么拿到就好。
4. 队列操作
我们通过上面的代码，可以知道队列的操作是通过宏定义的，宏的名称已经很容易看懂啦，所以这里不仔细过了。
例子
例子加上上面难点的讲解，应该能说的清楚了。
#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;
}
- 如何拿出数据的
user = QUEUE_DATA(q, struct user_s, node);
实际上是用q的地址减去8
注意q实际上是&john.node
找到首地址
- 环形双向链表图
上个手抄本，么么哒。
手抄本
总结
有时间还想把C++，C#和JS如何实现队列拿出来比较比较，实际上算法的思想应该是一样的，只是有的性能高，有的代码易读性好，代码少。哈哈，由于c语言一直处在浩强老湿那本书的水平，所以今天看到这个实现还是觉得很爽。。。
网友评论