所以我一直在尝试在C中创建一个通用的递归快速排序实现。为了使其通用，我使用了一个比较函数指针。此外，由于我们可以使用Lomuto或Hoare分区，我使用了一个指向两个独立函数的函数指针，每个分区一个。现在我只完成了洛穆托的部分。当然，比较函数并没有用在quicksort函数本身，而是用在分区函数上，所以我传递函数指针。应该很简单，但我迫切需要一些帮助，因为我在尝试调用函数时一直遇到分段错误
quicksort_recursive(array, 0, 8, sizeof(int), &cmpnum, &partition_lomuto);
这是比较功能：
int cmpnum(const void* s1, const void* s2)
{
int *a = (int*)s1;
int *b = (int*)s2;
if ((*a) > (*b))
return 1;
else if ((*a) < (*b))
return -1;
else
return 0;
}
这是阵列：
int array[] = [3, 7, 8, 5, 2, 1, 9, 5, 4];
罪犯就在这里：
void swap(void *a, void *b, size_t size)
{
char buffer[size];
memcpy(buffer, a, size);
memcpy(a, b, size);
memcpy(b, buffer, size);
return;
}
void *get(void *const array, size_t index, size_t size)
{
return ((char *)array) + (index * size);
}
size_t partition_lomuto(void *const array, size_t low, size_t high, size_t size, __compar_fn_t compare)
{
void *pivot = get(array, high, size);
size_t i = low;
for (size_t j = low; j <= high - 1; j++)
{
if(compare(get(array, j, size), pivot) <= 0)
{
i++;
swap(get(array, i, size), get(array, j, size), size);
}
}
swap(get(array, i + 1, size), get(array, high, size), size);
return (i + 1);
}
void quicksort_recursive(void *const array, size_t low, size_t high, size_t size, __compar_fn_t compare, size_t (*partition)(void *const array, size_t low, size_t high, size_t size, __compar_fn_t compare))
{
if (low < high)
{
size_t partition_index = partition(array, low, high, size, compare);
quicksort_recursive(array, low, partition_index - 1, size, compare, partition);
quicksort_recursive(array, low, partition_index + 1, size, compare, partition);
}
return;
}
使用gcc -fsanitize=address ...构建程序并运行它会导致以下错误：
=================================================================
==89==ERROR: AddressSanitizer: stack-buffer-overflow on address 0x7fff14f51124 at pc 0x7f766a029dd3 bp 0x7fff14f50f10 sp 0x7fff14f506c0
READ of size 4 at 0x7fff14f51124 thread T0
#0 0x7f766a029dd2 in __interceptor_memcpy (/lib64/libasan.so.6+0x39dd2)
#1 0x401381 in swap /tmp/t.c:19
#2 0x401527 in partition_lomuto /tmp/t.c:44
#3 0x401584 in quicksort_recursive /tmp/t.c:52
#4 0x4018e0 in main /tmp/t.c:64
#5 0x7f7669e4d1e1 in __libc_start_main (/lib64/libc.so.6+0x281e1)
#6 0x4010dd in _start (/tmp/a.out+0x4010dd)
Address 0x7fff14f51124 is located in stack of thread T0 at offset 84 in frame
#0 0x4015fc in main /tmp/t.c:60
This frame has 1 object(s):
[48, 84) 'array' (line 61) <== Memory access at offset 84 overflows this variable
HINT: this may be a false positive if your program uses some custom stack unwind mechanism, swapcontext or vfork
(longjmp and C++ exceptions *are* supported)
SUMMARY: AddressSanitizer: stack-buffer-overflow (/lib64/libasan.so.6+0x39dd2) in __interceptor_memcpy
Shadow bytes around the buggy address:
0x1000629e21d0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e21e0: 00 00 00 00 ca ca ca ca 04 cb cb cb cb cb cb cb
0x1000629e21f0: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e2200: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e2210: 00 00 00 00 00 00 00 00 00 00 f1 f1 f1 f1 f1 f1
=>0x1000629e2220: 00 00 00 00[04]f3 f3 f3 f3 f3 00 00 00 00 00 00
0x1000629e2230: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e2240: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e2250: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e2260: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
0x1000629e2270: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00
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
==89==ABORTING
看起来错误在这里：
swap(get(array, i + 1, size), get(array, high, size), size);
虽然你知道i <= high，i + 1可能会出界。
附言：您有low和high作为(包括((闭合(区间。If通常更容易推理使用半开区间的算法。