2. nginx基本数据结构之ngx_str_t ngx_queue_t

1420阅读　0评论2015-06-01　mizhouli
分类：LINUX

欢迎讨论指正。

这两个很简单，放在一起介绍。

1. 二进制安全字符串
保存长度，可以不以'\0'结尾，字符串中可以包含任何字符。
之所以列出，是因为nginx中大部分字符串都是使用 ngx_str_t 保存，使用频率非常高。
  

点击(此处)折叠或打开

  1. typedef struct {
  2.     size_t len;
  3.     u_char *data;
  4. } ngx_str_t;
  5. // 定义并初始化一个 ngx_str_t 变量，注意 由于使用sizeof，故str 应为常量字符串
  6. #define ngx_string(str) { sizeof(str) - 1, (u_char *) str }

  8. // 定义并初始化一个 ngx_str_t 变量，值为空串
  9. #define ngx_null_string { 0, NULL }

  11. // 修改一个 ngx_str_t 变量，注意 由于使用sizeof，故str 应为常量字符串
  12. #define ngx_str_set(str, text) \
  13.     (str)->len = sizeof(text) - 1; (str)->data = (u_char *) text

  15. // 修改一个 ngx_str_t 变量为空串
  16. #define ngx_str_null(str) (str)->len = 0; (str)->data = NULL
2. 带有头节点的双向循环队列
类似linux内核中的 list_head ,仅有链接指针，无数据，不负责内存分配，一般嵌入其他结构使用。

nginx_queue.h

点击(此处)折叠或打开

  1. /*
  2.  * Copyright (C) Igor Sysoev
  3.  * Copyright (C) Nginx, Inc.
  4.  */


  7. #include <ngx_config.h>
  8. #include <ngx_core.h>


  11. #ifndef _NGX_QUEUE_H_INCLUDED_
  12. #define _NGX_QUEUE_H_INCLUDED_



  16. typedef struct ngx_queue_s ngx_queue_t;

  18. struct ngx_queue_s {
  19.     ngx_queue_t *prev;
  20.     ngx_queue_t *next;
  21. };


  24. // 初始化队列，前向、后向指针都指到队列的头部本身
  25. #define ngx_queue_init(q) \
  26.     (q)->prev = q; \
  27.     (q)->next = q

  29. // 置空队列
  30. #define ngx_queue_empty(h) \
  31.     (h == (h)->prev)

  33. // 在头节点后插入节点x
  34. #define ngx_queue_insert_head(h, x) \
  35.     (x)->next = (h)->next; \
  36.     (x)->next->prev = x; \
  37.     (x)->prev = h; \
  38.     (h)->next = x


  41. #define ngx_queue_insert_after ngx_queue_insert_head

  43. // 插入队尾x
  44. #define ngx_queue_insert_tail(h, x) \
  45.     (x)->prev = (h)->prev; \
  46.     (x)->prev->next = x; \
  47.     (x)->next = h; \
  48.     (h)->prev = x

  50. // 获取队列的第一关元素
  51. #define ngx_queue_head(h) \
  52.     (h)->next

  54. // 获取队列的最后一个元素
  55. #define ngx_queue_last(h) \
  56.     (h)->prev

  58. // 获取哨兵，即头节点
  59. #define ngx_queue_sentinel(h) \
  60.     (h)

  62. // 获取下一个元素
  63. #define ngx_queue_next(q) \
  64.     (q)->next

  66. // 获取前一个元素
  67. #define ngx_queue_prev(q) \
  68.     (q)->prev


  71. // 从队列中移除x元素
  72. #if (NGX_DEBUG)

  74. #define ngx_queue_remove(x) \
  75.     (x)->next->prev = (x)->prev; \
  76.     (x)->prev->next = (x)->next; \
  77.     (x)->prev = NULL; \
  78.     (x)->next = NULL

  80. #else

  82. #define ngx_queue_remove(x) \
  83.     (x)->next->prev = (x)->prev; \
  84.     (x)->prev->next = (x)->next

  86. #endif

  88. // 把以h为队头的队列分割为2个队列，其中分割点q，另一个队列的头为n，q节点属于n为头的队列
  89. #define ngx_queue_split(h, q, n) \
  90.     (n)->prev = (h)->prev; \
  91.     (n)->prev->next = n; \
  92.     (n)->next = q; \
  93.     (h)->prev = (q)->prev; \
  94.     (h)->prev->next = h; \
  95.     (q)->prev = n;

  97. // 合并队列h，n
  98. #define ngx_queue_add(h, n) \
  99.     (h)->prev->next = (n)->next; \
  100.     (n)->next->prev = (h)->prev; \
  101.     (h)->prev = (n)->prev; \
  102.     (h)->prev->next = h;

  104. // 获取节点的数据指针,即宿主结构的指针。 q是队列中的节点，type队列类型，link是队列类型中ngx_queue_t的元素名
  105. #define ngx_queue_data(q, type, link) \
  106.     (type *) ((u_char *) q - offsetof(type, link))


  109. ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);
  110. void ngx_queue_sort(ngx_queue_t *queue,
  111.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));


  114. #endif /* _NGX_QUEUE_H_INCLUDED_ */
ngx_queue.c

点击(此处)折叠或打开

  1. /*
  2.  * find the middle queue element if the queue has odd number of elements
  3.  * or the first element of the queue's second part otherwise
  4.  */
  5. // 获取队列的中间节点的指针
  6. ngx_queue_t *
  7. ngx_queue_middle(ngx_queue_t *queue)
  8. {
  9.     ngx_queue_t *middle, *next;

  11.     // middle、next 都指向队列的第一个元素
  12.     middle = ngx_queue_head(queue);

  14.     if (middle == ngx_queue_last(queue)) {
  15.         // 只有一个元素，返回该元素
  16.         return middle;
  17.     }

  19.     next = ngx_queue_head(queue);

  21.     /*
  22.      * 循环中 middle前进一步， next前进2步，当next达到队尾，middle即为队列的中间节点
  23.      */
  24.     for ( ;; ) {
  25.         // middle前进一步
  26.         middle = ngx_queue_next(middle);

  28.         // next前进一步
  29.         next = ngx_queue_next(next);

  31.         // next到达队列尾部
  32.         if (next == ngx_queue_last(queue)) {
  33.             return middle;
  34.         }

  36.         // next再前进一步
  37.         next = ngx_queue_next(next);

  39.         // next到达队列尾部
  40.         if (next == ngx_queue_last(queue)) {
  41.             return middle;
  42.         }
  43.     }
  44. }


  47. // 稳定的插入排序
  48. /* the stable insertion sort */

  50. void
  51. ngx_queue_sort(ngx_queue_t *queue,
  52.     ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
  53. {
  54.     ngx_queue_t *q, *prev, *next;

  56.     q = ngx_queue_head(queue);

  58.     if (q == ngx_queue_last(queue)) {
  59.         return;
  60.     }

  62.     for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {

  64.         prev = ngx_queue_prev(q);
  65.         next = ngx_queue_next(q);

  67.         ngx_queue_remove(q);

  69.         do {
  70.             if (cmp(prev, q) <= 0) {
  71.                 break;
  72.             }

  74.             prev = ngx_queue_prev(prev);

  76.         } while (prev != ngx_queue_sentinel(queue));

  78.         ngx_queue_insert_after(prev, q);
  79.     }
  80. }




上一篇：1. nginx的编译及安装
下一篇：3. nginx基本数据结构之动态数组ngx_array_t