用稳定归并排序排列显示模式
Linux DRM 使用通用 list_sort 对显示模式链表排序；底层归并通过相等时优先取较早元素来保持稳定性。
工程问题#
显示器提供多个分辨率和刷新率候选，需要按首选标记、像素面积、刷新率与像素时钟排列，同时保持比较相等项的既有顺序。
实际实现#
drm_mode_sort 提供 drm_mode_compare 给 list_sort。排序器将循环双向链表暂时转为单链表，维护按规模组织的有序子链表并逐步归并；比较相等时从较早子链表取元素，最终一边归并一边恢复 prev 与循环链接。
处理流程#
- DRM 比较器定义显示模式的优先顺序
- 将链表元素逐步组成并归并为有序子链表
- 相等时保留较早输入元素优先；最终归并恢复双向循环结构
源码片段#
固定版本 · 原文摘录1862/**1863 * drm_mode_sort - sort mode list1864 * @mode_list: list of drm_display_mode structures to sort1865 *1866 * Sort @mode_list by favorability, moving good modes to the head of the list.1867 */1868void drm_mode_sort(struct list_head *mode_list)1869{1870 list_sort(NULL, mode_list, drm_mode_compare);1871}1872EXPORT_SYMBOL(drm_mode_sort);DRM 将显示模式链表与专用比较器交给通用 list_sort。业务排序规则与链表排序机制通过比较函数分离。
21 for (;;) {22 /* if equal, take 'a' -- important for sort stability */23 if (cmp(priv, a, b) <= 0) {24 *tail = a;25 tail = &a->next;26 a = a->next;27 if (!a) {28 *tail = b;29 break;30 }31 } else {32 *tail = b;33 tail = &b->next;34 b = b->next;35 if (!b) {36 *tail = a;37 break;38 }39 }40 }两个输入链表已经有序。比较结果相等时选择较早的 a；任一链表耗尽便接上另一条链表的剩余部分，这一局部规则维持排序稳定性。
一段真实调用与一段底层归并主体；排序不复制对象，只调整链接。DRM 源文件与通用 list_sort 文件各自保留其许可证。
收益与取舍#
工程分析带来的收益
- 稳定性由归并时的相等分支直接保证
- 利用已有节点链接重排对象，无需复制显示模式对象或分配同规模辅助数组
付出的代价
- 工程分析：归并比较量为 O(n log n)，实际成本还包括比较器计算与指针访存
- 排序期间会暂时改变链表表示，调用者必须保证独占修改及对象有效
- 比较器必须满足一致顺序；通用排序器并不验证显示模式能否被硬件真正使用
可比较的选择
数组排序将节点引用收集到数组可改善顺序访问，但要额外存储并明确排序是否稳定。
插入排序非常小或接近有序的列表实现简单；一般输入可能需要 O(n²) 次比较。
版本与适用范围#
Linux v6.12 的 drm_mode_sort 与 lib/list_sort.c；排序给出模式偏好，模式校验、连接器状态与最终 modeset 属于其他流程。
参考来源#
源码、官方文档与原始论文drivers/gpu/drm/drm_modes.c · drm_mode_compare / drm_mode_sort
lib/list_sort.c · list_sort invariant / merge scheduling
相关实现与比较#
4 个相关案例伙伴分配器把空闲物理页组织为不同 order 的连续块，并用空闲链表管理同阶块。
limit_req 把漏桶计算、红黑树查状态与队列回收组合起来，按配置的 key 管理请求速率。
QEMU 的 QEMUTimerList 用有序单链表维护定时器，链表头就是下一到期项。
缓存块命中后可能需要从队列中间移除，双向链表让这一步保持常数时间。