c - 具有比较功能的合并排序 - 核心转储

Question

您好，我正在使用比较函数运行合并短路，这会导致核心转储故障并出现以下错误:

part1 21 shortbooks.txt
*** glibc detected *** part1: free(): invalid next size (fast): 0x0867b258 ***
======= Backtrace: =========
/lib/libc.so.6[0x409fb6]
part1[0x80489c6]
part1[0x80487fb]
part1[0x80487fb]
part1[0x80487fb]
part1[0x8048ac9]
part1[0x8048d41]
/lib/libc.so.6(__libc_start_main+0xe6)[0x3b1e36]
part1[0x8048561]
======= Memory map: ========
00376000-00393000 r-xp 00000000 fd:00 1311353    /lib/ld-2.13.so
00393000-00394000 r--p 0001c000 fd:00 1311353    /lib/ld-2.13.so
00394000-00395000 rw-p 0001d000 fd:00 1311353    /lib/ld-2.13.so
0039b000-0051e000 r-xp 00000000 fd:00 1311360    /lib/libc-2.13.so
0051e000-0051f000 ---p 00183000 fd:00 1311360    /lib/libc-2.13.so
0051f000-00521000 r--p 00183000 fd:00 1311360    /lib/libc-2.13.so
00521000-00522000 rw-p 00185000 fd:00 1311360    /lib/libc-2.13.so
00522000-00525000 rw-p 00000000 00:00 0
00577000-00593000 r-xp 00000000 fd:00 1345987    /lib/libgcc_s-4.5.1-20100924.so.1
00593000-00594000 rw-p 0001b000 fd:00 1345987    /lib/libgcc_s-4.5.1-20100924.so.1
008e6000-008e7000 r-xp 00000000 00:00 0          [vdso]
08048000-08049000 r-xp 00000000 00:19 435651043  /home/S10/rowlanj0/COMP26120/ex7/part1
08049000-0804a000 rw-p 00001000 00:19 435651043  /home/S10/rowlanj0/COMP26120/ex7/part1
0867b000-0869c000 rw-p 00000000 00:00 0          [heap]
b783b000-b783c000 rw-p 00000000 00:00 0
b7867000-b7868000 rw-p 00000000 00:00 0
bfb25000-bfb49000 rw-p 00000000 00:00 0          [stack]
Aborted (core dumped)

有人可以建议可能导致此错误的原因以及如何解决它吗？

void memcopy(B *to, B *from, int count ) {

  while ( count-- > 0 ) *to++ = *from++ ;

}

void merge_sort(B* book, int n, int elementsize, int (*p_cmp_f)( ) )  {

B *firsthalf, *endoffirsthalf, *secondhalf, *endofsecondhalf, *resultbuffer, *p_result;

int halfsize ;

if (n <= 1 ) return ;

halfsize = n / 2 ;

firsthalf = book ;

secondhalf = book + halfsize * elementsize ;

merge_sort( firsthalf, halfsize, elementsize, p_cmp_f ) ;
merge_sort( secondhalf, n - halfsize, elementsize, p_cmp_f ) ;

endoffirsthalf = secondhalf ;

endofsecondhalf = book + n * elementsize ;

resultbuffer = (B*) malloc( n * elementsize ) ;

p_result = resultbuffer ;

while( firsthalf < endoffirsthalf && secondhalf < endofsecondhalf ) {

  if( (*p_cmp_f)( firsthalf, secondhalf ) < 0 ) {

    memcopy( p_result, firsthalf, elementsize ) ;
    firsthalf += elementsize ;

  }

  else {

    memcopy( p_result, secondhalf, elementsize ) ;
    secondhalf += elementsize ;

  }

  p_result += elementsize ;

}

while( firsthalf < endoffirsthalf ) {

  memcopy( p_result, firsthalf, elementsize ) ;
  firsthalf += elementsize ;
  p_result += elementsize ;

}

while( secondhalf < endofsecondhalf ) {

  memcopy( p_result, secondhalf, elementsize ) ;
  secondhalf += elementsize ;
  p_result += elementsize ;

}

  memcopy( book, resultbuffer, n * elementsize ) ;

  free(resultbuffer) ;

}

这是请求的代码。

这是结构体和比较函数之一:

 typedef struct book{
 double rating;
 double price;
 double relevance;
 int ID;
 }B;

和比较函数:

int comp_on_price(const void *a, const void *b)
{

if ((*(B *)a).price < (*(B *)b).price)
  return 1;
else if ((*(B *)a).price > (*(B *)b).price)
  return -1;
else
  return 0;
}

Answer 1

您收到此错误是因为您的程序正在破坏内部堆数据结构。这可能是一个很难追踪的问题，因为直到损坏发生很长时间后才可能检测到该问题。

一些常见原因是:

• 释放指针两次
• 释放未使用 malloc 分配的指针
• 缓冲区溢出:从使用 malloc 分配的缓冲区的任一端写入数据。

我不知道这是否是您问题的根本原因，但我确实注意到指针算术中的一些错误。

secondhalf = book + halfsize * elementsize ;

在下面的示例中，您不需要乘以 elementsize。当添加整数和指针时，编译器会自动执行此操作；它将假设elementsize == sizeof(B)。如果此假设无效，请在进行加法(与乘法)之前将 book 转换为 (char*)。这将始终有效，因为根据定义 sizeof(char) == 1。

如果您的程序很小，您可以尝试使用 Valgrind 来追踪任何问题。 Valgrind 致力于查找内存问题，例如堆损坏、泄漏和 undefined variable 的使用。但速度非常慢，因此不适用于长时间运行的程序。