ngx_sort

1 定义ngx_sort 函数 定义在 ./nginx-1.24.0/src/core/ngx_string.cvoidngx_sort(void*base,size_tn,size_tsize,ngx_int_t(*cmp)(constvoid*,constvoid*)){u_char*p1,*p2,*p;pngx_alloc(size,ngx_cycle-log);if(pNULL){return;}for(p1(u_char*)basesize;p1(u_char*)basen*size;p1size){ngx_memcpy(p,p1,size);for(p2p1;p2(u_char*)basecmp(p2-size,p)0;p2-size){ngx_memcpy(p2,p2-size,size);}ngx_memcpy(p2,p,size);}ngx_free(p);}ngx_sort 函数实现了一个 通用的插入排序算法 用于对任意类型的数组进行原地升序排序排序规则由传入的比较函数决定。 它通过临时分配一个元素大小的内存作为缓冲依次将每个元素插入到已排序部分的正确位置。2 详解1 函数签名voidngx_sort(void*base,size_tn,size_tsize,ngx_int_t(*cmp)(constvoid*,constvoid*))返回值 无返回值 该函数采用原地排序In-place Sorting。 所有交换和移动操作直接作用于 base 指向的原始内存区域 排序完成后原数组即变为有序状态无需返回新指针或副本参数 #1 void *base 指向待排序数组的首元素的指针 #2 size_t n 数组中元素的总个数 #3 size_t size 每个元素占用的字节数 #4 ngx_int_t (*cmp)(const void *, const void *) 函数指针 指向用户提供的比较函数的指针。 该比较函数定义了元素之间的“大小”关系从而决定排序的升序或降序。 比较函数的约定 返回值 0表示第一个参数 大于 第二个参数。 返回值 0表示两个参数 相等。 返回值 0表示第一个参数 小于 第二个参数。2 逻辑流程1 局部变量 2 分配临时内存 3 比较排序 4 释放临时内存1 局部变量{u_char*p1,*p2,*p;2 分配临时内存pngx_alloc(size,ngx_cycle-log);if(pNULL){return;}size需要分配的字节数。 log日志对象指针用于记录分配失败时的错误信息。 size当前调用中传入的参数表示待排序数组中每个元素的大小字节数。 ngx_sort 需要一块恰好能容纳一个元素的临时缓冲区 用于在移动元素时暂存当前待插入的值。 因为插入排序过程中需要将待插入元素保存起来 然后将其前面的较大元素依次后移 如果不保存后移操作会覆盖掉当前元素的值。3 比较排序for(p1(u_char*)basesize;p1(u_char*)basen*size;p1size){ngx_memcpy(p,p1,size);for(p2p1;p2(u_char*)basecmp(p2-size,p)0;p2-size){ngx_memcpy(p2,p2-size,size);}ngx_memcpy(p2,p,size);}#1 初始化外层循环的指针 p1。 (u_char *) base 将 base 强制转换为无符号字节指针以便进行精确的字节级指针算术。 加上 size 后p1 指向数组的第二个元素索引为 1的首地址。 插入排序将第一个元素视为初始的“已排序”部分因此从第二个元素开始依次插入到已排序序列中。#2 外层循环的继续条件。 (u_char *) base n * size 计算出数组最后一个元素之后的第一个字节地址即数组的结束边界。 只要 p1 还没有到达这个边界循环就继续。 意义 确保遍历数组中下标从 1 到 n-1 的所有元素 当 p1 等于结束边界时所有元素都已处理完毕。#3 每轮循环结束后将 p1 向后移动 size 字节即指向下一个待插入的元素#4 将当前待插入的元素复制到临时缓冲区 p 中#5 初始化内层循环的指针 p2。 p2 指向当前待插入元素的位置即 p1 的值。 意义 内层循环将从当前位置开始向左扫描已排序部分 p2 表示当前要比较并可能移动元素的位置#6 内层循环的继续条件。 包含两个必须同时满足的条件 p2 (u_char *) base 确保 p2 没有指向数组的第一个元素之前即 p2 至少大于数组起始地址。 因为 p2 - size 需要指向一个有效元素。 cmp(p2 - size, p) 0 调用比较函数判断 p2 前面的那个元素p2 - size 指向是否 大于 临时缓冲区 p 中保存的当前元素。 如果大于 0说明前一个元素比待插入元素大需要将其向后移动。 意义 从右向左遍历已排序部分只要前一个元素大于待插入元素就继续循环为待插入元素腾出空间。 循环条件中 保证了排序的稳定性相等元素不会移动#7 内层循环的迭代步长。 每轮循环结束后将 p2 向左移动 size 字节即指向更前一个元素的位置。 继续比较下一个左边的元素直到找到合适的位置或到达数组开头。#8 将前一个元素左边相邻元素复制到当前 p2 的位置。 p2 - size 指向左边相邻元素 ngx_memcpy(p2, p2 - size, size) 将这个元素向右移动一个位置覆盖当前 p2 的内容。 意义 这是插入排序中“移动元素”的核心操作。 较大元素向右移动为待插入元素腾出空间。 注意此时 p2 原值即当前待插入元素已经被保存到 p 中所以覆盖是安全的。#9 将临时保存的待插入元素放到正确的位置。 内层循环结束后p2 指向了第一个不需要移动的位置即左边元素 ≤ 待插入元素的位置或者 p2 已到达数组开头。此时将临时缓冲区 p 中的元素复制到 p2 指向的位置。 意义 完成当前元素的插入操作。至此从数组开头到 p1 的位置包括刚刚插入的元素已经全部有序。#10 逻辑流程: #10-1 外层循环依次处理每个元素从第二个到最后一个。 #10-2 内层循环将当前元素与已排序部分从右向左比较将大于它的元素向右移动。 #10-3 最后将当前元素插入到正确位置。4 释放临时内存ngx_free(p);}