helloxiaoli2
2021-09-11 17:02
采纳率: 50%
浏览 27

Leetcode56 合并区间, 线上执行时报heap-buffer-overflow


#define BASESIZE 20
#define INCREASE 50

int partition(int *nums, int low, int high)
{
    int i=low;
    int j=high;
    int pivot[2]={ nums[i], nums[i+1] };

    while(i<j) {
        while(i<j && nums[j]>=pivot[0]) j-=2;
        nums[i]=nums[j];
        nums[i+1]=nums[j+1];

        while(i<j && nums[i]<=pivot[0]) i+=2;
        nums[j]=nums[i];
        nums[j+1]=nums[i+1];
    }
    nums[i]=pivot[0];
    nums[i+1]=pivot[1];
    assert(i==j);

    return i;
}

void quickSort(int *nums, int low, int high)
{
    if(low<high) {
        int loc=partition(nums, low, high);
        quickSort(nums, low, loc-2);
        quickSort(nums, loc+2, high);
    }
}

int** merge(int** intervals, int intervalsSize, int* intervalsColSize, int* returnSize, int** returnColumnSizes){
    int **ret=NULL;
    *returnSize=0;

    if(intervalsSize==1) {
        (*returnSize)++;
        *returnColumnSizes=malloc(sizeof(int)*(*returnSize));
        if(!(*returnColumnSizes)) exit(-1);
        (*returnColumnSizes)[0]=2;
        return intervals;
    }
    
    quickSort(*intervals, 0, (intervalsSize-1)*2);

    (*returnSize)++;
    int *tmp=malloc(sizeof(int)*2);
    if(!tmp) exit(-1);
    tmp[0]=(*intervals)[0];
    tmp[1]=(*intervals)[1];

    int size=BASESIZE;
    ret=malloc(sizeof(int*)*size);
    if(!ret) exit(-1);
    ret[*returnSize-1]=tmp;

    int *preS=&ret[0][0]; 
    int *preE=preS+1;
    int *nextS=*intervals+2; 
    int *nextE=nextS+1;

    while(nextS<*intervals+2*intervalsSize-1) {
        assert(*preS<=*preE && *nextS<=*nextE);

        if(*preE<*nextS) {
            // 1. insert, change the size if need
            (*returnSize)++;
            if(*returnSize>size) {
                size+=INCREASE;
                int **old=ret;
                ret=realloc(ret, sizeof(int*)*size);
                if(!ret) exit(-1);
                assert(ret!=old);
            }

            tmp=malloc(sizeof(int)*2);
            if(!tmp) exit(-1);
            tmp[0]=*nextS; 
            tmp[1]=*nextE;

            ret[*returnSize-1]=tmp;

            // 2. move
            preS=&ret[*returnSize-1][0];
            preE=preS+1;
        } else if(*preE>=*nextS && *preE<=*nextE) {
            ret[*returnSize-1][1]=*nextE;
        } else if(*preE>=*nextE) {

        }

        nextS=nextS+2;
        nextE=nextS+1;
    }

    assert(*returnSize>=1);
    *returnColumnSizes=malloc(sizeof(int)*(*returnSize));
    if(!(*returnColumnSizes)) exit(-1);
    int i;
    for(i=0; i<*returnSize; i++) (*returnColumnSizes)[i]=2;

    return ret;
}

本地 gcc -O -g -fsanitize leetcode56.c, 再执行没问题。但是,线上执行时,老是报heap-buffer-overflow。

=================================================================
==42==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x602000000038 at pc 0x5630ea5d1af3 bp 0x7ffc1943e400 sp 0x7ffc1943e3f0
READ of size 4 at 0x602000000038 thread T0
    #2 0x7fd03662a0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
0x602000000038 is located 0 bytes to the right of 8-byte region [0x602000000030,0x602000000038)
allocated by thread T0 here:
    #0 0x7fd03726fbc8 in malloc (/lib/x86_64-linux-gnu/libasan.so.5+0x10dbc8)
    #4 0x7fd03662a0b2 in __libc_start_main (/lib/x86_64-linux-gnu/libc.so.6+0x270b2)
Shadow bytes around the buggy address:
  0x0c047fff7fb0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fc0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fd0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7fe0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
  0x0c047fff7ff0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
=>0x0c047fff8000: fa fa 00 00 fa fa 00[fa]fa fa 00 fa fa fa 00 fa
  0x0c047fff8010: fa fa 00 fa fa fa 00 fa fa fa fa fa fa fa fa fa
  0x0c047fff8020: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8030: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8040: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
  0x0c047fff8050: fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa fa
Shadow byte legend (one shadow byte represents 8 application bytes):
  Addressable:           00
  Partially addressable: 01 02 03 04 05 06 07 
  Heap left redzone:       fa
  Freed heap region:       fd
  Stack left redzone:      f1
  Stack mid redzone:       f2
  Stack right redzone:     f3
  Stack after return:      f5
  Stack use after scope:   f8
  Global redzone:          f9
  Global init order:       f6
  Poisoned by user:        f7
  Container overflow:      fc
  Array cookie:            ac
  Intra object redzone:    bb
  ASan internal:           fe
  Left alloca redzone:     ca
  Right alloca redzone:    cb
  Shadow gap:              cc
==42==ABORTING

  • 好问题 提建议
  • 收藏

2条回答 默认 最新

  • helloxiaoli2 2021-09-12 16:15
    已采纳

    参数理解错误。intervals的存储不是一维的。打印所有区间就可以明白。

    已采纳该答案
    评论
    解决 无用
    打赏 举报
  • 查看更多回答(1条)

相关推荐 更多相似问题