C: qsort 对结构体的 unsigned long long 成员进行排序时出现问题

Question

当无符号长整型是结构的一部分时，C 的 Qsort 算法不会对它们进行排序，这应该不重要。代码如下:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <errno.h>

typedef struct TextData {
  char catalog,  // The catalog code.
       txt[137]; // The text for this object.
  short mv;      // mv * 100.
  unsigned long long indx; // Hash of 2D position.
} txtD;          // 152 bytes.

// The comparison function required by qsort for txtD items.
int cmpTdata(const void *a,
             const void *b) {
  txtD *dataA = (txtD*) a;
  txtD *dataB = (txtD*) b;
  if ((dataB->indx - dataA->indx) < 0) { return 1; }
  else if ((dataB->indx - dataA->indx) > 0) { return -1; }
  else { return 0; }
}

int main(int argc, char** argv) {
  FILE *UNSORTED = fopen("/top/middle/directory/filename", "r");
  if (UNSORTED == NULL) {
    printf("Filename not opened for reading!\n");
    exit(0);
  }

  int stat = fseek(UNSORTED, 0L, SEEK_END);
  if (stat != 0) {
     printf("Fseek on failed to find the end! because %s.\n", strerror(errno));
     exit(0);
  }

  unsigned long long size = ftell(UNSORTED);
  if ((size == 0) && (errno != 0)) {
     printf("Error %d) Ftell is 0! because %s.\n",
            errno, strerror(errno));
     exit(0);
  }

  fclose(UNSORTED);

  int nrItems = size / sizeof(txtD);

  txtD *data = (txtD*) malloc(nrItems * sizeof(txtD));
  if (data == NULL) {
    printf("txtD structure not allocated because:\n%s.\n",
           strerror(errno));
    exit(0);
  }

  // Sort it in order of increasing indx.
  qsort(data, nrItems, sizeof(txtD), cmpTdata);

  // Save the sorted items using fopen and fwrite. I'll spare you the details.
}

这是一个简单读取结构并记录错误的程序的输出:

Item 2) previous index 466715 greater than t.indx 449261!
Item 4) previous index 464265 greater than t.indx 404184!
Item 5) previous index 404184 greater than t.indx 353788!
Item 7) previous index 446334 greater than t.indx 361489!
Item 8) previous index 361489 greater than t.indx 328323!
Item 10) previous index 487465 greater than t.indx 343185!
Item 12) previous index 494247 greater than t.indx 428224!
Item 14) previous index 478868 greater than t.indx 130860!
Item 16) previous index 444180 greater than t.indx 339954!
Item 18) previous index 342195 greater than t.indx 281552!
Item 20) previous index 394250 greater than t.indx 370791!
Item 22) previous index 458202 greater than t.indx 311406!
Item 23) previous index 311406 greater than t.indx 280793!
Item 25) previous index 466171 greater than t.indx 424598!
Item 27) previous index 467144 greater than t.indx 431265!
Item 29) previous index 472449 greater than t.indx 198109!
Item 31) previous index 469376 greater than t.indx 451215!
Item 33) previous index 453004 greater than t.indx 427448!
Item 34) previous index 427448 greater than t.indx 374260!
Item 37) previous index 447735 greater than t.indx 336330!

检查了41项，有21个错误。

顺便说一句，责备我没有使用 stderr 或其他风格上的违规行为是没有帮助的。为什么 qsort 不排序是。另请注意，当我对 double 进行排序时，函数 cmpTdata 对于其他结构也可以正常工作。

TIA!

Answer 1

function cmpTdata works fine for other structures when I'm sorting doubles.

double 数学与无符号 数学不同。以下内容永远不会成立，因为无符号永远不会小于 0。

if ((dataB->indx - dataA->indx) < 0) { return 1; }

这意味着代码不是用会发出警告的良好编译器编译的。所以最大的问题不是“算错了”，而是没有使用手边的工具。最好启用所有警告。

foo.c:9:35: warning: comparison of unsigned expression < 0 is always false [-Wtype-limits]

<小时/>

推荐 C 比较习惯用法 - 被各种编译器识别以生成高效的代码。

int cmpTdata(const void *a, const void *b) {
  const txtD *dataA = (txtD*) a;
  const txtD *dataB = (txtD*) b;
  return (dataA->indx > dataB->indx) - (dataA->indx < dataB->indx);
}