4 ms·
Bit of a tangent but, I don't know if a segfault should be considered a consequence of a "naive" implementation. Seems more like a consequence of a broken one.
by lamacase 12y ago
Bit of a tangent but, I don't know if a segfault should be considered a consequence of a "naive" implementation. Seems more like a consequence of a broken one.
A simple if (!A) goto err_free; would turn that segfault into a "Failed to parse file"
Also, it looks like qsort is implemented on his system as qsort_r:
http://osxr.org/glibc/source/stdlib/msort.c
Qsort_r appears to allocate O(n) extra memory when the data fits into 1/4 of physical memory. The comments suggest that the regular qsort is slower.
- dzeban 12y agoI guess, you're right - for naive implementation it should fall with error, not a segfault. Maybe I just add a check for realloc result. As for qsort implementation - I was confused by glibc sources ;-) What I've found was a slow but in-place implementation, and what you've shown me is an actual implementation that invokes an in-place variant when allocation was failed: tmp = malloc (size); __set_errno (save); if (tmp == NULL) { /* Couldn't get space, so use the slower algorithm that doesn't need a temporary array. */ _quicksort (b, n, s, cmp, arg); return; } Thanks for feedback!