ngx_queue_sort

1 定义ngx_queue_sort 函数 定义在 ./nginx-1.24.0/src/core/ngx_queue.cvoidngx_queue_sort(ngx_queue_t*queue,ngx_int_t(*cmp)(constngx_queue_t*,constngx_queue_t*)){ngx_queue_t*q,*prev,*next;qngx_queue_head(queue);if(qngx_queue_last(queue)){return;}for(qngx_queue_next(q);q!ngx_queue_sentinel(queue);qnext){prevngx_queue_prev(q);nextngx_queue_next(q);ngx_queue_remove(q);do{if(cmp(prev,q)0){break;}prevngx_queue_prev(prev);}while(prev!ngx_queue_sentinel(queue));ngx_queue_insert_after(prev,q);}}ngx_queue_sort 函数对 nginx 的双向链表进行原地插入排序。 它遍历链表中的每个元素将其从原位置移除 然后在已排序的部分中找到正确的位置插入 最终使整个链表按照用户提供的比较函数有序排列。2 详解1 函数签名voidngx_queue_sort(ngx_queue_t*queue,ngx_int_t(*cmp)(constngx_queue_t*,constngx_queue_t*))返回值 该函数不返回任何值。 排序操作直接在传入的链表上进行 即原地排序不需要返回新的链表头参数 ngx_queue_t *queue 该参数是一个指向链表哨兵节点的指针 通过它可以访问整个链表。 调用时queue 指向链表的哨兵 哨兵本身不存储数据仅作为头尾标记。 该链表是循环的哨兵的 next 指向第一个元素prev 指向最后一个元素。 ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *) 这是一个函数指针指向用户提供的比较函数。 其具体含义如下 返回类型 ngx_int_t nginx 中通常定义为 intptr_t 或 int用于返回比较结果。 参数列表 (const ngx_queue_t *, const ngx_queue_t *) 两个参数都是指向 ngx_queue_t 的常量指针分别代表待比较的两个链表节点元素。 比较逻辑由用户实现应返回 0 (负数) 第一个参数 小于 第二个参数 第一个参数排在前面 0 (零) 两个参数 相等 保持原有相对顺序 (稳定排序) 0 (正数) 第一个参数 大于 第二个参数 第二个参数排在前面 函数指针的使用方式 在 ngx_queue_sort 内部会通过 cmp(prev, q) 的形式调用该比较函数 以确定节点 q 应插入到 prev 的前面还是后面。2 逻辑流程1 局部变量 2 链表检查 3 遍历排序1 局部变量{ngx_queue_t*q,*prev,*next;2 链表检查qngx_queue_head(queue);if(qngx_queue_last(queue)){return;}目的排除不需要排序的情况 判断逻辑的三种情况 #1 链表为空 ngx_queue_head(queue) 和 ngx_queue_last(queue) 都等于哨兵 二者相等条件成立函数返回。空链表无需排序。 #2 链表只有一个有效节点 头节点和尾节点指向同一个有效节点 二者相等条件成立函数返回。单元素链表已有序。 #3 链表有两个或以上有效节点 头节点和尾节点不同条件不成立继续执行后续的插入排序循环。3 遍历排序for(qngx_queue_next(q);q!ngx_queue_sentinel(queue);qnext){prevngx_queue_prev(q);nextngx_queue_next(q);ngx_queue_remove(q);do{if(cmp(prev,q)0){break;}prevngx_queue_prev(prev);}while(prev!ngx_queue_sentinel(queue));ngx_queue_insert_after(prev,q);}}#1 循环初始化q ngx_queue_next(q) 这里将 q 更新为链表的第二个元素因为第一个元素作为已排序部分的基础不需要移动。 循环条件q ! ngx_queue_sentinel(queue) 当 q 没有指向哨兵节点时说明还有待处理的元素。 哨兵是链表的虚拟头尾标记遍历到哨兵意味着已经处理完所有有效节点。 循环增量q next 在每次迭代末尾将 q 更新为之前保存的 next即原链表中当前元素的下一个节点。 因为当前元素 q 可能在插入过程中被移动所以必须提前保存它的后继。#2 在移除 q 之前保存它在原链表中的前驱 prev 和后继 next。 prev 用于搜索插入位置从当前位置向前查找next 用于循环继续遍历。#3 将节点 q 从链表中临时移除使其脱离原位置。 这样后续的插入操作可以自由地将 q 放到任何地方。#4 搜索插入位置 从原前驱 prev 开始不断向前向链表头部方向移动直到找到正确的插入点。 比较逻辑 如果 cmp(prev, q) 0说明 prev 应该排在 q 之前或相等 则 q 应该插入在 prev 的后面此时终止循环。 否则继续向前移动 prev即 prev ngx_queue_prev(prev)。 边界条件 如果一直移动到哨兵节点prev ngx_queue_sentinel(queue) 说明 q 应该成为新的第一个元素即插入在哨兵之后。 为什么用 do-while 因为 prev 最初至少指向第一个元素q 至少是第二个元素 所以至少需要比较一次。 do-while 保证了至少执行一次比较逻辑简洁无需额外处理 prev 为哨兵的初始情况。#5 将节点 q 插入到 prev 的后面。 如果 prev 是哨兵则插入到链表头部 否则插入到已排序部分的适当位置。 插入后q 就位于已排序序列的正确位置已排序部分增长一个元素。