标签： Libc

2011年13月32日24点60分60秒

这是一个测试时候发现的问题，2011 年 13 月 32 日 24 点 60 分 60 秒，这个时间存在吗？

我觉得这应该是个错误的时间，但很不幸地是，如果往 struct tm 中填入这个时间，mktime() 时并不会报错。下面是一段简单的测试代码：

#include <stdio.h>
#include <string.h>
#include <time.h>

int main()
{
    struct tm t;
    memset(&t, 0, sizeof(t));
    t.tm_year = 2011-1900;
    t.tm_mon = 13-1;
    t.tm_mday = 32;
    t.tm_hour = 24;
    t.tm_min = 60;
    t.tm_sec = 60;
    printf("tm_mon=%d, tm_mday=%d, tm_hour=%d, tm_min=%d, tm_sec=%d\n",
            t.tm_mon, t.tm_mday, t.tm_hour, t.tm_min, t.tm_sec);
    time_t tt = mktime(&t);
    printf("%s", ctime(&tt));
    printf("tm_mon=%d, tm_mday=%d, tm_hour=%d, tm_min=%d, tm_sec=%d\n",
            t.tm_mon, t.tm_mday, t.tm_hour, t.tm_min, t.tm_sec);
}

这个程序执行的结果是：

$ ./a.out  
tm_mon=12, tm_mday=32, tm_hour=24, tm_min=60, tm_sec=60
Thu Feb  2 01:01:00 2012
tm_mon=1, tm_mday=2, tm_hour=1, tm_min=1, tm_sec=0

查看 man mktime，的确有对这个特性的解释：

...if structure members are outside their valid interval, they will be normalized
 (so that, for example,  40  October  is  changed into  9  November);...

这就意味着，对输入时间做严格的检查无法依赖于标准库中的 mktime() 函数，只能自己来进行。这应该也是 date 命令曾经改进过的地方。

$ date -d "2011-13-32" # date (coreutils) 5.2.1
Wed Feb  1 00:00:00 CST 2012
$ date -d "2011-13-32" # date (GNU coreutils) 8.5
date: invalid date `2011-13-32'

Cygwin GCC qsort 函数错误（续）

上一篇文章中提到我在为 qsort 写 compare 函数时犯了一个愚蠢的错误：我脑袋陷入了一个错误的逻辑，以为 compare 函数嘛，就是要 compare 一下，那么我用 '>' 或者 '< ' 这种比较算符就可以满足要求（潜意识里认为 > 会返回 1 或者 -1，显然是错的，上篇文章的评论者 Stephen 开始也犯了同样的直觉错误，不过他马上就醒悟过来了）。我当时脑袋里也犹豫了一下要不要处理相等的情况，后来想快排算法中没有判断相等的情况，那么我没必要加上等号。

这个错误直接导致了快排算法失效。

但是为什么在 Linux 下的 gcc 可以输出正确的排序结果呢？我想了很久，最终还是把 glibc 的代码看了一下，才发现，原来当数组规模比较小时时（数组大小小于物理内存的四分之一），glibc 的 qsort 其实不使用 quick sort(_quicksort)，而是使用 merge sort(msort_with_tmp)。而且在 msort_with_tmp 中，对 compare 的处理是比较其返回值是否 <=0，这样排序的结果就是正确的了。[1]

事实上最简单的快排算法是只使用 '<' 号或者 '<='的，比如 Wikipedia 上给出的快排算法，那么我们的 compare 只返回 -1 和 0 行吗？这取决于实现，比如对快排算法的优化中有一个就是对数组中有大量相等元素情况下的优化，其中一种实现 Three-way partition， 就需要使用到三种情况：大于、小于或等于。原始的快排 partition 是将数组按照与 pivot 的比较分为两段，Three-way partition 则是将数组分为三段，中间增加一段与 pivot 值相等的子数组。C 玩具代码的实现如下：

void qsort_3way(int a[], int lo, int hi)
{
  if (hi <= lo) return;
  int lt = lo, gt = hi, i = lt;
  int v = a[lo], t;
  while (i <= gt) {
    if (a[i] < v) {
      t = a[i]; a[i] = a[lt]; a[lt] = t;
      ++i; ++lt;
    } else if (a[i] > v) {
      t = a[i]; a[i] = a[gt]; a[gt] = t;
      --gt;  
    } else i++;
  }
  qsort_3way(a, lo, lt - 1);
  qsort_3way(a, gt + 1, hi);
}

但是 '<' 和 '>' 真的都需要吗？理论上来讲，'>' 是不需要的，我们显然可以将 a[i] > v 改成 v < a[i]。这也是 C++ 里面做的，C++ 中的 sort 函数只需要类重载 '< ' 运算符。但是 C 中并没有这种约定，我们不能预设 qsort 如何拿 compare() 的返回值与 0 比较。因此让 compare() 按照 C 的约定，返回大于、小于和等于 0 的三种情况是绝对正确的而且必要的。

我了解了正确的结果怎么得来的，但是我仍然不知道错误的结果是怎么得来的。看起来 Cygwin 使用的 libc 中没有采取类似 Linux 下 gcc 的策略（比如无法取到物理内存大小？）。quick sort 算法有很多优化的技巧和实现：有的使用 '< ' 符号比较，有的在分支数组足够小时采用插入排序，有的同时使用 '<', '> 两个符号，有的随机取 pivot，有的取三点中值作为 pivot。[2] 没有看到代码和调试，很难判断 Cygwin 的 libc 使用了什么算法（当然，尝试分析不同的输入输出是可以得到规律的，比密码分析还是要简单一些）。

[1] glibc/stdlib/msort.c.
[2] Jon Bentley and M. Douglas McIlroy, "Engineering a sort function", Software - Practice and Experience, Vol. 23 (11), 1249-1265, 1993.