Chinaunix首页 | 论坛 | 博客
  • 博客访问: 191407
  • 博文数量: 27
  • 博客积分: 725
  • 博客等级: 上士
  • 技术积分: 347
  • 用 户 组: 普通用户
  • 注册时间: 2008-10-04 09:01
文章分类

全部博文(27)

文章存档

2012年(15)

2011年(12)

分类: LINUX

2012-03-27 20:22:39

Nginx中大量用到链表操作,关于链表的使用,据我观察,有三种不同的方法,接下来我将好好分析一下:
首先第一种即将单链表与数组相结合,一个链表节点并非只保存一块数据,而是保存一块可以容纳若干块数据的缓冲区,具体实现在ngx_list.c和ngx_list.h两个文件中;第二种即为比较常规的双向环链,具体实现在ngx_queue.h中;第三种实现在ngx_event_posted.h中,其实也是双向链表,至于为什么要实现成这样,我会在后面谈谈我的看法。这里,我想重点向大家展示后两种的实现,大家看看有什么区别,希望能有人告诉我为什么要有这样的区别。以下贴出的代码只是为了展示实现机制,并不一定完全取自Nginx源码。
 
先给出第一种实现,如下:

  1. struct list_head {
  2.     struct list_head *next, *prev;
  3. };

  4. #define LIST_HEAD_INIT(name) { &(name), &(name) }

  5. #define LIST_HEAD(name) \
  6.     struct list_head name = LIST_HEAD_INIT(name)

  7. static inline void INIT_LIST_HEAD(struct list_head *list)
  8. {
  9.     list->next = list;
  10.     list->prev = list;
  11. }

  12. static inline void __list_add(struct list_head *new,
  13.              struct list_head *prev,
  14.              struct list_head *next)
  15. {
  16.     next->prev = new;
  17.     new->next = next;
  18.     new->prev = prev;
  19.     prev->next = new;
  20. }

  21. static inline void list_add(struct list_head *new, struct list_head *head)
  22. {
  23.     __list_add(new, head, head->next);
  24. }

  25. static inline void list_add_tail(struct list_head *new, struct list_head *head)
  26. {
  27.     __list_add(new, head->prev, head);
  28. }

  29. static inline void __list_del(struct list_head * prev, struct list_head * next)
  30. {
  31.     next->prev = prev;
  32.     prev->next = next;
  33. }

  34. static inline void list_del(struct list_head *entry)
  35. {
  36.     __list_del(entry->prev, entry->next);
  37.     entry->next = LIST_POISON1;
  38.     entry->prev = LIST_POISON2;
  39. }

再给出第二种实现,如下:

  1. struct hlist_head {
  2.     struct hlist_node *first;
  3. };

  4. struct hlist_node {
  5.     struct hlist_node *next, **pprev;
  6. };

  7. #define HLIST_HEAD_INIT { .first = NULL }
  8. #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL }
  9. #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL)

  10. static inline void INIT_HLIST_NODE(struct hlist_node *h)
  11. {
  12.     h->next = NULL;
  13.     h->pprev = NULL;
  14. }

  15. static inline int hlist_unhashed(const struct hlist_node *h)
  16. {
  17.     return !h->pprev;
  18. }

  19. static inline int hlist_empty(const struct hlist_head *h)
  20. {
  21.     return !h->first;
  22. }

  23. static inline void __hlist_del(struct hlist_node *n)
  24. {
  25.     struct hlist_node *next = n->next;
  26.     struct hlist_node **pprev = n->pprev;
  27.     *pprev = next;
  28.     if (next)
  29.         next->pprev = pprev;
  30. }

  31. static inline void hlist_del(struct hlist_node *n)
  32. {
  33.     __hlist_del(n);
  34.     n->next = LIST_POISON1;
  35.     n->pprev = LIST_POISON2;
  36. }

  37. static inline void hlist_del_init(struct hlist_node *n)
  38. {
  39.     if (!hlist_unhashed(n)) {
  40.         __hlist_del(n);
  41.         INIT_HLIST_NODE(n);
  42.     }
  43. }

  44. static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h)
  45. {
  46.     struct hlist_node *first = h->first;
  47.     n->next = first;
  48.     if (first)
  49.         first->pprev = &n->next;
  50.     h->first = n;
  51.     n->pprev = &h->first;
  52. }

  53. /* next must be != NULL */
  54. static inline void hlist_add_before(struct hlist_node *n,
  55.                     struct hlist_node *next)
  56. {
  57.     n->pprev = next->pprev;
  58.     n->next = next;
  59.     next->pprev = &n->next;
  60.     *(n->pprev) = n;
  61. }

  62. static inline void hlist_add_after(struct hlist_node *n,
  63.                     struct hlist_node *next)
  64. {
  65.     next->next = n->next;
  66.     n->next = next;
  67.     next->pprev = &n->next;

  68.     if(next->next)
  69.         next->next->pprev = &next->next;
  70. }

以上两种实现都摘自Linux内核,第一种也许大家都很熟悉,但是第二种可能平时用的相对少一些吧。在Nginx中,在事件处理机制里用到了第二种实现。对于所有到达的事件,Nginx都没有立刻处理,而是先将其加入到任务队列,等稍后再一起处理。我们看看其任务队列是如何实现的:

  1. struct ngx_event_s {
  2.      /* the links of the posted queue */
  3.     ngx_event_t *next;
  4.     ngx_event_t **prev;
  5. }
  6.     
  7. ngx_thread_volatile ngx_event_t *ngx_posted_accept_events;
  8. ngx_thread_volatile ngx_event_t *ngx_posted_events;

  9. #define ngx_locked_post_event(ev, queue) \
  10.                                                                               \
  11.     if (ev->prev == NULL) { \
  12.         ev->next = (ngx_event_t *) *queue; \
  13.         ev->prev = (ngx_event_t **) queue; \
  14.         *queue = ev; \
  15.                                                                               \
  16.         if (ev->next) { \
  17.             ev->next->prev = &ev->next; \
  18.         } \
  19.     }

  20. #define ngx_delete_posted_event(ev) \
  21.                                                                               \
  22.     *(ev->prev) = ev->next; \
  23.                                                                               \
  24.     if (ev->next) { \
  25.         ev->next->prev = ev->prev; \
  26.     } \
  27.                                                                               \
  28.     ev->prev = NULL;
在我看来,这两种实现的区别在于头结点的表示,第一种实现通常其头结点为struct list_head head;
即为一个结构体,而非一个指针,但是事实上这个头结点消耗了两个指针。而第二种实现通常其头结点为 struct list_head *head,即只消耗了一个指针,这种实现非常适合于hash链表中,在hash链中,每个头结点都是一个指针保存在hash数组中。如果hash因子很大的话,第二种实现会节约不少内存。Nginx中的任务队列其实可看作是hash因子为1的hash链吧。

 
阅读(3126) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~

重返人生2012-03-28 22:24:39

一般情况下用不到链表吧~