标题：glibc的qsort源码阅读笔记
出处：Felix021
时间：Tue, 02 Nov 2010 21:42:19 +0000
作者：felix021
地址：https://www.felix021.com/blog/read.php?1951

内容：
C标准中的qsort函数，可以对任意类型的数组进行快速排序，用起来也还算方便，不过行为有一点诡异。加上之前曾经看过一篇文章（沈大写的，曾经登上过ecom的双周刊，居然在这个youalab.com也等出来了-。-），说是qsort不是线程安全的，所以把glibc的代码翻出来，看看qsort的具体实现。

用Ubuntu的话，找代码就很容易了：引用
$ apt-get source libc6
$ cd eglibc-xxxx
$ grep -r . -Hne qsort | grep void


可以看到qsort是在stdlib.h里面的，源码在msort.c 302行，调用了qsort_r函数：void
qsort (void *b, size_t n, size_t s, __compar_fn_t cmp)
{
  return qsort_r (b, n, s, (__compar_d_fn_t) cmp, NULL);                                                      
}
其中__compar_fn_t就是 int (*)(const void *, const void *)类型的函数指针，__compar_d_fn_t则是 int (*)(const void *, const void *, void *)类型的函数指针(为什么还有个void *呢?很神奇~求解)。

qsort_r函数也在msort.c中，约164行起。为了榨干CPU的性能，写了很多代码来优化效率，其流程大致是：

1. 判断额外所需内存大小，如果很小(


Generated by Bo-blog 2.1.0