libuv queue的贯彻

近来羁押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;
}
  1. 怎么用出多少的

user = QUEUE_DATA(q, struct user_s, node);

骨子里是为此q的地点减去8
留神q实际上是&john.node

找到首地址

  1. 环形双向链表图
    落得个手抄本,么么哒。

手抄本

总结

发时间还惦记将C++,C#以及JS如何促成队列拿出去比较比,实际上算法的沉思应是平的,只是片性能大,有的代码易读性好,代码少。哈哈,由于c语言一直处在浩强老湿那本书的程度,所以今天看到这实现还是当十分爽。。。