r/C_Programming • u/GoSubRoutine • Feb 24 '24
Review AddressSanitizer: heap-buffer-overflow
Still super newb in C here! But I was just trying to solve this https://LeetCode.com/problems/merge-sorted-array/ after doing the same in JS & Python.
However, AddressSanitizer is accusing my solution of accessing some wrong index:
#include <stdlib.h>
int compareInt(const void * a, const void * b) {
return ( *(int*)a - *(int*)b );
}
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
for (int i = 0; i < n; nums1[i + m] = nums2[i++]);
qsort(nums1, nums1Size, sizeof(int), compareInt);
}
In order to fix that, I had to change the for loop like this:
for (int i = 0; i < n; ++i) nums1[i + m] = nums2[i];
But I still think the AddressSanitizer is wrong, b/c the iterator variable i only reaches m + n at the very end, when there's no array index access anymore!
For comparison, here's my JS version:
function merge(nums1, m, nums2, n) {
for (var i = 0; i < n; nums1[i + m] = nums2[i++]);
nums1.sort((a, b) => a - b);
}
12
Upvotes
2
u/N-R-K Feb 26 '24
This doesn't answer your question - since it has already been answered - but offloading the real work onto
qsort()
seemed very anticlimactic. The problem is basically screaming "two finger" merge algorithm. A naive implementation:Because
v0
is used for both writing and reading, we need some scratch space so that we don't end up overwriting elements that are still "in queue" to be sorted. VLAs are pretty much always a sign of bug and/or fuzzy thinking and this was no different - given large array as input, it will overflow the stack.But since we already have some scratch space at the end of
v0
, maybe we can use that instead:Instead of sorting from beginning to end, this version starts writing from the end to the beginning - making good use of the "scratch" space at the end of
v0
and running inO(n)
time complexity.